Author Topic: CRC circuit  (Read 497 times)

0 Members and 1 Guest are viewing this topic.

Offline promach

  • Frequent Contributor
  • **
  • Posts: 330
  • Country: us
CRC circuit
« on: July 07, 2020, 12:25:31 pm »
What do you guys think about this CRC circuit (CRC-3 polynomial divisor is 4'b1011) ?

I am bit confused...

« Last Edit: July 07, 2020, 12:27:09 pm by promach »
 

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #1 on: July 07, 2020, 08:01:55 pm »
What do you find confusing here? Seems like a typical LFSR-based CRC. It takes a bit stream and produces a 3-bit CRC.
Alex
 

Online asmi

  • Super Contributor
  • ***
  • Posts: 1129
  • Country: ca
Re: CRC circuit
« Reply #2 on: July 07, 2020, 08:03:31 pm »
The code is wrong. Blocking assignments should not be used inside clocked blocks.
 
The following users thanked this post: promach

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #3 on: July 07, 2020, 08:04:26 pm »
Yes, I missed that part. All assignments inside always should be "<=" indeed.
Alex
 

Offline promach

  • Frequent Contributor
  • **
  • Posts: 330
  • Country: us
Re: CRC circuit
« Reply #4 on: July 10, 2020, 10:17:39 am »
Looking at input BITSTRB; // Current bit valid (Clock) ,

Can I say that if the input message is of 32-bits length long, the whole CRC-3 process will only finish after 32 clock cycles ?

The draft verilog code together with testbench is located at this link here
 

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #5 on: July 10, 2020, 04:34:50 pm »
Yes, this is the simplest serial implementation of the CRC, so it will take 32 clock cycles for calculate the CRC of the 32 bit word.

There are tools to generate Verilog code for parallel implementations based on your polynomial and input/output sizes.
Alex
 
The following users thanked this post: promach

Offline promach

  • Frequent Contributor
  • **
  • Posts: 330
  • Country: us
Re: CRC circuit
« Reply #6 on: July 11, 2020, 12:37:33 pm »
I found this parallel implementation of CRC, but I do not quite understand how the two matrices (Min = 0, Nin = 0) work ?

The parallel implementation verilog code could be generated using this online CRC code generation tool

Code: [Select]
//-----------------------------------------------------------------------------
// Copyright (C) 2009 OutputLogic.com
// This source file may be used and distributed without restriction
// provided that this copyright statement is not removed from the file
// and that any derivative work contains the original copyright notice
// and the associated disclaimer.
//
// THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS
// OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
// WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//-----------------------------------------------------------------------------
// CRC module for data[11:0] ,   crc[3:0]=1+x^1+x^3+x^4;
//-----------------------------------------------------------------------------
module crc(
  input [11:0] data_in,
  input crc_en,
  output [3:0] crc_out,
  input rst,
  input clk);

  reg [3:0] lfsr_q,lfsr_c;

  assign crc_out = lfsr_q;

  always @(*) begin
    lfsr_c[0] = lfsr_q[0] ^ data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[6] ^ data_in[7] ^ data_in[8];
    lfsr_c[1] = lfsr_q[1] ^ data_in[0] ^ data_in[3] ^ data_in[6] ^ data_in[9];
    lfsr_c[2] = lfsr_q[2] ^ data_in[1] ^ data_in[4] ^ data_in[7] ^ data_in[10];
    lfsr_c[3] = lfsr_q[3] ^ data_in[0] ^ data_in[1] ^ data_in[5] ^ data_in[6] ^ data_in[7] ^ data_in[11];

  end // always

  always @(posedge clk, posedge rst) begin
    if(rst) begin
      lfsr_q <= {4{1'b1}};
    end
    else begin
      lfsr_q <= crc_en ? lfsr_c : lfsr_q;
    end
  end // always
endmodule // crc
« Last Edit: July 11, 2020, 12:49:58 pm by promach »
 

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #7 on: July 11, 2020, 05:55:03 pm »
Here is my implementation of the idea described in that article. This is for USB polynomials. And this only generated the XOR block.
Code: [Select]
#!/usr/bin/env python

# Inspired by http://outputlogic.com/?p=158

# USB 5 : 0x105   - x^5 + x^2 + 1
# USB 16: 0x18005 - x^16 + x^15 + x^2 + 1

if 0:
  N = 8        # Data width
  M = 5        # CRC width
  P = 0x05     # USB CRC5: x^5 + x^2 + 1
else:
  N = 8        # Data width
  M = 16       # CRC width
  P = 0x8005   # USB CRC16: x^16 + x^15 + x^2 + 1

def crc_bit(crc, bit):
  if ((crc >> (M-1)) ^ bit) & 1:
    crc = (crc << 1) ^ P
  else:
    crc = (crc << 1)
  return crc & ((1 << M) - 1)

def crc_par(crc, word):
  crc_out = crc
  for i in range(N):
    crc_out = crc_bit(crc_out, (word >> i) & 1)
  return crc_out

out_data = [[] for x in range(M)]
out_crc = [[] for x in range(M)]

c = 0
for i in range(N):
  c = crc_par(0, 1 << i)

  for j in range(M):
    if (c & (1 << j)) and (i not in out_data[j]):
      out_data[j] += [i]

for i in range(M):
  c = crc_par(1 << i, 0)

  for j in range(M):
    if (c & (1 << j)) and (i not in out_crc[j]):
      out_crc[j] += [i]

for j in range(M):
  s = '  crc_out[%d] = ' % j
  s += ' ^ '.join(['c[%d]' % v for v in out_crc[j]])
  s += ' ^ '
  s += ' ^ '.join(['d[%d]' % v for v in out_data[j]])
  print s

Here is example of the use from the project:

Code: [Select]
reg  [15:0] crc16_tx_r;

always @(posedge clk_i) begin
  if (reset_i || ST_IDLE == state_r)
    crc16_tx_r <= 16'hffff;
  else if (ST_TX_DATA == state_r && pkt_tx_next_o)
    crc16_tx_r <= usb_crc16(crc16_tx_r, pkt_tx_data_i);
end

function [15:0] usb_crc16(input [15:0] crc, input [7:0] data);
begin
  usb_crc16[0] = crc[8] ^ crc[9] ^ crc[10] ^ crc[11] ^ crc[12] ^
      crc[13] ^ crc[14] ^ crc[15] ^ data[0] ^ data[1] ^ data[2] ^
      data[3] ^ data[4] ^ data[5] ^ data[6] ^ data[7];
..............................................
  usb_crc16[15] = crc[7] ^ crc[8] ^ crc[9] ^ crc[10] ^ crc[11] ^
      crc[12] ^ crc[13] ^ crc[14] ^ crc[15] ^ data[0] ^ data[1] ^
      data[2] ^ data[3] ^ data[4] ^ data[5] ^ data[6] ^ data[7];
end
endfunction
Alex
 
The following users thanked this post: ramon, promach

Offline promach

  • Frequent Contributor
  • **
  • Posts: 330
  • Country: us
Re: CRC circuit
« Reply #8 on: July 11, 2020, 07:04:09 pm »
Let me check your python script in a while.

Why this parallel CRC code simulation result does not match the result for serial implementation of CRC code ?
 

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #9 on: July 11, 2020, 07:19:02 pm »
Your first link requires a log in. But in any case, there are many things that can be different for different CRC implementations - input bit order, polynomial bit order, input and output inversion. All that is also a part of the specification for the CRC.

For example in case of my code, the final CRC value that actually goes in the packet is inverted and bit-reversed - "~reverse(crc16_tx_r)".
Alex
 

Offline promach

  • Frequent Contributor
  • **
  • Posts: 330
  • Country: us
Re: CRC circuit
« Reply #10 on: July 12, 2020, 01:39:27 am »
Quote
Your first link requires a log in.

Here is the code and testbench inside the first link. But the simulation result does not match the result for serial implementation of CRC code

Code: [Select]
// Credit : http://outputlogic.com/?page_id=321
//-----------------------------------------------------------------------------
// Copyright (C) 2009 OutputLogic.com
// This source file may be used and distributed without restriction
// provided that this copyright statement is not removed from the file
// and that any derivative work contains the original copyright notice
// and the associated disclaimer.
//
// THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS
// OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
// WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//-----------------------------------------------------------------------------
// CRC module for data[11:0] ,   crc[2:0]=1+x^1+x^3;
//-----------------------------------------------------------------------------
module crc(
  input [11:0] data_in,
  input crc_en,
  output [2:0] crc_out,
  input reset,
  input clk);

  reg [2:0] lfsr_q,lfsr_c;

  assign crc_out = lfsr_q;

  always @(*) begin
    lfsr_c[0] = lfsr_q[0] ^ lfsr_q[1] ^ lfsr_q[2] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[4] ^ data_in[7] ^ data_in[9] ^ data_in[10] ^ data_in[11];
    lfsr_c[1] = lfsr_q[0] ^ data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[5] ^ data_in[7] ^ data_in[8] ^ data_in[9];
    lfsr_c[2] = lfsr_q[0] ^ lfsr_q[1] ^ data_in[1] ^ data_in[2] ^ data_in[3] ^ data_in[6] ^ data_in[8] ^ data_in[9] ^ data_in[10];

  end // always

  always @(posedge clk) begin
    if(reset) begin
      lfsr_q <= {3{1'b1}};
    end
    else begin
      lfsr_q <= crc_en ? lfsr_c : lfsr_q;
    end
  end // always
endmodule // crc

Code: [Select]
module test_crc();
 
  reg clk;
  reg reset;
  reg crc_en;
 
  reg [11:0] data_in;
 
  wire [2:0] crc_out; // result
 
  initial
  begin
    // Dump waves
    $dumpfile("test_crc.vcd");
    $dumpvars(0, test_crc);
   
    clk = 0;
    reset = 0;
   
    crc_en = 1;
    data_in = 'h1C0;
   
    @(posedge clk);
   
    reset = 1;
   
    @(posedge clk);
    @(posedge clk);
   
    reset = 0;
   
    #20 $finish;
   
  end
 
  always #5 clk = !clk;
 
  crc crc3(.data_in(data_in), .crc_en(crc_en), .clk(clk), .reset(reset), .crc_out(crc_out));
 
endmodule
 

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #11 on: July 12, 2020, 01:55:29 am »
I don't have time or energy to study different implementations. The first clear difference that is obvious immediately, if default value for the CRC. In one case it is 3'b000, and in the other case 3'b111.

Again, CRC-3 is not fixed thing. There are too many options for input and output parameters (inversion, bit order). You either need to know what specific configuration you want, or if you don't care, just take one and stick with it.
Alex
 
The following users thanked this post: promach

Offline promach

  • Frequent Contributor
  • **
  • Posts: 330
  • Country: us
Re: CRC circuit
« Reply #12 on: July 12, 2020, 03:01:57 pm »
Your suggestion about the reset signal solved the above problem.

See the updated verilog code and testbench below.

However, I am still not sure how the two matrices (Min = 0, Nin = 0) work as described in http://outputlogic.com/?p=158

Code: [Select]
// Credit : http://outputlogic.com/?page_id=321
//-----------------------------------------------------------------------------
// Copyright (C) 2009 OutputLogic.com
// This source file may be used and distributed without restriction
// provided that this copyright statement is not removed from the file
// and that any derivative work contains the original copyright notice
// and the associated disclaimer.
//
// THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS
// OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
// WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//-----------------------------------------------------------------------------
// CRC module for data[11:0] ,   crc[2:0]=1+x^1+x^3;
//-----------------------------------------------------------------------------
module crc(
  input [11:0] data_in,
  //input crc_en,
  output [2:0] crc_out,
  input reset,
  input clk);

  reg [2:0] lfsr_q,lfsr_c;

  assign crc_out = lfsr_q;

  always @(*) begin
    lfsr_c[0] = data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[4] ^ data_in[7] ^ data_in[9] ^ data_in[10] ^ data_in[11];
    lfsr_c[1] = data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[5] ^ data_in[7] ^ data_in[8] ^ data_in[9];
    lfsr_c[2] = data_in[1] ^ data_in[2] ^ data_in[3] ^ data_in[6] ^ data_in[8] ^ data_in[9] ^ data_in[10];

  end // always

  always @(posedge clk) begin
    if(reset) begin
      lfsr_q <= {3{1'b0}};
    end
    else begin
      lfsr_q <= lfsr_c;
    end
  end // always
endmodule // crc

Code: [Select]
module test_crc();
 
  reg clk;
  reg reset;
  //reg crc_en;
 
  reg [11:0] data_in;
 
  wire [2:0] crc_out; // result
 
  initial
  begin
    // Dump waves
    $dumpfile("test_crc.vcd");
    $dumpvars(0, test_crc);
   
    clk = 0;
    reset = 0;
   
    //crc_en = 1;
    data_in = 'h1C3;
   
    @(posedge clk);
   
    reset = 1;
   
    @(posedge clk);
    @(posedge clk);
   
    reset = 0;
   
    @(posedge clk);
   
    //crc_en = 0;
   
    @(posedge clk);
    data_in = 'h1C2;
   
    @(posedge clk);
   
    //crc_en = 1;
    data_in = 'h1C1;
   
    @(posedge clk);
    data_in = 'h1C0;
   
    @(posedge clk);
    //crc_en = 0;
   
    #30 $finish;
   
  end
 
  always #5 clk = !clk;
 
  crc crc3(.data_in(data_in), /*.crc_en(crc_en),*/ .clk(clk), .reset(reset), .crc_out(crc_out));
 
endmodule

 

Offline ataradov

  • Super Contributor
  • ***
  • Posts: 6590
  • Country: us
    • Personal site
Re: CRC circuit
« Reply #13 on: July 12, 2020, 06:36:38 pm »
I'm not sure I understand the question. There is detailed description of how to generate those matrices. They are generated from the serial version and contain partial results. Having that lets you easily generate parallel version.
Alex
 

Offline langwadt

  • Super Contributor
  • ***
  • Posts: 1938
  • Country: dk
Re: CRC circuit
« Reply #14 on: July 12, 2020, 06:54:50 pm »
The code is wrong. Blocking assignments should not be used inside clocked blocks.

maybe you shouldn't but you can
 

Offline matrixofdynamism

  • Regular Contributor
  • *
  • Posts: 53
Re: CRC circuit
« Reply #15 on: July 27, 2020, 12:07:55 am »
Anyone that wants to know anything about CRC, please do check out this page:

http://checksumcrc.blogspot.com/
 

Offline n5al

  • Contributor
  • Posts: 6
  • Country: mx
Re: CRC circuit
« Reply #16 on: Today at 08:24:06 am »
BTW,
There is a neat, well-written article, by Greg Morse, in the September 1986 issue of Byte magazine, that discusses how to do CRC calculations using parallel methods.  The article is focused on creating faster software implementations, but the basic techniques should apply to FPGA designs, as well.

link to magazine article: https://archive.org/details/byte-magazine-1986-09/page/n124/mode/1up
 
The following users thanked this post: promach


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf