## Parallel CRC Generator

Download a full version of this article |

Every modern communication protocol uses one or more error detection algorithms. Cyclic Redundancy Check, or CRC, is by far the most popular one. CRC properties are defined by the generator polynomial length and coefficients. The protocol specification usually defines CRC in hex or polynomial notation. For example, CRC5 used in USB 2.0 protocol is represented as 0×5 in hex notation or as G(x)=x^{5}+x^{2}+1 in the polynomial. This CRC is implemented in hardware as a shift register as shown in the following picture.

The problem is that in many cases shift register implementation is suboptimal. It only allows the calculation of one bit every clock. If a design has 32-bit wide datapath, meaning that every clock CRC module has to calculate CRC on 32-bit of data, this scheme will not work. Somehow this serial shift register implementation has to be converted into a parallel N-bit wide circuit, where N is the design datapath width, so that every clock N bits are processed.

I started researching the available literature on parallel CRC calculation methods and found only a handful of papers ([2], [3]) that deal with this issue. Most sources are academic and focus on the theoretical aspect of the problem. They are too impractical to implement in software or hardware for a quick code generation.

I came up with the following scheme that I’ve used to build an online Parallel CRC Generator tool. Here is a description of the steps in which I make use USB CRC5 mentioned above.

(1) Let’s denote N=data width, M=CRC width. For example, if we want to generate parallel USB CRC5 for 4-bit datapath, N=4, M=5.

(2) Implement serial CRC generator routine using given polynomial or hex notation. It’s easy to do in any programming language or script: C, Java, Perl, Verilog, etc.

(3) Parallel CRC implementation is a function of N-bit data input as well as M-bit current state CRC, as shown in the above figure. We’re going to build two matrices: Mout (next state CRC) as a function of Min(current state CRC) when N=0 and Mout as a function of Nin when M=0.

(4) Using the routine from (2) calculate CRC for the N values when Min=0. Each value is one-hot encoded, that is there is only one bit set. For N=4 the values are 0×1, 0×2, 0×4, 0×8. Mout = F(Nin,Min=0)

(5) Build NxM matrix, Each row contains the results from (3) in increasing order. For example, 1’st row contains the result of input=0×1, 2′nd row is input=0×2, etc. The output is M-bit wide, which the desired CRC width. Here is the matrix for USB CRC5 with N=4.

(6) Each column in this matrix, and that’s the interesting part, represents an output bit Mout[i] as a function of Nin.

(7) Using the routine from (3) calculate CRC for the M values when Nin=0. Each value is one-hot encoded, that is there is only one bit set. For M=5 the values are 0×1, 0×2, 0×4, 0×8, 0×10. Mout = F(Nin=0,Min)

(8) Build MxM matrix, Each row contains the results from (7) in increasing order. Here is the matrix for USB CRC5 with N=4

(9) Now, build an equation for each Mout[i] bit: all Nin[j] and Min[k] bits in column [i] participate in the equation. The participating inputs are XORed together.

Mout[0] = Min[1]^Min[4]^Nin[0]^Nin[3]

Mout[1] = Min[2]^Nin[1]

Mout[2] = Min[1]^Min[3]^Min[4]^Nin[0]^Nin[2]^Nin[3]

Mout[3] = Min[2]^Min[4]^Nin[1]^Nin[3]

Mout[4] = Min[0]^Min[3]^Nin[2]

That is our parallel CRC.

I presume since the invention of the CRC algorithm more than 40 years ago, somebody has already came up with this approach. I just coulnd’t find it and “reinvented the wheel”.

Keep me posted if the CRC Generation tool works for you, or you need more clarifications on the algorithm.

[**September 29th, 2010**] Users frequently ask why their implementation of serial CRC doesn’t match the generated parallel CRC with the same polynomial. There are few reasons for that:

– bit order into serial CRC isn’t the same as how the data is fed into the parallel CRC

– input data bits are inverted

– LFSR is not initialized the same way. A lot of protocols initialize it with F-s, and that’s what is done in the parallel CRC.

Download a full version of this article |

**References**

- CRC on Wikipedia
- G. Campobello, G Patane, M Russo, “Parallel CRC Realization”
- W Lu, S. Wong, “A Fast CRC Update Implementation”

hi, everyone if any could help me in coding crc in verilog with its test bench

thanks in advance

Hi,

