信息論與編碼試卷及答案

-11’〕填空題1948年美國(guó)數(shù)學(xué)家 香農(nóng) 發(fā)表了題通信的數(shù)學(xué)理論〞的長(zhǎng)篇論文從而創(chuàng)立信息論。必然事件的自信息是0 。離散平穩(wěn)無(wú)記憶信*的N次擴(kuò)展信源的熵等于離散信的熵的N倍 。對(duì)于離散無(wú)記憶信源，當(dāng)信源熵有最大值時(shí)，滿足條件信源符號(hào)等概分_。假設(shè)一離散無(wú)記憶信源的信源熵〔〕等于2.5，對(duì)信源進(jìn)展等長(zhǎng)的無(wú)失真二進(jìn)制編碼則編碼長(zhǎng)度至少為3 。對(duì)于香農(nóng)編碼、費(fèi)諾編碼和霍夫曼編碼，編碼方法惟一的是香農(nóng)編碼 。*線性分組碼的最小漢明距離為3，則這組碼最多能檢測(cè)_2 個(gè)碼元錯(cuò)誤，最多能正 1 個(gè)碼元錯(cuò)誤。設(shè)有一離散無(wú)記憶平穩(wěn)信道，其信道容量為C，只要待傳送的信息傳輸率R 小于 〔大于、小于或者等于則存在一種編碼，當(dāng)輸入序列長(zhǎng)度n足夠大使譯碼錯(cuò)誤概率任意小平均錯(cuò)誤概率不僅與信道本身的統(tǒng)計(jì)特性有關(guān)還譯碼規(guī)和 編碼法 有關(guān)〔5*地區(qū)的女孩中有25%是大學(xué)生，在女大學(xué)生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占總數(shù)的一半。假設(shè)我們得知"身高1.6米以上的*女孩是大學(xué)生〞的消息，問(wèn)獲得多少信息量.解：設(shè)A表示"大學(xué)生〞這一事件，B表示"身高1.60以上〞這一事件，則P(A)=0.25 p(B)=0.5 p(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(*;Y)=H(*)+H(Y)-H(*Y)證明：. z.- I;Y

pxyjii j pi X Y y pxypxy ijiiji

〔2分〕 HX H

i jX YXY

i j同理I;YHHX 〔1則因?yàn)镠HHX 〔故即I;YHHH 〔1分〕五〔18’〕.黑白氣象 圖的消息只有黑色和白色兩種，求：1〕黑色出現(xiàn)的概率為0.3，白色出現(xiàn)的概率為0.7。給出這個(gè)只有兩個(gè)符號(hào)的信源*的數(shù)學(xué)模型。假設(shè)圖上黑白消息出現(xiàn)前后沒(méi)有關(guān)聯(lián)，求熵HX；2〕 假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為 ， ，，

X。3〕分別求上述兩種信源的冗余度，比較它們的大小并說(shuō)明其物理意義。解：1〕信源模型為〔1分〕2〕由題意可知該信源為一階馬爾科夫信源?！?分〕由得極限狀態(tài)概率

〔4分〕〔2分〕. z.-3〕 1H(X)0.119

〔3分〕1 log2

2 〔1分〕 1

H(X) 0.4472 log2

2 〔1分〕2 映信源符號(hào)依賴關(guān)系的強(qiáng)弱，冗余度越大，依賴關(guān)系就越大2 18’〕.信源空間為 X x x x x x x x P(X) 1 2 3

4 5 6

7 ，試分別構(gòu)造二元香農(nóng)碼和二元霍夫 0.2 0.19 0.18 0.17 0.15 0.1 0.01 曼碼，計(jì)算其平均碼長(zhǎng)和編碼效率〔要求有編碼過(guò)程

p(x)12 1/3 1/6

1 4七〔6’〕.設(shè)有一離散信道，其信道傳遞矩陣為6 1/2 1/3，并設(shè) ( )1，試分別 px 2221/3 1/6 1/2

p(x)1 3 413分〕最小似然譯碼準(zhǔn)則下，有，3分〕最大后驗(yàn)概率準(zhǔn)則下，有，八〔10〕.二元對(duì)稱信道如圖。1〕假設(shè)p03，1HH|YI;Y；4 42〕求該信道的信道容量。解：1〕共6分23分〕此時(shí)輸入概率分布為等概率分布1分〕HX|Y0.749bit/符號(hào)

0 0 0 1 1 九〔18〕設(shè)一線性分組碼具有一致監(jiān)視矩陣H0 1 1 0 0 0 1 0 1 1〕求此分組碼n=",k="共有多少碼字.. z.--.z..z.2〕求此分組碼的生成矩陣?！硨懗龃朔纸M碼的所有碼字。4〕假設(shè)接收到碼字〔101001〕，求出伴隨式并給出翻譯結(jié)果。解：1〕n=6,k=3,共有8個(gè)碼字。〔3分〕C 2〕設(shè)碼字

