信息論與編碼試題集與答案講解

1、一填空題（本題20分，每小題2分）Hg = -fpdjbgp（叩1平均自信息為-表示信源的平均不確定度，也表示平均每個信源消息所提供的信息量。 心）=-yy?（口）bg p;?平均互信息-:表示從丫獲得的關(guān)于每個X的平均信息量，也表示發(fā)X前后丫的平均不確定性減少的量，還表示通信前 后整個系統(tǒng)不確定性減少的量。2、最大離散熵定理為：離散無記憶信源，等概率分布時熵最大。3、最大熵值為4、通信系統(tǒng)模型如下:噪聲bitfs為保證足夠大的信道容量,可采用（1）用頻帶換信噪比;Ct lim =障log1 +5、香農(nóng)公式為I（2）用信噪比換頻帶6、只要;，當(dāng)N足夠長時，一定存在一種無失真編碼。7、當(dāng)Rv C

2、時，只要碼長足夠長，一定能找到一種編碼方法和譯碼規(guī)則，使譯碼錯誤概率無窮小。 8在認識論層次上研究信息的時候，必須同時考慮到 形式、含義和效用 三個方面的因素。9、1948年，美國數(shù)學(xué)家 香農(nóng) 發(fā)表了題為“通信的數(shù)學(xué)理論”的長篇論文，從而創(chuàng)立了信息論 按照信息的性質(zhì)，可以把信息分成 語法信息、語義信息和語用信息 。按照信息的地位，可以把信息分成客觀信息和主觀信息。人們研究信息論的目的是為了 高效、可靠、安全 地交換和利用各種各樣的信息。信息的 可度量性 是建立信息論的基礎(chǔ)。統(tǒng)計度量是信息度量最常用的方法。熵 是香農(nóng)信息論最基本最重要的概念。事物的不確定度是用時間統(tǒng)計發(fā)生概率的對數(shù)來描述的。10

3、、 單符號離散信源一般用隨機變量描述，而多符號離散信源一般用隨機矢量 描述。11、 一個隨機事件發(fā)生某一結(jié)果后所帶來的信息量稱為自信息量，定義為其發(fā)生概率對數(shù)的負值。12、自信息量的單位一般有 比特、奈特和哈特。13、必然事件的自信息是0。14、 不可能事件的自信息量是s。15、 兩個相互獨立的隨機變量的聯(lián)合自信息量等于兩個自信息量之和。16、數(shù)據(jù)處理定理：當(dāng)消息經(jīng)過多級處理后，隨著處理器數(shù)目的增多，輸入消息與輸出消息之間的平均 互信息量趨于變小 。17、離散平穩(wěn)無記憶信源X的N次擴展信源的熵等于離散信源 X的熵的N倍。18、 離散平穩(wěn)有記憶信源的極限熵，出：=何：屮風(fēng)以必2 X。19、對于n

4、元m階馬爾可夫信源，其狀態(tài)空間共有 nm個不同的狀態(tài)。20、 一維連續(xù)隨即變量X在a，b區(qū)間內(nèi)均勻分布時，其信源熵為log2 (b-a)。1log 2 2二 eP21、 平均功率為P的高斯分布的連續(xù)信源，其信源熵，Hc (X) =2。22、對于限峰值功率的N維連續(xù)信源，當(dāng)概率密度 均勻分布 時連續(xù)信源熵具有最大值。23、 對于限平均功率的一維連續(xù)信源，當(dāng)概率密度高斯分布 時，信源熵有最大值。24、 對于均值為0,平均功率受限的連續(xù)信源，信源的冗余度決定于平均功率的限定值P和信源的熵功率P之比25、若一離散無記憶信源的信源熵 H (X)等于2.5，對信源進行等長的無失真二進制編碼，則編碼長度至少

5、為3nZ m n 1對應(yīng)的二元序 列的編碼效率為n，則三者的關(guān)系是 n 0 n n 1。在實際的游程編碼過程中，對長碼一般采取截斷 處理的方法?！?”游程和“ 1”游程可以分別進行哈夫曼編碼，兩個碼表中的碼字可以重復(fù)，但C碼 必須不同。在多符號的消息序列中，大量的重復(fù)出現(xiàn)的，只起占時作用的符號稱為“冗余變換”即：將一個冗余序列轉(zhuǎn)換成一個二元序列和一個L-D編碼是一種分幀傳送冗余位序列的方法。L-D編碼適合于冗余位較多或較少的情況。信道編碼的最終目的是提高信號傳輸?shù)目煽啃元M義的信道編碼即：檢、糾錯編碼BSC信道即：無記憶二進制對稱信道n位重復(fù)碼的編碼效率是1/n。等重碼可以檢驗 全部的奇數(shù)位錯和

