信息論與編碼ch10-總復(fù)習(xí)

信息論與編碼ch10-總復(fù)習(xí)第一頁，共56頁。信息論“三大定理”香農(nóng)信息論的三個(gè)基本概念—信源熵、信道容量、信息率失真函數(shù)，都是臨界值，是從理論上衡量通信能否滿足要求的重要界限。香農(nóng)的三個(gè)基本編碼定理—無失真信源編碼定理、信道編碼定理、限失真信源編碼定理，這是三個(gè)理想編碼的存在性定理。分別又稱為香農(nóng)第一、第二、第三定理。雖然三個(gè)定理都指出理想編碼是存在的，但如何尋找編碼以及能否做到“理想編碼”，則完全是另外一回事。這正是信源編碼或信道編碼所要討論的問題。第二頁，共56頁。課程類型：專業(yè)選修課學(xué)時(shí)：54考核：平時(shí)成績50％（作業(yè)、考勤、PROJECT）期末考試50％（閉卷）作業(yè)：20％（百分制：缺一次扣20分）考勤：10％（百分制：缺席一次扣10分）課程設(shè)計(jì)：20％（百分制：實(shí)際分?jǐn)?shù)）考試要求3第三頁，共56頁。時(shí)間：2015年6月28日地點(diǎn)待定考試形式：閉卷考試題型：簡答題(30分)，計(jì)算題(70分)帶計(jì)算器，計(jì)算題精確到小數(shù)點(diǎn)后2位認(rèn)真答題，字跡清楚，計(jì)算題須有中間過程考試要求4第四頁，共56頁。信息論與編碼基礎(chǔ)第五頁，共56頁。信息與消息和信號(hào)的區(qū)別消息：是指包含有信息的語言、文字和圖像等，可表達(dá)客觀物質(zhì)運(yùn)動(dòng)和主觀思維活動(dòng)的狀態(tài)。信號(hào)：把消息變換成適合信道傳輸?shù)奈锢砹?，這種物理量稱為信號(hào)（如電信號(hào)、光信號(hào)、聲音信號(hào)等）。第一章概論2023/4/166第六頁，共56頁。信息“本體論”層次定義：信息是該事物運(yùn)動(dòng)的狀態(tài)和狀態(tài)改變的方式。認(rèn)識(shí)論層次的信息是同時(shí)考慮語法信息、語義信息和語用信息的全信息。全信息：同時(shí)考慮外在形式/語法信息、內(nèi)在含義/語義信息、效用價(jià)值/語用信息，稱為全信息。語法信息：事物運(yùn)動(dòng)狀態(tài)和狀態(tài)改變的方式；語義信息：事物運(yùn)動(dòng)狀態(tài)和方式的具體含義；語用信息：事物運(yùn)動(dòng)狀態(tài)和方式及其含義對觀察者的效用。研究信息論的目的：它的主要目的是提高信息系統(tǒng)的可靠性、有效性和安全性以便達(dá)到系統(tǒng)最優(yōu)化。第一章概論2023/4/167第七頁，共56頁。單符號(hào)離散信源自信息量用概率測度定義信息量設(shè)離散信源X，其概率空間為如果知道事件xi已發(fā)生，則該事件所含有的自信息定義為當(dāng)事件xi發(fā)生以前：表示事件xi發(fā)生的不確定性。當(dāng)事件xi發(fā)生以后：表示事件xi所含有（或所提供）的信息量第二章信源熵2023/4/168第八頁，共56頁。聯(lián)合自信息量當(dāng)X和Y相互獨(dú)立時(shí)，p(xiyj)=p(xi)p(yj)第二章信源熵2023/4/169第九頁，共56頁。條件自信息量：已知yj

的條件下xi

仍然存在的不確定度。自信息量、條件自信息量和聯(lián)合自信息量之間的關(guān)系第二章信源熵2023/4/1610第十頁，共56頁?；バ畔⒘浚?/p>

