信息論與編碼全套教學課件

信息論與編碼

第1章緒論第2章信源與信息熵第3章信道與信道容量第4章失真與信息率失真函數(shù)第5章信源編碼第6章信道編碼第7章網(wǎng)絡(luò)信息論初步全套可編輯PPT課件2第1章緒論信息論是什么？編碼是用來干什么的？全套可編輯PPT課件3第1章緒論信息論與編碼課程的內(nèi)容體系信息與編碼的若干基本概念信息論的發(fā)展歷史全套可編輯PPT課件4第1章之“信息論與編碼”課程的內(nèi)容體系通信系統(tǒng)基本模型信息論與編碼課程內(nèi)容體系5第1章之“信息論與編碼”課程的內(nèi)容體系本課程所說“信息論”，主要是指“香農(nóng)信息論”；香農(nóng)信息論的主要內(nèi)容，來自于其1948年發(fā)表在貝爾技術(shù)雜志上的文章：“通信中的數(shù)學理論”；所以，香農(nóng)信息論，嚴格來說應(yīng)該是“通信論”。6通信系統(tǒng)基本模型既然是通信理論，首先看看通信的定義、基本框圖和基本問題：定義：通信是把信息從一個地方（發(fā)送端，信源）通過信息的通道（信道）送到另一個地方（接收端，信宿）。7通信系統(tǒng)基本模型基本框圖：信源信宿噪聲源信息信息干擾信道8通信系統(tǒng)基本模型基本問題：如何使通信“又快又好又安全”？快：用盡可能少的符號攜帶盡可能多的信息—有效性；好：信息傳輸要盡可能準確無誤—可靠性；安全：信息的安全性。本書只考慮有效性和可靠性。9“信息論與編碼”課程的內(nèi)容體系對有效性和可靠性這兩個通信中的基本問題，又各有兩個方面的內(nèi)容：希望“又快”（有效性）、“又好”（可靠性），這個“快”和“好”有沒有極限？如果有，極限是多少？這是“信息論”要解決的問題；用什么方法和手段達到或接近該極限？這是“編碼”所要解決的問題。

所以這門課叫做《信息論與編碼》10“信息論與編碼”課程的內(nèi)容體系所以，《信息論與編碼課程》的內(nèi)容體系，可以表示成一個2×2的矩陣：信息論編碼可靠性有效性有效性的極限是否存在及其大小問題可靠性的極限是否存在及其大小問題達到或接近有效性極限的手段和方法達到或接近可靠性極限的手段和方法11“信息論與編碼”課程的內(nèi)容體系有效性是要用盡可能少的符號攜帶盡可能多的信息，這個取決于信源的特性。所以在接下來的第2章，要研究信源與信源熵；可靠性取決于信息傳輸通道（信道）的特性，因此第3章研究信道與信道容量；12“信息論與編碼”課程的內(nèi)容體系相應(yīng)地：提高有效性的方法，是對信源進行編碼，稱為信源編碼，是第5章的內(nèi)容；提高可靠性的方法，是對信道上傳輸?shù)男畔⑦M行編碼，稱為信道編碼，是第6章的內(nèi)容；13“信息論與編碼”課程的內(nèi)容體系此外：第4章也是關(guān)于信源的，與第2章的不同在于：第2章的內(nèi)容用于無失真信源編碼，而第4章的內(nèi)容用于限失真信源編碼。由于其處理手段，類似于第3章信道的處理方法，故放于第3章之后；第7章對信息論的前沿技術(shù)—網(wǎng)絡(luò)信息論，進行了簡要介紹。14“信息論與編碼”課程的內(nèi)容體系所以，可以把上面的2×2矩陣重新表示為：信息論編碼可靠性有效性第2章、第4章第3章第5章第6章15“信息論與編碼”課程的內(nèi)容體系從橫的方向看：第2章（包括第4章）和第3章是平行的第2章研究信源，主要關(guān)心信源熵，是有關(guān)有效性的；

第3章研究信道，主要關(guān)心信道容量，是有關(guān)可靠性的；

第2章和第3章的章節(jié)結(jié)構(gòu)是幾乎一樣的。16“信息論與編碼”課程的內(nèi)容體系第5章和第6章是平行的第5章研究信源編碼，是實現(xiàn)有效性的方法；

第6章研究信道編碼，是實現(xiàn)可靠性的方法；

第5章和第6章的章節(jié)結(jié)構(gòu)是幾乎一樣的。17“信息論與編碼”課程的內(nèi)容體系從縱的方向看：第2章（包括第4章）和第5章是前后銜接的第2章研究信源特性，第5章在第2章的基礎(chǔ)上，研究提高有效性的手段和方法（信源編碼），這是一條有關(guān)有效性的主線；18“信息論與編碼”課程的內(nèi)容體系第3章和第6章是前后銜接的第3章研究信道特性，第6章在第3章的基礎(chǔ)上，研究提高可靠性的手段和方法（信道編碼），這是一條有關(guān)可靠性的主線；有效性的主線（第2、5章）和可靠性的主線（第3、6章）是平行的。19第1章緒論信息論與編碼課程的內(nèi)容體系信息與編碼的若干基本概念信息論的發(fā)展歷史20第1章之信息與編碼的若干基本概念信息的概念信息的度量21信息的概念信息論是研究信息的，所以首先要明白什么是信息？信息的本質(zhì)是什么？22信息的概念全部意義上的信息（全信息）包括：語法信息、語義信息和語用信息語法信息只考慮信息的外在形式；語義信息要考慮信息的內(nèi)容；語用信息要考慮信息的作用對象。23信息的概念考慮全信息，則無法進行深入研究?？藙诘?香農(nóng)等只考慮語法信息，對信息進行了深入研究，得到了有關(guān)信息的系統(tǒng)理論，是為“香農(nóng)信息論”，也稱“狹義信息論”。24信息的概念香農(nóng)：“信息是使隨機不確定性減少的程度”。要進行通信，一定是接收方關(guān)于某事件是未知的或不確定的；接收方接收到信息以后，可以消除或者減少這種不確定性。25信息的度量畢達哥拉斯：“萬物皆數(shù)”。要對信息進行深入研究，必須定量；信息量的多少，等于對隨機不確定性減少的程度；隨機不確定性可以用概率來描述。26信息的度量要實現(xiàn)度量，首先需定義一個單位：信息的基本單位：比特（bit）可以用一個“是（或否）”的回答來消除的不確定性，定義為1比特（2選1的不確定性）。27信息的度量一個事件包含的信息量必須滿足：與該事件出現(xiàn)的概率是反比例關(guān)系（備選答案越多（某一備選答案選中的概率越?。淮_定程度越大，信息量越大）；確定性的事件信息量為0；信息量具有可加性。28信息的度量根據(jù)以上條件，可以用公式：來計算信息的多少。當取以2為底的對數(shù)時，信息量的單位為比特。29第1章之信息論的形成和發(fā)展歷史略30第2章信源與信源熵信源的分類與數(shù)學模型離散單符號信源熵離散序列信源熵馬爾科夫信源極限熵連續(xù)信源熵波形信源熵連續(xù)信源最大熵定理信源的冗余度31信號分類

