CRC Example Solution

This is the solution to a Cyclic Redundancy Code problem 
showing how the CRC can be formed using shift-and-XOR. 

In the following, the presentation convention x~n means 
"x to the nth power", y[m] means "y sub m", and + means 
modulo two addition (exclusive OR). s(D) means s expressed 
as a polynomial in D, and S means the collected bits s[i].

PROBLEM:  Given g[0]=1, g[1]=1, and S=1011, generate the CRC
using shift-and-XOR; determine the 3-bit remainder code to be 
transmitted using a CRC for error detection.

PROBLEM RESTATED: Given generator polynomial g(D)=D~3 + D + 1,
and s(D)=D~3 + D + 1, find the remainder:

c(D)=remainder[(s(D)D~3)/g(D)]
    =remainder[(D~6 + D~4 + D~3)/(D~3 + D + 1)]

OBSERVATION:  The numerator is a power of D times the
denominator, thus the remainder will be 0.

SOLUTION:  Start by loading the first 3 bits of S, starting
with the MSB, into C. Feedback is initially zero.  That is,

	 Feedback=0
	 c[2]=s[3]=1
	 c[1]=s[2]=0
	 c[0]=s[1]=1

(This is equivalent to loading zeros in C and then shifting in 
the first 3 bits of S.)  Now form the successive values of c[i] as: 
         
         Feedback=previous c[2]
         c[2]=previous c[1]   
         c[1]=previous c[0] + Feedback
         c[0]=previous Next s + Feedback.

(Remember + is modulo 2 addition.)

Now the remaining bits of S are shifted in, followed by as many zeros
as there are bits in the CRC (this equivalent to multiplying by D to
that power, in this case D~3). At each step the feedback value is
XORed with the bits of c that have a 1 in the generator polynomial,
in this case c[0] and c[1] (because the generator contains D~0 and D~1; 
remember the highest power of D, i.e. D^3~ is implicit and does not
participate in the process).  Here are the successive values of C:

           Next s  c[0]   c[1]   c[2]   Feedback
           ------  ----   ----   ----   --------
             1      1      0      1        0
	     0      0      0      0        1
	     0      0      0      0        0
	     0      0      0      0        0
                    0      0      0        0

What is left in C is the CRC remainder 000, i.e. c(D)=0.

Here is the problem reworked with input S=11001 to show a non-zero
remainder:           
           
           Next s  c[0]   c[1]   c[2]   Feedback
           ------  ----   ----   ----   --------
	     0      0      1      1        0
	     1      1      1      1        1
	     0      0      0      1        1
	     0      1      1      0        1
	     0      0      1      1        0
	            1      1      1        1

This says the CRC remainder is 111, equivalent to finding:

c(D)=remainder[((D~4 + D~3 + 1)D~3)/(D~3 + D + 1)] = D~2 + D + 1