CCCC

HCT0T5 4 3 CCC 0

2 1 0由 得2 1 0CCC 04 3 03 1 5 CCC 03 1 5CCC令監(jiān)視位為

2 1

，則有CC 2 5 3CCC1 5 404 C04

〔3分〕11001100100110011013000000，001101，010011，011110，100110，101011，110101，1110004分〕4〕由ST

HRT得S 2分〕該碼字在第5101001〕糾正為〔1010111010011分〕一、填空題〔此題10空,每空1分,共10分〕1、必然事件的自信息量0 ，不可能事件的自信息量無(wú)。一信源有五種符{abcde}先驗(yàn)概率分別為=0.=0.2c=0.125d=e=0.062。符號(hào)"a〞的自信息量1 bit，此信源的熵1.875 bit/符號(hào)。3、如*線性分組碼的最小漢明dmin=6，最多能糾2 個(gè)隨機(jī)錯(cuò)。4、根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否一樣，可將密碼體制分對(duì)稱〔密鑰〕 和 非對(duì)稱〔雙密鑰。5、平均互信息量I(*;Y)與信源熵和條件熵之間的關(guān)系I(*:Y)=H(*)-H(*/Y) 。6、克勞夫特不等式是唯一可譯存在 的充要條件是否是唯可譯碼. 是 。三、單項(xiàng)選擇題(此題共10小題；每題2分，共20分)1、對(duì)連續(xù)集的熵的描述不正確的選項(xiàng)是〔A〕A連續(xù)集的熵和離散集的熵形式一致，只是用概率密度代替概率，用積分代替求和B連續(xù)集的熵值無(wú)限大C連續(xù)集的熵由絕對(duì)熵和微分熵構(gòu)成D連續(xù)集的熵可以是任意整數(shù)y|my|≠m時(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)于伴隨式的描述正確的選項(xiàng)是〔A〕A伴隨式s與傳送道出現(xiàn)的錯(cuò)誤圖樣e有關(guān)B通過(guò)伴隨式s可以完全確定傳送道出現(xiàn)的錯(cuò)誤圖樣eC伴隨式s與發(fā)送的具體碼字有關(guān)D伴隨式s與發(fā)送的具體碼字有關(guān)，與傳送道出現(xiàn)的錯(cuò)誤圖樣e也有關(guān)5、率失真函數(shù)的下限為〔B〕B0 D沒(méi)有下限6、糾錯(cuò)編碼中，以下哪種措施不能減小過(guò)失概率DA增大信道容量B 增大碼長(zhǎng)C減小碼率D減小帶寬7、*無(wú)記憶三符號(hào)信源a,b,c等概分布，接收端為二符號(hào)集，其失真矩陣為,則信源的最大平均失真度Dma*為〔D〕A1/3B2/3C3/3D4/38、一珍珠養(yǎng)殖場(chǎng)收獲240顆外觀及重量完全一樣的特大珍珠，但不幸被人用外觀一樣但重量?jī)H有微小差異的假珠換掉1顆。一人隨手取出3顆，經(jīng)測(cè)量恰好找出了假珠，不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說(shuō)他用天平最多6信息量〔AA0bitBlog6bitC6bitDlog240bit9、隨機(jī)噪聲電壓的概率密度函數(shù)p(*)=1/2，*的取值圍為－1V至+1V，假設(shè)把噪聲幅度從零開(kāi)場(chǎng)向正負(fù)幅度兩邊按量化單位為0.1V10BA21.61bit/sB43.22bit/sC86.44bit/sD以上都不對(duì)10、彩色電視顯像管的屏幕上有5×105個(gè)像元，設(shè)每個(gè)像元有64種彩色度，每種彩度又有種不同的亮度層次，如果所有的彩色品種和亮度層次的組合均以等概率出現(xiàn)，并且各個(gè)組合之25C〕A50.106B75.106C125.106D250.106第7章線性分組碼1.一個(gè)(5,3)線性碼C的生成矩陣為：〔1〕求系統(tǒng)生成矩陣；〔2〕列出C的信息位與系統(tǒng)碼字的映射關(guān)系；〔3〕求其最小Hamming距離，并說(shuō)明其檢錯(cuò)、糾錯(cuò)能力；〔4〕求校驗(yàn)矩陣H；〔5〕列出譯碼表，求收到r=11101時(shí)的譯碼步驟與譯碼結(jié)果。解：〔1〕線性碼C的生成矩陣經(jīng)如下行變換：得到線性碼C的系統(tǒng)生成矩陣為〔2c(cc0 1

, ,

