Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
Thank you for your answers, this was helpful –  Laurent Bienvenu Feb 15 '12 at 19:58
add comment

3 Answers 3

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

share|improve this answer
add comment

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.)

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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