RLE & Huffman Compression
Unit 5 Summary - part 3
Original (uncompressed) digital files are large when they're stored.
Disadvantages of uncompressed files:
- they use a lot of memory and makes the computer work slowly.
- they take up a lot of storage space.
- they are slow to send over the internet
Colour look-up table/colour palette:
Short list of colour codes needed to store an image.
In 24-bit colour there are 16 million possible colours; however, most images don't use all the colours.
Computers can make a short list of colours to only store the colours needed for that image.
Lossless compression:
-
reduces file size, the file is just stored more efficiently, no data is thrown away,
-
high quality
-
bigger file size.
Lossy compression:
-
reduces file size a lot, some data is thrown away,
-
low quality,
-
smaller file size.
What to lose in using LOSSY compression on IMAGES:
-
Details / resolution:
Image files are now made with fewer pixels.
Details are thrown away by using low resolution.
-
colour depth:
The image now only use fewer colours.
What LOSSY compression cause on AUDIO:
-
Fewer channels:
example from stereophonic to monophonic.
-
Lower sample rate:
fewer samples per second.
-
Lower sample resolution/bit depth:
the compression removes higher and lower sound to store fewer bits.
What LOSSY compression cause on VIDEO:
-
Fewer audio channels:
example: from quadrophonic to monophonic.
-
Lower sample rate.
-
Lower image resolution/quality.
Decompression:
Computers can decompress a compressed video/music to play it.
Lossless compression: full data (quality & details) can be restored to be played.
Lossy compression: not able to restore full data because they were thrown away when being compressed.
Run-length Encoding
(Lossless compression)
Huffman Coding
(Lossless Compression)
File Size Comparison
Huffman vs. ASCII/binary
Oxford AQA IGCSE 2019
08.1.
The Huffman tree in Figure 6 was built to encode a specific 17 character string.
In Figure 6, the underscore is used to represent a space.
A branch to the left is encoded as a 0 and a branch to the right is encoded as a 1.
Figure 6
The bit pattern below represents part of the string that has been encoded:
0000011001110110000001101
What word has been encoded by this bit pattern? [3 marks]
__________________________________________________________________________________
Answer:
1. Create a Huffman dictionary:
N = 000
A = 001
T = 100
L = 101
_ = 110
I = 111
E = 0100
R = 0101
O = 0110
W = 0111
2. The first numbers are 00000, and the letter that has all zeros is N, so it starts with N.
3. Try match this binary: 0000011001110110000001101 with the rest of the dictionary. (Only some letters on the tree are used.)
3. The answer is NATIONAL. Here's the points (based on the answer key:)
1 mark: At least 2 letters decoded correctly and in correct positions OR
2 marks: At least 4 letters decoded correctly and in correct positions OR
3 marks: All letters decoded correctly – NATIONAL
08.2.
The full 17 character string was represented in 55 bits using the Huffman tree in Figure 6. It could have been represented using ASCII instead.
Calculate how many bits of memory have been saved by using the Huffman code to represent the full 17 character string instead of using ASCII.
Show your working. [2 marks]
__________________________________________________________________________________
Answer:
ASCII has 7 bits, so: 7*17 = 119.
That Huffman tree in Figure 6 only has 55 bits, so: 119-55 = 64 bit reduction.
That means, 64 bits are saved.
08.3.
Using the Huffman tree in Figure 6 the character N has been encoded as the bit pattern 000 and the character E has been encoded as the bit pattern 0100
Answer:
N occurs more frequently in the full string, E doesn't occur more frequently than N in the full string;
04.4.
Run length encoding (RLE) can be used to compress bitmap images. Tick (√) one box to indicate which statement about run length encoding is true. [1 mark]
Answer:
D
Oxford AQA IGCSE 2020
12.
Figure 3 is an 8 x 8 black and white image.
The image could be compressed using run length encoding (RLE).
Figure 3
12.1.
Using B for black pixels and W for white pixels give a run length encoding for row 7 in Figure 3. [1 mark]
__________________________________________________________________________________
Answer:
B2 W4 B2;
12.2.
Explain how run length encoding works. [2 marks]
__________________________________________________________________________________
Alternative answers:
-
Store the colour/value of a pixel and a count/quantity/number/ frequency
-
Store the colour/value of a pixel and a count indicates the number of pixels of that colour there are before a pixel of a different colour is used in the image.
-
Store the colour/value of a pixel and a count indicates the total number of pixels of that colour there are in a run.
-
Store the colour/value of a pixel and a count indicates the number of consecutive pixels of the same colour in a row.
Oxford AQA IGCSE Specimen paper
03.
Figure 1 shows a black and white icon that is stored as a bitmap image.
In the bitmap, a white pixel is represented by the value 0 and a black pixel by the value 1.
Figure 1
03.3.
Run length encoding can be used to compress files like images.
Show how the top row of pixels from the image in Figure 1 could be compressed using run length encoding. [1 mark]
__________________________________________________________________________________
03.4.
Explain why run length encoding is good at compressing some images but would not work well for compressing a file of text. [2 marks]
__________________________________________________________________________________
Oxford AQA IGCSE Mock paper
12.1.
Explain what data compression is and why it is used. [2 marks]
__________________________________________________________________________________
12.2.
Some text has been compressed by encoding it using the Huffman tree in Figure 7.
In Figure 7, the underscore is used to represent a space and a branch to the right is encoded as a 1 and a branch to the left as a 0.
Figure 7
The bit pattern below represents the text that has been encoded:
0100110000101011001111000011010011111000
What is the text that was encoded? [2 marks]
__________________________________________________________________________________
12.3.
The text in question 12.2 could have been represented using the ASCII code instead.
Calculate how many bits of memory have been saved by using the Huffman tree in Figure 7 to represent the text instead of using the ASCII code.
Show your working. [2 marks]
__________________________________________________________________________________
