第七章：限失真編碼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：設(shè)有達(dá)到R(D)的試驗(yàn)信道p(v|u),要證明對(duì)于任意的R‘>R(D)時(shí)，存在一種信息傳輸率為R’的信源編碼，其平均失真度≤D+δtrainofthought：產(chǎn)生碼書(shū)選取編譯碼方法計(jì)算失真度method：產(chǎn)生碼書(shū)：在Vn空間隨機(jī)抽取M=2nR’個(gè)隨機(jī)序列v編碼方法：若存在與信源序列u構(gòu)成失真典型序列對(duì)的序列v(ω),則編碼uv(ω),否則編碼uv(1)譯碼：再現(xiàn)v(ω)失真度計(jì)算：在所有隨機(jī)碼書(shū)和Un空間統(tǒng)計(jì)平均的基礎(chǔ)上計(jì)算平均失真度§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：無(wú)噪無(wú)損信道傳輸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

無(wú)失真信源編碼定理限失真信源編碼定理信源冗余度壓縮編碼信源的熵壓縮編碼無(wú)失真、保熵有失真、熵壓縮信源壓縮的極限值：信源熵H(S)信源壓縮的極限值：率失真函數(shù)R(D)存在性、構(gòu)造性存在性定理§7.4:RelationandcompareofthethreeShannontheorems－2

信道編碼定理限失真信源編碼定理給定信道特性p=p(y|x)給定信源p=p(u)及失真測(cè)度d(u,v)對(duì)于假設(shè)的信源p=p(x)對(duì)于假設(shè)的試驗(yàn)信道p=p(v|u)尋求最優(yōu)的信道編碼C2尋求最優(yōu)的限失真編碼C3產(chǎn)生的誤碼率pe產(chǎn)生的最大失真D信道編碼存在的條件R<C限失真信源編碼存在的條件R>R(D)信道容量公式率失真函數(shù)公式存在符合條件的C2,使pe0存在符合條件的C3，使D’<DEntropycompressencodingEmphasizethreetypicalmethod:1）quantify,scalarquantityquantify,vectorquantify2）transformationencoding3）predictionencodingGenerally,wecallvectorquantifyandtransformationencodingtheentropycompressedgroupencoding,andcallpredictionencodingtheentropycompressedtreecode.Astheprevioussaying,withpermittedcertainDtocompresstheentropyrateleast,namely,maketheratedistortionfunctionleast.Dmin123RD1為直接矢量量化；2為先作變換，再L-M算法；３對(duì)其各分量直接用L-M算法結(jié)論：矢量量化是熵壓縮分組編碼的最有效方法如圖①>②>③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輸入輸出閾值代表級(jí)量化曲線(xiàn)QuantifyconceptofquantifyQuantifyinA/DFig.ofquantifyprocessAnexampleofquantify24位標(biāo)準(zhǔn)圖像8位（256色）標(biāo)準(zhǔn)圖像QuantifyconceptofquantifyQuantifyinA/DFig.ofquantifyprocessAnexampleofquantifyBasicprincipleofpredictionencodingmethod

Consideringthestrongrelevantcharacteristicsbetweentheneighboringdata,wemayusethevaluewhichalreadyappearedtocarryontheprediction(estimate),obtainedapredictionvalue,thensubtracttheactualvalueandthepredictionvalue,encodeandtransmitthedifferencesignal,thisencodemethodiscalledpredictivecodingmethod.PredictionencodingBestpredictioncode：en=yn-unisthesmallest.Havethreedifferentcriterions:Smallestmeanerror;Smallestmeanabsoluteerror;BiggestzeroerrorprobabilityN.DPCMbasicprinciple轉(zhuǎn)入f(i,j)e(i,j)量化器預(yù)測(cè)器預(yù)測(cè)器編碼器解碼器信道傳輸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個(gè)）qk:levelvalue（k個(gè)）4）

evenquantifyConcept：equalq