第5章-信源編碼課件

第5章

無失真信源編碼為什么要進(jìn)行編碼？信源發(fā)出的消息符號(hào)可能不適合信道的傳輸。將信源發(fā)出的消息符號(hào)轉(zhuǎn)換為適合信道傳輸?shù)姆?hào)。信源消息確定后，提高通信的有效性—信源編碼。提高通信的可靠性,編碼具有發(fā)現(xiàn)錯(cuò)誤或糾正錯(cuò)誤的抗干擾能力—信道編碼。提高通信的安全性—加密編碼。信源編碼：以提高通信有效性為目的的編碼。通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。加密編碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。一、信源的符號(hào)集和符號(hào)序列信源符號(hào)集：信源發(fā)出的符號(hào)消息的集合，記為X；設(shè)X有n個(gè)符號(hào)：X={x1,x2,…,xn

}.信源符號(hào)序列：由信源符號(hào)集合X中的符號(hào)組成長度為L的符號(hào)序列，記為。

L為信源符號(hào)序列長,不同的符號(hào)序列共有nL。

若L=1，則信源符號(hào)序列為信源符號(hào)集合中的符號(hào)。信源編碼器信道碼表5.1信源編碼的基本概念二、碼元和碼字

1°碼元(符)集

信道可傳輸?shù)幕痉?hào)的集合,記為Y；設(shè)Y有m個(gè)符號(hào)：

Y={y1,y2,…,ym

}，其中yi

稱為碼元或碼符。

m元信道:可傳輸m個(gè)基本符號(hào)的信道。二元信道:可傳輸2個(gè)基本符號(hào)的信道。這是一種最常用的信道,其基本符號(hào)常用0,1表示。

2°碼字:

由碼元組成的序列稱為碼字，記為Yi

。

碼字Yi的碼元個(gè)數(shù)Ki稱為Yi的碼長。

所有碼字Yi的碼長Ki

均相等稱為碼長為K定長碼。

碼字Yi的碼長Ki

不全相等稱為變長碼。三、編碼與譯碼1°信源編碼：將信源符號(hào)xi或符號(hào)序列XLi

按一種規(guī)則映像成碼字Yi的過程。2°無失真編碼：信源符號(hào)到碼字的映射必須一一對(duì)應(yīng)。3°譯碼：從碼符號(hào)到信源符號(hào)的映射。4°碼表：所有映射規(guī)則的集合。四、許用碼和禁用碼1°許用碼字：信源符號(hào)xi或符號(hào)序列XLi與碼字Yi定義對(duì)應(yīng)關(guān)系的碼字。2°禁用碼字：信源符號(hào)xi或符號(hào)序列XLi與碼字Yi未定義對(duì)應(yīng)關(guān)系的碼字。3°許用碼字的全體稱為碼集五、分組碼（塊碼）分類

1°按碼字的碼長分類定長碼：碼集中所有碼字的碼長相等。變長碼：碼集中所有碼字的碼長不全相等。

2°按信源符號(hào)與碼字對(duì)應(yīng)關(guān)系分類非奇異碼：信源符號(hào)與碼字是一一對(duì)應(yīng)的，碼2。奇異碼：信源符號(hào)與碼字不是一一對(duì)應(yīng)的，碼1。

3°按譯碼唯一性分類唯一可譯碼：對(duì)于多個(gè)碼字組成的有限長碼流，只能唯一地分割成一個(gè)個(gè)的碼字。唯一可譯碼又稱為單義碼。非唯一可譯碼：對(duì)有限長碼流，不能唯一地分割成一個(gè)個(gè)的碼字。信源符號(hào)ai碼1碼2a100a21110a30000a41101奇異碼與非奇異碼

【例】

碼流100111000…

碼1x1→0x2→10x3→11可分割10,0,11,10,0,0

x2

x1

x3

x2x1x1

碼2x1→1x2→10x3→11則無法唯一分割。4°按譯碼的即時(shí)性分類

非即時(shí)碼：接收端收到一個(gè)完整的碼字后，不能立即譯碼，還需要等到下一個(gè)碼字開始接收后才能判斷是否可以譯碼。即時(shí)碼：接收端收到一個(gè)完整的碼字后，就能立即譯碼，即時(shí)碼又稱為非延長碼或異前綴碼。

