PadhaikoAll subjects

Past exam question: 2074 Chaitra, Q9(a)

Data Communication · 4 marks

Open in the Padhaiko app

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

Question

Write down the Huffman Algorithm clearly.

Solution

Step-by-Step Specification of the Huffman Algorithm: The Huffman algorithm constructs an optimal prefix-free variable-length binary code for a discrete memoryless source:

  1. Source Probability Ordering: List all unique source symbols and their corresponding probabilities in strictly descending order ().
  2. Initial Node Creation: Treat each symbol as an individual leaf node of a binary tree, labeled with its probability.
  3. Iterative Binary Tree Reduction:
    • Identify the two available nodes with the lowest probabilities (say and ).
    • Create a new parent node with combined probability .
    • Connect the two children nodes to this parent.
    • Remove the two children from the active candidate list and insert the parent node, maintaining descending probability order.
  4. Termination: Repeat this reduction until exactly one root node with aggregate probability remains.
  5. Codeword Extraction: Label every left branch with binary digit 0 and every right branch with binary digit 1 (or vice versa). Trace the unique path from root to each terminal leaf node to obtain its prefix codeword.
Answer:

The Huffman Algorithm operates by:

  1. Sorting symbol probabilities in descending order.
  2. Successively merging the two lowest-probability nodes into a parent node whose probability equals their sum.
  3. Repeating until a single root node of probability is formed.
  4. Assigning binary 0 and 1 to opposing tree branches, extracting prefix codewords by tracing from root to each leaf.

All past exam questions for Data Communication