信源編碼及信道編碼1

第3章(1)

信源及信源編碼郵箱:frankgy@126.com

電話2/67-學習目標知道為什么要進行信源編碼？掌握信源及信源的數(shù)學模型掌握信息熵的概念了解典型的無失真信源編碼了解典型的限失真信源編碼學習完本節(jié)課程，您應(yīng)該能夠：-3/67-課程內(nèi)容

3.1信源及分類3.2信源的數(shù)學模型3.3信息的度量—信息熵3.4無失真信源編碼3.5限失真信源編碼-4/67-3.1信源及分類信源和信道：在現(xiàn)代通信中，信源和信道是組成通信系統(tǒng)的最基本單元。信源是產(chǎn)生信息的源信道則是傳送載荷信息的信號所通過的通道信源與信宿之間的通信是通過信道來實現(xiàn)的。-5/67-3.1信源及分類(續(xù))為什么要進行信源編碼？信源信源編碼信道編碼調(diào)制傳輸媒介信源譯碼信宿信道譯碼解調(diào)噪聲干擾若不進行編碼，信源會存在大量的統(tǒng)計多余的成分它完全可以利用信源的統(tǒng)計特性在接收端恢復(fù)出來-6/67-3.1信源及分類(續(xù))信源編碼信號要通過數(shù)字信道傳輸，首先要進行數(shù)字化處理，包括采樣、量化、編碼、壓縮等。信源編碼保證了信號能否進入有一定條件限制的數(shù)字信道里。信源編碼的任務(wù)是在分析信源統(tǒng)計特性的基礎(chǔ)上，設(shè)法通過信源的壓縮編碼去掉這些統(tǒng)計多余成分。保證信號進入有一定條件限制的數(shù)字信道。-7/67-3.1信源及分類(續(xù))信源的分類按刻畫信源的隨機過程的性質(zhì)劃分無記憶信源有記憶信源平穩(wěn)信源非平穩(wěn)信源連續(xù)信源離散信源。根據(jù)輸出符號間的依賴關(guān)系統(tǒng)計特性是否隨時間的起點改變根據(jù)信源符號的取值-8/67-3.1信源及分類(續(xù))按取值時刻與取值集合的連續(xù)與離散劃分時間(空間)取值信源種類舉例數(shù)學描述離散離散離散信源（數(shù)字信源）文字、數(shù)據(jù)、離散化圖象

離散隨機變量序列

離散連續(xù)連續(xù)信號跳遠比賽的結(jié)果、語音信號抽樣以后

連續(xù)隨機變量序列

連續(xù)連續(xù)波形信源（模擬信源）

語音、音樂、熱噪聲、圖形、圖象

隨機過程

連續(xù)離散不常見-9/67-課程內(nèi)容

3.1信源及分類3.2信源的數(shù)學模型3.3信息的度量—信息熵3.4無失真信源編碼3.5限失真信源編碼-10/67-3.2信源的數(shù)學模型離散信源數(shù)學模型：集合A中，包含該信源的所有可能輸出的消息，集合P中包含對應(yīng)消息的概率密度，各個消息的輸出概率總和應(yīng)該為1。AP=a1a2……aqp1p2……pq-11/67-3.2信源的數(shù)學模型(續(xù))連續(xù)信源數(shù)學模型：每次只輸出一種消息，但消息的可能數(shù)目是無窮多個。-12/67-課程內(nèi)容

3.1信源及分類3.2信源的數(shù)學模型3.3信息的度量—信息熵3.4無失真信源編碼3.5限失真信源編碼-13/67-3.3.1信息的度量中的概念度量通信的技術(shù)性能

度量通信的技術(shù)性能主要是從通信的數(shù)量與質(zhì)量兩方面來討論的一般數(shù)量指標用有效性度量，主要與信源統(tǒng)計特性有關(guān)而質(zhì)量指標用可靠性度量。主要決定于信道的統(tǒng)計特性有效性(數(shù)量指標)信道一定時,系統(tǒng)能夠傳輸信息內(nèi)容的多少?？煽啃?質(zhì)量指標)系統(tǒng)接收端恢復(fù)信息的準確程度。-14/67-3.3.1信息的度量中的概念(續(xù))自信息：一個事件（消息）本身所包含的信息，它是由事件的不確定性決定的。比如拋擲一枚硬幣的結(jié)果是正面這個消息所包含的信息。

