信息論與編碼實(shí)用教案

1、2022-7-71離散(lsn)序列信源的熵 設(shè)信源輸出(shch)的隨機(jī)序列為X =(X1X2XlXL) 序列中的變量Xlx1,x2, xn 隨機(jī)序列的概率為 式中，112121312121321111212()(,)() (/) (/)(/)() (/) (/)(/)iLLLLiiiLiiiiiiiiiiiiiiiLiip Xp XxXxXxp xp xxp xx xp xp xp xxp xxxpxxxxx11211LLiiiixx xx第1頁/共42頁第一頁，共43頁。2022-7-72121231( )()() () ()()()LLlLiiiiiiiiilpp x xxp xp x

2、p xp xxp x離散(lsn)無記憶信源的序列熵 當(dāng)信源無記憶(jy)時(shí)信源的序列熵為12121211221211111111()( )log( )()log()loglogloglogloglog()LLllLLLLLLLLnniiiillnnniiiiiiiiinnniiiiiiiiiLlliiHppp xp xp xp xp xp xp xp xp xp xp xp xpXxp xH Xxx 第2頁/共42頁第二頁，共43頁。2022-7-731LHHH XLXX1LllHH XLXXH離散(lsn)無記憶信源的序列熵 當(dāng)信源平穩(wěn)時(shí)，即與序號(hào)l無關(guān) 信源的序列熵可以表示為 信源序列中

3、，平均每個(gè)符號(hào)的熵為 離散(lsn)無記憶信源平均每個(gè)符號(hào)的符號(hào)熵HL(X)等于單個(gè)符號(hào)信源的符號(hào)熵H(X) 12,LLiiiip xp xp xp ppx第3頁/共42頁第三頁，共43頁。2022-7-74例題(lt) 有一個(gè)無記憶信源隨機(jī)變量X(0,1)，等概率分布，若以單個(gè)符號(hào)出現(xiàn)為一事件，則此時(shí)(c sh)的信源熵： 如果以兩個(gè)符號(hào)出現(xiàn)(L=2的序列)為一事件，則隨機(jī)序列X(00,01,10,11)，信源的序列熵 信源的符號(hào)熵為11()2log1 /22H Xbit 符號(hào)11()4log2 /44XHbit 序列211 /2HHHbiXtXX符號(hào)第4頁/共42頁第四頁，共43頁。202

4、2-7-75例題(lt) 例：有一離散平穩(wěn)(pngwn)無記憶信源求：二次擴(kuò)展信源的熵解：123111244xxxXP91log3 bit/iiiHpXp 序列211.5 /2HHbXXitH X符號(hào)第5頁/共42頁第五頁，共43頁。2022-7-76離散有記憶(jy)信源的序列熵 若信源輸出一個(gè)L長序列，則信源的序列熵為 平均每個(gè)符號(hào)的熵為 信源無記憶(jy)時(shí) 滿足平穩(wěn)時(shí)12121111()()()(/)(/)(/)()LLLLlLllHH X XXH XH XXH XXXH XH XXX1LHXXHL1LllHH XXH XLH X第6頁/共42頁第六頁，共43頁。2022-7-77例題

5、(lt) 例：已知離散有記憶(jy)信源中各符號(hào)的概率空間為:41943611210aaaPX第7頁/共42頁第七頁，共43頁。2022-7-78222100(/)()log(/)0.872 /ijjiijH XXp a ap aabit 符號(hào)例題(lt) 解：條件熵單符號(hào)信源熵信源的序列(xli)熵平均符號(hào)熵20()( )log( )1.543 /iiiH Xp ap abit 符號(hào)12121/2.415 bit/H X XH XH XX序列21211.207 bit/2HH X XX 符號(hào)第8頁/共42頁第八頁，共43頁。2022-7-79離散(lsn)平穩(wěn)信源 離散平穩(wěn)信源的聯(lián)合概率具有

