信息論及編碼習(xí)題解答

1、信息論與編碼習(xí)題解答第一章1. 一位朋友很不贊成“通信的目的是傳送信息”及“消息中未知的成分才算是信息”這些說法。他舉例說：我多遍地欣賞梅蘭芳大師的同一段表演，百看不厭，大師正在唱的正在表演的使我愉快，將要唱的和表演的我都知道，照你們的說法電視里沒給我任何信息，怎么能讓我接受呢？請(qǐng)從信息論的角度對(duì)此做出解釋。（主要從狹義信息論與廣義信息論研究的內(nèi)容去理解和解釋）答：從狹義信息論角度，雖然將要表演的內(nèi)容觀眾已知，但是每一次演出不可能完全相同。而觀眾在欣賞的同時(shí)也在接受著新的感官和視聽享受。從這一角度來(lái)說，觀眾還是可以得到新的信息的。另一種解釋可以從廣義信息論的角度來(lái)分析，它涉及了信息的社會(huì)性、實(shí)

2、用性等主觀因素，同時(shí)受知識(shí)水平、文化素質(zhì)的影響。京劇朋友們?cè)谛蕾p京劇時(shí)也因?yàn)橹饔^因素而獲得了享受，因此屬于廣義信息論的范疇。2利用下圖（圖1.2）所示的通信系統(tǒng)分別傳送同樣時(shí)間（例如十分鐘）的重大新聞公告和輕音樂，它們?cè)诮邮斩烁鞣娇虻妮斎胫兴男畔⑹欠裣嗤?，為什么？圖1.2 通信系統(tǒng)的一般框圖答：重大新聞是語(yǔ)言，頻率為3003400Hz，而輕音樂的頻率為2020000Hz。同樣的時(shí)間內(nèi)輕音樂的采樣編碼的數(shù)據(jù)要比語(yǔ)音的數(shù)據(jù)量大，按碼元熵值，音樂的信息量要比新聞大。但是在信宿端，按信息的不確定度，信息量就應(yīng)分別對(duì)待，對(duì)于新聞與音樂的信息量大小在廣義上說，因人而異。第二章1一珍珠養(yǎng)殖場(chǎng)收獲240顆

3、外觀及重量完全相同的特大珍珠，但不幸被人用外觀相同但重量?jī)H有微小差異的假珠換掉1顆。（1）一人隨手取出3顆，經(jīng)測(cè)量恰好找出了假珠，問這一事件大約給出了多少比特的信息量；（2）不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說他用天平最多6次能找出，結(jié)果確是如此，問后一事件給出多少信息量；（3）對(duì)上述結(jié)果作出解釋。解：（1）從240顆珍珠中取3顆，其中恰好有1顆假珠的概率為：所以，此事件給出的信息量為：I= log2P = log280=6.32 (bit)（2）240顆中含1顆假珠，用天平等分法最多6次即可找到假珠，這是一個(gè)必然事件，因此信息量為0。（3）按照Shannon對(duì)信息量的定義，只

4、在事件含有不確定成分，才有信息量，并且不確定成分越大，信息量也越大，必然事件則沒有信息量。但是從廣義信息論的角度，如果那個(gè)人不知道用天平二分法找假珠，另一個(gè)告訴他這個(gè)方法，使他由不知道到知道，也應(yīng)該含有一定的信息量。2每幀電視圖像可以認(rèn)為是由3´105個(gè)象素組成，所有象素均獨(dú)立變化，且每一象素又取128個(gè)不同的亮度電平，并設(shè)亮度電平等概率出現(xiàn)。問每幀圖像含有多少信息量？如果一個(gè)廣播員在約10000個(gè)漢字的字匯中選取1000個(gè)字來(lái)口述此電視圖像，試問廣播員描述此圖像所廣播的信息量是多少（假設(shè)漢字字匯是等概率分布，且彼此獨(dú)立）？若要恰當(dāng)?shù)孛枋龃藞D像，廣播員在口述中至少需用多少漢字？解：由

5、于每一象素取128個(gè)不同的亮度電平，各個(gè)亮度電平等概率出現(xiàn)。因此每個(gè)亮度電平包含的信息量為I(X) = lb(1/128)=lb128=7 bit/像素每幀圖像中像素均是獨(dú)立變化的，因此每幀圖像信源就是離散亮度電平信源的無(wú)記憶N次擴(kuò)展。由此，每幀圖像包含的信息量為I(XN) = NI(X)= 3´105´7 =2.1´106 bit/幀廣播員在約10000個(gè)漢字中選取字匯來(lái)口述此電視圖像，各個(gè)漢字等概分布，因此每個(gè)漢字包含的信息量為I(Y) = lb(1/10000)=lb1000=13.29 bit/字廣播員述電視圖像是從這個(gè)漢字字匯信源中獨(dú)立地選取1000個(gè)字

6、進(jìn)行描述，因此廣播員描述此圖像所廣播的信息量是I(YN) = NI(Y)= 1000´13.29 =1.329 ´104 bit/字由于口述一個(gè)漢字所包含的信息量為I(Y)，而一幀電視圖像包含的信息量是I(XN)，因此廣播員要恰當(dāng)?shù)孛枋龃藞D像，需要的漢字?jǐn)?shù)量為：字3已知 X： 1, 0P(X)： p, 1 p（1）求證：H(X) = H(p)（2）求H(p)并作其曲線，解釋其含義。（1） 證明：H(X)= I(X1) +I(X2) = plbp (1p)lb (1p) =H(p)（2） 解：該H(p)曲線說明，當(dāng)0與1等概出現(xiàn)時(shí)，即p=0.5時(shí)，熵最大。當(dāng)p由0.5分別趨向

