[Math] Polynomial Arithmetic Modulo 2 (CRC Error Correcting Codes)

binarycoding-theorymodular arithmetic

I'm trying to understand how to calculate CRC (Cyclic Redundancy Codes) of a message using polynomial division modulo 2. The textbook Computer Networks: A Systems Approach gives the following rules for division:

  1. Any polynomial $B(x)$ can be divided by a divisor polynomial $C(x)$ if $B(x)$ is of higher degree than $C(x)$.

  2. Any polynomial $B(x)$ can be divided once by a divisor polynomial $C(x)$ if $B(x)$ is of the same degree as $C(x)$.

  3. The remainder obtained when $B(x)$ is divided by $C(x)$ is obtained by performing the exclusive OR on each pair of matching coefficients.

For example: the polynomial $x^3 +1$ can be divided by $x^3 + x^2 + 1$ because they are both of degree 3. We can find the remainder by XOR the coefficients: $1001 \oplus 1101 = 0100$ and the quotient is obviously 1.

Now, onto long division – and the source of my confusion. The book says: "Given the rules of polynomial division above, the long division operation is much like dividing integers. We see that the division $1101$ divides once into the first four bits of the message $1001$, since they are of the same degree, and leaves the remainder $100$. The next step is to bring down a digit from the message polynomial until we get another polynomial with the same degree as $C(x)$, in this case, $1001$. We calculate the remainder and repeat until the calculation is complete.

So, given an example where I want to divide $010000$ by $1101$ where I know in advance that the quotient is $011$.

       0
      ________
1101 | 010000  // 1101 does not divide 0100.
       1101

       01
      ________
1101 | 010000  
        1101   // Bring down a digit from the right so we get the same degree as C(x).
        ----   // 1101 divides into 1000 as they have the same degree.
         1010  // Now XOR to find the remainder. Bring down the zero.

       011
      ________
1101 | 010000  
        1101   
        ----   
         1010  // Now XOR to find the remainder. Bring down the zero.
         1101  // 1101 divides 1010.


       011
      ________
1101 | 010000  
        1101   
        ----   
         1010  
         1101  
         ----
          111  // The remainder is 111.

Would this be correct based on the algorithm above?

Best Answer

Your calculations are correct.

It is worth keeping in mind that the quotient is not of importance in the CRC calculations, it is the remainder that is needed. The careful calculations that you have carried out and written up in detail are good for familiarizing oneself with the algorithm. However, after some practice, you may find the following shorthand much more handy

010000 1101 1101 111

Related Question