■《數字通信原理》(第3版)（第4章）1第

4

章

信息論基礎2本章的基本內容：信息的度量方法；離散信道及容量；連續信源、信道及容量；信源編碼的基本方法；信道編碼的基本方法；率失真理論。3n4.1

引言4消息與信息n

1948年，美國科學家香農的論文《通信的數學理論》，n

奠定了信息論的理論基礎。n 消息與信息(1)消息是由符號、文字、數字、語音或圖像組成的序列；nn

(2)消息是信息的載體，信息是消息的內涵；消息中可能包n

含信息，也可能不包含信息；n

(3)收到一則消息后，所得的信息量，在數量上等于獲得n

消息前后“不確定性”的消除量；nn(4)通信的目的在與傳送信息。n第4章信息論基礎5消息與信息(續)■通信系統傳遞信息的機制和本質■形式化：通信的基本任務是在接收端把發送端發出的消息從形式上恢復出來，而對消息內容的理解和判斷，不是通信的任務。■非決定論：通信過程傳遞的消息中所包含的內容，對接收者來說事先是無法預料的。■不確定性：是指收到該消息之前，對其中的內容出現與否，具有不確定的因素；這種不確定的因素可以通過通信來加以消除或部分消除。n第4章信息論基礎6n4.2

信息的度量7信息度量的概念n(1)某消息的信息量＝獲得該消息后不確定性的消除量；不確定性

可能性 概率問題：nnn(2)信息量可用概率的某種函數來度量不同的消息有信息量的多少的區別，因此nnn信息的度量方式應滿足信息量的可加性信息量應該是滿足可加性的概率的函數。n第4章信息論基礎離散信源信息的度量離散信源的信息量離散信源統計特性的描述方法－－概率場nn

設離散信源包含N種可能的不同符號，相應的概率場可表述為nn

概率場應滿足條件：nn第4章信息論基礎8離散信源的信息量(續)信息量作為概率的函數，具有形式n與統計獨立，滿足可加性要求n

若nnn

如定義n

直觀地，概率越小的事件一旦出現，提供的信息量越大。n

顯然有n可同時滿足是概率的函數和可加性兩個要求。n第4章信息論基礎9離散信源信的息量(續)n 定義離散消息xi的信息量:nn信息量的單位與對數的底有關：nlog以2為底時，單位為比特：bitnlog以e為底時，單位為奈特：nitnnnlog以10為底時，單位為哈特，hart一般在沒有特別聲明時均假定信息的單位為比特。n第4章信息論基礎10離散信源信的息量(續)n

示例：已知某信源的概率場為nn息量輸出的各符號統計獨立，計算序列S：“113200”，的信nn第4章信息論基礎11離散信源的平均信息量：信源的熵離散信源的熵如何描述或度量一個信源輸出信息量的大小？何種類型的信源輸出的信息量最大？定義4.2.2

離散信源 的熵nn

熵是信源在統計意義上輸出的每個符號的平均信息量。n

熵較大的信源，輸出同樣個數n

的符號，所含的信息量更大。n第4章信息論基礎12離散信源的熵(續)示例：求離散信源的熵。nn

按照定義：nn熵的單位：比特/符號n第4章信息論基礎13離散信源的熵(續)示例（續）：若上述離散信源發送獨立的符號序列：201

020

130

213

001

203

210

100

321

010023

102

002

10

312

032

100

120

210(1)求總的信息量；(2)利用熵估計總的信息量。解：(1)■■n(2)n

隨著符號序列的增大，兩者趨于相同。n第4章信息論基礎14離散信源的最大熵定理定義4.2.3凸集對任意，有定義4.2.4

若■型凸函數(下凸函數)■型凸函數(上凸函數)n第4章信息論基礎15離散信源的最大熵定理(續)若函數為若函數為型凸函數(下凸函數)，則一定存在最小值型凸函數(上凸函數)，則一定存在最大值■■型凸函數示例■n第4章信息論基礎16離散信源的最大熵定理(續)若是一組概率；是一個 型凸函數，則一般地有如下的關系式■■利用上面的關系式，可以證明如下的定理定理4.2.5

熵函數 是概率的 型凸函數。(上述關系式的證明過程參見教材)物理意義：一定存在一組概率，使得熵取最大值。n第4章信息論基礎17離散信源的最大熵定理(續)定理4.2.6當離散信源X取等概分布時，其熵值。取最大n

(證明過程參見教材。)n

物理意義：當信源取等概分布時，具有最大的不確定性。n示例：兩個信源符號的情形。P(x1)=p,P(x2)=1-p當p=1/2時，H(X)=Hmaxnnnnn等概的二元信源，每個符號可攜帶1比特信息。n第4章信息論基礎18離散信源的最大熵定理(續)定理4.2.6告訴我們：如果對信源的符號/碼元進行某種變化，使得變換后的符號集具有等概或近似等概的特性，可使得每個符號/碼元可攜帶最大的信息量。（不要與下面的概念混淆：對消息（語音、圖像等各類信號）的處理后得到的結果，只會有可能減少該消息的信息量，而不會增加信息量。）n第4章信息論基礎1n19離散信源的聯合熵與條件熵兩隨機變量的概率場n

滿足條件：n第4章信息論基礎20離散信源的聯合熵與條件熵(續)兩隨機變量的聯合熵在通信系統中，常常需要同時考慮兩個或兩個以上隨機變量。定義4.2.3兩隨機變量的聯合熵■如兩隨機變量統計獨立，有n第4章信息論基礎21兩隨機變量的聯合熵(續)對于統計獨立的兩隨機變量，不能從其中一個獲得有關另外一個的任何信息。兩隨機變量的條件熵兩隨機變量已知

后，

出現的概率稱為條件概率，記為■同理。已知后，

條件概率為在已知某個隨機變量的情況下，另一隨機變量仍包含的信息量（不確定性）為

