0
$\begingroup$

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

  1. $|A|=|B|=2^{r-1}/r$
  2. $\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))$
  3. $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$
  4. $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.)

$\endgroup$
5
  • $\begingroup$ "If you know an algorithm..." - Doesn't the answer on Math.SE provide an algorithm? "why does this method.... result in ...?" - Isn't that explained in the last paragraph of the answer on Math.SE? Have you tried working through some examples (say $r=2$, then $r=3$, then $r=4$) to get a better feeling for this? Rather than trying to draw a picture of a hypercube in some high-dimensional space, I would suggest you write down the coordinates of some point on the hypercube and try to convince yourself that it is covered, and repeat a few times. $\endgroup$
    – D.W.
    May 18, 2017 at 15:22
  • $\begingroup$ Yeah I tried. But I don't get a feeling for this. I know that algorithm works, and I can choose the 0 bit array to satisfy the cover, but I don't know why it works, which is why I posted this question in the first place. $\endgroup$ May 18, 2017 at 15:29
  • $\begingroup$ Requirement 2 shows that either $A$ is empty or $|B| \leq r$. Similar, requirement 3 gives a polynomial upper bound $\binom{r}{3}$ on the size of $A$. I suspect that you got it wrong somehow. $\endgroup$ Jul 19, 2017 at 7:04
  • $\begingroup$ Hamming codes give an explicit construction for certain values of $r$, if you relax the requirement of exact Hamming distance to minimum Hamming distance. In particular, if $r$ is a power of 2 then the augmented Hamming code consists of $2^{r-1}/r$ codewords at minimal distance 4. $\endgroup$ Jul 19, 2017 at 7:06
  • $\begingroup$ @YuvalFilmus Ah yes, thanks for pointing that out! Requirement 2 should be correct now. I'm confused, why shouldn't $|A| = 2^{r-1}/r$? $\endgroup$ Jul 19, 2017 at 13:09

1 Answer 1

0
$\begingroup$

I completely misunderstood Misha's answer. Here is my updated understanding of the equivalent problem. All quotes are from his answer.

  1. Let $S = \{0,1\}^{r-1}$, $|S| = 2^{r-1}$ bit arrays, each bit array has length $r-1$.

  2. Let $S_i = \{x\ |\ x \in S\ and\ x_i = 1\}$, where $x_i$ is the $i^{th}$ bit of bit array $x$. We set the $i^{th}$ bit of array $x$ to $1$.

    An even number of bit arrays is always chosen from $S_i$. If initially an odd number of bit arrays is chosen, then choose the bit array corresponding to the parity bit as well, so finally an even number of bit arrays are chosen.

    This corroborates with Misha's answer, as the coordinates numbered off exactly match the parity bit coverage.

    • Among the coordinates numbered $0\dots001, 0\dots011, 0\dots101, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
    • Among the coordinates numbered $0\dots010, 0\dots011, 0\dots110, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  3. Repeat step 2 for all $i \in [1,\ r-1]$.

    Let $A$ be the set of chosen bit arrays from $S_i$ for all $i$, where chosen bit arrays are hamming codewords.

    The hamming code is an even parity bit, single error correction code for arrays of length $r - 1$.

    The following describes single error correction, where "vertex" means "bit arrays", and "picked vertices" means "bit array in $A$" or "hamming codeword".

    If a vertex is not one of the picked vertices, find all the parity conditions that fail, let $i$ be the coordinate with a $1$ in all the bits corresponding to the failed conditions; change the $i^{\text{th}}$ coordinate, and you will get a picked vertex.

This solves the equivalent problem of finding set $A$.


Now, to solve the original problem.

(I originally thought the $00\dots00^{\text{th}}$ coordinate was for double error detection, and was wondering why I needed that in a single error correction code. I was completely wrong.)

Given a vertex, if it is one of the picked vertices, change the $00\dots00^{\text{th}}$ coordinate, and you will get another picked vertex.

This is equivalent to prepending a new bit, $b$, for each bit array within the set $A$ that we derived earlier, thus making all bit arrays have length $r$.

Arbitrarily let bit $b = 0$. Define $A_{new} = \{b\ x_1\dots x_{r-1}\ |\ x \in A\}$.

Let $B = \{\neg b\ x_1\dots x_{r-1}\ |\ x \in A\}$, so all bit arrays are same as $A_{new}$, except for every array, the $b$ bit is flipped.

This fits well with Misha's explanation that bit arrays from $A_{new}$ and $B$ are nearly-identical, because the only difference is the flipped bit $b$.

the $00\dots00^{\text{th}}$ coordinate of a vertex [...] is the "free" coordinate where we pick a vertex with $0$ and also pick a nearly-identical vertex with $1$.

This solves the original problem, such that the $2^r/r$ bit arrays are in sets $A_{new}$ and $B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.