7、于0和1時(shí)，熵逐漸減小至0。4證明H(X3|X1X2) £ H(X2|X1)，并說明等式成立的條件。證明：設(shè)離散平穩(wěn)信源輸出的隨機(jī)符號(hào)序列為X1,X2,X3,。又設(shè),而且都取自于同一符號(hào)集，并滿足有在區(qū)域0，1內(nèi)設(shè)f(x)=xlogx, f(x)在0，1內(nèi)是型凸函數(shù)，所以滿足詹森不等式 其中現(xiàn)今,設(shè)其概率空間為，并滿足所以根據(jù)詹森不等式得所以上式對(duì)所有的取值都成立，所以因?yàn)?，所以上式兩邊相乘，等?hào)不變。有上式對(duì)所有都成立，所以對(duì)所有求和下式也成立因?yàn)?H(X3|X1X2) £ H(X3|X2)所以是平穩(wěn)信源 H(X3|X2) = H(X2|X1)得 H(X3|X1X2) &

8、#163; H(X2|X1)只有當(dāng)(對(duì)所有)時(shí)等式成立。5設(shè)有一概率空間，其概率分布為p1, p2, , pq，且p1>p2。若取， ，其中0 <2e £ p1 p2，而其它概率值不變。證明由此得到的新的概率空間的熵是增加的，并用熵的物理意義加以解釋。證明：令 得因?yàn)閒(x)=xlogx是型函數(shù)，根據(jù)型凸函數(shù)的定義有所以 即 同理得 以上兩不等式兩邊相加，不等號(hào)不變。所以得 6某辦公室和其上級(jí)機(jī)關(guān)的自動(dòng)傳真機(jī)均兼有電話功能。根據(jù)多年來(lái)對(duì)雙方相互通信次數(shù)的統(tǒng)計(jì)，該辦公室給上級(jí)機(jī)關(guān)發(fā)傳真和打電話占的比例約為3:7，但發(fā)傳真時(shí)約有5%的次數(shù)對(duì)方按電話接續(xù)而振鈴，撥電話時(shí)約有1%

9、的次數(shù)對(duì)方按傳真接續(xù)而不振鈴。求：（1）上級(jí)機(jī)關(guān)值班員聽到電話振鈴而對(duì)此次通信的疑義度；（2）接續(xù)信道的噪聲熵。解：設(shè)發(fā)傳真和打電話分別為事件X1與X2,對(duì)方按傳真和按電話接續(xù)分別為事件Y1和Y2,則 P(X1)=30%,P(X2)=70% P(Y1|X1)=95%, P(Y2|X1)=5%, P(Y1|X2)=1%, P(Y2|X2)=99% P(X1Y1)=0.285, P(X1Y2)=0.015 P(X2Y1)=0.007, P(X2Y2)=0.693P(Y1)= P(X1Y1)+ P(X2Y1)= 0.292 P(Y2)=1 P(Y1)= 0.708 H(X)= P(X1)lb P(X

10、1) P(X2)lb P(X2) =0.8814 bit/符號(hào) H(Y)= P(Y1)lb P(Y1) P(Y2)lb P(Y2) =0.8713 bit/符號(hào) H(XY)= =1.0239 bit/兩個(gè)信符 I(X;Y)=H(X)+H(Y) H(XY)=0.7288 bit/信符 （1）聽到電話振鈴的疑義度H(X|Y2)= P(X1Y2)lb P(X1Y2) P(X2Y2)lb P(X2Y2)= 0.4575 bit/信符 （2）接續(xù)信道的噪聲熵H(Y|X)=H(Y)I(X;Y)=0.1425 bit/信符7四個(gè)等概分布的消息M1，M2，M3，M4被送入如圖所示的信道進(jìn)行傳輸，通過編碼使M1

11、 = 00，M2 = 01，M3 =10，M4 =11。求輸入是M1和輸出符號(hào)是0的互信息量是多少？如果知道第2個(gè)符號(hào)也是0，這時(shí)帶來(lái)多少附加信息量？圖2.6解：信源P(M1)= P(M2)= P(M3)= P(M4)=1/4, 信道為二元對(duì)稱無(wú)記憶信道，消息Mi與碼字一一對(duì)應(yīng)，所以設(shè)設(shè)接收序列為Y=(y1y2)接收到第一個(gè)數(shù)字為0，即y1=0。那么，接收到第一個(gè)數(shù)字0與M1之間的互信息為因?yàn)樾诺罏闊o(wú)記憶信道，所以同理，得輸出第一個(gè)符號(hào)是y1=0時(shí)，有可能是四個(gè)消息中任意一個(gè)第一個(gè)數(shù)字傳送來(lái)的。所以故得 接收到第二個(gè)數(shù)字也是0時(shí)，得到關(guān)于M1的附加互信息為 其中 同理，因?yàn)樾诺朗菬o(wú)記憶信道，所

12、以 得 輸出端出現(xiàn)第一個(gè)符號(hào)和第二個(gè)符號(hào)都為0的概率為所以 比特得附加互信息為 比特8證明若隨機(jī)變量X，Y，Z構(gòu)成馬氏鏈，即XYZ，則有ZYX。證明：因?yàn)?X,Y, Z)是馬氏鏈，有P(z|xy)=P(z|y),對(duì)所有成立，而P(x|yz)=P(xyz)/P(yz)= P(z|xy) P(xy)/ P(y) P(z|y)= P(z|xy) P(y) P(x|y)/ P(y) P(z|y)對(duì)所有成立故得P(x|yz)=P(x|y) 對(duì)所有成立所以(Z,Y, X)也是馬氏鏈。習(xí)題（第3章）1發(fā)出二重符號(hào)序列消息的信源熵為H(X2)，而一階馬爾可夫信源的信源熵為H(X/X)。試比較這兩者的大小，并說