或n第4章信息論基礎22離散信源的聯合熵與條件熵(續)兩隨機變量的條件熵定義4.2.4兩隨機變量的條件熵■一般地有(利用稍后的平均互信息量的非負性可以證明)一般地(具有某種相關性的兩隨機變量)，一個隨機變量的出現總是有助于降低另一隨機變量的不確定性。n第4章信息論基礎2324n4.3

離散信道及容量離散信源及容量信道模型■信道的輸入：信道的輸出：狹義信道的概念：物理傳輸信道，如無線信道，電纜光纖等；信道可以更一般化和廣義化，如記錄與重放等經歷的過程。離散信道模型(特性)可用其轉移概率來描述n第4章信息論基礎25離散信源及容量(續)離散信道模型■離散信道模型(特性)可用其轉移概率來描述，一般地有■■輸出不僅與當前的輸入有關，而且與之前的若干個輸入值有關，呈現某種“記憶”效應。在許多情況下，信道輸出主要只與當前的輸入有關：這類信道稱為無記憶信道。本課程主要討論無記憶信道。離散信道模型可以看作是屏蔽了物理信道細節的統計模型。n第4章信息論基礎26離散信源及容量(續)離散無記憶信道的轉移矩陣 輸出僅與當前的輸入有關■■■：當發送xi

時，收到yj

的概率。離散無記憶信道的后驗概率矩陣n第4章信息論基礎n當收到yj

時，發送是xi的概率27離散無記憶信道的轉移矩陣(續)示例：二元的離散無記憶信道■■發“0”和發“1”時能正確接收的概率為0.99，錯誤的概率為0.01。即有轉移矩陣■n第4章信息論基礎28離散信源及容量互信息量后驗概率是一種條件概率，在通信系統中可表示收到

后，發送端發送的是符號

的概率。接收端收到

后，關于

仍存在的不確定性可表示為■顯然

越大，不確定性就越小。定義4.3.1互信息量為：互信息量為收到后，關于的不確定性的消除量。n第4章信息論基礎29互信息量(續)互信息量具有對稱性互信息量的性質(1)若(2)若(3)若(4)若n第4章信息論基礎30離散信源及容量(續)平均互信息量定義4.3.2平均互信息量為：平均互信息量具有非負性(證明參見教材)表明：從統計上來說，兩相關聯的隨機變量集，其中一個集中符號的出現總是有利于提供有關另外一個集的信息。n第4章信息論基礎31離散信源及容量(續)平均互信息量具有非負性：證明：因為對數函數是一個型凸函數，由凸函數有關特性有由此可得進而可得n第4章信息論基礎32離散信源及容量(續)熵函數與平均互信息量間的關系等■n第4章信息論基礎33熵函數與平均互信息量間的關系(續)n 當信源X與Y統計獨立時n

(1)兩個符號同時出現時提供的平均信息量等于每個符號的平均信息量之和；n

(2)一個符號不能提供有關另一符號的任何信息。n第4章信息論基礎34熵函數與平均互信息量間的關系(續)n 當兩個信源相關時n

(1)聯合熵小于兩個信源的熵的和:nn

(2)平均互信息量等于兩信源熵重合的部分；n

(3)信源的條件熵等于其自身的熵減去平均互信息量：n第4章信息論基礎35離散信道的容量n

已知信道的轉移矩陣n 信源符號集：

； 符號傳輸速率：n

系統的平均信息速率為：n平均信息速率由信源統計特性和信道特性（轉移概率）決定。n第4章信息論基礎36離散信道的容量(續)nn 定義4.3.3離散信道的最大信息傳輸速率為其信道容量n(因為通常

是常數，人們在討論問題時通常將其省略)n 匹配信源的概念n

信道容量由信道特性和信源的統計特性共同決定。

n

信道特性確定之后，其容量由信源的統計特性決定。nnnnn匹配信源：能使單位時間內信道可傳輸的平均信息量達到信道容量的信源稱之。記匹配信源的分布特性：信道容量：n第4章信息論基礎37離散信道的容量(續)匹配信源(續)已知信道轉移概率，匹配信源統計特性的求解約束條件求

使得由拉格朗日求極值的原理：定義輔助方程令達到最大。可得信源分布特性應滿足的條件n第4章信息論基礎38離散信道的容量(續)匹配信源(續)若取得其解為：則可得最大的平均互信息量為由上述兩組關系式可得整理可得n第4章信息論基礎39離散信道的容量(續)匹配信源(續)記可得若已知信道轉移概率可求解由此可進一步得利用概率約束條件：n第4章信息論基礎40離散信道的容量(續)匹配信源(續)由此可得關于信源分布特性的方程組：求解該方程組，即可得能夠達到信道容量的信源統計特性。n第4章信息論基礎41離散信道的容量(續)n

由此可導出匹配信源統計特性的求解步驟：n

(1)解方程組n

求解得n

(2)求最大平均互信息量：n

(3)求相應后驗概率：n

(4)解方程組，nn確定匹配信源的分布特性n第4章信息論基礎42離散信道的容量(續)n

示例：求匹配信源的統計特性。已知信道轉移概率n

(1)解方程組得中間結果參數：nn(2)求最大平均互信息量：n

(3)求相應后驗概率：nn第4章信息論基礎43n離散信道的容量(續)n

示例(續)：n

(4)獲得匹配信源統計特性：n

(5)信道容量為：nn

注：若求解過程中出現n

，重新求解。n，可在方程組中令n第4章信息論基礎44離散無記憶對稱信道的容量(續)n 離散無記憶對稱信道

(定義)：n

轉移矩陣n轉移矩陣各行各列均具有相同的元素集的信道稱之。n

離散無記憶對稱信道滿足條件：n

對矩陣中任意的列元素，有n對矩陣中任意的行元素，有nn第4章信息論基礎45離散無記憶對稱信道的容量(續)n 離散無記憶對稱信道特性：n

(1)離散無記憶對稱信道的條件熵滿足：n

