信息論、編碼與密碼學(xué)課后習(xí)題答案

《信息論、編碼與密碼學(xué)》課后習(xí)題答案第1章信源編碼考慮一個(gè)信源概率為｛0.30,0.25,0.20,0.15,0.10｝的DMS求信源嫡H(X)。5解：信源嫡h(x)=-￡P(guān)klog2(Pk)k=1H(X)=-[0.30*(-1.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0.1*(-3.322)]=[0.521+0.5+0.464+0.411+0.332]=2.228(bit)故得其信源嫡H(X)為2.228bit證明一個(gè)離散信源在它的輸出符號(hào)等概率的情況下其嫡達(dá)到最大值。解：若二元離散信源的統(tǒng)計(jì)特性為P+Q=1H(X)=-[P*10g(P)+(1-P)*10g(1-P)]對(duì)H(X)求導(dǎo)求極值，由dH(X)/d(P)=0可得log可知當(dāng)概率P=Q=1/2時(shí)，有信源嫡H(X)max=1(bit)對(duì)于三元離散信源，當(dāng)概率R=F2=F3=1/3時(shí)，信源嫡H(X)max=1.585(bit),此結(jié)論可以推廣到N元的離散信源。1.3證明不等式lnxEx-11.3證明不等式lnxEx-1。畫出曲線X=皿乂和y2=x-1的平面圖以表明上述不等式的正確性。證明：f(x)=lnx-x1(x.0)f(x)」x令f(x)=0,x=1又有x0.0：：:xM1時(shí)f(x)0此時(shí)f(x)Wfmax=0也即lnx_x-1當(dāng)x_1時(shí)同理可得此時(shí)Inx_x-1綜上可得lnx三x-1證畢繪制圖形說明如下可以很明確說明上述不等式的正確性。證明I(X;Y)至0。在什么條件下等號(hào)成立?nm|(X;Y)f'、P(xi,yj)I(xi,yj)i3jTnmP(xnmP(xi,yj)10gijP(xi,yj)

P(xi)P(yj)當(dāng)和相互獨(dú)立時(shí)等號(hào)成立。有一個(gè)信源X,它有無窮多個(gè)可能的輸出，它們出現(xiàn)的概率為P(Xi)=2i-1,i=1,2,3,,.，這個(gè)信源的平均自信息H(X)是什么？解：因?yàn)镻(Xi)=2i-1,i=1,2,3,,n所以H(X)=-Ep(xi)10gp(xi)i1

=-log2(2+2.22+3.23+,..+n,2n)=2-(1-n)2n+1考慮另一個(gè)幾何分布的隨機(jī)變量X,滿足P(Xi)=P(1-P)i-1i=1,2,3,,..,這個(gè)信源的平均自信息H(X)是什么？解：因?yàn)镻(Xi)=P(1-P)i-1,i=1,2,3,n所以H(X)=-%p(xi)logp(xi)i=4=-logp(1-p)[p(1-p)+2p(1-p)2+3p(1-p)3+,,.+np(1-p)n]2=(1-n)(1-p)n-0?——Lp考慮一個(gè)只取整數(shù)值的隨機(jī)變量X,滿足P(X=n)=——,其中Anlogn.二1A=￡-,n=2,3,…戶。求嫡H(X)。n=2nlogn解：為了方便計(jì)算，設(shè)B=nlog2n,則A=￡工，P(X=n尸1—;根據(jù)公式計(jì)算自信息量為：I(X)=log則嫡為：HX="PXIX根據(jù)公式計(jì)算自信息量為：I(X)=log則嫡為：HX="PXIX="—logAB='、ABn=2n=210gAB

AB00=￡n=2UH1、logBZ—I?n3■'1,B"-n^B計(jì)算概率分布函數(shù)為p(x)=<p(x)=<0-x-a

(否則)的均勻分布隨機(jī)變量X的均勻分布隨機(jī)變量X的微分嫡H(X)。畫出H(X)相對(duì)于參數(shù)a(0.1<a<10)的平面圖，并對(duì)結(jié)果進(jìn)行評(píng)論。-bo解：根據(jù)公式(1-21)可知，微分嫡為：H(X)=—Jp(xJogpxdx3當(dāng)0Mxwa時(shí)，p(x)=a，,則a1.1.HX=-alogadxa1.1.HX=-alogadx0=1loga」xaaloga

aa二loga當(dāng)x<0或x>a時(shí)，p(x)=0，則H(X尸比根據(jù)得到的結(jié)果可以畫出相應(yīng)的平面圖，由圖可以看到隨著a的增加，即p(x)的減小，微分嫡H(X用應(yīng)的增加?？紤]一個(gè)信源的概率為6.35,0.25,0.20,0.15,0.05｝的DMS(1)給出此信源的霍夫曼碼。(2)計(jì)算出這些碼子的平均碼長(zhǎng)Ro(3)這個(gè)碼的效率“是多少？解：1)依題意，由霍夫曼編碼的規(guī)則，得：

表格如下:概率1X10.351.5151X20.252.00001X30.202.322000X40.152.7380010X50.054.3220011nX0.35X0.35X20.25X30.20X40.15X50.0510.6500.40000.200112)由平均碼長(zhǎng)公式R=￡n(Xk)■p(Xk)，代入數(shù)據(jù)，得：k=1—5R=n(xk)p(xk)=1(0.35)2(0.25)3(0.20)k=14(0.15)5(0.05)=0.350.50.60.60.25=2.3(bit)3)首先，該信源的嫡為：H(X)=八pklog2pk=-(0.35log20.350.2510g20.25k=10.201og20.200.151og20.150.051og20.05)=-(-0.351.515-0.252.0-0.202.322-0.152.738-0.054.322)=-(-0.5303-0.5-0.4644-0.4107-0.2161)=-(-2.1215)=2.1215(bit)該碼的效率為：=HCX)=(2.1215/2.300)=0.9224R考慮一個(gè)信源概率為{0.35,0.20,0.15,0.15,0.10,0.10,0.05,0.05}的DMS(1)給出此信源的一種有效定長(zhǎng)碼。(2)給出此信源的霍夫曼碼。(3)比較這兩種碼并給出評(píng)論。解：1）空2）依題意，由霍夫曼編碼的規(guī)則，得