6、(jyu)時(shí)間推移不變性 即平穩(wěn)信源發(fā)出的符號(hào)序列的概率分布與時(shí)間起點(diǎn)無關(guān)。 結(jié)論1：H(XL/XL-1)是L的單調(diào)非增函數(shù)12121212,LLiiiLihihihLp Xx XxXxp Xx XxXx1212311122-12322123211/ / /LLLLLLLLLLH XX XXH XX XXH XX XXH XX XXH XX XXH XXH X第9頁/共42頁第九頁，共43頁。2022-7-7101121121121112111/1 /1 /LlLLllLLLLLLHH X XXH XXLLH XH XXH XX XXLLH XX XXHXXXL離散(lsn)平穩(wěn)信源 結(jié)論(j

7、iln)2： HL (X) H(XL/XL-1) 結(jié)論(jiln)3： HL (X)是L的單調(diào)非增函數(shù)12121121111/ 1/1LLLLLLLLLLXXXXLHH X XXH X XXH XX XXLHH XXLHH1LLHHXX012LXHXHXHHXHX第10頁/共42頁第十頁，共43頁。2022-7-711離散(lsn)平穩(wěn)信源 結(jié)論4：當(dāng)L時(shí)，H(X)稱為極限熵 結(jié)論4在理論上定義了平穩(wěn)離散有記憶信源的極限熵，實(shí)際上如按此公式計(jì)算極限熵是十分困難的。 對(duì)于一般離散平穩(wěn)信源，取不太大的L就能得到非常接近H(X)的HL(X) ，因此實(shí)際應(yīng)用中常(zhngchng)取有限L下的條件熵H

8、(XL/XL-1)作為H(X)的近似值。121limlim/defLLLLLHHX XXH XXX第11頁/共42頁第十一頁，共43頁。2022-7-712馬爾可夫信源 在很多信源的輸出序列中，符號(hào)之間的依賴關(guān)系是有限的，信源符號(hào)發(fā)生的概率只與前邊已經(jīng)發(fā)出的若干個(gè)符號(hào)有關(guān)，而與更前面(qin mian)的符號(hào)無關(guān)。 為了描述這類信源，除了信源符號(hào)集外還要引入狀態(tài)集。即：信源輸出消息符號(hào)除與符號(hào)本身有關(guān)外，還與信源所處的狀態(tài)有關(guān)。 若一個(gè)信源滿足下面兩個(gè)條件，則稱為馬爾可夫信源： 某一時(shí)刻信源輸出符號(hào)的概率只與當(dāng)前所處的狀態(tài)有關(guān)，而與以前的狀態(tài)無關(guān)； 信源的下一個(gè)狀態(tài)由當(dāng)前狀態(tài)和下一刻的輸出符號(hào)

9、唯一確定。第12頁/共42頁第十二頁，共43頁。2022-7-713馬爾可夫信源 對(duì)于m階馬爾可夫信源X(x1,x2,xq)，引入符號(hào)條件概率和狀態(tài)轉(zhuǎn)移概率，可以轉(zhuǎn)化為馬爾可夫鏈。 令si = (xi1xi2xim)，i1,i2,im (1,2,q) 信源符號(hào)表中的數(shù)目為q， m個(gè)符號(hào)組成的序列(xli)si共有Q =qm種，這些序列(xli)組成狀態(tài)集S=s1,s2,sQ 例：二元序列(xli)為01011100，若m = 2，則Q =qm=22= 4，即s1=00 s2=01 s3=10 s4 = 11對(duì)應(yīng)的狀態(tài)序列(xli)為： s2s3s2s4s4s3s1第13頁/共42頁第十三頁，共