離散信號

時間和幅度均離散

連續(xù)信號

時間和幅度均連續(xù)

時間離散幅度連續(xù)信號

抽樣信號

幅度離散時間連續(xù)信號2.1信源的分類及數(shù)學模型2.1.1信源分類321、離散信源離散單符號信源離散序列信源2、時間離散幅度連續(xù)信源連續(xù)單符號信源連續(xù)序列信源無記憶有記憶馬爾科夫信源無記憶有記憶3、時間連續(xù)幅度連讀信源（波形信源）2.1.1信源分類信源分類：（由簡單到復(fù)雜）（1）離散單符號信源；（2）離散序列信源；（3）馬爾科夫信源；（4）連續(xù)單符號信源；（5）連續(xù)序列信源；（6）波形信源。33342.1.2信源的數(shù)學模型描述：通過概率空間描述（1）離散單符號信源離散信源：，pi

0。2.1.2信源的數(shù)學模型（2）離散序列信源（L次擴展信源）聯(lián)合概率：無記憶：

352.1.2信源的數(shù)學模型（3）馬爾科夫信源聯(lián)合概率：

3637（4）連續(xù)單符號信源顯然應(yīng)滿足pX(x)

0，

2.1.2信源的數(shù)學模型38（5）連續(xù)序列信源若為無記憶的，則

2.1.2信源的數(shù)學模型2.1.2信源的數(shù)學模型（6）波形信源某時刻的取值是隨機的，用隨機過程{x(t)}來描述對于限頻波形信源，設(shè)其最高頻率為fm，根據(jù)奈奎斯特抽樣定理，只要抽樣頻率fs≥2fm，則可用其抽樣信號無失真恢復(fù)原信號。設(shè)該波形信源持續(xù)時間為tB，如果我們?nèi)∽畹统闃宇l率fs＝2fm，則只需要個2fmtB采樣點即可。因此，一個代表波形信源的平穩(wěn)隨機過程{x(t)}，可以用序列長度L＝2fmtB的隨機矢量來表示即可，其概率空間可

用序列長度L＝2fmtB的連續(xù)序列信源的概率空間

來描述。3940從理論上說任何時間受限的函數(shù)，其頻譜是無限的；反之，任何頻帶受限的函數(shù)，其時間上是無限的。實際中，可認為函數(shù)在頻帶fm、時間tB以外的取值很小，不至于引起函數(shù)的嚴重失真。2.1.2信源的數(shù)學模型41（1）馬爾可夫信源簡化形式當信源的記憶長度為m+1時，該時刻發(fā)出的符號與前m個符號有關(guān)聯(lián)性，而與更前面的符號無關(guān)。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布42離散有記憶序列信源與馬爾可夫信源區(qū)別(a)離散有記憶序列信源(b)馬爾可夫信源43（2）齊次馬爾可夫信源齊次馬爾可夫信源：條件概率與時間起點無關(guān)。平穩(wěn)包含齊次，齊次不一定平穩(wěn)。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布平穩(wěn)與齊次區(qū)別若Q和T為任意兩個時刻，平穩(wěn)滿足44運用概率的一般運算法則45（3）馬爾可夫信源狀態(tài)轉(zhuǎn)移概率矩陣信源在某一時刻出現(xiàn)符號概率xj與信源此時所處狀態(tài)si有關(guān)，用符號條件概率表示p(xj/si)，狀態(tài)轉(zhuǎn)移概率表示為p(sj/si)狀態(tài)集為：2.1.3馬爾科夫信源的穩(wěn)態(tài)分布46馬爾可夫信源一步轉(zhuǎn)移概率特別關(guān)心n-m=1情況，pij(m,m+1)2.1.3馬爾科夫信源的穩(wěn)態(tài)分布47馬爾可夫信源一步轉(zhuǎn)移概率矩陣系統(tǒng)在任一時刻可處于狀態(tài)空間的任意一狀態(tài)，狀態(tài)轉(zhuǎn)移時，轉(zhuǎn)移概率是一個矩陣。由于共有Q=nm種不同狀態(tài)，可用Q×Q的矩陣來描述一步轉(zhuǎn)移概率矩陣：2.1.3馬爾科夫信源的穩(wěn)態(tài)分布48齊次馬爾可夫信源性質(zhì)對于齊次馬爾可夫鏈，一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。定義：若齊次馬爾可夫鏈對一切i,j存在不依賴于i的極限，則稱其具有遍歷性，pj稱為平穩(wěn)分布2.1.3馬爾科夫信源的穩(wěn)態(tài)分布49馬爾可夫信源定理：設(shè)有一齊次馬爾可夫鏈，其狀態(tài)轉(zhuǎn)移矩陣為P，其穩(wěn)態(tài)分布為wj=p(sj)2.1.3馬爾科夫信源的穩(wěn)態(tài)分布2.1.3馬爾科夫信源的穩(wěn)態(tài)分布該方程是否存在解？解是否唯一結(jié)論1：該方程一定存在非零解。

502.1.3馬爾科夫信源的穩(wěn)態(tài)分布解的唯一性

說明：以上條件只是馬爾科夫信源存在穩(wěn)態(tài)分布的必要條件，并不是充要條件。51由于52不可約性:就是任意一對i和j，都存在至少一個k，使pij(k)>0。非周期性:所有pii(n)>0的n中沒有比1大的公因子。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布53如圖2-1所示的二進制相對碼編碼器（其中T為時延模塊），初始狀態(tài)Y1=X1；其余時刻，如輸入X=0，則當前時刻輸出等于上時刻輸出，Yi+1=Yi；如輸入X=1，則當前時刻輸出異于上時刻輸出，

；若已知P(X=0)=p，P(X=1)=1-p=q，試寫出其轉(zhuǎn)移概率矩陣，并畫出狀態(tài)轉(zhuǎn)移圖。2.1.3馬爾科夫信源的穩(wěn)態(tài)分布解：由于當前時刻的輸出，取決于當前時刻的輸入，以及前一個時刻的輸出，所以輸出序列是一個一階馬爾可夫鏈。對于二進制信源，前一個時刻的輸出共有兩種（0或者1），所以狀態(tài)共有兩種：“0”狀態(tài)和“1”狀態(tài)。

即轉(zhuǎn)移概率矩陣為：其狀態(tài)轉(zhuǎn)移圖為：

54pqp10q2.1.3馬爾科夫信源的穩(wěn)態(tài)分布二階馬爾科夫信源，X{0,1},求穩(wěn)態(tài)概率分布55起始狀態(tài)符號01s1(00)1/21/2s2(01)1/32/3s3(10)1/43/4s4(11)1/54/5表2-1符號條件概率p(aj|si)解：對二階馬爾可夫鏈，其狀態(tài)共有四種，分別為：S=(00，01，10，11)，根據(jù)符號條件概率表2-1，可以寫出符號條件概率矩陣為：可得狀態(tài)轉(zhuǎn)移概率矩陣為5657狀態(tài)轉(zhuǎn)移概率起始狀態(tài)(si)s1(00)s2(01)s3(10)s4(11)1/201/401/203/4001/301/502/304/5s1(00)s2(01)s3(10)s4(11)2.1.3馬爾科夫信源的穩(wěn)態(tài)分布表2-2狀態(tài)條件概率p(sj|si)終止狀態(tài)(sj)狀態(tài)轉(zhuǎn)移圖：5800100111(0)1/2(0)1/5(1)2/3(0)1/4(1)1/2(1)4/5(1)3/4(0)1/359

