Jak działa CRC?

Rozdział 9 Różne algorytmy CRC

Rozdz. 9.1 Wstęp
Podstawą wszystkich algorytmów jest Rozdz. 4 Arytmetyka CRC. W Rozdz. 5 Obliczanie CRC na rejestrach pokazaliśmy jak ten algorytm przesunięć jednobitowych realizować na rejestrach. Programiści systemów mikroprocesorowych nie posługują się bitami lecz bajtami i tego właśnie dotyczą 3 metody tablicowe z przesunięciami bajtowymi w Rozdz 8:
– Tablicowa bezpośrednia
– Tablicowa „lewa” z podwójnym xor-owaniem
– Tablicowa „prawa” z podwójnym xor-owaniem
Metoda bezpośrednia ma charakter dydaktyczny i dlatego większość stosowanych w praktyce metod to są głównie różne modyfikacje metody “lewej” i “prawej”. 

Rozdz. 9.2 Jak klasyfikować metody CRC?
Znany popularyzator metod CRC pan Ross N. Williams stworzył ogólny program w języku C – Parametryczny Algorytm Obliczania CRC. Bazuje on na modelu tablicowym „lewym” z podwójnym xor-owaniem. Zmieniając parametry programu np. REFIN, REFOUT… możemy stworzyć nie tylko model “prawy” ale także inne nie ujęte w kursie modyfikacje. Programista korzystający z programu powinien jednak mieć świadomość jego nieoptymalności. Niezależnie od tego, czy będziemy głęboko wchodzić w CRC np. poprzez pisanie konkretnych aplikacji dla urządzeń, to już same parametry ułatwiają klasyfikacje różnych algorytmów CRC. Dlatego poruszam ten temat.
Tymi parametrami są:
– NAME nazwa algorytmu
– WIDTH wielkość rejestru CRC  przeważnie 8, 16 albo 32 bity (czasami “niebajtowa” wartość)–>im więcej tym większa moc wykrywania błędów!
– POLY wartość “dzielnika” inaczej generatora lub wielomianu*
– INIT stan początkowy rejestru CRC. W kursie była to wartość zerowa ale nie zawsze tak jest.
– REFIN jeżeli FALSE —>metoda Tablicowa „lewa” z podwójnym xor-owaniem która traktuje bit lewy bajtu jako najstarszy
              jeżeli TRUE—>metoda Tablicowa „prawa” z podwójnym xor-owaniem która traktuje bit prawy bajtu jako najstarszy
– REFOUT jeżeli FALSE –>metoda Tablicowa „lewa” z podwójnym xor-owaniem
                  jeżeli TRUE –>metoda  Tablicowa „prawa” z podwójnym xor-owaniem w której obracamy obliczone CRC
– XOROUT wartość bitowa przez którą xor-ujemy obliczone CRC. W kursie była to wartość zerowa ale nie zawsze tak jest.
– CHECK obliczone CRC dla wysyłanej wiadomości którą jest łańcuch “123456789”. Przydaje się do testowania programu.

Rozdz. 9.3 Odwrócone “dzielniki“
Występują też tzw. odwrócone  (reversed) “dzielniki” -inaczej odwrócone poly, generatory, wielomiany…
Np. dla  CRC którego standardową nazwą jest X25
X25 standard: 1-0001-0000-0010-0001–>hexa 1 01 00 02 01
X25 reversed:  1-0000-1000-0001-0001–>hexa 1 00 80 01 01
Pamiętaj, że w w odwracaniu bierze też udział pierwszy bit=1 “dzielnika”, niewidocznego w parametrze poly! Jest to zupełnie inne poly niż standard! Nie mylić z metodą tablicową odwróconą (“prawą”)!  Metody z tablicą odwróconą “prawą”  i normalną “lewą” oparte są na tym samym “dzielniku”!

Rozdz. 9.4 Przykłady algorytmów CRC
Name : “CRC-16”
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : BB3D
Uwaga: Parametry Poly, Init, Xorout i Check przedstawiono jako liczby hexa a nie binarne.

Name : “CRC-16/CITT”
Width : 16
Poly : 1021
Init : FFFF
RefIn : False
RefOut : False
XorOut : 0000
Check : ?

Name : “XMODEM”
Width : 16
Poly : 8408
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?

Name : “ARC”
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?

I wisienka na torcie!
CRC-32 używany w  PKZip, AUTODIN II, Ethernet i FDDI.

Name : “CRC-32”
Width : 32
Poly : 04C11DB7
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
Check : CBF43926

Uwaga:
Nie wszystkie używane w sieci algorytmy CRC łatwo poddają się klasyfikacji!