Hi, and welcome to our special
module on the MP3 audio encoder.
MP3 is a shorthand for MPEG layer 3, and
MPEG is a shorthand for
the Motion Picture Expert Group.
And what this all means is
that at one point in the 90s,
a lot of experts got together and
agreed on a set of standards for
video and audio compression and encoding.
MP3 turned out to be the most
used audio digital format for
digital audio storage,
streaming and playback.
And today a portable music device,
thanks to the MP3 encoding,
can store up to 30,000 songs, which
really means you can carry your entire
music collection with you everywhere.
So in this video we will look at the
technology behind the success of MP3, and
we will describe in detail
how the MP3 encoder works.
You will see how all the tools that
you have learned in our DSB class from
Fourier transform to filtering,
from sampling into quantization,
they all come together
in this application.
So how does the encoding and
decoding process take place?
Supposed you start with a discrete
time sound of signal x[n].
This is processed by the encoder and
converted into a binary string.
The decoder will take
that binary string and
convert it back in to a sound signal y[n].
The goal of this encoding and
decoding chain is to reduce the memory
requirements to store the sound waveform.
And the real achievement of MP3
is its ability to greatly reduce
the amount of data needed
to encode a file, and
this at a very reasonable trade-off with
respect to sound quality degradation.
The data reduction is determined
by looking at the amount of memory
that is necessary to store
the output of the encoder,
by comparing this quantity to the amount
of memory that we should have used
if we had wanted to store the original
signal in uncompressed format.
And remember that an uncoded raw audio
file will require quite a bit of storage.
For instance, if we sample at 48
kilohertz, which is the DVD standard,
and we use 16 bits per sample,
we will need 12 megabytes to store
a single minute of audio in stereo.
On the other hand, a high-quality
MP3 will require just 1.5 megabytes,
which represents almost an order
of magnitude in data reduction.
To achieve this performance, the coding
has to be done in a very clever way, and
one of the key ingredients in MP3 is
a model of the human auditory system.
So MP3 does not attempt to
preserve the original framework.
But rather it focuses on coding
the elements of the waveform
that are most important to our way of
listening to music and hearing sounds.
In particular,
the distortion introduced by the encoder,
the loss of information introduced
by the encoding mechanism,
is placed in parts of the spectrum of
the original signal that we cannot hear.
We will see that in more
detail in just a minute.
As we said, the origins of
MP3 date back to the 90s when
the Moving Picture Expert Group,
in short MPEG,
was set up by the International Standard
Organization to develop algorithms and
standards for audio and video compression.
And the audio compression part of
the standard, the MP3 protocol,
had its origins in a set of
compression algorithms that had been
developed in the 80s by
the Fraunhofer Institute in Germany.
We see a photo of the team
here in this picture.
The MP3 standard was quickly
embraced by the industry, and
this widespread acceptance is what
decreed its success ultimately.
Now let's try to understand how MP3
works using the simple block diagram.
Your input signal x[n] enters
a bank of subband filters.
There are 32 parallel filters
that subdivide the input signal
into 32 independent channels that span
the full spectral range of the input.
Each channel is then quantized
independently using a very clever method,
and the quantized sample
are then formatted and
encoded in a continuous bitstream.
The quantization scheme is clever
because the number of bits
allocated to each subband is dependent
on the perceptual importance
of each subband with respect to
the overall quality of the audio waveform.
In other words,
subbands that are deemed by the
psycho-acoustic model not to be important,
or are difficult to be perceived,
are allocated very few or no bits at all.
Whereas the most perceptually relevant
subbands are allocated the bulk of
the entire bit budget.
The reason why we can safely
allocate different amounts
of bits to the different subbands is to
be found in the so-called masking effect
of the human auditory system.
Suppose you have a sound with
a strong sinusoidal component,
as in this picture here.
The blue line represent
the spectrum of the sound, and
here with the red dot we indicate
the strong sinusoidal component.
When your ear listens to a sound
like this, a masking effect takes
place whereby frequency components
in the vicinity of the dominant peak
are not heard unless they are louder
than a given masking threshold.
In this figure, for example,
the masking threshold is
indicated by the red dotted line.
And what it indicates is that anything in
the spectrum that falls below the red line
will not be heard and
therefore can be removed without
any loss of perceptual quality.
Masking effects are something
that we experience every day.
Imagine being in a perfectly quiet room,
like in your home at night.
You can even hear your wristwatch ticking.
But of course, you wouldn't be able to
hear that noise in normal conditions
during the day, when a lot of other
auditory stimuli are reaching your ears.
Although if you were to record the audio
environment and analyze its spectrum,
you will see that it still contains the
information about your wristwatch ticking.
The shape of the masking threshold
is a function of the loudness and
the frequency of the dominant tone.
And it has been determined experimentally
by running a lot of listening
tests with human subjects.
Masking in the human ear takes
place within the critical bands.
And critical bands
are portions of the spectrum
that are treated by
the ear as a single unit.
Everything that happens within a critical
band cannot be further resolved
by the ear, so two different frequencies
taking place in the same critical band
are perceived as a single tone.
There are approximately 24 critical
bands in the human ear, and
here is a picture of their
distribution in frequency.
As you can see,
they get wider as we go up in frequency,
they follow a logarithmic scale.
Which means that the resolution power of
the ear is stronger at low frequencies,
whereas at high frequencies
we're less discriminant.
And therefore, when we quantize
things across critical bands,
we can probably fit more noise in the high
frequencies than in the low frequencies.
In the end, the purpose of
the psycho-acoustic model is to compute
the minimum number of bits that we need
to use to quantize each of the 32 subband
filter outputs so that the perceptual
distortion is as little as possible.
In the end we're given
a non-uniform bit allocation
which will allocate fewer bits to
the bands where the masking is strongest.
Interestingly enough, the specifications
of the psycho-acoustic model are not part
of the MP3 standard, which means
that manufacturers of MP3 encoders
can compete with better and better
versions of their psycho-acoustic model.
In the end, the number of bits used for
each subband is sent along with
the quantized data to the decoder, so
it doesn't really matter how this
bit distribution has been generated.
From a technical point of view, as you can
imagine, there are a lot of fine details
in the inner workings of
the psycho-acoustic model and
the bit allocation procedure.
And we will not have time to examine
all of this in this presentation, but
we can roughly sum up what happens inside
the psycho-acoustic model like so.
First of all,
remember that all processing is performed
on subsequent windows of a given length.
So that input signal comes in and
the stream of input samples
is cut into chunks of a given length,
say, 1,024 samples.
An FFT is then used to estimate
the energy of the signal in each
of the subbands computed
by the filter bank.
For each subband we try to distinguish
between tonal and non-tonal components,
components that have a strong sinusoidal
shape and noise-like components.
We have looked at masking for
tonal components, but
a similar type of masking takes place for
non-tonal components, and we will have
to take that into account as well.
The individual masking effect for tonal
and non-tonal components is computed for
each critical band.
And then these results are summed together
to obtain a global masking curve for
the audio frame that we are analyzing.
This masking curve is mapped
onto the 32 subbands.
And the number of bits
that we will use for
each subband is computed as a function
of the signal-to-mask ratio,
the power of the signal versus
the masking power for each critical band.
Let's now talk about the implementation
of this subband filtering in MP3.
As we said, the input is split
across a filter bank that
contains 32 filters isolating
different parts of the spectrum.
These filters are implemented as
512-tap FIRs, and they're followed
by a 32-times down-sampler to provide
the independent subband samples.
The filter prototype is a simple
low pass with a cutoff frequency
of pi over 64, and
a total bandwidth of pi over 32.
The different subbands are obtained by
modulating the base filter with a cosine
at multiples of pi over 64, and
the resulting filter bank looks like this.
We're showing the positive
half of the frequency axis.
This would be the first low
pass filter with an x zero.
This is the second one,
the third, the fourth, and so
on, covering the entire spectrum.
Now let's go back to
the implementation of the filter bank.
As you can see here from this block
diagram, each branch in the filter bank
comprises an FIR filter of length 512 and
a 32-time downsampler here.
What this means, of course, is that 31
out of 32 output samples of this filter
are discarded, and so this is, of course,
a very wasteful implementation.
Let's try and
make this a little bit more efficient.
This is actually explained
in the MP3 standard.
We start with the equation that expresses
the output of the subband number i as
a convolution of the impulse response of
the filter for that branch with the input.
And here you see that
the downsampling factor
translates to a factor of 32
in front of the input index.
We can now replace the expression for
the impulse response of the filter
as the prototype impulse response
times the modulating factor that
brings the filter to the proper
position in the frequency band.
And then here we're going
to apply a little trick.
We're going to express the index
k as the sum of two indices.
Namely, we're going to say that k is
equal to 64 times and index p plus q,
where q ranges from 0 to 63 and
p ranges from 0 to 7.
So with this split of the summation,
we can write the previous line as a double
summation, for p that goes from 0 to 7 and
for q that goes from 0 to 63,
as the same term, the modulation
term that we've seen before.
The prototype impulse response and
the input.
Where, again, we have made
the substitution k = 64 p + q.
Okay, so
with this trick we can actually simplify
the first term of this double summation.
Consider the cosine term.
We can write cosine of pi over 64 times 2i
plus 1 times 64p plus some other term,
let's call it f,
that depends only on i and q, and
we don't really care about that.
Now here, 64 is canceled out and
we're left with cosine of 2ip
pi plus p pi plus this term.
And now, well, this is a multiple of 2 pi,
so it doesn't influence the angle.
And here we have a multiple of pi.
And we know that cosine of pi plus alpha
is equal to minus cosine of alpha.
And so in the end,
what we can do is simplify this cosine
as cosine of pi over 64,
times 2i plus 1 times q minus 16.
And add a term minus 1 to the power
of p that we can move over to
the second summation.
And we have a simplified, quote unquote,
expression that looks like so.
An outside sum here that only involves the
cosine modulation, and an inner sum here,
which is a pre-subsampled implementation
of the filtering operation.
If we work out the indices and
convert this to an algorithmic procedure,
this is what we need to do.
We will use a 512-tap
input circular buffer, and
we will shift at each step 32 new input
audio samples, starting from the newest.
So at any time,
the circular buffer is holding 512
input samples in time-reversed order.
Then we take a new 512-point buffer and
we fill it,
sample by sample, with the product between
the prototype impulse response and
the content of the circular buffer.
Next we compute this
intermediate quantity here,
which is the sum of the contents of
this new buffer, 64 points apart.
We can do that for 63 different points.
And if you do the math, there are seven
points that we have summed together for
each q index.
Finally, each subband output is given
by this sum here, where we're taking
the intermediate quantity c[q] that
we computed before and we modulate it
with the cosines at the frequencies
that we had defined in the beginning.
And finally, quantization.
This is where the great bit rate
savings are going to be achieved.
MP3 uses uniform quantization
of subband samples.
And the number of bits per
sample in each subband
is determined by the psycho-acoustic
model, as we explained before.
We also said before that MP3
works on subsequent audio frames,
a frame being a window of input samples
that is processed independently.
There are 36 samples per band and
per frame in the MP3 standard.
And so
since all of these 36 samples are going
to be quantized by the same quantizer,
a rescaling is needed so that we are using
the full range of the quantizer.
Remember how uniform quantization works.
A quantizer maps an input interval
to a set of quantization levels.
Of course, you have to make sure that
the range of your input signal matches
the range of the quantizer.
For instance, this quantizer expects
input to range from minus 1 to 1,
but if your actual input only
lives in this small sub-interval,
you will not be able to make use
of the full quantization range.
So rescaling normally would imply
perfect renormalization of the 36
samples by dividing the samples by
the largest sampling magnitude.
Of course, in order for
the decoder to then reconstruct
the actual levels of the input,
we would have to send this normalization
factor alongside with quantized data.
But this would require
a lot of side information.
We would use 16 or 32 bits to encode
normalization factor and send it along.
Instead, the MPEG standard defines
16 predefined scale factors.
We will choose the one that best matches
the actual range of the input and
only use 4 bits to communicate
this range to the decoder,
thanks to the fact that these
predefined levels are set in stone.
Finally, the actual quantization is
performed according to this formula,
where b is the number of bits as
provided by the psycho-acoustic model,
and Qa and Qb,
functions of the number of bits,
are parameters that are encoded
inside the MP3 standard.
Finally, let's listen to some examples.
We all know that MP3 works very well, so
what we want to concentrate on here
is the importance of the variable
bit allocation across the subbands as
performed by the psycho-acoustic model.
So for a fixed bit budget we
could choose to allocate the same
number of bits to all subbands.
This would be uniform bit allocation.
Or we could use
a psycho-acoustic model and
allocate the bits smartly across subbands.
And so here are the examples,
starting with the original signal [NOISE].
Now let's listen to the same
signal encoded with uniform bit
allocation [NOISE].
And finally, this is the result of
a full-fledged MP3 implementation with
psycho-acoustically based
bit allocation [NOISE].
Of course, in both the uniform and
non-uniform bit allocation encoding
schemes, the target bit rate was very,
very low in order to exacerbate
the effects of quantization.
But the principle holds for all bit rates.