Noisy channel coding: feedback does not improve the channel capacity

Question

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)?

Answer 1

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.