[Math] Binary long division for polynomials in CRC computation

binarypolynomials

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.

Best Answer

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.

Related Question