設(shè)四種狀態(tài)的穩(wěn)態(tài)概率為W1，W2，W3，W4可得方程組解得穩(wěn)態(tài)分布的概率為：達到穩(wěn)態(tài)后的符號概率為：2.1.3馬爾科夫信源的穩(wěn)態(tài)分布例：設(shè)有一馬爾科夫鏈，其狀態(tài)轉(zhuǎn)移矩陣為判斷該馬爾科夫鏈是否存在穩(wěn)態(tài)分布？

60612.2離散單符號信源熵自信息量離散單符號信源熵離散單符號信源條件熵離散單符號信源聯(lián)合熵互信息信源熵性質(zhì)622.2.1自信息量自信息量

例以2為底，單位為比特，用bit（或b）表示。自信息量與不確定度自信息量：符號出現(xiàn)后，提供給收信者的信息量；不確定度：符號出現(xiàn)前，所含有的不確定性。二者數(shù)量上相等，物理含義不同。632.2.1自信息量642.2.1自信息量自信息量的性質(zhì)p(xi)=1,I(xi)=0；確定性事件不包含任何信息量；p(xi)=0,I(xi)=∞；出現(xiàn)的概率越小，包含的信息量越大；概率等于零時，包含的信息量為無窮大；非負性：p(xi)∈[0,1]，所以，故I(xi)≥0；可加性：如果符號xi中包含I(xi)的信息量，符號yj中包含I(yj)的信息量，則符號xi和yj同時出現(xiàn)包含的信息量，為兩者的自信息量之和（假定兩者互相獨立p(xi,yj)＝p(xi)p(yj)）：

I(xi,yj)=I(xi)+I(yj)

例：假設(shè)一次擲兩個各自均勻、互相不可區(qū)分但又不相關(guān)的骰子。如(A)、(B)分別表示：僅有一個骰子是3；至少有一個骰子是4；試計算(A)、(B)發(fā)生后提供的信息量。65662.2.2離散單符號信源熵離散單符號信源熵就是其平均不確定度

對于

，平均信息量為

離散單符號信源熵例題例：二元信源的熵67H(X)=-plogp-(1-p)log(1-p)=H(p)當p=0.5時，具有最大熵；當p=1或p=0時，H(X)=0;信源熵是p的上凸函數(shù)。682.2.3離散單符號信源條件熵給定條件yj，信源X的概率空間變化為

給定條件yj，可得條件熵：信息量例：某高三畢業(yè)生中，25%的女生考取了大學。在考取大學的女生中75%居住在城區(qū)，而高三畢業(yè)生中50%住在城區(qū)。假如我們得知“住在城區(qū)的女生考取了大學”的消息，試問獲取了多少信息量？69702.2.3離散單符號信源條件熵若Y∈{yj,j=1,2,…,m}，可得{H(Y|y1),H(Y|y2),…,H(Y|ym)}若以Y為條件下，則X的條件熵為條件熵H(Y|X)表示當已知Y時，X仍然具有的不確定度。

例2-4

某二進制數(shù)字通信系統(tǒng)如圖2-5所示。發(fā)送端信源X為二進制信源{0，1}，其概率空間為由于通信信道中有干擾和噪聲，導(dǎo)致接收端判決結(jié)果除了“0”和“1”以外，還有一種未知的狀態(tài)（既不是“0”也不是“1”），我們表示為“？”狀態(tài)。設(shè)信道的符號轉(zhuǎn)移概率為：求信源熵H(X)、條件熵H(X/Y)和H(Y/X)，以及信源熵H(Y)。71p(y=0/x=0)=3/4，

p(y=0/x=1)=0；p(y=1/x=0)=0，

p(y=1/x=1)=1/2；p(y=?/x=0)=1/4，

p(y=?/x=1)=1/2；圖2-5二進制數(shù)字通信系統(tǒng)解：（1）信源熵H(X)可直接由公式求得（2）根據(jù)條件熵公式，求條件熵H(Y/X)，，需要知道條件概率p(y=0/x=0)、p(y=1/x=0)、p(y=？/x=0)和p(y=0/x=1)、p(y=1/x=1)、p(y=？/x=1)；以及聯(lián)合概率p(x=0,

y=0)、p(x=0,

y=1)、p(x=0,y=？)和p(x=1，y=0)、p(x=1,y=1)、p(x=1,y=？)等：p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/6則由條件熵公式可得：72（3）、根據(jù)條件熵公式，求條件熵H(X/Y)，，需要知道條件概率p(x=0/y=0)、p(x=0/y=1)、p(x=0/y=？)和p(x=1/y=0)、p(x=1/y=1)、p(x=1/y=？)；以及聯(lián)合概率p(x=0,y=0)、p(x=0,y=1)、p(x=0,y=？)和p(x=1,y=0)、p(x=1,y=1)、p(x=1,y=?)等：故

73因此（4）由74得：752.2.4離散單符號信源聯(lián)合熵當X和Y聯(lián)合出現(xiàn)，若X∈{x1,x2,…,xn},Y∈{y1,y2,…,ym}，則其概率空間變化為

聯(lián)合熵：信息量例題例2-5根據(jù)例2-4的信源X和信源Y，求聯(lián)合熵H(X,Y)。

根據(jù)例2-4的求解過程，已知：

p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2

p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6

p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/676772.2.5互信息互信息：例2-4數(shù)字通信系統(tǒng)78符號間互信息：在X取值集合上做概率統(tǒng)計平均，即得：進一步，在Y取值集合上做概率統(tǒng)計平均，即得2.2.5互信息79而且：例2-6，求例2-4中，符號X和符號Y之間的互信息2.2.5互信息80信源熵、條件熵、聯(lián)合熵之間的關(guān)系若X和Y相互獨立，則信源熵、條件熵、聯(lián)合熵、互信息之間的關(guān)系

2.2.6信源熵、條件熵、聯(lián)合熵、互信息等之間的關(guān)系812.2.6信源熵、條件熵、聯(lián)合熵、互信息等之間的關(guān)系圖2-6互信息量與熵之間的關(guān)系圖2-7收、發(fā)兩端的熵關(guān)系822.2.7信源熵的性質(zhì)非負性對稱性確定性可擴展性遞增性83非負性84對稱性85確定性可擴展性遞增性這條性質(zhì)表明，若原信源X中有一元素劃分成m個元素（符號），而這m個元素的概率之和等于原元素的概率，則新信源的熵增加。熵增加了一項是由于劃分而產(chǎn)生的不確定性量。例H(1/3,1/3,1/6,1/6)8687上凸性極值性（最大離散熵定理）熵函數(shù)H(P)是概率矢量P={p1，p2，…，pn}的嚴格∩型凸函數(shù)（上凸函數(shù)）?？杉有?/p>

