+ All Categories

Download - Coduri BCH

Transcript
  • 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


Top Related