12.3 Moving Information Through Discrete Channels
201
For the binary channel, for example, we find p xy (1, 1) = (1 − ε)(1 − α). Summing
(12.9) over all possible input symbols x i gives us two ways to determine the probability p y (y j ) that the decoder finds a symbol y j
p y (y j ) =
i
p xy (x i , y j ) =
i
p yx (y j |x i ) p x (x i ) .
(12.10)
In the binary channel, we have p y (1) = 1 − γ and p y (0) = γ with γ = ε + α −
2εα. We observe that in (12.9) we can calculate the left-hand side p xy (x i , y j ) in a
second way, by multiplying the backwards conditional probability p xy (x i |y j ) that
the encoder sent x i if the decoder found y j by the probability p y (y j ) that symbol y j
arrives. We obtain
p xy (x i , y j ) = p xy (x i |y j ) p y (y j ) .
(12.11)
Note that the left-hand sides of (12.9) and (12.11) are the same and equating the
right-hand sides leads to Bayes’ theorem
p xy (x i |y j ) =
p yx (y j |x i ) p x (x i )
p y (y j )
.
(12.12)
which allows us to infer the probability that x i was sent, provided we have received y j .
Note how the calculation takes probabilities with which x i and y j occur—the prior
information—into account. For the binary channel, we find p xy (1|1) = (1 − ε)(1 −
α)/(1 − ε − α + 2εα) and calculating the other probabilities is left as an exercise.
But we do not really want to make predictions about what symbols were sent.
Instead, we want to assess the performance of the communication channel to transport
information and therefore consider the entropy of the involved distributions. The
entropy of the input H [x] and output H [y] are defined through their respective
probabilities and are given by
H [x] = −
i
p x (x i ) log 2 p x (x i ) and H [y] = −
j
p y (y j ) log 2 p y (y j ) ,
(12.13)
where we use square brackets to denote that the entropy depends on the set of all x or
y. In the binary channel, we have H [x] = H b (α). Here H b ( p) = −p log 2 p − (1 −
p) log 2 (1 − p) is the entropy of a binary system with probabilities p and 1 − p. Using
the probabilities p y (y j ) from above, we find H [y] = H b (γ ) with γ = ε + α − 2εα.
Analogously, the joint entropy H [x, y] is defined in terms of the joint probabilities
p xy (x i , y j ) as
H [x, y] = −
i
j
p xy (x i , y j ) log 2 p xy (x i , y j ) .
(12.14)
Evaluating H [x, y] for our binary channel by explicitly evaluating the sum yields
H [x, y] = H b (α) + H b (ε). Note that H [x, y] is given by the sum of the entropy
201
For the binary channel, for example, we find p xy (1, 1) = (1 − ε)(1 − α). Summing
(12.9) over all possible input symbols x i gives us two ways to determine the probability p y (y j ) that the decoder finds a symbol y j
p y (y j ) =
i
p xy (x i , y j ) =
i
p yx (y j |x i ) p x (x i ) .
(12.10)
In the binary channel, we have p y (1) = 1 − γ and p y (0) = γ with γ = ε + α −
2εα. We observe that in (12.9) we can calculate the left-hand side p xy (x i , y j ) in a
second way, by multiplying the backwards conditional probability p xy (x i |y j ) that
the encoder sent x i if the decoder found y j by the probability p y (y j ) that symbol y j
arrives. We obtain
p xy (x i , y j ) = p xy (x i |y j ) p y (y j ) .
(12.11)
Note that the left-hand sides of (12.9) and (12.11) are the same and equating the
right-hand sides leads to Bayes’ theorem
p xy (x i |y j ) =
p yx (y j |x i ) p x (x i )
p y (y j )
.
(12.12)
which allows us to infer the probability that x i was sent, provided we have received y j .
Note how the calculation takes probabilities with which x i and y j occur—the prior
information—into account. For the binary channel, we find p xy (1|1) = (1 − ε)(1 −
α)/(1 − ε − α + 2εα) and calculating the other probabilities is left as an exercise.
But we do not really want to make predictions about what symbols were sent.
Instead, we want to assess the performance of the communication channel to transport
information and therefore consider the entropy of the involved distributions. The
entropy of the input H [x] and output H [y] are defined through their respective
probabilities and are given by
H [x] = −
i
p x (x i ) log 2 p x (x i ) and H [y] = −
j
p y (y j ) log 2 p y (y j ) ,
(12.13)
where we use square brackets to denote that the entropy depends on the set of all x or
y. In the binary channel, we have H [x] = H b (α). Here H b ( p) = −p log 2 p − (1 −
p) log 2 (1 − p) is the entropy of a binary system with probabilities p and 1 − p. Using
the probabilities p y (y j ) from above, we find H [y] = H b (γ ) with γ = ε + α − 2εα.
Analogously, the joint entropy H [x, y] is defined in terms of the joint probabilities
p xy (x i , y j ) as
H [x, y] = −
i
j
p xy (x i , y j ) log 2 p xy (x i , y j ) .
(12.14)
Evaluating H [x, y] for our binary channel by explicitly evaluating the sum yields
H [x, y] = H b (α) + H b (ε). Note that H [x, y] is given by the sum of the entropy