The Shannon–Fano algorithm doesn't always generate an optimal code. In 1952, David A. Huffman gave a different algorithm that always produces an optimal tree for any given probabilities. While the Shannon–Fano tree is created from the root to the leaves, the Huffman

**HUFFMAN CODING:**

The Shannon–Fano algorithm doesn't always generate an optimal code. In 1952, David A. Huffman gave a different algorithm that always

produces an optimal tree for
any given probabilities. While the Shannon–Fano tree is created from the root
to the leaves, the Huffman

^{}

^{ü }**Procedure for Huffman Algorithm:**^{}

1. Create a
leaf node for each symbol algorithm works from leaves to the root in the
opposite direction and add it to frequency of occurrence.

2. While
there is more than one node in the queue:

·
Remove the two nodes of lowest probability or
frequency from the queue

·
Prepend 0 and 1 respectively to any code already
assigned to these nodes

·
Create a new internal node with these two nodes as
children and with probability equal to the sum of the two nodes' probabilities.

·
Add the new node to the queue.

3.
The remaining node is the root node and the tree is
complete.

^{ü} **Tree diagram:**

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Communication Theory : Information Theory : Huffman Coding |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.