PadhaikoAll subjects

Past exam question: 2075 Ashwin, Q9

Data Communication · 10 marks

Open in the Padhaiko app

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

Question

The source of information symbols {A0, A1, A2, A3 and A4} have corresponding probabilities {0.4, 0.3, 0.15, 0.1 and 0.5}. Encode the source symbols using most efficient coding scheme and calculate the corresponding efficiency.

Solution

Selection of the Most Efficient Coding Scheme: According to Shannon's source coding theorem, the Huffman Coding Algorithm produces the mathematically optimal (most efficient) prefix-free variable-length binary code for a discrete memoryless source with known symbol probabilities. Given symbol alphabet with sorted probabilities:

(Note: The exam printed as a typo for , but probabilities must sum to ; ).

Huffman Tree Construction:

  1. Stage 1: Merge lowest two symbols:
    • Remaining set:
  2. Stage 2: Merge lowest two:
    • Remaining set:
  3. Stage 3: Merge lowest two:
    • Remaining set:
  4. Stage 4: Merge final two:

Assigning bits (0 to top/higher probability, 1 to bottom/lower probability):

Codeword Table and Performance Evaluation:

SymbolProbability CodewordLength
01
102
1103
11104
11114
Total1.00——
  1. Average Codeword Length ():
  1. Entropy ():
  1. Coding Efficiency ():
Answer:

The most efficient coding scheme is the Huffman Code:

Performance:

All past exam questions for Data Communication