资源描述:
《j. j. rissanen generalized kraft inequality and arithmetic coding》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、J.J.RissanenGeneralizedKraftInequalityandArithmeticCodingAbstract:Algorithmsforencodinganddecodingfinitestringsoverafinitealphabetaredescribed.ThecodingoperationsarearithmeticinvolvingrationalnumbersliasparameterssuchthatZi2"i52".Thiscodingtechniquereq
2、uiresnoblocking,andtheper-symbollengthoftheencodedstringapproachestheassociatedentropywithinE.Thecodingspeediscomparabletothatofconventionalcodingmethods.IntroductionTheoptimalconventionalinstantaneousHuffmancodeThismeansthat,ifthestringsaregeneratedby
3、anin-[11foranindependentinformationsourcewithsymboldependentinformationsource,themeanofn"L(s)probabilities(p,,...,p,)maybeviewedasasolutiontoapproachestheentropyfunctionfromabovewithinantheintegerprogrammingproblem:Findmnaturalnum-errorE+O(1/n).berslia
4、slengthsofbinarycodewordssuchthatCipil,isThecodingoperationsarearithmetic,andtheyre-minimizedundertheconstrainingKraftinequalitysembletheconcatenationoperationsinconventionalcodinginthatthecodeofthestringsak,whereukisaI.newsymbol,isobtainedbyreplacingo
5、nlyafew(always1lessthansomefixednumber)oftheleft-mostbitsoftheThentheminimizedsumB,p,l,approximatestheShannon-coderepresentingsbyanewlongerstring.Asaresult,BoltzmannentropyfunctionH(p,,...,p,)=-zip,logthecodingoperationscanbeaccomplishedwithaspeedpifro
6、mabovewithanerrornomorethanone.Ifabettercomparabletothatofconventionalcoding.approximationisrequired,blockingisneeded;e.g.,akthTheprimaryadvantageoftheresulting"arithmeticextensionofthealphabetmustbeencoded,whichre-coding"isthatthereisnoblockingneedede
7、venfortheducestheleastupperboundoftheerrorto1/k[2].binaryalphabet.Inaddition,forsmallalphabetsizestheWedescribeanothercodingtechniqueinwhichmsizeoftablestobestoredandsearchedissmallerthanpositiverationalnumbersI,,...,1,areselectedsuchthecodewordtablesi
8、nconventionalcodingmethods.thatageneralizedKraftinequalityholds:ForabinaryalphabetaspecialchoiceofparametersI,andI,leadstoaparticularlysimplecodingtechnique2"i52-€,E>0.thatiscloselyrelatedtooneduetoFano[31.1Thecodingmethoddescribedherei