1.3 Data Storage and Compression - IGCSE Computer Science

Learning Objectives

By the end of this lesson, you will be able to:

Understand howdata storage is measured(bit, nibble, byte, KiB, MiB, GiB, TiB, PiB, EiB)
Convert between different units of data storage
Calculate the file sizeof an image file and a sound file, using information given
Understand thepurpose of and need for data compression
Understand how files are compressed usinglossyandlosslesscompression methods
Understand and applyRun-Length Encoding (RLE)
UnderstandHuffman codingas a lossless compression technique
Compare common file formats such asMP3, MP4, JPEG, TIFF, BMP, MIDI

Key Terms

Bit (b)

A single binary digit — either 1 or 0. The smallest unit of data.

Nibble

4 bits — half a byte. One nibble = one hexadecimal digit.

Byte (B)

8 bits. The standard unit for storing a single character.

Kibibyte (KiB)

1,024 bytes (2¹⁰). Part of the IEC binary system.

Mebibyte (MiB)

1,024 KiB = 1,048,576 bytes (2²⁰).

Gibibyte (GiB)

1,024 MiB = 1,073,741,824 bytes (2³⁰).

Tebibyte (TiB)

1,024 GiB = 1,099,511,627,776 bytes (2⁴⁰).

Pebibyte (PiB)

1,024 TiB = 1,125,899,906,842,624 bytes (2⁵⁰).

Exbibyte (EiB)

1,024 PiB = 1,152,921,504,606,846,976 bytes (2⁶⁰).

Compression

Reducing the size of a file so it takes up less space on secondary storage.

Lossy Compression

Data is permanently lost to reduce file size. The original file cannot be reconstructed.

Lossless Compression

No data is lost. The file can be returned to its original state.

Run-Length Encoding (RLE)

A lossless compression method that stores a value and the number of times it repeats consecutively.

Huffman Coding

A lossless compression algorithm where frequently used characters get shorter binary codes.

Bit Rate

The number of bits per second used when creating an audio file (e.g. MP3). Usually 80–320 kbps.

Perceptual Music Shaping

Removes sounds the human ear cannot hear properly, e.g. softer sounds when two sounds play together.

Bandwidth

The maximum rate of transfer of data across a network, measured in bits per second.

MP3

MPEG-3 uses audio compression to reduce music files by about 90%. A lossy format.

MP4

MPEG-4 can store multimedia (music, video, photos, animation), not just sound.

JPEG

Joint Photographic Experts Group — a lossy format for storing photographs at reduced file size.

1. Units of Data Storage

Aunit of datais a term given to describe different amounts of binary digits stored on a digital device.

Unit	Symbol	Value
Bit	b	1 or 0
Nibble	—	4 bits
Byte	B	8 bits
Kibibyte	KiB	1,024 B (2¹⁰)
Mebibyte	MiB	1,024 KiB (2²⁰)
Gibibyte	GiB	1,024 MiB (2³⁰)
Tebibyte	TiB	1,024 GiB (2⁴⁰)
Pebibyte	PiB	1,024 TiB (2⁵⁰)
Exbibyte	EiB	1,024 PiB (2⁶⁰)

Megabyte vs Mebibyte

1 kibibyte (1 KiB)= 1024 bytes (1024 B) — binary prefixes (to the power of 2)
1 kilobyte (1 KB)= 1000 bytes (1000 B) — decimal prefixes (to the power of 10)

Converting Between Units

Movingupin size of unit =division
Movingdownin size of unit =multiplication
For units bigger than a byte, use multiples of1024 (2¹⁰).
For bits and bytes, use8(as there are 8 bits in a byte).

Conversion Examples

2000 kilobytes in mebibytes:

2000 ÷ 1024 = 1.95 MiB

2 terabytes in gigabytes:

2 × 1024 = 2048 GiB

24 bits in bytes:

24 ÷ 8 = 3 B

10 bytes in bits:

10 × 8 = 80 b

IEC (International Electrotechnical Commission)

The IEC system uses binary prefixes (KiB, MiB, GiB, etc.) and is more accurate for measuring internal memory.

1 kibibyte (1 KiB) = 2¹⁰ = 1,024 bytes
1 mebibyte (1 MiB) = 2²⁰ = 1,048,576 bytes
1 gibibyte (1 GiB) = 2³⁰ = 1,073,741,824 bytes
1 tebibyte (1 TiB) = 2⁴⁰ = 1,099,511,627,776 bytes
1 pebibyte (1 PiB) = 2⁵⁰ = 1,125,899,906,842,624 bytes
1 exbibyte (1 EiB) = 2⁶⁰ = 1,152,921,504,606,846,976 bytes

