信息論與編碼姜丹第三版答案

1、信息論與編碼習題參考答案第一章 單符號離散信源信息論與編碼作業(yè)是74頁，1.1的（1）（5），1.3,1.4,1.6,1.13,1.14還有證明熵函數(shù)的連續(xù)性、擴展性、可加性1.1同時擲一對均勻的子，試求：(1)“2和6同時出現(xiàn)”這一事件的自信息量；(2)“兩個5同時出現(xiàn)”這一事件的自信息量；(3)兩個點數(shù)的各種組合的熵；(4)兩個點數(shù)之和的熵； (5)“兩個點數(shù)中至少有一個是1”的自信息量。解： (3)信源空間：X(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)P(X)1/362/362/362/362/362/36X(2,2)(2,3)(2,4)(2,5)(2,6)P(x)1/

2、362/362/362/362/36X(3,3)(3,4)(3,5)(3,6)P(x)1/362/362/362/36X(4,4)(4,5)(4,6)P(x)1/362/362/36X(5,5)(5,6)(6,6)P(x)1/362/361/36(4)信源空間：X23456789101112P(x)1/362/363/364/365/366/365/364/363/362/361/36(5) 1.2如有6行、8列的棋型方格，若有兩個質點A和B，分別以等概落入任一方格內(nèi)，且它們的坐標分別為（Xa，Ya）, （Xb，Yb）,但A，B不能同時落入同一方格內(nèi)。（1） 若僅有質點A，求A落入任一方格的平

3、均信息量；（2） 若已知A已落入，求B落入的平均信息量；（3） 若A，B是可辨認的，求A，B落入的平均信息量。解：1.3從大量統(tǒng)計資料知道,男性中紅綠色盲的發(fā)病率為7%,女性發(fā)病率為0.5%.如果你問一位男士：“你是否是紅綠色盲？”他的回答可能是：“是”，也可能“不是”。問這兩個回答中各含有多少信息量？平均每個回答中各含有多少信息量？如果你問一位女士，則她的答案中含有多少平均信息量？解：1.4某一無記憶信源的符號集為0，1，已知（1） 求符號的平均信息量；（2） 由1000個符號構成的序列，求某一特定序列（例如有m個“0”,（1000-m）個“1”）的自信量的表達式；（3） 計算（2）中序列的

4、熵。解：1.5設信源X的信源空間為：求信源熵，并解釋為什么H(X)log6，不滿足信源熵的極值性。解：1.6為了使電視圖象獲得良好的清晰度和規(guī)定的對比度，需要用5105個像素和10個不同的亮度電平，并設每秒要傳送30幀圖象，所有的像素是獨立的，且所有亮度電平等概出現(xiàn)。求傳輸此圖象所需要的信息率（bit/s）。解：1.7設某彩電系統(tǒng)，除了滿足對于黑白電視系統(tǒng)的上述要求外，還必須有30個不同的色彩度。試證明傳輸這種彩電系統(tǒng)的信息率要比黑白系統(tǒng)的信息率大2.5倍左右。證:1.8每幀電視圖像可以認為是由3105個像素組成，所以像素均是獨立變化，且每像素又取128個不同的亮度電平，并設亮度電平是等概出現(xiàn)

5、。問每幀圖像含有多少信息量？若現(xiàn)在有一個廣播員，在約10000個漢字中選1000個字來口述這一電視圖像，試問若要恰當?shù)孛枋龃藞D像，廣播員在口述中至少需要多少漢字？解:1.9給定一個概率分布和一個整數(shù)m，。定義，證明：。并說明等式何時成立？證：1.10找出兩種特殊分布:p1p2p3pn，p1p2p3pm,使H(p1,p2,p3,pn)=H(p1,p2,p3,pm)。解：1.15兩個離散隨機變量X和Y，其和為ZXY，若X和Y統(tǒng)計獨立，求證：(1) H(X)H(Z), H(Y)H(Z)(2) H(XY)H(Z)證明：第二章 單符號離散信道2.1設信源通過一信道，信道的輸出隨機變量Y的符號集,信道的矩

