KODE SIKLIK (CYCLIC CODES)

Coding Theory

KODE SIKLIK (CYCLIC CODES)

Muhamad Zaki Riyanto NIM: 02/156792/PA/08944 E-mail: [email protected] http://zaki.math.web.id Dosen Pembimbing: Drs. Al. Sutjiana, M.Sc.

1.1 Pendahuluan Salah satu bahasan yang paling penting pada linear codes adalah cyclic codes (kode siklik). Secara umum kode ini lebih mudah untuk diimplementasikan dan mempunyai aplikasi yang luas. Dilihat dari sudut pandang teori aljabar, kode ini sangat menarik untuk dipelajari. Banyak dari kode-kode yang diturunkan dari cyclic code. Kita mulai dengan membahas tentang pendefinisian suatu cyclic subspace.

Definisi Suatu subruang S atas Vn ( F ) disebut cyclic subspace (subruang siklik) jika

( a1 , a2 ,..., an −1 , an ) ∈ S , maka ( an , a1 , a2 ,..., an −1 ) ∈ S . Dengan kata lain, S merupakan suatu subspace dan untuk setiap vektor a ∈ S , setiap cyclic shift (pergeseran siklik) juga berada di dalam S.

Definisi Suatu linear code C disebut cyclic codes (kode siklik) jika C merupakan cyclic subspace.

Copyright © 2006 http://zaki.math.web.id

1

Karena cyclic code merupakan linear code, maka suatu cyclic code mempunyai codeword 0 dan tertutup terhadap operasi penjumlahan.

Contoh 1. 1) S = {( 0000 )} ⊆ V4 ( Z 2 ) merupakan cyclic subspace. 2) S = {( 0000 ) , (1111)} ⊆ V4 ( Z 2 ) merupakan cyclic subspace. 3) S = {( 0000000 ) , (1011100 ) , ( 0101110 ) , ( 0010111) , (1110010 ) , ( 0111001) ,

(1001011) , (1100101)} merupakan cyclic subspace pada V7 ( Z 2 ) . 4) Subset di bawah ini bukan merupakan cyclic subspace atas V4 ( Z 2 ) .

S = {( 0000 ) , (1001) , (1100 ) , ( 0110 ) , ( 0011) , ( 0111) , (1011) , (1101)}. Setiap cyclic shift (pergeseran siklik) dari codeword (0111) tidak berada di dalam S. S juga bukan merupakan subspace, sebab di dalam S tidak tertutup terhadap penjumlahan.

1.2 Rings dan Ideals Definisi Suatu ring komutatif dengan unity ( R, +, ∗) adalah suatu struktur aljabar yang terdiri dari suatu himpunan R dan dua operasi biner yang dinotasikan dengan + dan * yang memenuhi sifat-sifat untuk semua a, b, c ∈ R. 1)

( R, + ) merupakan grup abelian dengan elemen identitas e.

2)

( a * b) * c = a * (b * c) .

3)

(a + b) *c = a * c + b * c

dan c * ( a + b ) = c * a + c * b.

4) Terdapat suatu elemen 1 ∈ R sehingga a *1 = 1* a = a. 5) a * b = b * a.


2

Contoh 2. 1) Himpunan semua bilangan bulat terhadap operasi penjumlahan dan perkalian membentuk suatu ring ( Z , +,*) , dinotasikan dengan Z. 2) Himpuan semua bilangan bulat positif modulo n merupakan ring, dinotasikan dengan Z n . 3) Himpunan semua polynomial dengan koefisiennya adalah elemen suatu field (lapangan) F atas ring R. Ring ini dinotasikan dengan F[x]. Dua operasinya adalah penjumlahan dan perkalian polynomial.

Dari 3) dapat dikonstruksikan suatu ring dengan elemen yang berhingga sebagai berikut. Diberikan sebarang polynomial tidak nol

f ( x) ∈ F [ x], didefinisikan dua

polynomial h( x), g ( x) ∈ F [ x] , h(x) dan g(x) disebut kongruen atas polynomial modulo

