1. Data representation and logic gates

A computer is built from millions of tiny switches (transistors). Each switch has only two states: on or off, so it can store one binary digit (bit): 1 or 0.

• All data — numbers, characters, sound samples, pixel colours and program instructions — must be converted to binary before the computer can store or process it.
• The binary data is then processed using logic gates: circuits that take one or two binary inputs and give one binary output.
• Two states are easy to tell apart reliably, even with electrical noise, which is why binary (not denary) is used inside the hardware.

You must recognise and draw the standard symbol for each gate and know its truth table. Gates in this section have at most two inputs.

Symbol shapes: NOT is a triangle with a small circle (the bubble) at its point; AND has a flat back and a round front (D-shape); OR has a curved back and a pointed front; XOR is an OR with an extra curved line behind the back. NAND and NOR are AND and OR with a bubble on the output.

The same truth tables in Python, where &, |, ^ work on single bits:

for a in (0, 1):
    for b in (0, 1):
        print(a, b, 'AND', a & b, 'OR', a | b, 'XOR', a ^ b,
              'NAND', 1 - (a & b), 'NOR', 1 - (a | b))

Converting: going to a smaller unit, multiply; going to a bigger unit, divide. Bits ↔ bytes uses 8; every step from bytes up uses 1024.

• 3 GiB in MiB: 3 × 1024 = 3072 MiB
• 4 KiB in bits: 4 × 1024 = 4096 bytes; 4096 × 8 = 32 768 bits
• 2 097 152 bytes in MiB: 2 097 152 ÷ 1024 = 2048 KiB; 2048 ÷ 1024 = 2 MiB
• 6 nibbles = 24 bits = 3 bytes

The base is how many different digits a number system uses.

• Denary — base 10, digits 0–9.
• Binary — base 2, digits 0 and 1. Place values (right to left): 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048.
• Hexadecimal — base 16, digits 0–9 then A=10, B=11, C=12, D=13, E=14, F=15. One hex digit = exactly one nibble (4 bits).

In the exam binary numbers are at most 12 bits long and conversions use positive integers only.

Denary → binary (156): write the place values and take away the largest that fits.

156 − 128 = 28, 28 − 16 = 12, 12 − 8 = 4, 4 − 4 = 0 → 10011100.

Binary → hex: split into nibbles from the right: 1001 1100 → 9 and 12 → 9C.

Hex → binary (B7): B = 1011, 7 = 0111 → 10110111.

Hex → denary (B7): 11 × 16 + 7 = 183.

Denary → hex (183): 183 ÷ 16 = 11 remainder 7 → B and 7 → B7.

12-bit example: 2748 = 1010 1011 1100 → hex ABC (10 × 256 + 11 × 16 + 12 = 2748).

Check any answer in Python:

print(bin(156), hex(156), int('10110111', 2), int('B7', 16))
# 0b10011100 0x9c 183 183

Hexadecimal is a human-friendly way of writing binary — the computer still stores binary.

• It is shorter: 12 binary digits become 3 hex digits, so it is easier to read and remember.
• There are fewer mistakes when people read, copy or type it.
• It converts to and from binary easily — each hex digit is one nibble.

