2749771995

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

Macierz generująca i macierz kontroli parzystości (n, fc)-kodu linowego są ze sobą ściśle związane, gdyż

HG = 0_k oraz G^TH^T= 0_k.

Przykład 2.6. Macierz

H =

10 10] 1 1 0 1 J

jest macierzą kontroli parzystości (4,2)-kodu C = {0000,0101,1011,1110} z przykładu 2.3.    □

Definicja 2.7. Wektor Hv^T nazywamy syndromem słowa v G GF(q)ⁿ.

W przypadku kodów liniowych, jeśli wektory u, v G C to również wektor u — v G C. Ponieważ d(u,v) = wt(u — v), gdyż obie strony wyrażają liczbę miejsc na których wektory u i u się różnią, zatem, aby znaleźć odległość kodu liniowego nie trzeba porównywać wszystkich par słów kodowych.

Twierdzenie 2.8. Odległość kodu liniowego równa jest minimalnej wadze niezerowych słów kodowych.

Inny sposób określania odległości kodu liniowego daje następujący lemat.

Lemat 2.9. Niech H będzie macierzą kontroli parzystości liniowego kodu C. Wówczas kod C ma odległość równą d wtedy i tylko wtedy, gdy każde d — 1 kolumn macierzy H jest liniowo niezależnych i pewne d kolumn tej macierzy jest liniowo zależnych.

Zatem odległość kodu liniowego jest minimalną liczbą liniowo zależnych kolumn macierzy kontroli parzystości natomiast ilość symboli kontrolnych jest maksymalną liczbą liniowo niezależnych kolumn tej macierzy.

Jeśli (n, fc)-kod liniowy ma odległość równą d to powiemy o nim, że jest {n,k,d)~kodem liniowym. Zatem {n,k,d)~kody liniowe są (n, 2^fc,d)-kodami systematycznymi, dla których współczynnik sprawności R =

Jeśli u G C jest słowem kodowym kodu liniowego, wówczas liczba słów kodowych v G C, dla których d(u,v) = wt(u — v) = i równa jest liczbie Ai słów kodowych o wadze i.