Ideas of Hamming Code

Problem: Want to transmit n bits, which we call data bits. But the transmission process can corrupt the bits. How to detect if there is corruption.

Assumption: The transmission process corrupts at most 1 bit, also called bit flip, i.e., changing 0 to 1 or 1 to 0.

Solve the problem under this assumption and then consider worse situations later (not included in the current notes). In any case, we cannot allow too much corruption. Sometimes you just have to improve the medium of transmission first.

Idea: Parity check.
Transmit n+1 bits. The n data bits and 1 more bit such that the sum of the all transmitted bits is 0 modulo 2.

When the receiver receives the bits, add them up modulo 2. If the result is 0, then no corruption. If the result is 1, then there is corruption and ask the sender to send again and pray the next time there is no corruption.

New problem: Too passive! The receiver wants to be able to detect if there is corruption and, in addition, wants to determine which bit is flipped and thus will be able to correct it.

Idea: Put in more parity checks and the combo of failed parity checks somehow should pinpoint where the corruption is.

Estimate how many parity checks are needed: Transmit n+r bits: n bits are the data bits and r bits for parity checks.

Total n+r+1 outcomes: one of the n+r bits is corrupted or nothing is corrupted. The r bits for parity checks can represent 2^{r} numbers. Thus given n, we choose r such that 2^{r} \ge n+r+1.

Need a dictionary from combo of failed checks to position of corrupted bit: (If all parity checks pass, then there is no corruption.)

Label the positions of all total bits: 1,2,3,\ldots,n+r. Set P := \{1,2,3,\ldots,n+r \}. Let C be the subset of P corresponding to the positions of the parity check bits. We will choose C appropriately later. Let v_{i} denote the value of the i-th bit for i\in P.

For j\in C, we want to associate a subset P_{j} of P such that j\in P_{j}. We set v_{j} to be the number such that \sum_{i\in P_{j}} v_{i} = 0 modulo 2, i.e., the j-th parity check checks the bits at positions in P_{j}.

When the receiver receives the bits, they find which parity checks fail, in other words, they find the subset C' of C such that for j\in C', \sum_{i\in P_{j}} v_{i} \neq 0 modulo 2 and for j\in C\setminus C', \sum_{i\in P_{j}} v_{i} = 0 modulo 2. We want to choose P_{j}’s appropriately so that only the flip of one particular bit can result in having C' as the set of failed parity checks.

How to choose P_{j}’s:

There is an ingenious way devised by Hamming for the choice of C and P_{j} for j\in C. Set \begin{equation*} C := \{ 1, 10, 100 ,\ldots \} \end{equation*} where the numbers are in radix 2. Set \begin{equation*} P_{j} := \{ i\in P \,\vert\,i \mathop{\mathrm{\mathrm{AND}}}j \neq 0 \} = \{ \text{number of the form $*\cdots * 1 * \cdots *$, with the $1$ at location $j$} \} \end{equation*} where \mathop{\mathrm{\mathrm{AND}}} is the bitwise AND operator the numbers are in radix 2.

Then if C' is the set of failed parity checks, then \sum_{a\in C'} a is the position of the bit that is corrupted. (If the sum is 0, this means that there is no corruption.)