Databases Reference
In-Depth Information
Substituting the expression for
c
(
x
)
in Equation (
66
), we get the expression for the entropy of
the optimum quantizer:
log
2
x
max
M
H
(
Q
)
=
h
(
X
)
−
(72)
Note that while this result provides us with an easy method for designing optimum quan-
tizers, our derivation is only valid if the source
pdf
is entirely contained in the interval
[−
, and if the step size is small enough that we can reasonably assume the
pdf
to be constant over a quantization interval. Generally, these conditions can only be satisfied if
we have an extremely large number of quantization intervals. While theoretically this is not
much of a problem, most of these reconstruction levels will be rarely used. In practice, as men-
tioned in Chapter 3, entropy-coding a source with a large output alphabet is very problematic.
One way we can get around this is through the use of a technique called
recursive indexing
.
Recursive indexing is a mapping of a countable set to a collection of sequences of symbols
from another set with finite size [
85
]. Given a countable set
A
x
max
,
x
max
]
= {
a
0
,
a
1
,...
}
and a finite set
1, we can represent any element in
A
by a sequence of
elements in
B
in the following manner:
B
= {
b
0
,
b
1
,...,
b
M
}
of size
M
+
1.
Take the index
i
of element
a
i
of
A
.
2.
Find the quotient
m
and remainder
r
of the index
i
such that
i
=
mM
+
r
3.
Generate the sequence
b
M
b
M
···
b
M
b
r
m
times
B
is called the representation set. We can see that given any element in
A
we will have a
unique sequence from
B
representing it. Furthermore, no representative sequence is a prefix
of any other sequence. Therefore, recursive indexing can be viewed as a trivial, uniquely
decodable prefix code. The inverse mapping is given by
b
M
b
M
···
b
M
b
r
→
a
mM
+
r
m
times
Since the mapping is one-to-one, if it is used to convert the index sequence of the quantizer
output into the sequence of the recursive indices, the former can be recovered without error
from the latter. Furthermore, when the size
M
1 of the representation set
B
is chosen
appropriately, in effect we can achieve a reduction in the size of the output alphabets that are
used for entropy coding.
+
Example9.7.1:
Suppose we want to represent the set of nonnegative integers
A
= {
0
,
1
,
2
,...
}
with the
representation set
B
. Then the value 12 would be represented by the
sequence 5, 5, 2, and the value 16 would be represented by the sequence 5, 5, 5, 1. Whenever
the decoder sees the value 5, it simply adds on the next value until the next value is smaller
than 5. For example, the sequence 3, 5, 1, 2, 5, 5, 1, 5, 0 would be decoded as 3, 6, 2, 11, 5.
= {
0
,
1
,
2
,
3
,
4
,
5
}
