2749772006

5

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

Definicja 1.10. Zbiór

K_r(u) := {v e GF(q)ⁿ \ d(u,v) < r} nazywamy kulą o promieniu r i środku u.

Definicja 1.11. Minimalną odległością nietrywialnego kodu C nzaywamy d := min{d(u, v) \ u,v G C,u v}.

Ponieważ w praktyce trudno jest dokładnie obliczyć prawdopodobieństwo błędu po dekodowaniu, odległość kodu jest bardzo dobrą miarą "dobroci” kodu. Podczas transmisji wektor kodowy może przejść przez kanał bez zmiany (nie wystąpiły żadne błędy), może zostać zmieniony na inne słowo kodowe lub zostać zmieniony na wektor niekodowy. Dekoder jest tak skonstruowany, że odróżnia słowa kodowe od ciągów niekodowych. Gdy na skutek błędów wektor kodowy zostanie zamieniony na inny wektor kodowy, wówczas dekoder nie ma możliwości odróżnienia błędnie odebranego słowa i nie może wykryć żadnego błędu. Natomiast ciągi niekodowe umożliwiają dekoderowi wykrycie błędów. Na przykład, aby mieć możliwość wykrycia wszystkich pojedynczych błędów odległość kodu musi być co najmniej 2, gdyż inaczej błąd na jednej pozycji może przekształcić jedno słowo kodowe w inne słowo kodowe.

Twierdzenie 1.12. Warunkiem koniecznym i dostatecznym na to, aby dany kod umożliwiał wykrycie t lub mniej błędów jest, aby odległość kodu była równa co najmniej t + 1.

Rolą dekodera jest nie tylko wykrywać, ale także poprawiać zlokalizowane błędy. W praktyce powszechnie stosowana jest strategia dekodowania z maksymalną wiarygodnością. Polega ona na tym, iż dekoder analizując odebrany wektor, znajduje słowo kodowe różniące się od ciągu odebranego najmniejszą liczbą pozycji (najbliższe w sensie odległości słowo kodowe) i przyjmuje, że właśnie taki ciąg został wysłany.

Jeśli odległość kodu C wynosi d oznacza to, że dowolne dwa słowa kodowe różnią się na co najmniej d miejscach. Stąd kule K_r(u) o promieniu r = [|(d—

1)] wokół słów kodowych u 6 C są rozłączne, ([rr] := max{n € Z|n < z}.)

Twierdzenie 1.13. KodC o odległości d może poprawić do [\{d—1)] błędów.