f(x) jika dan hanya jika f(x) membagi h(x) – g(x), yaitu h(x) dan g(x) mempunyai sisa yang sama apabila dibagi dengan f(x). Kongruensi ini membentuk relasi ekuivalensi dan membentuk partisi-partisi, dengan klas-klas ekuivalensi memuat g(x) yang dinotasikan dangan [g(x)] kemudian didefinisikan sebagai

[ g ( x)] = {h( x) : h( x) ≡ g ( x) (mod f ( x))} . Diberikan R = F [ x]/( f ( x)) = {[ g ( x)] : g ( x) ∈ F [ x]} . Didefinisikan operasi penjumlahan dan perkalian pada klas-klas ekuivalensi sebagai berikut [ g ( x)] + [h( x)] = [ g ( x) + h( x)] dan [ g ( x)]*[h( x)] = [ g ( x)* h( x)]. Maka ( R, +,*) merupakan ring dan disebut dengan ring polynomial atas F modulo

f(x).


3

Definisi Diberikan ring ( R, +,*) . Suatu subset tak kosong I ⊆ R disebut ideal dari ring R jika 1)

( I, +)

merupakan grup, dan

2) i * r ∈ I untuk setiap i ∈ I dan setiap r ∈ R.

Ideal memainkan peran yang penting di dalam mempelajari cyclic subspace atas Vn ( F ) . Pada subbahasan 1.3 akan dipelajari pembentukan korespondensi 1-1 antara ideals dari ring polynomial atas F modulo x n − 1 dan cyclic subspace atas Vn ( F ) . Salah satu cara untuk mengkonstruksi suatu ideal adalah sebagai berikut. Ambil sebarang g ∈ R, g ≠ 0 dan bentuk

I = { g * r : r ∈ R} . Mudah untuk menunjukkan bahwa I adalah ideal. I dsebut dengan ideal yang dibangun oleh g. Tetapi tidak selalu mungkin untuk mengkonstruksi semua ideal dari suatu ring dengan cara seperti itu. Apabila ring R mempunyai sifat bahwa untuk sebarang ideal I atas R terdapat suatu elemen g ∈ I sehingga I = { g * r : r ∈ R} , maka R disebut dengan principal ideal ring.

Teorema 1.1 F[x] merupakan suatu principal ideal ring.

Teorema 1.2 F[x]/(f(x)) merupakan suatu principal ideal ring.

Contoh 3. Diberikan R = Z 2 [ x] /( f ( x)) dengan f ( x) = x 6 − 1 dan himpunan

I = {0,1 + x 2 + x 4 , x + x 3 + x5 ,1 + x + x 2 + x3 + x 4 + x 5 } .


4

I merupakan suatu ideal dari R. Mudah untuk membuktikan bahwa ( I , + ) merupakan grup. Ideal I tersebut dibangun oleh g ( x) = 1 + x 2 + x 4 .

1.3 Ideal dan Cyclic Subspace Telah kita ketahui bahwa Vn ( F ) merupakan grup abelian terhadap operasi penjumlahan vektor. Akan kita pelajari sifat-sifat dari suatu ring dengan mendefinisikan suatu operasi perkalian antara dua vektor. Cara yang paling mudah adalah dengan mengasiosikan suatu polynomial pada F[x] dengan setiap vektor pada Vn ( F ) . Jika v = (a0 a1...an −1 ) , kemudian diberikan v( x) = a0 + a1 x + ... + an −1 x n −1. Selanjutnya, untuk mendefinisikan suatu operasi perkalian vektor, kita pilih polynomial f ( x) = x n − 1∈ F [ x] .

Kemudian,

untuk

v1 , v2 ∈

Vn ( F ) ,

diberikan

