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

（有問題請更正并通知xiezg@）第二章信息的度量一珍珠養(yǎng)殖場收獲240顆外觀及重量完全相同的特大珍珠，但不幸被人用外觀相同但重量僅有微小差異的假珠換掉1顆。（1）一人隨手取出3顆，經(jīng)測量恰好找出了假珠，問這一事件大約給出了多少比特的信息量；（2）不巧假珠又滑落進(jìn)去，那人找了許久卻未找到，但另一人說他用天平最多6次能找出，結(jié)果確是如此，問后一事件給出多少信息量；（3）對上述結(jié)果作出解釋。解：（1）從240顆珠子中取3顆，含1顆假珠的概率為（2）240顆中含1顆假珠，用天平等分法最多6次即可找到假珠，是必然事件，因此信息量為0。（3）按照shannon對信息量的定義，只有事件含有不確知成分，才有信息量，且不確知成分越大，信息量越大，必然事件則沒有信息量。但從廣義信息論來說，如果那人不知用天平二分法找假珠，另一人告之此事，使他由不知到知，也應(yīng)該含有一定的信息量。2．每幀電視圖像可以認(rèn)為是由3105個象素組成，所有象素均獨立變化，且每一象素又取128個不同的亮度電平，并設(shè)亮度電平等概率出現(xiàn)。問每幀圖像含有多少信息量？如果一個廣播員在約10000個漢字的字匯中選取1000個字來口述此電視圖像，試問廣播員描述此圖像所廣播的信息量是多少（假設(shè)漢字字匯是等概率分布，且彼此獨立）？若要恰當(dāng)?shù)孛枋龃藞D像，廣播員在口述中至少需用多少漢字？解：設(shè)電視圖像每個像素取128個不同的亮度電平，并設(shè)電平等概率出現(xiàn)，則每個像素亮度含有的信息量為比特/像素一幀中像素均是獨立變化的，則每幀圖像信源就是離散亮度信源的無記憶N次擴(kuò)展信源。得每幀會圖像含有的信息量為比特/每幀廣播口述時，廣播員是從10000個漢字字匯中選取的，假設(shè)漢字字匯是等概率分布的，則漢字字匯中每個漢字含有的信息量比特/字廣播員口述電視圖像是從此漢字字匯信源中獨立地選取1000個字來描述的。所以，廣播員描述此幀圖像所廣播的信息量為比特/千字若廣播員仍從此漢字字匯信源Y中獨立地選取漢字來描述電視圖像，每次口述一個漢字含有信息量是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)時，即p=0.5時，熵最大。當(dāng)p由0.5分別趨向于0和1時，熵逐漸減小至0。4．證明H(X3|X1X2)H(X2|X1)，并說明等式成立的條件。證明：設(shè)離散平穩(wěn)信源輸出的隨機(jī)符號序列為…X1,X2,X3,…。又設(shè),,,而且都取自于同一符號集，并滿足有在區(qū)域[0，1]內(nèi)設(shè)f(x)=－xlogx,f(x)在[0，1]內(nèi)是型凸函數(shù)，所以滿足詹森不等式其中現(xiàn)今,設(shè)其概率空間為，并滿足所以根據(jù)詹森不等式得所以上式對所有的取值都成立，所以因為，所以上式兩邊相乘，等號不變。有上式對所有都成立，所以對所有求和下式也成立因為H(X3|X1X2)H(X3|X2)所以是平穩(wěn)信源H(X3|X2)=H(X2|X1)得H(X3|X1X2)H(X2|X1)只有當(dāng)(對所有)時等式成立。5．設(shè)有一概率空間，其概率分布為{p1,p2,…,pq}，且p1>p2。若取，，其中0<2證明：令得因為f(x)=－xlogx是型函數(shù)，根據(jù)型凸函數(shù)的定義有所以即同理得以上兩不等式兩邊相加，不等號不變。所以得6．某辦公室和其上級機(jī)關(guān)的自動傳真機(jī)均兼有電話功能。根據(jù)多年來對雙方相互通信次數(shù)的統(tǒng)計，該辦公室給上級機(jī)關(guān)發(fā)傳真和打電話占的比例約為3:7，但發(fā)傳真時約有5%的次數(shù)對方按電話接續(xù)而振鈴，撥電話時約有1%的次數(shù)對方按傳真接續(xù)而不振鈴。求：（1）上級機(jī)關(guān)值班員聽到電話振鈴而對此次通信的疑義度；（2）接續(xù)信道的噪聲熵。解：設(shè)發(fā)傳真和打電話分別為事件X1與X2,對方按傳真和按電話接續(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(Y)=－P(Y1)lbP(Y1)－P(Y2)lbP(Y2)=0.8713bit/符號H(XY)==1.0239bit/兩個信符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．四個等概分布的消息M1，M2，M3，M4被送入如圖所示的信道進(jìn)行傳輸，通過編碼使M1=00，M2=01，M3=10，M4=11。求輸入是M1和輸出符號是0的互信息量是多少？如果知道第2個符號也是0，這時帶來多少附加信息量？圖2.6解：信源P(M1)=P(M2)=P(M3)=P(M4)=1/4,信道為二元對稱無記憶信道，消息Mi與碼字一一對應(yīng)，所以設(shè)設(shè)接收序列為Y=(y1y2)接收到第一個數(shù)字為0，即y1=0。那么，接收到第一個數(shù)字0與M1之間的互信息為因為信道為無記憶信道，所以同理，得輸出第一個符號是y1=0時，有可能是四個消息中任意一個第一個數(shù)字傳送來的。所以故得接收到第二個數(shù)字也是0時，得到關(guān)于M1的附加互信息為其中同理，因為信道是無記憶信道，所以得輸出端出現(xiàn)第一個符號和第二個符號都為0的概率為所以比特得附加互信息為比特8．證明若隨機(jī)變量X，Y，Z構(gòu)成馬氏鏈，即X→Y→Z，則有Z→Y→X。證明：因為(X,Y,Z)是馬氏鏈，有P(z|xy)=P(z|y),對所有成立，而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)對所有成立故得P(x|yz)=P(x|y)對所有成立所以(Z,Y,X)也是馬氏鏈。第三章離散信源1.由于，即可以看做是先發(fā)出一個符號，再在此基礎(chǔ)上發(fā)出一個與前一符號相關(guān)的符號，而,第二個符號可以看做為具有一階馬爾可夫性，故有。2.由轉(zhuǎn)移到可以認(rèn)為遍歷了每個，故，即有成立。3.香農(nóng)圖略由題轉(zhuǎn)移概率為，由馬爾可夫趨于穩(wěn)定時頻率分布不變，故得，即又由代入解得，，又，，，故H=1/2*lb3/2+1/4*lb34香農(nóng)圖略由題，由得，故H1=lb3,對二階馬爾可夫鏈有狀態(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）對p求導(dǎo)得，令，得，得6記，，則由條件（1）得，由條件（2）得，故，代入上邊兩式整理有，進(jìn)行遞推有，7由于，當(dāng)信源為無記憶信源時，，故得信道為無記憶時，，故得當(dāng)信源信道都無記憶時有，故有當(dāng)信源信道中有一個有記憶或兩個都有記憶時，信號之間或信道對信號存在干擾，故信宿對信源的不確定性增加了，由于熵是對信源不確定性的平均減少量，是信宿獲得的關(guān)于信源的平均信息量，由于不確定性的增加使獲得的信息量減少，故有，當(dāng)為無記憶時，傳輸?shù)男畔⒘磕苓_(dá)到理想狀態(tài)。故有。第四章離散信源的信源編碼簡述信源譯碼的錯誤擴(kuò)展現(xiàn)象。答：由于信道的干擾作用，造成了一定量的錯誤，這些錯誤在譯碼時又造成了更多的錯誤，這就是通信譯碼的錯誤擴(kuò)展現(xiàn)象。針對某種應(yīng)用，給出一種你認(rèn)為是有價值的減小信源譯碼錯誤擴(kuò)展的方法。答：在信源編碼的每個碼字施加和碼字等長的附加位，編碼時將要寫入的信息在新碼字上順序?qū)憙蛇叄g碼時先譯前半段，若碼長無誤則譯后半段，若前后不一致則要求重發(fā)，在帶寬充足的條件下可以采用這種方法。試說明已有的解決信源譯碼錯誤擴(kuò)展問題的方法，簡述其基本思路及利弊。答：信道編碼的方法優(yōu)點：加入了糾錯碼，減少了譯碼錯誤的可能性，減少了發(fā)生錯誤擴(kuò)展的概率。]缺點：需要對發(fā)送的碼字加入冗余，是一種降低效率來換取可靠性的方法。某通信系統(tǒng)使用文字字符共10000個，據(jù)長期統(tǒng)計，使用頻率占80%的共有500個，占90%的有1000個，占99%的有4000個，占99.9%的7000個。（1）求該系統(tǒng)使用的文字字符的熵；（2）請給出該系統(tǒng)一種信源編碼方法并作簡要評價。解：(1)(2)可以使用huffman編碼的方法，為使壓縮效果理想，可以使用擴(kuò)展信源的方法。一通信系統(tǒng)傳送的符號只有3個，其使用概率分別為0.2、0.3和0.5，但傳送時總是以3個符號為一個字，故該系統(tǒng)的信源編碼以字為基礎(chǔ)并采用二進(jìn)制霍夫曼編碼。根據(jù)字的概率大小，編碼結(jié)果為：概率在(0，0.020)，采用6比特；在(0.020，0.045]，采用5比特，但允許其中一個用4比特；在(0.045，0.100]，在0.100以上，采用3比特。求該種信源編碼的效率。解：假設(shè)三個符號分別為abc，則p(a)=0.2,p(b)=0.3,p(c)=0.5下面對每個字可能出現(xiàn)的情況加以討論。3個符號都為a則 編6bit碼，共1種3個符號都為b則 編5bit碼，共1種3個符號都為c則 編3bit碼，共1種3個符號有2個a，1個b則編6bit碼，共3種3個符號有2個a，1個c則編5bit碼，共3種3個符號有2個b，1個a則編6bit碼，共3種3個符號有2個b，1個c則編5bit碼，共3種3個符號有2個c，1個a則編4bit碼，共3種3個符號有2個c，1個b則編4bit碼，共3種3個符號有1個a，1個b,1個c則編5bit碼，共6種平均碼長為＝4.488bit/字1=R1/C=4.455/4.488=99.26%設(shè)有一個無記憶信源發(fā)出符號A和B，已知p(A)=1/4,p(B)=3/4。（1）計算該信源熵；（2）設(shè)該信源改為發(fā)出二重符號序列消息的信源，采用費諾編碼方法，求其平均信息傳輸速率；（3）又設(shè)該信源改為發(fā)三重序列消息的信源，采用霍夫曼編碼方法，求其平均信息傳輸速率。解：（1）該離散無記憶信源的熵為（2）費諾編碼消息符號序號(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編碼的平均長度為碼元/符號平均傳輸速率為（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編碼的平均長度為碼元/符號平均傳輸速率為已知一個信源包含8個符號消息，它們的概率分布如下表：ABCDEFGH0.050.060.10.070.04信源每秒鐘內(nèi)發(fā)出一個符號，求該信源的熵及信息傳輸速率；（2）對這8個符號作二進(jìn)制碼元的霍夫曼編碼，寫出各個代碼組，并求出編碼效率。解：（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è)信道基本符號集合A={at1=1,t2=2,t3=3,t4=4,t5=5（各碼元時間）用這樣的信道基本符號編成消息序列，且不能出現(xiàn)這四種符號相連的情況。（1）求這種編碼信道的信道容量；（2）若信源的消息集合X={x1,x2,…,x7}，它們的出現(xiàn)概率分別是P(x1)=1/2,P(x2)=1/4,P(x3)=1/8,…,P解：（1）這是一個有固定約束的不均勻編碼的信道，有約束條件（即不能出現(xiàn)），可以把a(bǔ)1,a2作為狀態(tài)1，a3,a4,a5作為狀態(tài)2，得香農(nóng)線圖時間長度分別為b11=,b12(a3)=3,b12(a4)=4,b12(a5)=5,b21(a1)=1,b21(a2)=2,b22(a3)=3,b22(a5)=5,寫出行列式，可得特征方程為解方程可得所以bit/碼元時間因為規(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比特/符號比特命題得證。5．2比特/符號比特/符號比特/符號R=0.049*1000=49比特5．3比特/符號比特/符號比特/符號比特/符號5．4比特/符號5．5（1）由圖可知這是個對稱信道，當(dāng)輸入符號等概時，,,1/81/800P(xy)=01/81/80001/8 1/81/8 001/8對任意x均成立所以，C=1比特/符號。（2）由圖可知，信道亦為對稱信道，P(xy)=P(x)P(y|x)=1/61/61/121/121/121/121/6 1/6=0.0817比特/符號（3）同上，信道為對稱離散信道，P(xy)=1/6 1/91/181/181/61/91/91/181/6比特/符號。6.設(shè)據(jù)對稱性由，代入所以奈特/符號。7該信道可看成4個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-)]級聯(lián)后的信道仍是對稱信道，可代入公式：其中--〉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由圖可知信道為對稱信道，且信源的符號消息等概分布，因此比特/符號。9后驗概率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ù)最小錯誤概率準(zhǔn)則，應(yīng)作如下譯碼：錯誤概率為10（1）（2）（3）5．11？？5．12（1）對信源四個消息進(jìn)行編碼，選擇碼長n=4，這組碼為C:{()}i=(1,2)編碼后的信息傳輸率比特/符號（2）設(shè)接收序列根據(jù)信道的傳輸特性，輸入序列共有16個，正好分成4個互不相交的子集，每個碼字只傳輸?shù)狡渲袑?yīng)的一個子集：(001/21/2)à(00)(011/21/2)à(01)(101/21/2)à(10)(111/21/2)à(11)所以根據(jù)選擇的譯碼規(guī)則=(1/21/2)正好將接收序列譯成所發(fā)送的碼字，可計算每個碼字引起的錯誤概率所以有。13(1)P(y)=[7/125/12]P(x|y)=6/73/51/72/5又比特/符號所以比特/符號此信道為二元對稱信道，所以信道容量比特/符號根據(jù)二元對稱信道的性質(zhì)可知，輸入符號為等概分布，即P(0)=P(1)=1/2時信道的信息傳輸率才能達(dá)到這個信道的容量值。（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）編碼時碼長盡可能長，這樣根據(jù)香濃第二定理，總存在一種編碼，只要碼長足夠長，總存在一種編碼，是錯誤概率任意小。最好結(jié)合實際分析如何克服隨機(jī)，突發(fā)干擾。（4）C=Blog(1+S/N)=2.048log(1+)=8.34Mbps，不失真條件下，該信道允許最大信息傳輸速率為8.34Mbps。6.2（1）比特/樣值（2）對樣值進(jìn)行256級量化，當(dāng)其服從均勻分布時，信源有最大熵，H=log256=8比特/符號（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.因為，所以2A=1A=1/2所以H(X)=1奈特/自由度（1）=b=-logbp(x)dx-2b=因為p(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è)輸入符號表與輸出符號表為X=Y={0,1,2,3}，且輸入信號的分布為p(X=i)=1/4,i=0,1,2,3設(shè)失真矩陣為求和及。設(shè)無記憶信源，接收符號AY={1/2,1/2}，失真矩陣。試求：Dmax和Dmin及達(dá)到Dmax和Dmin時的轉(zhuǎn)移概率矩陣。,在時，由于，所以在時，由于，所以三元信源的概率分別為p(0)=0.4,p(1)=0.4,p(2)=0.2，失真函數(shù)dij為：當(dāng)i=j時，dij=0；當(dāng)ij時，dij=1(i,j=0,1,2)，求信息率失真函數(shù)R(D)。，由定義知：，平均失真度一定與試驗信道的平均錯誤概率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)輸入信源為高斯分布時等號成立。證明：證明上界：連續(xù)信源R(D)函數(shù)是在約束條件下，求平均互信息：引入?yún)⒘縎和待定函數(shù)。在失真不超過D時，為下確界的試驗信道滿足由泛函分析中的變分法求的條件極值令由于以上規(guī)定了下確界，則 （1）設(shè)集合則有 （2）令其中由（1）得即當(dāng)時，且，得由（2）（3）兩式，有 （4）由對數(shù)得換底公式，有 （5）若要（1）式等號成立，則等效于（5）式等號成立。令則然后再求二階導(dǎo)數(shù)，得由于是得概率密度函數(shù)且所以，即（5）式右邊為上凸函數(shù)，在的S上確極大值，有代入得 （6）由式（5）得即證明上界設(shè)信道的傳遞函數(shù)的概率為：它是已知時y的概率分布，即均值為，方差為的高斯分布，其中。設(shè)，由于所以輸出信號，于是時均值為零，方差為的隨即變量。當(dāng)方差受限時，高斯隨即變量的差熵最大，有當(dāng)且僅當(dāng)是高斯分布時，上式等號成立。綜上所述，隨機(jī)變量X服從對稱指數(shù)分布，失真函數(shù)為d(x,y)=|x–y|，求信源的R(D)。，令，得且得對進(jìn)行傅立葉變換由，得且當(dāng)時設(shè)有平穩(wěn)高斯信源X(t)，其功率譜為，失真度量取，容許的樣值失真為D。試求：信息率失真函數(shù)R(D)；用一獨立加性高斯信道（帶寬為，限功率為P，噪聲的雙邊功率譜密度為）來傳送上述信源時，最小可能方差與的關(guān)系。（1）對于時間連續(xù)的平穩(wěn)高斯信源，當(dāng)功率譜密度已知時，在本題中即（2）信道容量為bit/s由定理可知，當(dāng)時，可以采用最佳編碼，其硬氣的錯誤小于等于D。取,求得最小均方誤差D。令，得時，時，時，由于所以如下圖：某工廠的產(chǎn)品合格率為99%，廢品率為1%。若將一個合格產(chǎn)品作為廢品處理，將損失1元；若將一個廢品當(dāng)作合格產(chǎn)品出廠，將損失100元；若將合格品出廠，廢品報廢，不造成損失。試分析質(zhì)量管理中各種情況造成的損失及付出的代價。解根據(jù)題意有信源空間：好（合格）廢（廢品）P(好)=0.99P(廢)=0.01選擇失真函數(shù)為d(好，好)=0d(廢，廢)=0d(好，廢)=10d(廢，好)=100失真矩陣為可將產(chǎn)品檢驗分成如下4種情況：全部產(chǎn)品都當(dāng)合格品，全部產(chǎn)品都當(dāng)廢品，完美的檢驗和允許出錯的檢驗。下面分別進(jìn)行討論。情況1全部產(chǎn)品不經(jīng)檢驗而出廠——都當(dāng)合格品。把這一過程看作是一個“信道”，其“傳遞概率”為P(好/好)=1 P(廢/好)=0 P(好/廢)=1 P(廢/廢)=0信道矩陣為這種情況的平均損失，即平均失真度，為=P(好)P(好/好)d(好,好)+P(好)P(廢/好)d(好,廢)+P(廢)P(好/廢話)d(廢,好)+P(廢)P(廢/廢)d(廢,廢)=0.011100=1元/個情況2全部產(chǎn)品不經(jīng)檢驗全部報廢——都當(dāng)廢品這時的信道傳輸概率為P(好/好)=0 P(廢/好)=1 P(好/廢)=0 P(廢/廢)=1信道矩陣為平均失真度為

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