Sampling and Quantisation

Two continuities

Until now we have worked comfortably with messages already made of separate bricks: letters from an alphabet, numbered boxes or clean strings of bits. Nature, however, does not present itself neatly packed into digital cubes. A song is a wave of air pressure vibrating smoothly and without a break in time. A painting or a landscape is a flood of light whose shades slide continuously across a canvas. Both are continuous phenomena in two ways at once: they are continuous in space or time (between any two instants there is an infinity of intermediate moments) and they are continuous in intensity (between a whisper and a shout, or between two shades of blue, there is an infinity of intermediate degrees).

A computer, though, is a finite machine: its memory can hold neither an infinity of instants nor an infinity of shades. To bring nature into circuits of silicon we are obliged to make two clean cuts. The first cut, called sampling, sections time or space: we measure the signal only here and there, at regular intervals of the clock, ignoring completely what happens between measurements. The second cut, called quantisation, sections the measured values: every continuous value is rounded to the nearest step on a finite scale of preset values. Every photograph in your telephone and every tune heard through headphones is the fruit of these two cuts.

The two operations are completely independent of one another. We may choose to measure very many times a second while using a ruler with coarse steps, or to measure seldom but with microscopic precision on every step. The marks each cut leaves are utterly different and deserve to be made out one at a time, patiently.

Sampling

A sample is simply a “snapshot” of the signal taken at a precise moment in time: a reading of the height of the sound wave in that microsecond. How often we take those measurements in a second is called the sampling rate. Between two successive measurements we keep absolutely nothing, and on playback the device must reconstruct the shape of the original wave. The most naive and direct method of restoring it — which you can try in the figure below — is to join the measured points with straight lines, as in a children’s drawing.

If we set the points very close together, the broken line follows the original curve so faithfully that eye and ear can no longer make out any departure. But if we thin the samples out, the angles turn sharp and the rapid oscillations are lost entirely. So far everything looks like a gradual, predictable loss: the more rarely we measure, the more washed-out the sound becomes. Yet if we drop the rate below a certain limit, something spectacular and deeply unsettling happens.

Aliasing and the Nyquist rate

Have you ever seen in a western how the wheels of an accelerating wagon seem at some point to slow down, stop dead or even turn strangely backwards? Or filmed helicopters whose blades seem frozen in the air? That is an optical illusion caused by the fact that a camera samples the world in discrete frames (24 frames a second, say). When the motion is too swift relative to the frame rate, a rapid movement becomes absolutely identical, point for point, with a false slow one.

In signal theory this deceiving mask is called aliasing (from the Latin for “under another name”). When we sample a fast wave too rarely, the measured points land exactly on the path of a slow wave that never existed in reality. It is not a fault of the measuring device — the measurements are correct to the millimetre — but a fatal mathematical ambiguity: the same string of numbers fits both a real high vibration and a low phantom. On playback the device will always choose the slower version, inventing false sounds that soil the music.

Where does the saving boundary lie? The answer is a jewel of modern science, called the the Nyquist rate, formulated by Harry Nyquist and proved faultlessly by Claude Shannon: to capture and rebuild a wave with perfect fidelity, we must measure it at a frequency strictly greater than twice the fastest oscillation in its make-up. If a wave holds frequencies up to f oscillations per second, we need at least 2f samples per second. Keep that golden rule and the miracle happens: a continuous wave, with its infinity of instants, is preserved with no loss of information at all in a discrete string of numbers.

That is why the music on a compact disc (CD) is recorded at exactly 44,100 measurements a second: human hearing can perceive sounds up to about 20,000 vibrations a second (hertz). Twice that limit is 40,000, and the 44,100 give a comfortable margin so that an electronic filter can cut away in advance any ultrasonic noise that is too fast. What is deliberately cut at the input can never come back as a parasitic alias.

Quantisation

If sampling solved the problem of time, the second cut solves the problem of the size of the values. In nature a guitar string can vibrate at any intensity from a continuum with no steps in it. But a computer’s memory works with bits: if we allot b bits to every measurement, we have at our disposal a scale with exactly 2^b possible steps (as we learned in the first lesson). To quantise is to take the true value of the wave and round it to the nearest permitted step.

