Codul Golay

7/23/2019 Codul Golay

1/7

Codul Golay

Are capacitatea de corectie pentru maxim 3 erori.

Codul Golay binar extins

Acest cod a fost folosit de programul spa ial Voyager la nceputul anilor 80,

la transmiterea fotografiilor planetelor Jupiter i Saturn.

Se consider matricea !"! din figura de mai #os$

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0

B=

0 0

0 0 0 0 0

0 0 0 0 0

0

%ie G matricea !X !& G ' (I12|B). Codul liniar *inar generat de G se nume te

codul Golay extins i +a fi notat !&C .

Observa ii :

limin-nd ultima linie i coloan, matricea rmas s spunem B este

generat ciclic (spre st-nga) de cu+-ntul *inar 00000. /eci

0

TB

B

=

unde ' . +ident, B este simetrica ( TB B= ).

!&C

are n ' !&; k ' ! si

!

! &012= cu+inte cod.


2/7

Conform eoremei de mai #os o matrice de control a codului esteH ' (B |

I12).

Teorema. Un cod sisteatic cu atricea generatoare G ' (I|B) adite ca

atrice de control H ' (!BT|I"#

Teorema. H ' (I12|B).este de aseenea atrice de control $entru !&C #

%eonstratie$ 4iniile dinB au pondere impara (5 sau )6 deci produsul (scalar)

al unei linii cu ea 7nsasi este . +erificare simpla arata ca produsul primei linii

cu oricare alta linie dinB este 0. Structura ciclica a luiB asigura ca atunci

produsul scalar al oricaror doua linii este 0.

9n conclu:ie, !T

BB I= . /ar TB B= , asa ca putem scrie$

! !

( ; ) 0.T TGH I B I B I BB I I B

= = + = + = + =


3/7

i *) r r= + . /eoarece !&C este auto dual, + si rSau un numar par (sa

:icem !y) de elemente 7n comun. /eci ( ) ( ) ( ) !(! )s+ ) + ) + r y= + care

este multiplu de &.

%olosind acum un procedeu de inductie, cum orice cu+ant cod este com*inatie

liniara de linii din G, ponderea sa +a fi multiplu de &.

2. (riele 11 linii din G sunt cu)inte ! cod de $ondere ,- deci distanta codului

!&C este . sau ,.

3. !&C nu are cu)inte de $ondere &.

Sa presupunem ca exista !&) C cu +(+) ' &. xist>a atunci!

! !u u /

cu ( ; )) u I B= ; ! ( ; )) u I B= /eoarece exista o #umatate din + care are cel

putin doi de , re:ulta ( ) !+ u sau !( ) !+ u . ?e dealta parte, suma

a una sau doua linii dinB nu poate a+ea o pondere mai mica de &6 deci

( ) ( ) ( ) &+ ) + u + u B= + > , contradictie.

Decodificarea codului Golay extins

Conform eoremei &'", un cod Golay extins poate corecta orice com*inatie de

maxim 3 erori.


4/7

! ! !

! !

A , B .B B

s u u u u u B uI I

= = = + +

.

/e aici re:ulta urmatoarea o*ser+atie$ daca !( ) + u , atunci s este sau un

cu+ant de pondere maxim 3 (daca !( ) 0+ u = ), sau o linie a luiB cu cel mult doi

*iti scim*ati (daca !( ) + u = ).

Similar, daca ( ) + u , atunci !s este sau un cu+ant de pondere maxim 3 sau

o linie a luiB cu cel mult doi *iti scim*ati.

/aca se foloseste si faptul ca ! ! ! ( )s u B u u u B B s B= + = + = (deci se

poate folosi doar prima matrice de control), putem defini urmatorul algoritm de

decodificare a codurilor Golay extinse$

Algoritm C:

1. Se calculeaa sindromul s ! aH"

2. Daca w#e$ 3% atunci e ! &s; '(% ST)*.

3. Daca exista o linie i0 a luiB cu w#s + i0 $ 2% atunci e ! &s + bi; ei(%

ST)*.

,. Daca w#sB$3% atunci e ! &'; sB(% ST)*.

-. Daca exista o linie bi a luiB cu w#sB+bi$ 2% atunci e ! &ei; sB+bi(%

ST)*.

. Daca e nu a fost determinat inca% se cere retransmiterea.

Sa notat cu ei un cu+ant de lungime ! cu pe po:itia i si 0 7n rest.

