Cykliczny kod nadmiarowy
1. Dfefinicja
Cykliczny kod nadmiarowy, inaczej: cykliczna kontrola nadmiarowa (ang.) Cyclic Redundancy Check, CRC - jest to system sum kontrolnych wykorzystywany do wykrywania przypadkowych błędów pojawiających się podczas przesyłania i magazynowania danych binarnych.
2. Obliczanie
n-bitowy cykliczny kod nadmiarowy (n-bitowy CRC) definiuje się jako resztę z dzielenia ciągu danych przez (n+1)-bitowy dzielnik CRC, zwany również wielomianem CRC.
Przykład
Załóżmy n= 3.
Ustalmy (n+1)-bitowy dzielnik w postaci liczby 1011.
Weźmy 14-bitowy ciąg danych: 11010011101110.
Algorytm postępowania w celu obliczenia 3-bitowego CRC jest następujący:
dodajemy do ciągu danych 3 wyzerowane bity,
w linii poniżej wpisujemy 4-bitowy dzielnik CRC,
jeżeli mamy 0 nad najstarszą pozycją dzielnika, to przesuwamy dzielnik w prawo o jedną pozycję, aż do napotkania 1,
wykonujemy operację XOR pomiędzy bitami dzielnika i odpowiednimi bitami ciągu danych, uwzględniając dopisane 3 bity
wynik zapisujemy w nowej linii poniżej,
jeżeli liczba bitów danych jest większa lub równa 4, przechodzimy do kroku 2,
3 najmłodsze bity stanowią szukane CRC, czyli cykliczny kod nadmiarowy:
11010011101110 000 <--- 14 bitów danych + 3 wyzerowane bity
1011 <--- 4-bitowy dzielnik CRC
01100011101110 000 <--- wynik operacji XOR
1011
00111011101110 000
1011
00010111101110 000
1011
00000001101110 000
1011
00000000110110 000
1011
00000000011010 000
1011
00000000001100 000
1011
00000000000111 000
101 1
00000000000010 100
10 11
------------------
00000000000000 010 <--- CRC
Po stronie odbiorczej wykonywane jest sprawdzenie poprawności otrzymanych danych, przy wykorzystaniu, utworzonego po stronie nadawczej, kodu nadmiarowego CRC. Jeżeli w przesłanych danych nie ma przekłamań, to po wykonaniu powyższej procedury reszta z dzielenia przez dany dzielnik CRC wynosi 0:
11010011101110 010 <--- przesłany bez przekłamań ciąg 14 bitów danych + CRC
1011 <--- ustalony uprzednio, 4-bitowy dzielnik
01100011101110 010 <--- wynik operacji XOR
1011
00111011101110 010
1011
00010111101110 010
1011
00000001101110 010
1011
00000000110110 010
1011
00000000011010 010
1011
00000000001100 010
1011
00000000000111 010
101 1
00000000000010 110
10 11
------------------
00000000000000 000 <--- wynik operacji równy 0 oznacza poprawną transmisję