限失真信源編碼定理－1

7.4:限失真信源編碼定理1,限失真信源編碼定理限失真信源編碼定理的證明限失真信源編碼定理的實(shí)用意義,7.4:限失真信源編碼定理2,限失真信源編碼定理設(shè)R(D)為一離散無記憶平穩(wěn)信源的信息率失真函數(shù)，并且有有限的失真測度。對(duì)于任意D0，0，0以及任意足夠長的碼長n，則一定存在一種信源編碼C，其碼字個(gè)數(shù)為:M=expnR(D)+而編碼后碼的平均失真度: d(C)D+如果用二元編碼，R(D)取比特為單位，則上式M可寫成: M=2nR(D)+,7.4:限失真信源編碼定理3,定理解釋：對(duì)于任何失真度D0，只要碼長n足夠長，總可以找到一種編碼C，使編碼后每個(gè)信源符號(hào)的信息傳輸率: R=logM/n=R(D)+ 即: RR(D) 而碼的平均失真度d(C)D。在允許失真D的條件下，信源最小的、可達(dá)的信息傳輸率是信源的R(D)。,7.4:限失真信源編碼定理4,限失真信源編碼定理的證明問題：設(shè)有達(dá)到R(D)的試驗(yàn)信道p(v|u),要證明對(duì)于任意的RR(D)時(shí)，存在一種信息傳輸率為R的信源編碼，其平均失真度D+思路：產(chǎn)生碼書選取編譯碼方法計(jì)算失真度方法：產(chǎn)生碼書：在Vn空間隨機(jī)抽取M=2nR個(gè)隨機(jī)序列v編碼方法：若存在與信源序列u構(gòu)成失真典型序列對(duì)的序列v(),則編碼uv(),否則編碼uv(1)譯碼：再現(xiàn)v()失真度計(jì)算：在所有隨機(jī)碼書和Un空間統(tǒng)計(jì)平均的基礎(chǔ)上計(jì)算平均失真度,7.4:限失真信源編碼定理5,限失真信源編碼定理的幾點(diǎn)說明只是一個(gè)存在性定理，沒有構(gòu)造方法存在問題：符合實(shí)際信源的R(D)函數(shù)計(jì)算相當(dāng)困難信源統(tǒng)計(jì)特性的確切數(shù)學(xué)描述難得符合主客觀實(shí)際的失真測度難得R(D)計(jì)算本身困難即使求得了R(D)，還需研究最佳編碼方法才能達(dá)到極限值R(D)。,7.4:限失真信源編碼定理6,限失真信源編碼定理的實(shí)用意義如何進(jìn)行限失真信源編碼？舉例：R（D）的實(shí)用意義在允許一定失真的情況下，信源的R(D)函數(shù)可以作為衡量各種壓縮編碼方法性能優(yōu)劣的一種尺度。,舉例：二進(jìn)制無記憶對(duì)稱信源編譯碼：,無噪無損信道傳輸,舉例：結(jié)論,R=1/3（比特/信源符號(hào)）該壓縮編碼方法下的信息傳輸率d(C)=1/4該壓縮編碼方法下的平均失真R(1/4)=1-H(1/4)=0.189(比特/信源符號(hào)）失真1/4下，最小的信息傳輸率R是0.189(比特/信源符號(hào)）R(1/4),量化,它包括標(biāo)量和矢量兩種，這是重點(diǎn)講標(biāo)量量化1 標(biāo)量量化適用范圍：連續(xù)無記憶信源2標(biāo)量量化的概念：連續(xù)信號(hào)量化K個(gè)若干可能離散值 舉例：A/D采集版,量化,量化概念A(yù)/D中的量化量化過程示意圖一個(gè)量化實(shí)例,量化處理是使數(shù)據(jù)比特率下降的一個(gè)強(qiáng)有力的措施。 量化輸入值動(dòng)態(tài)范圍很大，需要以多比特?cái)?shù)表示一個(gè)數(shù)值，量化輸出只能取有限個(gè)整數(shù)，稱量化級(jí)。每個(gè)量化輸入被強(qiáng)迫歸一到與其接近的某個(gè)輸出，即量化到某個(gè)級(jí)。量化處理總是把一批輸入量化到一個(gè)輸出級(jí)上，所以量化是個(gè)多對(duì)一的處理過程，量化中由信息丟失，或者說，會(huì)引起量化誤差（量化噪聲）。,模擬量經(jīng)過A/D轉(zhuǎn)換，得到二進(jìn)制碼的過程，就是脈沖編碼調(diào)制（PCM）編碼過程，也稱PCM編碼。 A/D轉(zhuǎn)換中的采樣和量化分別是對(duì)時(shí)間和模擬量進(jìn)行數(shù)字化的過程。,量化,量化概念A(yù)/D中的量化量化過程示意圖一個(gè)量化實(shí)例,輸入,輸出,量化曲線,量化,量化概念A(yù)/D中的量化量化過程示意圖一個(gè)量化實(shí)例,24位標(biāo)準(zhǔn)圖像 8位（256色）標(biāo)準(zhǔn)圖像,量化,量化概念A(yù)/D中的量化量化過程示意圖一個(gè)量化實(shí)例,預(yù)測編碼方法基本原理,從相鄰數(shù)據(jù)之間有很強(qiáng)的相關(guān)性特點(diǎn)考慮，可以利用前面已經(jīng)出現(xiàn)的數(shù)值，進(jìn)行預(yù)測（估計(jì)），得到一個(gè)預(yù)測值，將實(shí)際值與預(yù)測值求差，對(duì)這個(gè)差值信號(hào)進(jìn)行編碼、傳送，這種編碼方法即成為預(yù)測編碼方法。,預(yù)測編碼,最佳的預(yù)測編碼：en=yn-un 最小有三種不同的標(biāo)準(zhǔn)：最小均方誤差；最小平均絕對(duì)誤差；最大零誤差概率；,DPCM基本原理,DPCM編、解碼原理圖,預(yù)測編碼,不帶量化器的DPCM線性預(yù)測編碼，屬于無失真編碼系統(tǒng)；帶有量化器的DPCM線性預(yù)測編碼，屬于有失真編碼系統(tǒng)。 DPCM線性預(yù)測系統(tǒng)是一個(gè)負(fù)反饋系統(tǒng)，對(duì)誤差有收斂性。發(fā)送端與接收端之間的誤差等于量化誤差。 最佳量化器的設(shè)計(jì)，可利用人眼的視覺可見度閾值和視覺掩蔽效應(yīng)等生理特征，來確定量化器的級(jí)數(shù)和步距，使量化誤差總處于人眼難以覺察的范圍內(nèi)，達(dá)到主觀評(píng)定準(zhǔn)則的要求。,最佳量化,預(yù)測編碼,自適應(yīng)預(yù)測編碼ADPCM,自適應(yīng)技術(shù)的概念是：預(yù)測器的預(yù)測系數(shù)和量化器的量化參數(shù)，能夠根據(jù)圖像的局部區(qū)域分布特點(diǎn)自動(dòng)調(diào)整。 實(shí)踐證明，ADPCM編、解碼系統(tǒng)與DPCM編、解碼系統(tǒng)相比，不僅能改善恢復(fù)圖像的評(píng)測質(zhì)量和視覺效果，同時(shí)還能進(jìn)一步壓縮數(shù)據(jù)。 ADPCM系統(tǒng)包括自適應(yīng)預(yù)測，即預(yù)測系數(shù)的自適應(yīng)調(diào)整和自適應(yīng)量化，即量化器參數(shù)的自適應(yīng)調(diào)整兩部分內(nèi)容。,預(yù)測編碼,變換編碼原理,定義：將空域圖像信號(hào)映射變換到另一個(gè)正交矢量空間（變換域或頻域），產(chǎn)生一批變換系數(shù)，對(duì)系數(shù)進(jìn)行編碼處理原理：信號(hào)在時(shí)域描述時(shí)信息冗余度大，變換后，參數(shù)獨(dú)立，去掉相關(guān)性，減少冗余，數(shù)據(jù)量大大減少。利用人的視覺特性，對(duì)高頻細(xì)節(jié)不敏感，可以濾除高頻系數(shù)，保留低頻系數(shù)。,變換原理在數(shù)學(xué)上的解釋,信號(hào)在時(shí)域描述時(shí)信息冗余度大，變換后，參數(shù)獨(dú)立，數(shù)據(jù)量減少?？臻g內(nèi)的變換就是尋找一組新的規(guī)范正交基，求去原向量在新的正交基上的系數(shù)。,利用人的視覺特性，對(duì)高頻細(xì)節(jié)不敏感，可以濾除高頻系數(shù)，保留低頻系數(shù)。用有限維線性組合去逼近原向量，投影定理。,最佳正交變換K-L變換,X1,X2,對(duì)相關(guān)向量求協(xié)方差矩陣，按照特征值的大小排列特征向量。變換域中能量集中到少數(shù)幾個(gè)變換系數(shù)上（特征值大的特征向量上的系數(shù)），編碼效率最高，誤差最小。,K-L變換圖示,3） 標(biāo)量量化涉及幾個(gè)性解指標(biāo) P243信息速率RK平均失真DK量化器輸出最大速率Mk=log2k顯然：取不同的TK和qk,量化將有不同的RK，DK，MKTK:門限電平（k+1個(gè)）qk:電平值 （k個(gè)）,4） 均勻量化概念：量化間隔相等最優(yōu)均勻量化：使DK達(dá)到最小均勻量化 例：對(duì)高斯信源 即:Rk=1/4+1/2log(Pu/Dk)問題：均勻量化不是DK最小的一個(gè)、提出一種Uoyd-Max算法,5）Lioyd-Max算法思想：反復(fù)對(duì)TK、qk在使DK最小的兩個(gè)必要條件進(jìn)行迭代（必要條件為：P235） Tk-1=1/2(qk-1+qk) (u- qk)p(u)du=0 則求