bch codes final slide

PendahuluanMotivasi

Dasar TeoriPembahasan

Kesimpulan

BCH Codes(Bose -Chaudhuri- Hocquenghem Codes)

Wawin1 Qori Maryamah1 Aliyah1 Hirwanto1

1Universitas Gadjah Mada,Yogyakarta, Indonesia

Presentasi Paper BCH Codes, 2013

Wawin,Qori, Aliyah, Hirwanto BCH Codes

PendahuluanMotivasi


Kesimpulan

Daftar Isi1 Pendahuluan2 Motivasi3 Dasar Teori

Finite FieldRing PolynomialMinimal PolynomialCyclotomic Coset

4 PembahasanPengantarBCH CodesParameter BCH CodeDecoding BCH Code

5 Kesimpulan


PendahuluanMotivasi


Kesimpulan

BCH Codes

BCH codes merupakan salah satu kelas yang sangat pentingdari kode siklik yang mulai dikembangkan pada tahun 1960oleh R.C. Bose dan D.Ray-Cahudhuri kemudian dilanjutkanoleh A. Hocquenghem sehingga biasa disebut BCH codes(Bose-Chaudhuri-Hocquenghem codes) dan merupakangeneralisasi dari Hamming code untuk mengoreksi kesalahanganda( multiple error correction). BCH code didefinisikan olehkelipatan persekutuan terkecil (f1(x), f2(x), ..., ft(x)) sukubanyak yang diberikan.


PendahuluanMotivasi


Kesimpulan

Motivasi

Secara khusus, kode siklik didapat dari generator sukubanyaknya. Bagaimanapun, umumnya kita kesulitan dalammendapatkan informasi pada jarak minimum(minimumdistance) kode siklik dari generator suku banyaknya, meskipunkita dapat melengkapi hasilnya. Dengan kata lain, kita perlumemilih beberapa generator khusus suku banyaknya sehinggakita bisa mendapatkan informasi dengan algoritma yang lebihsederhana dan lebih efisien. Kita selanjutnya akanmendiskusikan salah satu generator khusus yang kita pilih yaituBCH-code, dan juga bagaimana kita membentuk algoritmauntuk BCH- codes. Untuk generator khusus yang lain sepertiReed Solomon, Quadratic-Residus Code.


PendahuluanMotivasi


Kesimpulan


Finite Field

Definisi 3.1Field dengan | F |<∞ disebut lapangan hingga(finite field) danF∗ sebagai himpunan F \ {0}.

Definisi 3.2Misalkan F lapangan. Karakteristik F adalah bilangan bulatpositif terkecil m dengan demikian bahwa

m∑i=1

1 = 1 + 1 + . . .+ 1 = 0

dimana 1 ∈ F. Jika m tidak ada maka karakteristiknya 0.


PendahuluanMotivasi


Kesimpulan


Lemma 3.3 dan Definisi 3.4

Lemma 3.3Jika α, β ∈ F mempunyai karakteristik p, maka

(α+ β)p = αp + βp

Definisi 3.4Anggota α ∈ F lapangan hingga dikatakan generator F∗ atauelemen primitif jika

{αi : i ≥ 0} = F∗


PendahuluanMotivasi


Kesimpulan


Contoh 3.5

Contoh 3.5Diberikan GF(9) yang dikontruksikan menggunakan polynomialyang irreducible f (x) = x2 + 1 ∈ Z3[x ]. Carilah elemen primitif.Kita akan mencoba bahwa α = x + 1 merupakan elemenprimitif maka(1 + x)0 = 1 (1 + x)4 = 2(1 + x)1 = 1 + x (1 + x)5 = 2 + 2x(1 + x)2 = 2x (1 + x)6 = x(1 + x)3 = 1 + 2x (1 + x)7 = 2 + x

Jadi α = 1 + x merupakan elemen primitif untuk GF (9)


PendahuluanMotivasi


Kesimpulan


Ring Polynomial

Definisi 3.6Misalkan F merupakan lapangan. Himpunan

F [x ] = {n∑

i=0

aix i : ai ∈ F,n ≥ 0}

disebut sebagai ring polynomial atas F.

Teorema 3.7Misalkan f (x) suku banyak atas F dengan derajat(degree) ≥ 1.Maka F[x ]/(f (x)) bersama dengan operasi penjumlahan danperkalian berbentuk gelanggang. Lebih jauh, F[x ]/(f (x))adalah lapangan jika dan hanya jika irreducible.


