Project P076
Hamming code
Hamming's (7,4) code: 4 data bits sent as 7 so that one flipped bit is found by the checks that fail and put right; what two or three flips do to it; and the eighth parity bit that turns two flips from a wrong answer into a detected error.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Hamming's (7,4) code sends 4 data bits as 7. The checks that fail spell out which bit flipped, so one flip can be put right. The program shows what two or three flips do to it, and how an eighth parity bit turns two flips from a wrong answer into a detected error.
main.eml- the menu, reading bits and positions, and the reportshamming.eml- encoding, the syndrome, correction, flipping, distance, the eighth bit, and all 16 codewords
How each part works:
- Positions 1 to 7. The parity bits sit at 1, 2 and 4, and the data at 3, 5, 6 and 7. Parity bit p covers every position whose number has p in its binary form: p1 covers 1, 3, 5, 7; p2 covers 2, 3, 6, 7; p4 covers 4, 5, 6, 7. Each is set so its positions hold an even number of 1s.
- Receiving: the three checks are run again. Those that fail add up to the syndrome, and a single flip at position k fails exactly the checks that k's binary form names. So the syndrome is k, and bit k is flipped back.
- Distance, as in the corpus case
hamming-distance: the number of places two words differ. Any two codewords differ in at least 3, so one flip leaves the received word nearer the word sent than any other. - Two flips land nearer a different codeword. The 7-bit decoder always assumes one flip, so it changes a third bit and gives the wrong data. Three flips can even look like none.
- The eighth bit makes the whole word even. One flip makes the word odd, and is corrected. Two flips leave it even while the checks fail, so the error is detected but not corrected: ask again. Three flips look like one, so that is wrong too.
What is checked: menu choices 1 to 5; exactly 4 or 7 bits, 0 or 1 (spaces ignored); 1 to 3 different positions from 1 to 7. An empty answer cancels.
Sessions: sessions/basic.in gives: - 1011 sent as 0110011; - 0110111 received: the checks point at 5, and 1011 comes back; then 0110011, which passes; - 1011 with position 5 flipped (corrected), with 3 and 5 (wrong with 7 bits, detected with 8), and with 1, 2 and 3 (passes every check, wrong); - 0000 with 1, 2 and 4 flipped, wrong both ways; - all 16 codewords, at least 3 places apart.
sessions/bad-input.in gives: - menu choices 0 and x; - data 101 and 10a1, a 4-bit word where 7 are needed, then cancels; - positions 8, "3 3" and four positions, then a cancel.
Built on the verified corpus case hamming-distance (counting the places two equal-length words differ).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Hamming code ==
Hamming's (7,4) code: 4 data bits sent as 7, so one flipped bit can be found and put right.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 0
Pick a number from 1 to 5.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> x
Pick a number from 1 to 5.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 1
4 data bits (like 1011)> 101
Type exactly 4 bits, 0 or 1.
4 data bits (like 1011)> 10a1
Type exactly 4 bits, 0 or 1.
4 data bits (like 1011)>
Cancelled.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 2
7 bits received> 0110
Type exactly 7 bits, 0 or 1.
7 bits received>
Cancelled.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 3
4 data bits (like 1011)> 1011
positions to flip (1 to 3 of 1-7, like 3 5)> 8
Type 1 to 3 different positions from 1 to 7, like 3 5.
positions to flip (1 to 3 of 1-7, like 3 5)> 3 3
Type 1 to 3 different positions from 1 to 7, like 3 5.
positions to flip (1 to 3 of 1-7, like 3 5)> 1 2 3 4
Type 1 to 3 different positions from 1 to 7, like 3 5.
positions to flip (1 to 3 of 1-7, like 3 5)>
Cancelled.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 5
Bye.
What was typed (16 lines)
0
x
1
101
10a1
2
0110
3
1011
8
3 3
1 2 3 4
5
basic
interpreter: byte-equal== Hamming code ==
Hamming's (7,4) code: 4 data bits sent as 7, so one flipped bit can be found and put right.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 1
4 data bits (like 1011)> 1011
position 1 2 3 4 5 6 7
role p1 p2 d1 p4 d2 d3 d4
bit 0 1 1 0 0 1 1
p1 makes positions 1, 3, 5, 7 even; p2 makes 2, 3, 6, 7 even; p4 makes 4, 5, 6, 7 even.
1011 is sent as 0110011.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 2
7 bits received> 0110111
position 1 2 3 4 5 6 7
role p1 p2 d1 p4 d2 d3 d4
bit 0 1 1 0 1 1 1
The checks that fail add up to 5, so position 5 is flipped back: 0110011, data 1011.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 2
7 bits received> 0110011
position 1 2 3 4 5 6 7
role p1 p2 d1 p4 d2 d3 d4
bit 0 1 1 0 0 1 1
All three checks pass: the data is 1011.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 3
4 data bits (like 1011)> 1011
positions to flip (1 to 3 of 1-7, like 3 5)> 5
sent 0110011, received 0110111 - 1 flipped.
7 bits: the checks point at position 5; flipping it back gives data 1011.
That is right.
8 bits (an eighth bit making the word even): it looks like one flip, so it corrects it - data 1011.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 3
4 data bits (like 1011)> 1011
positions to flip (1 to 3 of 1-7, like 3 5)> 3 5
sent 0110011, received 0100111 - 2 flipped.
7 bits: the checks point at position 6; flipping it back gives data 0101.
That is wrong: 1011 was sent. The 7-bit code always assumes one flip, and cannot tell more from one.
8 bits (an eighth bit making the word even): the checks fail but the word is still even, so two bits changed - detected, not corrected; ask again.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 3
4 data bits (like 1011)> 1011
positions to flip (1 to 3 of 1-7, like 3 5)> 1 2 3
sent 0110011, received 1000011 - 3 flipped.
7 bits: every check passes, so the decoder takes it as sent - data 0011.
That is wrong: 1011 was sent. The 7-bit code always assumes one flip, and cannot tell more from one.
8 bits (an eighth bit making the word even): it looks like one flip, so it corrects it - data 0011.
That is wrong too: to the eighth bit, three flips look like one.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 3
4 data bits (like 1011)> 0000
positions to flip (1 to 3 of 1-7, like 3 5)> 1 2 4
sent 0000000, received 1101000 - 3 flipped.
7 bits: the checks point at position 7; flipping it back gives data 0001.
That is wrong: 0000 was sent. The 7-bit code always assumes one flip, and cannot tell more from one.
8 bits (an eighth bit making the word even): it looks like one flip, so it corrects it - data 0001.
That is wrong too: to the eighth bit, three flips look like one.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 4
data codeword
0000 0000000
0001 1101001
0010 0101010
0011 1000011
0100 1001100
0101 0100101
0110 1100110
0111 0001111
1000 1110000
1001 0011001
1010 1011010
1011 0110011
1100 0111100
1101 1010101
1110 0010110
1111 1111111
Any two codewords differ in at least 3 places, so one flip leaves a word nearer the one sent than any other, and two flips can land nearer a different one.
1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit
choice> 5
Bye.
What was typed (20 lines)
1
1011
2
0110111
2
0110011
3
1011
5
3
1011
3 5
3
1011
1 2 3
3
0000
1 2 4
4
5
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P076 Hamming code: 4 data bits sent as 7, any one flipped bit found and
# put right; what two flips do to it; and the eighth parity bit that turns
# two flips from a wrong answer into a detected error.
import hamming
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def bits_of(s, n):
# "1011" -> [1, 0, 1, 1] if s is exactly n bits (spaces ignored), else [].
[] => out
for c in s:
if c == "0":
out + [0] => out
elif c == "1":
out + [1] => out
elif c != " ":
return []
if len(out) != n:
return []
return out
def text(bits):
"" => s
for b in bits:
s + str(b) => s
return s
def positions_of(s):
# "3 5" -> [3, 5]: one to three different positions from 1 to 7.
[] => out
for c in s:
if c >= "1" and c <= "7":
for p in out:
if p == int(c):
return []
out + [int(c)] => out
elif c != " " and c != ",":
return []
if len(out) == 0 or len(out) > 3:
return []
return out
def ask_bits(prompt, n):
while True:
trim(input(prompt)) => s
if s == "":
return []
bits_of(s, n) => b
if len(b) == n:
return b
("Type exactly " + str(n) + " bits, 0 or 1.") ^0
def layout(c):
" position 1 2 3 4 5 6 7" ^0
" role p1 p2 d1 p4 d2 d3 d4" ^0
"" => line
for b in c:
line + " " + str(b) => line
(" bit " + line) ^0
def send():
ask_bits("4 data bits (like 1011)> ", 4) => d
if len(d) == 0:
"Cancelled." ^0
return
hamming.encode(d) => c
layout(c)
" p1 makes positions 1, 3, 5, 7 even; p2 makes 2, 3, 6, 7 even; p4 makes 4, 5, 6, 7 even." ^0
(text(d) + " is sent as " + text(c) + ".") ^0
def receive():
ask_bits("7 bits received> ", 7) => c
if len(c) == 0:
"Cancelled." ^0
return
hamming.correct(c) => r
layout(c)
if r[0] == 0:
("All three checks pass: the data is " + text(hamming.data_of(c)) + ".") ^0
else:
("The checks that fail add up to " + str(r[0]) + ", so position " + str(r[0]) + " is flipped back: " + text(r[1]) + ", data " + text(hamming.data_of(r[1])) + ".") ^0
def experiment():
ask_bits("4 data bits (like 1011)> ", 4) => d
if len(d) == 0:
"Cancelled." ^0
return
while True:
trim(input("positions to flip (1 to 3 of 1-7, like 3 5)> ")) => s
if s == "":
"Cancelled." ^0
return
positions_of(s) => ps
if len(ps) > 0:
hamming.encode(d) => c
hamming.flipped(c, ps) => bad
hamming.correct(bad) => r
hamming.data_of(r[1]) => got
("sent " + text(c) + ", received " + text(bad) + " - " + str(len(ps)) + " flipped.") ^0
if r[0] == 0:
("7 bits: every check passes, so the decoder takes it as sent - data " + text(got) + ".") ^0
else:
("7 bits: the checks point at position " + str(r[0]) + "; flipping it back gives data " + text(got) + ".") ^0
if got == d:
" That is right." ^0
else:
(" That is wrong: " + text(d) + " was sent. The 7-bit code always assumes one flip, and cannot tell more from one.") ^0
hamming.with_parity(c) => w
hamming.flipped(w, ps) => wbad
hamming.secded(wbad) => v
if v[0] == "two errors":
("8 bits (an eighth bit making the word even): the checks fail but the word is still even, so two bits changed - detected, not corrected; ask again.") ^0
elif v[0] == "corrected":
("8 bits (an eighth bit making the word even): it looks like one flip, so it corrects it - data " + text(v[1]) + ".") ^0
else:
("8 bits (an eighth bit making the word even): every check passes - data " + text(v[1]) + ".") ^0
if v[0] != "two errors" and v[1] != d:
" That is wrong too: to the eighth bit, three flips look like one." ^0
return
"Type 1 to 3 different positions from 1 to 7, like 3 5." ^0
def table():
hamming.codewords() => cs
" data codeword" ^0
for n in [0:15]:
(" " + text(cs[n][2:3] + cs[n][4:7]) + " " + text(cs[n])) ^0
16 => fewest
for i in [0:15]:
for j in [i + 1:15]:
hamming.distance(cs[i], cs[j]) => k
if k < fewest:
k => fewest
("Any two codewords differ in at least " + str(fewest) + " places, so one flip leaves a word nearer the one sent than any other, and two flips can land nearer a different one.") ^0
"== Hamming code ==" ^0
"Hamming's (7,4) code: 4 data bits sent as 7, so one flipped bit can be found and put right." ^0
True => running
while running:
"" ^0
"1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
send()
elif choice == "2":
receive()
elif choice == "3":
experiment()
elif choice == "4":
table()
elif choice == "5":
False => running
else:
"Pick a number from 1 to 5." ^0
"Bye." ^0
Python projection (main.py)
import hamming
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def bits_of(s, n):
out = []
for c in s:
if c == "0":
out = out + [0]
elif c == "1":
out = out + [1]
elif c != " ":
return []
if len(out) != n:
return []
return out
def text(bits):
s = ""
for b in bits:
s = s + str(b)
return s
def positions_of(s):
out = []
for c in s:
if c >= "1" and c <= "7":
for p in out:
if p == int(c):
return []
out = out + [int(c)]
elif c != " " and c != ",":
return []
if len(out) == 0 or len(out) > 3:
return []
return out
def ask_bits(prompt, n):
while True:
s = trim(input(prompt))
if s == "":
return []
b = bits_of(s, n)
if len(b) == n:
return b
print("Type exactly " + str(n) + " bits, 0 or 1.")
def layout(c):
print(" position 1 2 3 4 5 6 7")
print(" role p1 p2 d1 p4 d2 d3 d4")
line = ""
for b in c:
line = line + " " + str(b)
print(" bit " + line)
def send():
d = ask_bits("4 data bits (like 1011)> ", 4)
if len(d) == 0:
print("Cancelled.")
return
c = hamming.encode(d)
layout(c)
print(" p1 makes positions 1, 3, 5, 7 even; p2 makes 2, 3, 6, 7 even; p4 makes 4, 5, 6, 7 even.")
print(text(d) + " is sent as " + text(c) + ".")
def receive():
c = ask_bits("7 bits received> ", 7)
if len(c) == 0:
print("Cancelled.")
return
r = hamming.correct(c)
layout(c)
if r[0] == 0:
print("All three checks pass: the data is " + text(hamming.data_of(c)) + ".")
else:
print("The checks that fail add up to " + str(r[0]) + ", so position " + str(r[0]) + " is flipped back: " + text(r[1]) + ", data " + text(hamming.data_of(r[1])) + ".")
def experiment():
d = ask_bits("4 data bits (like 1011)> ", 4)
if len(d) == 0:
print("Cancelled.")
return
while True:
s = trim(input("positions to flip (1 to 3 of 1-7, like 3 5)> "))
if s == "":
print("Cancelled.")
return
ps = positions_of(s)
if len(ps) > 0:
c = hamming.encode(d)
bad = hamming.flipped(c, ps)
r = hamming.correct(bad)
got = hamming.data_of(r[1])
print("sent " + text(c) + ", received " + text(bad) + " - " + str(len(ps)) + " flipped.")
if r[0] == 0:
print("7 bits: every check passes, so the decoder takes it as sent - data " + text(got) + ".")
else:
print("7 bits: the checks point at position " + str(r[0]) + "; flipping it back gives data " + text(got) + ".")
if got == d:
print(" That is right.")
else:
print(" That is wrong: " + text(d) + " was sent. The 7-bit code always assumes one flip, and cannot tell more from one.")
w = hamming.with_parity(c)
wbad = hamming.flipped(w, ps)
v = hamming.secded(wbad)
if v[0] == "two errors":
print("8 bits (an eighth bit making the word even): the checks fail but the word is still even, so two bits changed - detected, not corrected; ask again.")
elif v[0] == "corrected":
print("8 bits (an eighth bit making the word even): it looks like one flip, so it corrects it - data " + text(v[1]) + ".")
else:
print("8 bits (an eighth bit making the word even): every check passes - data " + text(v[1]) + ".")
if v[0] != "two errors" and v[1] != d:
print(" That is wrong too: to the eighth bit, three flips look like one.")
return
print("Type 1 to 3 different positions from 1 to 7, like 3 5.")
def table():
cs = hamming.codewords()
print(" data codeword")
for n in range(0, 16):
print(" " + text(cs[n][2:3] + cs[n][4:7]) + " " + text(cs[n]))
fewest = 16
for i in range(0, 16):
for j in range(i + 1, 16):
k = hamming.distance(cs[i], cs[j])
if k < fewest:
fewest = k
print("Any two codewords differ in at least " + str(fewest) + " places, so one flip leaves a word nearer the one sent than any other, and two flips can land nearer a different one.")
print("== Hamming code ==")
print("Hamming's (7,4) code: 4 data bits sent as 7, so one flipped bit can be found and put right.")
running = True
while running:
print("")
print("1) send 2) receive 3) flip bits and see 4) all 16 codewords 5) quit")
choice = trim(input("choice> "))
if choice == "1":
send()
elif choice == "2":
receive()
elif choice == "3":
experiment()
elif choice == "4":
table()
elif choice == "5":
running = False
else:
print("Pick a number from 1 to 5.")
print("Bye.")
hamming.eml
eml# P076 Hamming code - Hamming's (7,4) code: 4 data bits sent as 7, so that
# any one flipped bit can be found and put right. Positions 1 to 7; the
# parity bits sit at 1, 2 and 4, the data at 3, 5, 6 and 7. Parity bit p
# covers every position whose number has p in its binary form, so the
# three checks that fail spell out, in binary, the position that flipped.
# Bits are lists of 0 and 1; index 0 is position 1.
def xor(a, b):
return (a + b) % 2
def covers(p, pos):
# Whether parity bit p (1, 2 or 4) covers position pos: bit p of pos.
pos => n
p => q
while q > 1:
int((n - n % 2) / 2) => n
int(q / 2) => q
return n % 2 == 1
def encode(data):
# [d1, d2, d3, d4] -> the 7 bits [p1, p2, d1, p4, d2, d3, d4].
[0, 0, data[0], 0, data[1], data[2], data[3]] => c
for p in [1, 2, 4]:
0 => s
for pos in [1:7]:
if pos != p and covers(p, pos):
xor(s, c[pos - 1]) => s
s => c[p - 1]
return c
def syndrome(c):
# Re-run the three checks; each that fails adds its p. 0 means every
# check passes; otherwise it is the position a single flip would be at.
0 => out
for p in [1, 2, 4]:
0 => s
for pos in [1:7]:
if covers(p, pos):
xor(s, c[pos - 1]) => s
if s == 1:
out + p => out
return out
def data_of(c):
return [c[2], c[4], c[5], c[6]]
def correct(c):
# [the syndrome, the 7 bits with that position flipped back].
syndrome(c) => s
[0] * 7 => out
for i in [0:6]:
c[i] => out[i]
if s > 0:
xor(out[s - 1], 1) => out[s - 1]
return [s, out]
def flipped(c, positions):
# A copy of the bits with the given positions (1-based) flipped.
[0] * len(c) => out
for i in [0:len(c) - 1]:
c[i] => out[i]
for p in positions:
xor(out[p - 1], 1) => out[p - 1]
return out
def distance(a, b):
# The corpus case hamming-distance: how many positions differ.
0 => d
for i in [0:len(a) - 1]:
if a[i] != b[i]:
d + 1 => d
return d
def with_parity(c):
# The extended (8,4) code: an eighth bit makes the whole word even.
0 => s
for b in c:
xor(s, b) => s
return c + [s]
def secded(w):
# Decoding the 8-bit word: one flip is corrected; two are detected but
# cannot be corrected - the syndrome says something is wrong while the
# overall parity says an even number of bits changed. Returns
# [verdict, data or []] with verdict "ok", "corrected" or "two errors".
syndrome(w[0:7]) => s
0 => total
for b in w:
xor(total, b) => total
if s == 0 and total == 0:
return ["ok", data_of(w)]
if total == 1:
if s == 0:
return ["corrected", data_of(w)]
return ["corrected", data_of(correct(w[0:7])[1])]
return ["two errors", []]
def codewords():
# All 16 codewords, in the order of their data bits 0000 to 1111.
[] => out
for n in [0:15]:
[0, 0, 0, 0] => d
n => r
for i in [0:3]:
r % 2 => d[3 - i]
int((r - r % 2) / 2) => r
out + [encode(d)] => out
return out
Python projection (hamming.py)
def xor(a, b):
return (a + b) % 2
def covers(p, pos):
n = pos
q = p
while q > 1:
n = int((n - n % 2) / 2)
q = int(q / 2)
return n % 2 == 1
def encode(data):
c = [0, 0, data[0], 0, data[1], data[2], data[3]]
for p in [1, 2, 4]:
s = 0
for pos in range(1, 8):
if pos != p and covers(p, pos):
s = xor(s, c[pos - 1])
c[p - 1] = s
return c
def syndrome(c):
out = 0
for p in [1, 2, 4]:
s = 0
for pos in range(1, 8):
if covers(p, pos):
s = xor(s, c[pos - 1])
if s == 1:
out = out + p
return out
def data_of(c):
return [c[2], c[4], c[5], c[6]]
def correct(c):
s = syndrome(c)
out = [0] * 7
for i in range(0, 7):
out[i] = c[i]
if s > 0:
out[s - 1] = xor(out[s - 1], 1)
return [s, out]
def flipped(c, positions):
out = [0] * len(c)
for i in range(0, len(c)):
out[i] = c[i]
for p in positions:
out[p - 1] = xor(out[p - 1], 1)
return out
def distance(a, b):
d = 0
for i in range(0, len(a)):
if a[i] != b[i]:
d = d + 1
return d
def with_parity(c):
s = 0
for b in c:
s = xor(s, b)
return c + [s]
def secded(w):
s = syndrome(w[0:7])
total = 0
for b in w:
total = xor(total, b)
if s == 0 and total == 0:
return ["ok", data_of(w)]
if total == 1:
if s == 0:
return ["corrected", data_of(w)]
return ["corrected", data_of(correct(w[0:7])[1])]
return ["two errors", []]
def codewords():
out = []
for n in range(0, 16):
d = [0, 0, 0, 0]
r = n
for i in range(0, 4):
d[3 - i] = r % 2
r = int((r - r % 2) / 2)
out = out + [encode(d)]
return out