7/25/2019 Coduri BCH
1/48
Coduri BCH(Bose/Chaudhuri/Hocquenghem)
7/25/2019 Coduri BCH
2/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
2
1. Cmpuri Galois GF(q)
1.2. Polinoame n cmp binar
Cele mai cunoscute cmpuri binare sunt cmpurile extinse ale
cmpului GF(2), cunoscuteisub denumirea GF(2m);
Aritmeticabinar utilizeaz operaiilede adunarei nmulire
modulo 2,
Un polinom f(X) definit ntr-un cmp GF(2) este de forma:
fi= 0sau1
Exist2n polinoame de gradn
Un element, , al cmpului este zero sau rdcin a
polinomului f(X) dac f() = 0. Dac este rdcin a
polinomuluif(X),rezult cX- este un factor al polinomului
f(X).
7/25/2019 Coduri BCH
3/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
3
1. Cmpuri Galois GF(q)
1.2. Polinoame n cmp binar
Un polinom p(X) definit n cmpul GF(2), de gradm este
ireductibildacp(X)nu se poate descompune n factori de
grad mai mare ca0imai mic dectm.
Un polinom ireductibil pi(X) de grad m este primitiv dac
existcel mai mic numrntreg n = 2m-1, pentru care pi(X)
este un factor al polinomului Xn+1.
7/25/2019 Coduri BCH
4/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
4
1. Cmpuri Galois GF(q)
1.3. Construcia cmpului Galois GF(2m)
Cmpul Galois extins GF(2m)conine elementele binare 1,0, elementul i puterile sale.
are urmtoarele proprieti:
conine 2m elemente.
7/25/2019 Coduri BCH
5/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
5
1. Cmpuri Galois GF(q)
1.3. Construcia cmpului Galois GF(2m)
Seconsiderpolinomul primitivpi(X)n cmpulGF(2)de gradm.
pi(X) este un factor al polinomuluiX2m-1
+1ipi()=0
Rezult care conine 2m elemente
7/25/2019 Coduri BCH
6/48
7/25/2019 Coduri BCH
7/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
7
1. Cmpuri Galois GF(q)
1.3. Construcia cmpului Galois GF(2m)
EXEMPLUL 1
Se consider m=3,pi(X)=1+X+X
3 polinom primitiv n cmpul GF(2)
Deoarece: pi()=1++3 =0 rezult3 =1+
Suma i produsul a dou elemente din cmpul GF(23
)
7/25/2019 Coduri BCH
8/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
8
1. Cmpuri Galois GF(q)
1.3. Construcia cmpului Galois GF(2m)
Tabelul 1
EXEMPLUL 1
7/25/2019 Coduri BCH
9/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
9
1. Cmpuri Galois GF(q)
1.3. Construcia cmpului Galois GF(2m)
EXEMPLUL 2
S se determine elementele cmpului Galois GF(24)generate de polinomul primitiv
pi(X)=1+X+X4
Deoarece: pi()=1++4 =0 rezult4 =1+
7/25/2019 Coduri BCH
10/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
10
Tabelul 2
EXEMPLUL 2
7/25/2019 Coduri BCH
11/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
11
1. Cmpuri Galois GF(q)
1.4. Proprieti ale cmpului extins Galois GF(2m)
Polinoamele definite n cmpul GF(2) au rdcini careaparincmpului extins GF(2m)
EXEMPLUL 3:
Polinomulpi(X)=1+X3+X4 este ireductibil n cmpul GF(2), rezult cnu
arerdcini n acest cmp, dar n schimb are 4 rdcini n cmpuluiextins Galois GF(24).
Se poate verifica, utiliznd tabelul 2c 7,11,13 i 14 suntrdcinilepolinomuluipi(X).
Rezult:
7/25/2019 Coduri BCH
12/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
12
1. Cmpuri Galois GF(q)
1.4. Proprieti ale cmpului extins Galois GF(2m)
EXEMPLUL 3:
Rezult:
7/25/2019 Coduri BCH
13/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
13
1. Cmpuri Galois GF(q)
1.4. Proprieti ale cmpului extins Galois GF(2m)
Teorem:
Fie f(X) este un polinom definit n cmpul GF(2). Dac un
element ceaparinecmpului extins Galois GF(2m) este o
rdcina polinomuluif(X), atunci pentru orice ntreg pozitivl
0,2leste de asemenea ordcina acestui polinom.
Elementul2lse numeteconjugatul lui.
7/25/2019 Coduri BCH
14/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
14
1. Cmpuri Galois GF(q)
1.4. Proprieti ale cmpului extins Galois GF(2m)
EXEMPLUL 4:
Se consider polinomul pi (X) = 1 + X3 + X4 definit pecmpulGF(2).7 - ordcina polinomuluipi(X)Rezult(7 )2=14, (7 )4=28 =13 i(7 )8=56 =11 sunt
rdciniale luipi(X)n acest exemplu severific, c rdcina =7satisfacecondiia:
7/25/2019 Coduri BCH
15/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
15
1. Cmpuri Galois GF(q)
1.5. Polinoame minimale
Polinomul de grad minim(X), definit n cmp GF(2), alcrui
rdcin este elementul , se numete polinomul minimal al
elementului.() = 0
Polinomul minimal al elementului0esteXipolinomul minimal
al elementului1este 1+X
7/25/2019 Coduri BCH
16/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
16
1. Cmpuri Galois GF(q)
1.5. Polinoame minimale
Proprieti:
Polinomul minimal al elementului ceaparinecmpului
Galois GF(2m) este un polinom ireductibil.
Fie un polinom f(X)definit n cmp GF(2) iun (X)-
polinom minimal al elementului . Dac este o
rdcin a polinomului f(X) rezult c (X) este un
factor a luif(X).
Polinomul minimal (X) al elementului definit n
cmpul cmpului Galois GF(2m) este un factor al
polinomului X2m
+X.
7/25/2019 Coduri BCH
17/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
17
1. Cmpuri Galois GF(q)
1.5. Polinoame minimale
Proprieti:
Fief(X)un polinom ireductibil definit n cmpul GF(2)i
un (X) unpolinom minimal al elementului definit n
cmpul Galois GF(2m) .Dac f() = 0atunci f(X) =(X)
Fie (X) unpolinom minimal al elementului definit n
cmpul Galois GF(2m) i ecel mai mic numr ntreg
pentru care este satisfcut relaia 2e= , polinomul
minimal al elementuluieste:
7/25/2019 Coduri BCH
18/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
18
1. Cmpuri Galois GF(q)
1.5. Polinoame minimale
Exemplul 5
Sse determine polinomul minimal (X) alelementului = 7
definit n cmpul Galois GF(24).
Din exemplul 4 seobserv c:
suntrdciniale polinomuluipentru care=7 esterdcin.
7/25/2019 Coduri BCH
19/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
19
1. Cmpuri Galois GF(q)
1.5. Polinoame minimale
Exemplul 5
Deoarece rezulte= 4.
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
20/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
20
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
BCH = R.C. Bose, K,Ray-Chaudhuri, A. Hocquenghem
coduri bloc
generalizare a codurilor Hamming
sunt construite pentru a corectaterori sau mai puine. sunt definite n cmpul binar GF(2)
metoda de construcie a acestor coduri se bazeaz pe
calculul celui mai mic multiplu comun (c.m.m.m.c.) al
polinoamelor minimale specifice
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
21/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
21
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
pentru oricenumrntreg pozitiv, m3it
7/25/2019 Coduri BCH
22/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
22
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
fieun element primitiv n cmpul GF(2m),
polinomul generator al codului BCH corector de t erori, cu
lungimea cuvntului de cod n = 2m-1,este polinomul de grad
minim n GF(2) alecrui rdcinisunt , 2, , 2t:
i iconjugatulsusuntrdcinilepolinomuluig(X),
dac i(X)este polinomul minimal al elementului i atunci
polinomul generator este:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
23/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
23
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
EXEMPLUL 4
Fie un element primitiv cmpul Galois GF(24) generat depolinomul primitivpi(X)=1+X+X4.(v. exemplul 2).Polinoamele minimale ale elementelor, 3 i 5 sunt:
Polinomul generator al codului BCH corector det=2eroriin =24-1 = 15este:
CBCH(n,k) = CBCH(15,7) , dmin 5
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
24/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
24
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
EXEMPLUL 4
Polinomul generator al codului BCH corector det=3eroriin =24-1 = 15este:
CBCH(n,k) = CBCH(15,5) , dmin 7
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
25/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
25
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
Fie codulCBCH(n,k)corector deterori sau maipuine
n = 2m-1lungimea cuvntului de cod
orice polinom al codului CBCH (n,k) va avea ca rdcini
elementele , 2
, , 2t
ielementele conjugatele. cuvntul de cod al codului CBCH(n,k) reprezentat sub form
polinomialeste:
elementul primitiv i este rdcina polinomului c(X).
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
26/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
26
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
Subform matriceal relaia anterioarseexprim:
Produsul scalar dintre cuvntul de cod ivectorulrdcinilor este egal cu zero.
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
27/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
27
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
28/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
28
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
Dac c este un cuvnt de cod, atunci:
Dac pentru anumite valori ale lui i i j, j este
conjugatul luii
, atunci c(j
)=0.Produsul dintre cu rndulial
matricei H este 0.
Rezult cunele rnduri ale matricei H pot fi omise.
Matricea H devine:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
29/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
29
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
Matricea H devine:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
30/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
30
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
EXEMPLUL 5
Fie codul binar BCH, CBCH(15,7) de lungime n = 24-1 = 15 ,corector de t=2erori sau mai puine i un element primitivcmpul Galois GF(24) generat de polinomul primitiv
pi(X)=1+X+X4. (v. exemplul 2).
Matricea de control aparitii,H, se poate scrie:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
31/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
31
2. Coduri BCH
2.1. Descrierea codurilor BCH ciclice
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
32/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
32
2. Coduri BCH
2.2. Decodarea codurilor BCH
Fie:
r(X)cuvntulrecepionatc(X)cuvntul de code(X)eroareaaprutn timpul transmisiei
Vectorul sindrom reprezint rezultatul verificrii cuvntuluirecepionat;coninedate(informaie)desprepoziia i numrulerorilor din cuvntulrecepionat.
Rezult:vectorul sindrom pentru decodarea codurilor BCH:
7/25/2019 Coduri BCH
33/48
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
34/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
34
2. Coduri BCH
2.2. Decodarea codurilor BCH
EXEMPLUL 6
Fie codul binar BCH, CBCH (15,7) de lungime n = 24-1 = 15 ,corector det=2erori sau maipuine. Vectorulrecepionateste deformar=(1000000010000000).
Sse determine vectorul sindrom.r(X) = 1+X8formapolinomial
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
35/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
35
2. Coduri BCH
2.3. Polinoame utilizate pentru localizarea erorilor i evaluarea erorilor
Seconsider cvectorul eroareconine erori plasate npoziiile:
Se numete locator (al erorii de pe poziia i din cuvntulrecepionat), elementul cmpului GF(2q), ce este puterea l aelementului generator al cmpului:
Componentele vectorului sindrom secalculeazcurelaia:
rezultun sistem cu 2tecuaii:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
36/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
36
2. Coduri BCH
2.3. Polinoame utilizate pentru localizarea erorilor i evaluarea erorilor
Rezultun sistem cu 2tecuaii:
variabile necunoscute.
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
37/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
37
2. Coduri BCH
2.3. Polinoame utilizate pentru localizarea erorilor i evaluarea erorilor
Algoritmul care va rezolva acest sistem de ecuaii este un
algoritm de decodare a codului BCH binar.
Variabilele necunoscuteprecizeaz poziiaerorilor.
Polinomul erorilor (x) - polinomul ale crui rdcini suntlocatorii erorilor
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
38/48
TEORIA TRANSMITERII INFORMAIEI
16.11.2012
38
2. Coduri BCH
2.3. Polinoame utilizate pentru localizarea erorilor i evaluarea erorilor
Polinomul erorilor (x)-polinomul ale crui rdcini sunt
locatorii erorilor
Polinomul utilizat pentru evaluarea erorilor
Valoare erorii se poate calcula curelaia:
Polinomul sindrom de grad este definit:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
39/48
16.11.2012
39
2. Coduri BCH
2.3. Polinoame utilizate pentru localizarea erorilor i evaluarea erorilor
Ecuaie cheie (Key ecuation) = relaie ntre polinoamele (X),
S(X), i W(X)
Rezolvarea ecuaiei cheie reprezint un algoritm pentru
decodarea codului BCH. Teorem: Exist un polinom (X), astfel nct ntre
polinoamele (X), S(X), i W(X) exist urmtoarea ecuaie
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
40/48
16.11.2012
40
2. Coduri BCH
2.3. Polinoame utilizate pentru localizarea erorilor i evaluarea erorilor
Demonstraie:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
41/48
16.11.2012
41
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Fiedounumere AiB. Algoritmul Euclideandetermincel
mai mare divizor comun al acestor dou numere, C=
c.m.m.d.c.(A, B), i de asemenea determin dou numere
ntregi (doupolinoame) SiT, astfel nct
Acest algoritm este util pentru a rezolvaecuaia:
unde: X2t >> A iS(X) >> B
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
42/48
16.11.2012
42
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Algoritmul Euclidean
Fie A i B dou numere ntregi (AB ) sau dou polinoame
(grad(A)grad(B))
Condiii iniiale: r1= A i r0= B
ri
se obine ca fiind restul mpririi dintre ri-2
i ri-1
condiiile iniiale sunt:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
43/48
16.11.2012
43
http://stud.usv.ro/TTI/CURS/
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Exemplul 7
Fie:
Rezult: c.m.m.d.c. (112,54) =2
TEORIA TRANSMITERII INFORMAIEI
http://stud.usv.ro/TTI/CURS/http://stud.usv.ro/TTI/CURS/7/25/2019 Coduri BCH
44/48
16.11.2012
44
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Se va aplica algoritmul Euclideanecuaiei:
Rezult:
nmulim cu relaia anterioar;
Unde:
Rezult:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
45/48
16.11.2012
45
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Exemplul 8
Fie codul binar BCH, CBCH (15,7) de lungime n = 24-1 = 15, corectorde t=2erori sau mai puine. Vectorul recepionat este de formar=(1000000010000000).S se determine utiliznd algoritmul euclideandecoded code polynomial. (polinomul de decodarea a codului)
Componentele vectorului sindrom sunt: (ex. 6)
Rezult polinomul sindrom:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
46/48
16.11.2012
46
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Algoritmul este ntrerupt atunci cnd gradul polinomului ri(X) estemai mic dect gradul polinomului din coloana t
i
(X).
Exemplul 8
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
47/48
16.11.2012
47
2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanExemplul 8 Polinomulti(X)estenmulitcu un factorGF(24). =
Rezult:
Se va nlocui variabilaXn the polinomul (X) cu 1,, 2
, . . . ,n1, unden= 2m1. Deoarece n = 1 and h = nh, atunci dac h este o
rdcin a polinomului (X), nh este locatorul erorii, caredetermin poziia,rnh, aerorii.
Se vor calcula apoi:
TEORIA TRANSMITERII INFORMAIEI
7/25/2019 Coduri BCH
48/48
16.11.2012
2. Coduri BCH
2.4. Decodarea codului binar BCH utiliznd Algoritmul Euclidean
Exemplul 8