Calculate the Cyclic Redundancy Code for a binary sequence

[Ross]

Hi, first post here so I hope I have got the right topic area.

I am having trouble with how to calculate the Cyclic Redundancy Code (CRC) of a binary number, particularly the actual long division of it. The example question I will give below is one that I have the answer for but I dont understand the answer or how the working out is done, so feel free to inform me of the basics of this type of question.

The question is:

Calculate the Cyclic Redundancy Code (CRC) for the binary sequence 1010111 using the generator function X[sup:334r2hmg]4[/sup:334r2hmg] + X[sup:334r2hmg]2[/sup:334r2hmg] + 1


I will not include the answer that I have just yet, but may start to put the first few bits up if it is requested.

 

[chrisr]

\(\displaystyle The\ cyclic\ redundancy\ code\ is\ calculated\ by\ finding\ the\ remainder\)
\(\displaystyle that\ results\ from\ dividing\ the\ binary\ sequence\ by\ the\ generator.\)
\(\displaystyle In\ binary\ the\ generator\ x^4+x^2+1\ may\ be\ written\ 10101.\)
\(\displaystyle The\ CRC\ is\ the\ remainder\ resulting\ from\ dividing\ 1010111\ by\ 10101.\)

\(\displaystyle You\ can\ do\ this\ in\ binary,\ or\ in\ electronics\ using\ a\ shift\ register\ and\ exor\ gates,\)
\(\displaystyle or\ using\ polynomial\ division\ in\ powers\ of x,\)
\(\displaystyle or\ by\ dividing\ 87\ by\ 21,\ which\ is\ 4\ remainder\ 3.\)
\(\displaystyle The\ CRC\ checksum\ is\ 0011.\)

 

[Ross]

Thank you for you your input ChrisR.

[\(\displaystyle The\ CRC\ is\ the\ remainder\ resulting\ from\ dividing\ 1010111\ by\ 10101.\)

Can you show the binary division for this? And then what would the word to be transmitted be?

\(\displaystyle You\ can\ do\ this\ in\ binary,\ or\ in\ electronics\ using\ a\ shift\ register\ and\ exor\ gates,\)
\(\displaystyle or\ using\ polynomial\ division\ in\ powers\ of x,\)
\(\displaystyle or\ by\ dividing\ 87\ by\ 21,\ which\ is\ 4\ remainder\ 3.\)
\(\displaystyle The\ CRC\ checksum\ is\ 0011.\)

I sort of see what you are getting at here except for the last line. Although, none of those four lines are in the answer I have, so I am not completely sure if what you have there is right or not.


To clarify, this is an exam question so I would have to show all my working out on paper.

 

[chrisr]

\(\displaystyle In\ this\ example\ the\ binary\ division\ is\ very\ fast.\)

\(\displaystyle 1010111\ divided\ by\ 10101.\)
\(\displaystyle 10101\ goes\ into\ 1010100\ 100\ times,\ which\ in\ decimal\ is\ 4.\)
\(\displaystyle The\ remainder\ therefore,\ is\ 11\ which\ is\ 3\ in\ decimal.\)
\(\displaystyle You\ now\ need\ to\ know\ how\ many\ binary\ digits\ make\ the\ checksum.\)
\(\displaystyle Let\ me\ double-check\ this.\)

\(\displaystyle That\ CRC\ isn't\ good\ enough\ to\ provide\ an\ error-check\ of\ zero.\)
\(\displaystyle There\ are\ numerous\ algorithms,\ I'll\ have\ another\ look.\)

 

[chrisr]

\(\displaystyle Hi,\ Ross,\)

\(\displaystyle The\ idea\ is\ that\ the\ message\ is\ considered\ as\ a\ binary\ number.\)
\(\displaystyle The\ generator\ polynomial\ is\ the\ divisor\ which\ can\ be\ written\ in\ binary.\)
\(\displaystyle Dividing\ the\ message\ by\ the\ generator\ yields\ a\ remainder\ left\ over\)
\(\displaystyle after\ the\ division.\)
\(\displaystyle This\ remainder\ is\ the\ checksum\ and\ is\ transmitted\ with\ the\ data.\)
\(\displaystyle At\ the\ receiver\ the\ same\ division\ takes\ place\ on\ the\ message\ bits,\)
\(\displaystyle not\ including\ the\ attached\ checksum.\)
\(\displaystyle The\ receiver\ should\ calculate\ the\ same\ checksum\ and\ notice\ that\)
\(\displaystyle the\ transmitted\ checksum\ agrees\ with\ the\ checksum\ calculated\ by\ the\ receiver.\)
\(\displaystyle In\ your\ case\ the\ remainder\ is\ binary\ 11,\)
\(\displaystyle it's\ transmission\ depends\ only\ on\ the\ number\ of\ bits\ wide\ this\ checksum\ is\ transmitted\ using.\)
\(\displaystyle A\ 3-bit\ checksum\ is\ 011,\ 4-bits\ is\ 0011\ etc.\)