4
$\begingroup$

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the sense that, for some $k$, reading $k$ bits is never sufficient to decode (even were the channel noiseless).

In other words, for each subset of $k$ locations and each codeword $w$, there exists a codeword $w'$ that matches $w$ at those $k$ locations.

To make the question harder, I'm actually most interested in "balanced" binary codes -- every word has Hamming weight $\frac{n}{2}$. But it seems independently interesting to get an answer even without the balanced condition.

How large can $k$ be? Can it be $\Omega(n)$? (What is $k$ for the Hadamard code?)

Notes: We can restate this as a combinatorics problem (up to a constant factor or two), treating each codeword as a subset of $\{1,\dots,n\}$ indicating the coordinates equal to $1$: Come up with a set of subsets of $\{1,\dots,n\}$, each of size $n/2$, such that pairwise intersection is $O(n)$ (this is the distance requirement) and for each subset $S$ and each $X \subseteq S$ with $|X| \leq k$, there exists an $S'$ such that $X \subseteq S'$.

The problem of finding the largest $k$ seems too large for exhaustive search even over very small $n$.

Examples: For $n=4$, take all of the weight-$2$ words: $\{1100,1010,1001,0110,0101,0011\}$. Here $d=2$ and $k=1$ (we must read at least two locations to have a hope of uniquely identifying a codeword).

For $n=8$, I believe we can take the following weight-$4$ words: $\{11110000, 00001111, 11000011, 10100101, 10010110, 01101001, 01011010, 00111100\}$. Here $d=4$ and $k=2$.

$\endgroup$
  • $\begingroup$ This seems to be related to secret sharing: distributing a secret to $n$ people so that at least $t$ shares are required to reconstruct it, or so that knowing any $t-1$ shares does not reveal any information. My knowledge on the topic ends about here; I don't know if binary codes have been used as in this problem. $\endgroup$ – Janne Kokkala Dec 18 '14 at 8:10
  • $\begingroup$ there is a discrepancy in the definition of $k$ vs examples; e.g. your 1st example corresponds to $k=1$, according to your definition. $\endgroup$ – Dima Pasechnik Dec 18 '14 at 8:33
  • $\begingroup$ @JiK, thanks, I'll follow up on secret-sharing. $\endgroup$ – usul Dec 18 '14 at 8:54
  • $\begingroup$ @DimaPasechnik, right, there is an off-by-one error that I'll fix. $\endgroup$ – usul Dec 18 '14 at 8:54
  • $\begingroup$ After looking into secret-sharing a bit, I don't see a useful connection. There are too many components that differ strongly (use of randomness, the fact that $t-1$ shares reveals zero information, lack of notion of distance between words). But maybe one can put to use Shamir's basic idea (each share is a point on a polynomial of degree $t$). $\endgroup$ – usul Dec 19 '14 at 11:48
2
$\begingroup$

For each $k$ take $n=2^k$ and the hyperplanes of the $k$-dimensional affine space over $\mathbb{F}_2$. There are $n$ points and $2^{k+1}-2$ hyperplanes; the codewords are the indicator functions of the latter. Then $k-1$ bits never suffice, but $k$ bits always do give you unique codeword.

$\endgroup$
  • $\begingroup$ So $k = \log(n)$, and what is the distance of the code? Thanks. $\endgroup$ – usul Dec 19 '14 at 11:40
  • $\begingroup$ the supports of the codewords either have empty intersection, or intersection of size $2^{k-2}$. So the Hamming distance between any two is $2^{k-1}$ or $2^k$. Thus the minimal distance is $2^{k-1}$. $\endgroup$ – Dima Pasechnik Dec 19 '14 at 14:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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