v1 ( x)v2 ( x) = v( x) dimana v( x) merupakan polynomial dengan derajad yang lebih kecil dari klas-klas ekuivalensi [v1 ( x)v2 ( x)] atas F [ x]/( f ( x)) . Dengan kata lain, v( x ) adalah sisa dari polynomial ketika v1 ( x)v2 ( x) dibagi oleh f ( x ) . Dengan operasi perkalian yang telah didefinisikan di atas, dan dengan bentuk pengasosiasian antara polynomial-polynomial dan vektor-vektor, dapat kita perhatikan bentuk dari Vn ( F ) dan F [ x ] /( f ( x )) . Suatu elemen dari Vn ( F ) dapat disajikan sebagai suatu n-tuple atas F atau suatu polynomial dengan derajad paling besar adalah n-1 atas F. Komponen-komponen dari n-tuple merepresentasikan koefisien-koefisien dari polynomial, dari order yang kecil ke order yang lebih besar. Akan kita pelajari bagaimana memilih polynomial f ( x) = x n − 1 yang digunakan untuk mendefinisikan operasi perkalian. Diberikan v = (a0 a1...an −1 ) ∈ Vn ( F ) . v( x) = a0 + a1 x + ... + an −1 x n −1 xv( x) = a0 x + a1 x 2 + ... + an −1 x n . Kemudian apabila x n − 1 ≡ 0 ( mod f ( x) ) berakibat x n ≡ 1( mod f ( x) ) . Sehingga


5

xv( x) = an −1 + a0 x + a1 x 2 + ... + an − 2 x n −1 = (an −1a0 a1...an − 2 ), dan dapat kita lihat bahwa mengalikan dengan x dapat membentuk korespondensi pada suatu cyclic shift dari v. Dengan observasi ini kita dapat membentuk suatu teorema yang sangat mendasar dan penting dalam mempelajari cyclic code.

Teorema 1.3 Suatu subset tak kosong S atas Vn ( F ) merupakan suatu cyclic subspace jika dan hanya jika himpunan polynomial I yang diasosiasikan dengan S merupakan suatu ideal dari ring R atas polynomial yang diasosiasikan dengan Vn ( F ) .

Teorema 1.4 Diberikan ideal I tak nol pada Vn ( F ) dan diberikan monic polynomial g ( x) dengan derajad yang merepresentasikan suatu klas-klas dari I, maka [ g ( x)] (sering ditulis g ( x) ) membangun I dan g ( x) membagi f ( x) = x n − 1 .

Teorema 1.5 Terdapat dengan tunggal suatu monic polynomial dengan derajad lebih kecil yang membangun suatu ideal tak nol I atas Vn ( F ) .

Teorema 1.6 Diberikan monic polynomial h( x) yang membagi f ( x) = x n − 1 . Maka h( x) merupakan

generator

polynomial

(polynomial

pembangun)

dari

ideal

I = {a( x)h( x) : a( x) ∈ R} atas R = F [ x] /( x n − 1).

Teorema 1.7 Terdapat suatu korespondensi 1-1 antara cyclic subspace dari Vn ( F ) dan monic polynomial g ( x ) ∈ F [ x ] yang membagi f ( x) = x n − 1 .


6

Contoh 4. Diberikan V7 ( Z 2 ) dan f ( x) = x 7 − 1 . Faktorisasi dari f ( x ) adalah x 7 − 1 = ( x + 1)( x3 + x 2 + 1)( x3 + x + 1). Monic yang membagi f ( x ) adalah

g1 ( x) = 1 g 2 ( x) = x + 1 g3 ( x) = x 3 + x 2 + 1 g 4 ( x) = x3 + x + 1 g5 ( x) = ( x + 1)( x 3 + x 2 + 1) g 6 ( x) = ( x + 1)( x3 + x + 1) g 7 ( x) = ( x 3 + x 2 + 1)( x3 + x + 1) g8 ( x) = f ( x). g5 ( x) membangun cyclic subspace S = {( 0000000 ) , (1011100 ) , ( 0101110 ) , ( 0010111) , (1001011) , (1100101) ,

(1110010 ) , ( 0111001)}. g 7 ( x) membangun cyclic subspace S=

{( 0000000 ) , (1111111)}.

V7 ( Z 2 ) mempunyai tepat 8 cyclic subspace.

Teorema 1.8 Diberikan

f ( x) = x n − 1

dengan

f ( x) = p1a1 ( x) p2 a2 ( x)... pt at ( x)

dengan

pi ( x) ≠ p j ( x) untuk i ≠ j adalah irreducible (tak dapat difaktorkan) monic polynomial atas F, dan ai merupakan bilangan bulat positif, 1 ≤ t ≤ i. Maka Vn ( F ) memuat sebanyak (a1 + 1)(a2 + 1)...(at + 1) cyclic subspace.


