Associated Topics || Dr. Math Home || Search Dr. Math

### 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).

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
for the explanation.  It really helped :-)

```
Associated Topics:
College Number Theory
High School Calculators, Computers
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search