TEORIA TRANSMISIEI INFORMAIEI

TEORIA TRANSMITERII INFORMAtIEI~ CURS VII ~S.l. dr. ing. Alexandra Ligia BalanCoduri BCH(Bose/Chaudhuri/Hocquenghem)

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20123http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.2. Polinoame n cmp binarCele mai cunoscute cmpuri binare sunt cmpurile extinse ale cmpului GF(2), cunoscute i sub denumirea GF(2m);Aritmetica binar utilizeaz operaiile de adunare i nmulire modulo 2,Un polinom f(X) definit ntr-un cmp GF(2) este de forma:fi = 0 sau 1Exist 2n polinoame de grad nUn element, , al cmpului este zero sau rdcin a polinomului f(X) dac f() = 0. Dac este rdcin a polinomului f(X), rezult c X- este un factor al polinomului f(X).

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20124http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.2. Polinoame n cmp binarUn polinom p(X) definit n cmpul GF(2), de grad m este ireductibil dac p(X) nu se poate descompune n factori de grad mai mare ca 0 i mai mic dect m.

Un polinom ireductibil pi(X) de grad m este primitiv dac exist cel mai mic numr ntreg n = 2m-1, pentru care pi(X) este un factor al polinomului Xn+1.

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20125http://stud.usv.ro/TTI/CURS/ 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.

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20126http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.3. Construcia cmpului Galois GF(2m)Se consider polinomul primitiv pi(X) n cmpul GF(2) de grad m.

pi(X) este un factor al polinomului X2m-1+1 i pi()=0

Rezult care conine 2m elemente

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20127http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.3. Construcia cmpului Galois GF(2m)Mulimea este un grup de ordin 2m -1 fa de operaia de nmulire.

Elementele mulimii respect proprietatea de comutativitate fa de operaia de adunare.

Rezult:

mulimea este un cmp Galois sau un cmp finit cu 2m elemente.

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20128http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.3. Construcia cmpului Galois GF(2m)EXEMPLUL 1

Se consider m=3, pi(X)=1+X+X3 polinom primitiv n cmpul GF(2)

Deoarece: pi()=1++3 =0 rezult 3 =1+

Suma i produsul a dou elemente din cmpul GF(23)

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.20129http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.3. Construcia cmpului Galois GF(2m)

Tabelul 1EXEMPLUL 1TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201210http://stud.usv.ro/TTI/CURS/ 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 rezult 4 =1+

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201211http://stud.usv.ro/TTI/CURS/ Tabelul 2EXEMPLUL 2

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201212http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.4. Proprieti ale cmpului extins Galois GF(2m)Polinoamele definite n cmpul GF(2) au rdcini care aparin cmpului extins GF(2m)

Exemplul 3:

Polinomul pi(X)=1+X3+X4 este ireductibil n cmpul GF(2), rezult c nu are rdcini n acest cmp, dar n schimb are 4 rdcini n cmpului extins Galois GF(24).

Se poate verifica, utiliznd tabelul 2 c 7, 11, 13 i 14 sunt rdcinile polinomului pi(X).

Rezult:TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201213http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.4. Proprieti ale cmpului extins Galois GF(2m)Exemplul 3:

Rezult:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201214http://stud.usv.ro/TTI/CURS/ 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 ce aparine cmpului extins Galois GF(2m) este o rdcin a polinomului f(X), atunci pentru orice ntreg pozitiv l 0, 2l este de asemenea o rdcin a acestui polinom.

