The problem below is based on the Coding Theory, specifically on Reed-Muller codes (RM codes). These are linear codes whose codewords have size $2^{n}$ for some $n \in \mathbb{Z}^{+}$. Here the alphabet is
$\{0,1\},$ so the field is $\mathbb{Z}_{2}$ and all arithmetic is done modulo $2$.
The $2^{n}$ -bit RM code is defined as the code space spanned by the $n+1$ elementary codewords. These elementary codewords have a specific pattern explained below with examples. For $n=2,3$ and $4$ these are (written as column vectors):
$n=2 \quad\left[\begin{array}{lll}
1 & 0 & 0 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
1 & 1 & 1
\end{array}\right],$ $n=3\left[\begin{array}{llll}
1 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 1
\end{array}\right],$ $n=4\left[\begin{array}{lllll}
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 & 1
\end{array}\right].$
Let $C$ be the $2^{n}$ -bit RM code space (the span of the elementary codewords above). I want to show that any two distinct codewords in $C$ have distance $2^{n-1}$ (that is, they differ in $2^{n-1}$ digits).
Can you help, can you add an answer? Thanks…
Best Answer
We proceed by induction noting that this is true for $n=2$ by inspection. Now as assume it's true for natural $k$ and we call the codeword matrix $M_k$. The first part of constructing the $k+1$ matrix is to construct the block matrix $\pmatrix{M_k | M_k}^T$ which has $k$ columns with the top and bottom each having distance $2^{k-1}$ by the induction hypothesis. Now each column must be $2^{k-1}+2^{k-1}=2^k$ from each other because we can sum over the top and bottom halves separately to get the hamming distance.
We have to add one more column which has a top half that is all $0$ and the bottom half is all $1$, which is the second column in your examples and it's easy to see the first column, the vector of all ones. Now we also note that if we replaced the vector of all ones with the zero vector, the distance wouldn't change so the top and bottom halves again have the same distance from the rest of the vectors and so the total distance is $2^{k-1}+2^{k-1} = 2^k$ and we are done.