A 64 GiB RAM could store 64 × 2³⁰ bytes of data (68,719,476,736 bytes).

Activity 1: Unit Conversions

Convert the following. Show all working.

2048 KiB to MiB
5 GiB to MiB
3 TiB to GiB
48 bits to bytes
7 bytes to bits
1 PiB to TiB

Solution:

2048 ÷ 1024 =2 MiB
5 × 1024 =5120 MiB
3 × 1024 =3072 GiB
48 ÷ 8 =6 bytes
7 × 8 =56 bits
1 × 1024 =1024 TiB

Check Your Understanding: Units of Storage

1. How many bits are in a byte? [1 mark]

[1]8 bits = 1 byte

2. How many bytes are in 1 KiB? [1 mark]

[1]1,024 bytes (2¹⁰)

3. Convert 4096 MiB to GiB. [2 marks]

[1]4096 ÷ 1024
[1]= 4 GiB

4. What is the difference between 1 KB and 1 KiB? [2 marks]

[1]1 KB = 1,000 bytes (decimal/SI units)
[1]1 KiB = 1,024 bytes (binary/IEC units)

5. How many nibbles are in 3 bytes? [1 mark]

[1]6 nibbles (1 byte = 2 nibbles, so 3 × 2 = 6)

6. A computer has 16 GiB of RAM. How many bytes is this? [2 marks]

[1]16 × 2³⁰
[1]= 17,179,869,184 bytes

2. Calculating File Sizes

Bitmap Image File Size

Size = Resolution × Colour Depth

Size = Width × Height × Colour Depth

Resolution = width × height (total pixels)

Sound File Size

Size = Sample Rate × Duration × Sample Resolution

For stereo sound, multiply the result by 2.

Worked Examples

Image Example

Resolution:500 × 500 pixels

Colour Depth:24 bits (3 bytes)

500 × 500 × 24 = 6,000,000 bits

÷ 8 = 750,000 bytes

÷ 1024 = 732 KiB

Sound Example

Sample Rate:100 samples/second

Duration:60 seconds

Resolution:24 bits

100 × 60 × 24 = 144,000 bits

÷ 8 = 18,000 bytes

÷ 1024 = 18 KiB

CD Quality Audio Example

Music sampled 44,100 times per second, 16 bits per sample, stereo (2 channels)

44100 × 16 × 2 ÷ 8 = 176,400 bytes per second

For a 4-minute track: 4 × 60 × 176,400 = 42,336,000 bytes

÷ 1024 ÷ 1024 = 40.4 MiB

Why Estimate File Size?

It is important to estimate the file size of an image or sound file so it is possible to estimate how many images can be stored on a device, or to decide if it can be sent as an email attachment.

Activity 2: File Size Calculations

A black and white image is 512 pixels by 256 pixels. Calculate the file size in kilobytes (KB) (1 KB = 1024 bytes). [3]
A photograph has a bit depth of 8 bytes and image resolution of 1500 pixels wide and 3000 pixels high. Calculate the file size of the photograph in megabytes. [3]
A camera detector has an array of 2048 by 2048 pixels and uses a colour depth of 16. Find the size of an image taken by this camera in MiB. [3]
An audio CD has a sample rate of 44,100 and a sample resolution of 16 bits. The music uses two channels. Calculate the file size for a 60-minute recording in MiB. [4]

Solution:

512 × 256 = 131,072 pixels
Black and white = 1 bit per pixel
131,072 × 1 = 131,072 bits ÷ 8 = 16,384 bytes
16,384 ÷ 1024 =16 KB
1500 × 3000 = 4,500,000 pixels
× 8 = 36,000,000 bits
÷ 1,000 ÷ 1,000 =36 MB
2048 × 2048 = 4,194,304 pixels
× 16 = 67,108,864 bits ÷ 8 = 8,388,608 bytes
÷ 1024 ÷ 1024 =8 MiB
44100 × 16 × (60 × 60) × 2 = 5,080,320,000 bits
÷ 8 = 635,040,000 bytes
÷ 1024 ÷ 1024 ≈605 MiB

Check Your Understanding: File Sizes

1. What is the formula for calculating the file size of a bitmap image? [2 marks]

[1]File size = image resolution × colour depth
[1]Or: width × height × colour depth

2. A bitmap is 800 × 600 pixels with a colour depth of 24 bits. Calculate the file size in bytes. [2 marks]

[1]800 × 600 × 24 = 11,520,000 bits
[1]11,520,000 ÷ 8 = 1,440,000 bytes

3. A mono sound file is recorded at 22,050 Hz with a resolution of 8 bits for 10 seconds. Calculate the file size in bytes. [2 marks]

[1]22,050 × 8 × 10 = 1,764,000 bits
[1]1,764,000 ÷ 8 = 220,500 bytes

