信息論與編碼試卷及答案解析

.PAGE一、（11’）填空題1948年，美國數(shù)學(xué)家香農(nóng)發(fā)表了題為“通信的數(shù)學(xué)理論”的長篇論文，從而創(chuàng)立了信息論。必然事件的自信息是0。離散平穩(wěn)無記憶信源X的N次擴(kuò)展信源的熵等于離散信源X的熵的N倍。對于離散無記憶信源，當(dāng)信源熵有最大值時，滿足條件為__信源符號等概分布_。若一離散無記憶信源的信源熵H（X）等于2.5，對信源進(jìn)行等長的無失真二進(jìn)制編碼，則編碼長度至少為3。對于香農(nóng)編碼、費(fèi)諾編碼和霍夫曼編碼，編碼方法惟一的是香農(nóng)編碼。已知某線性分組碼的最小漢明距離為3，那么這組碼最多能檢測出_2_______個碼元錯誤，最多能糾正___1__個碼元錯誤。設(shè)有一離散無記憶平穩(wěn)信道，其信道容量為C，只要待傳送的信息傳輸率R__小于___C（大于、小于或者等于），則存在一種編碼，當(dāng)輸入序列長度n足夠大，使譯碼錯誤概率任意小。平均錯誤概率不僅與信道本身的統(tǒng)計特性有關(guān)，還與___譯碼規(guī)則____________和___編碼方法___有關(guān)（5）居住在某地區(qū)的女孩中有25%是大學(xué)生，在女大學(xué)生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占總數(shù)的一半。假如我們得知“身高1.6米以上的某女孩是大學(xué)生”的消息，問獲得多少信息量？解：設(shè)A表示“大學(xué)生”這一事件，B表示“身高1.60以上”這一事件，則P(A)=0.25p(B)=0.5p(B|A)=0.75（2分）故p(A|B)=p(AB)/p(B)=p(A)p(B|A)/p(B)=0.75*0.25/0.5=0.375（2分）I(A|B)=-log0.375=1.42bit（1分）四、（5）證明：平均互信息量同信息熵之間滿足I(X;Y)=H(X)+H(Y)-H(XY)證明：（2分）同理（1分）則因為（1分）故即（1分）五、（18’）.黑白氣象傳真圖的消息只有黑色和白色兩種，求：1）黑色出現(xiàn)的概率為0.3，白色出現(xiàn)的概率為0.7。給出這個只有兩個符號的信源X的數(shù)學(xué)模型。假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵；2）假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為，，，，求其熵。3）分別求上述兩種信源的冗余度，比較它們的大小并說明其物理意義。解：1）信源模型為（1分）2）由題意可知該信源為一階馬爾科夫信源。（2分）

由（4分）得極限狀態(tài)概率（2分）（3分）3）（1分）（1分）。說明：當(dāng)信源的符號之間有依賴時，信源輸出消息的不確定性減弱。而信源冗余度正是反映信源符號依賴關(guān)系的強(qiáng)弱，冗余度越大，依賴關(guān)系就越大。（2分）六、（18’）.信源空間為，試分別構(gòu)造二元香農(nóng)碼和二元霍夫曼碼，計算其平均碼長和編碼效率（要求有編碼過程）。七（6’）.設(shè)有一離散信道，其信道傳遞矩陣為，并設(shè)，試分別按最大后驗概率準(zhǔn)則與最大似然譯碼準(zhǔn)則確定譯碼規(guī)則，并計算相應(yīng)的平均錯誤概率。1）（3分）最小似然譯碼準(zhǔn)則下，有，2）（3分）最大后驗概率準(zhǔn)則下，有，

八（10）.二元對稱信道如圖。1）若，，求、和；

2）求該信道的信道容量。解：1）共6分

