Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

CRC circuit question

wwfeldman

Advanced Member level 2
Joined
Jan 25, 2019
Messages
693
Helped
169
Reputation
338
Reaction score
167
Trophy points
43
Activity points
5,023
i'm not sure i follow - the diagram looks opposite the description
that is, the description "flows" from left to right, but the schematic "flows" from right to left

this is how i read your schematic
S is the input to the flip flop
Q is the output, and the triangle is the clock input
the data input goes into the leftmost XOR
as there are only three FF, this is a 3 bit LFSR, so the 4'b1011 isn't clear


since it looks like a 3 bit device, the equation (feedback polynomial) is
x^3 + x^2 + 1, which looks like your 1011, with the order increasing (1 + x^2 +x^3)
the 0 is the missing x term
look at the section in the wiki article on "Some polynomials for maximal LFSRs"

your device looks like a Galois LFSR
 

promach

Advanced Member level 3
Joined
Feb 22, 2016
Messages
870
Helped
1
Reputation
2
Reaction score
2
Trophy points
18
Activity points
8,486
the description "flows" from left to right, but the schematic "flows" from right to left
I do not quite understand your explanation about this in your previous post just above
 

wwfeldman

Advanced Member level 2
Joined
Jan 25, 2019
Messages
693
Helped
169
Reputation
338
Reaction score
167
Trophy points
43
Activity points
5,023
your first post says:
"the input bits are shifted into the very left xor gate. the MSB (the leftmost bit) of each byte is shifted in first. "
"Each flip flop represents a single CRC output bit. The leftmost flip flop is the MSB or the CRC."
comparing this to the schematic:
the input bits come in the little vertical line near the "1" in the leftmost flip flop.

the output of that gate then goes to the far right flip flop as an input. it is shifted in first, and so is the MSB
but it is on the right in the drawing, not the left.
so when you take he output, the Q from the rightmost flip flop is the MSB
so there is some confusion about left and right.

is your question answered?
 
Last edited by a moderator:

promach

Advanced Member level 3
Joined
Feb 22, 2016
Messages
870
Helped
1
Reputation
2
Reaction score
2
Trophy points
18
Activity points
8,486
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 here at this link
 

wwfeldman

Advanced Member level 2
Joined
Jan 25, 2019
Messages
693
Helped
169
Reputation
338
Reaction score
167
Trophy points
43
Activity points
5,023
as far as i know, you can start and stop the process where you like
as long as you do it the same way each time you look at the same signal

you have a 3 bit CRC with at most 8 states
it is possible, since your data stream is 32 bits long, that two different data streams can yield the same CRC
I suggest you use a CRC with at least 5 bits, preferably more, to avoid that specific issue
 

wwfeldman

Advanced Member level 2
Joined
Jan 25, 2019
Messages
693
Helped
169
Reputation
338
Reaction score
167
Trophy points
43
Activity points
5,023
what is the purpose of the CRC?

and i may have been wrong about the number of bits you need
 

promach

Advanced Member level 3
Joined
Feb 22, 2016
Messages
870
Helped
1
Reputation
2
Reaction score
2
Trophy points
18
Activity points
8,486
my input message is of 12-bits long.

is CRC-3 divisor of 4'b1011 enough to avoid crc collision issue ?
 

wwfeldman

Advanced Member level 2
Joined
Jan 25, 2019
Messages
693
Helped
169
Reputation
338
Reaction score
167
Trophy points
43
Activity points
5,023
a 12 bit message has 2^12 or 4069 different possible data streams
a 3 bit CRC has at most 8 possible states
a 4 bit CRC has at most 16 possible states

if you squeeze 4096 possible data streams into 8 or 16 states, there must be duplicates
on average, there will be 512 possible data streams for each state of the 3 bit CRC
and 256 possible data streams for the 4 bit CRC
 

    promach

    points: 2
    Helpful Answer Positive Rating

promach

Advanced Member level 3
Joined
Feb 22, 2016
Messages
870
Helped
1
Reputation
2
Reaction score
2
Trophy points
18
Activity points
8,486
The above code implementation is for serial input.

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:
//-----------------------------------------------------------------------------
// 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 edited:

promach

Advanced Member level 3
Joined
Feb 22, 2016
Messages
870
Helped
1
Reputation
2
Reaction score
2
Trophy points
18
Activity points
8,486
The following code is for CRC-3 divisor of 4'b1011

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

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

Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top