一般式當X、Y相互獨立時熵的可加性可這樣理解：復(fù)合事件集合的平均不確定性為各個分事件集合的平均不確定性的和。88遞增性這條性質(zhì)表明，若原信源X中有一元素劃分成m個元素（符號），而這m個元素的概率之和等于原元素的概率，則新信源的熵增加。熵增加了一項是由于劃分而產(chǎn)生的不確定性量。例H(1/3,1/3,1/6,1/6)8990

2.3離散序列信源熵離散無記憶信源及其信息熵離散有記憶信源熵離散平穩(wěn)信源的極限熵

2.3離散序列信源熵離散序列信源（L次擴展信源）概率空間離散序列信源熵：

91單位：比特/序列獨立但非同分布獨同分布序列熵

2.3.1離散無記憶信源的序列熵92消息熵平均符號熵單位：比特/符號i.i.d.9394

2.3.2離散有記憶信源熵消息熵：序列熵：95對于有記憶離散序列信源，可得：結(jié)論1：離散序列信源的極限熵為：

結(jié)論2：

是L的單調(diào)非增函數(shù)結(jié)論3：

結(jié)論4：

是L的單調(diào)非增函數(shù)2.3.3離散平穩(wěn)信源的極限熵96例

離散有記憶信源p(xj/xi)xjxix1x2x3x19/111/80x22/113/42/9x301/87/997解：

H(X2/X1)＝0.87比特/符號

H(X1)＝1.5比特/符號

H(X1,X2)＝H(X1)＋H(X2/X1)

＝1.5＋0.87＝2.37比特/序列 平均符號熵H2(X)＝0.5H(X2)＝1.185比特/符號比較上述結(jié)果可得：H2(X)<H1

(X)，即二重序列的符號熵值較單符號熵變小了，也就是不確定度減小了，這是由于符號之間存在相關(guān)性造成的。98馬氏鏈極限熵齊次馬爾科夫鏈2.4馬爾科夫信源的極限熵99例2-8求馬氏鏈平均符號熵（三個狀態(tài)）

1/0.1s1

1/0.50/0.90/0.50/0.8s2

s31/0.2

三狀態(tài)馬爾可夫信源狀態(tài)轉(zhuǎn)移圖解得：W1＝5/59，W2＝9/59，W3＝45/59。馬爾可夫信源的熵：比特/符號100求解馬爾可夫信源熵的步驟為：(1)根據(jù)題意畫出狀態(tài)轉(zhuǎn)移圖，或?qū)懗鰻顟B(tài)轉(zhuǎn)移矩陣；(2)計算信源的平穩(wěn)分布概率（假定信源具有平穩(wěn)分布）；(3)根據(jù)一步轉(zhuǎn)移概率和穩(wěn)態(tài)分布概率，計算信源熵（極限熵）。1011022.5連續(xù)單符號信源熵2.5.1幅度連續(xù)的單個符號信源熵1032.5.1幅度連續(xù)的單個符號信源熵1042.6連續(xù)序列信源熵連續(xù)序列的熵和離散序列的熵性質(zhì)完全相同，只要把離散信源熵用連續(xù)信源熵替代即可。105

2.7波形信源熵波形信源可用隨機過程x(t)表示。對限時tB和限頻fm平穩(wěn)隨機過程，可以抽樣成序列長度L=2fmtB的連續(xù)序列信源，其熵為：2.8連續(xù)信源最大熵定理問題的提出:

在連續(xù)信源中，不同約束條件(峰值功率、平均功率)下，有不同的最大熵。無約束時，最大熵不存在。106對于定義域為有限的隨機變量X，當它是均勻分布時，具有最大熵。變量X的幅度取值限制在[a，b]，當pX

(x)=1/(b-a)，則Hc(X)=log(b-a)峰值功率受限為P，則輸出信號的瞬時電壓限定在

P1/2，等價于取值幅度受限。

限峰功率最大熵定理107108限平均功率最大熵定理對于相關(guān)矩陣一定隨機變量X，當它是正態(tài)分布時具有最大熵最大熵定理（總結(jié)）無約束條件的最大熵不存在限峰功率最大熵限平均功率最大熵1091102.9信源的冗余度冗余度，表示給定信源在實際發(fā)出消息時所包含的多余信息。它來自兩個方面，一是信源符號間的相關(guān)性；二是信源符號分布的不均勻性1112.9信源的冗余度例：計算英文字母冗余度H0(X)=l0g27=4.76比特/符號H1(X)=4.03比特/符號H2(X)=3.32比特/符號H3(X)=3.1比特/符號H∞(X)=1.4比特/符號本章小結(jié)112第二章主要內(nèi)容結(jié)構(gòu)113本章小結(jié)本章學習思路信源（信息的出發(fā)點）→對信源進行分類→給出數(shù)學模型→信源的重要參數(shù)：熵、互信息等→按照分類，從簡單到復(fù)雜，研究信源的熵等重要參數(shù)114定義、性質(zhì)

計算公式、相互關(guān)系自信息量信源熵、條件熵、聯(lián)合熵、互信息序列熵、平均符號熵、極限熵連續(xù)信源最大熵定理冗余度115第3章信道與信道容量信道的分類與數(shù)學模型離散單符號信道的信道容量離散序列信道的信道容量連續(xù)單符號信道的信道容量連續(xù)序列信道的信道容量波形信道的信道容量信道冗余度1163.1.1信道的分類（按照信道輸入信號分類）

離散單符號信道

離散序列信道

連續(xù)單符號信道

連續(xù)序列信道

