How do you compute the XOR Remainder used in CRC?

Question

I'm trying to remember how the math is worked out to compute the remainder of an XOR algorithm in Cyclical Redundancy Checks to verify the remainder bits of a network message.

I shouldn't have tossed that text book.

This is easily done in code, but how is it worked out by hand?

I know it looks something like a standard division algorithm, but I can't remember where to go from there to get the remainder.

      ___________
1010 | 101101000

Note: I did google it, but wasn't able to find a place where they mapped the steps in figuring the remainder.

Answer 1

1010 | 101101000
       1010
       0001 this result is 1011 XOR 1010 = 0001
          1010
          1010
          0000  thus no remainder. 

Thus 101101000 is perfect and no error has occurred in transmission/reception

Answer 2

In my experience it's easier to convert it to a polynomial when calculating by hand, especially when there're a lot of zeroes.

1010 = 1*x^3 + 0*x^2 + 1*x^1 + 0*x^0 = x^3 + x = x3 + x
101101000 = x8 + x6 + x5 + x3

       -------------------
x3 + x ) x8 + x6 + x5 + x3

Then you divide the largest term in the dividend (x^8) with the first term in the divisor (x^3), resulting in x^5. You put that number on top and then multiply it with each term in the divisor. This yields the following for the first iteration:

        x5
       -------------------
x3 + x ) x8 + x6 + x5 + x3
         x8 + x6

Doing XOR for each term then yields the new dividend: x5 + x3:

        x5
       -------------------
x3 + x ) x8 + x6 + x5 + x3
         x8 + x6
       -------------------
         x5 + x3

Follow the same pattern until the dividend's largest term is smaller then the divisor's largest term. After the calculations are complete it will look like this:

        x5 + x2
       -------------------
x3 + x ) x8 + x6 + x5 + x3
         x8 + x6
       -------------------
         x5 + x3
         x5 + x3
       -------------------
         0

The reminder in this case is 0, which would indicate that most likely no errors has occurred during the transmission.

Note: I've shortened x^y as xy in the example above to reduce the clutter in the answer, since SO doesn't support math equation formatting.

Note2: Adding/subtracting a multiple of the divisor from the dividend will also give the reminder 0, since (P(x) + a*C(x)) / C(x) = P(x)/C(x) + a*C(x)/C(x) gives the same reminder as P(x)/C(x) since the reminder of a*C(x)/C(x) is 0.

Answer 3

It is long division by binary 11. There is an example on Wikipedia.

Answer 4

Let's assume that we want to divide 101110000 to 1001.

101110000
1001
--------- XOR the 1011 and 1001
0010

Now we will remove the zeros at the beginning of our XOR result which is 0010 and slide numbers from the top.

101110000
1001
--------- 
  1010

Continue the XOR 1001 with the result.

101110000
1001
--------- 
  1010
  1001
---------
  0011
--------- Remove zeros at the beginning
    1100
    1001
---------
    0101
--------- Remove zeros at the beginning
     1010
     1001
---------
     0011

Answer is 0011.