FundamentalsofMultimedia,Chapter7EntropyandCode LengthAscanbeseen inEq.(7.3):theentropynisaweighted-sum;henceit represents the average amount ofoftermslog2information contained per symbol in the source S.Theentropynspecifiesthelowerboundfortheaveragenum-berof bitstocode eachsymbol inS,i.e.,n≤T(7.5)T- the average length (measured in bits) of the codewordsproduced by the encoder
Fundamentals of Multimedia, Chapter 7 Entropy and Code Length • As can be seen in Eq. (7.3): the entropy η is a weighted-sum of terms log 2 1 pi; hence it represents the average amount of information contained per symbol in the source S. • The entropy η specifies the lower bound for the average number of bits to code each symbol in S, i.e., η ≤ ¯l (7.5) ¯l - the average length (measured in bits) of the codewords produced by the encoder
FundamentalsofMultimedia,Chapter77.3 Run-Length CodingMemorylessSource:aninformationsourcethat isindepen-dently distributed. Namely,the value of the current symboldoes not depend on the values of the previously appearedsymbols.Insteadofassumingmemorylesssource,Run-LengthCoding(RLC)exploits memorypresentin theinformationsource.Rationale for RLC:if theinformation sourcehastheprop-erty that symbols tend to form continuous groups, then suchsymbol and the lengthof the group canbe coded
Fundamentals of Multimedia, Chapter 7 7.3 Run-Length Coding • Memoryless Source: an information source that is independently distributed. Namely, the value of the current symbol does not depend on the values of the previously appeared symbols. • Instead of assuming memoryless source, Run-Length Coding (RLC) exploits memory present in the information source. • Rationale for RLC: if the information source has the property that symbols tend to form continuous groups, then such symbol and the length of the group can be coded
FundamentalsofMultimedia,Chapter77.4Variable-Length Coding (VLC)Shannon-FanoAigorithmatop-downapproach1.Sort the symbols according to the frequency count of theiroccurrences.2.Recursivelydividethesymbolsintotwoparts,eachwithap-proximatelythe samenumber of counts,until allparts con-tain only one symbol.AnExample:codingof“HELLO"EHL0Symbol1121CountFrequencycountofthesymbolsin"HELLO
Fundamentals of Multimedia, Chapter 7 7.4 Variable-Length Coding (VLC) Shannon-Fano Algorithm — a top-down approach 1. Sort the symbols according to the frequency count of their occurrences. 2. Recursively divide the symbols into two parts, each with approximately the same number of counts, until all parts contain only one symbol. An Example: coding of “HELLO” Symbol HELO Count 1121 Frequency count of the symbols in ”HELLO
FundamentalsofMultimedia,Chapter7(5)(5)001(3)0L:(2)H,E,O:(3)L:(2)H:(1)E,O:(2)(b)(a)(5)0(3)0L:(2)(2)0H:()1E:(1)0:(1)(c)Fig.7.3:CodingTree for HELLO byShannon-Fano
Fundamentals of Multimedia, Chapter 7 L:(2) (5) H,E,O:(3) (a) 0 1 (b) L:(2) (5) H:(1) E,O:(2) (3) 0 1 0 1 L:(2) O:(1) (5) E:(1) H:(1) (c) (2) (3) 0 1 0 1 0 1 Fig. 7.3: Coding Tree for HELLO by Shannon-Fano
FundamentalsofMultimedia,Chapter7Table 7.1:Result of Performing Shannon-Fano on HELLO10g2 1CountCodeSymbol# of bits usedL2021.32H122.3210E311102.323012.3211110TOTALnumberofbits:
Fundamentals of Multimedia, Chapter 7 Table 7.1: Result of Performing Shannon-Fano on HELLO Symbol Count log 2 1 pi Code # of bits used L 2 1.32 0 2 H 1 2.32 10 2 E 1 2.32 110 3 O 1 2.32 111 3 TOTAL number of bits: 10