# CRC circuit question

#### promach

How to arrive at this CRC circuit (CRC-3 polynomial divisor is 4'b1011) ?

I am bit confused...

#### wwfeldman

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

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

the description "flows" from left to right, but the schematic "flows" from right to left

#### wwfeldman

"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.

Last edited by a moderator:

#### promach

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

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

what is the purpose of the CRC?

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

#### promach

my input message is of 12-bits long.

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

#### wwfeldman

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

#### promach

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

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