13、明原因。2 設(shè)隨機(jī)變量序列(XYZ)是馬氏鏈，且X：a1, a2, , ar，Y： b1, b2, , bs，Z： c1, c2, , cL。又設(shè)X與Y之間的轉(zhuǎn)移概率為p(bj /ai) ( i =1, 2, , r；j =1, 2, , s)；Y與Z之間的轉(zhuǎn)移概率為p(ck /bj) ( j =1, 2, , s；k =1, 2, , L)。試證明X與Y之間的轉(zhuǎn)移概率為3 有一個(gè)馬爾可夫信源，已知，試畫出該信源的香農(nóng)線圖，并求出信源熵。一步轉(zhuǎn)移矩陣為P，可得 故 所以，信源熵為4一個(gè)馬爾科夫鏈的基本符號(hào)為0，1，2三種，他們以等概率出現(xiàn)，且具有相同的轉(zhuǎn)移概率，沒有任何固定約束，試（1）畫出單

14、純馬爾科夫鏈信源的香農(nóng)線圖，并求穩(wěn)定狀態(tài)下的信源熵H1。（2）畫出二階馬爾科夫鏈信源的香農(nóng)線圖，并求穩(wěn)定狀態(tài)下的信源熵H2。解：（1）由已知得 則香農(nóng)線圖如下 穩(wěn)定時(shí) bit/符號(hào)（2）二階馬爾可夫信源，初始狀態(tài)有個(gè)，等概分布 bit/符號(hào)010210111220212200圖中每條路徑概率均為1/35某一階馬爾可夫信源的狀態(tài)轉(zhuǎn)移如圖3.4所示，信源符號(hào)集為X：0, 1, 2，并定義。試求：（1） 信源的極限熵H¥；（2） p取何值時(shí)H¥取最大值。圖3.4解：（1）一步轉(zhuǎn)移矩陣為P，可得 計(jì)算得則得所以，信源熵為（2）因?yàn)?求其對(duì)p的一階導(dǎo)數(shù)令所以當(dāng)p=2/3時(shí)，信源的極限

15、熵達(dá)到最大值。6設(shè)隨機(jī)變量序列X=X1X2¼XN通過某離散信道X; P(Y/X); Y，其輸出序列為Y=Y1Y2¼YN。試證明若（1）p (bjN / ai1 ai1aiN；bj1 bj2bjN 1) = p (bjN / aiN)；（2）p (bj1 bj2bjN 1 / ai1 ai1aiN) = p (bj1 bj2bjN 1 / ai1 ai1aiN1)則該信道的轉(zhuǎn)移概率為證明：7設(shè)信源X的N次擴(kuò)展信源X=X1X2¼XN通過信道X; P(Y/X); Y，其輸出序列為Y=Y1Y2¼YN。試證明（1） 當(dāng)信源為無(wú)記憶信源，即X1X2¼XN之

16、間統(tǒng)計(jì)獨(dú)立時(shí)，有；（2） 當(dāng)信道無(wú)記憶時(shí)，有；（3） 當(dāng)信源、信道均為無(wú)記憶時(shí)，有；（4） 用熵的概念解釋以上3種結(jié)果。證明：（1）設(shè)信道輸入連續(xù)型隨機(jī)序列X=(X1X2XN),輸出也是連續(xù)型隨機(jī)序列Y=(Y1Y2YN)，信道的傳遞概率密度函數(shù)為因?yàn)樾旁礋o(wú)記憶，即隨機(jī)序列X中各分量彼此互相獨(dú)立，因而有 可得 另外 其中R為實(shí)數(shù)集。因?yàn)樗?因此，其中（1）式是根據(jù)詹森不等式。（2）式是因?yàn)?所以 所以證得 （2）設(shè)信道輸入連續(xù)型隨機(jī)序列，輸出連續(xù)型隨機(jī)序列。因?yàn)樾诺罒o(wú)記憶，有 X和Y的平均互信息 而 與前半題同理得 因此 根據(jù)詹森不等式，有 其中因?yàn)?由此證得 （3） 設(shè)X和Y的一個(gè)取值為 信

17、源無(wú)記憶時(shí)滿足 （1）而信道無(wú)記憶時(shí)滿足 （2）及 所以當(dāng)信道和信源都是無(wú)記憶時(shí)，不但上面（1）和（2）式滿足，同時(shí)滿足同理 . (4)根據(jù)平均互信息的表達(dá)式得 所以信道和信源都是無(wú)記憶的。將(2),(3),(4)式代入得 因?yàn)閄i(i=1,2,N)取自同一信源X，而又通過同一信道，輸出Yi(i=1,2,N)，Yi也屬同一信源Y, 又信道的傳遞概率與i無(wú)關(guān)（時(shí)不變信道），即 其中 得 所以 第章習(xí)題1. 簡(jiǎn)述信源譯碼的錯(cuò)誤擴(kuò)展現(xiàn)象。答：由于信道的干擾作用，造成了一定量的錯(cuò)誤，這些錯(cuò)誤在譯碼時(shí)又造成了更多的錯(cuò)誤，這就是通信譯碼的錯(cuò)誤擴(kuò)展現(xiàn)象。2. 針對(duì)某種應(yīng)用，給出一種你認(rèn)為是有價(jià)值的減小信源譯

18、碼錯(cuò)誤擴(kuò)展的方法。答：在信源編碼的每個(gè)碼字施加和碼字等長(zhǎng)的附加位，編碼時(shí)將要寫入的信息在新碼字上順序?qū)憙蛇?，譯碼時(shí)先譯前半段，若碼長(zhǎng)無(wú)誤則譯后半段，若前后不一致則要求重發(fā)，在帶寬充足的條件下可以采用這種方法。3. 試說明已有的解決信源譯碼錯(cuò)誤擴(kuò)展問題的方法，簡(jiǎn)述其基本思路及利弊。答：信道編碼的方法優(yōu)點(diǎn)：加入了糾錯(cuò)碼，減少了譯碼錯(cuò)誤的可能性，減少了發(fā)生錯(cuò)誤擴(kuò)展的概率。缺點(diǎn)：需要對(duì)發(fā)送的碼字加入冗余，是一種降低效率來(lái)?yè)Q取可靠性的方法。4. 某通信系統(tǒng)使用文字字符共10 000個(gè)，據(jù)長(zhǎng)期統(tǒng)計(jì)，使用頻率占80%的共有500個(gè)，占90%的有1000個(gè)，占99%的有4000個(gè)，占99.9%的7000個(gè)。（

