信息率失真函數(shù)與限失真信源編碼

信息率失真函數(shù)與限失真信源編碼第一頁，共五十七頁，2022年，8月28日本章研究內(nèi)容概述失真的度量信息率失真函數(shù)限失真信源編碼定理限失真信源編碼定理應(yīng)用實用型信源編碼香農(nóng)三大定理的關(guān)系和比較第二頁，共五十七頁，2022年，8月28日§7.1:概述－1無噪信道編碼定理回顧：總可以找到一種輸入分布（信源編碼方法），使在無噪無損信道上，能夠以信道容量C無誤地傳輸信息。信源編碼無噪無損信道R=C;PE=0,最佳分布消息壓縮冗余度最好地利用C限：平均碼長最小值Hr(S)每個碼符號平均能夠攜帶的最大信息量第三頁，共五十七頁，2022年，8月28日§7.1:概述－2有噪信道編碼定理回顧：只要R<C，總可以找到一種信道編碼方法，使在信道上能夠以盡可能小的PE傳輸信息。增加冗余度，最好地匹配信道特性限：信息傳輸率最大值C每個信道符號平均能夠攜帶的最大信息量信源編碼信道R<C;PE=ε,消息信道編碼第四頁，共五十七頁，2022年，8月28日§7.1:概述－3存在問題對于連續(xù)和模擬信源H(S)=∞信道傳輸率R=H(S)/n（比特/碼符號）R=

∞平均碼長l=Hr(S)=H(S)/logr,l=∞,實際上，因為B有限，C一定有限，R<C第五頁，共五十七頁，2022年，8月28日§7.1:概述－4實際需求特點：信宿對真實度的要求：實際語音信號：20Hz~8KHz

人耳能夠分辨：300Hz~3400Hz圖象色差：可達(dá)足夠多視覺分辨：256級（黑白）已足夠可以允許一定的失真度完全保真沒必要第六頁，共五十七頁，2022年，8月28日§7.1:概述－5引出的研究內(nèi)容限失真的信源編碼問題允許一定的失真度下，能將信源信息壓縮到什么程度？（最少需要多少比特才能在收端描述信源？）一定的信息傳輸率R下，可能達(dá)到的最小的平均失真是多少？相關(guān)問題失真如何度量？率失真函數(shù)如何計算？第七頁，共五十七頁，2022年，8月28日§7.1:概述－6方法：抽象：將與討論重點關(guān)系小的部分抽象因為涉及信源編碼，對信道進(jìn)行抽象信道編碼→信道→信道譯碼信道*研究失真影響時，“信道*”可以忽略根據(jù)信道編碼定理：信道*是一個沒有干擾的廣義信道，信宿收到信息的失真只來自于信源編碼第八頁，共五十七頁，2022年，8月28日§7.1:概述－7方法：虛擬：將討論重點虛擬細(xì)化將限失真信源的編譯碼過程虛擬信源編碼過程→信道*

→信源譯碼過程試驗信道可以用信道傳遞概率來描述限失真信源編譯碼前后的關(guān)系第九頁，共五十七頁，2022年，8月28日信源編碼信道編碼信道信道譯碼信源譯碼信源信宿信源編碼信道*信源譯碼信源信宿信源信宿試驗信道UVP(V|U)第十頁，共五十七頁，2022年，8月28日§7.2:失真的度量－1失真度定義平均失真度保真度準(zhǔn)則試驗信道第十一頁，共五十七頁，2022年，8月28日§7.2:失真的度量－2失真度定義在U,V聯(lián)合空間上定義：d（ui，vj），ui∈U，vj∈V

為U,V的失真測度。d（ui，vj）有距離的概念性質(zhì)1：ui=vj時，d=0性質(zhì)2：mind=0性質(zhì)3：0<d<∞第十二頁，共五十七頁，2022年，8月28日§7.2:失真的度量－3失真度定義

0,ui=vj

離散信源：用失真矩陣描述。dij=>0,ui≠

vj

0,ui=vj

漢明距離度量時：dij=1,ui≠

vj連續(xù)信源：用失真函數(shù)描述。d(u,v)=(u-v)2=|u-v|

第十三頁，共五十七頁，2022年，8月28日§7.2:失真的度量－4平均失真度單符號失真度：d（ui，vj）≥0，（i=1~r，j=1~s）信源的失真矩陣可表示為：共r×s個元素第十四頁，共五十七頁，2022年，8月28日§7.2:失真的度量－5平均失真度平均失真度：∵U，V是隨機變量；∴d（ui，vj）也是隨機變量平均失真度：