7

Teorema 1.9 Diberikan monic polynomial g ( x) yang membagi f ( x) = x n − 1 atas F yang mempunyai derajad n-k. Maka g ( x ) merupakan generator polynomial untuk suatu cyclic subspace Vn ( F ) yang mempunyai dimensi k.

Contoh 5. Misalkan

akan

kita

konstruksikan

suatu

binary

cyclic

(7,4)-code.

Karena

g ( x) = x 3 + x + 1 adalah monic yang membagi x 7 − 1 , g ( x ) membangun suatu cyclic subspace pada V7 ( Z 2 ) yang mempunyai dimensi 4.

Contoh 6. Misalkan kita akan mengkonstruksi suatu binary cyclic (15,9)-code. Karena g ( x) = (1 + x + x 2 )(1 + x + x 4 ) adalah monic yang membagi x15 − 1 atas Z 2 dan g ( x ) mempunyai derajad 6, g ( x ) membangun suatu cyclic subspace yang berdimensi 9.

1.4 Matriks Generator dan Matriks Parity-Check Diberikan g ( x ) sebagai generator dari suatu cyclic (n,k)-code C atas F. Dari pembahasan sebelumnya, dapat diketahui bahwa g ( x ) mempunyai derajad n-k, dan setiap codeword di C mempunyai bentuk a ( x ) g ( x ) . Berdasarkan Teorema 1.9, kita asumsikan deg a ( x) ≤ k − 1. Kemudian diberikan suatu message space (ruang message) yang terdiri dari semua polynomial atas F yang mempunyai derajad kurang dari atau sama dengan k-1. Kemudian message a ( x) dikodekan menjadi codeword a ( x ) g ( x ) . Karena a ( x ) g ( x ) mempunyai derajad yang paling besar adalah n-1, maka tidak perlu mereduksi dengan modulo f ( x) = x n − 1 . Suatu matriks generator untuk C diberikan sebagai berikut


8

 g ( x)   1   x g ( x)  G =  x 2 g ( x)     :   x k −1 g ( x)   

Contoh 7. Diketahui f ( x) = x 7 − 1. g ( x) = 1 + x + x3 membangun suatu (7,4)-cyclic code atas Z 2 . Message space yang terdiri dari semua polynomial atas Z 2 dengan derajad terbesar adalah 3. Misalkan kita mempunyai polynomial a ( x) = 1 + x 2 + x3 , maka a ( x) dikodekan menjadi codeword polynomial a ( x) g ( x) = 1 + x + x 2 + x3 + x 4 + x 5 + x 6 . Pada vektor biner, message 4-tuple (1011) dikodekan menjadi codeword (1111111). Matriks generatornya adalah

 g ( x)  1  1  x g ( x)  0  G= 2 =  x g ( x)  0     x 3 g ( x)  0

1 0 1 0 0 0 1 1 0 1 0 0  . 0 1 1 0 1 0  0 0 1 1 0 1

Untuk menkodekan a = (1011) , hitung aG = (1111111).

Setelah kita megetahui polynomial yang membangun suatu cyclic code C, bagaimana dengan polynomial yang membangun dari dual code C ⊥ dari C. Akan kita lihat bahwa jika C adalah cyclic code, maka C ⊥ juga merupakan cyclic code. Misalkan h( x) = f ( x) / g ( x) dengan f ( x) = x n − 1 dan g ( x) merupakan monic polynomial yang membagi f ( x) , dan g ( x ) membangun C. jika deg g ( x) = n − k , maka deg h( x) = k . Karena g ( x ) monic, maka h( x) juga monic. Akibatnya h( x) membangun suatu cyclic code C ' yang berdimensi n-k. Misalkan c1 ( x) = a1 ( x) g ( x) ∈ C dan c2 ( x) = a2 ( x)h( x) ∈ C ' . Maka

c1 ( x)c2 ( x) = a1 ( x) g ( x)a2 ( x)h( x) = a1 ( x)a2 ( x) f ( x) ≡ 0 ( mod f ( x) ) .


9