【例】

非即時(shí)碼碼流01001100…

x1→0x2→01x3→11譯碼為x2x1x1x3x1?

即時(shí)碼碼流01001100…

x1→0x2→10x3→11譯碼為x1x2x1x3x1x1信源符號(hào)ai碼1碼2a110a21001a3100001a410000001即時(shí)碼與唯一可譯碼即時(shí)碼

異前綴碼(即時(shí)碼)：碼集中任何一個(gè)碼不是其他碼的前綴。

即時(shí)碼必定是唯一可譯碼,唯一可譯碼不一定是即時(shí)碼。5°有實(shí)用價(jià)值的分組碼分組碼：將信源符號(hào)集中的每個(gè)信源符號(hào)固定地映射成一個(gè)碼字。是非奇異碼、唯一可譯碼、即時(shí)碼。六、碼樹圖

1°碼樹圖:用碼樹來描述給定碼集中各碼字的方法。

2°碼樹圖的樹根、樹枝、節(jié)點(diǎn)中間節(jié)點(diǎn)（一級(jí)節(jié)點(diǎn)、二級(jí)節(jié)點(diǎn)…）用○表示,終端節(jié)點(diǎn)用●表示。

3°二元（進(jìn)制）碼樹

【例1】

x1→1x2→01x3→00

A○01○●x1

【例2】

x1→1x2→10x3→1101○●x2A○11●x3●x101●x2●x34°用碼樹圖構(gòu)造碼在樹的生長過程中，中間節(jié)點(diǎn)生出樹枝，各樹枝標(biāo)出相應(yīng)的碼元，為了清晰起見，相同碼元的樹枝方向相同，終端節(jié)點(diǎn)表示信源符號(hào)，從樹根到終端節(jié)點(diǎn)所經(jīng)過的樹枝旁的碼元按經(jīng)過的順序組成的序列構(gòu)成碼字。5°用碼樹圖構(gòu)造即時(shí)碼的條件如果表示信源符號(hào)的終端節(jié)點(diǎn)不再延伸，這樣構(gòu)造的碼滿足即時(shí)碼條件。七、唯一可譯碼存在的條件1°前提條件：非奇異碼2°唯一可譯碼存在定理設(shè)n為信源符號(hào)或信源符號(hào)序列個(gè)數(shù)，m為碼元個(gè)數(shù)，Ki

為信源各符號(hào)或信源符號(hào)序列對(duì)應(yīng)的碼長。則唯一可譯碼存在的充分和必要條件是滿足Kraft不等式

【注意】

Kraft不等式是一個(gè)存在定理，不是唯一可譯碼的判定定理;

如果n、m、Ki

滿足Kraft不等式，則存在唯一可譯碼;

如果是唯一可譯碼,則n、m、Ki

必定滿足Kraft不等式。一、平均碼長和編碼有效性

1平均碼長

單符號(hào)信源空間，其中

信源符號(hào)xi

對(duì)應(yīng)的碼字為Yi

（i=1,2,…,n），碼字Yi對(duì)應(yīng)的碼長為Ki（i=1,2,…,n

）。

所有的Ki相等為定長碼，記為K,不相等時(shí)為變長碼。

單符號(hào)對(duì)應(yīng)變長碼的平均碼長為

碼符/信源符號(hào)5.2離散信源編碼符號(hào)序列信源空間XL

其中XL是X的L次擴(kuò)展。

信源符號(hào)序列

對(duì)應(yīng)的碼字為Yi

（i=1,2,…,nL），碼字Yi對(duì)應(yīng)的碼長為Ki（i=1,2,…,n

L）。

符號(hào)序列對(duì)應(yīng)變長碼的平均碼長為

碼符/信源符號(hào)序列碼符/信源符號(hào)2編碼效率（碼率）定義：平均一個(gè)碼符所攜帶的平均信息量稱為編碼效率，記作η。概率匹配原則：概率大的編短碼，概率小的編長碼。按照概率匹配原則編碼可以提高編碼效率?！纠?.2.1】信源空間

