信息論與編碼C

1、制作人：陳瑞焦良葆年月曰填空題（本題15空，每空1分，共15分）設(shè)信源X包含設(shè)信源X包含n個(gè)不同離散消息，當(dāng)且僅當(dāng)X中各個(gè)消息出現(xiàn)的概率（相等）時(shí),信源熵達(dá)到最大值，為（log2n信源熵達(dá)到最大值，為（log2n ）。丄迓H （X離散平穩(wěn)有記憶信源的平均符號(hào)熵Hn （X）的表達(dá)式為（N “=1| X nT)1 )，極限熵H的表達(dá)式為（熵H的表達(dá)式為（oolim h( x i X N-1)N 1N s）。如糾錯(cuò)碼的最小距離為d .，則可以檢出任意小于等于（d 1 ） inmin個(gè)隨機(jī)差錯(cuò),可以糾正任意小于等于（如糾錯(cuò)碼的最小距離為d .，則可以檢出任意小于等于（d 1 ） inmin個(gè)隨機(jī)差錯(cuò),

2、可以糾正任意小于等于（d i 1） /2 ）個(gè)隨機(jī)差錯(cuò)。min一個(gè)（2， 1， 3）卷積碼的約束長(zhǎng)度為（3 ），共有（8 ）種狀態(tài)。卷積碼的自由距離的定義為（任意長(zhǎng)度卷積碼編碼后序列之間的最小漢明距離），可用（網(wǎng)格圖）法和（梅森公式）法計(jì)算自由距離。根據(jù)密碼算法所使用的加密密鑰和解密密鑰是否相同，可將密碼體制分成（對(duì)稱密碼體制）和（非對(duì)稱密碼體制）。算術(shù)編碼是發(fā)展迅速的一種（無(wú)）失真信源編碼方法，其基本思想是（將一定精度的數(shù)值作為序列的編碼）。一 判斷題（本題10小題,每小題1分，共10分）1. 72. 73. 74. 75. x6. x7. 78. x9. 710. x（1）離散信源的最大熵

3、的值取決于符號(hào)狀態(tài)數(shù)，狀態(tài)數(shù)越多，熵越大。（）（2）只要已知某一個(gè)信源符號(hào)的先驗(yàn)概率及相應(yīng)的轉(zhuǎn)移概率，就可以得到相應(yīng)的互信 TOC o 1-5 h z 息量。（）（3）限失真信源編碼逆定理說(shuō)明在允許失真D的條件下，信源最小的、可達(dá)的信息傳輸率是信源的R（D）。（）（4） 如X可以唯一確定Y,則H（Y/X）=O。（）（5）馬爾可夫序列的聯(lián)合概率具有時(shí)間推移不變性。（）（6） 碼組0，01，011，0111屬于不等長(zhǎng)的即時(shí)碼。（）（7） 極限熵H =有記憶信源的最小平均消息熵。（）00（8）若碼么=101111，111100，則和P之間的漢明距離為D，P）二3。（）（9）設(shè)（7, 4）循環(huán)碼的生成

4、多項(xiàng)式為g（x）=x3+x+1，當(dāng)接收碼字為0010011時(shí)，接收碼字中有錯(cuò)。（）（10）條件熵H（Y/X）稱為疑義度，可疑度，它表示接收者收到Y(jié)后，對(duì)信源X仍然存在的平均不確定度。（）三 名詞解釋（本題4小題,每小題5分，共20分）1漢明碼漢明碼失糾錯(cuò)能力t=1的一類碼的統(tǒng)稱，其n，k的值服從規(guī)律：（n,k）=（2m-1,2m-1-m）。2算術(shù)編碼從全序列出發(fā)，將各信源序列的概率映射到0，1區(qū)間，使每個(gè)序列對(duì)應(yīng)到區(qū)間上的一點(diǎn), 這些點(diǎn)將區(qū)間分成若干小段，每段的長(zhǎng)度對(duì)應(yīng)某一序列的概率。再在段內(nèi)取一個(gè)二進(jìn)制小 數(shù)，其長(zhǎng)度與該序列的概率匹配，達(dá)到高效率編碼的目的。3檢錯(cuò)重傳在接收端根據(jù)編碼規(guī)則進(jìn)行

5、檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過(guò)反向信道要求發(fā)送端重新 發(fā)送，直到接收端檢查無(wú)誤為止。4噪聲熵條件熵H（Y/X）可看作唯一地確定信道噪聲所需要的平均信息量，因此也稱為噪聲熵或散 步度。四計(jì)算題（本題3小題，共25分）1.設(shè)（7, 4）循環(huán)碼的生成多項(xiàng)式g（x） = x3 + x +1，求：1）監(jiān)督多項(xiàng)式；2）此循環(huán)碼的生成矩陣（非系統(tǒng)碼和系統(tǒng)碼形式）；3）一致監(jiān)督矩陣；4）若輸入u（x）二1 + x2 + x3，試求系統(tǒng)碼形式的輸出碼字。（2+4+2+2=10 分）解：1）已知循環(huán)碼（7,4），用1 + x + x3去除1 + x7得到監(jiān)督多項(xiàng)式h x）2）非系統(tǒng)碼的生成矩陣2）非系統(tǒng)碼的生成