波形信道主要目的：研究信道中理論上能夠傳輸或存儲的最大信息量，即信道容量。3.1信道的分類1173.1.2信道的數(shù)學模型描述：信道把特定輸入符號映射為特定輸出符號的能力（正確概率）以及映射為其他輸出符號的可能性（錯誤概率）。圖3-1信道模型圖P(Y|X)1181.離散單符號信道的數(shù)學模型轉(zhuǎn)移概率矩陣離散單符號信道模型P(Y|X)119例：二進制對稱信道（BSC）轉(zhuǎn)移概率矩陣圖3-2二進制對稱信道（BSC）p11=1-p，p12=p，p21=p，p22=1-p1202.離散序列信道的數(shù)學模型當輸入為離散序列時，用隨機矢量x來表示，若輸出隨機矢量為y，則信道可用轉(zhuǎn)移概率P(y/x）表示。當信源和信道無記憶時，離散序列信道可看成一系列離散單符號信道。121例:擴展信道如果對離散單符號信道進行L次擴展，就形成了L次離散無記憶序列信道BSC的二次擴展信道

00101101000111X

{00,01,10,11}，Y

{00,01,10,11}，二次擴展無記憶信道的序列轉(zhuǎn)移概率p(00/00)=p(0/0)p(0/0)=(1-p)2，p(01/00)=p(0/0)p(1/0)=p(1-p)，p(10/00)=p(1/0)p(0/0)=p(1-p)，p(11/00)=p(1/0)p(1/0)=p2101223.連續(xù)單符號信道的數(shù)學模型對連續(xù)單符號輸入信源x，對應(yīng)的輸出為隨機變量y。若信道為加性高斯白噪聲信道:

y=x+n其中，n為0均值、方差為σ2的高斯隨機變量。若給定輸入x0，則1234.連續(xù)序列信道的數(shù)學模型當輸入為連續(xù)序列時，用隨機矢量x來表示，若輸出隨機矢量為y，則信道可用轉(zhuǎn)移概率密度pY(y/x）表示。若輸入序列無記憶，無記憶連續(xù)序列信道可以看作是一系列連續(xù)單符號信道。1245.波形信道的數(shù)學模型若輸入為波形信源，用隨機過程{x(t)}表示，則輸出也為隨機過程，記為{y(t)}。若滿足限時（tB）限頻（fm）條件，則可以抽樣成L=2fmtB的連續(xù)平穩(wěn)隨機序列，則信道用轉(zhuǎn)移概率密度描述，為：若信源信道無記憶，則1251.互信息量表達式3.1.3信道容量的定義126定理3.1

在p(yj|xi)給定時，互信息量I(X;Y)是p(xi)的上凸函數(shù)。通信的目的:每次信道使用（每發(fā)送一個符號），傳送到接收端盡可能多的信息量（互信息量I(X;Y)取最大值）。需要解決的問題是：①該最大值是多少？②p(xi)是什么分布時，取得該最大值？1272.信道容量的定義信道容量（ChannelCapacity）：信道所能傳送的最大信息量。比特/符號（bits/symbol或bits/channeluse）

在p(y/x)給定時，I(X;Y)是關(guān)于p(x)的上凸函數(shù)。信道容量要解決的問題：C=?p(xi)=?128離散無記憶信道（DMC）

對稱離散無記憶信道

準對稱離散無記憶信道

一般離散無記憶信道3.2離散單符號信道的信道容量129輸入對稱如果轉(zhuǎn)移概率矩陣P的每一行都是第一行的置換(包含同樣元素)，稱該矩陣是輸入對稱。輸出對稱如果轉(zhuǎn)移概率矩陣P的每一列都是第一列的置換(包含同樣元素)，稱該矩陣是輸出對稱。對稱信道如果輸入、輸出都對稱。3.2.1對稱離散無記憶信道130對稱DMC信道例子131輸入對稱132如果信道輸入符號等概分布p(ai)＝1/n當轉(zhuǎn)移概率矩陣列對稱時，信道輸出符號p(bj)等概分布－－輸出對稱133例3-2.求信道容量134例3-3.求信道容量信道輸入符號和輸出符號的個數(shù)相同，都為n，且正確的傳輸概率為1－

，錯誤概率

被對稱地均分給n-1個輸出符號，此信道稱為強對稱信道或均勻信道，是對稱離散信道的一個特例。135例3-4.二進制對稱信道（BSC）：當

時，錯誤概率為0，無差錯，信道容量達到最大，每符號1bit，輸入端的信息全部傳輸至輸出端。當

時，錯誤概率與正確概率相同，從輸出端得不到關(guān)于輸入的任何信息，互信息為0，即信道容量為0。對于

的情況，可在BSC的輸出端顛倒0和1，導(dǎo)致信道容量以

點中心對稱。136例3-5.串聯(lián)信道137例3-5.串聯(lián)信道圖3-6m個BSC串聯(lián)信道的互信息串接的信道越多，其信道容量可能會越小，當串接信道數(shù)無限大時，信道容量就有可能趨于零。

138若信道的轉(zhuǎn)移概率矩陣輸入對稱而輸出不對稱，這樣的信道稱為準對稱離散無記憶信道。當輸入等概率時不能確保輸出等概：一般情況下：

3.2.2準對稱離散無記憶信道1391.求極值方法例：求信道容量信道的輸入符號有兩個，可設(shè)p(a1)＝

，p(a2)＝1－

，信道的輸出符號有三個，用b1、b2、b3表示

3.2.2準對稱離散無記憶信道1401.求極值方法因為

，所以應(yīng)有：

p(a1)＝p(a2)＝1/21412.矩陣分解法

將轉(zhuǎn)移概率矩陣劃分成若干個互不相交的對稱的子集，則準對稱DMC的信道容量為：其中，Nk為第k個對稱子矩陣一行元素之和，Mk為第k個對稱子矩陣一列元素之和。

1422.矩陣分解法

1433.觀察法

觀察該矩陣可知，因為p(xi)無論如何分布，p(b3)為恒定值0.2，故要得到最大的H(Y)，b1和b2應(yīng)為均勻分布，即p(b1)=p(b2)=0.4，此時：p(a1)=p(a2)=0.5。

144一般地說，為使I(X;Y)最大化以便求取DMC容量，輸入符號概率集{p(ai)}必須滿足的充分和必要條件是：

當信道平均互信息達到信道容量時，輸入符號概率集{p(ai)}中每一個符號ai對輸出端Y提供相同的互信息，只是概率為零的符號除外。

3.2.2一般離散無記憶信道145離散序列信道

對離散無記憶序列信道：若信道同時還是平穩(wěn)的，則3.3離散序列信道的信道容量1461.信道無記憶的情形例：X1=X2=…=XL=Y1=Y2=…=YL3.3.1信道與信源無記憶情形1472.信源無記憶的情形例：Yi=Xi+1,YL=X1;X1,X2,…，XL互相獨立1483.信源和信道皆無記憶的情形此時，149對離散單符號信道進行N次擴展，就形成了N次離散無記憶信道。3.3.2N次擴展信道BSC的二次擴展信道0010110100011011X

{00,01,10,11}，Y

{00,01,10,11}，二次擴展無記憶信道的序列轉(zhuǎn)移概率p(00/00)=p(0/0)p(0/0)=(1-p)2，p(01/00)=p(0/0)p(1/0)=p(1-p)，p(10/00)=p(1/0)p(0/0)=p(1-p)，p(11/00)=p(1/0)p(1/0)=p2150擴展信道若p＝0.1，則C2＝2－0.938＝1.062比特/序列

151序列轉(zhuǎn)移概率若信道無記憶，則3.3.3獨立并聯(lián)信道圖3-8獨立并聯(lián)信道只有當輸入相互獨立時取等號。152平均互信息

I(X;Y)＝HC(Y)－HC(Y/X)3.4連續(xù)單符號信道的信道容量圖3-9連續(xù)單符號信道y=x+npn(x)＝N(0,

2)153pn(n)＝N(0,

2)，當

pY(y)＝N(0,Po)時取得maxHC(Y)，

pX(x)＝N(0,Ps)，Po=Ps+2C＝1/2log(1+SNR)

信道輸入X是均值為零、方差為PS的高斯分布隨機變量時，信息傳輸率達到最大值。若是加性的，可以求出信道容量的上下界

154

信道輸入隨機序列X＝X1X2…XL，輸出隨機序列Y＝Y(jié)1Y2…YL，加性信道有y=x+n，其中n=n1n2…nL

是均值為零的高斯噪聲

3.5連續(xù)序列信道的信道容量圖3-10多維無記憶加性信道等價于L個獨立并聯(lián)加性信道155連續(xù)單符多維無記憶高斯加性信道就可等價成L個獨立的并聯(lián)高斯加性信道。若

將總功率P如何分配給輸入序列中的各個符號，才能得到最大的信道容量？3.5連續(xù)序列信道的信道容量156噪聲均值為零、方差相同（平均分配，每個符號均值為0，方差為S的高斯變量）

若噪聲均值為零、方差不同，總平均功率受限P，功率則應(yīng)合理分配。最大容量問題即為：3.5連續(xù)序列信道的信道容量157用拉格朗日乘子法構(gòu)造無約束極值問題：各個時刻的信道輸出功率相等設(shè)為常數(shù)

158討論均值為零、方差不同，總平均功率受限P，功率合理分配。159注水法(water-filling)功率分配該功率分配方法，可以形象地描述為圖3-11，如果把噪聲功率看成是容器底部的凸起，把v看成是水平面，則每個子信道上分配的功率，就如往底部有不同凸起的容器中注水，故形象地稱為“注水算法”。圖3-11注水法功率分配160例：有一并聯(lián)高斯加性信道，各子信道噪聲方差為（1）P=5：輸出端總功率

各子信道分配的功率分別是：0.95，0.85，0.75，0.65，0.55，0.45，0.35，0.25，0.15，0.05。（2）P=3？平均輸出功率（水平面）為10.5/10=1.05161限時限頻(fm)高斯白噪聲過程可分解L＝2fmtB維統(tǒng)計獨立的隨機序列

若每個抽樣時刻的噪聲均為零均值、方差為σ2的加性高斯噪聲（W為帶寬，W=fm），則：3.6波形信道的信道容量162信道容量單位時間的信道容量香農(nóng)公式

輸入信號{x(t)}滿足均值為零、平均功率P的高斯白噪聲的特性163帶寬W一定時，信噪比SNR與信道容量Ct成對數(shù)關(guān)系，SNR增大，Ct就增大，但增大到一定程度后就趨于緩慢。增加輸入信號功率有助于容量的增大，但該方法是有限的；降低噪聲功率也是有用的，當N0→0,Ct→∞即無噪聲信道的容量為無窮大。討論

Ct

＝Wlog(1+SNR)單位時間的信道容量圖3-12信道容量與信噪比的關(guān)系164Ct一定時，帶寬W增大，信噪比SNR可降低，即兩者是可以互換的。若有較大的傳輸帶寬，則在保持信號功率不變的情況下，可容許較大的噪聲，即系統(tǒng)的抗噪聲能力提高。無線通信中的擴頻系統(tǒng)就是利用了這個原理，將所需傳送的信號擴頻，使之遠遠大于原始信號帶寬，以增強抗干擾的能力。Ct＝Wlog(1+SNR)比特/秒165Ct/W＝log(1+SNR)比特/秒/Hz，單位頻帶的信息傳輸速率－－頻帶利用率，該值越大，信道就利用得越充分。當SNR=1（0dB），Ct/W=1bit/s/Hz；當SNR=-1.6dB，Ct/W=0bit/s/Hz。（因為此時需要無窮大的的帶寬W）。頻帶利用率圖3-13頻帶利用率與信噪比的關(guān)系166

信源發(fā)出的消息（符號）要通過信道來傳輸，因此要求信源的輸出與信道的輸入匹配。符號匹配：信源輸出的符號必須是信道能夠傳送的符號；信息匹配：當信源與信道連接時，信息傳輸率達到信道容量，則稱信源與信道達到匹配。3.7信道冗余度167

信道冗余度信道絕對冗余度

γ=C－I(X;Y)；信道相對冗余度γ=168信道冗余度冗余度大：信源與信道匹配程度低，信道的信息傳遞能力未得到充分利用；冗余度?。盒旁磁c信道匹配程度高，信道的信息傳遞能力得到較充分利用；冗余度為零，說明信源與信道（信息）完全匹配，即信源概率分布符合最佳輸入分布。一般來說，實際信源的概率分布未必就是信道的最佳輸入分布，所以I(X;Y)≤C，冗余度不為零。本章小結(jié)169第三章主要內(nèi)容結(jié)構(gòu)170本章小結(jié)本章學習思路信道（信息傳輸?shù)耐罚鷮π诺肋M行分類→給出數(shù)學模型→信道的重要參數(shù)：信道容量→按照分類，從簡單到復(fù)雜，研究信道的信道容量。171第4章失真與信息率失真函數(shù)失真的概念和性質(zhì)信息率失真函數(shù)172問題信源熵H(X)的物理含義是什么？為什么要研究信源熵？信源無失真?zhèn)鬏斔璧淖钚⌒畔⒙蕿镽

