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ę