From a Received Word to a Correction
A received seven-bit word may differ from the transmitted codeword because one bit was flipped. For the binary \([7,4,3]\) Hamming code, the parity-check matrix turns that discrepancy into a short three-bit calculation: the syndrome. When at most one bit has changed, a nonzero syndrome identifies the position of the error. After correcting that bit, the four information bits can be read from their designated positions.
All entries and arithmetic below are in \(\mathbb{F}_2=\{0,1\}\), where addition and multiplication are performed modulo \(2\). In particular, \(1+1=0\). A seven-bit word is treated as a column vector, but we write its entries in order as \(x_1x_2\cdots x_7\); position 1 is the leftmost bit. Use the parity-check matrix whose \(j\)th column records the binary labels of position \(j\), with the \(1\)'s place first, the \(2\)'s place second, and the \(4\)'s place third:
Its columns \(\mathbf{h}_1,\dots,\mathbf{h}_7\) are exactly the seven distinct nonzero vectors in \(\mathbb{F}_2^3\). The code is the null space of this matrix: a word \(\mathbf{c}\) is a codeword exactly when \(\mathbf{H}\mathbf{c}=\mathbf{0}\). In bit equations, that condition is
For any received word \(\mathbf{r}\), its syndrome is \(\mathbf{s}=\mathbf{H}\mathbf{r}\). The syndrome is zero precisely when the received word satisfies all three parity checks. A nonzero syndrome records which checks fail, and, under the single-error assumption, points to the changed position.
Why a Syndrome Locates One Error
The decoding rule follows from the matrix-vector product. Suppose the transmitted word is \(\mathbf{c}\) and the received word is \(\mathbf{r}=\mathbf{c}+\mathbf{e}\), where \(\mathbf{c}\) is a codeword. If there is no error, \(\mathbf{e}=\mathbf{0}\). If exactly bit \(j\) is flipped, \(\mathbf{e}=\mathbf{e}_j\). Since \(\mathbf{H}\mathbf{c}=\mathbf{0}\), the syndrome is \(\mathbf{H}\mathbf{r}=\mathbf{H}\mathbf{e}\).
- syndrome \(\mathbf{s}=\mathbf{0}\) means no bit was changed;
- syndrome \(\mathbf{s}=\mathbf{h}_j\ne\mathbf{0}\) means bit \(j\) was changed, and adding \(\mathbf{e}_j\) to \(\mathbf{r}\) recovers \(\mathbf{c}\).
Proof. If no bit was changed, then \(\mathbf{r}=\mathbf{c}\), so \(\mathbf{s}=\mathbf{H}\mathbf{c}=\mathbf{0}\). If exactly bit \(j\) was changed, then \(\mathbf{r}=\mathbf{c}+\mathbf{e}_j\), so \(\mathbf{s}=\mathbf{H}\mathbf{r}=\mathbf{H}\mathbf{c}+\mathbf{H}\mathbf{e}_j=\mathbf{0}+\mathbf{h}_j=\mathbf{h}_j\). Every column is nonzero, so this syndrome is not zero. Because the columns are distinct, it identifies exactly one position \(j\). Adding \(\mathbf{e}_j\) to the received word flips that bit back: \(\mathbf{r}+\mathbf{e}_j=\mathbf{c}+\mathbf{e}_j+\mathbf{e}_j=\mathbf{c}\), since \(1+1=0\) in \(\mathbb{F}_2\). Thus the stated rule both locates and corrects the error under the at-most-one-error assumption. \(\square\)
To convert a syndrome \((s_1,s_2,s_3)^\top\) into a position number for this particular matrix, use \(s_1+2s_2+4s_3\). This reads the row entries in the order used to construct the columns. For instance, \((1,1,0)^\top\) labels position \(1+2=3\), so it is column \(\mathbf{h}_3\). This numerical shortcut depends on the stated column ordering; matching the syndrome directly against the displayed columns is always unambiguous.
Systematic Encoding and Information Positions
For this matrix, the parity positions are 1, 2, and 4. The information positions are 3, 5, 6, and 7. Write a word in the order \((p_1,p_2,d_1,p_4,d_2,d_3,d_4)\), where the \(p_i\)'s are parity bits and \(d_1,d_2,d_3,d_4\) are information bits. Solving the three parity equations for the parity bits gives
Proof. Choose any four information bits and define \(p_1,p_2,p_4\) by the displayed formulas. The first parity-check equation becomes \(p_1+d_1+d_2+d_4=0\); substituting \(p_1=d_1+d_2+d_4\) makes its left side \(0\), because each bit occurs twice. The second and third equations also become \(0\), by substituting their respective formulas. The resulting word is therefore a codeword. Conversely, if a word is a codeword, its first parity-check equation forces \(p_1=d_1+d_2+d_4\); its second forces \(p_2=d_1+d_3+d_4\); and its third forces \(p_4=d_2+d_3+d_4\). Thus the information bits determine the parity bits uniquely, and every codeword has the stated form. \(\square\)
After correcting a received word, recover its information by reading positions 3, 5, 6, and 7, in that order. Do not extract the information bits before correcting: an error may have changed one of those positions.
Worked Decodings
Worked Example: Correcting an Error in Position 6
Encode information bits \(1011\), then decode the received word \(0110001\).
For \(d_1=1,d_2=0,d_3=1,d_4=1\), the parity bits are
The codeword is \(\mathbf{c}=0110011\). Check its parity equations: positions \(1,3,5,7\) give \(0+1+0+1=0\); positions \(2,3,6,7\) give \(1+1+1+1=0\); and positions \(4,5,6,7\) give \(0+0+1+1=0\).
The received word \(0110001\) differs from \(\mathbf{c}\) in position 6. Its syndrome, computed from the three checks, is
Therefore flip position 6. The corrected word is \(0110011\). Its syndrome is \(\mathbf{0}\), as checked above. Reading positions 3, 5, 6, and 7 gives \(1011\), the information bits used to form the codeword.
Worked Example: A Zero Syndrome
Decode the received word \(1011010\), assuming at most one bit was changed.
Compute the checks directly:
The word already satisfies all parity checks, so under the at-most-one-error assumption no bit was changed. The information bits are the entries in positions 3, 5, 6, and 7: \(1,0,1,0\). Check by encoding \(d_1=1,d_2=0,d_3=1,d_4=0\): \(p_1=1+0+0=1\), \(p_2=1+1+0=0\), and \(p_4=0+1+0=1\). These give \(1011010\), exactly the received word.
Worked Example: Correcting an Error in an Information Bit
Decode \(0101100\), assuming at most one error, and recover its information bits.
The syndrome is
This calculation would be incorrect: the third check uses positions 4, 5, 6, and 7, whose entries are \(1,1,0,0\), but the first check uses positions 1, 3, 5, and 7. Recomputing each row carefully for \(\mathbf{r}=0101100\) gives
The syndrome identifies position 3, so flip that bit: \(0101100\) becomes \(0111100\). Verify the correction: its first check is \(0+1+1+0=0\), its second is \(1+1+0+0=0\), and its third is \(1+1+0+0=0\). The corrected word is a codeword. Its information bits, from positions 3, 5, 6, and 7, are \(1,1,0,0\). Encoding these bits gives \(p_1=1+1+0=0\), \(p_2=1+0+0=1\), and \(p_4=1+0+0=1\), producing \(0111100\) as required.
Scope of the Rule and a Common Pitfall
The theorem guarantees decoding when zero or one bit has changed. It does not guarantee that a word with multiple errors will be corrected to the transmitted word. A multiple-error syndrome can equal a column of \(\mathbf{H}\); the single-error rule would then point to a position even though that explanation does not describe the actual changes. The assumption about the number of errors is part of the decoding method, not an optional detail.
Common pitfall: mixing up syndrome order and bit position. With the matrix used here, the syndrome \((1,1,0)^\top\) is column 3 and identifies position 3. Reading the entries as a usual left-to-right binary numeral and calling it position 6 would be wrong for this column convention. The correction is to match all three syndrome entries to the displayed columns, or to use the stated rule \(s_1+2s_2+4s_3\). Also perform every syndrome sum modulo \(2\): for example, \(1+1=0\), not \(2\).
The practical sequence is short: compute \(\mathbf{H}\mathbf{r}\), match a nonzero syndrome to its column, flip that position, and check that the corrected word has zero syndrome. Then read positions 3, 5, 6, and 7 to recover the information bits. Keeping the parity-check convention visible prevents both arithmetic errors and bit-order errors.
Check Your Understanding
Use the displayed parity-check matrix and assume at most one bit has been changed in each decoding question.
- Compute the syndrome of \(1100101\). If it is nonzero, which position does it identify?
- Encode the information bits \(0101\) in systematic form and verify all three parity checks.
- A received word has syndrome \((0,1,0)^\top\). Which bit should be flipped, and why?
- After correcting \(0011011\), state which four positions contain the information bits.
- Why does a zero syndrome alone not guarantee that no bits changed if multiple errors are allowed?
