<p>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.</p>

CC BY-SA 4.0
2021-01-24T14:12:07.953Z
Reading this a few years later, I don’t understand my own proof.  Not sure which time I’m confused at.
Geoffrey Irving
CC BY-SA 3.0
2017-11-13T17:18:58.133Z
2017-11-13T17:18:58.133Z
Geoffrey Irving
<p>Say we have $N$ bits that we'd like to store in an $M$-bit error correcting code, where $M &gt; N$.  Given $\epsilon &gt; 0$, as long as $N &gt; N_0(\epsilon)$ we can recover the original bits as long as any $N(1+\epsilon)$ of the $M$ bits are correct.</p>

<p>Now say the bits are ordered in decreasing order of importance.  Can we pick a single $M$-bit code so that if $K &gt; 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$.</p>

<it.information-theory>
Error correction that adapts to different error rates
Geoffrey Irving
# Error correction that adapts to different error rates

(Asked by: username_0 on 2017-11-09)

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

**Tags:** it.information-theory

---

## 1 answers

### Answer by username_0 on 2017-11-13. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: Reading this a few years later, I don’t understand my own proof.  Not sure which time I’m confused at.  

---

