信息論與編碼試卷及答案

1、一、（11'）填空題（1）1948年，美國數(shù)學(xué)家香農(nóng) 發(fā)表了題為"通信的數(shù)學(xué)理論”的長篇論文，從而創(chuàng)立了信息論。（2）必然事件的自信息是0。（3）離散平穩(wěn)無記憶信源 X的N次擴展信源的熵等于離散信源X的熵的N倍。（4）對于離散無記憶信源，當(dāng)信源熵有最大值時，滿足條件為_-信源符號等概分布_。（5）若一離散無記憶信源的信源熵H（X等于，對信源進行等長的無失真二進制編碼，則編碼長度至少為_3。（6）對于香農(nóng)編碼、費諾編碼和霍夫曼編碼，編碼方法惟一的是香農(nóng)編碼。（7）已知某線性分組碼的最小漢明距離為3 ,那么這組碼最多能檢測出丄個碼元錯誤，最多能糾正1_個碼元錯誤。（8）設(shè)有一離散

2、無記憶平穩(wěn)信道，其信道容量為C,只要待傳送的信息傳輸率R小于 _ C（大于、小于或者等于），則存在一種編碼，當(dāng)輸入序列長度n足夠大，使譯碼錯誤概率任意小。（9）平均錯誤概率不僅與信道本身的統(tǒng)計特性有關(guān)，還與譯碼規(guī)則和 _編碼方法有關(guān)三、（5 ）居住在某地區(qū)的女孩中有25%是大學(xué)生，在女大學(xué)生中有75%是身高米以上的，而女孩中身高米以上的占總數(shù)的一半。假如我們得知“身高 1.6米以上的某女孩是大學(xué)生”的消息，問獲得多少信息量解：設(shè)A表示“大學(xué)生”這一事件，B表示“身高以上”這一事件，則P（A）= P（B）= P（BIA）=（ 2分）故 P（AlB）=P（AB）p（B）=p（A）p（BA）p（B）

3、=*=（ 2分）I(AlB)=(1分)四、（5）證明：平均互信息量同信息熵之間滿足I(X; Y)=H(X)+H (Y )-H(X Y) 證明:P Xi yjI X;YP Xiyj logX YP XPXyjlog P XiX YH X H XY同理I X;Y H Y HYX則HYX H Y I X;Y因為H XY H X HYX故H XY H X H Y I X;Y即I X;Y H X H Y H XYP Xi yj log PXiyj（2分）X Y（1 分）（1分）（1 分）五、（18'）.黑白氣象傳真圖的消息只有黑色和白色兩種，求：1） 黑色出現(xiàn)的概率為，白色出現(xiàn)的概率為。給出這個

4、只有兩個符號的信源X的數(shù)學(xué)模型。假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵H X ；2） 假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為，求其熵H X 。3）分別求上述兩種信源的冗余度，比較它們的大小并說明其物理意義。解：1）信源模型為（1分）2）由題意可知該信源為一階馬爾科夫信源。（2分）得極限狀態(tài)概率3）H（X）log2 20.119（4分）（2 分）（3分）H （X）0.447log2 2（1 分）（1 分）21。說明：當(dāng)信源的符號之間有依賴時，信源輸出消息的不確定性減弱。而信源冗余度正是反映信源符號依賴關(guān)系的強弱，冗余度越大，依賴關(guān)系就越大。（2分）六、（18' ） 信源空間為P（X）X

5、X2×3X4X5X5X70.2 0.19 0.18 0.170.15 0.10.01,試分別構(gòu)造二元香農(nóng)碼和二元霍夫曼碼，計算其平均碼長和編碼效率（要求有編碼過程）1/21/31/6P(X)411 ,試分別214七 （6 ）.設(shè)有一離散信道，其信道傳遞矩陣為1/61/21/3 ,并設(shè)P（X2）1/31/61/2P(X3)按最大后驗概率準(zhǔn)則與最大似然譯碼準(zhǔn)則確定譯碼規(guī)則，并計算相應(yīng)的平均錯誤概率。1）（ 3分）最小似然譯碼準(zhǔn)則下，有，2）（ 3分）最大后驗概率準(zhǔn)則下，有，八（10）二元對稱信道如圖。3 11）若 P 0-， P 1,求 HX、HXlY 和 IX;Y ；4 42）求該信道

6、的信道容量。解：1）共6分H X |Y 0.749bit/符號2），（ 3分）此時輸入概率分布為等概率分布。（1分）000111九、（18）設(shè)一線性分組碼具有一致監(jiān)督矩陣H0110011010111）求此分組碼n=,k=共有多少碼字2） 求此分組碼的生成矩陣G3）寫出此分組碼的所有碼字。4）若接收到碼字（101001）,求出伴隨式并給出翻譯結(jié)果。2）設(shè)碼字 CC5C4C3C2C1C0 由 HC TC2C1C0 0C4C3C0 0C5C3C1C0 0令監(jiān)督位為C2C1C0，則有C2C5C3C1C5C4C0C4C3100110010011生成矩陣為001101解： 1）n=6,k=3, 共有8個碼

