2
$\begingroup$

In the context of noisy channel coding, a theorem by Shannon says that, by using suitable channel codes, communication with rate up to the channel capacity is possible.

I've seen numerous claims that this capacity (of one way communication) cannot be improved by adding a feedback channel, which tells the sender which sent symbols were corrupted by the noisy channel.

In a lecture by MacKay, he proves this fact for the binary erasure channel (BEC). This channel essentially loses a fraction $p$ of sent symbols and has a capacity $C=1-p$. I have doubts about the proof presented in the lecture, since it seems to assume that any lost symbol can be re-transmitted and will then not be lost a second time. Perhaps asymptotically this assumption can be justified but it's not obvious to me.

On the other hand, I've seen claims in literature saying that the feedback does not help for any channel. I'm not sure how the feedback channel is defined exactly for this claim to hold. Is the feedback channel itself also noisy? I think, with added noiseless feedback, the binary symmetric channel (BSC) and the BEC should have the same capacity, since it no longer matters if the bits are lost of flipped. This seems to contradict the claim, meaning that the feedback channel assumed there is not noiseless. Is it then the same channel added backwards?

Finally, how does one prove this result rigorously (perhaps for BSC as an example, or in general)?

$\endgroup$
5
$\begingroup$

I have doubts about the proof presented in the lecture, since it seems to assume that any lost symbol can be re-transmitted and will then not be lost a second time.

No, it doesn't assume that. You send a symbol until the decoder tells you it was received ok. Hence, for a probability of channel error $p$, the number of tries (channel use) for each symbol follows a geometric distribution, and the average number of tries is $1/(1-p)$.

I've seen claims in literature saying that the feedback does not help for any channel. I'm not sure how the feedback channel is defined exactly for this claim to hold.

That holds only for memoryless channels. And "it does not help" only in the sense that the capacity is the same. This is all explained in Cover & Thomas textbook, sect 7.12.

Is the feedback channel itself also noisy?

It's assumed that the feedback channel is perfect (noiseless). If the above property is true with this assumption, then it's also true if the feedback is noisy.

I think, with added noiseless feedback, the binary symmetric channel (BSC) and the BEC should have the same capacity, since it no longer matters if the bits are lost of flipped

Not true. For a BEC, the receiver knows if a channel error occurred, for the BSC it doesn't.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for the answer! I still don't understand the difference between BSC and BEC with feedback. The receiver can just send each symbol he received back to the sender. Then the sender will know if it was correct or not. Why is this not possible? $\endgroup$ Dec 3 '20 at 8:59
  • 3
    $\begingroup$ The sender would know but the receiver wouldn't. What would then the sender do? If he simply retransmits the wrong symbol, the receiver cannot know if the new bits correspond to retrasmision of old wrong messages, or trasmision of new messages. $\endgroup$
    – leonbloy
    Dec 3 '20 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.