《信息論與編碼》習(xí)題集

1、第二章習(xí)題：補(bǔ)充題：擲色子，(1)若各面出現(xiàn)概率相同(2)若各面出現(xiàn)概率與點(diǎn)數(shù)成正比試求該信源的數(shù)學(xué)模型6解：(1)根據(jù)p(ai) 1,且 p(a1) Lp(a6),得i 11 、，p(a1) Lp(a6),所以信源概率空間為66r1(2)根據(jù)p(aj 1,且 p(a1)k, p(a2) 2k,L p(a6) 6k ,得 k 一。i 1212-2由符號(hào)集 0,1組成的二階馬爾可夫鏈，其轉(zhuǎn)移概率為P(0/00)=0.8 , P(0/11)=0.2 , P(1/00)=0.2 ,P(1/11)=0.8 , P(0/01)=0.5 , P(0/10)=0.5 , P(1/01)=0.5 , P(1/

2、10)=0.5 。畫出狀態(tài)圖，并計(jì)算各狀態(tài)的 穩(wěn)態(tài)概率。解：由二階馬氏鏈的符號(hào)轉(zhuǎn)移概率可得二階馬氏鏈的狀態(tài)轉(zhuǎn)移概率為：P(00/00)=0.8 P(10/11)=0.2 P(01/00)=0.2P(11/11)=0.8 P(10/01)=0.5 P(00/10)=0.5二進(jìn)制二階馬氏鏈的狀態(tài)集各狀態(tài)穩(wěn)定概率計(jì)算:S=S1, S2,S3, S4=00 , 01, 10, 11P(11/01)=0.5 P(01/10)=0.54Wjj 14WiPij i 1W1W1P11W2P21W3P31W4P41W2W1P12W2P22W3P32W4P42W3W1P13W2P23W3P33W4P43W4W1P

3、14W2P24W3P34W4P44 TOC o 1-5 h z W1W2 W3 W41得：W1 W4 W2 W3 1414即：P(00)=P(11)= P(01)=P(10)=14143時(shí)，該消息所包含的信息量是多少？當(dāng)小圓點(diǎn)數(shù)之和2-6擲兩粒骰子，當(dāng)其向上的面的小圓點(diǎn)數(shù)之和是 是7時(shí)，該消息所包含的信息量又是多少？ 解：6P P(1) P(6) P(2) P(5) P(3) P(4) P(4) P(3) P(5) P(2) P(6) P(1) 27 36 2-7I (7) log 2 p(7) log 2 6(比特)2-7設(shè)有一離散無記憶信源，其概率空間為該信源發(fā)出的消息符號(hào)序列為(202

4、120 130 213 001 203 210 110 321 010 021 032 011 223 210),求此消息的自信息量是多少及平均每個(gè)符號(hào)攜帶的信息量？解：消息序列中，“0”個(gè)數(shù)為n1=14, “1”個(gè)數(shù)為n2=13, “2”個(gè)數(shù)為n3=12, “3”個(gè)數(shù)為n4=6.消息序列總長為N = n + n2 + n3 + n4=45(個(gè)符號(hào))(1)消息序列的自信息量：(2)平均每個(gè)符號(hào)攜帶的信息量為：2-14在一個(gè)二進(jìn)制信道中，信息源消息集X=0, 1,且P(1)=P(0),信宿的消息集 丫=0, 1,信道傳輸概率 P ( 1/0) =1/4 , P (0/1 ) =1/8。求：(1)

5、在接收端收到y(tǒng)=0后，所提供的關(guān)于傳輸消息x的平均條件互信息量I (X;y=0)。(2)該情況所能提供的平均互信息量I (X; Y)。解：X=0,1,Y=0,11求 p(yj)p(xyj)i 0 1(2) I(X;Y)P(yj)I(X;yj)j 02-25某一無記憶信源的符號(hào)集為0, 1,已知p0 1/4, p1 3/4。(1)求符號(hào)的平均嫡。(2)由100個(gè)符號(hào)構(gòu)成的序列，求某一特定序列(例如有m個(gè)0和100-m個(gè)1)的自信息量的表達(dá)式。(3)計(jì)算(2)中的序列的嫡。解：(1)對(duì)離散無記憶信源符號(hào)的平均嫡：21133H (X)p(Xi )log p(Xi)-log - -log - 0.81

6、 比特/符號(hào)i 14444(2)長度為L=100的符號(hào)序列中某特定序列i (00 011 1),其中“0”的個(gè)數(shù)為m, “1”的個(gè)數(shù)為100-m.該特定序列的概率為對(duì)離散無記憶信源，其符號(hào)獨(dú)立出現(xiàn)，即P( i)P(00 011 1)P(0)P(0)p(0)p(1)p(1)p(1) p(0)mp(1)100m 則該特定序列的自信息量為：=41+1.59m (bit)(3)長度為L=100的符號(hào)序列離散無記憶信源嫡：100H(XL)=H(X 1X2 X100)=H(X| ) LH (X) 100H(X)=81 (比特/序列)2-30 有一馬爾可夫信源，已知轉(zhuǎn)移概率為 p(s1/s1) 2/3, p

7、/s1) 1/ 3 , p(S) / s2) 1 , p(s2 / s2) 0。試畫出狀態(tài)轉(zhuǎn)移圖，并求出信源嫡。解：(1)由題意知，該馬爾可夫信源階數(shù)為(2)信源嫡：a)求穩(wěn)態(tài)概率 Wi p(si)1,狀態(tài)集S二Sl,S2狀態(tài)轉(zhuǎn)移圖為:22W WW2Wj 1WiWiRi W 2P213Aj 1_1計(jì)算方程：:即：W2 叫電 W2P22W2 皿23WiPij WjWiW21W W 1i 1V VV V21得：W10.75W1 0.25即：P(S1)=0.75, P(S2)=0.25b)求 H(X/S i)2H(X/S i )p Xj/ si log p x / si2則信源嫡：H H2psiHX

