信息論與編碼試題集與答案(新)

1、1. 在無失真的信源中，信源輸出由H(X)來度量；在有失真的信源中，信源輸出由R(D)來度量。2. 要使通信系統(tǒng)做到傳輸信息有效、可靠和，必須首先信源 編碼，然后一加密_編碼，再_信道.編碼，最后送入信道。3帶限AWGN波形信道在平均功率受限條件下信道容量的基本公式，也就是有名的香農(nóng)公式是C Wlog(1 SNR);當歸一化信道容量C/W趨近于零時，也即信道完全喪失了通信能力，此時Eb/No為-1.6 dB，我們將它稱作香農(nóng)限，是一切編碼方式所能達到的理論 極限。4. 系統(tǒng)的密鑰量越小，密鑰熵 H(K)就越 小，其密文中含有的關于明文的信息量I(M ； C)就越 大。425. 已知n= 7的循

2、環(huán)碼g(x) x x x 1，則信息位長度k為_J_，校驗多項式h(x) = x3 x 1。6. 設輸入符號表為 X= 0 , 1，輸出符號表為 Y= 0,1。輸入信號的概率分布為p = (1/2,1/2)，失真函數(shù)為 d(0, 0) = d(1, 1) = 0 , d(0, 1) =2 , d(1 , 0) = 1，則 Dmin= _0_, R(Dmin)1 0=1bit/symbol，相應的編碼器轉(zhuǎn)移概率矩陣p(y/x) =; Dmax=0.5 , R(Dmax)=0 10_，相應的編碼器轉(zhuǎn)移概率矩陣1 0p(y/x) = 10。7. 已知用戶 A的RSA公開密鑰(e,n)=(3,55)

3、, p 5,q 11,貝U (n)40，他的秘密密鑰(d,n) = (27,55)。若用戶B向用戶A發(fā)送m=2的加密消息，則該加密后的消息為 _8_。、判斷題1. 可以用克勞夫特不等式作為唯一可譯碼存在的判據(jù)。()2. 線性碼一定包含全零碼。()3. 算術編碼是一種無失真的分組信源編碼，其基本思想是將一定精度數(shù)值作為序列的編碼，是以另外一種形式實現(xiàn)的最佳統(tǒng)計匹配編碼。(X)4. 某一信源，不管它是否輸出符號，只要這些符號具有某些概率特性，就有信息量。(X)5. 離散平穩(wěn)有記憶信源符號序列的平均符號熵隨著序列長度L的增大而增大。(X)6. 限平均功率最大熵定理指出對于相關矩陣一定的隨機矢量X，當

4、它是正態(tài)分布時具有最大熵。()7. 循環(huán)碼的碼集中的任何一個碼字的循環(huán)移位仍是碼字。()8. 信道容量是信道中能夠傳輸?shù)淖钚⌒畔⒘俊?X)9. 香農(nóng)信源編碼方法在進行編碼時不需要預先計算每個碼字的長度。(X)10. 在已知收碼R的條件下找出可能性最大的發(fā)碼Ci作為譯碼估計值，這種譯碼方法叫做最佳譯碼。三、計算題某系統(tǒng)(7, 4)碼C( C6C5C4C3C2C1C0)位與信息位的關系為：C2m3葉mC1m3m2m1c 0m2m1m(1)求對應的生成矩陣和校驗矩陣；(2 )計算該碼的最小距離；(3 )列出可糾差錯圖案和對應的伴隨式;(4)若接收碼字 R=1110011，求發(fā)碼。(m3 m2 m1m

5、C2G Co)其三位校驗100011010 11 1100解：1.0100011GH11 11 0010001011101 11 100100011012.dmin=33.SE000000000000100000010100000010100000010010100010001110010000011010000011010000004. RHT=001E=0000001接收出錯R+E=C = 1110010(發(fā)碼)四、計算題已知X,Y的聯(lián)合概率p x,y為：求 H X ， H Y ， HX,Y，I X;Y解：p(x 0)2/3p(x1)1/ 3XY0101/31/31亠1/3p(y 0)1/

6、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/symbol六、計算題X1X2，每秒鐘發(fā)出2.55個信源符號若有-信源XP0.8 0.2I X;Y H(X) H (Y) H(X,Y) 0.251 bit/symbol五、計算題 一階齊次馬爾可夫信源消息集X a! a2, a3,狀態(tài)集S 3，S2 ,S3，且令Si ai ,i 1,2,3，條件轉(zhuǎn)移概率為1 41 4 1 2P(aj/S)13 13 13，(1)畫出該馬氏鏈的狀態(tài)轉(zhuǎn)移圖；2 3 130(2) 計算信源的極限熵。解：抑2

