(a) Run length encoding (RLE) represents data as frequency/data pairs. Give the RLE of this bit pattern as frequency/data pairs. [2]
0000000111110000000011(b) The Huffman tree shown was built for the text ABRACADABRA.
(i) State the Huffman code for the character R. [1]
(ii) Calculate the number of bits needed to store ABRACADABRA using this Huffman code. [2]
(iii) Calculate how many bits are saved compared with storing the text using 7-bit ASCII. [2]
- (a) 7 0, 5 1 (first two pairs correct)(1)
- (a) 8 0, 2 1 (all pairs correct, in order)(1)
- (b)(i) 101(1)
- (b)(ii) Codes: A = 0, B = 100, R = 101, C = 110, D = 111 and frequencies used, e.g. 5×1 + 2×3 + 2×3 + 1×3 + 1×3(1)
- (b)(ii) 23 (bits)(1)
- (b)(iii) 11 × 7 = 77 (bits)(1)
- (b)(iii) 77 − 23 = 54; follow through from their (ii)(1)
- Answer: (a) 7 0 5 1 8 0 2 1 (b)(i) 101 (ii) 23 bits (iii) 54 bits
- Examiner tip: In (iii) count every character, including repeats: 11 characters × 7 bits, not 5 distinct characters.