《數(shù)字通信原理》第4章 信息論基礎(chǔ)

1、數(shù)字通信原理(4)馮穗力等編著電子工業(yè)出版社2012年8月1第 4 章 信息論基礎(chǔ)本章的基本內(nèi)容：信息的度量方法；離散信道及容量；連續(xù)信源、信道及容量；信源編碼的基本方法；率失真理論。24.1 引言3 消息與信息 1948年，美國科學(xué)家香農(nóng)的論文通信的數(shù)學(xué)理論， 奠定了信息論的理論基礎(chǔ)。 消息與信息 (1)消息是由符號(hào)、文字、數(shù)字、語音或圖像組成的序列； (2)消息是信息的載體，信息是消息的內(nèi)涵；消息中可能包 含信息，也可能不包含信息； (3)收到一則消息后，所得的信息量，在數(shù)量上等于獲得 消息前后“不確定性”的消除量； (4)通信的目的在與傳送信息。第4章 信息論基礎(chǔ)4 消息與信息(續(xù))通信

2、系統(tǒng)傳遞信息的機(jī)制和本質(zhì) 形式化：通信的基本任務(wù)是在接收端把發(fā)送端發(fā)出的消息從形式上恢復(fù)出來，而對(duì)消息內(nèi)容的理解和判斷，不是通信的任務(wù)。非決定論：通信過程傳遞的消息中所包含的內(nèi)容，對(duì)接收者來說事先是無法預(yù)料的。不確定性：是指收到該消息之前，對(duì)其中的內(nèi)容出現(xiàn)與否，具有不確定的因素；不確定的因素可以通過通信來加以消除或部分消除。 第4章 信息論基礎(chǔ)54.2 信息的度量6 信息度量的概念 (1) 某消息的信息量獲得該消息后不確定性的消除量； 不確定性可能性概率問題： 信息量可用概率的某種函數(shù)來度量 (2) 不同的消息有信息量的多少的區(qū)別，因此 信息的度量方式應(yīng)滿足信息量的可加性 信息量應(yīng)該是滿足可加

3、性的概率的函數(shù)。第4章 信息論基礎(chǔ)7 離散信源信息的度量 離散信源的信息量 離散信源統(tǒng)計(jì)特性的描述方法概率場 設(shè)離散信源包含N種可能的不同符號(hào)，相應(yīng)的概率場可表述為 概率場應(yīng)滿足條件： 第4章 信息論基礎(chǔ)8 離散信源的信息量(續(xù)) 信息量作為概率的函數(shù)，具有形式 若 與 統(tǒng)計(jì)獨(dú)立，滿足可加性要求 如定義 顯然有 可同時(shí)滿足是概率的函數(shù)和可加性兩個(gè)要求。 第4章 信息論基礎(chǔ)9 離散信源信的息量(續(xù)) 定義 離散消息xi的信息量: 信息量的單位與對(duì)數(shù)的底有關(guān)： log以2為底時(shí)，單位為比特：bit log以e為底時(shí)，單位為奈特：nit log以10為底時(shí)，單位為哈特，hart 一般在沒有特別聲明時(shí)

4、均假定信息的單位為比特。 第4章 信息論基礎(chǔ)10 離散信源信的息量(續(xù)) 示例：已知某信源的概率場為 輸出的各符號(hào)統(tǒng)計(jì)獨(dú)立，計(jì)算序列S“113200”的信息量 第4章 信息論基礎(chǔ)11 離散信源的平均信息量：信源的熵 離散信源的熵 定義4.2.2 離散信源 的熵 熵是信源在統(tǒng)計(jì)意義上每個(gè)符號(hào)的平均信息量。第4章 信息論基礎(chǔ)12 離散信源的熵(續(xù)) 示例：求離散信源 的熵。 按照定義： 熵的單位：比特/符號(hào) 第4章 信息論基礎(chǔ)13 離散信源的熵(續(xù)) 示例（續(xù)）：若上述離散信源發(fā)送獨(dú)立的符號(hào)序列： 201 020 130 213 001 203 210 100 321 010 023 102 00

5、2 10 312 032 100 120 210 (1)求總的信息量；(2)利用熵估計(jì)總的信息量。解：(1) (2) 第4章 信息論基礎(chǔ)14 離散信源的最大熵定理 定義4.2.3 凸集 對(duì)任意 ，有 定義4.2.4 若 型凸函數(shù)(下凸函數(shù)) 型凸函數(shù)(上凸函數(shù)) 第4章 信息論基礎(chǔ)15 離散信源的最大熵定理(續(xù)) 若函數(shù)為型凸函數(shù)(下凸函數(shù))，則一定存在最小值 若函數(shù)為型凸函數(shù)(上凸函數(shù))，則一定存在最大值 型凸函數(shù)示例 第4章 信息論基礎(chǔ)16 離散信源的最大熵定理(續(xù)) 若 是一組概率； 是一個(gè)型凸函數(shù)，則一般地有如下的關(guān)系式 利用上面的關(guān)系式，可以證明如下的定理 定理4.2.5 熵函數(shù) 是

6、概率 的型凸函數(shù)。 第4章 信息論基礎(chǔ)17 離散信源的最大熵定理(續(xù)) 定理4.2.6 當(dāng)離散信源X取等概分布時(shí)，其熵 取最大值。 即：當(dāng)信源取等概分布時(shí)，具有最大的不確定性。示例：兩個(gè)信源符號(hào)的情形。 P(x1)=p,P(x2)=1-p 當(dāng)p=1/2時(shí)，H(X)= Hmax第4章 信息論基礎(chǔ)18 離散信源的聯(lián)合熵與條件熵 兩隨機(jī)變量 的概率場 滿足條件：第4章 信息論基礎(chǔ)19 離散信源的聯(lián)合熵與條件熵(續(xù)) 兩隨機(jī)變量的聯(lián)合熵 定義4.2.3 兩隨機(jī)變量 的聯(lián)合熵 如兩隨機(jī)變量統(tǒng)計(jì)獨(dú)立，有第4章 信息論基礎(chǔ)20 兩隨機(jī)變量的聯(lián)合熵(續(xù)) 對(duì)于統(tǒng)計(jì)獨(dú)立的兩隨機(jī)變量，不能從其中一個(gè)獲得有關(guān)另外一