7、字。（ 3分）3）所有碼字為 000000， 001101，010011T0得3分）3分）（2分）011110，100110，101011，110101，111000。（4分）4）由 ST HRT 得S 101 ，（2分）該碼字在第 5位發(fā)生錯誤，（ 101001）糾正為（ 101011），即譯碼為 （ 101001）1分）一、填空題（本題 10空, 每空1分, 共10分） 1、必然事件的自信息量是 0，不可能事件的自信息量是 _無窮 。2、一信源有五種符號a , b, c, d, e,先驗概率分別為Pa=, R=, Pc=, Pd=Fb=O符號“ a”的自信息量為 _1bit ，此信源的熵為

8、符號。3、如某線性分組碼的最小漢明距 dmin=6 ,最多能糾正 2_個隨機錯。4、 根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否相同,可將密碼體制分成_對稱（單密鑰） 和_非對稱（雙密鑰） O5、 平均互信息量 I（X;Y） 與信源熵和條件熵之間的關(guān)系是 _I（X:Y）=H（X）-H（X/Y） O6、 克勞夫特不等式是唯一可譯碼 存在的充要條件。00 , 01, 10, 11是否是唯一可譯碼 _是O三、單項選擇題 （本題共 10小題；每小題 2分，共 20分） 1、對連續(xù)集的熵的描述不正確的是（A）A連續(xù)集的熵和離散集的熵形式一致，只是用概率密度代替概率，用積分代替求和B連續(xù)集的熵值無限大C

9、連續(xù)集的熵由絕對熵和微分熵構(gòu)成D 連續(xù)集的熵可以是任意整數(shù)2、設(shè)信道輸入為Xm,輸出為y,若譯碼準(zhǔn)則是當(dāng)P（y | Xm） Fty | Xm）,對所有mm時, 將y判為m ,則稱該準(zhǔn)則為（D）A 最大后驗概率譯碼準(zhǔn)則 B 最小錯誤概率準(zhǔn)則C 最大相關(guān)譯碼準(zhǔn)則 D 最大似然譯碼準(zhǔn)則3、線性分組碼不具有的性質(zhì)是（ C）A 任意多個碼字的線性組合仍是碼字B 最小漢明距離等于最小非 0重量C 最小漢明距離為 3D 任一碼字和其校驗矩陣的乘積 cmHT=04、關(guān)于伴隨式的描述正確的是（ A）A伴隨式S與傳送中信道出現(xiàn)的錯誤圖樣e有關(guān)B通過伴隨式S可以完全確定傳送中信道出現(xiàn)的錯誤圖樣 eC伴隨式S與發(fā)送的

10、具體碼字有關(guān)D伴隨式S與發(fā)送的具體碼字有關(guān)，與傳送中信道出現(xiàn)的錯誤圖樣 e也有關(guān)5、率失真函數(shù)的下限為（ B）AH（U）B0CI （U; V）D 沒有下限6、糾錯編碼中,下列哪種措施不能減小差錯概率（ D）A 增大信道容量 B 增大碼長 C 減小碼率 D 減小帶寬7、已知某無記憶三符號信源 a,b,c 等概分布,接收端為二符號集,其失真矩陣為 , 則信源的最大平均失真度 DmaX 為（ D）A 1/3 B 2/3 C 3/3 D 4/38、一珍珠養(yǎng)殖場收獲 240 顆外觀及重量完全相同的特大珍珠,但不幸被人用外觀相同但重量僅有 微小差異的假珠換掉 1 顆。一人隨手取出 3 顆,經(jīng)測量恰好找出了

11、假珠,不巧假珠又滑落進去, 那人找了許久卻未找到,但另一人說他用天平最多 6 次能找出,結(jié)果確是如此,這一事件給出的 信息量（ A ）。A 0bit B log6bit C 6bit D log240bit9、已知隨機噪聲電壓的概率密度函數(shù) P（X） =1/2, X的取值范圍為一1V至+1V,若把噪聲幅度從零開始向正負幅度兩邊按量化單位為 做量化，并且每秒取 10 個記錄，求該信源的時間熵（ B ） A S B S C bit /S D以上都不對10、彩色電視顯像管的屏幕上有 5×105 個像元，設(shè)每個像元有 64 種彩色度，每種彩度又有 16 種不同的亮度層次，如果所有的彩色品種和

