Error correcting codes - basic question - MathOverflow

Error correcting codes - basic question

2012-02-11T11:02:05Z

Hi,

I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), with the following requirement: knowing any $k$ bits of the string $x$ (together with their respective positions in $x$), one can fully retrieve the information $F$. For which $(n,k)$ can this be achieved? What I am hoping to get is $k=o(n)$, but I do not know whether this is possible.

Thanks in advance!

Answer by none for Error correcting codes - basic question

2012-02-11T12:02:17Z

That is called an "erasure code"; see the Wikipedia article of that name.

Answer by Anadim for Error correcting codes - basic question

2012-02-12T08:03:25Z

It is easy to see that if you have an information object of size $k$ bits (symbols), then you need at least $k$ coded bits (symbols) to reconstruct it (Singleton Bound). This bound is achieved by $(n,k)$ maximum distance separable (MDS) codes. Reed Solomom (RS) is a family of $(n,k)$-MDS codes. $(n,k)$-RS codes exist for any $n>k$ and can be constructed with a finite field of order at least $n$.

Answer by Mark Wildon for Error correcting codes - basic question

2012-02-12T19:19:37Z

To elaborate on Anadim's answer, if $C$ is a code of length $n$, then any codeword in $C$ is uniquely determined by any $k$ of its positions if and only if $C$ has minimum distance at least $n-k+1$. The Singleton bound says that, over an alphabet of size $q$, a code of length $n$ and minimum distance $n-k+1$ has size at most $q^k$. So if $k = o(n)$ then there are no asymptotically good codes satisfying your requirements.

If $q$ is large then the Singleton bound is attained by any MDS (maximum distance separable) code, for example, by the Reed–Solomon codes mentioned by Anadim. So if you have $q^m$ possible strings then, using Reed–Solomon codes, the feasible pairs are $(n,k)$ for $n$ and $k$ such that $q \ge n \ge k \ge m$. The restriction $q \ge n$ means this is not an asymptotic result, but for practical purposes, if you can take $q$ large, you can then make $k$ small compared to $n$.

Over the binary alphabet, the only MDS-codes of length $n$ are the repetition code of size $2$, the parity check code of size $2^{n-1}$, and the complete code consisting of all $2^n$ words of length $n$. In this case Hamming's packing bound is stronger than the Singleton bound, and the Plotkin bounds are stronger still when the minimum distance is large compared to $n$. In particular, one of the Plotkin bounds states that if $k < n/2$ then a binary code of length $n$ and minimum distance $n-k+1$ has size at most $2(n-k+1)$. This shows that if $k=o(n)$ then any binary code satisfying your requirements is necessarily very small.

If you are willing to take $k\approx n/2$ then it might work well to use a shortened Hadamard code of length $2k-1$, size $2k$ and minimum distance $k$. These attain one of the Plotkin bounds, so are the largest possible binary codes of length $2k-1$ that allow any codeword to be reconstructed from any $k$ of its positions. (A special case when $k=4$ is the subcode of the binary Hamming code of length $7$ consisting of all words of even weight.)