What is cyclic redundancy check and how it works in simple terms (for-dummies style)?

Question

I'm having trouble understanding the concept and workings of the ugly sounding term "cyclic redundancy check". I'm attending a college course on Computer Networks and I'm getting lost already.

The trouble is that my understanding of mathematics is very limited (studied maths a long time ago in school and forgot most of it) and I can't get for example what the hell a generator polynomial is, what polynomials have to do with CRC and to sum it up - all of that seems totally incomprehensible to me.

I read the wiki entry on CRC but it didn't help me since I'm no good at maths and all these symbols and math terms are like Chinese to me.

I understand that CRC is used for error detection when sending data on the network but from then on I'm lost.

Can anybody help me with explaining this concept in simple terms and possibly give an example?

During the last lecture the professor started drawing all these one's and zeroes, dividing and I don't know what and I was just staring and feeling stupid.

I'd be very grateful it anybody can help me understand!

Answer 1

If you want the answer to be very simple you need to accept some oversimplification, if you're willing to live with that, here it goes:

Data is transmitted over imperfect links - errors may occur on the way. Imagine you want to make sure the received information is the same as the transmitted one without wasting too much bandwidth, how would you do that?

You could transmit every piece of information twice and if on the receiving end you see that the first one is different to the second one you know an error has occurred and you need to request the data again - but this would be very wasteful, it would effectively cut your bandwidth in half.

Now, what if you could calculate some value that is much smaller than the data itself yet is dependent on it? So if the data changed along the way (due to error), the calculated value would no longer "match" the data and you would know an error has occurred. Is there such a calculation?

What about simple division and taking a remainder as this value?

Say I want to transmit an information/number 1,000. I divide it by chosen number - like 6 for instance ... that gives me 166 and a remainder of 4. I take the remainder as my check value which is much smaller than the information I'm actually transmitting so I'm not wasting too much bandwidth and I transmit 1,000 followed by 4. A receiver gets it, takes the number 1,000 divides it by 6 and if the remainder is 4 then it assumes that no error has occurred.

If an error had occurred and it would receive 998 instead of 1,000 due to error on the link - it would divide it by 6, get a remainder of 2 which does not match 4 and viola it knows an error has occurred. That is the basic principle of CRC.

Of course it is a little more complicated because it divides by a polynomial but the principle of using a remainder as a "short value representing the data" to check it for errors in the same way stands.

I hope this helps you to get your head around on what's going on ;)