10、43頁。2022-7-714馬爾可夫信源 符號(hào)條件概率 信源在某一時(shí)刻出現(xiàn)符號(hào)xj的概率與信源此時(shí)所處(su ch)的狀態(tài)si有關(guān)，用條件概率表示為p(xj /si) i=1,2, ,Q j=1,2, ,q 狀態(tài)轉(zhuǎn)移概率 當(dāng)信源符號(hào)xj出現(xiàn)后，信源所處(su ch)的狀態(tài)將發(fā)生變化，并轉(zhuǎn)入一個(gè)新的狀態(tài)。這種狀態(tài)的轉(zhuǎn)移可用狀態(tài)轉(zhuǎn)移概率表示,/ijnjmijipm np SsSsp ss第14頁/共42頁第十四頁，共43頁。2022-7-715馬爾可夫信源 一步轉(zhuǎn)移(zhuny)概率（基本轉(zhuǎn)移(zhuny)概率） Pij(m,n)中n=m+1，即Pij(m, m+1)，記為Pij(m) pij(m

11、) = pSm+1=sj /Sm= si=p(sj /si) 齊次馬爾可夫鏈 其轉(zhuǎn)移(zhuny)概率具有推移不變性，即只與狀態(tài)有關(guān)，與時(shí)刻m無關(guān) pij(m) = pSm+1=sj /Sm= si=p(S2=sj /S1=si)=pij 性質(zhì)：0;1ijijjpp第15頁/共42頁第十五頁，共43頁。2022-7-7161111(/)QjiQQQppPp sspp轉(zhuǎn)移概率(gil)矩陣 若信源處于某一狀態(tài)si ，當(dāng)發(fā)出一個(gè)符號(hào)后，所處狀態(tài)就改變了。任何時(shí)候信源處于什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出的符號(hào)決定。 系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間S = s1,s2,sQ中的任意一個(gè)狀態(tài)，狀態(tài)轉(zhuǎn)移時(shí)的

12、轉(zhuǎn)移概率矩陣 矩陣中第i行元素對(duì)應(yīng)于從某一個(gè)狀態(tài)si轉(zhuǎn)移到所有(suyu)狀態(tài)sj的轉(zhuǎn)移概率 第j列元素對(duì)應(yīng)于從所有(suyu)狀態(tài)si轉(zhuǎn)移到同一狀態(tài)sj的轉(zhuǎn)移概率 符號(hào)條件概率矩陣1111(/)qjiQQqppPp xspp第16頁/共42頁第十六頁，共43頁。2022-7-717齊次馬爾可夫鏈 切普曼柯爾莫郭洛夫方程 k步轉(zhuǎn)移概率與l(lk)步和(k-l)步轉(zhuǎn)移概率之間的關(guān)系 當(dāng)l1時(shí)， 若用矩陣(j zhn)表示， klk lijirrjrppp 11kkkijirrjirrjrrpp ppp 12kkkkPPPPPPP第17頁/共42頁第十七頁，共43頁。2022-7-718狀態(tài)(zh

13、ungti)轉(zhuǎn)移圖（香農(nóng)線圖） 齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）表示 每個(gè)圓圈(yunqun)代表一種狀態(tài) 狀態(tài)之間的有向線代表從某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移 有向線一側(cè)的符號(hào)和數(shù)字分別代表發(fā)出的符號(hào)和條件概率第18頁/共42頁第十八頁，共43頁。2022-7-70.5(/)0.8jiPp xs例題(lt) 例：設(shè)有一個(gè)二進(jìn)制二階馬爾可夫信源，信源符號(hào)集為0,1，條件概率為繪制(huzh)該信源的狀態(tài)轉(zhuǎn)移圖。0/00(1/11)0.81/00(0/11)0.20/01(0/10)1/01(1/10)0.5pppppppp0.80.200000.5

14、0.5(/)0.50.500000.20.8jiPp ss第19頁/共42頁第十九頁，共43頁。2022-7-720,12211YXYXY例題(lt) 例：如圖所示是一個(gè)相對(duì)碼編碼器。輸入的碼Xr(r=1,2,)是相互獨(dú)立的，取值0或1，且已知p(X=0)=p, p(X=1)=1p=q，輸出的碼是Yr，顯然Yr是一個(gè)一階馬氏鏈，Yr確定后，Yr+1概率分布只與Yr有關(guān)(yugun)，與Yr-1 、Yr-2 等無關(guān)p00= p(Y2=0/Y1=0)= p(X=0)= p p01= P(Y2=1/Y1=0)= p(X=1)= q p10= P(Y2=0/Y1=1)= p(X=1)= q p11=

