Suppose we have a binary symmetric channel with $p=\frac{1}{3}$; that is, a communications channel in which each bit is flipped with independent probability $\frac{1}{3}$. I know that there is a code such that, in the (highly probable) event that no more than $p$ of the bits are corrupted, we can guarantee recovery of any message we put through... so in particular, we can certainly recover a message that is correct in $\frac{1}{4}$-th of its positions, reducing the error introduced by the channel.


Now, let's ask this for a useless channel - a binary symmetric channel $C$ with $p=\frac{3}{4}$. Obviously, this can't carry any information, but bear with me. Is there a code such that, if we feed an encoded message through the channel $C$, we can recover (with high probability) a version of the message with at most two-thirds of the bits flipped? That is, is it possible to reduce the error (without actually recovering any information) even in a capacity-0 channel? Obviously, we can't get our error down under $\frac{1}{2}$, since that would violate the channel capacity theorem... but can we get as close as we like? Or is this generally impossible?


Stating this final question: For fixed $\epsilon>0$ and $\delta\in(\frac{1}{2},1)$, is there a code that can implement a channel with symmetric error no more than $\frac{1}{2}+\epsilon$ over a channel with symmetric error bounded by $\delta$? (For what it's worth, I don't care about the rate, just the error bounds.)


I welcome any suggestions that would clarify the question as explained above - I haven't done much coding theory, so I'm not used to the terms.



Noise reduction in capacity-0 channels
Given that the channel BSC(3/4) is binary, you can use an error correcting code with rate strictly less than H(1/4) where H denotes the binary entropy function, and achieve asymptotically error free transmission as promised by Shannon.


Note that your channel output can be followed or input preceded by bit inversion to obtain an equivalent BSC(1/4) channel. So choose your favourite code, encode your data flip the bits of the codeword and transmit. Then decode as normal.


Does this answer your question?