12、亮度層次的組合均以等概率出現(xiàn)，并且各個組合之 間相互獨立。每秒傳送 25 幀圖像所需要的信道容量（ C ）A B 75.106 C D第 7 章 線性分組碼1.已知一個（5, 3）線性碼C的生成矩陣為：11001G0110100111（1）求系統(tǒng)生成矩陣；（2）列出C的信息位與系統(tǒng)碼字的映射關(guān)系；（3）求其最小Hamming距離，并說明其檢錯、糾錯能力；（4）求校驗矩陣H；（5）列岀譯碼表，求收到 r=11101時的譯碼步驟與譯碼結(jié)果。解：（1）線性碼C的生成矩陣經(jīng)如下行變換：110011001101101將第2、3加到第1行011010011100111100111001101101將第勸卩

13、到第2行010100011100111得到線性碼C的系統(tǒng)生成矩陣為10011GS0101000111(2)碼字C (C,Cl, ,Cn 1)的編碼函數(shù)為C f (m) m0 1 0 0 1 1 m1 0 1 0 1 0 m2 0 0 1 1 1生成了的8個碼字如下信息元系統(tǒng)碼字000Ooooo00100111010010100110110110010011101101001101100111111110（3）最小漢明距離d=2 ,所以可檢1個錯，但不能糾錯11110H10 10 1(5)消息序列 m=000,001,010,011,100,101,110,111,由 c=mGs得碼字序列Co=

14、OOOOO, C1=00111,C2=01010, C3=01101,C4=10011, C5=10100, C6=11001, C7=11110則譯碼表如下:0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111當(dāng)接收到r =(11101)時，查找碼表發(fā)現(xiàn)它所在的列的子集頭為(01101),所以將它譯為C=011012設(shè)(7, 3

15、 )線性碼的生成矩陣如下010101 0G001011 1100110 1(1)求系統(tǒng)生成矩陣；(2)求校驗矩陣；(3)求最小漢明距離；(4)列岀伴隨式表。解：(1)生成矩陣G經(jīng)如下行變換0 10 10 1010 0 110 100101110010111100110101010101001101100110100101 1101010 1001010 1000101 11得到系統(tǒng)生成矩陣:1001101GS01010100010111(2)由 G In k,Ak(n k),HAk (n k),n k,得校驗矩陣為110 10 0 010 10 10 0 H0 110 0 101 0 1 0

16、0 0 1(3) 由于校驗矩陣 H的任意兩列線性無關(guān)，3列則線性相關(guān)，所以最小漢明距離d=3。(4) (7, 3)線性碼的消息序列 m=000,001,010,011,100,101,110,111,由 c=mGs得碼字序列：CO=Ooooooo,g=0010111，C2=0101010, C3=0111101，0=1001101, C5=1011010，©=1100111，C7=1110000。又因伴隨式有 24=16種組合，差錯圖7樣為1的有177種，差錯圖樣為2的有221種，而由HrTHeT ,則計算陪集首的伴隨式，構(gòu)造伴隨表如下:伴隨式陪集首伴隨式陪集首00000000000

17、0101100100011011000000100110001001010010000011110011000011100100001100000110010000001000111001001000100000010010110100001001000000100011001010000010000001011000001103.已知一個(6, 3)線性碼C的生成矩陣為:100101G010011001110(1)寫岀它所對應(yīng)的監(jiān)督矩陣 H;(2)求消息M=(101)的碼字；(3)若收到碼字為101010 ,計算伴隨式，并求最有可能的發(fā)送碼字。解：(1)線性碼C的生成矩陣G就是其系統(tǒng)生成矩陣

18、 G,所以其監(jiān)督矩陣 H直接得岀:10 110 0H 0110101 1 0 0 0 1(2)消息 MKm, m, m)=(101),則碼字 C 為:Cf(m) 10 0 10 1 0 011 1010 10 11(3)收到碼字r=(101010),則伴隨式101011110rH101010 g001100010001又(6, 3)線性碼的消息序列m=000,001,010,011,100,101,110,111,由C=mGs得碼字序列：6=000000,C=001110,C2=010011,C3=011101 ,C4=100101,C5=101011,C6=110110,C7=111000o

19、伴隨式有23=8種情況，則計算伴隨式得到伴隨表如下：伴隨式陪集首000000000101100000011010000110001000100000100010000010001000001111100010伴隨式(001)對應(yīng)陪集首為(000001),而C=葉e,則由收到的碼字r=(101010),最有可能發(fā)送的碼字 C為:C= (101011)。4 設(shè)(6, 3)線性碼的信息元序列為X1 X2X3, 它滿足如下監(jiān)督方程組X1X2X40X2X3X50X1X3X60(1) 求校驗矩陣，并校驗 10110是否為一個碼字；(2) 求生成矩陣，并由信息碼元序列101生成一個碼字解：(1)由監(jiān)督方程直

