Information Representation

📏 1.02 Numbers and quantities

The word number covers several kinds of value:

A quantity is a number with a unit. Large quantities are tidied up with exponents: 23 567 m = 23.567 × 10³ m = 23.567 km. The 10³ is replaced by the decimal prefix kilo.

Computing caused confusion. Memory comes in sizes that are powers of 2, and 2¹⁰ = 1024 is close to 1000, so for years 1 kilobyte was used to mean 1024 bytes. The same computer's specification might quote a 1.6 GHz processor (decimal), 8 GB of RAM (really binary) and a 400 GB disk (decimal). To fix this, the IEC defined binary prefixes:

Choose the prefix that leaves one or two digits before the decimal point: 34 560 bytes = 34 560 ÷ 1024 = 33.75 KiB; 3 456 000 bytes = 3 456 000 ÷ 1024² ≈ 3.296 MiB.

➖ 1.03 Internal coding of numbers

This section covers integers only; numbers with fractional parts come in Chapter 16. An integer can be stored unsigned (never negative) or signed.

Unsigned is simple: the binary value, padded to fit the register. A 16-bit register holds 0 to 65 535. The bigger the range needed, the more bits per value.

Sign and magnitude

The obvious way to show a sign is to give it a bit: the leftmost bit is 0 for + and 1 for −, and the rest holds the size of the number. It is easy for people to read but awkward for the processor (see the problems below).

One's complement and two's complement

The one's complement of a binary number flips every bit. The two's complement is the one's complement plus 1. A quicker way to get the two's complement: working from the right, keep every bit up to and including the first 1, then flip all the bits to its left:

To store a signed integer in two's complement:

• Positive: convert to binary and make sure there is a leading 0 (pad with 0s to fill the register).
• Negative: convert the size to binary, add a leading 0, then take the two's complement.

Points worth knowing about two's complement:

• There is only one zero (sign and magnitude has +0 and −0).
• The leading bit tells you the sign: 0 positive, 1 negative.
• Taking the two's complement twice gets you back to the start.
• Adding leading 0s to a positive number, or leading 1s to a negative one, does not change its value.
• The range is lopsided: with 8 bits it is −128 to +127.

➕ Binary arithmetic

Binary addition follows four rules: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 carry 1, and 1 + 1 + 1 = 1 carry 1.

Overflow

In the sum above, the answer needs five bits. If the register only holds a nibble, the result is stored as 1001 and the answer is wrong. That is overflow.

With signed numbers the danger is hidden. In an 8-bit two's complement register:

Adding two numbers of the same sign and getting the opposite sign is the giveaway. Chapter 6 shows how the processor detects this with its status flags.

Two's complement makes subtraction easy: to subtract, add the negative. A − B is calculated as A + (two's complement of B), and any carry out of the register is ignored. The processor needs only an adder.

🧮 Binary coded decimal (BCD)

Sometimes it is handier to code each denary digit separately. In BCD each digit 0–9 gets its own four-bit code, 0000 to 1001. The codes 1010 to 1111 are never used.

A byte can hold one digit (with four leading 0s), or two digits side by side: packed BCD. Here is 8503 both ways:

Where BCD is used: anything that shows digits one at a time, such as a calculator display or a digital clock, because each digit can be sent straight to its own display segment. It is also used for currency: binary cannot hold most decimal fractions exactly (Chapter 16), but BCD keeps every cent exact.

Adding in BCD

Add 0.26 + 0.85 by adding the nibbles as binary:

Figure 1.02 Incorrect BCD addition

The fix: whenever a nibble is above 1001 (or produced a carry), add 0110 (6) to it and carry 1 to the next digit. Six is the gap between 16, where binary carries, and 10, where denary carries.

Figure 1.03 Correct BCD addition

🔤 1.04 Internal coding of text

ASCII

For text to be stored and shared, every computer must agree on which code stands for which character. The first widely used standard was ASCII, the American Standard Code for Information Interchange, from the 1960s. It is a 7-bit code, so it has 128 codes. Some of them:

What the table shows:

• Some codes are control characters, not printable symbols: NUL, SOH and others were meant to control devices such as printers.
• Most codes are for characters on an English keyboard.
• Digits are in order (0 is 48, 1 is 49 …) and so are letters (A is 65, B is 66 …).
• An upper-case letter and its lower-case partner differ only in bit 5 (counting the least significant bit as bit 0): A is 010 00001 and a is 011 00001. That is a difference of 32.

A digit's code is not its value: the character 1 is 49. Character codes for digits are only for text, such as printing a number; you cannot do arithmetic with them directly.

Over time, countries made their own variations: a UK version swapped # for £, and some codes picked up new meanings (code 1 was often shown as a smiley ☺). Extended ASCII uses all eight bits, giving 256 codes. The extra 128 hold other characters; one widely used set, ISO Latin-1, includes accented letters such as Ç and ü.

🌍 Unicode

ASCII only really suits English. Unicode, standardised internationally as ISO/IEC 10646, aims to give every character in every writing system, plus symbols and emoji, its own unique number called a code point. Code points are written U+ followed by at least four hex digits, e.g. U+0041 for A.

The first 128 code points are the same as ASCII, and U+0000 to U+00FF match ISO Latin-1, so older text still makes sense.

UTF-8

A code point must still be stored as bytes. The most widely used encoding is UTF-8, which uses one to four bytes per character:

• A one-byte code starts with 0, so plain ASCII text is already valid UTF-8.
• A lead byte starts with 11; the number of 1s before the first 0 says how many bytes the character uses.
• Every continuation byte starts with 10, so a program that lands in the middle of a character can find where the next one starts.
• The two-byte form has 11 free bits, so it has room for 2¹¹ = 2048 code points. The Latin-1 extras U+0080 to U+00FF are stored as 11000010 10000000 (C2 80) up to 11000011 10111111 (C3 BF).

✏️ 1.05 Images: vector graphics

An image can be made in a graphics package, or captured by a camera or a scanner. There are two very different ways to store it.

A vector graphic is built from drawing objects: lines, curves, circles, rectangles, polygons and text. It is what CAD (computer-aided design) and drawing packages produce. The file does not store the picture; it stores a drawing list, one command per object. Each command gives the object's properties, for example:

• its geometry: for a circle, the position of the centre and the radius
• the line: its thickness, style and colour
• The fill colour, if the shape is closed

To display the graphic, the software reads the drawing list and calculates where each object goes. If you ask for it bigger, the file is read again and a new set of calculations is done, so the image stays sharp and in proportion, never squashed or stretched.

Only a graph plotter, an expensive specialised device, can draw a vector graphic directly. For other screens and printers the file usually has to be converted to a bitmap first.

🟦 Bitmaps

Most images, such as photographs, are not made of neat geometric shapes, so they are stored as bitmaps. Bitmaps come from scanning, screenshots, cameras and simple paint programs.

A bitmap is a two-dimensional grid of pixels (picture elements). A pixel is the smallest part of the image you can identify, and it has only two properties: its position in the grid and its colour. Whether it is shown as a square, a circle or a dot does not matter.

How many bits store each colour? One bit allows only black and white. Four bits allow simple greys. At least eight bits per pixel are needed for a reasonably realistic image. The number of bits per pixel is the colour depth.

A related term is bit depth: the bits used for each of the red, green and blue components in RGB. The two are sometimes mixed up. A colour depth of 8 gives 2⁸ = 256 colours; a bit depth of 8 gives 256 × 256 × 256 = 16 777 216 colours. The eye cannot tell that many apart, but gradual changes such as a blue sky would otherwise show visible bands of colour.

Resolution matters too. The image resolution is pixels per row × number of rows in the file. The screen resolution is how many pixels a particular screen can show. A screen design must consider both.

A bitmap file does not say how big a pixel is in real life. Scaling an image does not change the number of pixels in it: on a suitable screen you cannot see individual pixels, but magnify it too far and they appear.