19、1）求該系統(tǒng)使用的文字字符的熵；（2）請(qǐng)給出該系統(tǒng)一種信源編碼方法并作簡(jiǎn)要評(píng)價(jià)。解：(1) (2)可以使用huffman編碼的方法，為使壓縮效果理想，可以使用擴(kuò)展信源的方法。5. 一通信系統(tǒng)傳送的符號(hào)只有3個(gè)，其使用概率分別為0.2、0.3和0.5，但傳送時(shí)總是以3個(gè)符號(hào)為一個(gè)字，故該系統(tǒng)的信源編碼以字為基礎(chǔ)并采用二進(jìn)制霍夫曼編碼。根據(jù)字的概率大小，編碼結(jié)果為：概率在(0，0.020)，采用6比特；在(0.020，0.045 ，采用5比特，但允許其中一個(gè)用4比特；在(0.045，0.100，在0.100以上，采用3比特。求該種信源編碼的效率。解：假設(shè)三個(gè)符號(hào)分別為a b c，則p(a)=0.2

20、,p(b)=0.3,p(c)=0.5 下面對(duì)每個(gè)字可能出現(xiàn)的情況加以討論。3個(gè)符號(hào)都為a 則 編6bit碼，共1種3個(gè)符號(hào)都為b 則 編5bit碼，共1種3個(gè)符號(hào)都為c 則 編3bit碼，共1種3個(gè)符號(hào)有2個(gè)a，1個(gè)b 則 編6bit碼，共3種3個(gè)符號(hào)有2個(gè)a，1個(gè)c 則 編5bit碼，共3種3個(gè)符號(hào)有2個(gè)b，1個(gè)a 則 編6bit碼，共3種3個(gè)符號(hào)有2個(gè)b，1個(gè)c 則 編5bit碼，共3種3個(gè)符號(hào)有2個(gè)c，1個(gè)a 則 編4bit碼，共3種3個(gè)符號(hào)有2個(gè)c，1個(gè)b 則 編4bit碼，共3種3個(gè)符號(hào)有1個(gè)a，1個(gè)b,1個(gè)c 則 編5bit碼，共6種平均碼長(zhǎng)為4.488 bit/字 h1 = R1

21、 /C = 4.455/4.488 = 99.26%6. 設(shè)有一個(gè)無(wú)記憶信源發(fā)出符號(hào)A和B，已知p(A) = 1/4, p(B) = 3/4。（1）計(jì)算該信源熵；（2）設(shè)該信源改為發(fā)出二重符號(hào)序列消息的信源，采用費(fèi)諾編碼方法，求其平均信息傳輸速率；（3）又設(shè)該信源改為發(fā)三重序列消息的信源，采用霍夫曼編碼方法，求其平均信息傳輸速率。解：（1）該離散無(wú)記憶信源的熵為（2）費(fèi)諾編碼消息符號(hào)序號(hào)(i)消息概率pi第一次分解第二次分解第三次分解二進(jìn)制代碼組碼組長(zhǎng)度biBB9/16(9/16)001AB3/16(7/16)1(3/16) 0102BA3/16(4/16) 1(3/16)01103AA1/1

22、6(1/16) 11113編碼的平均長(zhǎng)度為 碼元/符號(hào)平均傳輸速率為 ? （3）霍夫曼編碼0 BBB 27/640100 BAA9/640 (18/64)0 1.0101 BAB9/6411110 ABB9/640 (37/64)11100 AAB3/640 (6/64) 0(19/64) 111101 ABA3/64 1 (10/64)111110 BAA3/640 (1/16) 111111 AAA1/641 編碼的平均長(zhǎng)度為 碼元/符號(hào)平均傳輸速率為 7. 已知一個(gè)信源包含8個(gè)符號(hào)消息，它們的概率分布如下表：ABCDEFGH0.10.180.40.050.060.10.070.04（1）

23、 信源每秒鐘內(nèi)發(fā)出一個(gè)符號(hào)，求該信源的熵及信息傳輸速率；（2）對(duì)這8個(gè)符號(hào)作二進(jìn)制碼元的霍夫曼編碼，寫出各個(gè)代碼組，并求出編碼效率。解：（1）該信源的熵信息傳輸速率R=2.55bit/s（2）霍夫曼編碼C 0.40B 0.180 1.0A 0.100.230F 0.1010.3710.611G 0.070 0.13E 0.061 0.191D 0.050 0.091H 0.041編碼結(jié)果：CBAF G ED H01101001110 10101011 1110 11111平均碼長(zhǎng)為： 所以編碼效率為8. 設(shè)信道基本符號(hào)集合A =a1, a2, a3, a4, a5，它們的時(shí)間長(zhǎng)度分別為t1 =

24、1, t2 =2, t3 =3, t4 =4, t5 =5 （各碼元時(shí)間）用這樣的信道基本符號(hào)編成消息序列，且不能出現(xiàn)這四種符號(hào)相連的情況。（1）求這種編碼信道的信道容量；（2）若信源的消息集合X = x1, x2, , x7，它們的出現(xiàn)概率分別是P(x1)=1/2, P(x2)=1/4, P(x3)=1/8, , P(x6) = P(x7)=1/64, 試求按最佳編碼原則利用上述信道來(lái)傳輸這些消息時(shí)的信息傳輸速率；（3）求上述信源編碼的編碼效率。解：（1）這是一個(gè)有固定約束的不均勻編碼的信道，有約束條件（即不能出現(xiàn)），可以把a(bǔ)1, a2作為狀態(tài)1，a3, a4, a5作為狀態(tài)2，得香農(nóng)線圖時(shí)

25、間長(zhǎng)度分別為b11=,b12 (a3)=3, b12 (a4)=4, b12 (a5)=5, b21(a1)=1, b21(a2)=2, b22(a3)=3, b22(a5)=5,寫出行列式，可得特征方程為解方程可得所以 bit/碼元時(shí)間（2） 因?yàn)橐?guī)定a1 a2不能連用，故不能用和做碼字，根據(jù)最佳編碼的兩個(gè)原則，及單譯可譯定理，出現(xiàn)概率大的消息用短碼的原則，可用x1x2x3 x4x5x6 x71/21/4 1/8 1/16 1/32 1/64 1/64a3a4 a1a3a5 a1 a4a2a3 a2 a4344555 6（3）編碼效率為 h = R /C =0.541/0.675=80%第、

