DEV Community

Cover image for Error Detection: Parity, Checksum & Cyclic Redundancy Check (CRC)
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Error Detection: Parity, Checksum & Cyclic Redundancy Check (CRC)

#programming #computerscience

Error Detection: Parity, Checksum & Cyclic Redundancy Check (CRC)

When raw electrical voltage pulses or radio waves travel across cables and air, electromagnetic interference inevitably corrupts bits in flight.

To prevent silent data corruption, network protocols append redundant error-detecting bits to every frame. Among all techniques, Cyclic Redundancy Check (CRC) is the undisputed champion of the Data Link layer.

⚡ Why Parity and Checksums Fail

Technique Where Used Detection Strength Fatal Blind Spot
Simple Parity Serial UART, RAM All single-bit errors Blind to any even number of bit flips (2, 4, 6)
Internet Checksum IPv4, TCP headers Good general software checksum Blind to byte swaps and equal opposing errors
Cyclic Redundancy Check (CRC) Ethernet, Wi-Fi, 4G/5G, SATA Near 100% of all error patterns Requires hardware shift registers

🧠 The Mathematics of CRC

CRC treats binary bit strings as algebraic polynomials over the Galois field GF(2), where addition and subtraction are identical to bitwise XOR (oplus) with no carries and no borrows:

beginaligned 1 oplus 1 &= 0 \\ 1 oplus 0 &= 1 \\ 0 oplus 1 &= 1 \\ 0 oplus 0 &= 0 endaligned
Enter fullscreen mode Exit fullscreen mode

The 4-Step CRC Algorithm

  1. Let the original data be D (k bits) and the agreed Generator Polynomial be G of degree r (r + 1 bits).
  2. Append r zero bits to the end of D, yielding D · 2^r.
  3. Divide D · 2^r by G using modulo-2 XOR long division.
  4. The remainder R (r bits) is the Frame Check Sequence (FCS).
  5. The transmitted frame is T = (D · 2^r) oplus R. 
At the Receiver:
                Received Frame (T)
                ──────────────────  =  Remainder ?
                  Generator (G)

  • If Remainder == 0: Frame is intact and accepted!
  • If Remainder != 0: Frame suffered bit corruption -> Discard immediately!
Enter fullscreen mode Exit fullscreen mode

In standard IEEE 802.3 Ethernet, CRC-32 uses a 33-bit generator polynomial that catches 100% of burst errors up to 32 consecutive bits long, keeping our global internet packets bit-for-bit clean!

Solve step-by-step CRC polynomial divisions with our interactive calculator on Binary Dose.

Top comments (0)