4. Why is it important to estimate the file size of an image? [2 marks]

[1]So it is possible to estimate how many images can be stored
[1]Or to decide if it can be sent as an email attachment

5. A camera has 1024 × 1536 pixels and uses 24-bit colour. How many photographs could be stored on a 16 GiB memory card? [4 marks]

[1]1024 × 1536 = 1,572,864 pixels
[1]× 24 = 37,748,736 bits ÷ 8 = 4,718,592 bytes per photo
[1]16 GiB = 17,179,869,184 bytes
[1]17,179,869,184 ÷ 4,718,592 ≈ 3,640 photos

6. A stereo sound file has a sample rate of 48,000 Hz, resolution of 16 bits, and is 30 seconds long. Calculate the file size in MiB. [3 marks]

[1]48,000 × 16 × 30 × 2 = 46,080,000 bits
[1]÷ 8 = 5,760,000 bytes
[1]÷ 1024 ÷ 1024 ≈ 5.49 MiB

3. The Need for Compression

Sound and image files can be very large. It is therefore necessary toreduce (or compress)the size of a file.

Why Compress Files?

Tosave storage spaceon devices such as the hard disk drive / solid state drive.
Toreduce the time taken to streama music or video file.
Toreduce the time taken to upload, download or transfera file across a network.
Compressed files containfewer bits of datathan uncompressed files and therefore useless bandwidth, resulting in a faster data transfer rate.
Reduced file size also reduces costs.Cloud storage costs are based on file size; an ISP may charge based on the amount of data downloaded.

The Impact of Compression

Lessbandwidthrequired
Lessstorage spacerequired
Shortertransmission time

Bandwidth

The maximum rate of transfer of data across a network, measured inbits per second.

Real-Life Example: Cloud Storage & Streaming

When you stream a video on Netflix, the file is compressed so it can be sent over the internet quickly and without using too much of your bandwidth. If the video were uncompressed, it would take much longer to load and might use up your entire monthly data allowance. Similarly, when you store photos in Google Drive, compression means you can store more photos in your free storage space.

Activity 3: Why Compress?

A recording of a concert is stored as a file. The file is compressed using lossy compression before it is streamed to users.

State why this file needs to be compressed. [2]
Define the term lossy compression. [2]
The file could be compressed using lossless compression. Explain why lossy compression is a more appropriate compression technique than lossless for this file. [3]

Solution:

The data files are very large [1]; it would take a long time to send the uncompressed file / compressed files will download faster / a higher bandwidth would be needed [1].
Data is lost [1]; the decompressed file is not the same as the original [1].
Lossy creates a smaller file than lossless [1]; the recording of the concert is a large file size and needs significant reduction [1]; lossy removes detail which can be lost without people noticing (e.g. reduction in sound quality will not be noticed) [1].

Check Your Understanding: Need for Compression

1. State three reasons why files need to be compressed. [3 marks]

[1]To save storage space
[1]To reduce transmission time (upload/download/streaming)
[1]To reduce the bandwidth required

2. What is bandwidth and what is it measured in? [2 marks]

[1]Bandwidth is the maximum rate of transfer of data across a network
[1]Measured in bits per second

3. How does compression reduce costs for cloud storage users? [2 marks]

[1]Cloud storage cost is based on the size of files stored
[1]Compressed files are smaller, so they cost less to store

4. Explain why an ISP might charge a user based on the amount of data downloaded. [2 marks]

[1]Downloading data uses the ISP's network bandwidth
[1]The more data downloaded, the more network resources are used, so the ISP may charge accordingly

5. Why would a video streaming service compress its video files? [2 marks]

[1]To reduce the time taken to stream the video to users
[1]To reduce the bandwidth required, allowing more users to stream simultaneously without buffering

6. What are the three main impacts of compression? [3 marks]

[1]Less bandwidth required
[1]Less storage space required
[1]Shorter transmission time

4. Lossy Compression

What is Lossy Compression?

Some data ispermanently lostandcannot be recovered.
The compression algorithmeliminates unnecessary datafrom the file.
Greatly reduces file size.
Reduces the quality of images/sound.
Irreversible— the original file cannot be reconstructed.
Suitable forimages, sound and video.
Cannot be used withtext or executable files(where any loss would be disastrous).

How Lossy Works

The algorithms have to decide which parts of the file need to be retained and which parts can be discarded.

For animage: may reduce the resolution and/or the bit/colour depth.
For asound file: may reduce the sampling rate and/or the resolution.
Lossy files aresmallerthan lossless files — great benefit for storage and data transfer.

Example: Lossy Compression on Photographs

In photographs, lossy compression will try to group similar colours together, reducing the amount of colours in the image without compromising the overall quality.

