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 :-)
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.