1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Commented Oct 11, 2014 at 6:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Commented Oct 11, 2014 at 6:17
  • 3
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Oct 11, 2014 at 6:46
  • $\begingroup$ 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. $\endgroup$
    – Eric Astor
    Commented Oct 11, 2014 at 15:07
  • $\begingroup$ @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 $\endgroup$
    – Eric Astor
    Commented Oct 11, 2014 at 15:57

1 Answer 1

Reset to default
2
+50
$\begingroup$

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?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .