Data representation, multimedia and compression

Binary magnitudes and the two systems of prefixes

A bit is one binary digit, a nibble is 4 bits and a byte is 8 bits. Everything in this section is about counting those units, and the awkward part is that two systems of prefixes are in use at the same time. Memory is made of cells selected by binary addresses, so the number of locations in a memory chip is always a power of two: 2^10 = 1024, 2^20 = 1 048 576, 2^30 = 1 073 741 824, 2^40 = 1 099 511 627 776. The prefixes that describe these powers of two are the binary prefixes: kibi, mebi, gibi and tebi.

The prefixes you meet in physics, and in advertising, are the decimal prefixes: kilo, mega, giga and tera, which are powers of ten. One kilobyte (kB) is 1000 bytes, but one kibibyte (KiB) is 1024 bytes. One megabyte (MB) is 1 000 000 bytes, but one mebibyte (MiB) is 1 048 576 bytes. The symbols matter as well as the words: the binary prefixes always take the letter i, so KiB, MiB, GiB and TiB are the binary ones and kB, MB, GB and TB are the decimal ones.

The gap between the two systems grows at every step, because you are multiplying by 1024 instead of 1000 each time: the binary unit is about 2.4% larger at kilo, 4.9% at mega, 7.4% at giga and 10.0% at tera. That is why a hard drive sold as 1 TB holds 10^12 bytes, which an operating system working in powers of two reports as about 931 GiB. The manufacturer is not lying and the computer is not broken; they are using different prefixes, and an exam question that asks you to explain the discrepancy wants exactly that sentence.

In an exam, always say which system you are using. RAM, cache sizes and file sizes within an operating system are usually quoted in binary prefixes because they are powers of two; storage device capacities, network speeds and data transfer allowances are usually quoted in decimal prefixes. If a question simply says GB and asks for a number of bytes, use 10^9 and say so; if it says GiB, or asks about a memory chip, use 2^30.

• kibi (Ki) = 2^10 = 1024, against kilo (k) = 10^3 = 1000.
• mebi (Mi) = 2^20 = 1 048 576, against mega (M) = 10^6 = 1 000 000.
• gibi (Gi) = 2^30 = 1 073 741 824, against giga (G) = 10^9 = 1 000 000 000.
• tebi (Ti) = 2^40 = 1 099 511 627 776, against tera (T) = 10^12 = 1 000 000 000 000.
• 1 byte = 8 bits, 1 nibble = 4 bits; a 4 GiB memory module holds 4 x 2^30 bytes.
• The binary prefix always contains an i: KiB is 1024 bytes, kB is 1000 bytes.

Number bases, conversion, BCD and where each is used

Denary is base 10 and uses the digits 0 to 9. Binary is base 2, using only 0 and 1, which suits a circuit that can be on or off. Hexadecimal is base 16, using 0 to 9 and then A to F for the values 10 to 15. Hexadecimal exists for one reason: 16 = 2^4, so one hex digit holds exactly four bits, one nibble. Converting between binary and hex is therefore grouping, never arithmetic, which is why programmers use it.

To convert binary to denary, add the place values of the 1 bits: 128, 64, 32, 16, 8, 4, 2, 1, so 1100 1010 = 128 + 64 + 8 + 2 = 202. To convert denary to binary, subtract the largest place value that fits, then the next, and so on: 202 - 128 = 74, 74 - 64 = 10, 10 - 8 = 2, 2 - 2 = 0, giving 1100 1010. To convert binary to hex, group the bits into fours starting from the right and convert one group at a time: 1100 -> C and 1010 -> A, so 202 is CA. To convert hex to denary, multiply each digit by its power of 16: 2F = 2 x 16 + 15 = 47.

Binary Coded Decimal (BCD) is not a number base. Each denary digit is stored separately in its own nibble, so 47 is stored as 0100 0111, not as the binary 0010 1111. A byte holds two BCD digits, so it can represent 00 to 99, where the same byte in pure binary can represent 0 to 255. The six codes 1010 to 1111 are never used, and that wasted capacity is the price you pay for the convenience.

BCD is used where the digits themselves matter rather than the number as a whole. A calculator, a digital clock or a digital multimeter has to send one digit at a time to a seven-segment display driver, and those drivers expect a BCD digit; converting pure binary into separate decimal digits for display needs extra time and code. Financial and accounting systems also use BCD-based decimal types, because values such as 0.10 cannot be held exactly in binary and rounding errors are unacceptable in money.

