Databases Reference
In-Depth Information
9.7.2 Entropy-Constrained Quantization
Although entropy coding the Lloyd-Max quantizer output is certainly simple, it is easy to see
that we could probably do better if we take a fresh look at the problem of quantizer design,
this time with the entropy as a measure of rate rather than the alphabet size. The entropy of
the quantizer output is given by
M
H
(
Q
)
=−
P
i
log
2
P
i
(57)
i
=
1
where
P
i
is the probability of the input to the quantizer falling in the
i
th quantization interval
and is given by
b
i
P
i
=
f
X
(
x
)
dx
(58)
b
i
−
1
has no effect on the rate. This
means that we can select the representation values solely to minimize the distortion. However,
the selection of the boundary values affects both the rate and the distortion. Initially, we found
the reconstruction levels and decision boundaries that minimized the distortion, while keeping
the rate fixed by fixing the quantizer alphabet size and assuming fixed-rate coding. In an
analogous fashion, we can now keep the entropy fixed and try to minimize the distortion. Or,
more formally:
Notice that the selection of the representation values
{
y
j
}
2
q
For a given
R
o
, find the decision boundaries
{
b
j
}
that minimize
σ
given by
Equation (
3
), subject to
H
(
Q
)
R
o
.
The solution to this problem involves the solution of the following
M
−
1 nonlinear equa-
tions [
131
]:
ln
P
l
+
1
P
l
=
λ(
y
k
+
1
−
y
k
)(
y
k
+
1
+
y
k
−
2
b
k
)
(59)
where
is adjusted to obtain the desired rate, and the reconstruction levels are obtained using
Equation (
27
). A generalization of the method used to obtain the minimum mean squared
error quantizers can be used to obtain solutions for this equation [
132
]. The process of finding
optimum entropy-constrained quantizers looks complex. Fortunately, at higher rates we can
show that the optimal quantizer is a uniform quantizer, simplifying the problem. Furthermore,
while these results are derived for the high-rate case, it has been shown that the results also
hold for lower rates [
132
].
λ
9.7.3 High-Rate Optimum Quantization
At high rates, the design of optimum quantizers becomes simple, at least in theory. Gish and
Pierce's work [
133
] says that at high rates the optimum entropy-coded quantizer is a uniform
quantizer. Recall that any nonuniform quantizer can be represented by a compander and a
uniform quantizer. Let us try to find the optimum compressor function at high rates that
minimizes the entropy for a given distortion. Using the calculus of variations approach, we
will construct the functional
