Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M.

Muttur

1.3
COMPRESSION
LEARNING OBJECTIVES
Candidates should be able to:

a) Show understanding of the need for and examples of the use of compression
b) Show understanding of lossy and lossless compression and justify the use of a method in a given situation
c) Show understanding of how a text file, bitmap image, vector graphic and sound file can be compressed

[Including the use of run-length encoding (RLE)]

1.3 (A) – NEED FOR COMPRESSION

File Compression
File compression means reducing the size of a file so that it takes up less space on disk or is transmitted faster
over Internet connections. The easiest way to reduce file size is to remove redundant information. Instead of
listing a piece of information over and over again, file-compression programs lists that information once and
then refers back to it whenever it appears in the original program.

Nyquist Theorem
There are various ways you can reduce the size of files. We have also seen that humans have a limit to the
frequencies that they can perceive. So sampling rate would be needed to only store the samples that humans
can perceive. The range of human hearing is between 20 Hz and 20 KHz.

You lose your hearing with age. The older you are the less likely you are able to hear the full spectrum.

Why cannot we use 20 KHz as our sampling rate (record 20 000 cycles per second).

Cycle - A complete oscillation (up and down) in a sound wave

Period - The time that a wave takes to oscillate one cycle.
Frequency - The number of waves passing a point per second

We are going to try and sample this sound that shows 3 cycles

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 1

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur

Taking one sample per cycle leads to a straight line! We're going to need more samples

Taking 1.5 samples per cycle leads to a skewed representation

What we need to properly represent a sound wave is to sample it at least two times per cycle.
2 samples per cycle gives us a close representation of the sound.

Therefore the minimum sampling rate that satisfies the sampling for the human ear is 40 kHz (2*20kHz). The
44.1 kHz sampling rate used for Compact Disc was chosen for this and other technical reasons.

Nyquist's theorem - the sample rate should be at a frequency which is at least twice the value of the highest
frequency in the sampled signal.

1.3 (B) LOSSY AND LOSSLESS COMPRESSION

Lossless Compression
Lossless compression allows you to compress a file and then recreate the original file exactly. All lossless
compression is based on breaking the file into smaller form for transmission and then putting it back together
on the receiving end to be used again.

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 2

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur

Lossy Compression
Lossy compression eliminate “unnecessary” (redundant) bits of information. The file is hence smaller. This type
of compression is used a lot for reducing the file size of bitmap pictures.

With lossy compression, you cannot get the original file back after it has been compressed. Lossy compression
must not be used for anything that needs to be reproduced exactly such as software applications, databases,
text documents, etc.

Lossy compression is preferred for graphics, sound or video. Even if the compressed file is of lower quality and
some data is missing, it is highly unlikely that the human ear or eye would notice the difference.

1.3 (C) FILE FORMATS

The following are the file formats used most usually:
 pictures
o JPEG
o PNG
 Sound
o MP3
o AAC
o OGG
 Video
o MP4
o DivX

Image Compression
JPEG is used here. It replaces a series of pixels with an average colour. This is called a sub sample.

MP3 Compression
The MP3 format is a compression system for music. The goal is to compress a CD-quality song by a factor of 10
to 14 without noticeably affect the CD-quality sound. A 32 megabyte song on a CD compresses down to about
3 MB. This is then easier to download and allows you to store hundreds/thousands of songs on your computer’s
hard disk.

MP3 compression uses a technique called perceptual music shaping. There are certain sounds that the human
ear cannot hear (20 Hz to 20 KHz only can be heard), there are certain sounds that the human ear hears much
better than other and if there two sounds playing simultaneously, we hear the louder one but cannot hear the
softer one.

MP4 Compression
Temporal and spatial redundancy are two techniques most often used to compress video files.

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 3

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur

Runtime Encoding (RTE) / Runlength Encoding (RLE)

This is a form of data compressions in which runs of data (sequences in which the same data value occurs) are
stored as a single data value and count rather than the original run. This is most useful on data that contains
many such runs. This type of compression is used when compressing text file or a program.

Example:
Consider a screen containing plain black text on a solid white background. There will be many runs of white
pixels in the blank space and many runs of black pixels within the text. Consider a line from that screen with B
representing a black pixel and W representing a white pixel.

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWW
WWW
The above line can be replaced by:
W12B1W12B3W24B1W14
67 characters have been replaced by only 18 characters.

An alternative way to represent run-length encoded data: run lengths for runs of two or more characters only
are encoded:

WW12BWW12BB3WW24BWW14

This would be interpreted as a run of twelve Ws, a B, a run of twelve Ws, a run of three Bs, etc. In data where
runs are less frequent, this can significantly improve the compression rate.

Huffmann Encoding
Huffman encoding is used for sound compression.

Variable-length codes are assigned to characters. Length of the assigned codes are based on the frequencies of
corresponding characters. The most frequent character gets the smallest code and the least frequent character
gets the largest code.

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 4

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur

EXERCISES
Question 1

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 5

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur
Question 2

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 6

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur

Question 3

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 7

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 8

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur
Question 4

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 9

Computer Science Compiled – Workbook 2023 – Part 1 | A Level 9618 (Lower Six) | © M. Muttur
Question 5

Muzzammil Muttur |  5 493 1972 | [email protected] | @mmuttur 10