北京郵電大學 通信原理 第七章 信源與信源編碼II

1、第七章 信源與信源編碼 彭濤 P 2 7.1 引言 n信源編碼：去掉信源輸出中的冗余信息，提高 有效性 n內(nèi)容 n信源分類及其統(tǒng)計特性 n信息熵，信源剩余度 n互信息，各類熵與互信息的關(guān)系 nHuffman編碼 n無失真/限失真信源編碼定理 n率失真函數(shù) n矢量量化、變換編碼 P 3 7.2 信源分類及其統(tǒng)計特性描 述 n信源分類 n連續(xù)/模擬信源 n離散/數(shù)字信源 n重點研究 P 4 7.2 信源分類及其統(tǒng)計特性描 述 n單消息（符號）離散信源 n只輸出一個離散符號 n統(tǒng)計特性描述 1 1 1 , , 11,2,1 ii in iin n ii i XxP x Xxxx P xP xP xP

2、 x P xinP x 用符號可能取值范圍 和符號取值 的概率描述 其中，0，且 P 5 7.2 信源分類及其統(tǒng)計特性描 述 n離散消息（符號）序列信源 n輸出一個離散消息（符號）序列 n統(tǒng)計特性描述 1 1 112132111 1 1 , , ,|,|, , , L L iL LL iL iLLL L i n i n LL XXXX xxxxnX P xP xxxP xP xxP xx xP xxx aaa X P aP aP aP x 離散消息序列由 個符號組成，則消息序列可表示成 維隨機矢量 ， 其可能取值有種可能性，構(gòu)成取值集合 則離散消息序列的統(tǒng)計特性表示為取值集合及其取值概率 P

3、6 7.2 信源分類及其統(tǒng)計特性描 述 n離散消息（符號）序列信源 n離散無記憶序列信源：序列中前后符號相互 統(tǒng)計獨立 n離散有記憶序列信源：序列中前后符號不是 相互統(tǒng)計獨立的 n可用馬爾可夫鏈表示 1 1 , L lLl l P xP xxxP x P 7 7.3 信息熵H(X) n信息的基本特征：不確定性。因此信息應(yīng)該是 概率P的函數(shù) n信息的兩個特點 n隨概率P的遞減性：概率越大，信息量越小 n可加性：兩個獨立消息的總信息量應(yīng)是兩個消息的 信息量的和 n滿足這兩個條件的表示信息量的函數(shù)只有一種 可能：對數(shù)函數(shù) P xI P x ， I P x P yI P xI P y P 8 7.3

4、信息熵H(X) n單消息離散信源的信息度量 n自信息量：出現(xiàn)某個消息時的信息量 n理解：消息出現(xiàn)概率越小，信息量越大 1 loglog ii i I P xP x P x P 9 7.3 信息熵H(X) n單消息離散信源的信息度量 n兩個單消息離散信源X,Y的聯(lián)合信息量 |log| |log| ,log, ii iiii ii iiii ii iiii xy I P yxP yx yx I P xyP xy xy I P x yP x y 知道了消息 的情況下，消息 新帶來的信息量： 知道了消息 的情況下，消息 新帶來的信息量： 兩個消息 ， 一共帶來的信息量： P 10 7.3 信息熵H(X

5、) n單消息離散信源的信息熵 n前面定義的是一個具體消息的信息量，因為信源輸 出的消息有多種可能性，所以可以把信息熵理解為 這個輸出消息（考慮多種可能性）的平均信息量 n信息熵也可以理解為對信源的不確定性的平均度量 n在各種可能性等概時，信源的信息熵最大（圖7.3.1） 1 loglog n iiii i H XE I P xEP xP xP x P 11 7.3 信息熵H(X) n信息量和信息熵的單位 n對數(shù)以2為底時，單位為比特(bit) n對數(shù)以e為底時，單位為奈特(Nat) n對數(shù)以10為底時，單位為笛特(Det) n1bit=0.693Nat=0.301Det P 12 7.3 信息

