- Alibek Jakupov

# Information Theory: Step 4 Huffman decoder

Updated: May 6, 2019

In previous article we implemented Huffman algorithm.

Here is a brief summary of the previous article

**Given (Input)**

A set of symbols and their weights (usually proportional to probabilities).

Alphabet A={a1,a2,…,an}, which is the symbol alphabet of size n.

Set W={w1,w2,…,wn}, which is the set of the (positive) symbol weights (proportional or equal to probabilities), i.e. wi = weight (ai), 1 <= i <= n.

**Find** **(Output)**

A binary code (a set of codewords) with minimum expected codeword length.

Code C(A,W)={c1,c2,…,cn}, which is the set of (binary) codewords, where ci is the codeword for ai, 1 <= i <= n.

A prefix code is a uniquely decodable code: a receiver can identify each word without requiring a special marker between words.

Thus it makes sense to add a decoder for our algorithm. The logic is quite simple : we construct a dictionary and then use this dictionary to decode our message.

And as usual, __git hub__ link