# Noise reduction in capacity-0 channels

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.

• The standard way a binary symmetric channel with crossover probability $p>1/2$ is handled in textbooks is the following. The receiver is to first flip all the bits. After that you can treat it as a BSC-channel with crossover probability $1-p$. The case $p=1/2$ is the one where no communication can take place, because there is no correlation between what is received and what is transmitted. – Jyrki Lahtonen Oct 11 '14 at 6:16
• Given that this is a textbook answer I don't think this question is at the research level, so it isn't suitable to MO. – Jyrki Lahtonen Oct 11 '14 at 6:17
• The statement "Obviously, this can't carry any information" is obviously false, and I would vote to close this question except that you can't vote to close questions with open bounties. This question is built on a basic error, and although the speculations about reducing the errors in channels with no information sound interesting, I don't see any meaning because of that error. – Douglas Zare Oct 11 '14 at 6:46
• Thank you all for explaining - this DID come up in a research context (in a different field), and I apparently didn't know enough to think of the obvious answer. Nor did two others I consulted. I attached the bounty to provoke responses. Thank you for providing the response I was looking for. – Eric Astor Oct 11 '14 at 15:07
• @Jyrki, if your comment was an answer, I would be awarding you the bounty at the moment - it's extremely clear and explains my mistake – Eric Astor Oct 11 '14 at 15:57