/upa determinarea erorii e, cu+antul cod transmis se determina prin + ' a @ e.

/xem0lul 1. a decodiica cu)antul a ' 00; 00000000#

indroul este

s ' aHT' 00 @ 0000 ' 0000000000#

%eoarece +(s) ' ! 3- se gaseste e ' s; 0B ' 0000000000; 000000000000


5/7

deci s!a transis cu)antul + ' a @ u ' 0000; 00000000#

/eoarece G ' (I12|B) este 7n forma esalonat canonica, mesa#ul de informatie

(orice cu+ant din !!/ ) apare pe primele ! po:itii ale cu+antului cod. Astfel, 7n

exemplul de sus, mesa#ul de informatie a fost 0000.

/xem0lul 2. e cere decodiicarea cu)antului a ' 0000000;

00000000#

indroul este s ' aH ' 0000000 @ 00000000 ' 0000000#

%eoarece +(s) ' D- se trece la $asul 3 al 3lgoritului C si se calculea4a5

s @ * ' 00000000

s @ *! ' 000000

s @ *3 ' 0000

s @ *& ' 00000000

s @ *D ' 0000000000

%eoarece +(s @ *D) !- se deterina

e ' s @ *D; eDB ' 0000000000; 00000000000

si se decide ca s!a transis cu)antul ! cod

+ ' a @ e ' 00000; 0000000#

/xem0lul 3. a decodiica cu)antul a ' 000000; 0000000#

indroul estes ' aHT' u @ u!B ' 000000 @ 00000 ' 00000

care are $onderea 5# Trecand la $asul 3se gaseste +(s @ *i) 3$entru toate

liniile lui B; deci se continua cu $asul &5 al doilea sindro este

sB ' 000 cu $onderea 8# (asul D )a da5

sB @ * ' 000000

sB @ *! ' 0000

sB @ *3 ' 000000


6/7

sB @ *& ' 0000000000

!a a*uns la +(sB @ *&) !- deci se $oate deterina eroarea5

e ' e&; sB @ *&B ' 00000000000; 0000000000

deci cu)antul ! cod transis a ost5

+ ' a @ e ' 0000000; 000000000#

Codul Golay

?rin relaxarea codului Golay extins (eliminarea ultimului *it din fiecare cu+ant

cod) se a#unge la Codul Golay 0inar.

%ie EB matricea !x o*tinuta dinBprin eliminarea ultimei coloane. /efinim

G ' (I12|B). Codul liniar *inar generat de G se numeste codul Golay si este notat

cu !3C . Caracteristicile sale sunt$

n ' !3; k ' !;=umar de cu+inte cod$ !! &012= #

+ident, extensia lui !3C este !&C .

Teorema.%istanta unui cod Golay este d ' 5#

%eonstratie$ /emonstratia se poate face fie direct (similar celei de la eorema

(F)) fie folosind faptul ca !3C este relaxarea codului !&C , care are distanta 8.

9n consecinta, un cod Golay +a corecta orice com*inatie de maxim 3 erori.

Teorema. Codul Golay este $erect#

%eonstratie$ Se +erifica relatia$

! 0 ! 3 ! ! !3

!3 !3 !3 !3! ( ) ! ( !3 !D3 55) ! ! !C C C C + + + = + + + = =

e:ulta ca orice cu+ant a !3!a / se afla la distanta maxim 3 de un cu+ant cod.

Astfel, daca se adauga la sfarsit 0 sau , formand 0a respecti+ a pentru a o*tine

un cu+ant de pondere impara, acest cu+ant este la distanta maxim 3 de un cu+ant

cod !&c C . Se foloseste Algoritmul C pentru a o*tine acest cu+ant cod, apoi

se elimina ultimul caracter din c6 se a#unge astfel la cel mai apropiat cu+ant

cod din C!3 fata de a.

Algoritmul D:


7/7

1. Se formeaa cuantul extins de 0ondere im0ara 0a sau a "

2. Se decodifica ia folosind Algoritmul C si se obtine !&c C "

3. Se elimina ultimul caracter din c.

/xem0lu. a decodiica a ' 00000000; 0000#

%eoarece a are $ondere i$ara- se construieste

0a ' 00000000; 00000#

indroul acestui cu)ant este s' 00000#

(entru ca s' *2@ e1@ e!- 0a se decodiica in

0000000000; 000000- asa ca a este decodiicat 6n 0000000000;

00000#

Codul Golay

Documents

Transcript of Codul Golay