PendahuluanMotivasi


Kesimpulan


Lemma 3.8 dan Lemma 3.9

Lemma 3.8

Untuk setiap anggota tak nol α ∈ GF (q), αq−1 = 1.Selanjutnya, α ∈ GF (qm) jika hanya jika αq = α.

Lemma 3.9Untuk setiap elemen β dari finite field F dengan q elemen, kitamempunyai βq = β


PendahuluanMotivasi


Kesimpulan


Minimal Polynomial

Definisi 3.10Misalkan F lapangan dengan karakteristik p dan misalkanα ∈ F∗. Suku banyak minimal α terhadap GF (p) merupakansuku banyak monic m(x) derajat terkecil di GF (p)[x ] dengandemikian m(α) = 0.

Teorema 3.11Suku banyak minimal anggota α tunggal.


PendahuluanMotivasi


Kesimpulan


1. Bukti Teorema 3.2

Andaikan F = GF (q) dan F mempunyai karakteristik p.Mengikuti Lemma 3.8 bahwa α memenuhi suku banyakxq−1 − 1 ∈ GF (p)[x ]. Ketika terdapat suatu suku banyakGF (p)[x ] dengan α akarnya maka ada salah satu dari akarnyadengan derajat terkecil. Ini mengatakan bahwa ada sukubanyak minimal yaitu m(x). Andaikan ada dua suku banyakmonic m1(x) dan m2(x) dengan derajat terkecil mempunyaiakar α.


PendahuluanMotivasi


Kesimpulan


2. Lanjutan Bukti Teorema 3.2

Dengan menggunakan algoritma pembagian suku banyakdidapat

m1(x) = l(x)m2(x) + r(x),

dimana deg r(x) < deg m2(x) atau r(x) = 0. Ketika m1(α) = 0dan m2(α) = 0, kita mempunyai r(α) = 0, tetapi karena m2(x)mempunyai derajat terkecil maka r(x) = 0, sehingga m2(x)membagi m1(x). Dengan cara yang sama, m1(x) membagim2(x) dan ketika keduanya merupakan suku banyak monic,maka m1(x) = m2(x) sehingga terbukti α tunggal.

Teorema 3.12Untuk α ∈ F ∗, suku banyak minimal α, maka m(α)(x) adalahsuku banyak yang irreducible.


PendahuluanMotivasi


Kesimpulan


Definisi 3.13Untuk α ∈ F, misalkan t bilangan bulat positif terkecil dengandemikian αpt

= α, maka himpunan conjugates dari α(terhadapGF (p)) adalah

C(α) = {α, αp, αp2, αp3

, . . . , αpt−1}

C(α) = C(αpi),∀i ∈ F lapangan dengan karakteristik p

Lemma 3.14Misalkan F lapangan hingga dengan karakteristik p, misalkanα ∈ F ∗, dan C(α) himpunan konjugat α terhadap GF (q), maka

m(x) =∏

β∈C(α)

(x − β)


PendahuluanMotivasi


Kesimpulan


Bukti Lemma 3.14Misalkan m(x) =

∑ti=0 mix i dengan koefisien mi ∈ F, kita

catatan bahwam(x)p =

∏β∈C(α)(xβ)

p =∏β∈C(α)(xp − βp)

=∏β∈C(α)(x

p − β) = m(xp)

=∑t

i=1 x ip

Dengan mengikuti Lemma 3.3 didapat bahwa

{β : β ∈ C(α)} = {βp : β ∈ C(α)}Dilain pihak, kita dapatkan bahwa

m(x)p =t∑

i=1

(mix i)p =t∑

i=1

mpi x ip

Jadi, mi = mpi dan dengan menggunakan Lemma 3.8 sehingga

terbukti bahwa mi ∈ GF (p),0 ≤ i ≤ t .Wawin,Qori, Aliyah, Hirwanto BCH Codes

PendahuluanMotivasi


Kesimpulan


Teorema 3.15Untuk α ∈ F, suku banyak minimal α diberikan oleh

mα(x) =∏

β∈C(α)

(x − β)

Contoh 3.16

Kontruksikan lapangan F = GF (23). Hal pertama yangdiperlukan adalah suku banyak pangkat tiga atas Z2. Misalkankita mengambil f (x) = x3 + x + 1 dan anggota-anggota Fadalah

