信息論與編碼第4章無失真信源編碼

信源編碼信源編碼是以提高通信的有效性為目的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。同樣多的信息用較少的碼率來傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。1信源編碼的基本途徑有兩個(gè)：使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。2信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：無失真信源編碼定理限失真信源編碼定理

無失真信源編碼只適用于離散信源

對(duì)于連續(xù)信源，只能在失真受限制的情況下進(jìn)行限失真編碼下面介紹幾種典型的離散信源編碼方法。3第4章無失真信源編碼4.1無失真信源編碼的概念4.2等長編碼4.3變長編碼4.4常用的變長編碼算法44.1無失真信源編碼的概念信源符號(hào)(字母)集：S＝{s1,s2,…,sq}.碼符號(hào)(字母、元)集：A＝{a1,a2,…,am}.編碼函數(shù)f:將有限個(gè)信源符號(hào)變換成有限個(gè)碼符號(hào)的函數(shù)

用AN表示全體長度為N的信源符號(hào)序列構(gòu)成的集合碼字：wi

=f(si)碼字wi的長度(碼長)：li=l(wi)碼:C={wi

=f(si)|si

SN}.54.1無失真信源編碼的概念N=1時(shí)f：無失真信源編碼器6如何分離碼字？如果0，01都是碼字，譯碼時(shí)如何分離？？74.1無失真信源編碼的概念例4-1幾個(gè)二元碼

信源符號(hào)概率分布碼1:C1碼2:C2碼3:C3碼4:C4碼5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001碼的擴(kuò)展碼C1的擴(kuò)展:s1s3

001084.1無失真信源編碼的概念m元碼:碼符號(hào)集A＝{a1,a2,…,am}.

二元碼:m=2,A＝{0,1}等長碼（定長碼）:所有碼字的碼長相等.

例:中文電報(bào)碼是碼長為4的等長的10元碼中

0022;國

0948;

北

0554;京

0079.變長碼（非定長碼）:碼字的碼長不相等.非奇異碼:

s1,s2

A,s1

s2

f(s1)

f(s2)

否則，稱為奇異碼94.1無失真信源編碼的概念唯一可譯碼:

任意有限長的碼元序列,只能被唯一地分割成一個(gè)一個(gè)的碼字,則稱為唯一可譯碼,或單義可譯碼.否則，就稱為非唯一可譯碼,或非單義可譯碼.

例：碼4是唯一可譯碼:1000100

1000,100

碼3是非唯一可譯碼:1000100

10,00,10,0或10,0,01,00信源符號(hào)概率分布碼1:C1碼2:C2碼3:C3碼4:C4碼5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001備注等長碼非唯一可譯非

唯一可譯唯一可譯及時(shí)碼104.1無失真信源編碼的概念即時(shí)碼:

如果收到一個(gè)碼字后,就能及時(shí)譯出，則稱為即時(shí)碼,也稱為非延長碼，或異前綴碼.即沒有任何完整的碼字是其它碼字的前綴。否則，就稱為非即時(shí)碼.

例：碼5是即時(shí)碼,碼4是非即時(shí)碼.信源符號(hào)概率分布碼1:C1碼2:C2碼3:C3碼4:C4碼5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001備注等長碼非唯一可譯非

唯一可譯唯一可譯及時(shí)碼11關(guān)系即時(shí)碼一定是唯一可譯碼唯一可譯碼一定是非奇異碼定長的非奇異碼一定是唯一可譯碼非定長的非奇異碼不一定是唯一可譯碼4.1無失真信源編碼的概念12第4章無失真信源編碼4.1無失真信源編碼的概念4.2等長編碼4.3變長編碼4.4常用的變長編碼算法134.2等長編碼離散信源X的熵：H(X)字母集:S＝{s1,s2,…,sq}.對(duì)信源輸出的N個(gè)符號(hào)進(jìn)行編碼:共有qN個(gè)消息碼元集A＝{a1,a2,…,am}.

長度為L的等長碼：共有mL個(gè)可能碼字能正確譯碼的必要條件：(非奇異碼)144.2等長編碼編碼速率（編碼信息率）:編碼后每個(gè)信源符號(hào)所能承載的的最大信息量編碼效率平均碼長：平均每個(gè)信源符號(hào)所需要的碼符號(hào)個(gè)數(shù)編碼效率:154.2等長編碼例4-2

設(shè)一個(gè)離散信源的輸出字母表有q=10個(gè)符號(hào)，將其編為無失真二元碼，即m=2

，求平均碼長。164.2等長編碼無失真編碼假設(shè)信道無干擾譯碼錯(cuò)誤概率:Pe=P{M

M’}無失真編碼:譯碼錯(cuò)誤概率Pe可以任意小.MWM’信源信源編碼信道

信宿信源解碼W174.2等長編碼等長信源編碼定理定理4-1(Shannon信源編碼定理)

設(shè)離散無記憶信源X的熵為H(X),若對(duì)長為N的信源符號(hào)序列進(jìn)行等長編碼,碼長為L

,碼元符號(hào)個(gè)數(shù)為m.則對(duì)任意的

