信息論與編碼試卷及答案

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

2、道，其信道容量為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è)AI示“大學(xué)生”這一事件，B表示“身高以上”這一事件，則P(A)=p(B)=p(B|A)=(2分)故p(A|B)=p(AB)/p(B)=p(A)p(B|A)/p(B)=*=(2分)I(A|B)=

3、(1分)四、(5)證明：平均互信息量同信息嫡之間滿足I(X;Y)=H(X)+H(Y)-H(XY)證明:pXiyjIX;YpXiyjlogXYpXpxyjlogpXiXYHXHXY同理IX;YHYHYX則HYXHYIX;Y因為HXYHXHYX故HXYHXHYIX;Y即pXiyjlogpXiyjXY（1分）（1分）（2分）IX;YHXHYHXY（1分）五、（18）.黑白氣象傳真圖的消息只有黑色和白色兩種，求：1）黑色出現(xiàn)的概率為，白色出現(xiàn)的概率為。給出這個只有兩個符號的信源上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求嫡HX；X的數(shù)學(xué)模型。假設(shè)圖2）假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為，求其嫡HX3）分別求上

4、述兩種信源的冗余度，比較它們的大小并說明其物理意義。解：1）信源模型為（1分）2）由題意可知該信源為一階馬爾科夫信源。（2分）（4分）得極限狀態(tài)概率（2分）（3分）3）dH（X）110.11910g22dH（X）10.44710g22（1分）（1分）21。說明：當(dāng)信源的符號之間有依賴時，信源輸出消息的不確定性減弱。而信源冗余度正是反映信源符號依賴關(guān)系的強弱，冗余度越大，依賴關(guān)系就越大。六、（18）.信源空間為XX1X2X3X4X5X6X7P（X）0.20.190.180.170.150.10.01（2分）,試分別構(gòu)造二元香農(nóng)碼和二元霍夫曼碼，計算其平均碼長和編碼效率（要求有編碼過程）,、1P（

5、K）-1/21/31/641七（6）.設(shè)有一離散信道，其信道傳遞矩陣為1/61/21/3，并設(shè)p（x2），試分別21/31/61/21P（X3）4按最大后驗概率準(zhǔn)則與最大似然譯碼準(zhǔn)則確定譯碼規(guī)則，并計算相應(yīng)的平均錯誤概率。1） （3分）最小似然譯碼準(zhǔn)則下，有，2） （3分）最大后驗概率準(zhǔn)則下，有，/I（10）.二元對稱信道如圖。.311）若p0p1,求HX、HX|Y和IX;Y；442）求該信道的信道容量。解：1）共6分HX|Y0.749bit/符號2）,（3分）此時輸入概率分布為等概率分布。（1分）九、（18）設(shè)一線性分組碼具有一致監(jiān)督矩陣H0001110110011010111）求此分組碼n

6、=,k=共有多少碼字2）求此分組碼的生成矩陣G3）寫出此分組碼的所有碼字。4）若接收到碼字（101001）,求出伴隨式并給出翻譯結(jié)果。解：1）n=6,k=3,共有8個碼字。（3分）2）設(shè)碼字CC5c4c3c2C1C。由HCT0T得C2CiC。0C4C3C00C5C3C1C00（3分）令監(jiān)督位為C2CiC。，則有C2C1C0C5C5C4C3C4C3（3分）100110010011生成矩陣為001101（2分）3）所有碼字為000000,001101，010011，011110,100110,101011,110101,111000O（4分）4）由STHRT得S101,（2分）該碼字在第5位發(fā)生錯

7、誤，（101001）糾正為（101011）,即譯碼為（101001）（1分）一、填空題（本題10空，每空1分，共10分）1、必然事件的自信息量是0,不可能事件白自信息量是無窮。2、一信源有五種符號a,b,c,d,e,先驗概率分別為Pa=，昨，Pc二，Pd=自二。符號“a”的自信息量為1bit,此信源的燧為符號。3、如某線性分組碼的最小漢明距dmin=6,最多能糾正2個隨機錯。4、根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否相同，可將密碼體制分成對稱（單密鑰）和非對稱（雙密鑰）。5、平均互信息量I（X;Y）與信源燧和條件燧之間的關(guān)系是_I（X:Y）=H（X）-H（X/Y）。6、克勞夫特不等式是唯一