📐 Bitmap file size

A large file takes more storage and longer to display or send over a network. A vector file is usually much smaller than an equivalent bitmap. You can calculate a bitmap's size from its resolution and colour depth. A laptop screen of 1366 × 768 with a colour depth of 24:

That assumed the colour depth (bits per pixel) was given. If instead the bit depth is 8, each pixel needs 8 + 8 + 8 = 24 bits.

A real bitmap file is a little larger, because it also starts with a file header describing how the image is coded: at the very least its colour (or bit) depth and resolution.

⚖️ Bitmap or vector?

• Choose a vector graphic for a diagram that is part of an architectural, engineering or manufacturing design.
• A vector file must be converted to a bitmap before it can be printed on a laser or inkjet printer.
• A digital camera produces a bitmap automatically.
• A bitmap is the usual choice for putting an image into a document, publication or web page.

🔊 1.06 Sound

Natural sound is a variation in air pressure that the ear detects. A real sound mixes many waves of different frequencies, so its amplitude changes continuously but irregularly.

To store or transmit it, the analogue signal must become binary. A sound encoder does this in two stages:

1. A band-limiting filter removes high-frequency components. The ear cannot hear them anyway, and they would cause problems for the coding.
2. An analogue-to-digital converter (ADC) turns the analogue data into digital data.

The ADC samples the wave at regular times (the blue lines). It cannot measure the amplitude exactly, so each sample is rounded to the nearest of a fixed set of levels (the horizontal lines). In Figure 1.07, samples 1 and 4 land on a level and are accurate; samples 5 and 6 fall about halfway between two levels and are not.

Two decisions control the quality:

• Sampling resolution: how many bits store each sample. Three bits give only 8 levels, as in the figure, so the rounding error is large. 16 bits is reasonable for most digitised sound.
• Sampling rate: how many samples are taken per second. Nyquist's theorem says you must sample at least twice the highest frequency in the sound.

Raising either the sampling rate or the resolution makes the copy more faithful, and makes the file bigger.

🗜️ 1.07 Compression techniques

Big files need more storage, and, more importantly, take longer to transmit or download. Compression makes them smaller. There are two kinds:

Many real formats combine both.

Every file is binary, so one general lossless method could compress anything: a good program spots repeated patterns without knowing what the file is. In practice most techniques are designed for one type of file.

Run-length encoding (RLE): lossless, good for bitmaps

RLE replaces a run of identical bytes with a count and one copy of the byte. Four identical bytes:

A real scheme also needs a way to tell a count byte from a data byte; there are several, and you do not need the details.

Huffman coding: lossless, good for text

Text must be compressed losslessly, because one wrong character changes the meaning. Huffman coding analyses the text, then gives the most frequent characters the shortest codes instead of a full byte each. The bytes become a bit stream. If a text used only eight letters, the codes could be:

The key is the prefix property: no code is the start of a longer code. So when decoding the bit stream there is never any doubt where one character ends.

Other file types

• Sound, lossless: Huffman coding works because some amplitude values occur much more often than others.
• Vector graphics: best converted to Scalable Vector Graphics (SVG), a markup-language description that compresses well losslessly.
• Sound, lossy: neighbouring samples rarely differ much, so store the differences between samples using fewer bits. Or transform the samples from the time domain into the frequency domain, re-code the barely audible frequencies with fewer bits, then transform back.
• Bitmaps, lossy: choose a scheme with a smaller colour depth and replace each pixel's colour with the closest colour in the new scheme.

📌 Summary

• Any binary code or number can be written down as hexadecimal.
• Signed integers are usually coded in two's complement.
• Binary addition can cause overflow.
• BCD is a convenient code for single denary digits.
• ASCII and Unicode are standard coding schemes for text.
• An image can be stored as a vector graphic or as a bitmap.
• An ADC works by sampling a continuous waveform.
• Lossless compression lets a decoder recover the original file; lossy compression loses some information for good.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

Question 1 uses two successive bytes from a file: 10010101 and 00110011.