Hexadecimal is used wherever a human has to read or write a binary value. Memory addresses in a debugger or a hex dump, machine code instructions and opcodes, colours in a web page such as #FF8000, MAC addresses, IPv6 addresses, error codes, hash values and Unicode code points are all written in hex. The reason is always the same three points: it is far shorter than binary, each digit maps to exactly four bits so conversion is instant, and there are fewer characters to misread.

Negative numbers: one's and two's complement

A fixed number of bits can only hold a fixed range of values, so a decision has to be made about how to represent a negative number. The method used in this syllabus and in real hardware is to give the most significant bit a negative place value. That bit is the sign bit: 0 means the number is positive and 1 means it is negative. The advantage over simply marking a sign is that ordinary binary addition then works for negative numbers with no special cases.

One's complement is formed by inverting every bit: 46 in 8 bits is 0010 1110, so -46 in one's complement is 1101 0001. In 8 bits it covers -127 to +127 and it has two representations of zero, 0000 0000 (+0) and 1111 1111 (-0), which means a test for zero needs two comparisons and arithmetic needs an extra correction step.

Two's complement is formed by inverting every bit and then adding 1, which is the same as subtracting the value from 2^n: 46 is 0010 1110, inverting gives 1101 0001, adding 1 gives 1101 0010, and 256 - 46 = 210 = 1101 0010. In 8 bits two's complement covers -128 to +127 and has only one zero. The range is asymmetric because 1000 0000 is -128 and there is no positive counterpart.

To read a two's complement number back, use -128 as the place value of the sign bit: 1101 0010 is -128 + 64 + 16 + 2 = -46. To change the sign of a number, apply the same invert-and-add-1 operation in either direction, which is why subtraction can be done by addition in hardware. In 16 bits the range is -32 768 to +32 767, so doubling the word length does not simply double the range.

Binary addition, subtraction and overflow

The four rules of binary addition are 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 carry 1, and 1 + 1 + 1 = 1 carry 1. Work from the least significant bit upwards and write the carry above the next column. For example 0010 0011 (35) + 0001 1010 (26) = 0011 1101 (61), and in that sum the carry out of the most significant bit is 0, so nothing has been lost.

Subtraction is done by adding the two's complement. To work out A - B, find the two's complement of B and add it to A, then discard any carry out of the most significant bit. For 61 - 26: 26 is 0001 1010, so -26 is 1110 0110, and 0011 1101 + 1110 0110 = 1 0010 0011. The carry out is discarded and the answer is 0010 0011 = 35. The discarded carry is not a mistake - it is the bit that was borrowed to make the negative number in the first place.

Overflow happens when the true result is outside the range that the word length can represent, so the answer wraps round and is wrong. With signed numbers the reliable test is that the carry into the sign bit differs from the carry out of it, which has a simple consequence: adding two positive numbers and getting a negative result, or adding two negative numbers and getting a positive result, means overflow. For example 100 + 100 in 8-bit two's complement is 0110 0100 + 0110 0100 = 1100 1000, which reads as -56, and -100 + -100 is 1001 1100 + 1001 1100 = 1 0011 1000, which reads as +56. Both results are wrong because 200 and -200 are outside -128 to +127.

A carry out of the most significant bit is not the same thing as overflow. Adding -1 and +1 gives 1111 1111 + 0000 0001 = 1 0000 0000: there is a carry out, but the answer 0 is correct and there is no overflow. In unsigned arithmetic, overflow is simply a result that needs more than the available bits, so 255 + 1 = 0 with a carry out. When overflow occurs a program must either test the processor's overflow flag and handle the error, or use a wider word length such as 16 or 32 bits.

Character data and character sets

A computer stores characters as numbers, so every character set is a published table that maps each character to a unique binary code. The set is agreed in advance so that a file written on one machine can be read on another. The three the syllabus names are ASCII, extended ASCII and Unicode, and the differences between them are all about how many bits are used and whose characters are included.

ASCII uses 7 bits, so it defines 128 characters. Codes 0 to 31 are control codes that tell a device what to do rather than printing a symbol - null, tab, carriage return, line feed, escape - and 127 is delete. Codes 32 to 126 are the printable characters, and the arrangement is deliberate: the digits 0 to 9 are at 48 to 57, capital letters A to Z at 65 to 90, and lower case a to z at 97 to 122, so converting between cases is a single bit change and 32 is the space character. You are not expected to memorise any of these codes, but the pattern explains why sorting text alphabetically works.