6、熵H(X) n兩個單消息離散信源的聯(lián)合熵和條件熵 11 11 ,/ ,log,log, / |log|,log| |log| nm ijijijij ij nm jijiijji ij iji X Y H X YE I P x yEP x yP x yP x y H Y XE I P yxEP yxP x yP yx H X YE I P xyEP x 聯(lián)合熵 兩個符號帶來的總信息熵 平均信息量 條件熵 知道一個符號條件下，另一個符號帶來的信息熵 平均信息量 11 ,log| nm jijij ij yP x yP xy P 13 7.3 信息熵H(X) n聯(lián)合熵和條件熵的一些性質(zhì) max 1

7、,| Shannon| , 3, , H X YH XH Y XH YH X Y H XH X YH YH Y X X Y X Y H X YH XH Y 理解為兩符號先后到達的過程：兩個符號的總信息熵 一個符號的信息熵知道這個符號的條件下另一個符號帶來的信息熵 2不等式：； 理解：一個消息沒有任何前兆時帶來的信息肯定大于等于有前兆帶來的信息 當獨立時，等號成立；否則都是大于號成立 統(tǒng)計獨立時，其聯(lián)合熵取最大值 兩符號信息熵之和 P 14 7.3 信息熵H(X) n離散消息序列信源的信息熵、剩余度 1 112111 11211 11 , ,|, 0|,| 11 ,lim, iL LLL LL

8、LLL L XXXX H XH XXH XH XXH XXX H XXXH XXH X HXH XXHXH XX LL 離散平穩(wěn)有記憶信源輸出的消息序列為 1 其總信息熵為 其中，每發(fā)一個符號具有不同的信息熵 依次遞減 ： 2 定義平均符號信息熵為：總信息熵除以符號個數(shù) ， P 15 7.3 信息熵H(X) n離散消息序列信源的信息熵、剩余度 2102 0 0 30log N 4 HXHXHXHXN HX HX H 容易看出： 其中：是具有 種取值可能的單消息信源的最大信息熵 等概時 符號所含的信息熵依次遞減，平均符號信息熵自然越來越小 編碼時如果有以下假設(shè)：消息序列的各符號統(tǒng)計獨立；各取值等

9、概出現(xiàn) 則實際是沒有對信源進行仔細的研究，利用其統(tǒng)計特性， 認為其平均符號信息熵為。如實際中的文字編碼 這必然會產(chǎn)生大量冗余，這正是進行壓縮編碼的前提 信源效率： 0 1 X R HX ；信源剩余度： P 16 7.4 互信息I(X;Y) n互信息的定義I(X;Y)及理解 ,| | |0 ;|log; | |log; | | i ij ij j ji ji H X YH XH Y XH YH X Y H XH X YH YH Y X H XH X YH YH Y X P x I X YH XH X YEE i x y P xy P y H YH Y XEE i yx P yx H XXH X

10、YY X 前面已知： ； 由此可見： 互信息定義： 互信息的理解：是 所含的信息；是已知 的條件下 還能帶來的信息量。那么兩YX YX 者之差自然就是由于知道 使得 減 少的信息量，也即由 可以得到的關(guān)于 的信息量 P 17 7.4 互信息I(X;Y) n各種信息熵的關(guān)系 P 18 7.5 無失真離散信源編碼定理 n信源編碼 n離散信源輸出的是各種離散消息和符號 n模擬信源輸出的是模擬信號（連續(xù)信號） n為了進行數(shù)字通信，必須進行信源編碼，將 信源輸出轉(zhuǎn)變成數(shù)字信息 n信源編碼中考慮的兩個基本問題 n編碼輸出的信息速率（總是希望它盡可能?。?n編碼所造成的失真 P 19 7.5 無失真離散信源