H(X)；允許信源有失真時，輸出的最小速率可降低為R<H(X)；失真D越大，R可以越小，因此R是D的函數(shù)，且為單調(diào)遞減函數(shù)。R(D)就叫做信息率失真函數(shù)。173限失真編碼的必要性對于連續(xù)信源，因為其熵為無窮大，若要求對其進行無失真編碼，需要用無窮多個比特才能完全無失真地來描述。由于人耳能夠接收的帶寬和分辨率是有限的，因此對數(shù)字音頻，就允許有一定的失真，并且對音樂欣賞沒有影響。可把頻譜范圍從20Hz~8000Hz的語音信號去掉低頻和高頻，保留帶寬范圍300Hz~3400Hz的信號，這種失真是允許的。對于數(shù)字電視，由于人的視覺系統(tǒng)對低頻比較敏感，對高頻不太敏感，且人眼分辨率有限，因此可以在一定限度內(nèi)損失部分高頻分量。174限失真編碼從直觀感覺可知，若允許失真越大，信息傳輸率可越??；若允許失真越小，信息傳輸率需越大。所以信息傳輸率與信源編碼所引起的失真(或誤差)是有關(guān)的。1754.1失真的概念和性質(zhì)X={xi}，xi

{a1,…an}

信源編碼器

Y={yj}，yj

{b1,…bm}失真函數(shù)d(xi，yj)176最常用的失真函數(shù)均方失真：

相對失真：誤碼失真：絕對失真：前三種失真度量適用于連續(xù)信源，后一種適用于離散信源。177失真矩陣

單個符號的失真度的全體構(gòu)成的矩陣，稱為失真矩陣178平均單符號失真

已知p(ai)和d(ai，bj)，平均失真只是符號轉(zhuǎn)移概率p(bj/ai)的函數(shù)。p(bj/ai

)在此實質(zhì)上代表編碼方式。179例：x1

y1x2

y2x1

y1x2

y1180序列失真函數(shù)平均序列失真其中d(Xl，Yl)是編碼前序列中的第l個符號和編碼后序列中的第l個符號之間的失真。

1814.2信息率失真函數(shù)

信源編碼器的目的是使編碼后所需的信息傳輸率R盡量小，R

給定失真的限制值D，使

D，找最小R，

R(D)，定義為信息率失真函數(shù)。4.2.1信息率失真函數(shù)的定義：182p(yj/xi)信源符號編碼概率信道轉(zhuǎn)移概率

將信源編碼器看作信道，信源編碼器輸出的信息率R對應(yīng)到信道，即為接收端Y需要獲得的有關(guān)X的信息量，也就是互信息I(X;Y)。183D允許試驗信道

