Query in 32 bit Parallel CRC...urgent

[osr]

Hi,

Can anyone plz tell me the theory behind 32bit parallel CRC? i m not
getting the basis on which the 32 bit CRC is being calculated in the
code below.This code is generated from the CRC tool of wesite www.easics.com.I
refered many ieee papers even then i couldnt get the idea.Plz help me
its urgent.


library IEEE;
use IEEE.std_logic_1164.all;

package PCK_CRC32_D8 is

-- polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
-- data width: 8
-- convention: the first serial data bit is D(7)
function nextCRC32_D8
( Data: std_logic_vector(7 downto 0);
CRC: std_logic_vector(31 downto 0) )
return std_logic_vector;

end PCK_CRC32_D8;

library IEEE;
use IEEE.std_logic_1164.all;

package body PCK_CRC32_D8 is

-- polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
-- data width: 8
-- convention: the first serial data bit is D(7)
function nextCRC32_D8
( Data: std_logic_vector(7 downto 0);
CRC: std_logic_vector(31 downto 0) )
return std_logic_vector is

variable D: std_logic_vector(7 downto 0);
variable C: std_logic_vector(31 downto 0);
variable NewCRC: std_logic_vector(31 downto 0);

begin

D := Data;
C := CRC;

NewCRC(0) := D(6) xor D(0) xor C(24) xor C(30);
NewCRC(1) := D(7) xor D(6) xor D(1) xor D(0) xor C(24) xor C(25)
xor
C(30) xor C(31);
NewCRC(2) := D(7) xor D(6) xor D(2) xor D(1) xor D(0) xor C(24)
xor
C(25) xor C(26) xor C(30) xor C(31);
NewCRC(3) := D(7) xor D(3) xor D(2) xor D(1) xor C(25) xor C(26)
xor
C(27) xor C(31);
NewCRC(4) := D(6) xor D(4) xor D(3) xor D(2) xor D(0) xor C(24)
xor
C(26) xor C(27) xor C(28) xor C(30);
NewCRC(5) := D(7) xor D(6) xor D(5) xor D(4) xor D(3) xor D(1) xor
D(0) xor C(24) xor C(25) xor C(27) xor C(28) xor C(29)
xor
C(30) xor C(31);
NewCRC(6) := D(7) xor D(6) xor D(5) xor D(4) xor D(2) xor D(1) xor
C(25) xor C(26) xor C(28) xor C(29) xor C(30) xor
C(31);
NewCRC(7) := D(7) xor D(5) xor D(3) xor D(2) xor D(0) xor C(24)
xor
C(26) xor C(27) xor C(29) xor C(31);
NewCRC(8) := D(4) xor D(3) xor D(1) xor D(0) xor C(0) xor C(24)
xor
C(25) xor C(27) xor C(28);
NewCRC(9) := D(5) xor D(4) xor D(2) xor D(1) xor C(1) xor C(25)
xor
C(26) xor C(28) xor C(29);
NewCRC(10) := D(5) xor D(3) xor D(2) xor D(0) xor C(2) xor C(24)
xor
C(26) xor C(27) xor C(29);
NewCRC(11) := D(4) xor D(3) xor D(1) xor D(0) xor C(3) xor C(24)
xor
C(25) xor C(27) xor C(28);
NewCRC(12) := D(6) xor D(5) xor D(4) xor D(2) xor D(1) xor D(0)
xor
C(4) xor C(24) xor C(25) xor C(26) xor C(28) xor
C(29) xor
C(30);
NewCRC(13) := D(7) xor D(6) xor D(5) xor D(3) xor D(2) xor D(1)
xor
C(5) xor C(25) xor C(26) xor C(27) xor C(29) xor
C(30) xor
C(31);
NewCRC(14) := D(7) xor D(6) xor D(4) xor D(3) xor D(2) xor C(6)
xor
C(26) xor C(27) xor C(28) xor C(30) xor C(31);
NewCRC(15) := D(7) xor D(5) xor D(4) xor D(3) xor C(7) xor C(27)
xor
C(28) xor C(29) xor C(31);
NewCRC(16) := D(5) xor D(4) xor D(0) xor C(8) xor C(24) xor C(28)
xor
C(29);
NewCRC(17) := D(6) xor D(5) xor D(1) xor C(9) xor C(25) xor C(29)
xor
C(30);
NewCRC(18) := D(7) xor D(6) xor D(2) xor C(10) xor C(26) xor C(30)
xor
C(31);
NewCRC(19) := D(7) xor D(3) xor C(11) xor C(27) xor C(31);
NewCRC(20) := D(4) xor C(12) xor C(28);
NewCRC(21) := D(5) xor C(13) xor C(29);
NewCRC(22) := D(0) xor C(14) xor C(24);
NewCRC(23) := D(6) xor D(1) xor D(0) xor C(15) xor C(24) xor C(25)
xor
C(30);
NewCRC(24) := D(7) xor D(2) xor D(1) xor C(16) xor C(25) xor C(26)
xor
C(31);
NewCRC(25) := D(3) xor D(2) xor C(17) xor C(26) xor C(27);
NewCRC(26) := D(6) xor D(4) xor D(3) xor D(0) xor C(18) xor C(24)
xor
C(27) xor C(28) xor C(30);
NewCRC(27) := D(7) xor D(5) xor D(4) xor D(1) xor C(19) xor C(25)
xor
C(28) xor C(29) xor C(31);
NewCRC(28) := D(6) xor D(5) xor D(2) xor C(20) xor C(26) xor C(29)
xor
C(30);
NewCRC(29) := D(7) xor D(6) xor D(3) xor C(21) xor C(27) xor C(30)
xor
C(31);
NewCRC(30) := D(7) xor D(4) xor C(22) xor C(28) xor C(31);
NewCRC(31) := D(5) xor C(23) xor C(29);

