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

1、一、（11）填空題（1） 1948年，美國數(shù)學(xué)家 香農(nóng) 發(fā)表了題為“通信的數(shù)學(xué)理論”的長篇論文，從而創(chuàng)立了信息論。（2） 必然事件的自信息是 0 。 （3） 離散平穩(wěn)無記憶信源x的n次擴(kuò)展信源的熵等于離散信源x的熵的 n倍 。 （4） 對(duì)于離散無記憶信源，當(dāng)信源熵有最大值時(shí)，滿足條件為_信源符號(hào)等概分布_。（5） 若一離散無記憶信源的信源熵h（x）等于2.5，對(duì)信源進(jìn)行等長的無失真二進(jìn)制編碼，則編碼長度至少為 3 。（6） 對(duì)于香農(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|

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

4、系為 ，求其熵。3）分別求上述兩種信源的冗余度，比較它們的大小并說明其物理意義。解：1）信源模型為 （1分）2）由題意可知該信源為一階馬爾科夫信源。 （2分）由 （4分）得極限狀態(tài)概率 （2分） （3分）3） （1分） （1分）。說明：當(dāng)信源的符號(hào)之間有依賴時(shí)，信源輸出消息的不確定性減弱。而信源冗余度正是反映信源符號(hào)依賴關(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ò)

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

6、01101，010011，011110，100110，101011，110101，111000。（4分）4）由得 ，（2分）該碼字在第5位發(fā)生錯(cuò)誤，（101001）糾正為（101011），即譯碼為（101001）（1分） 一、填空題（本題10空,每空1分,共10分）1、必然事件的自信息量是_0_，不可能事件的自信息量是_無窮_。2、一信源有五種符號(hào)a，b，c，d，e，先驗(yàn)概率分別為pa=0.5，pb=0.25，pc=0.125，pd=pe=0.0625。符號(hào)“a”的自信息量為_1_bit，此信源的熵為_1.875_bit/符號(hào)。3、如某線性分組碼的最小漢明距dmin=6，最多能糾正_2_個(gè)隨機(jī)

7、錯(cuò)。4、根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否相同，可將密碼體制分成_對(duì)稱（單密鑰）_和_非對(duì)稱（雙密鑰）_。5、平均互信息量i(x;y)與信源熵和條件熵之間的關(guān)系是_i(x:y)=h(x)-h(x/y)_。6、克勞夫特不等式是唯一可譯碼_存在_的充要條件。00，01，10，11是否是唯一可譯碼？_是_。三、單項(xiàng)選擇題(本題共10小題；每小題2分，共20分)1、對(duì)連續(xù)集的熵的描述不正確的是（a）a 連續(xù)集的熵和離散集的熵形式一致，只是用概率密度代替概率，用積分代替求和b 連續(xù)集的熵值無限大c 連續(xù)集的熵由絕對(duì)熵和微分熵構(gòu)成d 連續(xù)集的熵可以是任意整數(shù)2、設(shè)信道輸入為xm，輸出為y，若譯碼準(zhǔn)

8、則是當(dāng)p(y | xm)p(y | xm)，對(duì)所有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）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(

9、u) b0 ci(u; v) d沒有下限6、糾錯(cuò)編碼中，下列哪種措施不能減小差錯(cuò)概率（d）a 增大信道容量b 增大碼長c 減小碼率d 減小帶寬7、已知某無記憶三符號(hào)信源a,b,c 等概分布，接收端為二符號(hào)集，其失真矩陣為,則信源的最大平均失真度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 0bi

10、t b log6bit c 6bit d log240bit9、已知隨機(jī)噪聲電壓的概率密度函數(shù) p(x) =1/2，x 的取值范圍為1v 至+1v，若把噪聲幅度從零開始向正負(fù)幅度兩邊按量化單位為0.1v 做量化，并且每秒取10 個(gè)記錄，求該信源的時(shí)間熵（b ）a 21.61bit/s b 43.22bit/s c 86.44 bit /s d 以上都不對(duì)10、彩色電視顯像管的屏幕上有5×105 個(gè)像元，設(shè)每個(gè)像元有64 種彩色度，每種彩度又有16種不同的亮度層次，如果所有的彩色品種和亮度層次的組合均以等概率出現(xiàn)，并且各個(gè)組合之間相互獨(dú)立。每秒傳送25 幀圖像所需要的信道容量（c ）a

11、 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）求其最小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

12、) 最小漢明距離d=2，所以可檢1個(gè)錯(cuò)，但不能糾錯(cuò)。(4) 由，得校驗(yàn)矩陣(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則譯碼表如下：0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100

13、110010110110010010101011100011111當(dāng)接收到r =(11101)時(shí)，查找碼表發(fā)現(xiàn)它所在的列的子集頭為(01101)，所以將它譯為c=01101。2設(shè)（7, 3）線性碼的生成矩陣如下（1）求系統(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=0000000，c1=

14、0010111，c2=0101010，c3=0111101，c4=1001101，c5=1011010，c6=1100111，c7=1110000。又因伴隨式有24=16種組合，差錯(cuò)圖樣為1的有，差錯(cuò)圖樣為2的有，而由，則計(jì)算陪集首的伴隨式，構(gòu)造伴隨表如下：伴隨式陪集首伴隨式陪集首000000000000101100100011011000000100110001001010010000011110011000011100100001100000110010000001000111001001000100000010010110100001001000000100011001010000010

15、000001011000001103已知一個(gè)(6, 3)線性碼c的生成矩陣為：（1） 寫出它所對(duì)應(yīng)的監(jiān)督矩陣h；（2） 求消息m=(101)的碼字；（3） 若收到碼字為101010，計(jì)算伴隨式，并求最有可能的發(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=0111

16、01，c4=100101，c5=101011，c6=110110，c7=111000。伴隨式有23=8種情況，則計(jì)算伴隨式得到伴隨表如下：伴隨式陪集首000000000101100000011010000110001000100000100010000010001000001111100010伴隨式（001）對(duì)應(yīng)陪集首為（000001），而c=r+e，則由收到的碼字r=(101010)，最有可能發(fā)送的碼字c為：c=（101011）。4設(shè)(6, 3)線性碼的信息元序列為x1x2x3，它滿足如下監(jiān)督方程組（1）求校驗(yàn)矩陣，并校驗(yàn)10110是否為一個(gè)碼字； （2）求生成矩陣，并由信息碼元序列101生

17、成一個(gè)碼字。解：（1）由監(jiān)督方程直接得監(jiān)督矩陣即校驗(yàn)矩陣為：因?yàn)槭盏降男蛄?0110為5位，而由（6, 3）線性碼生成的碼字為6位，所以10110不是碼字。（2）由，則生成矩陣為：信息碼元序列m=（101），由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-

18、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)式為，分別由編碼電路和代數(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ù)冪次為對(duì)應(yīng)的最小