Scribd
Upload
56 views4 pages

Huffman Algorithm and Markov Sources Sources: Ete/Eee 422 Saif Ahmed (Sfa)

Huffman discovered simple properties of optimal prefix-free codes that led to a recursive procedure for constructing optimal codes. This procedure results in the Huffman algorithm, one of the most efficient forms of discrete coding. The algorithm calculates symbol probabilities, generates a tree diagram recursively mapping symbols by probability, and encodes the tree. Markov sources are a memory-based coding system that uses state transitions, requiring less complex circuits than other systems by keeping memory of previous symbols if needed.

Uploaded by

Saif Ahmed
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
56 views4 pages

Huffman Algorithm and Markov Sources Sources: Ete/Eee 422 Saif Ahmed (Sfa)

Huffman discovered simple properties of optimal prefix-free codes that led to a recursive procedure for constructing optimal codes. This procedure results in the Huffman algorithm, one of the most efficient forms of discrete coding. The algorithm calculates symbol probabilities, generates a tree diagram recursively mapping symbols by probability, and encodes the tree. Markov sources are a memory-based coding system that uses state transitions, requiring less complex circuits than other systems by keeping memory of previous symbols if needed.

Uploaded by

Saif Ahmed
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

Huffman Algorithm and Markov

Sources
ETE/EEE 422
Saif Ahmed (SfA)
Huffman Algorithm

Huffman ignored the Kraft inequality, and looked at the binary code tree to
establish properties that an optimal prefix-free code should have. After
discovering a few simple properties, he realized that they led to a simple
recursive procedure for constructing an optimal code.

Leading to one of the most efficient forms of discrete coding, yet to be


used
Huffman Algorithm
• Read a set of messages, and calculate a probability for each symbol
• Generate a tree diagram recursively for symbols such that p(A) = x and p(A’) = 1-x
• Continue until all of the symbols are mapped in the tree
• Encode the tree
Markov Sources
• A memory based coding system that works with the aid of state transitions

• Advantage:
• less complicated circuit system
• Keep the memory of the previous symbol, if required

You might also like