信息論與編碼課后習(xí)題答案曹雪虹文檔良心出品

1、第六章：信道編碼(本章復(fù)習(xí)大綱我重新修改了一下,尤其要關(guān)注紅色內(nèi)容) 1、根本概念：過失符號(hào)、過失比特；過失圖樣：隨機(jī)過失、突發(fā)差 錯(cuò)；糾錯(cuò)碼分類：檢錯(cuò)和糾錯(cuò)碼、分組碼和卷積碼、線性碼與非線性 碼、糾隨機(jī)過失碼和糾突發(fā)過失碼；矢量空間、碼空間及其對(duì)偶空間；有擾離散信道的編碼定理：R<eNE(R)(掌握信道編碼定理的內(nèi)容及 減小過失概率的方法)；線形分組碼的擴(kuò)展與縮短(掌握奇偶校驗(yàn) 碼及縮短碼的校驗(yàn)矩陣、生成矩陣與原線形分組碼的關(guān)系).2、線性分組碼(封閉性)：生成矩陣及校驗(yàn)矩陣、系統(tǒng)形式的G和H、 伴隨式與標(biāo)準(zhǔn)陣列譯碼表、碼距與糾錯(cuò)水平、完備碼(漢明碼)、循環(huán)碼的生成多項(xiàng)式及校驗(yàn)多項(xiàng)式、