H(X)=－(1/2log1/2＋1/4log1/4＋1/8log1/8＋1/8log1/8)=1.75bit/消息信源符號(hào)個(gè)數(shù)為n=4，二元碼符{0,1}，碼符個(gè)數(shù)為m=2，Ki為信源各符號(hào)對(duì)應(yīng)的碼字長,且滿足Kraft不等式。

定長碼:

K1=K2=K3=K4=22-2+2-2+2-2+2-2=1

碼字:Y1=00,Y2=01,Y3=10,Y4=11

變長碼:

K1=1,K2=2,K3=3,K4=32-1+2-2+2-3+2-3=1

碼字:Y1=0,Y2=10,Y3=110,Y4=111定長碼

x1→00x2→01x3→10x4→11

K=2η=1.75÷2=0.825變長碼

方案1:

x1→0x2→10x3→110x4→111=1×1/2+2×1/4+3×1/8+3×1/8=1.75碼符/信源符號(hào)

η=1.75÷1.75=1

方案2:

x1→111x2→110x3→10x4→0=3×1/2+3×1/4+2×1/8+1×1/8=2.625碼符/信源符號(hào)

η=1.75÷2.625=0.667

比較方案1、2.二、定長編碼定理

1定長編碼定理

信源X有n個(gè)信源符號(hào),其L次擴(kuò)展信源為XL,信源熵為H(XL),信源

XL中的信源符號(hào)序列均用碼長為

KL的碼字對(duì)其進(jìn)行編碼，H(X)=H(XL)/L,對(duì)任意ε>0,δ>0,只要當(dāng)L足夠大時(shí),必定可使譯碼碼小于δ。若譯碼差錯(cuò)一定是有限值,當(dāng)L足夠大時(shí),譯碼必定出錯(cuò)。

2切比雪夫不等式設(shè)隨機(jī)變量ξ有數(shù)學(xué)期望Mξ及方差Dξ,則對(duì)任何正數(shù)ε，不等式成立。3定長編碼L的計(jì)算計(jì)算隨機(jī)變量I(xi)的數(shù)學(xué)期望M[I(xi)]，即H(X)；計(jì)算I(xi)的方差σ2(X)

。計(jì)算符號(hào)序列長度L

若已知編碼效率η和譯碼錯(cuò)誤概率δ三、變長編碼定理

1平均碼長的界限—變長編碼定理符號(hào)信源空間

Y1

Y2…Yn

對(duì)應(yīng)K1K2

…

Kn。m為碼符個(gè)數(shù)，則存在唯一可譯碼，使其平均碼長滿足如下不等式證明：若xi

按如下不等式取所對(duì)應(yīng)碼字的碼長為Ki若為整數(shù),則上述不等式左邊取等號(hào)。

故可得因?yàn)樗运写a字長度滿足Kraft不等式。

如何降低平均碼長：（1）減少信源熵H(X)；

（2）增加信道碼元數(shù)m。2離散平穩(wěn)無記憶序列變長編碼定理信源X

的L次擴(kuò)展信源XLXL的信源熵為：H(XL)bit/L個(gè)信源符號(hào)

XL所對(duì)應(yīng)碼字的碼長為碼符/L個(gè)信源符號(hào)因?yàn)椋?/p>

所以，當(dāng)L→∞時(shí)

【例5.2.2】

H(X)=0.811bit/符號(hào)

定長碼

x1→0，x2→1K=1

編碼效率η=H(X)/K=0.811序列：L=2，XL

x1x1

x1x2

x2x1

x2x2p(XL)9/163/163/161/16

H(XL)=1.622bit/2個(gè)符號(hào)

序列的定長碼Y00011011K

2222編碼效率η=H(XL)/KL=H(X)/K=0.811序列的變長碼

Y010110111

Ki

1233=1×9/16+2×3/16+3×3/16+3×1/16=27/16=1.6875碼符/2個(gè)信源符號(hào)編碼效率

η=H(X)/K=0.811×32/27=0.961

當(dāng)L=3η=0.985

L=4η=0.991采用擴(kuò)展信源提高編碼效率帶來的問題：

(1)碼表迅速擴(kuò)大

(2)需求內(nèi)存大

(3)譯碼延時(shí)三、信息傳輸效率

1平均信息率R

平均每個(gè)碼元所含有的信息量。單位:bit/碼元