互信息：一個事件所給出關(guān)于另一個事件的信息比如今天下雨所給出關(guān)于明天下雨的信息-15/67-3.3.1信息的度量中的概念(續(xù))平均自信息：事件集（用隨機變量表示）所包含的平均信息，它表示信源的平均不確定性。比如拋擲一枚硬幣的試驗所包含的信息。

平均互信息一個事件集所給出關(guān)于另一個事件集的平均信息比如今天的天氣所給出關(guān)于明天的天氣的信息。-16/67-3.3.1信息的度量中的概念(續(xù))什么是信源的不確定性信源發(fā)出的消息中必須包含信宿事先不知道的內(nèi)容，這樣發(fā)出的信息才有意義，這就是信源的不確定性。消息的不確定性越大，信息量就越多信源提供的不確定度就是信源提供的信息量。信道信源信宿-17/67-3.3.1信息的度量中的概念(續(xù))什么是信源的不確定性(續(xù))自信息量：設(shè)信源發(fā)出的消息Xi的概率為P(i),I(xi)表示Xi提供的信息量

I(xi)=log(1/P(i))對數(shù)若取2為底，則信息量的單位為比特（bit）對數(shù)若取e為底，則信息量的單位為奈特（nat）對數(shù)若取10為底，則信息量的單位為笛特（Det）換算公式如下：

1bit=0.693Nat=0.301Det1、當事件發(fā)生前，表示該事件發(fā)生的不確定性；2、當事件發(fā)生后，表是該事件所提供的信息量-18/67-3.3.1信息的度量中的概念(續(xù))舉例:當某事件必然發(fā)生時，就不存在不確定性，即不確定性為0。即P(xi)=1時，I(1)=-log1=0當某事件幾乎不發(fā)生時（或發(fā)生概率很?。洳淮_定性應(yīng)趨于無窮大，即limI[p(xi)]=-log0=∞發(fā)生概率小的事件其不確定性比大概率事件大，即I(x1)=-logp(x1)I(x2)=-logp(x2),(p(x1)>p(x2)),則I(x1)<I(x2)-19/67-例：設(shè)天氣預(yù)報有兩種消息，晴天和雨天，出現(xiàn)的概率分別為1/4和3/4，我們分別用來表示晴天，以來表示雨天，則我們的信源模型如下：3.3.1信息的度量中的概念(續(xù))-20/67-3.3.2離散信源的平均信息量—信息熵離散信源由有限個消息符號或狀態(tài)構(gòu)成的信源就是有限信源也稱離散信源。信息熵設(shè)離散信源X可輸出n種彼此獨立的符號,各符號出現(xiàn)概率如下：

X:x1,x2,……,xn

P(x):P(x1),P(x2),……,P(xn)

則該信源的平均信息量為：-21/67-3.3.2離散信源的平均信息量—信息熵(續(xù))信息熵定義：信源各個離散消息的自信息量的數(shù)學期望(即概率加權(quán)的統(tǒng)計平均值)為信源的平均信息量，一般稱為信源的信息熵，也叫信源熵或香農(nóng)熵，有時稱為無條件熵或熵函數(shù)，簡稱熵，記為。信息熵具有以下兩種物理含義：1、表示信源輸出前信源的平均不確定性2、表示信源輸出后，每個符號所攜帶的平均信息量-22/67-3.3.2離散信源的平均信息量—信息熵(續(xù))舉例例：對于二元離散信源，出現(xiàn)0、1的概率分別為：P(0)=p,P(1)=1-p,則該信源熵為：數(shù)學證明只有當p=1/2時H2(x)取值最大:H2(x)=1當p=1或p=0時H2(x)取值最小。即當一個二元信源只能發(fā)出全0或全1時，其消息序列不包含任何信息。反之當?shù)雀怕拾l(fā)出0、1時信息量最大。對于N個符號：p=1/N時，信源的熵最大HN(x)=log2N-23/67-

則：說明第二個信源的平均不確定性更大一些3.3.2離散信源的平均信息量—信息熵(續(xù))例：天氣預(yù)報，有兩個信源-24/67-3.3.2離散信源的平均信息量—信息熵(續(xù))信息熵的基本性質(zhì)熵函數(shù)可以表示為：-25/67-性質(zhì)1：非負性即H(X)≥0由于0≤pi≤1，所以logpi≤0，-pilogpi≥0，則總有H(X)≥0。3.3.2離散信源的平均信息量—信息熵(續(xù))-26/67-性質(zhì)2：對稱性

當變量交換順序時，熵函數(shù)的值不變。

