Databases Reference
In-Depth Information
Once we know the set of compression schemes to which we have to confine ourselves, we
can start to look at the rate of these schemes. In Example
8.4.2
, the rate was the entropy of
Y
.
However, that was a result of the fact that the conditional probability describing that particular
source coder took on only the values 0 and 1. Consider the following trivial situation.
Example8.5.2:
Suppose we have the same source as in Example 8.4.2 and the same reconstruction alphabet.
Suppose the distortion measure is
2
d
(
x
i
,
y
j
)
=
(
x
i
−
y
j
)
and
D
∗
225. One compression scheme that satisfies the distortion constraint randomly
maps the input to any one of the outputs; that is,
=
1
8
P
(
y
j
|
x
i
)
=
for
i
=
0
,
1
,...,
15 and
j
=
0
,
2
,...,
14
We can see that this conditional probability assignment satisfies the distortion constraint:
N
−
1
i
M
−
1
j
=
(
x
i
,
y
j
)
(
x
i
)
(
y
j
|
x
i
)
D
0
d
P
P
=
0
=
N
−
1
i
=
0
M
−
1
j
=
0
(
2
1
16
1
8
=
x
i
−
y
j
)
128
15
0
7
1
2
=
0
(
i
−
2
j
)
i
=
j
=
=
42
.
5
is 3 bits. However, we
are not transmitting
any
information. We could get exactly the same results by transmitting
0 bits and randomly picking
Y
at the receiver.
As each of the eight reconstruction values is equally likely,
H
(
Y
)
cannot be a measure of the rate. In
his 1959 paper on source coding [
111
], Shannon showed that the minimum rate for a given
distortion is given by
Therefore, the entropy of the reconstruction
H
(
Y
)
R
(
D
)
=
min
I
(
X
;
Y
)
(56)
{
P
(
y
j
|
x
i
)
}∈
To prove this is beyond the scope of this topic. (Further information can be found in [
38
,
112
].)
However, we can at least convince ourselves that defining the rate as averagemutual information
gives sensible answers when used for the examples shown here. Consider Example
8.4.2
.The
average mutual information in this case is 3 bits as shown in Example
8.4.3
, which is what we
said the rate was. In fact, notice that whenever the conditional probabilities are constrained to
be of the form of Equation (
50
),
H
(
Y
|
X
)
=
0
