Im trying to understand CRC and I'm getting confused as how to calculate the 'divisor'.
In the example on wikipedia the divisor is 11 (1011) for input of 11010011101100
11010011101100 000 <--- input left shifted by 3 bits
1011 <--- 开发者_StackOverflow中文版divisor (4 bits) = x³+x+1
------------------
01100011101100 000 <--- result
How is the divisor calculated? In this example (x³+x+1) x is 2? Where did the 2 come from?
From the "Mathematics of CRC" section of that same wikipedia it starts "Mathematical analysis of this division-like process reveals how to pick a divisor that guarantees good error-detection properties." This is the key to it. Some divisors are better than others so you just find a standard one and use that usually.
The bottom of that page describes some of the different CRCs used and the polynomial that defines their divisors.
It's written in the next sentence @wikipedia:
If the input bit above the leftmost divisor bit is 0, do nothing. If the input bit above the leftmost divisor bit is 1, the divisor is XORed into the input.
Which means:
1101 xor 1011 => 0110
The divisor in binary is just the coefficients of its polynomial. x^3 + x + 1 = 1x^3 + 0x^2 + 1x +11; read off the cofficients to get 1 0 1 1
精彩评论