信息論副本

1、一、 填空1. 11948年美國數(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）等于2.5，對信源進(jìn)行等長的無失真二進(jìn)制編碼，則編碼長度至少為 3 。6. 對于香農(nóng)編碼、費(fèi)諾編碼和霍夫曼編碼，編碼方法惟一的是 香農(nóng)編碼。7. 已知某線性分組碼的最小漢明距離為3，那么這組碼最多能檢測出_2_個碼元錯誤，最多能糾正_1_個碼元錯誤。8. 設(shè)有一離散無記憶平

2、穩(wěn)信道，其信道容量為C，只要待傳送的信息傳輸率R_ 小于_C則存在一種編碼，當(dāng)輸入序列長度n足夠大，使譯碼錯誤概率任意小。9. 概率大的事件自信息量大。 （ ´ ）10. 互信息量可正、可負(fù)亦可為零。 （ Ö ）11.對于固定的信源分布，平均互信息量是信道傳遞概率的下凸函數(shù)。 （Ö ）12.可以用克勞夫特不等式作為唯一可譯碼存在的判據(jù)。 （Ö ）13.線性碼一定包含全零碼。 （Ö ）14.離散平穩(wěn)有記憶信源符號序列的平均符號熵隨著序列長度L的增大而增大。 （×） 15.限平均功率最大熵定理指出對于相關(guān)矩陣一定的隨機(jī)矢量X，當(dāng)它是正態(tài)分

3、布時具 有最大熵。 （Ö ） 16.循環(huán)碼的碼集中的任何一個碼字的循環(huán)移位仍是碼字。 （Ö ）17.信道容量是信道中能夠傳輸?shù)淖钚⌒畔⒘俊?（×）18相互獨(dú)立的事件所包含的信息量分別為,則聯(lián)合消息所包含的信息量為（）。19、比較大?。篐(X)(小于 )H(Y/X)(小于 )H(XY).20、扔一枚硬幣所獲得的平均信息量是（小于等于1bit）。21、香農(nóng)公式為（）。22、有一離散無記憶信源的熵為H(X)，則其五維延長信源的熵=（）。23、線性分組碼（n，k），若要求它能糾正2個隨機(jī)錯誤，則其最小碼距為（5）；若要求它能糾正2個隨機(jī)錯誤且能檢測到2個隨機(jī)錯誤，則其最小

4、碼距為（7）。24、若某無記憶信源X為，壓縮信源后變?yōu)榉朰,且，其失真矩陣為，則相應(yīng)的率失真函數(shù)自變量的最大值max=( 1 ), 最小值min=( )。二、 計算1. 居住在某地區(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.75 ，故：p(A|B)=p(AB)/p(B)=p(A)p(B|A)/p(B)=0.75*0.25/0.5=

5、0.375 I(A|B)=-log0.375=1.42bit 2.黑白氣象傳真圖的消息只有黑色和白色兩種，求：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）信源模型為 2）由題意可知該信源為一階馬爾科夫信源。得極限狀態(tài)概率 3） 說明：當(dāng)信源的符號之間有依賴時，信源輸出消息的不確定性減弱。而信源冗余度正是反映信源符號依賴關(guān)系的強(qiáng)弱，冗余度越大，依賴關(guān)系就越大。3、信源空間為，試分

6、別構(gòu)造二元香農(nóng)碼和二元霍夫曼碼，計算其平均碼長和編碼效率（要求有編碼過程）。解：4（10¢）.二元對稱信道如圖。1）若，求、和；2）求該信道的信道容量。解：1）2） 此時輸入概率分布為等概率分布。5、設(shè)一線性分組碼具有一致監(jiān)督矩陣1）求此分組碼n=?,k=?共有多少碼字？2）求此分組碼的生成矩陣G。3）寫出此分組碼的所有碼字。4）若接收到碼字（101001），求出伴隨式并給出翻譯結(jié)果。解：1）n=6,k=3,共有8個碼字。2）設(shè)碼字 由得 令監(jiān)督位為，則有 生成矩陣為 3） 所有碼字為000000，001101，010011，011110，100110，101011，110101，1

7、11000。4）由得，該碼字在第5位發(fā)生錯誤，（101001）糾正為（101011），即譯碼為（101001）6.寫出香農(nóng)公式，并說明其物理意義。當(dāng)信道帶寬為5000Hz，信噪比為30dB時求信道容量。答：香農(nóng)公式為，它是高斯加性白噪聲信道在單位時間內(nèi)的信道容量，其值取決于信噪比和帶寬。由得，則。7. 信源空間為，試分別構(gòu)造二元和三元霍夫曼碼，計算其平均碼長和編碼效率。答：1）二元碼的碼字依序為：10，11，010，011，1010，1011，1000，1001。平均碼長，編碼效率2）三元碼的碼字依序為：1，00，02，20，21，22，010，011。平均碼長，編碼效率。8.某系統(tǒng)（7，4）

8、碼其三位校驗位與信息位的關(guān)系為：（1）求對應(yīng)的生成矩陣和校驗矩陣；（2）計算該碼的最小距離；（3）列出可糾差錯圖案和對應(yīng)的伴隨式；（4）若接收碼字R=1110011，求發(fā)碼。解：1. 2. dmin=3; 3. 4. RHT=001接收出錯E=0000001 R+E=C= 1110010(發(fā)碼) 9.一階齊次馬爾可夫信源消息集,狀態(tài)集，且令，條件轉(zhuǎn)移概率為，(1)畫出該馬氏鏈的狀態(tài)轉(zhuǎn)移圖；計算信源的極限熵。解：(1)（2）H(X|S1) =H(1/4,1/4,1/2)=1.5比特/符號H(X|S2)=H(1/3,1/3,1/3)=1.585比特/符號H(X|S3)=H(2/3,1/3)= 0.

9、918比特/符號 比特/符號10.若有一信源，每秒鐘發(fā)出2.55個信源符號。將此信源的輸出符號送入某一個二元信道中進(jìn)行傳輸（假設(shè)信道是無噪無損的，容量為1bit/二元符號），而信道每秒鐘只傳遞2個二元符號。（1） 試問信源不通過編碼（即x1®0,x2®1在信道中傳輸）（2） 能否直接與信道連接？（3） 若通過適當(dāng)編碼能否在此信道中進(jìn)行無失真?zhèn)鬏敚浚?） 試構(gòu)造一種哈夫曼編碼(兩個符號一起編碼)，（5） 使該信源可以在此信道中無失真?zhèn)鬏?。解?.不能，此時信源符號通過0，1在信道中傳輸，2.55二元符號/s>2二元符號/s 2. 從信息率進(jìn)行比較，2.55*= 1.84

10、 < 1*2。3.可以進(jìn)行無失真?zhèn)鬏?1.56 二元符號/2個信源符號此時 1.56/2*2.55=1.989二元符號/s < 2二元符號/s11.設(shè)信源為，試求（1）信源的熵、信息含量效率以及冗余度；（2） 求二次擴(kuò)展信源的概率空間和熵。解：（1）（2）二次擴(kuò)展信源的概率空間為：12. 假定一個電視每秒鐘顯示30個畫面，每個畫面大約有個像素，每個像素需要16比特的彩色顯示。假定SNR為25dB， 計算支持電視信號傳輸所需要的帶寬（利用信息容量定理）解：根據(jù)題意該電視信號所需的信息容量根據(jù)信息容量定理：，其中為信噪比，據(jù)題意據(jù)上式解得帶寬13. 明是一個線性碼。它的最小距離是什么？

11、證明：由書中的定義3.8可知，線性碼應(yīng)該滿足一下條件：（1） 兩個屬于該碼的碼字的和仍然是一個屬于該碼的碼字，（2） 全零字總是一個碼字，（3） 兩個碼字之間的最小距離等于任何非零碼字的最小重量，即解：設(shè)，即，首先證明條件（1）：，很明顯，條件（1）是滿足的。條件（2）也是顯然成立的。最后證明條件（3）：不難看出最小距離，并且最小重量，即綜上可知就是一個線性碼，它的最小距離是2。I.線性碼的性質(zhì)：兩個屬于該碼的碼字的和仍是屬于該碼的碼字；全零碼字總是一個碼字；一個線性碼的兩個碼字之間的最小距離等于任何非零碼字的最小重量，即d*=w*滿足三條性質(zhì)所以，這個碼是線性碼。14 考慮GF（2）上的下列

