What is the difference between these two implementations as the feedback is in first implementation the last reg only but the second implementation last reg xored with the input bit, so, what is the difference and how can i take the output from them ?
I think the first anwser didn't get the point of the question, though the shift register on the very right side in the first picture is indeed useless and just delays the calculation by one clock cycle as he said, and we can ignore it.
The most significant difference is that in the first picture the MSB decide whether to enable other xor gates or just shift the bits to more significant bits(which is the same with our calculation steps), while in the second picture the MSB first xors with the input and use the result to decide other xor gates to function or not.
At the beginning, I did't understand the logic of the latter one until I try to calculate the polynomial \$x^3+x^2+1\$ in the latter format(xor with input) and found that this hardware implementation can directly give the mode 2 division of 1000 when you just input the digit 1 and needn't input the 0s suffix(which can save 3 clock cycle in this example). Then after understanding its function, I think it's easy for you to understand the mathematical principle of the latter implementation. And from this point, you can also come up with this idea naturally because we can get the result without the 0s suffix actually so why not design a combinational circuit to implement this logic and discard following normal human's calculation steps to solve this more efficiently?
I encountered the second format when reading the DS18B20 datasheet(actually in most applications) but there're few explanations on the Internet. Most crc principle articles just explain crc with the first format,so that I have struggled the whole afternoon. In this process, I also found an implementation of crc, an 8-bit concurrent implementation, and I think their design principle is similar. It use a more complex combinational circuit to calculate the new result directly within one clock cycle when inputing 8 less significant bits simultaneously, which I think is also beneficial for your understanding.
The first example does in fact have the input xored with the output. It's just that the input has a pipeline register which will in essence delay the output by one clock cycle. It doesn't change the polynomial or affect the calculation, and could be removed.
The key difference is the number of registers between the xor gates. It is this that sets the polynomial.
In the second case you have three between the first xor gate and the second, giving you \$x^3\$. Then you have four registers between the second xor gate and the output, giving you \$x^3 \times x^4 = x^7\$. Thus you get the polynomial of \$x^7 + x^3 + 1\$.
In the first case you have two between the first xor gate and the second, giving you \$x^2\$. Then you have 1 register between the second xor gate and the output, giving you \$x^2 \times x^1 = x^3\$. Thus you get a polynomial of \$x^3 + x^2 + 1\$.
I have been comparing these two types of implementations and have also struggled to understand the second one mathematically. It’s true they both xor the output of the shift register with the input data, but in the first case it is only the output bit that determines if the polynomial is subtracted from the CRC value. This is the straightforward case derived from polynomial division. But in the second case, it is the output xor’d with the input bit that determines if the polynomial is subtracted. I haven’t found any reference describing why this works, but it does seem to work.
