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:
– when even elements located in the column over the line
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 digits long
2. Write on the position under upper line because “factor” 11001 is 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 to the “quotient” in the upper line because first “rest” isn’t 0000.  If the rest were 0000 append 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!

One thought on “4. CRC Arithmetic

Leave a Reply

Your email address will not be published. Required fields are marked *