FundamentalsofMultimedia,Chapter7(5)(5)00(2)(3)E,O:(2)L,H:(3)00H:(1)0:(1)L:(2)E:(1)(a)(b)Fig.7.4 Another codingtree forHELLO by Shannon-Fano
Fundamentals of Multimedia, Chapter 7 (5) (a) L,H:(3) E,O:(2) 0 1 (5) (3) H:(1) E:(1) O:(1) (2) L:(2) 0 1 (b) 0 1 0 1 Fig. 7.4 Another coding tree for HELLO by Shannon-Fano
FundamentalsofMultimedia,Chapter7Table 7.2:AnotherResult ofPerformingShannon-FanoonHELLO (seeFig.7.4)10g2 CodeSymbolCount# of bits usedL24001.32H21012.322E1102.32201112.3210TOTALnumberofbits:
Fundamentals of Multimedia, Chapter 7 Table 7.2: Another Result of Performing Shannon-Fano on HELLO (see Fig. 7.4) Symbol Count log 2 1 pi Code # of bits used L 2 1.32 00 4 H 1 2.32 01 2 E 1 2.32 10 2 O 1 2.32 11 2 TOTAL number of bits: 10
FundamentalsofMultimedia,Chapter7HuffmanCodingALGORITHM7.1 HuffmanCodingAlgorithmabottom-upapproach1.Initialization: Put all symbols on a list sorted according totheirfrequency counts.2.Repeatuntilthelisthasonlyonesymbolleft:(1)From the list pick two symbols with thelowestfrequency counts.Forma Huffmansubtree that has thesetwo symbols aschildnodesand create a parent node.(2)Assignthesumofthechildren'sfrequencycountstotheparent andinsert it into the list suchthatthe orderis maintained.(3) Delete the children from the list.3.Assignacodewordforeachleafbasedonthepathfromtheroot
Fundamentals of Multimedia, Chapter 7 Huffman Coding ALGORITHM 7.1 Huffman Coding Algorithm — a bottomup approach 1. Initialization: Put all symbols on a list sorted according to their frequency counts. 2. Repeat until the list has only one symbol left: (1) From the list pick two symbols with the lowest frequency counts. Form a Huffman subtree that has these two symbols as child nodes and create a parent node. (2) Assign the sum of the children’s frequency counts to the parent and insert it into the list such that the order is maintained. (3) Delete the children from the list. 3. Assign a codeword for each leaf based on the path from the root
FundamentalsofMultimedia,Chapter7PI:(2)P2:(3)00P1:(2)10E:(1)0:(1)H:(1)E:(1)0:(1)(b)(a)P3:(5)0P2:(3)0L:(2)P1:(2)0H:(1)E:(1)0:(1)(c)Fig.7.5:Coding Tree for "HELLO using theHuffmanAlgorithm
Fundamentals of Multimedia, Chapter 7 E:(1) P1:(2) O:(1) (a) 0 1 (b) H:(1) P2:(3) E:(1) O:(1) P1:(2) 0 1 0 1 L:(2) O:(1) P3:(5) E:(1) H:(1) (c) P1:(2) P2:(3) 0 1 0 1 0 1 Fig. 7.5: Coding Tree for “HELLO” using the Huffman Algorithm
FundamentalsofMultimedia,Chapter7HuffmanCoding (cont'd)InFig.7.5,newsymbolsP1,P2,P3arecreatedtorefertotheparent nodes in the Huffman coding tree. The contents in thelistareillustratedbelow:LHEOAfterinitialization:LP1HAfter iteration (a):L P2After iteration (b):P3After iteration (c):
Fundamentals of Multimedia, Chapter 7 Huffman Coding (cont’d) In Fig. 7.5, new symbols P1, P2, P3 are created to refer to the parent nodes in the Huffman coding tree. The contents in the list are illustrated below: After initialization: L H E O After iteration (a): L P1 H After iteration (b): L P2 After iteration (c): P3