8、可譯碼存在的充要條件。00,01,10,11是否是唯可譯碼是。三、單項選擇題（本題共10小題；每小題2分，共20分）1、對連續(xù)集的燧的描述不正確的是（A）A連續(xù)集的燧和離散集的燧形式一致，只是用概率密度代替概率，用積分代替求和B連續(xù)集的燧值無限大C連續(xù)集的燧由絕對燧和微分燧構(gòu)成D連續(xù)集的燧可以是任意整數(shù)2、設(shè)信道輸入為xm,輸出為y,若譯碼準(zhǔn)則是當(dāng)P（y|xmj）P（y|xm）,對所有m#nn時,將y判為mi,則稱該準(zhǔn)則為（D）A最大后驗概率譯碼準(zhǔn)則B最小錯誤概率準(zhǔn)則C最大相關(guān)譯碼準(zhǔn)則D最大似然譯碼準(zhǔn)則3、線性分組碼不具有的性質(zhì)是（QA任意多個碼字的線性組合仍是碼字B最小漢明距離等于最小非0重

9、量C最小漢明距離為3D任一碼字和其校馬矩陣的乘積cmH=04、關(guān)于伴隨式的描述正確的是（A）A伴隨式s與傳送中信道出現(xiàn)的錯誤圖樣e有關(guān)B通過伴隨式s可以完全確定傳送中信道出現(xiàn)的錯誤圖樣eC伴隨式s與發(fā)送的具體碼字有關(guān)D伴隨式s與發(fā)送的具體碼字有關(guān)，與傳送中信道出現(xiàn)的錯誤圖樣e也有關(guān)5、率失真函數(shù)的下限為（B）AH；U）B0CI（UV）D沒有下限6、糾錯編碼中，下列哪種措施不能減小差錯概率（D）A增大信道容量B增大碼長C減小碼率D減小帶寬7、已知某無記憶三符號信源a,b,c等概分布，接收端為二符號集，其失真矩陣為，則信源的最大平均失真度Dmax為（D）A1/3B2/3C3/3D4/38、一珍珠養(yǎng)

10、殖場收獲240顆外觀及重量完全相同的特大珍珠，但不幸被人用外觀相同但重量僅有微小差異的假珠換掉1顆。一人隨手取出3顆，經(jīng)測量恰好找出了假珠，不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說他用天平最多6次能找出，結(jié)果確是如此，這一事件給出的信息量（A）。A0bitBlog6bitC6bitDlog240bit9、已知隨機噪聲電壓的概率密度函數(shù)p（x）=1/2,x的取值范圍為一1V至+1V,若把噪聲幅度從零開始向正負(fù)幅度兩邊按量化單位為做量化，并且每秒取10個記錄，求該信源的時間嫡（B）AsBsCbit/sD以上都不對10、彩色電視顯像管的屏幕上有5X105個像元，設(shè)每個像元有64種彩色度，

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

12、01101將第3加到第2行10011010100011100111得到線性碼C的系統(tǒng)生成矩陣為10011GS0101000111碼字c(C0,C1,Cn1)的編碼函數(shù)為cf(m)m010011m101010m200111生成了的8個碼字如下信息元系統(tǒng)碼字0000000000100111010010100110110110010011101101001101100111111110最小漢明距離d=2,所以可檢1個錯，但不能糾錯。由GInk,Ak(nk),HAk(nk)T,Ink，得校驗矩陣1111010101(5)消息序列m=000,001,010,011,100,101,110,111,由c=

13、mGs得碼字序列c=00000,c1=00111,C2=01010,c3=01101,C4=10011,c5=10100,ce=11001,c7=11110則譯碼表如下:0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111當(dāng)接收到r=(11101)時，查找碼表發(fā)現(xiàn)它所在的列的子集頭為,所以將它譯為(01101)c=01101。2.

14、設(shè)(7,3)線性碼的生成矩陣如下2.設(shè)(7,3)線性碼的生成矩陣如下G(1)求系統(tǒng)生成矩陣；(2)求校驗矩陣；(3)求最小漢明距離；(4)列出伴隨式表。解：(1)生成矩陣G經(jīng)如下行變換010101001011100110100110001011010101得到系統(tǒng)生成矩陣：Gs(2)由GInk，Ak(nk)，HAk(nk)010101000101111001101010011011交換第1、3行001011110101010110011011交換第2、3行010101000010111100110101010100010111,Ink,得校驗矩陣為11010001010100H01100101

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

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

