3
$\begingroup$

Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is straight forward to show that two different elements of the Hadamard code differ on exactly a fraction of $1/2$ of their values, e.g. their relative distance is exactly $1/2$.

What about the distance of arbitrary vectors to the Hadamard code? I've read in certain papers that this distance is also bounded by $1/2$ but other papers explicetely consider the case of vectors having distance $> 1/2$ to all elements of the code. Can anyone help me?

$\endgroup$
4
$\begingroup$

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, i.e. any Boolean vector is at most $\frac{N}{2}-\frac{\sqrt{N}}{2}$ Hamming distance away from some code word of the punctured Hadamard code. The $O(\sqrt{N})$ advantage over $\frac{N}{2}$ is optimal for any set of $O(N)$ points in $\{0, 1\}^N$.

The punctured Hadamard code maps $x \in \{0,1\}^n$ to the sequence $(\langle x, u\rangle\bmod 2)_{u \in \{1\}\times\{0, 1\}^{n-1}}$. It's not hard to see that the distance of the code is still $N/2$ as in the Hadamard code, but the number of codewords is $2N$. If we map each code word to a vector in $\{-1, 1\}^N$ by mapping $1$ to $-1$ and $0$ to $1$ we get vectors $v_1, \ldots, v_N, -v_1, \ldots, -v_N$ such that $\langle v_i, v_j \rangle = 0$ for any $i \neq j$. Taking any $x \in \{0, 1\}^N$ and mapping it to $u := 1 - 2x$ in the same way, we see that $x$ is Hamming distance $d$ away from a codeword if there exists an $i$ such that $|\langle v_i, u\rangle| = N-2d$. In other words, it's enough to show that for any $u \in \{-1, 1\}^N$ there exists an $i$ such that $|\langle v_i, u\rangle| \geq \sqrt{N}$. But this follows from the properties of the $v_i$: $$ \max_i |\langle v_i, u\rangle|^2 \geq \frac{1}{N}\sum_{i = 1}^N{|\langle v_i, u\rangle|^2} = \sum_{i = 1}^N{u_i^2} = N. $$ The inequality is by averaging and the first equality is true because $\frac{1}{\sqrt{N}}v_1, \ldots, \frac{1}{\sqrt{N}}v_N$ is an orthonormal basis of $\mathbb{R}^N$.

The fact that no set of $O(N)$ points in $\{0, 1\}^N$ can cover $\{0, 1\}^N$ with radius $\frac{N}{2} - \omega(\sqrt{N})$ is equivalent to the fact that for any $v_1, \ldots, v_M \in \{-1, 1\}^N$, $M = O(N)$, there exists a vector $u \in \{-1, 1\}^N$ such that $|\langle v_i, u\rangle| = O(\sqrt{N})$ for all $i$. This is a restatement of Spencer's "Six Standard Deviations Suffice" theorem from discrepancy theory.

$\endgroup$
  • $\begingroup$ Thank you for this answer. I really thought the answer is trivial but a lookup on the coverage radius tells me this is not the case ... $\endgroup$ – SpaceMonkey Jan 14 '15 at 23:11
  • $\begingroup$ What if I'm okay with using $n^\alpha$ codewords? Are there any constructions which can then give me better (smaller) covering radius? $\endgroup$ – Thomas Ahle Mar 16 '16 at 15:08
  • 2
    $\begingroup$ @ThomasAhle The general version of Spencer's result is that for any $v_1, \ldots, v_M \in \{-1, 1\}^N$ there exists a vector $u \in \{-1, 1\}^N$ such that $|\langle v_i, u \rangle| = O(\sqrt{N\log(2M/N)})$. So the covering radius is at least $N/2 - O(\sqrt{N\log(2M/N)})$. This is tight for a random construction. Check this paper for explicit constructions: cs.tau.ac.il/~shpilka/publications/RabaniShpilka09.pdf $\endgroup$ – Sasho Nikolov Mar 17 '16 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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