may i know that how you are realizing matrix H1 and matrix H2.

Thanks

C.Ashok

Hi,

I couldn’t understand how to calculate the (Nin=0, Min) case. how i should enter data to CRC calculator in order to calculate Min=0×1,0×2, etc.

Thanks in advance

Dear Evgeni,

I generated crc module for ethernet with 32 bit polynomial and 32 bit data input.

Used a standard udp frame and made a small testbench to test crc verilog module.

Calculated crc online http://www.lammertbies.nl/comm/info/crc-calculation.html

The 2 outputs donot match. Tried byte-reflect from its least-significant-bit-first order to the normal most-significant-bit first order. Does not seem to match.

Do I need to do something else ?

Thanks in advance!

Evgeni,

I found the answer in the comments section.

Thanks for providing the tool.

full version of this document pdf file has some typo.

Mout[0] = Min[1] ^ Min[4] ^ Min[0] ^ Min[3]

-> Mout[0] = Min[1] ^ Min[4] ^ Nin[0] ^ Nin[3]

Shouldn’t the crc_out be 1 bit less (in width) than the polynom itself? I see crc_out in the width of the polynom I inserted.

while making wcb castings we are using crc materials. what about the role of crc

can you help me

Hi

I am using the crc32 generator code from this site for poly : 04C11DB7 for data width 128.

I am using it in my code and I have to do the verification for which I am writing the following function

function bit[31:0] crc32_8(bit [31:0] accum, bit [127:0] data);

bit [31:0] local_accum = accum;

bit [7:0] local_data = data;

for (int j=0; j> 1) ^ ( (((local_data[j] & 1) ^ (local_accum & 1)) == 1) ? 32′hEDB88320 : 0 );

local_data[j] = local_data[j] >> 1;

end

return local_accum;

endfunction : crc32_8

but the answers are not matching. Do I need to take a complement and reverse the crc?

Can someone please help?

Hi,

I have a question. I am using the crc32 generator code from this site for poly : 04C11DB7 for data width 32 and 16. Theoretically, the result of 32-bits data should be cascaded result of 2 16-bit data like following code,

assign crc32_d32 = gen_crc32_d32(data[31:0], crc_in);

assign crc32_d16_l = gen_crc32_d16(data[15:0], crc_in);

assign crc32_d16_h = gen_crc32_d16(data[31:16],crc32_d16_l);

I think crc32_d32 should be equal to crc32_d16_h, but the simulation result is not for data that is not 32′h0.

Can anyone tell me why these 2 results are different?

Hi,

First thing is to make it work with 1-bit data, to eliminate the possibility of incorrect bit/byte order. That’s usually the source of most of the problems.

Thanks,

Evgeni

@Evgeni

Hi, Evgeni,

I had tried to implement 1-bit and loop 32 times, but got different result with 32-bits/round and 16-bits 2 rounds. Suppose I should get 16-bits/round result after 16-th loop and 32-bits/round result at 32-th loop. I completely confused….

That’s correct,

You shoud get the same results with 32 data bit single round, 1 data bit 32 rounds, and 16 data bits 2 rounds.

Thanks,

Evgeni

I have a problem to download the VHDL implementation code when i set up my data length and polynom length. Is the generator link somehow broken?

Hi,

I cannot reproduce this problem. Can you please specify data and polynom you’re using ?

Thanks,

Evgeni

@Evgeni

I want to test a data width of 6 bits with a crc16. When i run the first setup, it says:

“Selected USB 2.0 CRC16 and data width=6. Proceed to Step 2″. It is marked as green.

When I try to download the code in step 2 as verilog or vhdl file nothing happens.

I am designing an Ethernet application where I am required to form the packet payload at a rate of 128-bits each clock. However, each clock, from 1 to 4 of the 32-bit words forming the 128 bits will be valid.

Can I use 4 32-bit CRC generators concurrently (1 for each of the 4 32-bit streams) and then combine the 4 CRC results at the end of the payload to form the complete CRC32 for the packet? Can the 4 partial results be easily combined?

Any suggestions would be much appreciated. Thanks.

Hi,

Each of the four streams will look like this: “….D000D000D000…”, where each nibble in that string is 32-bit. “D” is a data dword, followed by 3 dwords of zeros. So after each 32-bit CRC calculation on data, you’d need to multiply the result by X^96.

Thanks,

Evgeni