Kody i szyfry
4. Kody wykrywające i korygujące błędy
4.2. Wykrywanie błędów metodą kontroli parzystości
Wykrywanie błędów metodą kontroli parzystości jest najprostszą często stosowaną metodą wykrywania błędów.
Załóżmy, że w systemie cyfrowym chcemy przesyłać dane porcjami za pomocą słów n bitowych. Niech x1x2...xn ∈ {0,1}n będzie takim n bitowym słowem. Przed wysłaniem uzupełniamy to słowo jeszcze jednym bitem xn+1 tzw. bitem parzystości przy czym
xn+1 = 1 jeśli liczba jedynek w słowie x1x2...xn ∈ {0,1}n jest nieparzysta
xn+1 = 0 jeśli liczba jedynek w słowie x1x2...xn ∈ {0,1}n jest parzysta
Zatem słowo przesyłane x1x2...xnxn+1 zawiera zawsze parzystą liczb jedynek. Łatwo sprawdzić, że układ generujący bit parzystości jest n wejściową sumą modulo 2.
xn+1 = x1 ⊕ x2 ⊕ ... ⊕ xn
Nadajnik wysyła słowo n+1 bitowe x1x2...xnxn+1 a w odbiorniku dostajemy słowo być może z błędami (przekłamaniami) y1y2...ynyn+1 ∈ {0,1}n+1. Sprawdzamy parzystość liczby jedynek w słowie binarnym odebranym y1y2...ynyn+1. Układ sprawdzający czy liczba jedynek jest parzysta jest n+1 wejściową sumą modulo 2 (por. Rys.2). Jeśli liczba jedynek w słowie y1y2...ynyn+1 jest parzysta to na wyjściu układu mamy 0 jeśli nieparzysta to 1.
Jeśli wysłaliśmy parzystą liczbę jedynek a otrzymaliśmy w odbiorniku nieparzystą tzn., że podczas przesyłania wystąpił błąd. Sprawdzając parzystość wykryjemy każdą nieparzystą ilość błędów.
Zamiast funkcji xn+1 = x1 ⊕ x2 ⊕ ... ⊕ xn można wykorzystać funkcję xn+1 = 
, wtedy przesyłane słowo będzie zawierało nieparzystą liczbę jedynek.
Pewną modyfikacją opisanej wyżej koncepcji są kody ze stałą liczbą jedynek m w słowie kodowym o stałej długości n tzw. „kody m z n” (por. podrozdział „kody numeryczne”). Pojedyncza zmiana 0 na 1 lub odwrotnie zmienia w takich kodach „bilans” jedynek i zer” i możemy wykryć błąd.
Rys. 2. Układy sprawdzające parzystość słowa binarnego x1x2x3x4x5x6x7x8