5
$\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$.

Improve this question
$\endgroup$
5
  • $\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, 2014 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, 2014 at 8:33
  • $\begingroup$ @JiK, thanks, I'll follow up on secret-sharing. $\endgroup$
    – usul
    Dec 18, 2014 at 8:54
  • $\begingroup$ @DimaPasechnik, right, there is an off-by-one error that I'll fix. $\endgroup$
    – usul
    Dec 18, 2014 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, 2014 at 11:48

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So $k = \log(n)$, and what is the distance of the code? Thanks. $\endgroup$
    – usul
    Dec 19, 2014 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, 2014 at 14:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .