1
$\begingroup$

I am trying to understand hamming codes for single bit error correction. I understood all the things like hamming distance , k bit error detection and all basics for hamming codes. Also, I know the algorithm for error correction using hamming codes. I have read many answers from different stackexchange sites and also I fear that this question may be marked as duplicated. But I am not satisfied, I just know a procedure and don't know the intuition behind the idea.

Let's say we need to send a 4-bit message for which three parity bits will be used. Now the sequence will be p1 p2 m3 p4 m5 m6 m7 and my instructor is saying that p1 will be responsible for detecting errors in bits ( 1 , 3 , 5 , 7 ) , p2 for ( 2 , 3 , 6 , 7 ) and p4 for ( 4 , 5 , 6 , 7 ). Why is it so?

Why only $2^n$ position bits are selected for parity? How to visualize its working?

$\endgroup$

1 Answer 1

3
$\begingroup$

Hamming codes are designed to correct a single error. A valid codeword $p_1 p_2 m_3 p_4 m_5 m_6 m_7$ satisfies the constraints \begin{align} &p_1 \oplus m_3 \oplus m_5 \oplus m_7 = 0 \\ &p_2 \oplus m_3 \oplus m_6 \oplus m_7 = 0 \\ &p_4 \oplus m_5 \oplus m_6 \oplus m_7 = 0 \end{align} (This is arranged simply by choosing $p_1 = m_3 \oplus m_5 \oplus m_7$, and similarly for $p_2,p_4$).

If a single error occurs in one of the positions $1,3,5,7$, then the first parity check will fail. Similarly, if a single error occurs in one of the positions $2,3,6,7$ then the second parity check will fail, and if a single error occurs in one of the positions $4,5,6,7$ then the third parity check will fail. Each single error is associated with a different pattern of failed parity checks, and this allows us to locate the error and correct it.

More generally, a Hamming code of length $2^n-1$ has $2^n-n-1$ message bits and $n$ parity checks, and is able to detect and correct one error. These parameters are optimal, in the sense that if a code has $m$ message bits, $n$ parity checks and is able to correct one error, then $m \leq 2^n - n - 1$. To see this, let $w_1,\ldots,w_{2^m}$ be all possible codewords. Let $B(w_i)$ consists of $w_i$ together with all words obtained by flipping a single bit. Given a word in $B(w_i)$, we can detect whether any error occurred, and if so, fix it, recovering $w_i$. This shows that the balls $B(w_i)$ are disjoint from one another. Each one contains $1 + (m + n)$ words, and so the union of all balls contains $2^m (1 + m + n)$ words. Since every word has length $m + n$, the number of possible words is $2^{m + n}$, resulting in the inequality $$ 2^m (1 + m + n) \leq 2^{m + n}, $$ or $1 + m + n \leq 2^n$, that is, $m \leq 2^n - n - 1$.

For general $n$, the parity checks of Hamming codes are constructed as follows. Number the positions of the bits from $1$ to $2^n-1$, and think of them as words of length $n$ over $\{0,1\}$ different from $0\cdots0$. For $i = 0,\ldots,n-1$, we have a parity check stating that the XOR of all bits at indices $\ell \in \{0,1\}^n$ satisfying $\ell_i = 1$. We choose indices $2^0,2^1,\ldots,2^{n-1}$ as parity bits (the analogs of $p_1,p_2,p_4$ above), and the rest as message bits. We can calculate the parity bits from the message bits as above.

If we start with a codeword and flip the bit at position $\ell$, then the $i$th parity check will fail iff $\ell_i = 1$. This enables us to correct the error, since its position is spelled out by the parity checks.

$\endgroup$
2
  • $\begingroup$ I don't understand what do you mean by for a total of $2^m(1+m+n)$ $\endgroup$ Sep 12, 2021 at 6:46
  • $\begingroup$ This is the total number of words in all balls. $\endgroup$ Sep 12, 2021 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.