yj對xi的互信息量定義為的后驗(yàn)概率與先驗(yàn)概率比值的對數(shù)。第二章信源熵2023/4/1611第十一頁，共56頁。觀察者站在輸出端：兩個(gè)不確定度之差是不確定度被消除的部分，即等于自信息量減去條件自信息量。觀察者站在輸入端：觀察者得知輸入端發(fā)出xi前、后對輸出端出現(xiàn)yj的不確定度的差。觀察者站在通信系統(tǒng)總體立場上：通信后的互信息量，等于前后不確定度的差。第二章信源熵2023/4/1612第十二頁，共56頁。平均信息量—信源熵：自信息的數(shù)學(xué)期望。也稱為信源的信息熵/信源熵/香農(nóng)熵/無條件熵/熵函數(shù)/熵。信息熵的意義：信源的信息熵H是從整個(gè)信源的統(tǒng)計(jì)特性來考慮的。它是從平均意義上來表征信源的總體特性的。對于某特定的信源，其信息熵只有一個(gè)。不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。信源熵的三種物理含義信源熵H(X)是表示信源輸出后每個(gè)消息/符號(hào)所提供的平均信息量；信源熵H(X)是表示信源輸出前，信源的平均不確定性；用信源熵H(X)來表征變量X的隨機(jī)性。第二章信源熵2023/4/1613第十三頁，共56頁。條件熵：是在聯(lián)合符號(hào)集合XY上的條件自信息的數(shù)學(xué)期望。第二章信源熵2023/4/1614第十四頁，共56頁。信道疑義度—H(X/Y)：表示信宿在收到Y(jié)后，信源X仍然存在的不確定度。是通過有噪信道傳輸后引起的信息量的損失，故也可稱為損失熵。噪聲熵—H(Y/X)：表示在已知X的條件下，對于符號(hào)集Y尚存在的不確定性（疑義），這完全是由于信道中噪聲引起的。第二章信源熵2023/4/1615第十五頁，共56頁。聯(lián)合熵H(XY)：表示輸入隨機(jī)變量X，經(jīng)信道傳輸?shù)竭_(dá)信宿，輸出隨機(jī)變量Y。即收、發(fā)雙方通信后，整個(gè)系統(tǒng)仍然存在的不確定度。第二章信源熵2023/4/1616第十六頁，共56頁。最大離散熵定理(極值性)：離散無記憶信源輸出n個(gè)不同的信息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)(即p(xi)=1/n)，熵最大。H[p(x1),p(x2),…,p(xn)]≤H(1/n,1/n,…,1/n)=log2n

出現(xiàn)任何符號(hào)的可能性相等時(shí)，不確定性最大。第二章信源熵2023/4/1617第十七頁，共56頁。二進(jìn)制信源的熵函數(shù)H(p)為第二章信源熵2023/4/1618第十八頁，共56頁。平均互信息量定義：互信息量I(xi;yj)在聯(lián)合概率空間P(XY)中的統(tǒng)計(jì)平均值。從一個(gè)事件獲得另一個(gè)事件的平均互信息需要消除不確定度，一旦消除了不確定度，就獲得了信息。第二章信源熵2023/4/1619第十九頁，共56頁。站在輸出端：I(X;Y)—收到Y(jié)前、后關(guān)于X的不確定度減少的量。從Y獲得的關(guān)于X的平均信息量。站在輸入端：I(Y;X)—發(fā)出X前、后關(guān)于Y的先驗(yàn)不確定度減少的量。站在總體：I(X;Y)—通信前、后整個(gè)系統(tǒng)不確定度減少量。第二章信源熵2023/4/1620第二十頁，共56頁。BSC信道的平均互信息量設(shè)二進(jìn)制對稱信道的輸入概率空間為

轉(zhuǎn)移概率如圖2.1.8所示。第二章信源熵2023/4/1621第二十一頁，共56頁。

平均互信息量當(dāng)q不變(固定信道特性)

