數字通信原理4信息論基礎1ppt課件

1、1 1、消息與信息、消息與信息 (1) (1) 消息是由符號、文字、數字、語音或圖像組成的序消息是由符號、文字、數字、語音或圖像組成的序列；列； (2) (2) 消息是信息的載體，信息是消息的內涵；消息中可消息是信息的載體，信息是消息的內涵；消息中可能包能包 含信息，也可能不包含信息；含信息，也可能不包含信息； (3) (3) 收到一則消息后，所得的信息量，在數量上等于獲收到一則消息后，所得的信息量，在數量上等于獲得得 消息前后消息前后“不確定性的消除量；不確定性的消除量； (4) (4) 通信的目的在與傳送信息。通信的目的在與傳送信息。2 2、信息度量的概念、信息度量的概念 (1) (1)

2、某消息的信息量獲得該消息后不確定性的消除量；某消息的信息量獲得該消息后不確定性的消除量； 不確定性不確定性可能性可能性概率問題：概率問題： 信息量可用概率的某種函數來度量信息量可用概率的某種函數來度量 (2) (2) 不同的消息有信息量的多少的區(qū)別，因而不同的消息有信息量的多少的區(qū)別，因而 信息的度量方式應滿足信息量的可加性信息的度量方式應滿足信息量的可加性 信息量應該是滿足可加性的概率的函數。信息量應該是滿足可加性的概率的函數。 11Niixp NNxpxpxpXpxxxX.:.:2121n同時滿足概率函數和可加性兩個要求。同時滿足概率函數和可加性兩個要求。 iixpfxIixjx jiji

3、jijixpfxpfxpxpfxxpfxxI iiixpxpfxI1log jijijijixpxpxpxpfxxpfxxI1log1logn 離散信源信的息量離散信源信的息量( (續(xù)續(xù)) )n 定義定義 離散消息離散消息xixi的信息量的信息量: :nn 信息量的單位與對數的底有關：信息量的單位與對數的底有關：n log log以以2 2為底時，單位為比特：為底時，單位為比特：bitbitn log log以以e e為底時，單位為奈特：為底時，單位為奈特：nitnitn log log以以1010為底時，單位為哈特，為底時，單位為哈特，harthartn n 一般在缺省時取單位為比特。一般在

4、缺省時取單位為比特。 iiixPxPxPIlog1logn 離散信源信的息量離散信源信的息量( (續(xù)續(xù)) )n 例如：已知某信源的概率場為例如：已知某信源的概率場為nn 輸出的各符號統計獨立，計算序列輸出的各符號統計獨立，計算序列S“113200S“113200的信息量的信息量n 81414183:3210:XpX bitsppppppppppppSpSI83.111415. 11415. 1232201log01log21log31log11log11log0023111log1logNixXi,.,2 , 1,: iNiixpxpXHlog1n 離散信源的熵離散信源的熵( (續(xù)續(xù)) )n

5、例如：求離散信源例如：求離散信源 n 的熵。的熵。n n 按照定義：按照定義： n 81414183:3210:XpX 符號比特906. 181log8141log4141log4183log83log41iiixpxpXHn 離散信源的熵離散信源的熵( (續(xù)續(xù)) )n 例如續(xù)）：若上述離散信源發(fā)送獨立的符號序列：例如續(xù)）：若上述離散信源發(fā)送獨立的符號序列：n 201 020 130 213 001 203 210 100 321 010 201 020 130 213 001 203 210 100 321 010 n 023 102 002 10 312 032 100 120 210 0

6、23 102 002 10 312 032 100 120 210 n (1) (1)求總的信息量；求總的信息量；(2)(2)利用熵估計總的信息量。利用熵估計總的信息量。n (1) (1)n n n (2) (2) 比特55.10781log741log1341log1483log23log41iiixpnI 比特62.108096. 1713142341XHnIiinn當當p=1/2p=1/2時，時，H(X)=HmaxH(X)=Hmax NiNNNNNNNHxpxpxpH1211log1log11,.,1,1,.,maxNjMiyxXYji,.,2 , 1;,.,2 , 1,:NMNMMMM

7、MNNNNyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxXYpXY,.,.,.,.,:221122222212221121211111111 MiNjjiyxpNjMiyxXYji,.,2 , 1;,.,2 , 1,:符號比特 MijiNjjiyxpyxpXYH11log YHXHypypxpxpypxpypxpyxpyxpXYHjNjjMiiiMijiNjjiMijiNjji loglogloglog111111n 兩隨機變量的聯合熵兩隨機變量的聯合熵( (續(xù)續(xù)) )n 對于統計獨立的兩隨機變量，不能從其中一個獲得有關另外對于統計獨立的兩隨機變量，