50% lossy compression: 76 KB
80% lossy compression: 38 KB

Data has been removed and the overall quality has been reduced, however it is difficult to visually see a difference. Lossy compressed photographs take up less storage space which means you can store more and they are quicker to share across a network.

Common Lossy Formats

JPEG— for photographs
MP3— for music/audio
MP4— for video and multimedia
WMV— Windows Media Video
MPG— video format

Perceptual Music Shaping

Used by MP3 to remove sounds that the human ear can't hear properly.

If two sounds are played at the same time, only thelouder onecan be heard by the ear, so thesofter sound is eliminated.
Frequencies outside the human hearing range are removed.
This means certain parts of the music can be removed without affecting quality too much.

Activity 4: Lossy Compression

Define the term lossy compression. [2]
Explain why lossy compression is suitable for photographs but not for text files. [3]
Describe how perceptual music shaping works. [3]

Solution:

Lossy compression is when data is lost [1] in order to reduce the size on secondary storage; the original file cannot be reconstructed [1].
For photographs, reducing the quality slightly is acceptable because humans may not notice the difference [1]. For text files, any loss of data would corrupt the file and make it unreadable [1]. Text files require lossless compression [1].
Perceptual music shaping removes certain sounds [1]. Frequencies outside the human hearing range are removed [1]. If two sounds are played at the same time, only the louder one can be heard, so the softer sound is eliminated [1].

Check Your Understanding: Lossy Compression

1. Is lossy compression reversible? [1 mark]

[1]No — lossy compression is irreversible because data is permanently lost

2. Give two examples of file formats that use lossy compression. [2 marks]

[1]JPEG
[1]MP3 (or MP4, WMV, MPG)

3. Why is lossy compression not suitable for text files? [2 marks]

[1]Any loss of data would corrupt the text file and make it unreadable
[1]Text must be preserved exactly, so lossless compression is required

4. How does lossy compression reduce the size of an image file? [2 marks]

[1]It may reduce the resolution and/or the bit/colour depth
[1]It groups similar colours together, reducing the amount of colours in the image

5. What is perceptual music shaping? [2 marks]

[1]A technique used in MP3 compression that removes sounds the human ear cannot hear properly
[1]For example, if two sounds are played together, the softer sound is eliminated

6. Explain why lossy compression can reduce a file size much more than lossless compression. [2 marks]

[1]Lossy permanently removes data from the file
[1]Lossless keeps all data and only encodes it differently, so it cannot reduce the size as dramatically

5. Lossless Compression

What is Lossless Compression?

No data is lost— the file is just encoded differently.
Files arerecovered to their original statewhen decompressed.
Can be used withall types of data.
Less effectiveat reducing file size than lossy.
Most suitable fortext documents and executable files.
Important for files where any loss of data would be disastrous (e.g. a spreadsheet or a computer application).

Lossless File Formats

TIF— Tagged Image File Format
PDF— Portable Document Format
GIF— Graphics Interchange Format
PNG— Portable Network Graphics
ZIP— compressed archive

Lossless compressed documents take up less storage space which means you can store more and they are quicker to share across a network.

Types of Lossless Compression Algorithms

Huffman Coding

A lossless data compression algorithm.
Instead of having each character coded in one byte, an analysis is carried out to find themost often used characters.
These are then givenshorter codes.
The original stream of bytes becomes abit stream.
Most frequent character gets thesmallest code; least frequent character gets thelargest code.

Example Codes:

Code 10 = e

Code 01 = t

Code 111 = o

Code 110 = h

Code 0001 = l

Code 0000 = p

Code 0011 = w

Code 0010 = z

Run-Length Encoding (RLE)

A simple form of lossless data compression.
Works on sequences with thesame value occurring many consecutive times.
Encodes the sequence to store only asingle value and its count.
Particularly well suited topalette-based bitmap imagessuch as computer icons.
Was a popular image compression method on early online services such as CompuServe.
RLE is only effective where there is a long run of repeated units/bits.

RLE Example 1: Text Data

Original string:aaaaabbbbbccddddd

Each character = 1 byte, so this string needs 16 bytes.

RLE coded:

05 97 04 98 02 99 05 100

This means: 5 characters with ASCII code 97 ('a'), 4 with 98 ('b'), 2 with 99 ('c'), 5 with 100 ('d').

Each number requires 1 byte, so the RLE code needs8 bytes— half the original file size!

Issue:A string like 'cdcdcdcdcd' isn't compressed well by RLE. To cope with this, aflagis used. A flag preceding data indicates that what follows are the number of repeating units. For example, 255 05 97 where 255 is the flag. When a flag is not used, the next byte(s) are taken at face value and a run of 1 (e.g. 01 99 means one character with ASCII code 99 follows).

