Databases Reference
In-Depth Information
Notice that the intervals closer to zero are smaller. Hence, the maximum value that the
quantizer error can take on is also smaller, resulting in a better approximation. We pay for
this improvement in accuracy at lower input levels by incurring larger errors when the input
falls in the outer intervals. However, as the probability of getting smaller input values is much
higher than getting larger signal values, on average the distortion will be lower than if we
had a uniform quantizer. While a nonuniform quantizer provides lower average distortion, the
design of nonuniform quantizers is also somewhat more complex. However, the basic idea
is quite straightforward: find the decision boundaries and reconstruction levels that minimize
the mean squared quantization error. We look at the design of nonuniform quantizers in more
detail in the following sections.
9.6.1
pdf-Optimized Quantization
A direct approach for locating the best nonuniform quantizer, if we have a probability model
for the source, is to find the
that minimize Equation (
3
). Setting the derivative of
Equation (
3
) with respect to
y
j
to zero, and solving for
y
j
, we get
{
b
i
}
and
{
y
i
}
b
j
b
j
−
1
xf
X
(
x
)
dx
y
j
=
(27)
b
j
b
j
−
1
f
X
(
x
)
dx
The output point for each quantization interval is the centroid of the probability mass in
that interval. Using the Leibniz integral rule, and taking the derivative of Equation (
3
) with
respect to
b
j
and setting it equal to zero, we get an expression for
b
j
as
y
j
+
1
+
y
j
b
j
=
(28)
2
The decision boundary is simply the midpoint of the two neighboring reconstruction levels.
Solving these two equations will give us the values for the reconstruction levels and decision
boundaries that minimize the mean squared quantization error. Unfortunately, to solve for
y
j
, we need the values of
b
j
and
b
j
−
1
, and to solve for
b
j
, we need the values of
y
j
+
1
and
y
j
. In a 1960 paper, Joel Max [
122
] showed how to solve the two equations iteratively. The
same approach was described by Stuart P. Lloyd in a 1957 internal Bell Labs memorandum.
Generally, credit goes to whomever publishes first, but in this case, because much of the early
work in quantizationwas done at Bell Labs, Lloyd'sworkwas given due credit and the algorithm
became known as the Lloyd-Max algorithm. However, the story does not end (begin?) there.
AllenGersho[
127
] points out that the same algorithm was published by Lukaszewicz and
Steinhaus in a Polish journal in 1955 [
128
]! Lloyd's paper remained unpublished until 1982,
when it was finally published in a special issue of the
IEEE Transactions on Information Theory
devoted to quantization [
129
].
To see how this algorithm works, let us apply it to a specific situation. Suppose we want to
design an
M
-level symmetricmidrise quantizer. To define our symbols, we will use Figure
9.20
.
From the figure, we see that we need to obtain the reconstruction levels
{
y
1
,
y
2
,...,
y
2
}
and
the decision boundaries
{
b
1
,
b
2
,...,
b
2
−
1
}
to design this quantizer. The reconstruction levels