8、/si1-33 11=P Si p(&)H X/& p s2 H X /s2-H -, H 1,044 34=0.69比特/符號(hào)2-33 一階馬爾可夫信源的狀態(tài)圖如圖2-14所示，信源X符號(hào)集為0, 1, 2。(1)求平穩(wěn)后信源的概率分布；(2)求信源嫡H ;(3)求當(dāng)p=0或p=1時(shí)信源的嫡，并說明其理由。解：(1) 一階馬爾可夫信源的狀態(tài)空間S=X=0 , 1, 2,由圖2-14狀態(tài)轉(zhuǎn)移圖中分析得，此馬爾可夫鏈?zhǔn)菚r(shí)齊的，狀態(tài)有限的和不可約閉集，非周期，所以具有各態(tài)歷經(jīng)性。平穩(wěn)后狀態(tài)的極限分布存在，因?yàn)槭且浑A馬爾可夫信源，狀態(tài)的極限分布即平穩(wěn)后信源符號(hào)的一維概率分布，即根據(jù)狀態(tài)轉(zhuǎn)移圖，得狀態(tài)

9、一步轉(zhuǎn)移矩陣：計(jì)算方程組3皿Wp11W2p21W3 p31WjWiPiji 1 3Wj1W2即皿口2 W2p22W3 p32W3W1p13W2p23W3p33j 1W1W2 W31整理計(jì)算得：W1 W2 W31/3即狀態(tài)極限概率P(0)=P(1)=P(2)=1/3(2)根據(jù)馬爾可夫信源嫡的表達(dá)式：3由 H X /Sip xj /xi log p xj /xij i同理 H X/1H(p,1 p)從而3 p(0) H 1 p, p Hip, p (1 p)log(1 p) plog p 比特/符號(hào)(3)當(dāng)p=0或p=1時(shí)信源的嫡H H 1 p, p H (1,0)H(0,1) 0,這是因?yàn)閜=0