7、個(gè)的任何信息。第4章 信息論基礎(chǔ)21 離散信源的聯(lián)合熵與條件熵(續(xù)) 兩隨機(jī)變量的條件熵 定義4.2.4 兩隨機(jī)變量 的條件熵 一般地有(利用稍后的平均互信息量的非負(fù)性) 具有某種相關(guān)性的兩隨機(jī)變量，一個(gè)隨機(jī)變量的出現(xiàn)總是 有助于降低另一隨機(jī)變量的不確定性。 第4章 信息論基礎(chǔ)224.3 離散信道及容量23 離散信源及容量 信道模型 信道的輸入： 信道的輸出： 信道模型(特性)可用其轉(zhuǎn)移概率來描述第4章 信息論基礎(chǔ)24 離散信源及容量(續(xù)) 信道模型 信道模型(特性)可用其轉(zhuǎn)移概率來描述，一般地有 輸出不僅與當(dāng)前的輸入有關(guān)，而且與之前的若干個(gè)輸入值 有關(guān)，呈現(xiàn)某種“記憶”效應(yīng)。第4章 信息論基

8、礎(chǔ)25 離散信源及容量(續(xù)) 離散無記憶信道的轉(zhuǎn)移矩陣 輸出僅與當(dāng)前的輸入有關(guān) 離散無記憶信道的后驗(yàn)概率矩陣 第4章 信息論基礎(chǔ)26 離散無記憶信道的轉(zhuǎn)移矩陣(續(xù)) 示例：二元的離散無記憶信道 發(fā)“0”和發(fā)“1”時(shí) 能正確接收的概率為0.99， 錯(cuò)誤的概率為0.01。 即有 轉(zhuǎn)移矩陣 第4章 信息論基礎(chǔ)27 離散信源及容量 互信息量 后驗(yàn)概率 是一種條件概率，在通信系統(tǒng)中可表示 收到 后，發(fā)送端發(fā)送的是符號(hào) 的概率。 接收端收到 后，關(guān)于 的不確定性可表示為 定義4.3.1 互信息量為： 互信息量為收到 后，關(guān)于 的不確定性的消除量。 第4章 信息論基礎(chǔ)28 互信息量(續(xù)) 互信息量具有對(duì)稱性

9、 互信息量的性質(zhì) (1) 若 (2) 若 (3) 若 (4) 若 第4章 信息論基礎(chǔ)29 離散信源及容量(續(xù)) 平均互信息量 定義4.3.2 平均互信息量為： 平均互信息量具有非負(fù)性 表明從統(tǒng)計(jì)上來說，兩相關(guān)聯(lián)的隨機(jī)變量集，其中一個(gè)集中符號(hào)的出現(xiàn)總是有利于提供有關(guān)另外一個(gè)集的信息。第4章 信息論基礎(chǔ)30 離散信源及容量(續(xù)) 熵函數(shù)與平均互信息量間的關(guān)系 第4章 信息論基礎(chǔ)31 熵函數(shù)與平均互信息量間的關(guān)系(續(xù)) 當(dāng)信源X與Y統(tǒng)計(jì)獨(dú)立時(shí) (1)兩個(gè)符號(hào)同時(shí)出現(xiàn)時(shí)提供的平均信息量等于每個(gè)符號(hào)的平均信息量之和； (2)一個(gè)符號(hào)不能提供有關(guān)另一符號(hào)的任何信息。第4章 信息論基礎(chǔ)32 熵函數(shù)與平均互信

10、息量間的關(guān)系(續(xù)) 當(dāng)兩個(gè)信源相關(guān)時(shí) (1)聯(lián)合熵小于兩個(gè)信源的熵的和: (2)平均互信息量等于兩信源熵重合的部分； (3)信源的條件熵等于其自身的熵減去平均互信息量：第4章 信息論基礎(chǔ)33 離散信道的容量 已知信道的轉(zhuǎn)移矩陣 信源符號(hào)集： ； 符號(hào)傳輸速率： 系統(tǒng)的平均信息速率為： 第4章 信息論基礎(chǔ)34 離散信道的容量(續(xù)) 定義4.3.3 離散信道的最大傳輸速率為其信道容量 匹配信源的概念 信道容量由信道特性和信源的統(tǒng)計(jì)特性決定。 信道特性確定之后，其容量由信源的統(tǒng)計(jì)特性決定。 匹配信源：能使單位時(shí)間內(nèi)信道可傳輸?shù)钠骄畔⒘窟_(dá)到信 道容量的信源稱之。 記匹配信源的分布特性： 信道容量：