6、部分的偶數(shù)位錯85、86、87、8889、90、91、92、93、94、95、96、97、9899、任意兩個碼字之間的最小漢明距離有稱為碼的最小距若糾錯碼的最小距離為若檢錯碼的最小距離為線性分組碼是同時具有dmin，冗余位縮短了的多元序列。,mi nd(c,c)貝U dmin= cdmin -12-個差錯dmi n,則可以糾正任意小于等于t=dmi n，則可以檢測出任意小于等于l= dmi n-1 個差錯。 分組特性和線性特性的糾錯碼。100、循環(huán)碼即是采用循環(huán)移位特性界定的一類線性分組碼。1. 信息的基本概念在于它的不確定性 。2. 按照信源發(fā)出的消息在時間和幅度上的分布情況，可將信源分成離

7、散 信源和 連續(xù)信源兩大類。3. 個隨機事件的自信息量 定義為其出現(xiàn)概率對數(shù)的負值。4. 按樹圖法構(gòu)成的碼一定滿足 即時碼的定義。5. 有擾離散信道編碼定理稱為香農(nóng)第二極限定理。6. 糾錯碼的檢、糾錯能力是指 檢測、糾正錯誤碼元的數(shù)目。7. 信道一般指傳輸信息的物理媒介，分為有線 信道和 無線 信道。8. 信源編碼的主要目的是 提高通信系統(tǒng)的有效性。1 .設(shè)X的取值受限于有限區(qū)間a,b ,則X服從 均勻 分布時，其熵達到最大；如 X的均值為, 方差受限為二2，則X服從 高斯 分布時，其熵達到最大。2. 信息論不等式：對于任意實數(shù) z 0，有In z汐一1，當(dāng)且僅當(dāng)z = 1時等式成立。3. 設(shè)

8、信源為X=0，1，P （0） =1/8，則信源的熵為1/8呱8 7/8log2（7/8）比特/符號，如信源發(fā)出由m個“0”和（100-m）個“ 1”構(gòu)成的序列，序列的自信息量為mlog2 8 （100一 m）Iog2（7/8）比特/符號。4. 離散對稱信道輸入等概率時，輸出為等概 分布。5. 根據(jù)碼字所含的碼元的個數(shù)，編碼可分為定長 編碼和 變長 編碼。6. 設(shè)DM助U1U2U3U4U5U6用二元符號表X=X1=0x=1對其進行定Pu 一 0.37 0.250.18 0.10 0.07 0.03_長編碼，若所編的碼為000,001,010,011,100,101，則編碼器輸出碼元的一維概率 P

9、（xJ= 0.747 ,P（x2）二 0.253。1. 在現(xiàn)代通信系統(tǒng)中，信源編碼主要用于解決信息傳輸中的有效性，信道編碼主要用于解決信息傳輸中的可靠性，加密編碼主要用于解決信息傳輸中的安全性 。2. 離散信源 X = X1X2 X3 X4 ，則信源的熵為1.75bit/ 符號 。|p（x） 1/2 1/4 1/8 1/83. 對稱DMC信道的輸入符號數(shù)為n,輸出符號數(shù)為 m,信道轉(zhuǎn)移概率矩陣為pj，則該信道的容量為mC =log m 亠二 pij log pij。n4. 采用m進制編碼的碼字長度為K，碼字個數(shù)為n,則克勞夫特不等式為Ki 2進制的哈夫曼碼時，要考慮是否需要增加概率為0的碼字，

10、以使平均碼長最短。對42、 游程序列的熵（“0”游程序列的熵與“ 1”游程序列的熵的和）大于等于原二元序列的熵。錯43、 在游程編碼過程中，“0”游程和“ 1”游程應(yīng)分別編碼，因此，它們的碼字不能重復(fù)。錯44、 L-D編碼適合于冗余位較多和較少的情況，否則，不但不能壓縮碼率，反而使其擴張。對45、 狹義的信道編碼既是指：信道的檢、糾錯編碼。對46、 對于BSC言道，信道編碼應(yīng)當(dāng)是一對一的編碼，因此，消息m的長度等于碼字c的長度47、 等重碼和奇（偶）校驗碼都可以檢出全部的奇數(shù)位錯。對48、漢明碼是一種線性分組碼。對49、 循環(huán)碼也是一種線性分組碼。對50、 卷積碼是一種特殊的線性分組碼。錯三、

