I have been thinking a bit about error correcting codes, in particular the following problem:

Consider the problem of transmitting a single real number $x \in [0,1]$ over a lossy connection, where each bit sent has a i.i.d probability $p < 0.5$ of being flipped during transmission. For a given number of transmitted bits $N$, devise encoding and decoding algorithms $E$ and $D$ respectively minimizing the expected difference $$\mathbb{E}[|D(E(x)) - x|]$$ where with some abuse of notation we let $E(x)$ denote the encoded value after bits have randomly been flipped.

Simply constructing a binary representation of $x$ using $N$ bits will give an error of at most $2^{-N}$ if no bits gets flipped, but with probablity $p$ the highest-order bit would be flipped, giving an error of about $\frac{1}{2}$. In particular this simple scheme have an expected error ~ $\frac{1}{2}p$.

Instead we could do a simple error correcting mechanism transmitting an $N/k$ bit long binary representation with each bit duplicated $k$ times. In the reconstruction, for each of the $k$-bit blocks, you choose the value (either $0$ or $1$) which occurs the most. For each of the $N/k$ blocks, the probability that the wrong bit is being reconstructed is now (approximately) upper bounded by $$\alpha_p = (4p(1-p))^{k/2}$$ A quick computation shows this scheme has an expected reconstruction error of $$O\left(\alpha_p^{\frac{k}{2}} + 2^{-\frac{N}{K}}\right)$$ which for a proper value of $k$ (in particular, $k = \sqrt{-\frac{N}{2\cdot \log_2{\alpha_p}}}$) gives an expected error of $$O\left(2^{-\sqrt{-N\log_2{\alpha_p}}}\right)$$

which gets us back to a super-polynomially error guarantee at least. Since the highest-order bits are the most important for the reconstructed distance error, I also experimented with replicating the top-bits more than the lower-order bits, but that didn't get me asymptotically better results.

Are there better known results for this problem?

  • $\begingroup$ Why not take a $m$ bit representation of $x$, encoded with an error correcting code to $N$ bits? I anticipate this will give a better scheme. $\endgroup$
    – D.W.
    Oct 23, 2022 at 19:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.