CRC dumbed down

[RoGeorge]

Usually one will use a ready made library to calculate the CRC in software, or use a shift register made of FF and XOR gates to obtain the CRC in hardware, but this time I've made the mistake of reading about the math behind, and got bamboozled. 

Is the CRC the same as the reminder of a modulo n division?

For example, if my datastream is (333)₁₀, and the CRC polynom is X²+1, so (101)₂ or (5)₁₀, is the CRC equal with 333 modulo 5, so is CRC == 3 in this example?

[0xdeadbeef]

A CRC calculation is the implementation of a polynomial division. The data represented as  binary polynomial is divided by the generator polynomial and the remainder of this division  is the CRC.
E.g. the generator polynomial 1x4 + 1x3 + 1x2 + 0x1 + 1x0 has the binary representation 0b11101 which, truncated to 4bit,  equals 13.
The polynomial division is carried out using bitwise exclusive OR operations.
The start value does not increase the size of the bit stream. It's  just treated as the carry or remainder from a previous calculation. Effectively, it's XORed to the data nibble.
Also, zero padding is necessary (degree R -1). Without zero padding,  the R-1 lowest nibbles would always contribute to the remainder.

Fun Fact: in 2007, I wrote a little document to the guy who wrote the SENT SAE J2716 specification (Single Edge Nibble Transmission) explaining why the "CRC" algorithm shown there wasn't really a CRC calculation and that the look-up table of 256 elements could be reduced to 16 elements. As far as I recall, reply was more or less "but it works". The reduced table actually made it into the next revision of the spec (without mentioning me of course) but the SENT "CRC" is still not really a normal CRC.

[oPossum]

A great explanation of how CRC works....

[RoGeorge]

A great explanation of how CRC works....

https://youtube.com/watch?v=izG7qT0EpBw

That video, together with the followup video about the hardware implementation https://youtube.com/watch?v=sNkERQlK8j8 , cleared out all my questions, thank you!

[brucehoult]

Is the CRC the same as the reminder of a modulo n division?

No, but for a typical application within a computer or in RAM or disk a modulo division and a CRC will provide the same amount of protection, namely a division by N checksum will detect (N-1)/N of all possible random corruptions of the data.

A CRC provides the same amount of protection overall, but with a distribution tailored to specifically bit-serial communication channels, namely (IIRC) with a "good" CRC:

- detection of all 1 bit errors

- detection of essentially all 2 bit errors (of any separation)

- detection of all errors that flip an odd number of bits

- detection of all burst errors shorter than the CRC

The last one is what makes CRC the best for an actual noisy physical channel.

If your data is being transmitted, say, byte-serial on 8 wires e.g. a "parallel port", or stored in 8 Nx1 RAM chips (etc) then you should NOT use a CRC on the whole data, but a separate CRC on each of bit 0, bit 1, ... bit 7 from each byte.

Otherwise the specific property that a CRC is designed for is wasted and you might as well use a cheaper checksum.

[golden_labels]

oPossum, this is a beautifully simple introduction!

If anybody is discouraged by the use of polynomials, a small note. Ben Eater already gave a hint, but let me be more explicit. I guess polynomials were introduced to most people as equations, a “special kind of a function.” This perspective only stands in a way of seeing, what happens here. Forget it. Instead assume a polynomial is nothing more than a “fancy kind of a number.” Each time your brain tries to sum these x-es, just kick it in the butt.

Why is CRC described in terms of polynomials? Because they provide a convenient, very flexible, universal recipe. Maths is all about finding possibly general patterns. They’re easy to prove, they can be recycled for a wide variety of applications, they remain connected with other similar patterns. See that this method works regardless of what x-es are, as long as they follow some simple rules. If they’re chosen right, the entire operation can be implemented with XOR gates.

[ejeffrey]

Also the reason we use these "fancy kinds of numbers" rather that regular integers is to make it easier to implement in hardware.  In "binary polynomial arithmetic" each bit position is independent and addition is done modulo 2.  This eliminates carry, so that addition is just XOR. Multiplication is done by shift and add just like integer multiplication but the addition is done without carry.

[brucehoult]

Also the reason we use these "fancy kinds of numbers" rather that regular integers is to make it easier to implement in hardware.  In "binary polynomial arithmetic" each bit position is independent and addition is done modulo 2.  This eliminates carry, so that addition is just XOR. Multiplication is done by shift and add just like integer multiplication but the addition is done without carry.

Note that various CPUs have instructions to do binary polynomial multiplication directly e.g. RISC-V's clmul in the Zbc extension (included as standard but optional in RVA23)

https://five-embeddev.com/riscv-bitmanip/1.0.0/bitmanip.html#insns-clmul