11、第4章 信息論基礎(chǔ)35 離散信道的容量(續(xù)) 匹配信源(續(xù)) 已知信道轉(zhuǎn)移概率，匹配信源統(tǒng)計(jì)特性的求解 約束條件 求 使得 達(dá)到最大。 由拉格朗日求極值的原理： 定義輔助方程 令 可得信源分布特性應(yīng)滿足的條件第4章 信息論基礎(chǔ)36 離散信道的容量(續(xù)) 由此可導(dǎo)出匹配信源統(tǒng)計(jì)特性的求解步驟： (1)解方程組 求解得 (2)求最大平均互信息量： (3)求相應(yīng)后驗(yàn)概率： (4)解方程組，確定匹配信源的分布特性 第4章 信息論基礎(chǔ)37 離散信道的容量(續(xù)) 示例：求匹配信源的統(tǒng)計(jì)特性。已知信道轉(zhuǎn)移概率 (1)解方程組得中間結(jié)果參數(shù)： (2)求最大平均互信息量： (3)求相應(yīng)后驗(yàn)概率： 第4章 信息論

12、基礎(chǔ)38離散信道的容量(續(xù)) 示例(續(xù))： (4)獲得匹配信源統(tǒng)計(jì)特性： (5)信道容量為： 注：若求解過程中出現(xiàn) ，可在方程組中令 ，重新求解。 第4章 信息論基礎(chǔ)39 離散無記憶對(duì)稱信道的容量(續(xù)) 離散無記憶對(duì)稱信道(定義)： 轉(zhuǎn)移矩陣 轉(zhuǎn)移矩陣各行各列均具有相同的元素集的信道稱之。 離散無記憶對(duì)稱信道滿足條件： 對(duì)矩陣中任意的列元素，有 對(duì)矩陣中任意的行元素，有 第4章 信息論基礎(chǔ)40 離散無記憶對(duì)稱信道的容量(續(xù)) 離散無記憶對(duì)稱信道特性： (1)離散無記憶對(duì)稱信道的條件熵滿足： 條件熵取值僅由信道特性決定，與信源的統(tǒng)計(jì)特性無關(guān)。 (2)若輸入信道的信源符號(hào)等概 則信道的輸出符號(hào)也等

13、概 第4章 信息論基礎(chǔ)41 離散無記憶對(duì)稱信道的容量(續(xù)) 信道容量： 對(duì)于離散無記憶對(duì)稱信道，若要使信息傳輸速率達(dá)到信道容量，要求信源的符號(hào)等概分布。 對(duì)于非等概的信源，可設(shè)法對(duì)其輸出的符號(hào)進(jìn)行適當(dāng)?shù)慕M合，使得重新構(gòu)建后的符號(hào)(信源)，具有近似等概的分布特性。 (參見“信源的等長編碼”一節(jié))第4章 信息論基礎(chǔ)424.4 連續(xù)信源、信道及容量43 連續(xù)信源、信道及容量 連續(xù)信源的相對(duì)熵 若已知隨機(jī)信號(hào) 幅度取值的概率密度函數(shù)： 取值在任意小區(qū)間 內(nèi)的概率 (參見示意圖) 連續(xù)信源轉(zhuǎn)變?yōu)榫哂衝個(gè)隨機(jī)變量的信源，且有 利用離散隨機(jī)變量熵的定義，得 第4章 信息論基礎(chǔ)44 連續(xù)信源、信道及容量(續(xù))

14、 連續(xù)信源的相對(duì)熵 概率密度函數(shù)的離散化示意圖，輸入的取值范圍 第4章 信息論基礎(chǔ)45 連續(xù)信源的相對(duì)熵(續(xù)) 連續(xù)信源的熵應(yīng)為 可見連續(xù)信源的熵?zé)o限大。該熵稱為連續(xù)信源的絕對(duì)熵，無 法確切地定義。 通常上式的第一項(xiàng)是有限值，且其具有特定的物理意義。第4章 信息論基礎(chǔ)46 連續(xù)信源的相對(duì)熵(續(xù)) 定義4.4.1 連續(xù)信源的相對(duì)熵為 示例 某信號(hào)的相對(duì)熵為 信號(hào)經(jīng)2倍幅度放大后的相對(duì)熵為 信號(hào)的簡單放大并沒有增加任何新的信息，但其相對(duì)熵發(fā)生 了增大的變化，這說明相對(duì)熵已經(jīng)不再具有信源平均信息量 的內(nèi)涵。第4章 信息論基礎(chǔ)47 連續(xù)信源的相對(duì)條件熵 對(duì)于連續(xù)隨機(jī)變量，同樣可以導(dǎo)出其條件熵 可見連續(xù)

15、信源的條件熵取值無限大，同樣無法確切定義。但通常上式的第一項(xiàng)是一個(gè)有限取值的量。 連續(xù)信源的熵和條件熵均取值無限大，說明要在一個(gè)容量有 限的通信系統(tǒng)中傳遞連續(xù)信源的全部信息是不可能的。第4章 信息論基礎(chǔ)48 連續(xù)信源的相對(duì)條件熵(續(xù)) 定義4.4.3 連續(xù)信源的相對(duì)條件熵 因?yàn)椋?說明相對(duì)熵和相對(duì)條件熵的差值與普通的熵和條件熵的差值 一樣，仍然等于平均互信息量。 同理可以導(dǎo)出：第4章 信息論基礎(chǔ)49 連續(xù)信源相對(duì)熵的最大化 定理4.4.3 連續(xù)信源的相對(duì)熵函數(shù) 是信源概率密度函 數(shù) 的型凸函數(shù)。 相對(duì)熵 作為概率密度函數(shù) 的函數(shù)存在最大值。 第4章 信息論基礎(chǔ)50 連續(xù)信源相對(duì)熵的最大化(續(xù))

