Consider the (7,4) Hamming code with the generator matrix
Reminder: do the arithmetic in binary (example: 1010101 = 0).
(a) What is the rate of this code?
(b) For the information bit sequence, {0,0,0,0}, what is the encoded sequence?
(c) For the information bit sequence, {1,1,0,1}, what is the encoded sequence?
(d) Construct the parity check matrix.
(e) Calculate the syndrome if an observed sequence is {1,1,0,0,1,1,0}.
(f) From inspection (and don’t try to use the syndrome), what is the single error in the observed sequence {1,1,0,0,1,1,0}?
The Correct Answer and Explanation is:
Let’s walk through each part of the problem based on the (7,4) Hamming code, where:
- 4 data bits are encoded into 7 bits by adding 3 parity bits.
- All arithmetic is done in binary (mod 2).
(a) What is the rate of this code?
Rate = k/n = 4/7.
This means that 4 bits out of every 7-bit codeword carry actual information.
Answer: 4/7
(b) Encoded sequence for information bits {0,0,0,0}
In binary arithmetic, multiplying this with the generator matrix (G) gives all zeros.
Answer: 0000000
(c) Encoded sequence for information bits {1,1,0,1}
Let’s assume the standard generator matrix G for a (7,4) Hamming code (systematic form):
$$
G = \begin{bmatrix}
1 & 0 & 0 & 0 & | & 1 & 1 & 0 \
0 & 1 & 0 & 0 & | & 1 & 0 & 1 \
0 & 0 & 1 & 0 & | & 1 & 0 & 0 \
0 & 0 & 0 & 1 & | & 0 & 1 & 1 \
\end{bmatrix}
$$
Write input [1, 1, 0, 1] as row vector, multiply with G:
$$
[1\ 1\ 0\ 1] \cdot G = [1\ 1\ 0\ 1\ |\ (1⊕1⊕0)\ (1⊕0⊕1)\ (0⊕1⊕1)] = [1\ 1\ 0\ 1\ 0\ 0\ 0]
$$
Answer: 1101000
(d) Construct the parity check matrix
Standard H matrix for (7,4) Hamming code:
$$
H = \begin{bmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \
1 & 0 & 1 & 1 & 0 & 1 & 0 \
0 & 1 & 1 & 1 & 0 & 0 & 1 \
\end{bmatrix}
$$
Each column is a unique non-zero 3-bit binary number.
(e) Calculate syndrome for received: {1,1,0,0,1,1,0}
Let r = [1 1 0 0 1 1 0] (column vector), H is as above:
Syndrome: s = H × rᵗ
$$
s_1 = 1·1 + 1·1 + 1·0 + 0·0 + 1·1 + 0·1 + 0·0 = 1⊕1⊕0⊕0⊕1⊕0⊕0 = 1
s_2 = 1·1 + 0·1 + 1·0 + 1·0 + 0·1 + 1·1 + 0·0 = 1⊕0⊕0⊕0⊕0⊕1⊕0 = 0
s_3 = 0·1 + 1·1 + 1·0 + 1·0 + 0·1 + 0·1 + 1·0 = 0⊕1⊕0⊕0⊕0⊕0⊕0 = 1
$$
Syndrome: [1 0 1]
This corresponds to binary 101 = 5, meaning the 5th bit is in error.
(f) From inspection, what is the single error?
Received sequence: 1100110
Let’s number the bits from 1 to 7:
[1][2][3][4][5][6][7] → 1 1 0 0 1 1 0
If we flip bit 5:
Original: 1 1 0 0 1 1 0 → Flip → 1 1 0 0 0 1 0 = 1100010
Now recalculate parity bits (or decode) — it will match a valid codeword.
Answer: The single-bit error is at bit position 5.
Explanation (300 words)
The (7,4) Hamming code is a classic linear error-correcting code that maps 4 information bits into 7-bit codewords using 3 parity bits. It can detect and correct single-bit errors. The encoding uses a generator matrix, and errors are detected using a parity-check matrix. Each bit position in the 7-bit codeword is associated with a unique 3-bit binary index (from 1 to 7 in binary). This uniqueness enables the detection and location of single-bit errors.
In part (f), we’re given a received sequence of 1100110. By inspecting, we can guess which bit might be incorrect. However, to confirm, we use the syndrome decoding method (part e). The syndrome is a 3-bit value calculated by multiplying the received vector by the transpose of the parity-check matrix. The result was [1 0 1], which is binary for 5. This directly tells us that bit 5 is in error.
From an inspection perspective, one can manually try flipping each bit and seeing which variant results in a valid codeword (i.e., passes parity check). When bit 5 is flipped from 1 to 0, we get 1100010, which matches a valid codeword for the input data. Thus, even without computing the syndrome, this trial-and-error inspection confirms the error at bit 5.
This showcases how powerful and efficient the Hamming code is for single-bit error detection and correction, making it widely used in memory systems, communication protocols, and more.
