2749772000

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

O < i < t.

Dla i > t wartość a* jest niezwykle trudno obliczyć i jest znana tylko dla kilku kodów.

Jeśli prawdopodobieństwo (1 — p) popełnienia błędu przy przesyłaniu pojedynczego symbolu jest małe, to p « 1 oraz

(1 -p)*p⁽ⁿ ^ > (1 -p)^{t+1)p^{{n 1}

lub

W tym przypadku część wzoru (4) dotycząca dużych i jest mało znacząca i wówczas

„Tl—t— 1

są wygodnymi przybliżeniami.

Metoda logicznej większości. Niech dla (n, fc)-kodu liniowego równania (3) kontroli parzystości będą takie, że dla pewnego 1 < i < k zmienna Vi występuje w każdym równaniu układu oraz dla każdego j / i zmienna Vj występuje co najwyżej w jednym równaniu.

Załóżmy, że dekoder otrzymuje słowo x E GF(q)ⁿ, w którym wystąpiło t < \{n — k) błędów. Jeśli symbol Xi jest przesłany poprawnie, to co najwyżej t równań układu (3) będzie różnych od zera. Jeśli natomiast zmienna Xi jest niepoprawna, to co najmniej n — k — (t — 1) równań jest różnych od zera. Ponieważ n — k — (t — 1) > t to liczba równań równych 0 decyduje, czy symbol Xi został przesłany poprawnie czy też nie. Jeśli co najwyżej t równań układu (3) jest różnych od zera to zmienna Xi jest poprawna, jeśli jednak co najmniej t + 1 równań jest różnych od zera, na pozycji i wystąpił błąd.

Przykład 2.21. Niech C będzie (7,4)-kodem binarnym o następujących równaniach kontroli parzystości:

xi+x₂ + x₃ = 0,

X\ + Xą + £5 = 0,

Xi+Xq+X₇ = 0.