ENCODING DAN DECODING KODE HAMMING SEBAGAI KODE TAK SIKLIK DAN SEBAGAI KODE SIKLIK Lilik Hardianti, Loeky Haryanto, Nur Erawaty
Abstrak Kode linear biner [n, k, d] adalah sebuah subruang vektor C ⊆ GF(2n) berdimensi k di mana bobot terkecil dari vektor-vektor kodenya adalah d. Matriks perentang G dari kode C adalah matriks berukuran k × n yang k baris-barisnya adalah k vektor-vektor kode di dalam C yang saling bebas linear. Proses encoding kode C dimodelkan secara matematis sebagai hasil kali antara vektor v ∈ GF(2k) dengan matriks generator G. Hasil encoding vektor v adalah vektor kode c = vG ∈ C. Dual dari kode C adalah subruang vektor C⊥ ⊆ GF(2n) berdimensi n − k yang berisi vektor-vektor yang tegak lurus pada semua vektor-vektor kode di dalam C. Subruang C⊥ direntang oleh matriks cek paritas H dari kode C. Untuk setiap m ≥ 1, kode Hamming Hm ⊆ GF(2n), dimana n = 2m − 1; didefinisikan sebagai subruang vektor berdimensi k = n − m yang memenuhi syarat: n kolom-kolom matriks cek paritasnya bisa dipilih sebagai penyajian biner dari bilangan 1, 2, …, 2m − 1 secara berururtan. Akibatnya, Hm adalah sebuah kode [2m − 1, 2m − m − 1, 3]. Dekoding kode Hm dimodelkan secara matematis melalui perhitungan sindrom S(v) = HvT terhadap vektor v ∈ GF(2n). Jika S(v) ≠ 0, maka penyajian basis 10 (desimal) dari S(v) menyatakan posisi bit dalam v yang harus dikoreksi. Dalam notasi polinom, sebuah kode siklik dimodelkan secara aljabar sebagai ideal utama
⊆ GF(2n)[x]/<xn − 1>. Jika n = 2m − 1 dan polinom generator g(x) dari ideal dipilih sama dengan salah satu polinom minimal berderajat m untuk suatu unsur primitif α atas GF(2), maka ideal utama tersebut menyajikan kode siklik yang ekuivalen dengan kode Hamming Hm. Kata kunci: Kode Hamming, Kode Siklik, Matriks Pembangun, Matriks Cek Paritas
Abstract A binary linear code [n, k, d] is a k-dimension subspace C ⊆ GF(2n) in which d is the minimum weight of its codewords. The generator matrix of C is a k × n matrix whose k rows are any k independent codewords of C. Encoding the code C is modeled mathematically as matrix multiplication between v ∈ GF(2k) and the generator matrix G of C. The encoded word of v is a codeword c = vG ∈ C. The dual of C is a (n − k)-dimension subspace C⊥ ⊆ GF(2n) whose elements are all vectors perpendicular to all codewords in C. C⊥ is generated by the parity-check matrix H of C. For every m ≥ 1, the Hamming code Hm ⊆ GF(2n), where n = 2m − 1; is defined as a (n − m)dimension subspace sastifying the following condition: the n binary column vectors of its parity check matrix can be chosen to represent the integers 1, 2, …, 2m − 1 consecutively. Accordingly, Hm is an [2m − 1, 2m − m − 1, 3]-code. Decoding Hm is mathematically modeled as computing the syndrome S(v) = HvT of v ∈ GF(2n). If S(v) ≠ 0, then the decimal representation of S(v) associated to the corrupted bit position of v. In polynomial notation, a cyclic code is modeled algebraically as a prime ideal ⊆ GF(2n)[x]/<xn − 1>. If n = 2m − 1 and the polynomial generator g(x) is chosen as mdegree minimal polynomial for a primitive element α over GF(2), then the prime ideal represents a cyclic code equivalent to the Hamming code Hm. Keywords: Hamming Code, Cyclic Code, Generator Matrix, Parity Check Matrix 1. Pendahuluan Ide dasar dari teori kode pengoreksi kesalahan adalah memberi sedikit tambahan data (redundansi) terhadap pesan asli. Setiap data bisa dinyatakan sebagai kumpulan vektor-vektor biner. Redundansi pada pesan asli v (sebagai vektor biner) berupa untaian biner dengan panjang k ditambahkan oleh enkoder dan pesan c (yang telah diberi redudansi sehingga menjadi untaian biner dengan panjang n > k) dinamakan kata kode (codeword).
Pada Gambar 1.1, diilustrasikan bagaimana error-correcting codes bekerja pada pengiriman data. Sumber pesan
Enkoder
Kanal (Noise)
Dekoder
Pesan diterima
Gambar 1.1 ilustrasi error-correcting codes. Dalam komunikasi dan pemrosesan informasi, pengkodean (encoding) adalah proses konversi informasi dari suatu sumber menjadi data, yang selanjutnya dikirimkan ke penerima. Pengawakodean (decoding) adalah proses kebalikannya, yaitu konversi data yang telah dikirimkan oleh sumber pesan menjadi informasi yang dimengerti oleh penerima. Salah satu jenis kode yang banyak digunakan adalah kode siklik. Himpunan C yang berunsurkan vektor-vektor biner disebut kode siklik jika memenuhi sifat: Untuk setiap c0c1 ...cn−1cn ∈ C berlaku cnc0c1 ...cn−1 ∈ C. Beberapa kode yang lebih dahulu berkembang sebelum teori kode siklik dipelajari dan berkembang ternyata kemudian bisa dibuktikan ekuivalen dengan salah satu kode siklik. Beberapa di antara kode siklik tersebut antara lain kode Hamming dan sebagian dari bit-bit kode Golay. Kode Hamming dikenalkan oleh Richard Hamming (1950) sebagai kode tunggal pengoreksi kesalahan (single error-correcting code) 2. Teori-Teori Pendukung Salah satu konsep aljabar terpenting di dalam teori kode pengoreksi kesalahan adalah konsep ideal. Ideal di dalam suatu gelanggang G didefinisikan sebagai suatu himpunan I ⊆ G yang memenuhi sifat: untuk setiap x ∈ G dan a ∈ I berlaku ax ∈ I (sehingga dari asumsi sifat komutatif gelanggang, xa ∈ I). Sebuah ideal disebut ideal utama (prime ideal) jika terdapat sebuah g ∈ I sedemikian hingga untuk setiap a ∈ I, terdapat x ∈ G sedemikian hingga a = xg. Fakta ini biasa dilambangkan sebagai I = atau I = gG (dan I = Gg, karena G diasumsikan komutatif). Jika g = 1, maka mudah dibuktikan bahwa <1> = G. Jika setiap ideal I ⊆ G direntang oleh satu unsur g ∈ G (yaitu I = ), maka G disebut daerah ideal utama (principal ideal domain). Sebuah ideal M ⊆ G disebut ideal maksimal jika untuk setiap ideal I ⊆ G berlaku implikasi: jika M ≤ I ≤ G maka I = M atau I = G. Dalam aplikasi, daerah integral yang terpenting adalah F[x], di mana F adalah lapangan. A. Lapangan Hingga (Finite Field) Lapangan hingga F selalu memiliki sebanyak q unsur di mana q = pn, untuk suatu bilangan prima p, pada tulisan ini selalu diasumsikan p = 2. F disebut juga lapangan Galois sehingga biasa dilambangkan dengan GF(q). Karena q = 2n, lapangan hingga GF(q) adalah sebuah lapangan perluasan dari lapangan GF(2), artinya GF(2) ⊆ GF(q). Definisi 2.1 (Unsur Primitif) Unsur primitif dari lapangan GF(q) adalah sebuah unsur α sedemikian hingga setiap unsur di dalam lapangan GF(q) kecuali 0 dapat diekspresikan sebagai perpangkatan dari α. B.
Polinom Primitif dan Polinom Minimal Definisi 2.2 (Polinom Primitif) Polinom irreduksi p(x) atas GF(q) adalah polinom primitif atas GF(q) jika terdapat unsur primitif α sedemikian hingga p(α) = 0. Tabel 2.1 Beberapa Polinom primitif di dalam GF(2)[x] m (derajat) p(x), polinom primitif 2 x2 + x +1 3 x3 + x +1, x3 + x2 +1, 4 x4 + x +1 5 x5 + x2+1 (Richard E. Blahut: 2003)
Definisi 2.3 (Polinom Minimal) Misalkan GF(q) adalah lapangan, GF(Q) adalah lapangan perluasan dari GF(q) dan β ∈ GF(Q). Polinom irreduksi m(x) yang memiliki derajat terkecil atas GF(q) dengan m(β) = 0 disebut polinom minimal untuk β atas lapangan GF(q) dan β dikatakan memiliki polinom minimal m(x) atas GF(q). C. Ruang Vektor Pilih lapangan F2 = {0, 1}, unsur-unsurnya disebut bit. Ruang vektor F2 dilengkapi dengan dua operator biner, yaitu operator tambah dan perkalian skalar. Pernyataan W adalah subruang vektor dari V dilambangkan W ≤ V. Telah diketahui bahwa jika F adalah lapangan, maka Fn adalah ruang vektor dari semua vektor dengan panjang n yang unsur-unsurnya merupakan elemen dari F, yaitu: Fn = {(a1, a2, …, an): ai ∈ F}. n Penjumlahan vektor di F menggunakan penjumlahan komponoen-per-komponen unsur-unsur F. Telah diketahui pula bahwa untuk setiap bilangan prima p dan setiap bilangan positif n ≥ 1, terdapat lapangan hingga yang terdiri atas q = pn unsur-unsur. Lapangan ini akan diberi simbol GF(q) atau F q. Dalam aljabar linear, sebuah basis untuk V adalah sebuah subhimpunan tak kosong B = {v1, v2, …, vk } ⊆ V yang memenuhi: 1. B merentang V, yaitu V = , dan 2. B bebas linear. D. Kode Linear Sembarang subhimpunan C ⊆ GF(2n) disebut kode (biner). Kode C ⊆ GF(2n) disebut kode linear jika C ≤ GF(2n). Untuk kode biner, pembuktian suatu himpunan adalah subruang (kode linear) menjadi lebih sederhana. Sesungguhnya, W ≤ GF(2n) jika dan hanya jika untuk setiap v, w ∈ W berlaku v + w ∈ W. Kode linear C dengan panjang n dan berdimensi k didefinisikan sebagai subruang C ⊆ F2n yang berdimensi k. Kode linear C ini disebut kode [n, k]. Jarak minimum kode C didefinisikan dan diberi lambang sebagai d(C) = min {d(u, v) | u, v ∈ C, u ≠ v}. Bobot dari u ∈ C didefinisikan sebagai banyak bit-1 di antara komponen-komponen u dan diberi lambang wt(u). Bisa dibuktikan, d(C) = min {wt(u) | u ∈ C, u ≠ 0}. Jika jarak minimum dari C diketahui, misalnya d = d(C), maka C disebut kode [n, k, d] atau lengkapnya, kode linear-[n, k, d]. Definisi 2.4 Sebuah matriks k × n yang barisnya membentuk basis untuk kode linear [n, k] disebut matriks perentang (generator matrix) untuk kode C. E.
Kode Siklik
Definisi 2.5 Kode linear C [n, k, d] adalah siklik jika untuk setiap (c0, c1, …, cn-1) kata kode (codeword) di dalam C, maka (cn-1, c0, …, cn-2) adalah kata kode juga di dalam C. F.
Kode Hamming
Kode Hamming adalah sebuah kelas dari kode pengoreksi kesalahan (error correcting codes) yang hanya dapat mengoreksi satu kesalahan. Kode Hamming biner mempunyai parameter-parameter sebagai berikut: 1) Panjang kode n = 2m − 1, dengan m ≥ 3
2) Dimensi k = 2m − m − 1 3) Jarak minimum d = 3
3. Pembahasan A. Kode Linear Definisi 3.1 Himpunan bagian C ⊆ GF(2n) yang tidak kosong adalah kode linear jika untuk setiap u, v ∈ C berlaku u + v ∈ C dan au ∈ C, a ∈ GF(2). Setiap unsur c ∈ C disebut vektor kode. Proses pengubahan informasi atau pesan biner dengan panjang k ke dalam bentuk vektor biner dengan panjang n > k disebut sebagai pengkodean (encoding). Encoding dari sebuah pesan u = u1u2 … uk ∈ GF(2k) menjadi vektor kode c ∈ C dilakukan dengan cara mengalikan pesan u dengan matriks generator G k
c = uG =
∑u i =1
i
ri
dimana (r1, r2, ..., rk) adalah baris-baris pada matriks generator G. Jika vektor kode: c = c1c2...cn dikirim dan vektor v = v1v2…vn diterima, maka ē = v − c = e1 e1…en disebut vektor kesalahan. Jika v bukan vektor kode, decoder harus memutuskan, vektor kode c (yang berubah menjadi vektor v) manakah yang dikirim, atau vektor kesalahan ē yang mana terjadi sehingga vektor v diterima dengan kesalahan. B.
Sindrom
Misalkan H adalah matriks cek-paritas dari kode C ⊆ GF(2n) yang berdimensi k. Hasil kali S(v) = H·vT ∈ GF(2n−k) antara sembarang vektor v ∈ GF(2n) dengan matriks cek-paritas H untuk kode C disebut sindrom dari v. Sindrom bisa digunakan untuk mendeteksi adanya kesalahan, bahkan bisa untuk mengkoreksi kesalahan pada kode linear, apabila kode yang digunakan tidak terlalu kompleks. Teorema 3.1 Jika C adalah kode linear dan c ∈ C, maka sindrom dari c adalah vektor nol; dengan kata lain: S(c) = H·cT = 0. Teorema 3.2 Jika C ⊆ GF(2n) dan u, v ∈ GF(2n) maka S(u) = S(v) jika dan hanya jika u − v ∈ C. Akibat Teorema 3.2 Misalkan u ∈ GF(2n). Himpunan semua vektor-vektor v ∈ GF(2n) yang memenuhi kesamaan S(u) = S(v) adalah sebuah koset dari C; persisnya {v ∈ GF(2n) | S(v) = S(u)} = u + C. Hasil di atas bisa diilustrasikan melalui contoh berikut. Contoh 3.1: Pandang kode C = {0000000, 0011011, 1100101, 1111110}. Matriks paritas dari C adalah
1 0 H = 0 1 0
1 0 1 1 1
1 1 1 0 1
1 0 0 1 1
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0
Dari matriks cek-paritas H untuk kode C ini, diturunkan tabel berikut:
32 koset C= 0000010 + C 0000100 + C 0001000 + C … 0011000 + C …
Tabel 3.1 Kode Linear C = {c0, c1, c2, c3} ≤ F27, d(C) = 4. coset leader v0 = e v1 = e + c 1 v2 = e + c 2 v3 = e + c 3 [0000000] [0011011] [1100101] [1111110] [0000010] [0011001] [1100111] [1111100] [0000100] [0011111] [1100001] [1111010] [0001000] [0010011] [1101101] [1110110] … … … … [0011000] [0000011] [1111101] [1100110] … … … …
Sindrom s = HviT [00000]T [11110]T [10101]T [10011]T … [01110]T …
Perhatikan, setiap unsur v ∈ GF(27) yang sebaris dengan coset leader e dan sekolom dengan vektor kode c memenuhi kesamaan v = e + c. Karena c = v – e dan coset leader e dipilih sebagai salah unsur dengan bobot terkecil di dalam koset e + C, maka jarak v dan c adalah jarak minimum di antara semua jarak antara v dengan vektor kode. C. Konstruksi Tak Siklik Kode Hamming Definisi 3.2 Misalkan m ≥ 3. Kode Hamming Hm adalah kode linear yang setiap kolom dari matriks cekparitasnya adalah penyajian biner dari bilangan 1 sampai dengan 2m − 1. Jadi, kode Haming memiliki parameter-parameter: 1) Panjang vektor kode n = 2m − 1 2) Dimensi k = 2m − m − 1 3) Jarak minimum d = 3 Dengan kata lain, kode Hamming Hm adalah kode [2m − 1, 2m − m − 1, 3]. Contoh 3.2: Dengan m = 3, bisa dikonstruksi kode Hamming H3 yang memiliki vektor kode panjang n = 23 − 1. Karena kode Hamming H3 berdimensi k = 23 − 3 − 1 = 4, dualnya, kode H3⊥; berdimensi n − k = n − 4 = 3. Ini berarti H1, matriks cek-paritas kode H3 (atau matriks generator kode H3⊥) berukuran 3 × 7.
0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 . 1 0 1 0 1 0 1 Setiap vektor kode c ∈ H3 memenuhi kesamaan H·cT = 0. Sebagai contoh jika c1 = [0 1 1 0 0 1 1], c2 = [0 0 0 1 1 1 1] maka c1, c2 ∈ H3 sebab memenuhi kesamaan
0 0 0 1 1 1 1 1 0 0 1 1 [0 1 1 0 0 1 1]T = 1 0 1 0 1 0 1
0 0 . 0
0 0 0 1 1 1 1 1 0 0 1 1 [0 0 0 1 1 1 1]T = 1 0 1 0 1 0 1
0 0 . 0
H·c1T = 0 1 dan H·c2T = 0 1
Jadi untuk mendapatkan kode linear C dari matriks cek paritas H ini, cukup dicari sebuah basis dari C yang bisa diperoleh dari bentuk solusi umum SPL homogin HcT = 0, atau c4 + c5 + c6 + c7 = 0, c2 + c3 + c6 + c7 = 0, c1 + c3 + c5 + c7 = 0; Dengan menukarkan baris pertama dengan baris ketiga matriks koefisien SPL, matriks eselon tereduksi yang diperoleh adalah matriks
1 0 1 0 1 0 1 H’ = 0 1 1 0 0 1 1 0 0 0 1 1 1 1 Matriks H’ berbentuk eselon tereduksi dari matriks ini disimpulkan bahwa SPL memiliki peubah bebas c3, c5, c6 dan c7 sehingga peubah utama c1, c2 dan c4 bisa dinyatakan sebagai jumlah dari peubah-peubah bebas: c1 = c3 + c5 + c7, c2 = c3 + c6 + c7, c4 = c5 + c6 + c7. Dengan mengeliminasi ketiga peubah utama, setiap solusi merupakan kombinasi linear dari vektor-vektor basis ruang solusi. Ke-4 vektor basis ini menjadi ke-4 baris dari matriks generator G sehingga setiap solusi (yaitu setiap vektor kode) bisa ditulis dalam bentuk c = vG sebagai berikut
1 1 (c1, c2, c3, c4, c5, c6, c7) = (c3, c5, c6, c7) 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 1
di mana v = (c3, c5, c6, c7) ∈ GF(24). Ini berarti semua vektor kode c ∈ H3 bisa diperoleh dari encoding terhadap semua vektor v ∈ GF(24), yaitu dari hasil kali c = v·G. Pada khususnya kedua vektor kode c1, c2 ∈ C ⊆ GF(27) diperoleh dari vektor v1 = [1 0 0 1] ∈ GF(24) dan v2 = [0 1 1 1] ∈ GF(24) melalui ‘encoding’ dengan menggunakan matriks generator seperti berikut
1 1 c1 = [0 1 1 0 0 1 1] = [1 0 1 1] 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 = v1·G 0 1
1 1 c2= [0 0 0 1 1 1 1] = [0 1 1 1] 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 = v ·G. 0 2 1
dan
Sesungguhnya, H3 = {0000000, 1101001, 0101010, 1000011, 1001100, 0100101, 1100110, 0001111, 1110000, 0011001, 1011010, 0110011, 0111100, 1010101, 0010110, 1111111}. D. Decoding Kode Hamming dengan Sindrom Kode Hamming adalah kode paling banyak digunakan untuk peralatan digital di mana peluang terjadi kesalahan pada lebih dari 1 bit boleh dikatakan nol. Sesungguhnya dengan menggunakan matriks cek-paritas H untuk kode Hamming, jika vektor r diperoleh dari vektor kode dengan satu kesalahan (corrupted) bit, maka nilai desimal (bilangan basis 10) dari sindrom Hr menyatakan posisi bit yang perlu dikoreksi. Contoh 3.3: Misalnya dikirimkan (atau disimpan) data berupa tiga vektor kode c = [0 1 1 0 0 1 1]. Hasil pengiriman (atau pengaksesan) data ini ternyata adalah vektor v = [0 0 1 0 0 1 1]. Dari hasil kali H dengan vT diperoleh sindrom
1 0 1 0 1 0 1 1 0 0 1 1 [0 0 1 0 0 1 1]T = 0 0 0 1 1 1 1
H·vT = 0 1
0 1 ≡ 2 (dalam basis 10) 0
Jadi disimpulkan bahwa vektor v memiliki kesalahan bit pada posisi 2. Dengan demikian, decoder akan merubah bit ke-2 dari vektor v. E.
Kode Siklik
Kode linear C dengan panjang n atas lapangan hingga GF(q) adalah siklik jika untuk setiap vektor kode c = c0c1…cn-1 di dalam C maka vektor c = cn-1c0…cn-2 diperoleh dari cyclic shift (pergeseran siklik) koordinat i → i + 1 (mod n) juga berada di dalam C (juga vektor kode). Jadi, kode siklik memuat semua n pergeseran siklik atas setiap vektor kode. Untuk memeriksa kode siklik C atas lapangan GF(q), setiap kata kode diubah ke dalam bentuk polinom berdasarkan bijeksi antara vektor c = c0c1…cn-1 ∈ GF(qn) dengan polinom c(x) = c0 + c1x + …+ cn-1xn−1 ∈ GF(q)[x]/, di mana q = 2n dan p(x) adalah polinom primitif berderajat n. Jadi dalam bentuk polinom, C adalah kode linear jika hanya jika untuk setiap kata kode c(x) = c0 + c1x + …+ cn-1xn−1 ∈ C maka berlaku xc(x) = cn-1xn + c0x + …+ cn-2xn−1 ∈ C. Agar kode siklik C invariant pada pergeseran siklik sehingga jika c(x) di dalam C, maka xc(x) diberikan dengan perkalian kongruen modulo xn − 1. Ini memberikan kesan bahwa teori yang tepat untuk mempelajari kode siklik adalah teori gelanggang hasil bagi Rn = GF(2)[x] / < xn − 1> Pembahasan di atas menunjukkan bahwa kode siklik adalah ideal dari Rn. Mempelajari kode siklik dalam GF(qn) sama dengan mempelajari kode siklik dalam Rn. Ini bergantung pada faktor xn − 1. Teorema 3.3 Kode linear C’ di dalam GF(qn) adalah siklik jika dan hanya jika C adalah ideal di dalam Rn. F.
Koset Siklotomik
Definisi 3.3 Misalkan n dan p adalah bilangan yang saling prima. Koset siklotomik dari p (p-koset siklotomik) modulo n yang memuat i didefinisikan sebagai berikut Ci = {i·pj mod n) ∈ Zn | j = 0, 1, 2, ..., m − 1} Subhimpunan {i1, i2, ...,it} ⊆ Zn disebut himpunan lengkap yang menyajikan (representasi) koset siklotomik q modulo n jika C i1 , C i2 ,..., C it saling lepas dan
U
t j =1
Ci = Zn. Untuk n = pm − 1, maka j
│Ci│≤ m. Bilangan bulat positif terkecil a sedemikian rupa sehingga qa = 1 mod n disebut order dari q modulo n dan diberi lambang ordn(q). Dalam tulisan ini, q = 2 dan n = 2m − 1 di mana m adalah derajat polinom primitif yang digunakan untuk mengkonstrusi lapangan hingga.
Teorema 3.4 Misalkan n adalah bilangan bulat positif yang relatif prima dengan q. Misalkan t = ordn(q), dan α adalah akar ke-n dari 1 ∈ GF(qt). (i) Untuk setiap bilangan bulat s dengan 0 ≤ s < n, polinom minimal dari αs atas GF(q) ( x − α i ) , dengan Cs adalah koset siklotomik q dari s modulo n. adalah M αs ( x) =
∏ i∈Cs
(ii)
Selanjutnya
( x n − 1) = ∏ M α s ( x ) s
adalah faktorisasi xn − 1 atas GF(q), di mana s berjalan sebagai representasi dari koset siklotomik q modulo n.
Contoh 3.4 Dari koset siklotomik untuk p = 2 dan dengan modulo n = 23− 1 = 7, faktorisasi dari x7 − 1 bisa diperoleh dengan menggunakan α, akar dari polinom primitif x3 + x + 1 sebagai berikut: C0 = {(0⋅2j mod 7) ∈ Zn, j = 0, 1, 2, ...} = {0} ⇒ diperoleh faktor (x − α0) = (x − 1)
C1 = {(1⋅2j mod 7) ∈ Zn, j = 0, 1, 2, ...} = {1, 2, 4} = C2 = C4, ⇒ diperoleh faktor (x − α)(x − α2)(x − α3) = x3 + x + 1 C3 = {(3⋅2j mod 7) ∈ Zn, j = 0, 1, 2, ...} = {3, 5, 6} = C5 = C6 ⇒ diperoleh faktor (x − α3)(x − α5)(x − α6) = x3 + x2 + 1 Himpunan {0, 1, 3} adalah himpunan lengkap dari representasi dari koset siklotomik dari 2 modulo 7. G. Dimensi dan Matriks Paritas Kode Siklik Teorema 3.5 Jika I adalah ideal tak kosong di dalam Rn maka polinom monik tak nol dengan derajat terkecil di di dalam I, namakan g(x); adalah sebuah generator dari I. Dengan kata lain Rn adalah daerah ideal utama. Lebih jauh, g(x) membagi xn - 1. Baris-baris matriks pengecekan paritas dari kode C bisa dinyatakan sebagai
g ( x) xg ( x) H= ... n −k x g ( x) atau jika g(x) = g0 + g1x + … + gn−kxn−k , gi ∈ GF(q); maka g0 0 H= 0
g1 L g n − k g 0 g1 L 0
L
(3.1)
0 gn−k
0 0
g0
g1
0
L g n − k
L L
0 0 M
(3.2).
Teorema 3.6 Misalkan g(x) = g0 + g1x +…+ gn−kxn−k adalah polinom generator dari kode siklik C pada GF(qn) dengan gn−k ≠ 0, maka ekspresi (3.1) dan (3.2) merupakan dua cara penyajian matriks generator kode C ⊆ Rn Contoh 3.5 Diberikan kode siklik biner-[7, 4] dengan polinom generator g(x) = 1 + x + x3. Maka kode ini memiliki matriks generator:
1 0 G= 0 0
1 0 1 0 0 0 g ( x) 1 1 0 1 0 0 xg ( x) ≈ 0 1 1 0 1 0 x 2 g ( x) 0 0 1 1 0 1 x 3 g ( x)
Definisi 3.4 n −1
Misalkan h(x) =
∑h x i=0
i
i
adalah polinom berderajat k (hk ≠0) atas lapangan GF(q), polinom
terbalik (reciprocal polynomial) hR(x) dari h(x) didefinisikan: hR(x) = xkh(x−1) =
n −1
∑h i =0
k −i
xi
Contoh 3.6 Misalkan terdapat polinom h(x) = 1 + 2x + 3x5 + x7 ∈ GF(5)[x], maka hR(x) = x7h(x−1) = x7(1 + 2x−1 + 3x−5 + x−7) = x7 + 2x6 + 3x2 + 1 = 1 + 3x2 + 2x6 + x7
Teorema 3.7 Misalkan C = ⊆ Rn adalah sebuah kode siklik berdimensi k dan xn − 1 = g(x)h(x). Jika h(x) = h0 + h1x + … + hkxk maka generator kode dual C⊥ adalah h0−1hR(x) = h0−1xkh(x−1) = xk + h0−1h1 xk−1 + … + h0−1hk, di mana h0 adalah konstan dari h(x). Definisi 3.5 Jika C adalah kode biner siklik dengan panjang n dan xn − 1 = g(x)h(x), maka h0−1hR(x) disebut polinom cek paritas dari C Akibat Teorema 3.7 Matriks generator untuk kode dual dari C (matriks cek paritas kode C) adalah
hk 0 0
hk −1 hk 0
L h0 0 hk −1 L h0 L
0
hk
0 0 hk −1
0 0 M L h0
L L
Contoh 3.7 Kode-[7, 4, 3] adalah kode yang ekuivalen dengan kode Hamming H3. dengan polinom generator g(x) = 1 + x2 + x3. Jika h(x) = (x7−1)/g(x) = (x7−1)/1 + x2+x3 = 1 + x2+x3 + x4, maka hR = 1 + x +x2 + x4 adalah polinom cek paritas dari kode C sehingga kode ini memiliki matriks cek paritas:
1 1 1 0 1 0 0 H= 0 1 1 1 0 1 0 0 0 1 1 1 0 1 H. Konstruksi Kode Siklik Untuk mengkosntruksi suatu kode siklik, dapat dilihat dari matriks generatornya atau daari penjabaran aljabar polinom generatornya. Teorema 3.8 Kode C ⊆ Rn siklik jika C memenuhi dua kondisi (i) a(x), b(x) ∈ C ⇒ a(x) + b(x) ∈ C (ii) a(x) ∈ C, r(x) ∈ Rn ⇒ r(x)a(x) ∈ C. Contoh 3.8 Misalkan terdapat kode dengan matriks generator yang membangun kode C (7,3) sebagai berikut
1 0 1 1 1 0 0 G= 0 1 0 1 1 1 0 0 0 1 0 1 1 1 memiliki kata kode c1 = 1011100, c2 = 0101110, c3 = 0010111, c1 + c2 = 1110010, c1 + c3 = 1001011 c2 + c3 = 0111001, c1 + c2 + c3 = 1100101. Kode ini siklik karena pergeseran siklik dari baris pertama memberikan semua vektor kode tak nol dari kode linear, c1 → c2 , c2 → c3 , c3 → c1 + c3 , c1 + c3 → c1 + c2 + c3 , c1 + c2 + c3 → c1 + c2 , c1 + c2 → c2 + c3 , c2 + c3 → c1 . Jarak minimum kode adalah 4. Jadi kode ini adalah kode siklik C[7, 3, 4]. Misalkan F2[x] adalah polinom dengan koefisien dari GF(2) dan GF(2)[x]/<x7 − 1> adalah himpunan polinom sisa hasil bagi dari GF(2)[x] oleh x7 − 1. Misalkan g(x) = 1 + x2 + x3 + x4 adalah polinom generator yang membangun kode, yaitu polinom irreduksi berderajat 4 yang membagi x7 − 1. Perhatikan polinom r(x)g(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5 + a6x6, dengan r(x) adalah polinom yang berderajat kurang dari 3.
Selanjutnya polinom hasil kali r(x)g(x) dinyatakan sebagai vektor kode 0⋅g(x) = 0 ≡ (0000000) 1⋅g(x) = 1 + x2 + x3 + x4 ≡ (1011100) x⋅g(x) = x + x3 + x4 + x5 ≡ (0101110) (1 + x)⋅g(x) = 1 + x + x2 + x5 ≡ (1110010) x2⋅g(x) = x2 + x4 + x5 + x6 ≡ (0010111) (1 + x2)⋅g(x) = 1 + x3 + x5 + x6 ≡ (1001011) (x + x2)⋅g(x) = x + x2 + x3 + x6 ≡ (0111001) (1 + x + x2)⋅g(x) = 1 + x + x4 + x6 ≡ (1100101) Secara umum dapat diambil polinom r(x) berderajat i mod (x7 − 1), sehingga
n −1 n−1 n −1 r ( x ) g ( x ) = ∑ ri xi ∑ gi xi ≡ ∑ ci xi mod (x7 − 1) i =0 i =0 i =0 untuk setiap ci ∈ F. I.
Kode Hamming adalah Kode Siklik Perhatikan matriks H = [1
α
α2
αn−1]
...
Selanjutnya tulis setiap unsur αj dalam bentuk polinom derajat < n = pm − 1 kemudian tulis kembali ke bentuk kolom dengan m komponen. Misalkan C adalah kode biner dengan matriks cek paritas H. 1.
2.
H adalah matriks cek paritas dari C jika baris-baris matriks H bebas linear. Untuk menunjukkan H bebas linear, nyatakan setiap αj dalam bentuk kolom biner panjang m. Jadi H adalah matriks m × n. Perhatikan bahwa kolom m pertama dari H berbentuk matriks identitas (αj = 1.αj untuk 0 ≤ j ≤ m − 1) sehingga H berbentuk matriks kolom tereduksi. Akan ditunjukkan bahwa C adalah kode Hamming Karena {αj : 0 ≤ j ≤ n − 1} = {1, α, α2, ..., α 2 − 2 } = GF(2m)\{0} dapat dilihat bahwa kolom-kolom di H semuanya tak nol dengan panjang m sehingga mewakili semua bilangan tak nol (dalam basis 10) dari 1 sampai dengan 2m − 1. Jadi menurut definisi kode Hamming, maka kode C adalah kode Hamming c ∈ C jika dan hanya jika α adalah akar dari polinom kode c(x) = c0 + c1x + ... + cn−1xn−1 yang bersesuaian dengan vektor kode c. Fakta ini bisa diverifikasi karena c ∈ C ⇔ HcT = 0 ⇔ [1 α α2 ... αn−1][ c0 c1 ... cn−1]T = 0 ⇔ c0·1 + c1·α + ... + cn−1·αn−1 = 0 ⇔ c(α) = 0. C adalah kode siklik. Misalkan c ∈ C disajikan sebagai polinom c(x) = c0 + c1x + ... + cn−1xn−1. Misalkan c’ adalah hasil pergeseran siklik dari c yang disajikan sebagai polinom c'(x) ≡ xc(x) mod (xn − 1). Ini berarti c'(x) = xc(x) + a(x)(xn − 1) untuk suatu polinom a(x) ∈ GF(2)[x]. Jadi c'(α) = αc(α) + a(α)(αn − 1). Karena c ∈ C, maka sesuai pembahasan di bagian 3, c(α) = 0. Juga karena α adalah unsur dengan order n, maka αn = 1 dan αn − 1 = 0. Akibatnya c'(α) = αc(α) + a(α)(αn − 1) =α·0 + a(α)·0 = 0 Menurut hasil di bagian 3, c' ∈ C. Jadi C adalah kode siklik. C adalah ideal utama. Akan dibuktikan bahwa terdapat polinom g(x) ∈ F2(x)/<xn − 1> sedemikian hingga setiap polinom kode c(x) = c0 + c1x + ... + cn−1xn−1 yang bersesuaian dengan vektor kode c ∈ C adalah kelipatan dari polinom g(x) tersebut. m
3.
4.
5.
6.
7.
8.
Pilih polinom g(x) sebagai polinom dengan derajat terkecil yang memenuhi g(α) = 0. Pilih sembarang c ∈ C dan misalkan polinom kode c(x) = c0 + c1x + ... + cn−1xn−1 bersesuaian dengan vektor kode c. Berdasarkan algoritma hasil bagi Euclid (dalil sisa), terdapat polinom q(x) dan r(x) sedemikian sehingga c(x) = q(x)g(x) + r(x) dengan r(x) = 0 atau derajat r(x) < derajat g(x). Seandainya, r(x) ≠ 0 maka derajat r(x) < derajat g(x) dan lebih jauh dari sifat tertutup C (terhadap +) r(x) = c(x) − q(x)g(x) = c(x) + q(x)g(x) ∈ C. Menurut hasil di bagian 3, r(α) = 0. Hasil ini kontradiksi dengan definisi g(x) sebagai polinom dengan derajat terendah yang memenuhi g(α) = 0. Jadi r(x) = 0 dan c(x) = q(x)g(x). Terbukti, untuk setiap polinom kode c(x) = c0 + c1x + ... + cn−1xn−1 yang bersesuaian dengan vektor kode c ∈ C, terdapat polinom q(x) yang memenuhi c(x) = q(x)g(x). Polinom generator g(x) dari kode C adalah polinom minimal Sesuai hasil di bagian 5, setiap unsur di dalam kode linear C adalah kelipatan dari polinom g(x) yang disebut polinom generator dari C. Misalkan M(x) adalah polinom minimal untuk α atas GF(2), sehingga M(x) adalah polinom derajat terkecil yang memiliki akar α dan setiap polinom yang juga memiliki akar α habis dibagi oleh M(x). Karena g(α) = 0 maka dari sifat minimal polinom M(x), maka M(x) membagi g(x). Sebaliknya n = 2m − 1 di mana deg(M(x)) = m < n dan M(α) = 0, disimpulkan M(x) ∈ C. Ini berarti polinom generator g(x) membagi M(x) ∈ C. Dari kedua hasil di atas, bahwa M(x) membagi g(x) dan g(x) membagi M(x) terbukti bahwa g(x) = M(x). Jadi polinom generator dari C adalah polinom minimal dari α atas GF(2) yang berderajat m. Hasil ini juga menegaskan bahwa dimensi dari C adalah n − m = 2m − 1 − m. Misalkan w = (w0, w1, ...,wn−1) ∈ GF(2)n. Akan dibuktikan bahwa w ∈ C jika dan hanya jika w(α) = 0 sebagai berikut w ∈ C ⇔ HwT = 0 ⇔ [1 α α2 ... αn−1][ w0 w1 ... wn−1]T = 0 ⇔ w0 · 1 + w1 · α + ... + wn−1 · αn−1 = 0 ⇔ w(α) = 0 Kesimpulannya bahwa C adalah kode siklik. Misalkan c ∈ C, maka c'(x) ≡ xc(x) mod (xn − 1) jadi c'(x) = xc(x) + a(x) (xn − 1) untuk suatu polinom a(x) ∈ GF(2)[x]. Sehingga c'(α) ≡ αc(α) + a(α) (αn − 1) karena c ∈ C, maka diperoleh c(α) = 0 (sesuai pembahasan di bagian 3). Karena α adalah unsur dengan order n, maka αn = 1 dan αn − 1 = 0. Jadi c'(α) = 0. Sehingga c' ∈ C (oleh (3)). Jadi C adalah kode siklik. Misalkan g(x) adalah polinom generator dari C dan M(x) adalah polinom minimal untuk α atas GF(2). Karena g(x) ∈ C, maka dari bagian 3 diperoleh bahwa g(α) = 0 sehingga M(x) ∈ C sehingga M(α) = 0. Dari sifat minimal polinom M(x), maka M(x) membagi g(x). Juga karena deg(M(x)) = m < n dan M(α) = 0 disimpulkan M(x) ∈ C. Dengan demikian polinom generator g(x) membagi M(x) ∈ C. Jadi M(x) membagi g(x) dan g(x) membagi M(x). Karena M(x) dan g(x) keduanya monik, haruslah g(x) = M(x). Jadi polinom generator dari C adlah polinom minimal dari α atas GF(2) dan berderajat m. Sehingga dimensi dari C adalah n − m = 2m − 1 − m.
4. Penutup Kesimpulan yang dapat diambil dari tulisan ini adalah 1. Konsep ruang vektor atas lapangan F2, khususnya ruang vektor F2n = GF(2n) dan konsep ideal prima adalah konsep terpenting di dalam pembahasan kode linear biner. Konsep perkalian vektor baris dengan matriks digunakan untuk merentang (dalam bahasa pengkodean: encoding) vektorvektor panjang k menjadi vektor-vektor kode yang panjangnya n > k. Konsep sistem persamaan
2.
3. 4.
5.
linear digunakan untuk menentukan matriks paritas H jika matriks generator G diketahui, dan sebaliknya. Kode linear biner [n, k, d] adalah subruang dari F2n berdimensi k dengan panjang kode n dan jarak minimum d. Khususnya, kode Hamming (tak siklik) Hm bisa diperoleh dari matriks paritas kode tersebut yang berukuran m × (2m − 1), di mana kolom-kolom matriks paritas menyajikan bilangan 1, 2, …, 2m − 1 dalam biner. Kesalahan perubahan bit dari vektor kode c ∈ C menjadi vektor v panjang n bisa dideteksi jika v ∉ C. Sindrom dari vektor kode selalu merupakan vektor 0, sindrom dari bukan vektor kode bukan vektor 0. Sindrom dari vektor dengan kesalahan bit menggunakan matriks paritas H yang kolomkolomnya menyajikan bilangan-bilangan 1, 2, ..., 2m−1, m adalah banyak kolom H; menunjukkan posisi bit yang salah. Kode siklik bisa dinyatakan secara aljabar sebagai sebuah ideal di gelanggang GF(2n)[x]/<xn − 1> yang dibangun oleh suatu polinom generator g(x) dimana g(x) membagi xn − 1. Khusus untuk kode Hamming siklik, generatornya adalah salah satu polinom minimal untuk suatu unsur α di dalam GF(2n).
Daftar Pustaka Adams, Sarah Spence. Introduction to Algebraic Coding Theory. Fall. 2006 Blahut, Richard E. Algebraic Codes for Data Transmission. New York: Cambridge Press. 2003 Haryanto, Loeky, Amir Kamal Amir. 2012. Bahan Ajar untuk Pasca Sarjana (S2) Aljabar Linear Lanjut. Makassar: Universitas Hasanuddin Ling, San, Chaoping Xing. 1999. Coding Theory. New York: Cambridge Press. 2004 Lint, J.H. van. Introduction to Coding Theory. Berlin: Springer Purser, Michael. 1995. Introduction to Error-Correcting Codes. London: Artech House Pretzel, Oliver. 1992. Error-Correcting Codes and Finite Fields. London: Clarendon Press Skorobogatov, Alexei. Rings and Fields (Lectures). London Vanstone, Scott A., Paul C. van Oorcshot. 1989. An Introduction to Error Correcting Codes With Applications. London: Kluwer Academic Publisher http://personal.fmipa.itb.ac.id/ebaskoro/files/2008/02/bukukoding.pdf [diakses pada tanggal 2 September 2012 pukul 21.13]
