# Huffman coding

Given a set of N symbols S={si, i=1,…N} with probabilities of occurrence Pi, i=1,…N, find the optimal encoding of the symbol to achieve the minimum transmission rate (bits/symbol)

Algorithm:

Each symbol is a leaf node in a tree

Combining the two symbols or composite symbols with the least probabilities to form a new parent composite symbol, which has the combined probabilities. Assign a bit 0 and 1 to the two links

Continue this process until all symbols are merged into one root node (bottom up)

For each symbol, the sequence of the 0s and 1s from the root node to the symbol is the codeword