CLR cover

Problem 132: 1-error correcting linear Hamming codes

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

Sending a message through a noisy line may produce errors. The goal of the problem is to present a method for correcting a message in which only one error is assumed to occur. A message is a word of bits. To allow checking and correcting a possible transmission error in a word $w \in \{\sa{0},\sa{1}\}^*$, a very short word depending on it and easily computable, $f(w)$, is appended to $w$. The complete message to be sent is then $\code(w)=w\cdot f(w)$.

We assume that the length of a message $w$ is of the form $k=2^r-r-1$, $|f(w)|=r$ and the total length of the code is then $n=k+r=2^r-1$, for an integer $r\gt 2$. Hence, the size $r$ of the additional part of the code is only logarithmic according to length of the message. Such codes are called $(n,k)$-codes. We consider only binary words and use linear algebra methods. A word $b_1b_2\cdots b_k$ is identified with the vector $[b_1,b_2,\ldots, b_k]$.

The set of length-$n$ binary words containing at least two occurrences of $\sa{1}$ has size $k=2^r-r-1$.

We construct $f(w)$ as $M\times w^T$, multiplication of a $r\times k$ matrix $M$ by the transposed vector associated with $w$. Then, $$\code^M(w) = [w,f(w)] = [w,M\times w^T].$$

The length-$n$ elements of $\Codes^M_n=\{\code_n^M(w):\, w\in \{0,1\}^k\}$ are called codewords and the set $\Codes^M_n$ is called a Hamming code if $$(*)\ \ \ \min\,\{\ham(u,v)\;:\; u,v\in \Codes^M_n, u\ne v\,\}\geq 3,$$ where $\ham(u,v)$ is the Hamming distance (number of mismatches).

Build a matrix $M$ for which $\Codes^M_n$ is a Hamming code.

Use the observation.

Show how to correct the message assuming it contains at most one error.

References