CRC circuit question

[promach]

For N=4 and M=5 we want the results from the following calculations:
Mout = CRC_parallel("1000", "00000")
Mout = CRC_parallel("0100", "00000")
Mout = CRC_parallel("0010", "00000")
Mout = CRC_parallel("0001", "00000")
Mout = CRC_parallel("0000", "10000")
Mout = CRC_parallel("0000", "01000")
Mout = CRC_parallel("0000", "00100")
Mout = CRC_parallel("0000", "00010")
Mout = CRC_parallel("0000", "00001")

The results from having a bit set in Nin go to matrix 1. One Mout result per row.
The results from having a bit set in Min go to matrix 2. One Mout result per row.

in the pdf , step 2 mentioned that I need to run crc_serial() code for N times <-- I understand this.

However, in step 4, why The values are one-hot encoded—that is, each of the N_IN values has only one bit set. ?

 

[std_match]

in the pdf , step 2 mentioned that I need to run crc_serial() code for N times <-- I understand this.

However, in step 4, why The values are one-hot encoded—that is, each of the N_IN values has only one bit set. ?

The one-hot encoding is just the simplest case, but it isn't necessary to generate table 1 + 2 and the equations.
What you need is only the correlation from a flipped input bit to flipped output bits.
When you flip only one Nin/Min input bit, the same output bits will always flip, regardless of the fixed state of the other Nin/Min bits.
Since the output is all zeros when the input is all zeros, the one-hot input encoding is the simplest case. You directly know that an output bit = '1' is a flipped output bit.

 

[promach]

In step 3, what does it exactly mean by Matrix H1 describes M_OUT(next CRC state) as a function of N_IN(input data) when M_IN= 0 ?

 

[std_match]

In step 3, what does it exactly mean by Matrix H1 describes M_OUT(next CRC state) as a function of N_IN(input data) when M_IN= 0 ?

It means that the matrix shows the relations between flipped Nin bits and flipped output/Mout bits (= which Nin terms to include in the parallel equations). Min = 0 only means that no Min bit is flipped, that happens for the other table/matrix.

 

[promach]

okay, could you show me how to obtain the first row (Nin[0]) of table 1 (Min = 0) ?

How do you exactly flip Nin[0] to obtain first row ?

--- Updated Sep 10, 2020 ---

 

[std_match]

okay, could you show me how to obtain the first row (Nin[0]) of table 1 (Min = 0) ?

How do you exactly flip Nin[0] to obtain first row ?

You clear/reset everything (=the shift register= Min) and execute the serial implementation N times with "0001" as the input data sequence (= Nin[3:0]).
The bits in the shift register (= Mout) are the data for the first row in table 1.

 

[promach]

okay, thanks. I know exactly how to reproduce table 1

What about first row (Min[0]) of table 2 (Nin = 0) ?

 

[std_match]

okay, thanks. I know exactly how to reproduce table 1

What about first row (Min[0]) of table 2 (Nin = 0) ?

In the simulator, you initiate the shift register contents (Min) to "00001" and then execute the serial implementation N times with "0000" as the input data sequence (Nin=0)

 

[promach]

okay, now I have reproduced table 2 using your advice above.

However, why is table 2 (Nin =0) needed at all to produce parallel CRC equation ?

 

[std_match]

okay, now I have reproduced table 2 using your advice above.

However, why is table 2 (Nin =0) needed at all to produce parallel CRC equation ?

The CRC calculation depends both on previous bits (used to calculate Min) and new bits (Nin).
So both Min and Nin terms are needed in the equations. Table 1 gives the Nin terms and table 2 gives the Min terms.

 

[promach]

What does it exactly mean by each set bit j in column i ?

 

[std_match]

What does it exactly mean by each set bit j in column i ?

Each row in table 1 and table 2 corresponds to an Nin/Min "input" bit. Each column corresponds to an Mout "output" bit.
A '1' means that the Nin/Min term must be included in the parallel equation for the output bit corresponding to the column.
A '0' means that the Nin/Min term must not be included in the equation.

By "flipping" one input bit at a time you calculate the rows in the matrices/tables.
A complete column (in both tables) defines which Nin/Min terms must be included in the equation for one Mout output bit.

 

[promach]

Maybe if you could show how to derive the first parallel equation M_out[0] from table 1 and table 2, then it is easier to understand ?

M_out[0] = M_in[1] ^ M_in[4] ^ M_in[0] ^ M_in[3]

 

[std_match]

Maybe if you could show how to derive the first parallel equation M_out[0] from table 1 and table 2, then it is easier to understand ?

M_out[0] = M_in[1] ^ M_in[4] ^ M_in[0] ^ M_in[3]

I now see that there is a "typo" in the pdf you have linked ( http://outputlogic.com/my-stuff/circuit-cellar-january-2010-crc.pdf ).
The line you show is incorrect. It should be:

M_out[0] = M_in[1] ^ M_in[4] ^ N_in[0] ^ N_in[3]

This may have confused you.
They have it correct in the Verilog code in listing 4.

You get the equation for M_out[0] by looking at the corresponding column in table 1 and 2.
In table 1, column M_out[0], you have '1' in the rows for N_in[0] and N_in[3], which means they are included in the equation.
In table 2, column M_out[0], you have '1' in the rows for M_in[1] and M_in[4], which means they are included in the equation.

 

[promach]

ok, but why XOR all four bits together to obtain M_out[0] ?

 

[std_match]

ok, but why XOR all four bits together to obtain M_out[0] ?

CRC calculation in 100% XOR operations.
In the serial implementation they happen after each other.
In the parallel implementation you do all of them in one clock cycle.
When the bits move around in the serial implementation, it is possible that one input bit is "involved" more than once for generating an output bit.
Input signals that have been used an even number of times (zero is even) have no effect, so they don't appear in the parallel equation.
Input signals that have been used an odd number of times have the same effect as being XOR-ed once, so they appear in the parallel equation.