7、3W3w1打13w21w3W2w10.41 w13w2W3t w20.31W30.3w1w2w3H(X|S1)=H(1/4,1/4,1/2)=1.5 比特/符號H(X|S2)=H(1/3,1/3,1/3)=1.585 比特/符號H(X|S3)=H(2/3,1/3)= 0.918 比特 /符號3wHii 1X|Si0.4 1.5 0.3 1.5850.3 0.918 1.351 比特/符號將此信源的輸出符號送入某一個二元信道中進行傳輸 (假設信道是無噪無損的，容量為1bit/二元符號)，而信道每秒鐘只傳遞 2個二元符號。(1 ) 試問信源不通過編碼(即 xi 0,X2 1在信道中傳輸)(2) 能

8、否直接與信道連接？(3) 若通過適當編碼能否在此信道中進行無失真?zhèn)鬏敚?4) 試構造一種哈夫曼編碼(兩個符號一起編碼)，(5) 使該信源可以在此信道中無失真?zhèn)鬏?。解?不能，此時信源符號通過0, 1在信道中傳輸，2.55二元符號/s2二元符號/s2.55* H(0.8,0.2) = 1.84 1*20X1X1 0.640.64 -11X1X2 0.163.100X2X10.160/匕 0.161101X2X2 0.042.從信息率進行比較，可以進行無失真?zhèn)鬏?0.6401.0.3*此時pKj0.64 0.16*20.2*31.56二元符號/2個信源符號1.56/2*2.55=1.989 二元符

9、號/s H(Y)D . H (Y/X) H(Y)(D)B .在樹枝上安排碼字D .在終端節(jié)點上安排碼字(C)B .非奇異碼是唯一可譯碼D .非奇異碼不是唯一可譯碼(B)B .完備性D .確定性得分評卷人三、名詞解釋(共15分，每題5分)1.奇異碼包含相同的碼字的碼稱為奇異碼。2. 碼距兩個等長碼字之間對應碼元不相同的數(shù)目，稱為碼距。3. 輸出對稱矩陣轉(zhuǎn)移概率矩陣的每一列都是第一列的置換(包含同樣元素)，則該矩陣稱為輸出對稱矩陣。得分評卷人簡答題(共20分，每題10分)1. 簡述信息的特征。答：信息的基本概念在于它的不確定性，任何已確定的事物都不含信息。 接收者在收到信息之前，對它的容是不知道的

10、，所以信息是新知識、新容。 信息是能使認識主體對某一事物的未知性或不確定性減少的有用知識。 信息可以產(chǎn)生，也可以消失，同時信息可以被攜帶、貯存及處理。信息是可以量度的，信息量有多少的差別。2. 簡單介紹哈夫曼編碼的步驟。 將信源消息符號按其出現(xiàn)的概率大小依次排列p(xi) P(X2)p(Xn) 取兩個概率最小的符號分別配以0和1，并將這兩個概率相加作為一個新符號的概率,與未分配碼元的符號重新排隊。 對重排后的兩個概率最小符號重復步驟2的過程。 繼續(xù)上述過程，直到最后兩個符號配以0和1為止。35分）X (0,1)，條件概率為 從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字

11、。得分評卷人四、計算題(共1. 設有一個二進制一階馬爾可夫信源，其信源符號為p(0/0)= p(1/0)=0.5p(1/1)=0.25p(0/1)=0.75W0.5W)0.75WWW 1W00.6W0.42. 設輸入符號與輸出符號為X = Y 0,1,2,3,且輸入符號等概率分布。設失真函數(shù)為漢R Dmin R 0 H Xlog2 4 2bit/ 符號明失真。求 Dmax 和 D min 及 R(Dmax)和 R(Dmin) ( 20 分)解：p X0p冷p X2p x3140111D101111011110失真矩陣的每一行都有0，因此 Dmin=0-111,-111,-1114443Dmax

