Hi and welcome to module 7.2.
Now that we know more or less how to deal
with stochastic serials, we are ready to
look into the inner workings of the
quantizer.
And try to describe the kind of distortion
introduced by the quantizer itself.
The way we will do that is by equating the
distortion to a source of white noise, and
by analyzing the properties of this noise.
Of course, we're analyzing the very simple
type of quantization over a very simple
class of signals.
And quantization it can be designed to be
much more complicated than that.
But this is a very good starting point and
we will leave the design of more complex
systems to your next signal processing
class.
Hi, and welcome to module 7.2 of Digital
Signal Processing, in which we will talk
about Quantization.
We will examine quantization in general
terms, and then concentrate on uniform
quantization and the associated error
analysis.
And then we will briefly talk about
clipping, saturation and companding.
Quantization is really the second half of
this story in the digital signal
processing, the first half being the
discretization of time.
We soon realize that digital devices can
only deal with integers no matter how many
bits we use inside each memory cell, and
so we need to map the numeric range that
discreet time samples live on onto a
finite set of values.
In so doing, the reason irreversible loss
of information because we're chopping the
amplitudes according to the resolution
that our system allows for.
If we are to represent the situation
graphically, we have a sequence of
discrete time samples here that belong,
say to the set of complex numbers.
These samples go through a quantizer and
the sequence of quantized samples come out
where each quantized sample now belongs to
the set of integers.
When modeled input as a stochastic process
and to study the facts of the system we
have to consider several factors.
How many bits per sample this quantizer
will allocate?
What is the storage scheme used to
represent the quantized samples, for
instance, is it fixed point or floating
point.
And what are the properties of the input
as a stochastic process?
What is it's range, and what is it's
probability distribution?
The simplest quantizer is the scalar
quantizer.
In this quantizer, each sample is encoded
visually so we don't take into account
relationship between neighboring samples.
Each sample is quantized independently, so
there is no memory of previous
quantization operations.
And each sample is encoded using R bits.
So, the rate here is R bits per sample.
Let's see what happens when we scalar
quantize an input.
Assume we know that each input sample Is
strictly between A and B.
Each sample is quantized over 2 to the R
possible values, because we are using R
bits per sample.
And this define 2 to the R intervals over
the range A to B.
Each interval will be associated to a
quantization value.
Which means that whenever the sample say,
falls into this interval here.
It will be replaced by this representative
value for the interval, and similarly for
the other intervals.
So, let's look at an example for R equal
to 2, the range a to be would be divided
into 4 intervals and these are the
boundaries of each interval.
We would associate a representative point
to each interval.
And we would encode each interval using 2
bits.
So the sequence zero-zero would be
associated to the first interval, and so
on and so forth.
In other words, the quantized values would
be one of these four possible values.
And internally the quantizer would know
how to associate this binary value to this
real value.
The two natural questions at this point
are what are the optimal interval
boundaries i of k, and what are the
optimal quantization values for each
interval had x of k.
To find an answer, let's consider the
quantization error.
So, this is defined as the difference
between the quantized value.
Namely, the representative value for each
interval, minus the real value.
We modeled the input as a stochastic
process, as we said in the beginning.
And we modeled the error as a white noise
sequence.
In other words, we assume the, the samples
are uncorrelated.
And we assume that all error samples have
the same distribution.
This is a rather drastic assumptions, but
as a first approximation, it will give us
a good feeling for the effects of a
quantizer.
In order to proceed further, we need the
statistical description of the input
samples.
Let's also make some assumptions on the
internal structure of the quantizer.
And let's consider the simple but very
common case of uniform quantization.
The range in this case is split into 2 to
the R equal intervals.
But with delta, which is equal to B minus
A, the range of the input samples, divided
by the 2 to the R, the number of levels
afforded to by a rate of R bits per sum.
So in case of R is equal to 2 as before, a
range will be split into 4 equal with
intervals.
The mean square quantization error is the
variance of the error signal, namely the
expectation of the difference between the
quantized samples and the original
samples.
If we know the probability distribution
function for the input, we can write that
as the integral from A to B of the PDF of
the input times the error function, which
is the quantized value of the integration
variable minus the integration variable
squared.
This is a standard application of the
expectation theorem.
And we can finally split the integral over
the independent quantization intervals,
and we get this last formulation here.
Now, in order to proceed, we need to know
the probability distribution function of
the input to compute these integrals.
So now, we make a further hypothesis on
the input.
We assume that it is uniformly
distributed.
That means that the probability
distribution function is just a constant
from A to B, A value 1 over B minus A.
The mean square error becomes before the
sum of 2 to the R minus 1 independent
integrals.
Each one of which, is the integral over
the quantization interval of the
representative value for the interval
which we haven't determined yet, minus tau
square divided by B minus A.
In order to find the optimal quantization
points, we minimize the mean square error
with respect to the quantization points
themselves.
We take partial derivatives of the error
with respect to x hat of m.
When we take partial derivatives of the
sum, the partial derivative will kill all
terms of the sum except the one that
depends on the derivation variable.
So we're left with an integral over the
interval i m of two times the quantization
point minus tau divided by B minus A and d
tau.
We have to compute this integral over the
quantization interval number m.
And you remember the range is from A to B,
we divide this into two to the r-equal
intervals of size delta.
And the lower and upper boundary for the
interval number m will be a plus m minus
delta and A plus m minus delta plus delta.
In order to minimize the error we set the
partial derivatives to zero for all
quantization intervals and we find that
this happens when then quantization point
is the interval's midpoint with this we
can plot the quantizers characteristic.
Here we show it for R equal to 3, 3 bits
per sample.
And you can see that the quantizer
associates each quantization interval to
its midpoint.
And you have the typical staircase
characteristic of the uniform quantizer.
Back to the mean square error, we now
replace into the expression for the mean
square error, the values that we found in
the previous analysis.
Namely, the boundaries for each
quantization interval, the value for the
meet point and the expression for the
priority distribution of the input.
And if we compute this integral, we obtain
the fundamental result of uniform
quanitization, the mean square error for
uniform quanitizer is equal to delta
square over 12.
Where delta is B minus A divided by 2 to
the R.
If we analyze the error a little bit
further, we can relate the expression of
the error to the expression for the
signal's energy.
Since we assume that the input is
uniformly distributed.
We can compute its variance, ie, its
energy, as B minus A squared over 12.
It's the variance of a uniformly
distributed variable.
And so we can compute the signal to noise
ratio as the power of the signal divided
by the power of the error.
And the signal to noise ratio happens to
be 2 to the 2R, so if the input is
uniformly distributed, and the quantizer
is a uniform quantizer, which means it's
matched to the input.
The signal to noise ratio is only a
function of the number of bits per sample
that we allocate.
We can express this result in decibels by
taking 10 times the log in base 10 of 2 to
the power of 2R.
And we get the famous and handy formula,
of 6 dBs per bit.
In other words, every bit we add to the
internal representation of a quantized
signal adds 6 dBs of signal to noise
ratio.
So, for instance, a compact disc has 16
bits per sample, so, the maximum signal to
noise ratio that you can achieve in a CD
is 96 dBs.
A DVD on the other hand, has 24 bits per
sample, so your signal to noise ratio
grows to 144 dBs.
So what happens if, as is very likely to
happen in real life, the input is not
bounded to a known interval A, B.
Well, we have two choices, the first one
is to clip samples.
So if the sample is smaller than A, we set
it to A and if it's greater than B we set
it to B.
In this case, we introduce linear
distortion in the signal and this is
really the principle behind distortion
boxes for guitars.
So, interesting, but not necessarily what
we want to hear all the time.
Alternatively, we can use a saturation
curve to smoothly map the input onto the
desired range.
This is closer to the saturation
characteristic of old electronic
components, such as tubes, that are
praised by audiophiles for their lack of
audible distortion.
We can plot the clipping and saturation
curves by taking for instance, the
interval minus 1, 1.
And we can see the clipping curve would
map values outside of the range to the
edge of the range.
Whereas, the saturation curve is linear
around zero and then tapers off
asymtodically.
If the input is not uniform, we can still
use a uniform quantizer, and accept an
error penalty.
For instance, if the input is Gaussian, it
can be shown that the mean square error
has this form.
It depends now of course on the variance
of the input, but even for input signals
with unit variance, it would be larger
than delta squared over 12.
Alternatively, if we know the exact
probability distribution function for the
input, we can use the Lloyd-Max algorithm
to design an optimal quantizer for the
input.
Alternatively, a common practice in audio
signal processing is the use of
companders.
The idea is that samples from signals such
as speech or music will be generally small
in amplitude with the occasional excursion
into the outer reaches of the range.
So for instance, this is a mu law
compander, commonly used in radio and you
see that small values, say between here
and here get allocated to a wide number of
quantization levels.
Whereas the rest of the range will share
the other half.
So there's a, so say, 10% of the range
will get 50% of the quantization level and
the remaining 90% will get the remaining
50%.
So we have more precision for the values
that we know to be more probable.