10、或p=1時(shí)信源為確定性信源，觀察著對(duì)信源發(fā)出什么符號(hào)不存在任何不確定度，所以信源不提供任何的信息量。AfV* zzfe弟二早3-1 .設(shè)二進(jìn)制對(duì)稱信道的概率轉(zhuǎn)移距陣為，紂(1)若p(El )=3/4,p(0)=1/4，求 H(X),H(X|Y),H(Y|X)和I(X;Y)。(選做)(2)求該信道的信道容量及其達(dá)到信道容量時(shí)的輸入概率分布。解：(1)由題意可得x的先驗(yàn)概率p(Q)=3/4,p(D)=1/4.H(x)=H(3/4,1/4)=0.82bit/ 符號(hào)由概率轉(zhuǎn)移距陣得 符號(hào)轉(zhuǎn)移概率：p(匚I |匚I )=2/3,p(IZI|IZI )=1/3,p(匚1|匚I )=1/3,p(IZI|匚I

11、 )=2/3.聯(lián)合概率： p(口口 )=p(LI)pl 口 )=1/2同理:p(口 口 )=1/4 , p(口=1/12, pd，口)=1/6則條件嫡：=0.91bit/符號(hào)另外p(y0)p(xy。)p(x0y。)p(xy。)p(Q)=7/12p(口=5/12H (Y)p(yj)10g p(yj)=0.9799根據(jù) H(XY) H(X) H(Y/X) H (Y) H (X/Y)得H (X/Y) H (X) H (Y/X) H(Y)=0.7494bit/符號(hào)互信息：I (X;Y) H(X) H (Y / X) H (Y) H (Y/X) =0.066bit/符號(hào)(2)由概率轉(zhuǎn)移距陣，可知該信道為

12、對(duì)稱DMC信道第4頁故其信道容量：C log 2 m H (Y / x )(m=2為接收端信宿符號(hào)集中符號(hào)數(shù)目)log2 2 H (2 /3,1/ 3) =0.082bit/符號(hào)當(dāng)其達(dá)到信道容量時(shí)輸入為等概分布P(尸P(口)=1/2.1PP3-5求下列兩個(gè)信道的容量，并加以比較PP2解：由于兩信道均為準(zhǔn)對(duì)稱信道(行元素對(duì)應(yīng)相同，但列元素不相同)，可分解為其信道容量公式為則一1- 八 ,Q 0Ci C2.,即信道2比信道1好一些。23-10. 一個(gè)平均功率受限制的連續(xù)信道，其通頻帶為1MHZ，信道上存在白色高斯噪聲。(1)已知信道上的信道的信號(hào)與噪聲的平均功率比值為10,求該信道的信道容量；(2

13、)信道上的信道與噪聲的平均功率比值降至5,要達(dá)到相同的信道容量，信道通頻帶應(yīng)為多大？(3)若信道通頻帶減為 0.5MHZ時(shí)，要保持相同的信道容量，信道上的信號(hào)與噪聲的平均功率比值應(yīng)等 于多大？解：由題意可得：由SNR=10信道的信道容量：C=wIl=3.46Mbit/s(2)若SNR=5,信道容量彳W寺不變.由 c=wII得亞=。Ll=1.34MHZ若W減為0.5 MHZ,信道容量保持不變由。=w回正包易得第四章1+SNR=121 故 SNR=120.4-1設(shè)有一個(gè)二元等概信源X=0, 1, p0P1 1/2,通過一個(gè)二進(jìn)制對(duì)稱信道(BS。其失真函數(shù)dj與信道轉(zhuǎn)移概率pj分別定義為試求失真矩陣

14、d和平均失真D。.,1 ,ii一,解：由dj, 失真矩陣dj 0 ,ijPj,ij轉(zhuǎn)移概率矩陣p,ij平均失真為4-3設(shè)輸入符號(hào)表與輸出符號(hào)表為X=Y=0 ,1, 2, 3,且輸入信號(hào)的分布為p(X i) 1/4,i 0,1,2,3 ,設(shè)失真矩陣為求Dmin , Dmax和R(Dmin ) , R(Dmax)以及相應(yīng)的編碼器轉(zhuǎn)移概率矩陣。解：對(duì)離散信源，Dmin 0當(dāng)Dmin 0時(shí)為無失真編碼，信源符號(hào)與碼符號(hào)一一對(duì)應(yīng)，即10 0 0則信道轉(zhuǎn)移概率矩陣為 p0 10 00 0 100 0 0 1R(Dmax) 0 得 pjpj假設(shè)j 1時(shí)失真達(dá)到Dmax ,即pi1p1則 p(b1) 1,p也

15、)p(b3)p(b4) 010 0 0此時(shí)信道轉(zhuǎn)移概率矩陣為10 0 010 0 010 0 04-5具有符號(hào)集U U0,U1的二元信源，信源發(fā)生概率為： p(U0) p,p(U0) 1 p, 0 p 1/2。Z 信道如圖4-7所示，接收符號(hào)集 V Vo,Vi,轉(zhuǎn)移概率為：p(Vo/Uo) 1, p(Vi/Ui) 1 q。發(fā)出符號(hào) 與接收符號(hào)的失真： d(u0,v0) d(u1,v1) 0 , d(u1,v0) d(u0,v1) 1。(1)計(jì)算平均失真 D；此時(shí)平均失真D是多大?此時(shí)平均失真D是多大?(2)率失真函數(shù) R(D)的最大值是什么？當(dāng)q為什么值時(shí)可達(dá)到該最大值?(3)率失真函數(shù) R(

16、D)的最小值是什么？當(dāng)q為什么值時(shí)可達(dá)到該最小值?(4)畫出、口)口的曲線。解：概率轉(zhuǎn)移矩陣為:失真矩陣為D(1)1111Dp(Ui, Vj)d(u,Vj)p(Ui)p(Vj /Ui)d(u,Vj)i 0 j 0i 0 j 0p(U0)p(V0/u0)d(U0,V0) p(U0)p(V1/u0)d(U0,V1) p(u1)p(v0 /u1)d(u,V1) p(u1)p(v1/u1)d(U1,V1)0 0 q(1 p) 0 q(1 P)；(2) maxR(D) H (U )plog p (1 p)log(1 p),率失真函數(shù)取最大值時(shí)比對(duì)應(yīng)最小的失真，對(duì)離散信源，最小失真為零，即Dq(1 p)|

17、min 0,由于 0 p 1/2,所以 1 p 0,貝Uq0(3) min R(D) 0 ,對(duì)應(yīng)最大的失真,解方程 R(D) H(U)得 q 0則平均失真D 0;D q(1 p) max 1 p 此時(shí) D q(1 p) 0(4) R(D)D 曲線：(2) (3)的傳統(tǒng)解法：maxR(D) H (U) plog p (1 p)log(1 p)min R(D) 0,令 R(D)=0 ,得 q 1此時(shí)平均失真D q(1 p) 1 p第五章信源編碼5-1將下表所列的某六進(jìn)制信源進(jìn)行二進(jìn)制編碼，試問(1)這些碼中哪些是唯一可譯碼？(2)哪些碼是非延長碼(即時(shí)碼)？(3)對(duì)所有的唯一可譯碼求出其平均碼長和

18、編碼效率。解：C1=000 , 001, 010, 011, 100, 101 C2=0 , 01, 011, 0111, 01111, 011111C3=0 , 10, 110, 1110, 11110, 111110C1碼組為等長碼，因各碼字均不相同，則必為唯一可譯碼。C2碼組中各碼字長度分別為k1 1,k2 2,k3 3,k1 1,k, 4*5 5,則根據(jù)克勞夫特不等式則存在該碼長分布的唯一可譯碼；下一步檢驗(yàn)該碼長構(gòu)成的具體碼字：最短的碼字“0”是其他碼的前綴，尾隨后綴分別為1, 11, 111, 1111, 11111,這些尾隨后綴都不是碼組中的單獨(dú)碼字；次短的碼字“01”是碼字011

19、, 0111, 01111, 011111的 前綴，其尾隨后綴為11, 111, 1111, 11111不是碼組中的單獨(dú)碼字，.依次可判斷其他次短碼字雖然是長碼字的前綴，但尾隨后綴均不是碼組中的單獨(dú)碼字，由此可斷定該碼字 是唯一可譯碼。C3碼組的碼長分布與 C2碼組相同，滿足克勞夫特不等式，下一步檢驗(yàn)該碼長構(gòu)成的具體碼字：最短的碼字“0不是其他碼字的前綴，沒有尾隨后綴，次短碼字“10“、110” “1110 ”、”11110”都不是其他碼字的前綴，沒有尾隨后綴，所以必是唯一可譯碼。(C3碼組滿足克勞夫特不等式，又是非前綴碼，所以是唯一可譯碼)C1、C2、C3是唯一可譯碼，在唯一可譯碼中，分為即

20、時(shí)碼和非即時(shí)碼。即時(shí)碼的判斷方法有兩 種：根據(jù)定義：即時(shí)碼又叫非前綴碼或非延長碼。則 C1、C3是即時(shí)碼根據(jù)碼樹：碼組中的各碼字都處在樹的終端節(jié)點(diǎn)上，則為即時(shí)碼。第7頁碼樹省略判斷結(jié)果為：C1、C3的各碼字均處在碼樹的終端節(jié)點(diǎn)上，是即時(shí)碼6根據(jù)公式Kp(u)kii 1根據(jù)編碼效率公式H(X)得K61_ 11H (X) p(ui)log p(ui) log 2 log 4 4 log162 比牛寸/付3i 124165-10 設(shè)有離散無記憶信源 P(X尸0.37,0.25,0.18,0.10,0.07,0.03;(1)求該信源符號(hào)嫡H(X);(2)用哈夫曼編碼編成二進(jìn)制變長碼，計(jì)算編碼效率。(3

21、)要求譯碼錯(cuò)誤小于10 3 ,采用定長二元碼要達(dá)到(2)中的哈夫曼編碼效率，問需要多少個(gè)信源符號(hào) 連在一起編？6解：(1)信源嫡 H(X)p(xjlog p(xj 2.26比特/符號(hào)i 1(2)用哈夫曼編碼編成二進(jìn)制變長碼為00 , 01, 11, 101, 1000, 1001平均碼長_6k kip(xi)0.37 2 0.25 2 0.18 2 0.1 3 0.07 4 0.03 4 2.3 碼符號(hào)/信源符號(hào)i 1編碼效率小(9 26 98.3%k 2.3(3)要求譯碼錯(cuò)誤小于10 3,采用定長二元碼要達(dá)到(2)中的哈夫曼編碼效率。第一步： 根據(jù)H(X)98.3%0.039H(X)第二步

22、2(X) E I(xi) E(I(x)2 E I(x) H(X) 2 EI(x)2H(X)2 0.7983 人一_3要求譯碼錯(cuò)誤小于10 ，令 10 ,則需要一起編的符號(hào)長度應(yīng)滿足5-12已知一信源包含 8個(gè)消息符號(hào)，其出現(xiàn)的概率P(X尸0.1,0.18,0.4,0.05,0.06,0.1,0.07,0.04,則求(1)該信源在每秒內(nèi)發(fā)出一個(gè)符號(hào)，求該信源的嫡及信息傳輸速率；(2)對(duì)這8個(gè)符號(hào)作哈夫曼編碼，寫出相應(yīng)碼字，并求出編碼效率；(3)進(jìn)行香農(nóng)編碼，寫出相應(yīng)碼字，并求出編碼效率；(4)進(jìn)行費(fèi)諾編碼，寫出相應(yīng)碼字，并求出編碼效率；8解：(1)信源嫡 H (X) p(xi)log p(xi)

23、 2.55 比特/符號(hào) i 1信息傳輸速率Rt nH(X) 1 H (X) 2.55比特/秒(2)對(duì)這8個(gè)符號(hào)作哈夫曼編碼所編碼為1 , 001 , 011, 0000, 0100, 0101, 00010, 00011;平均碼長_8碼符號(hào)/信源符號(hào)k kiP(Xi)i 10.4 10.18 3 0.13 0.1 4 0.07 4 0.064 0.050.042.61編碼效率H(X)k255 97.7%2.61(3)香農(nóng)編碼 編碼過程： 所編碼為00 , 平均碼長011, 10011010, 1100, 11011, 11101,11110;_8k kiP(xJi 10.4 20.18 3 0

24、.14 0.1 4 0.07 40.065 0.050.043.17編碼效率H(X)2 55T 80.4%3.17碼符號(hào)/信源符號(hào)(4)費(fèi)諾編碼 所編碼為00 , 平均碼長011001100, 1101, 11101111；_8k kiP(Xi)i 10.4 20.182 0.1 30.1 3 0.07 40.06 4 0.050.042.64編碼效率HJ 注 96.6%碼符號(hào)/信源符號(hào)2.64補(bǔ)充1：幾種實(shí)用的無失真信源編碼方法. MH編碼它將游程編碼和哈夫曼編碼MH編碼是用于黑白二值文件傳真的數(shù)據(jù)壓縮編碼。它是一維編碼方案。 相結(jié)合的一種標(biāo)準(zhǔn)的改進(jìn)哈夫曼碼。游程編碼是無失真信源編碼，二元序

25、列編成多元碼在二元序列中，只有0”和1”兩個(gè)碼元，我們吧連續(xù)出現(xiàn)的0“叫做0”游程，連續(xù)出現(xiàn)的 叫做1游程。連續(xù)出現(xiàn) 0”或者1”碼元的個(gè)數(shù)叫做游程長度。這樣，一個(gè)二元序列可以轉(zhuǎn)換成游程序列，例如：二元序列0001100111100010 可以變換成3224311 ,若規(guī)定游程必須從 ?！庇纬涕_始，則上述變換是可逆的。如果連0或連1”非常多，則可以達(dá)到信源壓縮的目的。游程編碼是無失真信源編碼.算術(shù)編碼算術(shù)編碼也是一種無失真信源編碼方法。前面討論的無失真信源編碼方法，都是針對(duì)單個(gè)信源符號(hào)的編碼，當(dāng)信源符號(hào)之間有相關(guān)性時(shí)，這些第9頁編碼方法由于沒有考慮到符號(hào)之間的相關(guān)性，因此編碼效率就不可能很高。

26、解決的辦法是對(duì)較長的信源序列進(jìn)行編碼，但會(huì)遇到與定長編碼時(shí)同樣的問題。而且，采用前面的序列編碼需要完全知道聯(lián)合概率和條件概率，這在場合下也是比較困難的。為了解決這個(gè)問題，需要跳出分組碼的局限，研究非分組碼。算術(shù)編碼就是一種非分組編碼方法。其基本思路是：從全序列出發(fā)，將不同的信源序列的累計(jì)概率映射到 0 ， 1 區(qū)間上，使每個(gè)序列對(duì)應(yīng)區(qū)間上的一點(diǎn)，也就是說，把區(qū)間 0 ， 1 分成許多互不重疊的小區(qū)間，不同的信源序列對(duì)應(yīng)不同的小區(qū)間，可以證明，只要這些小區(qū)間互不重疊，就可以編得即時(shí)碼。這種編碼方法無需計(jì)算出所有信源序列的概率分布及編出碼表，可以直接對(duì)輸入的信源符號(hào)序列進(jìn)行編碼輸出。 LZ 碼LZ

27、 碼是一種通用編碼方法，無需知道信源的統(tǒng)計(jì)特性，而且編碼效率很高?；舅惴ㄊ牵簩㈤L度不同的符號(hào)串編成一個(gè)新的短語(符號(hào)串)，形成短語詞典的索引表。LZ78 是一種分段編碼 ，它的短語詞典是由前面已見到的文本字段來定義的。(續(xù)上) 補(bǔ)充2：幾種常用的限失真信源編碼方法： 矢量量化連續(xù)信源進(jìn)行編碼的主要方法是量化，即將連續(xù)的樣值X離散化成為yi, i 1,2,L ,nn是量化級(jí)數(shù)，這樣就把連續(xù)值轉(zhuǎn)化為n個(gè)實(shí)數(shù)中的一個(gè)，可以用 0, 1,2,，n等n個(gè)數(shù)字來表示。由于x是一個(gè)標(biāo)量，因此稱為標(biāo)量量化 。在量化的過程中，將會(huì)引入失真，量化是必須使這些失真最小。要想得到更好的性能，僅采用標(biāo)量量化是不可能的

28、。從前面的討論我們已經(jīng)知道，把多個(gè)信源符號(hào)組成一個(gè)符號(hào)序列進(jìn)行聯(lián)合編碼可以提高編碼效率。連續(xù)信源也是如此，當(dāng)把多個(gè)信源符號(hào)聯(lián)合起來形成多維矢量，然后進(jìn)行量化，可以進(jìn)一步壓縮碼率，這種量化方法叫做矢量量化 。實(shí)驗(yàn)證明，即使各信源符號(hào)相互獨(dú)立，矢量量化也可以壓縮信息率，因此，人們對(duì)矢量量化非常感興趣，是當(dāng)前信源編碼的一個(gè)熱點(diǎn)，而且不僅限于連續(xù)信源，對(duì)離散信源也可以如此。如圖像編碼時(shí)采用矢量量化，但由于聯(lián)合概率密度不易測定，目前常用的是訓(xùn)練序列的方法，如圖像編碼時(shí)就要采用訓(xùn)練序列的方法，找到其碼書，進(jìn)行量化。還可以與神經(jīng)網(wǎng)絡(luò)方法結(jié)合，利用神經(jīng)網(wǎng)絡(luò)的自組織來得到訓(xùn)練集。 預(yù)測編碼預(yù)測就是從已收到的符號(hào)

29、來提取關(guān)于未收到的符號(hào)的信息，從而預(yù)測其最可能的制作為預(yù)測值。并把它與實(shí)際值之差進(jìn)行編碼，由于這個(gè)差值一般都比較小，所以在編碼時(shí)會(huì)出現(xiàn)很多連“0”值，再采用游程編碼，就可以大大地壓縮碼率。由此可見，預(yù)測編碼是利用信源符號(hào)之間的相關(guān)性來壓縮碼率的，對(duì)于獨(dú)立信源，預(yù)測就沒有可能。 變換編碼變換是一個(gè)廣泛的概念。變換編碼就是經(jīng)變換后的信號(hào)能更有效地編碼，也就是通過變換來解除或減弱信源符號(hào)間的相關(guān)性，以達(dá)到壓縮碼率的效果(如單頻率正弦波信號(hào)，變換到頻域) 。一般地，對(duì)一個(gè)函數(shù) f (t) ，變換式為：而反變換為：要使上式成立，要求(i, t) 必須是正交完備的(相當(dāng)于歐氏空間的坐標(biāo)投影) ，求 ai

30、的公式，實(shí)際上就是內(nèi)積運(yùn)算，把函數(shù)f(t) 投影到 (i,t) 上去。信源編碼常用的變換有：DCT (discrete Cosine Transform )變換：如JPEG、MPEG等圖像壓縮標(biāo)準(zhǔn)中，就是主要采用的這種變換壓縮方法。K-L 變換： K-L 變換是均方誤差準(zhǔn)則下的最佳變換。它是一種正交變換，變幻后的隨機(jī)變量之間互不相關(guān)，一般認(rèn)為， K-L 變換是最佳變換，其最大缺點(diǎn)是計(jì)算復(fù)雜，除了需要測定相關(guān)函數(shù)和解積分方程外，變換時(shí)的運(yùn)算也十分復(fù)雜，也沒有快速算法，因此， K-L 變換不是一種實(shí)用的變換編碼方法，但經(jīng)常用來作為標(biāo)準(zhǔn)，評(píng)估其他方法的優(yōu)劣。( 3 ) 小波( Wavelet Tra

31、nsform )變換：小波變換是當(dāng)前信號(hào)處理以及多種應(yīng)用科學(xué)中廣泛用到的一種相當(dāng)有效的數(shù)學(xué)工具。 小波變換的概念首先是由法國的石油地質(zhì)工程師J.Morlet 于 1980 年提出的， 1990 年 Mallat 等人一起建立了多分辯分析的概念。與經(jīng)典的 Fourier 分析相比較，小波的最大優(yōu)勢是變換本身具有時(shí)間與頻率的雙重局部性質(zhì)，解決 了 Fourier 分析不能處理的許多實(shí)際問題，因而小波變換被人們稱之為 “數(shù)學(xué)顯微鏡”。20 世紀(jì) 90 年代中期以前， 圖像壓縮主要采用離散余弦變換(DCT) 技術(shù)， 著名的 JPEG、 H.263 等圖像壓縮國際標(biāo)準(zhǔn)均采用 DCT 方法實(shí)現(xiàn)圖像壓縮。而

32、 DCT 最大的缺陷是當(dāng)壓縮比較大時(shí)，會(huì)出現(xiàn)馬賽克效應(yīng)，因而影響圖像壓縮質(zhì)量。 最近幾年來， 由于小波變換具有DCT 無可比擬的良好壓縮性質(zhì)， 在最新推出的靜態(tài)圖像壓縮國際標(biāo)準(zhǔn)JPEG2000 中， 9/7 雙正交小波變換已經(jīng)正式取代 DCT 而作為新的標(biāo)準(zhǔn)變換方法。( 4 )分形( Fractal Transform )變換：基于塊的分形編碼是一種利用圖像的自相似性來減少圖象冗余度的新型編碼技術(shù)，它具有以下特點(diǎn)：? 較高的壓縮比。? 解碼圖象的分辨率無關(guān)性?？砂慈我飧哂诨虻陀谠幋a圖象的分辨率來進(jìn)行解碼。當(dāng)要解碼成較 高分辨率圖象時(shí)，引入的細(xì)節(jié)會(huì)與整個(gè)圖象大致和諧一致，從而比象素復(fù)制或插值方

33、法得到的圖象看起來更自然。這種縮放能力也可以用作圖象增強(qiáng)工具。? 解碼速度快。分形壓縮是一非對(duì)稱過程，雖然編碼很耗時(shí) ，但解碼速度快，因此較適用于一次 編碼多次解碼的應(yīng)用中。? 編碼時(shí)間過長，實(shí)時(shí)性差，從而阻礙了該方法在實(shí)際中的廣泛應(yīng)用。還有很多其他的編碼方法，這里就不再一一介紹了。補(bǔ)充3：香農(nóng)第二定理信道編碼定理、 有噪信道編碼定理如一個(gè)離散無記憶信道，信道容量為Co當(dāng)信息傳輸率RWC時(shí)，只要碼長足夠長，總可以找到一種信道編碼方法，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。、 有噪信道編碼逆定理如一個(gè)離散無記憶信道，信道容量為Co當(dāng)信息傳輸率 RC時(shí)，則無論碼長n多長，總找不到一種編碼方法，

34、使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。這個(gè)定理是信道編碼的理論依據(jù)，可以看出：信道容量是一個(gè)明確的分界點(diǎn)，當(dāng)取分界點(diǎn)以下的信息傳輸率時(shí)，信道輸出端誤碼率以指數(shù)趨進(jìn)于 0 ；當(dāng)取分界點(diǎn)以下的信息傳輸率時(shí)， 輸出端誤碼率以指數(shù)趨進(jìn)于 1 ；因此在任何信道中，信道容量都是可達(dá)的、最大的可靠信息傳輸率。這個(gè)定理是一個(gè)存在定理，它沒有給出一個(gè)具體可構(gòu)造的編碼方法，在它的證明過程中，碼書是隨機(jī)的選取的，它有助于指導(dǎo)各種通信系統(tǒng)的設(shè)計(jì)，有助于評(píng)價(jià)各種系統(tǒng)及編碼的效率。補(bǔ)充4：無噪信道編碼定理無失真信源編碼定理失真信源編碼定理通常又稱為無噪信道編碼定理。 此定理可以表述為：若信道的信息傳輸率 R 不大于信

35、道容量C， 總能對(duì)信源的輸出進(jìn)行適當(dāng)?shù)木幋a， 使得在無噪無損信道上能無差錯(cuò)地以最大傳輸率C 傳輸信息；但要使信道的信息傳輸率R 大于 C 而無差錯(cuò)地傳輸信息是不可能的。Ss1s2補(bǔ)充5：若有一信源ss每秒鐘發(fā)出 2.66 個(gè)信源符號(hào)。將此信源的輸出符號(hào)送入某一個(gè)p(s)0.80.2二元信道中進(jìn)行傳輸(假設(shè)信道是無噪無損的 ) ，二信道每秒鐘傳遞二個(gè)二元符號(hào)。試問此信源不通過編碼能否直接與信道連接？若通過適當(dāng)編碼能否在信道中進(jìn)行無失真?zhèn)鬏?？若能連接， 使說明如何編碼并說明 原因。解：信源p(s)si s20.8 0.2其信源嫡2H(S) p(Si)log p(Si) 0.722 比特/符號(hào) i

36、1而其每秒鐘發(fā)2.66個(gè)信源符號(hào)，所以信源輸出的信息速率為送入一個(gè)二元無噪無損信道，此信道的最大信息傳輸率(信道容量)C=1比特/符號(hào)。而信道每秒鐘只傳送兩 個(gè)二元符號(hào)，所以信道的最大信息傳輸速率可見Rt Ct ,根據(jù)無噪信道編碼定理(即無失真信源編碼定理)，因?yàn)镽t Ct ,所以總能對(duì)信源的輸出進(jìn)行適當(dāng)?shù)木幋a，使此信源在此信道中進(jìn)行無失真?zhèn)鬏?。如果?duì)信源不進(jìn)行編碼，直接將信源符號(hào)si以0符號(hào)傳送，s2以1符號(hào)傳送，這時(shí)因?yàn)樾旁摧敵鰹?.66二元信源符號(hào)/秒，大于2二元信道符號(hào)/秒，就會(huì)使信道輸入端造成信源符號(hào)的堆積，信息不能按時(shí) 發(fā)送出去。所以，不通過編碼此信源不能直接與信道連接。若要連接，

37、必須對(duì)信源的輸出符號(hào)序列進(jìn)行編碼，也就是對(duì)此信源的 N次擴(kuò)展信源進(jìn)行編碼。但擴(kuò)展次數(shù)N越大，編碼越復(fù)雜，設(shè)備代價(jià)越大，所以盡量使擴(kuò)展次數(shù)N小，而又能使信源在此信道中無失真?zhèn)鬏?。先考慮N=2,并對(duì)二次擴(kuò)展信源進(jìn)行哈夫曼編碼，得得k2 1.56二元符號(hào)/信源序列k 0.78二元符號(hào)/信源符號(hào)二次擴(kuò)展編碼后，送入信道的傳輸速率為所以，必須考慮 N=3即對(duì)三次擴(kuò)展信源進(jìn)行哈夫曼編碼，得 得k3 2.184二元符號(hào)/信源序列k 0.728二元符號(hào)/信源符號(hào)二次擴(kuò)展編碼后，送入信道的傳輸速率為 此時(shí)，就可以在此信道中進(jìn)行無失真?zhèn)鬏斄?。、，、?S s1 s2 一, 一- 一人補(bǔ)充6 :若有一信源每秒鐘發(fā)出

