信息論與編碼理論

1、第3章信道容量習(xí)題解答3-1設(shè)二進(jìn)制對稱信道的轉(zhuǎn)移概率矩陣為2/3 1/31/3 2/3解：(1) 若 P(aJ 3/4,P(a2)1/4，求 H(X), H (Y), H (X |Y), H(Y|X)和 l(X;Y)。H(X)=P(ai )log p(aji=13 311log( )log() 0.8113(bit/ 符號)4 4443 2117p(b1)=p(a1)p(b1|aj+p(a2)p(b1|&)=4 3 4 3123 1125p(b2)=p(a1)p(b2|aj+p(a2)p(b2|a2)=4 3 4 312H(Y)=p(bj)log(bj)=j=10.9799(bit/

2、 符號)22H(Y|X)=p(q ,bj)logp(bj|ajp(bj|aj)logp(bj|aji,jjI log(|) 1 log(1) 0.9183(bit/符號)I(X;Y)=H(Y)H(Y|X)=0.97990.91830.0616(bit/ 符號)H(X|Y)=H(X)I(X;Y)=0.81130.06160.7497(bit/ 符號)(2)求該信道的信道容量及其達(dá)到信道容量時(shí)的輸入概率分布二進(jìn)制對稱信息的信道容量H(P)= -plog(p)-(1-p)log(1-p)1122C=1-H(P)=1+丄log( -) + log( )=0.0817(bit/符)3333BSC言道達(dá)到

3、信道容量時(shí)，輸入為等概率分布，即：0.5，0.5注意單位3-4設(shè)BSC信道的轉(zhuǎn)移概率矩陣為1)寫出信息熵H(Y)和條件熵H(Y|X)的關(guān)于H( 1)和H( 2)表達(dá)式，其中H( ) log (1 )log(1 )。2)根據(jù) H ( )的變化曲線，定性分析信道的容道容量，并說明當(dāng) 12的信道容量。解：(1)設(shè)輸入信號的概率頒布是 p,1-pp(b1)p(a1)p(b1 |a1)p(a2)(b1 |a2)p (11)(1 p) 2p(b2)p(a1)p(b2 |a1)p(a2)p(b2 |a2)p1(1p) (1 2)H(Y)p(b1)log p(b1)p(b2)logp(b2)p(1 1) (1

4、 p)2 log p(1 1)(1 p) 2 p 1(1 p) (1 2)log p 1(1 p)(1 2 )Hp(1 1) (1 p)2H(Y|X)2p(ai)p(bj |ai )logp(bj |ai)i ,j 1p (1 1)log(11) 1log( 1)(1 p)(1 2)log(12) 2 log( 2)p H( 1) (1 p) H( 2)(2) H ( ) 的變化曲線，是一個(gè)上凸函數(shù)，當(dāng)輸入等概率分布時(shí)達(dá)到信道 容量。C mp(ax)xI(X;Y) mp(ax)x H (Y ) H(Y |X)mp(ax)x H p (1 1) (1 p) 2 p H( 1) (1 p) H (

5、 2) 由于函數(shù)H (& )是一個(gè)凸函數(shù)，有一個(gè)性質(zhì)：f ( 1 (1 ) 2) f( 1) (1 ) f( 2)可知：C假設(shè)12 時(shí)此信道是一個(gè)二元對稱信道，轉(zhuǎn)移概率分布為：1 Q1信道容量：1 2C 1- log -(1- )log(1-)1-H()3-10電視圖像由30萬個(gè)像素組成，對于適當(dāng)?shù)膶Ρ榷龋粋€(gè)像素可取 10 個(gè)可辨別的亮度電平，假設(shè)各個(gè)像素的10個(gè)亮度電平都以等概率出現(xiàn)，實(shí) 時(shí)傳送電視圖像每秒發(fā)送30幀圖像。為了獲得滿意的圖像質(zhì)量，要求信號 與噪聲的平均功率比值為30dB,試計(jì)算在這些條件下傳送電視的視頻信號 所需的帶寬。解：I (X) log103.32bit/ 像

6、素1秒可以傳送的信息量為：3.3219bit/ 像素 30 10000像 素 30=2.9897 107bitC Blog(1 善),已知:10log1°(善)30dB1032.9897 107Blog(1 103)可得：B 2.9995 106HZ3-11 一通信系統(tǒng)通過波形信道傳送信息，信道受雙邊功率譜密度N°/20.5 10 8 W/Z Hz的加性高斯白噪聲的干擾，信息傳輸速率R 24 kbit/s，信號功率 P 1W1)若信道帶寬無約束，求信道容量；解：帶限的加性高斯白噪聲波形信道的信道容量為無帶寬約束時(shí):PS N0WPSC lim Ct limlog（1 ）ww

7、No FSNoW昱 loge 1.4427 108bit/sNo2）若信道的頻率圍為 0到3KHz求信道容量和系統(tǒng)的頻帶利用率 R/W （bps/Hz）（注：W為系統(tǒng)帶寬）；對同樣的頻帶利用率，保證系統(tǒng)可靠傳 輸所需的最小Eb/N。是多少dB?W=3KHZ在最大信息速率條件下，每傳輸1比特信息所需的信號能量記為&Eb=CSC W log(1_FLN0WWlog(1SNR)3000 log(11 10 83000)4.5074 104bps24kbit/s3KHz8bps/Hz33.47dBFs1N。3）若信道帶寬變?yōu)镹0C 1 10 8 4.5074 104 100KHz欲保持與2）相

8、同的信道容量，則此時(shí)的信噪比為多少dB？信號功率要變化多數(shù)dB?W 100KHZ4.5074 104bps Wlog(1 電)105log(1笙)N0WN0WSNR -F0.3667即:4.3654dBN°WFs' 0.3667 105 10 80.3667 10 3w信號功率的變化為:Fs'0.3667 10 310log1° 亠 10log1°34.3569dBFs1第4章無失真信源編碼習(xí)題參考答案4-1 :611111IaP(Si )li3(- -i 12416 161661111lBP(Si )li123i 1241616符號61111lC

9、P(Si)li123i 1241616符號61111IeP(Si)li12(-i 1241616(1) A、B、C E編碼是唯一可譯碼。(2) A、C E碼是及時(shí)碼。(3)唯一可譯碼的平均碼長如下:4-3 :(1)1丄)3碼元/信源符號16114 丄5 丄 62.125碼元/信源161611一4562.125碼元/信源16161 11) 42碼元/信源符號6 168H(X)=- p(x i)logp(x i)i=111 11 1=-_log - log - log22 44 81111 ,1- log - log - 8 1616 323211 11- log - log 6464 12812

10、81log1281128平均碼長：_ 6lP(s)hi 11111118163264128128)3碼元/信源符號所以編碼效率:H(X)0.6615(3)仙農(nóng)編碼:信源符號Si符號概率p(Si)加概率碼長碼字Si10102S21121042S313311084S41741110168115S55111103216S613161111106432S716371111110128641127S871111111128128費(fèi)諾碼:信源符號Si符號概率p(Si)編碼碼字碼長S112001S2140102S31801103S4丄16011104S5132110111105S6丄641101111106

11、S7112811011111107S811281111111174-5 :(1)霍夫曼編碼：對X的霍夫曼編碼如下:信符號編碼過程碼長碼源 符 號Si概率p(Si)字S0.20.2叩.26JF0.350.39J0.6101020.190.190.20.26y6.350聲91112S0.180.180.190.20 i/ 0.2610003S0.170.1710.18!00.1910013S0.150.1500.1710103S60.100 #.0.11101104S0.01101114l 0.2 20.19 20.183 0.17 3 0.15 3 0.1 4 0.01 42.72 碼元 /信源

12、符號7H(X)i 1Pi log Pi2.61碼元/符號H(X)2.610.9596l2.72Y的二元霍夫曼編碼:信 源 符 號Si符號 概率P(Si)編碼過程碼字碼 長S10.49丿0.490.490.490.49/0.490.49.0.51011S20.140.140.140.140.1410.230.280.4910003S30.140.140.140.140.140.14 /0.2310013S40.070.070.070.09f,0.140.14101004S50.070.070.07/r 0.07 丄0.09101014S60.040.0490500.07101114S70.02胃

13、0.03/00.041011015S80.0200.0210110006S90.0110110016平均碼長:r 0.49 10.14 3 2 0.07 4 2 0.04 4 0.02 5 0.02 6 0.01 62.23碼元/信源符9H(Y) Pi log Pi 2.31 碼元 / 符號i 1H (Y)2.31編碼效率：0.9914l 2.33仙農(nóng)編碼：對X的仙農(nóng)編碼:信源符號S符號概率P(Si)和概率碼長碼字S0.203000S0.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.997111

14、1110平均碼長:l 0.2 3 0.19 3 0.18 3 0.17 3 0.15 3 0.1 4 0.01 73.14碼兀/信源符H(X)l2.613.140.8312對Y的仙農(nóng)編碼:信源符號S符號概率P(Si)和概率碼長碼字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.9971111110平均編碼長度:l 0.49 2 0.14 2 0.07 4 2 0.04 5 0.02 6 2 0

15、.02 6 0.01 72.89碼元/信源符H(Y) 2.31編碼效率：一0 7993l 2.89費(fèi)諾編碼：對X的費(fèi)諾編碼:信源符號Si符號概率p(Si)編碼碼字碼長S10.200002S20.19100103S30.1810113S40.170102S50.15101103S60.1011011104S70.01111114平均編碼長度:l 0.2 2 0.19 3 0.18 3 0.17 2 0.15 3 0.1 4 0.01 42.74碼元/信源符號編碼效率：261 0.9526l 2.74對Y進(jìn)行費(fèi)諾編碼:信源符號Si符號概率p(Si)編碼碼字碼長S10.49001S20.140010

16、03S30.1411013S40.070011004S50.071111014S60.041011104S70.0210111105S80.021101111106S90.0111111116平均碼長:l 0.49 10.14 2 3 0.07 4 2 0.04 4 0.02 5 0.02 6 0.01 62.33碼元/信源符號編碼效率:H(Y) 2.310.9914l 2.33(4)由三種編碼的編碼效率可知：仙農(nóng)編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼 效率最高，費(fèi)諾碼居中。4-7 : 由三元編碼方式可知：R=t> B=R-i(K 2)+2由本題可知D=3,

17、K=8, R=2,所以，首先合并最后兩個(gè)信源概率，其中一種編碼 方式如下：信源符號S符號概率p(Si)編碼碼字碼 長S10.40.40.40.4001S20.20.20.2*0.4121S30.10.1.0.2廠0.22112S40.10.1/0.1彳122S50.05,0.1/0.121013S60.05/ 0.05f11023S0.050?0.05210004S80.051100144-21 :(1)符號概率分布區(qū)間00.250,0.2510.750.25,1由題目可知信源符號為:1011 0111 1011 0111p(s 1011 0111 1011 01110.00012371243

18、 12 1 4p(1) p(0) (3)G算術(shù)碼的碼長丨 log p(s)13由序列S的分布函數(shù)F( S)由二元整樹圖來計(jì)算：F(S) 13 23厶13 8 12310 13312 141 (：)(：) (；)(：)(；)(；)(；)4 44444444所以算術(shù)編碼為：0100 0011 0011平均碼長及編碼效率如下:1空160.8125碼元/符號H(S)p(1)log p(1) p(0)log p(0)0.8113 bit/ 符號H(S) 0.9985l(2)由于信源符號集中共有 2個(gè)元素，因此只需要log 21位二進(jìn)制數(shù)就可以表示其編碼，該符號集的編碼表如下:符號01編碼01按照分段規(guī)則

19、，分段為：1 0 11 01 111 011 0111短語數(shù)為7,可用n log 73位來表示段號；每個(gè)信源符號編碼長度為1，所以短語長度為：3+1=4,具體編碼過程如下:盹 1=1. 段號短語編碼110001200000311001140101015111011160111001701111101平均編碼長度：i 7 (31)1.75碼元/符16編碼效率為：H(S)0.8113 0 46361.755.21失真矩陣：d020p2d22)-2Dmin O,R(Dmin) H(X) H(1/2,1/2) log2 1bit/符號轉(zhuǎn)移矩陣:p2Dmax mnPidjPzd?" p

20、9;2j 1,2 i 1j 1,21 0m1n2 0此時(shí)，轉(zhuǎn)移矩陣:P0 1，R(Dmax)01R(D)定義域:0,-第6章信道編碼概述習(xí)題答案6-211極大似然譯碼規(guī)則譯碼時(shí)，由轉(zhuǎn)移概率矩陣可知：第一列中1，第二列中1，第三221列中丄為轉(zhuǎn)移概率的最大值，所以平均錯誤概率為:2Pe1 (1 丄)2 3 61)1 (16431)最小錯誤概率譯碼，輸入 x與輸出y的聯(lián)合概率分布為:1 1 14'61211124® 1211112,24,811111111E 2412824121224由工111由于-1124242可以看出最佳譯碼為最小錯誤概率譯碼，平均錯誤概率為6-4(1) 求

