[<<][math][>>][..]Wed Oct 23 09:20:49 EDT 2019

EDIT: Principle is right, but implementation details requires some additional assumptions. See end. CRC is modulo reduction using an irreducible polynomial. I.e. long division. However, how does a bit stream actually map to the input polynomial? And why does accumulator chaining work? Let's try to perform a division and fill in the gaps. x^3 + x + 1 is 1011 Dividing 10101010 by 1011 10101010 | 1011 10110000 |------- -------- | 10011 11010 10110 ----- 1110 1011 ---- 101 Only the remainder is useful. How to turn this into something that takes a single bit at a time? Note that only the first 4 bits of the dividend are necessary. That is the key to turning this into a state machine. To visualize, spell out the zero subtractions explicitly. 10101010 | 1011 10110000 |------- -------- | 10011 0011010 0000000 ------- 011010 000000 ------ 11010 10110 ----- 1110 1011 ---- 101 Then mask out the bits that do not need to be known at each step, feeding in a bit when it is necessary. 1010.... | 1011 10110000 |------- -------- | 10011 0011... 0000000 ------- 0110.. 000000 ------ 1101. 10110 ----- 1110 1011 ---- 101 The trick here is that there is no carry! This allows us to carry on a step without knowing the downstream bits! This would not work so smoothly with an addition operation that carries over into lower significant bits. To restore symmetry, add zero bits. ........ 00000000 -------- 1....... 00000000 -------- 10...... 00000000 -------- 101..... 00000000 -------- 1010.... | 1011 10110000 |------- -------- | 000010011 0011... 0000000 ------- 0110.. 000000 ------ 1101. 10110 ----- 1110 1011 ---- 101 This property allows to just roll the algoritm. So the "accumulator" is essentially the first 4 digits of the intermediate, which will end up as the full modulo at the end. This all seems plausible. So let's implement it and see if it holds up. There are essentially only two operations: - devision reduction step - shift in a new bit The polynomial is typically represented as bits without the top bit which is always 1. In our case, the poly residu is 011. Suppose the accumulator is 1010 The algorithm step is then: - store the top bit - shift in the new bit - xor with residu if top bit was 1 Now I just need to know what the bit order convention is. It seems that shifting in MSB first makes most sense. Let's check this with a crc8 plucked from the internet. EDIT: This mentions padding at the end. https://en.wikipedia.org/wiki/Cyclic_redundancy_check Still not quite clear. I'm doing something else. https://rosettacode.org/wiki/CRC-32 I think I have the definition wrong. From the wikipedia page: This is first padded with zeros corresponding to the bit length n of the CRC. This is done so that the resulting code word is in systematic form. https://en.wikipedia.org/wiki/Systematic_code A systematic code is any error-correcting code in which the input data is embedded in the encoded output. I don't understand this. But what I am doing is padding with zeros at the start? So I give up. Interpret and generalze a working implementation instead: https://stackoverflow.com/questions/21001659/crc32-algorithm-implementation-in-c-without-a-look-up-table-and-with-a-public-li So CRC32 and CRC32B are not the same: https://stackoverflow.com/questions/15861058/what-is-the-difference-between-crc32-and-crc32b

[Reply][About]

[<<][math][>>][..]