8、不能從其中一個獲得有關另外一個的任何信息。一個的任何信息。NjMiyxXYji,.,2 , 1;,.,2 , 1,: MijiNjjiyxpyxpYXH11log MiijNjjixypyxpXYH11log XHYXHp(xi/yj)xiyji=1,2,.,Mj=1,2,.,N圖 4-3-1 信道模型NjMiyxXYXYpji,.,2 , 1,.,2 , 1,:,MixXi,.,2 , 1,:NjyYj,.,2 , 1,: nkkkkjjixxxypNjMiyxXY.,.,2 , 1,.,2 , 1,:1MNMMNNijxypxypxypxypxypxypxypxypxypxypXYp/./

9、./././212222111211NMNNMMjiyxpyxpyxpyxpyxpyxpyxpyxpyxpyxpYXp/././././212222111211 離散無記憶信道的轉移矩陣離散無記憶信道的轉移矩陣( (續(xù)續(xù)) ) 例如：二元的離散無記憶信道例如：二元的離散無記憶信道 發(fā)發(fā)“0“0和發(fā)和發(fā)“1“1時時 能正確接收的概率為能正確接收的概率為0.990.99， 錯誤的概率為錯誤的概率為0.010.01。 即有即有 轉移矩陣轉移矩陣 99. 01/10/0 pp01. 01/00/1 pp99. 001. 001. 099. 0/ijxypXYpjiyxp/ixjyjyixjijiyxp

10、yxI/1log/ jiijiyxIxIyxI/;jyix 互信息量互信息量( (續(xù)續(xù)) ) 互信息量具有對稱性互信息量具有對稱性 互信息量的性質互信息量的性質 (1) (1) 假設假設 （2 2假設假設 (3) (3) 假設假設 (4) (4) 假設假設 ijjijjijiijijiijiijixyIypxypypxpyxpxpyxpyxpxpyxIxIyxI;/loglog/log/1log1log/;1/jiyxp ijixIyxI; 1/jiiyxpxp ijixIyxI;0 ijixpyxp/0;jiyxI ijixpyxp/00;jiyxI MiNjjijiyxIyxpYXI11;

11、0;YXIXYIYXI; YXHXHYXI/; XYHYHYXI/; XHYXH/ YHXYH/ YHXHXYH 熵函數與平均互信息量間的關系熵函數與平均互信息量間的關系( (續(xù)續(xù)) ) 當信源當信源X X與與Y Y統計獨立時統計獨立時 (1) (1)兩個符號同時出現時提供的平均信息量等于每個符號的兩個符號同時出現時提供的平均信息量等于每個符號的平均信息量之和；平均信息量之和； (2) (2)一個符號不能提供有關另一符號的任何信息。一個符號不能提供有關另一符號的任何信息。 YHXHXYH0;XYIYXIYXI, XH YHXYHYXHXYH YHXHXYH YXIXHYXH;/ 離散信道的容量

12、離散信道的容量 已知信道的轉移矩陣已知信道的轉移矩陣 信源符號集：信源符號集： 符號傳輸速率：符號傳輸速率： 系統的平均信息速率為：系統的平均信息速率為： MNMMNNijxypxypxypxypxypxypxypxypxypxyp/././././212222111211 XSR SMiNjijiijiSMiNjijijiSIRxpyxpxpyxpRxpyxpyxpRYXIR 1111/log/log;SMixpIMixpRYXIRCii;maxmax,.,2, 1,.,2, 1, Nixpim,.,2 , 1, SmIMixpRIRCi,.,2, 1,maxMixypxypxypjNjij

13、Njijij,.2 , 1/log/11Mij,.2 , 1,NjmjI12log NjypIjj,.2 , 12max NjxpxypxypypimMiijMiijj,.2 , 1/112141041010000104104121/ijxypXYp2, 0, 0, 2432125log2222log2log20021NjmjI 1012,522522,101225log2425log0325log0225log21ypypypyp 304,3011,3011,3044321xpxpxpxpmmmm秒比特/1320100032. 1100025logSmRICMNMMNNijxypxypxyp

14、xypxypxypxypxypxypxyp/././././212222111211NjxypxypMiijij,.,2 , 1/log/1常數MixypxypNjijij,.,2 , 1/log/1常數ijNjijxypxypXYHlog/1jiMijiyxpyxpYXHlog/1 MiMxpi,.,2 , 1,1 NjNxypMxypMxypxpyxpypMiijMiijMiijiMijij,.,2 , 1,1/1/1/1111 SSMixpSMixpSMixpSMixpRRXHRXHRYXHXHRYXICiiii常數常數常數logMmaxmax/max;max,.,2, 1,.,2, 1