信源的熵只與概率空間的總體結(jié)構(gòu)有關(guān)，而與各概率分量對應(yīng)的狀態(tài)順序無關(guān)；3.3.2離散信源的平均信息量—信息熵(續(xù))-27/67-性質(zhì)3：確定性；

當信源X的信源空間[X，P]中,任一個概率分量等于1，根據(jù)完備空間特性，其它概率分量必為0，這時信源為一個確知信源，其熵為0。

如果一個信源的輸出符號幾乎必然為某一狀態(tài)，那么這個信源沒有不確定性，信源輸出符號后不提供任何信息量。3.3.2離散信源的平均信息量—信息熵(續(xù))-28/67-性質(zhì)4：可加性

即統(tǒng)計獨立信源X和Y的聯(lián)合信源的熵等于它們各自的熵之和。3.3.2離散信源的平均信息量—信息熵(續(xù))H(XY)=H(X)+H(Y)-29/67-性質(zhì)5：極值性

上式表明，對于具有q個符號的離散信源，只有在q個信源符號等可能出現(xiàn)的情況下，信源熵才能達到最大值，這也表明等概分布的信源的平均不確定性最大，這是一個很重要得結(jié)論，稱為最大離散熵定理例：對于一個二元信源H(X)=H(1/2,1/2)=log2=1bit3.3.2離散信源的平均信息量—信息熵(續(xù))-30/67-聯(lián)合熵及條件熵類似于對信息熵H(X)的定義，同理也可以進一步對信宿熵H(Y)、條件熵H(Y/X)、H(X/Y)聯(lián)合熵H(X，Y)作如下類似定義：3.3.2離散信源的平均信息量—信息熵(續(xù))-31/67-它們之間，有如下主要性質(zhì)：

又稱為Shannon不等式。3.3.2離散信源的平均信息量—信息熵(續(xù))-32/67-3.3.3冗余度什么是冗余度定義:它表示給定信源在實際發(fā)出消息時所包含的多余信息,也稱余度或剩余度。為了定量地描述信源的有效性，定義下面兩個概念其中：H∞

表示考慮全部信源統(tǒng)計特性后信源的最小信息熵，它是信道傳送的理論上最佳值。H0是不考慮信源統(tǒng)計特性，即認為信源消息均為等概率時信源的最大熵。-33/67-3.3.3冗余度(續(xù))信源的冗余度來自兩個方面信源符號間的相關(guān)性信源符號分布的不均勻性。壓縮剩余度的方法減小符號間的相關(guān)性使信源符號等概率分布-34/67-3.3.3冗余度(續(xù))冗余的利弊從提高信息傳輸效率的觀點看從提高抗干擾能力角度來看信源編碼與信道編碼的目的信源編碼是減少或消除信源的剩余度以提高信息的傳輸效率信道編碼則通過增加冗余度來提高信息傳輸?shù)目垢蓴_能力。-35/67-3.3.3冗余度(續(xù))冗余度計算舉例:下表為各字母出現(xiàn)概率，計算其冗余度字母概率字母概率字母概率空格0.2S0.052Y,W0.012E0.105H0.047G0.011T0.072D0.035B0.0105O0.654L0.029V0.008A0.063C0.023K0.003N0.059F,U.0225X0.002I0.055M0.021J,Q0.001R0.054P.0175Z0.001-36/67-3.3.3冗余度(續(xù))由上述表格，首先求得獨立等概率情況下的值：再求獨立不等概率情況下的還可進一步求得有一階、二階記憶下的和：-37/67-3.3.3冗余度(續(xù))最后用推斷方法求這樣，利用公式可分別求得η=H∞/H0=1.4/4.76=0.29，γ=1-0.29=0.71。-38/67-課程內(nèi)容

3.1信源及分類3.2信源的數(shù)學模型3.3信息的度量—信息熵3.4無失真信源編碼3.5限失真信源編碼-39/67-3.4.1碼的分類分組碼是一組固定長度的碼組，可表示為（n,k）。在分組碼中，監(jiān)督位被加到信息位之后，形成新的碼。在編碼時，k個信息位被編為n位碼組長度，而n-k個監(jiān)督位的作用就是實現(xiàn)檢錯與糾錯。線性分組碼:當分組碼的信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系時，這種分組碼就稱為線性分組碼。kn-kn100100118偶校驗-40/67-設(shè)各字母的使用頻度為{E,M,C,A,D}={1,2,3,3,4}。用頻度為權(quán)值生成哈夫曼樹，并在葉子上標注對應(yīng)的字母，樹枝分配代碼“0”或“1”分組碼形式：EMCAD=>000001010011100共15位3.4.1碼的分類(續(xù))非分組碼是一組非固定長度的碼組，也稱樹碼。例如：哈夫曼編碼-41/67-3.4.1碼的分類(續(xù))奇異碼和非奇異碼若信源符號和碼字是一一對應(yīng)的，則該碼為非奇異碼。反之為奇異碼。非奇異碼可以將符號唯一的恢復(fù)，但是當信源輸出符號序列的時候，會遇到麻煩。