15、p(Y2=1/Y1=1)= p(X=0)= pTXrYrpqPqp第20頁/共42頁第二十頁，共43頁。2022-7-721穩(wěn)定(wndng)的馬爾可夫信源 不可約性 對(duì)任意一對(duì)i和j，都存在至少一個(gè)k，使pij(k)0 若對(duì)所有k，pij(k) 0，意味著一旦出現(xiàn)狀態(tài)si就不再可能到達(dá)狀態(tài)sj，無法各態(tài)遍歷 非周期性 所有pij(n)0的n中沒有(mi yu)比1大的公因子第21頁/共42頁第二十一頁，共43頁。2022-7-722馬爾可夫信源 遍歷性的直觀意義 不論質(zhì)點(diǎn)從哪一個(gè)狀態(tài)si出發(fā)，當(dāng)轉(zhuǎn)移步數(shù)k足夠大時(shí)，轉(zhuǎn)移到sj的概率pij(k)都近似等于某個(gè)常數(shù)Wj 即：如果轉(zhuǎn)移步數(shù)k充分大，

16、就可以用常數(shù)Wj作為k步轉(zhuǎn)移概率pij(k)的近似值 意味著：馬爾可夫信源在初始時(shí)刻可以處在任意狀態(tài)，信源狀態(tài)之間可以轉(zhuǎn)移。經(jīng)過足夠長時(shí)間之后，信源處于什么狀態(tài)已與初始狀態(tài)無關(guān)，每種狀態(tài)出現(xiàn)的概率已達(dá)到一種穩(wěn)定(wndng)分布。第22頁/共42頁第二十二頁，共43頁。2022-7-723iijjiW pW limkijjkpW穩(wěn)定(wndng)的馬爾可夫信源 極限概率Wj 一個(gè)不可約的、非周期的、狀態(tài)有限的馬爾可夫鏈，其k步轉(zhuǎn)移概率pij(k)在k時(shí)趨于一個(gè)和初始狀態(tài)無關(guān)的概率，即 不論起始狀態(tài)如何，這種馬氏鏈都可以最后達(dá)到穩(wěn)定，即所有(suyu)變量Xk的概率分布均不變?？梢杂肞這一矩陣充

17、分描述穩(wěn)定的馬氏鏈。 平穩(wěn)分布Wj可用下列方程組求得1jjW 第23頁/共42頁第二十三頁，共43頁。2022-7-724例題(lt) 例：有一個(gè)二元二階馬爾可夫信源，信源符號(hào)集為0,1,狀態(tài)變量S=00,01,10,11。已知符號(hào)條件概率(gil)： p(0/00) = 1/2 p(1/00)=1/2 p(0/01) = 1/3 p(1/01)=2/3 p(0/10) = 1/4 p(1/10)=3/4 p(0/11) = 1/5 p(1/11)=4/5 求：信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率(gil) 畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。 求平穩(wěn)分布概率(gil) 第24頁/共42頁第二十四頁，