17、101100H011010110001(2)消息城(m,m,m)=(101),則碼字c為:cf(m)100101001110101011(3)收到碼字r=(101010),則伴隨式101011T110rH101010g001100010001又(6,3)線性碼的消息序列m=000,001,010,011,100,101,110,111,由c=mGs得碼字序列：c0=000000,c=001110,C2=010011,C3=011101,C4=100101,C5=101011,C6=110110,C7=111000。伴隨式有23=8種情況，則計算伴隨式得到伴隨表如下:伴隨式(001)對應(yīng)陪集首為

18、(000001),而C=r+e,則由收到的碼字r=(101010),最有可能發(fā)送的碼字c為:伴隨式陪集首000000000101100000011010000110001000100000100010000010001000001111100010C=(101011)4.設(shè)(6,3)線性碼的信息元序列為X1X2X3,它滿足如下監(jiān)督方程組X1x2x40X2X3X50XiX3X60(1)求校驗矩陣，并校驗10110是否為一個碼字；(2)求生成矩陣，并由信息碼元序列101生成一個碼字。解：(1)由監(jiān)督方程直接得監(jiān)督矩陣即校驗矩陣為:110100H011010101001因為收到的序列10110為5位

19、，而由(6,3)線性碼生成的碼字為6位，所以10110不是碼字。(2)由GInk,Ak(nk),HAk(nk)T,Ink，則生成矩陣為:10010G0101100101信息碼元序列M=(101),由c=mGs得碼字為c：cm0100101m1010110第8章循環(huán)碼1.已知(8,5)線性分組碼的生成矩陣為1111000100010010Gs1m2001011101110G(1)證明該碼是循環(huán)碼；(2)求該碼的生成多項式(1)證明如下：010001000100011110000g(x)。0000111110000100010000100010000100010111000011111000001

20、111000001111000010001011100001111100000111100001000100001000101110000111110000011110000011110000011110111000011111000001111000001111000001111000001111由生成矩陣可知為(8、5)循環(huán)碼。(2)生成多項式如下：32.g(x)xxx12 .證明：x10x8x5x4x2x1為(15,5)循環(huán)碼的生成多項式，并寫出信息多項式為、4.一一4一.一一.、一m(x)xx1時的碼多項式(按系統(tǒng)碼的形式)。由定理8-1可知(n,k)循環(huán)碼的生成多項式g(x)為xn+

21、1的因子，g(x)為n-k次多項式，本題目中知：g(x)x10x8x5x4x2x1為一個10次多項式，n-k=15-5=1015108542并且：(x1)mod(xxxxxx1)0所以：x10x8x5x4x2x1是x1的一個因子，也是循環(huán)碼的生成多項式。按系統(tǒng)碼構(gòu)造多項式如下：如下:時鐘信息兀寄存器碼字輸出碼字D0DiD20000111101200110301110410111500116000170000m(x)b(x)8xnk/410x(xx1)x(m(x)xnk)mod(x1076xxx14x8x1110x4x1)c(x)nk14m(x)xb(x)x11x10x3.已知(7,4)循環(huán)碼的

22、生成多項式為g(x)3x1,信息多項式為m(x)x1,分別由編碼電路和代數(shù)計算求其相應(yīng)的碼多項式由題目可知代數(shù)計算求解過程如下：C(x)om(x)m(x)b(x)3x1nk63xxx(m(x)xnk)mod(x3c(x)m(x)xnkb(x)x1)3x2xx2xxc(1001110)由編碼電路進(jìn)行求解:編碼電路如下所示：編碼過程可得：c(x)x6x3x2x4.令(15,11)循環(huán)碼的生成多項式為g(x)x4x1,計算(1)若信息多項式為m(x)x10x81,試求編碼后的系統(tǒng)碼字;(2)求接收碼組R(x)X14X4x1的校正子多項式。(1)解題過程如下：108m(x)xx1nk414124m(x)xm(x)xxxxb(x)(m(x)xnk)mod(x4x1)x21nk141242c(x)m(x)xb(x)xxxx1c(1010000000010101)(2)校正多項式如下所示：S(x)R(x)g(x)14x4x11-mod(g(x)5.碼長為n=15的本原BC削，求不同糾錯能力下的BC削各自的生成多項式g(x)n2m115m4糾錯能力：t2m18,所以最多能糾正7個錯誤碼。有限域GF(24),4次本原多項式f(x)x4