例如：C(x1)=0,C(x2)=1,C(x3)=01，01解碼出現(xiàn)了歧義。解決的方法是在輸出碼字之間加入間隔符，這是低效的做法。-42/67-3.4.1碼的分類(續(xù))唯一可譯碼任意有限長的碼元序列，只能被唯一地分割成一個個的碼字。例如：若C(x1)=00，C(x2)=11，則C(x1x2)=0011即時碼和非即時碼如果接收端收到一個完整的碼字后，能立即譯碼，不需等下一個碼接收后就能判斷是否可以譯碼，這樣的碼叫做即時碼。例如：C(1)=0,C(2)=10,C(3)=110,C(4)=111，則序列01011111010可以立即斷句為0,10,111,110,10，從而立即可譯-43/67-3.4.2編碼的理論知識信源編碼器模型分組碼單符號信源編碼器模型

分組碼單符號信源譯碼器模型-44/67-唯一可譯碼的條件：可導(dǎo)出唯一可譯碼存在的充分和必要條件，即各碼字的長度Ki應(yīng)符合Kraft不等式：式中，m是進制數(shù)，n是信源符號數(shù)。3.4.2編碼的理論知識(續(xù))-45/67-3.4.2編碼的理論知識(續(xù))例:設(shè)二進制碼樹中X∈｛x1，x2，x3,x4｝，K1=1，K2=2，K3=2，K4=3，應(yīng)用上述判斷定理，可得因此，不存在滿足這種Ki的唯一可譯碼,例：若C(x1)=00，C(x2)=11K1=2,k2=2-46/67-3.4.3幾種典型編碼方法最佳碼定義:

若一個唯一可譯碼的平均碼長小于所有其它唯一可譯碼，則稱該碼為最優(yōu)碼。下面重點介紹幾種最佳編碼:-47/67-3.4.3幾種典型編碼方法(續(xù))香農(nóng)編碼方法將信源消息符號按其出現(xiàn)的概率大小依次排列p(x1)≥p(x2)≥…≥p(xn)

確定滿足下列不等式的整數(shù)碼長Ki：為了編成唯一可譯碼，計算第i個消息的累加概率將累加概率Pi變換成二進制數(shù)。取Pi二進數(shù)的小數(shù)點后Ki位即為該消息符號的二進制碼字。-48/67-3.4.3幾種典型編碼方法(續(xù))香農(nóng)編碼方法舉例：消息序號si

消息概率p(si)

累加概率Pi

-logp(si)

代碼組長度li

二進制代碼組

s1

0.2000

0.0000

2.3219

3

000

s2

0.1900

0.2000

2.3959

3

001

s3

0.1800

0.3900

2.4739

3

011

s4

0.1700

0.5700

2.5564

3

100

s5

0.1500

0.7400

2.7370

3

101

s6

0.1000

0.8900

3.3219

4

1110

s7

0.0100

0.9900

6.6439

7

