無損信源編碼

無損信源編碼信息熵和信源編碼定理（1）1.信息熵計(jì)算公式

x0,x1…..xr…x∈A={a1,a2…am}H0=log2mbitH1=-∑p(x)logp(x)H2=-∑p(x0)∑P(x1|x0)logP(x1|x0)

…….Hk+1=-∑p(x0,x1..xk-1)∑P(xk|x0,x1..xk-1)logP(xk|x0,x1..xk-1)第2頁,共38頁，星期六，2024年，5月信息熵和信源編碼定理（2）

H0

H1

….

Hk

…...H(x0,x1..xk-1)=-∑p(x0,x1..xk-1)logp(x0,x1..xk-1)

極限熵H=LimHk=LimH(x0,x1..xk-1)/kk無限2.等長碼的編碼定理碼字同樣長有利于傳輸?shù)湫托蛄小猘r出現(xiàn)Spr次.第3頁,共38頁，星期六，2024年，5月信息熵和信源編碼定理(3)當(dāng)S趨于無限，非典型序列出現(xiàn)的概率趨于零。可只編這些序列，差錯(cuò)接近零。典型序列個(gè)數(shù)是

N=S!/∏(Spr)！用斯斗林公式S!=(S/e)S√(2πS)

每個(gè)信源符號(hào)所需碼長是(S→∝)liml=lim(logN)/S=-∑prlogpr

第4頁,共38頁，星期六，2024年，5月熵和信信息源編碼定理(4)

S有限時(shí)有失真，可容忍時(shí)S已很大。

很難實(shí)現(xiàn)。

3.變長碼的編碼定理可分離的必要條件是異前置性。碼樹結(jié)構(gòu)(根，葉，節(jié)，枝）R000111第5頁,共38頁，星期六，2024年，5月信息熵和信源編碼定理(5)一個(gè)長為li的碼字占2L-li個(gè)長為L的碼字。

Kraft不等式：∑2L-li≤2L，∑2-li≤1

可分離的充要條件?？赏茝V到k進(jìn)碼。若li=-logpi

-logpi≦l<1-logpi,

第6頁,共38頁，星期六，2024年，5月信息熵和信源編碼定理(6)∑2-li≦∑pi=1,可以編碼,平均碼長l，有

-∑pilogpi≦l=∑lipi<1-∑pilogpi,SH1≦Sl<1+SH1,S→∝,l→H1,

這就是變長碼編碼定理，得證。對(duì)于相關(guān)信源，可把一段（長S）序列作為一個(gè)符號(hào)，有mS個(gè)碼字,進(jìn)行編碼。第7頁,共38頁，星期六，2024年，5月赫夫曼編碼（1）1.概述從仙農(nóng)碼到赫夫曼碼

例xia1a2a3a4a5pi0.40.30.20.050.05li22355

碼字00011001010010101

Ra1(00)a2(01)a3(100)a4(10100)a5(10101)第8頁,共38頁，星期六，2024年，5月赫夫曼編碼(2)這是仙農(nóng)碼，非滿樹，可改進(jìn)。平均碼長l=2.5,H=1.95

編碼效率η=H/l=78%

不先規(guī)定碼長的費(fèi)諾碼

0(a1,a4,a5)0(a1)001(a4,a5)0(a4)0101(a5)0111(a2,a3)0(a2)101(a3)11第9頁,共38頁，星期六，2024年，5月赫夫曼編碼(3)

l1=l2=l3=2,l4=l5=3,l=2.1

=93%

另一種編法：

0(a1)01(a2,a3,a4,a5)0(a2)101(a3,a4,a5)0(a3)1101(a4,a5)0(a4)11101(a5)1111第10頁,共38頁，星期六，2024年，5月赫夫曼編碼(4)

l1=1,l2=2,l3=3,l4=l5=4,l=2.0,

=97.5%

如何達(dá)到最佳，導(dǎo)出赫夫曼碼

2.編碼步驟：先按概率大小排隊(duì)，作為葉。把最小兩個(gè)賦予0和1，合成一個(gè)節(jié)點(diǎn)再排隊(duì)，直至只剩一個(gè)根。用上例來編赫夫曼碼：第11頁,共38頁，星期六，2024年，5月赫夫曼編碼（5）

a2,a3,a4,a5(0.6)a1(0.4)R1a2(0.3)00a3(0.2)a3,a4,a5(0.3)010a4(o.05)a4,a5(0.1)0110a5(0.05)0111l1=1,l2=2,l3=3,l4=l5=4l=2.0

=97.5%10100110第12頁,共38頁，星期六，2024年，5月赫夫曼編碼(6)用數(shù)學(xué)歸納法可證明其最佳性。若T(m-1)為m-1元編碼時(shí)的最佳樹，它必為滿樹，需將一葉分裂為二以構(gòu)成T(m)。平均碼長增加

l=(pm+pm-1)(lm-1+1-lm-1)=pm+pm-1,

這已是最小，得證。

D=(pm-1+pm)(2lm-1+1),lm-1最小,向上排。第13頁,共38頁，星期六，2024年，5月赫夫曼編碼(7)

3.推廣

k進(jìn)碼，分裂一次增加k-1片葉，所以

m=s(k-1)+k

例：k=3a1(0.4)R0a2(0.3)1a3(0.2)a3a4a5(0.3)20a4(0.05)21a5(0.05)22滿樹012012第14頁,共38頁，星期六，2024年，5月赫夫曼編碼(8)

k=4,s=1,m=7a1(0.4)R0a2(0.3)1a3(0.2)2a4(0.05)a4,a5,a6,a7(0.1)30a5(0.05)31a6,a7(0)不用32，33012

1

302第15頁,共38頁，星期六，2024年，5月赫夫曼編碼(9)

k=3,l=1.3,

=1.95/(1.3log3)=94.6%k=4,l=1.1,

=1.95/(1.1log4)=88.6%k=5,l=1,

=1.95/log5=84%

為了提高效率，需有m>>k,m=2時(shí)，能用并元來擴(kuò)大m，S個(gè)符號(hào)并成一個(gè)使m=2S。例：獨(dú)立二元序列p0=0.7,H=0.881,S=3

第16頁,共38頁，星期六，2024年，5月赫夫曼編碼(10)

符號(hào)概率碼字碼長符號(hào)概率碼字碼長

0000.3430020110.063100040010.1471121010.0631001401000631010410000271.0114l=2.726/3=0.909,

=0.881/0.909=96.9%

增大S尚可進(jìn)一步提高效率。第17頁,共38頁，星期六，2024年，5月赫夫曼編碼(11)并元還可部分解除相關(guān)性。若

P(0|0)=0.97,P(0|1)=0.07,

利用平穩(wěn)性，可得：p0=0.7,p1=0.30000.65900110.019511111110.259101100.0195110100010.020411000100.001471101101000.020411101010.00147110111第18頁,共38頁，星期六，2024年，5月赫夫曼編碼(12)

l=1.53/3=0.51<0.909

=48.3%

平均碼長更小，但效率下降，說明相關(guān)性未完全解除。

4.缺點(diǎn)和措施兩大問題：

a.變速輸出和恒速傳輸?shù)拿?，必須用存?chǔ)器來調(diào)整。存儲(chǔ)量的估計(jì)：第19頁,共38頁，星期六，2024年，5月赫夫曼編碼(13）若信源每秒輸出S個(gè)符號(hào)，符號(hào)的平均碼長為L比特，信道傳輸速率為R比特每秒，且R=SL,則T內(nèi)的必特?cái)?shù)為