11、計算題1. 設(shè)隨機變量X =x1, x2 =0,1和 - y1, y2 - 0,1的聯(lián)合概率空間為(xi,y2)gyj3/83/8XY _ (心)_PxY = _ 1/8定義一個新的隨機變量z二X Y（普通乘積）1)計算熵 H (X), H (Y), H (Z), H (XZ,H (YZ,以及 H (XYZ；2)計算條件熵 H (X|Y), H( Y|X), H (X|Z), H (Z|X), H (Y|Z), H (Z|Y), H (X|YZ),以及 H ( Z|XY);3)計算平均互信息量I (X; Y), I (X: Z), I(Y: Z), I (X; Y|Z), I (Y; Z|X)

12、以及 I(Y|XZ),Z|Y)解：（1）XY0101/83/81/213/81/81/21/21/2H(X) =1/2log22 1/2log22=1H(Y) =1/2log22 1/2log22 =1110 111XYZ 000001010011100 1011/803/803/800 1/8Z 017/8 1/8H(Z) =7/8log2(8/7) 1/8log2 8XZ 000110111/203/8 1/8H(XZ) =1/2log2 2 3/8log2(8/3) 1/8log281/203/8 1/8H(YZ) =1/2log22 3/8log2(8/3) 1/8log28(2)H(

13、X|Y) -1/2(1/4log24 3/4log2(4/3) 1/2(1/4log2 4 3/4log2(4/3)H(Y|X) -1/2(1/4log24 3/4log2(4/3) 1/2(1/4log24 3/4log2(4/3)XZ0101/201/213/81/81/27/81/8H(X|Z)=7/8(4/7log2(7/4) 3/7log2(7/3) 1/8(0log20 1log21)H(Z |X) -1/2(1 log21 0log20) 1/2(3/4log2(4/3) 1/4log24)YZ0101/201/213/81/81/27/81/8H(Y|Z) =7/8(4/7lo

14、g2(7/4) 3/7 log2 (7/3) 1/8(0log2 0 1log2 1)H(Z |Y1/2(1log21 0log20) 1 /2(3/4log2(4/3) 1/4log24)H(X |YZ) =1/2(1/4log24 3/4log2(4/3) 3/8(1 log21 Olog?。)1/8(1 也1 OgO)H(Y | XZ) =1/2(1/4log2 4 3/4log2(4/3)3/8(1log21 0log20) - 1/8(1log2 V 0log20) H(Z | XY 0I(X;Y)二 H (X) -H (X |Y)I(X;Z) =H(X) -H(X |Z)l(Y;Z

15、) =H(Y) _H(Y|Z)I(X;Y|Z)二H(X |Z) -H(X |YZ)I(X;Z |Y) = H (X |Y) _H (X |ZY)2.設(shè)二元對稱信道的輸入概率分布分別為Px =3/41/4，轉(zhuǎn)移矩陣為Pyix丄2/31/31/32/3(1) 求信道的輸入熵，輸出熵，平均互信息量;(2) 求信道容量和最佳輸入分布;(3)求信道剩余度解：(1)信道的輸入熵 H(X)=3/4log2(4/3) 1/4log2 4 ；_1/21/4Pxy電/12 1/6一PY二7/12 5/12H(Y) =7/12log2(12/7) 5/12log2 (12/5)H (Y | X) =3/4H(1/2

16、,1/4)1 /4H (1/12,1 /6)I(X;Y)二H(Y) -H(Y|X)(2)最佳輸入分布為Px二1/2 1/2，此時信道的容量為C =1-H(2/3,1/3)信道的剩余度：C - l(X;Y)1/23.設(shè)有DMC，其轉(zhuǎn)移矩陣為札x】=1/61/3 1/61/2 1/3，若信道輸入概率為Px 1 - 0.5 0.25 0.251，.1/3 1/6 1/2試確定最佳譯碼規(guī)則和極大似然譯碼規(guī)則，并計算出相應(yīng)的平均差錯率11/41/61/12解: Pxy =1/241/81/121/121/241/8 一工(bjp最佳譯碼規(guī)則：F(b2)=a1，平均差錯率為1-1/4-1/6-1/8=11

17、/24、F(b3)十3極大似然規(guī)則:F(bJ*F(b2)理)=二a2，平均差錯率為=a3某系統(tǒng)(7, 4)碼C =(C6C5C4C3C2C1Co) =(m3m2mo C2 C1 Co)其三位校驗位與信息位的關(guān)系為:c2 = m3 mi m0* q = m3 十 m2 十 gc 0 = m2 + mo(1) 求對應(yīng)的生成矩陣和校驗矩陣；(2) 計算該碼的最小距離；(3) 列出可糾差錯圖案和對應(yīng)的伴隨式;(4) 若接收碼字R=111QQ11，求發(fā)碼解：1.2.dmin = 3-100010G =001000Q11QQQ11Q11111Q13.SE00000000000010000001010000

18、0010100000010010100010001110010000011010000011010000004. RHt=OO1接收出錯xY0101/31/31亠1/3E=QQQQQQ1R+E=C 1110010 (發(fā)碼)四、計算題已知X,Y的聯(lián)合概率p x, y為：求 H X，H Y，H X,Y，I X;Yp(y =0) =1/ 3 p(y =1) =2/3H X =H Y 二h(1/3,2/3) =0.918 bit/symbolH x,Y 二H(1/3,1/3,1/3)=1.585 bit/symbolI X;Y =H(x)H(Y)-H(X,Y) =0.251 bit/symbol五、計

19、算題一階齊次馬爾可夫信源消息集 X a1,a2,a3,狀態(tài)集S S1,S2,S3，且令Sai,i =1,2,3，條件轉(zhuǎn)移概率為P(aj/S|v3 13 1j3 ， (1)畫出該馬氏鏈的狀態(tài)轉(zhuǎn)移圖;(2)計算信源的極限熵。解：(1)H(X|S1) = H1/4,1/4,1/2)=1.5比特/符號比特/符號H(XS) =H1/3,1/3,1/3)=1.585H = f wH (X |S. )=0.4 X1.5 +0.3x1.585+0.3x0.918 丄.351 比特 / 符號 i =1六、計算題若有一信源X2 I,每秒鐘發(fā)出2.55個信源符號 P 一 p.8 0.2 一將此信源的輸出符號送入某一

20、個二元信道中進行傳輸（假設(shè)信道是無噪無損的，容量為 1bit/二元符號），而信道每秒鐘只傳遞2個二元符號。1）試問信源不通過編碼（即X1 0,X2 1在信道中傳輸）2）能否直接與信道連接？3）若通過適當(dāng)編碼能否在此信道中進行無失真?zhèn)鬏敚?）試構(gòu)造一種哈夫曼編碼（兩個符號一起編碼），5）使該信源可以在此信道中無失真?zhèn)鬏敗＝猓?.不能，此時信源符號通過0,1在信道中傳輸，2.55二元符號/s2二元符號/s2.從信息率進行比較，2.55* H (0.8,0.2) = 1.84 1*2可以進行無失真?zhèn)鬏?X1X1 0.6411X1X2 0.16100XX10.160101沁 0.0410.64 0.6

21、40* 0.361-0.200.13._4KpK =0.64 0.16*20.2*3 =1.56 二元符號 /2 個信源符號i i此時 1.56/2*2.55=1.989 二元符號 /s 2 二元符號 /s七、計算題兩個BSC信道的級聯(lián)如右圖所示:(1) 寫出信道轉(zhuǎn)移矩陣；(2) 求這個信道的信道容量。解:(1)一1 一 ez 一1一P叮名 1一(1一 名)2+21- ； 2；(1 - ；)2(1 - )2 2 (1E)+ Z(2) C =log2 -H(1 - ；)2；2)4.設(shè)有DMC，其轉(zhuǎn)移矩陣為lPY|X 11/21/61/31/31/21/61/61/3，若信道輸入概率為1/2Px

22、丨二 0.5 0.25 0.251，試確定最佳譯碼規(guī)則和極大似然譯碼規(guī)則，并計算出相應(yīng)的平均差錯率。(1/41/61/12解: Pxy =1/241/81/121/121/241/8 一最佳譯碼規(guī)則：F(b2Ha1，平均差錯率為1-1/4-1/6-1/8=11/24iF (b3)= a3極大似然規(guī)則：F(b2)=a2，平均差錯率為1-1/4-1/8-1/8=1/2。iF (b3)= a31.設(shè)有一個二進制一階馬爾可夫信源，其信源符號為X (0,1)，條件概率為p(0/0)= p (1/0)=0.5 p(1/1)=0.25p(0/1)=0.75畫出狀態(tài)圖并求出各符號穩(wěn)態(tài)概率。(15分)0.75W

23、0 -0.5W00.75W1W0 W =1W0 =0.6W1 =0.42. 設(shè)輸入符號與輸出符號為X= 丫 0,1,2,3，且輸入符號等概率分布。設(shè)失真函數(shù)為漢明失真。求Dnax和 Dnin 及 R( Dna)和 & gn)( 20 分)1解：P X。二 p 捲二 p X2 二 P X340 11110 11D =110 1.11 1 0 一失真矩陣的每一行都有0,因此din=0R Dmin 二R 0 二H X =log24=2bit/符號311113Dmax二qinp(Gd(Xi,yj) =411 1,4111,41 1 1i=0L444丿4R Dmax =0設(shè)隨機變量X =X1,X2二0,

24、1和丫 =%,y2 =0,1的聯(lián)合概率空間為XY_(X1,y1)(X1, y2)(X2,y1)(X2,y2)1H1/83/83/81/8 一定義一個新的隨機變量Z=X Y(普通乘積)計算熵 H (X)，H (Y)，H (Z)，H (XZ)，H( YZ)，以及 H (XYZ ；計算條件熵 H (X|Y), H( Y|X)，H (X|Z)，H (Z|X)，H (Y|Z)，H (Z|Y)，H (X|YZ)，H (Y|XZ)以及 H (Z|XY)；計算平均互信息量 I (X；Y)，I (X：Z)，I (Y：Z)，I(X；Y|Z)，I(Y；Z|X)以及 I(X:,Z|Y )。解: (1)XY0101/8

25、3/81/213/1/1/8821/21/2H(X) =1/2log22 1/2log22=1H(Y) =1/2log22 1/2log22 =1XYZ 0000010100111001011101111/803/803/8001/8Z 017/8 1/8H(Z) =7/8log2(8/7) 1/8log2 8XZ000110111/203/81/8H(XZ) =1/2log2 2 3/8log2(8/3) 1/8log28YZ000110111/203/8 1/8H(YZ) =1/2log22 3/8log2(8/3) 1/8log28(2)H(X |Y) -1/2(1/4log24 3/4

26、log2(4/3) 1/2(1/4log2 4 3/4log2(4/3)H(Y|X) -1/2(1/4log24 3/4log2(4/3) 1/2(1/4log24 3/4log2(4/3)Z0101/201/213/81/81/27/81/8H(X|Z) =7/8(4/7log2(7/4) 3/7log2(7/3) 1/8(0log20 1log21)H(Z|X) =1/2(1log21 0log20) 1/2(3/4log2(4/3) 1/4log24)Z0101/201/213/81/81/27/81/8H(Y|Z) =7/8(4/7log2(7/4) 3/7log2(7/3) 1/8(

27、0log2。Ilog?。H(Z |Y) =1/2(1log21 0log20) 1 /2(3/4log2(4/3) 1/4log24)H(X |YZ) =1/2(1/4log24 3/4log2(4/3) 3/8(1 log21 Olog?。)1/8(1 也1 Olog?。)H(Y | XZ) =1/2(1/4log2 4 3/4log2(4/3)3/8(1log21 0log20)1/8(1log2 V 0log20) H (Z | XY0I(X;Y)二 H(X) -H(X |Y) I (X;Z)二 H (X) -H(X |Z)I (Y;Z) =H (Y) -H (Y |Z) l(X;Y|Z

28、) =H(X |Z) -H(X |YZ)I(X;Z |Y) =H (X |Y) -H (X |ZY)設(shè)二元對稱信道的輸入概率分布分別為Px打3/4 1/4，轉(zhuǎn)移矩陣為_ 2/3 1/3-1/3 2/3一求信道的輸入熵，輸出熵，平均互信息量; 求信道容量和最佳輸入分布；求信道剩余度。解：(1)信道的輸入熵 H(X)=3/4log2(4/3) 1/4log24 ；Pxy二1/21/4Jj/12 1/6 一PY二7/12 5/12H(Y) =7/12log2(12/7) 5/12log2 (12/5)H (Y | X) =3/4H(1/2,1/4)1/4H (1/12,1/6)l(X;Y) =H(Y) -H(Y| X)2)最佳輸入分布為Px二1/2 1/2，此時信道的容量為C =1-H(2/3,1/3)信道的剩余度：C l(X;Y)1/2 1/3 1