21、信息傳輸率；f log 4 1 “口Rbit/符號2根據(jù)信道的傳輸特性，可知可以輸出24=16種序列，可以分成 4個(gè)子集，分別為:a1=(0 0a2=(0 1a3=(1 0a4=(1 11 1)一(0 0 y2 21 1-)-(0 1 y2 21 1)(1 0 y2 2)1) - (1 1 y3 y 4)3 y 4)3 y 4)3 y 4)y3,y 4 (0 1)傳輸信道如下所示:(0 0(0 1(1 0(1 112)1)1)0000 00010010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 11111111000

22、 0 0 000 000 04444000011 1100 000 0 00444411110000000000 0 044441111000000000 0 0 044441 1譯碼規(guī)則為：f(y 1,y 2,y 3,y 4)=(y 1,y 2,二,二)i)0 i=1、2、3、42 2每個(gè)碼字引起錯誤的概率：pep( | i) p(f(r所以PeP( i)Pe 0C第7章線性分組碼習(xí)題答案1.已知一個(gè)(5, 3)線性碼C的生成矩陣為:11001G0110100111(1)求系統(tǒng)生成矩陣；(2)列出C的信息位與系統(tǒng)碼字的映射關(guān)系；(3) 求其最小Hamming距離，并說明其檢錯、糾錯能力；(4

23、) 求校驗(yàn)矩陣H;(5) 列出譯碼表，求收到 r=11101時(shí)的譯碼步驟與譯碼結(jié)果。解：(1)線性碼C的生成矩陣經(jīng)如下行變換：110011001101101將第2、3加到第1行011010011100111100111001101101將第勸卩到第2行010100011100111得到線性碼C的系統(tǒng)生成矩陣為10011Gs0101000111(2) 碼字c (Co，Ci， ,Cn 1)的編碼函數(shù)為c f (m) mo 1 0 0 1 1 mi 0 1 0 1 0 m2 0 0 1 1 1 生成了的8個(gè)碼字如下信息元系統(tǒng)碼字000000000010011101001010011011011001

24、0011101101001101100111111110(3) 最小漢明距離d=2，所以可檢1個(gè)錯，但不能糾錯。(4) 由 G In k，Ak (n k)，H Ak(nk)T，ln k】，得校驗(yàn)矩陣11110H10 10 1(5)消息序列 m=000,001,010,011,100,101,110,111，由 c=mGs得碼字序列co=OOOOO, C1=00111, C2=01010, C3=01101,所以將C4=10011, C5=10100, C6=11001, C7=11110則譯碼表如下：00000001110101001101100111010011001111101000010

25、11111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111當(dāng)接收到r =（11101）時(shí)，查找碼表發(fā)現(xiàn)它所在的列的子集頭為（01101）,它譯為C=01101。2 設(shè)（7, 3 ）線性碼的生成矩陣如下0101010G 00101111001101（1）求系統(tǒng)生成矩陣；（2）求校驗(yàn)矩陣；（3）求最小漢明距離；（4）列出伴隨式表。解：（1）生成矩陣G經(jīng)如下行變換010101010011010010111交換第1、行001011110

26、011010101010100110110011010010111交換第2、行°10101001010100010111得到系統(tǒng)生成矩陣:1001101Gs01010100010111 由 G In k，Ak（n k），H Ak （n k）T,ln k，得校驗(yàn)矩陣為110 10 0 010 10 10 0 H0 110 0 101 0 1 0 0 0 1(3) 由于校驗(yàn)矩陣 H的任意兩列線性無關(guān)，3列則線性相關(guān)，所以最小漢明距離 d=3。(4) (7, 3)線性碼的消息序列mF000,001,010,011,100,101,110,111，由 c=mGs得碼字序列：6=0000000

27、, C1=0010111，C2=0101010，C3=0111101, C4=1001101, c5=1011010，C6=1100111, C7=1110000。又因伴隨式有24=16種組合，差錯圖樣為1的有77種，17tT T差錯圖樣為 2的有21種，而由HrT HeT，則計(jì)算陪集首的伴隨式，構(gòu)造伴2隨表如下：伴隨式陪集首伴隨式陪集首000000000000101100100011011000000100110001001010010000011110011000011100100001100000110010000001000111001001000100000010010110100001001000000100011001010000010000001011000001103 .已知一個(gè)(6, 3)線性碼C的生成矩陣為:100101G010011 .001110(1)寫出它所對應(yīng)的監(jiān)督矩陣H；