16、(1)峰值功率受限情況下的相對(duì)熵最大化條件 可以證明：當(dāng)連續(xù)信源的概率密度函數(shù)服從均勻分布時(shí)，該連續(xù)信源有最大的相對(duì)熵。 在區(qū)間 均勻分布連續(xù)信源 的概率密度函數(shù)為 其相對(duì)熵為 峰值受限信號(hào) 若 第4章 信息論基礎(chǔ)51 連續(xù)信源相對(duì)熵的最大化(續(xù))(2)均值受限情況下的相對(duì)熵最大化條件 可以證明：當(dāng)連續(xù)信源的概率密度函數(shù)服從指數(shù)分布時(shí)，該連續(xù)信源有最大的相對(duì)熵。 均值受限信號(hào) 指數(shù)分布 相對(duì)熵第4章 信息論基礎(chǔ)52 連續(xù)信源相對(duì)熵的最大化(續(xù))(3)平均功率受限情況下的相對(duì)熵最大化條件 可以證明：當(dāng)連續(xù)信源的概率密度函數(shù)服從高斯分布時(shí)，該連續(xù)信源有最大的相對(duì)熵。 平均功率受限信號(hào) 高斯分布 相

17、對(duì)熵第4章 信息論基礎(chǔ)53 加性高斯噪聲信道的容量 加性高斯噪聲(干擾)信道(AWGN) 信道輸入： 信道輸出： 加性高斯噪聲： 已知通過信道后，從 可獲得的關(guān)于 的平均互信息量 若已知信號(hào) 的帶寬為 。 對(duì)任意的這類信號(hào) 則無失真無冗余的抽樣頻率應(yīng)為： (單位時(shí)間的樣點(diǎn)數(shù)) 單位時(shí)間內(nèi)傳輸?shù)男畔⒘?，即信息速率為?章 信息論基礎(chǔ)54 加性高斯噪聲信道的容量(續(xù)) 加性高斯噪聲(干擾)信道(AWGN)的信道容量 信號(hào)與噪聲間的關(guān)系可用方程組表示為 或 二維函數(shù)概率密度間的關(guān)系 為雅可比行列式第4章 信息論基礎(chǔ)55 加性高斯噪聲信道的容量(續(xù)) 因?yàn)?所以有 若已知信源x的統(tǒng)計(jì)特性，收到y(tǒng)后不可

18、確定的部分為 噪聲的影響所導(dǎo)致。第4章 信息論基礎(chǔ)56 加性高斯噪聲信道的容量(續(xù)) 因此可得第4章 信息論基礎(chǔ)57加性高斯噪聲信道的信道容量(續(xù)) 因?yàn)?(1) 在均方受限的條件下，高斯分布的信源有最大的相對(duì)熵 (2) 兩高斯分布的隨機(jī)變量之和( )仍為高斯隨機(jī)變量 (3) 信號(hào) 與噪聲 統(tǒng)計(jì)獨(dú)立 因而有第4章 信息論基礎(chǔ)58 加性高斯噪聲信道容量(續(xù)) 信道容量 若記 得香農(nóng)公式第4章 信息論基礎(chǔ)59加性高斯噪聲信道容量(續(xù))由香農(nóng)公式(香農(nóng)定理) 得到的重要結(jié)論： (1) 信道容量C隨S/N增大而增大； (2) C一定時(shí)，W與S/N之間可以彼此互換； (3) N 0, C ：無擾信道的容

19、量為無窮大； (4) 對(duì)受高斯噪聲干擾的信道，當(dāng) W ， 信道容量趨于 一有限的確定值： (S與N0固定時(shí))第4章 信息論基礎(chǔ)60 信道容量和帶寬的歸一化分析 歸一化信道容量：單位時(shí)間單位頻帶內(nèi)可達(dá)到的信息速率。 注：所謂物理不可 實(shí)現(xiàn)是指不可 能實(shí)現(xiàn)無差錯(cuò) 傳輸。第4章 信息論基礎(chǔ)61 信道容量和帶寬的歸一化分析(續(xù)) 歸一化信道帶寬：單位信息速率所需要的最小帶寬。第4章 信息論基礎(chǔ)62 信道容量和帶寬的歸一化分析(續(xù)) 關(guān)于Eb/N0的歸一化信道帶寬 Eb：比特能量； N0：噪聲功率密度譜； 當(dāng) Eb/N0 1.59dB 時(shí)，無法實(shí)現(xiàn)無差 錯(cuò)的傳輸。第4章 信息論基礎(chǔ)634.5 信源編碼的

20、基本方法64 信源編碼的基本方法 信源編碼的目的：提高傳輸效率 （1）去除消息中的冗余度，使傳輸?shù)姆?hào)盡可能都是獨(dú)立的，沒有多余的成分(如語音、圖像信號(hào)壓縮)； （2）使傳輸?shù)姆?hào)所含的信息最大化。例如，通過編碼使符號(hào)以等概分布的形式出現(xiàn)，使每個(gè)符號(hào)可能攜帶的信息量達(dá)到最大； （3）采用不等長編碼，讓出現(xiàn)概率大的符號(hào)用較短的碼元序列表示，對(duì)概率小的符號(hào)用較長的碼元序列； (4) 在允許一定失真的條件下，如何實(shí)現(xiàn)高效率的編碼。第4章 信息論基礎(chǔ)65 離散無記憶信源 (DMS: Discrete Memoryless Source） 離散無記憶信源的輸出序列： 各個(gè)符號(hào)間彼此獨(dú)立 其中 反之，若輸

21、出的各符號(hào)間有一定的相關(guān)性，則其為一種 有記憶的信源。 有記憶的信源，經(jīng)過處理后，有可能變?yōu)橐环N無記憶的信 源。如有記憶的信源，經(jīng)過理想的、完全去除冗余的 壓縮編碼后產(chǎn)生的輸出。第4章 信息論基礎(chǔ)66 離散無記憶信源編碼與譯碼 若將信源輸出的符號(hào)按每J個(gè)為一組進(jìn)行編碼，則任意的第m個(gè)分組可以表示為 (信源符號(hào)集) 編碼輸出 其中 為輸出的碼元集。 接收端的譯碼輸出第4章 信息論基礎(chǔ)67 離散無記憶信源編碼與譯碼(續(xù)) 待編碼碼組簡單記為 編碼輸出碼組(碼字)第4章 信息論基礎(chǔ)68 離散無記憶信源編碼與譯碼(續(xù))定義4.5.1 若對(duì)信源的每個(gè)不同的符號(hào)或不同的符號(hào)序列，編 碼后產(chǎn)生的碼字不同，則

