15.0 Codecs

15.0 Codecs#

A primary goal of this chapter is to design codecs. The word is a portmanteau of coder and decoder, the two halves of every codec:

Definition 48 (Codec)

A codec is a pair of functions:

  • A coder, which compresses audio \(\mathbf{x}\) into some discrete set of codes, for example, a string of bits.

  • A decoder, which reconstructs audio from those codes. It aims to be the inverse of the coder.

Passing audio through the coder and then the decoder, \(\hat{\mathbf{x}} = \text{Decoder}(\text{Coder}(\mathbf{x}))\), is called a round trip.

A block diagram. On the left, a blue waveform labeled audio x. An arrow leads to a box labeled Coder, then to a string of bits, 0010110, labeled codes, then to a box labeled Decoder, and finally to a red waveform labeled round trip x-hat, which resembles the original but is slightly noisy. A dashed double arrow beneath the diagram connects the two waveforms and is labeled distortion: error(x, x-hat).

Fig. 118 A codec. The coder compresses audio into codes, and the decoder reconstructs audio from the codes. The distortion compares the original audio to its round trip.#

We have already studied one codec, without referring to it as such. Digital audio itself is a “codec” for analog sound. The analog-to-digital converter (sampling, then quantization) is the coder, and its codes are the integers of a digital audio file. The digital-to-analog converter is the decoder.

Rate and distortion#

Codec design has two goals that are fundamentally in tension with one another: (1) use as few bits as possible, and (2) reconstruct the audio as faithfully as possible.

Definition 49 (Rate and distortion)

The information rate of a codec is the number of bits that its codes take up per second of audio:

\[\text{rate} = \frac{\texttt{size}(\text{Coder}(\mathbf{x}))}{T} \quad \left[\frac{\text{bits}}{\text{second}}\right],\]

where \(T\) is the duration of \(\mathbf{x}\) in seconds.

The distortion of a codec is some measurement of error between the input \(\mathbf{x}\) and its round trip:

\[\text{distortion} = \texttt{error}\big(\mathbf{x}, \text{Decoder}(\text{Coder}(\mathbf{x}))\big).\]

A good codec minimizes both.

For example, consider CD-quality digital audio as a codec for analog sound. It stores \(44{,}100\) samples per second for each of \(2\) channels (stereo), at \(16\) bits per sample. Working through the units, its rate is

\[44{,}100 \left[\frac{\text{samples}}{\text{second · channel}}\right] \cdot 2 \left[\text{channels}\right] \cdot 16 \left[\frac{\text{bits}}{\text{sample}}\right] = 1{,}411{,}200 \left[\frac{\text{bits}}{\text{second}}\right],\]

or about \(1411\) kilobits per second (kbps). Since we sample at \(f_s > 2 f_{\max}\), sampling itself is lossless (by the Nyquist-Shannon sampling theorem). So the only distortion of this codec is the quantization noise we studied in Chapter 7, which is about \(96\) dB below full scale, and imperceptible.

From here on, the input to our codecs is “uncompressed” digital audio, rather than analog sound. So a codec has zero distortion if it perfectly reconstructs the digital samples (we no longer count the quantization noise of the original digital audio as distortion). We will also often compare a codec’s rate to the rate of its input:

Definition 50 (Compression factor)

The compression factor of a codec on an input \(\mathbf{x}\) is

\[\frac{\texttt{size}(\mathbf{x})}{\texttt{size}(\text{Coder}(\mathbf{x}))}.\]

For CD-quality audio as the input, it is \(1411\) kbps divided by the rate of the codec. We write compression factors with a \(\times\). For example, a codec with a rate of \(141\) kbps has a compression factor of \(10\times\).

In this chapter, we will study the compression algorithms underlying several file formats, including MP3, FLAC, and MIDI. These make very different tradeoffs between rate and distortion:

A square scatter plot with information rate in bits per second on a logarithmic horizontal axis, from about 30 to 10 million, and distortion on the vertical axis, with four levels from bottom to top: none (lossless), imperceptible, perceptible, and only the score survives. WAV (16-bit PCM) sits at about 1.4 million bits per second with no distortion. FLAC is a short bar from about 700,000 to 1 million bits per second, also with no distortion. MP3 is a diagonal bar from 320,000 bits per second with imperceptible distortion to 64,000 bits per second with perceptible distortion. MIDI is a bar from 100 to 1000 bits per second at the top level, only the score survives. A dashed gray arrow labeled better points toward the bottom left corner, in the empty region between MIDI and MP3.

Fig. 119 Approximate rates and distortions of the formats in this chapter, for stereo music, with CD-quality digital audio (16-bit PCM) as the input. Lower is better on both axes.#