How does CRC work?
Chapter 4 CRC Arithmetic
Chapter 4.1 Introduction
Let’s return to elementary school. Division Subject. You will see then, that the CRC callculation is similar but much simpler! No „how much something” fits in „other something”! Nothimg in the memory in subtraction. You do logical XOR operations only. But let’s return to elementary school first.
Note
I used the word „rest” in calculations and animations. But the word „remainder” is the better!
Chapter. 4.2 Division example
Fig. 4-1
The decimal remainder calculation ANIMATION
Chapter 4.3 Logical xor operations training
You must be xor operation world champion, when you start to study CRC arithmetic.
Fig. 4-2
The row under line is a logical xor of the upper rows. Check all the columns for Fig. 4-2a and Fig. 4-2b.
There are more than 2 rows in the Fig. 4-2c. The result xor operation is:
– 0 when even elements located in the column over the line
– 1 when odd elements located in the column over the line
Chapter 4.4 The CRC calculation method
It’s very important chapter!
Fig. 4-3
The CRC as a „rest” of the „division” ANIMATION
The quotation marks are used because the operation is similar to the common division only!
Note that the „quotient” isn’t important. The „rest” CRC is important only!
Compare with the normal division chapter 4.1 and understand CRC alghorithm yourself!
It should be:
We divide „dividend” 10101101 by the „factor” 11001. The result „quotient” 11000001 isn’t important. Important is the „rest”=1001
1. Append 4 zeroes to the „quotient” because „factor” is 4 digits long
2. Write 1 on the 5 position under upper line because „factor” 11001 is 5 digits long
3. Calculate first „rest” as in the common division chapter 4.1. i.e. we subtract 1×11001 as in the common subtraction. The subtraction is replaced by the xor operation. 1100 is the first „rest” i.e. first CRC.
4. Append 1 to the „quotient” in the upper line because first „rest” isn’t 0000. If the rest were 0000 append 0 to the „quotient”.
Calculate second „rest” as 0000
…
etc.
End when the „rest” position is just under appended 0000 to the quotient.
The CRC result is 1001.
Chapter 4.5 The modified CRC calculation method
Let’s append 1001 (as the CRC in the previous chapter) to the quotient instead of the 0000. What’s the CRC result?
Fig. 4-4
The modified CRC calculation method ANIMATION
The ultimate CRC=0000!
Algorithm flow is identical as Fig. 4-3 up to fourth rest. It’s obviously because appended 1001 hasn’t influence up to the fourth rest.
By the way
See Fig. 4-1 When rest=24 is added to quotient 3274 the result rest=0000 Please check it!
See Fig. 4-4 When CRC=1001 is appended to quotient 10101101 the result CRC=0000
Conclusion
CRC and common division algorithms are similar!