Scribd
Upload
2 views2 pages

Huffman Coding

Huffman coding is a lossless data compression algorithm that creates a prefix-free variable length code using a binary tree based on symbol probabilities. The process involves listing probabilities, combining the lowest, re-sorting, and assigning bits until a single root node remains. It produces optimal average code lengths and ensures no codeword is a prefix of another, making it efficient for data representation.

Uploaded by

meheraf.gsc2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

Huffman Coding

Huffman coding is a lossless data compression algorithm that creates a prefix-free variable length code using a binary tree based on symbol probabilities. The process involves listing probabilities, combining the lowest, re-sorting, and assigning bits until a single root node remains. It produces optimal average code lengths and ensures no codeword is a prefix of another, making it efficient for data representation.

Uploaded by

meheraf.gsc2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lecture 6: Huffman Coding Algorithm

Topic: Optimal Variable Length Source Coding

1 Introduction
Huffman coding is an algorithm used for lossless data compression. It was developed by
David Huffman in 1952. The algorithm builds a prefix-free variable length code by
constructing a binary tree based on the probabilities of each symbol.

2 The Huffman Algorithm Steps


To generate Huffman codes, follow these steps:

1. List Probabilities: Arrange the symbols in descending order of their probabilities.

2. Combine: Take the two symbols with the lowest probabilities and combine them
into a single node with a probability equal to their sum.

3. Re-sort: Place the new sum back into the list and re-sort the symbols by proba-
bility.

4. Repeat: Repeat the process until only one node (the root) remains with a proba-
bility of 1.0.

5. Assign Bits: Starting from the root, assign ’0’ to one branch and ’1’ to the other
branch of every junction.

3 Numerical Example
Consider a source with 5 symbols and the following probabilities: Symbols: A : 0.35, B :
0.27, C : 0.15, D : 0.15, E : 0.08.

3.1 Codeword Assignment Table


After constructing the Huffman Tree, we obtain the following codewords:

Symbol (xi ) Probability P (xi ) Codeword Length (li )


A 0.35 11 2
B 0.27 01 2
C 0.15 10 2
D 0.15 001 3
E 0.08 000 3

1
3.2 Average Length Calculation
The average length L is calculated as:
X
L= P (xi ) · li
L = (0.35 × 2) + (0.27 × 2) + (0.15 × 2) + (0.15 × 3) + (0.08 × 3)
L = 0.70 + 0.54 + 0.30 + 0.45 + 0.24 = 2.23 bits/symbol

4 Properties of Huffman Coding


• Optimal: Huffman coding produces the shortest average code length among all
prefix codes for a given set of probabilities.

• Prefix Property: No codeword is a prefix of another, ensuring instantaneous


decoding.

• Uniqueness: The Huffman tree (and thus the codes) may not be unique if prob-
abilities are tied, but the resulting average length L will always be the same and
optimal.

Huffman coding is a powerful tool for efficient data representation. In modern systems,
it is often combined with other techniques to achieve maximum compression efficiency.

You might also like