2749772007

6

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

Strategia dekodowania z maksymalną wiarygodnością nie jest jedyną możliwą. Czasami stosuje się niepełną strategię dekodowania. W takim przypadku dekoder poprawia pewną ustaloną liczbę błędów, a gdy wystąpi ich więcej jedynie informuje o tym lub prosi o retransmisję tych danych, w których wystąpiło więcej błędów.

Odległość kodu determinuje ilość błędów, które można wykryć lub poprawić. Często jednak potrzeba więcej informacji na temat odległości między słowami kodowymi.

Definicja 1.14. Niech Ci C C będzie podzbiorem słów kodowych o wadze i.

Niech Ai := \Ci\. Ciąg (A₀, Ai,..., A_n) nazywamy rozkładem wagi kodu C.

Definicja 1.15. Numeratorem kodu C nazywamy wielomian

Wc(x,y) := £Axⁿ-y =

i=0    u&C

Przykład 1.16. Niech C = {00,11}. Wówczas — 1, Ai = 0, A₂ = 1 oraz Wc(x,y) = x² + y².

Kod C = {000,100,010,110} ma rozkład A₀ = 1, A, = 2, A₂ = 1, A₃ = 0 oraz

Wc(x, y) = x³ + 2 x²y + xy².

□

Definicja 1.17. Dwa kody Ci iCi długości n nad ciałem GF(q) są równoważne, jeśli istnieje permutacja 7r E S_n taka, że (ui,... ,u_n) E C\ wtedy i tylko wtedy, gdy (u^i),..., u_n(_n)) E C₂.

Przykład 1.18. Kody Ci = {0000,0011,1100,1111} oraz C₂ = {0000,0101,

1010,1111} są równoważne.    □

Kody równoważne zachowują odległość między słowami kodowymi zatem mają dokładnie takie same własności dotyczące zdolności poprawiania i korygowania błędów. Jeśli jeden z nich można odkodować to można i równoważny.