第七章：限失真編碼2(英文)

1、7.4: Limited loss source 7.4: Limited loss source encoding theoremencoding theorem1nLimited loss source encoding theoremnAuthentication nPractical significance7.4: Limited loss source 7.4: Limited loss source encoding theoremencoding theorem2nLimited loss source encoding theoremLimited loss source e

2、ncoding theoremnAssume R(D) is a distortion function of discrete non-memory steady source, and it has limited infidelity measure. For any D0，0，0 and any enough code length n，there will inevitably exist a kind of source encoding C，which code number is:M=expnR(D)+its average infidelity after encoding:

3、 d(C)D+if used dual encoding，the unit of R(D) is bit，then the previous expression M can be : M=2nR(D)+7.4: Limited loss source 7.4: Limited loss source encoding theoremencoding theorem3nExplanation：nFor any infidelity D0，if the code length n is enough，we can always find a kind of encoding C to make

4、the info. transmit rate of each source signal be after encoding: R=logM/n=R(D)+ namely: RR(D) its code average infidelity d(C)D。nWith permitted distortion D, the least and available info. transmit rate is R(D) of the source.7.4: Limited loss source 7.4: Limited loss source encoding theoremencoding t

5、heorem4nAuthentication nproblem：n設(shè)有達到設(shè)有達到R(D)的試驗信道的試驗信道p(v|u),要證明對于任意的要證明對于任意的RR(D)時，存在一種時，存在一種信息傳輸率為信息傳輸率為R的信源編碼，其平均失真度的信源編碼，其平均失真度D+ntrain of thought：n產(chǎn)生碼書產(chǎn)生碼書n選取編譯碼方法選取編譯碼方法n計算失真度計算失真度nmethod：n產(chǎn)生碼書：在產(chǎn)生碼書：在Vn空間隨機抽取空間隨機抽取M=2nR個隨機序列個隨機序列vn編碼方法：若存在與信源序列編碼方法：若存在與信源序列u構(gòu)成構(gòu)成失真典型序列失真典型序列對的序列對的序列v(),則編碼則編碼

6、uv(),否則編碼否則編碼uv(1)n譯碼：再現(xiàn)譯碼：再現(xiàn)v()n失真度計算：在所有隨機碼書和失真度計算：在所有隨機碼書和Un空間統(tǒng)計平均的基礎(chǔ)上計算平均失真度空間統(tǒng)計平均的基礎(chǔ)上計算平均失真度7.4: Limited loss source 7.4: Limited loss source encoding theoremencoding theorem5nSeveral statementsnIt is only a existence theorem, doesnt has construct methods.nProblem existed：nIt is difficult to ca

7、lculate the function R(D) of practical sourcenIt is difficult to get accurate mathematic description of the source statistic characteristicsnIt is difficult to get the infidelity measure of the practical sourcenR(D) itself is difficult to calculatenEven if we have got R(D)，we still research the best

8、 encoding method to get the limit value of R(D).7.4: Limited loss source 7.4: Limited loss source encoding theoremencoding theorem6nPractical significancenHow to encoding？nExample：nPractical significance of R（D）nSource function R(D) can be a kind of scale to measure various compressed encoding metho

