PadhaikoAll subjects

Past exam question: 2076 Ashwin, Q8(a)

Data Communication · 7 marks

Open in the Padhaiko app

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

Question

Design a Binary Shannon-Fano code with a six symbol source with probability assignment as .

Solution

Principles of Binary Shannon-Fano Coding Algorithm:

  1. Arrange source symbols in descending order of probabilities.
  2. Divide the sorted set of symbols into two subsets whose accumulated probability sums are as nearly equal as possible.
  3. Assign binary digit 0 to the first subset and binary digit 1 to the second subset.
  4. Recursively repeat the partitioning and bit-assignment process for each subset until each sub-group contains exactly one symbol.

Sorting and Recursive Partitioning: Source symbols sorted in descending probability order:

Total probability .

Iteration 1:

Iteration 2 (Partitioning Subset B):

Iteration 3 (Partitioning Subset B2):

Iteration 4:

Assigned Shannon-Fano Codewords Table:

SymbolProbability Stage 1Stage 2Stage 3Stage 4Final CodewordCodeword Length ()
0———01
10——102
110011004
110111014
111011104
111111114
Answer:

The Binary Shannon-Fano code assignments are:

All past exam questions for Data Communication