12、生成矩陣a.用此矩陣生成所有可能的碼字。b.求奇偶校驗矩陣H。c.求與其等價的一個系統(tǒng)碼的生成矩陣。d.構(gòu)造該碼的標(biāo)準(zhǔn)陣列。e.這個碼的最小距離是多少。f.這個碼能檢測多少錯誤。g.寫出這個碼能檢測的所有錯誤模式。h.這個碼能糾多少個錯誤。i.如果我們用此編碼方案，那么符號錯誤概率是多少？將它與末尾的錯誤概率進(jìn)行比較。這是一個線性碼？解：a.=,=,=,= =,=此矩陣生成的碼為：00000，01010，10011，11001，10100，11110，00111，01101 。 b.二元情況下，, 奇偶校驗矩陣可寫為：。 d.該碼的標(biāo)準(zhǔn)陣列 e.奇偶校驗矩陣H的第1、3列的和為零向量，因此，這

13、個碼的最小距離為：d*=2。f.一個碼至少可以檢測所有重量小于或等于（d*-1）的非零錯誤模式。g.這個碼能檢測的所有錯誤模式00001，00010，00100，01000，10000h.能糾正不多于t個錯誤應(yīng)滿足又d*=2 所以即這個碼能糾0個錯誤。15. 構(gòu)造C=00000，10101，01010，11111的生成矩陣。因為這個G不是唯一的，給出另一個能生成這個碼字集合的生成矩陣。解：設(shè)生成矩陣是G=，由題知，m=2,n=5, c=iG，i=(0,0) (0,1),(1,0),(1,1)，生成矩陣G=。16.設(shè)多項式為GF(2)上分組長度為15的一個循環(huán)碼的生成多項式。(1)求生成矩陣G.

14、。(2)求奇偶校驗矩陣H。(3)這個碼能檢測多少個錯誤？(4)這個碼能糾多少個錯誤？(5)將生成矩陣寫成系統(tǒng)型。解：(1)由生成多項式可知，生成矩陣為：(2)由于已知分組長度為15，設(shè)奇偶校驗多項式為h(x),則有即：其中，上式為取模運(yùn)算。故，對應(yīng)的奇偶校驗矩陣為：(3)建立如下表格：ii(x)c(x)=i(x)g(x)c00o0000000000000000011g(x)10xx g(x)11x+1(x+1) g(x)由該表格可以看出，該碼的最小距離為7。即：故可知，該碼可以檢測個錯誤。(4)由于，則有：即：故該碼可以糾3個錯誤。(5)該生成矩陣的系統(tǒng)型為：17. 二元對稱信道的信道矩陣為，

15、信道傳輸速度為1500二元符號/秒，設(shè)信源為等概率分布，信源消息序列共有13000個二元符號，問：（1）試計算能否在10秒內(nèi)將信源消息序列無失真?zhèn)魉屯?？?）若信源概率分布為，求無失真?zhèn)魉鸵陨闲旁聪⑿蛄兄辽傩枰嚅L時間？答：1）信道容量為信源序列信息量為而10秒內(nèi)信道能傳遞的信息量為故不能無失真地傳送完。2）此時信源序列信息量為信息傳輸率為則18.某碼長n=15循環(huán)碼的生成多項式試（1）畫出其編碼器原理圖（2）分析當(dāng)信息位為01010101011時，編碼器的工作原理；并指出相應(yīng)的輸出碼字。編碼器如下所示19.、某二進(jìn)制卷積碼的編碼電路如下所示:試：（1）該卷積碼的n=?k=?N=?（2）設(shè)輸

16、入信息序列20試寫出（1）離散信源最大熵定理（2）比較每組事件中誰的信息量大。1）A：電視廣告：“送禮只送腦白金”。B：用戶的話：“送禮只送腦白金”。2）A：八月份的天氣預(yù)報：“明天有雨”。B：十二月份的天氣預(yù)報：“明天有雨”。21試計算下列信道的信道容量，并指出此時信源的概率分布。22、（15分）設(shè)信源有8個獨(dú)立的消息，它們出現(xiàn)的概率如下：A：0.1 B：0.18 C：0.4 D：0.05E：0.06 F：0.1 G：0.07 H：0.04試按哈夫曼編碼法進(jìn)行編碼，并計算出平均碼長和編碼效率。 解：=2.552bit/符號,平均碼長=2.61碼元/符號，信源編碼的編碼效率=97.79%霍夫曼編碼 符號 代碼組 biC 0.4 0 0 1B 0.18 0 110 3A 0.1 0 (1,0) 100 3 0 (0.23) 1F 0.1 0 1 1 (0.6) 1111 4G 0.07 1 1011 4 1E 0.06 0 (0.13) 1 1010 4