Coduri BCH

7/25/2019 Coduri BCH
1/48
Coduri BCH(Bose/Chaudhuri/Hocquenghem)

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).

3/48
16.11.2012
3
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.

4/48
16.11.2012
4
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.

5/48
16.11.2012
5
Seconsiderpolinomul primitivpi(X)n cmpulGF(2)de gradm.
pi(X) este un factor al polinomuluiX2m-1
+1ipi()=0
Rezult care conine 2m elemente

6/48

7/48
16.11.2012
7
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
)

8/48
16.11.2012
8
Tabelul 1
EXEMPLUL 1

9/48
16.11.2012
9
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+

10/48
16.11.2012
10
Tabelul 2
EXEMPLUL 2

11/48
16.11.2012
11
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:

12/48
16.11.2012
12
EXEMPLUL 3:
Rezult:

13/48
16.11.2012
13
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.

14/48
16.11.2012
14
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:

15/48
16.11.2012
15
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

16/48
16.11.2012
16
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.

17/48
16.11.2012
17
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:

18/48
16.11.2012
18
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.

19/48
16.11.2012
19
Exemplul 5
Deoarece rezulte= 4.

20/48
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

21/48
16.11.2012
21
2. Coduri BCH
pentru oricenumrntreg pozitiv, m3it

22/48
16.11.2012
22
2. Coduri BCH
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:

23/48
16.11.2012
23
2. Coduri BCH
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

24/48
16.11.2012
24
2. Coduri BCH
EXEMPLUL 4
Polinomul generator al codului BCH corector det=3eroriin =24-1 = 15este:
CBCH(n,k) = CBCH(15,5) , dmin 7

25/48
16.11.2012
25
2. Coduri BCH
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).

26/48
16.11.2012
26
2. Coduri BCH

Date post:	27-Feb-2018
Category:	Documents
View:	230 times
Download:	0 times

Coduri BCH

Documents

Indesit coduri piese

Coduri vopsea Espero

Coduri Postale Craiova

Codificare CPV coduri selectare

Guvern coduri fiscale_prezentare_25_mar_2015

coduri vivanco UR 89