Dengan perkalian polynomial mod f ( x ) , sebarang codeword dari C dikalikan dengan sebarang codeword dari C ' menghasilkan polynomial 0 yang berkorespondensi dengan codeword 0. Apakah ini mengakibatkan C ' adalah dual code dari C? Jawabannya adalah tidak, sebab jika hasil perkalian dua polynomial di dalam F [ x ] /( f ( x )) adalah 0 tidak mengakibatkan vektor yang berkorespondensi di Vn ( F ) orthogonal, yaitu mempunyai inner product 0 atas F. Akan kita tunjukkan bahwa kode C ' dan C ⊥ saling berhubungan yaitu keduanya merupakan kode yang ekuivalen. Misal diberikan dua vektor a = (a0 a1...an −1 ) ∈ C dan b = (b0b1...bn −1 ) ∈ C ', dan hasil perkalian

 n −1  n −1  n −1 a ( x)b( x) =  ∑ ai x i  ∑ ai x i  ≡ ∑ ci xi ( mod x n − 1)  i =0  i =0  i =0 untuk suatu ci ∈ F . Konstanta dari hasil perkalian adalah c0 = a0b0 + a1bn −1 + a2bn − 2 + ... + an −1b1 , Karena x n ≡ 1( mod f ( x) ) , maka c0 dapat ditulis sebagai inner produk

c0 = a ⋅ b , dimana b adalah n-tuple yang diperoleh dari b dengan cyclically shifting (menggeser secara siklik) b satu posisi ke arah kiri dan kemudian menukar urutan komponenn −1

komponen dari b. Dengan

memperhatikan perkalian

∑c x i =0

i

i

dengan x n −t akan

mengakibatkan ct menjadi konstantanya, dan merupakan konstanta dari hasil perkalian a ( x)( x n −t b( x)) .

Akibatnya

ct = a ⋅ b ,


10

dengan b menjadi suatu n-tuple yang diasosiasikan dengan polynomial x n −t b( x) . Melihat bentuk dari b( x), b merupakan vektor yang diperoleh dengan menggeser secara siklik vektor b sebanyak t+1 posisi ke arah kiri dan menukar urutan komponenkomponennya.

Contoh 8. Misal diberikan n = 3, dan vektor a = (a0 a1a2 ), b = (b0b1b2 ). Kemudian dengan modulo x3 − 1 , a ( x)b( x) = (a0 + a1 x + a2 x 2 )(b0 + b1 x + b2 x 2 )

= (a0b0 + a1b2 + a2b1 ) + (a0b1 + a1b0 + a2b2 ) x + (a0b2 + a1b1 + a2b0 ) x 2 . Koefisien dari x 0 adalah a ⋅ (b0b2b1 ). (b0b2b1 ) diperoleh dari b dengan menggeser b secara siklik sebanyak 3 – 0 – 1 = 2 posisi dari (b1b2b0 ) dan menempatkan koefisien terakhir ke koefisien pertama, sehingga diperoleh (b0b2b1 ) . Karena a ( x)b( x) ≡ 0 ( mod x n − 1) , koefisien dari setiap xi haruslah 0. Hal ini mengakibatkan a ⋅ c = 0 (yaitu a dan c saling orthogonal) dimana c adalah sebarang cyclic shift dari vektor yang diperoleh dari b dengan menukar komponen b. Karena h( x) membangun C ' , maka {h( x), xh( x),..., x n − k −1h( x)} merupakan basis untuk C ' dan

 h( x )   1  x h( x )   G' =   :  n − k −1  h( x)   x adalah matriks generator untuk C ' . Akibatnya G ' membangun kode C ' , dengan dimensi C ' adalah n-k yang juga sama dengan dimensi dari C ⊥ . Dengan menggunakan b( x) di atas menjadi h( x) , akan kita lihat bahwa dengan menukar kolom terakhir dari G ' ke kolom pertama, kita akan memperoleh suatu matriks H yang membangun C ⊥ , dan matriks ini merupakan matriks parity-check untuk C.


11

Contoh 9. Misalkan kita akan mengkonstruksikan suatu matriks generator dan matriks paritycheck untuk suatu (7,4)-binary cyclic code. Karena g ( x) = 1 + x + x3 membagi f ( x) = x 7 − 1 ,