Extended ASCII uses 8 bits and so defines 256 characters. The extra 128 codes were used for accented letters, currency symbols, box-drawing characters and mathematical symbols, which made it possible to write most Western European languages. The problem is that no single version was agreed: different manufacturers assigned different characters to the same code, so a file written with one version showed the wrong symbols when opened with another.

Unicode is the answer to that problem. It is a single character set intended to cover every character in every written language, plus symbols and emoji, and it currently defines well over 100 000 characters. Unicode is a set of code points, usually written U+0041, and it is stored using an encoding such as UTF-8, UTF-16 or UTF-32. UTF-8 is variable length: it uses 1 byte for the first 128 code points, which are identical to ASCII, and up to 4 bytes for characters from other scripts, which is why an old ASCII file is still valid UTF-8 and why English text stays compact while Chinese or Arabic text takes more space.

Bitmap images: encoding, file size and the effect of changing them

A bitmapped image is a rectangular grid of pixels. Each pixel holds one colour, stored as a binary code whose length is the colour depth, also called the bit depth: 1 bit gives 2 colours, 8 bits give 256, 16 bits give 65 536 and 24 bits give 16 777 216, which is enough for photographic work. The image is stored as the pixel values written in order, usually row by row, and a palette or colour table may be used when the depth is small so that each pixel stores an index instead of a full colour.

Before the pixel data comes the file header, which is metadata about the file rather than part of the picture: an identifier that shows the file type, the width and height in pixels, the colour depth, the resolution metadata used for printing, the palette if there is one, the compression method used, and the offset at which the pixel data starts. Without the header the pixel data is just a long stream of bits with no way of knowing where one row ends and the next begins, so no program could draw it. The header is small and is normally ignored in file size estimates.

Image resolution is the number of pixels in the image itself, quoted as width x height, so a 4000 x 3000 image contains 12 million pixels. Screen resolution is the number of pixels the display can show, such as 1920 x 1080. They are different things: an image larger than the screen has to be scrolled or scaled down to fit, and scaling down throws pixels away. For printing, resolution is often quoted in dots per inch, which is why the same image can look sharp on a screen and soft on a poster.

The file size is estimated as width x height x colour depth in bits, divided by 8 to convert to bytes, plus a small allowance for the header. A 4000 x 3000 image at 24 bits is 4000 x 3000 x 24 = 288 000 000 bits, which is 36 000 000 bytes, or 36 MB (34.3 MiB). That single calculation shows why uncompressed photographs are so large and why the prefixes of the first section matter.

Changing the image changes both quality and file size, and the two changes behave differently. Increasing the image resolution captures or stores more detail but increases the number of pixels, so the file grows with the square of the change: double the width and the height and the file is four times as large. Reducing resolution makes the file smaller and loses fine detail, and enlarging an image beyond its own resolution cannot add detail - the software interpolates new pixels, so the result looks blocky and soft. Increasing the colour depth gives more colours, smoother gradients and less banding, and increases the file size in direct proportion, because each pixel simply uses more bits. Reducing the colour depth produces visible bands where a gradient should be, and can turn a photograph into a posterised image.

Vector graphics and choosing between bitmap and vector

A vector graphic is not stored as pixels at all. It is stored as a drawing list, an ordered set of instructions for drawing drawing objects such as lines, rectangles, circles, curves and text. Each object has properties that describe it: its type, the coordinates of its position, its size or radius, its fill colour, its line colour and thickness, its rotation, and its transparency or layering. A circle might be recorded as a centre at (120, 80), a radius of 40, a red fill and a black outline two units thick.

When the graphic is displayed or printed, the software reads the drawing list and draws the objects at the resolution of the output device. This has two consequences that examiners look for. First, enlarging a vector graphic does not lose quality, because the shape is recalculated rather than resampled - the same circle is drawn with more pixels, not stretched. Second, the file size depends on the number and complexity of the objects, not on the size at which the graphic is displayed, so the same logo file is equally small on a business card and on a billboard.

The limitation is content. A vector graphic is good at shapes with flat or gradient fills and at text, and poor at anything photographic, because a photograph contains millions of subtly different colours that no list of shapes can describe. Attempting photographic realism in vector produces very large files and still looks artificial. A vector file that includes a photograph therefore embeds a bitmap inside the drawing list, which is why some logos contain a raster element.