20、接得監(jiān)督矩陣即校驗矩陣為:110100H011010101001因為收到的序列10110 為 5位，而由（ 6, 3 ）線性碼生成的碼字為6 位，所以 10110 不是碼字由 G I n k ,Ak (n k) ,H Ak (n k) ,I n k，則生成矩陣為：100101G 0 10110GS001011信息碼元序列M= (101),由c=mGs得碼字為Cc m0 100101 m1 010110 m2 001011 101110第 8 章 循環(huán)碼1. 已知（8, 5） 線性分組碼的生成矩陣為1111000010001000G0100010000100010111000011)證明該碼是循

21、環(huán)碼；2)求該碼的生成多項式g(x)。1）證明如下：1 1 1 1 0 0 0 01 1 1 1 0 0 0 01 0 0 0 1 0 0 00 1 1 1 1 0 0 00 1 0 0 0 1 0 0(1) (2) 0 1 0 0 0 1 0 00 0 1 0 0 0 1 00 0 1 0 0 0 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 11 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 0 0 00 1 1 1 1 0 0 00 0 1 1 1 1 0 0(3) (4) 0 0 1 1 1 1 0 00 0 1 0 0 0 1 00 0

22、 0 1 1 1 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 11 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 0 0 00 1 1 1 1 0 0 00 0 1 1 1 1 0 0(4) (5) 0 0 1 1 1 1 0 00 0 0 1 1 1 1 00 0 0 1 1 1 1 00 0 0 1 0 0 0 10 0 0 0 1 1 1 1由生成矩陣可知為( 8、 5)循環(huán)碼。 (2)生成多項式如下：(2) (3)(1) (5)g(x) x3 x2 x 12. 證明： x10 x8 x5 x4 x2 x 1為(15, 5) 循環(huán)碼的生成

23、多項式，并寫出信息多項式為4m(x) x4 x 1 時的碼多項式(按系統(tǒng)碼的形式) 。由定理 8-1 可知( n， k )循環(huán)碼的生成多項式 g(x) 為 xn+1 的因子， g(x) 為 n-k 次多項式，本題目4 nEAQ中知： g(x) x10x8x5x4x2x 1為一個 10 次多項式， n-k=15-5=1015 10 8 5 4 2并且： (x 1) mod( x x x x x x 1) 0所以： x10 x8 x5 x4 x2 x 1 是 x15 1 的一個因子，也是循環(huán)碼的生成多項式。 按系統(tǒng)碼構(gòu)造多項式如下：m(x) x4 x 1m(x)n k4X(X10141110X 1

24、) XXXXb(x)(m(x) Xn k108542)mod(xXXXXX1)876XXXXC(X)n km(x) X14111087b(x) XXXXX6XX333.已知(7, 4)循環(huán)碼的生成多項式為 g(x) X X 1 ,信息多項式為m(x) X1 ,分別由編碼電路和代數(shù)計算求其相應(yīng)的碼多項式C(X)。由題目可知代數(shù)計算求解過程如下：m(x) X31n k 63m(x) X X Xb(X) (m(X) Xn k)mod(X3 X 1) X2 XC(X) m(x) Xn k b(x) X6 X3 X2 XC (1001110)由編碼電路進行求解: 編碼電路如下所示：編碼過程如下:時鐘信息

25、元寄存器碼字輸出碼字D) D1 D200 0 0111 1 01200 1 10301 1 10410 1 1150 0 1160 0 0170 0 00可得：C(X) X6 X3 X2 X4.令(15, 11)循環(huán)碼的生成多項式為g(x) X4 X 1 ,計算(1)若信息多項式為 m(x)10X1,試求編碼后的系統(tǒng)碼字;(2)求接收碼組R(X) X14X41的校正子多項式。(1) 解題過程如下:m(x)m(x)b(x)10 8 X X 1Xn k m(x)(m(x) Xn k) mod(xn km(x) X b(x) X414X X412 XC(X)C (1010000000010101)X

26、141)12X2X4X(2) 校正多項式如下所示:S(X)R(X)g(x)X144XX4X 1X 13mod(g(x) X 15.碼長為n=15的本原BCH碼，求不同糾錯能力下的BCH碼各自的生成多項式 g(x)。n 2m 115 m 4糾錯能力：t 2m 18 ,所以最多能糾正 7個錯誤碼。有限域GF( 24)，4次本原多項式f() X4 X 1，%為f(x)的一個根，可知:10,計算 2t=14個連續(xù)幕次為對應(yīng)的最小多項式：m()4 XX 1,m2(x) X4X 1,m3(x)432XXXX1m4(x)4 XX 1,m5 (x) X2X 1,ms()432XXXX1m7(x)4 X3X 1,m8() X4 X 1,m9()4X X 1m°()2 XX 1,m11()432XXXX 1m2()4