AlgoVerse

Hamming (7,4) code

Add 3 parity bits to 4 data bits so that if one bit is flipped on the way, the syndrome tells exactly where, and it can be fixed.

In the Hamming (7,4) code, positions 1, 2 and 4 (the powers of 2) are parity bits and the rest are data:

Read the full explanation ↓
Input:
data="1011" · error=5PDF export

The data 1011; the code word is 0110011. Bit 5 is flipped on the way, and the syndrome points exactly at 5.

  1. def hamming(data, error):
  2. # Positions 1 … 7 hold p1 p2 d1 p3 d2 d3 d4; c[k - 1] is the bit at position k.
  3. d = [int(b) for b in data]
  4. c = [0, 0, d[0], 0, d[1], d[2], d[3]]
  5. table = [["p1", "p2", "d1", "p3", "d2", "d3", "d4"], c]
  6. c[0] = c[2] ^ c[4] ^ c[6]
  7. c[1] = c[2] ^ c[5] ^ c[6]
  8. c[3] = c[4] ^ c[5] ^ c[6]
  9. sent = "".join(str(b) for b in c)
  10. if error:
  11. c[error - 1] = c[error - 1] ^ 1
  12. # Each check covers the positions whose number has that bit set; together they spell the bad position.
  13. s1 = c[0] ^ c[2] ^ c[4] ^ c[6]
  14. s2 = c[1] ^ c[2] ^ c[5] ^ c[6]
  15. s4 = c[3] ^ c[4] ^ c[5] ^ c[6]
  16. syndrome = s1 + 2 * s2 + 4 * s4
  17. if syndrome:
  18. c[syndrome - 1] = c[syndrome - 1] ^ 1
  19. decoded = f"{c[2]}{c[4]}{c[5]}{c[6]}"
  20. return decoded

Invariant: Each position 1 to 7 lies in a different set of checks (the bits of its number); so the pattern of failed checks pins down the error uniquely.

Start

0123
1011
sent—
syndrome—
decoded—

The table is still empty.

Local variables

data'1011'
error5

Orange = changed in this step

Call stack

  1. hamming()line 1
Step 1 of 18
Black = encoded, syndrome · Orange = key stepparity: 0/3 · encoded: 0/1 · flip: 0/1 · syndrome: 0/1 · corrected: 0/1 · decoded: 0/1
    Explanation

    The idea

    In the Hamming (7,4) code, positions 1, 2 and 4 (the powers of 2) are parity bits and the rest are data:

    • p1 checks the positions whose number has bit 1 set: 1, 3, 5, 7;
    • p2 checks positions 2, 3, 6, 7;
    • p4 checks positions 4, 5, 6, 7.

    Detecting and correcting

    The receiver recomputes all three checks. If the bit at position k was flipped, exactly the checks covering k fail, that is, the bits of the number k. So the binary number formed by the failed checks (the syndrome) is k, and that bit is flipped back. A zero syndrome means no error.

    The code corrects any single-bit error but not two.

    What to watch in the trace

    • The table gives each position's name and bit; watch which bit gets flipped and fixed again.