11、編碼定理 n無失真離散信源編碼 n研究在無失真編譯碼條件下，傳送離散信源 發(fā)出信息的最小編碼速率 n兩種基本編碼方法 n等長編碼：編碼輸出的所有碼字長度都相同 n變長編碼：編碼輸出碼字長度不相同 P 20 7.5 無失真離散信源編碼定理 n等長編碼定理原理圖 n無失真要求：nL=mK（無信息丟失） n有效性要求： mK盡可能小 信源編碼 輸出 L n共有種消息序列 1lL xxxx輸入 1kK K SSS m S 總碼組數(shù) P 21 7.5 無失真離散信源編碼定理 n等長編碼定理 n編碼滿足下式，當L足夠大時，必然可以使 譯碼差錯率趨近于0（無失真或近似無失真） n反之，如果上式不滿足，即 R

12、=K*log2m/L=H(X)，則L足夠大時，必可 使譯碼差錯率趨近于0；反之，譯碼必定出 錯且差錯率不趨近于0 2 log2 KK RmmR LL 進行二進制編碼時， P 23 7.5 無失真離散信源編碼定理 n等長編碼和變長編碼的比較 n等長編碼將信源輸出符號序列的任意一種取 值（概率可能不同）都編碼成相同長度的輸 出碼字，沒有利用信源的統(tǒng)計特性 n變長編碼可以根據(jù)信源輸出符號序列各種取 值的概率大小不同，將他們編碼成不同長度 的輸出碼字，利用了信源的統(tǒng)計特性。因此 又稱其為熵編碼。 P 24 7.5 無失真離散信源編碼定理 n等長編碼和變長編碼的比較 n編碼效率 n由于變長編碼利用了信源

13、的統(tǒng)計特性，因此， 一般在相同的編碼效率和譯碼差錯率要求下， 變長編碼需要的信源消息序列長度L遠小于 等長編碼需要的L 2 , log/ L H XL H XH X KmKK L 進行二進制編碼時 P 25 Huffman編碼 n等長編碼：對信源輸出的各種出現(xiàn)概率的符號 用等長的碼字表示 n沒有充分利用信源的統(tǒng)計特性 n變長編碼：根據(jù)信源輸出符號出現(xiàn)概率不同選 擇碼字，出現(xiàn)概率大的用短碼，出現(xiàn)概率小的 用長碼 n利用了信源的統(tǒng)計特性，其編碼效率高于等長編碼 nHuffman編碼：Huffman提出的一種變長編碼 n是單消息信源的最佳變長編碼 P 26 Huffman編碼 n圖解Huffman編

14、 碼方法 n1.寫出消息概率 n2.對最小的兩概 率編碼（0/1） n3.對這兩概率合 并 n4.重復2和3，直 至結(jié)束 n5.自頂而下到達 某消息即得編碼 P 27 Huffman編碼 n確定了對信源符號的編碼規(guī)則，可進行編譯碼 n這種特性得益于Huffman編碼的非延長性和異前置性 n非延長性：把任一許用碼組延長（添加數(shù)字）都得不到許用 碼字；異前置性：將任一許用碼組的最后一位或幾位去掉都 得不到許用碼組。 n這兩種性質(zhì)可以從Huffman編碼的規(guī)則看出來 1234567 53624375 53624375 10 11 000 001 010 0110 0111 010 000 0110

15、11 001 000 0111 010 0100000110110010000111010 xxxxxxx x x x x x x x x x x x x x x x x 如果信源輸出一列消息： 可得到編碼序列： 同樣，如果接收端收到序列： 由編碼規(guī)則，很容易將其譯碼出來： P 28 7.7 信息率失真R(D)函數(shù) n在前面的討論中，其基本出發(fā)點是如何保證信 息的無失真?zhèn)鬏?。但在許多實際應(yīng)用中，人們 并不要求完全無失真地恢復消息，而是只要滿 足一定的條件，近似地恢復信源發(fā)出的消息就 可以了。 n原因1：實際的信源常常是連續(xù)的，信息率無限大 n原因2：實際信道帶寬是有限的，所以信道容量受 限制

