Study Guide

Data compression

CIE A-Level Computer ScienceΒ· Unit 1: Information RepresentationΒ· 20 min read

1. Purpose of Data Compressionβ˜…β˜…β˜†β˜†β˜†β± 5 min

Data compression reduces the number of bits required to store or transmit digital data. It works by removing redundancy: repeated or unnecessary data that does not add meaningful value for the end user.

πŸ“˜ Definition

Data Compression

The process of encoding information using fewer bits than the original uncompressed representation, to reduce storage requirements and transmission time.

Example:

A 10MB uncompressed image can be compressed to 2MB for web use.

πŸ“ Worked Example

A 5-minute uncompressed audio file is 50MB and takes 10 seconds to download over a mobile connection. After compression, it is 8MB. How long does it take to download, assuming a constant bit rate?

  1. 1

    Calculate the original download speed:

  2. 2
    Speed=50 MB10 s=5 MB/s\text{Speed} = \frac{50 \text{ MB}}{10 \text{ s}} = 5 \text{ MB/s}
  3. 3

    Calculate the new download time for the compressed file:

  4. 4
    Time=8 MB5 MB/s=1.6 seconds\text{Time} = \frac{8 \text{ MB}}{5 \text{ MB/s}} = 1.6 \text{ seconds}
  5. 5

    Compression reduces download time by 84% in this example.

Exam tip:

You can often be asked to list three advantages of compression: smaller storage size, faster transmission, lower bandwidth costs.

2. Lossless vs Lossy Compressionβ˜…β˜…β˜†β˜†β˜†β± 7 min

All compression methods fall into one of two broad categories, distinguished by whether original data can be perfectly reconstructed after compression.

πŸ“˜ Definition

Lossless Compression

Compression that allows perfect reconstruction of the original uncompressed data, with no loss of information.

Example:

ZIP files for compressing documents use lossless compression.

πŸ“˜ Definition

Lossy Compression

Compression that permanently removes some data from the original file, achieving higher compression ratios but cannot reconstruct the original perfectly.

Example:

MP3 audio files remove inaudible frequencies to reduce size.

  • Lossless compression typically gives 2:1 to 4:1 compression (files are 25-50% of original size).

  • Lossy compression can give 10:1 to 100:1 compression (files are 1-10% of original size).

  • Lossless compression is required when any data loss would break the file: text documents, spreadsheets, executable programs.

  • Lossy compression is used for media where small losses are unnoticeable: images, audio, video.

πŸ“ Worked Example

For each file type, state whether lossy or lossless compression is appropriate: (a) A school essay, (b) A mobile photo for social media, (c) A spreadsheet of exam results, (d) A streaming podcast.

  1. 1

    (a) Essay: Any change to text changes the content, so lossless compression is appropriate.

  2. 2

    (b) Social media photo: Small quality reductions are acceptable for smaller files, so lossy compression is appropriate.

  3. 3

    (c) Exam results spreadsheet: Data accuracy is critical, so lossless compression is appropriate.

  4. 4

    (d) Streaming podcast: Small quality loss is unnoticeable and reduces bandwidth costs, so lossy compression is appropriate.

Exam tip:

Always justify your choice of compression type by linking it to the requirement for perfect reconstruction.

3. Common Lossless Compression Algorithmsβ˜…β˜…β˜…β˜†β˜†β± 8 min

CIE 9618 expects you to understand two widely used lossless compression algorithms: Run-Length Encoding (RLE) and Lempel-Ziv-Welch (LZW) compression.

πŸ“˜ Definition

Run-Length Encoding (RLE)

A simple lossless algorithm that replaces consecutive repeated occurrences of the same value with a single pair (count, value), instead of storing each repeat individually.

πŸ“ Worked Example

Compress the following sequence of 16 pixel values using RLE: 00 00 00 00 00 11 11 11 11 22 22 22 33 33 33 33. Write the output as (count, value) pairs and calculate the compression ratio.

  1. 1

    Group consecutive identical values: 5 Γ— 00, 4 Γ— 11, 3 Γ— 22, 4 Γ— 33

  2. 2

    Convert to (count, value) pairs:

  3. 3
    (5,00),(4,11),(3,22),(4,33)(5, 00), (4, 11), (3, 22), (4, 33)
  4. 4

    Original size: 16 Γ— 8 bits = 128 bits. Compressed size: 8 pairs Γ— 8 bits = 64 bits. Compression ratio = 2:1.

πŸ“˜ Definition

Lempel-Ziv-Welch (LZW)

