第5章 无失真编码.ppt

Chapter 5 Lossless Source CodingInformationTheoryandCodinglGeneralmodelofdiscrete,lossless(无失真）,non-memorysource:InputsymbolsetCodesymbolsetCodewordset5.1LosslessencoderlHowtocodelosslessly?Assumingthatthestatisticalcharacteristicsofthesourcecanbeignored,itmustsatisfy thefollowingcondition.Togetthetargetoflosslesscoding,itmustconformtothecondition,whichguaranteesthatthereareplentyofcodesymbolstobeused.lFromtheconditionwecangetaninequality,lE.g.5.1SupposeweonlyhavethefirsteightlettersofEnglishalphabet(AtoH)inourvocabulary.TheFixedLengthCode(FLC)forthissetofletterswouldbeLetterCodewordLetterCodewordA000E100B001F101C010G110D011H111Fixed Length CodelAVariableLengthCode(VLC)forthesamesetofletterscanbeLetterCodewordLetterCodewordA00E101B010F110C011G1110D100H1111Variable Length Code1(Huffman coding)lSupposewehavetocodetheseriesofletters:”ABADCAB”.Thefixedlengthcodeandvariablelengthcoderepresentationsofthe7lettersareFixed Length Code000 001 000 011 010 000 001Total bits=21Variable Length Code00 010 00 100 011 00 010Total bits=18ItcanbeseenthattheVLCusesafewernumberofbitsthanFLCsincetheletters,forexample,A,appearingmorefrequently in the sentence are represented with a fewernumberofbits00.lInstantaneous code(prefix code)(1)Itisakindofuniquelydecodablecode(2)Inanunfixedlengthcode,thereisnoonecodebeingprefixtoothercodes.(3)Whendecoding,itdoesnotneedtorefertoitsfollowingcodes,andcanmakethejudgmentimmediately,carryingoutnon-delaydecoding.lLetushavealookatExample5.1again.NowweconsideranotherVLCforthefirst8lettersofEnglishalphabet:LetterCodewordLetterCodewordA0E10B1F11C00G000D01H111Variable Length Code2lThissecondvariablelengthcodeappearstobemoreefficientthanthefirstoneintermsofrepresentationoftheletters.Variable Length Code100 010 00 100 011 00 010Total bits=18Variable Length Code20 1 0 01 00 0 1Total bits=9However,it has decoding problemsHowever,it has decoding problems:Original:010010001-ABADCABNow:010010001-AEABAADOr010010001-ABAABAAABlDefinition 5.1APrefix Codeisoneinwhichnocodewordformstheprefixofanyothercodeword.SuchcodesarealsocalledUniquely DecodableorInstantaneous Codes.lThe optimal codeItisakindofuniquelydecodablecodeItsaveragecodelengthislessthanthatofanyotheruniquelydecodablecode.5.2.1Fixedlengthcodingtheorem5.2LosslesssourcecodingFixed length source coding theoremFixed length source coding theorem:Astothediscrete,non-memory,stationary,ergodicsourcesymbolsequence S=(S1,S2.Sq)，wecanuserdifferentsymbolsX=(x1,x2.xr)toperformfixedlengthcode.Forany0and0，astotheN-expansionsource,Ifissatisfied,andwhenNisbigenough，thedecodingerrorcanbelessthan.Thefixedlengthcodingtheoremhaspresentedatheoreticallimitofthecodelengthusedforfixedlengthcoding.lIftheequallengthcodeisdemandedtobeuniquelydecodable,thenitmusthas:lIfN1，then：Conclusion：foruniquedecoding,eachsourcesymbolneedsatleastcodesymbolstoberepresented.lWhenusedual-codesymboltocode,r2，then：Conclusion：whenuseequallengthdual-code,thelimitcodelengthofeachsourcesymbolisExample5.2.2Unfixedlength(Variablelength)sourcecodinglSeveralconceptsofcodetype(Eg.2.4.2)lNon-singularcodeandsingularcodelUniquelydecodablecodelPrefixcode（instantaneouscode,non-delaycode）lKrafttheoremlUnfixedlengthcodingtheorem（ShannonFirstTheorem）Kraft theoremlquestion：findreal-time,uniquelydecodablecodelmethod：researchthecodepartitionconditionofthereal-timeuniquelydecodablecodelintroduction：conceptof“codetree”lconclusion：presenttheconditionthatthereal-timeuniquelydecodablecode(prefixcode)exists,thatis,theKrafttheoremcode treeThe corresponding relationship between VLC and code tree：(1)TreerootStartingpointofacodeword(2)NumberofbranchesfromatreenodeCodedimension(3)NodePartofacodeword(4)TerminalnodeEndofacodeword(5)NumberofbranchesCodelength(6)Non-fullbranchtreeVariablelengthcode(7)FullbranchtreeFixedlengthcodelTheorem 5.1(Kraft Inequality)AnecessaryandsufficientconditionfortheexistenceofabinaryprefixcodesetwhosecodewordshavelengthsisCode tree map for prooflAveragelengthoftheprefixcodeAdiscretenon-memorystationarysourceItslimitsourceentropyisandthenumberofinputsymbolsetis.Thecodelengthofeachcodewordis,thentheaveragecodelengthofprefixcodeis5.3.3 Lossless unfixed length(variable length)source coding theorem lLossless unfixed length source coding theorem(Shannon First Theorem)lFor discrete non-memory stationary source S,its limit entropy is and its code signals are X=x1,xr.lWe can always code the source S by using a coding method to construct uniquely decodable code.Thus the average code length of each source signal satisfies:lTheorem 5.3(Source Coding TheoremSource Coding Theorem)LetXbethesetoflettersfromaDMSwithfiniteentropyH(X)andxk,k=1,2,Ltheoutputsymbols,occurringwithprobabilities.Giventheseparameters,itispossibletoconstructacodethatsatisfiestheprefixconditionandhasanaveragelengthRthatsatisfiesthefollowinginequalityl lExample：discretesourcewithoutmemoryIts entropy is:Use dual signals（0,1;r=2）construct a prefix code：The average code length of each signal is：The code efficiency is：Construct a prefix code of expansion source S2Prefixcodes1s19/160s1s23/1610s2s13/16110s2s21/16111average code length：average code length of each signal in source S2：code efficiency：Also has:In order to improve the code efficiency,a two-dimensional union code is adopted by considering the 2nd order expansion source of S.Conclusion：Usingunfixedlengthcode,wecanachievequitehighcodingefficiencyevenwhenNisnotveryhigh.Moreoverwemayrealizelosslesscoding.AlsowithNincreasing,thecodingefficiencymoreandmoreapproachesto1.5.4Typicalexampleoflosslesssourcecodingl5.4.1 Huffman codinglCodingmethodlCharacteristiclApplication（Huffman coding）Eg.5.7Codingsteps：1)SortthesourcemessageUaccordingtotheirprobabilitiesinadescendingorder;2)Startfromthetwoleastprobabilities;forexample,thelowerbranchwithlittleprobabilityisassigned“1”,andtheupperbranchisassigned“0”.Ifthetwobranchesprobabilitiesareequal,stillassignthelowerbranch“1”,andtheupper“0”.3)Combinethetwocodedbranches,reorderandrecode.4)Repeatstep3）untilthesumoftheprobabilitiesis1.5)Turnoverfromtherightmostendtotheleftalongthetreebranchtogetthecorrespondingcodeword,likeU3“110”.（Huffman coding）lE.g.1：E.g.2Eight symbols(A-H)with the probabilities of occurrence given in the right table.Please draw the Huffman coding procedure and compute the coding efficiency.SymbolProbabilityA0.10B0.18C0.40D0.05E0.06F0.10G0.07H0.04(1)The entropy of this source is:(2)The average length of codeword is:(3)The efficiency of this code is therefore:lCharacteristicslCodingmethodisnotunique.lEnsurethesignalwithhigherprobabilityhasashortercodeword,whilethesignalwithlowerprobabilityhasalongerone.Thiscanguaranteeashorteraveragecodelength.lThelasttwocodewordsarealwaysdifferentinthelastbitsymbol,andthesameinthepreviousbits.lThetwolongestsymbolshavethesamecodelength.These four characteristics make Huffman coding be one of the optimum coding.lApplication:lApply widely in various fields.example：International digital facsimile coding standard(1980)US HDTV(1995)lProblems：lError spreadinglAlgorithm complexity rapidly grows with the source string length increasingEnd of Chapter 5