第十五頁，共五十七頁，2022年，8月28日§7.2:失真的度量－6平均失真度confer:d&d：描述了某個信源符號通過傳輸后失真的大小，不同的信源符號，其d不同。：描述了某一個單符號信源在某一試驗信道傳輸下的失真，它不僅與單個符號的d有關(guān)，還與試驗信道的統(tǒng)計特性有關(guān)。第十六頁，共五十七頁，2022年，8月28日§7.2:失真的度量－7平均失真度N維信源符號序列的平均失真度：此時D為一rN×sN階的矩陣與：d（u，v）、p(u)、p(v|u)、N均有關(guān)第十七頁，共五十七頁，2022年，8月28日§7.2:失真的度量－8平均失真度N維信源符號序列信源平均失真度信源、信道均無記憶時：信源平穩(wěn)時：序列中第l個分量的平均失真度第十八頁，共五十七頁，2022年，8月28日§7.2:失真的度量－9保真度準(zhǔn)則給定D，若≤

D，則稱此為保真度準(zhǔn)則對于序列信源，保真度準(zhǔn)則為：≤

ND第十九頁，共五十七頁，2022年，8月28日§7.2:失真的度量－10試驗信道：P(v|u)不是實際的信道特性矩陣，在此相當(dāng)于不同的編碼方法，編碼方法不同，不同。定義：所有≤

D的試驗信道構(gòu)成D失真許可的試驗信道集合BD第二十頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－1問題引出度量了失真，進(jìn)一步關(guān)心的問題是：一定的失真D下，最小的信息傳輸率R是多少？一定的失真D下，收端再現(xiàn)信源需要的最低的平均信息量是多少？定義：（信息）率失真函數(shù)R(D)

