Calculate the Cyclic Redundancy Code for a binary sequence

R

Ross

New member
Joined
Dec 31, 2009
Messages
2
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.
 
The cyclic redundancy code is calculated by finding the remainder\displaystyle The\ cyclic\ redundancy\ code\ is\ calculated\ by\ finding\ the\ remainder
that results from dividing the binary sequence by the generator.\displaystyle that\ results\ from\ dividing\ the\ binary\ sequence\ by\ the\ generator.
In binary the generator x4+x2+1 may be written 10101.\displaystyle In\ binary\ the\ generator\ x^4+x^2+1\ may\ be\ written\ 10101.
The CRC is the remainder resulting from dividing 1010111 by 10101.\displaystyle The\ CRC\ is\ the\ remainder\ resulting\ from\ dividing\ 1010111\ by\ 10101.

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

chrisr said:
[The CRC is the remainder resulting from dividing 1010111 by 10101.\displaystyle The\ CRC\ is\ the\ remainder\ resulting\ from\ dividing\ 1010111\ by\ 10101.
Click to expand...


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

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

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.
 
In this example the binary division is very fast.\displaystyle In\ this\ example\ the\ binary\ division\ is\ very\ fast.

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

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

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