CRC(cyclic redundancy check) - hardware implementation

[fiol73]

Dear all,

I have a problem. I do not understand how I can implement a divisor circuit for CRC, when the generator polynomial and the message vector are given. The idea is that I should be able to design an easy divisor circuit with G(x)=x^3+x+1 and message vector M(x)=x^6+x^5+x+1 that emulates the binary division:

(2^n)*M(x) : G(x) which is in binary:
_____________________________
1011 ) 1100011 000 (last 3 zeros: FCS)

How to do this operation designing a divisor circuit and shift registers?

I hope somebody out there will help me. Thanks.

 

[ljcox]

It's a long time since I studied CRC polynomials, so I don't remember what the G(x) & M(x) are.

However, if all you want to do is divide one binary number by another, then you could do it by successive subtraction and shift the result of each step in a shift register. eg 12/4 = 12 - 4 - 4 - 4 = 0. Since 4 had to be subtracted 3 times then 12/4 = 3. 13/4 = 13 - 4 - 4 - 4 - 4 = -3 so it is 3 with a remainder of 1.

 

[atferrari]

If you intend to use a micro and by chance it's a 18F, not gates, you could check a division routine I wrote, under PICs

**broken link removed**

might be too much but could help you to understand. HTH

 

[geko]

How to do this operation designing a divisor circuit and shift registers?

Google for 'Linear Feedback Shift Register' (LFSR). There you will find what you are looking for.

 

[Papabravo]

You need a shift register with access to the outputs of the appropriate stages and some exclusive OR gates.

In a micro it is usually done with a lookup table so all the data bits and the current CRC are used to compute the next CRC.

 

[Leftyretro]

National Semiconductor had a IC chip CRC generator/checker in the 80s that performed basic operation but not sure if it was configurable to all the flavors of CRC used these days.

http://www.datasheetcatalog.com/datasheets_pdf/7/4/F/4/74F401.shtml

Lefty