對于N維序列信源：第二十一頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－2率失真函數(shù)的進(jìn)一步解釋單位：比特/信源符號（同互信息）離散無記憶信源：RN(D)=NR(D)P(v|u)無實際信道含義，只代表不同編碼方法求R(D)就是在D條件下，選擇一種編碼方法，使R最小。定義域：D∈[0,Dmax]R(D)的性質(zhì)：凸?fàn)钚詥握{(diào)遞減性連續(xù)性一般情況下:Dmin=0,R(Dmin)=H(U)(有條件)當(dāng)D≥Dmax時，R(D)=0;而當(dāng)Dmin<D<Dmax時，H(U)>R(D)>0.第二十二頁，共五十七頁，2022年，8月28日7.3：刪除信道，求§7.3:率失真函數(shù)－3第二十三頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－4Dmax與R(Dmax)DmaxDR(D)R(D)>0R(D)=0定義當(dāng)DDmax時，R(Dmax)=0使R(Dmax)=0的p(v|u)不止一個不同的p(v|u)有不同的對我們有意義的：具有最小的的p(v|u)利用該p(v|u)求得使R(Dmax)=0時的DmaxR=0時，U,V統(tǒng)計獨立p(v|u)只是v的函數(shù),則有：p(v|u)＝P(v)第二十四頁，共五十七頁，2022年，8月28日例：二元信源,計算?！?.3:率失真函數(shù)－5第二十五頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－6R(D)的計算求解R(D)，--求解互信息的極小值互信息I(X,Y)是條件轉(zhuǎn)移概率的下凸函數(shù)極小值存在一般情況下很難得到R(D)的顯函數(shù)表達(dá)式，只能得到參量表達(dá)式具體計算很困難，一般利用計算機進(jìn)行迭代計算第二十六頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－7二進(jìn)制對稱信源的R(D)計算已知條件：二進(jìn)制對稱信源U={0,1}，接收變量V={0,1}，允許的失真DP(u)=[ω，1－ω]，ω≤1/2漢明失真矩陣第二十七頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－8求解步驟：由Dmin=0，找到滿足最小失真的試驗信道p(v|u),得到R(0)由漢明失真矩陣和失真度定義，計算最大允許的失真度Dmax由Dmax，找到滿足最大失真的試驗信道p,并得到R(Dmax)在一般條件下當(dāng)0<D<Dmax時，計算平均失真度選取一個信道，使＝D，求互信息求互信息的下限值得到R(D)驗證：找到滿足R(D)的試驗信道，驗證其正確性結(jié)果分析：R(D)曲線分析第二十八頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－90.10.20.40.60.81.00.10.20.30.40.5DR(D)(比特/符號）ω＝0.3ω＝0.1ω＝0.2ω＝0.5對于同一個D：信源分布越均勻，R(D)就越大，信源壓縮的可能性越小反之，若信源分布越不均勻，即信源剩余度越大，R(D)就越小，壓縮的可能性就越大。二進(jìn)制對稱信源的R(D)函數(shù)第二十九頁，共五十七頁，2022年，8月28日等概信源的信息率失真函數(shù)。信源輸出符號集，等概分布，輸出符號集，失真函數(shù)定義為

§7.3:率失真函數(shù)－10第三十頁，共五十七頁，2022年，8月28日第三十一頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－11高斯信源的R(D)計算已知條件：高斯信源U，其均值為m，方差為σ2，接收變量V概密函數(shù)：失真函數(shù)：均方誤差失真，即：求解步驟：計算平均失真度當(dāng)≤D，求互信息求互信息的下限值得到包含有D和σ2的R(D)表達(dá)式討論D和σ2比值不同時R(D)的取值驗證：找到滿足R(D)的試驗信道，驗證其正確性結(jié)果分析：R(D)曲線分析第三十二頁，共五十七頁，2022年，8月28日§7.3:率失真函數(shù)－12當(dāng)D＝σ2時，R(D)＝0。即：如果允許失真等于信源的方差，則只需用均值m來表示信源輸出，而不需要傳送信源的任何實際輸出。當(dāng)D＝0時，R(D)∞。即：在連續(xù)信源情況下，要毫無失真地傳送連續(xù)信源必須要求信道具有無限大的容量。當(dāng)D＝0.25σ2時,R(D)=1（比特/自由度）。即：允許均方誤差小于或等于σ2/4時，連續(xù)信號的每個樣本值最少需要用一個二元符號來傳輸。0.00.20.40.60.81.0D/σ2R(D)(比特/自由度）1.21.40.20.40.60.81.01.2高斯信源在均方誤差準(zhǔn)則下的R(D)函數(shù)第三十三頁，共五十七頁，2022年，8月28日§7.4:限失真信源編碼定理－1限失真信源編碼定理限失真信源編碼定理的證明限失真信源編碼定理的實用意義第三十四頁，共五十七頁，2022年，8月28日§7.4:限失真信源編碼定理－2限失真信源編碼定理設(shè)R(D)為一離散無記憶平穩(wěn)信源的信息率失真函數(shù)，并且有有限的失真測度。對于任意D≥0，ε＞0，δ＞0以及任意足夠長的碼長n，則一定存在一種信源編碼C，其碼字個數(shù)為:M=exp{n［R(D)+ε］}而編碼后碼的平均失真度:d(C)≤D+δ如果用二元編碼，R(D)取比特為單位，則上式M可寫成:M=2{n［R(D)+ε］}第三十五頁，共五十七頁，2022年，8月28日§7.4:限失真信源編碼定理－3定理解釋：對于任何失真度D≥0，只要碼長n足夠長，總可以找到一種編碼C，使編碼后每個信源符號的信息傳輸率:R′==R(D)+ε即:R′≥R(D)

而碼的平均失真度d(C)≤D。在允許失真D的條件下，信源最小的、可達(dá)的信息傳輸率是信源的R(D)。第三十六頁，共五十七頁，2022年，8月28日§7.4:限失真信源編碼定理－4限失真信源編碼定理的證明問題：設(shè)有達(dá)到R(D)的試驗信道p(v|u),要證明對于任意的R‘>R(D)時，存在一種信息傳輸率為R’的信源編碼，其平均失真度≤D+δ思路：產(chǎn)生碼書選取編譯碼方法計算失真度方法：產(chǎn)生碼書：在Vn空間隨機抽取M=2nR’個隨機序列v編碼方法：若存在與信源序列u構(gòu)成失真典型序列對的序列v(ω),則編碼uv(ω),否則編碼uv(1)譯碼：再現(xiàn)v(ω)失真度計算：在所有隨機碼書和Un空間統(tǒng)計平均的基礎(chǔ)上計算平均失真度第三十七頁，共五十七頁，2022年，8月28日§7.4:限失真信源編碼定理－5限失真信源編碼定理的幾點說明只是一個存在性定理，沒有構(gòu)造方法存在問題：符合實際信源的R(D)函數(shù)計算相當(dāng)困難信源統(tǒng)計特性的確切數(shù)學(xué)描述難得符合主客觀實際的失真測度難得R(D)計算本身困難即使求得了R(D)，還需研究最佳編碼方法才能達(dá)到極限值R(D)。第三十八頁，共五十七頁，2022年，8月28日§7.4:限失真信源編碼定理－6限失真信源編碼定理的實用意義存在性R（D）的實用意義在允許一定失真的情況下，信源的R(D)函數(shù)可以作為衡量各種壓縮編碼方法性能優(yōu)劣的一種尺度。舉例：第三十九頁，共五十七頁，2022年，8月28日舉例：二進(jìn)制無記憶對稱信源編譯碼：無噪無損信道傳輸?shù)谒氖?，共五十七頁?022年，8月28日舉例：結(jié)論

R’=1/3（比特/信源符號）該壓縮編碼方法下的信息傳輸率d(C)=1/4該壓縮編碼方法下的平均失真R(1/4)=1-H(1/4)=0.189(比特/信源符號）失真1/4下，最小的信息傳輸率R是0.189(比特/信源符號）R(1/4)<R’在1/4失真度下，該壓縮編碼方法不是最佳的，或該信源還可以壓縮第四十一頁，共五十七頁，2022年，8月28日§7.5:限失真信源編碼定理應(yīng)用－1定理：對任一連續(xù)非正態(tài)信源，若已知其方差為，熵為，并規(guī)定失真函數(shù)為，則其R(D)滿足下列不等式：

（正態(tài)）（上限）結(jié)論：在平均功率受限條件下，正態(tài)分布R(D)函數(shù)值最大，它是其他一切分布的上限值，也是信源壓縮比中最小的。所以人們往往將它作為連續(xù)信源壓縮比中最保守的估計值。第四十二頁，共五十七頁，2022年，8月28日§7.5:限失真信源編碼定理應(yīng)用－2利用連續(xù)信源的R(D)函數(shù)，分析語音的波形編碼：為了分析方便，假設(shè)語音遵從平穩(wěn)正態(tài)分布：例1：分析PCM編碼及其壓縮潛力：

采樣率：8KHz；量化位數(shù)：8

信息率：8*8=64Kb/s

相關(guān)性：樣點間獨立，且每個樣點8bit

信噪比：入公用網(wǎng)的要求26dB，

第四十三頁，共五十七頁，2022年，8月28日§7.5:限失真信源編碼定理應(yīng)用－3其中D為噪聲（允許失真）功率。R（D）：由正態(tài)分布的信息率失真函數(shù)的公式：實際語音的R(D)值要小于4.3bit，因為語音不遵從正態(tài)分布，而是近似遵從Laplace分布（一級近似）、Gamma分布（二級近似）。它們的R(D)函數(shù)值均小于正態(tài)分布的R(D)值?？梢?，4.3bit至現(xiàn)用的PCM8bit，大約有一倍差距。第四十四頁，共五十七頁，2022年，8月28日§7.5:限失真信源編碼定理應(yīng)用－4例2：若對語音編碼進(jìn)一步計入相關(guān)性，則其R(D)函數(shù)為：

則可算出其R(D)值，即對應(yīng)壓縮比（相對于PCM編碼64Kb/s） 若計入語音實際分布，R(D)值小于正態(tài)分布值，以及R(D)的主觀特征，在25-26dB要求下，實際R(D)值大約等于2左右，可以獲得大約4倍的壓縮比。信噪比（dB）35322825232017R(D)(bit)43.52.52.3421.51壓縮倍數(shù)22.283.23.4245.38第四十五頁，共五十七頁，2022年，8月28日結(jié)論：壓縮比K1）2）壓縮比K第四十六頁，共五十七頁，2022年，8月28日§7.5:限失真信源編碼定理應(yīng)用－5例3：參量編碼： 以英語為例，其音素大約為128~256個，按照通常講話速率，每秒大約平均發(fā)出10個音素，這時語音信源給出的信息率為：

第四十七頁，共五十七頁，2022年，8月28日§7.6:香農(nóng)三大定理的關(guān)系和比較－1

無失真信源編碼定理限失真信源編碼定理信源冗余度壓縮編碼信源的熵壓縮編碼無失真、保熵有失真、熵壓縮信源壓縮的極限值：信源熵H(S)信源壓縮的極限值：率失真函數(shù)R(D)存在性、構(gòu)造性存在性定理第四十八頁，共五十七頁，2022年，8月28日§7.7:香農(nóng)三大定理的關(guān)系和比較－2

信道編碼定理限失真信源編碼定理給定信道特性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)生的誤碼率p