CRC circuit question

Status
Not open for further replies.
What does first input bit affected the state as if it were m*x^8 vs just m exactly mean ?
 

a 1 bit message doesn't have a crc of 1 or 0 unless the polynomial is x^8 + 1.

in context, a serial version doesn't need to shift inputs 8 times before "interesting" things happen.

in more context, the crc is defined as message * x^crclen, (sometimes with a prefix before the message but that isn't relevant.)
 
Last edited:

std_match said:
I see absolutely no reason to use anything else than the "standard" serial CRC implementation, and the parallel version of it.
Click to expand...
I take this back a little ...
For checking the CRC of a received message, the long division implementation can be better.
You have 2 alternatives:

1. Calculate the received message CRC (without the received CRC) using the optimized implementation and compare with the received CRC.

2. Process the received message including the CRC with the "long division" implementation. If the CRC is correct, the result will be zero.
In this case you don't need to input "extra" appended zeros. The received CRC is used instead of the zeros.

Both alternatives should use about the same in clock cycles, but no 2 can maybe save some logic.
 

    P

    promach

    Points: 2
    Helpful Answer Positive Rating
For checking the CRC of a received message, the long division implementation can be better.
Click to expand...

What ?
 

Until now, we have discussed how to generate the CRC.
If you receive a message that already has a CRC at the end, there are two ways to check it.

1. Generate the CRC as in the transmitter and compare with the received CRC.

2. Divide the complete message, including the CRC, with the polynomial and check the remainder. This is not the same operation as calculating the CRC, there are no appended zeros. The received CRC is used instead of appended zeros. If the remainder is zero, the CRC was correct. You can't do this with the "optimized" serial/parallel CRC generator, since it always assumes M appended zeros after the input message/bits, which is what you want for generating the CRC. The "long division" implementation is the way to go for this type of CRC check.


Do "simulations" with pen and paper! (or with an RTL simulator)
 
Last edited:


What do you mean by the quoted message above ?


and yes, both the un-optimized and optimized versions use the same clock cycles (which again depends on bitwidth of the input data).

Code: 
module serial1(crc, data);

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

input [4:0] crc;
input data;

always @(*)
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

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

endmodule


Code: 
module serial2 (
    input clock,
    input enable,
    input reset,

    input data,
    input input_strobe,

    output [7:0] crc
);

reg [7:0] C;
genvar i;

generate
for (i = 0; i < 8; i=i+1) begin: reverse
    assign crc[i] = ~C[7-i];
end
endgenerate


always @(posedge clock) begin
    if (reset) begin
        C <= 8'hff;
    end else if (enable) begin
        if (input_strobe) begin
            C[0] <= data ^ C[7];
            C[1] <= data ^ C[7] ^ C[0];
            C[2] <= data ^ C[7] ^ C[1];
            C[7:3] <= C[6:2];
        end
    end
end

endmodule
--- Updated ---

From Figure 1 of http://outputlogic.com/my-stuff/circuit-cellar-january-2010-crc.pdf , I understood how to construct the un-optimized version of serial CRC implementation.

But I am not so sure about the optimized, serial CRC version at http://jhshi.me/2016/10/18/calculating-crc-for-ht-sig-in-80211n-preamble/index.html#.X0oUGJX-tD8
 
Last edited:

promach, all code and both links in your last post (#86) are for the "optimized" CRC generation, where you don't need to input M zeros after the message. The schematic diagrams in your links may confuse you because the layout and the polynomial are different, but both are the same type (the "optimized" CRC generator).

The un-optimized I have linked to earlier is implemented exactly as the CRC definition, a long division where you must append M zeros to the input message before dividing by the polynomial. This type is a little more effective for CRC checking, where you use the received CRC instead of the appended zeros.

To see if a serial CRC generator is the optimized version or not, check how many clock cycles it will take for an input bit to influence the subtraction/xor with the polynomial. This can happen immediately in the optimized version, but it takes M clock cycles in the "long division" implementation.
--- Updated ---

This is the (optimized) CRC5 implementationversion from your link:



This is a modified version, the "long division" type, where you must append 5 zeros to the input message when generating the CRC:


Can you see the difference?
 
Last edited:

    P

    promach

    Points: 2
    Helpful Answer Positive Rating
The schematic diagrams in your links may confuse you because the layout and the polynomial are different, but both are the same type (the "optimized" CRC generator).
Click to expand...

Wait, how does the change in input of the XOR gate in the bottom version leads to "long division" type ?
 

The long division type is the easy one to understand. The polynomial XOR operations are controlled by the highest bit in the shift register.

The "optimized" serial CRC generator is not obvious, but it will create the same signal for controlling the polynomial XOR, but M=8 clock cycles earlier than the long division type. It isn't easy to explain the operation, but it is like a long division type where the input bit is always '0', and this is compensated for by XOR with the actual data bit when the polynomial-XOR-controlling signal is created.

The layout of the schematic diagram can help or confuse. Do simulations!

The original optimized for polynomial G(x) = x^8 + x^2 + x + 1 :


The long division type, needs 8 zeros after the input message/bits:
 

    P

    promach

    Points: 2
    Helpful Answer Positive Rating
For the optimized version, see the following where the simulation result does not match result from online CRC calculator.



crc_serial_optimized.v

Code: 
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: 
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;
   //new_data = 0;
   data = 0;
  
   @(posedge clk);
   @(posedge clk);

   reset = 0;

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

   //data = 4'b1011;
   //new_data = 1;   
   data = 1'b1;

   @(posedge clk);
   //new_data = 0;
   data = 1'b1;

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

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

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

   // data = 4'b1010;
   //new_data = 1;
   data = 1'b0;

   @(posedge clk);
   //new_data = 0;
   data = 1'b1;

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

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

   #50 $finish;
end

always  #5 clk = !clk;

endmodule
 

I am not a verilog person, but I think you have a race condition that will be corrected if you change to nonblocking assignments in the test bench.
 

race condition ?

crc[index] acts as shift registers.
 

You have a simulation problem.
Is it easy to manually calculate the expected changes to crc[0]. In your simulation crc[0] is wrong already when crc[4:0] = 0x1b
It should be 0x1e.
I guess it is the "race condition" problem when simulating verilog code. The problem doesn't exist in VHDL.
I simulated your code with Questasim on Edaplayground without any changes, and also with the TB assignments changed to nonblocking:





Both are the same, but different from your simulation. Maybe your simulator will give a different (and correct) result if you use the modified code with nonblocking assignments. I am not a verilog person, so I am not the one to explain what effect the change from blocking to nonblocking assignments should have, or if there is a much better way to fix your simulation error.

The modified testbench code:

Code: 
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;
   //new_data = 0;
   data <= 0;
  
   @(posedge clk);
   @(posedge clk);

   reset <= 0;

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

   //data = 4'b1011;
   //new_data = 1;   
   data <= 1'b1;

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

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

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

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

   // data = 4'b1010;
   //new_data = 1;
   data <= 1'b0;

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

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

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

   #50 $finish;
end

always  #5 clk = !clk;

endmodule
 

Ok, I am now getting the same simulation result as yours using your modified testbench (non-blocking).

However, the crc result is only correct for the first data (0xD), but not for the second data (0x5)
Why ?
 
Last edited:

From a mathematical view, the serial input data is with the most significant bit first, so the two first 4-bit words you give it is 0xd and 0xa.
Also, please show which online CRC calculator you use, and all the settings and input data for getting the "correct" result.
 

If you want to calculate intermediate CRC values, the input message includes all previous words.

The simulation and the online calculator agree.
Input message = 0xd gives CRC=0x1c
Input message = 0xda gives CRC=0x14
Input message = 0xdaf gives CRC=0x11
 

    P

    promach

    Points: 2
    Helpful Answer Positive Rating
As for the unoptimized OR the "long division" version, I am not getting any correct simulation output.



crc_serial_long_division.v

Code: 
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: 
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);
   // 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;


   //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;

   #100 $finish;
end

always  #5 clk = !clk;

endmodule
 

The appended zeros must come after the message bits, not before ...
 

    P

    promach

    Points: 2
    Helpful Answer Positive Rating
Ok, for those interested in verilog implementation of serial CRC (both optimized and long-division versions), you can find attached the verilog source code together with their corresponding testbench inside the attached zip file.

However, what I do not understand is why the verilog circuit for the long-division version needs to append 5 zeroes ?
 

Attachments

  • crc_serial.zip
    1.9 KB · Views: 103

Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…