Assignment — Hamming code and error correction

In many digital courses the first written assignment is not a circuit: it is a review of Richard Hamming plus a worked Hamming code (detect and correct one bad bit). Both halves are here — for the paper and for the exam.

1. Historical review (the paper)

Do not paste this section verbatim: rewrite and cite.

Richard Wesley Hamming (1915–1998)

Born in Chicago. Ph.D. in mathematics (University of Illinois, 1942).
Manhattan Project (Los Alamos): he ran calculations on electromechanical computers. Weekend jobs died on bit errors; he had to redo the work by hand. That frustration is the origin of the code.
Bell Labs (1946–1976), with Shannon and others. In 1950 he publishes Error Detecting and Error Correcting Codes in the Bell System Technical Journal.
Hamming distance: how many bits you must flip to go from one valid word to another. Minimum distance 3 → correct 1 error (or detect 2).
Turing Award 1968. IEEE Hamming Medal. Quote often used in reports: “The purpose of computing is insight, not numbers.”

The problem he solved

A single parity bit only detects (odd number of ones → “something failed”) and the machine halted. Hamming wanted the system to name which bit and invert it. Parity bits sit at powers of 2: each parity votes on a subset, and the vote pattern is the address of the error (the syndrome).

Typical rubric

Who Hamming was and which lab he worked in (not “a scientist”).
Detect vs correct.
Hamming distance with a 4-bit example.
One (7,4) code worked by hand (next section).
One modern use: ECC RAM, satellites, QR, storage — one sentence, not a catalogue.

Usual length: 3–6 pages. History ≈ 40 %, numeric example ≈ 40 %, closing ≈ 20 %.

2. The Hamming (7,4) code

(7,4) = 4 data bits + 3 parity bits → 7-bit word. Corrects 1 error (SEC). Two errors need an extra overall parity (extended Hamming).

Positions 1 through 7. Powers of 2 are parity:

Position	1	2	3	4	5	6	7
Role	(p_1)	(p_2)	(d_1)	(p_4)	(d_2)	(d_3)	(d_4)

Even parity (usual in class): each (p) makes its group have an even number of ones.

(p_1): positions 1, 3, 5, 7
(p_2): positions 2, 3, 6, 7
(p_4): positions 4, 5, 6, 7

Example: data `1011`

Place data at 3,5,6,7 → 1 0 1 1
Incomplete word: _ _ 1 _ 0 1 1

(p_1) (1,3,5,7): p1, 1, 0, 1 → two ones → (p_1 = 0)
(p_2) (2,3,6,7): p2, 1, 1, 1 → three ones → (p_2 = 1)
(p_4) (4,5,6,7): p4, 0, 1, 1 → two ones → (p_4 = 0)

Sent word: 0 1 1 0 0 1 1

Correction: the syndrome

Recompute the three parities. An odd group sets that syndrome bit to 1. The binary number (p_4 p_2 p_1) is the error position (0 = no error).

Suppose 0 1 1 0 0 1 0 arrives (bit 7 dropped).

(p_1): 0,1,0,0 → odd → (s_1 = 1)
(p_2): 1,1,1,0 → odd → (s_2 = 1)
(p_4): 0,0,1,0 → odd → (s_4 = 1)

Syndrome (s_4 s_2 s_1 = 111_2 = 7) → flip bit 7 → 0110011.

3. Link to gates

Even parity of 4 bits is cascaded XOR: (p = a \oplus b \oplus c \oplus d). In hardware that is XOR gates (7486 in TTL). Hamming is parity several times, on subsets.

How to turn it in

Cover page with your name and course title (Logical systems / Digital — any university).
Cite Hamming 1950 and Floyd or Rojas on codes (CALETAS links above).
A diagram of positions 1–7, not only prose.
A second example other than 1011.

Then Next continues to Boolean algebra. The Proteus paper is partial IV (end of theory); in the sidebar it sits with this one under Assignments.