22、稱該碼為唯一可譯碼。 若待編碼的符號(hào)序列的不同組合個(gè)數(shù)為 碼字集中不同的碼字個(gè)數(shù) 編碼輸出為唯一可譯碼的(必要)條件 對(duì)于碼元取自 ，碼字長度為 一個(gè)碼字，其最大可攜帶的信息量為第4章 信息論基礎(chǔ)69 離散無記憶信源編碼與譯碼(續(xù))定義4.5.2 編碼表示一個(gè)信源符號(hào)所需的平均信息量的定義為 編碼速率 。 碼字長度為常數(shù)的編碼稱為等長編碼，反之稱為不等長編碼。 對(duì)長度為 的信源符號(hào)序列進(jìn)行編碼： 等長編碼的編碼速率 不等長編碼的編碼速率 其中 為不等長編碼的平均碼長。第4章 信息論基礎(chǔ)70 離散無記憶信源編碼與譯碼(續(xù)) 定義4.5.3 信源的熵 與編碼速率 的比值定義為編碼效率 要保證編碼沒

23、有信息丟失，要求第4章 信息論基礎(chǔ)71 離散無記憶信源的等長編碼* 等長編碼：對(duì)信源的每個(gè)符號(hào)，或每組符號(hào)，用長度相等的代碼來表示。 單個(gè)符號(hào)獨(dú)立編碼 采用 進(jìn)制碼元編碼 若信源符號(hào)集有 L 種符號(hào)，要保證譯碼的惟一性，由 碼字長度應(yīng)取 取整得 編碼效率： 第4章 信息論基礎(chǔ)72 離散無記憶信源的等長編碼(續(xù)) 擴(kuò)展編碼(聯(lián)合編碼)：將 J 個(gè)信源符號(hào)進(jìn)行聯(lián)合編碼 由譯碼唯一性要求 取整得 平均每個(gè)符號(hào)所需的碼元數(shù) J 取值的增大有利于效率的提高。第4章 信息論基礎(chǔ)73 離散無記憶信源的等長編碼(續(xù)) 信源統(tǒng)計(jì)特性對(duì)編碼效率的影響例4.5.1 采用二進(jìn)制碼元分別對(duì)J4的兩信源符號(hào)序列進(jìn)行編碼。

24、 信源1： 因?yàn)?故可取 平均每個(gè)符號(hào)的碼元數(shù) 編碼效率第4章 信息論基礎(chǔ)74 離散無記憶信源的等長編碼(續(xù)) 信源2： 同理有 平均每個(gè)符號(hào)的碼元數(shù) 編碼效率第4章 信息論基礎(chǔ)75 離散無記憶信源的等長編碼(續(xù)) 來自同樣符號(hào)集，但不同統(tǒng)計(jì)特性的信源，因其熵 不同。編碼效率 可能差異很大。第4章 信息論基礎(chǔ)76 離散無記憶信源(DMS)的有損等長編碼 一種考慮信源統(tǒng)計(jì)特性的編碼 信源符號(hào)集 由最大熵定理 由熵的定義，可知 由譯碼的唯一性要求 可得 碼組長度應(yīng)滿足條件 由 得第4章 信息論基礎(chǔ)77 離散無記憶信源(DMS)的有損等長編碼 一種考慮信源統(tǒng)計(jì)特性的編碼(續(xù)) 對(duì)任意統(tǒng)計(jì)特性的信源，

25、要使下式成立，即獲得較高的編碼效率，通常 J 取值要非常大，方能使 無損的等長編碼，往往會(huì)因?yàn)?J 的取值過大，難以實(shí)際應(yīng)用。 下面考慮有損的等長編碼。第4章 信息論基礎(chǔ)78 離散無記憶信源(DMS)的有損等長編碼 對(duì)于長度為 J 的DMS碼組(或稱為一序列): 碼組中的每個(gè)符號(hào)： 由符號(hào)間的獨(dú)立性，有 碼組 包含的信息量為： 根據(jù)熵的定義，隨著 J 的增大，有 或 可以證明當(dāng) J 足夠大時(shí)，有第4章 信息論基礎(chǔ)79 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 即： 定義 4.5.4 典型序列集：滿足下列條件的序列 的集合稱之。 其中 。 通常取 為一個(gè)較小的正數(shù)。 非典型序列集：典型序列集

26、的補(bǔ)集稱之。記為 典型序列集和非典型序列集構(gòu)成了序列 所有組合； 構(gòu)成該符號(hào)序列的整個(gè)空間：第4章 信息論基礎(chǔ)80 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 定理4.5.5 (信源劃分定理)：任給 ，當(dāng) J 足夠大時(shí),有 即有： 典型序列出現(xiàn)的概率：若 則 即有： 典型序列趨于等概分布。 典型序列的數(shù)目：第4章 信息論基礎(chǔ)81 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 典型序列的出現(xiàn)概率： 即： 典型序列集 為高概率集； 非典型序列集 為低概率集。 第4章 信息論基礎(chǔ)82 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 典型序列集在整個(gè)序列空間中所占的比例： 可選擇 ，使?jié)M足 因此 說明