26、章習(xí)題51 比特/符號(hào) 比特 命題得證。52 比特/符號(hào) 比特/符號(hào) 比特/符號(hào) R=0.049*1000=49 比特53 比特/符號(hào) 比特/符號(hào) 比特/符號(hào) 比特/符號(hào)54 比特/符號(hào)55 （1）由圖可知這是個(gè)對(duì)稱信道，當(dāng)輸入符號(hào)等概時(shí)，, , 1/8 1/8 0 0 P(xy)= 0 1/8 1/8 0 0 0 1/8 1/8 1/80 0 1/8 對(duì)任意x均成立 所以，C=1 比特/符號(hào)。 （2）由圖可知，信道亦為對(duì)稱信道， P(xy)=P(x)P(y|x)= 1/6 1/6 1/12 1/12 1/12 1/12 1/61/6 =0.0817 比特/符號(hào) （3）同上，信道為對(duì)稱離散信道

27、， P(xy)= 1/6 1/9 1/18 1/18 1/6 1/9 1/9 1/18 1/6 比特/符號(hào)。56 設(shè) 據(jù)對(duì)稱性 由，代入所以 奈特/符號(hào)。57 該信道可看成4個(gè)BSC信道串聯(lián)而成， 1- 1- = 1-4(1-)1-2(1-) 4(1-)1-2(1-) 4(1-)1-2(1-) 1-4(1-)1-2(1-) 級(jí)聯(lián)后的信道仍是對(duì)稱信道，可代入公式： 其中-4(1-)1-2(1-) 1-1-4(1-)1-2(1-) 則4(1-)1-2(1-)log4(1-)1-2(1-)+1-4(1-)1-2(1-)log4(1-)1-2(1-) 代入=，得C=0.9949 所以信道容量C=C*1

28、024=1018.8 kbps。58 由圖可知信道為對(duì)稱信道，且信源的符號(hào)消息等概分布，因此 比特/符號(hào)。59 后驗(yàn)概率 1/4 1/6 1/12 P(xy)= 1/24 1/8 1/12 1/12 1/24 1/8 由 P(y)=3/8 1/3 7/24 所以 2/3 1/2 2/7 P(x|y)= 1/9 3/8 2/7 2/9 1/8 3/7根據(jù)最小錯(cuò)誤概率準(zhǔn)則，應(yīng)作如下譯碼： 錯(cuò)誤概率為 510 （1）（2）（3）511 ？512 （1）對(duì)信源四個(gè)消息進(jìn)行編碼，選擇碼長(zhǎng)n=4，這組碼為 C : () i=(1,2) 編碼后的信息傳輸率 比特/符號(hào) （2）設(shè)接收序列 根據(jù)信道的傳輸特性，

29、輸入序列共有16個(gè)，正好分成4個(gè)互不相交的子集，每個(gè)碼字只傳輸?shù)狡渲袑?duì)應(yīng)的一個(gè)子集： (0 0 1/2 1/2)à(0 0 ) (0 1 1/2 1/2)à(0 1 ) (1 0 1/2 1/2)à(1 0 ) (1 1 1/2 1/2)à(1 1 ) 所以根據(jù)選擇的譯碼規(guī)則 =(1/2 1/2) 正好將接收序列譯成所發(fā)送的碼字，可計(jì)算每個(gè)碼字引起的錯(cuò)誤概率 所以有。513(1) P(y)=7/12 5/12P(x|y)= 6/7 3/5 1/7 2/5 又 比特/符號(hào) 所以 比特/符號(hào)(2) 此信道為二元對(duì)稱信道，所以信道容量 比特/符號(hào)根據(jù)二元對(duì)稱信

30、道的性質(zhì)可知，輸入符號(hào)為等概分布，即P(0)=P(1)=1/2時(shí)信道的信息傳輸率才能達(dá)到這個(gè)信道的容量值。514 （1）由P(y)=1/2 1/4+1/4a 1/4-1/4a所以（2）(3) 6.1 (1) 收到傳真的概率為8/(4+8+3+1)*2/(7+1+2)=1/10 I=-log1/10=3.3 比特 （2）可采取壓縮編碼，安最佳編碼原則編碼等措施 （3）編碼時(shí)碼長(zhǎng)盡可能長(zhǎng)，這樣根據(jù)香濃第二定理，總存在一種編碼，只要碼長(zhǎng)足夠長(zhǎng)，總存在一種編碼，是錯(cuò)誤概率任意小。最好結(jié)合實(shí)際分析如何克服隨機(jī)，突發(fā)干擾。 （4）C=Blog(1+S/N)=2.048log(1+)=8.34Mbps，不失