因為：n 條件熵關。僅由信道特性決定，與信源的統計特性無n第4章信息論基礎46離散無記憶對稱信道的容量(續)n 離散無記憶對稱信道特性：nn

(2)若輸入信道的信源符號等概nnnn則信道的輸出符號也等概n第4章信息論基礎47離散無記憶對稱信道的容量(續)n 信道容量：nn 對于離散無記憶對稱信道，若要使信息傳輸速率達到信道容量，要求信源的符號等概分布。n

對于非等概的信源，可設法對其輸出的符號進行適當的組合/變換，使得重新構建后的符號(信源)，具有近似等概的分布特性。n

(參見“信源的等長編碼”一節)n第4章信息論基礎4849n4.4

連續信源、信道及容量連續信源、信道及容量連續信源的相對熵離散信道可以看作一種抽象的信道，對符號進行判決后統計的的結果，實際的物理信道是一種連續的信道。若已知隨機信號

幅度取值的概率密度函數：取值在任意小區間內的概率■(參見示意圖)連續信源轉變為具有n個隨機變量的信源，且有利用離散隨機變量熵的定義，得n第4章信息論基礎50連續信源、信道及容量(續)連續信源的相對熵■概率密度函數的離散化示意圖，輸入的取值范圍n第4章信息論基礎51連續信源的相對熵(續)連續信源的熵應為■可見連續信源的熵無限大。該熵稱為連續信源的絕對熵。連續信源的絕對熵，無法確切地定義。通常上式的第一項是有限值，且稍后可見其具有特定的物理意義。n第4章信息論基礎52連續信源的相對熵(續)定義4.4.1連續信源的相對熵為示例某信號的相對熵為信號經2倍幅度放大后的相對熵為信號的簡單放大并沒有增加任何新的信息，但其相對熵發生了增大的變化，這說明：■相對熵已經不再具有信源平均信息量的內涵。n第4章信息論基礎53連續信源的相對條件熵對于連續隨機變量，同樣可以導出其條件熵可見連續信源的條件熵取值無限大，同樣無法確切定義。但通常上式的第一項是一個有限取值的量。連續信源的熵和條件熵均取值無限大，說明要在一個容量有限的通信系統中傳遞連續信源的全部信息是不可能的。n第4章信息論基礎54連續信源的相對條件熵(續)定義4.4.3連續信源的相對條件熵因為：說明相對熵和相對條件熵的差值與普通的熵和條件熵的差值一樣，仍然等于平均互信息量。同理可以導出：n第4章信息論基礎55連續信源相對熵的最大化是信源概率密度函■定理4.4.3連續信源的相對熵函數數

的 型凸函數。相對熵作為概率密度函數的函數存在最大值。(上述結論的證明需要用到泛函的數學知識，泛函研究函數的函數問題。)n第4章信息論基礎56連續信源相對熵的最大化重要結論：利用泛函分析的方法可以證明：若

和

是任意兩個取值均在區間的概率密度函數。則有的連續隨機變量對于某，若成立則有最大的相對熵由此可得各種不同條件下達到最大相對熵的條件。n第4章信息論基礎57連續信源相對熵的最大化(續)(1)峰值功率受限情況下的相對熵最大化條件當連續信源的概率密度函數服從均勻分布時，該連續信源有最大的相對熵。在區間

均勻分布連續信源

的概率密度函數為的任意的峰值功率受限的信號，假定同樣分布在區間其分布為一般地，有由此可得n第4章信息論基礎58連續信源相對熵的最大化(續)(1)峰值功率受限情況下的相對熵最大化條件當連續信源的概率密度函數服從均勻分布時，該連續信源有最大的相對熵。在區間

均勻分布連續信源

的概率密度函數為其相對熵為最大相對熵峰值受限信號因為n第4章信息論基礎59連續信源相對熵的最大化(續)(2)均值受限情況下的相對熵最大化條件同理可證明：當連續信源的概率密度函數服從指數分布時，該連續信源有最大的相對熵。均值受限信號對指數分布相對熵為最大相對熵n第4章信息論基礎60連續信源相對熵的最大化(續)(3)平均功率受限情況下的相對熵最大化條件同樣可證明：當連續信源的概率密度函數服從高斯分布時，該連續信源有最大的相對熵。平均功率受限信號對高斯分布有最大相對熵因為高斯分布的信號具有廣泛的代表性，因此平均功率受限的場景在通信中作為最常用和基本的假設。n第4章信息論基礎61加性高斯噪聲信道的容量加性高斯噪聲(干擾)信道(AWGN)（說明研究AWGN的意義）加性高斯噪聲：信道輸入：

信道輸出：已知通過信道后，從

可獲得的關于

的平均互信息量若已知信號

的帶寬為

。則無失真無冗余的抽樣頻率應為：對任意的這類信號(單位時間的樣點數)單位時間內傳輸的信息量，即信息速率為n第4章信息論基礎62加性高斯噪聲信道的容量(續)加性高斯噪聲(干擾)信道(AWGN)的信道容量信號與噪聲間的關系可用方程組表示為或二維函數概率密度間的關系稱為雅可比行列式n第4章信息論基礎63加性高斯噪聲信道的容量(續)對于加性噪聲與信號間的關系因為所以有即：若已知信源x的統計特性，收到y后不可確定的部分為■噪聲的影響所導致。n第4章信息論基礎64加性高斯噪聲信道的容量(續)■因此可得n第4章信息論基礎65加性高斯噪聲信道的信道容量(續)因為(1)在均方受限的條件下，高斯分布的信源有最大的相對熵(2)

兩高斯分布的隨機變量之和(

)仍為高斯隨機變量(3)

信號

與噪聲

統計獨立因而有n第4章信息論基礎66加性高斯噪聲信道容量(續)信道容量若記得香農公式(香農信道容量定理)n第4章信息論基礎67加性高斯噪聲信道容量(續)由香農公式(香農定理)得到的重要結論：nn (1)信道容量C隨S/N增大而(關于對數)增大；n (2)C一定時，W與S/N之間可以彼此互換；n (3)N 0,C

