Find hamming codewords in r=2^k dimensions
-
04-11-2019 - |
سؤال
There is the original problem, and an equivalent problem.
The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$.
Misha Lavrov gave an excellent answer on Math.SE that solves the original problem. However, I don't get his construction.
If you could prove that his algorithm solves the problem for any $r=2^k$, or provide your own algorithm that solves the problem / equivalent problem for any $r=2^k$, I'd really appreciate it.
The original problem: choose $2^r/r$ bit arrays, where each bit array is of length $r$, and $r=2^k$ for all $k \ge 2$, such that the chosen arrays can be split into 2 sets, $A$ and $B$, where
- $|A|=|B|=2^{r-1}/r$
- $\forall x \in A.(\exists y \in B.(hamming \space distance (x, y) = 1))$ and $\forall y \in B.(\exists x \in A.(hamming \space distance (x, y) = 1))$
- $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$
- $hamming \space distance (i, j) = 3 \quad \forall i, j \in B, \space i \neq j$
Here is the answer for $k = 2$, where blue circles are chosen bit arrays.
(P.S. Instead of $n=2^r$ dimensions in my question on Math.SE, I used $r=2^k$ here, because Misha's answer referred to bit arrays of length $r$. I hope this is not too confusing.)
لا يوجد حل صحيح