31、真條件下，該信道允許最大信息傳輸速率為8.34Mbps。6.2 （1） 比特/樣值 （2）對(duì)樣值進(jìn)行256級(jí)量化，當(dāng)其服從均勻分布時(shí)，信源有最大熵，H=log256=8比特/符號(hào) （3） 所以 。（4）S/N=36dB, C=5.17Mbps 所以。6.3 (1) 比特/樣值 （2） 冗余度= （3） 其中C=9.6K B=1.2288*2Mbps, 得S/N=-25.7dB (4) =2.45766.4 由于P(x)=1/2=,所以電壓為1V(-1)V上的均勻分布， 又 ,所以 10=2，=5 =2*（1/2）lb(4Ps)= lb(4*1)=2=10 bit/s6.5 又,所以 10=2，

32、=5所以6.6 6.7 所以 B=.6.8 (1)(2)又 而 ， 所以 S/N=, 所以=9.97B B=66.9 所以 所以 P=.6.10 =所以 （2）利用關(guān)系式 ，所以式（2）變?yōu)?，為一常量?.11 = 再由逐步分布積分得 H(X)=-2AlnA-2Aln2+2A. 因?yàn)椋?A=1 A=1/2 所以 H(X)=1 奈特/自由度6.12 （1） =b =-logbp(x)dx-2b = 因?yàn)閜(x)dx=1，所以b=。 故H(X)=2/3loge+loga-log3(2) 若Y=X+A，則 , 所以 H(Y)=2/3loge+loga-log3(3) 若Y=2X ，則，所以H(Y

33、)=H(X)-log1/2=2/3loge+loga-log3/2。6.13 6.14 (1)(2) 所以 B=(3) 所以 S/N=120第七章 習(xí)題1. 設(shè)某二址接入信道，輸入X1, X2和輸出Y的條件概率為P(Y/X1X2 )，其值是： p (0/00) = 1 e p (0/01) =1/2 p (0/10) =1/2 p (0/11) =e p (1/00) =e p (1/01) =1/2 p (1/10) =1/2 p (1/11)=1e其中e <1/2，試求其容量界限。2. 設(shè)某廣播信道，其輸入X和輸出Y1、Y2之間的條件概率P(Y1/X)和P(Y2/X)的具體值是：其中

34、e 1 <1/2, e 2 <1/2，試求其容量界限。3. 計(jì)算圖7.12中二址接入信道的容量。圖7.16第8章 習(xí)題1. 設(shè)輸入符號(hào)表與輸出符號(hào)表為X=Y=0, 1, 2, 3，且輸入信號(hào)的分布為p(X = i) = 1/4, i = 0, 1, 2, 3設(shè)失真矩陣為求和及。2. 設(shè)無(wú)記憶信源，接收符號(hào)AY =1/2, 1/2，失真矩陣。試求：Dmax和Dmin及達(dá)到Dmax和Dmin時(shí)的轉(zhuǎn)移概率矩陣。, 在時(shí)，由于，所以在時(shí)，由于，所以3. 三元信源的概率分別為p(0) = 0.4, p(1) = 0.4, p(2) = 0.2，失真函數(shù)dij為：當(dāng)i = j時(shí)，dij = 0

35、；當(dāng)i ¹ j時(shí)，dij = 1 (i, j = 0, 1, 2)，求信息率失真函數(shù)R(D)。，由定義知：，平均失真度一定與試驗(yàn)信道的平均錯(cuò)誤概率Pe有關(guān)，即根據(jù)保真度準(zhǔn)則，應(yīng)有Pe £ D根據(jù)Fano不等式H(X/Y) £ H (Pe) + Pe log (r1)4. 設(shè)有一連續(xù)信源，其均值為0，方差為，熵為H(X)，定義失真函數(shù)為“平方誤差”失真，即。證明其率失真函數(shù)滿足下列關(guān)系式：當(dāng)輸入信源為高斯分布時(shí)等號(hào)成立。證明：（1） 證明上界：連續(xù)信源R(D)函數(shù)是在約束條件下，求平均互信息：引入?yún)⒘縎和待定函數(shù)。在失真不超過D時(shí)，為下確界的試驗(yàn)信道滿足由泛函分析中

36、的變分法求的條件極值令由于以上規(guī)定了下確界，則（1）設(shè)集合則有（2）令其中由（1）得即當(dāng)時(shí)，且，得由（2）（3）兩式，有（4）由對(duì)數(shù)得換底公式，有（5）若要（1）式等號(hào)成立，則等效于（5）式等號(hào)成立。令則然后再求二階導(dǎo)數(shù)，得由于是得概率密度函數(shù)且所以，即（5）式右邊為上凸函數(shù)，在的S上確極大值，有代入得（6）由式（5）得即（2） 證明上界設(shè)信道的傳遞函數(shù)的概率為：它是已知時(shí)y的概率分布，即均值為，方差為的高斯分布，其中。設(shè)，由于所以輸出信號(hào)，于是時(shí)均值為零，方差為的隨即變量。當(dāng)方差受限時(shí)，高斯隨即變量的差熵最大，有當(dāng)且僅當(dāng)是高斯分布時(shí)，上式等號(hào)成立。綜上所述，5. 隨機(jī)變量X服從對(duì)稱指數(shù)分布，

37、失真函數(shù)為d (x, y) = | x y |，求信源的R(D)。，令，得且得對(duì)進(jìn)行傅立葉變換由，得且當(dāng)時(shí)6. 設(shè)有平穩(wěn)高斯信源X (t)，其功率譜為，失真度量取，容許的樣值失真為D。試求：（1） 信息率失真函數(shù)R(D)；（2） 用一獨(dú)立加性高斯信道（帶寬為，限功率為P，噪聲的雙邊功率譜密度為）來(lái)傳送上述信源時(shí)，最小可能方差與的關(guān)系。（1）對(duì)于時(shí)間 連續(xù)的平穩(wěn)高斯信源，當(dāng)功率譜密度已知時(shí)，在本題中即（2）信道容量為bit/s由定理可知，當(dāng)時(shí)，可以采用最佳編碼，其硬氣的錯(cuò)誤小于等于D。取,求得最小均方誤差D。令，得時(shí)，時(shí)，時(shí)，由于所以如下圖：7. 某工廠的產(chǎn)品合格率為99%，廢品率為1%。若將一

