PadhaikoAll subjects

Past exam question: 2072 Chaitra, Q10

Data Communication · 6 marks

Open in the Padhaiko app

Topic: Wireless propagation (Introduction to groundwave propagation, sky…

Question

A message source generates 8 symbols with the following probabilities:

Encode the message using Huffman code.

Solution

Initial Probabilities and Dyadic Property: Notice that all probabilities are powers of two ( for , and ). Check the sum of probabilities:

Huffman Tree Construction: Following Huffman's algorithm, repeatedly combine the two lowest probability nodes:

  1. Iteration 1: Combine and to form node with probability:
  1. Iteration 2: Combine and to form node with probability:
  1. Iteration 3: Combine and to form node with probability:
  1. Iteration 4: Combine and to form node with probability:
  1. Iteration 5: Combine and to form node with probability:
  1. Iteration 6: Combine and to form node with probability:
  1. Iteration 7: Combine and to form root node with probability .

Assign 0 to the upper branch and 1 to the lower branch at each internal node.

Codeword Assignment Table:

SymbolProbability Assigned Binary CodewordCode Length
01
102
1103
11104
111105
1111106
11111107
11111117

Performance and Efficiency Evaluation: Calculate source entropy :

Calculate average codeword length :

Coding efficiency :

Because the symbol probabilities are exact negative powers of 2, the Huffman code achieves theoretical 100% efficiency.

Answer:

Huffman codewords for the 8 dyadic symbols: : 0, : 10, : 110, : 1110, : 11110, : 111110, : 1111110, : 1111111. Average length , giving 100% coding efficiency.

All past exam questions for Data Communication