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

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)信源熵有最大值時(shí)，滿足條件為_信源符號等概分布_。（5） 若一離散無記憶信源的信源熵H（X）等于2.5，對信源進(jìn)行等長的無失真二進(jìn)制編碼，則編碼長度至少為 3 。（6） 對于香農(nóng)編碼、費(fèi)諾編碼和霍夫曼編碼，編碼方法惟一的是 香農(nóng)編碼 。（7） 已知某線性分組碼的最小漢明距離為3，那么這組碼最多能檢測出_2_個(gè)碼元錯(cuò)誤，最多能糾正_1_個(gè)碼元

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

3、5 （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分）則 因?yàn)?（1分）故即 （1分）五、（18）.黑白氣象傳真圖的消息只有黑色和白色兩種，求：1） 黑色出現(xiàn)的概率為0.3，白色出現(xiàn)的概率為0.7。給出這個(gè)只有兩個(gè)符號的信源X的數(shù)學(xué)模型。假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵；2） 假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為 ，求其熵。3）分別

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

5、小似然譯碼準(zhǔn)則下，有， 2）（3分）最大后驗(yàn)概率準(zhǔn)則下，有，八（10）.二元對稱信道如圖。1）若，求、和； 2）求該信道的信道容量。 解：1）共6分 2）， （3分）此時(shí)輸入概率分布為等概率分布。（1分）九、（18）設(shè)一線性分組碼具有一致監(jiān)督矩陣1）求此分組碼n=?,k=?共有多少碼字？2）求此分組碼的生成矩陣G。3）寫出此分組碼的所有碼字。4）若接收到碼字（），求出伴隨式并給出翻譯結(jié)果。解：1）n=6,k=3,共有8個(gè)碼字。（3分）2）設(shè)碼字由得 （3分） 令監(jiān)督位為，則有 （3分）生成矩陣為 （2分）3）所有碼字為，。（4分）4）由得 ，（2分）該碼字在第5位發(fā)生錯(cuò)誤，（）糾正為（），即譯

6、碼為（）（1分） 一、填空題（本題10空,每空1分,共10分）1、必然事件的自信息量是_0_，不可能事件的自信息量是_無窮_。2、一信源有五種符號a，b，c，d，e，先驗(yàn)概率分別為Pa=0.5，Pb=0.25，Pc=0.125，Pd=Pe=0.0625。符號“a”的自信息量為_1_bit，此信源的熵為_1.875_bit/符號。3、如某線性分組碼的最小漢明距dmin=6，最多能糾正_2_個(gè)隨機(jī)錯(cuò)。4、根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否相同，可將密碼體制分成_對稱（單密鑰）_和_非對稱（雙密鑰）_。5、平均互信息量I(X;Y)與信源熵和條件熵之間的關(guān)系是_I(X:Y)=H(X)-H(X/

7、Y)_。6、克勞夫特不等式是唯一可譯碼_存在_的充要條件。00，01，10，11是否是唯一可譯碼？_是_。三、單項(xiàng)選擇題(本題共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)，對所有mm時(shí)，將y判為m，則稱該準(zhǔn)則為（D）A 最大后驗(yàn)概率譯碼準(zhǔn)則B 最小錯(cuò)誤概率準(zhǔn)則C 最大相關(guān)譯碼準(zhǔn)則D 最大似然譯碼準(zhǔn)則3、線性分組碼不具有的性質(zhì)是（C

8、）A 任意多個(gè)碼字的線性組合仍是碼字B 最小漢明距離等于最小非0重量C 最小漢明距離為3D 任一碼字和其校驗(yàn)矩陣的乘積cmHT=04、關(guān)于伴隨式的描述正確的是（A）A 伴隨式s與傳送中信道出現(xiàn)的錯(cuò)誤圖樣e有關(guān)B 通過伴隨式s可以完全確定傳送中信道出現(xiàn)的錯(cuò)誤圖樣eC 伴隨式s與發(fā)送的具體碼字有關(guān)D 伴隨式s與發(fā)送的具體碼字有關(guān)，與傳送中信道出現(xiàn)的錯(cuò)誤圖樣e也有關(guān)5、率失真函數(shù)的下限為（B）AH(U) B0 CI(U; V) D沒有下限6、糾錯(cuò)編碼中，下列哪種措施不能減小差錯(cuò)概率（D）A 增大信道容量B 增大碼長C 減小碼率D 減小帶寬7、已知某無記憶三符號信源a,b,c 等概分布，接收端為二符號

