2.2 Mutual Information and Shannon Capacity

Channel capacity was pioneered by Claude Shannon in the late 1940s, using a mathematical theory of communication [111 113]. The capacity of a channel, denoted by C, is the maximum rate at which reliable communication can be performed, without any constraints on transmitter and receiver complexity. Shannon showed that for any rate R, there exist rate R channel codes with arbitrarily small block (or symbol) error probabilities. Thus, for any rate R and any desired non-zero probability of error P _e , there exists a rate R code that achieves P _e . However, such a code may have a very long block length, and the encoding and decoding complexity may also be extremely large. In fact, the required block length may increase as the desired P _e is decreased and/or the rate R is increased towards C. In addition, Shannon showed that codes operating at rates R>C cannot achieve an arbitrarily small error rate, and thus the error probability of a code operating at a rate above capacity is bounded away from zero. Therefore, the channel capacity is truly the fundamental limit to communication.

Although it is theoretically possible to communicate at any rate below capacity, it is actually a very difficult problem to design practical channel codes (or codes with reasonable block length and encoding/decoding complexity) at rates close to capacity. Tremendous progress has been made in code design over the past...