l07 data compression

《l07 data compression》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学内容应用信息论基础IntroductionandPreviewEntropyRelativeEntropyandMutualInformationEntropy,RelativeEntropy,andMutualInformation金明录教授AsymptoticEquipartitionPropertyEntropyRatesofaStochasticProcessEntropyRatesofaStochasticProcessDataCompressionChannelCapacityDifferentialEntropy

2、GaussianChannelRateDistortionTheoryNetworkInformationTheory12-13学年第二学期DUT应用信息论基础金明录教授DUT应用信息论基础金明录教授ContentsReviewSourceCodingSourceCodingTreeofCodeSummaryofSourceCodingTheoremKftiKraftinequalitlity1、FixedlengthWhatWeCannotDo:FundamentalLimitationsofSCSourceCoddiing2、V

3、ariablelengthVariablelengthSummaryofSourceCodingTheoremEfficiencyofCodesWhatWeCanDo:AnalysisofSomeGoodCodesWhatWeCanDo:AnalysisofSomeGoodCodesSummaryDUT应用信息论基础金明录教授DUT应用信息论基础金明录教授等长编码等长信源编码定理任何一个离散随机序列信源当序列长度N→∝时,信源序列会产编码器S{s,s,,s}C{w1,w2,,wq}生两极分化.大概率事件集合G与小概率事件集合G,即

4、qN=G∪G12qNNNNPG()1;PG()()NX{x1,x2,,xD}NN信源序列集合qNHS(())NHS(())2(PSS,,,S)212N单符号信源siwi(xi1,xi2,,xiL)(1)2NHS(())G2NHS(())GNNLqDGN[H(S)]N2N[logqH(s)]单个符号L长2NNLqq共有q个共有D个GN等长信源编码定理N次扩展信源(,,,)(,,,)L能无失真编码L不能无失真编码isi1si2siNWixi1xi

5、2xiLHD(X)HD(X)2N译码概率趋于0N译码概率趋于1编码效率NLL长2qDN长HD(X)NHD(X)NDI(XN)共有qN个共有DL个(N/L)LH2X2()1DUT应用信息论基础金明录教授DUT应用信息论基础金明录教授变长信源编码定理变长信源编码定理无失真变长信源编码定理(香农第一定理)物理意义：又称无噪信道编码定理离散无记忆平稳信源S，其熵率为H(X)，并有码符号编码后的码符号信源尽可能为等概分布，使每个码符号X={x1,…,xD}。对信源S进行编码,总可以找到一种编码方法

6、，平均所含的信息量达到最大构成唯一可译码，使信源S中每个信源符号所需的平均码长要做到无失真编码，变换每个信源符号平均所需最少的满足:D元码元数就是信源的熵率H(X)LlogD信源的熵率是描述信源每个符号平均所需最少的比特数定理说明：是存在性定理－－具有理论指导意义另一方面,必可以找到前缀码，使其平均码长满足是构造性定理－－设计出多种具体编码方法H(X)L1logDDUT应用信息论基础金明录教授DUT应用信息论基础金明录教授EfficiencyofCodesDefinition:Theefficiencyofaprefixcode

7、isdefinedasHD(X)H(X)LLlogDEfficiencyofCodes物理意义：编码前平均每个信源符号携带的信息量为：H(X)编码后平均每个信源符号携带的最大的信息量为：LlogD所以编码效率表示符号利用效率。DUT应用信息论基础金明录教授DUT应用信息论基础金明录教授EfficiencyofCodesEfficiencyofCodesExtensionofthesource：xiP(x)codeExample:DMSiXxxx1x19/160X1231x1x23/1610p44x2x13/1

8、6110then：L27134216x2x21/16111EntropyH(X)4log44log30.811Foreverys