How does CRC work?
Chapter 9 Various CRC algorithms CRC
Chapter. 9.1 Introduction
The basis of all algorithms is Chapter. 4 CRC arithmetic. In Chapter. 5 Calculating CRC on registers. We showed how to implement this single-bit shift algorithm on registers. Programmers of microprocessor systems do not use bits but bytes, and this is what the three array methods with byte shifts in Chapter 8 are about:
– Direct array method
– “Left” array method with double xoring
– “Right” array method with double xoring
The direct method is didactic in nature and therefore most of the methods used in practice are mainly various modifications of the “left” and “right” methods.
Chapter 9.2 How to classify CRC methods?
The well-known popularizer of CRC methods, Mr. Ross N. Williams, created a general program in the C language – Parametric CRC Calculation Algorithm. It is based on the “left” array model with double xoring. By changing program parameters, e.g. REFIN, REFOUT… we can create not only the “right” model but also other modifications not included in the course. However, a programmer using the program should be aware of its non-optimality. Regardless of whether we go deep into CRC, e.g. by writing specific applications for devices, the parameters themselves facilitate the classification of various CRC algorithms. That’s why I’m bringing this up.
These parameters are:
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.
These parameters are:
– NAME algorithm name
– WIDTH CRC registry size 8, 16 or 32 bits mostly–>the more, the greater the error detection power!
– POLY value of the “divisor“, also known as the generator or polynomial*
– INIT CRC initial state. In the course it was zero, but this is not always the case.
– REFIN if FALSE –>“Left” array method with double xoring which treats the left bit of the byte as the oldest
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!