時(shí)，可得I(X;Y)隨輸入概率分布p變化的曲線，如圖2.1.9所示；二進(jìn)制對稱信道特性固定后，輸入呈等概率分布時(shí)，平均而言在接收端可獲得最大信息量。第二章信源熵2023/4/1622第二十二頁，共56頁。當(dāng)固定信源特性

p時(shí)，I(X;Y)就是信道特性q的函數(shù)，如圖2.1.10所示；當(dāng)二進(jìn)制對稱信道特性q=/q=1/2時(shí)，信道輸出端獲得信息量最小，即等于0。說明信源的全部信息信息都損失在信道中了。這是一種最差的信道。第二章信源熵2023/4/1623第二十三頁，共56頁。離散無記憶信源X的N次擴(kuò)展信源的熵等于離散信源X的熵的N倍，即H(X)=H(XN)=NH(X)離散平穩(wěn)信源：各維聯(lián)合概率均與時(shí)間起點(diǎn)無關(guān)的完全平穩(wěn)信源稱為離散平穩(wěn)信源。二維離散平穩(wěn)信源的熵為第二章信源熵2023/4/1624第二十四頁，共56頁。平均符號(hào)熵：信源平均每發(fā)一個(gè)符號(hào)提供的信息量為離散平穩(wěn)有記憶信源的極限熵：當(dāng)N→∞時(shí)，平均符號(hào)熵取極限值稱之為極限熵或極限信息量。用H∞表示，即極限熵的存在性：當(dāng)離散有記憶信源是平穩(wěn)信源時(shí)，極限熵等于關(guān)聯(lián)長度N→∞時(shí)，條件熵H(XN/X1X2…XN-1)的極限值，即極限熵的含義：代表了一般離散平穩(wěn)有記憶信源平均每發(fā)一個(gè)符號(hào)提供的信息量。第二章信源熵2023/4/1625第二十五頁，共56頁。信源熵的相對率η

：η=H∞/H0信源冗余度ξ：

ξ=1－η=(H0－H∞)/H0信源的冗余度表示信源可壓縮的程度。第二章信源熵2023/4/1626第二十六頁，共56頁。

數(shù)據(jù)處理定理

數(shù)據(jù)處理定理：當(dāng)消息經(jīng)過多級(jí)處理后，隨著處理器數(shù)目的增多，輸入消息與輸出消息之間的平均互信息量趨于變小。即I(X;Z)≤I(X;Y)I(X;Z)≤I(Y;Z)2023/4/1627第二十七頁，共56頁。結(jié)論：兩級(jí)串聯(lián)信道輸入與輸出消息之間的平均互信息量既不會(huì)超過第Ⅰ級(jí)信道輸入與輸出消息之間的平均互信息量，也不會(huì)超過第Ⅱ級(jí)信道輸入與輸出消息之間的平均互信息量。當(dāng)對信號(hào)/數(shù)據(jù)/消息進(jìn)行多級(jí)處理時(shí)，每處理一次，就有可能損失一部分信息，也就是說數(shù)據(jù)處理會(huì)把信號(hào)/數(shù)據(jù)/消息變成更有用的形式，但是絕不會(huì)創(chuàng)造出新的信息。這就是所謂的信息不增原理。