12、 minp(X)d(Xj,yJJ i 0R Dmax一、填空題1.設信源X包含4個不同離散消息，當且僅當X中各個消息出現(xiàn)的概率為 1/4_時,信源熵達到最大值，為 _2_,此時各個消息的自信息量為_2 _。2如某線性分組碼的最小漢明距dmin=4，則該碼最多能檢測出 3個隨機錯，最多能糾正_1個隨機錯。3克勞夫特不等式是唯一可譯碼存在的充要條件。4平均互信息量l(X;Y)與信源熵和條件熵之間的關系是(X;Y)=H(X)-H(X/Y )_。5._信源_提高通信的有效性，_信道_目的是提高通信的可靠性，_加密_編碼的目的是保證通信的安全性。6信源編碼的目的是提高通信的有效性，信道編碼的目的是提高通

13、信的可靠性加密編碼的目的是保證通信的安全性 。7設信源X包含8個不同離散消息，當且僅當X中各個消息出現(xiàn)的概率為 _1/8時，信源熵達到最大值，為 3。8自信息量表征信源中各個符號的不確定度，信源符號的概率越大，其自信息量越_小_9信源的冗余度來自兩個方面，一是信源符號之間的 _相關性_,二是信源符號分布的不均勻性。10. 最大后驗概率譯碼指的是譯碼器要在已知 r的條件下找出可能性最大的發(fā)碼作為譯碼估值 ，即令 =maxP( |r)。11. 常用的檢糾錯方法有_前向糾錯、反饋重發(fā)和混合糾錯三種。二、單項選擇題1下面表達式中正確的是(Aa.p(yj/xj 1jC.p(Xi, yj) (yj)。b.

14、p(yj/Xi) 1iD.p(x,yj) q(Xi)2.彩色電視顯像管的屏幕上有3. 已知某無記憶三符號信源a,b,c 等概分布，接收端為二符號集，其失真矩陣為 d= 1 121則信源的最大平均失真度Dmax為(D )。A. 1/3B. 2/3C. 3/3D. 4/34. 線性分組碼不具有的性質(zhì)是(C )。A. 任意多個碼字的線性組合仍是碼字B. 最小漢明距離等于最小非0重量C最小漢明距離為 3D.任一碼字和其校驗矩陣的乘積CmHT=05. 率失真函數(shù)的下限為(B)。A .H(U)B.0C(U; V)D.沒有下限6. 糾錯編碼中，下列哪種措施不能減小差錯概率(D )。但不幸被人用外觀相同但重量

15、A. 增大信道容量 B. 增大碼長C. 減小碼率D. 減小帶寬7. 一珍珠養(yǎng)殖場收獲 240 顆外觀及重量完全相同的特大珍珠， 僅有微小差異的假珠換掉 1 顆。一人隨手取出 3 顆，經(jīng)測量恰好找出了假珠， 不巧假珠又滑6 次能找出，結果確是如此，這D. log240bit落進去，那人找了許久卻未找到，但另一人說他用天平最多一事件給出的信息量( A )。A. 0bitB. log6bitC. 6bit8. 下列述中，不正確的是(D )。A. 離散無記憶信道中，H (Y)是輸入概率向量的凸函數(shù)B. 滿足格拉夫特不等式的碼字為惟一可譯碼C. 一般地說，線性碼的最小距離越大，意味著任意碼字間的差別越大

16、，則碼的檢錯、糾錯能力越強D. 滿足格拉夫特不等式的信源是惟一可譯碼9. 一個隨即變量 x 的概率密度函數(shù) P(x)= x /2， 0 x 2V ，則信源的相對熵為( C )。A . 0.5bitB. 0.72bitC. 1bitD. 1.44bit10. 下列離散信源，熵最大的是(D )。A. H (1/3,1/3,1/3)；B. H (1/2,1/2)；11. 下列不屬于消息的是（ B ）。A.文字B.信號C.圖像D. 語言12. 為提高通信系統(tǒng)傳輸消息有效性，信源編碼采用的方法是（A ）。A. 壓縮信源的冗余度B.在信息比特中適當加入冗余比特C.研究碼的生成矩陣D.對多組信息進行交織處理

17、13.最大似然譯碼等價于最大后驗概率譯碼的條件是D ）。B.無錯編碼A. 離散無記憶信道C.無擾信道D .消息先驗等概14. 下列說確的是（C ）。A. 等重碼是線性碼B. 碼的生成矩陣唯一C. 碼的最小漢明距離等于碼的最小非0重量D. 線性分組碼中包含一個全0碼字15. 二進制通信系統(tǒng)使用符號0和 1，由于存在失真， 傳輸時會產(chǎn)生誤碼， 用符號表示下列事件，u0:一個0發(fā)出u1: 個1發(fā)出 v0 :一個0收到 v1: 一個1收到則已知收到的符號，被告知發(fā)出的符號能得到的信息量是（A ）。A. H（U/V）B. H（V/U）C. H（U,V）D. H（UV）16. 同時扔兩個正常的骰子，即各面

18、呈現(xiàn)的概率都是 1/6，若點數(shù)之和為 12，則得到的自信 息為（ B ）。A. log36bitB. log36bitC. log （11/36）bit D. log （11/36）bit17. 下列組合中不屬于即時碼的是（A ）。A. 0， 01， 011B. 0， 10， 110 C. 00， 10， 11D. 1 ， 01， 0011101018. 已知某（ 6， 3）線性分組碼的生成矩陣 G 110001 ，則不用計算就可判斷出下列碼中011101不是該碼集里的碼是（ D ）。A. 000000B. 110001C. 011101D. 11111119一個隨即變量x的概率密度函數(shù) P（

19、x）= x /2，0 x 2V，則信源的相對熵為（ C ）。20設有一個無記憶信源發(fā)出符號A和B，已知p（A）；,p（B） 4，發(fā)出二重符號序列消2息的信源，無記憶信源熵 H（X ）為（A ）。A.0.81bit/ 二重符號B.1.62bit/ 二重符號C.0.93 bit/ 二重符號D .1.86 bit/ 二重符號三、判斷題1確定性信源的熵 H（0,0,0,1）=1。（錯）2信源X的概率分布為P（X）=1/2, 1/3, 1/6，對其進行哈夫曼編碼得到的碼是唯一的。（錯）3離散無記憶序列信源中平均每個符號的符號熵等于單個符號信源的符號熵。（對）4非奇異的定長碼一定是唯一可譯碼。（錯）5信息

20、率失真函數(shù) R（D）是在平均失真不超過給定失真限度D的條件下，信息率容許壓縮的最小值。（對）6信源X的概率分布為 P（X）=1/2, 1/3, 1/6，信源Y的概率分布為 P（Y）=1/3,1/2,1/6，貝U信源X和Y的熵相等。（對）7互信息量l（X;Y）表示收到Y后仍對信源X的不確定度。（對）8對信源符號X=a 1,a2,a3,a4進行二元信源編碼，4個信源符號對應碼字的碼長分別為心=1,K2=2 , K3=3, K3=3，滿足這種碼長組合的碼一定是唯一可譯碼。（錯）1/3 1/3 1/6 1/69.DMC信道轉(zhuǎn)移概率矩陣為 P，則此信道在其輸入端的信源分1/6 1/6 1/3 1/3布為

21、P（X）=1/2,1/2時傳輸?shù)男畔⒘窟_到最大值。（錯）10設 C = 000000, 001011,010110, 011101, 100111, 101100, 110001, 111010是一個二元線性分組碼，則該碼最多能檢測出3個隨機錯誤。（錯）四、名詞解釋1極限熵：2信道容量： 3平均自信息量五、計算題1設離散無記憶信源Xa1 0 a2 1 a3 2 a4 3P(x) 3/81/41/41/8其發(fā)生的消息為(),(1) 根據(jù)“離散無記憶信源發(fā)出的消息序列的自信息等于消息中各個符號的自信息之和”，求此消息的自信息量；(2) 在此消息中平均每個符號攜帶的信息量是多少？Xx1x22已知一個

22、二元信源連接一個二元信道，如圖所示。其中，11。P-2 2試求：l(X,Y) , H(X,Y)，H(X/Y)，和 H(Y/X)。3設輸入信號的概率分布為P=(1/2,1/2)，失真矩陣為d0 1 、。試求 Dmin，D max， R(Dmin)，2 0R(D max)。4信源X共有6個符號消息，其概率分布為P(X)=0.37，0.25，0.18，0.10，0.07，0.03。(1)對這6個符號進行二進制哈夫曼編碼(給出編碼過程)，寫出相應碼字，并求出平均碼長和編碼效率。(2 )哈夫曼編碼的結果是否唯一？如果不唯一，請給出原因。5.二進制通信系統(tǒng)使用符號0和1，由于存在失真，傳輸時會產(chǎn)生誤碼，用

23、符號表示下列事件。X0： 個0發(fā)出；X1： 個1發(fā)出y0 :一個0收到；y1 :一個1收到 給定下列概率：p(x)=1/2， p(y/x0)=3/4， p(y/x1 )=1/2。(1)求信源的熵H(X);(2 )已知發(fā)出的符號，求收到符號后得到的信息量H(Y/X);(3) 已知發(fā)出和收到的符號，求能得到的信息量H(X,Y)。6設DMC信道的傳輸情況如下圖所示。(1)試寫出該信道的轉(zhuǎn)移概率矩陣；(2 )求該信道的信道容量。Y7.設輸入信號的概率分布為P=(1/2,1/2)，失真矩陣為 d0 11/4。試求D min，10 1/4D max， R(D min) , R(Dmax)。P(X) =0.

24、4，0.2，0.2，0.1，8設有離散無記憶信源 X共有5個符號消息，其概率分布為0.1。(1)對這5個符號進行二進制哈夫曼編碼(給出編碼過程)，寫出相應碼字，并求出平均碼長和編碼效率；(2 )哈夫曼編碼的結果是否唯一？如果不唯一，請給出原因。平均自信息為表示信源的平均不確定度，也表示平均每個信源消息所提供的信息量。平均互信息 3MPg)表示從丫獲得的關于每個X的平均信息量，也表示發(fā)X前后丫的平均不確定性減 少的量，還表示通信前后整個系統(tǒng)不確定性減少的量。2、最大離散熵定理為：離散無記憶信源，等概率分布時熵最大。3、最大熵值為卅吸=辰航閥。P4、通信系統(tǒng)模型如下:bills5、用為保證足夠大的

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