2749771994

Kody wykrywające i korygujące błędy - konspekt wykładu 2006/07    12

Dla każdego kodu liniowego, istnieje równoważny mu kod, którego macierz generująca ma postać standardową.

Przykład 2.3. Macierze

' 1	0 ■		1	0 '
1	1	i G2 =	0	1
1	0		1	0
. 0	1.		_ 1	1.

są macierzami generującymi (4,2)-kodu C = {0000,0101,1011,1110}.    □

(n, /c)-kod liniowy generowany przez macierz G = /jp €    możemy

zdefiniować również nieco inaczej. Z równań (2) otrzymujemy następującą zależność:

k

y,puvi+v_k+i = o,

i—1

i    (3)

k

J2P(n-k)iVi+V_n = 0.

Stąd dla macierzy H := P\I_n-k G    kod C = {v G GF(q)ⁿ\Hv^T =

Or-a;}- Warunek ten oznacza, że każdy wektor v G C jest ortogonalny do każdego wiersza macierzy H. Otrzymane w ten sposób równości (3) noszą nazwę równości kontroli parzystości.

Definicja 2.4. Macierz H — P\I_n~k € Mjj__k nazywamy macierzą kontroli parzystości (n,k)-kodu liniowego generowanego przez macierz G = /jp G

M^kn-_k-

Opis (3) daje elegancki układ równań. Każda niewiadoma (symbol sprawdzający) występuje dokładnie raz w każdym równaniu a równań jest tyle, ile symboli sprawdzających.

Lemat 2.5. Kod liniowy długości n ma wymiar k wtedy i tylko wtedy, gdy jego macierz kontroli parzystości ma rząd n — k.