4
$\begingroup$

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.

enter image description here

1 Answers 1

4

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.

  • 0
    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?2012-02-24
  • 0
    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](http://en.wikipedia.org/wiki/Computation_of_CRC).2012-02-24
  • 0
    Indeed, I'm getting very confused here. The article is talking about CRC computation which is done by using logical circuit which is for computers, the method I'm doing is a bit different. As I earlier [asked](http://math.stackexchange.com/questions/112978/problem-while-calculating-frame-check-sequence-fcs-in-cyclic-redundancy-check), person explained how to do this by equation, but since I'm doing this by using long division is a bit different.2012-02-24
  • 1
    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.2012-02-24
  • 0
    After reading and rereading I had an eureka moment here :D Thanks a lot man!! This comment was very helpful!2012-02-24
  • 2
    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.2012-02-24
  • 3
    And for what it's worth, the quotient is not used at all in CRC error-checking; it is only the remainder that matters.2012-02-25
  • 0
    @HelpNeeder, in my answer to [your other question about this same exercise](http://math.stackexchange.com/q/112978/11619) I also used polynomial algebra. Henning does it that way. Dilip does it that way. I do it that way. May be the author of your textbook should get the hint :-) All: Is this question a dup? I think that it would have been better to keep the discussion of this exercise in that one thread. HelpNeeder, may be you were too quick to accept my answer there? It's no big deal, but not accepting an answer invites more answers, and it sounds like you needed more help!2012-02-25
  • 0
    @Jyrki Lahtonen, Well it could be done in one thread, I believe. But Not to confuse people who answers I rather focus on a single topic in my question. I apologize if I'm wrong. Well, the book shows us the different approach using Modulo 2 arithmetic, it's just they also provide by doing long polynomial division. I just wanted to know how to do the simple way, not to confuse myself.2012-02-25
  • 0
    Also, if you have any extra information that might be useful to me then post your answer :) I will up vote/accept for information and effort.2012-02-25
  • 0
    @HelpNeeder: I apologize, my previous comment was out of place. At that time I missed the link you had given to your earlier question. Not doing that is ... not recommended, but you have not done anything wrong. Your teacher and/or the author of that textbook is the target of my 'wrath'. In my experience telecommunications engineers/programmers have no trouble at all understanding the arithmetic of polynomials with binary coefficients, so I was disappointed to see a text trying to avoid that. Henning does explain it in that you don't necessarily want to write out all those powers of $x$.2012-02-26
  • 0
    ...(cont.) particularly not when in practical application the packet that you protect with a CRC may be a few thousand bits long :-)2012-02-26
  • 0
    @Jyrki Lahtonen, you are right, using this in real life situation would be trouble some. But we have learned the division method, then using a circuit and my teacher didn't explain much about of doing your way :D2012-02-28