# Calculating CRC by long division: How to decide the top number of long division?

Ok, I know how to use long division by using regular numbers, but when comes to binary numbers I'm getting confused.

In following calculation I can see the equation solved but I don't understand where the top number came from. How to decide what bit goes on top while doing this?

PS. We are doing the XOR comparison.

-

It is in fact obvious from the diagram. The number on the left is the divisor, while the number at the top is the quotient, and CRC is the final remainder.

In long division, every time you successfully subtract a multiple of the divisor, that (single digit) multiplier goes in the quotient above the right hand digit of the multiple of the divisor. In binary, the multiplier is always $1$ since there is no other positive single digit.

If you cannot subtract a multiple of the divisor with a right hand digit in that place because the running remainder is too small, then you put $0$ in that place in the quotient.

-
Yes, I do agree while doing the subtraction, but when I use XOR method then it doesn't make any sense to me. If it wouldn't be too much to ask, could you explain this step by step from this example? –  HelpNeeder Feb 24 '12 at 23:08
I missed that - I had thought this was long division but in binary and did not check all the details. It seems that you follow the same rule, but only use the "divisor" when its first bit matches the first bit of the "running remainder". This all looks strange to me, as does Wikipedia's article. –  Henry Feb 24 '12 at 23:22
In your example, the leading bit of the "dividend" is in position 13 so you put the "divisor" under it, making its final bit in position 8, so you put a 1 in position 8 of the "quotient". You do your XOR which eliminates the bit of the "dividend" in position 13 from the "running remainder" as intended, but also the bit in position 12. So you next put the "divisor" with its leading bit in position 11 and final bit in position 6, put a 1 in position 6 of the "quotient", and do your XOR. The leading bit of the "running remainder is now in position 10 and you carry on. –  Henry Feb 24 '12 at 23:29
There's no need for scare quotes here really -- what is going on is not long division of binary numbers, but long polynomial division of formal polynomials with coefficients in $\mathbb F_2$ (i.e., the integers modulo 2). We see only the coefficients because writing down the "$x^i+$" over and over would waste space without contributing information that is not inherent in the horizontal positions anyway. In polynomial division you subtract each coefficient by itself, without any carry between columns, and it so happens that subtraction modulo 2 is the same as XOR. –  Henning Makholm Feb 24 '12 at 23:57
And for what it's worth, the quotient is not used at all in CRC error-checking; it is only the remainder that matters. –  Dilip Sarwate Feb 25 '12 at 0:25