Information Representation

A computer can only store and process binary: sequences of 0s and 1s, each held as one of two states in a circuit. Everything else (numbers, text, pictures, sound, programs) has to be turned into binary first. Paper 1 asks you to convert between number systems, calculate file sizes and explain how data is encoded and compressed, so this chapter is worth getting completely fluent in.

1.1 Data representation

Binary prefixes and decimal prefixes

A bit is one binary digit. A byte is 8 bits. Large amounts of data use prefixes, and there are two families that mean different things:

A 1 TB drive sold by a manufacturer holds $10^{12}$ bytes, which the operating system may report as about 0.91 TiB. That is why a new drive appears to have "less space" than advertised.

Number systems

You must be able to use three bases and convert between them.

• Denary (base 10) uses the digits 0–9.
• Binary (base 2) uses 0 and 1. The place values from the right are 1, 2, 4, 8, 16, 32, 64, 128.
• Hexadecimal (base 16) uses 0–9 and A–F, where A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

Tap to enlarge

The number 181 shown in binary with its place values, as the denary sum 128+32+16+4+1, and as hexadecimal B5 by grouping the bits in fours; plus a note that in two's complement the left-hand bit is worth minus 128

Close

Binary to denary

Add the place values that have a 1. For 10110101:

$128 + 32 + 16 + 4 + 1 = 181$

Denary to binary

Subtract the largest place value that fits, write a 1, and carry on down. To convert 181: 128 fits (remainder 53), 64 does not, 32 fits (21), 16 fits (5), 8 no, 4 fits (1), 2 no, 1 fits. That gives 10110101.

Hexadecimal

Each hexadecimal digit stands for exactly 4 bits (a nibble), so converting between binary and hexadecimal is just regrouping:

1011 0101  ->  B 5   so  10110101 = B5

To convert hexadecimal to denary, multiply each digit by its place value (16, 1): B5 = 11 × 16 + 5 = 181.

Binary Coded Decimal (BCD)

In BCD each denary digit is stored separately in its own 4 bits. The denary number 259 becomes:

2     5     9
0010  0101  1001

BCD is not the same as ordinary binary (259 in binary is 100000011). It is used where individual digits must be shown or processed, such as the digits on a digital clock, a calculator display, a petrol pump or an electronic scale, and where exact decimal values matter in financial systems, because no conversion rounding is needed.

Negative numbers: two's complement

Unsigned binary can only store zero and positive numbers. Two's complement lets an 8-bit register store from −128 to +127. The most significant bit (the left-hand bit) has a negative place value:

So 10000000 is −128 and 11111111 is −1.

Method to convert a negative denary number, for example −45:

1. Write the positive number in binary: 45 = 00101101.
2. Invert every bit (swap 0 and 1): 11010010.
3. Add 1: 11010011.

Check: −128 + 64 + 16 + 2 + 1 = −45. ✓

Method to convert a two's complement number back to denary: if the left bit is 1, either use the negative place value directly, or invert and add 1 to find the size and then put a minus sign in front.

One's complement

In one's complement you simply invert every bit to make a negative: −45 is 11010010. It has two representations of zero (00000000 and 11111111), which is why computers use two's complement instead. You may be asked for either.

Binary addition and subtraction

Add column by column from the right, using these rules:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 1 = 0, carry 1
• 1 + 1 + 1 (including a carry) = 1, carry 1

Worked example (8-bit): 00101011 + 00110110

  0 0 1 0 1 0 1 1      (43)
+ 0 0 1 1 0 1 1 0      (54)
-----------------
  0 1 1 0 0 0 0 1      (97)

Subtraction is done by adding the negative. To work out 107 − 54, find −54 in two's complement (11001010) and add: the carry out of the left-hand bit is discarded and the 8-bit answer is 00110101 = 53. ✓

Character sets

A character set gives each character a unique binary code.

• ASCII uses 7 bits (128 characters: letters, digits, punctuation and control codes). Extended ASCII uses 8 bits (256 characters) and adds accented letters and symbols. In ASCII the capital letters are in order, so A is 65 and B is 66; lower case a is 97; the digit 0 is 48.
• Unicode uses more bits per character (commonly 16 or 32, with encodings such as UTF-8 and UTF-16) and so can represent the characters of every language, as well as symbols and emoji. The first 128 Unicode characters are the same as ASCII.