27、雖然典型序列集是一個(gè)高概率集，但其數(shù)目在整個(gè)序列空間中可能只占很小的比例； 第4章 信息論基礎(chǔ)83 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 典型序列集的形象說明 如果容許一定的失真，只對(duì)典型序列編碼，對(duì)非典型序列不 予編碼傳輸，碼字長度可大大縮短，從而有效提高傳輸效率。第4章 信息論基礎(chǔ)84 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 例4.5.2：已知二元信源 信源的熵為： 所有的序列 構(gòu)成的集合 為第4章 信息論基礎(chǔ)85 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 示例(續(xù))： (1) 若取 由 平均信息量落在該范圍內(nèi)的序列(典型序列)為 其概率和 第4章 信息論基礎(chǔ)86 離散無

28、記憶信源(DMS)的有損等長編碼(續(xù)) 示例(續(xù))： (2) 若取 由 平均信息量落在該范圍內(nèi)的序列(典型序列)為 其概率和 第4章 信息論基礎(chǔ)87 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 可達(dá)速率的概念 譯碼錯(cuò)誤概率定義為 定義4.5.6 可達(dá)速率 給定信源和編碼速率R，對(duì)任意的 若存在 和編譯碼方法： 、 使當(dāng) 時(shí)，有 則該編碼速率稱為可達(dá)的 反之稱速率是不可達(dá)的。 前面已經(jīng)定義編碼速率：第4章 信息論基礎(chǔ)88 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 定理 4.5.7 若 ，則速率 R 是可達(dá)的； 若 ，則速率 R 是不可達(dá)的。 該定理說明，若 ，則存在編碼方法，當(dāng) J 足夠

29、大時(shí)，只需對(duì)典型序列進(jìn)行編碼，可使編碼誤差足夠地小。 定理的物理意義是：只有用于承載每個(gè)符號(hào)信息的平均比特?cái)?shù)大于等于信源的熵，才能使譯碼的誤差任意地小。 第4章 信息論基礎(chǔ)89 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 分析在滿足一定的譯碼錯(cuò)誤概率的條件下，若只對(duì)典型序列編碼，如何確定編碼長度： 若記：編碼速率： 自信息方差： 則不能正確譯碼的概率 滿足關(guān)系式(參見信源劃分定理證明) 根據(jù)上式，可確定編碼序列的長度 J 。第4章 信息論基礎(chǔ)90 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 示例： (1)對(duì)二元符號(hào)進(jìn)行無差錯(cuò)的二進(jìn)制編碼 此時(shí) 、 、 (2) 若要求編碼效率 ， 求所需的編

30、碼序列長度 J 由 得第4章 信息論基礎(chǔ)91 離散無記憶信源(DMS)的有損等長編碼(續(xù)) 自信息方差： 最后得所需的符號(hào)序列長度 (該取值太大，可見等長編碼不易在實(shí)際系統(tǒng)中應(yīng)用)第4章 信息論基礎(chǔ)92 不等長編碼的基本概念 定義4.5.8 若碼中每個(gè)碼字都含有一個(gè)特定的符號(hào)用于標(biāo)識(shí) 一個(gè)碼字的起點(diǎn)，則稱這種碼為逗點(diǎn)碼。 例：0，01，011，0111 為逗點(diǎn)碼。 定義4.5.9 對(duì)任一碼字 ，稱該碼字的前面 位 ， ，為碼字 的長為 的字頭或前綴。 定義4.5.10 若碼字集中任一碼字都不是另一碼字的字頭，則 稱這種碼為異字頭碼，或異前綴碼。 定義4.5.11 對(duì)具有 個(gè)元素的信源符號(hào)集：

31、若符號(hào) 用 元碼編碼后輸出的碼字長度為 ，則定 義信源符號(hào)的平均碼字長度為：第4章 信息論基礎(chǔ)93 異字頭不等長編碼 異字頭碼的優(yōu)點(diǎn)：異字頭碼譯碼時(shí)具有即時(shí)性，即當(dāng)收到一個(gè)完整的碼字后即可譯碼，不用擔(dān)心這一碼字是另一碼字的字頭部分。 異字頭碼的編碼樹：異字頭碼的編碼可用編碼樹來描述第4章 信息論基礎(chǔ)94第4章 信息論基礎(chǔ) 異字頭不等長編碼(續(xù))（1）從根朝下，第一級(jí)有 個(gè)節(jié)點(diǎn)；第二級(jí)有 個(gè)節(jié)點(diǎn)；如此類推，第r 級(jí)有 個(gè)節(jié)點(diǎn)。（2）從任一節(jié)點(diǎn)引出的分支有 個(gè)，從根開始，可分別用0，1，2， 1來標(biāo)記。（3）不再發(fā)出分支的節(jié)點(diǎn)稱為端節(jié)點(diǎn)，若用端節(jié)點(diǎn)表示不同的信源符號(hào)，取相應(yīng)的從根到該節(jié)點(diǎn)的標(biāo)號(hào)序列

32、為碼字，則必能保證碼字的異字頭條件。（4）若各分支均延伸到最高級(jí)的各端點(diǎn)，則可構(gòu)成一棵對(duì)稱的樹，稱為滿樹，否則稱為非滿樹。95第4章 信息論基礎(chǔ) 異字頭不等長編碼(續(xù)) 異字頭碼的編碼原則 編碼時(shí)應(yīng)盡可能地使碼字中的任一碼元載荷達(dá)到其最大的信息量： 。 應(yīng)使每個(gè)節(jié)點(diǎn)發(fā)出的種 分支出現(xiàn)的概率盡可能相等。 異字頭碼的編碼方法 將信源符號(hào)分成盡可能等概的個(gè)子集，與碼樹的第一級(jí)的個(gè)節(jié)點(diǎn)對(duì)應(yīng)； 對(duì)每個(gè)子集按同樣的方法又分為個(gè)二級(jí)子集，與碼樹的第二級(jí)節(jié)點(diǎn)相對(duì)應(yīng)； 以此類推，直至子集不能再分為止。 96第4章 信息論基礎(chǔ) 異字頭不等長編碼(續(xù)) 示例： 對(duì)信源符號(hào)集 做 的三進(jìn)制異字頭不等長編碼。 解：97