>0,

>0,只要時(shí),則譯碼差錯(cuò)概率一定是有限值(不可能實(shí)現(xiàn)無失真編碼),而當(dāng)N足夠大時(shí),譯碼錯(cuò)誤概率近似等于1。則當(dāng)N足夠大時(shí)，必可使譯碼錯(cuò)誤概率小于

。反之，當(dāng)184.2等長編碼等長信源編碼定理最佳等長編碼:

編碼效率:194.2等長編碼等長信源編碼定理設(shè)信源自信息方差為D(X)=D[I(pi)]，編碼效率為

,當(dāng)允許譯碼錯(cuò)誤概率Pe

<

時(shí)，有容許譯碼錯(cuò)誤概率越小信源序列長度越大編碼效率越高20第4章無失真信源編碼4.1無失真信源編碼的概念4.2等長編碼4.3變長編碼4.4常用的變長編碼算法214.3變長編碼字母集:S＝{s1,s2,…,sq}.信源X的概率分布：p(si)(i=1,2,…,q

).離散信源X的熵：H(X)碼元集A＝{a1,a2,…,am}.

信源符號(hào)si的碼字:wi=f(si)

碼字wi的長度為li

(i=1,2,…,q

)224.3變長編碼編碼速率:編碼后每個(gè)信源符號(hào)所能承載的的最大信息量編碼效率:不等長碼的編碼效率平均碼長:碼的多余度（剩余度）:234.3變長編碼平均碼長：平均每個(gè)信源符號(hào)所需的碼元符號(hào)個(gè)數(shù)信源符號(hào)概率分布碼1:C1碼2:C2碼3:C3碼4:C4碼5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001備注2非唯一可譯非唯一可譯唯一可譯及時(shí)碼平均碼長21.51.51.8751.875244.3變長編碼碼樹編碼方法三元樹碼：C={w1,w2,…,w11}w1=0,w2=11,w3=12,w4=20,w5=22,w6=100,w7=101,w8=102,w9=210,w10=211,w11=212.樹碼一定是即時(shí)碼011201201210202w2w3w1w4w10w5w9w8w7w6w110級(jí)節(jié)點(diǎn)1級(jí)節(jié)點(diǎn)2級(jí)節(jié)點(diǎn)3級(jí)節(jié)點(diǎn)254.3變長編碼碼樹編碼方法（1）樹根編碼的起點(diǎn)；（2）每一個(gè)中間節(jié)點(diǎn)樹枝的個(gè)數(shù)

編碼的進(jìn)制數(shù)；（3）樹的節(jié)點(diǎn)

編碼或編碼的一部分；（4）樹的終止節(jié)點(diǎn)（端點(diǎn)、樹葉）

碼；（5）樹的節(jié)數(shù)

碼長；（6）碼位于多級(jí)節(jié)點(diǎn)

變長碼；（7）碼位于同一級(jí)節(jié)點(diǎn)碼

等長碼；011201201210202w2w3w1w4w10w5w9w8w7w6w110級(jí)節(jié)點(diǎn)1級(jí)節(jié)點(diǎn)2級(jí)節(jié)點(diǎn)3級(jí)節(jié)點(diǎn)264.3變長編碼克拉夫不等式(L.G.Kraft,1949)長度為l1,l2,…,lr的m元即時(shí)碼存在的充分必要條件是：麥克米倫定理(麥克米倫:B.McMillan,1956).長度為l1,l2,…,lr的m元唯一可譯碼存在的充分必要條件是:274.3變長編碼例信源符號(hào)概率分布碼1:C1碼2:C2碼3:C3碼4:C4碼5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001備注2非唯一可譯非唯一可譯唯一可譯及時(shí)碼平均碼長21.51.51.8751.87528判斷以下碼字是否可分離（唯一可譯）？習(xí)題294.3變長編碼設(shè)離散信源X的熵為H(X),則其任意一個(gè)m元唯一可譯碼滿足：同時(shí)存在m元唯一可譯碼，其平均長度滿足：單個(gè)符號(hào)不等長信源編碼定理304.3變長編碼設(shè)離散信源X的熵為H(X),其N次擴(kuò)張信源為XN，將信源XN編為m元碼，總存在唯一可譯碼f，使得信源X的每個(gè)符號(hào)所需的平均碼長滿足：離散平穩(wěn)無記憶序列變長編碼定理香農(nóng)第一編碼定理31第4章無失真信源編碼4.1無失真信源編碼的概念4.2等長編碼4.3變長編碼4.4常用的變長編碼算法324.4.1香農(nóng)編碼設(shè)有離散無記憶信源331234香農(nóng)編碼方法的步驟按信源符號(hào)的概率從大到小的順序排隊(duì)不妨設(shè)34例設(shè)有一單符號(hào)離散無記憶信源試對(duì)該信源編二進(jìn)制香農(nóng)碼。35編碼過程（1）3637§4.1.2費(fèi)諾編碼對(duì)概率按m進(jìn)行分組，使每組概 率盡可能相等給每個(gè)分組分配一個(gè)碼元對(duì)每個(gè)分組重復(fù)2、3步，直到不可分為止1234按信源符號(hào)的概率從大到小的順序排隊(duì)不妨設(shè)38設(shè)有一單符號(hào)離散無記憶信源試對(duì)該信源編二進(jìn)制費(fèi)諾碼。例39編碼過程40可以看出本例中費(fèi)諾碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近的信源。41將信源符號(hào)按概率由大到小順序排隊(duì)給兩個(gè)概率最小的符號(hào)各分配一個(gè)碼位，將其概率相加后合并作為一個(gè)新的符號(hào)，與剩下的符號(hào)一起，再重新排隊(duì)給縮減信源中概率最小的符號(hào)各分配一個(gè)碼元重復(fù)步驟2、3直至概率和為121434.4.3赫夫曼編碼42設(shè)有一單符號(hào)離散無記憶信源試對(duì)該信源編二進(jìn)制哈夫曼碼。例43編碼過程444546說明：Huffman碼的編碼方法不是唯一的。首先，每次對(duì)縮減信源兩個(gè)最小的符號(hào)分配“0”和“1”碼元試任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長，平均碼長都不變，所以沒有本質(zhì)區(qū)別。其次，若合并后的新符號(hào)的概率與其他符號(hào)的概率相等，從編碼的方法上來說，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不同。不同的編法得到的碼字長度也不盡相同。47對(duì)信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號(hào)合并后的概率與其它信源符號(hào)的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼。此時(shí)將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。如下面的例子48例

