Query in Parallel CRC(urgent)

O

osr 19 years ago

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

formatting link

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

Vote

P

Petter Gustad 19 years ago

You can use the serial form and make a parallel version symbolically. Here is one example:

formatting link

Petter

A: Because it messes up the order in which people normally read text. Q: Why is top-posting such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail?

Vote

C

Colin Hankins 19 years ago

Hopefully this all makes sense. The serial version of the CRC is the CRC polynomial. If you take your serial version initialized to 0 and shift in a

1b, the resulting FCS is 00000001x. If you next shift in a 0b the resulting FCS is 00000002x. If you continue this process you will have a table of FCS values that look like this:

0000 0001

0000 0002 0000 0004 0000 0008 0000 0010 0000 0020 0000 0040 0000 0080 0000 0100 0000 0200 0000 0400 0000 0800 0000 1000 0000 2000 0000 4000 0000 8000 0001 0000 0002 0000 0004 0000 0008 0000 0010 0000 0020 0000 0040 0000 0080 0000 0100 0000 0200 0000 0400 0000 0800 0000 1000 0000 2000 0000 4000 0000 8000 0000

As you can tell all we did was shift that first initial bit all the way through each of the 32 flip-flops. But on

the 32nd (if you start the count from 0) shift that last bit is fed back into some of the other flop-flops. Thus the next shift in the sequence which corresponds with the power of your CRC polynomial is:

04C1 1DB7

This is your CRC polynomial. You can then continue shifting these values. What this table of values constitutes is

the Galois Field for your chosen polynomial.

Here are the shifts 32 to 39 in binary. This part of the Galois Field forms a matrix of 8 shifts used to shift in

your data one byte at a time. Lets call this matrix Alpha8.

32 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 33 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 34 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 35 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 36 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 37 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 38 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 0 39 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0

FCS(x+8)=(FCS(x)*Alpha8)+(NewByte*Alpha8)

Of course, the Alpha8 matrix multiplied by FCS(x) is the matrix formed by the Galois Field of shifts 39 down to 8.

Thus you can see the first term in the VHDL code you provide NewCRC(0) := D(6) xor D(0) xor C(24) xor C(30); comes from the formula I listed above. D is the new byte and Alpha8 is the first column of values in the matrix:

32 1 33 0 34 0 35 0 36 0 37 0 38 1 39 0

So D*Alpha8 is D(6) + D(0), and modulo addition is an xor so it is D(6) xor D(0). If we the do the same thing for

the second part of the equation, FCS(x)*Alpha8 you get C(30) + C(24). Putting it all together is D(6) xor D(0) xor

C(30) xor C(24).

You do this for each column to get all 32 values for the FCS.

Vote