若p(xi)和d(xi，yj)已定，則可給出滿足條件的所有轉(zhuǎn)移概率分布pij，它們構(gòu)成了一個信道集合PD。稱為D允許試驗信道。184信息率失真函數(shù)R(D)所有的允許試驗信道PD（即滿足

失真要求的所有假想信道）上，最低的輸出信息速率（最有效的信源編碼），就叫做信息率失真函數(shù)。離散無記憶信源：185例4-1：計算平均失真。已知編碼器輸入的概率分布為p(x)=[0.5,0.5]，兩種信源編碼器轉(zhuǎn)移矩陣分別為：定義單符號失真度：186例4-1：計算平均失真。由此可得：由轉(zhuǎn)移概率矩陣，可得：1874.2.2信息率失真函數(shù)的性質(zhì)1.R(D)函數(shù)的定義域和值域

⑴Dmin和R(Dmin)

Dmin＝0

對于連續(xù)信源：

188討論何時Dmin=0?只有當失真矩陣中每行至少有一個零元素。何時R(0)=H(X)?只有當失真矩陣中每行至少有一個零，并每一列最多只有一個零。否則R(0)可以小于H(X)，表示這時信源符號集中有些符號可以壓縮、合并而不帶來任何失真。189定理證明：190證明：1911.R(D)函數(shù)的定義域和值域

(2)

Dmax和R(Dmax)

選擇所有滿足R(D)＝0中D的最小值，定義為R(D)定義域的上限D(zhuǎn)max，即因此可以得到R(D)的定義域為192Dmax=?R(D)＝0就是I(X;Y)＝0，這時試驗信道輸入與輸出是互相獨立的，所以條件概率p(yj/xi)與xi無關(guān)。即需滿足條件193

從上式觀察可得：在j=1，…，m中，可找到

值最小的j，當該j對應(yīng)的pj＝1，而其余pj為零時，上式右邊達到最小，這時上式可簡化成194例4-2：設(shè)輸入輸出符號表為X＝Y(jié)

{0，1}，輸入概率分布p(x)={1/3，2/3}，失真矩陣為求Dmin和Dmax。195解：

當Dmin＝0時，R(Dmin)＝H(X)＝H(1/3,2/3)＝0.91比特/符號，這時信源編碼器無失真，該編碼器的轉(zhuǎn)移概率為196當R(Dmax)＝0時

此時輸出符號概率p(b1)＝0，p(b2)＝1，

所以這時的編碼器的轉(zhuǎn)移概率為

1972.R(D)函數(shù)的下凸性

當給定信源概率分布p(x)時，互信息量I(X;Y)是信道（假想信道）的轉(zhuǎn)移概率p(y/x)的下凸函數(shù)，有極小值，該極小值即為信息率失真函數(shù)：3.R(D)函數(shù)的單調(diào)遞減性

若D>D’,PD

PD’(選擇pij的范圍大)198綜上所述，可以得出如下結(jié)論：R(D)是非負的實數(shù)，即R(D)

0。其定義域為0～Dmax，其值為0～H(X)。當D>Dmax時，R(D)

0。R(D)是關(guān)于D的下凸函數(shù)，因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴格遞減函數(shù)。容許的D越大，所要求的R越小。反之亦然。199由以上三點結(jié)論，對一般信息率失真R(D)曲線的形態(tài)可以畫出來：R(D)H(X)R(D)

0

D

Dmax

DR(D)0Dmax

D

離散信源連續(xù)信源2004.信息率失真函數(shù)與信道容量的比較

信息率失真函數(shù)R(D)信道容量C研究對象信源信道給定條件信源概率分布p(x)信道轉(zhuǎn)移概率p(y|x)選擇參數(shù)信源編碼器編碼方法p(y|x)信源分布p(x)限制條件結(jié)論H(X/Y)=H(X)-I(X;Y)噪聲干擾丟失的信息量編碼壓縮損失的信息量比較項本章小結(jié)201第四章主要內(nèi)容結(jié)構(gòu)202本章小結(jié)本章學習思路失真信源編碼必要性→失真測度函數(shù)→信源編碼器數(shù)學模型→D允許試驗信道→信息率失真函數(shù)→信息率失真函數(shù)性質(zhì)203本章小結(jié)本章學習要點1.失真函數(shù)

均方失真、絕對失真、相對失真、誤碼失真2.平均失真度測量

(1)單符號平均失真：

(2)序列平均失真：204本章小結(jié)本章學習要點3.D允許試驗信道4.信息率失真函數(shù)5.失真函數(shù)的性質(zhì)

下凸性，單調(diào)遞減性

205第5章信源編碼目的：提高通信系統(tǒng)的有效性，即通過編碼，用盡可能短的編碼序列符號來表示原信源序列?；舅枷胧牵?.盡可能去除原消息序列中符號之間的相關(guān)性；2.盡可能使編碼后各符號出現(xiàn)的概率相等。206第5章信源編碼主要解決兩個方面的問題：1.“信源編碼是用盡可能短的編碼序列符號來表示原信源序列”，這個“短”，有沒有極限？如果有，該極限是多少？2.用什么方法達到或者接近該極限？207非分組碼和分組碼將長消息序列按順序分成若干個符號一組，對每一組獨立進行編碼，稱為分組碼；否則稱為非分組碼。定長碼和變長碼若編碼后的碼字長度都相同，則稱為定長碼；否則稱為變長碼。5.1信源編碼的有關(guān)概念5.1.1幾個概念208奇異碼和非奇異碼若編碼前的信源組和編碼后的碼字是一一對應(yīng)的，則稱為非奇異碼；否則稱為奇異碼。非唯一可譯碼和唯一可譯碼如果任意有限長的碼元序列都只能被唯一地分割成一個個的碼字，則稱為唯一可譯碼；否則稱為非唯一可譯碼。5.1信源編碼的有關(guān)概念209非即時碼和即時碼在接收端接收碼元序列的過程中，如果接收到的碼元序列已經(jīng)組成了一個碼字，但接收端并不能立即判斷出，還要等下一個碼字開始接收的時候才能判斷出前者已經(jīng)是一個完整碼字，從而開始譯碼，則稱為非即時碼；反之則稱為即時碼。5.1信源編碼的有關(guān)概念2105.1信源編碼的有關(guān)概念5-1編碼的分類2115.1信源編碼的有關(guān)概念信源符號ai符號出現(xiàn)的概率p(ai)碼1碼2碼3碼4碼5a11/2000011a21/40111101001a31/8100000100001a41/811110110000001例5-1表5-1中的分組碼1、碼2、碼3、碼4和碼5，從上述的4個方面分別判斷屬于什么類型的碼。表5-1碼的不同屬性2125.1.2克勞福特不等式唯一可譯碼存在的充分和必要條件各碼字的長度Ki應(yīng)符合克勞夫特不等式：

其中m是進制，n是信源可能取值的符號數(shù)。213例：設(shè)對符號集{ai,i=1,2,3,4}進行二進制編碼；(1)對應(yīng)的碼長分別為K1＝1,K2＝2,K3＝2,K4＝3，試判斷是否存在這樣的唯一可譯碼；(2)

若K1=1,

K2=2,

K3=3,

K4=3又如何？答：(1)由克勞福特定理可得：因此不存在滿足這種碼長的唯一可譯碼。