maka

g ( x)

membangun

(7,4)-cyclic

code

tersebut.

h( x) = f ( x) / g ( x) = 1 + x + x 2 + x 4 membangun suatu (7,3)-cyclic code C ' . Matriks generator untuk C adalah

 g ( x)  1  1  x g ( x)  0  = G= 2  x g ( x)  0    3  x g ( x)  0

1 0 1 0 0 0 1 1 0 1 0 0  . 0 1 1 0 1 0  0 0 1 1 0 1

Matriks generator untuk C ' adalah

 h( x)  1 1 1 0 1 0 0   1  G ' =  x h( x)  = 0 1 1 1 0 1 0  .  x 2 h( x)  0 0 1 1 1 0 1   

Dengan menukar kolom terakhir ke kolom pertama dari G ' , diperoleh matriks generator untuk C ⊥ yaitu

0 1 1 0 1 0 1  H = 0 1 1 1 0 1 0  . 1 0 1 1 1 0 0 

Dapat ditunjukkan bahwa GH T = 0. Karena C ' dan C ⊥ dapat diperoleh dengan menukar komponen-komponen pada semua vektor, maka C ' dan C ⊥ merupakan kode yang ekuivalen. Jadi C ⊥ merupakan dual code dari C . h( x) dikatakan membangun dual code yang juga membangun dari kode


12

yang ekuivalen dengan dual codenya. Dengan mudah dapat dilihat dari konstruksi H bahwa C ⊥ juga merupakan cyclic code.

Definisi k

Diberikan polynomial h( x) = ∑ ai xi dengan derajad k (ak ≠ 0) . Didefinisikan i=0

reciprocal polynomial hR ( x) dari h( x) dengan k

hR ( x) = ∑ ak −i xi i =0

Dapat dilihat bahwa hR ( x) = x k ⋅ h(1 x) , dengan k = deg h( x) .

Teorema 1.10 Diberikan g ( x) polynomial monic yang membagi f ( x) = x n − 1 (atas F) dengan derajad n-k yang menjadi generator untuk cyclic (n,k)-code. Diberikan

h( x) = f ( x) g ( x) . Maka hR ( x) adalah reciprocal polynomial dari h( x)

yang

membangun C ⊥ .

Polynomial h(x) sering disebut dengan parity-check polynomial.

1.5 Encoding Cyclic Codes Diberikan polynomial g ( x) yang membangun suatu cyclic (n,k)-code C atas

F. Suatu matriks generator untuk C dengan bentuk [ R I k ] yang dikonstruksikan sebagai berikut. Bagilah x n − k +i dengan g ( x ) untuk 0 ≤ i ≤ k − 1. Diperoleh

x n − k +i = qi ( x) g ( x) + ri ( x) dengan deg ri ( x) < deg g ( x) = n − k atau ri ( x) = 0. Maka x n − k +i − ri ( x ) = qi ( x ) g ( x ) ∈ C .


13

Jika kita mengambil vektor-vektor koefisien yang berkorespondensi dengan x n − k +i − ri ( x ) sebagai baris-baris dari suatu matriks, maka kita akan memperoleh suatu

matriks generator dengan bentuk [ R I k ] , dimana baris-baris dari R berkorespondensi dengan − ri ( x), 0 ≤ i ≤ k − 1.

Contoh 10. Misal diberikan binary cyclic (7,4)-code seperti contoh 9, yang dibangun oleh

g ( x) = 1 + x + x3 . Dengan algoritma pembagian, diperoleh x3 = (1)( x3 + x + 1) + (1 + x) x 4 = ( x)( x 3 + x + 1) + ( x + x 2 ) x5 = ( x 2 + 1)( x3 + x + 1) + (1 + x + x 2 ) x 6 = ( x 3 + x + 1)( x 3 + x + 1) + (1 + x 2 ).

Matriks generator untuk kode tersebut adalah

1 0 G= 1  1

1 0 1 0 0 0 1  0 1 1 0 1 0 0 = [ R I 4 ] dengan R =  1 1 1 0 0 1 0   0 1 0 0 0 1 1

