0
$\begingroup$

Say we have $N$ bits that we'd like to store in an $M$-bit error correcting code, where $M > N$. Given $\epsilon > 0$, as long as $N > N_0(\epsilon)$ we can recover the original bits as long as any $N(1+\epsilon)$ of the $M$ bits are correct.

Now say the bits are ordered in decreasing order of importance. Can we pick a single $M$-bit code so that if $K > K_0(\epsilon)$ out of the $M$ bits are uncorrupted, we can recover the first $K(1 - \epsilon)$ original bits correctly? Here the difference is that the code is independent of $K$.

$\endgroup$
0
$\begingroup$

This is impossible as stated. Consider $M = N, K = N/2$. Up to $\epsilon$, we're asking to be able to recover the whole input from the whole code, and the first half of the input from either the first half of the code or the second half. But if we can recover the first half of the input from the first half of the code, this implies we can recover the second half of the input from the second half of the code, and vice versa. Thus we can recover both halves of the input from the first half of the code, which is impossible.

$\endgroup$

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.