9、集，其失真矩陣為,則信源的最大平均失真度Dmax 為（ D）A 1/3 B 2/3 C 3/3 D 4/38、一珍珠養(yǎng)殖場收獲240 顆外觀及重量完全相同的特大珍珠，但不幸被人用外觀相同但重量僅有微小差異的假珠換掉1 顆。一人隨手取出3 顆，經(jīng)測量恰好找出了假珠，不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說他用天平最多6 次能找出，結(jié)果確是如此，這一事件給出的信息量（ A）。A 0bit B log6bit C 6bit D log240bit9、已知隨機(jī)噪聲電壓的概率密度函數(shù) p(x) =1/2，x 的取值范圍為1V 至+1V，若把噪聲幅度從零開始向正負(fù)幅度兩邊按量化單位為0.1V

10、做量化，并且每秒取10 個(gè)記錄，求該信源的時(shí)間熵（B ）A 21.61bit/s B 43.22bit/s C 86.44 bit /s D 以上都不對10、彩色電視顯像管的屏幕上有5105 個(gè)像元，設(shè)每個(gè)像元有64 種彩色度，每種彩度又有16種不同的亮度層次，如果所有的彩色品種和亮度層次的組合均以等概率出現(xiàn)，并且各個(gè)組合之間相互獨(dú)立。每秒傳送25 幀圖像所需要的信道容量（C ）A 50.106 B 75.106 C 125.106 D 250.106第7章 線性分組碼1. 已知一個(gè)(5, 3)線性碼C的生成矩陣為：（1）求系統(tǒng)生成矩陣；（2）列出C的信息位與系統(tǒng)碼字的映射關(guān)系；（3）求其最小

11、Hamming距離，并說明其檢錯(cuò)、糾錯(cuò)能力；（4）求校驗(yàn)矩陣H；（5）列出譯碼表，求收到r=11101時(shí)的譯碼步驟與譯碼結(jié)果。解：（1）線性碼C的生成矩陣經(jīng)如下行變換：得到線性碼C的系統(tǒng)生成矩陣為（2）碼字的編碼函數(shù)為生成了的8個(gè)碼字如下信息元系統(tǒng)碼字0000000000100111010010100110110110010011101101001101100111111110(3) 最小漢明距離d=2，所以可檢1個(gè)錯(cuò)，但不能糾錯(cuò)。(4) 由，得校驗(yàn)矩陣(5) 消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得碼字序列c0=00000, c1=0011

12、1,c2=01010, c3=01101,c4=10011, c5=10100,c6=11001, c7=11110則譯碼表如下：0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111當(dāng)接收到r =(11101)時(shí)，查找碼表發(fā)現(xiàn)它所在的列的子集頭為(01101)，所以將它譯為c=01101。2設(shè)（7, 3）線性碼的生成矩陣如下（1）

13、求系統(tǒng)生成矩陣；（2）求校驗(yàn)矩陣；（3）求最小漢明距離；（4）列出伴隨式表。解：（1）生成矩陣G經(jīng)如下行變換得到系統(tǒng)生成矩陣：（2）由，得校驗(yàn)矩陣為（3）由于校驗(yàn)矩陣H的任意兩列線性無關(guān)，3列則線性相關(guān)，所以最小漢明距離d=3。（4）（7, 3）線性碼的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得碼字序列：c0=，c1=，c2=，c3=，c4=，c5=，c6=，c7=。又因伴隨式有24=16種組合，差錯(cuò)圖樣為1的有，差錯(cuò)圖樣為2的有，而由，則計(jì)算陪集首的伴隨式，構(gòu)造伴隨表如下：伴隨式陪集首伴隨式陪集首00000101110110011010111