214(2)由克勞福特定理可得：因此滿足這種碼長的唯一可譯碼是存在的,例如{0，10，110，111}。

克勞夫特不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。例如，{0,10,010,111}215無失真信源編碼定理定長信源編碼定理變長信源編碼定理限失真信源編碼定理

5.2信源編碼定理2165.2.1無失真信源編碼（香農(nóng)第一定理）X＝(X1X2…Xi…XL)Xi

{a1,a2,…,ai,…,an}

nL種信源編碼器Yk

{b1,b2,…,bj,…,bm}

M=mKL種

KL

logm用Y表示L長的信源序列X，則送出一個信源符號所需要的信息率平均為

編碼目的：使最小。

217無失真信源編碼定理研究的內(nèi)容:最小信息率為多少時，才能得到無失真的譯碼？若小于這個信息率是否還能無失真地譯碼?

無記憶平穩(wěn)信源平均符號熵為HL(X)，對任意

，只要

則當L足夠大時，必可使譯碼差錯概率小于δ；即可實現(xiàn)幾乎無失真編碼；

反之，當時，譯碼差錯一定是有限值，而L足夠大時，譯碼幾乎必定出錯。2181.無失真定長信源編碼定理：碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，當然條件是L足夠大。反之，當時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零。當時，則為臨界狀態(tài)，可能無失真，也可能有失真。219說明：L,,

,δ三者之間有什么關(guān)系？對于給定的

和δ，多大的L算足夠大？220問題：式中

為信源序列的自信息方差，

為一正數(shù)。當

和

2均為定值時，只要L足夠大，Pe可以小于任一正數(shù)

。即，如果給定差錯概率上界δ，則

越小，要求的編碼長度L就越大。L越大，編碼器越復(fù)雜，且時延越大，在有時延要求的場合，往往難以滿足實時性要求。增加

，可以減小對編碼長度L的要求，但以犧牲編碼效率為代價：221討論：222例題5-3：設(shè)離散無記憶信源概率空間為若要求編碼效率為90%，譯碼差錯概率δ≤10-6試求所需要的編碼序列長度L。223例題5-3：自信息方差為：若要求編碼效率η=90%：若要求編碼效率δ≤10-6：當L有限時，要做到高編碼效率、低錯誤率，對于定長編碼來說是不可能做到的。對例5-3中的信源，有8種不同的信源符號取值（a1~a8），如果用二進制序列來表示的話，每個符號需要3

bit（3位二進制數(shù)可以表示8中不同的符號）。但由于不是等概率的，所以其熵H(X)=2.55

bit，按照無失真定長信源編碼定理，其極限編碼長度是2.55bit，而，也就是說，只能表示5.856種不同的符號，其余的符號怎么辦？實際上，由于a1~a8中部分符號的概率較小，如果序列長度L足夠大，則總有某種序列出現(xiàn)的概率足夠小，對這些概率足夠小的序列，如果不設(shè)計對應(yīng)的編碼碼字，造成的錯誤概率也非常小。224思考：2252.無失真變長信源編碼定理：平均碼長：定長編碼中，由于所有的碼字都使用相同的長度，限制了其靈活性，導(dǎo)致或者效率不高，或者復(fù)雜度太高（L太大）。變長編碼可以對出現(xiàn)概率大的信源盡量用短碼，從而提高編碼效率.（統(tǒng)計匹配）2262.無失真變長信源編碼定理：(1).單符號變長編碼定理若離散單符號信源X：xi∈{a1,a2,…,an}的熵為H(X)，對每個單符號進行無失真變長編碼，設(shè)yj∈{b1,b2,…,bm}。則227(2).離散平穩(wěn)無記憶序列變長編碼定理

對于平均符號熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中

為任意小正數(shù)。228例題5-4：設(shè)離散無記憶信源概率空間為試討論其編碼效率。若L=1,用二元定長編碼(0，1)來構(gòu)造一個即時碼：x1→0，x2→1。平均碼長＝1二元碼符號/信源符號

編碼效率為輸出的信息率為229（續(xù)）例題5-4：若對長度為L=2的信源序列進行變長編碼，其即時碼如表5-2所示。230（續(xù)）例題5-4：xip(xi)即時碼x1x19/160x1x23/1610x2x13/16110x2x21/16111表5-2長度為2的信源序列對應(yīng)的即時碼該碼平均長度：單符號平均碼長：編碼效率為：231（續(xù)）例題5-4：232（續(xù)）例題5-4：L＝3

η3=0.985

R3＝0.985比特/二元碼符號

L＝4

η4=0.991

R4＝0.991比特/二元碼符號

233（續(xù)）例題5-4：定長二元碼編碼，要求編碼效率達到96％時，允許譯碼錯誤概率δ≤10-5

。2345.2.2限失真信源編碼（香農(nóng)第三定理）

信息率失真函數(shù)給出了失真小于D時所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D。

限失真信源編碼定理：對于任意的D≥0和

＞0，當信息率R>R(D)時，一定存在一種編碼方法，其譯碼失真小于或等于D+

，條件是編碼的信源序列長度L足夠長。反之，如果R<R(D)，則無論采用什么編碼方法，其譯碼失真必大于D。2355.2.2限失真信源編碼（香農(nóng)第三定理）香農(nóng)第三定理是一個存在性定理，它只說明一定存在一種滿足要求的編碼方法。至于如何尋找這種最佳壓縮編碼方法，定理中沒有給出。在實際應(yīng)用中，該理論主要存在以下兩類問題：（1）符合實際信源的R(D)函數(shù)的計算相當困難；（2）即使求得了符合實際的信息率失真函數(shù)，還需要研究采用何種編碼方法，才能達到或接近極限值R(D)。2365.2.2限失真信源編碼（香農(nóng)第三定理）237香農(nóng)編碼哈弗曼編碼算術(shù)編碼（非分組碼）

5.3常用信源編碼方法2385.3.1

香農(nóng)編碼將信源消息符號按其出現(xiàn)的概率大小依次排列確定滿足下列不等式的整數(shù)碼長Ki

5.3常用信源編碼方法239香農(nóng)編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進制數(shù)。取Pi二進數(shù)的小數(shù)點后Ki位即為該消息符號的二進制碼字。

5.3常用信源編碼方法240香農(nóng)編碼為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進制數(shù)。取Pi二進數(shù)的小數(shù)點后Ki位即為該消息符號的二進制碼字。

241香農(nóng)編碼

香農(nóng)編碼的基本做法：是把長度為1的整個累積概率區(qū)間，按照信源符號集中q個信源符號的概率大小，分成q份不同長度的子區(qū)間（每份子區(qū)間的長度正比于對應(yīng)符號的概率大?。瑢⒚糠N信源符號xi，映射到其對應(yīng)子區(qū)間上的一個點。這樣，每個信源符號xi映射區(qū)間都是不重疊的，從而可以保證唯一可譯碼，而且可以證明，也是即時碼；另一方面，碼字長度由其概率決定，概率大的用短碼。

242香農(nóng)編碼

例5.4設(shè)信源共7個符號消息

信源消息符號ai符號概率p(ai)累加概率Pi-logp(ai)碼字長度Ki碼字a10.200