Quantized signal: continuous time, discrete values.
Digital signal (sampled, quantized): discrete time, discrete
values.
In
digital signal
processing,
quantization is the process of
approximating ("mapping") a continuous range of values (or a very
large set of possible discrete values) by a relatively small
("finite") set of ("values which can still take on continuous
range") discrete symbols or integer values. For example,
rounding a
real number
in the interval [0,100] to an
integer
0,1,2\dots,100.
In other words, quantization can be described as a mapping that
represents a finite continuous interval I=[a,b] of the range of a
continuous valued signal, with a single number
c, which is
also on that interval. For example, rounding to the nearest integer
(rounding ½ up) replaces the interval [c-.5, c+.5) with the number
c, for integer
c. After that quantization we
produce a finite set of values which can be encoded by binary
techniques for example.
In signal processing, quantization refers to approximating the
output by one of a discrete and finite set of values,
while replacing the
input by a discrete set is called
discretization, and is done by
sampling: the resulting sampled
signal is called a
discrete
signal (discrete
time), and need not be quantized
(it can have continuous
values). To produce a
digital signal (discrete time and discrete
values), one both samples (discrete time) and quantizes the
resulting sample values (discrete values).
Definition
A common use of quantization is in the conversion of a
discrete signal (a
sampled continuous signal) into a
digital signal by quantizing.Both of these
steps (sampling and quantizing) are performed in
analog-to-digital converters
with the quantization level specified in
bits.A
specific example would be
compact disc
(CD) audio which is sampled at 44,100
Hz and
quantized with
16 bits (2
bytes) which can be one of 65,536 (i.e. 2^{16})
possible values (of amplitude) per sample.
Applications
In electronics, adaptive quantization is a quantization process
that varies the step size based on the changes of the input signal,
as a means of efficient compression. Two approaches commonly used
are forward adaptive quantization and backward adaptive
quantization.
In signal processing the quantization process is the necessary and
natural follower of the sampling operation. It is necessary because
in practice the digital computer with is general purpose CPU is
used to implement DSP algorithms. And since computers can only
process finite word length (finite resolution/precision)
quantities, any infinite precision continuous valued signal should
be quantized to fit a finite resolution, so that it can
berepresented (stored) in CPU registers and memory.
We shall be aware of the fact that, it is not the continuous values
of the analog function that inhibits its binary encoding, rather it
is the existence of infinitely many such values due to the
definition of continuity,(which therefore requires infinitely many
bits to represent). For example we can design a quantizer such that
it represents a signal with a single bit (just two levels) such
that, one level is "pi=3,14..." (say encoded with a 1) and the
other level is "e=2.7183..." ( say encoded with a 0), as we can
see, the quantized values of the signal take on infinite precision,
irrational numbers. But there are only two levels. And we can
represent the output of the quantizer with a binary symbol.
Concluding from this we can see that it is not the discreteness of
the quantized values that enable them to be encoded but the
finiteness enabling the encoding with finite number of bits.
In theory there is no relation between quantization values and
binary code words used to encode them (rather than a table that
shows the corresponding mapping, just as examplified above).
However due to practical reasons we may tend to use code words such
that their binary mathematical values has a relation with the
quantization levels that is encoded. And this last option merges
the first two paragrahs in such a way that, if we wish to process
the output of a quantizer within a DSP/CPU system (which is always
the case) then we can not allow the representation levels of the
quantizers to take on arbitrary values, but only a restricted range
such that they can fit in computer registers.
A quantizer is identified with its number of levels M, the decision
boundaries {di} and the corresponding representation values
{ri}.
The output of a quantizer has two important properties: 1) a
Distortion resulting from the approximationand 2) a Bit-Rate
resulting from binary encoding of its levels. Therefore the
Quantizer design problem is aRate-Distortion optimization
type.
If we are only allowed to use fixed length code for the output
level encoding (the practical case)then the problem reduces into a
distortion minimization one.
The design of a quantizer usually means the process to find the
sets {di} and {ri} such that a measure ofoptimality is satisfied
(such as MMSEQ (Minimum Mean Squarred Quantization Error))
Given the number of levels M, the optimal quantizer which minimizes
the MSQE with regards to the given signal statistics is called the
Max-Lloyd quantizer, which is a non-uniform type in general.
The most common quantizer type is the uniform one. It is simple to
design and implement and for most casesit suffices to get
satisfactory results. Indeed by the very inherent nature of the
design process,a given quantizer will only produce optimal results
for the assumed signal statistics. Since it isvery difficult to
correctly predict that in advance, any static design will never
produce actualoptimal performance whenever the input statistics
deviates from that of the design assumption.The only solution is to
use an adaptive quantizer.
Mathematical description
Quantization is referred to as
scalar quantization, since it operates
on scalar (as opposed to multi-dimensional
vector) input data.In general, a scalar
quantization operator can be represented as
- Q(x) = g(\lfloor f(x) \rfloor)
where an integer result i = \lfloor f(x) \rfloor that is sometimes
referred to as the
quantization index,
- f(x) and g(i) are arbitrary real-valued functions.
The integer-valued quantization index i is the representation that
is typically stored or transmitted, and then the final
interpretation is constructed using g(i) when the data is later
interpreted.
In computer audio and most other applications, a method known as
uniform quantization is the most common. There are two
common variations of uniform quantization, called
mid-rise
and
mid-tread uniform quantizers.
If x is a real-valued number between -1 and 1, a mid-rise uniform
quantization operator that uses
M bits of precision to
represent each quantization index can be expressed as
- Q(x) = \frac{\left\lfloor 2^{M-1}x
\right\rfloor+0.5}{2^{M-1}}.
In this case the f(x) and g(i) operators are just multiplying scale
factors (one multiplier being the inverse of the other) along with
an offset in
g(
i) function to place the
representation value in the middle of the input region for each
quantization index. The value 2^{-(M-1)} is often referred to as
the
quantization step size. Using this quantization law
and assuming that
quantization
noise is approximately
uniformly distributed over
the quantization step size (an assumption typically accurate for
rapidly varying x or high M) and further assuming that the input
signal x to be quantized is approximately uniformly distributed
over the entire interval from -1 to 1, the
signal to noise ratio (SNR) of the
quantization can be computed via the
20 log
rule as
\frac{S}{N_q} \approx 20 \log_{10}(2^M)=6.0206 M \
\operatorname{dB}.
From this equation, it is often said that the SNR is approximately
6
dB per
bit.
For mid-tread uniform quantization, the offset of 0.5 would be
added within the floor function instead of outside of it.
Sometimes, mid-rise quantization is used without adding the offset
of 0.5. This reduces the signal to noise ratio by approximately
6.02 dB, but may be acceptable for the sake of simplicity when the
step size is small.
In
digital telephony, two popular
quantization schemes are the 'A-law'
(dominant in Europe) and 'μ-law' (dominant in North America and Japan
).
These schemes map discrete analog values to an 8-bit scale that is
nearly linear for small values and then increases logarithmically
as amplitude grows. Because the human ear's perception of
loudness is roughly logarithmic, this provides a
higher signal to noise ratio over the range of audible sound
intensities for a given number of bits.
Quantization and data compression
Quantization plays a major part in
lossy data compression. In many
cases, quantization can be viewed as the fundamental element that
distinguishes
lossy data
compression from
lossless
data compression, and the use of quantization is nearly always
motivated by the need to reduce the amount of data needed to
represent a signal. In some compression schemes, like
MP3 or
Vorbis, compression is also
achieved by selectively discarding some data, an action that can be
analyzed as a quantization process (e.g., a vector quantization
process) or can be considered a different kind of lossy
process.
One example of a lossy compression scheme that uses quantization is
JPEG image compression.During JPEG encoding,
the data representing an image (typically 8-bits for each of three
color components per pixel) is processed using a
discrete cosine transform and is
then quantized and
entropy coded.
By reducing the precision of the transformed values using
quantization, the number of bits needed to represent the image can
be reduced substantially.For example, images can often be
represented with acceptable quality using JPEG at less than 3 bits
per pixel (as opposed to the typical 24 bits per pixel needed prior
to JPEG compression).Even the original representation using 24 bits
per pixel requires quantization for its
PCM sampling structure.
In modern compression technology, the
entropy of the output of a quantizer
matters more than the number of possible values of its output (the
number of values being 2^M in the above example).
In order to determine how many bits are necessary to effect a given
precision, algorithms are used. Suppose, for example, that it is
necessary to record six significant digits, that is to say,
millions. The number of values that can be expressed by N bits is
equal to two to the Nth power. To express six decimal digits, the
required number of bits is determined by rounding (6 / log 2)where
log refers to the base ten, or common,
logarithmup to the nearest integer. Since the logarithm of 2, base
ten, is approximately 0.30102, the required number of bits is then
given by (6 / 0.30102), or 19.932, rounded up to the nearest
integer,
viz.,
20 bits.
This type of quantizationwhere a set of binary digits,
e.g., an arithmetic register in a CPU, are used to
represent a quantityis called Vernier quantization. It is also
possible, although rather less efficient, to rely upon equally
spaced quantization levels. This is only practical when a small
range of values is expected to be captured: for example, a set of
eight possible values requires eight equally spaced quantization
levelswhich is not unreasonable, although obviously less efficient
than a mere trio of binary digits (bits)but a set of, say,
sixty-four possible values, requiring sixty-four equally spaced
quantization levels, can be expressed using only six bits, which is
obviously far more efficient.
Relation to quantization in nature
At the most fundamental level, some
physical quantities are quantized. This is
a result of
quantum mechanics (see
Quantization ). Signals may
be treated as continuous for mathematical simplicity by considering
the small quantizations as negligible.
In any practical application, this inherent quantization is
irrelevant for two reasons. First, it is overshadowed by
signal noise, the intrusion of extraneous
phenomena present in the system upon the signal of interest. The
second, which appears only in measurement applications, is the
inaccuracy of instruments. Thus, although all physical signals are
intrinsically quantized, the error introduced by modeling them as
continuous is vanishingly small.
See also
External links
Wikis
Quiz
Map
Search