1 0 1 1  . 1 1  0 1

Baris-baris dari R berkorespondensi dengan polynomial 1 + x, x + x 2 ,1 + x + x 2 dan 1 + x 2 . Suatu message m=(1011) dikodekan menjadi c = mG = (100 1011).

Pandang suatu message polynomial k −1

a ( x) = ∑ ai x i . i =0


14

Telah kita ketahui bahwa a ( x) g ( x) adalah suatu codeword tetapi dengan menggunakan

a ( x) g ( x) information symbols menjadi tidak jelas. Jika G = [ R I k ] adalah matriks generator untuk C, maka message symbols (a0 a1...ak −1 ) ternyata berada di k posisi terakhir dari codeword. Codeword yang berkorespondensi dengan message a ( x) dapat ditentukan dengan melakukan operasi perhitungan sebagai berikut. Bagilah x n − k a ( x) dengan g ( x ) untuk mendapatkan

x n − k a ( x ) = q ( x ) g ( x ) + t ( x) atau

q ( x ) g ( x ) = −t ( x ) + x n − k a ( x ) , dengan t ( x) = 0 atau deg t ( x) < deg g ( x) = n − k . Maka q ( x ) g ( x ) adalah suatu codeword dengan information symbols sebanyak k yaitu (a0 a1...ak −1 ) yang menjadi k komponen terkahir, dan n – k

parity-check symbols, koefisien dari −t ( x) yang

merupakan n – k komponen pertama.

Contoh 11. Diberikan g ( x) = 1 + x + x3 yang membangun suatu binary cyclic (7,4)-code. Misalkan kita ingin mencari suatu codeword c yang mempunyai information symbols (1011) pada 4 posisi terakhir. Ambil a ( x) = 1 + x 2 + x3 . Kemudian x3 a ( x) dibagi dengan g ( x ) ,

x3 a ( x) = ( x 3 + x 2 + x + 1) g ( x) + 1 dan ( x 3 + x 2 + x + 1) g ( x) = 1 + x3 + x 5 + x 6 . Oleh karena itu c = (100 1011) merupakan codeword dengan information symbols (1011) dengan posisi teratas.

Diberikan suatu cyclic (n,k)-code dengan generator polynomial

g ( x) = g 0 + g1 x + ... + g n − k −1 x n − k −1 + x n − k


15

dan matriks generator G = [ R I k ] . Baris-baris R adalah negated coefficients dari polynomial sisa yaitu ri ( x), 0 ≤ i ≤ k − 1 dimana

x n − k + i = qi ( x) g ( x) + ri ( x) , deg ri ( x) < deg g ( x) atau ri ( x) = 0 . Kemudian n – k parity-check symbols untuk information symbols (a0 a1...ak −1 ) diberikan sebagai k −1

∑ a r ( x) . i =0

i i

Pada kasus biner, kita dapat mengkodekan dengan suatu algoritma yang sederhana dan efisien, dan mudah untuk diimplementasikan pada hardware (perangkat keras). Algoritma ini digunakan untuk mengkodekan suatu pesan m = (a0 a1...ak −1 ) menjadi codeword c = ( s0 s1...sn − k −1a0 a1...ak −1 ) .

Algoritma: Encoding Algorithm for Binary Cyclic Codes. Let gˆ = ( g 0 g1...g n − k −1 ). Let Message symbols (a0 a1...ak −1 ). Let Parity-check symbols s = ( s0 s1...sn − k −1 ). (1)

Set s j = 0, 0 ≤ j ≤ n − k − 1.

(2)

Set i = 1.

(3)

If ak −i = sn − k −1 then For j from n – k – 1 to 1, set s j = s j −1 .

s0 = 0 . Otherwise For j from n – k – 1 to 1, set s j = s j −1 + g j .

s0 = g 0 . (4)

i=i+1

(5)

If i > k , stop. Otherwise, go to (3).


16

Penjelasan singkat tentang algoritma. Dengan menggunakan matriks generator G = [ R I k ] , kemudian, seperti pada penjelasan sebelumnya, n – k parity-check symbols berkorespondensi dengan suatu message a ( x) yaitu koefisien-koefisien dari −t ( x) dimana

