Binary long division for polynomials in CRC computation

Question

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.

Answer 1

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.

Answer 2

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$).

Answer 3

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)

Answer 4

$1232 = 94 * 13 + 10$

$10011010000 = 1011110 * 1101 + 1010$

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