Notes · Computer ScienceUK · A-Levels

Fundamentals of data representation

Inside a computer everything - numbers, text, images, sound - is ultimately a pattern of bits, and this chapter shows exactly how. It develops the number bases and binary arithmetic, signed integers in two's complement, fixed- and floating-point reals, character sets, bitwise operations, the representation of images and sound, and finally data compression and encryption. It is the most calculation-heavy topic in the A-Level, and every value must be computed exactly.

6 sections~22 min reading time3 competenciesLevel Foundation 1 · Standard 3 · Advanced 2

T·0555 / 14

Exam profile

AO1 · Know binary, denary and hexadecimal, two's complement, floating point, character sets, image and sound representation, compression and encryptionAO2 · Convert between bases, perform binary and two's-complement arithmetic, normalise floating-point numbers and calculate file sizesAO3 · Evaluate representation, precision and compression trade-offs

Operators:convertcalculaterepresentnormaliseexplaincompare

basic level

AS-Level expects base conversions, unsigned binary arithmetic, ASCII/Unicode, and basic image and sound representation.

higher level

The full A-Level adds two's-complement signed arithmetic, fixed- and floating-point representation with normalisation and error, bitwise masks, and compression (RLE and Huffman) and encryption (Caesar, Vernam, and public-key principles).

Depth

Text

Contents · 6 sections

Fundamentals of data representation

Number bases and conversions#

FoundationAQA 7517 4.5.1AQA 7517 4.5.2DfE GCE Computer Science - number systems

Denary, binary and hexadecimal reference

Fig. 1The values 0 to 15 in all three bases. Each hexadecimal digit corresponds to exactly one 4-bit nibble, which is why hex is such a convenient shorthand for binary.

A number base (radix) is the number of distinct digits it uses, and it fixes the place values as successive powers of the base. Denary (base 10) uses digits 0-9 with place values

\dots, 10^2, 10^1, 10^0

. Binary (base 2) uses only 0 and 1 with place values

\dots, 8, 4, 2, 1

; it is the native language of the computer because a bit maps directly onto a two-state electronic switch. Hexadecimal (base 16) uses 0-9 then A-F for the values 10-15, with place values

\dots, 256, 16, 1

Hexadecimal is used because it is a compact, human-friendly shorthand for binary: exactly four bits (a nibble) map to one hex digit, so a byte is two hex digits. Long binary strings that are hard to read and easy to mis-copy -

11001011

- become two hex characters -

\text{CB}

- with no loss of information and a trivial mental conversion. This is why memory addresses, colour codes (

\text{\#FF8000}

) and machine code are almost always written in hex.

To convert denary to binary, repeatedly subtract the largest place value that fits (or repeatedly divide by 2 and read the remainders bottom-up). To convert binary to denary, add the place values wherever there is a 1. To convert binary to hex, split the bits into nibbles from the right and translate each; to go from hex to binary, expand each hex digit to its four bits. Denary to hex is easiest done via binary, or by repeated division by 16. The reference table opposite lists the first sixteen values in all three bases - worth knowing by heart.

Units of storage follow from the bit. Eight bits make a byte, the smallest addressable unit and enough for one character or an integer 0-255. Larger amounts use the decimal prefixes kilo, mega, giga and tera (

10^3, 10^6, 10^9, 10^{12}

bytes) as recommended by the specification, alongside the binary kibi/mebi/gibi prefixes (

2^{10} = 1024

2^{20}, 2^{30}

) that reflect the powers of two the hardware actually uses. Being clear about which is meant avoids the common confusion between a 'kilobyte' as 1000 or 1024 bytes.

203 = 128 + 64 + 8 + 2 + 1 = 11001011_2 = \text{CB}_{16}

Denary to binary to hex

Sum the place values that make 203, group the bits into two nibbles, and translate each to a hex digit.

Worked example

Converting 203 to binary and hex

Convert the denary number 203 to 8-bit binary and then to hexadecimal.

Subtract place values
$203 - 128 = 75$ ; $75 - 64 = 11$ ; 32 and 16 do not fit; $11 - 8 = 3$ ; 4 does not fit; $3 - 2 = 1$ ; $1 - 1 = 0$ . So the 128, 64, 8, 2 and 1 columns are set.
Write the bits
Columns 128 64 32 16 8 4 2 1 give 1 1 0 0 1 0 1 1, i.e. $11001011$ .
Group into nibbles
$1100\ 1011$ : $1100 = 12 = \text{C}$ and $1011 = 11 = \text{B}$ .

Result: $203_{10} = 11001011_2 = \text{CB}_{16}$ . Checking: $\text{C} \times 16 + \text{B} = 12\times16 + 11 = 203$ .

Typical mistakes

Grouping bits into nibbles from the left instead of the right when converting to hex - always group from the least-significant end.
Misreading hex digits A-F as ten to fifteen: A = 10, B = 11, ..., F = 15, not A = 1.

Active revision

Convert denary 203 to binary and to hexadecimal, and convert hexadecimal 2F to binary and to denary, showing your working.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education) · AQA A-level Computer Science 7517 specification (AQA)