{0,1, x , x + 1, x + x2, x2,1 + x2,1 + x + x2}.


PendahuluanMotivasi


Kesimpulan


1. Penyelesaian Contoh 3.7

Ketika x3 + x + 1 = 0 mod f (x), maka kita mempunyaix3 ≡ −x − 1 = x + 1(mod(f (x))), dan 1 = −1 ∈ Z2.Selanjutnya kita tuliskan anggota lapangan dengana0 + a1x + a2x2, maka didapatkan0 = (000) x2 = (001)1 = (100) 1 + x2 = (101)x = (010) x + x2 = (011)1 + x = (110) 1 + x + x2 = (111)

Jika kita mengambil α, maka dengan mudah kita dapatkanbahwa α merupakan generator F. Andaikan kita mengambilβ = (101) dan kita akan dicari mβ(x).


PendahuluanMotivasi


Kesimpulan


2. Lanjutan Penyelesaian Contoh 3.7Dengan menggunakan Teorema 3.15 diatas

mβ(y) =∏

δ∈C(β)

(y − β)(y − β2)(y − β4)

dan ketika β8 = β dan kita akan menghitung(y − β)(y − β2)(y − β3)=y3 + (β + β2 + β4)y2 + (ββ2 + ββ4 + β2β4)y + ββ2β4

Dengan menggunakan representasi setiap anggota tak nolsebagai akar dari generator α, dengan mengambil α = x , kitadapatkanα0 = (100) α4 = (011)α1 = (010) α5 = (111)α2 = (001) α6 = (101)α3 = (110) α7 = (100)


PendahuluanMotivasi


Kesimpulan


3. Lanjutan Penyelesaian Contoh 3.7

Ketika β = α6, maka β2 = α12 = α5 = dan β4 = α24 = α3,diperolehβ + β2 + β4 = α6 + α5 + α3

= (101) + (111) + (110)= 100

ββ2 + ββ4 + β2β4 = β3 + β5 + β6

= α18 + α30 + α36

= α4 + α2 + α= 0

ββ2β4 = β7

= α42

= 1


PendahuluanMotivasi


Kesimpulan


4. Lanjutan Penyelesaian Contoh 3.7

Jadi, didapat suku banyak minimal β2 dan β4 yaitu

mβ(y) = y3 + y2 + 1

Sedangkan suku banyak minimal α juga merupakan sukubanyak minimal α2 dan α4 yaitu

mα(y) = y3 + y + 1


PendahuluanMotivasi


Kesimpulan


Definisi Cyclotomic Coset

Definisi 3.17Diberikan q dan n dan bilangan bulat i ,0 ≤ i ≤ n − 1,cyclotomic coset (q modulo n) memuat i didefinisikan oleh

Ci = {i , iq, iq2, . . . , iqn−1}

dimana anggota-anggota himpuna mengambil modulo n, dan sbilangan bulat terkecil dengan demikian iqs ≡ i(modn).C = {Ci : 0 ≤ i ≤ n − 1} disebut himpunan cyclotomic cosetq modulo n


PendahuluanMotivasi


Kesimpulan


Contoh 3.18Untuk n = 9 dan q = 2, didapatC1 = [1,2,4,8,7,5] = C2 = C4 = C8 = C7 = C5C − 3 = [3,6] = C6C − 0 = [0]

Teorema 3.19Misalkan f (x) = xn − 1 suku banyak atas GF (q). Banyaknyafaktor irreducible dari f (x) adalah sama dengan banyakcyclotomic coset q modulo n.


PendahuluanMotivasi


Kesimpulan

PengantarBCH CodesParameter BCH CodeDecoding BCH Code

Pengantar

Suku banyak monic g(x) ∈ GF (q)[x ] dikatakan sebagai splitdidalam perluasan field GF (qm) dari GF (q) jika g(x) bisadifaktorkan sebagai hasil kali suku banyak linear di GF (qm),kita bisa menuliskannya ;

g(x) = (x − α1)(x − α2) . . . (x − αn)

dimana αi ∈ GF (qm) dan GF (qm) disebut sebagai splitting fielddari g(x). Secara umum, dapat didefinisikan bahwa splittingfield dari g(x) ∈ GF (qm) sebagai lapangan terkecil GF (qm),dengan kata lain lapangan terkecil yang memuat semua akar-akar dari g(x).


PendahuluanMotivasi