33、第4章 信息論基礎(chǔ) 不等長編碼的基本定理* 定理4.5.12 對(duì)具有個(gè)符號(hào)的信源符號(hào)集： ，其相應(yīng)的長度為 的元異字頭碼存在的充要條件是如下的不等式成立即：當(dāng)滿足條件 時(shí)，一定存在與該碼字對(duì)應(yīng)的編碼樹。 定理4.5.13 唯一可譯碼必滿足(Kraft)不等式： (定理4.5.13）系：任一唯一可譯碼可用相應(yīng)的碼字長度一樣的異字頭碼代替。 即：任一唯一可譯碼可用相應(yīng)的碼字長度一樣的異字頭碼代替，而不改變?cè)摯a的任何性質(zhì)。 98第4章 信息論基礎(chǔ) 不等長編碼的基本定理*(續(xù))定理4.5.14 （不等長編碼定理）（1）若 是組成碼字的元素的個(gè)數(shù)，則任一唯一可譯碼的平均碼長滿足： （2）存在有 元的可譯

34、碼，其平均長度99第4章 信息論基礎(chǔ) 不等長編碼的基本定理*(續(xù)) 多個(gè)符號(hào)的聯(lián)合不等長編碼 記： 信源符號(hào)集： 待編碼的符號(hào)序列(符號(hào)分組)： 特定符號(hào)序列 編碼后輸出的碼字長度 符號(hào)序列 編碼后的平均碼字長度 符號(hào)序列 的熵函數(shù) 則由定理4.5.14，可得 100第4章 信息論基礎(chǔ) 不等長編碼的基本定理*(續(xù)) 定義4.5.15 對(duì) J 個(gè)信源符號(hào)進(jìn)行不等長聯(lián)合編碼時(shí)平均一個(gè)信源符號(hào)的編碼長度定義為 由前面的討論可得 可見：多個(gè)符號(hào)的不等長聯(lián)合編碼有同樣利于提高編碼效率。 101第4章 信息論基礎(chǔ) 不等長編碼的基本定理(續(xù)) 離散無記憶信源的擴(kuò)展信源的編碼 以 J 個(gè)離散無記憶信源符號(hào)為一

35、組可構(gòu)成一個(gè)擴(kuò)展信源 擴(kuò)展信源的熵函數(shù)為 由前面的分析可得 可見對(duì)擴(kuò)展后的離散無記憶信源的編碼有利于提高編碼效率。 且有102第4章 信息論基礎(chǔ) 不等長編碼的基本定理(續(xù)) 定義4.5.16 不等長碼的編碼速率定義為 是平均每個(gè)信源符號(hào)編碼時(shí)所需的碼元的個(gè)數(shù)； 是每個(gè)碼元可能攜帶的最大信息量； 編碼速率的物理意義是由平均 個(gè)碼元構(gòu)成的碼字可攜帶的最大信息量。 定義4.5.17 不等長碼的編碼效率定義為編碼效率表示的是每個(gè)信源符號(hào)平均信息量與編碼所需的平均碼字符號(hào)可攜帶最大信息量的比值。 103第4章 信息論基礎(chǔ) 不等長編碼的基本定理(續(xù))例4.5.7 某離散無記憶信源的消息符號(hào)和其概率場為 試

36、分析對(duì)其采用 的碼字進(jìn)行單個(gè)符號(hào)編碼和兩個(gè)符號(hào)的聯(lián)合編碼時(shí)的平均碼長和編碼效率。解：信源的熵(1) 對(duì)單個(gè)信源進(jìn)行編碼時(shí)，碼字的碼元集 平均碼長 編碼速率 編碼效率：104第4章 信息論基礎(chǔ) 不等長編碼的基本定理(續(xù))例4.5.7 (2) 若對(duì)每兩個(gè)信源符號(hào)進(jìn)行聯(lián)合編碼 符號(hào)序列的平均碼長 平均每個(gè)符號(hào)的編碼長度 編碼速率 編碼效率 可見效率明顯提高。105 霍夫曼(Huffman)編碼 霍夫曼編碼是一種異字頭不等長編碼，其基本思想是： 對(duì)出現(xiàn)概率大的符號(hào)或符號(hào)組用位數(shù)較少的碼字表示； 對(duì)出現(xiàn)概率小的符號(hào)或符號(hào)組用位數(shù)較多的碼字表示。 由此可提高編碼效率。 霍夫曼編碼： 定理4.5.17 霍夫

37、曼編碼一種最佳的不等長編碼。 霍夫曼編碼的應(yīng)用條件： 信源的分布(統(tǒng)計(jì))特性已知。 記 信源符號(hào)集為： 組成編碼輸出碼字的碼元集為：第4章 信息論基礎(chǔ)106 霍夫曼編碼(續(xù)) 霍夫曼編碼的步驟：(1)將L個(gè)信源符號(hào):S1、S2、SL 按概率P(Si)大小，以遞減次序，從上到下排成一列；(2)對(duì)處于最下面的概率最小的D個(gè)信源符號(hào)，一一對(duì)應(yīng)地分別賦予碼字元素C1、C2、CD，把這D個(gè)概率最小的信源符號(hào)相應(yīng)的概率相加，所得的值用一個(gè)虛擬的符號(hào)代表，與余下的L-D個(gè)符號(hào)組成含有(L-D)+1=L-(D-1)個(gè)符號(hào)的第一次縮減信源S(1)；(3)對(duì)縮減信源S(1)仍按其概率大小以遞減次序從上到下排列，按