x n −k a( x) = q ( x) g ( x) + t ( x) . Untuk menghitung t ( x) , kita hitung x n − k a ( x) (mod g ( x)) . Karena

a ( x) = a0 + a1 x + ... + ak −1 x k −1 . diperoleh

x n − k a ( x) = a0 x n − k + a1 x n − k +1 + ... + ak −1 x n −1 .

Dengan memperhatikan proses perkaliannya, hal ini sama halnya dengan menghitung

(...((( a

k −1

)

)

)

x n − k ) x + ak − 2 x n − k x + ak −3 x n − k x + ... + a0 x n − k .

Setiap ekspresi dalam kurung, mulai dari yang paling dalam, berkorespondensi dengan suatu iterasi sesuai dengan algoritma. Reduksi dengan modulo g ( x) pada setiap iterasi akan diambil dan pada penjumlahan pada tiap iterasi tersebut yang berkorespondensi dengan s, yaitu suatu polynomial dengan derajad terbesar adalah n – k – 1.

Selama iterasi ke-i berlangsung, s dikalikan dengan x, dan dijumlahkan ak −i x n − k . Maka s akan mempunyai derajad n – k, sebab bentuk x n − k diperoleh dari proses-proses pergeseran atau penjumlahan. Untuk mengambil sisa dari modulo g ( x) , x n−k

direduksi

dengan

menghilangkannya

dan

menjumlahkan

kembali

gˆ ( x) = g ( x) − x n − k (karena x n − k ≡ gˆ( x) (mod g ( x)) ). Jika sn − k −1 = 1 sebelum s digeser, maka pergeseran menghasilkan suatu x n − k , akan memerlukan perhitungan ulang


17

kembali. Jika ak −i = 1 , maka hal ini memerlukan perhitungan ulang kembali (necessitates

feedback).

Jika

keduanya

sn − k −1

dan

ak − i

adalah

1,

maka

x n − k + x n − k ≡ 0 (mod 2) , dan akan mengakhiri perhitungan yang lainnya. Oleh karena itu perhitungan ulang (feedback) diperlukan dalam melakukan iterasi i jika dan hanya jika sn − k −1 ≠ ak −i . Setelah iterasi ke-k, suatu (n,k)-tuple s berkorespondensi dengan x n − k a ( x) (mod g ( x)) , dan menghasilkan n – k parity-check symbols. Untuk menggunakan skema pengkodean ini, matriks generator G = [ R I k ] tidak harus disajikan secara ekplisit.

Contoh 12. Pada contoh 11, g ( x) = 1 + x + x3 membangun suatu binary cyclic (7,4)-code. Kita akan mengkodekan

message

m

=

(1011)

sabagai

berikut.

Kita

mempunyai

gˆ = ( g 0 g1 g 2 ) = (110) , (a0 a1a2 a3 ) = (1011) , dan kita mulai dengan ( s0 s1s2 ) = (000) .

ak − i

i

s

0

000

1

110

1

2

101

1

3

100

0

4

100

1

Diperoleh parity-check symbols adalah (100). Maka message m = (1011) tersebut dikodekan menjadi codeword c = (100 1011).


18

Contoh 12. Diberikan g ( x) = 1 + x 4 + x 6 + x 7 + x8 generator untuk suatu binary (15,7)-code C. Akan kita kodekan suatu message m = (1011011) sebagai berikut. Kita mempunyai gˆ = (1000 1011) . ak − i

i

s

0

0000 0000

1

1000 1011

1

2

0100 0101

1

3

1010 1001

0

4

0101 0100

1

5

1010 0001

1

6

1101 1011

0

7

0110 1101

1

Jadi, message m = (1011011) dikodekan menjadi codeword c = (0110 1101 1011 011).

DAFTAR PUSTAKA Fraleigh, John B., 2000, A First Course in Abstract Algebra, Sixth Edition, AddisonWesley Publishing Company, Inc., USA. Vanstone, Scott A. and van Oorschot, Paul C., 1989, An Introduction to Error Correcting Codes with Applications, Kluwer Academic Publishers, Massachusetts, USA.


19

KODE SIKLIK (CYCLIC CODES)

Recommend Documents