CRC circuit

[tru]

In Step 6, you’re ready to construct the parallel CRC equations. Each set bit j in column i of the matrix H1—and that’s the critical part of the method—participates in the parallel CRC equation of the bit MOUT as NIN[j].  Likewise, each set bit j in column i of the matrix H2 participates in the parallel CRC equation of the bit MOUT as MIN[j].  All participating inputs MIN[j] and NIN[j] that form MOUT are XORed together.

In http://outputlogic.com/my-stuff/circuit-cellar-january-2010-crc.pdf#page=4 , step 6 wordings are so vague and confusing ...

I think step 6 is same meaning as the slightly clearer step 9 on the webpage version http://outputlogic.com/?p=158:

(9) Now, build an equation for each Mout bit: all Nin[j] and Min[k] bits in column 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.

It basically just means the equations are made using the columns and rows of the two matrices, i.e. for each Mout column look at the rows where there is a 1 and xor them as an equation.

So for instance the first equation Mout[0], if you look at the first column (right hand side) in the first matrix you see there is a 1 value for rows Nin[0] and Nin[3], and similarly for the second matrix in Mout[0] column there is a 1 value for rows Min[1] and Min[4], these together gives you the first equation:
Mout[0] = Min[1]^Min[4]^Nin[0]^Nin[3]

[promach]

So for instance the first equation Mout[0], if you look at the first column (right hand side) in the first matrix you see there is a 1 value for rows Nin[0] and Nin[3], and similarly for the second matrix in Mout[0] column there is a 1 value for rows Min[1] and Min[4], these together gives you the first equation:
Mout[0] = Min[1]^Min[4]^Nin[0]^Nin[3]

but how does doing this cross-mapping across these two matrices generate a "parallel" CRC ?

[promach]

I do not quite understand how the following serial implementation of CRC works ?

Why crc5_serial[2] = crc[1] ^ crc[4] ^ data; ?

Code: [Select]

/=============================================================
// Verilog function that implements serial USB CRC5
//=============================================================
function [4:0] crc5_serial;
input [4:0] crc;
input data;
begin
        crc5_serial[0] = crc[4] ^ data;
        crc5_serial[1] = crc[0];
        crc5_serial[2] = crc[1] ^ crc[4] ^ data;
        crc5_serial[3] = crc[2];
        crc5_serial[4] = crc[3];
end
endfunction
//============================================================


[ataradov]

This is a literal implementation of the most basic CRC circuit like this https://media.cheggcdn.com/media/611/61121185-c994-4bb8-829b-e2f0fa545114/phpOk2gly.png Note that polynomial is different on the picture, but the same principle applies.

EDIT: Well, your article has the actual circuit.  I'm not really sure what the question is actually asking then. This is how you build CRC circuits.

[tru]

Why crc5_serial[2] = crc[1] ^ crc[4] ^ data; ?

As ataradov said it is "literally" the LFSR circuit as shown in figure 1 in the article.

If you look at figure 1 there are two xor gates and five shift register bit boxes, let's label the xor gates xor0 and xor1, and shift boxes from right to left as box0 to box4.

code from xor0 gate:
the first xor gate is fed with input box4 and data bit and we can write this as:

Code: [Select]

xor0_output = box4 ^ datasince box4 is crc[4] in the Verilog code so the above translates directly to the line:

Code: [Select]

crc5_serial[0] = crc[4] ^ data
code from xor1 gate:
the second xor gate is fed with input box1 and the output of xor0 gate and we can write this as:

Code: [Select]

xor1_output = box1 ^ xor0_output
which is same as:
xor1_output = box1 ^ box4 ^ datasince box1 is crc[1] and box4 is crc[4] in the Verilog code the above translates directly to the line:

Code: [Select]

crc5_serial[2] = crc[1] ^ crc[4] ^ data

[hamster_nz]

That function combines the CRC's state and the input data bit to generate the next state value.

 It doesn't have the required storage elements to hold that state.

That will be defined in whatever is using this function.

[promach]

How does the following serial CRC code implementation works ?
It is different from the long division operations.

crc_serial_optimized.v

Code: [Select]

module crc_serial_optimized(clk, reset, data, crc);

//=============================================================
// Verilog function that implements serial USB CRC5
//=============================================================

input clk, reset;
input data;
output reg [4:0] crc;

always @(posedge clk)
begin
    if(reset) crc <= 0;

    else begin

        crc[0] <= crc[4] ^ data;
        crc[1] <= crc[0];
        crc[2] <= crc[1] ^ crc[4] ^ data;
        crc[3] <= crc[2];
        crc[4] <= crc[3];
    end
end

//============================================================

endmodule

crc_serial_optimized_tb.v

Code: [Select]

module crc_serial_optmized_tb();

reg clk;
reg reset;
reg data;
wire [4:0] crc;

wire new_data;