2），（3分）此時輸入概率分布為等概率分布。（1分）九、（18）設(shè)一線性分組碼具有一致監(jiān)督矩陣1）求此分組碼n=?,k=?共有多少碼字？2）求此分組碼的生成矩陣G。3）寫出此分組碼的所有碼字。4）若接收到碼字（101001），求出伴隨式并給出翻譯結(jié)果。解：1）n=6,k=3,共有8個碼字。（3分）2）設(shè)碼字由得（3分）令監(jiān)督位為，則有（3分）生成矩陣為（2分）3）所有碼字為000000，001101，010011，011110，100110，101011，110101，111000。（4分）4）由得，（2分）該碼字在第5位發(fā)生錯誤，（101001）糾正為（101011），即譯碼為（101001）（1分）一、填空題（本題10空,每空1分,共10分）1、必然事件的自信息量是____0____，不可能事件的自信息量是___無窮______。2、一信源有五種符號{a，b，c，d，e}，先驗概率分別為Pa=0.5，Pb=0.25，Pc=0.125，Pd=Pe=0.0625。符號“a”的自信息量為___1_____bit，此信源的熵為__1.875______bit/符號。3、如某線性分組碼的最小漢明距dmin=6，最多能糾正___2___個隨機(jī)錯。4、根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否相同，可將密碼體制分成___對稱（單密鑰）_____和___非對稱（雙密鑰）____。5、平均互信息量I(X;Y)與信源熵和條件熵之間的關(guān)系是__I(X:Y)=H(X)-H(X/Y)______。6、克勞夫特不等式是唯一可譯碼__存在_______的充要條件。{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|xm’)≥P(y|xm)，對所有m≠m’時，將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ā)送的具體碼字有關(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）A1/3B2/3C3/3D4/38、一珍珠養(yǎng)殖場收獲240顆外觀及重量完全相同的特大珍珠，但不幸被人用外觀相同但重量僅有微小差異的假珠換掉1顆。一人隨手取出3顆，經(jīng)測量恰好找出了假珠，不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說他用天平最多6次能找出，結(jié)果確是如此，這一事件給出的信息量（A）。A0bitBlog6bitC6bitDlog240bit9、已知隨機(jī)噪聲電壓的概率密度函數(shù)p(x)=1/2，x的取值范圍為－1V至+1V，若把噪聲幅度從零開始向正負(fù)幅度兩邊按量化單位為0.1V做量化，并且每秒取10個記錄，求該信源的時間熵（B）A21.61bit/sB43.22bit/sC86.44bit/sD以上都不對10、彩色電視顯像管的屏幕上有5×105個像元，設(shè)每個像元有64種彩色度，每種彩度又有16種不同的亮度層次，如果所有的彩色品種和亮度層次的組合均以等概率出現(xiàn)，并且各個組合之間相互獨(dú)立。每秒傳送25幀圖像所需要的信道容量（C）A50.106B75.106C125.106D250.106第7章線性分組碼1.已知一個(5,3)線性碼C的生成矩陣為：（1）求系統(tǒng)生成矩陣；（2）列出C的信息位與系統(tǒng)碼字的映射關(guān)系；（3）求其最小Hamming距離，并說明其檢錯、糾錯能力；（4）求校驗矩陣H；（5）列出譯碼表，求收到r=11101時的譯碼步驟與譯碼結(jié)果。解：（1）線性碼C的生成矩陣經(jīng)如下行變換：得到線性碼C的系統(tǒng)生成矩陣為（2）碼字的編碼函數(shù)為生成了的8個碼字如下信息元系統(tǒng)碼字0000000000100111010010100110110110010011101101001101100111111110(3)最小漢明距離d=2，所以可檢1個錯，但不能糾錯。(4)由，得校驗矩陣(5)消息序列m=000,001,010,011,100,101,110,111，由c=mGs得碼字序列c0=00000,c1=00111,c2=01010,c3=01101,c4=10011,c5=10100,c6=11001,c7=11110則譯碼表如下：0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111當(dāng)接收到r=(11101)時，查找碼表發(fā)現(xiàn)它所在的列的子集頭為(01101)，所以將它譯為c=01101。2．設(shè)（7,3）線性碼的生成矩陣如下（1）求系統(tǒng)生成矩陣；（2）求校驗矩陣；（3）求最小漢明距離；（4）列出伴隨式表。解：（1）生成矩陣G經(jīng)如下行變換得到系統(tǒng)生成矩陣：（2）由，得校驗矩陣為（3）由于校驗矩陣H的任意兩列線性無關(guān)，3列則線性相關(guān)，所以最小漢明距離d=3。（4）（7,3）線性碼的消息序列m=000,001,010,011,100,101,110,111，由c=mGs得碼字序列：c0=0000000，c1=0010111，c2=0101010，c3=0111101，c4=1001101，c5=1011010，c6=1100111，c7=1110000。又因伴隨式有24=16種組合，差錯圖樣為1的有，差錯圖樣為2的有，而由，則計算陪集首的伴隨式，構(gòu)造伴隨表如下：伴隨式陪集首伴隨式陪集首000000000000101100100011011000000100110001001010010000011110011000011100100001100000110010000001000111001001000100000010010110100001001000000100011001010000010000001011000001103．已知一個(6,3)線性碼C的生成矩陣為：（1）寫出它所對應(yīng)的監(jiān)督矩陣H；（2）求消息M=(101)的碼字；（3）若收到碼字為101010，計算伴隨式，并求最有可能的發(fā)送碼字。解：（1）線性碼C的生成矩陣G就是其系統(tǒng)生成矩陣GS，所以其監(jiān)督矩陣H直接得出：（2）消息M=(m0,m1,m2)=(101)，則碼字c為：（3）收到碼字r=(101010)，則伴隨式又（6,3）線性碼的消息序列m=000,001,010,011,100,101,110,111，由c=mGs得碼字序列：c0=000000，c1=001110，c2=010011，c3=011101，c4=100101，c5=101011，c6=110110，c7=111000。伴隨式有23=8種情況，則計算伴隨式得到伴隨表如下：伴隨式陪集首000000000101100000011010000110001000100000100010000010001000001111100010伴隨式（001）對應(yīng)陪集首為（000001），而c=r+e，則由收到的碼字r=(101010)，最有可能發(fā)送的碼字c為：c=（101011）。4．設(shè)(6,3)線性碼的信息元序列為x1x2x3，它滿足如下監(jiān)督方程組（1）求校驗矩陣，并校驗10110是否為一個碼字；（2）求生成矩陣，并由信息碼元序列101生成一個碼字。解：（1）由監(jiān)督方程直接得監(jiān)督矩陣即校驗矩陣為：因為收到的序列10110為5位，而由（6,3）線性碼生成的碼字為6位，所以10110不是碼字。（2）由，則生成矩陣為：信息碼元序列M=（101），由c=mGs得碼字為c：第8章循環(huán)碼1.已知(8,5)線性分組碼的生成矩陣為（1）證明該碼是循環(huán)碼；（2）求該碼的生成多項式。（1）證明如下：由生成矩陣可知為（8、5）循環(huán)碼。（2）生成多項式如下：2.證明：為(15,5)循環(huán)碼的生成多項式，并寫出信息多項式為時的碼多項式（按系統(tǒng)碼的形式）。由定理8-1可知（n，k）循環(huán)碼的生成多項式g(x)為xn+1的因子，g(x)為n-k次多項式，本題目中知：為一個10次多項式，n-k=15-5=10并且：所以：是的一個因子，也是循環(huán)碼的生成多項式。按系統(tǒng)碼構(gòu)造多項式如下：3.已知(7,4)循環(huán)碼的生成多項式為，信息多項式為，分別由編碼電路和代數(shù)計