RLE Example 2: Black and White Image (The Letter 'F')

Original 8×8 grid (1 = white, 0 = black):

Original: 8 × 8 = 64 bytes

Compressed RLE format:

9W 6B 2W 1B 7W 1B 7W 5B 3W 1B 7W 1B 7W 1B 6W

Using W = 1 and B = 0 we get:

91 60 21 10 71 10 71 50 31 10 71 10 71 10 61

Compressed RLE format has30 values, so needs only30 bytesto store the image (down from 64 bytes).

RLE Example 3: Coloured Image

An 8×8 image with 4 colours. Each colour is made up of red, green and blue (RGB).

Square colour	Red	Green	Blue
Black	0	0	0
White	255	255	255
Green	0	255	0
Red	255	0	0

RLE data:2 0 0 0 4 0 255 0 3 0 0 0 6 255 255 255 1 0 0 0 2 0 255 0 4 255 0 0 4 0 255 0 1 255 255 255 2 255 0 0 1 255 255 255 4 0 255 0 4 255 0 4 255 255 255 2 0 255 0 1 0 0 0 2 255 255 255 2 255 0 0 2 255 255 255 3 0 0 0 4 0 255 0 2 0 0 0

Original image (8×8) would need 3 bytes per square (RGB) = 8 × 8 × 3 =192 bytes.

RLE code has92 values, so compressed file =92 bytes.

This gives a file reduction of about52%.

Note: In reality, file reductions will not be as large due to other data stored with the compressed file (e.g. a file header).

Activity 5: Lossless Compression & RLE

Explain the difference between lossless and lossy data compression techniques. [6]
A black and white bitmap image is shown below. Explain how run-length encoding (RLE) will compress the image. [2]
Using RLE, compress the text string "AAAABBCCDAA". [2]

Solution:

Lossless:designed to lose none of the original detail / allows original file to be recreated exactly [1]. Based on some form of replacement [1]. Maximum compression about 50% [1].
Lossy:may result in loss of detail compared to original file / does not allow original file to be re-created exactly [1]. Techniques make decisions about what parts are important and discard other information [1]. Can reduce to about 10% (e.g. JPEG, MP3) [1].
RLE stores the colour and the number of times it occurs [1]. For example, an image with 5 black pixels followed by 1 white pixel would be stored as B5 W1 [1].
"AAAABBCCDAA" →4A2B2C1D2A[1] because there are four 'A's, two 'B's, two 'C's, one 'D', and two 'A's [1].

Check Your Understanding: Lossless Compression

1. Is lossless compression reversible? [1 mark]

[1]Yes — lossless compression is reversible; the file can be returned to its original state

2. What is Run-Length Encoding (RLE)? [2 marks]

[1]A lossless compression method that stores a value and the number of times it repeats consecutively
[1]It is effective where there are long runs of repeated data (e.g. repeated colours in an image)

3. How does Huffman coding compress data? [2 marks]

[1]It analyses the text to find the most frequently used characters
[1]These are given shorter binary codes, while less frequent characters get longer codes

4. When is RLE not effective? [2 marks]

[1]When the data does not contain long runs of repeated values
[1]For example, a string like "cdcdcdcdcd" would not compress well and could even increase in size

5. Give two examples of lossless file formats. [2 marks]

[1]PNG or TIF or GIF or PDF or ZIP
[1]Any second correct format from the list

6. Why is lossless compression more suitable for text documents than lossy compression? [2 marks]

[1]Text documents must preserve every character exactly — any loss of data would corrupt the file
[1]Lossless compression allows the original text to be perfectly reconstructed

6. File Formats

A number of different file formats are used in computer systems. Different formats are suited to different types of data.

Sound	Pictures	Video	Text	Numbers
MP3	JPEG	MP4	ASCII	Real
WAV	GIF	AVI	TXT	Integer
AIFF	TIFF	WebM	RTF	Currency
M4A	BMP	WMV	DOC	Date

MPEG-3 (MP3) and MPEG-4 (MP4)

MP3

Uses technology known asaudio compressionto convert music and other sounds into an MP3 file format.
Reduces the size of a normal music file by about90%.
Example: an 80 MB music CD can be reduced to 8 MB.
Uses alossy format— the original file cannot be put back together again.
Usesperceptual music shaping— removes sounds the human ear can't hear properly.
Quality depends on thebit rate— the number of bits per second used when creating the file.
Bit rates roughly between 80 and 320 kbps; 200 or higher gives a sound quality close to a normal CD.

MP4

Slightly different to MP3 files.
Allows the storage ofmultimedia filesrather than just sound.
Music, videos, photos and animation can all be stored in the MP4 format.
Videos can be streamed over the internet using MP4 without losing any real discernible quality.

