Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 57 ยท Combinational Building Blocks

Parity and Error Detection

Build parity generators and checkers from XOR gates, learn the checksum idea, and encode and correct single-bit errors with a Hamming(7,4) code in Python.

Bits get damaged. A cosmic ray flips a memory cell, a noisy cable turns a 1 into a 0, a scratched disc misreads a pit. Digital hardware cannot prevent every flip, but it can notice them, and with a little more cleverness it can even repair them. The cheapest trick is a single extra bit called a parity bit.

In this lesson you will build parity generators and checkers out of XOR gates, see exactly which errors parity can and cannot catch, meet the checksum idea, and finish with the Hamming(7,4) code, which locates a flipped bit and corrects it. Everything here is pure combinational logic: no memory, just gates.

Parity: counting the ones

A parity bit is chosen so that the total number of 1s in a word, including the parity bit itself, has a fixed oddness.

  • Even parity: the total number of 1s is even.
  • Odd parity: the total number of 1s is odd.

Take the data 1011. It has three 1s. With even parity we append a 1 so the total becomes four: 10111. With odd parity we append a 0 and keep three: 10110.

The XOR gate is a one-bit parity detector. a XOR b is 1 exactly when an odd number of its inputs are 1. Chain more XORs and the output is 1 when an odd number of inputs are 1, whatever the width:

P = d3 โŠ• d2 โŠ• d1 โŠ• d0

That P is exactly the even-parity bit: it is 1 when the data has an odd number of 1s, so adding it makes the total even. For odd parity you invert it (XNOR the last stage).

XOR trees

Because XOR is associative, a long chain can be rearranged as a balanced tree. Eight inputs need seven two-input XOR gates either way, but a chain is 7 gate delays deep while a tree is only 3. For a wide bus the tree wins. The general rule is that n inputs need n - 1 gates and a tree depth of ceil(log2 n).

One extra bit, one big win

Generator XOR all data bits to make the parity bit.
Checker XOR all bits plus parity. A 1 means error.
Tree layout Depth grows as log2 of the width.

Sender generates, receiver checks.

1 / 2

A parity generator and checker

The checker works on the received word including its parity bit. If the data and the parity bit agree, the XOR of everything is 0 for even parity. A 1 raises the error flag.

Python Parity generator and checker

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.

Single flips and triple flips are always caught, because they change the count of 1s by an odd number. Two flips ([0, 3]) and four flips go unnoticed because the count stays even. Real links often add a second layer of protection for exactly this reason.

Parity tells you that something is wrong, never where. A receiver that sees a parity error can only ask for the data to be sent again or discard it.

The checksum idea

When data comes in whole blocks (a network packet, a file), a longer check value gives better protection than one parity bit per word. A checksum combines all the bytes of a block into one small number, and the sender appends it. The receiver recomputes it and compares.

The simplest version adds all bytes and keeps the low 8 bits. Another version XORs all bytes together, which is simply a column-wise parity: bit 0 of the checksum is the parity of all bit-0s, and so on. Both are cheap in hardware, but both have weaknesses. An addition checksum is blind to bytes that are swapped, and an XOR checksum is blind to two flips in the same bit column. Stronger codes such as CRC treat the data as a polynomial and use a chain of XORs and shifts. They are built from the same XOR gates, plus flip-flops that you will meet in later chapters.

Python Sum checksum versus XOR 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.

Swapping two bytes keeps both checksums unchanged, so both miss it. Flipping the same bit in two bytes cancels in the XOR checksum, but the sum still moves. No cheap checksum catches everything, which is why you pick the check to match the errors you expect.

Hamming(7,4): finding and fixing one flipped bit

Richard Hamming's idea was to use several overlapping parity bits so that together they point at the damaged position. The Hamming(7,4) code protects 4 data bits with 3 parity bits, giving a 7-bit codeword.

Number the positions 1 to 7. The parity bits sit at the positions that are powers of two (1, 2 and 4); the data bits fill the rest (3, 5, 6, 7). Each parity bit covers every position whose binary number has a particular bit set:

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

The receiver recomputes the three groups. Each group that fails contributes a 1 to a 3-bit number called the syndrome, with the p4 check as the most significant bit. If all three checks pass, the syndrome is 000 and nothing is wrong. Otherwise the syndrome, read as a binary number, is the position of the flipped bit. Flip that bit back and the data is repaired.

Why does this work? Every position from 1 to 7 has a different pattern of "which groups include me", and that pattern is just its binary number. A flip in position 5 (binary 101) breaks groups p1 and p4, so the syndrome is 101 = 5.

flowchart LR
    D["4 data bits"] --> E["Encoder<br/>3 XOR trees"]
    E --> C["7-bit codeword"]
    C --> N["Noisy channel<br/>one bit may flip"]
    N --> S["Syndrome<br/>3 XOR trees"]
    S --> F["Flip bit at<br/>syndrome position"]
    F --> O["4 data bits"]

Encode with three parity trees, check with three more, and the syndrome names the broken bit.

Python Hamming(7,4) with a live 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.

Every one of the 128 cases (16 data words, each with no error or one of 7 single errors) is recovered, but the last test shows the limit: with two flips the syndrome points at a position that was fine, and the "repair" makes the data wrong. Adding one more overall parity bit gives SECDED (single error correct, double error detect), which is what ECC memory uses.

In hardware the whole decoder is combinational: three XOR trees compute the syndrome, a 3:8 decoder turns it into a one-hot "this bit is bad" line, and an XOR gate on each data bit flips it back when its line is high.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which gate computes the parity of its inputs?

    An XOR output is 1 when an odd number of inputs are 1, which is exactly the parity of the inputs.
  2. 2. Even parity is used on the data 1101. What is the parity bit?

    1101 has three ones, which is odd, so the parity bit must be 1 to make the total of four ones even.
  3. 3. Which error does a single parity bit fail to detect?

    Two flips change the number of 1s by an even amount, so the parity looks correct. Odd numbers of flips, including a flipped parity bit, are caught.
  4. 4. In Hamming(7,4) the syndrome reads 110 (binary). What does that mean?

    The syndrome is the binary number of the bad position, and 110 is 6. The receiver flips bit 6 back.
  5. 5. Eight inputs are XORed in a balanced tree of two-input gates. What is the tree depth?

    The depth is log2(8) = 3 levels, using 7 gates in total. A chain would use the same 7 gates but be 7 levels deep.

Summary

  • A parity bit makes the number of 1s even (or odd); an XOR tree of the data bits generates it, and the same XOR tree over the received word checks it.
  • Parity catches every odd number of bit flips but misses even numbers, and it never says where the error is.
  • A balanced XOR tree of n inputs uses n - 1 gates and has depth ceil(log2 n).
  • Checksums fold a whole block into a small number; simple sum and XOR checksums each have blind spots that CRCs reduce.
  • Hamming(7,4) adds three overlapping parity bits so the syndrome names the position of a single flipped bit, which is then corrected; two flips fool it, and an extra overall parity bit (SECDED) detects them.

Next: SR Latches and Feedback.