Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 67 ยท Data Representation

Parity, Checksums and Error-Correcting Codes

Learn how parity bits, checksums, CRC and Hamming codes detect and correct bit errors in memory and networks, with working Python implementations.

Hardware is imperfect. A cosmic ray flips a bit in RAM, electrical noise corrupts a bit on a cable, a scratch damages a disc. If a single flipped bit turned your bank balance into a different number, computers would be useless. The solution is redundancy: add a few extra bits, computed from the data, so the receiver can notice that something changed, and sometimes even fix it.

In this lesson you will build four tools in Python, from the simplest to the most powerful: a parity bit, a checksum, a CRC, and a Hamming code that corrects a single flipped bit. You will test each one by flipping bits yourself.

Detect or correct?

There are two goals:

  • Error detection says "this data is damaged". The fix is to ask again (resend, re-read, use another copy).
  • Error correction reconstructs the original data without asking. It needs more redundancy, but it is the only option when you cannot ask again: memory, deep-space probes, optical discs.

The key measure is the Hamming distance: the number of bit positions in which two valid codewords differ. If every pair of valid codewords is at least d bits apart, the code can detect up to d - 1 bit errors and correct up to (d - 1) / 2 of them (rounded down).

Minimum distance Detects Corrects
1 (no redundancy) 0 0
2 (parity) 1 0
3 (Hamming 7,4) 2 1
4 (SECDED) 3 1 (and detects 2)

Parity

A parity bit is one extra bit chosen so that the total number of 1s is even (even parity) or odd (odd parity). With even parity, 1011001 has four 1s, so the parity bit is 0; 1011000 has three, so the parity bit is 1.

If any single bit flips, the count of 1s changes parity and the receiver notices. Two flips cancel each other and slip through. Parity cannot say which bit is wrong, so it only detects errors. Serial links, old memory and some caches use it because it costs one gate tree (XORs) and one extra bit.

flowchart LR
  D["Data bits<br/>1011001"] --> X["XOR of all bits"]
  X --> P["Parity bit<br/>0"]
  D --> W["Codeword<br/>10110010"]
  P --> W

The parity bit is the XOR of all data bits.

Python Even parity: catches one flip, misses two

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.

Checksums

Parity covers one word. For a block of bytes (a network packet, a download) you want something stronger. A checksum adds up the data and sends the sum along.

The simplest version is the sum of all bytes modulo 256. It is cheap but weak: reordering bytes gives the same sum, and two errors can cancel (one byte +1, another -1). The Internet checksum used by IP, TCP and UDP adds 16-bit words using ones' complement arithmetic (the carry that falls off the top is added back in) and sends the complement of the result. The receiver adds everything including the checksum and expects all ones.

A checksum catches most random corruption, but it cannot catch swapped words, and it is not designed to resist someone deliberately altering data. For that you need a cryptographic hash.

Python A simple checksum and the Internet checksum

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.

CRC: polynomial division on bits

A cyclic redundancy check (CRC) is the workhorse of Ethernet, Wi-Fi, USB, ZIP, PNG and disk sectors. The idea: treat the message as one huge binary polynomial, divide it by a fixed generator polynomial, and send the remainder as the check value. The receiver divides again; a non-zero remainder means damage.

Division here uses XOR instead of subtraction, so there are no borrows and the whole thing is a shift register with a few XOR gates, which is why it is so cheap in hardware. A CRC of n bits is guaranteed to detect:

  • all single-bit errors and all double-bit errors (for suitable polynomials and message lengths),
  • any odd number of errors (if the polynomial has a factor x + 1),
  • every burst of errors no longer than n bits,
  • and all but a fraction of about 1 / 2^n of longer bursts.

Bursts are exactly what noisy cables and scratched discs produce, which is why CRC beats a plain checksum.

Python CRC-8 computed bit by bit

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.

Real systems use wider CRCs (CRC-16, CRC-32) so that the chance of an undetected random error is about one in four billion. A CRC is still not secure: an attacker can craft changes that keep the same CRC.

Hamming codes: correcting a bit

Richard Hamming invented codes that fix errors automatically. The classic Hamming(7,4) code protects 4 data bits with 3 parity bits, giving 7-bit codewords with minimum distance 3.

