What is the decoding error percentage of (7,4) Hamming code?

Question

The decoding error occurs where there are more than 1 bits that are flipped. Hence, if the probability that a bit is flip is $10\%$, then shouldn't the decoding error percentage be $1-0.1\cdot0.9^6\cdot7-0.9^7 = 0.149$? Why my textbook (by MacKay) claims that it is $7\%$?

Answer 1

Let $E$ denote the event that the output of the decoder is a codeword that is not the same as the transmitted codeword, and let $E_i$ denote the event that the $i$-th data bit in the output codeword differs from the $i$-th data bit of the transmitted codeword. Clearly we have that $$E = E_1 \cup E_2 \cup \cdots \cup E_k.\tag{1}$$ since if none of the $E_i$ occur, then the data bits in the output codeword are all correct and so the output codeword must be the same as the transmitted codeword.

Now, in general, the events $E_i$ are neither independent events nor equiprobable events. The Bit Error Rate (BER) for the decoded data bits, denoted by $P_b$ here, is defined as the arithmetic average of the $k$ $P(E_i)$ values. It is generally quite time-consuming to determine the values of the $P(E_i)$ or their average $P_b$ except for codes of very short blocklengths, whereas $P(E)$, the probability that the decoder output is not the same as the transmitted codeword, is easier to determine (or overbound for bounded-distance decoders that are prone to decoder failure). It is straightforward to show that $$\frac 1k P(E) \leq P_b \leq P(E)\tag{2}$$ which in the instance that is puzzling the OP tells us that the BER must be between $3.725\%$ and $14.9\%$. More can be said in this particular case, however, the codewords of a $[7,4]$ Hamming code are very closely related to what is called a biorthogonal signal set in the communications literature (the codewords of the $[8,4]$ extended Hamming code are exactly a biorthogonal signal set). For a biorthogonal signal set, the BER is very nearly $\frac 12P(E)$, and so the $7\%$ BER claimed in the Mackay text can be explained as being consistent with this result, with some differences because the $[7,4]$ Hamming code is not quite a biorthogonal signal set, and because $P_b$ is not exactly $\frac 12 P(E)$ for a biorthogonal signal set.

Masochists who really want to delve into the details can find information about orthogonal and biorthogonal signal sets and their relationship to first-order Reed-Muller codes (of which class the $[8,4]$ extended Hamming code is an example) can find some basic information on pp. 161-180 of this ancient Lecture Note of mine.