A dictionary-based lossless algorithm that replaces repeated sequences of data with shorter index codes referencing entries in a dictionary built from the input data.

LZW is used in common file formats including GIF, TIFF, and PDF. It works by scanning input, adding new sequences to the dictionary, and replacing repeated sequences with their shorter index.

βœ“ Quick check

Test your understanding:

  1. Which lossless algorithm works best for an image with large areas of solid colour?

    • Run-Length Encoding

    • LZW

4. Common Lossy Compression Methodsβ˜…β˜…β˜…β˜†β˜†β± 8 min

Lossy compression methods are designed for specific media types, and exploit limitations in human perception to remove redundant data that most users will not notice.

πŸ“˜ Definition

JPEG Compression

The most common lossy compression for digital images, which divides the image into 8x8 blocks and removes high-frequency detail that the human eye cannot easily detect.

πŸ“˜ Definition

MP3 Compression

Lossy compression for digital audio that uses perceptual masking to remove sound frequencies that are inaudible to most human listeners.

πŸ“ Worked Example

A 24-bit colour bitmap image with dimensions 1920 Γ— 1080 pixels is uncompressed. Calculate the uncompressed file size in MB, then the compressed size after JPEG compression with a 25:1 ratio.

  1. 1

    Calculate the total number of pixels:

  2. 2
    1920Γ—1080=2,073,600 pixels1920 \times 1080 = 2{,}073{,}600 \text{ pixels}
  3. 3

    Calculate total number of bits:

  4. 4
    2,073,600Γ—24=49,766,400 bits2{,}073{,}600 \times 24 = 49{,}766{,}400 \text{ bits}
  5. 5

    Convert to megabytes:

  6. 6
    49,766,4008Γ—1024Γ—1024β‰ˆ5.93 MB (uncompressed)\frac{49{,}766{,}400}{8 \times 1024 \times 1024} \approx 5.93 \text{ MB (uncompressed)}
  7. 7

    Calculate compressed size for 25:1 compression ratio:

  8. 8
    5.9325β‰ˆ0.24 MB=240 KB\frac{5.93}{25} \approx 0.24 \text{ MB} = 240 \text{ KB}

Exam tip:

Always check unit conversions when calculating file sizes: this is the most common mark-losing error in these questions.

5. Common Pitfalls

Wrong move:

Confusing lossy and lossless compression when selecting an appropriate use case

Why:

Many students mix up the categories, especially for media files shared online

Correct move:

Always remember: if perfect reconstruction is required, use lossless. If quality tradeoff is acceptable, use lossy.

Wrong move:

Forgetting to convert between bits and bytes when calculating compressed file sizes

Why:

Compression ratios are unit-agnostic, but questions almost always request answers in bytes or megabytes

Correct move:

Always check the units of the original size and the requested final answer, and convert correctly before giving your final result.

Wrong move:

Claiming compression always results in a smaller file size than the original

Why:

Compression relies on redundancy; highly random data with no repeated patterns has no redundancy to remove

Correct move:

For random data, compression can result in a slightly larger file than the original, as the compression algorithm adds metadata to the output.

Wrong move:

Stating RLE can only be used for bitmap images

Why:

Students often associate RLE only with image compression, so they limit its use incorrectly in exam answers

Correct move:

RLE can be applied to any sequence of data with consecutive repeated values, including text, sound, and other data types.

6. Quick Reference Cheatsheet

Feature

Lossless Compression

Lossy Compression

Perfect reconstruction possible

Yes

No

Typical compression ratio

2:1 to 4:1

10:1 to 100:1

Common use cases

Text, spreadsheets, executables

Images, audio, video

Common algorithms

RLE, LZW, ZIP

JPEG, MP3, H.264

Maximum file size reduction

Moderate

Very large

When this came up on past exams

AI-estimated based on syllabus patterns β€” cross-check with official past papers for accuracy. Use only as revision-focus signals.

  • 2022 Β· 11

    Compare lossy vs lossless compression

  • 2023 Β· 12

    Calculate RLE compressed file size

  • 2024 Β· 13

    State advantages of data compression

Going deeper

What's Next

Understanding data compression is foundational for working with digital media and data transmission, core topics for both Paper 1 and practical assessment in CIE 9618. You will build on this knowledge to learn about specific media file formats, how compression impacts bandwidth requirements for network transmission, and advanced encoding techniques used in modern digital systems. Mastering the distinction between lossy and lossless compression and file size calculations will help you earn easy marks in both multiple-choice and extended response questions.