The difference between the true height of the wave and the step onto which it was forced is called the quantisation error. That error is always kept in check: it never exceeds half a step. And the beauty of the binary system is that every extra bit added doubles the number of steps available, cutting the error exactly in two.

Unlike the deceiving monsters of aliasing, the quantisation error is friendly and gentle. To the ear it does not create phantom melodies; it is heard as a discreet, even hiss in the background, called quantisation noise. If we use only 8 bits per sample (256 steps), the hiss is still noticeable in very quiet musical passages. But if we move to 16 bits (standard CD quality, with more than 65,000 fine steps), the steps become so small that the background noise falls far below the biological threshold of the human eardrum. The music simply sounds crystalline.

Images

Exactly the same two cuts govern the visual world as well, the only difference being that the space of an image has two dimensions — width and height. Spatial sampling cuts the picture into a fine grid of small squares called pixels, and their density forms the resolution of the screen. Quantisation settles how many steps of brightness and colour each pixel can take, a quantity known as colour depth.

Each cut leaves its own distinct mark on the image, and an attentive eye soon learns to tell them apart. When quantisation is too poor (too few bits of colour), we get banding: a clear vault of sky, which in nature passes imperceptibly from azure to deep blue, breaks abruptly into coarse stripes with visible edges, because dozens of fine shades are crowded onto the same step.

If, on the other hand, the sampling is too sparse (insufficient resolution) and the image holds fine, dense detail — the stripes of a shirt or the bricks of a building — two-dimensional aliasing appears, known as the moiré effect: strange waves, fans or large grids suddenly show up that are not on the real shirt at all. As with sound, the only remedy is to smooth the image optically before the sensor captures it; once the alias has been recorded it has merged with the data and can never be separated out again.

What it takes up

Having settled the rules of the game, we can easily work out the real cost of the digital world. Take a minute of stereo music at compact-disc quality: 44,100 samples a second, times 16 bits per sample, times 2 channels (left and right), for 60 seconds. The result is dizzying: nearly 85 million bits, that is about 10 megabytes for a single minute of listening. A modern 12-megapixel photograph (4000 by 3000 points), with 8 bits for each of the three primary colours (red, green, blue), gathers in a single shot more than 288 million bits — roughly 36 megabytes of raw data.

The lossless compression methods we studied in the second lesson (such as the Huffman algorithm) can squeeze these numbers, but only modestly: neighbouring pixels resemble one another, yet are rarely perfectly identical. The spectacular saving that made possible the modern internet of images and streaming music is called lossy compression (the way the famous JPEG or MP3 formats work). This bold compression knowingly throws away exactly those microscopic details that the biology of the human eye or ear cannot notice anyway — very faint sounds masked by a thunder of drums, or imperceptible shades within a shadow — and only then compresses what is left. Files thus shrink tenfold or even twentyfold, without our experience of listening or watching suffering at all.

This distinction hides a deep philosophical view: lossless compression is a strictly physical and mathematical method, completely neutral — it does not care whether the data represent a ninth symphony or engine noise. Lossy compression, by contrast, always presupposes a model of the human observer. It does not try to preserve the outer world in itself, but only what is relevant to our senses. And the great models of artificial intelligence we shall explore later in the course carry this idea to its height: they learn to retain not every mechanical detail, but the meaningful essence of the world.

The world, as a string of bits

Having come this far, the first great part of our course, devoted to Information, closes its circle. We have seen how any phenomenon in nature — a whisper, a ray of sun, the warmth of an afternoon, the position of a planet or the press of a key — can be translated without remainder into a clean string of bits. Information theory has shown us with astonishing precision how short that string can be made by compression and how sturdily it can be clothed against storms of noise by correcting codes. Nothing of the world’s richness is lost by accident: sampling below the Nyquist rate and quantisation are the only gates where a toll is paid, and we choose both in full awareness.

There remains, though, the great physical question we have left waiting since the first page: what kind of material object can house a bit, and what force in the universe can switch it from 0 to 1? With that curiosity in our hearts we step into Part II of our journey, opening the door to the fascinating world of matter and the electronic switch.