∞：無擾信道的容量為無窮大；n (4)

對受高斯噪聲干擾的信道，當

W ∞，信道容量趨于n 一個正比于信號功率、反比于噪聲功率密度譜的確定值：nn第4章信息論基礎68信道容量和帶寬的歸一化分析歸一化信道容量：單位時間單位頻帶內可達到的信息速率。注：所謂物理不可■實現是指不可能實現無差錯傳輸。■■n第4章信息論基礎69信道容量和帶寬的歸一化分析(續)歸一化信道帶寬：單位信息速率所需要的最小帶寬。n第4章信息論基礎70信道容量和帶寬的歸一化分析(續)關于Eb/N0的歸一化信道帶寬Eb：比特能量；N0：噪聲功率密度譜；■當Eb/N0<－1.59dB時，無法實現無差錯的傳輸。■■■n第4章信息論基礎71信道容量和帶寬的歸一化分析(續)■香農定理指出了給定帶寬的加性高斯噪聲干擾信道、已知信號平均功率和噪聲平均功率的情況下可能獲得的最高信息傳輸速率。香農定理給出的容量公式計算所得的是(兩點間)信息速率的上限；香農定理并沒有告訴人們如何才能實現達到信道容量的信息傳輸速率。n第4章信息論基礎7n7273n4.5

信源編碼的基本方法74信源編碼的基本方法信源編碼的目的：提高傳輸/存儲效率（1）去除消息中的冗余度，使傳輸的符號盡可能都是獨立的，沒有多余的成分(如語音、圖像信號壓縮)；（2）使傳輸的符號所含的信息最大化。例如，通過編碼使符號以等概分布的形式出現，使每個符號可能攜帶的信息量達到

最大；（3）提高編碼(傳輸)效率。采用不等長編碼，讓出現概率大的符號用較短的碼元序列表示，對概率小的符號用較長的碼元

