Exercise 1.6: (7, 4) Hamming Code
In 1962, Richard Wesley Hamming specified a class of binary block codes that differ in the number $m$ of check bits supplied. The codeword length is always $n = 2^m - 1$. The information word consists of $k = n - m$ bits:
- $m = 2$: $\text{(3, 1)}$ Hamming code ⇒ identical to $\text{RC (3, 1)}$,
- $m = 3$: $\text{(7, 4)}$ Hamming code,
- $m = 4$: $\text{(15, 11)}$ Hamming code,
- $m = 5$: $\text{(31, 26)}$ Hamming code, etc.
In the course of this task there are questions
- to the code size $ |\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}|$,
- to the code rate $R$, and
- to the minimum distance $d_{\rm min}$.
Furthermore, we want to clarify whether the $\underline{u}_{i} ⇒ \underline{x}_{i}$ given for this task by its code table $\text{(7, 4)}$-Hamming code is systematic, and whether it is a so-called "perfect code". The running index can take the values $i = 1, \text{...}\hspace{0.05cm} , 2^k =16$ .
One speaks of a perfect code if the following condition is satisfied:
- $$2^k = \frac{2^n} {\sum_{f=0}^t {n \choose f}}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
Here $t$ denotes the number of correctable errors. For odd minimum distance $d_{\rm min}$ holds:
- $$ t = \frac{d_{\rm min}-1 } {2} \hspace{0.05cm}.$$
The interpretation to this condition can be found in the sample solution.
Hints:
- This exercise belongs to the chapter Examples of Binary Block Codes.
- Reference is made to the chapter Hamming Codes.
- For this Hamming code, different test equations were used than in the theory section. Therefore, the code tables also differ.
- In the Exercise 1.7, where the same code is used, the chart of the check equations is given.
Questions
Solution
- From the equation $|C| = 2^k$ it follows that $\underline{k = 4}$.
- The length of each codeword is $\underline{n = 7}$.
- Thus, the code rate is $\underline{R = 4/7} = 0.571$.
(2) Correct YES:
- Each codeword $\underline{x}$ first contains the $k = 4$ bits of the information word $\underline{u}$. This is followed by $m = 3$ check bits:
- $$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_5,x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_3) \hspace{0.05cm}.$$
- This corresponds exactly to the definition of a systematic code .
(3) For any Hamming code, the minimum distance $d_{\rm min} \underline{= 3}$.
- From the table, you can see that the minimum Hamming_Weight (the number of ones in a codeword) is equal to 3.
- A linear code, in fact, also includes the zero word, so that holds:
- $$d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}') = \min_{\underline{x} \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} }\hspace{0.1cm}w_{\rm H}(\underline{x}) = 3 \hspace{0.05cm}.$$
(4) The specification $d_{\rm min} = 3$ means that $\underline{e = 2}$ errors can be detected and $\underline{t = 1}$ errors can be corrected.
(5) Correct is YES:
- The condition for a perfect code is according to the specification:
- $$ 2^m = {\sum_{f=0}^t {n \choose f}} \hspace{0.05cm}.$$
- In the (7, 4)-Hamming code considered here, $n = 7$, $m = 3$, and $t = 1$, giving a value of 8 on both sides of the equation:
- $$ 2^3 = 8\hspace{0.05cm}, \hspace{0.35cm} {\sum_{f=0}^1 {7 \choose f}} = {7 \choose 0} + {7 \choose 1} = 1 + 7 = 8 \hspace{0.05cm}.$$
(6) Correct statements 2 and 3:
- If there were a channel code with finite codeword length $n$ that made the block error probability zero for all channels, it would not only be perfect, but a miracle.
- But due to the channel coding theorem, ${\rm Pr(block error)} = 0$ is not even possible with finite $n$.
Let's illustrate statement 2 with a graph. Here, the high-dimensional space is shown in a highly simplified way (in 2D). We assume the numerical values $k = 4$, $n = 7$, $m = 3$ and $t = 1$ of the (7, 4, 3)-Hamming code:
- For the receive word, $2^7 = 128$ points are possible in 7-dimensional space. The red dots mark the $2^4 = 16$ valid codewords.
- The circles include 8 points each, namely a valid codeword and $n = 7$ receive words after only one error, which are assigned to exactly this codeword during decoding.
- Total there are $2^4 = 16$ such circles. Therefore, because of $128 = 16 - 8$, not a single receive word $\underline{y}$ lies outside such an assignment circle.
Also the last statement is true, which shall be shown exemplarily for $d_{\rm min} = 4$:
- Hereby also only $t = 1$ error can be corrected.
- If a receive word $\underline{y}$ differs from permissible code words in two bits, this point is not to be assigned to any circle. Then there are also points outside the circles and the condition of a perfect code is no longer fulfilled.
(7) Correct are statements 1, 2, 3 and 5:
- All Hamming codes have the minimum Hamming distance $d_{\rm min} = 3$ ⇒ $t = 1$.
- At the same time, any $(n, k)$ Hamming code can also be written as a $(2^m - 1, 2^m - 1 - m)$ code, where $m = n - k$ indicates the number of check bits.
- Thus, the equation of a perfect code is always satisfied:
- $${\sum_{f=0}^1 {n \choose f}} = 1 + n = 2^m \hspace{0.05cm}.$$
Where:
- $m = 2$: (3, 1) Hamming code, ⇒ identical to RC (3, 1),
- $m = 3$: (7, 4) Hamming code,
- $m = 4$: (15, 11) Hamming code,
- $m = 5$: (31, 26) Hamming code,
- $m = 6$: (63, 57) Hamming code,
The repetition code with $n = 5$ also satisfies the condition. With $d_{\rm min} = 5$, $t = 2$ and $m = 4$ we obtain:
- $${\sum_{f=0}^2 {5 \choose f}} = 1 + 5 + 10 = 16 = 2^m \hspace{0.05cm}.$$
The other repetition codes (RC) with odd $n$ are also perfect, but not with even $n$: RC (4, 1), RC (6, 1), etc. This has already been justified in the sample solution to the subtask (6).
