PadhaikoAll subjects

Past exam question: 2078 Bhadra, Q8

Data Communication · 10 marks

Open in the Padhaiko app

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

Question

Encode "Jasta lai tastai dhido lai nistai" using weighted Huffman encoder. Also demonstrate how it is decoded.

Solution

Frequency Analysis of the Input Message: Given string: "Jasta lai tastai dhido lai nistai" (case-sensitive, including spaces). Total length: characters across 11 unique symbols:

Check total: .

Huffman Tree Construction and Codeword Table: Iteratively merging the two lowest-weight nodes (0 to left child, 1 to right child):

SymbolWeight CodewordLength
'a'700214
'i'6111318
' '5110315
't'4011312
's'301039
'd'2100048
'l'2100148
'J'11010055
'h'11010155
'n'11011055
'o'11011155
Total33——104

Average codeword length , entropy , efficiency .

Encoding the Message: Substituting each character with its prefix codeword:

Complete encoded bitstream (104 bits): 10100000100110011010010011111001100010011001111101000101011111000101111101001001111101011011101001100111

Demonstration of Decoding Procedure: The decoder starts at the root of the shared Huffman tree and reads incoming bits left-to-right (0 = left, 1 = right) until reaching a leaf:

  1. 10100: reaches leaf 'J'. Emit 'J', reset to root.
  2. 00: reaches leaf 'a'. Emit 'a', reset to root.
  3. 010: reaches leaf 's'. Emit 's', reset to root.
  4. 011: reaches leaf 't'. Emit 't', reset to root.
  5. 00: reaches leaf 'a'. Emit 'a', reset to root.
  6. 110: reaches leaf ' '. Emit ' ', reset to root.

Continuing through all 104 bits uniquely reconstructs "Jasta lai tastai dhido lai nistai" with zero ambiguity because the code is prefix-free.

Answer:

For "Jasta lai tastai dhido lai nistai" ( characters, 11 unique symbols), the weighted Huffman codewords are: 'a': 00, 'i': 111, ' ': 110, 't': 011, 's': 010, 'd': 1000, 'l': 1001, 'J': 10100, 'h': 10101, 'n': 10110, 'o': 10111. The full message encodes into (, efficiency ), and is uniquely decoded left-to-right by traversing the Huffman tree from root to leaf.

All past exam questions for Data Communication