PadhaikoAll subjects

Past exam question: 2079 Baishakh (Back), Q8

Data Communication · 10 marks

Open in the Padhaiko app

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

Question

Calculate coding efficiency of "Khoji Rahechha Desh Le Yek Yug Nayak" using Huffman coding technique.

Solution

Character Frequency Analysis and Probability Distribution: The message string to be encoded is:

Counting all characters (including spaces, which are essential delimiter symbols in digital text transmission):

The character frequency count and corresponding probabilities are:

Symbol ()Frequency ()Probability (bits)
[space]6
h5
a4
e4
Y2
k2
K1
o1
j1
i1
R1
c1
D1
s1
L1
u1
g1
N1
y1
Total361.0000—

Source Entropy Calculation: The theoretical minimum average information per symbol is given by Shannon's Source Entropy:

Substituting the calculated probabilities:

Huffman Tree Construction and Codeword Assignment: The Huffman algorithm iteratively combines the two lowest-probability nodes into a parent node until a single root node is formed:

  1. Combining 1-count symbols:
    • Pair each 1-frequency symbol in groups of two: each pair produces weight .
    • Combining pairs of weight 2 produces nodes of weight 4.
  2. Assigning binary digits (0 to left branch, 1 to right branch):
    • High-frequency symbols receive shorter 3-bit codes:
      • [space] (): length bits (111)
      • h (): length bits (101)
      • a (): length bits (000)
      • e (): length bits (001)
    • Medium-frequency symbols receive 4-bit and 5-bit codes:
      • k (): length bits (0100)
      • Y (): length bits (11011)
      • All thirteen 1-frequency symbols (K, o, j, i, R, c, D, s, L, u, g, N, y) receive 5-bit codes (e.g., 01010, 01011, 01100, etc.).

Average Codeword Length and Coding Efficiency:

  1. Average Codeword Length ():
  1. Coding Efficiency ():
  1. Code Redundancy ():

(Note: If the string is evaluated case-insensitively with 17 symbols, , , and . Both approaches demonstrate optimal Huffman coding efficiency exceeding ).

Answer:

For the string "Khoji Rahechha Desh Le Yek Yug Nayak" ( characters, 19 unique symbols):

All past exam questions for Data Communication