10
$\begingroup$

enter image description here

I have attached an image showing a Modulo 2 binary division.

I can roughly understand the working below which is using XOR calculation but I am not sure how the answer (in red) is being computed based on the workings.

I have searched the net and couldn't find any good step by step guide to solve this binary long division.

Hope someone can enlighten me.

$\endgroup$
  • 2
    $\begingroup$ It looks like you are XORring as opposed to subtracting. This means that you are doing long division in the ring of polynomials of binary coefficients ($\Bbb{F}_2[x]$). This is the operation that is needed e.g. when doing CRC-checks. But it is not to be confused with division of integers in base 2. The example is doing polynomial arithmetic, because if it were integer division, you should be borrowing at some steps. $\endgroup$ – Jyrki Lahtonen Feb 19 '14 at 16:51
  • $\begingroup$ Yup it is based on XOR, I have updated my question title. $\endgroup$ – Withhelds Feb 19 '14 at 16:56
  • 1
    $\begingroup$ See this question and its answers for another worked out example. $\endgroup$ – Jyrki Lahtonen Feb 19 '14 at 17:01
  • 2
    $\begingroup$ You are calculating $x^{11}+x^{10}+x^9+x^6+x^4$ divided by $x^4+x^3+x+1$ in the ring $\Bbb{F}_2[x]$. The quotient is $x^7+x^5+x^3+x^2$, and the remainder is $x^2$. The LSB is the constant term, the next bit the coefficient of the linear term ($x^1$) and so forth. $\endgroup$ – Jyrki Lahtonen Feb 19 '14 at 17:09
1
$\begingroup$

Each bit is the highest order bit of what remains so far, right shifted by four places because the dividend has highest term $2^4$. So the first bit is $1$ (as always). Because the first subtraction results in a $0$ in the next column, the second bit of the quotient is $0$. It is just like base $10$ division, if you get a zero in the next column over you put a zero in the quotient and skip it. Try dividing $\frac {100100}{99}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have updated my question and it is based on XOR. $\endgroup$ – Withhelds Feb 19 '14 at 16:57
  • 1
    $\begingroup$ My answer is based on XOR. As I understand it, you are asking how to determine each bit of the quotient. In XOR division, you just look at the leading bit at each stage. The first zero in the quotient comes because of the leading zero in the fourth line (including the quotient). The second comes because of the leading zero in the sixth line. The last two come from the two leading zeros in the tenth line. In regular binary division, you would have a zero any time the current remainder is less than the dividend. $\endgroup$ – Ross Millikan Feb 19 '14 at 17:12
  • 1
    $\begingroup$ Thanks, I have managed to understand :) $\endgroup$ – Withhelds Feb 20 '14 at 8:19
1
$\begingroup$

First of all, this is XOR not subtraction. Similar bits being XOR'ed always equal 0, different bits (no matter the order) in an XOR always equal 1. 0 XOR 0 = 0, 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1. Once you have grasped this firmly, it makes the math easier and behaves very similarly to traditional long division as far as having leading zero's in the dividend, put a 0 in the quotient and shift the divisor over one.

A 1 is placed above the 5th bit like in regular long division to mark the place of the last character of the Divisor. If we follow the bits in order the first part is 11100 XOR 11011 Bit1 1 XOR 1 = 0 Bit2 1 XOR 1 = 0 Bit3 1 XOR 0 = 1 Bit4 0 XOR 1 = 1 Bit5 0 XOR 1 = 1

This gives you a remainder of 0111. Since there is a leading 0 in the dividend the divisor gets shifted over again and a 0 is placed above the 6th bit.

This process is repeated until the divisor's last bit is in line with the dividend's last bit. If there is a leading 0 in the dividend place a 0 over the last bit in the dividend, if there is not a leading 0, place a 1 and do the math.

Important to note: once the last XOR math has been calculated, the remainder is your Modulo.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.