crc_serial_optimized crc5(.clk(clk), .reset(reset), .data(data), .crc(crc));

initial
begin
   $dumpfile("crc_serial_optimized.vcd");
   $dumpvars(1, crc5);

   clk <= 0;
   reset <= 1;
   data <= 0;
   
   @(posedge clk);
   @(posedge clk);

   reset <= 0;

   @(posedge clk);
   @(posedge clk);

   //data = 4'b1101;  "0xD"
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b1;

   @(posedge clk);

   // data = 4'b0101;  "0xA"
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b0;

   #50 $finish;
end

always  #5 clk = !clk;

endmodule


[ataradov]

Here is an article that explains the transition from the long division to the LFSR version http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

It is a long division, you just don't keep the integer part of the result.

[promach]

What do you exactly mean by It is a long division, you just don't keep the integer part of the result. ?

[ataradov]

I mean exactly what I said. CRC is the remainder from the division. You don't need to keep the result of the division, just the remainder. And that what this LFSR circuit does. I have no way to explain that any better.

Work though the first two examples in that link. It shows detailed operation of the long division and equivalent LFSR-based algorithm.

[promach]

Your so-called LFSR circuit is just long division which requires zeroes to be appended to the end of the message bits.



crc_serial_long_division.v

Code: [Select]

module crc_serial_long_division(clk, reset, data, crc);

//=============================================================
// Verilog function that implements serial USB CRC5
//=============================================================

input clk, reset;
input data;
output reg [4:0] crc;

always @(posedge clk)
begin
    if(reset) crc <= 0;

    else begin

        crc[0] <= crc[4] ^ data;
        crc[1] <= crc[0];
        crc[2] <= crc[1] ^ crc[4];
        crc[3] <= crc[2];
        crc[4] <= crc[3];
    end
end

//============================================================

endmodule

crc_serial_long_division_tb.v

Code: [Select]

module crc_serial_long_division_tb();

reg clk;
reg reset;
reg data;
wire [4:0] crc;

wire new_data;

crc_serial_long_division crc5(.clk(clk), .reset(reset), .data(data), .crc(crc));

initial
begin
   $dumpfile("crc_serial_long_division.vcd");
   $dumpvars(1, crc5);

   clk <= 0;
   reset <= 1;
   data <= 0;
   
   @(posedge clk);
   @(posedge clk);

   reset <= 0;

   @(posedge clk);
   @(posedge clk);

   //data = 4'b1101;  "0xD"
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b1;

   @(posedge clk);

   // data = 4'b1010;  "0xA"
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b1;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   // appends 5 zeroes
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b0;

   @(posedge clk);
   data <= 1'b0;

   #50 $finish;
end

always  #5 clk = !clk;

endmodule


[ataradov]

What do you mean by "your"? Yes, LFSR is a way to implement a long division that discards quotient and produces just a remainder. Did I say anything else?

I'm not really sure what do you want from us here.

[promach]

Why optimized version at reply #56 does not require zero appending to the end of message bits , while long division version at reply #60 requires so ?

optimized version



long division version

[ataradov]

Section 4.2 "Modified CRC-8 bitwise implementation for one byte input data" of the link I posted earlier explains the difference.

[promach]

The explanation in section 4.2 : The first 8 left-shifts are useless because the CRC value is initialized with 0 so no XOR operation is performed. This means we can initialize the CRC value directly with the input byte.
still does not explain the difference between the top input of the XOR gate in the middle as shown in reply #62

[hamster_nz]

LFSRs are related to CRCs.

LFSRs have the XNOR or XOR forms,

So wondering if the same is true for CRCs, and they have different formas I Googled for "Different forms of CRC".

Now Google thinks I have colo-rectal cancer. 

[tru]

long division version (crc_serial_long_division.v):
Is a LFSR circuit that performs a portion of long division to give remainders.
Note: it does NOT produce traditional CRC at each shift stage, the CRC is produced at the end after you feed in zeroes of CRC width, see *key note below.

optimized version (crc_serial_optimized.v)
Is a LFSR circuit that produces CRC at each shift stage, hence optimized version (or perhaps better: direct version).
The optimised one doesn't need to be fed with zeroes because it directly produces traditional CRC at each shift stage.
Optimisation is possible because the zeroes are constant values.  Feeding in zeroes will not affect the XOR operations (result remains unchanged if you xor with 0) but it does affect the INPUT of the XORs.
If you feed in zeroes upto CRC width the first box will wrap around to the first, hence why the middle XOR's input is changed to the output of the first XOR logic gate.

*The key note here is that the traditional CRC isn't just the remainder of the message, it is the remainder of the message appended with zeroes of CRC width.

[promach]

