Czym jest Cykliczny Kod Nadmiarowy?

Wyobraź sobie, że wysyłasz ważny dokument pocztą. Aby mieć pewność, że dotrze on w nienaruszonym stanie, możesz na kopercie zapisać specjalny „numer weryfikacyjny”, obliczony na podstawie treści dokumentu. Odbiorca wykonuje to samo obliczenie na otrzymanym dokumencie i sprawdza, czy jego numer zgadza się z Twoim. Jeśli tak, dokument jest prawdopodobnie nienaruszony. Jeśli nie, coś poszło nie tak.

Cykliczny Kod Nadmiarowy (CRC) to potężna, cyfrowa wersja tej idei. Jest to kod wykrywający błędy, powszechnie stosowany w sieciach cyfrowych i urządzeniach do przechowywania danych w celu wykrywania przypadkowych zmian w surowych danych. Generuje on krótką sekwencję binarną o stałej długości, znaną jako suma kontrolna CRC, dla danego bloku danych. Ta suma kontrolna jest jak "cyfrowy odcisk palca", który jest dołączany do danych i przesyłany razem z nimi.

Sedno Idei: Wielomiany i Arytmetyka Modulo-2

„Magia” skuteczności CRC tkwi w traktowaniu ciągów binarnych tak, jakby były to wielomiany matematyczne. Na przykład ciąg binarny $1101$ można zinterpretować jako wielomian:

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

Wszystkie obliczenia są wykonywane przy użyciu specjalnego rodzaju matematyki zwanej Arytmetyką Modulo-2. W tym systemie dodawanie i odejmowanie działają dokładnie tak samo jak operacja logiczna XOR, co znacznie upraszcza wymagany sprzęt.

Jak Oblicza się CRC (Po Stronie Nadawcy)

Przejdźmy przez przykład. Załóżmy, że chcemy wysłać wiadomość 110101 i uzgodniliśmy wielomian generujący 101.

1. Krok 1: Dołączenie Zer.

   Najpierw do końca naszej wiadomości dołączamy pewną liczbę zer. Liczba zer jest o jeden mniejsza od długości wielomianu generującego. Nasz generator $(101)$ ma długość 3 bitów, więc dołączamy $3-1=2$ zera.
   Nasza wiadomość z dopełnieniem to teraz: 11010100.

2. Krok 2: Długie Dzielenie Binarne (Modulo-2).

   Następnie dzielimy wiadomość z dopełnieniem przez wielomian generujący, używając długiego dzielenia binarnego modulo-2 (gdzie odejmowanie to XOR).

   

   Dzielenie daje iloraz (który odrzucamy) i resztę. W tym przypadku reszta to 11. Ta reszta to nasza suma kontrolna CRC.

3. Krok 3: Stworzenie Ramki do Wysłania.

   Na koniec zastępujemy zera, które dodaliśmy w Kroku 1, obliczoną sumą kontrolną CRC.
   Oryginalna Wiadomość: $(110101)$
   Dopełniona Zerami: $(11010100)$
   XOR Reszta: $(00000011)$
   Końcowa Ramka do Wysłania: 11010111

Jak Sprawdzane Są Błędy (Po Stronie Odbiorcy)

Odbiorca wykonuje prosty proces weryfikacji.

1. Odbierz Ramkę: Odbiorca otrzymuje kompletną ramkę, zawierającą dane i sumę kontrolną CRC: $(11010111)$.
2. Wykonaj Dzielenie: Dzieli całą otrzymaną ramkę przez ten sam wielomian generujący $(101)$.
3. Sprawdź Resztę:
   • Jeśli reszta wynosi zero, odbiorca zakłada, że dane dotarły bez wykrywalnych błędów i akceptuje pakiet. CRC jest następnie usuwane, pozostawiając oryginalne dane.
   • Jeśli reszta jest różna od zera, sygnalizuje to, że podczas transmisji wystąpił błąd. Odbiorca odrzuca wtedy cały pakiet, wiedząc, że jest uszkodzony. Zazwyczaj protokół wyższej warstwy (taki jak TCP) jest odpowiedzialny za żądanie retransmisji.

Interaktywny Kalkulator CRC

Dlaczego CRC jest tak skuteczne?

Siła CRC leży w matematycznych właściwościach dzielenia wielomianów. Dobrze dobrany wielomian generujący sprawia, że jest wysoce nieprawdopodobne, aby błędy transmisyjne przekształciły oryginalną wiadomość w inną poprawną wiadomość, która wciąż byłaby idealnie podzielna przez generator. CRC jest szczególnie dobre w wykrywaniu:

• Wszystkich pojedynczych błędów bitowych.
• Wszystkich podwójnych błędów bitowych (o ile wielomian generujący ma co najmniej trzy $1$).
• Dowolnej nieparzystej liczby błędów.
• Błędów seryjnycho długości równej stopniowi wielomianu generującego. Jest to jego najważniejsza zaleta w rzeczywistych kanałach transmisyjnych.

Ta niezawodność jest powodem, dla którego CRC jest de facto standardem wykrywania błędów w wielu technologiach, w tym w ramkach Ethernet (CRC-32), Wi-Fi, HDLC oraz formatach plików, takich jak ZIP i PNG.