概率1x10.202.32201x20.202.322000X30.152.738001X40.152.738100X50.101.000101X60.101.000110X70.054.3221110X80.054.32211113)空一個(gè)DMSR有三個(gè)輸出符號(hào)，它們的概率為{0.5,0.4,0.1}(1)給出此信源的霍夫曼碼并確定編碼效率。(2)每次考慮兩個(gè)符號(hào)時(shí)，給出此信源的霍夫曼碼并確定編碼效率

(3)每次考慮三個(gè)符號(hào)時(shí)，給出此信源的霍夫曼碼并確定編碼效率解：(1)本題的霍夫曼編碼如下圖所示：0.50.40.50.40~0.51.0圖1.11霍夫曼編碼則霍夫曼碼如下表:符號(hào)概率碼字X10.51X20.400X30.101該信源的嫡為：3H(X)=4pklog2Pkk二=一(0.5log20.50.4log20.40.1log20.1)=0.50000.52880.3322=1.3610Qit)平均每個(gè)符號(hào)的比特?cái)?shù)為：_3R「n(xQp(Xk)k=1=1(0.5)2(0.4)2(0.1)=0.50.80.2=1.5000(bit/符號(hào))該碼的效率為：=1.3160/1.50000.9073(2)把符號(hào)每?jī)蓚€(gè)分一組，重新應(yīng)用霍夫曼編碼算法，如下表所示:符號(hào)對(duì)概率碼字X1X10.2500X1X20.20010X2X10.20011X2X20.161010X1X30.05100X3X10.05110X2X30.041011X3X20.041110X3X30.011111該信源的嫡為:92H(X)=T,Pklog2Pk=2.7219(bit)kW=H(X)=1.3610?it)每個(gè)組的平均比特?cái)?shù)為：_9R=、n(Xk)P(Xk)k1-2(0.25)3(0.2)3(0.2)4(0.16)3(0.05)3(0.05)4(0.04)4(0.04)4(0.01)=3.00(bit/符號(hào)對(duì))=R=3.00/2=1.5000bit/符號(hào))故該碼的效率為：=1.3160/1.50000.9073(3)依題意，把符合每三個(gè)分成一組，再重新應(yīng)用霍夫曼編碼算法，得：

XdXXd012500X1X1X20.100000.2000XiX2X10100010X2XiXi0.10000X1X2X20.080010.2400X2X1X20.080000.16001XXX0080010X2X2X20.06400.185010.5800xl0.025000.0500011X^^X3X10.02500.34001.0000X3X1X10.025000.04500.14001010X1X2X30.02000.08500.4200011X1X3X20.02000.04000.2350x2x1x30.02000x2x3x10.02000.0400X3X1X20.02000.07600.1100X3X2X10.020000.0360x2x2x3001601110.0320X2X3X20.01600XXX0.016010編碼表格如下:概率自信息為X1X10.12502.7090100X1X1X20.10003.32230000X1X2X10.10003.32230001X2X1X10.10003.3223110X1X2X20.08003.6443011

概率1x2xix20.08003.64430100x2x2X10.08003.64430101x2x2x20.06403.96620011X1X1X30.02505.3223101104x3x10.02505.322310111x3x〔xi0.02505.322311100*1x2x30.02005.6444111012x3x20.02005.644411110x22x30.02005.644411111x2x3x10.02005.6444001000x32x20.02005.6444001001x3x2a0.02005.6444001010x2x2x30.01605.9664001011x2x3x20.01605.9664101000x3x2x20.01605.9664101001Xx3x30.00507.66461010101x3x1x30.00507.664610101000x3x3、0.00507.664610101001x2x3x30.00407.966610101100x3x2x30.00407.966610101101x3x3x20.00407.966610101110符號(hào)對(duì)概率自信息碼字X3X3X30.00109.9668101011111.14確定下列比特流的Lempel-Ziv碼0100111110010100000101010110011000隊(duì)碼字流恢復(fù)原來的序列。解：根據(jù)Lempel-Ziv算法列出下表:字典位置字典內(nèi)容定長(zhǎng)碼字00010000000010100001001100000100100110010101011110100101100010011101110100011100000000110100100100110010101000100101110110101110110010100111011001000111100010000第2章信道容量和編碼2.1考慮圖2-10所示的二元信道，設(shè)發(fā)送二元符號(hào)的先驗(yàn)概率為R和Pi,其中解：P'X=0；=p2.1考慮圖2-10所示的二元信道，設(shè)發(fā)送二元符號(hào)的先驗(yàn)概率為R和Pi,其中解：P'X=0；=p0P(X=1；=p1P1Y=ix=0}=pP1Y=0X=l}=qP〈Y=0X=0}=1-pP1Y=1X=l}=1-qP'X=0,Y=0)=P：X=0：P[Y=0X=0)=P：Y=0)P[X=0Y=0)P'：X-0Y=0；=P〔X=0〉P〔Y=0X=0}p01-pP1Y=0)pq1-pp〔qP(Y=0；=P1X=0)P'Y=0X=0}P(X=1：P：Y=0X=1)=p01-pp1qP《X=1,Y=1}=P1X=1p{y=1X=1}=P1Y=1》五權(quán)=1丫="P*=1Y=。=P〈X=1)P(Y=1|XHP'Y=1)p11-q

