Compression

— Computer Science · AS Level (9618) · Ch 1: Information Representation, Part 3 —

★ Exam Tip: Chapter 1 = Data Representation → Multimedia → Compression. Everything up to lossless / lossy is O-level content; RLE onwards is AS content. Definitions are worth 1 mark (sometimes 2) — and every extra point you write can pick up a mark.

1. What is Compression?

Compression = "Reduction of file size"

Why do we need to compress a file?

The data files are very large.
It would take a long time to send the non-compressed file // compressed files will download faster.
A higher bandwidth would be needed to transmit the uncompressed file.

Remember: // in a mark scheme = "this point OR the next one". Learn whichever is easier — one is enough.

Compressing ⇒ smaller file ⇒ higher rate of transfer (upload/download) when quality of data isn't the main need — you only want the data to reach the other person quickly.

same data — the smaller file reaches the receiver sooner

bandwidth = rate of data transfer

Sir's way to remember it: link it to the internet — "high bandwidth" = fast connection (e.g. 40 MB per second). But the real meaning is wider: wherever you talk about a rate of data transfer you can use the word bandwidth.

Network bandwidth — rate of data transfer of the internet connection
Application bandwidth — rate at which an app is transferring data
Wire / PC bandwidth — rate of data through a wire (e.g. 45 MB/s or 50 GB/s); a movie download has its own rate too

Student doubt: "Is it always per second?" — No. Bandwidth = rate of data transfer, i.e. per unit time; that unit of time can be anything. Don't write "per second" in the definition.

2. Types of Compression

Lossless file compressionIn this technique the data is not lost, and the compressed file can be decompressed as the original.

Lossy file compressionIn this technique the data is lost and the decompressed file is not the same as the original.

Trick (sir): lossLESS → less loss → data is not lost. Lossy → think of cropping a picture.

Why cropping = lossy: cut off part of an image ⇒ file size drops, but the cut-off data is gone for good. You can't convert the remaining image back to the original form.

lossless: round trip gives the original back

lossy: removed data cannot be rebuilt

	Lossless	Lossy
Data	not lost	lost
After decompressing	same as original	not the same
File size reduction	smaller, but less reduction	much smaller
Examples (this chapter)	RLE	crop, JPEG, MP3, fewer colours / lower resolution

Marks: the definition usually carries 1 mark — "data is not lost" and "can be decompressed as the original" — and a 2-mark version may ask for both points. Learn the wording exactly as boxed above.

3. Application of Lossy and Lossless

Lossy: accuracy of data is not important; a smaller file size is needed ⇒ lossy reduces file size more than lossless.
Lossless: accuracy of data is important.

Why learn this? Scenario-based questions — you must decide where to use lossy and where lossless. Examples: a plain text file or an image whose small quality drop won't matter → lossy; data where every bit counts → lossless.

how to judge a scenario question — questions are never the same, so you decide

4. Scenario Based Questions

Scenario 1identify technique

Q: Abdullah wants to compress the source code. Identify the most appropriate compression technique he should use.

Judge first: is every bit of data important? For code, yes — remove even one letter (e.g. the P in print) and it breaks.

Lossless
In this technique data is not lost
Any lost data will mean that the program will not work

Answer: Lossless

Scenario 2identify technique

Q: A photograph is to be emailed to a friend. (Scenario is unclear — so either answer can score if explained.)

Lossy

All the data is not required
The number of colours can be reduced without the user noticing
Email requires a significantly smaller file size
Takes a shorter time to transmit

Lossless (the "OR" answer)

A high quality image may be needed (e.g. sending it for a contest)
All of the data is needed and cannot afford to lose any data — accuracy, resolution, colours

Answer: Lossy OR Lossless — with reasons

Sir's exam advice: when the scenario is unclear, pick the side you have more points for in your head (2–3 lossy points vs 1–2 lossless) — but you must explain your choice. Also write the definition and an example — examples carry marks too. More relevant content = safer side if the marking changes. Just keep it related to the scenario.

Is lossy ever intentional? Yes — by choice, not compulsion. Image has the password "Taha"; you only need the viewer to read it. Quality and colours don't matter ⇒ degrade the quality, shrink the file ⇒ lossy, because you wanted a smaller file.

Note: the examiner likes to confuse you — the question never says "source code is very important". You must spot that. "Source code" ⇒ click: every character matters.

5. How can a Bitmap Image be Compressed? — RLE

RLE = Run Length Encoding — a lossless compression method

Idea: in an image, the same colour repeats in long runs of consecutive pixels. Instead of storing every pixel, store the colour code once + how many times it repeats.

