CRC circuit question

[std_match]

Wait, why is it crc[4] ^ data ?

This expression corresponds to the leftmost bit in the intermediate values in the long division (if '1' subtract the polynomial).
crc[4] contains a bit that has already been subjected to the polynomial subtractions, before the corresponding data bit was available.
This XOR operation compensates for that.

The long division shifts in the data bits and then "subtracts" the polynomial.
The serial CRC does the polynomial subtractions from zeros, and later "adds" the real input bits when they arrive. This "addition" is the crc[4] ^ data.

(with no carry/borrow, xor/add/subtract are all the same operation)

 

[promach]

What about crc5_serial[2] = crc[1] ^ crc[4] ^ data; ?

 

[std_match]

What about crc5_serial[2] = crc[1] ^ crc[4] ^ data; ?

If (crc[4] ^ data) = '1' then apply the x^2 term from the polynomial when crc[1] is shifted into crc5_serial[2] ( invert crc[1] )

 

[promach]

but what I do not understand is why 'data' and 'crc[4]' appear only inside the logic for 'crc5_serial[0]' and 'crc5_serial[2] ' ?

 

[std_match]

but what I do not understand is why 'data' and 'crc[4]' appear only inside the logic for 'crc5_serial[0]' and 'crc5_serial[2] ' ?

The condition for applying the polynomial is (crc[4] ^ data).
The polynomial has an x^2 term and an x^0 term.
So, (crc[4] ^ data) appears in the equations for crc5_serial[2] and crc5_serial[0].
The other bits are not affected by the polynomial.

 

[promach]

The condition for applying the polynomial is (crc[4] ^ data). ???

 

[std_match]

The condition for applying the polynomial is (crc[4] ^ data). ???

The bits you see in the shift register of the "standard" serial CRC are not the intermediate results you see when you do the long divison.
For the long division, you look at the highest bit of the intermediate result to decide if the polynomial shall be subtracted.
That bit is identical to what you get with the expression (crc[4] ^ data) in the serial CRC.

The intermediate results in the long division are input bits that have been subjected to earlier polynomial subtractions.

The shift register bits in the serial CRC are zero bits that have been subjected to the same earlier polynomial subtractions.
When you XOR (add) the highest shift register bit with the input bit, you get the same bit as the highest bit in the long division, the one that decides if the polynomial should be subtracted. So, (crc[4] ^ data) is the condition for subtracting the polynomial.

You should do some CRC calculations manually with the long division method and the serial CRC method to see what is going on.
The internal bits are different but the end result is the same.

In Wikipedia, there is a serial CRC implementation that works exactly like the long division:

http://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks

I found a "better" hand-drawn picture of that implementation:

http://furycomputing.wordpress.com/...at-calculates-crc-using-a-parallel-equations/

That is different from the Verilog code in your post #58, which I call the "standard" serial CRC implementation.
Here is a "standard" serial CRC implementation for the same polynomial as in the Wikipedia implementation above:

Calculating CRC for HT-SIG in 802.11n Preamble

The HT-SIG field of 802.11n PLCP preamble contains a 8-bit CRC for the receiver to validate the sanity of the header. Here is how to calculate it.

jhshi.me

Both implementations above use the same polynomial.
The drawback with the top one (Wikipedia) is that nothing happens for the first M=8 clock cycles, and you must append M zeros after the input message.

The bottom one is the "standard" serial CRC implementation which starts immediately and doesn't need appended input zeros.

As I mentioned earlier, it isn't obvious that both implementations give the same end result. The bits that move in the shift registers are different.

Both can be converted to parallel versions, but if you convert the Wikipedia one, the parallel version also needs M appended input zeros.
That is really bad if CRC size M isn't a multiple of the input "chunk" size N. The parallel USB CRC5 in your post #13 is a good example. It processes N=4 input bits at a time to produce a M=5 bit CRC. A parallel version of the long division would have trouble appending 5 zeros the the input data (unless the input message size is one bit less than a multiple of 4).

I see absolutely no reason to use anything else than the "standard" serial CRC implementation, and the parallel version of it.

 

[promach]