6、矩陣G=x 3.g ( x)x3 + x 4 + x 6x 2.g ( x)x 2 + x3 + x5x.g (x)x + x 2 + x 4_ g (x)_1 + x + x3x 6 + r (x)x 6 + r (x)6x 6 + x 2 + 1xn-1 + r(x)n-1x 5 + r (x)5x5 + x2 + x + 1xn - 2 + r(x)n-2x 4 + r (x)4x 4 + x 2 + x系統(tǒng)G=xn - k + r(x)一n 一 k一=x 3 + r (x)L3J=x 3 + x + 1rn - i是g （X）除xn-i所得的余式3)H=x2 - h(x)x - h(

7、x) h( x)x 6 + x 4 + x 3 + x 2x 5 + x 3 + x 2 + xx 4 + x 2 + x + 1C(X)=r(x)+ xn-ku(x) xn-ku(x) = x j4 . (x3 + x2 + 1) = x6 + x5 + x3r(x)= xnr(x)= xn-ku(x)mod g (x) = x6 + x5 + x3 + 1=11010011）信道容量C的定義式什么？2） 求該信道的信道容量C。（3+3=6分）c = max i （ x ； y ）解：1）信道容量的定義式為：p（xi）（3分）1已知離散無(wú)記憶信源s 1已知離散無(wú)記憶信源s -_ P(s)_1

8、)求信源熵H (S)；2)進(jìn)行哈夫曼編碼，并求平均碼長(zhǎng)和編碼效率;c = max i( x ； y)丄丄丄丄 12)p(xi)=log24H( 2 4 8 8 )=2 2 log22 4 log24 8 log28 8 log28=0.25 3 已知 X, YW0, 1, XY 構(gòu)成的聯(lián)合概率為 p (00) =p (11) =1/8, p (01) =p (10)=3/8，試計(jì)算熵 H (X), H (XY), H (X/Y)。(9 分) 解：p(0)=p(00)+p(01)=l/8+3/8=l/2 p(l)=p(10)+p(ll)=l/8+3/8=l/2 q(0)=p(00)+p(10)=

9、l/8+3/8=l/2 q(1)=p(01)+p(11)=3/8+1/8=1/2 H(X)=1/21og22+1/21og22=1bit/ 符號(hào)H(XY)=2 X 1/8log28+2 X 3/8log28/3=1.8bit/ 符號(hào)H(X/Y)=左1譬log嚳dog竺芻og竺j=0 i=0 曲)曲)2X 1/2 S/8+2X 1/2 幻/8 2.89bit/ 符號(hào)五綜合題(本題3小題，共30分)vS小S . S彳S lS /*123. 45603020150.150101，試求.3)哈夫曼編碼是否唯一？如果不唯一，哪種編碼方法更佳？ (3+4+3=103)-Y P(s)log P(s)解：1)

10、H(S)= i= - 0.3l og20.3 - 0.2log20.2 - 2 X 0.15log20.15 - 2 X 0.1log20.1=2.47bit/ 符號(hào)2)符號(hào)s5s6概率編碼0001011符號(hào)s5s6概率編碼0001011K=0.3 X 2+0.2 X 2+0.15 X 3+0.15 X 3+0.1 X 3+0.1 X 3=2.5H (S)2.47q =K = 2.5 =98.8%3)由于按照概率大小順序排隊(duì)方法的不惟一，哈夫曼編碼不惟一。將新合并的等概率消息 排列到上支路(即大概率位置)，可以證明它將有利于縮短碼長(zhǎng)的方差，即編出的碼更接 近于等長(zhǎng)碼，這種編碼方法更佳。2 一個(gè)

11、二進(jìn)制(r=2)二階(m=2)馬爾柯夫信源的原始信源為X0, 1,這時(shí)的狀態(tài)空間為: S=S口其一步轉(zhuǎn)移概率為：0/0000p(0/00)P(0/SJP(S1/S1)=0.81/0001p(1/00)P(1/SJp(S2/S1)=0.20/0110p(0/01)P(0/S2)P(S3/S2)=0.51/0111p(1/01)P(1/S2)p(S4/S2)=0.50/1000p(0/10)P(0/S3)p(S1/S3)=0.51/1001p(1/10)P(1/S3)p(S2/S3)=0.50/1110p(0/11)P(0/S4)p(S3/S4)=0.21/1111p(1/11)P(1/S4)p(

12、S4/S4)=0.8試：1)畫(huà)出信源的狀態(tài)轉(zhuǎn)移圖；求各狀態(tài)的穩(wěn)態(tài)概率Wi； 計(jì)算該馬爾可夫信源的極限熵。(3+3+4=10分)陣為：0.80.200000.50.5P(1)=0.50.500000.20.8根據(jù)各態(tài)歷經(jīng)定理的有:p(S1)0.80根據(jù)各態(tài)歷經(jīng)定理的有:p(S1)0.800.50p(S2)0.200.50p(S3)00.500.5p(S4)00.500.8p(Sl)+p(S2)+p(S3)+p(S4)=lp(S1)p(S2)p(S3)p(S4)和 p(Si)0 (i=1,2,3,4)2)由狀態(tài)圖可以判斷，這是一個(gè)非周期不可閉集，具有各態(tài)歷經(jīng)性, 方法同樣可以判斷，存在狀態(tài)極限概率。其約束條件為：解得其極限概率分別為：p(S1)=p(S4)=5/14; p(S2)=p(S3)=2/143)由極限概率和狀態(tài)轉(zhuǎn)移概率就可以計(jì)算馬爾柯夫信源的極限熵:於 4 p (Si) p (Sj / Si) log p (Sj / Si) = 0.8bit / fuhaoi=1 j=13已知一個(gè)(7, 3)線性分組碼的生成矩陣為1)2)3)4)，求:求一致校驗(yàn)陣H； 求出碼字空間集合； 計(jì)算該線性分組碼的最小距離d.。min接收到的碼字為R1=0010100，如何判斷是否有錯(cuò)?(3+3+2+2=10