6、陣：試求：(1) 信源X中的符號a1和a2分別含有的自信息量；(2) 收到消息Yb1，Yb2后，獲得關于a1、a2的互交信息量：I(a1;b1)、I(a1;b2)、I(a2;b1)、I(a2;b2)；(3) 信源X和信宿Y的信息熵；(4) 信道疑義度H(X/Y)和噪聲熵H(Y/X)；(5) 接收到消息Y后獲得的平均互交信息量I(X;Y)。解:2.2某二進制對稱信道，其信道矩陣是：設該信道以1500個二進制符號/秒的速度傳輸輸入符號。現(xiàn)有一消息序列共有14000個二進制符號，并設在這消息中p(0)= p(1)=0.5。問從消息傳輸?shù)慕嵌葋砜紤]，10秒鐘內(nèi)能否將這消息序列無失真的傳送完。解:2.3

7、有兩個二元隨機變量X和Y，它們的聯(lián)合概率為PX=0,Y=0=1/8，PX=0,Y=1=3/8，PX=1,Y=1=1/8，PX=1,Y=0=3/8。定義另一隨機變量Z=XY，試計算：(1) H(X),H(Y),H(Z),H(XZ),H(YZ),H(XYZ);(2) H(X/Y),H(Y/X),H(X/Z),H(Z/X),H(Y/Z),H(Z/Y),H(X/YZ),H(Y/XZ),H(Z/XY);(3) I(X;Y),I(X;Z),I(Y;Z),I(X;Y/Z),I(Y;Z/X),I(X;Z/Y)。解:2.4已知信源X的信源空間為某信道的信道矩陣為： b1 b2 b3 b4試求：(1)“輸入a3，

8、輸出b2的概率”；(2)“輸出b4的概率”；(3)“收到b3條件下推測輸入a2”的概率。解：2.5已知從符號B中獲取關于符號A的信息量是1比特，當符號A的先驗概率P(A)為下列各值時，分別計算收到B后測A的后驗概率應是多少。(1) P(A)=10-2；(2) P(A)=1/32；(3) P(A)=0.5。解：2.6某信源發(fā)出8種消息，它們的先驗概率以及相應的碼字如下表所列。以a4為例，試求：消息a1a2a3a4a5a6a7a8概率1/41/41/81/81/161/161/161/16碼字000001010011100101110111(1) 在W4011中，接到第一個碼字“0”后獲得關于a4

9、的信息量I(a4;0)；(2) 在收到“0”的前提下，從第二個碼字符號“1”中獲取關于a4的信息量I(a4;1/0)；(3) 在收到“01”的前提下，從第三個碼字符號“1”中獲取關于a4的信息量I(a4;1/01)；(4) 從碼字W4011中獲取關于a4的信息量I(a4;011)。解：2.13把n個二進制對稱信道串接起來，每個二進制對稱信道的錯誤傳輸概率為p(0p1)，試證明：整個串接信道的錯誤傳輸概率pn=0.51-(1-2p)n。再證明：n時，limI(X0;Xn)=0。信道串接如下圖所示：X0X1XnX2BSCIIBSCNBSCI解：2.18試求下列各信道矩陣代表的信道的信道容量：(1)

