Answer to Question #171303 in Algorithms for Michael

Question

Question 1 Given that the messages y1, y2, y3, y4, y5 with the corresponding probabilities 0.4, 0.2, 0.2, 0.1, and 0.1 a) Construct a binary code by using a Shannon Fano Algorithm to determine?

I. Code efficiency ii. Redundancy of the code iii. Code tree

Question 2 a) Consider a Huffman’s Algorithm that uses a variable-length encoding scheme to compress the original text: GOOD DAY to determine the following?

I. Code tree ii. Codeword iii. Average code length

Question 3 a) Write a short note on the following and state any two (2) practical examples under each? I. Impact printer ii. Non-impact printer b) What is the difference between Additive Color and Subtractive Color and two (2) examples under each?

Answer 1

Question 2

a) Code:

D: 00, O: 01, Space: 100, A: 101, G: 110, Y: 111

i) Code tree:

II) Codeword:

11001010 01000010 11110000

III) Average code length:

$E(L)=\sum L(x_i)P(x_i)=2\cdot0.25+2\cdot0.25+4\cdot3\cdot0.125=2.5\ bits$

Question 1

a)

iii) Code tree:

Code:

$y_1: 11, y_2:011,y_3:00,y_4:10,y_5:010$

i) Code efficiency:

$\eta=H/L$

$L$ is the average codeword length

$E(L)=\sum L(y_i)P(y_i)=2\cdot0.4+3\cdot0.2+2\cdot0.2+2\cdot0.1+3\cdot0.1=2.3\ bits$

$H$ is the entropy per source symbol

$H=-\sum P_{i}logP_i$

$P_i$ is probability of symbol.

$H=-(0.4log0.4+0.2log0.2+0.2log0.2+0.1log0.1+0.1log0.1)=1.47$

$\eta=1.47/2.3=0.64$

ii) Redundancy of the code:

$R=L-H$

$R=2.3-1.47=0.83$