當(dāng)已用某種方式取得Y后，不管怎樣對Y進(jìn)行處理，所獲得的信息不會(huì)超過I(X;Y)。每處理一次，只會(huì)使信息量減少，至多不變。也就是說在任何信息流通系統(tǒng)中，最后獲得的信息量，至多是信源提供的信息。一旦在某一過程中丟失了一些信息，以后的系統(tǒng)不管怎樣處理，如果不能接觸到丟失信息的輸入端，就不能再恢復(fù)已丟失的信息。2023/4/1628第二十八頁，共56頁。隨機(jī)過程{x(t)}中某一樣本函數(shù)x(t)的時(shí)間平均值定義：隨機(jī)過程{x(t)}在某時(shí)刻ti所取的隨機(jī)變量的統(tǒng)計(jì)平均值/集平均定義：遍歷的隨機(jī)過程：時(shí)間平均與統(tǒng)計(jì)平均相等，即第二章信源熵2023/4/1629第二十九頁，共56頁。連續(xù)信源的熵為上式定義的熵在形式上和離散信源相似，也滿足離散熵的主要特性，如可加性，但在概念上與離散熵有差異因?yàn)樗チ穗x散熵的部分含義和性質(zhì)。三種限定條件下連續(xù)信源的最大熵定理第二章信源熵2023/4/1630第三十頁，共56頁。連續(xù)信源熵有關(guān)問題說明連續(xù)信源熵并不是實(shí)際信源輸出的絕對熵；連續(xù)信源的絕對熵還有一項(xiàng)正的無限大量，雖然log2(b－a)小于0，但兩項(xiàng)相加還是正值，且一般還是一個(gè)無限大量。因?yàn)檫B續(xù)信源的可能取值數(shù)有無限多，若假定等概率，確知其輸出值后所得信息量也將為無限大；Hc(X)已不能代表信源的平均不確定度，也不能代表連續(xù)信源輸出的信息量。連續(xù)信源熵的意義這種定義可以與離散信源在形式上統(tǒng)一起來；在實(shí)際問題中常常討論的是熵之間的差值問題，如信息變差、平均互信息等。在討論熵差時(shí)，兩個(gè)無限大量互相抵消。所以熵差具有信息的特征；連續(xù)信源的熵Hc(X)具有相對性，因此Hc(X)也稱為相對熵。第二章信源熵2023/4/1631第三十一頁，共56頁。信道容量C：在信道中最大的信息傳輸速率，單位是比特/信道符號(hào)。單位時(shí)間的信道容量Ct：若信道平均傳輸一個(gè)符號(hào)需要t秒鐘，則單位時(shí)間的信道容量為

Ct實(shí)際是信道的最大信息傳輸速率。第三章信道容量2023/4/1632第三十二頁，共56頁。求信道容量的方法當(dāng)信道特性p(yj/xi)固定后，I(X;Y)隨信源概率分布p(xi)的變化而變化。調(diào)整p(xi)，在接收端就能獲得不同的信息量。由平均互信息的性質(zhì)已知，I(X;Y)是p(xi)的上凸函數(shù)，因此總能找到一種概率分布p(xi)（即某一種信源），使信道所能傳送的信息率為最大。C和Ct都是求平均互信息I(X;Y)的條件極大值問題，當(dāng)輸入信源概率分布p(xi)調(diào)整好以后，C和Ct已與p(xi)無關(guān)，而僅僅是信道轉(zhuǎn)移概率的函數(shù)，只與信道統(tǒng)計(jì)特性有關(guān)；信道容量是完全描述信道特性的參量；信道容量是信道能夠傳送的最大信息量。第三章信道容量2023/4/1633第三十三頁，共56頁。當(dāng)n=2時(shí)的強(qiáng)對稱離散信道就是二進(jìn)制均勻信道。二進(jìn)制均勻信道的信道容量為：二進(jìn)制均勻信道容量曲線如圖3.2.5所示。第三章信道容量2023/4/1634第三十四頁，共56頁。香農(nóng)公式說明當(dāng)信道容量一定時(shí)，增大信道帶寬，可以降低對信噪功率比的要求；反之，當(dāng)信道頻帶較窄時(shí)，可以通過提高信噪功率比來補(bǔ)償。當(dāng)信道頻帶無限時(shí)，其信道容量與信號(hào)功率成正比。第三章信道容量2023/4/1635第三十五頁，共56頁。信道編碼定理：若有一離散無記憶平穩(wěn)信道，其容量為C，輸入序列長度為L，只要待傳送的信息率R<C，總可以找到一種編碼，當(dāng)L足夠長時(shí)，譯碼差錯(cuò)概率Pe<ε，ε為任意大于零的正數(shù)。反之，當(dāng)R>C時(shí)，任何編碼的Pe必大于零，當(dāng)L→∞，Pe→1。信道編碼定理說明：同無失真信源編碼定理類似，信道編碼定理也是一個(gè)理想編碼的存在性定理。它指出信道容量是一個(gè)臨界值，只要信息傳輸率不超過這個(gè)臨界值，信道就可幾乎無失真地把信息傳送過去，否則就會(huì)產(chǎn)生失真。第三章信道容量2023/4/1636第三十六頁，共56頁。失真度設(shè)離散無記憶信源為第四章信息率失真函數(shù)2023/4/1637第三十七頁，共56頁。對每一對(xi,yj)，指定一個(gè)非負(fù)函數(shù)d(xi,yj)≥0i=1,2,…,n