38、個(gè)合格產(chǎn)品作為廢品處理，將損失1元；若將一個(gè)廢品當(dāng)作合格產(chǎn)品出廠，將損失100元；若將合格品出廠，廢品報(bào)廢，不造成損失。試分析質(zhì)量管理中各種情況造成的損失及付出的代價(jià)。解根據(jù)題意有信源空間： 好（合格） 廢（廢品） P(好)=0.99 P(廢)=0.01選擇失真函數(shù)為d(好，好)=0 d(廢，廢)=0 d(好，廢)=10 d(廢，好)=100失真矩陣為可將產(chǎn)品檢驗(yàn)分成如下4種情況：全部產(chǎn)品都當(dāng)合格品，全部產(chǎn)品都當(dāng)廢品，完美的檢驗(yàn)和允許出錯(cuò)的檢驗(yàn)。下面分別進(jìn)行討論。情況1全部產(chǎn)品不經(jīng)檢驗(yàn)而出廠都當(dāng)合格品。把這一過程看作是一個(gè)“信道”，其“傳遞概率”為P(好/好)=1P(廢/好)=0P(好/廢)=

39、1P(廢/廢)=0信道矩陣為這種情況的平均損失，即平均失真度，為 =P(好)×P(好/好) ×d(好,好)+ P(好)×P(廢/好) ×d(好,廢)+P(廢)×P(好/廢話) ×d(廢,好)+ P(廢)×P(廢/廢) ×d(廢, 廢)=0.01´1´100=1元/個(gè)情況2全部產(chǎn)品不經(jīng)檢驗(yàn)全部報(bào)廢都當(dāng)廢品這時(shí)的信道傳輸概率為P(好/好)=0P(廢/好)=1P (好/廢)=0P (廢/廢)=1信道矩陣為平均失真度為 =P(好)×P(好/好) ×d(好,好)+ P(好)×

40、P(廢/好) ×d(好,廢)+P(廢)×P(好/廢) ×d(廢,好)+ P(廢)×P(廢/廢) ×d(廢, 廢)=0.99´1´1=0.99元/個(gè) 全部報(bào)廢造成損失小于全部出廠造成的損失。情況3經(jīng)過檢驗(yàn)?zāi)苷_無(wú)誤地判斷合格品和廢品完美的檢驗(yàn)這相當(dāng)于無(wú)噪信道的情況，信道矩陣為平均失真度為即這種情況不會(huì)另外造成損失。 情況4 檢測(cè)時(shí)允許有一定的錯(cuò)誤非完美的檢驗(yàn)設(shè)檢驗(yàn)的正確率為p，則信道的傳輸概率為P(好/好)=p P(廢/好)=1-p P(好/廢)=1-p P(廢/廢)=p信道矩陣為平均失真度為 =P(好)×P(廢/好

41、) ×d(好, 廢)+P(廢)×P(好/廢) ×d(廢,好)=0.99´(1-p)´1+0.01´p´100 = 1.99(1-p)元/個(gè)8. 設(shè)輸入符號(hào)表為X= 0, 1 ，輸出符號(hào)表為Y=0, 1。定義失真函數(shù)為：d (0, 0) = d (1,1) = 0d (0, 1) = d (1,0) = 1試求失真矩陣D。9. 某二元信源X的信源空間為其中w < 1/2，其失真矩陣為（1） 試求和；（2） 試求及；（3） 試求；（4） 寫出取得的試驗(yàn)信道的各傳遞概率；（5） 當(dāng)d = 1時(shí)，寫出與試驗(yàn)信道相對(duì)應(yīng)的反向試驗(yàn)

42、信道的信道矩陣。解： （1）（因?yàn)椋?）（3） 由于令，則得到得到D=0時(shí)，D=d時(shí)，所以（4）（5）d=1時(shí)，第9章 習(xí)題1. 對(duì)(2, 1), (3, 1), (4, 1), (5, 1)，討論其糾檢錯(cuò)能力，對(duì)用完備譯碼、不完備譯碼以及不完備譯碼ARQ等方法譯碼，求譯碼錯(cuò)誤概率。解： 對(duì)(2, 1)碼，若d=1，能糾檢錯(cuò)0個(gè)；若d=2,能檢1個(gè)錯(cuò)，糾0個(gè)錯(cuò) 對(duì)(3, 1)碼，若d=1，能糾檢錯(cuò)0個(gè)；若d=2,能檢1個(gè)錯(cuò)，糾0個(gè)錯(cuò)；若d=3，能檢2個(gè)錯(cuò)，糾1個(gè)錯(cuò)對(duì)(4, 1)碼，若d=1，能糾檢錯(cuò)0個(gè)；若d=2,能檢1個(gè)錯(cuò)，糾0個(gè)錯(cuò)；若d=3，能檢2個(gè)錯(cuò)，糾1個(gè)錯(cuò)，若d=4,能檢3個(gè)錯(cuò)，糾