16、n原因3：實際生活中，人們一般并不要求獲得完全 無失真的消息，通常只要求近似地再現(xiàn)原始消息， 即允許一定的失真存在。如：聽電話、看電影 P 29 7.7 信息率失真R(D)函數(shù) n信息率失真理論 n香農(nóng)定義了信息率失真函數(shù)R(D) n定理指出：在允許一定失真度D的情況下，信 源輸出的信息率可壓縮到R(D) n信息率失真理論是信源編碼（包括量化（模 數(shù)轉(zhuǎn)換）、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮） 的理論基礎(chǔ) P 30 7.7 信息率失真R(D)函數(shù) n失真函數(shù)和平均失真 n對X（單消息信源取值空間）和Y（單消息信 宿取值空間），可定義它們的失真函數(shù) n在此基礎(chǔ)上，定義平均失真 0 , 0 ij ij

17、ij xy d x y xy ,|, ijijiij ij dE d x yP xP yx d x y P 31 7.7 信息率失真R(D)函數(shù) n允許失真D和試驗信道集合PD n人們對信息傳輸?shù)氖д嬗幸螅@個要求就 是允許失真D n當信源確定（P(X)已知），允許失真度D也 給定時，選擇信道使平均失真小于允許失真。 凡滿足要求的信道稱為D失真許可的試驗信 道，簡稱試驗信道，所有試驗信道的集合就 是PD dD 保真度條件 |:|, Djiijiij ij PP yxdP xP yx d x yD P 32 7.7 信息率失真R(D)函數(shù) n互信息I(X;Y)的性質(zhì) n性質(zhì)1：互信息I(X;Y

18、)是先驗概率P(X)的上凸 函數(shù)，研究信道容量時用到 n性質(zhì)2：互信息I(X;Y)是信道轉(zhuǎn)移概率概率 P(Y|X)的下凸函數(shù)，研究信息率失真函數(shù)時 用到 ;| | |log;| | ji ijijji ij iji i I X YH YH Y X P yx P xP yxI P yP yx P xP yx P 33 7.7 信息率失真R(D)函數(shù) n信息率失真函數(shù)R(D) n在信源和允許失真給定以后，PD是滿足允許 失真的試驗信道集合，平均互信息I(X;Y)是 信道傳遞概率p(yj|xi)的下凸函數(shù)，所以在PD 中一定可以找到某個試驗信道，使I(X;Y)達 到最小，即 n這個最小值R(D)稱為

19、信息率失真函數(shù)，簡稱 率失真函數(shù) | min; jiD P y xP R DI X Y P 34 7.7 信息率失真R(D)函數(shù) n信息率失真函 數(shù)R(D)的性質(zhì) n可以證明：R(D) 是關(guān)于允許失 真D的單調(diào)遞減 的下凸函數(shù) P 35 7.7 信息率失真R(D)函數(shù) n信息率失真函數(shù)的物理意義 n信息率失真函數(shù)是在滿足保真度條件下，信宿必須獲得的平 均信息量的最小值，是信源必須輸出的最小信息率 n信息傳輸速率本質(zhì)上是描述信源特性的，因此R(D) 也應(yīng)該是 僅僅用于描述信源 n若信源消息經(jīng)無失真編碼后的信息傳輸速率為R，則在保真度 條件下信源編碼輸出的信息率就是R(D)，且 n說明在保真度條件

20、下信源編碼比無失真情況得到了壓縮，同 時R(D)是保真度條件下對信源進行壓縮的極限值，亦即信源 信息率可壓縮的最低限度，它僅取決于信源特性和保真度要 求，與信道特性無關(guān) 0R DR DRH X P 36 7.7 信息率失真R(D)函數(shù) n補充內(nèi)容：信道容量問題 n信道容量和信息率失真函數(shù)都是求互信息I(X;Y)的 極值問題，有相仿之處，故常稱為對偶問題 n平均互信息I(X;Y)是信源概率分布P(X) 的上凸函數(shù)， 根據(jù)上凸函數(shù)定義，如果I(X;Y)在定義域內(nèi)對P(X) 的極值存在，則該極值一定是極大值。信道容量就 是在固定信道情況下(P(yj|xi)確定)，求平均互信息 極大值的問題，即 ma