Kesimpulan


Splitting field g(x) bisa didapatkan dari derajat faktor irreducibleatas GF (q). Catatan bahwa g(x) boleh irreducible atas GF (q),tetapi selalu faktor- faktornya sebagai hasil kali suku banyaklinear yang berbeda di splitting field. Untuk contoh,g(x) = x2 + x + 1 adalah merupakan irreducible atas GF (2)dan tidak mempunyai akar di GF (2), tetapi atas GF (4),

g(x) = (x + α)(x + α2)

dan mempunyai akar-akarnya adalah α dan α2, dimanaGF (4) = {0,1, α, α2} dengan α2 + α+ 1 = 0


PendahuluanMotivasi


Kesimpulan


Contoh

Contoh 4.1Diberikan suku banyak dibawah ini

g(x) = 1 + x3 + x5 + x6 + x8 + x9 + x10

atas GF (2), dapat dicek bahwa g(x) tidak mempunyai akar diGF (2), ataupun GF (22),GF (23), dan GF (24), tetapimenggunakan GF (5) didapat akar -akar α darih(x) = 1 + x2 + x5 yaitu α, α3, dan anggota kojugatenya adalahα, α2, α4, α8, α16 dan α3, α6, α12, α24, α17 adalah

merupakan akar -akar dari g(x), dan semua akar dari g(x) diGF (25)


PendahuluanMotivasi


Kesimpulan


Contoh

Contoh 4.2Diberikan suku banyak dibawah ini :

g(x) = 2 + 2x + x4 + 2x5 + x6 + x7

atas GF (3) dan hanya memiliki satu akar dengan yaitu 1, dantidak ada akar dari persamaan tersebut di GF (32), sedangkandengan mengggunakan GF (33) didapat akar α darih(x) = 1 + 2x2 + x3 yaitu;

1, α2, α6, α18, α4, α12, α10

Akar -akar diatas merupakan akar α dari g(x).


PendahuluanMotivasi


Kesimpulan


Contoh 4.3

Diberikan g(x) = 1 + x + x3 yang merupakan generates darikode biner (7,4)− codeC. Ketika g(x) membagi x7 − 1 atasGF (2),dan 23 ≡ 1(mod 7) yang merupaka semua akar darig(x) di GF (23). Jika kita misalkan α ∈ GF (23), dengan akar-akarnya dari g(x) adalah α, α2, dan α4. Kita cukupmengatakan bahwa α merupakan akarnya ketika α2 dan α4

elemen konjugate dari α sehingga parity check matrix nyaadalah[

1 α α2 α3 α4 α5 α6]=

1 0 0 1 0 1 10 1 0 1 1 1 00 0 1 0 1 1 1


PendahuluanMotivasi


Kesimpulan


Definisi 4.4

Definisi 4.4Misalkan kita mempunyai sebanyak t suku banyakf1(x), f2(x), . . . , ft(x) ∈ F[x ], maka kelipatan persekutuanterkecil dari f1(x), f2(x), . . . , ft(x) adalah suku banyak monicdengan derajat terkecil dan merupakan perkalian dari semuasuku banyak f1(x), f2(x), . . . , ft(x). Selanjutnya, dinotasikansebagai lcm(f1(x), f2(x), . . . , ft(x)).


PendahuluanMotivasi


Kesimpulan


Penjeleasan lebih lanjut

Jika f1(x), f2(x), ..., ft(x) ∈ Fq[x ] dapat difaktorisasi menjadif1(x) = a1.p1(x)e1,1 . . . pn(x)e1,n

f2(x) = a2.p1(x)e2,1 . . . pn(x)e2,n

......

ft(x) = at .p1(x)et,1 . . . pn(x)et,n

dimana pi(x) merupakan suku banyak monic yang irreducibleatas Fq maka

lcm(f1(x), f2(x), ..., ft(x)) = p1(x)max{e1,1,...,et,1}...pn(x)max{e1,n,...,et,n}


PendahuluanMotivasi


Kesimpulan


Contoh 4.5 dan Lemma 4.6

Contoh 4.5Diberikan polinomial biner,f1(x) = (1 + x)2(1 + x + x4)3

f2(x) = (1 + x)(1 + x + x2)2

f3(x) = x2(1 + x + x4)sehingga,lcm(f1(x), f2(x), f3(x)) = x2(1 + x)2(1 + x + x2)2(1 + x + x4)3