18、共43頁。2022-7-725例題(lt)121234( )( )() 1/21/2() 1/32/3(/)() 1/43/4(0100011011) 1/54/5jiaassp asss5/45/100004/34/13/23/100002/12/1)|(43214321sssssspssssij(1)1/2(0)1/2(0)1/3(1)2/300011110(1)3/4(0)1/4(0)1/5(1)4/5第25頁/共42頁第二十五頁，共43頁。2022-7-726例題(lt)131132243244123411241324113524351ijWWWWWWpWWWWWWWWWWijiWW1

19、23436,353564,357WWWW11()(/) ( )iiip ap as p s1316161492353354355735221326364426()(/) ( )2353354355735iiip ap as p s第26頁/共42頁第二十六頁，共43頁。2022-7-7271/2 1/4 1/4/01/2 1/2100jip as例題(lt)123123,Xa a aSs s s03/41/4/01/21/2100jip ss 第27頁/共42頁第二十七頁，共43頁。2022-7-728馬爾可夫信源的熵 M階馬爾可夫信源的極限(jxin)熵齊次、遍歷的馬爾可夫信源的熵1( )(

20、/ )miiiHp s H X s(/ )(/ )log (/ )ijijijH X sp xsp xs 1211121lim/LLLmmmHH XX XXHXXXXXHX 第28頁/共42頁第二十八頁，共43頁。2022-7-729例題(lt)00.500.20.8P第29頁/共42頁第二十九頁，共43頁。2022-7-730第2章信源及信源熵2.1 信源的描述(mio sh)和分類2.2 離散信源熵和互信息2.3 離散序列信源的熵2.4冗余度2.5連續(xù)信源的熵和互信息第30頁/共42頁第三十頁，共43頁。2022-7-731冗余度 又稱多余度、剩余度，表示信源在實(shí)際發(fā)出

21、消息時(shí)所包含的多余信息。 冗余度來自(li z)兩個(gè)方面： 信源符號(hào)間的相關(guān)性：相關(guān)程度越大，信源的實(shí)際熵越小，趨于極限熵；相關(guān)程度減小，信源實(shí)際熵增大。 信源符號(hào)分布的不均勻性：等概率分布時(shí)信源熵最大。第31頁/共42頁第三十一頁，共43頁。2022-7-732冗余度 理論上傳送一個(gè)信源的信息(xnx)，只需要傳送極限熵H(X)即可。 實(shí)際上只能計(jì)算出Hm(X) H(X) 信息(xnx)效率 冗余度01mHXHX11mHXHX 第32頁/共42頁第三十二頁，共43頁。2022-7-733冗余度 由于信源存在冗余度，即存在一些不必要傳送的信息，因此信源就存在進(jìn)一步壓縮其信息率的可能性。 信源冗

22、余度越大，其進(jìn)一步壓縮的潛力(qinl)越大。這是信源編碼與數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。 例：英文字母26個(gè)，加上空格27個(gè)符號(hào)等概率 H0 = log27 = 4.76比特/符號(hào) 不等概率 H1 = 4.03比特/符號(hào) 考慮相關(guān)性 H2 = 3.32比特/符號(hào) 極限熵 H =1.4比特/符號(hào)00.2910.71HXHX 信息效率冗余度第33頁/共42頁第三十三頁，共43頁。2022-7-734冗余度 哪種語言(yyn)最簡潔？第34頁/共42頁第三十四頁，共43頁。2022-7-735第2章信源及信源熵2.1 信源的描述和分類(fn li)2.2 離散信源熵和互信息2.3 離散序列信源的熵2.

23、4冗余度2.5連續(xù)信源的熵和互信息第35頁/共42頁第三十五頁，共43頁。2022-7-736連續(xù)(linx)信源的熵和互信息 連續(xù)信源的求解 先將連續(xù)信源在時(shí)間上離散化，再對(duì)連續(xù)變量進(jìn)行量化分層，并用離散變量來逼近連續(xù)變量。 量化間隔越小，離散變量與連續(xù)變量越接近，當(dāng)量化間隔趨近于零時(shí)，離散變量就等于(dngy)連續(xù)變量。 連續(xù)信源的概率空間 ( , )( )( )XXa bRXpxpxP或( )0( )1( )1XbXXaRpxpx dxpx dx或第36頁/共42頁第三十六頁，共43頁。2022-7-737(1)( )()( )1ia i xXxXaiiaiXp xppx dxaxxpi

24、 連續(xù)(linx)信源的熵和互信息 離散(lsn)化 , ,()/ ,(1),ixa bxbanxaix ai x 令11( )log( )( )log( )nniiXiXiiinHXp xp xpxxpxx ）第37頁/共42頁第三十七頁，共43頁。2022-7-738連續(xù)(linx)信源的熵和互信息 極限(jxin)化 當(dāng)n，即x0時(shí)，00lim ( )log( )lim log( ) ( )lolim log g( )nnbbXiXiXiXXiaaxbxiaH XHXpxpx dxpxpxpxxx dxdx ()( )log( )cXXHXpxpx dx 第38頁/共42頁第三十八頁，共43頁。2022-7-739連續(xù)(linx)信源的熵和互信息 連續(xù)(lin