return NewCRC;

end nextCRC32_D8;

end PCK_CRC32_D8;

Thanks

 

[Ben Jones]

Hi,

Can anyone plz tell me the theory behind 32bit parallel CRC? i m not
getting the basis on which the 32 bit CRC is being calculated in the
code below.

The CRC calculation is just an LFSR. Every time a new bit arrives, the
register is shifted and some XORs are done. You can write down an equation
for the new CRC state in terms of the old CRC state and the new input bit -
it looks a lot like the "generator polynomial" that defines the CRC being
used. Hopefully you know that much already, but if not, it's generally
available knowledge.

To develop a parallel CRC implementation, you just have to consider what
happens when you update the CRC multiple times. This just means applying the
simple "single-update" equation over and over again. The state of the CRC
register after two updates is a function of the original state and the two
input bits, nothing more. The equation for this can be derived from the
single-update equation in a number of ways but it's a pretty easy thing to
do once you know how the CRC works.

Deriving the multiple-update equations for longer and longer look-aheads is
not complicated, but it is tedious and error prone - hence there are tools
(like the one you found) that do it for you.

My suggestion would be to start with a very small LFSR with a simple
polynomial, and derive these equations yourself for that reduced system - on
paper, and/or with a little bit of programming. Once you've been through
that process you'll understand a lot better.

Cheers,

-Ben-

 

[Pascal Peyremorte]

Ben Jones a écrit :

The CRC calculation is just an LFSR. Every time a new bit arrives, the
register is shifted and some XORs are done.

Hello,

The mathematical theory is quite a bit more complex and the "shift / xor" is
only the result of a mathematical simplification.

The CRC of a block stream is the reminder of the divide of the number constitued
by all bytes of the block following each other by the number used in the
exclusive OR (the "CRC generator").

As you can write in decimal that any number N= "...dcba" = a*10^0 + b*10^1 + ...
You can consider your stream as a Base256 number, with a "byte" element :
N = Byte0*256^0 + Byte1*256^1 + ... Byten*256^n,
which is the same than consider it as a base 2 number with a "bit" element :
N = Bit0*2^0 + Bit1*2^1 + Bit2*2^2 + ....

Then you can divide that number N by the "CRC generator", a value that you
choose for some properties, ie 0x110201 (= CCITT polynom = 2^16+2^12+2^5+2^0)
and the CRC will be the reminder of the divide.


When you can compute the CRC bit by bit in hardware in realtime, there are not
any problem, the computation is quite simple and fast.

But in a byte based stream, (or wider), the CRC computation needs too much time
and resources, so the mathematicians have produced an equivalent result based on
the modulo 2 theory that enable to compute the CRC with a significant less
amount of time and ressources.

Please refer to the excellent article "The Great CRC Mystery" from Terry Ritter,
available on many web site like http://www.ciphersbyritter.com/ARTS/CRCMYST.HTM.

Pascal

 

[Ben Jones]

Ben Jones a écrit :

The mathematical theory is quite a bit more complex and the "shift / xor"
is only the result of a mathematical simplification.

Yes, that's almost true. The mathematics underlying *why* CRCs work as
error-detecting codes is pretty complicated. However, to go from
remainder-only modulo-2 division to shift/xor operations is not even a
simplification - they are exactly the same thing! See for example Numerical
Recipes in C, section 20.3 (p896+).

The Ritter link is very useful background. It is definitely most important
to understand the basic principles of serial CRC before considering parallel
architectures!

Cheers,

-Ben-

 

[Mike Treseler]

Can anyone plz tell me the theory behind 32bit parallel CRC? i m not

Google this group.
This subject has been covered many times.

-- Mike Treseler