Optimisation is possible because the zeroes are constant values.  Feeding in zeroes will not affect the XOR operations (result remains unchanged if you xor with 0) but it does affect the INPUT of the XORs. 
If you feed in zeroes up to CRC width, the first box will wrap around to the first, hence why the middle XOR's input is changed to the output of the first XOR logic gate.

What do you exactly mean by the first box will wrap around to the first ?

[ataradov]

still does not explain the difference between the top input of the XOR gate in the middle

It does. That's the exact modification you need to  make to initialize the CRC without waiting for it to shift the initial zeros. Looks how optimized version feeds the input bit into all the taps (2 in this case). This way you don't need to wait for the initial zeros to shift out.

[tru]

Optimisation is possible because the zeroes are constant values.  Feeding in zeroes will not affect the XOR operations (result remains unchanged if you xor with 0) but it does affect the INPUT of the XORs. 
If you feed in zeroes up to CRC width, the first box will wrap around to the first, hence why the middle XOR's input is changed to the output of the first XOR logic gate.

What do you exactly mean by the first box will wrap around to the first ?

If you feed in zeroes of CRC width the value in the first box will xor middle gates and wrap around.

Let's look at the long division LFSR stages with a very simple example.
We are using USB CRC5 with a data bit (message bit) width of 1.
Suppose our message is 1:
data = 1

Note the results of each stage is calculated and shown in the next stage so I can show previous and current.

About the stages:
First we feed in message bit 1 at stage 0.
Next we append zeroes, so feed in a zero for the following five stages (width of CRC).

Notice the 1 coloured in red, it shows how this 1 bit moves inside the LFSR, this 1 is the XOR0 gate result from the start.

Look at the last stage 5, the red coloured 1 has reached into the last box, and now begins to wrap around and will be the input to both of the XOR gates.
You can see that the input to those XOR gates are:
XOR0 (first gate) = 1 ^ 0
XOR1 (middle gate) = 1 ^ 0

For the optimised version we only care for the last stage and all intermediate stage values can be thrown away or ignored.  The last stage XOR1 is equivalent to inputting the XOR0 gate result and the previous box, which we could have done from the start without going through all those stages.

[BrianHG]

Since it's partially relevant, error detection and correction, part 1 of 2, hamming codes:
This 3Blue1Brown visualizes the error detection and correction process.

[promach]

Thanks, @tru

I have understood the reasoning behind the optimized version of serial crc implementation.

Now, how do I make parallel implementation of both the "optimized" and "long division" versions of serial crc implementation ?

[tru]

Thanks, @tru

I have understood the reasoning behind the optimized version of serial crc implementation.

Now, how do I make parallel implementation of both the "optimized" and "long division" versions of serial crc implementation ?

http://outputlogic.com/?p=158
The parallel generation method described in the article works for both LFSR type.

If you take my C code from an earlier post and put in your chosen USB CRC5 LFSR version (in C of course) or modify the existing LFSR code, then the resulting two matrices will give you the parallel code for that particular version.

In fact the example in that article is the parallel code (with chosen input width of 4 bits parallel) of the optimised version (USB CRC5 LFSR):

Code: [Select]

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]Where Mout = CRC, Min = Previous CRC, Nin = Data

Above can be rewritten as:

Code: [Select]

CRC[0] = PrevCRC[1] ^ PrevCRC[4] ^ Data[0] ^ Data[3]
CRC[1] = PrevCRC[2] ^ Data[1]
CRC[2] = PrevCRC[1] ^ PrevCRC[3] ^ PrevCRC[4] ^ Data[0] ^ Data[2] ^ Data[3]
CRC[3] = PrevCRC[2] ^ PrevCRC[4] ^ Data[1] ^ Data[3]
CRC[4] = PrevCRC[0] ^ PrevCRC[3] ^ Data[2]
Perhaps if we look at a data input example using the LFSR optimised version:
If we input 4 bit data into the LFSR:
Initial seed value = 00000
Data = 1010
We get CRC = 00111
*Note with this particular LFSR the data bits needs to be fed starting from the highest bit order.

Try the same 4 bit input data with the above parallel code:
Data = 1010 (Data[3] = 1, Data[2] = 0, Data[1] = 1, Data[0] = 0)
Since we are at the start the PrevCRC is the initialisation value, let's use 00000 for easier calculation (but bear in mind that USB CRC5 uses 11111 as initial value).

Code: [Select]

CRC[0] = 0 ^ 0 ^ 0 ^ 1 = 1
CRC[1] = 0 ^ 1 = 1
CRC[2] = 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1
CRC[3] = 0 ^ 0 ^ 1 ^ 1 = 0
CRC[4] = 0 ^ 0 ^ 0 = 0As you can see it gives the same result of 00111.

[promach]

the resulting two matrices will give you the parallel code for that particular version.

I was asking the reasoning or purpose behind having two matrices.

[etherbladenet]

I believe this video will be of help - visualisation of CRC and Parallel CRC on FPGA: