FundamentalsofMultimedia,Chapter7Properties ofHuffman Coding1.UniguePrefixProperty:No Huffman codeis aprefixofanyotherHuffman code-precludes any ambiguity in decoding2.Optimality: minimumredundancy code-provedoptimalfor a given data model (i.e.,a given, accurate, probabilitydistribution):Thetwoleastfrequentsymbolswillhavethesamelengthfor their Huffman codes, differing only at the last bit.Symbolsthatoccurmorefreguentlywill haveshorterHuff-mancodesthansymbolsthat occurlessfrequentlyThe averagecode lengthfor an information source S isstrictly less than n +1.Combined with Eq.(7.5), wehave:i<n+1(7.6)
Fundamentals of Multimedia, Chapter 7 Properties of Huffman Coding 1. Unique Prefix Property: No Huffman code is a prefix of any other Huffman code - precludes any ambiguity in decoding. 2. Optimality: minimum redundancy code - proved optimal for a given data model (i.e., a given, accurate, probability distribution): • The two least frequent symbols will have the same length for their Huffman codes, differing only at the last bit. • Symbols that occur more frequently will have shorter Huff- man codes than symbols that occur less frequently. • The average code length for an information source S is strictly less than η + 1. Combined with Eq. (7.5), we have: ¯ l<η + 1 (7.6)
FundamentalsofMultimedia,Chapter7Extended Huffman CodingMotivation: All codewords in Huffman coding have integerbit lengths. It is wasteful when Pi is very large and hencelog2元 is close to0Why not group several symbols together and assign a singlecodewordtothegroupasa whole?.ExtendedAlphabet:Foralphabet S=[s1,s2,..,n],ifksymbols are grouped together,then the extended alphabetis:ksymbolsS(k) = [$1$1...S1, 8181...82, ..., $181 ...8n,S1$1...S2S1,., SnSn...Sn).the size of the new alphabet s(k)isnk
Fundamentals of Multimedia, Chapter 7 Extended Huffman Coding • Motivation: All codewords in Huffman coding have integer bit lengths. It is wasteful when p i is very large and hence log 2 1 pi is close to 0. Why not group several symbols together and assign a single codeword to the group as a whole? • Extended Alphabet: For alphabet S = { s 1, s 2,.,s n }, if k symbols are grouped together, then the extended alphabet is: S ( k ) = { k symbols z }| { s 1 s 1 .s 1, s 1 s 1 .s 2, ., s 1 s 1 .s n, s 1 s 1 .s 2 s 1, ., s n s n .s n }. — the size of the new alphabet S ( k ) is n k