The choice for a given task is decided by the content and the use, not by habit. If the picture is made of shapes and has to be scaled to different sizes, use a vector. If the picture is a photograph, a scan, a screenshot or anything with continuous tone, use a bitmap, and accept that it has one fixed resolution.

Sound: sampling, encoding and file size

A sound is a pressure wave, and a microphone converts it into a voltage that changes continuously. That is analogue data: the value exists at every instant and can take any value in a range. A computer can only store numbers, so the wave must be converted into digital data by an analogue-to-digital converter, which does two things: it measures the wave at regular intervals, and it rounds each measurement to the nearest available binary value.

Sampling is the taking of those measurements. The sampling rate is how many samples are taken per second, measured in hertz: a CD uses 44 100 samples per second. The sampling resolution, also called the bit depth, is the number of bits used for each sample, so 16-bit sampling gives 65 536 possible amplitude levels. Rounding each sample to the nearest level is called quantisation, and the small error it introduces is heard as low-level noise.

The file size follows from those two numbers: sampling rate x sampling resolution x duration in seconds x number of channels, divided by 8. A three-minute stereo track at 44 100 Hz and 16 bits is 44 100 x 16 x 180 x 2 = 254 016 000 bits, or 31 752 000 bytes, about 31.8 MB. Compare that with a bitmap; the same arithmetic applies, and again the division by 8 catches people out.

Changing either setting has a predictable effect. Raising the sampling rate records the wave more often, so rapid changes are captured and higher frequencies are preserved, and the file size rises in direct proportion. Lowering it loses the fast changes: high frequencies disappear, and a rate that is too low for the sound being recorded misrepresents the wave altogether. Raising the sampling resolution gives more amplitude levels, so each sample is closer to the true value, the quantisation noise falls and the dynamic range improves, and again the file size rises in proportion. Lowering it produces audible hiss and a flattened, distorted sound. Typical settings are 44 100 Hz at 16 bits for music, and 8 000 Hz for speech in a telephone system, where the range of frequencies needed is much smaller.

Compression: lossy, lossless and the methods used for each file type

Compression reduces the number of bits needed to store or transmit the same content, and the reasons are practical: storage costs money, a network has limited bandwidth, and a smaller file uploads, downloads, streams and backs up faster. A web page of uncompressed 24-bit photographs would take seconds to load on a slow connection, and a music library of uncompressed audio would fill a phone several times over.

Lossless compression reduces the file and lets the original be reconstructed exactly. It works by finding and removing redundancy - repeated patterns, unused space in the encoding, predictable sequences. Lossy compression reduces the file much further by permanently discarding data that is judged to matter least, usually because a human eye or ear will not notice its absence. The discarded data can never be recovered, and repeated lossy compression of the same file makes the loss worse each time.

Run-length encoding (RLE) is the simplest lossless method. A run of identical values is replaced by a count and the value: a row of pixels of 12 white, then 3 black, then 5 white is stored as 12W 3B 5W instead of twenty separate values. RLE works extremely well on images with large areas of one colour - icons, logos and scanned line drawings - and on fax pages, which are mostly long runs of white. It works badly on photographs, where neighbouring pixels almost never share a value for long, because every short run still needs a count, and the file can end up larger than the original.

Different file types are compressed in different ways. A text file is compressed losslessly, usually by a dictionary method that replaces frequently repeated words and sequences with short codes, as ZIP and GZIP do; lossy compression of text is never acceptable because every character carries meaning. A bitmap image can be compressed with RLE where there are flat areas of colour, with a lossless format such as PNG for graphics and screenshots, or with a lossy format such as JPEG for photographs, which discards fine colour detail and high-frequency information that the eye is unlikely to notice. A vector graphic is already a compact list of objects, so it is compressed by removing unused or redundant properties, rounding long coordinate values, merging repeated objects and then applying a general lossless method such as the DEFLATE compression used inside an SVG file; the savings are real but smaller than for a bitmap, because there was less redundancy to remove. A sound file can be compressed losslessly with a format such as FLAC, which typically halves the size by predicting each sample from the ones before it, or lossily with MP3 or AAC, which use a model of human hearing to discard quiet sounds that would be masked by louder ones at the same moment.