第七章：限失真编码2(英文)

§7.4:Limitedlosssourceencodingtheorem－1LimitedlosssourceencodingtheoremAuthenticationPracticalsignificance§7.4:Limitedlosssourceencodingtheorem－2LimitedlosssourceencodingtheoremAssumeR(D)isadistortionfunctionofdiscretenon-memorysteadysource,andithaslimitedinfidelitymeasure.ForanyD≥0，ε＞0，δ＞0andanyenoughcodelengthn，therewillinevitablyexistakindofsourceencodingC，whichcodenumberis:M=exp{n［R(D)+ε］}itsaverageinfidelityafterencoding:d(C)≤D+δifuseddualencoding，theunitofR(D)isbit，thenthepreviousexpressionMcanbe:M=2{n［R(D)+ε］}§7.4:Limitedlosssourceencodingtheorem－3Explanation：ForanyinfidelityD≥0，ifthecodelengthnisenough，wecanalwaysfindakindofencodingCtomaketheinfo.transmitrateofeachsourcesignalbeafterencoding:R′=logM/n=R(D)+εnamely:R′≥R(D)itscodeaverageinfidelityd(C)≤D。WithpermitteddistortionD,theleastandavailableinfo.transmitrateisR(D)ofthesource.§7.4:Limitedlosssourceencodingtheorem－4Authenticationproblem：设有达到R(D)的试验信道p(v|u),要证明对于任意的R‘>R(D)时，存在一种信息传输率为R’的信源编码，其平均失真度≤D+δtrainofthought：产生码书选取编译码方法计算失真度method：产生码书：在Vn空间随机抽取M=2nR’个随机序列v编码方法：若存在与信源序列u构成失真典型序列对的序列v(ω),则编码uv(ω),否则编码uv(1)译码：再现v(ω)失真度计算：在所有随机码书和Un空间统计平均的基础上计算平均失真度§7.4:Limitedlosssourceencodingtheorem－5SeveralstatementsItisonlyaexistencetheorem,doesn'thasconstructmethods.Problemexisted：ItisdifficulttocalculatethefunctionR(D)ofpracticalsourceItisdifficulttogetaccuratemathematicdescriptionofthesourcestatisticcharacteristicsItisdifficulttogettheinfidelitymeasureofthepracticalsourceR(D)itselfisdifficulttocalculateEvenifwehavegotR(D)，westillresearchthebestencodingmethodtogetthelimitvalueofR(D).§7.4:Limitedlosssourceencodingtheorem－6PracticalsignificanceHowtoencoding？Example：PracticalsignificanceofR（D）SourcefunctionR(D)canbeakindofscaletomeasurevariouscompressedencodingmethodswithcertainpermitteddistortion.

example：BinarysymmetricsourcewithoutmemoryCompiledcode：无噪无损信道传输Example:conclusion