38、2.66個(gè)信源符號(hào)。將此信源的輸出符號(hào)送入某一個(gè)p(s) 0.5 0.5二元信道中進(jìn)行傳輸(假設(shè)信道是無噪無損的)，二信道每秒鐘傳遞二個(gè)二元符號(hào)。(1)試問此信源能否在此信道中無失真?zhèn)鬏敗?2)若此信源失真測度定義為漢明失真，問允許信源平均失真為多大時(shí)，此信源就可以在此信道中傳輸。左 Ss1S2解：(1)信源p(s)0.5 0.5其信源嫡2H(S) p(Si)log p(Si) 1 比特/符號(hào) i 1而其每秒鐘發(fā)2.66個(gè)信源符號(hào)，所以信源輸出的信息速率為送入一個(gè)二元無噪無損信道，此信道的最大信息傳輸率(信道容量)C=1比特/符號(hào)。而信道每秒鐘只傳送兩個(gè)二元符號(hào)，所以信道的最大信息傳輸速率可見

39、Rt Ct ,根據(jù)無噪信道編碼定理(即無失真信源編碼定理)，因?yàn)镽t Ct,所以不論進(jìn)行任何編碼此信源都不可能在此信道中實(shí)現(xiàn)無失真的傳輸，所以信源在此信道中傳輸會(huì)引起錯(cuò)誤和失真。(2)若此信源失真測度定義為漢明失真，因?yàn)槭嵌旁?，輸入是等概分布，所以信源地信息率失真函?shù)為R(D) 1 H (D)比特/信源符號(hào)Rt(D) 2.66R(D) 2.66(1 H(D)比特/秒若Ct Rt(D)則此信源在此信道中傳輸時(shí)不會(huì)引起錯(cuò)誤。也就是不會(huì)因?yàn)樾诺蓝黾有旁葱碌氖д??？偟男旁吹氖д媸?信源壓縮編碼所造成的允許失真D。所以有故 D=0.0415允許信源平均失真為 D=0.0415時(shí)，此信源就可以在此信

