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

..《信息論、編碼與密碼學(xué)》課后習(xí)題答案第1章信源編碼考慮一個信源概率為{0.30,0.25,0.20,0.15,0.10}的DMS。求信源熵H〔X。解：信源熵 H<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證明一個離散信源在它的輸出符號等概率的情況下其熵達到最大值。解：若二元離散信源的統(tǒng)計特性為 P+Q=1H<X>=-[P*log<P>+<1-P>*log<1-P>] 對H<X>求導(dǎo)求極值,由dH<X>/d<P>=0可得可知當概率P=Q=1/2時,有信源熵對于三元離散信源,當概率時,信源熵, 此結(jié)論可以推廣到N元的離散信源。1.3證明不等式。畫出曲線和的平面圖以表明上述不等式的正確性。證明：Y=lnxY=x-1yx1繪制圖形說明如下Y=lnxY=x-1yx1可以很明確說明上述不等式的正確性。1.4證明1.5有一個信源X,它有無窮多個可能的輸出,它們出現(xiàn)的概率為P〔Xi=2i-1,i=1,2,3,….,這個信源的平均自信息H〔X是什么？解：因為P〔Xi=2i-1,i=1,2,3,… 所以H〔X=- =-log2<2+2.22+3.23+…..+n.2n> =2-〔1-n2n+11.6考慮另一個幾何分布的隨機變量X,滿足P〔Xi=P〔1-Pi-1i=1,2,3,…..,這個信源的平均自信息H〔X是什么？ 解：因為P〔Xi=P〔1-Pi-1,i=1,2,3, 所以H〔X=- =-logp<1-p>[p<1-p>+2p<1-p>2+3p<1-p>3+…….+np<1-p>n] =<1-n><1-p>n+1-1.7考慮一個只取整數(shù)值的隨機變量,滿足,其中,。求熵。解：為了方便計算,設(shè),則,；根據(jù)公式計算自信息量為：；則熵為：=？1.8計算概率分布函數(shù)為的均勻分布隨機變量的微分熵。畫出相對于參數(shù)的平面圖,并對結(jié)果進行評論。解：根據(jù)公式〔1-21可知,微分熵為：當時,,則當或時,,則根據(jù)得到的結(jié)果可以畫出相應(yīng)的平面圖,由圖可以看到隨著的增加,即的減小,微分熵相應(yīng)的增加。000.1101.9考慮一個信源的概率為的DMS。給出此信源的霍夫曼碼。計算出這些碼子的平均碼長。這個碼的效率是多少？解：1依題意,由霍夫曼編碼的規(guī)則,得：1.000.650.400.200.350.250.200.150.05 表格如下：符號概率自信息碼字0.351.51510.252.000010.202.3220000.152.73800100.054.3220011由平均碼長公式,代入數(shù)據(jù),得：3首先,該信源的熵為：該碼的效率為：1.10考慮一個信源概率為{0.35,0.20,0.15,0.15,0.10,0.10,0.05,0.05}的DMS。<1>給出此信源的一種有效定長碼。<2>給出此信源的霍夫曼碼。<3>比較這兩種碼并給出評論。解：1空依題意,由霍夫曼編碼的規(guī)則,得:符號概率自信息碼字0.202.322010.202.3220000.152.7380010.152.7381000.101.0001010.101.0001100.054.32211100.054.3221111空1.11一個DMS只有三個輸出符號,它們的概率為{0.5,0.4,0.1}。<1>給出此信源的霍夫曼碼并確定編碼效率。<2>每次考慮兩個符號時,給出此信源的霍夫曼碼并確定編碼效率。<3>每次考慮三個符號時,給出此信源的霍夫曼碼并確定編碼效率。解：<1>本題的霍夫曼編碼如下圖所示：0.50.50.40.1010.5101.0圖1.11霍夫曼編碼則霍夫曼碼如下表：符號概率碼字x10.51x20.400x30.101該信源的熵為：平均每個符號的比特數(shù)為：該碼的效率為：〔2把符號每兩個分一組,重新應(yīng)用霍夫曼編碼算法,如下表所示：符號對概率碼字x1x10.2500x1x20.20010x2x10.20011x2x20.161010x1x30.05100x3x10.05110x2x30.041011x3x20.041110x3x30.011111該信源的熵為：每個組的平均比特數(shù)為:故該碼的效率為：<3>依題意,把符合每三個分成一組,再重新應(yīng)用霍夫曼編碼算法,得:編碼表格如下：符號對概率自信息碼字0.12502.70901000.10003.322300000.10003.322300010.10003.32231100.08003.64430110.08003.644301000.08003.644301010.06403.966200110.02505.3223101100.02505.3223101110.02505.3223111000.02005.6444111010.02005.6444111100.02005.6444111110.02005.64440010000.02005.64440010010.02005.64440010100.01605.96640010110.01605.96641010000.01605.96641010010.00507.664610101010.00507.6646101010000.00507.6646101010010.00407.9666101011000.00407.9666101011010.00407.9666101011100.00109.966810101111解：根據(jù)Lempel-Ziv算法列出下表：字典位置字典內(nèi)容定長碼字00010000000010100001001100000100100110010101011110100101100010011101110100011100000000110100100100110010101000100101110110101110110010100111011001000111100010000第2章信道容量和編碼2.1考慮圖2-10所示的二元信道,設(shè)發(fā)送二元符號的先驗概率為P0和P1,其中P0+P1=1,求后驗概率和。001P00P111-qpq1-p解：〔1一個信道具有帶寬3000Hz,且SNR=20dB.求信道容量?！?若SNR增加到25dB,求信道容量。解：<1>SNR=20dB=100信道容量=Wlog2<1+SNR/W><b/s>=3000*log2<1+100/3000>=142<b/s><2>SNR=25dB=316信道容量=Wlog2<1+SNR/W><b/s>=3000*log2<1+316/3000>=413<b/s>2.7假定一個電視每秒鐘顯示30個畫面,每個畫面大約有個像素,每個像素需要16比特的彩色顯示。假定SNR為25dB,計算支持電視信號傳輸所需要的帶寬〔利用信息容量定理解：根據(jù)題意,該電視信號所需的信息容量為：根據(jù)信息容量定理：,其中為信噪比,據(jù)題意據(jù)上式解得帶寬2.8考慮圖2-15所示的Z型信道。 〔1求獲得信道容量所需要的輸入概率。 〔2若將N個這樣的信道相級聯(lián),證明聯(lián)合信道可以用一個信道轉(zhuǎn)移概率為的等價Z信道表示。 〔3當時聯(lián)合信道的容量是什么？圖2-15解：<1>w為帶寬信道容量<b/s><2>由圖可知信道轉(zhuǎn)移概率為P那么N級級聯(lián)的信道轉(zhuǎn)移概率<3>當時級聯(lián)信道的信道容量為每一次使用該信道時的最大平均互信息。其中最大值是在所有可能的輸入概率上求得的即：2.10<1>證明對有限方差,高斯隨機變量具有所有隨機變量可能獲得的最大微分熵。<2>證明該熵由公式給出。證明：<1>由題意可知,高斯隨機變量獲得的微分熵為：則有：即其平均功率為：對于有限方差的高斯隨機變量,即當平均功率受限時,有：即有：綜上可得,對于平均功率受限的連續(xù)隨機變量,當服從高斯分布時具有最大微分熵。<2>隨機變量的微分熵為：<1>對于高斯分布,我們有：<2>其中,m為數(shù)學(xué)期望。將<2>式代入<1>可得：<3>由<3>式可以推出：<4>故<4>式即為本題所證。2.11第3章糾錯控制編碼3.1證明是一個線性碼。它的最小距離是什么？證明：由書中的定義3.8可知,線性碼應(yīng)該滿足一下條件：兩個屬于該碼的碼字的和仍然是一個屬于該碼的碼字,全零字總是一個碼字,兩個碼字之間的最小距離等于任何非零碼字的最小重量,即設(shè),即,,,,首先證明條件〔1：,,,,,,很明顯,條件〔1是滿足的。條件〔2也是顯然成立的。最后證明條件〔3：不難看出最小距離,并且最小重量,即綜上,三個條件都滿足,那么就是一個線性碼,它的最小距離是2。3.3考慮GF〔2上的下列生成矩陣用此矩陣生成所有可能的碼字。求奇偶校驗矩陣H。求與其等價的一個系統(tǒng)碼的生成矩陣。構(gòu)造該碼的標準陣列。這個碼的最小距離是多少。這個碼能檢測多少錯誤。寫出這個碼能檢測的所有錯誤模式。這個碼能糾多少個錯誤。如果我們用此編碼方案,那么符號錯誤概率是多少？將它與末尾的錯誤概率進行比較。這是一個線性碼？解：〔1========此矩陣生成的碼為：{00000,01010,10011,11001,10100,11110,00111,01101}又在二元情況下,奇偶校驗矩陣可寫為：<4該碼的標準陣列奇偶校驗矩陣H的第1、3列的和為零向量,因此,這個碼的最小距離為：d*=2。一個碼至少可以檢測所有重量小于或等于〔d*-1的非零錯誤模式。這個碼的最小距離為：d*=2,所以重量為1的錯誤模式可以檢測得到。這個碼能檢測的所有錯誤模式{00001,00010,00100,01000,10000}能糾正不多于t個錯誤應(yīng)滿足又d*=2所以即這個碼能糾0個錯誤才vv{00000,01010,10011,11001,10100,11110,00111,01101}線性碼的性質(zhì)：兩個屬于該碼的碼字的和仍是屬于該碼的碼字00000+01010=01010 00000+11001=1100100000+10011=1001100000+10100=1010000000+11110=1111000000+00111=0011100000+01101=0110101010+10011=1100101010+11001=1001101010+10100=1111001010+11110=1010001010+00111=0110101010+01101=0011110011+11001=0101010011+10100=0011110011+11110=0110110011+00111=1010010011+01101=1111011001+10100=0110111001+11110=0011111001+00111=1111011001+01101=1010010100+11110=0101010100+00111=1001110100+01101=1100111110+00111=1100111110+01101=1001100111+01101=01010滿足第一條性質(zhì)全零碼字總是一個碼字{00000,01010,10011,11001,10100,11110,00111,01101}滿足第二條性質(zhì)一個線性碼的兩個碼字之間的最小距離等于任何非零碼字的最小重量,即d*=w*D<00000,01010>=2D<00000,10011>=3D<00000,11001>=3 D<00000,10100>=2 D<00000,11110>=4 D<00000,00111>=3D<00000,01101>=3D<01010,10011>=3 D<01010,11001>=2D<01010,10100>=4D<01010,11110>=2D<01010,00111>=3D<01010,01101>=3{00000,01010,10011,11001,10100,11110,00111,01101}D<10011,11001>=2D<10011,10100>=3D<10011,11110>=3 D<10011,00111>=2D<10011,01101>=4D<11001,10100>=3 D<11001,11110>=3D<11001,00111>=4D<11001,01101>=2D<10100,11110>=2D<10100,00111>=3D<10100,01101>=3D<11110,00111>=3 D<11110,01101>=3D<00111,01101>=2這個碼的最小距離為2等于該碼的最小重量滿足第三條性質(zhì)所以,這個碼是線性碼。3.4構(gòu)造C={00000,10101,01010,11111}的生成矩陣。因為這個G不是唯一的,給出另一個能生成這個碼字集合的生成矩陣。解：設(shè)生成矩陣是G=,由題知,m=2,n=5,c=iGi=<0,0><0,1>,<1,0>,<1,1>生成矩陣G=3.7對下列每一個集合S,列出擴張碼<S>: 〔1S={0101,1010,1100} 〔2S={1000,0100,0010,0001} 〔3S={11000,01111,11110,01010}解:<1>0101+1010=1111,0101+1100=1001 1010+1100=0110,0101+1010+1100=0011再補上0000及原先3個公共組成第二,三問步驟省略<S>為{1111,1001,0110,0011,0000,0101,1010,1100}<2><S>為{1100,1010,1001,0110,0101,0011,1110,1011,0111,1101,1111,0000,1000,0100,0010,0001}<3><S>為{10111,00110,10010,10001,00101,10100,01001,11000,01111,11110,01010,00000,11011,01100,11101}3.8考慮〔23,12,7二元碼。證明若它被用在一個比特錯誤概率為p=0.01的二元對稱信道〔BSC中,字錯誤概率將約為0.00008解：由題可得其轉(zhuǎn)移概率p=0.01,在<>二元碼中其可以糾出2t+1>=7t=3位錯誤即在碼元中出現(xiàn)4個錯才會使得其出現(xiàn)誤碼率,出現(xiàn)3個以上錯誤的概率為則出現(xiàn)的誤字率為0.00008所以得證。3.9假設(shè)是一個二元碼,它的奇偶校驗矩陣為。證明由通過添加整體奇偶校驗比特得到的擴展碼的奇偶校驗矩陣為.證明：根據(jù)題意,擴展碼為:,又得奇偶校驗矩陣為,。,即擴展碼的奇偶校驗矩陣為。證畢。3.11設(shè)C是長度為n,最小距離為7的二元完備碼。證明n=7或n=23。證明：由完備碼的定義可知,一個完備碼必須滿足下列條件：<1>由題意可知：,其中即有：當n=7時,由〔1式可得,右式展開得：同理,可證得n=23時,同樣滿足〔1式。故可證明當n=7或n=23時,C是二元完備碼。3.12用來表示二元漢明碼的碼率,求。解：根據(jù)二元漢明碼的性質(zhì)可知：其中m是任意正整數(shù)。則由碼率的定義可知：則有：第4章循環(huán)碼4.1下面的哪個碼是〔a循環(huán)碼,〔b與一個循環(huán)碼等價？〔1上的。〔2上的。〔3上的?！?上的。〔5長度為的-元重復(fù)碼。解：由書中定義4.1可知,循環(huán)碼需要滿足兩個條件,首先它必須是一個線性碼,其次它的一個碼字的任意循環(huán)移位的結(jié)果還是一個碼字,即若為其中的一個碼字,則也是其中一個碼字。下面一一證明：〔1首先證明是一個線性碼：設(shè),則,,,,,,,,,,,,,,顯然不滿足線性碼的第一個條件,則它不是一個線性碼,就不可能是一個循環(huán)碼?！?首先證明是一個線性碼：設(shè),則,,,,,,,,,滿足線性碼的第一個條件,顯然第二個條件也滿足。中的最小距離,最小重量,即,也滿足第三個條件,可知是一個線性碼。下面證明是循環(huán)的,,經(jīng)過循環(huán)移位之后得到的碼字是,這個碼字不是中的碼字,即不滿足循環(huán)碼的第二個條件。綜上可知,不是一個循環(huán)碼,但是它與一個循環(huán)碼等價?！?首先證明是一個線性碼：設(shè),則,,,,,,,,,顯然不滿足線性碼的第一個條件,則它不是一個線性碼,就不可能是一個循環(huán)碼?！?首先證明是一個線性碼：設(shè),則,,,,,滿足線性碼的第一個條件,顯然第二個條件也滿足。中的最小距離,最小重量,即,也滿足第三個條件,可知是一個線性碼。下面證明是循環(huán)的,,經(jīng)過循環(huán)移位之后得到的碼字是,這個碼字不是中的碼字,即不滿足循環(huán)碼的第二個條件。綜上可知,不是一個循環(huán)碼,但是它與一個循環(huán)碼等價?！?長度為的-元重復(fù)碼,假設(shè),,則,可知其不為線性碼,也定不為循環(huán)碼。4.2為下列定義的多項式環(huán)構(gòu)造加法和乘法表+01xX+1001xX+11101+xxxxX+101X+1X+1x10乘法表如下：.01xX+100000101xX+1x0x1X+1X+10X+1X+10加法表如下：+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+22x+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+12x+2002x+12x+2X+2X+1X+12x+12x2x22x+2X+2X112x4.4找出所有分組長度為5的二元循環(huán)碼,求出每個碼的最小距離。 解：要找到分組長度為5的所有2元循環(huán)碼,首先要分解=在GF〔2中,是既約的,所求的循環(huán)碼為：定義在R5中的多項式=24=16個,信息多項式和對應(yīng)的碼字多項式在下表中列出：000000,00000000011,00011,111010010,00110,111110011,00110,10001010001010010101111011001010011101001100011000100111011101011110101110101110010100110110111111011000111110001故不同的碼字有：碼字最小碼距0000000001120011021110141111101000121010120111140100121100021101141110141010021011141111044.7設(shè)多項式為GF<2>上分組長度為15的一個循環(huán)碼的生成多項式。<1>求生成矩陣G.。<2>求奇偶校驗矩陣H。<3>這個碼能檢測多少個錯誤？<4>這個碼能糾多少個錯誤？ <5>將生成矩陣寫成系統(tǒng)型。解：<1>由生成多項式可知：生成矩陣為：<2>由于已知分組長度為15,設(shè)奇偶校驗多項式為h<x>,則有：即：其中,上式為取模運算。故,對應(yīng)的奇偶校驗矩陣為：<3>建立如下表格：ii<x>c<x>=i<x>g<x>c00o0000000000000000011g<x>10xxg<x>11x+1<x+1>g<x>由該表格可以看出,該碼的最小距離為7。即：故可知,該碼可以檢測個錯誤。<4>由于,則有：即：故該碼可以糾3個錯誤。<5>該生成矩陣的系統(tǒng)型為：4.11生成多項式為的碼在中作檢錯和糾錯標準?！?這個碼能糾多少個隨機錯誤？〔2這個碼能糾多少個突發(fā)錯誤？解：又經(jīng)過嘗試我們得到分組長度是滿足且能整除的最小整數(shù),可以糾的突發(fā)錯誤最多為t=12個；能糾的隨機錯誤為x=5個。第5章BCH碼5.1用一個合適的本原多項式由構(gòu)造。解：考慮由子域構(gòu)造擴域,已知,,現(xiàn)在對進行分解,即在上分解,下面考慮擴域上的元素,這些元素可以表示為：通過觀察上的元素,我們可以選擇作為本原多項式來構(gòu)造?？紤]上的元素,并不是上的本原元,則我們可以假設(shè)上的本原元為,則可以通過的冪模得到上的所有元素。經(jīng)過多項式的運算可以得到中的元素：5.2找出分組長度為26的糾三個錯誤的三元BCH碼的生成多項式g<x>Z的冪GF<27>的元素Z1zZ2Z2Z3Z+2Z4Z2+2zZ52z2+2z+1Z6Z2+z+1Z72Z82z2+2Z91Z10Z2+zZ11Z2+z+2Z122z2+z+2Z132Z142zZ152z2+1Z16Z+2Z17Z2+1Z18Z2Z19Z+2Z202z2+z+1Z21Z+1Z22Z2Z23Z24Z255.4求下列碼的生成多項式和最小距離：<1>RS<15,11>碼。<2>RS<15,7>碼。<3>RS<31,21>碼。解：<1>由RS<15,11>碼可知,n=15,k=11。則根據(jù)RS碼的性質(zhì)可知,n-k=2t即：2t=15-11=4一個RS碼的生成多項式可以寫成：故該RS<15,11>碼的生成多項式為：我們這里用到擴域GF<16>上的元素,該擴域是由GF<2>以本原多項式構(gòu)造的<書上例5.7>。則有：該RS<15,11>碼的最小距離為：<2>由RS<15,7>碼可知,n=15,k=7。根據(jù)RS碼的性質(zhì)：n-k=2t即：2t=15-7=8根據(jù)<1>題所涉及的性質(zhì)可知,RS<15,7>碼的生成多項式為：該RS<15,7>碼的最小距離為：<3>RS〔31,21碼中,t=5,115.6考慮上具有下列奇偶校驗矩陣的碼<1>證明該碼糾三個錯誤的碼?！?求該碼的生成多項式證明：又因為在中,矩陣中元素所以經(jīng)過計算,中滿足和為零的行向量的最小個數(shù)為7,,所以這個碼能糾個錯。證畢。第6章卷積碼6.2設(shè)計一個〔12,4系統(tǒng)卷積編碼器使其約束長度且?！?構(gòu)造該編碼器的網(wǎng)格圖?！?該碼的是什么？解：〔1由題意可知,,,且約束長度為可以得到,,通過這些參量我們可以設(shè)計出編碼器,如下圖所示：編碼輸出編碼輸出輸入移位寄存器這個編碼器每次把1比特輸入編碼成3比特的輸出。信息幀的長度為,碼字幀的長度為,分組長度為12,該編碼器的約束長度為,碼率為。編碼器的狀態(tài)圖：〔只有四種狀態(tài)00000111101111000卷積編碼器輸入和輸出的比特如下表所示輸入比特編碼器當前狀態(tài)編碼器之后狀態(tài)輸出比特0000000000100010010101000100101100110111001000111010101010110110011100111011100100010001011001100000010101011111011100100011001011101110111001110110011111111100編碼器的網(wǎng)格圖為：000010011100000000000010110110110101001001011111111111011001101110010000100100002121,,,因為,6.3考慮下圖所示的二元編碼器〔1構(gòu)造該編碼器的網(wǎng)格圖〔2記下該編碼器的輸入當前狀態(tài)下一個狀態(tài)輸出000000000000100001000001010000100001110001100000001000010011101001010111011000110111111001110110000100001010100101001011010100101011110101101010001100011100101101011101011100111101111101111100由圖可得6.4考慮圖6-36所示的二元編碼器。ii3i2i1++++++c1c2c3c4圖6-36<1>寫出該編碼器的k,n,v,m及R的值。<2>給出該編碼器的生成多項式矩陣G<D>。<3>給出該編碼器的生成矩陣G。<4>給出該編碼器的奇偶校驗矩陣H。<5>該編碼的d*、dfree和nfree的值各是多少？<6>該編碼器在dfree的Heller界上是最優(yōu)的嗎？<7>用該編碼器將下列比特序列進行編碼：101001001010000。解：<1>由題意可知：m=4由圖6-36可知：k0=3,n0=4。則有：k=<m+1>k0=15,n=<m+1>n0=20由約束長度公式可得：v=mk0=12由碼率公式可得：R=k0/n0=0.85<2>該編碼器的生成多項式矩陣為：<3>由圖可知：故該編碼器的生成矩陣G為;將5個矩陣代入矩陣G中既可。<4>將5個矩陣進行變換得：其中,I為k0*k0階單位矩陣,即3*3階單位矩陣。P1,P2,P3