Coduri BCH

Date post:27-Feb-2018
Category:
View:230 times
Download:0 times
Share this document with a friend
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

Embed Size (px)
Recommended