Skip to main content

Huffman coding principle

Short answer

Huffman coding assigns shorter variable-length prefix codes to more frequent symbols, minimizing average code length. The algorithm repeatedly merges the two least probable nodes, building a binary tree, then assigns 0/1 to branches. Example: probabilities 0.4,0.3,0.2,0.1 yield codes A=0, B=10, C=111, D=110 with average length 1.9 bits.

Explain the general working principle of the Huffman coding algorithm.

Huffman coding is a lossless source-coding method that assigns variable-length prefix codes to symbols, shorter codes to more probable symbols and longer codes to rare ones, so that the average code length is minimum and close to the entropy.

Principle

  • A prefix code has no codeword that is a prefix of another, so decoding is instant and unambiguous.
  • Frequent symbols get short codes, so the average length L = Σ pᵢ lᵢ is minimised. Huffman's algorithm produces an optimal prefix code for given probabilities, with H ≤ L < H + 1.

Algorithm

  1. List the symbols with their probabilities (or frequencies).
  2. Pick the two symbols with the smallest probabilities and merge them into a new node whose probability is the sum.
  3. Repeat step 2 with the new node in the list until only one node (the root, probability 1) remains.
  4. Label the two branches at each node 0 and 1.
  5. Read the code for each symbol from the root down to its leaf.

Small example

A = 0.4, B = 0.3, C = 0.2, D = 0.1.

 D(0.1)+C(0.2)=0.3 ; 0.3+B(0.3)=0.6 ; 0.6+A(0.4)=1
 A=0  B=10  C=111  D=110

L = 0.4(1) + 0.3(2) + 0.2(3) + 0.1(3) = 1.9 bits; H = 1.846 bits; efficiency = 97.2 %.

Properties

  • Efficiency η = H / L. No other symbol-by-symbol code gives a smaller L.
  • Codes are not unique when ties occur, but L is the same.
  • The code table must be sent to the decoder (or both sides must know probabilities).
  • Used in JPEG, MP3, ZIP and fax.

✓ Answer checked by Claude Sonnet 5.5

Related questions

All Data Communication chapter 8 questions →