j=1,2,…,m

稱d(xi,yj)為單個(gè)符號(hào)的失真度/失真函數(shù)。表示信源發(fā)出一個(gè)符號(hào)xi，在接收端再現(xiàn)yj所引起的誤差或失真。第四章信息率失真函數(shù)2023/4/1638第三十八頁，共56頁。平均失真度定義d(xi,yj)只能表示兩個(gè)特定的具體符號(hào)xi和yj之間的失真。平均失真度：平均失真度為失真度的數(shù)學(xué)期望，第四章信息率失真函數(shù)2023/4/1639第三十九頁，共56頁。平均失真度意義是在平均意義上，從總體上對整個(gè)系統(tǒng)失真情況的描述。它是信源統(tǒng)計(jì)特性p(xi)、信道統(tǒng)計(jì)特性p(yj/xi)和失真度d(xi,yj)的函數(shù)。當(dāng)p(xi)，p(yj/xi)和d(xi,yj)給定后，平均失真度就不是一個(gè)隨機(jī)變量了，而是一個(gè)確定的量。如果信源和失真度一定，就只是信道統(tǒng)計(jì)特性的函數(shù)。信道傳遞概率不同，平均失真度隨之改變。第四章信息率失真函數(shù)2023/4/1640第四十頁，共56頁。允許平均失真度：率失真函數(shù)中的自變量D，也就是人們規(guī)定的平均失真度的上限值。率失真函數(shù)的定義域問題就是在信源和失真函數(shù)已知的情況下，討論允許平均失真度D的最小和最大值問題。D的選取必須根據(jù)固定信源X的統(tǒng)計(jì)特性P(X)和選定的失真函數(shù)d(xi,yj)，在平均失真度的可能取值范圍內(nèi)。第四章信息率失真函數(shù)2023/4/1641第四十一頁，共56頁。常用的失真函數(shù)第一種當(dāng)a=1時(shí)稱為漢明失真矩陣。第二種/平方誤差失真矩陣：d(xi,yj)=(yj－xi)2第四章信息率失真函數(shù)2023/4/1642第四十二頁，共56頁。單符號(hào)信源和單符號(hào)信道的信息率失真函數(shù)在信源和失真度給定以后，PD是滿足保真度準(zhǔn)則的試驗(yàn)信道集合，平均互信息I(X;Y)是信道傳遞概率p(yj/xi)的下凸函數(shù)，所以在PD中一定可以找到某個(gè)試驗(yàn)信道，使I(X;Y)達(dá)到最小，即這個(gè)最小值R(D)稱為信息率失真函數(shù)，簡稱率失真函數(shù)。在信源給定以后，總希望在允許一定失真的情況下，傳送信源所必須的信息率越小越好。從接收端來看，就是在滿足保真度準(zhǔn)則的條件下，尋找再現(xiàn)信源消息必須的最低平均信息量，即平均互信息的最小值。第四章信息率失真函數(shù)2023/4/1643第四十三頁，共56頁。求信息率失真函數(shù)的方法信息率失真函數(shù)R(D)是假定信源給定的情況下，在用戶可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。它反映的是信源可壓縮程度。率失真函數(shù)一旦找到，就與求極值過程中選擇的試驗(yàn)信道不再有關(guān)，而只是信源特性的參量。不同的信源，其R(D)是不同的。第四章信息率失真函數(shù)2023/4/1644第四十四頁，共56頁。