The drawback with the top one (Wikipedia) is that nothing happens for the first M=8 clock cycles, and you must append M zeros after the input message.

The bottom one is the "standard" serial CRC implementation which starts immediately and doesn't need appended input zeros.

Wait, I am really confused about your reasoning/explanation about zero appending for BOTH picture screenshots of serial implementation ?

 

[std_match]

Wait, I am really confused about your reasoning/explanation about zero appending for BOTH picture screenshots of serial implementation ?

No, only the top one needs appended input zeros, but it will need it also when it is converted to a parallel version.

 

[promach]

what I do not understand is why the top version needs to append input zeroes, and why the bottom version does not need to append input zeroes ?

 

[std_match]

what I do not understand is why the top version needs to append input zeroes, and why the bottom version does not need to append input zeroes ?

The top one is implemented exactly as the definition of the CRC (a "Long division"), which specifies that M zero bits must be appended to the input message before division by the polynomial.

The bottom one uses a smart optimization to give the same result without the appended zeros. It isn't obvious, but it basically always calculates the intermediate value in the shift register assuming that the following M input bits are zero, and does a correction when a "real" input bit = '1' arrives. When the last "real" bit has been processed, it has the final result since it has assumed that the following M bits are zero.

 

[promach]

The bottom one uses a smart optimization to give the same result without the appended zeros. It isn't obvious, but it basically always calculates the intermediate value in the shift register assuming that the following M bits are zero, and does a correction when the "real" input bit arrives. When the last "real" bit has been processed, it has the final result since it has assumed that the following M bits are zero.

assuming that the following M bits are zero ??

 

[std_match]

assuming that the following M bits are zero ??

The shift register will contain the remainder for the currently received input bits appended with M zeros, divided by the polynomial.
For M=8 and the input message 10101010, after processing the 3 first input bits the shift register will contain the remainder for 10100000000 divided by the polynomial.
After the last (8th) message bit, the shift register will contain the remainder for 1010101000000000 divided by the polynomial, which is the final result that we want, calculated in 8 clock cycles. The "long division" version needs 16 clock cycles.

 

[promach]

For M=8 and the input message 10101010, after processing the 3 first input bits the shift register will contain the remainder for 10100000000 divided by the polynomial.
After the last (8th) message bit, the shift register will contain the remainder for 1010101000000000 divided by the polynomial, which is the final result that we want, calculated in 8 clock cycles.

calculated in 8 clock cycles ??

For bottom version, shifting in 8 bits of the input message into the shift register already required 8 clock cylces ...

 

[std_match]

calculated in 8 clock cycles ??

For bottom version, shifting in 8 bits of the input message into the shift register already required 8 clock cylces ...

For the bottom one (the optimized) you don't need to shift in the M zeros after the message, but the value in the shift register is always the remainder of (the currently received input bits + M zeros) divided the polynomial.

 

[promach]

Why the value in the shift register is always the remainder of (the currently received input bits + M zeros) divided the polynomial. ?

 

[std_match]

I think you have to "simulate" some simple examples with pen and paper to see what's going on.
The only internal signal that is identical between the two implementations is the one that controls the subtraction/xor with the polynomial, but it takes M (wasted) clock cycles in the long division implementation before it is affected by the input bits.

 

[vGoodtimes]

Why the value in the shift register is always the remainder of (the currently received input bits + M zeros) divided the polynomial. ?

Let the polynomail be p = (x^8 + x^2 + x + 1). in terms of long division: rem(1/p) = 1. rem(x/p) = x, rem(x^2/p) = x^2 ... rem(x^7/p) = x^7.
rem(x^8/p) = x^2 + x + 1.

the first bit comes in, the value becomes 0x07 which would represent x^2 + x + 1. So that first input bit affected the state as if it were m*x^8 vs just m.

 

[promach]

the first bit comes in, the value becomes 0x07 which would represent x^2 + x + 1.

0x07 should be represented with x¹ + x + 1 instead

Please correct me if wrong.

 

[vGoodtimes]

x^1 == x.
you could also write (x^2 + x^1 + x^0) vs (x^2 + x + 1)