The trick is where the parity bits sit. Number the positions 1 to 7. Positions that are powers of two (1, 2, 4) hold parity bits; the others (3, 5, 6, 7) hold data. Each parity bit checks the positions whose binary index has that bit set:

Parity bit Checks positions
p1 (position 1) 1, 3, 5, 7
p2 (position 2) 2, 3, 6, 7
p4 (position 4) 4, 5, 6, 7

When a codeword arrives, recompute the three checks. Each failed check contributes its weight to the syndrome: p1 fails = 1, p2 fails = 2, p4 fails = 4. The syndrome, read as a binary number, is the position of the flipped bit (0 means no error). Flip that bit back and you have the original.

flowchart TD
  R["Received 7 bits"] --> C["Recompute p1, p2, p4 checks"]
  C --> S["Syndrome = failed checks as a binary number"]
  S -->|"0"| OK["No error"]
  S -->|"1 to 7"| F["Flip bit at that position"]
  F --> OUT["Extract data bits 3, 5, 6, 7"]
  OK --> OUT

The syndrome points directly at the damaged position.

Python Hamming(7,4): correct every single-bit error

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 last line shows the limit: with two errors Hamming(7,4) "corrects" the wrong bit and returns bad data silently.

SECDED: what ECC memory really uses

Server and workstation RAM uses SECDED codes: Single-Error Correction, Double-Error Detection. Add one extra overall parity bit to a Hamming code. Now a non-zero syndrome with a failed overall parity means one error (correct it), while a non-zero syndrome with a good overall parity means two errors (report them, do not "fix" anything). A typical ECC DIMM stores 72 bits for every 64 bits of data, an overhead of 12.5%. The memory controller checks every read, repairs single-bit flips on the fly and logs them, so admins can see a failing module before it causes a crash.

Redundancy is a general trade-off. The more errors you want to catch or fix, the more extra bits you pay for; the table below summarizes the tools in this lesson.

Method Overhead Detects Corrects Typical use
Parity 1 bit per word 1 bit (odd counts) No Serial lines, caches
Checksum 8 to 16 bits per packet Most random errors No IP, TCP, UDP headers
CRC 8 to 32 bits per block Bursts and random errors No Ethernet, disks, files
Hamming SECDED 8 bits per 64 2 bits 1 bit ECC memory
Reed-Solomon Configurable Many Many (burst) CDs, QR codes, RAID 6

RAID storage uses the same ideas at the disk level. See Disks, SSDs and RAID for how a parity disk lets you rebuild a failed drive.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A code has minimum Hamming distance 3. What can it do?

    Distance 3 means two valid codewords differ in at least 3 bits, enough to detect two flips or to correct one by picking the nearest codeword.
  2. 2. Why can a single parity bit not correct an error?

    A failed parity check says that an odd number of bits changed, but it carries no position information.
  3. 3. In Hamming(7,4), the syndrome 6 (binary 110) means what?

    The syndrome is built from the failed parity checks (p2 and p4 here, 2 + 4 = 6) and equals the position of the damaged bit.
  4. 4. What is a main advantage of CRC over a simple sum checksum?

    CRC treats data as a polynomial, so position matters and bursts up to the CRC width are always caught. It is not cryptographically secure and does not correct errors.
  5. 5. What does SECDED stand for in ECC memory?

    SECDED codes fix any one flipped bit and detect (but cannot fix) any two.

Summary

  • Redundant bits let a receiver detect, and sometimes correct, damaged data.
  • The Hamming distance of a code decides how many errors it detects (d - 1) and corrects ((d - 1) / 2).
  • A parity bit detects any single flip but cannot locate it, and misses even numbers of flips.
  • Checksums sum the data; CRCs divide it as a polynomial and catch bursts, but neither is secure against tampering.
  • Hamming(7,4) puts parity bits at power-of-two positions; the syndrome is the position of the flipped bit.
  • SECDED codes (Hamming plus an overall parity bit) protect ECC memory.

Now that you can trust your bits, move on to the circuits that process them in Logic Gates and Boolean Algebra.