12.3 Moving Information Through Discrete Channels
203
Fig. 12.3 The mutual information I [x; y] for the binary symmetric channel as a function of α for
ε = 0.05 and 0.2 (left) and the channel capacity C as a function of the error rate ε (right).
which Shannon used in [2] to characterize the communication channel. From our
earlier discussion of identifying H [y|x] with the amount of noise created in the
channel, we interpret (12.18) as the amount of information I [x; y] we can learn
about the input x is given by whatever information H [x] was sent minus the information H [x|y], which was destroyed in the channel. For the binary channel, we find
I [x; y] = H b (γ ) − H b (ε) with γ = ε + α − 2εα.
Using the mutual information I [x; y] we can now define the channel capacity C
as the maximum achievable I [x; y], where we maximize with respect to all possible
input probability distributions p x (x i )
C = max I [x; y] .
(12.19)
In general it is not possible to find this maximum explicitly, but for our binary
channel all possible input distributions are parameterized by α. Therefore, we can
either analytically or numerically determine the maximum of I [x; y] = H b (α +
ε − 2εα) − H b (ε) as a function of α; or simply inspect the plot on the left-hand
side in Fig. 12.3, where we display I [x; y] as a function of α for two values of ε.
Both curves assume their maximum at α = 1/2. Using α = 1/2 we then show the
channel capacity C as a function of the bit-flip probability ε on the right-hand side in
Fig. 12.3. We observe that for very small error rates the capacity approaches C = 1,
which means that every bit that is sent is also received. As the bit-flip rate ε gets
closer to 1/2 the capacity approaches zero; if half the time the bits are randomly
flipped, it is impossible to recover the input signal. As the bit-flip rate ε increases
further and approaches unity, the capacity C again approaches C = 1 bit/bit; if each
bit is flipped with certainty ε = 1, we can also recover the full information that was
sent through the channel.
But what does a capacity C = 0.5 mean? It is instructive to write this as
C = 1 bit/2 bits. In other words, we need to transmit two bits, in order to effectively transmit one bit reliably. That such error-correcting codes, in the limit of long
messages, always exist for any non-zero capacity C is the essence of Shannon’s
channel coding theorem [2, 10]. He also showed that it is not possible to transmit
203
Fig. 12.3 The mutual information I [x; y] for the binary symmetric channel as a function of α for
ε = 0.05 and 0.2 (left) and the channel capacity C as a function of the error rate ε (right).
which Shannon used in [2] to characterize the communication channel. From our
earlier discussion of identifying H [y|x] with the amount of noise created in the
channel, we interpret (12.18) as the amount of information I [x; y] we can learn
about the input x is given by whatever information H [x] was sent minus the information H [x|y], which was destroyed in the channel. For the binary channel, we find
I [x; y] = H b (γ ) − H b (ε) with γ = ε + α − 2εα.
Using the mutual information I [x; y] we can now define the channel capacity C
as the maximum achievable I [x; y], where we maximize with respect to all possible
input probability distributions p x (x i )
C = max I [x; y] .
(12.19)
In general it is not possible to find this maximum explicitly, but for our binary
channel all possible input distributions are parameterized by α. Therefore, we can
either analytically or numerically determine the maximum of I [x; y] = H b (α +
ε − 2εα) − H b (ε) as a function of α; or simply inspect the plot on the left-hand
side in Fig. 12.3, where we display I [x; y] as a function of α for two values of ε.
Both curves assume their maximum at α = 1/2. Using α = 1/2 we then show the
channel capacity C as a function of the bit-flip probability ε on the right-hand side in
Fig. 12.3. We observe that for very small error rates the capacity approaches C = 1,
which means that every bit that is sent is also received. As the bit-flip rate ε gets
closer to 1/2 the capacity approaches zero; if half the time the bits are randomly
flipped, it is impossible to recover the input signal. As the bit-flip rate ε increases
further and approaches unity, the capacity C again approaches C = 1 bit/bit; if each
bit is flipped with certainty ε = 1, we can also recover the full information that was
sent through the channel.
But what does a capacity C = 0.5 mean? It is instructive to write this as
C = 1 bit/2 bits. In other words, we need to transmit two bits, in order to effectively transmit one bit reliably. That such error-correcting codes, in the limit of long
messages, always exist for any non-zero capacity C is the essence of Shannon’s
channel coding theorem [2, 10]. He also showed that it is not possible to transmit