序列；(4)在允許一定失真的條件下，如何實現高效率的編碼。n第4章信息論基礎離散無記憶信源(DMS:Discrete

Memoryless

Source） 離散無記憶信源的輸出序列：各個符號間彼此獨立其中反之，若輸出的各符號間有一定的相關性，則其為一種有記憶的信源。有記憶的信源，經過處理后，有可能變為一種無記憶或近似無記憶的的信源。如：有記憶的信源，經過理想的、完全去除冗余的壓縮編碼后產生的輸出。n第4章信息論基礎75■(信源符號集)編碼輸出其中■為輸出的碼元集。接收端的譯碼輸出n第4章信息論基礎離散無記憶信源編碼與譯碼■在通信過程中往往需要將信源輸出的符號變換成便于傳輸的碼字若將信源輸出的符號按每J

個為一組進行編碼，則任意的第m個分組可以表示為76離散無記憶信源編碼與譯碼(續)■將待編碼碼組簡單記為編碼輸出碼組(碼字)簡單記為譯碼后，存在雖然經過的是無擾信道，但仍存在的可能性，是因為編碼后的碼字，有可能不是唯一可譯的。n第4章信息論基礎77離散無記憶信源編碼與譯碼(續)■定義4.5.1若對信源的每個不同的符號或不同的符號序列，編■碼后產生的碼字不同，則稱該碼為唯一可譯碼。J

個待編碼的符號序列的不同組合個數為碼字集中不同的碼字個數編碼輸出為唯一可譯碼的(必要)條件對于碼元取自

，碼字長度為一個碼字，其最大可攜帶的信息量(由最大熵定理)為n第4章信息論基礎78離散無記憶信源編碼與譯碼(續)定義4.5.2編碼表示一個信源符號所需的平均信息量的定義為編碼速率

。碼字長度為常數的編碼稱為等長編碼，反之稱為不等長編碼。對長度為

的信源符號序列進行編碼：等長編碼的編碼速率不等長編碼的編碼速率中

為不等長編碼的平均碼長。n第4章信息論基礎79離散無記憶信源編碼與譯碼(續)定義4.5.3

信源的熵 與編碼速率率的比值定義為編碼效■要保證編碼(后譯碼)沒有信息丟失，要求n第4章信息論基礎80離散無記憶信源的等長編碼*等長編碼：對信源的每個符號，或每組符號，用長度相等的代碼來表示。單個符號獨立編碼

采用

進制碼元編碼若信源符號集有L

種符號，要保證譯碼的惟一性，由碼字長度應取■■取整得■■編碼效率：■n第4章信息論基礎81離散無記憶信源的等長編碼(續)擴展編碼(聯合編碼)：將J個信源符號進行聯合編碼由譯碼唯一性要求取整得平均每個符號所需的碼元數J

取值的增大有利于效率的提高。n第4章信息論基礎82

離散無記憶信源的等長編碼(續)信源統計特性對編碼效率的影響例4.5.1采用二進制碼元分別對J＝4的兩信源符號序列進行編碼。（假定僅考慮譯碼的唯一性。）信源1：因為故可取平均每個符號的碼元數編碼效率n第4章信息論基礎83離散無記憶信源的等長編碼(續)信源2：同理有取平均每個符號的碼元數編碼效率n第4章信息論基礎84離散無記憶信源的等長編碼(續)■■來自同樣符號集，但不同統計特性的信源，因其熵■可能不同。編碼效率■可以差異很大。n第4章信息論基礎85■離散無記憶信源(DMS)的有損等長編碼一種考慮信源統計特性的編碼 信源符號集■■■■■得■由最大熵定理由熵的定義，可知由譯碼的唯一性要求可得碼組長度應滿足條件由其中n第4章信息論基礎86離散無記憶信源(DMS)的有損等長編碼一種考慮信源統計特性的編碼(續)對任意統計特性的信源，要獲得較高的編碼效率，即在

足夠小的情況下，使成立■通常J

取值要非常大，方能實現。■理論上，只有：下面考慮有損的等長編碼。方可實現無損的等長編碼。n第4章信息論基礎87離散無記憶信源(DMS)的有損等長編碼對于長度為J

的DMS碼組(一組符號序列):碼組中的每個符號：由符號間的獨立性，有碼組

包含的信息量為：根據熵的定義，隨著J

的增大，有■或可以證明當J

足夠大時，有n第4章信息論基礎88離散無記憶信源(DMS)的有損等長編碼(續)即：定義

4.5.4－典型序列集：滿足下列條件的序列的集合稱之。其中

。當J

足夠大時，可取一個較小的正數，以保證其典型性。－非典型序列集：典型序列集的補集稱之。記為典型序列集和非典型序列集構成了序列構成該符號序列的整個空間：所有組合；n第4章信息論基礎89離散無記憶信源(DMS)的有損等長編碼(續)定理4.5.1(信源劃分定理)：任給有，當J

足夠大時,即有：證明：對于消息序列其符號信息量

的方差■由概率論中的弱大數定理，任給n第4章信息論基礎90離散無記憶信源(DMS)的有損等長編碼(續)由此可得對于任給的，當J

足夠大時，有即當J

足夠大時，因而有n第4章信息論基礎91離散無記憶信源(DMS)的有損等長編碼(續)典型序列出現的概率：若因為由

，可得即當J

足夠大時，有：即，典型序列趨于等概分布。同樣可證，典型序列的數目：n第4章信息論基礎92離散無記憶信源(DMS)的有損等長編碼(續)典型序列的出現概率：即：典型序列集非典型序列集為高概率集；

為低概率集。n第4章信息論基礎93離散無記憶信源(DMS)的有損等長編碼(續)典型序列集在整個序列空間中所占的比例：在一般情況下，可選擇，使滿足因此說明雖然典型序列集是一個高概率集，但其數目在整個序列空間中可能只占很小的比例；■n第4章信息論基礎94離散無記憶信源(DMS)的有損等長編碼(續)■典型序列集的形象說明■研究典型序列集特性的意義：如果容許一定的失真，只對典型序列編碼，對非典型序列不予編碼傳輸，碼字長度可大大縮短，從而有效提高傳輸效率。n第4章信息論基礎95離散無記憶信源(DMS)的有損等長編碼(續)例4.5.2：已知二元信源信源的熵為：所有的序列構成的集合為n第4章信息論基礎96離散無記憶信源(DMS)的有損等長編碼(續)示例(續)：(1)若取由平均信息量落在該范圍內的序列(典型序列)為■其概率和■n第4章信息論基礎97離散無記憶信源(DMS)的有損等長編碼(續)示例(續)：(2)若取由平均信息量落在該范圍內的序列(典型序列)為■所占據的比例31.25%，其概率和■n第4章信息論基礎98離散無記憶信源(DMS)的有損等長編碼(續)可達速率的概念譯碼錯誤概率定義為定義4.5.5可達速率給定信源和編碼速率R，對任意的和編碼譯碼方法：

、若存在使當

時，有

則該編碼速率稱為可達的反之稱速率是不可達的。前面已經定義編碼速率：n第4章信息論基礎99離散無記憶信源(DMS)的有損等長編碼(續)定理

4.5.2■若若，則速率R

是可達的；，則速率R

是不可達的。■該定理說明，若

，則存在編碼方法，保證典型序列的譯碼具有唯一性。當J

足夠大時，只需對典型序列進行編碼，可使編碼誤差足夠地小。定理的物理意義是：只有用于承載每個符號信息的平均比特數大于等于信源的熵，才能使譯碼的誤差任意地小。n第4章信息論基礎100離散無記憶信源(DMS)的有損等長編碼(續)分析在滿足一定的譯碼錯誤概率的條件下，若只對典型序列編碼，如何確定編碼長度：■滿足關系式若記：編碼速率：自信息方差：則不能正確譯碼的概率(參見信源劃分定理證明)■■根據上式，可確定編碼序列的長度J

。n第4章信息論基礎101離散無記憶信源(DMS)的有損等長編碼(續)示例：(1)對熵等于0.722信源的二元符號進行無差錯的■二進制編碼此時

、■、(2)若要求編碼效率，■求所需的編碼序列長度J由■■得n第4章信息論基礎102離散無記憶信源(DMS)的有損等長編碼(續)自信息方差：最后得所需的符號序列長度（編碼輸出一個碼組大小）約1兆個字符組成一個碼組。該取值太大，工程上難以實現。可見高效率的等長編碼不易在實際系統中應用。n第4章信息論基礎103不等長編碼的基本概念■定義4.5.6若碼中每個碼字都含有一個特定的符號用于標識 一個碼字的起點，則稱這種碼為逗點碼。■例：0，01，011，0111

為逗點碼。定義4.5.7

對任一碼字

，稱該碼字的前面

位■，

，為碼字

的長為

的字頭或前綴。■定義4.5.8若碼字集中任一碼字都不是另一碼字的字頭，則 稱這種碼為異字頭碼，或異前綴碼。■定義4.5.9對具有若符號

用個元素的信源符號集：元碼編碼后輸出的碼字長度為

，則定■義信源符號的平均碼字長度為：n第4章信息論基礎104異字頭不等長編碼異字頭碼的優點：異字頭碼譯碼時具有即時性，即當收到一個完整的碼字后即可譯碼，不用擔心這一碼字是另一碼字的字頭部分。異字頭碼的編碼樹：異字頭碼的編碼可用編碼樹來描述n第4章信息論基礎105n第4章信息論基礎異字頭不等長編碼(續)n（1）從根朝下，第一級有

個節點；第二級有個節點；如此類推，第r

級有個節點。n（2）從任一節點引出的分支有1，2，…，－1來標記。個，從根開始，可分別用0，n（3）不再發出分支的節點稱為端節點，若用端節點表示不同的信源符號，取相應的從第一級到該節點的標號序列為碼字，則必能保證碼字的異字頭條件。n（4）若各分支均延伸到最高級的各端點，則可構成一棵對稱的樹，稱為滿樹，否則稱為非滿樹。106n第4章信息論基礎異字頭不等長編碼(續)異字頭碼的編碼原則編碼時應盡可能地使碼字中的任一碼元載荷達到其最大的信息量：

。應使每個節點發出的

種分支出現的概率盡可能相等。異字頭碼的編碼方法將信源符號分成盡可能等概的個子集，與碼樹的第一級的D個節點對應；對每個子集按同樣的方法又分為個二級子集，與碼樹的第二級D個節點相對應；以此類推，直至子集不能再分為止。107n第4章信息論基礎異字頭不等長編碼(續)示例：對信源符號集做解：的三進制異字頭不等長編碼。108n第4章信息論基礎不等長編碼的基本定理*定理4.5.3

對具有L個符號的信源符號集：，其相應的長度為

的元異字頭碼存在的充要條件是如下的不等式成立

(D

為碼元的個數)即：當滿足條件

時，一定存在與該碼字對應的編碼樹。定理4.5.4唯一可譯碼必滿足(Kraft)不等式：(定理4.5.4）系：任一唯一可譯碼可用相應的碼字長度一樣的異字頭碼代替。即：任一唯一可譯碼可用相應的碼字長度一樣的異字頭碼代替，而不改變該碼的任何性質。109n第4章信息論基礎不等長編碼的基本定理*(續)n定理4.5.5

（不等長編碼定理）n（1）若

是組成碼字的元素的個數，則任一唯一可譯碼的平均碼長滿足：nn（2）存在有元的可譯碼，其平均長度n定理4.5.5告訴我們不等長編碼應該唯一可譯平均碼長應該滿足條件110n第4章信息論基礎不等長編碼的基本定理*(續)多個符號的聯合不等長編碼記：信源符號集：待編碼的符號序列(符號分組)：■特定符號序列符號序列編碼后輸出的碼字長度編碼后的平均碼字長度符號序列

的熵函數則由定理4.5.5，相應地，若滿足則存在使得符號序列唯一可譯的編碼。111n第4章信息論基礎不等長編碼的基本定理*(續)定義4.5.15 對

J

個信源符號進行不等長聯合編碼時平均一個信源符號的編碼長度定義為■由前面的討論可得■112n第4章信息論基礎不等長編碼的基本定理(續)離散無記憶信源的擴展信源的編碼的效率以J

個離散無記憶信源符號為一組可構成一個擴展信源擴展信源的熵函數為由前面的對J

個信源符號進行不等長聯合編碼分析，可得可見對擴展后的離散無記憶信源的編碼有利于提高編碼效率。且有113n第4章信息論基礎不等長編碼的基本定理(續)定義4.5.11不等長碼的編碼速率定義為■是平均每個信源符號編碼時所需的碼元的個數； 是每個碼元可能攜帶的最大信息量；編碼速率的物理意義是由平均

個碼元構成的碼字可攜帶的最大信息量。定義4.5.17不等長碼的編碼效率定義為■編碼效率表示的是每個信源符號平均信息量與編碼所需的平均碼字符號可攜帶最大信息量的比值。114n第4章信息論基礎不等長編碼的基本定理(續)■例4.5.7

某離散無記憶信源的消息符號和其概率場為n試分析對其采用

的碼字進行單個符號編碼和兩個符號的聯合編碼時的平均碼長和編碼效率。解：信源的熵(1)對單個信源進行編碼時，碼字的碼元集編碼速率平均碼長編碼效率：115n第4章信息論基礎不等長編碼的基本定理(續)■例4.5.7 (2)

若對每兩個信源符號進行聯合編碼符號序列的平均碼長平均每個符號的編碼長度編碼速率編碼效率■可見效率明顯提高。且較之等長編碼更容易實現。116霍夫曼(Huffman)編碼霍夫曼編碼是一種異字頭不等長編碼，其基本思想是：■■對出現概率大的符號或符號組用位數較少的碼字表示；對出現概率小的符號或符號組用位數較多的碼字表示。由此可提高編碼效率。這一思想在不等長編碼中已經用過。霍夫曼編碼：提供了一種便于實現的最佳不等長編碼的具體方法。■定理4.5.6

霍夫曼編碼一種最佳的不等長編碼。霍夫曼編碼的應用條件：■信源的分布(統計)特性已知。記信源符號集為：■組成編碼輸出碼字的碼元集為：n第4章信息論基礎117118霍夫曼編碼(續)霍夫曼編碼的步驟：■(1)將L個信源符號:S1、S2、…、SL按概率P(Si)大小，以遞減次序，從上到下排成一列；■(2)對處于最下面的概率最小的D個信源符號，一一對應地分別賦予碼字元素C1、C2、…、CD，把這D個概率最小的信源符號相應的概率相加，所得的值用一個虛擬的符號代表，與余下的L-D個符號組成含有(L-D)+1=L-(D-1)個符號的第一次縮減信源{S(1)}；■(3)對縮減信源{S(1)})仍按其概率大小以遞減次序從上到下排列，按照步驟(2)的方法處理，得到一個含有[(L-D)+1]-D+1=L-2(D-1)個符號的第二次縮減信源{S(2)}；■(4)按照上述的方法，依次繼續下去，每次縮減所減少的符號數是D-1個；只要縮減后的信源Si符號的個數大于D，縮減就繼續進行；n第4章信息論基礎霍夫曼編碼(續)霍夫曼編碼的步驟：■(5)當進行第a次縮減后信源{S(a）}符號個數剛好等于D，即有■■則對最后這D個符號分別賦予碼字元素C1、C2、…、CD；n(6)從最后賦予的碼符號開始，沿著每一信源符號在各次縮減過程中得到的碼字元素進行路線前向返回，達至每一信源符號，按前后次序，把返回路途中所遇到的碼元素排成序列，這個序列，就是相應信源符號對應的碼字；n第4章信息論基礎119霍夫曼編碼(續)霍夫曼編碼的步驟：■(7)若進行a次縮減后，當進行第a次縮減后信源S(a)符號個數不等于D，即有則中止縮減，增加符號個概率為0的虛假信源重新編碼，使在a次編碼后一定有增加虛擬信元符號有利于提高編碼效率。n第4章信息論基礎120霍夫曼編碼(續)示例：已知信源符號集■編碼輸出的碼字符號集為解：已知：

嘗試■需要增加虛假符號數為■新構建的信源滿足：n第4章信息論基礎121霍夫曼編碼示例(續)：改造后的符號概率場為編碼過程如下n第4章信息論基礎122霍夫曼編碼(續)示例(續)：平均碼字長度：123n第4章信息論基礎霍夫曼編碼(續)■示例(續)：如果不加入虛假符號，直接進行編碼，則有平均碼字長度n第4章信息論基礎124霍夫曼編碼(續)碼字長度的均勻性和方差在同樣的平均碼字長度的情況下，碼字長度越均勻，對傳輸越有利。定義4.5.13碼字長度的方差其中■編碼的排序過程不同會極大影響碼長的方差。n第4章信息論基礎125霍夫曼編碼(續)碼字長度的均勻性和方差(續)■示例：信源的符號空間為編碼輸出碼字集編碼方式1

將局部概率和置于相同概率的最低位置n第4章信息論基礎126霍夫曼編碼示例：編碼方式1(續)平均碼長：方差：n第4章信息論基礎127霍夫曼編碼編碼方式2將局部概率和置于相同概率的最高位置平均碼長：方差：n第4章信息論基礎128霍夫曼編碼(續)可見■雖然平均碼長一樣，但編碼方法2使得輸出的碼長更為均勻。在編碼過程中，當對縮減信源概率重新排列時，應使合并得到的局部概率和，盡量使其處于較高位置；使得合并元素重復編碼的次數減少，有利于降低碼字長度的方差。■多個符號的霍夫曼聯合編碼具體操作方法與單個符號的霍夫曼編碼類似，參照前面聯合編碼時計算概率的操作方法。n第4章信息論基礎129130n4.6

信道編碼的基本概念與方法信道編碼的基本概念和定理編碼信道的基本模型記信源符號集編碼輸出碼字集■接收碼字集信道譯碼輸出信源符號集發送碼字的先驗概率■■注：在本教材中，只討論離散無記憶信道的情形。n第8章差錯控制編碼131信道編碼的基本概念和定理(續)記接收碼字的統計特性為對于離散信道，其特性可由轉移概率矩陣來表示因為有n第8章差錯控制編碼132信道編碼的基本概念和定理(續)由先驗概率率矩陣及轉移概率矩陣，可導出后驗概及的分布特性n第8章差錯控制編碼133信道編碼的基本概念和定理(續)譯碼規則對譯碼性能的影響■■示例

設發送碼字集接收碼字集兩不同的二元對稱信道轉移概率矩陣分別為■(1)

(2)■分析在兩種信道下不同譯碼規則對譯碼性能的影響。解：若記譯碼的規則一般地記為n第8章差錯控制編碼134信道編碼的基本概念和定理(續)可能的譯碼方法包括如下4種對于信道1：

傳輸正確的概率大于傳輸錯誤的概率。不同譯碼規則導致的出錯概率依次分別為采用規則(2),出錯概率最小；n第8章差錯控制編碼135信道編碼的基本概念和定理(續)可能的譯碼方法包括如下4種對于信道1：對于規則（1），只要發“1”，必定出錯，發“0”一定沒錯。因此有：對于規則（2），發“0”，收到“1”，發“1”，收到“0”時出錯，因此有：其他兩種情形可做類似的分析。由此可見，此時，采用規則(2),出錯概率最小。n第8章差錯控制編碼136信道編碼的基本概念和定理(續)同樣的4種譯碼規則：對于信道2：

傳輸出錯的概率大于傳輸正確的概率不同的譯碼規則導致的出錯概率依次分別為采用規則(3),出錯概率最小。■n第8章差錯控制編碼137信道編碼的基本概念和定理(續)同樣的4種譯碼規則：對于信道2：

，傳輸出錯的概率大于傳輸正確的概率采用規則（3）時，采用與接收碼元相反的狀態進行譯碼只有在傳輸正確時出現譯碼錯誤：■采用規則（4）時，傳輸“0”時，一定出現譯碼錯誤：可見采用規則(3),出錯概率最小。■n第8章差錯控制編碼138139信道編碼的基本概念和定理(續)啟示：■不同的譯碼規則，對誤碼率的影響很大；對不同的信道特性，應選擇不同的譯碼規則。■n第8章差錯控制編碼信道編碼的基本概念和定理(續)對于信道2：不同的譯碼規則導致的出錯概率依次分別為采用規則(3),出錯概率最小。啟示：■不同的譯碼規則，對誤碼率的影響很大；對不同的信道特性，應選擇不同的譯碼規則。■n第8章差錯控制編碼140信道編碼的基本概念和定理(續)最大后驗概率譯碼準則已知后驗概率矩陣若譯碼正確譯碼錯誤誤碼的概率正確譯碼的概率n第8章差錯控制編碼141信道編碼的基本概念和定理(續)已知后驗概率矩陣，最合理的譯碼規則是：對每個收到的符號，取相應最可能發送的碼字作為譯碼輸出即，若規定譯碼規則則可使得差錯概率最小最佳譯碼方法。具體的譯碼操作方法由若則取作為譯碼輸出。n第8章差錯控制編碼142信道編碼的基本概念和定理(續)示例：利用最大后驗譯碼準則分析上一示例的譯碼問題。(1)首先確定系統的后驗概率矩陣a.若轉移概率矩陣為因為有可得導出后驗概率矩陣n第8章差錯控制編碼143信道編碼的基本概念和定理(續)對于前面導出的后驗概率矩陣，最佳的譯碼規則正確譯碼的概率誤碼率n第8章差錯控制編碼144n第8章差錯控制編碼信道編碼的基本概念和定理(續)b.若轉移概率矩陣為同理可得■相應的后驗概率矩陣■145信道編碼的基本概念和定理(續)此時譯碼規則相應地變為正確譯碼的概率誤碼率為由本例可見：■采用后驗概率譯碼準則，無論哪一種情形，總是可以得到最好的譯碼效果。n第8章差錯控制編碼146信道編碼的基本概念和定理(續)最大似然譯碼準則已知概率的基本關系式對于離散無記憶信道因而在先驗等概的條件下，最大后驗概率譯碼規則可變為■即此時直接可根據轉移概率矩陣進行最佳判決。注意在上例中轉移概率矩陣與后驗概率矩陣相同，譯碼結果與最大后驗概率譯碼結果相同。n第8章差錯控制編碼147信道編碼的基本概念和定理(續)費諾不等式■■若記

發送符號集及分布接收符號集及分布發送與接收符號集中元素相同發送符號經信道傳輸后出錯的概率(誤碼率)可表示為后，關于疑義度：發送

接收到確定性稱之。根據條件熵的定義，疑義度為仍然存在的平均不n第8章差錯控制編碼148信道編碼的基本概念和定理(續)接收譯碼錯誤判決的概率■正確的判決概率與熵的定義類似，可定義：判決的不確定性■時，判決的不確定性達到最大。定理

8.4.1(費諾不等式)

與間有如下的關■系式費諾不等式表明

的大小主要由判決不確定性及判決錯誤導致信息的丟失的多少限定。平均每個符號判決錯誤導致信息的丟失小于等于

，該值為已知出現錯誤時，要確定正確符號所需的最大信息量。n第8章差錯控制編碼149信道編碼的基本概念和定理(續)聯合典型序列集滿足下列條件的序列集分別稱之分別記為的 典型序列集和聯合典型序列集。和

。n第8章差錯控制編碼150信道編碼的基本概念和定理(續)■條件下

的典型序列集定義為記為。典型序列的有關性質性質1 當

N

足夠大時，有性質2 當

N

足夠大時，有上述性質描述了典型序列集與熵函數及平均互信息之間的關系。(為信道編碼定理的證明提供準備)n第8章差錯控制編碼151信道編碼的基本概念和定理(續)定義8.4.3(信道)編碼速率定義為:■■其中

信息位長度，

編碼輸出碼字長度。歸一化信道容量已知離散信道的容量由信息論的基本知識，有定義歸一化信道容量為n第8章差錯控制編碼152■信道編碼的基本概念和定理(續)若記發送序列為接收序列為對于離散無記憶信道：■對于N位的二元碼元序列，若編碼速率為■■則 可能的碼字組合數合法的碼字組合數合法的碼字標號集■■設發送的消息編號為

；編碼譯碼n第8章差錯控制編碼153信道編碼的基本概念和定理(續)發送編號為

消息時出錯的概率平均誤碼率可定義為定義8.4.4(可達編碼速率)若則稱

是可達的。n第8章差錯控制編碼154信道編碼的基本概念和定理(續)定理8.4.5(信道編碼定理)給定歸一化信道容量■信道編碼定理給出了編碼速率若

，則

是可達的。可達的基本條件。中隨機選擇

個獨立等概出現，■證明：設采用一種隨機編碼方法，從序列作為合法的碼字，碼字中每個碼元有發送消息序列：接收消息序列：譯碼輸出：若存在唯一的n第8章差錯控制編碼155信道編碼的基本概念和定理(續)使得則取若或同時有：則認為譯碼錯誤。n

采用隨機編碼方法，因沒有任何的傾向性，當

N

足夠大時，碼字中各個

元素的組合出現以大概率具有均勻性，所以譯碼錯誤的概率與發送的消息（消息的編號）無關。不妨假定發送的是編號為1

所對應的碼字。定義事件n第8章差錯控制編碼156信道編碼的基本概念和定理(續)n

則發送編號為1的碼字時，譯碼錯誤的概率為n因為n由

聯合典型序列的基本性質，當

N

足夠大時，有n當N

足夠大時，n都是可以忽略的小概率事件n因此只需考慮■時的情況。n第8章差錯控制編碼157為信道編碼的基本概念和定理(續)當發送一個碼字時，定義事件發送碼字序號：接收碼字

且有則有由

聯合典型序列性質2，有■個，對譯碼輸出正確的碼字應與發送的合法碼字一樣有所有的

相加得■n第8章差錯控制編碼158信道編碼的基本概念和定理(續)n

得到n

顯然有n

綜合上式及n

可得n

對于隨機編碼，平均錯誤概率就是任一特定碼字的錯誤概率，n

因此有■n第8章差錯控制編碼159信道編碼的基本概念和定理(續)n

將代入上式可得因此，若■則當反之，若則當■■證畢。n第8章差錯控制編碼160信道編碼的基本概念和定理(續)定理8.4.5(信道編碼定理)給定歸一化信道容量■信道編碼定理給出了編碼速率若

，則

是可達的。可達的基本條件。在信道編碼定理的證明過程中，可得當滿足條件

時，信道可達性的定理包含了可通過增大碼字的長度來改善信道編碼誤碼性能的思想。但是，信道編碼定理并沒有告訴我們如何具體應如何編碼，才能保證譯碼能夠滿足

的條件。n第8章差錯控制編碼161n第8章差錯控制編碼信道編碼的基本概念和定理(續)例8.4.4設某通信系統的不加編碼的錯誤概率為編碼速率為

，分析不同編碼方式的效果。(1)每兩比特信息為一組進行編碼可使的，相應的錯誤概率變為■162n第8章差錯控制編碼信道編碼的基本概念和定理(續)例8.4.4(續)前三位中1位誤碼的錯誤可得以糾正。正確