I am trying to understand this document, but can't seem to get it right. http://www.ross.net/crc/download/crc_v3.txt
What's the algorithm used to calculate it?
I thought it uses XOR but I don't quite get it how he gets 0110 from 1100 XOR 1001. It should be 101 (or 0101 or 1010 if a bit goes down). If I can get this, I think the rest would come easy, but for some reason I just don't get it.
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDEND
DIVISOR 0000.,,....,.,,,
----.,,....,.,,,
0000,,....,.,,,
0000,,....,.,,,
----,,....,.,,,
0001,....,.,,,
0000,....,.,,,
----,....,.,,,
0011....,.,,,
0000....,.,,,
----....,.,,,
0110...,.,,,
0000...,.,,,
----...,.,,,
1100..,.,,,
1001..,.,,,
====..,.,,,
0110.,.,,,
0000.,.,,,
----.,.,,,
1100,.,,,
1001,.,,,
====,.,,,
0111.,,,
0000.,,,
----.,,,
1110,,,
1001,,,
====,,,
1011,,
1001,,
====,,
0101,
0000,
----
1011
1001
====
0010 = 02 = 2 = REMAINDER
The part you quoted is just standard long division like you learned in elementary school, except that it is done on binary numbers. At each step you perform a subtraction to get the remainder, and this is done in the example you gave: 1100 - 1001 = 0110.
Note that the article just uses this as a preliminary example, and it is not actually what is done in calculating CRC. Instead of normal numbers, CRC uses division of polynomials over the field GF(2). This can be modeled by using normal binary numbers and doing long division normally, except for using XOR instead of subtraction.