Lemma 4.6Diberikan f1(x),f2(x), . . ., ft(x) suku banyak atas Fq. Jika f (x)habis dibagi oleh semua suku banyak fi(x),∀i = 1,2, . . . , tmaka f (x) habis dibagi oleh lcm(f1(x), f2(x), . . . , ft(x))


PendahuluanMotivasi


Kesimpulan


Bukti Lemma 4.6

Bukti.Ambil g(x) = lcm(f1(x), f2(x), . . . , ft(x)). Menggunakanalgoritma pembagian maka ada dua suku banyak u(x) dan r(x)atas Fq dengan demikian deg(r(x)) < deg(g(x)) danf (x) = u(x)g(x) + r(x). Jadi, r(x) = f (x)− u(x)g(x), danselanjutnya r(x) juga habis dibagi oleh semua fi(x). Ketika g(x)mempunyai derajat terkecil,dengan jelas bahwa r(x) = 0.


PendahuluanMotivasi


Kesimpulan


Contoh 4.7

Contoh 4.7

Suku banyak f (x) = x15 − 1 ∈ F2[x ] dibagi olehf1(x) = 1 + x + x2 ∈ F2[x ] habis dibagi olehf1(x) = 1 + x + x2 ∈ F2[x ], f2(x) = 1 + x + x4 ∈ F2[x ], danf3(x) = (1 + x + x2)(1 + x3 + x4) ∈ F2[x ]. Maka f (x) habisdibagi olehlcm(f1(x), f2(x), f3(x)) = (1 + x + x2)(1 + x + x4)(1 + x3 + x4).


PendahuluanMotivasi


Kesimpulan


Definisi 4.8

Definisi 4.8

Misalkan α elemen primitif dari Fqm dan dinotasikan oleh M i(x)merupakan polynomial minimal dari αi terhadap Fq. Sebuahprimitif BCH code atas Fq dengan panjang n = qm − 1 didesaindengan distance δ adalah q-ary cyclic code yang dibangun olehg(x) :=lcm(M(a)(x),M(a+1)(x), . . . ,M(a+δ−2)(x)) untuk suatubilangan bulat a. Lebih jauh, code ini disebut sebagai narrowsense jika a = 1.


PendahuluanMotivasi


Kesimpulan


Contoh 4.9

Contoh 4.9

Misalkan β merupakan akar dari 1 + x + x2 ∈ F2[x ], makaF4 = F2[β]. Misalkan α menjadi akar dari β + x + x2 ∈ F4[x ].Maka α elemen primitif dari F16. Diberikan narrow-sense 4−aryBCH code dengan panjang 15 didesain dengan distance 4,maka generator polynomialnya adalahg(x) = lcm(M(1)(x),M(2)(x),M(3)(x)) =1 + βx + βx2 + x3 + x4 + β2x5 + x6.


PendahuluanMotivasi


Kesimpulan


Parameter BCH Code

Teorema 4.10Diketahui panjang dari BCH code adalah qm − 1.

Dimensi dari q − ary BCH code dengan panjang qm − 1yang dibangun oleh

