CRC and checksums: detecting corrupted data

The calculation that checks whether a bit flipped in transit. The difference between a simple sum checksum and a CRC, and how to implement them.

On a noisy wire, a bit can change at any time. For the receiver to notice, the sender sends along a check value calculated from the data, and the receiver does the same calculation and compares.

The sender appends a check value to the data, and the receiver recalculates and compares.

Checksum

The receiver's check sequence.

Add or XOR all the bytes. It is one line to implement, but it does not notice two bytes changing in opposite directions or swapping order.

CRC

Treat the data as one long binary number, divide by a fixed polynomial and use the remainder as the check value. It catches bursts of bit errors very well, which is why CAN, Modbus, Ethernet and USB all use a CRC.

uint16_t crc16_modbus(const uint8_t *p, size_t n) {
    uint16_t crc = 0xFFFF;
    while (n--) {
        crc ^= *p++;
        for (int i = 0; i < 8; i++)
            crc = (crc & 1) ? (crc >> 1) ^ 0xA001 : crc >> 1;
    }
    return crc;
}

Implementation choices

Method	Speed	Memory
Bit-by-bit loop	Slow	Almost none
256-entry table	Fast	512 bytes (CRC16)
Hardware CRC unit	Fastest	None

Each kind of CRC has its own polynomial, initial value and bit reflection, so match exactly what is written in the other device's specification and verify with the result for the well-known test string "123456789".