How does CRC work?
Chapter 9 Various CRC algorithms
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:
– 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”.
Chapter 9.2 How to classify CRC methods?
A 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 suboptimal nature. 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 the size of the CRC register, usually 8, 16 or 32 bits (sometimes a “non-byte” value) –> the larger it is, the greater the error detection power!
– POLY value of the “divisor“, also known as the generator or polynomial*
– INIT initial state of the CRC register. 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
if TRUE —> “right” array method with double xoring which treats the right bit of the byte as the oldest
– REFOUT if FALSE –>Array method “left” with double xoring
if TRUE –>Array method “right” with double xoring in which we rotate the calculated CRC
– XOROUT bit value through which we xor the calculated CRC. In the course it was zero, but this is not always the case.
– CHECK calculated CRC for the sent message which is the string “123456789“. It is useful for testing the program.
Chaper 9.3 Inverted “divisors”
There are also so-called reversed “divisors” – otherwise 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”!
Ch. 9.4 Examples of CRC algorithms
Name : “CRC-16”
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : BB3D
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!