9、ds with certain permitted distortion. nexample：nBinary symmetric source without memorynCompiled code：2121,1 , 0)(upU111101110111011100001000100010001 ,02876514321)( vuuuuvuuuuUYCVUUf譯碼實際信道無噪無損信道傳輸0000 1111Example: conclusionnR=1/3（bit/source signal）nInfo. transmit rate with this compressed encoding

10、methodnd(C)=1/4nAverage distortion with this compressed encoding methodnR(1/4)=1-H(1/4)=0.189(bit/source signal ）nWith the 1/4 infidelity ，the least info. transmit rate R is 0.189(bit/source signal ）nR(1/4)RnWith the 1/4 infidelity, this compressed encoding method is not the best or the source can b

11、e further compressed.7.5: Relation and compare of the 7.5: Relation and compare of the three Shannon theoremsthree Shannon theorems1無失真信源編碼定理無失真信源編碼定理限失真信源編碼定理限失真信源編碼定理信源冗余度壓縮編碼信源的熵壓縮編碼無失真、保熵有失真、熵壓縮信源壓縮的極限值：信源熵H(S)信源壓縮的極限值：率失真函數(shù)R(D)存在性、構(gòu)造性存在性定理7.4: Relation and compare of the 7.4: Relation and compa

12、re of the three Shannon theoremsthree Shannon theorems2信道編碼定理信道編碼定理限失真信源編碼定理限失真信源編碼定理給定信道特性p=p(y|x)給定信源p=p(u)及失真測度d(u,v)對于假設(shè)的信源p=p(x)對于假設(shè)的試驗信道p=p(v|u)尋求最優(yōu)的信道編碼C2尋求最優(yōu)的限失真編碼C3產(chǎn)生的誤碼率pe產(chǎn)生的最大失真D信道編碼存在的條件RR(D)信道容量公式率失真函數(shù)公式存在符合條件的C2,使pe0存在符合條件的C3，使DQuantifyIt include scalar quantity and vector quantify. No

13、w we focus on the scalar quantity quantify.1 Application scope：continuous non-memory source2 Concept：continuous signal be quantified to K possible discrete values example：A/D gather boardQuantifyuconcept of quantifyuQuantify in A/DuFig. of quantify processuAn example of quantify Quantification proce

14、ssing is a powerful measure to drop the data bit rate . The dynamic range of quantification input value is huge, thus needs multi-bit to express one value. The quantification output only can take the limited integer, called the quantization step. Each quantification input is forced to turn to the cl

15、ose output, namely be quantified to some level. Quantification processing always quantified a batch of inputs to one output stage, therefore the quantification is a many-to -one treating processes. In the quantification processing information may be lost, that is, may lead to quantification error (q

16、uantification noise). The process of the simulation quantity obtaining the binary code after A/D transformation is the pulse code modulation (PCM), also called PCM encoding. The sampling and the quantification of A/D transformation are individually process of digitizing the time and the simulation q

17、uantity the process.Quantifyuconcept of quantifyuQuantify in A/DuFig. of quantify processuAn example of quantify輸入輸入輸出輸出閾值閾值代表級代表級量化曲線量化曲線Quantifyuconcept of quantifyuQuantify in A/DuFig. of quantify processuAn example of quantify 24位標準圖像 8位（256色）標準圖像Quantifyuconcept of quantifyuQuantify in A/DuFig.

18、 of quantify processuAn example of quantifyBasic principle of prediction encoding method Considering the strong relevant characteristics between the neighboring data, we may use the value which already appeared to carry on the prediction (estimate), obtained a prediction value, then subtract the act

19、ual value and the prediction value, encode and transmit the difference signal, this encode method is called predictive coding method.Prediction encodingBest prediction code：en=yn-un is the smallest.Have three different criterions: Smallest mean error; Smallest mean absolute error; Biggest zero error

20、 probability N.DPCM basic principle轉(zhuǎn)入f(i,j)e(i,j)量化器預(yù)測器預(yù)測器編碼器解碼器信道傳輸e(i,j)f(i,j)輸出f(i,j)f(i,j)f(i,j)f(i,j)DPCM編、解碼原理圖Prediction encoding The DPCM linear prediction coding which does not have the quantizer belongs to the lossless coding system; The DPCM linear prediction coding has the quantizer belo

21、ngs to the distortion coding system. DPCM linear prediction coding system is a negative feedback system and it has astringency to the error. Between the transmitting end and the receiving end, error was equal to the quantification error. To design best quantizer, may use the physiological characteri

22、stics such as the eye visual visibility threshold value and visual masking effect to determine the step and distance of the quantizer, this will cause the quantification error always be in the scope which the person eye perceived with difficulty, and achieved the subjectively evaluating criterion. B

23、est quantifyPrediction codingADPCM The concept of auto-adapted technology is: the prediction coefficient and the quantizer quantification parameter of the predictor can automatically adjust according to the characteristic of the picture partial region distribution. Practice proved that compares ADPC

24、M encoding and decoding system with those of DPCM, the ADPCM not only can improve the evaluation quality and the visual effect of restoring the picture, but also can further compress the data. ADPCM system including the adaptive prediction, namely the auto-adapted adjustment and the auto-adapted qua

25、ntification of the prediction coefficient, that is, the two parts of contents quantizer parameter auto-adapted adjusts.Prediction codingPrinciple of changeable codingnDef.： Mapping transforms the air zone picture signal to another orthogonal vectors space (transformation territory or frequency range

26、), produce one batch of transformation ratios, code the coefficient.nPrinciples：nInformation redundancy of the signal when time domain description is big, after the transformation, the parameter is independent, removes the relevance, reduces the redundancy, the data quantity will deeply reduce.nTaki

27、ng advantage of persons visual characteristic, that is, it is insensitive to the high frequency detail, we may filter the high frequency coefficient and reserve the low frequency coefficient.Explanation of transformation principle in mathematicsWhen time domain description the information redundancy

28、 of the signal is big, after the transformation, the parameter is independent, the data quantity reduces.The spatial transformation is seeking a group of new standard to get coefficient of the original vector in the new orthogonal cardinal numbers Taking advantage of persons visual characteristic, t

29、hat is, it is insensitive to the high frequency detail, we may filter the high frequency coefficient and reserve the low frequency coefficient .approaches the original vector with limited dimensions linear combination, the projection theorem.Best orthogonal transformation: K-L transformationX1X2Y1Y2

30、Getting the joint variance matrix of the correlation vector should according to size arrangement characteristic vector of the characteristic value. In the transformation territory the energy concentrates in the minority several transformation ratio (coefficient of in characteristic vector which has

31、big characteristic value), then coding efficiency will be the highest and the error will be the smallest.K-L變換圖示變換圖示3） Several indexes that the scalar quantity quantify concerning P243Info. Rate: RKAverage distortion: DKThe biggest output rate of the quantifier: Mk=log2kObviously: for different TK and qk, the quantification will has various RK，DK，MKTK: Thres