The binary Huffman coding procedure can be easily extended to the non- binary case where the code elements come from an m-ary alphabet, m is not equal to 2.
We obtained the Huffman algorithm based in the observation that in an optimum binary prefix code and the requirement that the two symbols with the lowest probability differ only in the last position.
(a)Symbols that occur more frequently will have shorter codewords than symbols that occur less frequently.
(b)The two symbols that occur least frequently will have the same length.
We can obtain a non- binary Huffman code in almost exactly the same way.
The obvious thing to do would be to modify the second observation to read : "The m symbol that occur least frequently will have the same length," and also modify the additional requirement to read "The m symbols with the lowest probability differ only in the last position."
Tunstall Codes
We obtained the Huffman algorithm based in the observation that in an optimum binary prefix code and the requirement that the two symbols with the lowest probability differ only in the last position.
(a)Symbols that occur more frequently will have shorter codewords than symbols that occur less frequently.
(b)The two symbols that occur least frequently will have the same length.
We can obtain a non- binary Huffman code in almost exactly the same way.
The obvious thing to do would be to modify the second observation to read : "The m symbol that occur least frequently will have the same length," and also modify the additional requirement to read "The m symbols with the lowest probability differ only in the last position."
Comments
Post a Comment