43、1個(gè)錯(cuò)對(duì)(5, 1)碼，若d=1，能糾檢錯(cuò)0個(gè)；若d=2,能檢1個(gè)錯(cuò)，糾0個(gè)錯(cuò)；若d=3，能檢2個(gè)錯(cuò)，糾1個(gè)錯(cuò)；若d=4,能檢3個(gè)錯(cuò)，糾1個(gè)錯(cuò)；若d=5,能檢4個(gè)錯(cuò)，糾2個(gè)錯(cuò)2. 為什么d =2的(n, n1)碼能檢測(cè)奇數(shù)個(gè)錯(cuò)誤？解:d=2，能檢1個(gè)錯(cuò)，又因?yàn)?n, n1)碼是奇偶校驗(yàn)碼，即對(duì)于奇校驗(yàn)碼：偶校驗(yàn)碼：當(dāng)出現(xiàn)一個(gè)錯(cuò)或者奇數(shù)個(gè)錯(cuò)時(shí)，在接收端奇校驗(yàn)碼：偶校驗(yàn)碼：都能檢測(cè)到錯(cuò)誤，故d =2的(n, n1)碼能檢測(cè)奇數(shù)個(gè)錯(cuò)誤。3. 設(shè)C = 11100, 01001, 10010, 00111是一個(gè)二元碼，求碼C的最小距離d。解：d(11100, 01001)=3 d(11100, 100

44、10)=3 d(11100, 00111)=4d(01001, 10010)=4 d(01001, 00111)=3 d(10010, 00111)=3故碼C的最小距離d=34設(shè)C = 00000000, 00001111, 00110011, 00111100是一個(gè)二元碼。（1） 計(jì)算碼C中所有碼字之間的距離及最小距離；（2） 在一個(gè)二元碼中，如果把某一個(gè)碼字中的0和1互換，即0換為1，1換為0，所得的字稱為此碼字的補(bǔ)。所有碼字的補(bǔ)構(gòu)成的集合稱為此碼的補(bǔ)碼。求碼C的補(bǔ)碼以及補(bǔ)碼中所有碼字之間的距離和最小距離，它們與（1）中的結(jié)果有什么關(guān)系？（3） 把（2）中的結(jié)果推廣到一般的二元碼。 解：（

45、1） d(00000000, 00001111)=4 d(00000000, 00110011)=4 d(00000000, 00111100)=4 d(00001111, 00110011)=4d(00001111, 00111100)=4 d(00110011,00111100)=4故碼C的最小距離d=4（2） 碼C的補(bǔ)碼是 11111111, 11110000, 11001100, 11000011 d(11111111, 11110000)=4 d(11111111, 11001100)=4 d(11111111, 11000011)=4 d(11110000, 11001100)=4

46、d(11110000, 11000011)=4 d(11001100, 11000011)=4故C補(bǔ)碼的最小距離d=4（3）推廣到一般的二元碼也有以上的結(jié)論設(shè)碼C中任意兩碼字的距離為d, 即兩碼字有d位不同，n-d位相同。變補(bǔ)后，仍有d位不同，n-d位相同，所以任意兩碼字的距離不變，最小距離當(dāng)然不變。習(xí)題（第10章）1. 已知11次本原多項(xiàng)式p (x) = x11 + x2 + 1，試求GF(211)中元素b =a 89及b 2, b 3, b 4, b 5的最小多項(xiàng)式。解：的共軛元為：2. 求碼長(zhǎng)為n的q元重復(fù)碼的生成矩陣。若n=2,q=2，則有224個(gè)碼字生成矩陣對(duì)于碼長(zhǎng)為n的q元重復(fù)碼，

47、生成矩陣是維單位矩陣。3. 一個(gè)二元(11, 24, 5)碼是線性碼嗎？為什么？是線性碼。13>114. 證明對(duì)于一個(gè)二元線性碼L一定滿足下列條件之一：（1） 碼L中所有碼字具有偶數(shù)重量；（2） 碼L中一半的碼字具有偶數(shù)重量，另一半的碼字具有奇數(shù)重量。證明：（反證法）奇奇數(shù)重量，偶偶數(shù)重量；由題意假設(shè)線性碼有個(gè)碼字，其中個(gè)是偶數(shù)重量，個(gè)是奇數(shù)重量。且若1）偶數(shù)個(gè)數(shù)大于奇數(shù)個(gè)數(shù)，則；若2）偶數(shù)個(gè)數(shù)小于奇數(shù)個(gè)數(shù)，則。情況1）成立，則第 個(gè)偶數(shù)重量的碼字與奇數(shù)重量的碼字相加時(shí)，結(jié)果應(yīng)是第個(gè)奇數(shù)重量的碼字。這與情況1）相矛盾。同理，可以推出情況2）時(shí)的矛盾。由此可得，原假設(shè)不成立。原命題得證。5

48、. 設(shè)二元線性碼L的生成矩陣為，求碼L的最小距離。因?yàn)樗浴?. 設(shè)3元線性碼L的生成矩陣為，求碼長(zhǎng)L的最小距離并且證明L是完備的。題中由生成矩陣知，該線性碼是碼，陪集首的個(gè)數(shù)為，能糾正3個(gè)錯(cuò)誤。而1bit錯(cuò)誤圖樣的個(gè)數(shù)為，又3<4，所以線性碼是完備的。7. 設(shè)二元線性碼L的生成矩陣為，建立碼L的標(biāo)準(zhǔn)陣并且對(duì)字11111和10000分別進(jìn)行譯碼。共個(gè)碼字。標(biāo)準(zhǔn)陣為譯碼得8. 設(shè)5元線性碼L的生成矩陣為。（1） 確定碼L的標(biāo)準(zhǔn)型生成矩陣；（2） 確定碼L的標(biāo)準(zhǔn)型校驗(yàn)矩陣；（3） 求碼L的最小距離。9. 設(shè)有碼如下所示：信息 碼字00 0000001 0110110 1011111 11010（1） 找出生成矩陣G與監(jiān)督矩陣H；（2） 在二元對(duì)稱信道下給出最大似然譯碼的譯碼表；（3） 求正確譯碼的概率。（1） 設(shè)信息位，碼字由編碼規(guī)則（2）譯碼表（3）正確譯碼的概率為：10. 建立二元漢明碼Ham (7,4)的包含陪集首和伴隨式的伴隨表，并對(duì)收到的字0000011，1111