Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\def\code{\mathit{code}}
\)
A possible $(7,4)$ 1-error correcting linear code is
\[f(b_1,\,b_2,\,b_3,\,b_4)\,=\, (b_1+b_2+b_3,\, b_1+b_2+b_4,\,
b_1+b_3+b_4).\]
\[
\begin{array}{ll}
\code(b_1,\,b_2,\,b_3,\,b_4)\,=\, & (b_1,\,b_2,\,b_3,\,b_4,\, b_1+b_2+b_3,\\
& b_1+b_2+b_4,\, b_1+b_3+b_4).
\end{array}
\]
The operations $+$ and $-$ on bits are here equal to the operation $xor$.
if $r=3,k=4$ and
$$A =
\left(\begin{array}{cccc}
1 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 0 & 1 & 1
\end{array}\right)
$$
then $\code_A$ is the code from the previous example.
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.
Observation
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.
References
-
R. W. Hamming,
Error detecting and error correcting codes,
Bell System Tech. J. 29 (1950) 147-160.