Order to write: first the colour code, then the count. e.g. white = 3B, 9 times ⇒ 3B9.

Q6 (board)bitmap · RLE

A black and white bitmap image (7 × 7 pixels) is shown. Colour codes: Black = 1A, White = 3B. Show how the image is compressed using RLE.

runs continue from one row into the next (first and last runs outlined)

Read the pixels left → right, row by row. Runs continue from the end of one row into the start of the next: e.g. 7 whites (top row) + 2 whites = 9 whites; row 2's last 2 whites + row 3's first white = 3 whites.

#	Run of	Code
1	9 white	3B9
2	3 black	1A3
3	3 white	3B3
4	2 black	1A2
5	1 white	3B1
6	2 black	1A2
7	2 white	3B2
8	1 black	1A1
9	3 white	3B3

#	Run of	Code
10	1 black	1A1
11	2 white	3B2
12	2 black	1A2
13	1 white	3B1
14	2 black	1A2
15	3 white	3B3
16	3 black	1A3
17	9 white	3B9
check: 9+3+3+2+1+2+2+1+3+1+2+2+1+2+3+3+9 = 49 pixels ✓

Compressed image (answer)3B9 1A3 3B3 1A2 3B1 1A2
3B2 1A1 3B3 1A1 3B2 1A2
3B1 1A2 3B3 1A3 3B9

Explanation (write this in the exam):

Looks for runs of consecutive pixels of the same colour
Stores the colour value once and the number of times it occurs
It is a lossless method of compression
Reference to the given image — e.g. "3B9: white repeated 9 times" (depends on the question)

Why lossless? Decompress the codes: 3B9 = white, white, white … 9 times ⇒ the original image is re-created exactly. No data is lost. (If we simply removed pixels instead, that would be lossy.)

Question variants: usually the exam doesn't say "compress it" — it asks "How will this image be compressed using RLE?" ⇒ explain the 3 points, then give the example codes from the image (that's the 4th point).
If colours are R, G, B (or any names) with no codes given, just write them: "R is repeated 9 times". Same method — colour, then count.

Not now: if a pattern repeats, you can give the whole pattern a flag and repeat the flag — that's a separate concept, not needed at this level.

6. Other Ways to Compress a Bitmap (Lossy)

JPEG — a file format for storing images (like .png, .jpg: formats for storing data). It is lossy and can cut a file by about 90%. What it does: removes the parts of the image that are not noticeable to the human eye.

The science: eyes see grey shades very well but colour detail less ⇒ grey stays exact, colour information is reduced. (The detail is huge — you only need the line above.)

Common mistake: JPEG (and later MP3) is a technology / format, not a method. "Describe lossy methods that can be used to compress an image" — writing "JPEG" gets no marks; most students lost marks exactly this way.

Describe lossy methods to compress an image

Reduce the bit depth — fewer bits per pixel, so each pixel needs less binary ⇒ file size drops.
Reduce the number of colours — near shades (e.g. shades of red) look almost the same, so use one shade. Fewer colours ⇒ fewer bits per colour ⇒ smaller file.
Reduce the image resolution — fewer pixels per unit measurement (per inch) ⇒ less binary to store.

bit depth ↓

number of colours ↓

resolution ↓

Recall (multimedia chapter): bit depth = number of bits allocated to one colour of a pixel; more bits ⇒ more shades possible ⇒ larger file.

Matching questions (learn this table)

Method	Type	What it does
Crop	lossy	removes pixels (pixel values = binary = data) — can't be decompressed back
RLE	lossless	stores colour code + count of repeats
JPEG	lossy	removes parts of the image the eye can't notice
Fewer colours	lossy	fewer bits needed per colour (bit depth)

Note: different formats work differently — JPEG uses its own technique; RAW = full high-quality image; JPEG is also high quality but drops the details you can't see.

7. How can a Vector Image be Compressed?

All of the above is for bitmap images (they have pixels). A vector image has no pixels ⇒ you can't reduce bit depth, number of colours or resolution. So what then? (not asked in a past paper yet, but know it — syllabus must be complete.)

Vector graphics are stored as .svg = Scalable Vector Graphics, which are defined in an XML text file (think of it like HTML — plain text). A text file can easily be compressed.

Vector image → by using .svg which are defined in XML / text files which allows them to be compressed

bitmap: a grid of pixel values

vector: described in a text file

8. How can Sound be Compressed? — MP3

Images used JPEG: remove what the eye can't notice. Sound does the same with MP3 — remove what the ear can't notice.

