Databases Reference
In-Depth Information
then
I
(
X
;
Y
)
=
H
(
Y
)
which had been our measure of rate.
In Example 8.5.2, the average mutual information is 0 bits, which accords with our intuitive
feeling of what the rate should be. Again, whenever
H
(
Y
|
X
)
=
H
(
Y
)
that is, knowledge of the source gives us no knowledge of the reconstruction,
I
(
X
;
Y
)
=
0
which seems entirely reasonable. We should not have to transmit any bits when we are not
sending any information.
At least for the examples here, it seems that the average mutual information does represent
the rate. However, earlier we said that the average mutual information between the source
output and the reconstruction is a measure of the information conveyed by the reconstruction
about the source output. Then why are we looking for compression schemes that
minimize
this
value? To understand this, we have to remember that the process of finding the performance
of the optimum compression scheme had two parts. In the first part, we specified the desired
distortion. The entire set of conditional probabilities over which the average mutual informa-
tion is minimized satisfies the distortion constraint. Therefore, we can leave the question of
distortion, or fidelity, aside and concentrate on minimizing the rate.
Finally, how do we find the rate distortion function? There are two ways. One is a
computational approach developed by Arimoto [
113
] and Blahut [
114
]. While the derivation
of the algorithm is beyond the scope of this topic, the algorithm itself is relatively simple. The
other approach is to find a lower bound for the average mutual information and then show that
we can achieve this bound. We use this approach to find the rate distortion functions for two
important sources.
Examp l e 8 . 5 . 3 : Rate distortion function for the binary source
Suppose we have a source alphabet
{
0
,
1
}
, with
P
(
0
)
=
p
. The reconstruction alphabet is also
binary. Given the distortion measure
(
x
i
,
y
j
)
=
x
i
⊕
y
j
,
(57)
d
where
⊕
is modulo 2 addition, let us find the rate distortion function. Assume for the moment
1
that
p
p
an encoding scheme that would satisfy the distortion criterion would
be not to transmit anything and fix
Y
<
2
.For
D
>
=
1. So for
D
p
R
(
D
)
=
0
(58)
We will find the rate distortion function for the distortion range 0
D
<
p
.