Joint Photographic Experts Group (JPEG)

JPEG files use alossyfile compression method.
Used to storephotographsat a reduced file size.
A JPEG will reduce the raw bitmap image by a factor of between5 and 15depending on the quality of the original.
When a photographic file undergoes compression, both thefile size and quality of imageare reduced.
Once the image is subjected to the JPEG compression algorithm, a new file is formed and the original file can no longer be constructed.
A raw bitmap is often referred to as aTIFF or BMP image(.TIF or .BMP).
TIFF and BMP are thehighest image qualitybecause they are not in a compressed format.

Activity 6: File Formats

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. [3]
Explain why JPEG is suitable for photographs but not for text documents. [3]
What is the difference between MP3 and MP4? [2]

Solution:

MP3 is a lossy compressed format [1]. It uses perceptual music shaping [1] which removes sounds the human ear can't hear (e.g. softer sounds when two sounds play together) [1].
JPEG uses lossy compression [1]. For photographs, some loss of detail is acceptable because humans may not notice the difference [1]. Text must be preserved exactly — any loss would corrupt it [1].
MP3 stores only sound/music [1]. MP4 can store multimedia including music, videos, photos and animation [1].

Check Your Understanding: File Formats

1. What type of compression does JPEG use? [1 mark]

[1]Lossy compression

2. By approximately how much does MP3 reduce a music file? [1 mark]

[1]About 90%

3. What is the difference between MP3 and MP4? [2 marks]

[1]MP3 stores only sound/music
[1]MP4 can store multimedia — music, videos, photos and animation

4. What is a bit rate and how does it affect MP3 quality? [2 marks]

[1]Bit rate is the number of bits per second used when creating the file
[1]Higher bit rates (200+ kbps) give sound quality close to a normal CD

5. Why are TIFF and BMP files larger than JPEG files? [2 marks]

[1]TIFF and BMP are not compressed (raw bitmap)
[1]JPEG uses lossy compression, which reduces file size significantly

6. A music track is 4 minutes long. Explain how you would calculate the number of megabytes required to store this track in uncompressed CD quality. [3 marks]

[1]Calculate bytes per second: 44,100 × 16 × 2 ÷ 8 = 176,400 bytes
[1]Multiply by number of seconds: 4 × 60 × 176,400
[1]Divide by 1024 × 1024 to convert to MiB

7. Run-Length Encoding (RLE) in Detail

Run-length encoding (RLE) is a simple form of lossless data compression that runs on sequences with the same value occurring many consecutive times. It encodes the sequence to store only a single value and its count.

How RLE Works

A repeating string is encoded intotwo values.
Thefirst valuerepresents the number of identical data items in the run.
Thesecond valuerepresents the code of the data item (such as ASCII code).
RLE is only effective where there is along run of repeated units/bits.

What RLE is Used For

Particularly well suited topalette-based bitmap imagessuch as computer icons.
Was a popular image compression method on early online services such as CompuServe.
Before the advent of more sophisticated formats such as GIF.
Can be used to compress a number of different file formats.

RLE on Text Data

Consider the text string:'aaaaabbbbbccddddd'

Assuming each character requires 1 byte, this string needs 16 bytes.

Assuming ASCII code is being used, the string can be coded as follows:

05 97 04 98 02 99 05 100

This means we have five characters with ASCII code 97, four characters with ASCII code 98, two characters with ASCII code 99, and five characters with ASCII code 100.

Assuming each number in the second row requires 1 byte of memory, the RLE code will need8 bytes. This ishalf the original file size.

Using a Flag in RLE

One issue occurs with a string such as'cdcdcdcdcd'where RLE compression isn't very effective.

To cope with this, we use aflag. A flag preceding data indicates that what follows are the number of repeating units.

For example:255 05 97where 255 is the flag and the other two numbers indicate that there are five items with ASCII code 97.
When a flag is not used, the next byte(s) are taken at face value and a run of 1 (for example,01 99means one character with ASCII code 99 follows).

Example:

Original string:aaaaaaaabbbbbbbbbbcdcdcdeeeeeeee

Coded version:08 97 10 98 01 99 01 100 01 99 01 100 01 99 01 100 08 101

Original = 32 characters = 32 bytes

Coded version = 18 values = 18 bytes

Introducing a flag (255):

255 08 97 255 10 98 99 100 99 100 99 100 255 08 101

This has 15 values = 15 bytes

Reduction of about53%compared to the original string.

RLE on a Black and White Image

The letter 'F' in an 8×8 grid where each square requires 1 byte of storage. A white square has value 1 and a black square has value 0.