2、系統(tǒng)形式的循環(huán)碼.作業(yè)：6-1、6-3、6-4、6-5 和 6-6 選一、6-7 6-8 和 6-9 選一6-1二元域上4維4重失量空間的元素個(gè)數(shù)總共有24=16個(gè),它們分別 是(0,0,0,0),(0,0,0,1)(1,1,1,1),它的一個(gè)白然基底是 (0,0,0,1),(0,0,1,0),(0,1,0,0訴日(1,0,0,0);其中一個(gè)二維子空間含有的元 素個(gè)數(shù)為22個(gè),選取其中一個(gè)白然基底為(0,0,0,1訴日(0,0,1,0),那么其 二維子空間中所包含的全部矢量為(0,0,0,0,),(0,0,0,1),(0,0,1,0)和 (0,0,1,1)(注選擇不唯一)；上述子空間對(duì)應(yīng)的對(duì)偶

3、子空間可以有三種不同的選擇：(0,0,0,0) ,(0,1,0,0),(1,0,0,0), (1,1,0,0)或(0,0,0,0) ,(0,1,0,0)或(0,0,0,0) (1,0,0,0).(注意此題中所包含的關(guān)于矢量空間的一些根本 概念)6-3由題設(shè)可以寫出該系統(tǒng)(8,4)碼的線形方程組如下：V7 =叱v6 =u2V5 =V4=U°注：系統(tǒng)碼高四位與信息位保持一致,Ui為信息位V3 =叱 U2 U0V2 =U3 UiU0Vi =U2 UiU0V.=U3 U2 Ui把上述方程組寫成矩陣形式,可以表示為V=UG,其中V為碼字構(gòu) 成的矢量,即V=V7,V6,V5,V4,V3,V2,V

4、l,V0, U為信息位構(gòu)成的矢量,即U= U3,U2,Ui,U0,觀察方程組可得系統(tǒng)生成矩陣為:一100011010100101100100111_00011110_G 二Li 41 %41由系統(tǒng)生成矩陣和校驗(yàn)矩陣的關(guān)系可得:一110J10110111111010000100001001001由校驗(yàn)矩陣可以看出,矩陣 H的任意三列都是線性無關(guān)的任意三列之和不為0,但存在四列線性相關(guān)的情況如第1、5、6、8列, 這四列之和為0,即校驗(yàn)矩陣H中最小的線性相關(guān)的列數(shù)為 4,從而得該線性分組碼的最小碼距為 4.注意：書上定理6.3的結(jié)論是 錯(cuò)誤的,正確的結(jié)論是線性分組碼的最小碼距為校驗(yàn)矩陣中最小的線性

5、相關(guān)的列數(shù).該編碼器的硬件邏輯連接圖略用WORD畫圖比較麻煩,希望同學(xué)們白己把硬件電路圖畫一下,主要考查數(shù)字電路一些知識(shí)點(diǎn),其他畫硬件邏輯電路圖題目也要白己畫.H刪除第一列：Hi =11;對(duì)縮減后的6,3碼再進(jìn)行次縮減可得5,2碼,5,2碼的校驗(yàn)矩陣H1刪除第一列:H201系統(tǒng)形式,其系統(tǒng)形式的生成矩陣為:1G1206-6110一1001 10110100 111：0011 110 一第一列和第三列交換 G系統(tǒng)形式的生成矩陣；6-4在例6-4中,該7,4漢明碼對(duì)應(yīng)的校驗(yàn)矩陣為:00101111一1 1 1 0 1 0 01H =0 10 10 11_哭也壁蛆f玉?1二T0 1 1 10 101

6、 0 0 1 1 0 1一|1 1 0 1 0 0 1一由7,4碼進(jìn)行第一次縮減可得6,3碼,該6,3校驗(yàn)矩陣為校驗(yàn)矩陣2由系統(tǒng)形式的生成矩陣和校驗(yàn)矩陣的關(guān)系可得,校驗(yàn)矩陣為一1011000111101000110010J100001 -系統(tǒng)形式;H =由標(biāo)準(zhǔn)陣列譯碼表的構(gòu)造可知,該碼表應(yīng)該有2n-k=16行伴隨 式的個(gè)數(shù)和2k=8列發(fā)送碼字的個(gè)數(shù),由C=mG可以得出發(fā)送的碼字為(0,0,0,0,0,0,0卜(0,0,1,1,1,1,0)、(0,1,0,0,1,1,1)、(0,1,1,1,0,0,1)、(1,0,0,1,1,0,1)、(1,0,1,0,0,1,1)、(1,1,0, 1,0,1,

7、0即(1,1,1,0,1,0,0).該(7,3) 碼的伴隨式為(0,0,0,0)、(0,0,0,1)、(0,0,1,0) (1,1,1,1)(16 個(gè)).由伴 隨式和過失圖案的對(duì)應(yīng)關(guān)系S=EHt可得：當(dāng)過失圖案為E0=(0,0,0,0,0,0,0)(全零)時(shí),伴隨式為S0=(0,0,0,0);當(dāng)過失圖案中有 一位發(fā)生錯(cuò)誤時(shí)(共有£=7種可能),過失圖案與伴隨式的對(duì)應(yīng)關(guān)系為：E1=(0,0,0,0,0,0,1),S1=(0,0,0,1)E2=(0,0,0,0,0,1,0),S2=(0,0,1,0)E3=(0,0,0,0,1,0,0) S3=(0,1,0,0)E4=(0,0,0,1,0,

8、0,0) S4=(1,0,0,0)E5=(0,0,1,0,0,0,0),S5=(1,1,1,0)E6=(0,1,0,0,0,0,0),S6=(0,1,1,1)E7=(1,0,0,0,0,0,0),S7=(1,1,0,1)；當(dāng)過失圖案中有兩位發(fā)生錯(cuò)誤時(shí)(共有簫=21種可能,只需列出其中的16-8=8種可能即可),這時(shí)過失圖案與伴隨式(必須與已求出的伴隨式不同)的對(duì)應(yīng)關(guān)系為：E8=(0,0,0,0,0,1,1尸S8=(0,0,1,1)E9=(0,0,0,0,1,1,0),S9=(0,1,1,0)E10=(0,0,0,1,1,0,0),S10=(1,1,0,0)E11=(0,1,1,0,0,0,0)

9、,Sh=(1,0,0,1)E12=(1,1,0,0,0,0,0),S12=(1,0,1,0)E13=(1,0,0,1,0,0,0),S13=(0,1,0,1)E14=(1,0,1,0,0,0,0),S14=(1,0,1,1)E15=(1,0,0,0,0,1,0),S15=(1,1,1,1)根據(jù)標(biāo)準(zhǔn)陣列譯碼表的構(gòu)造,列出該7,3碼的結(jié)構(gòu)為:S0(0000)C0+E0=C0(0000000)C1+E0=C1 (0011110)C2+E0=C2 (0100111)C3+E0=C3 (0111001)C4+E0=C4(1001101)C5+E0=C5(1010011)C6+E0=C6 (1101010

10、)C7+E0=C7 (1110100)Si(0001)C0+E 1=E1 (0000001)S2(0010)C0+E2=E2 (0000010)S3(0100)C°+E3=E3 (0000100)S4(1000)C°+E4=E4 (0001000)S5(1110)C°+E5=E5 (0010000)S6(0111)C0+E6=E6 (0100000)S7(1101)C°+E7=E7 (1000000)S8(0011)C0+E8=E8 (0000011)S9(0110)C0+E9=E9(0000110)S10(1100)C0+E10=E10 (000110

11、0)S11(1001)C0+E11=E11 (0110000)S12(1010)C0+E12=E12 (1100000)S13(0101)C0+E13=E13 (1001000)S14(1011)C0+E 14=E 14 (1010000)S15(1111)C0+E15=E15 (1000010)表格中的元素第一列除外為所有可能接收到的碼序列,共有2n=128 種可能,其中接收碼序列 R = Ei+Cj 表格空白地方需同學(xué)們白己計(jì) 算.表格第一行為發(fā)送碼字,第一列和第二列為伴隨式及其最小漢明距離對(duì)應(yīng)的過失圖案.表中每一行稱為一個(gè)陪集,陪集頭為對(duì)應(yīng)的 過失圖案；每一列為一個(gè)子集,子集首為對(duì)應(yīng)的發(fā)

12、送碼字.10 110 0 04由校驗(yàn)矩陣h = I1 1 1 0 1 0 0可以看出該校驗(yàn)矩陣的任意30 110 0 101 1 0 0 0 0 1 列線性無關(guān),存在4列如第1、4、5、7線性相關(guān),即矩陣H的最 小的線性相關(guān)的列數(shù)為4,故最小碼距 扁吊為4.10 0 110 1(5)由系統(tǒng)形式的生成矩陣G' = 0 1 0 0 1 1 1和C=mG可得,0 0 11110當(dāng)信 息序列 m=(101)時(shí),對(duì)應(yīng)的碼字為 C=(1010011),這時(shí)CHT=(0000),故碼字與校驗(yàn)矩陣H正交.(標(biāo)準(zhǔn)陣列譯碼表是重點(diǎn), 請(qǐng)務(wù)必掌握這種題型！)6-7 (1)設(shè)計(jì)系統(tǒng)(15,11雙明碼:對(duì)于(1

13、5,11)漢明碼,其校驗(yàn)矩陣H為4行15列矩陣,即H每一列有 4個(gè)元素,在二元域內(nèi),4個(gè)元素共有24=16種組合,除去全0(即0000) 組合外,所有不為零組合共有15種可能.所以校驗(yàn)矩陣每一列可全 部排列4個(gè)元素中所有不為零組合,所以校驗(yàn)矩陣為：-000 0000111111111H =000 111100001111,通過列置換轉(zhuǎn)換為011 001100110011101 010101010101-00001111111 10001系統(tǒng)形式可得H'01110001111 0100,再由10110110011 001011011010101 0001-線性分組碼系統(tǒng)形式的生成矩陣G

14、= L | Rj】和校驗(yàn)矩陣H =P(n-k)|Ij的關(guān)系,可得該漢明碼的系統(tǒng)生成矩陣為：-1000000000000111010000000000101001000000000110000100000000111000010000001001G =000001000001010000000100001011000000010001100000000001001101000000000101110000000000011111設(shè)計(jì)(15,11)循環(huán)漢明碼由題設(shè)知(15,11)循環(huán)碼的生成多項(xiàng)式為：g(x)=x4+x+1(a) 將信息多項(xiàng)式m(x)乘上xn-k(這里n=15, k=11),不妨選

15、取 m=(10000000000),即 m(x)= x10,這時(shí) m(x)xn-k=x14;(b) 將 m(x)xn-k除以 g(x)得余式 r(x)： r(x)=x3+1；(c) 信息序列m=(10000000000用應(yīng)的碼多項(xiàng)式為：C(x)= m(x)xn-k+r(x)= x14+x3+1,對(duì)應(yīng)碼矢量為(100000000001001)根據(jù)同樣的方法,可以求出由信息位組成的 10種其他白然基底 及它們對(duì)應(yīng)的碼字,從而得到該循環(huán)碼的11個(gè)線性無關(guān)的基底.(這樣選擇信息位有什么好處)信息位和基底的對(duì)應(yīng)關(guān)系如下：信息位系統(tǒng)碼子(10000000000) > (01000000000) &g

16、t; (00100000000) > (00010000000) > (00001000000) > (00000100000) > (00000010000) > (00000001000) > (00000000100) > (00000000010) > (00000000001) >(100000000001001)(010000000001101)(001000000001111)(000100000001110)(000010000000111)(000001000001010)(000000100000101)(000000010001011)(000000001001100)(000000000100110)(000000000010011)把上述11個(gè)碼字(線性無關(guān)的)作為基底構(gòu)成循環(huán)碼