21、x; P X CI X Y P 37 7.7 信息率失真R(D)函數(shù) n補充內(nèi)容：信道容量問題 n信道容量C只與信道情況，即信道的條件轉(zhuǎn) 移概率p(yj|xi) 有關(guān)，反映信道特性，與信 源特性無關(guān) n由于平均互信息與信源的特性有關(guān)，為了排除信 源特性P(X)對信道容量的影響，采用的做法是在 所有的信源中以那個能夠使平均互信息達到最大 的信源為參考。所以信道容量僅與信道特性有關(guān)， 信道不同，C亦不同 P 38 7.7 信息率失真R(D)函數(shù) n研究信息率失真函數(shù)和信道容量的意義 n研究信息率失真函數(shù)：為了解決在已知信源和允許 失真度D的條件下，使信源必須傳送給信宿的信息 率最小。即用盡可能少的

22、碼符號盡快地傳送盡可能 多的信源消息，以提高通信的有效性。這是信源編 碼問題 n研究信道容量：在實際應(yīng)用中，研究信道容量是為 了解決在已知信道中傳送最大信息率問題。目的是 充分利用已給信道，使傳輸?shù)男畔⒘孔畲蠖l(fā)生錯 誤的概率任意小，以提高通信的可靠性。這就是信 道編碼問題 P 39 7.8 限失真信源編碼定理 n限失真信源編碼定理 n設(shè)有一離散平穩(wěn)無記憶信源，若該信源的信 息率失真函數(shù)是R(D)，對于任意允許平均失 真D0，和任意小的0，若實際傳輸信息 率RR(D) ，只要信源序列長度L足夠長，一 定存在一種編碼方式C，使譯碼后的平均失 真dD+；反之，若RD n該定理可以推廣到連續(xù)平穩(wěn)無記

23、憶信源 P 40 7.8 限失真信源編碼定理 n限失真信源編碼定理 n理解1：信息率失真函數(shù)R(D)是一個界限， 只要實際傳輸信息率R大于這個界限，就可 以通過信源編碼技術(shù)將譯碼失真限制在給定 的范圍內(nèi)。即通信的過程中雖然有失真，但 仍能滿足要求，否則就不能滿足要求。 n理解2：限失真信源編碼的方向是尋求與信 源的信息率失真函數(shù)R(D)相匹配的編碼，即 RR(D)；這與無失真信源編碼相似，后者 尋求與信源信息熵匹配的編碼，即 RH(X)=R(D=0) P 41 7.8 限失真信源編碼定理 n實現(xiàn)限失真信源編碼的兩類方法 n1.適應(yīng)信源方法，即尋找適應(yīng)信源的客觀概 率統(tǒng)計特性的編碼方法。如充分考

24、慮信源消 息序列的各消息變量（或各取樣值）之間的 相關(guān)性，進行矢量量化編碼 n2.改造信源方法，即通過改造信源解除信源 消息序列的各消息變量（或各取樣值）之間 的相關(guān)性。如預(yù)測編碼和變換編碼 P 42 7.9.5 矢量量化 n標量量化的問題 n沒有充分利用信源消息序列中各個樣值之間 的相關(guān)性，編碼之后的信息率通常較高 n矢量量化的思路 n充分利用信源消息序列中各個樣值之間的相 關(guān)性，通過聯(lián)合量化，可以大幅度降低編碼 后的信息率，提高編碼效率 P 43 7.9.5 矢量量化 n基本原理 n將模擬信號抽樣序列中的每K個樣值分為一組，構(gòu) 成K維歐式空間RK中的一個隨機矢量X n將K維空間分割成L個子

