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:
– 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.
Chapter. 9.3 Inverted “divisors”
There are also so-called reversed “divisors” – also known as reversed polys, generators, polynomials…
E.g. for CRC whose standard name is 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
Remember that the first bit=1 of the “divisor”, invisible in the poly parameter, is also involved in the inversion! This is a completely different poly than the standard! Not to be confused with the reverse (“right”) array method! The inverted “right” and normal “left” array methods are based on the same “divisor”!
Chapter. 9.4 Examples of CRC algorithms
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.
Note:
The Poly, Init, Xorout and Check parameters are shown as hexa numbers and not binary.
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 : ?
And the icing on the cake!
CRC-32 used in PKZip, AUTODIN II, Ethernet and FDDI.
Name : “CRC-32”
Width : 32
Poly : 04C11DB7
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
Check : CBF43926
Note:
Not all CRC algorithms used on the network are easy to classify!