Let's Build an MP3 Decoder

http://blog.bjrn.se/2008/10/lets-build-mp3-decoder.html

by petercooper • 14 years ago

201 24 14 years ago

blog.bjrn.se

Wow, that takes me back. One of the first "serious" programs I wrote was an mp3 decoder in pascal. It took about 30 minutes per minute of audio to do the decode on my p90. I felt like king of the whole world.

jensnockert2• 14 years ago

Yeah, it is a good thing is that you can do it in essentially any language and it will be fast enough for realtime today.

At least as long as you design it reasonably well.

sliverstorm• 14 years ago

Bubble sort!

psykotic2• 14 years ago

In the same genre and likewise in Haskell, I recommend Exploring JPEG:

http://www.imperialviolet.org/binary/jpeg/

On the decoder side, for someone who has basic familiarity with compression and signal processing, the obstacles in understanding MP3 are polyphase filter banks and the mixed discrete cosine transform, which are not much explained in this article. They both take advantage of alias cancelation properties (in the frequency domain for the filter bank and in the temporal domain for the MDCT) that in my opinion are pretty subtle. The rest of the components in an MP3 decoder have close analogues in image compression (e.g. joint stereo is a decorrelation transform that is analogous to going from RGB to a luminance-chrominance color space), so they shouldn't be difficult to grasp.

For those trickier signal processing parts, Pan's IEEE article A Tutorial on MPEG/Audio Compression is a great place to start:

http://www.ee.columbia.edu/~dpwe/e6820/papers/Pan95-mpega.pd...

darxius• 14 years ago

Great read! (although I admit I'm not completely done it)

I think the whole process of taking something audible and "real" (like sound) and digitizing it is simply amazing.

DarkMeld• 14 years ago

What does it mean when a codec is "lossless"?

ewoodrich• 14 years ago

Think of more like RAR or ZIP compression: filesize it reduced, but no data is lost.

Unlike MP3 which uses a number of lossy compression techniques, including psychoacoustics, that are specifically designed to reduce the bitrate of an audio stream with minimal artifacts.

daeken• 14 years ago

It means that there's no loss of fidelity. If you convert raw audio (a WAV for instance) to MP3, vorbis, or other lossy formats and then convert it back, you'll end up with different (lower fidelity) data. Doing the same with FLAC or another lossless format gives you the exact same data back.

In the image space, PNGs are likewise lossless, whereas JPEG causes a loss of fidelity.

Caerus• 14 years ago

This is in no way rigorous, but hopefully the analogy helps.

Imagine you want to encode something like y = 2 * sin(2 * x) + .1 * sin(10 * x) to save space.

http://www.wolframalpha.com/input/?i=sin%28x%29+%2B+.1*sin%2...

That is composed of two different sine waves added together - one low frequency, large amplitude and one high frequency low amplitude. That can be encoded two different ways - lossy or lossless.

A lossy encoder gets rid of unimportant data and keeps a "close enough" representation of the original. In this example, .1 * sin(10 * t) is a minor component of the overall signal (plot them separately if you need to compare the difference) so the encoder chooses to delete it and only save 2 * sin(2 * t). In a real world sound, this would be like throwing away noise that is so high pitched we can't hear it, or is so quiet we can't detect it. A real encoder has to decide what the "small enough it can be deleted" threshold is, and it's rarely black and white.

A lossless encoder looks at that signal and thinks "there has got to be a more efficient way to store that data". They are both sine functions, so that doesn't need to be repeated twice. "x" is completely unnecessary, because it knows the sine functions are dependent on some variable. So, it could write out something like "sin (2,2) (.1,10)". All of the original data is still there, if whoever receives the data (the decoder) knows how to interpret it.

bwarp3• 14 years ago

Note: A fourier transform is never lossless - it's an approximation (usually a fairly good one though).

ugh• 14 years ago

That's the principle, but not how it really works. As you said, it's only an analogy, but one that comes close to sounding like the real thing and is as such potentially confusing.

Audio codecs don't try to find functions that describe waves, they sample the waves.

What you get from a microphone or an electric guitar is a changing voltage, a wave of some sort. To digitize that wave (i.e. to save it using numbers and not vinyl discs or magnetic tape) you take samples (i.e. measure the voltage) at regular intervals. You typically might do that 48k times or 96k times per second (i.e. have a sampling frequency of 48kHz or 96kHz).

What you do then with those samples is quantize them, i.e. they get an integer depinding on how high or low the voltage is, for example a 16 Bit number.

That's how an analog-digital converter works on a basic level (you also need an filter to get rid of all the frequencies you don't want to digitize). This process is of course lossy. It's not possible to recontruct the wave that was digitized perfectly, it's only an approximation. All analog-digital converters are lossy (in some sense of the word). If you sample at 48kHz all frequencies higher than half of that (24kHz) are irrevocably lost (look up the Nyquist-Shannon Sampling Theorem if you want to know more). Quantization also means that you have to round the voltage you are measuring up or down, the audible effect this has on the sound is that it adds noise.

The parameters are, however, usually chosen in such a way that a human ear can't tell the difference. A healthy and young ear can hear frequencies up to about 20kHz, that's why the music on CDs is sampled at 44.1kHz (40kHz with some safety margin).

But that's only the conversion and it has not much to do with lossy codecs.

A lossless codec takes the result of this digitization (let's say 48k 16Bit numbers for a one second sound) and encodes them in such a way that those exact same 48k 16Bit numbers can be reconstructed after decoding.

Re-encoding a sound file with a lossless codec can consequently still be lossy: If you change the parameters (e.g. you half the sampling rate) you are still losing imformation - but it's at least possible to preserve the result of the original digitization perfectly.

A lossy codec doesn't aim for perfect reconstruction of all the numbers. It uses quirks in human hearing to be more or less precise about how those numbers are reconstructed. For example: A really loud sound masks quieter sounds. It's not possible for humans to hear that quieter sound, so why bother with all that precision for that quiet sound? That's where, for example, MP3 can dynamically decrease the quality. It's quite ingenious, really.

It is of course inevitable that during that process information is lost. It's not possible to get those original 48k numbers back, but at least something that sounds to an human ear more or less like them.

nodata• 14 years ago

Lossless: zip/unzip.

Lossy: jpeg.

getsat• 14 years ago

Or:

Lossless: PNG

Lossy: JPEG

ZeroGravitas• 14 years ago

Another word for lossless is "reversible", i.e. you can get back out what you put in, which isn't the case with mp3, but is with zip or flac. If you don't worry about it being bit exact you can make it a fair bit smaller though, particularly if any of the original data is difficult/impossible to hear.

Qweef• 14 years ago

I don't think the "A Haskell tutorial" part of the submission title is accurate. It's an mp3 tutorial... which happens to use Haskell. Not everything which uses Haskell is specifically about doing so. :-)

petercooper• 14 years ago

Was that actually in the submission title here at HN? I didn't put that into it and it's not there now, so if it was.. we know an admin was fidgeting with it! :-)

rplnt• 14 years ago

Using this codec would probably be illegal in some countries. I guess it is all right to play with it, but don't incorporate it in your applications.

Let's Build an MP3 Decoder

Related Stories