( ESNUG 370 Item 4 ) -------------------------------------------- [05/17/01]
Subject: The Free EASICs Web CRC Tool & The Easy Way To Understand CRC's
> I found a CRC generation tool at http://www.easics.com/webtools/crctool .
> The tool generated a code for 32-bit CRC calculation. The polynomial used
> was (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32). I've included some equations
> here.
>
> NewCRC[0] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[24]
> ^ D[16] ^ D[12] ^ D[10] ^ D[9] ^ D[6] ^ D[0] ^ C[0] ^ C[6]
> ^ C[9] ^ C[10] ^ C[12] ^ C[16] ^ C[24] ^ C[25] ^ C[26]
> ^ C[28] ^ C[29] ^ C[30] ^ C[31]; ...
>
> Can anybody tell me how these equations are derived? How can we relate
> these equations with the polynomial?
>
> - T. Sung
From: Muzaffer Kal <muzaffer@dspia.com>
Think about the CRC shift register as a state machine. There is a data
input and the current state of CRC. At every clock the current state of the
CRC gets updated by obeying the rules of the feedback taps. If you do this
"data bus width" number of times, you get the a new state in the shift
register. Now you have a state of shift register which is "data bus width"
away from the start. This involves the initial state of the shift register
and the previous "data bus width" inputs. The code you get from crctool is
the result of a symbolic manipulation which executes this algorithm. This
can be accomplished with a scripting tool, i.e. Perl.
- Muzaffer Kal
FPGA DSP Consulting http://www.dspia.com
---- ---- ---- ---- ---- ---- ----
From: "Daniel Elftmann" <dane@actel.com>
You might find the following document helpful:
http://www.actel.com/docs/datasheets/CRCds.pdf
The intent of the Datasheet was to answer questions such as yours, so please
let me know if it does.
- Daniel Elftmann
Actel Corporation
---- ---- ---- ---- ---- ---- ----
From: Utku Ozcan <ozcan@netas.com.tr>
These equations are derived by multiplication of two matrices, which are
defined in Galois theory. This calculator has been implemented in either
scripting language or anyhthing like C. In any book on Error Correction &
Detection which covers Galois Fields GF (x, y) and CRC will help you.
- Utku Ozcan
Nortel Networks
---- ---- ---- ---- ---- ---- ----
From: Mark Curry <mcurry@ti.com>
Don't let all those other responses regarding "Galois" fields and ECCs throw
you off. Although these things are very useful, they're overboard for
understanding simple CRCs.
An EXCELLANT paper on understanding CRCs is located at:
http://www.ross.net/crc/crcpaper.html
CRCs from a hardware perspective are very easy to implement and understand.
It's only when you get to trying to implemenent them in software where
things get interesting. People have come up with some very interesting
optimized algorithms for calculating CRCs. But when you have control over
all the bits - it's very simple.
So, to start just read the above paper up to the point where he starts
talking about software algorithms...
- Mark Curry
Texas Instruments
|
|
