An Explanation of How Cyclic Redundancy Codes Work
During my time supervising the University of Cambridge Computer Laboratory Part IB Digital Communications I course, various questions or confusions arose concerning CRCs. Here is an in depth explanation on the issues raised. To the best of my knowledge it is correct, but if in doubt, ask the lecturer. You may also wish to see the page dedicated to other problems from the course.
CRCs: The Basics
CRCs work by dividing the message polynomial, M(x), by the special CRC polynomial P(x). The polynomials are all with binary coefficients (i.e. 1 or 0). The division is done modulo 2.
CRC arithmetic has no carry. This means that for, e.g., addition, each digit is independent of the previous ones. For example, 011 + 110 = (0+1)(1+1)(1+0) = 101. In normal binary arithmetic you would have expected the answer to be 001 with a carry out of 1. This interesting property means that addition and subtraction are now the same operation, i.e. 011 - 110 = (0-1)(1-1)(1-0) = 101. Note that in CRC arithmetic 0-1 = 1 because the digit "wraps" (imagine you overflow an integer variable in a program).
Multiplication in CRC arithmetic is pretty similar to what you're used to from school: 1101 * 10 = (1101 * 0) + shiftLeft[(1101 * 1)] = 0000 + 11010 = 11010. You'll see why the shiftLeft operator is there if you write down any long multiplication, just try doing 50*45 on paper and you'll find yourself automatically doing it ;-). Note that the final addition is done using CRC arithmetic, and therefore 101 * 101 = (101 * 1) + shiftLeft[(101*0)] + shiftLeft[shiftLeft[(101*1)]] = 101 + 0000 + 10100 = 10001 (NOT 11001 as would have been the case with normal binary arithmetic).
We are now in a position to define division as the inverse of multiplication. If a = b*c, then we can say that a is simply the CRC addition of various different shifts of b. This makes sense if you realise that c is a binary number, and therefore only has digits 0 and 1; If the digit of c under consideration is 0, then that step of the multiplication will give result b*0 = 0 (shifted left by some amount, but it'll still be 0). If that digit is a 1, then we get b*1 shifted left by some amount depending on what stage of the multiplication we're at. Hence, when we're dividing a by b, all we have to do is subtract different shifts of b to finally get the result.
For example 11010 divided by 10 (the inverse of the multiplication example above):
- First we subtract 10 right shifted all the way to the same MSB as the thing we're dividing: 11010 - 10000 = 01010.
- Then we take the right shift 10 one less than before, and subtract that from the previous result: 01010 - 01000 = 00010.
- Now the next less right shift: 00010 - 00100. Problem: we know that 00010 < 00100 as the first 1 in the second number comes in a higher bit position that the first 1 in the first number. So we do nothing.
- We continue with the next shift: 00010 - 00010 = 000000. We're done. The result is the remainder, which of course is 0, as 11010 is exactly divisible by 10.
Remember in all the subtractions we're using CRC arithmetic, which means that 0-1 = 1 (doesn't matter in the above example, but it obviously will in others!).
The Diagram on Slide 56
With the diagram shown on slide 56, the CRC polynomial is represented by the circuit itself. Now what we do is shift the dividend instead of the divisor, and therefore we shift in the M(x) polynomial "into" the P(x) circuit representation. Whenever a 1 enters the x^4 register, we know that the next shift of M(x) (which will put a 1 in an imaginary x^5 register), is greater or equal to P(x) (in terms of CRC arithmetic remember that the way you tell whether something is >= goes on the positions of the first 1s in each number, and nothing else), hence we can do the division. Division involves XORing that particular shift of M(x) with P(x). The points at which we connect the output of the x^4 register back into the rest of the circuit are those where we would have 1s in the P(x) polynomial, i.e. just _before_ the x^4, x^2 and the 1 registers. Hence whenever we perform another shift in of M(x), if the output of x^4 (i.e. the contents of the imaginary x^5 register) is 1, then we XOR it with the things going into the x^4, x^2 and the 1 registers. Hence we are subtracting x^5 + x^4 + x^2 + 1 each time, as required. When we have no further bits to shift in, this means that whatever is left in the registers is the remainder, as it will be smaller than P(x), and hence is not divisable by P(x) any further.
Assertions on Slide 55
For slide 55, the properties of a CRC polynomial, point 3 can be explained by noting that the third word is "also". This means that in addition to point 2 (P(x) must have a factor of length three terms), it should also have a factor of length two terms, so that any E(x) with an odd number of terms will not be divisible by it. Note that we need to specify that point 2 also holds, as otherwise we could have an E(x) = x^2 + 2x + 1, which has an odd number of terms, and yet is divisible by (x+1) (square it). Point 4 on that slide is also interesting: I can only explain it partially, but will attempt to get a full explanation to you ASAP. A burst error is one with E(x) = 00..0011..1100..00 i.e. all zeros except for a string of 1s in the middle somewhere. If we ignore the front zeros, and the number of 1s is c, whilst the number of proceeeding 0s is d, then we can factorise it into E(x) = (100..00)(11..11), where in the left hand bracket there are d 0s, and in the right hand half there are c 1s. If the length of the burst error (i.e. c), is less than the order of P(x) (which we generally call n), then P(x) will be greater than the right hand side, and hence won't divide it. The only problem now is to make P(x) not divide the right hand side. I have read that the way of doing this is to set the last bit of P(x) to be 1, but I'm not certain how this prevents us simply multiplying by 2 lots of times until we get 100..00. Anyway, you get the rough idea of what we're trying to do, (I hope!), and I suspect this is more than enough detail for the exam. However, I will attempt to find out, even if it's just for curiosity's sake! ;-).
CRCs and overlapping M(x)x^n and R(x)
When calculating the CRC of a message M, we obtain R(x) from taking the remainder of M(x)x^n and P(x). This remainder must necessarily be at least one degree less than P(x), as it must be smaller (otherwise, given it has binary coefficients, we could divide again by P(x)). Hence, whilst P(x) has degree n, and therore n+1 bits, R(x) has at most degree n-1, and therefore n bits. Hence, multiplying (and therefore shifting) M(x) up by n bits is sufficient to accommodate all n bits of the remainder, and there is no overlap (i.e. we can retrieve the message from what we transmit!).