Shannon capacity $C$ is the upper limit on a rate $R$ defined as the number of information symbols $k$ divided by the number of transmitted symbols $n$, that can be transmitted over a channel such that as $n \rightarrow \infty$, the probability of error goes to zero. If a rate $R > C $ is used, the probability of error is bounded away from zero.

Since $n$ is finite in practical applications, there is some nonzero probability of error.Thus, why would it matter if we transmit at a rate higher than $C$, Shannon's theorem predicts that such a rate will have a nonzero probability of error, but we already have a nonzero probability of error due to the fact that $n$ is finite.In other words, why don't we transmit at rates higher than $C$ if we are going to get a nonzero probability of error anyways ?

  • 5
    $\begingroup$ Not all nonzero numbers are equal. $\endgroup$ – Boris Bukh Aug 23 '16 at 13:53
  • $\begingroup$ But how do we know that the probability of error caused by transmitting at rates above C will be intolerable ? $\endgroup$ – Dina Abdelhadi Aug 23 '16 at 13:55
  • $\begingroup$ This sounds like an engineering question, not a theoretical CS one. $\endgroup$ – Peter Taylor Aug 23 '16 at 14:36
  • 2
    $\begingroup$ @PeterTaylor it can be tcs $\endgroup$ – 1.. Aug 25 '16 at 6:47
  • 1
    $\begingroup$ This paper talks about the achievable rates for any given error probability at finite blocklenghts. people.lids.mit.edu/yp/homepage/data/finite_block.pdf $\endgroup$ – Devil Aug 25 '16 at 23:31

Look at the strong converse to Shannon's theorem:

for rates above the channel capacity, if $n$ bits are to be transmitted, the probability of error is exponentially close to 1, so $1-e^{c n}$ for some constant $c$ depending on the channel.

Also, look at rate distortion theory.

This gives a formula for the highest rate at which you can transmit if you want to make sure that at most $\epsilon$ fraction of the transmitted bits are received erroneously.

Both of these quantify the cost of errors incurred when you transmit at $R>C$, and in most cases it's not worth it.


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.