Elementul 2l se numete conjugatul lui .

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201215http://stud.usv.ro/TTI/CURS/ 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 pe cmpul GF(2). 7 - o rdcin a polinomului pi (X) Rezult (7 )2= 14, (7 )4= 28 = 13 i (7 )8= 56 = 11 sunt rdcini ale lui pi (X)n acest exemplu se verific, c rdcina = 7 satisface condiia:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201216http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.5. Polinoame minimalePolinomul de grad minim (X), definit n cmp GF(2), al crui rdcin este elementul , se numete polinomul minimal al elementului . () = 0Polinomul minimal al elementului 0 este X i polinomul minimal al elementului 1 este 1+X TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201217http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.5. Polinoame minimaleProprieti:Polinomul minimal al elementului ce aparine cmpului Galois GF(2m) este un polinom ireductibil.Fie un polinom f(X) definit n cmp GF(2) i un (X) - polinom minimal al elementului . Dac este o rdcin a polinomului f(X) rezult c (X) este un factor a lui f(X).Polinomul minimal (X) al elementului definit n cmpul cmpului Galois GF(2m) este un factor al polinomului X2m+X.TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201218http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.5. Polinoame minimaleProprieti:Fie f(X) un polinom ireductibil definit n cmpul GF(2) i un (X) un polinom minimal al elementului definit n cmpul Galois GF(2m) . Dac f() = 0 atunci f(X) = (X) Fie (X) un polinom minimal al elementului definit n cmpul Galois GF(2m) i e cel mai mic numr ntreg pentru care este satisfcut relaia 2e= , polinomul minimal al elementului este:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201219http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.5. Polinoame minimaleExemplul 5

S se determine polinomul minimal (X) al elementului = 7 definit n cmpul Galois GF(24).

Din exemplul 4 se observ c:

sunt rdcini ale polinomului pentru care = 7 este rdcin.

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201220http://stud.usv.ro/TTI/CURS/ 1. Cmpuri Galois GF(q)1.5. Polinoame minimaleExemplul 5

Deoarece rezult e= 4.

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201221http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.1. Descrierea codurilor BCH ciclice BCH = R.C. Bose, K,Ray-Chaudhuri, A. Hocquenghem coduri bloc generalizare a codurilor Hamming sunt construite pentru a corecta t erori 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 specificeTEORIA TRANSMITERII INFORMAIEI CURS 716.11.201222http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.1. Descrierea codurilor BCH ciclicepentru orice numr ntreg pozitiv, m3 i t> A i S(X) >> B

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201243http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanAlgoritmul EuclideanFie A i B dou numere ntregi (AB ) sau dou polinoame (grad(A)grad(B))Condiii iniiale: r1 = A i r0 = Bri se obine ca fiind restul mpririi dintre ri-2 i ri-1

condiiile iniiale sunt:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201244http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanExemplul 7 Fie:

Rezult: c.m.m.d.c. (112,54) =2TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201245http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanSe va aplica algoritmul Euclidean ecuaiei:

Rezult:

nmulim cu relaia anterioar;

Unde:

Rezult:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201246http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanExemplul 8Fie codul binar BCH, CBCH (15,7) de lungime n = 24-1 = 15 , corector de t=2 erori sau mai puine. Vectorul recepionat este de forma r=(1000000010000000). S se determine utiliznd algoritmul euclidean decoded code polynomial. (polinomul de decodarea a codului)

Componentele vectorului sindrom sunt: (ex. 6)

Rezult polinomul sindrom:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201247http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanAlgoritmul este ntrerupt atunci cnd gradul polinomului ri(X) este mai mic dect gradul polinomului din coloana ti(X).

Exemplul 8TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201248http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanExemplul 8Polinomul ti(X) este nmulit cu un factor GF(24). =Rezult:

Se va nlocui variabila X n the polinomul (X) cu 1, , 2, . . . , n1, unde n = 2m 1. Deoarece n = 1 and h = nh, atunci dac h este o rdcin a polinomului (X), nh este locatorul erorii, care determin poziia, r nh , a erorii.Se vor calcula apoi:

TEORIA TRANSMITERII INFORMAIEI CURS 716.11.201249http://stud.usv.ro/TTI/CURS/ 2. Coduri BCH2.4. Decodarea codului binar BCH utiliznd Algoritmul EuclideanExemplul 8