對偶問題：信道容量和信息率失真函數(shù)的問題，都是求平均互信息極值問題。分三個(gè)方面說明：求極值問題平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,…,n)

的上凸函數(shù)，信道容量就是在固定信道情況下，求平均互信息極大值的問題，即I(X;Y)又是信道轉(zhuǎn)移概率分布p(yj/xi)(i=1,2,…,n;j=1,2,…,m)

的下凸函數(shù)，信息率失真函數(shù)就是在試驗(yàn)信道（滿足保真度準(zhǔn)則的信道）中尋找平均互信息極小值的問題，即第四章信息率失真函數(shù)2023/4/1645第四十五頁，共56頁。特性信道容量C一旦求出后，就只與信道轉(zhuǎn)移概率p(yj/xi)有關(guān)，反映信道特性，與信源特性無關(guān)；信息率失真函數(shù)R(D)一旦求出后，就只與信源概率分布p(xi)有關(guān)，反映信源特性，與信道特性無關(guān)。解決的問題信道容量是為了解決通信的可靠性問題，是信息傳輸?shù)睦碚摶A(chǔ)，通過信道編碼增加信息的冗余度來實(shí)現(xiàn)；信息率失真函數(shù)是為了解決通信的有效性問題，是信源壓縮的理論基礎(chǔ)，通過信源編碼減少信息的冗余度來實(shí)現(xiàn)。第四章信息率失真函數(shù)2023/4/1646第四十六頁，共56頁。限失真信源編碼定理：設(shè)一離散平穩(wěn)無記憶信源的輸出隨機(jī)變量序列為X=(X1,X2,…,XL)，若該信源的信息率失真函數(shù)是R(D)，并選定有限的失真函數(shù)。對于任意允許平均失真度D≥0，和任意小的ε>0，當(dāng)信息率R>R(D)，只要信源序列長度L足夠長，一定存在一種編碼方式C，使譯碼后的平均失真度；反之，若R<R(D)，則無論用什么編碼方式，必有，即譯碼平均失真必大于允許失真。信息率失真函數(shù)也是一個(gè)界限。只要信息率大于這個(gè)界限，譯碼失真就可限制在給定的范圍內(nèi)。即通信的過程中雖然有失真，但仍能滿足要求，否則就不能滿足要求。第四章信息率失真函數(shù)2023/4/1647第四十七頁，共56頁。研究信道編碼和率失真函數(shù)的意義研究信道容量的意義：在實(shí)際應(yīng)用中，研究信道容量是為了解決在已知信道中傳送最大信息率問題。目的是充分利用已給信道，使傳輸?shù)男畔⒘孔畲蠖l(fā)生錯(cuò)誤的概率任意小，以提高通信的可靠性。這就是信道編碼問題。

研究信息率失真函數(shù)的意義：研究信息率失真函數(shù)是為了解決在已知信源和允許失真度D的條件下，使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號(hào)盡快地傳送盡可能多的信源消息，以提高通信的有效性。這是信源編碼問題。第四章信息率失真函數(shù)2023/4/1648第四十八頁，共56頁。香農(nóng)編碼費(fèi)諾編碼哈夫曼編碼M進(jìn)制哈夫曼編碼編碼效率的計(jì)算第五章信源編碼2023/4/1649第四十九頁，共56頁。信源編碼：以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。密碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通常通過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。第五章信源編碼2023/4/1650第五十頁，共56頁。香農(nóng)編碼設(shè)離散無記憶信源二進(jìn)制香農(nóng)碼的編碼步驟如下：將信源符號(hào)按概率從大到小的順序排列，為方便起見，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i個(gè)碼字的累加概率，則20