# Binary long division for polynomials in CRC computation

I am trying to learn binary long division, and I am confused. An example in my book gives that $10011010000/1101 = 11111001$ plus a remainder of $101$, which doesn't make sense, since $1001$ is not divisible by $1101$, and so the first digit should be $0$. When I use an online calculator, it gives me a result of $01011110$, which makes more sense. Could anybody enlighten me, please?

To add some context, this is the polynomial long division involved in CRC computation. Maybe the numbers, which represent the coefficients of polynomials, aren't supposed to be converted to decimal? The number being divided had already been extended by the degree of the divisor.

• To understand why the polynomial (not the number) being divided has been extended by the degree of the divisor, see the answer to this question, which also gives some details about the division process. – Dilip Sarwate Mar 18 '13 at 1:59
• Its not ordinary arithmetic. Its XOR division, meaning there is now carry involved. – Robin Dec 11 '18 at 9:32

## 4 Answers

If it is polynomials, you can't transform to decimal. What you have is: $$x^{10} + x^7 + x^6 + x^4 / x^3 + x^2 + 1$$ The coefficients are in $\mathbb{Z}_2$ (they are 0 or 1, and $1 \cdot 1 = 1$, $1 + 1 = 0$). Do the polynomial long division.

Or work similar to what you would do when dividing integers, sliding the divisor against the dividend. Just that it is much simpler: Next bit is the first bit of what comes next, and in $\mathbb{Z}_2$ addition is substraction (and is the XOR operation for bitwise operations e.g. in C).

 10011010000/1101 = 111001
-1101
-----
1001
-1101
-----
1000
-1101
-----
1010
-0000
-----
0100
-0000
-----
1000
-1101
-----
101


Thus the quotient is 111001 (i.e., $x^5 + x^4 + x^3 + 1$) with remainder 101 (i.e., $x^2 + 1$).

• What do you do when you get to a situation with 0-1? There's no negative one – CodyBugstein Mar 2 '15 at 19:40
• @Imray You don't do any carryover in this situation. That is basically literally bit-by-bit XOR. – xji May 5 '15 at 6:18
• The result is incorrect. The quotient is 11111001 with remainder 101. If you were to multiply only leading terms from polynomials you would get x^5 * x^3 = x^8 which is not x^10 as it should be. This is an easy way to spot this mistake. – kr85 Jan 6 '16 at 22:59

the vonbrand answer is slightly off. This is the correct operations in GF(2) -

        11111001
------------
1101(10011010000
1101
----
1001
1101
----
1000
1101
----
1011
1101
----
1100
1101
----
1000
1101
----
101


In GF(2) X^10+X^7+X^6+X^4 MOD (X^3+X^2+1) = X^2+1

Therefor your text book's answer is correct.

• What do you do when you get to a situation with 0-1? There's no negative one – CodyBugstein Mar 2 '15 at 19:39
• Imray - there is no subtraction. Only addition modulo 2. – brett Mar 24 '15 at 17:01

here is an online python3 sample for printing the long division.

def bitstring(x):  return bin(x)[2:]
def printlongdiv(lhs, rhs):
rem = lhs
div = rhs
origlen = len(bitstring(div))

# first shift left until the leftmost bits line up.
count = 1
while (div | rem) > 2*div:
div <<= 1
count += 1

# now keep dividing until we are back where we started.
quot = 0
while count>0:
quot <<= 1
count -= 1
print("%14s" % bitstring(rem))
divstr = bitstring(div)
if (rem ^ div) < rem:
quot |= 1
rem ^= div

print(1, " " * (11-len(divstr)), divstr[:origlen])
else:
print(0, " " * (11-len(divstr)), "0" * origlen)
print(" " * (13-len(divstr)), "-" * origlen)
div >>= 1
print("%14s <<< remainder" % bitstring(rem))
print(" -> %10s <<< quotient" % bitstring(quot))

printlongdiv(0x4d0, 13)


$1232 = 94 * 13 + 10$

$10011010000 = 1011110 * 1101 + 1010$

The example is wrong and your online calculator is calculating correctly.

• It is polynomials, not integers in binary. – vonbrand Mar 18 '13 at 1:36
• The example is not wrong, and what is calculating (correctly) is not what the online calculator is calculating. – Dilip Sarwate Mar 18 '13 at 1:56
• my answer is obsolete, because the question has been substantialy changed. – V-X Mar 18 '13 at 6:51