The 8×8 grid would need64 bytes; the compressed RLE format has30 values, and therefore needs only30 bytesto store the image.

RLE on a Coloured Image

An object in four colours. Each colour is made up of red, green and blue (RGB).

Square colour	Red	Green	Blue
Black	0	0	0
White	255	255	255
Green	0	255	0
Red	255	0	0

The original image (8×8 square) would need 3 bytes per square (to include all three RGB values). Therefore, the uncompressed file is 8×8×3 =192 bytes.

The RLE code has92 values, which means the compressed file will be92 bytes. This gives a file reduction of about52%.

Note: In reality, file reductions will not be as large due to other data which needs to be stored with the compressed file (e.g. a file header).

Interactive RLE Visualisation

Click "Compress" to see how RLE compresses a simple black and white image.

Check Your Understanding: RLE in Detail

1. What are the two values stored by RLE for a repeating string? [2 marks]

[1]The number of identical data items in the run
[1]The code of the data item (e.g. ASCII code)

2. Compress the string "AAAABBCCDAA" using RLE. [2 marks]

[1]4A
[1]2B 2C 1D 2A (full answer: 4A2B2C1D2A)

3. Why might RLE not reduce the file size of a bitmap image? Give an example. [3 marks]

[1]RLE stores a colour and the number of times it occurs consecutively
[1]If the image does not have many sequences of the same colour, it would need to store each colour and then the count of 1, which adds data
[1]Example: Red-Green-Blue would become Red 1, Green 1, Blue 1

4. What is the purpose of a flag in RLE? [2 marks]

[1]A flag is used to indicate that what follows are the number of repeating units
[1]It helps to distinguish between a count and a data value when the data itself could be confused with a count

5. A black and white image uses 1 bit per pixel. The image is 100 pixels wide and 50 pixels high. The image contains long runs of white and black pixels. Estimate how RLE might compress this image. [3 marks]

[1]Uncompressed file size = 100 × 50 = 5,000 bits = 625 bytes
[1]RLE would store each run as a count and a colour value
[1]If there are long runs, the compressed file could be significantly smaller (e.g. if average run length is 10, it might use around 100 values instead of 5,000)

6. Explain why RLE is a lossless compression method. [2 marks]

[1]RLE only encodes the data differently, without permanently removing any information
[1]The original data can be perfectly reconstructed by expanding the runs back into their original sequences

Key Takeaways

Data storage units: bit, nibble, byte, KiB, MiB, GiB, TiB, PiB, EiB. IEC uses powers of 1024 (2¹⁰).
1 KiB = 1,024 bytes,1 MiB = 1,024 KiB,1 GiB = 1,024 MiB,1 TiB = 1,024 GiB.
Image file size= resolution × colour depth (or width × height × colour depth).
Sound file size= sample rate × duration × sample resolution. For stereo, multiply by 2.
Compressionreduces file size, saving storage space, reducing bandwidth required, and shortening transmission time.
Lossy compressionpermanently removes data; the original file cannot be reconstructed. Suitable for images, sound and video. Examples: JPEG, MP3, MP4.
Lossless compressiondoes not lose data; the file can be perfectly reconstructed. Suitable for text, spreadsheets, executables. Examples: PNG, ZIP, PDF, TIF, GIF.
Run-Length Encoding (RLE)is a lossless method that stores a value and the number of times it repeats consecutively.
Huffman codingis a lossless method where frequently used characters get shorter binary codes.
Perceptual music shapingremoves sounds the human ear cannot hear properly (used in MP3).
MP3compresses music by about 90%.MP4can store multimedia (music, video, photos, animation).
JPEGuses lossy compression for photographs, reducing file size by a factor of 5 to 15.
RLE is only effectivewhere there are long runs of repeated data. It is not effective for data with little repetition.
Aflagin RLE indicates that what follows are the number of repeating units.

Question Bank

1. Describe what is meant by a bitmap image. [2 marks]

[1]Made up of pixels
[1]Each pixel has one colour, stored as a binary number

2. Explain how a computer can store a black and white bitmap image. [2 marks]

[1]Each pixel requires only one bit (as there are only two colours)
[1]Black is represented by 1 and white by 0 (or vice versa); bits are stored for each pixel in sequence

3. The image is compressed before it is attached to an email. Explain how run-length encoding (RLE) will compress the image. [2 marks]

[1]Stores the colour and the number of times it occurs
[1]An example from the bitmap given, e.g. B5, W1, B1

4. The limited logo is 500 pixels by 1000 pixels and uses 35 different colours. Estimate the file size for the logo. Give your answer in kilobytes. Show your working. [4 marks]