38、照步驟(2)的方法處理，得到一個(gè)含有(L-D)+1-D+1=L-2(D-1)個(gè)符號(hào)的第二次縮減信源S(2)；(4)按照上述的方法，依次繼續(xù)下去，每次縮減所減少的符號(hào)數(shù)是D-1個(gè)；只要縮減后的信源Si符號(hào)的個(gè)數(shù)大于D，縮減就繼續(xù)進(jìn)行；第4章 信息論基礎(chǔ)107 霍夫曼編碼(續(xù)) 霍夫曼編碼的步驟：(5)當(dāng)進(jìn)行第a次縮減后信源S(a）符號(hào)個(gè)數(shù)剛好等于D，即有 則對(duì)最后這D個(gè)符號(hào)分別賦予碼字元素C1、C2、CD；(6)從最后賦予的碼符號(hào)開始，沿著每一信源符號(hào)在各次縮減過程中得到的碼字元素進(jìn)行路線前向返回，達(dá)至每一信源符號(hào)，按前后次序，把返回路途中所遇到的碼元素排成序列，這個(gè)序列，就是相應(yīng)信源符號(hào)對(duì)應(yīng)的

39、碼字；第4章 信息論基礎(chǔ)108 霍夫曼編碼(續(xù)) 霍夫曼編碼的步驟：(7)若進(jìn)行a次縮減后，當(dāng)進(jìn)行第k次縮減后信源S(a)符號(hào)個(gè)數(shù)不等于D，即有則中止縮減，增加 個(gè)概率為0的虛假信源符號(hào) 重新編碼，使在k次編碼后一定有 。第4章 信息論基礎(chǔ)109 霍夫曼編碼(續(xù)) 示例：已知信源符號(hào)集 編碼輸出的碼字符號(hào)集為 解：已知： 嘗試 需要增加虛假符號(hào)數(shù)為 新構(gòu)建的信源滿足：第4章 信息論基礎(chǔ)110 霍夫曼編碼示例(續(xù))：改造后的符號(hào)概率場為 編碼過程如下第4章 信息論基礎(chǔ)111 霍夫曼編碼(續(xù)) 示例(續(xù))： 平均碼字長度：第4章 信息論基礎(chǔ)112 霍夫曼編碼(續(xù)) 示例(續(xù))： 如果不加入虛假符號(hào)

40、，直接進(jìn)行編碼，則有 平均碼字長度第4章 信息論基礎(chǔ)113 霍夫曼編碼(續(xù)) 碼字長度的均勻性和方差 在同樣的平均碼字長度的情況下，碼字長度越均勻，對(duì)傳輸越有利。 定義4.5.16 碼字長度的方差 其中 編碼過程的排序過程不同會(huì)影響碼長的方差。第4章 信息論基礎(chǔ)114 霍夫曼編碼(續(xù)) 碼字長度的均勻性和方差(續(xù)) 示例：信源的符號(hào)空間為 編碼輸出碼字集 編碼方式1 將局部概率和置于相同概率的最低位置第4章 信息論基礎(chǔ)115 霍夫曼編碼示例：編碼方式1(續(xù)) 平均碼長： 方差：第4章 信息論基礎(chǔ)116 霍夫曼編碼 編碼方式2 將局部概率和置于相同概率的最高位置 平均碼長： 方差：第4章 信息論

41、基礎(chǔ)117 霍夫曼編碼(續(xù)) 可見 雖然平均碼長一樣，但編碼方法2使得輸出的碼長更為均勻。 在編碼過程中，當(dāng)對(duì)縮減信源概率重新排列時(shí)，應(yīng)使合并得到的局部概率和，盡量使其處于最高位置；使得合并元素重復(fù)編碼的次數(shù)減少，有利于降低碼字長度的方差。 第4章 信息論基礎(chǔ)1184.6 率失真理論119 實(shí)際系統(tǒng)中的權(quán)衡問題 實(shí)際系統(tǒng)中通常需要考慮性能與經(jīng)濟(jì)性之間的權(quán)衡問題； 可采用以某些不可察覺或可察覺但不影響應(yīng)用的信號(hào)失真代價(jià)，來換取所需的傳輸速率、存儲(chǔ)空間、運(yùn)算復(fù)雜度和系統(tǒng)實(shí)現(xiàn)成本的降低； 電話系統(tǒng)采樣8kHz采樣，8比特量化； 數(shù)字音響系統(tǒng)采樣44kHz采樣，16或24比特量化； 第4章 信息論基礎(chǔ)120 失真的概念 失真是指用某種尺度衡量的理想信源樣值 與“變換”后的樣值 間的差異。 這里所謂的“變換”，可以是某種有損的編碼，或者是經(jīng)傳輸后受到劣化的信號(hào)。 失真函數(shù)：對(duì)由符號(hào) 變?yōu)榉?hào) 產(chǎn)生失真造成的影響，可根據(jù)不同的情況定義一個(gè)非負(fù)函數(shù) 來描述，該函數(shù)就稱為失真函數(shù)。 失真函數(shù)的取值通常反映失真產(chǎn)生的代價(jià)。 第4章 信息論基礎(chǔ)121 失真的概念(續(xù)) 失真函數(shù)的示例： 第4章 信息論基礎(chǔ)122 率失真理論研究的問題 率失真理論研究的是限定失真條件下信源的編