popp11-qP〈Y=1}=pH=qPy=1X=0}+P1X=My=1X=1}=p°pp11—q2.5(1)一個(gè)電話信道具有帶寬3000Hz，且SNR=20dB.求信道容量(2)若SNR增力口至ij25dB,求信道容量。解：⑴SNR=20dB=100信道容量=亞10§2(1+SNR/W)(b/s)=3000*1og2(1+100/3000)=142(b/s)SNR=25dB=316信道容量=亞由92(1+SNR/W)(b/s)=3000*log2(1+316/3000)=413(b/s)假定一個(gè)電視每秒鐘顯示30個(gè)畫面，每個(gè)畫面大約有2M105個(gè)像素，每個(gè)像素需要16比特的彩色顯示。假定SNR為25dB,計(jì)算支持電視信號(hào)傳輸所需要的帶寬(利用信息容量定理)解：根據(jù)題意，該電視信號(hào)所需的信息容量為：C=30210516bit/s=9.6107bit/sP..p根據(jù)信息谷量定理：C=Wlog2(1+—^),其中一為信噪比，據(jù)題意NoWNoP——二25dBNo據(jù)上式解得帶寬C1.15107Hz考慮圖2-15所示的Z型信道。(1)求獲得信道容量所需要的輸入概率。(2)若將N個(gè)這樣的信道相級(jí)聯(lián)，證明聯(lián)合信道可以用一個(gè)信道轉(zhuǎn)移概率

的等價(jià)Z信道表示(3)當(dāng)Ntg時(shí)聯(lián)合信道的容量是什么?解：⑴w為帶寬P信道容量C=Wlog2(1)(b/s)INnVVC二Blog2(1。)(2)由圖可知信道轉(zhuǎn)移概率為PP(0|1)=P(1|0)=P那么N級(jí)級(jí)聯(lián)的信道轉(zhuǎn)移概率P(0|1)NP(0|1)N級(jí)級(jí)聯(lián)pW⑶當(dāng)Nt8時(shí)P(0|1)級(jí)聯(lián)信道的信道容量為每一次使用該信道時(shí)的最大平均互信息。其中最大值是在所有可能的輸入概率上求得的即:C=maxI(x;y)P(y區(qū))