[1]Number of pixels = 500 × 1000 = 500,000
[1]35 colours require 6 bits per pixel (2⁵ = 32, 2⁶ = 64)
[1]Number of bytes = (500,000 × 6) ÷ 8 = 3,000,000 ÷ 8 = 375,000
[1]= 375 KB

5. A recording of a concert is stored as a file. The file is compressed using lossy compression before it is streamed to users. (i) State why this file needs to be compressed. [1] (ii) Define the term lossy compression. [1] (iii) Explain why lossy compression is a more appropriate compression technique than lossless for this file. [3]

(i)The data files are very large / it would take a long time to send the uncompressed file / compressed files will download faster / a higher bandwidth would be needed
(ii)Data is lost / the decompressed file is not the same as the original
(iii)Lossy creates a smaller file than lossless [1]; the recording of the concert is a large file size and needs significant reduction [1]; lossy removes detail which can be lost without people noticing (e.g. reduction in sound quality will not be noticed) [1]

6. Explain the difference between lossless and lossy data compression techniques. [6 marks]

[1]Lossless is designed to lose none of the original detail / allows original file to be recreated exactly
[1]Lossless technique is based on some form of replacement (e.g. RLE, Huffman coding)
[1]Maximum lossless compression is about 50%
[1]Lossy may result in loss of detail compared to original file / does not allow original file to be re-created exactly
[1]Lossy techniques make decisions about what parts of the file are important and discard other information
[1]Lossy compression can reduce to about 10% (e.g. JPEG, MP3)

7. 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. [3 marks]

[1]MP3 is a lossy compressed format
[1]Uses psycho-acoustic modelling and perceptual music/noise shaping
[1]Certain parts of the music can be eliminated without significantly degrading the listener's experience / removes sound that the human ear can't hear

8. Photographs are compressed before they are uploaded to a web server. Customers download photographs from this web server. Explain reasons why compressing photographs will benefit customers. [2 marks]

[1]Customers will be able to download photographs in less time and they will take less bandwidth
[1]Photographs will take up less space on customer's storage medium, therefore customers can store more images and will have more space for other files

9. An image can be compressed using RLE. Explain reasons why RLE may not reduce the file size of a bitmap image. Give one example in your answer. [3 marks]

[1]RLE stores a colour and number of times it occurs consecutively
[1]An image may not have many sequences of the same colour; it would need to store each colour and then the count of 1, which adds data
[1]Example: Red-Green-Blue would become Red 1 Green 1 Blue 1

10. A music track is recorded on a CD. Music is sampled 44,100 times per second, each sample is 16 bits, and each track requires sampling for left and right speakers. (i) Calculate the number of bytes required to store one second of sampled music. Show your working. [3] (ii) A particular track is four minutes long. Describe how you would calculate the number of megabytes required to store this track. [2]

(i)44,100 × 16 × 2 = 1,411,200 bits ÷ 8 =176,400 bytes
(ii)Multiply 176,400 by (4 × 60) = 42,336,000 bytes, then divide by 1024 × 1024 =40.4 MiB

11. A black and white image is 512 pixels by 256 pixels. Calculate the file size of this image in kilobytes (KB) (1 KB = 1024 bytes). [3 marks]

[1]512 × 256 = 131,072 pixels
[1]× 1 bit = 131,072 bits ÷ 8 = 16,384 bytes
[1]÷ 1024 = 16 KB

12. Explain what is meant by perceptual music shaping. [3 marks]

[1]A technique used in lossy audio compression (e.g. MP3)
[1]It removes sounds that the human ear cannot hear properly
[1]For example, if two sounds are played at the same time, only the louder one is heard, so the softer sound is eliminated

13. Convert 2 TiB to GiB. [2 marks]

[1]2 × 1024
[1]= 2048 GiB

14. A company is developing a new messaging app that will be used by people all over the world. The app will allow users to send text messages, photos, and short voice recordings. Explain how compression would be used for each type of data and justify whether lossy or lossless compression would be more appropriate. [6 marks]

Text messages [2]:Uselosslesscompression [1] because text must be preserved exactly — any loss would corrupt the message [1].
Photos [2]:Uselossycompression (e.g. JPEG) [1] because reducing quality slightly is acceptable and greatly reduces file size for faster sending [1].
Voice recordings [2]:Uselossycompression (e.g. MP3) [1] because perceptual music shaping can remove sounds the human ear can't hear, significantly reducing file size with little noticeable quality loss [1].

15. A student says "Compression always makes a file smaller." Explain why this statement is not always true. [3 marks]

[1]RLE is only effective where there are long runs of repeated data
[1]If the data has little repetition, RLE could actually increase the file size because it adds count values
[1]Example: "cdcdcdcdcd" would become 01 99 01 100 01 99 01 100... which is larger than the original