x=∑ls,Ex=SLT=RT,

令y=(x-Ex)/,2是ls的方差，T大時(shí)，y是標(biāo)準(zhǔn)正態(tài)變量，設(shè)存儲(chǔ)器容量為2A

,開始為半滿，則取空和溢出的概率是

(-A)=p(y>A)=p(y<-A)第20頁,共38頁，星期六，2024年，5月赫夫曼編碼(14）根據(jù)要求的概率可選定A值,即得所需的存儲(chǔ)器容量。若R≠SL或起始存儲(chǔ)器非半滿，所需容量將增加。

b.差錯(cuò)擴(kuò)散問題差錯(cuò)使碼字分離出錯(cuò)而向后擴(kuò)散。最佳方案是全存儲(chǔ)和分段檢錯(cuò)反問要求重發(fā)。第21頁,共38頁，星期六，2024年，5月游程編碼（1）另一種擴(kuò)展二元信源符號(hào)集的方法。

1.游程和游程序列

0游程，其長度l0=連0個(gè)數(shù)，

1游程，其長度l1=連1個(gè)數(shù)。都是隨機(jī)變量，二元序列可變換成游程序列，例：000101110010001…3113213…第22頁,共38頁，星期六，2024年，5月游程編碼（2）二元時(shí)，若約定起始必為0游程，上列變換是可逆的。但對(duì)于多元序列不行。

2.游程長度的概率特性獨(dú)立序列：

p(l0)=p0l0-1p1,0游程必以10開始。

El0=∑l0p(l0)=1/p1,H(l0)=-∑p(l0)logp(l0)=H(p0)/p1,第23頁,共38頁，星期六，2024年，5月游程編碼（3）

同理，El1=1/p0，H(l1)=H(p0)/p0,

則對(duì)應(yīng)原序列的符號(hào)熵是

H=[H(l0)+H(l1)]/(El0+El1)=H(p0)

將0游程長度和1游程長度分別編赫夫曼碼(此時(shí)m>>2),可逼近H(l0)和H(l1)從而得到很高的編碼效率，比并元更易于實(shí)現(xiàn)，且能更好地解除相關(guān)性（一階和二階可全解除，更高階可減弱。這可說明如下：

第24頁,共38頁，星期六，2024年，5月游程編碼（4）

1游程以下列形式開始:…x01y…,x與前一個(gè)0游程長度有關(guān)，y是與當(dāng)前1游程長度有關(guān)，對(duì)于一階或二階馬氏鏈，當(dāng)01一定時(shí)，y的概率已與x的取值無關(guān)，也就是當(dāng)前1游程的長度與前一個(gè)0游程的長度相互獨(dú)立，游程序列是獨(dú)立序列。它對(duì)應(yīng)于原序列的符號(hào)熵等于原序列的條件熵。計(jì)算這熵值也可得這一結(jié)果。第25頁,共38頁，星期六，2024年，5月游程編碼（5）二元高階馬氏鏈通過游程變換雖不能完全解除相關(guān)性，但至少可降階，并減弱相關(guān)性。x010…101y中間ｋ個(gè)０1相間個(gè)符號(hào)。對(duì)于ｋ階馬氏鏈，ｙ的概率與ｘ取值無關(guān)，當(dāng)前的１游程只與前面ｋ-2個(gè)游程有關(guān),游程序列降至k-2階。不是０1相間時(shí)還要降得多。降階后的序列相關(guān)性也較弱。第26頁,共38頁，星期六，2024年，5月游程編碼（6）

3.實(shí)現(xiàn)問題：兩種游程分別編赫夫曼碼，兩個(gè)碼表。符號(hào)集中有無限個(gè)元，必須截止。令Ｎ=2n,l=1,2…2n-1各給一個(gè)碼字。l＞2n-1,用一個(gè)碼字C，

2n→Ｃ00..0(n個(gè)0),2n+1→C00..1

第27頁,共38頁，星期六，2024年，5月游程編碼（7）

2n+1-1→C11..1,2n+1→C00..0C00..02n+1+1→C00..0C00..1………0游程的n可與1游程的n不同，0游程的C不但要與本碼表的碼字異前置，還要與1游程的碼表異前置。才能分辨C00..0C是

0游程長度為2n，后面的C是1游程，還是0游程長度大于2n+1-1。第28頁,共38頁，星期六，2024年，5月冗余位編碼（1）

1.概述：冗余位---間隙固定碼位分成兩個(gè)序列傳送例x1,x2…xnyyyyyyxn+1,xn+2…xn+myyyy

分成x1,x2…xn,xn+1…xn+m和

11…..1000000111….10000

可逆變換第29頁,共38頁，星期六，2024年，5月冗余位編碼（2）后一序列通常是一階馬氏鏈，若

P(0|0)=a,P(0|1)=b,則

p0=a/(1-a+b),p1=/(1-b+a)H(y)=pH(a)+pH(b),H=H(y)+p1H(x)

當(dāng)p1小時(shí)，可極大地壓縮碼率。但同時(shí)傳送兩個(gè)序列有困難，通常只好分段來編碼。第30頁,共38頁，星期六，2024年，5月冗余位編碼（3）

2.L-D碼幀長N,信息位數(shù)Q,

nj是第j個(gè)信息位的位置0<n1<…<nO<N

傳送Q和T兩個(gè)值，就可正確譯碼。若,則nQ=k+1

第31頁,共38頁，星期六，2024年，5月冗余位編碼（4）

若,則nQ-1=l+1

直至求得n1，就可恢復(fù)這一幀。

由

.

第32頁,共38頁，星期六，2024年，5月冗余位編碼（5）

這樣就可唯一地判定nQ,

以后的T’相當(dāng)于Q-1個(gè)信息位的情況。從而判定nQ-1.

編一幀需比特第33頁,共38頁，星期六，2024年，5月冗余位編碼（6）

例：001000000010000N=15，Q=2，n1=3,n2=11,

需要4比特編Q,0010.

需要7比特編T,0101111

得碼字00100101111a3a11。

若Q=0或N,可只用4位碼：0000或1111

第34頁,共38頁，星期六，2024年，5月冗余位編碼（7）

Q0