14、101111100100011100100101100100011000101103已知一個(gè)(6, 3)線性碼C的生成矩陣為：（1） 寫出它所對應(yīng)的監(jiān)督矩陣H；（2） 求消息M=(101)的碼字；（3） 若收到碼字為，計(jì)算伴隨式，并求最有可能的發(fā)送碼字。解：（1）線性碼C的生成矩陣G就是其系統(tǒng)生成矩陣GS，所以其監(jiān)督矩陣H直接得出：（2）消息M=(m0,m1,m2)=(101)，則碼字c為：（3）收到碼字r=()，則伴隨式又（6, 3）線性碼的消息序列m=000,001,010,011,100,101,110,111，由c=mGs 得碼字序列：c0=，c1=，c2=，c3=，c4=，c5=，c

15、6=，c7=。伴隨式有23=8種情況，則計(jì)算伴隨式得到伴隨表如下：伴隨式陪集首000101011110100010001111伴隨式（001）對應(yīng)陪集首為（），而c=r+e，則由收到的碼字r=()，最有可能發(fā)送的碼字c為：c=（）。4設(shè)(6, 3)線性碼的信息元序列為x1x2x3，它滿足如下監(jiān)督方程組（1）求校驗(yàn)矩陣，并校驗(yàn)10110是否為一個(gè)碼字； （2）求生成矩陣，并由信息碼元序列101生成一個(gè)碼字。解：（1）由監(jiān)督方程直接得監(jiān)督矩陣即校驗(yàn)矩陣為：因?yàn)槭盏降男蛄?0110為5位，而由（6, 3）線性碼生成的碼字為6位，所以10110不是碼字。（2）由，則生成矩陣為：信息碼元序列M=（101

16、），由c=mGs 得碼字為c：第8章 循環(huán)碼1. 已知(8, 5)線性分組碼的生成矩陣為 （1）證明該碼是循環(huán)碼；（2）求該碼的生成多項(xiàng)式。（1）證明如下：由生成矩陣可知為（8、5）循環(huán)碼。（2）生成多項(xiàng)式如下：2. 證明：為(15, 5)循環(huán)碼的生成多項(xiàng)式，并寫出信息多項(xiàng)式為時(shí)的碼多項(xiàng)式（按系統(tǒng)碼的形式）。由定理8-1可知（n，k）循環(huán)碼的生成多項(xiàng)式g(x)為xn+1的因子， g(x)為n-k次多項(xiàng)式，本題目中知：為一個(gè)10次多項(xiàng)式，n-k=15-5=10并且：所以：是的一個(gè)因子，也是循環(huán)碼的生成多項(xiàng)式。按系統(tǒng)碼構(gòu)造多項(xiàng)式如下：3. 已知(7, 4)循環(huán)碼的生成多項(xiàng)式為，信息多項(xiàng)式為，分別由

17、編碼電路和代數(shù)計(jì)算求其相應(yīng)的碼多項(xiàng)式C(x)。由題目可知代數(shù)計(jì)算求解過程如下：由編碼電路進(jìn)行求解：編碼電路如下所示：編碼過程如下：時(shí)鐘信息元寄存器碼字輸出碼字D0 D1 D200 0 0111 1 01200 1 10301 1 10410 1 1150 0 1160 0 0170 0 00可得：4. 令(15, 11)循環(huán)碼的生成多項(xiàng)式為，計(jì)算 （1）若信息多項(xiàng)式為，試求編碼后的系統(tǒng)碼字； （2）求接收碼組的校正子多項(xiàng)式。(1)解題過程如下：（2）校正多項(xiàng)式如下所示：5. 碼長為n=15的本原BCH碼，求不同糾錯(cuò)能力下的BCH碼各自的生成多項(xiàng)式。糾錯(cuò)能力：，所以最多能糾正7個(gè)錯(cuò)誤碼。有限域GF（24），4次本原多項(xiàng)式，為f(x)的一個(gè)根，可知：，計(jì)算2t=14個(gè)連續(xù)冪次為對應(yīng)的最小多項(xiàng)式：(1) t=1的碼字： (15