P(yJP(y區(qū))

P(yJq-1r-1C=max''P(xj)P(yj|xj)logp(Xj)j=0i=02.10(1)證明對(duì)有限方差。2,高斯隨機(jī)變量具有所有隨機(jī)變量可能獲得的最大微分嫡。(2)證明該嫡由公式1/2log2(2necr2)給出。證明：(1)由題意可知，高斯隨機(jī)變量獲得的微分嫡為：2H(X)log2(2二ec)則有：212H(X);--e2二e即其平均功率為：了=，e2H(X)

2二e對(duì)于有限方差仃2的高斯隨機(jī)變量，即當(dāng)平均功率受限時(shí)，有：1p(x)dx=1,](x-m)2p(x)dx=二2.即有：H(X)_log2,2二ec-綜上可得，對(duì)于平均功率受限的連續(xù)隨機(jī)變量，當(dāng)服從高斯分布時(shí)具有最大微分嫡。(2)隨機(jī)變量的微分嫡為：TOC\o"1-5"\h\zH(X)=--p(x)log2P(x)dx⑴對(duì)于高斯分布，我們有：,、1,1,、2、(2)p(x)=--=7exp{-27?(x-m))(2)其中，m為數(shù)學(xué)期望。將(2)式代入(1)可得:H(X)=11,、2H(X)=1：p(x)[1n,2三一/(x-m)]dx由(3)式可以推出：12H(X)=—log2(2二5)(4)2故(4)式即為本題所證。2.11寫一個(gè)程序，它在輸入信道轉(zhuǎn)移矩陣后計(jì)算出信道容量？解：依據(jù)設(shè)定情況在一般的二元通信信道輸入前只有兩種狀態(tài)，杯口1,假設(shè)傳輸發(fā)生錯(cuò)誤概率為p,正確概率為1-p.這只是假定的一種情況，其實(shí)在程序中可看作這幾個(gè)參量為個(gè)數(shù)組。CP[]及WP口。再根據(jù)計(jì)算信道容量公式q1rlp(v"xDmax￡￡p(xj)p(yi|Xj)log，輸出對(duì)應(yīng)的信道谷重值。"itp(yi)第3章糾錯(cuò)控制編碼3.1證明C=6000,1100,0011,1111｝是一個(gè)線性碼。它的最小距離是什么？證明：由書中的定義3.8可知，線性碼應(yīng)該滿足一下條件：（1）兩個(gè)屬于該碼的碼字的和仍然是一個(gè)屬于該碼的碼字，（2）全零字總是一個(gè)碼字，（3）兩個(gè)碼字之間的最小距離等于任何非零碼字的最小重量，即d*=w*設(shè)C=QC2,C3,cj,即G=0000,C2=1100,q=0011,C4=1111,首先證明條件（1）:60=1100=3,GC3=0011=c3,GC4=1111=c4,c2c3=1111=c4,c2c4=0011=c3,c3c4=1100=c2,很明顯，條件（1）是滿足的。條件（2）也是顯然成立的。最后證明條件（3）:不難看出最小距離d*=2,并且最小重量w*=2,即d*=w*綜上，三個(gè)條件都滿足，那么C就是一個(gè)線性碼，它的最小距離是2。3.3考慮GF（2）上的下列生成矩陣「10100、G=10011101010,3）用此矩陣生成所有可能的碼字。4）求奇偶校驗(yàn)矩陣H5）求與其等價(jià)的一個(gè)系統(tǒng)碼的生成矩陣。6）構(gòu)造該碼的標(biāo)準(zhǔn)陣列。7）這個(gè)碼的最小距離是多少。8）這個(gè)碼能檢測(cè)多少錯(cuò)誤。9）寫出這個(gè)碼能檢測(cè)的所有錯(cuò)誤模式。

10）這個(gè)碼能糾多少個(gè)錯(cuò)誤。11）如果我們用此編碼方案，那么符號(hào)錯(cuò)誤概率是多少？將它與末尾的錯(cuò)誤概率進(jìn)行比較12）這是一個(gè)線性碼?1解：1解：(1)c1=(000)1?0011=(00000)1010,TOC\o"1-5"\h\z「101c2=(001)1001010[01C3=(010)100010101C4=(011)|100010101C5=(100甲00010101C6=(101)|100010101C7=(110)|10001000'11=(01010)10J00、11=(10011)1o,00、11=(11001)10」00'11=(10100)10/0011=(11110)10，00、11=(00111)10」001=(01101)0>1010C8=(11110010101此矩陣生成的碼為：{00000,01010,10011,11001,10100,11110,00111,01101}(2)G=，11L011-10-111-11、0-1」PT-r-1」又在二元情況下，1--1PT101J奇偶校驗(yàn)矩陣可寫為:H-JPT1111{010(4該碼的標(biāo)準(zhǔn)陣列11-1(5)奇偶校驗(yàn)矩陣H的第1、3列的和為零向量,因此，這個(gè)碼的最小距離為:d*=20(6)一個(gè)碼至少可以檢測(cè)所有重量小于或等于(d*-1)的非零錯(cuò)誤模式。這個(gè)碼的最小距離為：d*=2,所以重量為1的錯(cuò)誤模式可以檢測(cè)得到。(7)這個(gè)碼能檢測(cè)的所有錯(cuò)誤模式{00001,00010,00100,01000,10000}(8)能糾正不多于t個(gè)錯(cuò)誤應(yīng)滿足d*之2t+1又d*=2所以2_2t1即出這個(gè)碼能糾0個(gè)錯(cuò)誤(9)才vv11110,00111,01101}(10){00000,11110,00111,01101}線性碼的性質(zhì):1、兩個(gè)屬于該碼的碼字的和仍是屬于該碼的碼字00000+01010=0101000000+10011=1001100000+11110=1111000000+01101=0110101010+10011=1100101010+10100=1111001010+00111=0110100000+11001=1100100000+10100=1010000000+00111=0011101010+11001=1001101010+11110=1010001010+01101=0011110011+11001=0101010011+11110=0110110011+01101=1111011001+10100=0110111001+00111=1111010100+11110=0101010100+01101=1100111110+00111=1100110011+10100=0011110011+00111=1010011001+11110=0011111001+01101=1010010100+00111=1001111110+01101=1001100111+01101=01010滿足第一條性質(zhì)2、全零碼字總是一個(gè)碼字{00000,01010,10011,11001,10100,11110,00111,01101}滿足第二條性質(zhì)3、一個(gè)線性碼的兩個(gè)碼字之間的最小距離等于任何非零碼字的最小重量,即d*=w*即d*=w*D(00000,01010)=2D(00000,11001)=3D(00000,11110)=4D(0000001101)=3D(0101010011)=3D(0101010100)=4D(0101000111)=3D(0000010011)=3D(0000010100)=2D(0000000111)=3D(0101011001)=2D(0101011110)=2D(0101001101)=3{00000,01010,10011,11001,10100,11110,00111,01101}D(1001111001)=2D(1001111001)=2D(1001111110)=3D(1001101101)=4D(1100110100)=3D(1100100111)=4D(1010011110)=2D(1010001101)=3D(1111000111)=3D(1001110100)=3D(1001100111)=2D(1100111110)=3D(1100101101)=2D(1010000111)=3D(1111001101)=3D(0011101101)=2這個(gè)碼的最小距離為2等于該碼的最小重量滿足第三條性質(zhì)所以，這個(gè)碼是線性碼。3.4構(gòu)造C={00000,10101,01010,11111}的生成矩陣。因?yàn)檫@個(gè)G不是唯

a1na1n■,由題知，m=2,n=5,amna11…解：設(shè)生成矩陣是G=-ami…i=(0,0)(0,1),(1,0),(1,1)i=(0,0)(0,1),(1,0),(1,1)G=0101010101G=01010101013.7對(duì)下列每一個(gè)集合S,列出擴(kuò)張碼<S>:S={0101,1010,1100}S={1000,0100,0010,0001}S={11000,01111,11110,01010}解：0101+1010=1111,0101+1100=10011010+1100=0110,0101+1010+1100=0011再補(bǔ)上0000及原先3個(gè)公共組成第二，三問步驟省略S吻{1111,1001,0110,0011,0000,0101,1010,1100}⑵S吻{1100,1010,1001,0110,0101,0011,1110,1011,0111,1101,1111,0000,1000,0100,0010,0001}⑶S吻{10111,00110,10010,10001,00101,10100,01001,11000,01111,11110,01010,00000,11011,01100,11101}3.8考慮(23,12,7)二元碼。證明若它被用在一個(gè)比特錯(cuò)誤概率為p=0.01的二元對(duì)稱信道(BSC中，字錯(cuò)誤概率將約為0.00008解：由題可得其轉(zhuǎn)移概率p=0.01,在(23.12.7)二元碼中其可以糾出2t+1>=7t=3位錯(cuò)誤即在碼元中出現(xiàn)4個(gè)錯(cuò)才會(huì)使得其出現(xiàn)誤碼率，出現(xiàn)3個(gè)以上錯(cuò)誤的概率為TOC\o"1-5"\h\z2323'《3火1-P)23-n，C，nMn^40023c1122c2221^3320二1一C23Pq一C23Pq一C23Pq一C23Pq=0.00008則出現(xiàn)的誤字率為0.00008所以得證。3.9假設(shè)C是一個(gè)二元碼，它的奇偶校驗(yàn)矩陣為H。證明由C通過添加整體奇偶校驗(yàn)比特得到的擴(kuò)展碼G的奇偶校驗(yàn)矩陣為TOC\o"1-5"\h\z一1。1|0H1=H「.I_|01二1|1_證明：根據(jù)題意，擴(kuò)展碼G為：一|。1|0G=|C「，又「C得奇偶校驗(yàn)矩陣為H，-CHT=00—|0…1|0_H；ht1|1I-|:|1|1■C■CiH；=10〕0：=0000|0]一|0|—ht|0ITOC\o"1-5"\h\z|0_00二一|1|:=CHT|1|01-00即擴(kuò)展碼G的奇偶校驗(yàn)矩陣為H1證畢3.11設(shè)C是長(zhǎng)度為n,最小距離為7的二元完備碼。證明n=7或n=23。證明：由完備碼的定義可知，一個(gè)完備碼必須滿足下列條件：t2n“-cn⑴i=0由題意可知：d之2t+1,其中d=7即有：t<3當(dāng)n=7當(dāng)n=7時(shí)，由（1）式可得,右式展開得:3cc7=c；+c7+c；+c；i-0=172135=64=左式同理，可證得n=23時(shí)，同樣滿足（1）式故可證明當(dāng)n=7或n=23時(shí)，c是二元完備碼3.12用%來表示二元漢明碼的碼率，求limrH。k二解：根據(jù)二元漢明碼的性質(zhì)可知：(n,k)=(2m-1,2m-1-m)其中m是任意正整數(shù)。則由碼率的定義可知：k2m-1-mrH=7=2m1n2-1則有：2m-1-m

limrH=lim=1k=：Hi2m-1第4章循環(huán)碼4.1下面的哪個(gè)碼是(a)循環(huán)碼，(b)與一個(gè)循環(huán)碼等價(jià)？GF(2止白6000,0110,1100,0011,1001)。GF(2讓白60000,1011Q01101,11011}。GF(3止白向<00000,10110,01101,11011。GF(3止白幻000,1122,2211}。(5)長(zhǎng)度為n的q-元重復(fù)碼。解：由書中定義4.1可知，循環(huán)碼需要滿足兩個(gè)條件，(1)首先它必須是一個(gè)線性碼，(2)其次它的一個(gè)碼字的任意循環(huán)移位的結(jié)果還是一個(gè)碼字，即若

a0,a1,...,an」為其中的一個(gè)碼字，則2口」,注,...田口二也是其中一個(gè)碼字。下面一一證明：(1)首先證明G是一個(gè)線性碼：設(shè)C1={q,C2,C3,C4,C5},則G=0000,C2=0110,C3=1100,C4=0011,C5=1001,Gc2=0110=c2,gc3=1100=c3,gc4=0011=c4,gc5=1001=c5,c2c3=1010=?,01=0101=？，c2c5=1111=？，C3c4=1111"？，C3C5=0101=?,C4C5=1010=?顯然C1不滿足線性碼的第一個(gè)條件，則它不是一個(gè)線性碼，就不可能是一個(gè)循環(huán)碼。(2)首先證明C2是一個(gè)線性碼：設(shè)C2=b,C2,C3,C4},則6=00000,C2-10110,6=01101,C4=11011,C1C2=10110”，gc3=01101=c3,gc4=11011=c4,c2c3=11011=c4,c2c4=01101=03,c3c4=10110=C2

C2C2滿足線性碼的第一個(gè)條件，顯然第二個(gè)條件也滿足C2中的最小距離d*=3,最小重量w*=3,即d*=w*=3,C2也滿足第三個(gè)條件，可知C2是一個(gè)線性碼。下面證明C2是循環(huán)的，0=10110,經(jīng)過循環(huán)移位之后得到的碼字是02=01011,這個(gè)碼字不是C2中的碼字，即C2不滿足循環(huán)碼的第二個(gè)條件。綜上可知，C2不是一個(gè)循環(huán)碼，但是它與一個(gè)循環(huán)碼等價(jià)。(3)首先證明C3是一個(gè)線性碼：設(shè)C3=6,02,03,c4),則G=00000,02=10110,03=01101,04=11011,c102=10110=02,g03=01101=03,g04=11011=04,0203=11211二？，0204V21121=?,0304V12112=?顯然C3不滿足線性碼的第一個(gè)條件，則它不是一個(gè)線性碼，就不可能是一個(gè)循環(huán)碼。(4)首先證明C4是一個(gè)線性碼：設(shè)C4=b,02,03},則01=0000,02=1122,03=2211,GQ=1122=q,Gq=2211=03,0203=0000=GC4滿足線性碼的第一個(gè)條件，顯然第二個(gè)條件也滿足。C4中的最小距離d*=4,最小重量w*=4,即d*=w*=4,C4也滿足第三個(gè)條件，可知C4是一個(gè)線性碼。下面證明C4是循環(huán)的，02=1122,經(jīng)過循環(huán)移位之后得到的碼字是02=2112,這個(gè)碼字不是C4中的碼字，即C4不滿足循環(huán)碼的第二個(gè)條件。綜上可知，C4不是一個(gè)循環(huán)碼，但是它與一個(gè)循環(huán)碼等價(jià)。(5)長(zhǎng)度為n的q-元重復(fù)碼，假設(shè)n=3,q=2,則〃1111111“，可知其不為線性碼，也定不為循環(huán)碼。4.2為下列定義的多項(xiàng)式環(huán)構(gòu)造加法和乘法表

(1)定義在GF(2)上的(2)定義在GF(3)上的解：(1)(1)定義在GF(2)上的(2)定義在GF(3)上的解：(1)首先判斷得環(huán)的多項(xiàng)式的最高次數(shù)=1,環(huán)中有四個(gè)元素,分別為0,1,x,x+1.所得加法表如下:+01xX+1001xX+11101+xxxxX+101X+1X+1x10乘法表如下:.01xX+100000101xX+1x0x1X+1X+10X+1X+10(2)加法表如下:+012xX+1X+22x2x+12x+20012xX+1X+22x2x+12x+211201+x2+xx2x+12x+22x2201X+2xX+12x+22x2x+1xxX+1X+22x2x+12x+2012X+1X+1X+2x2x+12x+22x120X+2X+2xX+12x+22x2x+12012x2x2x+12x+2012xX+1X+2

2x+12x+12x+22x120X+1X+2x2x+22x+22x2x+1201X+2xX+1乘法表如下:.012xX+1X+22x2x+12x+200000000001012xX+1X+22x2x+12x+220212x2x+22x+1xX+2x+1x0x2x2X+22x+21X+12x+1X+10X+12x+2X+22x12x+12xX+20X+22x+12x+21xX+12x22x02xx12x+1X+122x+2x+22x+102x+1X+2X+122x2x+2X12x+202x+2X+12x+1x2X+212x4.4找出所有分組長(zhǎng)度為5的二元循環(huán)碼，求出每個(gè)碼的最小距離。解：要找到分組長(zhǎng)度為5的所有2元循環(huán)碼，首先要分解x5-1x5T=(x-1)(x4x3x2x1)在GF(2)中，(x4+x3+x2+x+1)是既約的，所求的循環(huán)碼為：c(x)=i(x)第(x)定義在R中的多項(xiàng)式i(x)=24=16個(gè)，信息多項(xiàng)式和對(duì)應(yīng)的碼字多項(xiàng)式在下表中列出：ii(x)c(x)c000000,00000000011x+1,x4+x3+x2+x00011,111010010xx2+x,x4+x3+x2+x00110,11111

0011x+125x+x,x+x00110,100010100x23x+x010100101x2+1x3+x2+x+1011110110x2+xx3+x010100111x2+x+1x3+1010011000x34_i_3x4+x110001001x3+1x4+x3+x+1110111010x3+xx4+x3+x2+x111101011x3+x+1x4+x3+x2+1101011100x3+x2x4+x2101001101x3+x2+1x4+x2+x+1101111110x3+x2+xx4+x3110001111x4+x3+x2+1x4+110001故不同的碼字有:碼字最小碼距000000000112001102111014111110100012101012011114010012110002110114111014101002

1011141111044.7設(shè)多項(xiàng)式108542g(x):xxxxxx1為GF(2)上分組長(zhǎng)度為15的一個(gè)循環(huán)碼的生成多項(xiàng)式⑴求生成矩陣G.o(2)求奇偶校驗(yàn)矩陣H(3)這個(gè)碼能檢測(cè)多少個(gè)錯(cuò)誤？(4)這個(gè)碼能糾多少個(gè)錯(cuò)誤？(5)將生成矩陣寫成系統(tǒng)型。解：(1)由生成多項(xiàng)式g(x)=x10+x8+x5+x4+x2+x+1可知:生成矩陣為:111011G=001111011G=001000000011010111101111001110101001010011100011000001000010010100101(2)由于已知分組長(zhǎng)度為15,設(shè)奇偶校驗(yàn)多項(xiàng)式為h(x),則有:x15-1=g(x)h(x)即:15108542h(x)=x-1/(xxxxxx1)5=5=xx3x其中，上式為取模運(yùn)算故，對(duì)應(yīng)的奇偶校驗(yàn)矩陣為:

ii(x)c(x)=i(x)g(x)c00o0000000000000000011g(x)00001010011011110xxg(x)00010100110111011x+1(x+1)g(x)000111110100101101010010101000101010H=10010101?????????????????????0000000(3)建立如下表格：0000000000010000000000100000001011015由該表格可以看出，該碼的最小距離為7即：d*=7故可知，該碼可以檢測(cè)d*-1=6個(gè)錯(cuò)誤.一r*一》?⑷由于d=7,則有：7至2t+1即：t<3故該碼可以糾3個(gè)錯(cuò)誤(5)該生成矩陣的系統(tǒng)型為:一10G=[I|P]=00一10G=[I|P]=00■000010001000100000001001100111111010101010101110101101101100110001011014.11生成多項(xiàng)式為g(x)=(x23+1)(x17+x3+1)的碼在GSM中作檢錯(cuò)和糾錯(cuò)標(biāo)準(zhǔn)(1)這個(gè)碼能糾多少個(gè)隨機(jī)錯(cuò)誤？(2)這個(gè)碼能糾多少個(gè)突發(fā)錯(cuò)誤？解：g(x)=(x12241)(x17x31)=x40x26x21x17x31.t=12,n-k=40又經(jīng)過嘗試我們得到分組長(zhǎng)度是滿足g(x)且能整除x23-1的最小整數(shù)n=75,.k=75-40=352x<k=35,x<5可以糾的突發(fā)錯(cuò)誤最多為t=12個(gè)；能糾的隨機(jī)錯(cuò)誤為x=5個(gè)。第5章BCH馬5.1用一個(gè)合適的本原多項(xiàng)式由GF(3胸造GF(9卜解：考慮由子域GF(3飽造擴(kuò)域GF(9),已知q=3,m=2,現(xiàn)在對(duì)xqm-1進(jìn)行分解，即在GF(3止分解，Xqm-1=X8-1H「：X1X-1X21X41下面考慮擴(kuò)域GF(9)上的元素，這些元素可以表示為：0z2zz12z1z22z2通過觀察GF(9)上的元素，我們可以選擇p(X)=X2+1作為本原多項(xiàng)式來構(gòu)造GF(9)?？紤]GF(9)上的元素，z并不是GF(9止的本原元，則我們可以假設(shè)GF(9)上的本原元為a=z+1,則可以通過a的幕模p(a相到GF(9)上的所有元素。經(jīng)過多項(xiàng)式的運(yùn)算可以得到GF(9)中的元素：口的曷GF(9上的元素

5.2找出分組長(zhǎng)度為26的糾三個(gè)錯(cuò)誤的三元BCHB的生成多項(xiàng)式g(x)依據(jù)確定可糾t個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式的步驟n=qm-1即3m-1=26,m=3.選取一個(gè)次數(shù)為3勺素多項(xiàng)式并構(gòu)造GF(27),令p(x)=x32x1Z的幕GF(27)的元素z1zZ2z2Z3Z+2Z4Z2+2zZ52z2+2z+1z6Z2+z+1Z72Z82z2+2Z91Z10Z2+zz11Z2+z+2z122z2+z+2Z132z142zZ152z2+1z16Z+2z17Z2+1z18z2Z19Z+2Z202z2+z+1Z21Z+1Z22Z2Z23Z2425Z5.4求下列碼的生成多項(xiàng)式和最小距離：(1)RS(15,11)碼。⑵RS(15,7)碼。⑶RS(31,21)碼。解：⑴由RS(15,11)碼可知，n=15,k=110則根據(jù)RS碼的性質(zhì)可知，n-k=2t即：2t=15-11=4一個(gè)RS碼的生成多項(xiàng)式可以寫成：g(x)=(x-")(x-"1)...(xT2ti」)(xT2t)故該RS(15,11)碼的生成多項(xiàng)式為：g(x)=(x-；：1)(x-；：2)(x-；：3)(x-；：4)我們這里用到擴(kuò)域GF(16)上的元素，該擴(kuò)域是由GF(2)以本原多項(xiàng)式p(z)=z/一13\3/-6\/一13\3/-6\2/一3\-10二x(二)x(二)x(二)x::該RS(15,11)碼的最小距離為：*.d-2t1=41=5⑵由RS(15,7)碼可知，n=15,k=7。根據(jù)RS碼的性質(zhì)：n-k=2t即：2t=15-7=8則有：g(x)=(x-c)(x-c2)(x-c3)(x-c4)4/323/32、23z2二x(z-z1)x(zz)xzx(zz1)

根據(jù)(1)題所涉及的Tt質(zhì)可知，RS(15,7)碼的生成多項(xiàng)式為：g(x)=(x-c)(x-c2)(x-c3333=27(mod11)=5,4=64(mod11)=9,5=125(mod11)=4,6=216(mod11)3333=27(mod11)=5,4=64(mod11)=9,5=125(mod11)=4,6=216(mod11)=773=343(mod11)=2,83=512(mod11)=6,93=729(mod11)=3,1°=1°°°(mod11)=1°2=16(mod11)=5,52=25(mod11)=3,62=36(mod11)=3,72=49(mod11)=522282=64(mod11)=9,92=81(mod11)=4,1°2=1°°(mod11)=1所以經(jīng)過計(jì)算，HT中滿足和為零的行向量的最小個(gè)數(shù)為7,d=2t+1,所以這d—1...個(gè)碼能糾t==3個(gè)錯(cuò)。證畢=[x4(.：13)x3(.：6)x2(.：3)x?°][x4(.：2)x3(.i)x2xF11]TOC\o"1-5"\h\z=x8(；：8)x7(.：1°)x6(；：2)x5(；：7)x4(.：14)x3-(；：14)x2(；：9)x；：6該RS(15,7)碼的最小距離為:一*_.___d_2t1=81=9⑶RS(31,21)碼中，t=5,d*=115.6考慮GF(11)上具有下列奇偶校驗(yàn)矩陣的碼5.6考慮GF(11)上具有下列奇偶校驗(yàn)矩陣的碼111I…1°…1°2…1°3(1)證明該碼糾三個(gè)錯(cuò)誤的碼(2)求該碼的生成多項(xiàng)式證明：ht11T1°1°1°1證明：ht11T1°1°1°12：3：12：3：1°1°21°3又因?yàn)樵贕F(11)中,矩陣中元素第6章卷積碼6.2設(shè)計(jì)一個(gè)（12,4）系統(tǒng)卷積編碼器使其約束長(zhǎng)度丫=3且~"之8（1）構(gòu)造該編碼器的網(wǎng)格圖。（2）該碼的dfree是什么？解：（1）由題意可知，n=12,k=4,且約束長(zhǎng)度為v=mkg=3可以得到m=3,k0=1,n0=3通過這些參量我們可以設(shè)計(jì)出編碼器，如下圖所示：這個(gè)編碼器每次把1比特輸入編碼成3比特的輸出。信息幀的長(zhǎng)度為ko=1,碼字幀的長(zhǎng)度為n0=3,分組長(zhǎng)度為12,該編碼器的約束長(zhǎng)度為v=m<=3,碼率為1/3。編碼器的狀態(tài)圖：（只有四種狀態(tài)）

01卷積編碼器輸入和輸出的比特如下表所示輸入比特編碼器當(dāng)前狀態(tài)編碼器之后狀態(tài)輸出比特0000000000100010010101000100101100110111001000111010101010110110011100111011100100010001011001100000010101011111011100100011001011101110111001110110011111111100編碼器的網(wǎng)格圖為:001001110002001110000110011001d；=2,d：=3,d：=5,d：=6因?yàn)閙=3,d4=d=6=dfree6.3考慮下圖所示的二元編碼器6.3考慮下圖所示的二元編碼器(1)構(gòu)造該編碼器的網(wǎng)格圖(2)記下該編碼器的k0,n0,v,m,R(1)輸入當(dāng)前狀態(tài)下一個(gè)狀態(tài)輸出000000000000100001000001010000100001110001100000001000010011101001010111011000110111111001110110000100001010100101001011010100101011110101101010001100011100101101011101011100111101111101111100k0(2)由圖可得k0=1,n°=3,v=4,v=mk°,彳寸m=4,R=—(2)由圖可得該碼的d*和dfree的值是多少？(3)解：由狀態(tài)表m=3則m+1級(jí)d=d1+d2+d3+d4=1+2+3+4=10dfree=max[dj]=86.4考慮圖6-36所示的二元編碼器圖6-36(1)寫出該編碼器的k,n,v,m及R的值。(2)給出該編碼器的生成多項(xiàng)式矩陣G(D)。⑶給出該編碼器的生成矩陣G⑷給出該編碼器的奇偶校驗(yàn)矩陣H(5)該編碼的d*、dfree和gree的值各是多少？(6)該編碼器在dfree的Heller界上是最優(yōu)的嗎？⑺用該編碼器將下列比特序列進(jìn)行編碼：101001001010000解：⑴由題意可知：m=4

由圖6-36可知：k0=3,n0=4o貝m:k=(m+1)k0=15,n=(m+1)no=20由約束長(zhǎng)度公式可得：v=mk=12由碼率公式可得：R=ko/n0=0.85⑵g/D)g14g/D)g14(D)g23(D)g24(D)g33(D)g34(D)g11(D)g12(D)G(D)=gMD)g22(D)91(D)932(D)DD2D2DD20D2DDD200D4D⑶由圖可知:00000000G0=0000,G00000000G4=0000,0010-01110,G2=10011p0000001,G3=0000-「00001000…]0…0…]0…0…G0GG2G3G4000G=00G0GG=00G0GG2G3G40將G°GG2G3G45個(gè)矩陣代入矩陣G中既可將G。GG2G3G45個(gè)矩陣進(jìn)行變換得:Go=[I|Po],Gi=D