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 12X12 din figura de mai jos:

Fie G matricea 12X 24 G = (I12|B). Codul liniar binar generat de G se numește

codul Golay extins și va fi notat .

Observații:

Eliminând ultima linie și coloană, matricea rămasă - să spunem B1 - este generată ciclic (spre stânga) de cuvântul binar 11011100010. Deci unde 1 = 11111111111. Evident, B este simetrica ( ).

- are n = 24; k = 12 ¸si cuvinte - cod.

- Conform Teoremei de mai jos o matrice de control a codului este H = (B |I12).

Teorema. Un cod sistematic cu matricea generatoare G = (I|B) admite ca

matrice de control H = (-BT|I).

Teorema. H = (I12|B).este de asemenea matrice de control pentru .

Demonstratie: Liniile din B au pondere impara (7 sau 11); deci produsul (scalar)

al unei linii cu ea ınsasi este 1. O verificare simpla arata ca produsul primei linii cu oricare alta linie din B este 0. Structura ciclica a lui B1 asigura ca atunci produsul scalar al oricaror doua linii este 0.

In concluzie, . Dar , asa ca putem scrie:

Vom folosi ambele matrici de control pentru decodificarea codului .

Corolar.

A. admite ca matrice generatoare si pe G = (B |I12).

B. Codul Golay extins este auto - dual .

Demonstratie: Se verifica imediat.

Teorema. are distanta minima d = 8. (*)

Demonstratie: Vom demonstra afirmatia ın trei pasi.

1. Ponderea cuvintelor din este multiplu de 4.

Sa observam ca liniile lui G au pondere 8 sau 12. Fie ca suma de doua linii din G : . Cum B are liniile ortogonale, rezulta ca si liniile lui

G sunt ortogonale. Deci ¸si au un numar par (sa zicem 2x) de elemente 1

ın comun. Atunci care este multiplu de 4.