信息論與編碼習(xí)題解答(待校200812)

（有問題請(qǐng)更正并通知xiezg@）第二章信息的度量一珍珠養(yǎng)殖場收獲240顆外觀及重量完全相同的特大珍珠，但不幸被人用外觀相同但重量僅有微小差異的假珠換掉1顆。（1）一人隨手取出3顆，經(jīng)測量恰好找出了假珠，問這一事件大約給出了多少比特的信息量；（2）不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說他用天平最多6次能找出，結(jié)果確是如此，問后一事件給出多少信息量；（3）對(duì)上述結(jié)果作出解釋。解：（1）從240顆珠子中取3顆，含1顆假珠的概率為（2）240顆中含1顆假珠，用天平等分法最多6次即可找到假珠，是必然事件，因此信息量為0。（3）按照shannon對(duì)信息量的定義，只有事件含有不確知成分，才有信息量，且不確知成分越大，信息量越大，必然事件則沒有信息量。但從廣義信息論來說，如果那人不知用天平二分法找假珠，另一人告之此事，使他由不知到知，也應(yīng)該含有一定的信息量。2．每幀電視圖像可以認(rèn)為是由3105個(gè)象素組成，所有象素均獨(dú)立變化，且每一象素又取128個(gè)不同的亮度電平，并設(shè)亮度電平等概率出現(xiàn)。問每幀圖像含有多少信息量？如果一個(gè)廣播員在約10000個(gè)漢字的字匯中選取1000個(gè)字來口述此電視圖像，試問廣播員描述此圖像所廣播的信息量是多少（假設(shè)漢字字匯是等概率分布，且彼此獨(dú)立）？若要恰當(dāng)?shù)孛枋龃藞D像，廣播員在口述中至少需用多少漢字？解：設(shè)電視圖像每個(gè)像素取128個(gè)不同的亮度電平，并設(shè)電平等概率出現(xiàn)，則每個(gè)像素亮度含有的信息量為比特/像素一幀中像素均是獨(dú)立變化的，則每幀圖像信源就是離散亮度信源的無記憶N次擴(kuò)展信源。得每幀會(huì)圖像含有的信息量為比特/每幀廣播口述時(shí)，廣播員是從10000個(gè)漢字字匯中選取的，假設(shè)漢字字匯是等概率分布的，則漢字字匯中每個(gè)漢字含有的信息量比特/字廣播員口述電視圖像是從此漢字字匯信源中獨(dú)立地選取1000個(gè)字來描述的。所以，廣播員描述此幀圖像所廣播的信息量為比特/千字若廣播員仍從此漢字字匯信源Y中獨(dú)立地選取漢字來描述電視圖像，每次口述一個(gè)漢字含有信息量是H(Y)，每幀電視圖像含有的信息量是，則廣播員口述此圖像至少需要的漢字?jǐn)?shù)等于字3．已知 X：1,0P(X)：p,1–p(1)求證：H(X)=H(p)(2)求H(p)并作其曲線，解釋其含義。（1）證明（2）H(p)H(p)10.510p該H(p)曲線說明，當(dāng)0與1等概出現(xiàn)時(shí)，即p=0.5時(shí)，熵最大。當(dāng)p由0.5分別趨向于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)镠(X3|X1X2)H(X3|X2)所以是平穩(wěn)信源H(X3|X2)=H(X2|X1)得H(X3|X1X2)H(X2|X1)只有當(dāng)(對(duì)所有)時(shí)等式成立。5．設(shè)有一概率空間，其概率分布為{p1,p2,…,pq}，且p1>p2。若取，，其中0<2證明：令得因?yàn)閒(x)=－xlogx是型函數(shù)，根據(jù)型凸函數(shù)的定義有所以即同理得以上兩不等式兩邊相加，不等號(hào)不變。所以得6．某辦公室和其上級(jí)機(jī)關(guān)的自動(dòng)傳真機(jī)均兼有電話功能。根據(jù)多年來對(duì)雙方相互通信次數(shù)的統(tǒng)計(jì)，該辦公室給上級(jí)機(jī)關(guān)發(fā)傳真和打電話占的比例約為3:7，但發(fā)傳真時(shí)約有5%的次數(shù)對(duì)方按電話接續(xù)而振鈴，撥電話時(shí)約有1%的次數(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.015P(X2Y1)=0.007,P(X2Y2)=0.693P(Y1)=P(X1Y1)+P(X2Y1)=0.292P(Y2)=1－P(Y1)=0.708H(X)=－P(X1)lbP(X1)－P(X2)lbP(X2)=0.8814bit/符號(hào)H(Y)=－P(Y1)lbP(Y1)－P(Y2)lbP(Y2)=0.8713bit/符號(hào)H(XY)==1.0239bit/兩個(gè)信符I(X;Y)=H(X)+H(Y)－H(XY)=0.7288bit/信符（1）聽到電話振鈴的疑義度H(X|Y2)=－P(X1Y2)lbP(X1Y2)－P(X2Y2)lbP(X2Y2)=0.4575bit/信符（2）接續(xù)信道的噪聲熵H(Y|X)=H(Y)－I(X;Y)=0.1425bit/信符7．四個(gè)等概分布的消息M1，M2，M3，M4被送入如圖所示的信道進(jìn)行傳輸，通過編碼使M1=00，M2=01，M3=10，M4=11。求輸入是M1和輸出符號(hào)是0的互信息量是多少？如果知道第2個(gè)符號(hào)也是0，這時(shí)帶來多少附加信息量？圖2.6解：信源P(M1)=P(M2)=P(M3)=P(M4)=1/4,信道為二元對(duì)稱無記憶信道，消息Mi與碼字一一對(duì)應(yīng)，所以設(shè)設(shè)接收序列為Y=(y1y2)接收到第一個(gè)數(shù)字為0，即y1=0。那么，接收到第一個(gè)數(shù)字0與M1之間的互信息為因?yàn)樾诺罏闊o記憶信道，所以同理，得輸出第一個(gè)符號(hào)是y1=0時(shí)，有可能是四個(gè)消息中任意一個(gè)第一個(gè)數(shù)字傳送來的。所以故得接收到第二個(gè)數(shù)字也是0時(shí)，得到關(guān)于M1的附加互信息為其中同理，因?yàn)樾诺朗菬o記憶信道，所以得輸出端出現(xiàn)第一個(gè)符號(hào)和第二個(gè)符號(hào)都為0的概率為所以比特得附加互信息為比特8．證明若隨機(jī)變量X，Y，Z構(gòu)成馬氏鏈，即X→Y→Z，則有Z→Y→X。證明：因?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)也是馬氏鏈。第三章離散信源1.由于，即可以看做是先發(fā)出一個(gè)符號(hào)，再在此基礎(chǔ)上發(fā)出一個(gè)與前一符號(hào)相關(guān)的符號(hào)，而,第二個(gè)符號(hào)可以看做為具有一階馬爾可夫性，故有。2.由轉(zhuǎn)移到可以認(rèn)為遍歷了每個(gè)，故，即有成立。3.香農(nóng)圖略由題轉(zhuǎn)移概率為，由馬爾可夫趨于穩(wěn)定時(shí)頻率分布不變，故得，即又由代入解得，，又，，，故H=1/2*lb3/2+1/4*lb34香農(nóng)圖略由題，由得，故H1=lb3,對(duì)二階馬爾可夫鏈有狀態(tài)為00，01，02，10，11，12，20，21，22，且P（0|00）=P（1|00）=P（2|00）=P（0|01）=P（1|01）=P（2|01）=P（0|02）=P（1|02）=P（2|02）=1/3,由,H2=9*1/9*1/3*lb3=2/3*lb35由于，由圖知，由得，，即。（2）對(duì)p求導(dǎo)得，令，得，得6記，，則由條件（1）得，由條件（2）得，故，代入上邊兩式整理有，進(jìn)行遞推有，7由于，當(dāng)信源為無記憶信源時(shí)，，故得信道為無記憶時(shí)，，故得當(dāng)信源信道都無記憶時(shí)有，故有當(dāng)信源信道中有一個(gè)有記憶或兩個(gè)都有記憶時(shí)，信號(hào)之間或信道對(duì)信號(hào)存在干擾，故信宿對(duì)信源的不確定性增加了，由于熵是對(duì)信源不確定性的平均減少量，是信宿獲得的關(guān)于信源的平均信息量，由于不確定性的增加使獲得的信息量減少，故有，當(dāng)為無記憶時(shí)，傳輸?shù)男畔⒘磕苓_(dá)到理想狀態(tài)。故有。第四章離散信源的信源編碼簡述信源譯碼的錯(cuò)誤擴(kuò)展現(xiàn)象。答：由于信道的干擾作用，造成了一定量的錯(cuò)誤，這些錯(cuò)誤在譯碼時(shí)又造成了更多的錯(cuò)誤，這就是通信譯碼的錯(cuò)誤擴(kuò)展現(xiàn)象。針對(duì)某種應(yīng)用，給出一種你認(rèn)為是有價(jià)值的減小信源譯碼錯(cuò)誤擴(kuò)展的方法。答：在信源編碼的每個(gè)碼字施加和碼字等長的附加位，編碼時(shí)將要寫入的信息在新碼字上順序?qū)憙蛇?，譯碼時(shí)先譯前半段，若碼長無誤則譯后半段，若前后不一致則要求重發(fā)，在帶寬充足的條件下可以采用這種方法。試說明已有的解決信源譯碼錯(cuò)誤擴(kuò)展問題的方法，簡述其基本思路及利弊。答：信道編碼的方法優(yōu)點(diǎn)：加入了糾錯(cuò)碼，減少了譯碼錯(cuò)誤的可能性，減少了發(fā)生錯(cuò)誤擴(kuò)展的概率。]缺點(diǎn)：需要對(duì)發(fā)送的碼字加入冗余，是一種降低效率來換取可靠性的方法。某通信系統(tǒng)使用文字字符共10000個(gè)，據(jù)長期統(tǒng)計(jì)，使用頻率占80%的共有500個(gè)，占90%的有1000個(gè)，占99%的有4000個(gè)，占99.9%的7000個(gè)。（1）求該系統(tǒng)使用的文字字符的熵；（2）請(qǐng)給出該系統(tǒng)一種信源編碼方法并作簡要評(píng)價(jià)。解：(1)(2)可以使用huffman編碼的方法，為使壓縮效果理想，可以使用擴(kuò)展信源的方法。一通信系統(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)分別為abc，則p(a)=0.2,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種平均碼長為＝4.488bit/字1=R1/C=4.455/4.488=99.26%設(shè)有一個(gè)無記憶信源發(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）該離散無記憶信源的熵為（2）費(fèi)諾編碼消息符號(hào)序號(hào)(i)消息概率pi第一次分解第二次分解第三次分解二進(jìn)制代碼組碼組長度biBB9/16(9/16)001AB3/16(7/16)1(3/16)0102BA3/16(4/16)1(3/16)01103AA1/16(1/16)11113編碼的平均長度為碼元/符號(hào)平均傳輸速率為（3）霍夫曼編碼0BBB 27/64 0100BAA 9/64 0(18/64)0 1.0101BAB 9/64 1 1110ABB 9/64 0 (37/64)11100AAB 3/64 0(6/64) 0 (19/64)111101ABA 3/64 1 (10/64) 111110BAA 3/64 0(1/16)111111AAA 1/64 1編碼的平均長度為碼元/符號(hào)平均傳輸速率為已知一個(gè)信源包含8個(gè)符號(hào)消息，它們的概率分布如下表：ABCDEFGH0.050.060.10.070.04信源每秒鐘內(nèi)發(fā)出一個(gè)符號(hào)，求該信源的熵及信息傳輸速率；（2）對(duì)這8個(gè)符號(hào)作二進(jìn)制碼元的霍夫曼編碼，寫出各個(gè)代碼組，并求出編碼效率。解：（1）該信源的熵信息傳輸速率R=2.55bit/s（2）霍夫曼編碼C0.4 0B0.18 0 1.0A0.1 0 0.23 0F0.1 0 1 0.37 1 0.61 1G0.07 00.13 E0.06 1 0.19 1D0.05 00.09 1H0.04 1編碼結(jié)果：C B A F G E D H0 110 100 1110 1010 10111110 11111平均碼長為：所以編碼效率為設(shè)信道基本符號(hào)集合A={at1=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解：（1）這是一個(gè)有固定約束的不均勻編碼的信道，有約束條件（即不能出現(xiàn)），可以把a(bǔ)1,a2作為狀態(tài)1，a3,a4,a5作為狀態(tài)2，得香農(nóng)線圖時(shí)間長度分別為b11=,b12(a3)=3,b12(a4)=4,b12(a5)=5,b21(a1)=1,b21(a2)=2,b22(a3)=3,b22(a5)=5,寫出行列式，可得特征方程為解方程可得所以bit/碼元時(shí)間因?yàn)橐?guī)定a1ax1 x2 x3 x4 x5 x6 x71/2 1/4 1/8 1/16 1/32 1/64 1/64a3 a4 a1a3 a5 a1a4 3 4 4 5 5 5 6（3）編碼效率為=R/C=0.541/0.675=80%第五章離散信道的信道編碼5．1比特/符號(hào)比特命題得證。5．2比特/符號(hào)比特/符號(hào)比特/符號(hào)R=0.049*1000=49比特5．3比特/符號(hào)比特/符號(hào)比特/符號(hào)比特/符號(hào)5．4比特/符號(hào)5．5（1）由圖可知這是個(gè)對(duì)稱信道，當(dāng)輸入符號(hào)等概時(shí)，,,1/81/800P(xy)=01/81/80001/8 1/81/8 001/8對(duì)任意x均成立所以，C=1比特/符號(hào)。（2）由圖可知，信道亦為對(duì)稱信道，P(xy)=P(x)P(y|x)=1/61/61/121/121/121/121/6 1/6=0.0817比特/符號(hào)（3）同上，信道為對(duì)稱離散信道，P(xy)=1/6 1/91/181/181/61/91/91/181/6比特/符號(hào)。6.設(shè)據(jù)對(duì)稱性由，代入所以奈特/符號(hào)。7該信道可看成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-)]log{4(1-)[1-2(1-)]}+1-4(1-)[1-2(1-)]log{4(1-)[1-2(1-)]}代入=，得C’=0.9949所以信道容量C’=C*1024=1018.8kbps。8由圖可知信道為對(duì)稱信道，且信源的符號(hào)消息等概分布，因此比特/符號(hào)。9后驗(yàn)概率1/41/61/12P(xy)=1/241/81/121/121/241/8由P(y)=[3/81/37/24]所以2/31/22/7P(x|y)=1/93/82/72/91/83/7根據(jù)最小錯(cuò)誤概率準(zhǔn)則，應(yīng)作如下譯碼：錯(cuò)誤概率為10（1）（2）（3）5．11？？5．12（1）對(duì)信源四個(gè)消息進(jìn)行編碼，選擇碼長n=4，這組碼為C:{()}i=(1,2)編碼后的信息傳輸率比特/符號(hào)（2）設(shè)接收序列根據(jù)信道的傳輸特性，輸入序列共有16個(gè)，正好分成4個(gè)互不相交的子集，每個(gè)碼字只傳輸?shù)狡渲袑?duì)應(yīng)的一個(gè)子集：(001/21/2)à(00)(011/21/2)à(01)(101/21/2)à(10)(111/21/2)à(11)所以根據(jù)選擇的譯碼規(guī)則=(1/21/2)正好將接收序列譯成所發(fā)送的碼字，可計(jì)算每個(gè)碼字引起的錯(cuò)誤概率所以有。13(1)P(y)=[7/125/12]P(x|y)=6/73/51/72/5又比特/符號(hào)所以比特/符號(hào)此信道為二元對(duì)稱信道，所以信道容量比特/符號(hào)根據(jù)二元對(duì)稱信道的性質(zhì)可知，輸入符號(hào)為等概分布，即P(0)=P(1)=1/2時(shí)信道的信息傳輸率才能達(dá)到這個(gè)信道的容量值。（1）由P(y)=[1/21/4+1/4a1/4-1/4a]所以（2）(3)第六章連續(xù)信源和連續(xù)信道第六章6.1(1)收到傳真的概率為8/(4+8+3+1)*2/(7+1+2)=1/10I=-log1/10=3.3比特（2）可采取壓縮編碼，安最佳編碼原則編碼等措施（3）編碼時(shí)碼長盡可能長，這樣根據(jù)香濃第二定理，總存在一種編碼，只要碼長足夠長，總存在一種編碼，是錯(cuò)誤概率任意小。最好結(jié)合實(shí)際分析如何克服隨機(jī)，突發(fā)干擾。（4）C=Blog(1+S/N)=2.048log(1+)=8.34Mbps，不失真條件下，該信道允許最大信息傳輸速率為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.6KB=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=10bit/s6.5又,所以10=2，=5所以6.66.7所以B=.(1)(2)又而，所以S/N=,所以=9.97BB=66.9所以所以P=.6.10=所以（2）利用關(guān)系式，所以式（2）變?yōu)?，為一常量?.11=再由逐步分布積分得H(X)=-2AlnA-2Aln2+2A.因?yàn)椋?A=1A=1/2所以H(X)=1奈特/自由度（1）=b=-logbp(x)dx-2b=因?yàn)閜(x)dx=1，所以b=。故H(X)=2/3loge+loga-log3若Y=X+A，則,所以H(Y)=2/3loge+loga-log3若Y=2X，則，所以H(Y)=H(X)-log1/2=2/3loge+loga-log3/2。6.136.14(1)(2)所以B=(3)所以S/N=120第七章網(wǎng)絡(luò)信息理論簡介（略）第八章信息率失真理論及其應(yīng)用設(shè)輸入符號(hào)表與輸出符號(hào)表為X=Y={0,1,2,3}，且輸入信號(hào)的分布為p(X=i)=1/4,i=0,1,2,3設(shè)失真矩陣為求和及。設(shè)無記憶信源，接收符號(hào)AY={1/2,1/2}，失真矩陣。試求：Dmax和Dmin及達(dá)到Dmax和Dmin時(shí)的轉(zhuǎn)移概率矩陣。,在時(shí)，由于，所以在時(shí)，由于，所以三元信源的概率分別為p(0)=0.4,p(1)=0.4,p(2)=0.2，失真函數(shù)dij為：當(dāng)i=j時(shí)，dij=0；當(dāng)ij時(shí)，dij=1(i,j=0,1,2)，求信息率失真函數(shù)R(D)。，由定義知：，平均失真度一定與試驗(yàn)信道的平均錯(cuò)誤概率Pe有關(guān)，即根據(jù)保真度準(zhǔn)則，應(yīng)有PeD根據(jù)Fano不等式H(X/Y)H(Pe)+Pelog(r–1)設(shè)有一連續(xù)信源，其均值為0，方差為，熵為H(X)，定義失真函數(shù)為“平方誤差”失真，即。證明其率失真函數(shù)滿足下列關(guān)系式：當(dāng)輸入信源為高斯分布時(shí)等號(hào)成立。證明：證明上界：連續(xù)信源R(D)函數(shù)是在約束條件下，求平均互信息：引入?yún)⒘縎和待定函數(shù)。在失真不超過D時(shí)，為下確界的試驗(yàn)信道滿足由泛函分析中的變分法求的條件極值令由于以上規(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）得即證明上界設(shè)信道的傳遞函數(shù)的概率為：它是已知時(shí)y的概率分布，即均值為，方差為的高斯分布，其中。設(shè)，由于所以輸出信號(hào)，于是時(shí)均值為零，方差為的隨即變量。當(dāng)方差受限時(shí)，高斯隨即變量的差熵最大，有當(dāng)且僅當(dāng)是高斯分布時(shí)，上式等號(hào)成立。綜上所述，隨機(jī)變量X服從對(duì)稱指數(shù)分布，失真函數(shù)為d(x,y)=|x–y|，求信源的R(D)。，令，得且得對(duì)進(jìn)行傅立葉變換由，得且當(dāng)時(shí)設(shè)有平穩(wěn)高斯信源X(t)，其功率譜為，失真度量取，容許的樣值失真為D。試求：信息率失真函數(shù)R(D)；用一獨(dú)立加性高斯信道（帶寬為，限功率為P，噪聲的雙邊功率譜密度為）來傳送上述信源時(shí)，最小可能方差與的關(guān)系。（1）對(duì)于時(shí)間連續(xù)的平穩(wěn)高斯信源，當(dāng)功率譜密度已知時(shí)，在本題中即（2）信道容量為bit/s由定理可知，當(dāng)時(shí)，可以采用最佳編碼，其硬氣的錯(cuò)誤小于等于D。取,求得最小均方誤差D。令，得時(shí)，時(shí)，時(shí)，由于所以如下圖：某工廠的產(chǎn)品合格率為99%，廢品率為1%。若將一個(gè)合格產(chǎn)品作為廢品處理，將損失1元；若將一個(gè)廢品當(dāng)作合格產(chǎn)品出廠，將損失100元；若將合格品出廠，廢品報(bào)廢，不造成損失。試分析質(zhì)量管理中各種情況造成的損失及付出的代價(jià)。解根據(jù)題意有信源空間：好（合格）廢（廢品）P(好)=0.99P(廢)=0.01選擇失真函數(shù)為d(好，好)=0d(廢，廢)=0d(好，廢)=10d(廢，好)=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(好/好)=1 P(廢/好)=0 P(好/廢)=1 P(廢/廢)=0信道矩陣為這種情況的平均損失，即平均失真度，為=P(好)P(好/好)d(好,好)+P(好)P(廢/好)d(好,廢)+P(廢)P(好/廢話)d(廢,好)+P(廢)P(廢/廢)d(廢,廢)=0.011100=1元/個(gè)情況2全部產(chǎn)品不經(jīng)檢驗(yàn)全部報(bào)廢——都當(dāng)廢品這時(shí)的信道傳輸概率為P(好/好)=0 P(廢/好)=1 P(好/廢)=0 P(廢/廢)=1信道矩陣為平均失真度為

=P(好)P(好/好)d(好,好)+P(好)P(廢/好)d(好,廢)+P(廢)P(好/廢)d(廢,好)+P(廢)P(廢/廢)d(廢,廢)=0.9911=0.99元/個(gè)全部報(bào)廢造成損失小于全部出廠造成的損失。情況3經(jīng)過檢驗(yàn)?zāi)苷_無誤地判斷合格品和廢品——完美的檢驗(yàn)這相當(dāng)于無噪信道的情況，信道矩陣為平均失真度為即這種情況不會(huì)另外造成損失。情況4檢測時(shí)允許有一定的錯(cuò)誤——非完美的檢驗(yàn)設(shè)檢驗(yàn)的正確率為p，則信道的傳輸概率為P(好/好)=p P(廢/好)=1-pP(好/廢)=1-p P(廢/廢)=p信道矩陣為平均失真度為=P(好)P(廢/好)d(好,廢)+P(廢)P(好/廢)d(廢,好)=0.99(1-p)1+0.01p100=1.99(1-p)元/個(gè)設(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]。某二元信源X的信源空間為其中w<1/2，其失真矩陣為試求和；試求及；試求；寫出取得的試驗(yàn)信道的各傳遞概率；當(dāng)d=1時(shí)，寫出與試驗(yàn)信道相對(duì)應(yīng)的反向試驗(yàn)信道的信道矩陣。解：（1）（因?yàn)椋?）由于令，則得到得到D=0時(shí)，D=d時(shí)，所以（4）（5）d=1時(shí)，，第九章差錯(cuò)控制的基本概念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ò)，糾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ò)為什么d=2的(n,n–1)碼能檢測奇數(shù)個(gè)錯(cuò)誤？解:d=2，能檢1個(gè)錯(cuò)，又因?yàn)?n,n–1)碼是奇偶校驗(yàn)碼，即對(duì)于奇校驗(yàn)碼：偶校驗(yàn)碼：當(dāng)出現(xiàn)一個(gè)錯(cuò)或者奇數(shù)個(gè)錯(cuò)時(shí)，在接收端奇校驗(yàn)碼：偶校驗(yàn)碼：都能檢測到錯(cuò)誤，故d=2的(n,n–1)碼能檢測奇數(shù)個(gè)錯(cuò)誤。設(shè)C={11100,01001,10010,00111}是一個(gè)二元碼，求碼C的最小距離d。解：d(11100,01001)=3d(11100,10010)=3d(11100,00111)=4d(01001,10010)=4d(01001,00111)=3d(10010,00111)=3故碼C的最小距離d=34．設(shè)C={00000000,00001111,00110011,00111100}是一個(gè)二元碼。計(jì)算碼C中所有碼字之間的距離及最小距離；在一個(gè)二元碼中，如果把某一個(gè)碼字中的0和1互換，即0換為1，1換為0，所得的字稱為此碼字的補(bǔ)。所有碼字的補(bǔ)構(gòu)成的集合稱為此碼的補(bǔ)碼。求碼C的補(bǔ)碼以及補(bǔ)碼中所有碼字之間的距離和最小距離，它們與（1）中的結(jié)果有什么關(guān)系？把（2）中的結(jié)果推廣到一般的二元碼。解：d(00000000,00001111)=4d(00000000,00110011)=4d(00000000,00111100)=4d(00001111,00110011)=4d(00001111,00111100)=4d(00110011,00111100)=4故碼C的最小距離d=4碼C的補(bǔ)碼是{11111111,11110000,11001100,11000011}d(11111111,11110000)=4d(11111111,11001100)=4d(11111111,11000011)=4d(11110000,11001100)=4d(11110000,11000011)=4d(11001100,11000011)=4故C補(bǔ)碼的最小距離d=4（3）推廣到一般的二元碼也有以上的結(jié)論設(shè)碼C中任意兩碼字的距離為d,即兩碼字有d位不同，n-d位相同。變補(bǔ)后，仍有d位不同，n-d位相同，所以任意兩碼字的距離不變，最小距離當(dāng)然不變。第十章線性分組碼已知11次本原多項(xiàng)式p(x)=x11+x2+1，試求GF(211)中元素=89及2,3,4,5的最小多項(xiàng)式。解：的共軛元為：求碼長為n的q元重復(fù)碼的生成矩陣。若n=2,q=2，則有22＝4個(gè)碼字生成矩陣對(duì)于碼長為n的q元重復(fù)碼，生成矩陣是維單位矩陣。一個(gè)二元(11,24,5)碼是線性碼嗎？為什么？是線性碼。13>11證明對(duì)于一個(gè)二元線性碼L一定滿足下列條件之一：碼L中所有碼字具有偶數(shù)重量；碼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è)不成立。原命題得證。設(shè)二元線性碼L的生成矩陣為，求碼L的最小距離。因?yàn)樗浴ＴO(shè)3元線性碼L的生成矩陣為，求碼長L的最小距離并且證明L是完備的。題中由生成矩陣知，該線性碼是碼，陪集首的個(gè)數(shù)為，能糾正3個(gè)錯(cuò)誤。而1bit錯(cuò)誤圖樣的個(gè)數(shù)為，又3<4，所以線性碼是完備的。設(shè)二元線性碼L的生成矩陣為，建立碼L的標(biāo)準(zhǔn)陣并且對(duì)字11111和10000分別進(jìn)行譯碼。共個(gè)碼字。標(biāo)準(zhǔn)陣為譯碼得設(shè)5元線性碼L的生成矩陣為。確定碼L的標(biāo)準(zhǔn)型生成矩陣；確定碼L的標(biāo)準(zhǔn)型校驗(yàn)矩陣；求碼L的最小距離。設(shè)有碼如下所示：信息碼字000000110110101111111010找出生成矩陣G與監(jiān)督矩陣H；在二元對(duì)稱信道下給出最大似然譯碼的譯碼表；求正確譯碼的概率。設(shè)信息位，碼字由編碼規(guī)則（2）譯碼表（3）正確譯碼的概率為：建立二元漢明碼Ham(7,4)的包含陪集首和伴隨式的伴隨表，并對(duì)收到的字0000011，1111111，1100110，1010101進(jìn)行譯碼。（1）（2）譯碼譯碼得到結(jié)果設(shè)一個(gè)[7,4]碼的生成矩陣為求出該碼的全部碼矢；求出該碼的一致校驗(yàn)矩陣；作出該碼的標(biāo)準(zhǔn)譯碼碼表。（1）（2）（3）設(shè)一個(gè)二進(jìn)制(n,k)碼C的G矩陣不含全零列，將C的所有碼字排成的陣，證明：陣中不含有全零列；陣中的每一列由個(gè)零和個(gè)1組成；在一特定分量上為0的所有碼字構(gòu)成C的一個(gè)子空間，問該子空間的維數(shù)是多少？（1）碼共有個(gè)碼字1．包括全零矢量；2．任意兩個(gè)碼字的和也是碼字；假設(shè)組成的陣包含一個(gè)全零列，則每個(gè)碼字重復(fù)兩次，實(shí)際只有個(gè)不同的碼字，與該碼的定義相矛盾。所以陣中不含全零列。（2）等效于證每一列中0和1的個(gè)數(shù)相等。如（3，3）碼由于任意兩個(gè)碼字的和也是碼字，所以碼字中奇數(shù)和偶數(shù)的數(shù)目相等。又由習(xí)題10.4(2)，線性碼中一半碼字具有偶數(shù)重量，另一半碼字具有奇數(shù)重量，于是每一列中0和1的個(gè)數(shù)相等。所以，陣中的每一列由個(gè)零和個(gè)1組成的命題成立。一個(gè)(8,4)系統(tǒng)碼，它的一致校驗(yàn)方程為：式中是信息位，是校驗(yàn)位。找出該碼的G和H，并證明該碼的最小距離為4。第十一章循環(huán)碼設(shè)p是一個(gè)素?cái)?shù)，在GF(p)上把分解成不可約因式的乘積；在GF(p)上把分解成不可約因式的乘積。在GF(3)上把分解成不可約多項(xiàng)式的乘積，確定所有碼長是4的三元循環(huán)碼，并寫出每一個(gè)碼的生成矩陣和校驗(yàn)矩陣。設(shè)在GF(q)上可分解成t個(gè)不同的不可約多項(xiàng)式的乘積，試問有多少個(gè)碼長為n的q元循環(huán)碼？設(shè)C是一個(gè)二元循環(huán)碼，證明分量全為1的向量(11…1)C的充分必要條件是C包含一個(gè)重量為奇數(shù)的碼字。在GF(2)上能分解成不可約因式的乘積：確定所有碼長為7的循環(huán)碼，并且準(zhǔn)確描述這些碼的特性。解：由題知n=7,k=6,4(1)當(dāng)k=6時(shí)g(x)=x-1(2)當(dāng)k=4時(shí)g(x)=x3+x+1或x3+x2+1請(qǐng)對(duì)任意一個(gè)21-bit的數(shù)據(jù)，例如使用自己的學(xué)號(hào)化成2進(jìn)制數(shù)，高位補(bǔ)“0”或某些隨機(jī)數(shù)）（1）給出BCH(31,21)碼的碼多項(xiàng)式；（2）假設(shè)傳輸過程中錯(cuò)了一位（可以任意設(shè)定），請(qǐng)譯碼；（3）假設(shè)傳輸過程中錯(cuò)了兩位（可以任意設(shè)定），請(qǐng)譯碼；（4）假設(shè)傳輸過程中錯(cuò)了三位（可以任意設(shè)定），請(qǐng)譯碼。解：（1）我們可以任選一個(gè)21-bit的數(shù)據(jù)，假設(shè)所選數(shù)據(jù)為020321，其二進(jìn)制數(shù)表示為：00010000000110010000121位碼查表可知（31，21）碼的本原多項(xiàng)式為：g(x)=x17+x9+x8+x5+1輸入多項(xiàng)式為：u(x)=x17+x9+x8+x5+1所以輸出碼多項(xiàng)式為：v(x)=u(x)g(x)=(x17+x9+x8+x5+1)(x10+x9+x8+x6+x5+x3+1)=x27+x26+x25+x23+x22+x20+x19+x17+x16+x14+x12+x8+x6+x3+1(2)假設(shè)接收到的多項(xiàng)式為：r(x)=x27+x25+x23+x22+x20+x19+x17+x16+x14+x12+x8+x6+x3+1則可得：σ（x）=α26x+1即錯(cuò)誤位置為26，可以糾正。(3)假設(shè)接收到的多項(xiàng)式為：r(x)=x27+x26+x23+x22+x20+x19+x17+x16+x14+x12+x8+x6+1則可得：σ（x）=（α25x+1）（α3x+1）所以：β1=α-25β2=α-3即錯(cuò)誤位置為x3和x25，可以糾正。(4)假設(shè)接收到的多項(xiàng)式為：r(x)=x27+x26+x25+x19+x17+x16+x14+x12+x8+x6+x3+1出現(xiàn)了3個(gè)錯(cuò)誤，接收端能檢出錯(cuò)誤，但無法糾正。已知GF(25)中元素的幾種表示如表11.8所示，有關(guān)元素的最小多項(xiàng)式如下：,,,,,?，F(xiàn)欲對(duì)上題信源編碼輸出進(jìn)行擴(kuò)展的BCH(32,16)信道編碼再傳送。（1）對(duì)于消息(1000111111101010)給出信道編碼的輸出碼字；（2）若接收矢量為(10001111111010100110100100111101)，試判斷是否有錯(cuò)，如只有一個(gè)錯(cuò)請(qǐng)糾正之，如有兩個(gè)或三個(gè)錯(cuò)請(qǐng)說明糾正的方法。表11.8GF(25)域元素的兩種表示（本原多項(xiàng)式p(x)=x5+x2+1）100001801101161101124111100001091101017100112511001200100101000118000112610111301000110011119001102701011410000120111020011002810110500101131110021110002901001601010141110122101013010010710100151111123011113100001解：由題知：m=5，n=25-1=31擴(kuò)展的BCH(31+L,K)碼，則L=1(即加了1為奇偶校驗(yàn)位)，K=16（1）若可以糾1個(gè)錯(cuò)，則g(x)=p(x)=x5+x2+1則編碼輸出為：u(x)g(x)=（2）令是(15,5)循環(huán)碼的生成多項(xiàng)式，求出該碼的校驗(yàn)多項(xiàng)式；寫出該碼的系統(tǒng)碼形式的G和H矩陣；構(gòu)造k級(jí)編碼器。解：由題可得：x10=g(x)+x8+x5+x4+x2+x+1x11=xg(x)+x9+x6+x5+x3+x2+xx12=x2g(x)+x10+x7+x6+x4+x3+x=(x2+1)g(x)+x8+x7+x6+x5+x3+x+1x13=(x3+x)g(x)+x9+x8+x7+x6+x4+x2+xx14=(x4+x2)g(x)+x10+x9+x8+x7+x5+x3+x2=(x4+x2+1)g(x)+x9+x7+x4+x3+x+1所以可得：bo(x)=x8+x5+x4+x2+x+1b1(x)=x9+x6+x5+x3+x2+xb2(x)=x8+x7+x6+x5+x3+x+1b3(x)=x9+x8+x7+x6+x4+x2+xb4(x)=x9+x7+x4+x3+x+1進(jìn)而有：G=H=求GF(25)上以,3為根的二進(jìn)制循環(huán)碼：寫出生成多項(xiàng)式g(x)，確定碼長n和信息位個(gè)數(shù)k；寫出該碼系統(tǒng)碼形式的G和H矩陣；求出該碼的R和最小距離。解：（1）查表可得本原多項(xiàng)式為：p(x)=x5+x2+1又g(x)=LCM{當(dāng)β1=α-β2=α-3用matlab函數(shù)gfminpol(1，5)和gfminpol(3，5)分別得：Φ1(x)=x5+x3+1Φ3(x)=x5+x3+x2+x+1所以g(x)=Φ1(x)Φ3(x)=x10+x7+x5+x2+x+1所以n=25-1=31，k=31-10=21（2）同樣由上題的方法可求出系統(tǒng)碼形式的G和H矩陣x10=g(x)+x7+x5+x2+x+1x11=xg(x)+x8+x6+x3+x2+x……….X31=………可進(jìn)一步寫出bo(x)……b21(x)，從而寫出G，HG=H=（3）令n是g(x)|(xn–1)|的最小正數(shù)?，F(xiàn)用該g(x)生成位n的循環(huán)碼，證明碼的最小距離至少為3。構(gòu)造(15,5,7)碼的譯碼器，它的生成多項(xiàng)式g(x)=x10+x8+x5+x4+x2+x+1，該碼能糾正3個(gè)錯(cuò)誤。設(shè)用簡單的捕錯(cuò)譯碼器譯碼。（1）證明所有2個(gè)錯(cuò)誤能被捕獲；（2）能捕獲所有3個(gè)錯(cuò)誤的圖樣嗎？若不能，則有多少種3個(gè)錯(cuò)誤圖樣不能被捕獲；（3）作出該碼的簡單捕獲譯碼器。對(duì)，存在有一個(gè)長為糾t個(gè)錯(cuò)誤的二進(jìn)制本原BCH碼嗎？若有找出它的g(x)。第十二章卷積碼試畫出k=3，效率為1/3，生成多項(xiàng)式如下所示的編碼狀態(tài)圖、樹狀圖和網(wǎng)格圖：解：g1(D)=D+D2，g2(D)=1+D，g3(D)=1+D+D2所以可得狀態(tài)圖如下：其中（s0:00，s1:01，s2:10，s3:11）樹狀圖如下：011011000100111001010110101011111………………10網(wǎng)格圖為：假定尋找從倫敦到維也納坐船或坐火車的最快路徑，圖12.25給出了各種安排，各條分支上標(biāo)注的是所需時(shí)間。采用維特比算法，找到從倫敦到維也納的最快路線，解釋如何應(yīng)用該算法，需做哪些計(jì)算，以及該算法要求在存儲(chǔ)器里保存什么信息。解：從倫敦到維也納的最快路線為：倫敦——巴黎——慕尼黑——維也納此算法需計(jì)算從倫敦到維也納中間所可能經(jīng)過的各節(jié)點(diǎn)離倫敦的時(shí)間，保留其中最短的，去除其它的。需要記錄下各中間節(jié)點(diǎn)離倫敦的最短時(shí)間，其算法的實(shí)現(xiàn)就是Dijkstra算法?？紤]圖12.26中的卷積碼。（a）寫出編碼器的連接矢量和連接多項(xiàng)式。（b）畫出狀態(tài)圖、樹狀圖和網(wǎng)格圖。解：（1）由圖可知：連接矢量為：g(1)=[1,0,1]g(2)=[0,1,1]連接多項(xiàng)式為：g(1)（D）=1+D2g(2)（D）=D+D（２）狀態(tài)圖為：其中（s0:00，s1:01，s2:10，s3:11）樹狀圖為：010100110100100111………………10網(wǎng)格圖為：下列碼率為1/2的編碼中哪些會(huì)引起災(zāi)難性錯(cuò)誤傳播？（a）g1(X)=X2，g2(X)=1+X+X3（b）g1(X)=1+X2，g2(X)=1+X3（c）g1(X)=1+X+X2，g2(X)=1+X+X3+X4（d）g1(X)=1+X+X3+X4，g2(X)=1+X2+X4（e）g1(X)=1+X4+X6+X10，g2(X)=1+X3+X4（f）g1(X)=1+X3+X4，g2(X)=1+X+X2+X4解：會(huì)引起災(zāi)難性錯(cuò)誤傳播的有：（ｂ）有公因子（１＋ｘ）（ｃ）有公因子（１＋ｘ＋ｘ２）（ｄ）有公因子（１＋ｘ＋ｘ２）故此三個(gè)會(huì)引起會(huì)引起災(zāi)難性錯(cuò)誤傳播。6.已知(2,1,3)碼的子生成元g(1,1)=(1101),g(1,2)=(1110)。求出該碼的G(D)和H(D)矩陣，以及G和H矩陣；畫出該碼的編碼器；求出相應(yīng)于信息序列M=(11001)的碼序列；此碼是否是系統(tǒng)碼？解：（１）因g(1,1)（Ｄ）=１＋Ｄ＋Ｄ３g(1,2)（Ｄ）＝１＋Ｄ＋Ｄ２所以Ｇ（Ｄ）＝［１＋Ｄ＋Ｄ３，１＋Ｄ＋Ｄ２］Ｈ（Ｄ）＝（２）（３）ｖ（１）＝（１１００１）＊（１１０１）＝１０１１０１