設(shè)有離散無記憶信源用兩種不同的方法對(duì)其編二進(jìn)制huffman碼49方法一方法二50信源符號(hào)xi概率p(xi)碼字Wi1碼長Ki1碼字Wi2碼長K’i2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113兩種不同的編碼方法得到的碼字和碼長的對(duì)比51平均碼長和編碼效率52兩種編碼方法編出的碼字的碼長方差比較53可以看出第二種編碼方法的碼長方差要小許多。這意味著第二種編碼方法的碼長變化較小，比較接近平均碼長。由此可以得到一個(gè)結(jié)論(怎樣得到碼方差較小的huffman編碼)。54結(jié)論：進(jìn)行赫夫曼編碼時(shí)，為得到碼方差最小的碼，應(yīng)使合并的信源符號(hào)位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

554.4常用的變長編碼算法最佳不等長編碼(最佳碼)

對(duì)于給定的信源和碼元符號(hào)集，在其所有的唯一可譯碼中，平均長度最小的碼稱為最佳碼，或緊致碼。字母集:S＝{s1,s2,…,sq}.信源X的概率分布：p(si)(i=1,2,…,q

).碼元集A＝{a1,a2,…,am}.

信源符號(hào)si的碼字:wi=f(si)

碼字wi的長度為li

(i=1,2,…,q

)564.4常用的變長編碼算法習(xí)題

已知離散無記憶信源X為：求二進(jìn)制香農(nóng)碼，二進(jìn)制費(fèi)諾碼，二進(jìn)制霍夫曼碼，三進(jìn)制霍夫曼碼。

574.4常用的變長編碼算法信源X的熵:H(X)=2.61符號(hào)序列概率分布第1次分組第2次分組第3次分組第4次分組碼字碼長a10.200(0.57)0(0.2)002a20.191(0.37)00103a30.1810113a40.171(0.43)0(0.17)102a50.151(0.26)01103a60.1010(0.10)11104a70.011(0.01)11114584.4常用的變長編碼算法習(xí)題

求以下信源X的霍夫曼碼解：賦予碼元594.4常用的變長編碼算法解：寫出碼字

604.4常用的變長編碼算法習(xí)題

求以下信源X的三進(jìn)制霍夫曼碼614.4常用的變長編碼算法符號(hào)序列概率分布123碼字碼長a0a0

9/169/169/160101a0a13/164/16017/16112a1a03/16013/161003a1a1

1/161013例4.10設(shè)二元離散無記憶信源X的符號(hào)集為{a0,a1},概率分布為：p0=0.75,p1=0.25,則

H(X)=0.75log0.750.25log0.25=0.811.

對(duì)兩個(gè)信源符號(hào)X2進(jìn)行編碼,則有624.4常用的變長編碼算法例4.10

對(duì)三個(gè)信源符號(hào)X3進(jìn)行編碼634.4常用的變長編碼算法課堂練習(xí)已知離散無記憶信源X如下，求其三元霍夫曼碼。并求其平均碼長與編碼效率。644.4常用的變長編碼算法LZ碼1977年，齊費(fèi)(J.Ziv,以色列)與蘭佩爾齊(A.Lempel,以色列)提出LZ碼，1978年進(jìn)行改進(jìn)，稱為LZ78.設(shè)信源符號(hào)集S＝{s1,s2,…,sq},輸入信源符號(hào)序列為

u=u1u2…uL

(ui

S)編碼規(guī)則分段：將符號(hào)序列u分成小段。分段原則:各小段盡可能短，且不相同.分成的小段稱為短語.

短語總數(shù)記為:M(u)依次