Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics 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.

CRC circuit question

Status
Not open for further replies.

promach

Advanced Member level 4
Joined
Feb 22, 2016
Messages
1,199
Helped
2
Reputation
4
Reaction score
5
Trophy points
1,318
Activity points
11,636
How to arrive at this CRC circuit (CRC-3 polynomial divisor is 4'b1011) ?


I am bit confused...

6ZdxnNE.png
 

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
 

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
 

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:

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
 

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
 

what is the purpose of the CRC?

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

my input message is of 12-bits long.

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

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

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
 

Step 4:
Min=0 means that the shift register for the serial CRC starts with all zeros, and then one N word is processed (shifted in).
The resulting shift register bits are Mout.
The N words used are all possible values with only one bit set ("one-hot encoded").

Step 5+6 (first matrix)
The row Nin[0] shows the shift register bits (Mout) after processing the N word with only the lowest bit set to 1.
The row Nin[1] shows the shift register bits (Mout) after processing the N word with only the second lowest bit set to 1.
etc.

Step 7 is similar to step 4 but Nin=0 means that the N words processed are all zero words (all bits are 0).
Instead the initial values in the shift register (Min) before processing a zero N word are all possible M words with one bit set ("one-hot encoded").

Step 8+9 (second matrix)
The row Min[0] shows the shift register bits (Mout) after processing a zero N word when the shift register started (Min) with only the lowest bit set to 1.
The row Min[1] shows the shift register bits (Mout) after processing a zero N word when the shift register started with only the second lowest bit set to 1.
etc.


A common confusion about CRC calculations is the bit order. From a mathematical standpoint, the first input bit to the "simple" serial CRC circuit is always the highest bit in the input message. The shift register bit that is XOR-ed with the input bit is the highest bit in the shift register.
The bit order used by data on the serial line and the output CRC can be specified the other way around, and this is why the CRC generators have the option to reverse the bit order on the input and output data. The order of the polynomial bits is also affected by the confusion.
 

    promach

    Points: 2
    Helpful Answer Positive Rating
I do not understand steps 5 and 6.

For first row, MOUT = 'b00101 which probably corresponds to the USB CRC5 polynomial G(x) = x5+ x2+ 1

however, how to compute the second row, MOUT = 'b01010 ?
 

I do not understand steps 5 and 6.

For first row, MOUT = 'b00101 which probably corresponds to the USB CRC5 polynomial G(x) = x5+ x2+ 1

however, how to compute the second row, MOUT = 'b01010 ?
For all rows, the shift register is first initialized to all zeros.

For the first row (Nin[0]), the word N="00001" is shifted in. Only the last (lowest) bit is set, which means that the polynomial bits are applied (XORed) in the last clock cycle of the CRC calculation. This means that the resulting shift register (Mout) is identical to the polynomial.

For the second row (Nin[1]), the word "00010" is shifted in. The second last bit is set. This means that there will be one more shift after the polynomial bits are applied. The result is the polynomial shifted left one step.

For the row Nin[3], the word "01000" is shifted in, This means that 3 shifts are done after the polynomial bits are applied. The highest polynomial bit will reach the higest bit in the shift register and be XORed with a zero in the input word. This means that the polynomial bits will be applied again. The result is the polynomial bits "00101" XORed with itself shifted left 3 bits ("01000"), and the result is "01101".

The whole first matrix can be constructed manually. The first row is the polynomial "00101", created by shifting in a one.
To get the next row, shift the row above left one step, and then XOR with "00101" if Mout[4] was '1' before the shift. This is exactly what the serial CRC implementation does in one clock cycle when shifting in a zero.
 

    promach

    Points: 2
    Helpful Answer Positive Rating
For the second row (Nin[1]), the word "00010" is shifted in. The second last bit is set. This means that there will be one more shift after the polynomial bits are applied. The result is the polynomial shifted left one step.

Wait, for second row, is the operation defined as "polynomial xor 'b00010" ?
 

Wait, for second row, is the operation defined as "polynomial xor 'b00010" ?
No, the first matrix is what you get in each clock cycle in the serial implementation if you start with all zeros in the shift register and then shift in a single '1' on the serial input, and then only zeros. The first row will be the polynomial (without the highest bit), and all other rows will be the previous row shifted left one bit and also XORed with the polynomial if Mout[4] was '1' before the shift.

The second row is just the polynomial (the result from the previous clock cycle) shifted left one bit. There is no XOR with the polynomial to create the second row since Mout[4] is '0' before the shift.
 

    promach

    Points: 2
    Helpful Answer Positive Rating
For a deeper understanding, I think you should look at the mathematical definition of the CRC, and how it can be done manually as a "long division". The only difference from a normal long division is that there is no carry between bits. It is an bitwise XOR operation instead of a subtraction with carry/borrow. Bitwise XOR is identical to addition/subtraction without carry/borrow.

For creating an M-bit CRC from an N-bit message with the polynomial P:
(P always has M+1 bits)

The first bit of the message is the highest bit.
Append M zero bits to the lower end of the message.
The CRC is the remainder when "dividing" (XOR, no carry/borrow) the message with appended zeros by the polynomial.

To create the fourth row in the matrix, the N-bit message is "1000" (N=4).
CRC size M = 5
Polynomial P = "100101" (M+1 bits)

The message with M appended zeros = "100000000"
Divide by P = "100101"

Long division with no borrow (same as XOR):
(we ignore the quotient and only keep track of the remainder, which is the CRC)

Code:
100000000
100101 subtract
=========
 001010 (The 5 highest bits are the first row in the matrix)
 100101 no subtraction
=========
  010100 (The 5 highest bits are the second row in the matrix)
  100101 no subtraction
=========
   101000 (The 5 highest bits are the third row in the matrix)
   100101 subtract
=========
    01101 (No more dividend bits, this is the remainder (CRC) for the message "1000" and the fourth row in the matrix)
We get all the matrix rows in one calculation, but each row really represents a different message.
If you do the above CRC calculation for the following messages, you will discover why you can get all of them in one calculation:
0001 (the remainder is the first row in the matrix)
0010 (the remainder is the second row in the matrix)
0100 (the remainder is the third row in the matrix)
1000 (this is the example calculation above, the remainder is the fourth row in the matrix)
 

    promach

    Points: 2
    Helpful Answer Positive Rating
Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top