MP3 uses technology known as audio compression. A sound file can be compressed by using the perceptual music shaping algorithm — a lossy compression (the decompressed file will not be the same as the original).

What perceptual music shaping removes

Frequencies outside the human hearing range (20 Hz – 20 000 Hz) are removed.
If two sounds are played at the same time, only the louder one can be heard by the ear, so the softer sound is removed (the ear wouldn't notice it anyway).

Remove data ⇒ less storage ⇒ file size automatically reduced ⇒ compressed.

outside 20 Hz–20 000 Hz the ear can't hear ⇒ removed

two sounds at once: the softer one is dropped

Common mistake: MP3 is a technology / file format, not a method. Perceptual music shaping is the method. "Describe lossy methods…" ⇒ don't write MP3.

sir's own Qdescribe lossy methods · sound

Q: Describe lossy methods that can be used to compress a sound. (Not in a past paper yet — these points are sir's, not from a mark scheme. Same logic as the image question.)

Reduce the sampling resolution — reduces the number of bits per sample ⇒ each sample has fewer bits ⇒ smaller file.
Reduce the sampling rate — reduces the number of samples per unit time ⇒ fewer bits to store.
Perceptual music shaping — removing parts of sounds which are not noticeable to the human ear.

Use the multimedia terms (sampling resolution, sampling rate) — NOT "MP3"

old paper (~2013–14)5 marks · explain

Q: When storing music tracks in a computer, the MP3 format is often used. This reduces file size by about 90%. Explain how the music quality is apparently retained.

MP3 is a lossy compressed format
It uses perceptual music shaping
It removes sounds that human ears can't hear
It only keeps sounds the human ear can hear better than others
It discards soft sounds — if two sounds are played together, only the louder is heard, so the softer is removed

Quality "appears" the same because only inaudible data was removed

Note: for sound there is no lossless method in this syllabus — only the points above. If a question asks for a lossless method for images, write RLE (run length encoding).

9. How can a Text File be Compressed?

Use RLE again — the same concepts as images, but with characters instead of pixels: consecutive identical characters. Each character has an ASCII code: A = 97, B = 98, C = 99 (as sir used).

count of repeats + ASCII code of the character

string = AAAAAAAA BBBBBBBB CCCCCC A: repeated 8 times, ASCII 97 ⇒ 08 97 B: repeated 8 times, ASCII 98 ⇒ 08 98 C: repeated 6 times, ASCII 99 ⇒ 06 99 compressed text = 08 97 08 98 06 99

Note: in the bitmap example sir wrote code → count (3B9); for text he wrote count → code (08 97). Follow the order the question / mark scheme gives and make clear which number is the count and which is the ASCII code.

★ Exam Tip: if asked to explain RLE for text, write the same RLE points as for images (runs of consecutive identical items; store the value once + the number of times it occurs; lossless) — just say characters / text instead of pixels.

10. Syllabus Notes and How to Revise

Video compression was removed from the syllabus — when doing topical past papers, skip the video questions and anything you haven't studied.
Topical past papers mix Data Representation + Multimedia + Compression (around 30–40 questions) — attempt all others.

Sir's memorising method: every concept has been explained, but memorising is still your job. Write it out looking → cover it and write it without looking → wrong? learn again, repeat. Only then attempt past papers and self-check with the mark scheme.

Quick Recap — Full Chapter Cheat-Sheet

✓ Quick Recap — Compression

Compression = reduction of file size. Why: files are large ⇒ long to send / faster to download ⇒ higher bandwidth needed for uncompressed.
Bandwidth = rate of data transfer (network / application / wire — no need to say "per second").
Lossless: data not lost, decompresses as the original (accuracy important · source code · high-quality image). Lossy: data lost, decompressed ≠ original (accuracy unimportant · much smaller file · cropping).
Scenario Q: decide accuracy vs file size → state technique → explain with 2–3 points + definition + example. Unclear? pick either and justify.
Bitmap RLE (lossless): runs of consecutive same-colour pixels → colour code + count (white 3B ×9 = 3B9). Explanation = 3 points + reference to the image.
Bitmap lossy methods: reduce bit depth, reduce number of colours, reduce resolution (also crop; JPEG is a format, not a method).
Vector: .svg stored as XML text ⇒ text compresses easily.
Sound (MP3 = technology): perceptual music shaping removes sounds outside 20 Hz–20 000 Hz and softer of two simultaneous sounds; also reduce sampling resolution / sampling rate. Lossy only.
Text: RLE with ASCII — e.g. 8 A, 8 B, 6 C ⇒ 08 97, 08 98, 06 99.