CLR cover

Additional Problem 7: 1-Error Correcting Linear Hamming Codes (Preliminary version)

\( \def\Bin{\mathit{Bin}} \def\Codes{\mathit{Codes}} \def\Ham{Ham} \)

Assume we are sending binary messages of length $n$, however we allow a single mismatch error. In order to correct a potential mismatch-error the last $r$ bits of a message are extra checking bits. Hence the real message $u$ has $k=n-r$ bits and the remaining suffix of length $r$ equals $f(u)$, for a simply computable function $f$.

We assume later here that $n=2^r-1, k=n-r$, for $r\gt 2$, hence the size $r$ of the checking part is only logarithmic. The constructed codes are called $(n,k)$-codes.


For $n=2^r-1,\, k=n-r$ we have $|\Bin^{(2)}_r|=k$, where $\Bin^{(2)}_k$ is the set of all binary words of length $k$ containing at least 2 ones. This property is crucial in our construction.

Denote by $\Bin_k$ be the set of all binary words of length $k$. Let $$\code(u)\,=\,u\cdot f(u),\ \ \Codes_n\,=\,\{\,\code(u)\,:\, u\in \Bin_k\}$$

Our construction uses an elementary linear algebra. Each binary string can be identified with a binary vector, hence we can use operation $f_A(w)=A\times w^T$ as the multiplication of a matrix $A$ by transposition of the vector corresponding to the string $u$. We have

$$\code_A(w)\,=\, w\cdot f(w)\,=\, w\cdot (A\times w^T)$$

The elements of $\code_n^A(u)$ are called code-words, denote their set by $\Codes^A_n$. In order to be able to 1-error correct messages we need the inequality \[(*)\ \ \ \min\,\{\Ham(u,v)\;:\; u,v\in \Codes^A_n, u\ne v\,\}\geq 3,\] where $\Ham(u,v)$ is the Hamming distance: the number of mismatch positions. The set $\Codes_n$ is called a Hamming code iff the inequality $(*)$ holds.

Construct a matrix $A$ such that $\Codes^A_n$ is a Hamming code - prove the property $(*)$.

Take $A$ whose columns are all distinct binary strings of length $n-k$ with at least two ones, as in the example for a (7,4)-code.

Show how to correct the message assuming there is at most one mismatch error.