R’=1/3（bit/sourcesignal）Info.transmitratewiththiscompressedencodingmethodd(C)=1/4AveragedistortionwiththiscompressedencodingmethodR(1/4)=1-H(1/4)=0.189(bit/sourcesignal）Withthe1/4infidelity，theleastinfo.transmitrateRis0.189(bit/sourcesignal）R(1/4)<R’Withthe1/4infidelity,thiscompressedencodingmethodisnotthebestorthesourcecanbefurthercompressed.§7.5:RelationandcompareofthethreeShannontheorems－1

无失真信源编码定理限失真信源编码定理信源冗余度压缩编码信源的熵压缩编码无失真、保熵有失真、熵压缩信源压缩的极限值：信源熵H(S)信源压缩的极限值：率失真函数R(D)存在性、构造性存在性定理§7.4:RelationandcompareofthethreeShannontheorems－2

信道编码定理限失真信源编码定理给定信道特性p=p(y|x)给定信源p=p(u)及失真测度d(u,v)对于假设的信源p=p(x)对于假设的试验信道p=p(v|u)寻求最优的信道编码C2寻求最优的限失真编码C3产生的误码率pe产生的最大失真D信道编码存在的条件R<C限失真信源编码存在的条件R>R(D)信道容量公式率失真函数公式存在符合条件的C2,使pe0存在符合条件的C3，使D’<DEntropycompressencodingEmphasizethreetypicalmethod:1）quantify,scalarquantityquantify,vectorquantify2）transformationencoding3）predictionencodingGenerally,wecallvectorquantifyandtransformationencodingtheentropycompressedgroupencoding,andcallpredictionencodingtheentropycompressedtreecode.Astheprevioussaying,withpermittedcertainDtocompresstheentropyrateleast,namely,maketheratedistortionfunctionleast.Dmin123RD1为直接矢量量化；2为先作变换，再L-M算法；３对其各分量直接用L-M算法结论：矢量量化是熵压缩分组编码的最有效方法如图①>②>③QuantifyItincludescalarquantityandvectorquantify.Nowwefocusonthescalarquantityquantify.1

Applicationscope：continuousnon-memorysource2

Concept：continuoussignalbequantifiedtoKpossiblediscretevalues

example：A/DgatherboardQuantifyconceptofquantifyQuantifyinA/DFig.ofquantifyprocessAnexampleofquantify

Quantificationprocessingisapowerfulmeasuretodropthedatabitrate.Thedynamicrangeofquantificationinputvalueishuge,thusneedsmulti-bittoexpressonevalue.Thequantificationoutputonlycantakethelimitedinteger,calledthequantizationstep.Eachquantificationinputisforcedtoturntothecloseoutput,namelybequantifiedtosomelevel.

Quantificationprocessingalwaysquantifiedabatchofinputstooneoutputstage,thereforethequantificationisamany-to-onetreatingprocesses.Inthequantificationprocessinginformationmaybelost,thatis,mayleadtoquantificationerror(quantificationnoise).

Theprocessofthesimulationquantityobtainingthebinarycode

afterA/Dtransformationisthepulsecodemodulation(PCM),alsocalledPCMencoding.

ThesamplingandthequantificationofA/Dtransformationareindividuallyprocessofdigitizingthetimeandthesimulationquantitytheprocess.QuantifyconceptofquantifyQuantifyinA/DFig.ofquantifyprocessAnexampleofquantify输入输出阈值代表级量化曲线QuantifyconceptofquantifyQuantifyinA/DFig.ofquantifyprocessAnexampleofquantify24位标准图像8位（256色）标准图像QuantifyconceptofquantifyQuantifyinA/DFig.ofquantifyprocessAnexampleofquantifyBasicprincipleofpredictionencodingmethod

Consideringthestrongrelevantcharacteristicsbetweentheneighboringdata,wemayusethevaluewhichalreadyappearedtocarryontheprediction(estimate),obtainedapredictionvalue,thensubtracttheactualvalueandthepredictionvalue,encodeandtransmitthedifferencesignal,thisencodemethodiscalledpredictivecodingmethod.PredictionencodingBestpredictioncode：en=yn-unisthesmallest.Havethreedifferentcriterions:Smallestmeanerror;Smallestmeanabsoluteerror;BiggestzeroerrorprobabilityN.DPCMbasicprinciple转入f(i,j)e(i,j)量化器预测器预测器编码器解码器信道传输e’(i,j)f’(i,j)输出f(i,j)f’(i,j)f’(i,j)f(i,j)DPCM编、解码原理图Predictionencoding

TheDPCMlinearpredictioncoding

which

doesnothavethequantizerbelongstothelosslesscodingsystem;TheDPCMlinearpredictioncodinghasthequantizerbelongstothedistortioncodingsystem.

DPCMlinearpredictioncodingsystemisanegativefeedbacksystemandithasastringencytotheerror.Betweenthetransmittingendandthereceivingend,errorwasequaltothequantificationerror.Todesignbestquantizer,mayusethephysiologicalcharacteristicssuchastheeyevisualvisibilitythresholdvalueandvisualmaskingeffecttodeterminethestepanddistanceofthequantizer,thiswillcausethequantificationerroralwaysbeinthescopewhichthepersoneyeperceivedwithdifficulty,andachievedthesubjectivelyevaluatingcriterion.

BestquantifyPredictioncodingADPCM

Theconceptofauto-adaptedtechnologyis:thepredictioncoefficientandthequantizerquantificationparameterofthepredictorcanautomaticallyadjustaccordingtothecharacteristicofthepicturepartialregiondistribution.

PracticeprovedthatcomparesADPCMencodinganddecodingsystemwiththoseofDPCM,theADPCMnotonlycanimprovetheevaluationqualityandthevisualeffectofrestoringthepicture,butalsocanfurthercompressthedata.

ADPCMsystemincludingtheadaptiveprediction,namelytheauto-adaptedadjustmentandtheauto-adaptedquantificationofthepredictioncoefficient,thatis,thetwopartsofcontentsquantizerparameterauto-adaptedadjusts.PredictioncodingPrincipleofchangeablecodingDef.：Mappingtransformstheairzonepicturesignaltoanotherorthogonalvectorsspace(transformationterritoryorfrequencyrange),produceonebatchoftransformationratios,codethecoefficient.Principles：Informationredundancyofthesignalwhentimedomaindescriptionisbig,afterthetransformation,theparameterisindependent,removestherelevance,reducestheredundancy,thedataquantitywilldeeplyreduce.Takingadvantageofperson'svisualcharacteristic,thatis,itisinsensitivetothehighfrequencydetail,wemayfilterthehighfrequencycoefficientandreservethelowfrequencycoefficient.

ExplanationoftransformationprincipleinmathematicsWhentimedomaindescriptiontheinformationredundancyofthesignalisbig,afterthetransformation,theparameterisindependent,thedataquantityreduces.ThespatialtransformationisseekingagroupofnewstandardtogetcoefficientoftheoriginalvectorintheneworthogonalcardinalnumbersTakingadvantageofperson'svisualcharacteristic,thatis,itisinsensitivetothehighfrequencydetail,wemayfilterthehighfrequencycoefficientandreservethelowfrequencycoefficient.approachestheoriginalvectorwithlimiteddimensionslinearcombination,theprojectiontheorem.Bestorthogonaltransformation:K-LtransformationX1X2Y1Y2Gettingthejointvariancematrixofthecorrelationvectorshouldaccordingtosizearrangementcharacteristicvectorofthecharacteristicvalue.Inthetransformationterritorytheenergyconcentratesintheminorityseveraltransformationratio(coefficientofincharacteristicvectorwhichhasbigcharacteristicvalue),thencodingefficiencywillbethehighestandtheerrorwillbethesmallest.K-L变换图示3）SeveralindexesthatthescalarquantityquantifyconcerningP243Info.Rate:RKAveragedistortion:DKThebiggestoutputrateofthequantifier:Mk=log2kObviously:fordifferent{TK}and{qk},thequantificationwillhasvariousRK，DK，MKTK:Threshold

level（k+1个）qk:levelvalue（k个）4）

evenquantifyConcept：equalq