40、道中傳輸補(bǔ)充7:為了傳輸一個(gè)由字母 A, B, C, D組成的符號(hào)集，把每個(gè)字母編碼成二元碼脈沖序列，以“00”代表A, “01”代表B, “10”代表C, “11”代表D,每個(gè)二元碼脈沖寬度為 5ms,不同字母等概率出現(xiàn)時(shí)，計(jì)算傳輸?shù)男畔⑺俾剩?113右每個(gè)子母出現(xiàn)的概率分別為Pa -，Pb-，Pc-，Pa，試計(jì)算傳輸?shù)男畔⑺俾省?4410解：(1)不同字母等概率出現(xiàn)時(shí)，符號(hào)集的概率空間為：每個(gè)符號(hào)含有的平均信息量即嫡為：5ms,則每個(gè)字母占用t 2 10ms。H(X) log 2 4 2比特/符號(hào)(字母)現(xiàn)在用兩個(gè)二元碼脈沖代表1個(gè)字母，每個(gè)二元碼脈沖寬度為一秒內(nèi)可以傳輸?shù)淖帜競€(gè)數(shù)：1 一一 , n - 100字母/秒t則信息傳輸速率：R nH(X) 200 比特/秒(2)字母出現(xiàn)概率不同時(shí)，據(jù)題意其概率空間為 則此時(shí)每個(gè)字母含有的平均信息量為：4H (X) p(ajog p(aj 1.985 比特/符號(hào)i 1同(1),計(jì)算得傳輸?shù)男畔⑺俾蕿镽 nH (X) 198.5 比特/秒第六章信道編碼例1設(shè)有一離散信道，其信道轉(zhuǎn)移矩陣為并設(shè)p(x1 1/2, p(x2) p(x3) 1/4,試分別按最小錯(cuò)誤概率準(zhǔn)則與最大似然譯碼準(zhǔn)則確定譯碼規(guī)則,并計(jì)算相應(yīng)的平均錯(cuò)誤概率。解：由于本離散信道的輸入符號(hào)的先驗(yàn)概率p(xi)不是等概分布，所以