n1

)的編碼函數(shù)為生成了的8個(gè)碼字如下信息元系統(tǒng)碼字0000000000100111010010100110110110010011101101001101100111111110最小漢明距離1個(gè)錯(cuò)，但不能糾錯(cuò)。由G[I

nk

,Ak(nk)

],H[Ak(nk)

T,I

nk

]，得校驗(yàn)矩陣(5)消息序列m=000,001,010,011,100,101,110,111，由c=mGs得碼字序列c=00000,c=00111,c=01010,c=01101,0 1 2 3c=10011,c=10100,c=11001,c=111104 5 6 7則譯碼表如下：0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111當(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〕由G[I

nk

,Ak(nk)

],H[Ak(nk)

T,I

nk

]，得校驗(yàn)矩陣為〔3〕由于校驗(yàn)矩陣H的任意兩列線性無(wú)關(guān)，3列則線性相關(guān)，所以最小漢明距離d=3。〔47,3〕線性碼的消息序列m=000,001,010,011,100,101,110,111，由c=mGs=0000000，c=0010111，0 1c=0101010，c=0111101，c=1001101，c=1011010，c=1100111，c=1110000。又因伴隨式有24=16種組合，過(guò)失圖2 3 4 5 6 77 7樣為1的有

7種，過(guò)失圖樣為2的有 種，而由HrT

HeT，則計(jì)算陪集首的伴隨式，構(gòu)造伴隨1 2表如下：伴隨式陪集首伴隨式陪集首00000000000010110010001101100000010011000100101001000001111001100001110010000110000011001000000100011100100100010000001001011010000100100000010001100101000001000000101100000110一個(gè)(6,3)線性碼C的生成矩陣為：〔1〕寫出它所對(duì)應(yīng)的監(jiān)視矩陣H；〔2〕求消息M=(101)的碼字；〔3〕假設(shè)收到碼字為101010，計(jì)算伴隨式，并求最有可能的發(fā)送碼字。解：〔1〕線性碼C的生成矩陣G就是其系統(tǒng)生成矩陣GS，所以其監(jiān)視矩陣H直接得出：〔2〕消息M=(m,m,m)=(101)，則碼字c為：0 1 2〔3〕收到碼字r=(101010)，則伴隨式又〔6,3〕線性碼的消息序列m=000,001,010,011,100,101,110,111，由c=mGs得碼字序列：c=000000，c=001110，0 1c=010011，c=011101，c=100101，c=101011，c=110110，c=111000。伴隨式有23=8種情況，則計(jì)算伴隨式得到伴2 3隨表如下：

4 5 6 7伴隨式陪集首000000000101100000011010000110001000100000100010000010001000001111100010伴隨式〔001〕對(duì)應(yīng)陪集首為〔000001〕，而c=r+e，則由收到的碼字r=(101010)，最有可能發(fā)送的碼字c為：c=〔101011設(shè)(6,3)線性碼的信息元序列為***，它滿足如下監(jiān)視方程組123〔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不是碼字?！?〕由G[I

nk

,Ak(nk)

],H[Ak(nk)

T,I

nk

]，則生成矩陣為：信息碼元序列M=〔101〕，由c=mGs得碼字為c：第8章 循環(huán)碼(8,5)線性分組碼的生成矩陣為〔1〕證明該碼是循環(huán)碼；〔2g(x)。〔1〕證明如下：由生成矩陣可知為〔8、5〕循環(huán)碼?！?〕生成多項(xiàng)式如下：證明：x10x8x5x4x2x1為(15,5)循環(huán)碼的生成多項(xiàng)式，并寫出信息多項(xiàng)式為m(x)x4x1時(shí)的碼多項(xiàng)式〔按系統(tǒng)碼的形式由定理8-1可知〔n，k〕循環(huán)碼的生成多項(xiàng)式g(*)為*n+1的因子，g(*)為n-k次多項(xiàng)式，此題目中知：g(x)x10x8x5x4x2x1為一個(gè)10次多項(xiàng)式，n-k=15-5=10(x151)mod(x10x8x5x4x2x1)0x10x8x5x4x2x1x151的一個(gè)因子，也是循環(huán)碼的生成多項(xiàng)式。按系統(tǒng)碼構(gòu)造多項(xiàng)式如下：(7,4g(x)x和代數(shù)計(jì)算求其相應(yīng)的碼多項(xiàng)式由題目可知代數(shù)計(jì)算求解過(guò)程如下：由編碼電路進(jìn)展求解：編碼電路如下所示：

x1，信息多項(xiàng)式為m(x)x

1，分別由編碼電路如下：時(shí)鐘0如下：時(shí)鐘0信息元存放器碼字D輸出碼字00 1DD0 02門1D0+D1D2+或門c(x)m11110120011030111041011150011