Error Detection

Detecting corrupted data. Learn parity bits, checksums (Internet checksum), cyclic redundancy checks (polynomial division, generator polynomials, burst-error detection, CRC-16/32), undetected error probability, and ARQ retransmission (stop-and-wait, go-back-N, selective repeat).

Every Ethernet frame, USB packet, CAN message and ZIP file carries a CRC. Detecting errors (and asking for retransmission) is often simpler and more efficient than correcting them.

An analogy

A checksum is like counting the items in a parcel and writing the total on the label: if the count at arrival differs, something was lost or changed.

Parity

One extra bit makes the number of 1s even (or odd). Detects any single-bit error but misses two-bit errors. Used in UART frames and memory.

Checksums

Sum of data words (e.g. 16-bit one's-complement Internet checksum in IP/UDP/TCP). Cheap in software, weaker than CRC against certain error patterns.

CRC

Treat data as a polynomial and divide by a generator using XOR. An r-bit CRC detects all single and double errors (for good polynomials), all odd numbers of errors (if (x + 1) is a factor), and all bursts ≤ r bits.

ARQ

Detected errors trigger retransmission: stop-and-wait (simple, inefficient on long links), go-back-N and selective repeat (sliding windows). Hybrid ARQ (LTE/5G) combines FEC with retransmissions and soft combining.

Formulas

• Even parity: p = d₁ ⊕ d₂ ⊕ … ⊕ d_n
• CRC: CRC = remainder of M(x)·x^r ÷ G(x) (mod-2)
• Undetected (random errors): P_ud ≈ 2^(−r)
• Stop-and-wait efficiency: η = 1 / (1 + 2a), a = propagation delay / frame time

Worked example: Parity

Given: Data 1011001 (four 1s); Even parity

Find: Parity bit.

• Four 1s already even → p = 0

Answer: Transmit 1011001 0

Worked example: CRC strength

Given: CRC-32

Find: Undetected probability for random corruption.

• P_ud ≈ 2⁻³² = 2.3 × 10⁻¹⁰

Answer: ≈ 1 in 4.3 billion corrupted frames

CRC-16/CCITT-FALSE in C

#include <stdint.h>
#include <stddef.h>

/* Polynomial x^16 + x^12 + x^5 + 1 (0x1021), init 0xFFFF */
uint16_t crc16_ccitt(const uint8_t *data, size_t len) {
    uint16_t crc = 0xFFFF;
    while (len--) {
        crc ^= (uint16_t)(*data++) << 8;
        for (int i = 0; i < 8; i++)
            crc = (crc & 0x8000) ? (uint16_t)((crc << 1) ^ 0x1021) : (uint16_t)(crc << 1);
    }
    return crc;
}
/* crc16_ccitt("123456789", 9) == 0x29B1  (standard check value) */

The bitwise loop implements mod-2 polynomial division. Production code uses a 256-entry lookup table or hardware CRC units found in most MCUs. The check value verifies an implementation.

Common mistakes

• Wrong: Mixing CRC variants. — Right: Match polynomial, init value, reflection and final XOR.
• Wrong: Using stop-and-wait on long links. — Right: Use sliding-window ARQ.

Applications

• Networks: Ethernet FCS (CRC-32), TCP checksums.
• Embedded buses: CAN CRC-15, Modbus CRC-16.
• Storage: Firmware images and file integrity.

Key takeaways

• Parity → checksum → CRC in strength.
• CRC = mod-2 remainder with G(x).
• P_ud ≈ 2⁻ʳ.
• ARQ retransmits detected errors.

Going further

• CRC polynomial selection: Hamming distance by message length (Koopman tables).
• Hybrid ARQ: Soft combining in LTE/5G.
• Cryptographic MACs: Detect intentional tampering (CRC cannot).