1.2 Multimedia

Bitmap images

A bitmap image is a grid of tiny squares called pixels. Each pixel is stored as a binary number that gives its colour. The file also stores a file header holding information needed to rebuild the image, such as its width and height in pixels, the colour depth and the file type.

Key terms:

• Pixel: the smallest single point of an image that can be given a colour.
• Image resolution: the number of pixels in the image (for example 1920 × 1080). More pixels means more detail.
• Screen resolution: the number of pixels the screen can display horizontally and vertically.
• Colour depth (also called bit depth): the number of bits used to store the colour of each pixel. 1 bit gives 2 colours, 8 bits gives 256 colours, 24 bits gives about 16.7 million colours.

Estimating the file size of a bitmap

$\text{file size (bits)} = \text{width} \times \text{height} \times \text{colour depth}$

Divide by 8 to get bytes. Worked example: an image 1 000 pixels wide and 500 pixels high with a colour depth of 24 bits:

$1000 \times 500 \times 24 = 12\,000\,000 \text{ bits} = 1\,500\,000 \text{ bytes} \approx 1.43 \text{ MiB}$

The header adds a small extra amount. In an exam, use the formula above unless you are told to include the header.

Changing the image resolution or colour depth

Vector graphics

A vector graphic is stored as a drawing list: a list of drawing objects such as lines, circles, rectangles and curves. Each object has properties that describe it: for example a circle has a centre point, a radius, a line colour, a line thickness and a fill colour. The picture is drawn again each time it is displayed by following the list.

Tap to enlarge

A small circle drawn as a bitmap, a grid of blue pixels that becomes blocky when enlarged, beside the same circle drawn as a vector graphic, a drawing list giving the object, centre, radius, line and fill colours, which stays smooth when enlarged

Close

Bitmap or vector?

Sound

Sound is an analogue signal: a continuously varying wave. A computer stores digital data, so the sound must be sampled: the amplitude (height) of the wave is measured at regular intervals and each measurement is stored as a binary number.

• Sampling rate: the number of samples taken each second, in hertz (Hz). CD quality is 44 100 Hz (44.1 kHz).
• Sampling resolution (also called bit depth): the number of bits used to store each sample. CD quality is 16 bits.

$\text{file size (bits)} = \text{sampling rate} \times \text{sampling resolution} \times \text{length in seconds} \times \text{channels}$

Tap to enlarge

A grey analogue sound wave sampled at regular intervals: with few samples and a low resolution the red digital copy is rough, and with more samples and a higher resolution it follows the wave closely, but the file is larger

Close

Worked example: 3 minutes of mono sound at 44 100 Hz and 16 bits: $44\,100 \times 16 \times 180 = 127\,008\,000$ bits, which is $127\,008\,000 \div 8 = 15\,876\,000$ bytes (about 15.1 MiB).

1.3 Compression

Compression reduces the size of a file. It is needed because:

• smaller files take less storage space, so more can be kept on a device;
• smaller files take less time and bandwidth to send over a network or stream, and download faster;
• email and websites often limit file sizes, and compressed pages load faster.

Lossy and lossless

How different files are compressed

Text files are compressed losslessly, for example by replacing repeated words or patterns with shorter codes (a dictionary), or by giving common letters shorter binary codes.

Bitmap images can be compressed:

• losslessly, using run-length encoding (RLE);
• lossily (for example JPEG), by reducing the colour depth or resolution, or by discarding fine detail the eye cannot easily see.

Vector graphics are already compact; their drawing lists can be compressed in the same way as text.

Sound files can be compressed lossily, for example in MP3 by:

• perceptual coding: removing sounds that humans cannot hear or would not notice, such as very high or very low frequencies, or quiet sounds hidden by louder sounds;
• reducing the sampling rate or the sampling resolution.

Run-length encoding (RLE)

RLE replaces a run of repeated data by a count and the value. Text example:

AAAAABBBCCCCCCDD   ->   5A 3B 6C 2D

The 16 characters become 8 characters (4 count–value pairs). For an image, each row of pixels is stored as pairs of (number of pixels, colour). RLE works best on data with long runs of identical values, such as a cartoon or a simple logo, and badly on data with few repeats, such as a photograph, where it can even make the file larger.