Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 37 ยท Error-correcting Codes

Error Detection: Parity, Checksums and CRC

Add redundancy to detect transmission errors: parity bits, sums and CRC. Implement CRC-8 and CRC-32 from scratch in Python and compare detection rates.

Shannon showed that reliable communication is possible. The practical question is how: what should you add to a message so that damage can be noticed, or even repaired? This chapter walks from the simplest answer to codes used in real systems. We start with detection: knowing that something went wrong, even if we cannot say where.

Detection matters more than it sounds. Ethernet frames, ZIP files, PNG images, hard-disk sectors and TCP segments all carry a few extra bytes whose only job is to say "this was damaged, throw it away or ask again". Detection also turns a binary symmetric channel into an erasure channel, which is much easier to handle.

The idea: redundancy

A code adds redundancy: out of all possible bit strings of length n, only some are valid codewords. The receiver checks whether the received word is valid. A word that is not valid proves that errors occurred. The minimum distance d of a code, the smallest number of bit positions in which two codewords differ, determines the power: a code detects up to d - 1 bit errors.

Parity

The simplest code appends one bit so that the total number of ones is even (even parity). The minimum distance is 2, so it detects every single-bit error but misses any even number of flips. The cost is a single bit of overhead.

Checksums

A checksum adds up the bytes of the message and appends the sum (modulo some number). It catches most random corruption, but it has weaknesses: swapping two bytes does not change a sum, and two errors can cancel each other.

CRC

A cyclic redundancy check treats the message as a polynomial over the two-element field GF(2) and divides it by a fixed generator polynomial. The remainder is the check value. Division over GF(2) uses XOR instead of subtraction, so it is cheap in hardware and software.

A CRC with an r-bit remainder is guaranteed to detect:

  • every single-bit error and every double-bit error (for suitable generators and message lengths);
  • every burst of errors of length up to r bits;
  • a fraction 1 - 2^(-r) of longer bursts and random corruption.
Python CRC-8 and CRC-32 from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test string 123456789 is the standard "check value" input for CRC algorithms. CRC-32 of it is 0xcbf43926, the same value your operating system's tools would give.

How good is each method?

Let us measure instead of guessing. We take random 100-byte messages, flip a chosen number of random bits, and count how often each method fails to notice.

Python Which method misses errors?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Parity catches 1 and 3 flipped bits but misses every even number. The 8-bit sum misses about 7% of double flips (two errors can cancel), while CRC-8 misses under 1% of them; both catch every single flip. For heavier damage both miss roughly 1 in a few hundred cases, as you would expect from an 8-bit check value. A CRC-32 is far stronger: it misses about 1 in four billion random corruptions.

Burst errors

Real channels often damage runs of consecutive bits: a scratch on a disc, a burst of interference. CRCs are designed for this.

Python CRC-32 and bursts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The count is zero, as the theory promises: a degree-32 generator polynomial detects every burst of up to 32 bits.

A CRC detects accidental damage, not attacks. Anyone can compute a matching CRC for a modified message. For security use a cryptographic hash or a message authentication code, see information theory in cryptography.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A single even-parity bit can detect which errors?

    A flip changes the parity. An odd number of flips changes it; an even number changes it back and goes unnoticed.
  2. 2. A code with minimum distance d can detect up to how many bit errors?

    To turn one codeword into another you need at least d flips, so up to d - 1 flips can never produce a valid codeword.
  3. 3. What bursts is a CRC with an r-bit remainder guaranteed to detect?

    Every burst of length up to r bits is detected; longer bursts are missed with probability about 2^-r.
  4. 4. Why is a CRC unsuitable as protection against deliberate tampering?

    A CRC is linear and has no secret, so forging a message with the same value is easy.

Summary

  • Redundancy makes only some bit strings valid; a received invalid word reveals errors.
  • A code with minimum distance d detects up to d - 1 errors.
  • Parity detects odd numbers of flips; checksums are cheap but weak.
  • CRCs use polynomial division over GF(2) and detect all short bursts.
  • Detection turns hidden flips into known erasures, but a CRC is not a security tool.

Next: Repetition Codes and Hamming Codes