15、,.,2, 1,.,2, 1, tX xp iaiaxxxXXiii,) 1(, nixpdxxpxPiaiaiiXX,.,2 , 11 11111nibaiaianiiniidxxpdxxpxpxPXX niiiiniinxpxpxPxPXH11loglog 連續(xù)信源的相對熵連續(xù)信源的相對熵( (續(xù)續(xù)) ) 連續(xù)信源的熵應為連續(xù)信源的熵應為 可見連續(xù)信源的熵無限大。該熵稱為連續(xù)信源的絕對熵，無可見連續(xù)信源的熵無限大。該熵稱為連續(xù)信源的絕對熵，無 法確切地定義。法確切地定義。 通常上式的第一項是有限值，且其具有特定的物理意義。通常上式的第一項是有限值，且其具有特定的物理意義。 dxxpxpdx

16、xpxpxpxpxpxpxpxpxpXHXHbanbanniiinniinniiinniiinnnlogloglimlogloglimloglimloglimloglimloglimlim, 0, 01, 01, 01, 01, 0, 0 連續(xù)信源的相對熵連續(xù)信源的相對熵( (續(xù)續(xù)) ) 定義定義4.4.1 4.4.1 連續(xù)信源的相對熵為連續(xù)信源的相對熵為 示例示例4.4.1 4.4.1 某信號的相對熵為某信號的相對熵為 信號經信號經2 2倍幅度放大后的相對熵為倍幅度放大后的相對熵為 信號的簡單放大并沒有增加任何新的信息，但其相對熵發(fā)生信號的簡單放大并沒有增加任何新的信息，但其相對熵發(fā)生 了增

17、大的變化，這說明相對熵已經不再具有信源平均信息量了增大的變化，這說明相對熵已經不再具有信源平均信息量 的內涵。的內涵。 dxxpxpXhbalog 121log21log111dxdxxpxpXhba 241log41log222dxdxxpxpXhba loglim/log/loglim/loglog/loglim/lim/00, 0110, 00, 0XXYYXXYYbabababajinimjjimndxdyyxpyxpypdxdyyxpxypyxpyxpYXHYXH XXYYbabadxdyyxpyxpypYXh/log/ YXhXhYXhXhYXHXHYXI/loglim/logli

18、m/;00 XYhYhYXI/; XYhYhXhYXI;ba,X bxaabxp,1 abXhXhplogmaxAx AxAAxp,21 AXhXhp2logmax dxxxp 0, 00,1xxeaxpax aXhXhplogmax dxxpx2 22221mxexpeXhXhp2log)()(2maxnxynxyyx XYhYhYXhXhYXI/;xWWfS2 WXYhYhWYXhXhWYXIfYXIRSb2/2/2; WYXICxp2;maxxnxxnxnxy,xyyxnxyxx,xyxnJxnpxyp11101,yyxnxyxnyyxxxyxxxyxnJ npxpxnpxyp npxp

19、npxpxpxnpxpxypxyp/ NhdnnpnpdxdnnpxnpdxdnnpxyxnJxnpdxdyxypxypXYh logloglog/log/ WNhYhWXYhYhWYXICxpxpxp2max2/max2;max加性高斯噪聲信道容量加性高斯噪聲信道容量( (續(xù)續(xù)) ) 因為因為 (1) (1) 在均方受限的條件下，高斯分布的信源有最大的相對熵在均方受限的條件下，高斯分布的信源有最大的相對熵 (2) (2) 兩高斯分布的隨機變量之和兩高斯分布的隨機變量之和( )( )仍為高斯隨機變量仍為高斯隨機變量 (3) (3) 信號信號 與噪聲與噪聲 統計獨立統計獨立 因而有因而有nxy

20、2222222222121nxyynxyyeeyp 2222log212log21lognxyeedyypypYh加性高斯噪聲信道容量加性高斯噪聲信道容量( (續(xù)續(xù)) ) 信道容量信道容量 若記若記 得香農公式得香農公式 222222222221logloglog22log22log212log212maxnxnnxnynynyxpWWWeeWWeeWNhYhC22,nxNSSNRWNSWC1log1log22加性高斯噪聲信道容量加性高斯噪聲信道容量( (續(xù)續(xù)) )由香農公式由香農公式( (香農定理香農定理) ) 得到的重要結論：得到的重要結論： (1) (1) 信道容量信道容量C C隨隨S/

21、NS/N增大而增大；增大而增大； (2) C (2) C一定時，一定時，W W與與S/NS/N之間可以彼此互換；之間可以彼此互換； (3) N (3) N 0, C 0, C ：無擾信道的容量為無窮大；：無擾信道的容量為無窮大； (4) (4) 對受高斯噪聲干擾的信道，當對受高斯噪聲干擾的信道，當 W W ， 信道容量趨于信道容量趨于 一確定值：一確定值： SNRWNSWC1log1log2202044. 1loglimNSeNSCWNSWC1log圖 441 歸一化信道容量特性曲線圖 442 歸一化信道帶寬特性曲線11logNSCW圖 443 關于Eb/n0的帶寬特性曲線120CWbCWnE

22、 離散無記憶信源離散無記憶信源 (DMS: Discrete Memoryless Source (DMS: Discrete Memoryless Source） 輸出序列：輸出序列： 各個符號間彼此獨立各個符號間彼此獨立 其中其中 反之，若輸出的各符號間有一定的相關性，則其為一種反之，若輸出的各符號間有一定的相關性，則其為一種 有記憶的信源。有記憶的信源。 有記憶的信源，經過處理后，有可能變?yōu)橐环N無記憶的信有記憶的信源，經過處理后，有可能變?yōu)橐环N無記憶的信 源。如有記憶的信源，經過理想的、完全去除冗余度的源。如有記憶的信源，經過理想的、完全去除冗余度的 壓縮編碼后的輸出。壓縮編碼后的輸出。

23、.21012nXXXXXXSXiLiSSi,.2 , 1,: 離散無記憶信源的等長編碼離散無記憶信源的等長編碼 等長編碼：對信源的每個符號，或每組符號，用長度相等的等長編碼：對信源的每個符號，或每組符號，用長度相等的代碼來表示。代碼來表示。 碼字：由若干碼元碼字元素構成的代碼單元。碼字：由若干碼元碼字元素構成的代碼單元。 單個符號獨立編碼單個符號獨立編碼 采用二進制碼元編碼采用二進制碼元編碼 若信源符號集有若信源符號集有L L種符號，要保證譯碼的惟一性，碼字長度種符號，要保證譯碼的惟一性，碼字長度應取應取 表示取表示取 X X 的整數部分。的整數部分。2222log,loglog1,logLL

24、NLL若為整數若不為整數 X 離散無記憶信源的等長編碼離散無記憶信源的等長編碼( (續(xù)續(xù)) ) 編碼效率：對碼字承載信息能力的利用程度編碼效率：對碼字承載信息能力的利用程度 其中其中 由離散信源的最大熵定理，可知由離散信源的最大熵定理，可知 編碼效率與信源的統計特性有很大的關系，僅當信源輸出編碼效率與信源的統計特性有很大的關系，僅當信源輸出 的符號等概分布時，且的符號等概分布時，且 為整數時，效率才能達為整數時，效率才能達 到到100100。 H SN= logH SLiii=1-p Sp S 2loglogH SLNLiii=1-p Sp S LSH2logmaxL2log 離散無記憶信源的

25、等長編碼離散無記憶信源的等長編碼( (續(xù)續(xù)) ) 擴展編碼：將擴展編碼：將J J個信源符號進行聯合編碼個信源符號進行聯合編碼 J J 個信源符號可能排列組合個數個信源符號可能排列組合個數 平均每個信源符號所需要的碼元個數平均每個信源符號所需要的碼元個數 假設假設 是整數是整數 假設假設 不是整數不是整數 J J 取值的增大有利于效率的提高。取值的增大有利于效率的提高。JL2222log,loglog1,logJJJLLNLL若為整數若不為整數22loglogJJNLNLJJL2logL2logJLJLJNNJJ1log1log22 離散無記憶信源的等長編碼離散無記憶信源的等長編碼( (續(xù)續(xù))

26、) 一般的編譯碼系統譯碼惟一性的要求一般的編譯碼系統譯碼惟一性的要求 記：編碼器輸入的符號集：記：編碼器輸入的符號集： 編碼輸出的碼元集：編碼輸出的碼元集： 擴展編碼的符號長度：擴展編碼的符號長度： 編碼輸出的碼字長度為：編碼輸出的碼字長度為： 則保證譯碼惟一性要求則保證譯碼惟一性要求 平均每個信源符號所需的碼元數應滿足平均每個信源符號所需的碼元數應滿足DiBBi,.2 , 1,:JNJNJDL22loglogJNLNJDLiSSi,.2 , 1,:J 離散無記憶信源的等長編碼離散無記憶信源的等長編碼( (續(xù)續(xù)) ) 若信源等概分布若信源等概分布 可以獲得較高的編碼效率?？梢垣@得較高的編碼效率

27、。 若信源非等概分布若信源非等概分布 則通常編碼效率較低。則通常編碼效率較低。 2logH SL 2logH SLNNp S=max 2logH SL 2logH SLNN= 離散無記憶信源離散無記憶信源(DMS)(DMS)的有損等長編碼的有損等長編碼 對于長度為對于長度為 J J 的的DMSDMS碼組碼組( (或稱為一序列或稱為一序列):): 碼組中的每個符號：碼組中的每個符號： 由符號間的獨立性，有由符號間的獨立性，有 碼組碼組 包含的信息量為：包含的信息量為： 根據熵的含義，隨著根據熵的含義，隨著 J J 的增大，有的增大，有 或或 SHJXIJJJXJX1JJjjP XP X 111l

28、ogloglogJJJjjJJjjjjI XP XP XP XI X LiSSXij,.2 , 1,: SHJXIIJJJ 離散無記憶信源離散無記憶信源(DMS)(DMS)的有損等長編碼的有損等長編碼( (續(xù)續(xù)) ) 典型序列集：滿足下列條件的序列典型序列集：滿足下列條件的序列 的集合稱之。的集合稱之。 其中其中 ，通常是一個很小的數。，通常是一個很小的數。 非典型序列集：典型序列集的補集稱之。非典型序列集：典型序列集的補集稱之。 典型序列集和非典型序列集構成了序列典型序列集和非典型序列集構成了序列 所有組合構成所有組合構成 符號組的空間。符號組的空間。 ,:JSJI XTJXH SH SJJ

29、X0JX 離散無記憶信源離散無記憶信源(DMS)(DMS)的有損等長編碼的有損等長編碼( (續(xù)續(xù)) ) 信源劃分定理：任給信源劃分定理：任給 ，當，當 J J 足夠大時，有足夠大時，有 即有：即有： 典型序列出現的概率：假設典型序列出現的概率：假設 那么那么 即有：即有： 典型序列趨于等概分布。典型序列趨于等概分布。 典型序列的數目：典型序列的數目：0,1JSP XTJ lim,1SJP TJ,JSXTJ 22J H SJ H SJP X 2JH SJP X 12,2J H SJ H SSTJ ,2JH SSTJ 離散無記憶信源離散無記憶信源(DMS)(DMS)的有損等長編碼的有損等長編碼(

30、(續(xù)續(xù)) ) 典型序列的出現概率：典型序列的出現概率： 即：即： 典型序列集典型序列集 為高概率集；為高概率集； 非典型序列集非典型序列集 為低概率集。為低概率集。 ,21JSJH SJSXTJP XTJ,STJ,STJ 離散無記憶信源離散無記憶信源(DMS)(DMS)的有損等長編碼的有損等長編碼( (續(xù)續(xù)) ) 典型序列集在整個序列空間中所占的比例：典型序列集在整個序列空間中所占的比例： 通常通常 取值很小，滿足取值很小，滿足 因而因而 說明雖然典型序列集是一個高概率集，但在整個序列空間中說明雖然典型序列集是一個高概率集，但在整個序列空間中可能只占很小的比例；可能只占很小的比例； 如果容許一

31、定的失真，只對典型序列編碼，對非典型序列不如果容許一定的失真，只對典型序列編碼，對非典型序列不予編碼傳輸，則可大大提高傳輸的效率。予編碼傳輸，則可大大提高傳輸的效率。 loglog,222J H SJLH SSJLJTJS log0LH S,0J 離散無記憶信源離散無記憶信源(DMS)(DMS)的有損等長編碼的有損等長編碼( (續(xù)續(xù)) ) 例如：已知二元信源例如：已知二元信源 信源的熵為：信源的熵為： 若取若取 所有的序列構成的集合為所有的序列構成的集合為 2 . 0:, 8 . 0:2211SPSSPSS S1 1S S1 1S S1 1序列出現概率序列出現概率P(SP(Si iS Sj j

32、S Sk k) )0.0080.0080.0320.0320.0320.0320.1280.1280.1280.1280.0320.032序列集序列集S S1 1S S2 2S S2 2S S1 1S S2 2S S1 1S S1 1S S1 1S S2 2S S2 2S S1 1S S1 1S S2 2S S2 2S S2 2S S2 2S S2 2S S1 1S S2 2S S1 1S S2 20.5120.5120.1280.128序列包含信息量序列包含信息量I(SI(Si iS Sj jS Sk k) )6.9666.9664.9664.9664.9664.9662.9662.9662

33、.9662.9664.9664.9660.9660.9662.9662.966序列包含平均信息量序列包含平均信息量I(SI(Si iS Sj jS Sk k)/3)/32.3222.3221.6551.6551.6551.6550.9890.9890.9890.9891.6551.6550.3220.3220.9890.989 722. 0SH3J 例如例如( (續(xù)續(xù)) )： 由：由： (1) (1) 若取若取 平均信息量落在該范圍內的序列為平均信息量落在該范圍內的序列為 如果要無失真地傳輸原來的全部序列，采用二進制編碼的如果要無失真地傳輸原來的全部序列，采用二進制編碼的 話，需要話，需要3

34、3比特；如僅傳輸典型序列，只需比特；如僅傳輸典型序列，只需2 2比特。比特。 3 . 0 SHJSSSISHkji022. 13 . 0722. 0422. 03 . 0722. 0JSSSIkji221SSS212SSS122SSS 例如例如( (續(xù)續(xù)) )： (1) (1) 若取若取 平均信息量落在該范圍內的序列為平均信息量落在該范圍內的序列為 如僅傳輸典型序列，同樣也只需如僅傳輸典型序列，同樣也只需2 2比特。比特。 5 . 0222. 15 . 0722. 0222. 05 . 0722. 0JSSSIkji221SSS212SSS122SSS222SSS 編碼速率編碼速率 假定信源輸

35、出按照假定信源輸出按照 J J 個符號構成的序列編碼個符號構成的序列編碼 編碼輸出編碼輸出 可能獲得的編碼輸出的碼字數為可能獲得的編碼輸出的碼字數為 相應的比特數為相應的比特數為 編碼速率編碼速率 R R 定義為：定義為： 若采用二進制編碼，則有若采用二進制編碼，則有1212,.,.,JJiLXXXXXS SS1212,.,.,JNiDYY YYYC CCNMDloglogMNRDJJNRJMlog 編譯碼傳輸模型編譯碼傳輸模型 譯碼錯誤概率定義為譯碼錯誤概率定義為 定義定義4.5.4 4.5.4 可達速率可達速率 給定信源和編碼速率給定信源和編碼速率R R，對任意的，對任意的 若存在若存在

36、和編譯碼方法：和編譯碼方法： 、 使當使當 時，有時，有 則該編碼速率稱為可達則該編碼速率稱為可達的的 反之稱速率是不可達的。反之稱速率是不可達的。JJEXXPP0J0JXCNYC10JJ EP 定理定理 4.5.5 4.5.5 假設假設 ，則速率，則速率 R R 是可達的；是可達的； 假設假設 ，則速率，則速率 R R 是不可達的。是不可達的。 該定理說明，假設該定理說明，假設 ，則存在編碼方法，當，則存在編碼方法，當 J J 足足夠夠 大時，只需對典型序列進行編碼，可使編碼誤差足夠地小。大時，只需對典型序列進行編碼，可使編碼誤差足夠地小。 SHR SHR SHR 在滿足一定的譯碼錯誤概率的

37、條件下，若只對典型序列編在滿足一定的譯碼錯誤概率的條件下，若只對典型序列編 碼，編碼效率可定義為碼，編碼效率可定義為 若記：編碼速率：若記：編碼速率： 自信息方差：自信息方差： 則不能正確譯碼的概率則不能正確譯碼的概率 滿足關系式滿足關系式 根據最后一個等式，可確定編碼序列的長度根據最后一個等式，可確定編碼序列的長度 J J 。 RSH SHR 212SHSISPiLiiI 22JII XPH SJJ 例如：例如： (1) (1)對二元符號進行無差錯的二進制編碼對二元符號進行無差錯的二進制編碼 此時此時 、 、 (2) (2) 若要求編碼效率若要求編碼效率 ， 求所需的編碼序列長度求所需的編碼

38、序列長度 J J 由由 得得1, 021SS1J2D1N1loglog211NRDJ 0.7220.7221H SR0.9410EP 0.9H SH SRH S 0.10.1 0.7220.08020.90.9H S 例如例如( (續(xù)續(xù)) )： 自信息方差：自信息方差： 最后得所需的符號序列長度最后得所需的符號序列長度 ( (該取值太大，可見等長編碼不易在實際系統中應用該取值太大，可見等長編碼不易在實際系統中應用) ) 22122112222loglog0.8 0.3220.7220.2 2.3220.7220.8 0.160.2 2.560.64LIiiip SI SH Sp Sp SH S

39、p Sp SH S252420.649.95 10100.0802IJ 霍夫曼霍夫曼(Huffman)(Huffman)編碼編碼 不等長編碼的概念：不等長編碼的概念： 對出現概率大的符號或符號組用位數較少的碼字表示；對出現概率大的符號或符號組用位數較少的碼字表示； 對出現概率小的符號或符號組用位數較大的碼字表示。對出現概率小的符號或符號組用位數較大的碼字表示。 霍夫曼編碼：霍夫曼編碼： 定理定理4.5.17 4.5.17 霍夫曼編碼一種最佳的不等長編碼。霍夫曼編碼一種最佳的不等長編碼。 霍夫曼編碼的應用條件：霍夫曼編碼的應用條件： 信源的分布信源的分布( (統計統計) )特性已知。特性已知。

40、記記 信源符號集為：信源符號集為： 編碼輸出符號集為：編碼輸出符號集為： LiSPSSii,.,2 , 1,:DiZZi,.,2 , 1,: 霍夫曼編碼的步驟：霍夫曼編碼的步驟：(1)(1)將將L L個信源符號按概率大小，以遞減次序，從上到下排成一列；個信源符號按概率大小，以遞減次序，從上到下排成一列；(2)(2)對處于最下面的概率最小的對處于最下面的概率最小的D D個信源符號，一一對應地分別賦個信源符號，一一對應地分別賦予碼字元素予碼字元素Z1Z1、Z2Z2、ZDZD，把這，把這D D個概率最小的信源符號相應個概率最小的信源符號相應的概率相加，所得的值用一個虛擬的符號代表，與余下的的概率相加

41、，所得的值用一個虛擬的符號代表，與余下的L-DL-D個個符號組成含有符號組成含有(L-D)+1=L-(D-1)(L-D)+1=L-(D-1)個符號的第一次縮減信源個符號的第一次縮減信源S(1)S(1)；(3)(3)對縮減信源對縮減信源S(1)S(1)仍按其概率大小以遞減次序從上到下排列，仍按其概率大小以遞減次序從上到下排列，按照步驟按照步驟(2)(2)的方法處理，得到一個含有的方法處理，得到一個含有(L-D)+1-D+1=L-2(D-1)(L-D)+1-D+1=L-2(D-1)個符號的第二次縮減信源個符號的第二次縮減信源S(2)S(2)；(4)(4)按照上述的方法，依次繼續(xù)下去，每次縮減所減少

42、的符號數按照上述的方法，依次繼續(xù)下去，每次縮減所減少的符號數是是D-1D-1個；只要縮減后的信源個；只要縮減后的信源SiSi符號的個數大于符號的個數大于D D，縮減就繼續(xù)進，縮減就繼續(xù)進行；行；(5)(5)當進行第當進行第k k次縮減后信源次縮減后信源S(k)S(k)符號個數剛好等于符號個數剛好等于D D，即有，即有 則對最后這則對最后這D D個符號分別賦予碼字元素個符號分別賦予碼字元素Z1Z1、Z2Z2、ZDZD；DDkL1 霍夫曼編碼的步驟霍夫曼編碼的步驟( (續(xù)續(xù)) )：(6)(6)從最后賦予的碼符號開始，沿著每一信源符號在各次縮減過從最后賦予的碼符號開始，沿著每一信源符號在各次縮減過程

43、中得到的碼字元素進行路線前向返回，達至每一信源符號，按程中得到的碼字元素進行路線前向返回，達至每一信源符號，按前后次序，把返回路途中所遇到的碼元素排成序列，這個序列，前后次序，把返回路途中所遇到的碼元素排成序列，這個序列，就是相應信源符號對應的碼字；就是相應信源符號對應的碼字；(7)(7)若進行若進行k k次縮減后，當進行第次縮減后，當進行第k k次縮減后信源次縮減后信源S(k)S(k)符號個數不符號個數不等于等于D D，即有，即有則中止縮減，增加則中止縮減，增加 個概率為個概率為0 0的虛假信源的虛假信源符號符號 重新編碼，使在重新編碼，使在k k次編碼后一定有次編碼后一定有 。DDkL11

44、DkLDm 0.00.:212121LmLixPxPxPxxxxxxxPXDDkL1 霍夫曼編碼霍夫曼編碼( (續(xù)續(xù)) ) 例如：已知信源符號集例如：已知信源符號集 編碼輸出的碼字符號集為編碼輸出的碼字符號集為 解：知：解：知： 嘗試嘗試 需要增加虛假符號數為需要增加虛假符號數為 新構建的信源滿足：新構建的信源滿足： S123456:8iiSSSSSSSP S2 , 1 , 0:Z6L3D2k3213261DkL1132631DkLDmDDkL3132711234561:80iiSSSSSSSSP S

45、例如例如( (續(xù)續(xù)) )：改造后的符號概率場為：改造后的符號概率場為 編碼過程如下編碼過程如下消息符號消息符號S S1 1符號概率P(S符號概率P(Si i) )SS1 1S S6 6S S5 5S S4 4S S3 3S S2 080.160.160 00.080.080.140.140 01 12 020.220 01 12 20.540.520.220 01 12 2碼字碼字C C1 1：1：1C C7 7：22：22C C6 6：21：21C C5

46、 5：20：20C C4 4：02：02C C3 3：01：01C C2 2：00：00S S(1)(1)S S(2)(2)1 0.242 0.202 0.182 0.162 0.142 0.081.76n 碼字符號 信源符號 例如例如( (續(xù)續(xù)) )： 平均碼字長度：平均碼字長度： 例如例如( (續(xù)續(xù)) )： 如果不加入虛假符號，直接進行編碼，則有如果不加入虛假符號，直接進行編碼，則有 平均碼字長度平均碼字長度2 0.242 0.202 0.182 0.162 0.142 0.082n 碼字符號 信源符號 霍夫曼編碼霍夫曼編碼( (續(xù)續(xù)) ) 碼字長度的均勻性和方差碼字長度的均勻性和方差 在

47、同樣的平均碼字長度的情況下，碼字長度越均勻，對傳輸在同樣的平均碼字長度的情況下，碼字長度越均勻，對傳輸越有利。越有利。 定義定義4.5.16 4.5.16 碼字長度的方差碼字長度的方差 其中其中 編碼過程的排序過程不同會影響碼長的方差。編碼過程的排序過程不同會影響碼長的方差。2221nnLCiiiiEnP Sn1nLiiinP S 碼字長度的均勻性和方差碼字長度的均勻性和方差( (續(xù)續(xù)) ) 例如：信源的符號空間為例如：信源的符號空間為 編碼輸出碼字集編碼輸出碼字集 編碼方式編碼方式1 112345:0.10.1iiSSSSSSP S1 , 0:Z消息符號消息符號S S1 1

48、符號概率P(S符號概率P(Si i) )S S5 5S S4 4S S3 3S S2 0.10 01 1碼字碼字C C1 1：1：1C C5 5：0011：0011C C4 4：0010：0010C C3 3：000：000C C2 2：01：00.20 01 0.40 01 0.40 01 1S S(1)(1)S S(2)(2)S S(3)(3) 例如：編碼方式例如：編碼方式1(1(續(xù)續(xù)) ) 平均碼長：平均碼長： 方差：方差：1 0.42

49、0.23 0.24 0.14 0.12.2An 碼字符號 信源符號252122222n0.41.36AiiiP Sn 編碼方式編碼方式2 2 平均碼長：平均碼長： 方差：方差：消息符號消息符號S S1 1符號概率P(S符號概率P(Si i) )S S5 5S S4 4S S3 3S S2 0.10 01 1碼字碼字C C1 1：00：00C C5 5：011：011C C4 4：010：010C C3 3：11：11C C2 2：10：100.20.20 01 10.20.2

50、0.40.40 01 0.40 01 S S(1)(1)S S(2)(2)S S(3)(3)0.40.42 0.42 0.22 0.23 0.1 3 0.12.2Bn 碼字符號 信源符號252122222n0.40.16BiiiP Sn 雖然平均碼長一樣，但編碼方法雖然平均碼長一樣，但編碼方法2 2使得輸出的碼長更為均勻。使得輸出的碼長更為均勻。結論：結論： 在霍夫曼編碼過程中，當對縮減信源概率重新排列時，應在霍夫曼編碼過程中，當對縮減信源概率重新排列時，應使合并得到的局部

51、概率和，盡量使其處于最高位置；使合并得到的局部概率和，盡量使其處于最高位置； 這樣可以使得合并元素重復編碼的次數減少，降低碼字長度這樣可以使得合并元素重復編碼的次數減少，降低碼字長度的方差，使得碼字長度比較均勻。的方差，使得碼字長度比較均勻。 22BA 失真的概念失真的概念 失真是指用某種尺度衡量的實際的信源樣值失真是指用某種尺度衡量的實際的信源樣值 與信號經過變與信號經過變化后對應值化后對應值 之差。之差。 失真函數：對由符號失真函數：對由符號 變?yōu)榉栕優(yōu)榉?引起誤差造成影響的大引起誤差造成影響的大小，人為定義一個非負函數稱之：小，人為定義一個非負函數稱之： 失真函數的取值通常反映失真產