Where it is used: colour codes in HTML/CSS (#FF0000 is red), MAC addresses (00:1A:2B:3C:4D:5E), IPv6 addresses, memory addresses and error codes, and showing memory contents in a debugger.

Add column by column from the right, carrying like denary:

Example: 01101101 (109) + 01011011 (91)

  carry  1 1 1 1 1 1 1
         0 1 1 0 1 1 0 1   (109)
       + 0 1 0 1 1 0 1 1   (91)
       = 1 1 0 0 1 0 0 0   (200)

Check: 109 + 91 = 200 and 11001000 = 128 + 64 + 8 = 200.

An 8-bit register can hold 0 to 255. If the result of an addition is bigger than 255, a ninth bit is needed — this is an overflow error.

Example: 11001000 (200) + 01100100 (100) = 300 = 1 00101100. The register keeps only 8 bits, 00101100 = 44, so the stored answer is wrong.

• Overflow happens because the result needs more bits than the register has.
• The extra carry bit is lost, so the stored value is incorrect; a program using it may crash or give wrong output.
• The CPU sets an overflow flag so the error can be detected.

A logical shift moves every bit left or right by a number of places. Bits shifted off the end are lost and the empty places are filled with 0.

• Left 2: 00010110 (22) → 01011000 (88) — each left place multiplies by 2, so 2 places = × 4.
• Right 3: 10110000 (176) → 00010110 (22) — each right place divides by 2 (whole-number), so 3 places = ÷ 8.

Effect when bits are lost: 01100101 (101) shifted left 3 → 00101000 (40), not 808 — the 1s pushed off the left end are lost, so the result is wrong. A right shift that loses 1s off the right end loses precision (e.g. 00000111 = 7 right 1 → 00000011 = 3, not 3.5).

x = 0b00010110
print(format((x << 2) & 0xFF, '08b'))   # 01011000
print(format(0b10110000 >> 3, '08b'))   # 00010110

In a cyclic shift nothing is lost: the bits pushed off one end come back in at the other end.

• Cyclic left 3 of 10110010: the first three bits 101 move to the end → 10010101.
• Cyclic right 2 of 10110010: the last two bits 10 move to the front → 10101100.

Effect: the same bits are kept in a new order, so a cyclic shift is not a multiply or divide; shifting 8 places brings back the original number. It is used where no data may be lost, e.g. in encryption and checksum calculations.

def rotl(x: int, n: int) -> int:
    n %= 8
    return ((x << n) | (x >> (8 - n))) & 0xFF

print(format(rotl(0b10110010, 3), '08b'))  # 10010101

Two's complement stores negative integers. The leftmost bit has a negative place value: −128.

The range is −128 to +127. A number starting with 1 is negative; starting with 0 is positive (and is written exactly like ordinary binary).

Denary → two's complement (−45):

1. Write +45 in 8-bit binary: 00101101
2. Invert every bit: 11010010
3. Add 1: 11010011

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

Two's complement → denary (11101100): −128 + 64 + 32 + 8 + 4 = −20.

Shortcut for negatives: from the right, keep every bit up to and including the first 1, then invert the rest (00101101 → 11010011).

print(format(-45 & 0xFF, '08b'))      # 11010011
v = 0b11101100
print(v - 256 if v >= 128 else v)   # -20

A character set is a list of characters, each with its own numeric code. To store text, the computer stores the code of each character, in binary.

• Each key press is converted to the character's code, e.g. 'A' = 65 = 01000001.
• The codes are sequential: 'B' = 66, 'C' = 67, so text can be sorted by comparing codes.
• When the text is displayed, the computer looks the code up in the same character set to show the right symbol. Both computers must use the same character set.

print(ord('A'), format(ord('A'), '08b'), chr(66))   # 65 01000001 B

Unicode's first 128 codes are the same as ASCII, so ASCII text is still valid Unicode.

Sound is an analogue wave. To store it, the computer samples the wave: it measures the amplitude (height) of the wave at regular time intervals and stores each measurement as a binary number.

• Sample rate — how many samples are taken per second (measured in hertz, e.g. 44 100 Hz).
• Sample resolution — the number of bits used to store each sample (e.g. 16 bits). More bits = more possible amplitude values.

The stored samples are only an approximation of the wave; the gaps between samples and the rounding of each sample lose a little detail.

The trade-off is always quality versus file size (and so storage space and transmission time).

A bitmap image is a grid of pixels (picture elements). Each pixel is one colour, and that colour is stored as a binary code.

• Resolution — the number of pixels in the image, given as width × height (e.g. 1920 × 1080).
• Colour depth — the number of bits used for each pixel's colour. 1 bit gives 2 colours (black/white), 8 bits give 256 colours, 24 bits give over 16 million colours.

The file stores the colour code of every pixel in order, row by row, plus some extra data about the image (its width, height and colour depth).

Purpose: reduce the file size.

Impact on storage: smaller files use less storage space on a device or server, so more files fit and storage costs less.

Impact on transmission: smaller files upload and download faster, use less bandwidth and less mobile data, and stream with less buffering. Email attachments may only be sent if under a size limit.

Compressing and decompressing takes some processing time, and lossy compression lowers quality.

Lossy compression permanently removes data, so the original file cannot be rebuilt exactly. It removes the data people are least likely to notice.

• Images (e.g. JPEG): reduce the colour depth or resolution, and merge pixels of very similar colours into one colour.
• Sound (e.g. MP3): perceptual coding removes sounds the human ear cannot hear (very high or low frequencies) and quieter sounds played at the same time as louder ones; the sample rate or resolution can also be reduced.
• Video (e.g. MP4): compresses each frame like an image and stores only the changes between frames instead of every full frame; frame rate or resolution can be reduced.

RLE replaces a run of the same repeated value with one copy of the value and a count of how many times it repeats. It works well on data with long runs (simple images, icons) and can make data with few repeats larger.

Text: AAAABBBCCD (10 characters) → 4A 3B 2C 1D (8 symbols).

Image: a row of pixels White ×5, Black ×3, White ×2 (WWWWWBBBWW) → 5W 3B 2W.

Decompressing repeats each value by its count, giving back exactly the original.

from itertools import groupby

def rle(text: str) -> str:
    return ''.join(f'{len(list(g))}{ch}' for ch, g in groupby(text))

print(rle('AAAABBBCCD'))   # 4A3B2C1D

Huffman coding gives each character a variable-length binary code: the most frequent characters get the shortest codes, rare ones get longer codes. No code is the start of another code, so the bit stream can be decoded without gaps. (You will be given the codes — you do not need to build or read a Huffman tree.)

Example — the word BANANA: A appears 3 times, N twice, B once. Given codes:

Encoded: B A N A N A → 11 0 10 0 10 0 → 110100100 = 9 bits. In 8-bit ASCII it would need 6 × 8 = 48 bits.

Decoding 110100100: read bits until they match a code — 11 = B, 0 = A, 10 = N, 0 = A, 10 = N, 0 = A → BANANA. Nothing is lost.

In a scenario, ask: must the file be exactly the same afterwards? If yes (text, code, data, evidence) → lossless. If small size matters more and a little quality loss won't be noticed → lossy.