Cyclic Redundancy Check

Date: 06/26/2002 at 19:22:41
From: S.H.
Subject: Cyclic Redundancy Check

I have been studying CRCs for several days now and I understand
perfectly HOW they work.  But I fail to see how appending zeros 
to the message string (before the division) provides an advantage. 

The CRC could be just as easily computed without the zeros and even 
divisibility would still be preserved by adding the CRC back to the 
message string; in fact, it seems that appending the zeros makes for 
more work.  None of the sources I have referenced address this issue 
specifically, so I assume it is probably something simple I am 
overlooking.  I have thought that, perhaps, appending the zeros 
provides for easier hardware implementation. 

Or, maybe, a longer message string has certain advantages in regards 
to error detection - I may be on the right track with this, though I 
haven't thought much about the error detection properties of the CRC 
at this point and, as far as I know, it is the length of the 
generator polynomial and not the message string that determines the 
length of burst errors that may be detected.  

Date: 06/28/2002 at 04:01:25
From: Doctor Jeremiah
Subject: Re: Cyclic Redundancy Check

Hi there!  Thanks for writing.

Basically a CRC operates on only one bit at a time (the leftmost 
bit of each step's subtraction), but the width of the polynomial
is bigger than one bit so we need to add enough extra bits so
that in the last step of the division the rightmost bit of
the message is the leftmost bit of a subtraction between it and
the polynomial's multiple.

Remember that it's the remainder left after the subtraction
that is the useful result of the leftmost bit involved in
the subtraction.  So each remainder is the output of the
subtraction's leftmost bit.

            ___100_ <- three digits: only 3 bits processed
 poly -> 10 ) 1001  <- message
              10
              --    <- process first bit
               00
               00
               --   <- process second bit
                01
                00
                --  <- process third bit
                 1  <- remainder

Notice how the last bit does not get processed during
the creation of the remainder?  We need to add a 0
on the end of the message so that we do one more step.

And if the divisor were 3 digits long we would need to
add 2 zeros on the end of the message to be able to
process all the bits.

             ____10_ <- two digits: only 2 bits processed
 poly -> 100 ) 1001  <- message
               100
               ---   <- process first bit
                 01
                 00
                 --  <- process second bit
                  1  <- remainder

So you need those extra zeros so that the last bits get
processed (become the leftmosts bits of subtraction steps).

Look at this page and see if it helps:

  http://www.cs.jhu.edu/~scheideler/courses/600.344_S02/CRC.html 

Here are a couple of other pages you might find helpful:

  http://www.ross.net/crc/crcpaper.html 
  http://www.efg2.com/Lab/Mathematics/CRC.htm 

Let me know if my explanation is too confusing and I will
try to do a better job of explaining it.

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/28/2002 at 10:44:52
From: S.H.
Subject: Thank you (Cyclic Redundancy Check)

Dr. Jeremiah:

Thank you for your prompt response.  After doing a paper 
trace to see how the hardware actually manipulates the 
data, I think I understand your explanation perfectly.  

If we append the 0s first, we will end up with a nice, neat 
CRC in the M bit register (where M is the width of the 
generator polynomial) after processing the last bit of the 
original data string.  I have noticed, however, that there 
is always a leading 0 in the M bit register after the 
procedure is finished because the CRC will never be wider 
than M-1 bits.  If it is convenient, could you please tell 
me what is done with the CRC (in the hardware) after it is 
found?  Are the contents of the register (leading 0 plus 
CRC) added to the message string (plus appended 0s)?
  
Obviously, keeping the leading 0 in there wouldn't change 
anything, as any bit XORed with 0 is itself.  Or, instead 
of adding, does the sending computer know to simply APPEND 
the last M-1 bits (thereby cutting off that leading 0)?    

Thank you again for getting back to me so quickly.  
I value the explanation and I certainly wish I had known of 
this resource during my college career.  I would have made 
full use of it when I was struggling through Advanced 
Calc :)

S.H.

Date: 06/29/2002 at 20:51:32
From: Doctor Jeremiah
Subject: Re: Cyclic Redundancy Check

Hi S.H., 

The sending computer does append the M-1 bits of the CRC (without
the leading 0) to the original message (not the one with the
appended 0s).  Or it could OR the full CRC to the augmented
message (the one with the appended 0s).  The second option
is what I had recommended but they both do the same thing.

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 07/03/2002 at 10:23:46
From: S.H.
Subject: Thank you (Cyclic Redundancy Check)

Yes, thank you, that was exactly what I wanted to know, and
fully answers my question.  Thank you for your patience and 
for the explanation.  It really helped :-)