Finite bits, finite choices

A bit has two possible states: 0 or 1. If a representation uses a fixed number of bits for each item, then it has a fixed number of different patterns available.

With n bits, the number of unique patterns is:

2^n

This is because each extra bit gives two possibilities for every pattern that already exists. Adding one bit therefore doubles the number of patterns.

The patterns are code labels. Their meaning depends on what is being represented: a number, a character, a pixel colour or a sound amplitude level.

Do not confuse the number of patterns with the largest unsigned number. Three bits give eight patterns, from 000 to 111; if these are treated as unsigned numbers, their values run from 0 to 7.

Worked example: choosing enough bits

A door controller must distinguish 18 different states.

1. Four bits provide 2^4 = 16 patterns. This is too few for 18 states.
2. Five bits provide 2^5 = 32 patterns. This is enough.
3. Therefore, the smallest sufficient width is 5 bits. It is fine that 14 of the patterns are unused.

The reliable method is to find the first power of two that is at least as large as the number of required values. Check the next smaller width as well: that proves your choice is the minimum.

Limits on character sets

A computer does not store the appearance of a character directly. In a character set, each character must have its own binary pattern so that it can be distinguished from every other character in that set.

If there are more required characters than available patterns, a unique code cannot be assigned to every character. The representation must leave some characters out or make two characters share a pattern. If two characters share a pattern, the stored code cannot tell them apart.

Seven-bit ASCII is a familiar example of a constrained character code. Seven bits provide 2^7 = 128 patterns. That is a useful set of codes, but it is not enough to give a separate code to every character and symbol used across the world's languages.

Worked example: a station display

A transport display uses a custom code and needs 70 different letters, digits and symbols.

• With 6 bits, it has 2^6 = 64 patterns. Six required symbols cannot receive their own unique pattern.
• With 7 bits, it has 2^7 = 128 patterns. Every required symbol can have a unique code.

One extra bit has not added just one new code: it has doubled the available patterns from 64 to 128.

Limits on bitmap colours

In a bitmap image, the colour of each pixel is stored as a binary pattern. Colour depth is the number of bits used for that pattern.

A one-bit colour depth gives two possible colour codes, not one. A particular palette may map them to black and white, but any two agreed colours could be used.

When the original image needs more colours than the colour depth permits, not every colour can have a different code. Some original colours must be replaced by, or mapped to, an available colour. This reduces colour accuracy and can turn a smooth change of shade into visible steps or bands.

Worked example: a weather icon

An icon is designed with 12 distinct colours but must be stored with a 3-bit colour depth.

• Three bits provide only 2^3 = 8 colour codes, so at least four of the 12 required colours cannot have their own code.
• Some colours must be replaced by one of the eight available colours, losing colour detail.
• Four bits provide 2^4 = 16 colour codes, so 4 bits is the minimum sufficient colour depth.

Colour depth is not the same as resolution. Colour depth controls the number of colour choices for each pixel; resolution describes the number of pixels. If the pixel grid stays unchanged, increasing colour depth does not add more pixels.

Limits on sound precision

When analogue sound is digitised, each sample records the signal's amplitude at one moment. The bit depth gives the number of bits available to store that amplitude.

With n bits per sample, there are 2^n possible amplitude levels:

An analogue signal can take values between the available digital levels. The sampled amplitude must therefore be assigned to an available level, normally the nearest one.

Worked example: representing one sample

Suppose a simple 2-bit system has four available amplitude levels labelled 0, 1, 2 and 3 units. A sampled amplitude of 2.6 units is represented by level 3.

quantisation error = |3 - 2.6| = 0.4 units

If the same amplitude range used a 3-bit depth, it would have eight levels rather than four. The levels could be placed closer together, so the chosen level could be closer to the original amplitude and the quantisation error could be smaller. The representation would be more precise, although it would still use a finite set of levels.

Bit depth is not sample rate. Bit depth controls how many amplitude levels are available for each sample; sample rate controls how often samples are taken. Increasing bit depth does not create extra sampling moments.

Choosing a fit-for-purpose width

The same pattern-limit model applies even though the stored patterns mean different things.

Use this three-step method whenever a context gives a required number of distinct values:

1. Identify what one binary pattern represents.
2. Find the smallest n for which 2^n is at least the number of required values.
3. Explain what would be lost, merged or made less precise if fewer bits were used.

Two final examples

Sound levels: A sensor needs 50 distinct amplitude levels. Five bits give 32 levels, which is too few; 6 bits give 64, so the minimum is 6 bits.

Display symbols: A display needs nine different symbols. Three bits give eight patterns, which is one short; 4 bits give 16, so the minimum is 4 bits.

More bits are not free. Increasing the width gives more unique patterns and can improve coverage or precision, but each encoded character, pixel or sample then contains more bits. A fit-for-purpose representation uses enough patterns for the requirement while recognising that storage is finite.