2碼元傳輸率碼元速率(RB)：每秒鐘傳輸碼元的數(shù)目.單位:波特(B)

碼元時(shí)間長度(TB):TB=1/RB，單位:秒(s)3平均信息傳輸率Rt

平均每秒鐘傳輸?shù)男畔⒘縍t

=R/TB

單位:bit/s四、最佳編碼

最佳碼：能載荷一定信息量，碼字的平均碼長最短,可分離的碼字集合。

編碼思路：對(duì)概率大的信息符號(hào)編以短碼，對(duì)概率小的信息符號(hào)編以長碼

。

這種編碼方法稱為統(tǒng)計(jì)編碼，熵編碼，概率匹配編碼。1Shannon編碼方法若xi按如下不等式取所對(duì)應(yīng)碼字的碼長為Ki

當(dāng)m等于2時(shí),logm=1，則Shannon編碼過程:將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序

p(x1)≥p(x2)…≥p(xn)按如下不等式取所對(duì)應(yīng)碼字的碼長為Ki計(jì)算第i個(gè)消息的累加概率,以便獲得唯一可譯碼將累加概率變換為二進(jìn)制數(shù)；

取二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki

位作為符號(hào)消息的二進(jìn)制碼?！纠?.2.3】

xix1

x2

x3

x4

x5

x6

x7

p(xi)0.200.190.180.170.150.100.01解：信源熵H(X)=2.61bit/符號(hào)平均碼長編碼效率xip(xi)I(xi)KiPiPi二進(jìn)制碼字x10.202.32300.0000000x20.192.4030.200.0011001x30.182.4730.390.0110011x40.172.5630.570.1001100x50.152.7430.740.1011101x60.103.3240.890.111001110x70.016.6470.990.111111011111110Shannon編碼過程【例5.2.3】

xix1

x2

x3

x4

x5

x6

x7

p(xi)0.200.190.180.170.150.100.01

2費(fèi)諾（Fano

）編碼方法將信源符號(hào)消息按其出現(xiàn)概率的大小依次排列

p(x1)≥p(x2)…≥p(xn)將依次排列的信源符號(hào)按其概率分為兩大組,使兩個(gè)組的概率之和近似相等,并對(duì)各組賦予一個(gè)碼元0和1。按前一步將每一大組再分為兩組,各組再賦予一個(gè)碼元0和1。如此重復(fù),直至每個(gè)組只剩一個(gè)信源符號(hào)為止。信源符號(hào)所對(duì)應(yīng)的碼字即為Fano

碼?！纠?.2.4】Fano

編碼過程xip(xi)第1次第2次第3次第4次碼字碼長x0.2000002x20.190100103x30.180110113x40.1710102x50.151101103x60.10111011104x70.01111111114平均碼長編碼效率3Huffman編碼方法將信源符號(hào)消息按其出現(xiàn)概率的大小依次排序

p(x1)≥p(x2)…≥p(xn)取兩個(gè)概率最小的符號(hào)分別配以0和1,并將這兩個(gè)概率相加作為新符號(hào)的概率,與未分配的符號(hào)重新排序。對(duì)重新排序后的兩個(gè)概率最小的符號(hào)重復(fù)(2)的過程。不斷重復(fù)上述過程，至最后兩個(gè)符號(hào)配以0和1為止。從最后一級(jí)開始,向前返回到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即為相應(yīng)的Huffman碼?！纠?.2.5】

x

p(xi)編碼過程碼字x10.200.200.260.350.390.610

10x20.190.190.200.260.3500.391

11x30.180.180.190.2000.261

000x40.170.170.1800.191

001x50.150.15

00.171010x60.1000.111

0110x70.011

0111平均碼長編碼效率Huffman編碼方法并不唯一，因?yàn)椋好看螌?duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長ki不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別?？s減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來說，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編碼方法得到的碼字長度ki也不盡相同。x

p(xi)編碼過程碼字

○x10.40.4

0.40.60

1

0

1x20.20.20.400.41

01○●x1x30.20.2

00.21

000

0

1

x40.100.2

1

0010○●x2X50.11

0011

0

1

x3●○x10.40.40.40.60

00

01x20.20.20.400.41

10

x4●●x5x30.20.200.21

11x40.100.21

100

x50.11

101

【例5.2.6】