第5章-无失真编码

Chapter5LosslessSourceCodingInformationTheoryandCodingGeneralmodelofdiscrete,lossless(无失真）,non-memorysource:InputsymbolsetCodesymbolsetCodewordset12(,,...,);1,2,...,liiiiiiilsWxxxiq12{,,...,)irXxxx5.1LosslessencoderHowtocodelosslessly?Assumingthatthestatisticalcharacteristicsofthesourcecanbeignored,itmustsatisfythefollowingcondition.Togetthetargetoflosslesscoding,itmustconformtothecondition,whichguaranteesthatthereareplentyofcodesymbolstobeused.NlqrFromtheconditionwecangetaninequality,rqNlrqlNloglogE.g.5.1SupposeweonlyhavethefirsteightlettersofEnglishalphabet(AtoH)inourvocabulary.TheFixedLengthCode(FLC)forthissetofletterswouldbeLetterCodewordLetterCodewordA000E100B001F101C010G110D011H111FixedLengthCodeAVariableLengthCode(VLC)forthesamesetofletterscanbeLetterCodewordLetterCodewordA00E101B010F110C011G1110D100H1111VariableLengthCode1(Huffmancoding)Supposewehavetocodetheseriesofletters:”ABADCAB”.Thefixedlengthcodeandvariablelengthcoderepresentationsofthe7lettersareFixedLengthCode000001000011010000001Totalbits=21VariableLengthCode000100010001100010Totalbits=18ItcanbeseenthattheVLCusesafewernumberofbitsthanFLCsincetheletters,forexample,A,appearingmorefrequentlyinthesentencearerepresentedwithafewernumberofbits‘00’.Instantaneouscode(prefixcode)(1)Itisakindofuniquelydecodablecode(2)Inanunfixedlengthcode,thereisnoonecodebeingprefixtoothercodes.(3)Whendecoding,itdoesnotneedtorefertoitsfollowingcodes,andcanmakethejudgmentimmediately,carryingoutnon-delaydecoding.LetushavealookatExample5.1again.NowweconsideranotherVLCforthefirst8lettersofEnglishalphabet:LetterCodewordLetterCodewordA0E10B1F11C00G000D01H111VariableLengthCode2Thissecondvariablelengthcodeappearstobemoreefficientthanthefirstoneintermsofrepresentationoftheletters.VariableLengthCode1000100010001100010Totalbits=18VariableLengthCode2010010001Totalbits=9However,ithasdecodingproblems:Original:010010001--ABADCABNow:010010001--AEABAADOr010010001--ABAABAAABDefinition5.1APrefixCodeisoneinwhichnocodewordformstheprefixofanyothercodeword.SuchcodesarealsocalledUniquelyDecodableorInstantaneousCodes.TheoptimalcodeItisakindofuniquelydecodablecodeItsaveragecodelengthislessthanthatofanyotheruniquelydecodablecode.5.2.1Fixedlengthcodingtheorem5.2LosslesssourcecodingFixedlengthsourcecodingtheorem:Astothediscrete,non-memory,stationary,ergodicsourcesymbolsequenceS=(S1,S2…..Sq)，wecanuserdifferentsymbolsX=(x1,x2….xr)toperformfixedlengthcode.Foranyε0andδ0，astotheN-expansionsource,Ifissatisfied,andwhenNisbigenough，thedecodingerrorcanbelessthanδ.Thefixedlengthcodingtheoremhaspresentedatheoreticallimitofthecodelengthusedforfixedlengthcoding.log()(0)lrHSNIftheequallengthcodeisdemandedtobeuniquelydecodable,thenitmusthas:IfN＝1，then：Conclusion：foruniquedecoding,eachsourcesymbolneedsatleastcodesymbolstoberepresented.Whenusedual-codesymboltocode,r＝2，then：Conclusion：whenuseequallengthdual-code,thelimitcodelengthofeachsourcesymbolislog/logqr1loglog()NlqlqbitNlog()qbitloglogNllqqrNrloglogqlrExample5.2.2Unfixedlength(Variablelength)sourcecodingSeveralconceptsofcodetype(Eg.2.4.2)Non-singularcodeandsingularcodeUniquelydecodablecodePrefixcode（instantaneouscode,non-delaycode）KrafttheoremUnfixedlengthcodingtheorem（ShannonFirstTheorem）Krafttheoremquestion：findreal-time,uniquelydecodablecodemethod：researchthecodepartitionconditionofthereal-timeuniquelydecodablecodeintroduction：conceptof“codetree”conclusion：presenttheconditionthatthereal-timeuniquelydecodablecode(prefixcode)exists,thatis,theKrafttheoremcodetreeThecorrespondingrelationshipbetweenVLCandcodetree：(1)Treeroot↔Startingpointofacodeword(2)Numberofbranchesfromatreenode↔Codedimension(3)Node↔Partofacodeword(4)Terminalnode↔Endofacodeword(5)Numberofbranches↔Codelength(6)Non-fullbranchtree↔Variablelengthcode(7)Fullbranchtree↔FixedlengthcodeBinarynon-fullbranchtreeBinaryfullbranchtreeTrinaryfullbranchtreeTheorem5.1(KraftInequality)AnecessaryandsufficientconditionfortheexistenceofabinaryprefixcodesetwhosecodewordshavelengthsisLnnn...21121Lknk000111CodetreemapforproofAveragelengthoftheprefixcodeAdiscretenon-memorystationarysourceItslimitsourceentropyisandthenumberofinputsymbolsetis.Thecodelengthofeachcodewordis,thentheaveragecodelengthofprefixcodeis)(SH11,...,...,...,iqiqSsSsSsSpppP,1,2,...,iliqql5.3.3Losslessunfixedlength(variablelength)sourcecodingtheorem1qiiillpLosslessunfixedlengthsourcecodingtheorem(ShannonFirstTheorem)Fordiscretenon-memorystationarysourceS,itslimitentropyisanditscodesignalsareX={x1,…,xr}.WecanalwayscodethesourceSbyusingacodingmethodtoconstructuniquelydecodablecode.Thustheaveragecodelengthofeachsourcesignalsatisfies:)(SH()()1loglogHsHslrrTheorem5.3(SourceCodingTheorem)LetXbethesetoflettersfromaDMSwithfiniteentropyH(X)andxk,k=1,2,…,Ltheoutputsymbols,occurringwithprobabilities.Giventheseparameters,itispossibletoconstructacodethatsatisfiestheprefixconditionandhasanaveragelengthRthatsatisfiesthefollowinginequalitykxP()()1HxRHxExample：discret