Huffman Coding
Huffman (1952) devised a variable-length encoding algorithm, based on the source letter probabilities. This algorithm is optimum in the sense that the average number of binary digits required to represent the source symbols is a minimum, subject to the constraint that the code words satisfy the Prefix condition.
The steps of the Huffman coding algorithm are given below:
1- Arrange the source symbols in decreasing order of their probabilities.
2- Take the bottom two symbols and tie them together as shown below. Add the probabilities of the two symbols and write it on the combined node. Label the two branches with 1 and 0.
3- Treat this sum of probabilities as a new probability associated with new symbol. Again pick the two smallest Probabilities. Tie them together to form a new probability. Whenever we tie together two probabilities (nodes) we label the two branches with 1 and 0.
4- Continue the procedure unit only one probability is left (and it should be 1).This completes the construction of the Huffman tree.
5- To find out the prefix codeword for any symbol, follow the branches from the final node back to the symbol. While tracing back the route read out the labels on the branches. This is the code word for the symbol.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|