g(x) := lcm(M(α)(x),M(α+1)(x), ...,M(α+δ−2)(x)

tidak tergantung dari pemilihan elemen primitif αq − ary BCH code dengan panjang qm − 1 yang didesaindengan distance δ memiliki dimensi setidaknyaqm − 1−m(δ − 1)


PendahuluanMotivasi


Kesimpulan


Contoh dari Teorema 4.10

Contoh 4.11(i) Diberikan cyclotomic cosets 2 modulo 15 dibawah ini :

C2 = {1,2,4,8} C3 = {3,6,12,9}.Maka dimensi dari binary BCH Codes dengan panjang 15dan didesign dengan distance 3 yang dibangun olehg(x) :=lcm(M(2),M(3)(x)) adalah

15− | C2 ∪ C3 |= 15− 8 = 7

(ii) Cyclotomic cosets dari 3 modulo 26 yaitu,C1 = C3 = {1,3,9}C2 = {2,6,18}C4 = {4,10,12}


PendahuluanMotivasi


Kesimpulan


Lanjutan Contoh 4.11 dan Proposisi 4.12

Kemudian dimensi dari ternary BCH codes dengan panjang 26dan didesain dengan distance 5 yang dibangun olehg(x) := lcm(M(1)(x),M(2)(x),M(3)(x),M(4)(x)) adalah

26− |C1 ∪ C2 ∪ C3 ∪ C4| = 26− 9 = 17

Proposisi 4.12

Narrow sense binary BCH code dengan panjang n = 2m − 1dan didesain dengan distance δ = 2t + 1 mempunyai dimensisedikitnya n −m(δ − 1)/2.


PendahuluanMotivasi


Kesimpulan


Contoh 4.13Narrow sense binary BCH code dengan panjang 63 didesaindengan distance δ = 5 mempunyai dimensi51 = 63− 6(5− 1)/2. Bagiamanapun, narrow sense binaryBCH code dengan panjang 31 didesain dengan distanceδ = 11 mempunyai dimensi 11 yang lebih besar daripada31− 5(11− 2)/2.


PendahuluanMotivasi


Kesimpulan


Lemma 4.14Misalkan C q-ary cyclic code dengan panjang n dan generatorpolynomial g(x). Andaikan α1, . . . , αr akar -akar dari g(x) danpolynomial g(x) tidak mempunyai akar ganda. Maka elemenc(x) ∈ Fq[x ]/(xn − 1) adalah codeword C jika hanya jikac(αi) = 0, untuk setiap i = 1, . . . , r .

Bukti.Jika c(x) codeword C, maka ada polynomial f (x) dengandemikian c(x) = g(x)f (x). Jadi kita mempunyaic(αi) = g(αi)f (αi) = 0 untuk semua i = 1, . . . , r . Secarakonvers, jika c(αi) = 0 untuk i = 1, . . . , r maka c(x) habisdibagi oleh g(x) ketika g(x) tidak mempunyai akar ganda. Inimengartikan bahwa c(x) adalah codeword C.


PendahuluanMotivasi


Kesimpulan


Contoh 4.15Diberikan binary [7,4]−Hamming code dengan generatorpolynomial g(x) = 1 ++x + x3. Semua elemen dari F8\{0,1}adalah akar-akarc(x) = 1 + x + x2 + x3 + x4 + x5 + x6 = (x7 − 1)/(x − 1),semua akar dari g(x) adalah akar-akar c(x). Jadi, 1111111adalah codeword.

Teorema 4.16BCH code didesain dengan distance(designed distance) δmempunyai minimum distance sedikitnya δ.


PendahuluanMotivasi


Kesimpulan


Bukti Teorema 4.16

Misalkan α merupakan elemen primitif dari Fqm dan misalkan Cadalah BCH code yang dibangun olehg(x) :=lcm(M(a)(x),M(a+1)(x), . . . ,M(a+δ−2)(x)). Dengan jelasbahwa elemen αa, . . . , αa+δ−2 adalah akar-akarnya g(x).Andaikan bahwa minimum distance d dari C lebih kecildaripada δ. Maka ada codeword tak nolc(x) = c0 + c1x + · · ·+ cn−1xn−1 dengan demikianwt(c(x)) = d < δ. Menggunakan Lemma 4.14, kita mempunyaic(αi) = 0 untuk semua i = a, . . . ,a + δ − 2;


PendahuluanMotivasi


Kesimpulan


Lanjutan Bukti Teorema 4.16

Andaikan bahwa minimum distance d dari C lebih kecildaripada δ. Maka ada codeword tak nolc(x) = c0 + c1x + · · ·+ cn−1xn−1 dengan demikianwt(c(x)) = d < δ. Menggunakan Lemma 4.14, kita mempunyaic(αi) = 0 untuk semua i = a, . . . ,a + δ − 2;

1 αa (αa)2 . . . (αa)n−1

1 αa+1 (αa+1)2 . . . (αa+1)n−1

1 αa+2 (αa+2)2 . . . (αa+2)n−1

......

... . . ....

1 αa+δ−2 (αa+δ−2)2 . . . (αa+δ−2)n−1

c0c1c2...

cn−1

= 0.

(1)


PendahuluanMotivasi


Kesimpulan


Asumsikan bahwa c(x) adalah R = {i1, . . . , id}, cj 6= 0 jikahanya jika j ∈ R. Maka persamaan (1) menjadi

(αa)i1 (αa)i2 (αa)i3 . . . (αa)id

(αa+1)i1 (αa+1)i2 (αa+1)i3 . . . (αa+1)id

(αa+2)i1 (αa+2)i2 (αa+2)i3 . . . (αa+2)id

......

......

...(αa+δ−2)i1 (αa+δ−2)i2 (αa+δ−2)i3 . . . (αa+δ−2)id

ci1ci2ci3...

cid

= 0.

(2)


PendahuluanMotivasi


Kesimpulan


Lanjutan Bukti Teorema 4.16

Ketika d ≤ δ − 1, kita mendapatkan sistem persamaan dibawahini dengan memilih persamaan d yang pertama sistempersamaan diatas sehingga didapatkan :

(αa)i1 (αa)i2 (αa)i3 . . . (αa)id

(αa+1)i1 (αa+1)i2 (αa+1)i3 . . . (αa+1)id

(αa+2)i1 (αa+2)i2 (αa+2)i3 . . . (αa+2)id

......

... . . ....

(αa+d−1)i1 (αa+d−1)i2 (αa+d−1)i3 . . . (αa+d−1)id

ci1ci2ci3...

cid

= 0.

(3)


PendahuluanMotivasi


Kesimpulan


Determinan D koefisien matriks persamaan diatas adalahsama dengan

D =d∏

j=1

(αa)ij det

1 1 1 . . . 1αi1 αi2 αi3 . . . αid

(α2)i1 (α2)i2 (α2)i3 . . . (α2)id

......

... . . ....

(αd−1)i1 (αd−1)i2 (αd−1)i3 . . . (αd−1)id

(4)

=d∏

j=1

(αa)ij∏k>l

(αik − αil ) 6= 0.

Dengan mengkombinasikan persamaan (44) dan (4), kitamendapatkan (ci1 , . . . , cid ) = 0 sehingga kontradiksi. Jaditerbukti


PendahuluanMotivasi


Kesimpulan


Contoh

Contoh 4.17

Misalkan α akar dari 1 + x + x3 ∈ F2[x ], dan misalkan C binaryBCH code dengan panjang 7 didesain dengan distance 4 yangdibangun oleh

g(x) = lcm(M(0)(x),M(1)(x),M(2)(x)) = 1 + x2 + x3 + x4

Maka d(C) ≤ wt(g(x)) = 4. Disisi lain dengan menggunakanteorema 4.16 didapat d(C) ≥ 4. Jadi, d(C) = 4.


PendahuluanMotivasi


Kesimpulan


Decoding BCH Codes

Pada bagian akan diberikan algoritma dalam decoding BCHcode yang dibagi menjadi 3 yaitu :

Menghitung syndromeMenemukan error locator polynomialMenemukan semua akar dari error locator polynomial

Untuk menyederhanakannya, kita hanya akan mendiskusikandecoding narrow sense binary BCH codes.


PendahuluanMotivasi


Kesimpulan


Decoding BCH Codes

Misalkan C narrow sense binary BCH codes dengan panjangn = 2m − 1 dan design distance δ = 2t + 1 yang dibangun olehg(x) := lcm(M(1)(x),M(2)(x), . . . ,M(δ−1)(x)), dimana M(i)(x)adalah polynomial minimal dari αi terhadap F2 untuk elemenprimitif α ∈ F2m . Ambil

H =

1 α (α)2 . . . (α)n−1

1 α2 (α2)2 . . . (α2)n−1

1 α3 (α3)2 . . . (α3)n−1

......

... . . ....

1 αδ−1 (αδ−1)2 . . . (αδ−1)n−1

(5)


PendahuluanMotivasi


Kesimpulan


Lanjutan Decoding BCH codes

Maka bisa ditunjukkan bahwa word c ∈ Fn2 adalah codeword C

jika hanya jika cHT = 0. Selanjutnya, kita bisa mendefinisikansindrome SH(w) dari w ∈ Fn

2 terhadap H adalah wHT .Andaikan bahwa w(x) = w0 + w1x + . . .+ wn−1xn−1 word yangditerima dengan error polynomial e(x) memenuhi wt(e(x)) ≤ t .Ambil c(x) = w(x)− e(x) maka c(x) adalah codeword.


PendahuluanMotivasi


Kesimpulan


Tahap 1. Menghitung Sindrome

Sindrome w(x) adalah

(s0, s1, . . . , sδ−2) := (w0,w1, . . . ,wn−1)HT

sehingga si = w(αi+1) = e(αi+1) untuk setiapi = 0,1, . . . , δ − 2, ketika αi+1 adalah akar-akar dari g(x).Asumsikan bahwa error diambil di posisi i0, i1, . . . , il−1 denganl ≤ t didapat

e(x) = x i0 + x i1 + · · ·+ x il−1 (6)


PendahuluanMotivasi


Kesimpulan


Lanjutan Tahap 1.Menghitung Sindrome

Maka kita mendapatkan sistem persamaan

αi0 + αi1 + · · · + αil−1 = s0=w(α),(αi0)2 + (αi1)2 + · · · + (αil−1)2 = s1 =w(α2),

......

...(αi0)δ−1 + (αi1)δ−1 + · · · + (αil−1)δ−1 = sδ−2=w(αδ−1).

(7)sebarang metode diatas untuk menyelesaikan sistempersamaan diatas merupakan algoritma decoding untuk BCHcodes.


PendahuluanMotivasi


Kesimpulan


Tahap 2. Menemukan error locator polynomial

Untuk e(x) = x i0 + x i1 + · · ·+ x il−1 , didefinisikan error locatorpolynomial oleh

σ(z) :=l−1∏j=0

(1− αij z).

Ini dapat ditemukan bahwa posisi error ij sejauh semuaakar-akar σ(z) yang diketahui. Untuk tahap ini, kita harusmenentukan error locator polynomial σ(z).


PendahuluanMotivasi


Kesimpulan


Teorema

Teorema 4.18

Andaikan polynomial sindrome s(z) =∑δ−2

j=0 sjz j adalah bukanpolynomial nol. Maka terdapat polynomial tak nol r(z) ∈ F2m [z]dengan demikian deg(r(z)) ≤ t − 1, gcd(r(z), σ(z)) = 1 dan

r(z) ≡ s(z)σ(z) (mod zδ−1) (8)


PendahuluanMotivasi


Kesimpulan


Lanjutan Teorema 4.18

Lebih jauh, untuk sebarang pasangan (u(z), v(z)) polynomialtak nol atas F2m memenuhi deg(u(z)) ≤ t − 1, deg(v(z)) ≤ tdan

u(z) ≡ s(z)v(z) (mod zδ−1) (9)

Kita mempunyai

σ(z) = βv(z), r(z) = βu(z), (10)

untuk elemen tak nol β ∈ F2m .


PendahuluanMotivasi


Kesimpulan


Tahap 3. Menemukan akar -akar error locatorpolynomial

Untuk melakukannya, kita bisa mencari semua kemungkinanakar -akar dengan menggunakan σ(z) di αi , untuk semuai = 1,2, . . . . . Setelah semua akar -akarnya αi1 , . . . , αil dariσ(z) ditemukan, kita mendapatkan error polynomial persamaan


PendahuluanMotivasi


Kesimpulan


Contoh 4.18

Contoh 4.19

Misalkan α akar dari g(x) = 1 + x + x3 ∈ F2[x ]. MakaHamming code yang dibangun olehg(x) =lcm(M(1)(x),M(2)(x)) mempunyai design distance δ = 3.Andaikan bahwa w(x) = 1 + x + x2 + x3 word yang diterima.


PendahuluanMotivasi


Kesimpulan


Contoh 4.18Menghitung sindrome :

(s0, s1) = (w(α),w(α2)) = (α2, α4)

Menemukan error locator polynomial :Selesaikan kongruensi polynomial

r(z) ≡ s(z)σ(z) (mod z2)

dengan deg(r(z)) = 0 dan deg(σ(z)) ≤ 1, dan

s(z) = α2 + α4z.

Kita mempunyai σ(z) = 1 + α2z dan r(z) = α2.Selanjutnya didapat error di tempat ketiga. Jadi, kita bisamemperbaiki(decode) w(x) kew(x)− x2 = 1 + x + x3 = 1101000.


PendahuluanMotivasi


Kesimpulan

Kesimpulan

BCH Code merupakan generalisasi dari Hamming code dandidefinisikan dari kelipatan persekutuaan terkecil dari sukubanyak monic dengan derajat terkecil atau

lcm(f1(x), f2(x), . . . , ft(x))

Didalam pembahasan paper ini hanya dibahas BCH codesebagai suku banyak. Adapun penerapan dari BCH codessendiri adalah sistem komunikasi via satelit, pemutarCD(compact disk), DVD, disk drivers, dan barcode dua dimensi.


PendahuluanMotivasi


Kesimpulan

Thank you for yourattention


bch codes final slide

Education