Cykliczny kod nadmiarowy (CRC)

Cykliczny kod nadmiarowy

Przy wysyłaniu ważnego dokumentu pocztą można zapisać na kopercie specjalny numer weryfikacyjny obliczony z treści dokumentu. Odbiorca wykonuje to samo obliczenie dla otrzymanego dokumentu i porównuje wynik z wartością nadawcy. Równość oznacza, że kontrola nie wykryła zmiany. Niezgodność wskazuje na zmianę w danych podczas zapisu lub transmisji.

Cykliczny kod nadmiarowy (CRC) realizuje tę kontrolę w postaci kodu wykrywającego błędy. Stosuje się go w sieciach cyfrowych i urządzeniach pamięci do wykrywania przypadkowych zmian w danych. Dla danego bloku oblicza krótką binarną sekwencję o stałej długości, zwaną sumą kontrolną CRC, a następnie dołącza ją do danych przed transmisją lub zapisem. W praktyce skrót CRC oznacza zarówno kod, jak i obliczoną wartość. Odbiorca wykonuje obliczenie ponownie i porównuje oba wyniki.

Wielomiany i arytmetyka modulo-2

W CRC ciąg binarny jest reprezentowany jako wielomian nad ciałem $GF(2)$ . Na przykład ciąg $1101$ odpowiada wielomianowi:

$1\cdot x^3 + 1\cdot x^2 + 0\cdot x^1 + 1\cdot x^0 = x^3 + x^2 + 1$

Dzielenie i pozostałe operacje CRC opierają się na . W tym systemie dodawanie i odejmowanie mają tę samą tabelę wartości co XOR, więc algorytm nie korzysta z przeniesień typowych dla arytmetyki całkowitoliczbowej.

Wielomian generujący G(x)

Nadawca i odbiorca uzgadniają wielomian generujący, $G(x)$ . Jego współczynniki można zapisać jako stały ciąg binarny, który pełni funkcję dzielnika w obliczeniach CRC. Wybór $G(x)$ określa, jakie wzorce błędów dany CRC wykrywa.

Obliczanie CRC po stronie nadawcy

Rozważmy przykład z wiadomością 110101 i uzgodnionym wielomianem generującym 101.

Krok 1: dołączenie zer.
Do końca wiadomości dołączamy tyle zer, ile wynosi stopień wielomianu generującego, czyli o jeden mniej niż liczba jego bitów. Generator $(101)$ ma 3 bity i stopień 2, więc dołączamy $3-1=2$ zera.
Wiadomość z dopełnieniem ma postać: 11010100.
Krok 2: dzielenie binarne modulo-2.
Wiadomość z dopełnieniem dzielimy przez wielomian generujący metodą dzielenia wielomianów modulo-2. Odejmowanie w kolejnych etapach zastępuje operacja XOR.
Dzielenie daje iloraz, który odrzucamy, oraz resztę. W tym obliczeniu reszta wynosi 11 i stanowi sumę kontrolną CRC.
Krok 3: utworzenie ramki do wysłania.
Dołączone w pierwszym kroku zera zastępujemy obliczoną sumą CRC.
Oryginalna wiadomość: $(110101)$
Wiadomość z zerami: $(11010100)$
Reszta XOR: $(00000011)$
Końcowa ramka do wysłania: 11010111

Weryfikacja ramki po stronie odbiorcy

Odbiorca ponownie dzieli odebraną ramkę przez ten sam wielomian generujący.

Odbierz ramkę: Odbiorca otrzymuje kompletną ramkę zawierającą dane i sumę kontrolną CRC: $(11010111)$ .
Wykonaj dzielenie: Dzieli całą otrzymaną ramkę przez ten sam wielomian generujący $(101)$ .
Sprawdź resztę:
- Jeśli reszta wynosi zero, kontrola nie wykryła błędu. Odbiorca akceptuje pakiet, a suma CRC zostaje usunięta, pozostawiając oryginalne dane.
- Jeśli reszta jest różna od zera, ramka zawiera wykryty błąd. Odbiorca odrzuca cały pakiet. Warstwa wyższa, na przykład TCP, może zlecić retransmisję.

Własności wykrywania błędów przez CRC

Możliwość wykrycia danego wzorca zależy od wielomianu generującego i długości chronionego bloku. Poniższe własności wynikają z budowy $G(x)$ oraz z zakresu odległości bitów, które mogą zostać zmienione:

Wszystkie błędy jednobitowe, jeżeli $G(x)$ ma co najmniej dwa niezerowe składniki.
Wszystkie błędy dwubitowe w określonym zakresie długości bloku, jeżeli $G(x)$ ma niezerowy wyraz stały i nie dzieli wielomianu $x^k+1$ dla żadnej możliwej odległości $k$ między zmienionymi bitami.
Wszystkie błędy o nieparzystej liczbie zmienionych bitów, jeżeli wielomian generujący zawiera czynnik $x+1$ .
Wszystkie o długości nieprzekraczającej stopnia wielomianu generującego, jeżeli jego wyraz stały jest niezerowy.

CRC wykrywa zmiany w danych, a korekcję realizuje osobny mechanizm. Stosuje się go między innymi w ramkach Ethernet, sieciach Wi-Fi, protokole HDLC oraz formatach ZIP i PNG.