(i) Construct a Huffman coding tree to determine the most efficient alternative coding for the symbols so as to minimise the number of bits/symbol to code a message.

(ii) Determine the average number of bits/symbol required to code a message using this more efficient alternative coding.

[15 marks]

(b) Huffman coding is an efficient means of coding a message so that it occupies the smallest number of average bits/symbol. A message of length x symbols is made from a set of 8 symbols drawn from a vocabulary shown below, with each symbol being coded using 3 binary bits: 3-bit coding Symbol element Relative frequency 0.18 0.1 0 0 0 0 0 B 1 0 1 0 0.05 D 0 1 1 0.05 E 1 0 0 0.4 F 1 0 1 0.06 G 1 1 0 0.04 H 1 1 1 0.12 So the message HEDGE (x = 5) would be coded as 111,100,011,110,100. This message requires a constant 3 bits/symbol. Analysis shows that in general usage, the symbols appear with the relative frequency as shown also in the table