1111110-49/67-3.4.3幾種典型編碼方法(續(xù))費諾編碼過程如下：將信源消息符號按其出現(xiàn)的概率大小依次排列：p(x1)≥p(x2)≥…≥p(xn)。將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進制碼元“0”和“1”。將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又賦予兩個組一個二進制符號“0”和“1”。如此重復(fù)，直至每個組只剩下一個信源符號為止。信源符號所對應(yīng)的碼字即為費諾碼。-50/67-3.4.3幾種典型編碼方法(續(xù))哈夫曼編碼過程如下：將n個信源消息符號按其出現(xiàn)的概率大小依次排列，p(x1)≥p(x2)≥…≥p(xn)取兩個概率最小的字母分別配以0和1兩碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊。對重排后的兩個概率最小符號重復(fù)步驟(2)的過程。不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。-51/67-3.4.3幾種典型編碼方法(續(xù))舉例:哈夫曼編碼0.60.3CEDBA0.10.40.30.10.1F0.020.0810.20000111101最后結(jié)果:A-0B-10C-1100D-1101E-1110F-1111-52/67-3.4.3幾種典型編碼方法(續(xù))哈夫曼編碼的基本特點構(gòu)造了一個碼樹，碼樹從端點開始構(gòu)造，直到樹根結(jié)束，最后得到一個碼樹，編出的碼是即時碼。采用概率匹配方法來決定各碼字的碼長編出的碼字并不惟一。優(yōu)點：可取得較好的冗余壓縮效果?？墒馆敵龃a元概率均勻化。-53/67-3.4.3幾種典型編碼方法(續(xù))游程編碼游程長度：在二元序列中，只有兩種符號，即“0”和“1”，這些符號可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長度分別稱為游程長度L(0)和L(1).對于多元序列也存在相應(yīng)的游程序列。例如m元序列中，可有m種游程。連著出現(xiàn)符號r的游程，其長度L(r)就是“r”的游程長度。-54/67-3.4.3幾種典型編碼方法(續(xù))游程編碼游程編碼(簡寫為RLE或RLC)是一種十分簡單的壓縮方法,它將數(shù)據(jù)流中連續(xù)出現(xiàn)的字符(稱為游程)用單一的記號來表示。例如,字符串a(chǎn)baCCCbbaaaa

可以壓縮為aba3c2b4a游程編碼的壓縮效果不太好,但由于簡單,編碼/解碼的速度非常快,因此仍然得到廣泛的應(yīng)用。許多圖形和視頻文件,如.TIF及.AVI等,都使用了這種壓縮。-55/67-課程內(nèi)容

3.1信源及分類3.2信源的數(shù)學模型3.3信息的度量—信息熵3.4無失真信源編碼3.5限失真信源編碼-56/67-3.5限失真信源編碼什么是限失真信源編碼限失真信源編碼要解決的問題：在允許一定失真程度的條件下，用盡可能少的符號來表達信源的信息，即信源熵所能壓縮的極限或者說編碼后信源輸出的信息率壓縮的極限值。它是量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。無失真的冗余度壓縮編碼主要是針對離散信源的有失真的熵壓縮編碼主要是針對連續(xù)信源主要方法：矢量量化編碼-57/67-3.5限失真信源編碼(續(xù))本節(jié)介紹以下幾種限失真編碼3.5.1矢量量化編碼3.5.2變換編碼3.5.3預(yù)測編碼-58/67-3.5.1矢量量化編碼標量量化：是對每個信源符號單獨處理忽略了信源符號的相關(guān)性。矢量量化通過將多個符號構(gòu)成的序列作為一個整體進行量化的方法,可以避免標量量化的固有缺點，這種方法稱為矢量量化。矢量量化編碼是在圖像、語音信號編碼技術(shù)中研究得較多的新型量化編碼方法。-59/67-3.5.1矢量量化編碼(續(xù))矢量量化原理：

先將待編碼的信源符號序列劃分為一個個等長的分組，每個分組含有若干個符號，形成一個矢量。每個矢量與預(yù)先生成的矢量碼書中的每個碼字進行比較，求出相應(yīng)的失真，然后用失真最小的碼字的編號作為量化器的輸出就實現(xiàn)了矢量量化。在譯碼端有一個同樣的碼書，所以譯碼工作只是通過接收的碼字序號在碼書中搜索相應(yīng)的碼字，算法簡單，容易實現(xiàn)。-60/67-3.5.1矢量量化編碼(續(xù))矢量量化原理圖搜索碼書查表信道傳輸矢量下標碼書輸入矢量輸出矢量-61/67-3.5.1矢量量化編碼(續(xù))矢量碼書的構(gòu)造(一般了解)目前最流行的算法是由Y.Linde、A.Buzo、R.M.Gray共同提出的LBG算法：采集用于構(gòu)造碼書的訓(xùn)練數(shù)據(jù)，為了得到性能較好的矢量碼書，一般要求訓(xùn)練樣本的數(shù)量N和碼字的個數(shù)L滿足：N≥20L；構(gòu)造初始碼書，常用的構(gòu)造方法有隨機碼書法、白噪聲碼書法等；按照初始碼書對所有的訓(xùn)練樣本進行矢量量化，得到分屬不同碼字的L個樣本集合和相應(yīng)的量化誤差；對每個樣本集合進行聚類，根據(jù)聚類的結(jié)果修正初始碼字，得到新的碼書；判斷量化誤差是否小于門限值、迭代次數(shù)是否超出規(guī)定值，若是，則訓(xùn)練結(jié)束，否則轉(zhuǎn)第3步繼續(xù)。-62/67-3.5.