Signed integers and binary arithmetic (two's complement)#

StandardAQA 7517 4.5.3DfE GCE Computer Science - signed binary

The range of an 8-bit two's-complement integer

Fig. 2The eight-bit patterns span

-128

(10000000) to

+127

(01111111), with 0 at 00000000. The range is asymmetric - one more negative value than positive - because the sign bit carries the place value

-128

To store negative integers, the standard method is two's complement, in which the most significant bit carries a negative place value. In 8 bits the place values are

-128, 64, 32, 16, 8, 4, 2, 1

, so the same eight bits now represent the range

-128

+127

- an asymmetric range with one more negative value than positive. A number is negative exactly when its leading bit is 1. Two's complement is used because it lets the same adder circuit perform both addition and subtraction with no special cases, and there is a single representation of zero.

To negate a number in two's complement - to form

-x

from

x

- you invert all the bits and add 1. For example

+40 = 00101000

; inverting gives

11010111

, and adding 1 gives

11011000

, which reads as

-128 + 64 + 16 + 8 = -40

. The same rule converts a negative pattern back to its magnitude. This 'flip and add one' procedure is the single most-tested manipulation in the topic, so practise it until it is automatic.

The great advantage of two's complement is that subtraction becomes addition: to compute

a - b

you negate

b

and add. The processor's adder handles

35 - 20

35 + (-20)

, and any carry out of the top bit is simply discarded. This is why a CPU needs no separate subtractor - the same arithmetic-logic unit adds signed numbers correctly whether the operands are positive or negative.

Overflow occurs when the true result of an operation lies outside the representable range - for 8-bit signed numbers, beyond

-128

+127

. Adding two positives and getting a negative sign bit (or two negatives giving a positive) signals overflow, and the stored answer is wrong. Overflow is detected in hardware and is a genuine cause of software faults; distinguishing it from a legitimate discarded carry (which is normal in two's-complement addition) is a frequent exam discriminator. A logical shift left multiplies an unsigned value by 2 and a shift right divides by 2, but shifting a signed value needs an arithmetic shift that preserves the sign bit.

\text{range of an } n\text{-bit two's-complement integer} = -2^{n-1} \text{ to } 2^{n-1}-1

Two's-complement range

For $n = 8$ this is $-128$ to $+127$ : the leading bit's place value is $-2^{n-1}$ , giving one extra negative value.

Worked example

Subtraction by adding the two's complement

Compute $35 - 20$ using 8-bit two's-complement arithmetic by negating 20 and adding.

Write the positives
$35 = 00100011$ and $20 = 00010100$ .
Negate 20
Invert $00010100$ to $11101011$ , then add 1 to get $-20 = 11101100$ .
Add 35 and -20
$00100011 + 11101100 = 1\,00001111$ . Discard the carry out of the top bit.

Result: The 8-bit result is $00001111 = 15$ , and $35 - 20 = 15$ . The carry out of the leading bit is discarded, not overflow, because the sign of the result is correct.

Typical mistakes

Confusing overflow (a wrong result outside the range, shown by an unexpected sign change) with a normal discarded carry.
Forgetting the '+1' step of two's-complement negation, or getting the asymmetric range wrong ( $-128$ to $+127$ , not $-127$ to $+127$ ).

Active revision

Represent $-40$ as an 8-bit two's-complement number, then compute $35 - 20$ in 8-bit two's complement by adding the complement, showing the carry, and state the range of an 8-bit signed integer.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Fixed- and floating-point representation#

AdvancedAQA 7517 4.5.4DfE GCE Computer Science - real numbers

A floating-point number's fields

Fig. 3The register is divided into a mantissa (significant bits, in two's complement with an assumed binary point after its sign bit) and an exponent (the power of two, in two's complement). The value is mantissa x 2 to the exponent; shifting the split between the fields trades range against precision.

Real (fractional) numbers are stored in two ways. In fixed-point representation the binary point sits at a fixed position, so bits before it have place values

\dots, 4, 2, 1

and bits after it have place values

\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \dots

. Fixed point is simple and fast but wastes bits: a set number are always reserved for the fractional part, giving a limited range and forcing a compromise between how large and how precise a number can be.

Floating-point representation instead splits the bits into a mantissa (significand) and an exponent, storing a value of the form

\text{mantissa} \times 2^{\text{exponent}}

(shown opposite) - the binary analogue of standard form. Both parts are usually held in two's complement so they can be signed. Moving the exponent lets the same number of bits represent both very large and very small magnitudes, which is why floating point is used for scientific and general real-number arithmetic. The trade-off is fixed: more bits given to the mantissa buy precision; more bits given to the exponent buy range - you cannot increase both without adding bits.

A floating-point number must be normalised to a unique form and to keep maximum precision. Normalisation shifts the mantissa so that (for a two's-complement mantissa) the first two bits differ -

0.1\dots

for a positive number,

1.0\dots

for a negative one - adjusting the exponent to compensate, so no significant bits are wasted on leading zeros. For example

5.5_{10} = 101.1_2

normalises to

0.10110000 \times 2^{3}

: mantissa

01011000

, exponent

0011

. Being able to normalise a denary value into a given mantissa/exponent format, and read one back, is a demanding but standard exam task.

Because only finitely many bits are available, most reals cannot be stored exactly - the value is rounded to the nearest representable number, introducing a rounding error. The absolute error is the difference between the stored and true values; the relative error is that difference as a fraction of the true value. These errors accumulate through a long calculation, which is why floating-point results can drift and why you should never test two floating-point numbers for exact equality. Understanding the range-versus-precision trade-off and the origin of rounding error is examined in evaluative questions.

\text{value} = \text{mantissa} \times 2^{\text{exponent}}

Floating-point value

The mantissa holds the significant digits and the exponent scales them - the binary equivalent of standard form.

\text{relative error} = \dfrac{\lvert \text{stored} - \text{true} \rvert}{\lvert \text{true} \rvert}

Relative rounding error

The absolute error expressed as a fraction of the true value; it accumulates through long calculations.

Worked example

Normalising 5.5 into floating point

Represent 5.5 in denary as a normalised floating-point number with an 8-bit two's-complement mantissa (binary point after the first bit) and a 4-bit two's-complement exponent.

Write in binary
$5.5_{10} = 101.1_2$ (that is $4 + 1 + 0.5$ ).
Normalise
Move the binary point to just after the leading 0 sign bit: $0.10110000 \times 2^{3}$ (the point moved 3 places right of its normalised position, so the exponent is 3).
Write the fields
Mantissa (sign 0, then $.1011000$ ) = $01011000$ ; exponent $3 = 0011$ in 4-bit two's complement.

Result: 5.5 is stored as mantissa $01011000$ , exponent $0011$ . Check: mantissa $= 0.6875$ , and $0.6875 \times 2^{3} = 0.6875 \times 8 = 5.5$ .

Typical mistakes

Failing to adjust the exponent when shifting the mantissa during normalisation - the value $\text{mantissa} \times 2^{\text{exponent}}$ must stay unchanged.
Assuming floating point stores values exactly and testing floats for exact equality, when rounding error means they may differ by a tiny amount.

Active revision

Normalise the denary number 5.5 into an 8-bit two's-complement mantissa (binary point after the first bit) and a 4-bit two's-complement exponent, and verify your representation converts back to 5.5.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Character sets and bitwise operations#

StandardAQA 7517 4.5.5AQA 7517 4.5.6DfE GCE Computer Science - character sets

Text is stored by assigning each character a number - a character code - defined by a character set. ASCII uses 7 bits to encode 128 characters: the upper- and lower-case letters, digits, punctuation and control codes. Two features are exploited constantly: the codes for the letters are contiguous (so 'A' = 65, 'B' = 66, ...; 'a' = 97, ...), which is why letters can be sorted and shifted arithmetically, and the digit characters are contiguous from '0' = 48, so the numeric value of a digit character is its code minus 48.

ASCII's 128 characters cannot represent the world's scripts, so Unicode was created to give every character in every language a unique code point, with encodings such as UTF-8 and UTF-16 using one to four bytes per character. The first 128 Unicode code points are identical to ASCII, so ASCII text is valid UTF-8. The cost of universality is size: a Unicode character generally needs more than one byte, so a document in Unicode can be larger than the same text in ASCII - a genuine storage trade-off.

Bitwise operations act on the individual bits of a value rather than on its numeric meaning, using the logic operations AND, OR, XOR and NOT applied bit-by-bit. Their most important use is masking: ANDing a value with a mask of 1s and 0s isolates chosen bits. For instance

\text{value AND } 00001111

keeps only the low four bits (setting the rest to 0), the standard way to extract a nibble; ORing with a mask sets chosen bits, and XORing flips them. Masks are how flags packed into a single byte are read and written.

Shifts move every bit left or right. A logical shift left by one moves each bit up a place and brings in a 0, which for an unsigned value multiplies by 2; a logical shift right divides by 2 (discarding the remainder). Shifting is far faster than multiplication and is used for exactly that reason. These bit-level operations, together with character-code arithmetic, are the machinery behind low-level tasks such as the Caesar cipher, colour manipulation and packing several small values into one word.

\text{value of digit character} = \text{ASCII code} - 48

Digit character to value

Because '0' = 48, '1' = 49, ..., subtracting 48 from a digit's code gives its numeric value.

Worked example

Masking to extract the low nibble

Compute $10110101 \text{ AND } 00001111$ , and separately shift $00010110$ left by one place. Interpret both results.

Apply the AND mask
AND gives 1 only where both bits are 1. The high nibble is masked to 0 (AND 0000) and the low nibble is preserved (AND 1111): $10110101 \text{ AND } 00001111 = 00000101$ .
Interpret the mask
The mask has extracted the low four bits, $0101 = 5$ , discarding the high nibble - the standard way to read a nibble out of a byte.
Shift left
$00010110$ shifted left by one is $00101100$ : $22$ becomes $44$ .

Result: The mask yields $00000101$ (the low nibble, 5); the left shift doubles the value from 22 to 44. Masks select bits; shifts multiply or divide by powers of two.

Typical mistakes

Assuming Unicode always uses a fixed number of bytes per character (UTF-8 is variable length, 1-4 bytes), or that it is unrelated to ASCII.
Confusing a logical shift with an arithmetic shift on a signed value - a logical right shift does not preserve the sign bit.

Active revision

Given ASCII 'A' = 65, state the code for 'F' and for 'a'. Then compute $10110101 \text{ AND } 00001111$ and state what the mask has done, and give the result of shifting $00010110$ left by one place and its denary meaning.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education)

Representing images and sound#

StandardAQA 7517 4.5.7AQA 7517 4.5.8DfE GCE Computer Science - media representation

Sampling an analogue sound wave

Fig. 4The continuous wave (curve) is measured at regular instants (the marked sample points, with drop lines to the axis). Each sample's amplitude is stored as a binary number. A higher sampling rate takes more points and reconstructs the wave more faithfully; the Nyquist theorem requires at least two samples per cycle of the highest frequency.

A bitmap image is a grid of pixels, each storing a colour as a binary number. Two properties fix its quality and size: the resolution (the number of pixels, e.g. width x height) and the colour depth (the number of bits per pixel, which sets how many colours are available -

d

bits give

2^{d}

colours). The uncompressed file size in bits is therefore width x height x colour depth, plus a small amount of metadata (dimensions, colour depth, date) needed to interpret the pixels. Doubling the colour depth or the resolution multiplies the storage accordingly - the central calculation of this section.

A vector image, by contrast, stores a set of drawing objects - lines, curves, shapes with their coordinates, colours and styles - rather than a grid of pixels. Vectors scale to any size without loss of quality and are compact for geometric artwork such as logos and diagrams, but they are unsuited to photographs, where bitmaps excel. Choosing bitmap versus vector for a given image is an evaluative exam point.

Sound is a continuous (analogue) wave that must be sampled to be stored digitally: its amplitude is measured at regular instants and each measurement stored as a binary number (shown opposite). The sampling rate is how many samples are taken per second (in hertz) and the sampling resolution (bit depth) is how many bits store each sample. A higher rate and resolution reproduce the sound more faithfully but produce a larger file - file size in bits is sampling rate x resolution x duration x channels. The Nyquist theorem states that to capture a frequency faithfully the sampling rate must be at least twice that frequency, which is why CD audio samples at 44.1 kHz to cover the ~20 kHz limit of human hearing.

The file-size formulas make the trade-offs concrete and are frequently examined. For an image, size scales with both resolution and colour depth; for sound, with rate, resolution, duration and the number of channels (stereo doubles mono). These uncompressed sizes are large - a few minutes of CD audio is tens of megabytes - which is exactly the motivation for the compression techniques in the next section. Always be explicit about whether an answer is in bits, bytes, kilobytes or kibibytes.

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

Bitmap file size

Colour depth $d$ gives $2^d$ possible colours per pixel; divide the bit total by 8 for bytes.

\text{sound size (bits)} = \text{sampling rate} \times \text{resolution} \times \text{seconds} \times \text{channels}

Sound file size

Higher rate or resolution improves fidelity but increases size proportionally; stereo (2 channels) doubles mono.

Worked example

Bitmap file-size calculation

An uncompressed bitmap is 64 pixels wide, 48 pixels high, with a colour depth of 4 bits per pixel. Find its size in bits, bytes and kibibytes.

Total bits
$64 \times 48 \times 4 = 3072 \times 4 = 12\,288$ bits.
Bytes
Divide by 8: $12\,288 \div 8 = 1536$ bytes.
Kibibytes
Divide by 1024: $1536 \div 1024 = 1.5$ KiB.

Result: The image is 12 288 bits = 1536 bytes = 1.5 KiB. A colour depth of 4 bits allows $2^4 = 16$ colours per pixel.

Typical mistakes

Forgetting to divide bits by 8 to get bytes, or mixing decimal (1000) and binary (1024) prefixes in the same answer.
Confusing sampling rate (samples per second) with sampling resolution (bits per sample) - both affect fidelity and size but differently.

Active revision

A bitmap is 64 pixels wide, 48 high, with a colour depth of 4 bits. Calculate its size in bits, bytes and kibibytes. Then find the size in megabytes of a 30-second mono sound sampled at 44 100 Hz with 16-bit resolution.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Data compression and encryption#

AdvancedAQA 7517 4.5.9AQA 7517 4.5.10DfE GCE Computer Science - compression and encryption

A Huffman coding tree

Fig. 5Built by repeatedly combining the two lowest-frequency nodes (C+D, then B+CD, then A+BCD). Labelling left edges 0 and right edges 1 gives the prefix-free codes A = 0, B = 10, C = 110, D = 111 - the frequent A gets the shortest code, so the encoded stream is shorter than fixed-length coding.

Data compression reduces the number of bits needed to store or transmit data, saving storage and bandwidth. Lossless compression reconstructs the original exactly and is essential for text and program files; lossy compression discards information judged imperceptible (as in JPEG or MP3) to achieve much smaller files where perfect fidelity is not required. The A-Level focuses on two lossless methods. Run-length encoding (RLE) replaces runs of repeated values by a single value and a count - 'AAAAAA' becomes '6A' - which is excellent for data with long runs (simple graphics) but can enlarge data with no repetition.

Dictionary-based compression and Huffman coding exploit frequency. Huffman coding builds a variable-length binary code in which the most frequent symbols get the shortest codes, using a binary tree built by repeatedly combining the two lowest-frequency items. The tree opposite encodes symbols with frequencies A:5, B:2, C:1, D:1, giving the prefix-free codes A = 0, B = 10, C = 110, D = 111. Because it is prefix-free (no code is the start of another) the stream decodes unambiguously, and weighting the common symbols with short codes makes the total shorter than fixed-length encoding.

Encryption protects data so that only authorised parties can read it, transforming plaintext into ciphertext with a key. The Caesar cipher shifts each letter a fixed number of places along the alphabet; it is trivially broken by trying all 25 shifts or by frequency analysis, so it is only illustrative. The Vernam cipher (one-time pad) XORs the plaintext with a truly random key as long as the message, used only once - it is provably unbreakable if the key is random, secret, never reused and the same length as the message. These conditions are exactly why the otherwise-perfect one-time pad is impractical for everyday use.

Practical systems use two families of key-based encryption. In symmetric encryption the same secret key encrypts and decrypts, which is fast but requires the key to be shared securely in advance - the key-distribution problem. In asymmetric (public-key) encryption each party has a mathematically linked public key (freely shared, used to encrypt) and private key (kept secret, used to decrypt), so a message encrypted with someone's public key can be read only with their private key - solving key distribution and underpinning HTTPS and digital signatures. The trade-off is speed: asymmetric encryption is slower, so in practice it is used to exchange a symmetric session key which then does the bulk encryption.

c_i = (p_i + k) \bmod 26

Caesar cipher

Each plaintext letter's position $p_i$ is shifted by the key $k$ and wrapped round the 26-letter alphabet.

Worked example

Huffman codes from a tree

Using the Huffman tree with A:5, B:2, C:1, D:1 (left edge = 0, right edge = 1), give the code for each symbol and encode the string 'BAD'.

Read the codes off the paths
A is the left child of the root: 0. B is right-then-left: 10. C is right-right-left: 110. D is right-right-right: 111.
Encode BAD
B = 10, A = 0, D = 111, so 'BAD' = 10 0 111 = 100111.
Why it decodes cleanly
No code is a prefix of another (prefix-free), so reading 100111 left to right: 10 (B), 0 (A), 111 (D) is the only possible split.

Result: Codes A = 0, B = 10, C = 110, D = 111; 'BAD' encodes to 100111 (6 bits, versus 6 bits for 2-bit fixed codes here, with the saving growing as the frequent A recurs).

Typical mistakes

Assuming compression always shrinks data - RLE enlarges data with no runs, and no lossless method can compress every possible input.
Muddling the keys in asymmetric encryption: the recipient's public key encrypts and only their matching private key decrypts.

Active revision

Build a Huffman tree for the symbols with frequencies E:8, A:5, T:3, N:2 (combining the two lowest each time), give each symbol's code, and state why the codes can be decoded without ambiguity.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

References & sources

Sources

Department for Education

GCE AS and A level subject content for computer science

AQA

AQA A-level Computer Science 7517 specification

Fundamentals of data representation

6 sections~22 min reading time3 competenciesLevel Foundation 1 · Standard 3 · Advanced 2

Fundamentals of data representation

Key points

Converting 203 to binary and hex

Key points

Subtraction by adding the two's complement

Key points

Normalising 5.5 into floating point

Key points

Masking to extract the low nibble

Key points

Bitmap file-size calculation

Key points

Huffman codes from a tree

Sources

Fundamentals of data representation

Key points

Converting 203 to binary and hex

Key points

Subtraction by adding the two's complement

Key points

Normalising 5.5 into floating point

Key points

Masking to extract the low nibble

Key points

Bitmap file-size calculation

Key points

Huffman codes from a tree

Sources