10、(2)(3)解：2.19設二進制對稱信道的信道矩陣為：(1) 若p(0)=2/3，p(1)=1/3，求H(X)，H(X/Y)，H(Y/X)和I(X;Y)；(2) 求該信道的信道容量及其達到的輸入概率分布。解：2.20設某信道的信道矩陣為試求：(1) 該信道的信道容量C；(2) I(a3;Y)；(3) I(a2;Y)。解:2.21設某信道的信道矩陣為試求：(1)該信道的信道容量C；(2)I(a1;Y)；(3)I(a2;Y)。解:2.22設某信道的信道矩陣為試該信道的信道容量C；解:2.23求下列二個信道的信道容量，并加以比較(其中0p,q0，則對每個j1，2，r都存在狀態(tài)極限概率：(證明詳見:p

11、171175)3.6設某齊次馬氏鏈的第一步轉移概率矩陣為：試求：(1) 該馬氏鏈的二步轉移概率矩陣；(2) 平穩(wěn)后狀態(tài)“0”、“1”、“2”的極限概率。解：3.7設某信源在開始時的概率分布為PX0=0=0.6;P X0=1=0.3; P X0=2=0.1。第一個單位時間的條件概率分布分別是：P X1=0/ X0=0=1/3; PX1=1/ X0=0=1/3; P X1=2/ X0=0=1/3;P X1=0/ X0=1=1/3; P X1=1/ X0=1=1/3; P X1=2/ X0=1=1/3;PX1=0/ X0=2=1/2; P X1=1/ X0=2=1/2; P X1=2/ X0=2=0

12、.后面發(fā)出的Xi概率只與Xi-1有關，有P(Xi/Xi-1)=P(X1/ X0)(i2)試畫出該信源的香農(nóng)線圖，并計算信源的極限熵H。解：香農(nóng)線圖如下：2011/21/21/31/31/31/31/31/33.8某一階馬爾柯夫信源的狀態(tài)轉移如下圖所示，信源符號集為X：0,1,2，并定義012p/2p/2p/2p/2p/2p/2(1) 試求信源平穩(wěn)后狀態(tài)“0”、“1”、“2”的概率分布p(0)、p(1)、p(2)；(2) 求信源的極限熵H；(3) p取何值時H取得最大值。解：3.9某一階馬爾柯夫信源的狀態(tài)轉移如下圖所示，信源符號集為X：0,1,2。試求：(1)試求信源平穩(wěn)后狀態(tài)“0”、“1”、“

13、2”的概率分布p(0)、p(1)、p(2)；(2)求信源的極限熵H；(3)求當p=0,p=1時的信息熵，并作出解釋。ppp012解:3.10設某馬爾柯夫信源的狀態(tài)集合S：S1S2S3，符號集X：123。在某狀態(tài)Si(i=1,2,3)下發(fā)發(fā)符號k(k=1,2,3)的概率p(k/Si) (i=1,2,3; k=1,2,3)標在相應的線段旁,如下圖所示.(1) 求狀態(tài)極限概率并找出符號的極限概率;(2) 計算信源處在Sj(j=1,2,3)狀態(tài)下輸出符號的條件熵H(X/Sj);(3) 信源的極限熵H.2:1/4S1S2S33:1/22:1/21:11:1/23:1/4解:3.12下圖所示的二進制對稱信

14、道是無記憶信道,其中,試寫出N=3次擴展無記憶信道的信道矩陣P.0 0 p X Y p1 1 解:第五章 多維連續(xù)信源與信道5.8設X()是時間函數(shù)x(t)的頻譜,而函數(shù)在T1tT2區(qū)間以為的值均為零.試證:(頻域抽樣定理,證明詳見p263-p265)5.9設隨機過程x(t)通過傳遞函數(shù)為K()的線性網(wǎng)絡,如下圖所示.若網(wǎng)絡的頻寬為F,觀察時間為T.試證明:輸入隨機過程的熵h(X)和輸出隨機過程的熵h(Y)之間的關系為:網(wǎng)絡K()x(t)y(t)(證明詳見p283-p287)5.11證明:加性高斯白噪聲信道的信道容量: 信息單位/N維其中N=2FT,2X是信號的方差(均值為零), 2N是噪聲的

15、方差(均值為零).再證:單位時間的最大信息傳輸速率 信息單位/秒(證明詳見p293-p297)5.12設加性高斯白噪聲信道中,信道帶寬3kHz,又設(信號功率+噪聲功率)/噪聲功率=10dB.試計算改信道的最大信息傳輸速率Ct.解:5.13在圖片傳輸中,每幀約有2.25106個像素,為了能很好的重現(xiàn)圖像,需分16個量度電平,并假設量度電平等概率分布,試計算每分鐘傳輸一幀圖片所需信道的帶寬(信噪功率比為30dB).解:5.14設電話信號的信息率為5.6104比特/秒.在一個噪聲功率譜為N0=510-6mW/Hz,限頻F、限輸入功率P的高斯信道中傳送,若F=4kHz,問無差錯傳輸所需的最小功率P是

16、多少W?若F則P是多少W?解:5.15已知一個高斯信道,輸入信噪功率比為3dB,頻帶為3kHz,求最大可能傳送的信息率是多少?若信噪比提高到15dB,求理論上傳送同樣的信息率所需的頻帶.解:5.17設某加性高斯白噪聲信道的通頻帶足夠寬(F),輸入信號的平均功率Ps=1W,噪聲功率譜密度N0=10-4W/Hz,若信源輸出信息速率Rt=1.5104比特/秒.試問單位時間內(nèi)信源輸出的信息量是否全部通過信道?為什么?解:第六章 無失真信源編碼6.3設平穩(wěn)離散有記憶信源XX1X2XN,如果用r進制符號集進行無失真信源編碼.試證明當N時,平均碼長(每信源X的符號需要的碼符號數(shù))的極限值:其中,Hr表示r進

17、制極限熵.證明:6.4設某信源S:s1,s2,s3,s4,s5,s6,其概率分布如下表所示,表中也給出了對應的碼1,2,3,4,5,6.(1)試問表中哪些碼是單義可譯碼?(2)試問表中哪些碼是非延長碼?(3)求出表中單義可譯碼的平均碼長.sipiW(1)W(2)W(3)W(4)W(5)W(6)s11/200000000s21/400101100110100s31/8010011110001110101s41/160110111111000011110110s41/321000111111110000011011111s61/321010111111111100000011101011解:(1)

18、W(1)是定長非奇異碼,單義可譯,W(2)是延長碼,單義可譯, W(3)是即時碼,單義可譯;(2) W(1)、W(3)是非延長碼;(3)6.5某信源S的信源空間為:(1) 若用U:0,1進行無失真信源編碼,試計算平均碼長的下限值;(2) 把信源S的N次無記憶擴展信源SN編成有效碼,試求N=2,3,4時的平均碼長;(3) 計算上述N=1,2,3,4,這四種碼的信息率. 解:對其進行Huffman編碼:碼長編碼信符010101信符概率10S220.64210S210.163110S120.163111S110.08碼長編碼信符信符概率010101010110S2220.5123100S2210.1

19、283111S2120.1283110S1220.128511100S112010.032511101S1210.032511110S211010.032511111S1110.008碼長編碼信符信符概率0.59040.38560.18080.08840.20480.20480.10240.05120.05120.01280.05120.014410S22220101010101010101010101010101010.40963100S22210.10243101S22120.102441100S21220.102441101S12220.10246111000S21120.0256611

20、1001S21210.02566111010S22110.02566111010S12210.02566111100S12120.02566111101S11220.025671111100S11120.006471111101S11210.006471111110S12110.0064811111110S21110.0064811111111S11110.00016(3)6.6設信源S的信源空間為符號集U:0,1,2,試編出有效碼,并計算其平均碼長.解:進行Huffman編碼:r=3,q=8,因為(q-r)mod(r-1)=5mod2=10,所以插入m=(r-1)- (q-r)mod(r-1

21、)=2-1=1個虛假符號,令其為S9,則:碼長編碼信符信符概率10S30120120120120.311S10.2220S40.2221S20.13220S50.053221S60.0542220S70.0542221S80.0542222S9（不使用）06.7設信源S的N次擴展信源SN,用霍夫曼編碼法對它編碼,而碼符號U: 1,2,r ,編碼后所得的碼符號可以看作一個新的信源試證明:當N時,.證明:6.8設某企業(yè)有四種可能出現(xiàn)的狀態(tài)盈利、虧本、發(fā)展、倒閉,若這四種狀態(tài)是等概率的,那么發(fā)送每個狀態(tài)的消息量最少需要的二進制脈沖數(shù)是多少?又若四種狀態(tài)出現(xiàn)的概率分別是:1/2,1/8,1/4,1/8

22、,問在此情況下每消息所需的最少脈沖數(shù)是多少?應如何編碼?解:設S:S1=“盈利”,S2=“虧本”,S3=“發(fā)展”,S4=“倒閉”,(1)若四種情況等概率出現(xiàn)時,即p(S1)=p(S2)=p(S3)=p(S4)=0.25時,用脈沖來表示各信息可視為對信源S進行編碼,由平均碼長界限定理知:所以發(fā)送每個狀態(tài)的信息最少需要2個二進制脈沖.(2) p(S1)=1/2,p(S2)=1/8,p(S3)=1/4,p(S4)=1/8時,由平均碼長界限定理:所以此情況下每消息所需的最少脈沖數(shù)是1.75個.達到此下限時要求各消息對應碼長ni與出現(xiàn)概率p(Si)關系為:p(Si)=2-ni,則n1=1,n2=3,n3

23、=2,n4=3.對信源進行Huffman編碼:碼長編碼信符信符概率10S11/21/2011/2210S3011/4011/41/23100S21/81/43101S21/8可見上面編碼符號最小碼長條件,可使發(fā)送每信息的脈沖數(shù)最少.6.9設某信源的信源空間為:試用U:0,1作碼符號集,采取香農(nóng)編碼方法進行編碼,并計算其平均碼長.解:碼長編碼信符信符概率10s11/21/21/21/21/2011/2210s21/41/41/4011/4011/41/23110s31/81/81/81/81/441110s41/16011/16011/161/8511110s5011/321/321/16611

24、1110s61/641/326111111s71/64第七章抗干擾信道編碼7.4設有一離散信道，其信道矩陣為：(1) 當信源X的概率分布為(a1)2/3，(a2)(a3)1/6時，按最大后驗概率準則選擇譯碼函數(shù)，并計算其平均錯誤譯碼概率Pemin(2) 當信源是等概信源時，按最大似然譯碼準則選擇譯碼函數(shù)，并計算其平均錯誤譯碼概率Pemin解：7.5某信道的輸入符號集X：0，1/2，1，輸出符號集Y：0，1，信道矩陣為：現(xiàn)有四個消息的信源通過這信道，設信息等概出現(xiàn)。若對信源進行編碼，我們選這樣一種碼：C:(x1,x2,1/2,1/2)，xi=0,1(i=1,2)其碼長n=4，并選取這樣的譯碼原則

25、：(y1,y2,y3,y4)=(y1,y2,1/2,1/2)(1) 這樣的編碼后信息傳輸效率等于多少？(2) 證明在選用的編碼規(guī)則下，對所有碼字有Pe0。解：7.6考慮一個碼長為4的二進制碼，其碼字為w1=0000；w2=0011；w3=1100；w4=1111。若碼字送入一個二進制對稱信道（其單符號的誤傳概率為p，p0.01），而碼字的輸入是不等概率的，其概率為：p(w1)=1/2，p(w2)=1/8，p(w3)=1/8，p(w4)=1/4試找出一種譯碼規(guī)則使平均錯誤概率Pemin=Pe。解：由于信道為二進制對稱信道，所以先驗概率等于后驗概率，且p錯誤傳遞概率p。試選擇譯碼函數(shù)，并使平均錯誤

26、概率Pe=Pemin，寫出Pemin的表達式。解： 000 001 010 100 011 101 110 111因為正確傳遞概率p錯誤傳遞概率p，所以選擇譯碼函數(shù)如下：F(000)=F(010)=F(100) =F(001)=000F(111)=F(011)=F(101) =F(110)=F(111)=1117.9設離散無記憶信道的輸入符號集X：0，1，輸出符號集Y：0，1，2，信道矩陣為：若某信源輸出兩個等概消息s1和s2，現(xiàn)在用信道輸入符號集中的符號對s1和s2進行信道編碼，以w1=00代表s1，w2=11代表s2。試寫出能使平均錯誤譯碼概率Pe=Pemin的譯碼規(guī)則，并計算Pemin。

27、解：7.10設某信道的信道矩陣為：其輸入符號等概分布，在最大似然譯碼準則下，有三種不同的譯碼規(guī)則，試求之，并計算出它們對應的平均錯誤概率。解：輸入符號等概分布，在最大似然譯碼準則下，有三種不同的譯碼規(guī)則:(1) F(b1)=a1，F(xiàn)(b2)=a1，F(xiàn)(b3)=a2(2) F(b1)=a1，F(xiàn)(b2)=a2，F(xiàn)(b3)=a2(3) F(b1)=a1，F(xiàn)(b2)=a3，F(xiàn)(b3)=a2第八章 限失真信源編碼8.1設信源X的概率分布P(X):p(a1), p(a2), ,p(ar) ,失真度為d (ai, bj)0,其中(i=1,2,r;j=1,2,s).試證明:并寫出取得的試驗信道的傳輸概率選取的原則,其中(證明詳見:p468-p470)8.2設信源X的概率分布P(X):p(a1), p(a2), ,p(ar) ,失真度為d(ai, bj)0,其中(i=1,2,r;j=1,2,s).試證明:并寫出取得的試驗信道傳遞概率的選取原