25、空間（胞腔）Ci。每個子空 間Ci中有一個離散的K維矢量Yi，稱為量化矢量或重 建矢量 n若輸入矢量X落在某子空間Ci中，則可將X量化維其 中的量化矢量Yi。這樣傳輸時，只需要傳輸量化矢 量Yi的標號i 12 , K Xx xx K i i CR P 44 7.9.5 矢量量化 n最佳矢量量化基本算法（LGB算 法） n使量化誤差/失真最小的矢量量化 算法即為最佳矢量量化，常用的失 真度量為均方誤差 nLGB算法的兩個條件： n1.若輸入矢量X與量化矢量Yi之間 的失真d(X,Yi)小于與其它任何量化 矢量Yj之間的失真d(X,Yj)，則判為 屬于Ci，即Ci是符合此條件的所有 矢量的集合 n

26、2.各子空間的量化矢量應(yīng)為該子空 間的概率質(zhì)心 n實現(xiàn)：迭代算法 2 2 1 , k K ikii k d X YxyXY :, iij CX d X Yd X Yji i i X C i X C Xp X dX Y p X dX P 45 7.10.1 預(yù)測編碼 n原理 n預(yù)測編碼不直接對信源輸出信號進行編碼， 而是先對信源輸出信號進行預(yù)測變換，對源 信號和預(yù)測變換后信號的差值（誤差）信號 進行編碼 n預(yù)測器輸出 n預(yù)測函數(shù)f的選?。壕€性函數(shù)、非線性函數(shù) 預(yù)測器 編碼器 輸出l x信源輸出 lll exx l x 12 , llll K xf xxx P 46 7.10.1 預(yù)測編碼 n根據(jù)

27、預(yù)測器輸入數(shù)據(jù)來源進行分類 nDPCM：預(yù)測器輸入為誤差信號的量化結(jié)果 nPCM：直接將信源輸出作為預(yù)測器輸入 n噪聲反饋型：前兩類的結(jié)合 P 47 7.10.1 預(yù)測編碼 nDPCM n其中，線性預(yù)測器輸出為 l x 量化器 線性 預(yù)測器 l x 編碼 理想 信道 譯碼 線性 預(yù)測器 l x l x lll exx l u l C l C l u l x l x 1 K lkl kk k xx 是一組預(yù)測系數(shù) P 48 7.10.1 預(yù)測編碼 nDPCM n易見，線性預(yù)測器在預(yù)測編碼中的作用非常 關(guān)鍵，其中預(yù)測系數(shù)的選取對編碼性能的影 響很大 n最佳線性預(yù)測（若采用MMSE即最小均方誤 差準

28、則）需滿足如下條件 2 2 2 1 0 K lkl k ll k l kkk Exx Exx E e P 49 7.10.1 預(yù)測編碼 nDPCM n由前頁式子可得以下方程 n由上面方程即可求得線性預(yù)測器的最優(yōu)預(yù)測 系數(shù) 1 2 1011 2102 120 opt opt Kopt ll k RRRR K RRRR K R KR KR KR R kE xx 其中，為相關(guān)函數(shù) P 50 7.10.1 預(yù)測編碼 nDPCM n由于在預(yù)測時是采用最小均方誤差準則，對 一些相關(guān)性較強的信源如話音，誤差信號的 方差遠小于源信號，這就意味著量化時量化 級數(shù)可大大減少，即可降低編碼速率 n應(yīng)用實例：CCITT于1984年提出的G.721建 議就是速率為32kbps的ADPCM話音編碼 P 51 7.10.1 預(yù)測編碼 nM n最簡單的DPCM就是M（增量調(diào)制） nM中量化器級數(shù)只有兩級，這樣編碼時僅編碼為1bit（差值為正編為1， 反之編為0） n預(yù)測器此時簡化為一個延時器，進行一個抽樣間隔的延時 n譯碼時規(guī)定一個增量值。接收1時在前