52、生的代價。失真函數的取值通常反映失真產生的代價。 kx kx0,iixxdkx kx 失真函數的示例：失真函數的示例： ( (漢明失真函數漢明失真函數) ) 連續(xù)信號無失真有失真dttxtxTtxtxdxxxxxxdxxxxdxxxxdTTTkkkkkkHpkkkkkkkk22221lim,01, 率失真理論在通信中的應用率失真理論在通信中的應用 已知輸入信號集：已知輸入信號集： 輸出信號集：輸出信號集： 對離散無記憶信道，有對離散無記憶信道，有 失真函數：對由輸入符號失真函數：對由輸入符號 變?yōu)檩敵龇栕優(yōu)檩敵龇?引起誤差造引起誤差造成影響的大小，可人為定義一個非負函數：成影響的大小，可人

53、為定義一個非負函數： MixXi,.,2 , 1,:NjyYj,.,2 , 1,:MNMMNNijxypxypxypxypxypxypxypxypxypxypXYp/././././212222111211,01,2,.,;1,2,.ijd x yiM jNjyix 失真函數矩陣：與轉移概率矩陣對應，可定義相應的失真度失真函數矩陣：與轉移概率矩陣對應，可定義相應的失真度矩陣：矩陣： 平均失真度平均失真度 定義定義4.6.1 4.6.1 平均失真度定義為平均失真度定義為 111212122212,.,.,.,.,NNMMMNd x yd x yd x yd xyd xyd xyDd xyd xyd xy 1111,/MNijijijMNijijiijDd x yp x yd x yp xp yx 平均失真度與信道轉移概率的關系平均失真度與信道轉移概率的關系 如給定信源的分布特性如給定信源的分布特性 和失真函數和失真函數 的定義，平均失真度由信道轉移概率決定的定義，平均失真度由信道轉移概率決定 Mixpi,.2 , 1, jiyxd,/jiDD p yx 率失真函數率失真函數 已知平均互信息定義為已知平均互信息定義為 平均互信息量是信道轉移概率平均互信息量是信道轉移概率 的的 U U 型凸函數。型凸函數。 MiNjjijiyxIyxpYX