# Error correcting codes for transmitting a real value $x$ in [0,1], minimizing the reconstructed distance to the original $x$

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?

• 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.
– D.W.
Commented Oct 23, 2022 at 19:03