第7章信道編碼技術(shù)(改1)

1、第1頁2022-6-12Department of Electronics and Information, NCUT Song Peng Song Peng7.1 線性分組碼線性分組碼7.2 卷積碼卷積碼7.3 TCM碼與級聯(lián)碼碼與級聯(lián)碼7.4 Turbo碼和碼和LDPC碼碼第2頁2022-6-12(1) 線性分組碼的編碼：線性分組碼的編碼：編碼過程分為兩步：編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組把信息序列按一定長度分成若干信息碼組, 每組由每組由 k 位組位組成成;編碼器按照預(yù)定的線性規(guī)則（由線性方程組規(guī)定），把編碼器按照預(yù)定的線性規(guī)則（由線性方程組規(guī)定），把信息碼組變換成

2、信息碼組變換成 n 重（重（nk）碼字，其中）碼字，其中 (nk) 個附加個附加碼元是由信息碼元的線性運算產(chǎn)生的。碼元是由信息碼元的線性運算產(chǎn)生的。(2) 線性分組碼的碼字?jǐn)?shù)：線性分組碼的碼字?jǐn)?shù)：信息碼組長信息碼組長 k 位，有位，有 2k 個不同的個不同的信息碼組，有信息碼組，有 2k 個碼字與它們一一對應(yīng)。個碼字與它們一一對應(yīng)。第3頁2022-6-12(3) 術(shù)語術(shù)語線性分組碼：線性分組碼：通過預(yù)定的線性運算將長為通過預(yù)定的線性運算將長為 k 位的信息碼位的信息碼組變換成組變換成 n 重的碼字重的碼字 (nk)。由。由 2k 個信息碼組所編成的個信息碼組所編成的 2k個碼字集合，稱為線性分

3、組碼。個碼字集合，稱為線性分組碼。碼矢：碼矢：一個一個 n 重的碼字可以用矢量來表示：重的碼字可以用矢量來表示：C C=(cn1,cn1,c1,c0 )(n,k) 線性碼：線性碼：信息位長為信息位長為 k，碼字長為，碼字長為 n 的線性碼。的線性碼。編碼效率編碼效率/編碼速率編碼速率/碼率碼率/傳信率：傳信率：R=k /n。 它說明了信道的利用效率，它說明了信道的利用效率，R 是衡量碼性能的一個重是衡量碼性能的一個重要參數(shù)。要參數(shù)。第4頁2022-6-12(1) 校驗方程校驗方程構(gòu)成碼字的方法：構(gòu)成碼字的方法：編碼是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，構(gòu)成編碼是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)

4、督碼元，構(gòu)成碼字。碼字。在在 k 個信息碼元之后附加個信息碼元之后附加 r(r=nk) 個校驗（監(jiān)督）碼元，使每個校驗元個校驗（監(jiān)督）碼元，使每個校驗元是其中某些信息元的模是其中某些信息元的模 2 和。和。舉例：舉例：k=3, r=4，構(gòu)成，構(gòu)成 (7,3) 線性分組碼。設(shè)碼字為：線性分組碼。設(shè)碼字為：(c6,c5,c4,c3,c2,c1,c0)c6,c5,c4為信息元，為信息元，c3,c2,c1,c0為校驗元，每個碼元取為校驗元，每個碼元取“0”或或“1”校驗元按下面方程組計算：校驗元按下面方程組計算：) 1 . 2 . 7 (4505614562463 ccccccccccccc1. 線性

5、分組碼的校驗矩陣線性分組碼的校驗矩陣第5頁2022-6-12(1) 校驗方程校驗方程監(jiān)督方程監(jiān)督方程/校驗方程：確定信息元得到監(jiān)督元規(guī)校驗方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程則的一組方程稱為監(jiān)督方程/校驗方程。由于所校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。一致校驗方程。為什么叫線性分組碼？為什么叫線性分組碼？由于一致監(jiān)督方程是線性由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運算關(guān)系，所的，即監(jiān)督元和信息元之間是線性運算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。以由線性監(jiān)督方程所確定的分

6、組碼是線性分組碼。1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣7.1線性分組碼第6頁2022-6-12(2) 舉例舉例信息碼組信息碼組 (101)，即，即c6=1, c5=0, c4=1得：得： c3=0, c2=0, c1=1, c0=1由信息碼組由信息碼組 (101) 編出的碼字為編出的碼字為 (1010011)。其它。其它 7 個碼字如表。個碼字如表。 00000000000000000000451562456346ccccccccccccc) 1 . 2 . 8 (4505614562463 ccccccccccccc1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣7.1線性分組碼第7

7、頁2022-6-12(3) 一致監(jiān)督矩陣一致監(jiān)督矩陣為了運算方便，將監(jiān)督方程為了運算方便，將監(jiān)督方程寫成矩陣形式，得：寫成矩陣形式，得：) 2 . 2 . 8 (000010001100100011001011100011010123456 cccccccHH C CT=0 0T 或或 C C HHT=0 0 C CT、HHT、0 0T 分別表示分別表示 C C、HH、0 0 的轉(zhuǎn)置矩陣。的轉(zhuǎn)置矩陣。1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣 00000000000000000000451562456346ccccccccccccc ) 3 . 2 . 8 (100011001000110

8、010111000110100000123456 HH0 0C Cccccccc令令7.1線性分組碼第8頁2022-6-12(3) 一致監(jiān)督矩陣一致監(jiān)督矩陣系數(shù)矩陣系數(shù)矩陣 H H 的后四列組成一個的后四列組成一個 (44) 階單位子陣，用階單位子陣，用 I I4 表示，表示，H H 的其余部分用的其余部分用 P P 表示：表示：推廣到一般情況：推廣到一般情況：對對 (n,k) 線性分組碼，每個碼字中的線性分組碼，每個碼字中的 r(r=nk) 個個監(jiān)督元與信息元之間的關(guān)系由下面的線性方程組確定：監(jiān)督元與信息元之間的關(guān)系由下面的線性方程組確定：1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣 )4

9、.2.8(1000010000100001110011111101434)37(434I IP PHHI IP P ,所所以以 )4.2.8(1000010000100001110011111101434)37(434I IP PHHI IP P ,所所以以) 5 . 2 . 8(000022110222212101212111 chchchchchchchchchrnnrnrnnnnnn7.1線性分組碼 )3 . 2 . 8(100011001000110010111000110100000123456 HH0 0C Cccccccc令令第9頁2022-6-12(3) 一致監(jiān)督矩陣一致監(jiān)督矩

10、陣令上式的系數(shù)矩陣為令上式的系數(shù)矩陣為 HH，碼字行陣列為，碼字行陣列為 C C ： 0211cccnnn C C) 6 . 2 . 8 (212222111211 rnrrnnnrhhhhhhhhhHH矩矩陣陣，簡簡稱稱監(jiān)監(jiān)督督矩矩陣陣。線線性性分分組組碼碼的的一一致致監(jiān)監(jiān)督督為為稱稱或或可可寫寫成成：式式),()7.2.8()()()()5.2.7(1111knrTnrnTrTnnrHH0 0HHC C0 0C CHH 矩矩陣陣，簡簡稱稱監(jiān)監(jiān)督督矩矩陣陣。線線性性分分組組碼碼的的一一致致監(jiān)監(jiān)督督為為稱稱或或可可寫寫成成：式式),()7.2.8()()()()5.2.7(1111knrTnr

11、nTrTnnrHH0 0HHC C0 0C CHH 1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣7.1線性分組碼) 5 . 2 . 8 (000022110222212101212111 chchchchchchchchchrnnrnrnnnnnn第10頁2022-6-12(4) 一致監(jiān)督矩陣特性一致監(jiān)督矩陣特性對對 H H 各行實行初等變換，將后面各行實行初等變換，將后面 r 列化為單位子陣，得列化為單位子陣，得到下面矩陣，行變換所得方程組與原方程組同解。到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣監(jiān)督矩陣 H H 的標(biāo)準(zhǔn)形式：的標(biāo)準(zhǔn)形式：后面后面 r 列是一單位子陣的監(jiān)督列是一單

12、位子陣的監(jiān)督矩陣矩陣 HH。)8 . 2 . 8(100010001212222111211 rnrrkknrpppppppppHH1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣7.1線性分組碼第11頁2022-6-12(4) 一致監(jiān)督矩陣特性一致監(jiān)督矩陣特性q H H 陣的每一行都代表一個監(jiān)督方程，它表示與該行中陣的每一行都代表一個監(jiān)督方程，它表示與該行中“1”相對應(yīng)相對應(yīng)的碼元的模的碼元的模 2 和為和為 0。 q H H 的標(biāo)準(zhǔn)形式表明相應(yīng)的監(jiān)督元是由哪些信息元決定。例如的標(biāo)準(zhǔn)形式表明相應(yīng)的監(jiān)督元是由哪些信息元決定。例如 (7,3) 碼的碼的 H H 陣的第一行為陣的第一行為 (1011

13、000)，說明第一個監(jiān)督元等于第一個和，說明第一個監(jiān)督元等于第一個和第三個信息元的模第三個信息元的模 2 和，依此類推。和，依此類推。 q H H 陣的陣的 r 行代表了行代表了 r 個監(jiān)督方程，由個監(jiān)督方程，由 H H 所確定的碼字有所確定的碼字有 r 個監(jiān)個監(jiān)督元。督元。q 為了得到確定的碼，為了得到確定的碼，r 個監(jiān)督方程（或個監(jiān)督方程（或 H H 陣的陣的 r 行）必須是線性行）必須是線性獨立的，即要求獨立的，即要求 H H 陣的秩為陣的秩為 r。q 若把若把 H H 陣化成標(biāo)準(zhǔn)形式，只要檢查單位子陣的秩，就能方便地陣化成標(biāo)準(zhǔn)形式，只要檢查單位子陣的秩，就能方便地確定確定 H H 陣本

14、身的秩。陣本身的秩。1. 線性分組碼的校驗矩陣線性分組碼的校驗矩陣7.1線性分組碼 )3 . 2 . 8(100011001000110010111000110100000123456 HH0 0C Cccccccc令令第12頁2022-6-12(1) 線性碼的封閉性線性碼的封閉性 線性碼的封閉性：線性碼的封閉性：線性碼任意兩個碼字之和仍是一個碼字。線性碼任意兩個碼字之和仍是一個碼字。 定理：定理：設(shè)二元線性分組碼設(shè)二元線性分組碼 C CI (C CI 表示碼字集合表示碼字集合) 是由監(jiān)督矩陣是由監(jiān)督矩陣H H 定義，若定義，若 U U 和和 V V 為其中的任意兩個碼字，則為其中的任意兩個碼

15、字，則 U U +V V 也是也是 C CI 中的一個碼字中的一個碼字。 證明證明：由于由于 U U 和和 V V 是碼是碼 C CI 中的兩個碼字，故有：中的兩個碼字，故有：HU HU T=0 0T HV HV T=0 0T ，那么，那么 HH(UU+V V)T=HH(U U T+V V T)=HU HU T+HV HV T=0 0T 即即 UU+V V 滿足監(jiān)督方程，所以滿足監(jiān)督方程，所以 UU+V V 一定是一個碼字。一定是一個碼字。 一個長為一個長為 n 的二元序列可以看作是的二元序列可以看作是 GFGF(2) (二元域二元域) 上的上的 n 維線性空間中的一維線性空間中的一點。所有點

16、。所有 2n 個矢量集合構(gòu)成了個矢量集合構(gòu)成了GFGF(2)上的上的 n 維線性空間維線性空間 V Vn。把線性碼放入線性。把線性碼放入線性空間中進(jìn)行研究，可使許多問題簡化而比較容易解決?？臻g中進(jìn)行研究，可使許多問題簡化而比較容易解決。(n,k) 線性碼是線性碼是 n 維線性空間維線性空間 V Vn 中的一個中的一個 k 維子空間維子空間 V Vk。7.1線性分組碼第13頁2022-6-12(2) 線性分組碼的生成矩陣線性分組碼的生成矩陣生成矩陣的來由：生成矩陣的來由：在由在由 (n,k) 線性碼構(gòu)成的線性空間線性碼構(gòu)成的線性空間 V Vn 的的 k 維子空維子空間中，一定存在間中，一定存在

17、k 個線性獨立的碼字：個線性獨立的碼字：g g1,g g2, g gk。碼。碼 C CI 中其它中其它任何碼字任何碼字 C C 都可以表示為這都可以表示為這 k 個碼字的一種線性組合，即：個碼字的一種線性組合，即：。寫寫成成矩矩陣陣形形式式得得：）（1, 1 , 0),2(1 . 3 . 802211 kiGFmmmmikkkg gg gg gC C 階階矩矩陣陣。是是一一個個待待編編碼碼的的信信息息組組nkmmmnkkk GGmm021 ) 2 . 3 . 8 (,1210211nkkkkknmmm GGmmg gg gg gC C7.1線性分組碼第14頁2022-6-12(2) 線性分組碼

18、的生成矩陣線性分組碼的生成矩陣生成矩陣定義：生成矩陣定義：由于矩陣由于矩陣 G G 生成了生成了 (n,k) 線性碼，稱矩陣線性碼，稱矩陣 G G 為為 (n,k) 線性碼的生成矩陣。線性碼的生成矩陣。) 3 . 3 . 8 (21222211121121 knkknnknkgggggggggg gg gg gGG 生成矩陣生成矩陣G G 的特性的特性q G G 中每一行中每一行 g gi=(gi1,gi2, gin ) 都是一個碼字；都是一個碼字；q 對每一個信息組對每一個信息組 mm，由矩陣，由矩陣 G G 都可以求得都可以求得 (n,k) 線性碼對應(yīng)的碼線性碼對應(yīng)的碼字。字。q (n,k

19、) 線性碼的每一個碼字都是生成矩陣線性碼的每一個碼字都是生成矩陣 G G 的行矢量的線性組合，的行矢量的線性組合，所以它的所以它的 2k 個碼字構(gòu)成了由個碼字構(gòu)成了由 G G 的行張成的的行張成的 n 維空間的一個維空間的一個 k 維子維子空間空間 V Vk。7.1線性分組碼111212122212nnkkknggggggggg第15頁2022-6-12 ) 4 . 3 . 8 (100010001)(21)( 22221)( 11211rkkknkkkknknnkqqqqqqqqq QQI IGG(2) 線性分組碼的生成矩陣線性分組碼的生成矩陣 線性系統(tǒng)分組碼線性系統(tǒng)分組碼q 線性系統(tǒng)分組碼

20、的構(gòu)成：線性系統(tǒng)分組碼的構(gòu)成：通過行初等變換，將通過行初等變換，將 G G 化為前化為前 k 列是列是單位子陣的標(biāo)準(zhǔn)形式。單位子陣的標(biāo)準(zhǔn)形式。)5 . 3 . 8(, 2 , 1, 2 , 1),(),(02211)(0210211 knjqmqmqmckimc,mmmccckjjkjkjknikinnkkknnn得得：將將上上式式代代入入GGC C7.1線性分組碼第16頁2022-6-12(2) 線性分組碼的生成矩陣線性分組碼的生成矩陣 線性系統(tǒng)分組碼線性系統(tǒng)分組碼q 線性系統(tǒng)分組碼定義：線性系統(tǒng)分組碼定義：用標(biāo)準(zhǔn)生成矩陣用標(biāo)準(zhǔn)生成矩陣 GGkn 編成的編成的碼字，前面碼字，前面 k 位為信

21、息位，后面位為信息位，后面 r=nk 位為校驗位，這位為校驗位，這種信息位在前校驗位在后的線性分組碼稱為線性系統(tǒng)分種信息位在前校驗位在后的線性分組碼稱為線性系統(tǒng)分組碼。組碼。q 當(dāng)生成矩陣當(dāng)生成矩陣 G G 確定之后，確定之后，(n,k) 線性碼就完全被確定，線性碼就完全被確定，只要找到碼的生成矩陣，編碼問題也同樣被解決。只要找到碼的生成矩陣，編碼問題也同樣被解決。7.1線性分組碼第17頁2022-6-12 )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC Cm

22、mGG，則則：若若(2) 線性分組碼的生成矩陣線性分組碼的生成矩陣舉例：舉例：(7,4) 線性碼的生成矩陣為：線性碼的生成矩陣為： )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC CmmGG，則則：若若 )1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174 GGmmC CmmGG，則則：若若7.1線性分組碼第18頁2022-6-12(3) 生成

23、矩陣與一致監(jiān)督矩陣的關(guān)系生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣由于生成矩陣 G G 的每一行都是一個碼字，所以的每一行都是一個碼字，所以 G G 的每行都滿足：的每行都滿足：HHrn(C C1n)T=(0 01r)T，則有：，則有：HHrn(GGkn)T=(0 0kr)T 或或 GGkn(HHrn)T=0 0kr線性系統(tǒng)碼的監(jiān)督矩陣線性系統(tǒng)碼的監(jiān)督矩陣 H H 和生成矩陣和生成矩陣 G G 之間可以直接互換。之間可以直接互換。rkrSrkkSIPHQIGrkrkTkrrTkrrkkTrkrrkkTSS0QPIPQIIPQIHG)()(krTrkTkrrk P PQQP PQQ)()(或或所所

24、以以， ) 6 . 3 . 7 ()( rTrkSrkkSI IQQHHQQI IGG7.1線性分組碼第19頁2022-6-12 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH陣陣：可可直直接接寫寫出出它它的的生生成成矩矩(3) 生成矩陣與一致監(jiān)督矩陣的關(guān)系生成矩陣與一致監(jiān)督矩陣的關(guān)系舉例：舉例： 已知已知 (7,4) 線性系統(tǒng)碼的監(jiān)督矩陣為：線性系統(tǒng)碼的監(jiān)督矩陣為：QQT 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH陣陣：可可直直接

25、接寫寫出出它它的的生生成成矩矩 1101000011010011100101010001100101101011100010111)4,7()4,7(GGHH陣陣：可可直直接接寫寫出出它它的的生生成成矩矩7.1線性分組碼第20頁2022-6-12(4) 對偶碼對偶碼 對偶碼：對偶碼：對一個對一個 (n,k) 線性碼線性碼C CI，由于，由于 HHrn(GGkn)T=(0 0kr)T，如果以如果以G G 作監(jiān)督矩陣，而以作監(jiān)督矩陣，而以 H H 作生成矩陣，可構(gòu)造另一個碼作生成矩陣，可構(gòu)造另一個碼 C CId，C CId是一個是一個 (n,nk) 線性碼，稱碼線性碼，稱碼 C CId 為原碼的對

26、偶碼為原碼的對偶碼。 例如例如： (7,4) 線性碼的對偶碼是線性碼的對偶碼是 (7,3) 碼：碼：q (7,3) 碼的生成矩陣碼的生成矩陣 GG(7,3) 是是 (7,4) 碼監(jiān)督矩陣碼監(jiān)督矩陣 HH(7,4) 101110011100100111001100101101011100010111)4,7()3,7(化化成成標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形式式HHGG7.1線性分組碼第21頁2022-6-12 4505614562463) 3 , 7 (1000110010001100101110001101cccccccccccccTT得得：由由0 0HHC CHH (n,k) 線性碼的編碼：線性碼的編碼：根據(jù)

27、線性碼的監(jiān)督矩陣或生成矩陣，根據(jù)線性碼的監(jiān)督矩陣或生成矩陣，將長為將長為 k 的信息組變換成長為的信息組變換成長為 n(nk) 的碼字。的碼字。 利用監(jiān)督矩陣構(gòu)造利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路線性分組碼的編碼電路q 設(shè)碼字為：設(shè)碼字為：C C=(c6c5c4c3c2c1c0)q 碼的監(jiān)督矩陣為：碼的監(jiān)督矩陣為： 4505614562463) 3 , 7 (1000110010001100101110001101cccccccccccccTT得得：由由0 0HHC CHH7.1線性分組碼的編碼第22頁2022-6-12 利用監(jiān)督矩陣構(gòu)造利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼

28、的編碼電路：線性分組碼的編碼電路：q 根據(jù)上面方程組可直接畫出根據(jù)上面方程組可直接畫出 (7,3) 碼的并行編碼電路和串行編碼電碼的并行編碼電路和串行編碼電路路:7.1線性分組碼的編碼3642654165054c c cc c c cc c cc c c 第23頁2022-6-12 利用監(jiān)督矩陣構(gòu)造利用監(jiān)督矩陣構(gòu)造 (7,4) 線性分組碼的編碼電路：線性分組碼的編碼電路：q 根據(jù)上面方程組可直接畫出根據(jù)上面方程組可直接畫出 (7,4) 碼的并行編碼電路和串行編碼碼的并行編碼電路和串行編碼電路電路:7.1線性分組碼的編碼第24頁2022-6-12(1) 漢明距離、漢明重量和漢明球漢明距離、漢明重

29、量和漢明球 漢明距離漢明距離（距離）：在（距離）：在 (n,k) 線性碼中，兩個碼字線性碼中，兩個碼字 UU、V V 之間對應(yīng)之間對應(yīng)碼元位上符號取值不同的個數(shù)，稱為碼字碼元位上符號取值不同的個數(shù)，稱為碼字 UU、V V 之間的漢明距離。之間的漢明距離。q 線性分組碼的一個碼字對應(yīng)于線性分組碼的一個碼字對應(yīng)于 n 維線性空間中的一點，碼字間的維線性空間中的一點，碼字間的距離即為空間中兩距離即為空間中兩對應(yīng)點的距離。因此，碼字間的距離滿足一般距對應(yīng)點的距離。因此，碼字間的距離滿足一般距離公理：離公理： 10)(),(niiivudV VUU 三三角角不不等等式式對對稱稱性性非非負(fù)負(fù)性性),(),

30、(),(),(),(0),(WWUUWWV VV VUUUUV VV VUUV VUUdddddd7.1線性分組碼第25頁2022-6-12(1) 漢明距離、漢明重量和漢明球漢明距離、漢明重量和漢明球 最小距離最小距離 dmin：在在 (n,k) 線性碼的碼字集合中，任意兩個碼字間距線性碼的碼字集合中，任意兩個碼字間距離的最小值，叫做碼的最小距離。若離的最小值，叫做碼的最小距離。若 C C(i) 和和 C C(j) 是任意兩個碼字，則是任意兩個碼字，則碼的最小距離表示為：碼的最小距離表示為：q 碼的最小距離是衡量碼抗干擾能力（檢、糾錯能力）的重要參數(shù)。碼的最小距離是衡量碼抗干擾能力（檢、糾錯能

31、力）的重要參數(shù)。碼的最小距離越大，碼抗干擾能力就越強(qiáng)。碼的最小距離越大，碼抗干擾能力就越強(qiáng)。 12 , 1 ,0,),(min)()(min kjijijiddC CC C漢明球：漢明球：以碼字以碼字 C C 為中心，半徑為為中心，半徑為 t 的漢明球是與的漢明球是與 C C 的漢明距離的漢明距離t 的向量全體的向量全體 S SC C(t) ：q任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明距離小漢明距離 dmin。 tdt ),()(R RC CR RS SC C7.1線性分組碼第26頁2022-6-12(1) 漢明距離、漢

32、明重量和漢明球漢明距離、漢明重量和漢明球漢明球：漢明球：漢明重量（碼字重量）漢明重量（碼字重量）W：碼字中非碼字中非 0 碼元符號的個數(shù)，稱為該碼碼元符號的個數(shù)，稱為該碼字的漢明重量。字的漢明重量。q在二元線性碼中，碼字重量就是碼字中含在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。的個數(shù)。最小重量最小重量 Wmin ：線性分組碼線性分組碼 C CI 中，非中，非 0 0 碼字重量最小值，叫做碼碼字重量最小值，叫做碼 C CI 的最小重量：的最小重量：Wmin =minW(V V),V VC CI ,V V0 07.1線性分組碼第27頁2022-6-12(1) 漢明距離、漢明重量和漢明球漢明

33、距離、漢明重量和漢明球 最小距離最小距離 與最小重量與最小重量 的關(guān)系：的關(guān)系：線性分組碼的最小距離等于它的最線性分組碼的最小距離等于它的最小重量。小重量。 檢錯能力：檢錯能力：如果一個線性碼能檢出長度如果一個線性碼能檢出長度l 個碼元的任何錯誤圖樣，個碼元的任何錯誤圖樣，稱碼的檢錯能力為稱碼的檢錯能力為 l。 糾錯能力：糾錯能力：如果線性碼能糾正長度如果線性碼能糾正長度t 個碼元的任意錯誤圖樣，稱個碼元的任意錯誤圖樣，稱碼的糾錯能力為碼的糾錯能力為 t。 最小距離與檢糾錯能力的關(guān)系：最小距離與檢糾錯能力的關(guān)系：線性碼的最小距離越大，意味著線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼

34、的檢、糾錯能力越強(qiáng)。任意碼字間的差別越大，則碼的檢、糾錯能力越強(qiáng)。7.1線性分組碼第28頁2022-6-12(2) 最小距離與檢、糾錯能力最小距離與檢、糾錯能力最小距離與糾錯能力：最小距離與糾錯能力：(n,k) 線性碼能糾線性碼能糾 t 個錯誤的充要條件是碼的個錯誤的充要條件是碼的最小距離為：最小距離為： dmin2t+1 最小距離與檢錯能力：最小距離與檢錯能力：(n,k) 線性碼能夠發(fā)現(xiàn)線性碼能夠發(fā)現(xiàn) l 個錯誤的充要條件是個錯誤的充要條件是碼的最小距離為：碼的最小距離為：dminl+1最小距離與檢錯能力：最小距離與檢錯能力： 幾何意義：幾何意義：7.1線性分組碼第29頁2022-6-12(

35、2) 最小距離與檢、糾錯能力最小距離與檢、糾錯能力最小距離與檢、糾錯能力：最小距離與檢、糾錯能力：(n,k) 線性碼能糾線性碼能糾 t 個錯誤，并能發(fā)現(xiàn)個錯誤，并能發(fā)現(xiàn) l 個個錯誤錯誤 (lt) 的充要條件是碼的最小距離為：的充要條件是碼的最小距離為： dmin t+l+1 最小距離與檢、糾錯能力：最小距離與檢、糾錯能力： 幾何意義：幾何意義：7.1線性分組碼第30頁2022-6-12(2) 最小距離與檢、糾錯能力最小距離與檢、糾錯能力當(dāng)當(dāng) (n,k) 線性碼的最小距離線性碼的最小距離 dmin 給定后，可按實際需要給定后，可按實際需要靈活安排糾錯的數(shù)目。靈活安排糾錯的數(shù)目。： dmin t

36、+l+1例如：例如：對對 dmin=8 的碼，可的碼，可用來糾用來糾 3 檢檢 4 錯，或糾錯，或糾 2檢檢 5 錯，或糾錯，或糾 1 檢檢 6錯，或者錯，或者只用于檢只用于檢 7 個錯誤。個錯誤。7.1線性分組碼第31頁2022-6-12(3) 線性碼的最小距離與監(jiān)督矩陣的關(guān)系線性碼的最小距離與監(jiān)督矩陣的關(guān)系定理定理1：設(shè)設(shè) H H 為為 (n,k) 線性碼的一致監(jiān)督矩陣，若線性碼的一致監(jiān)督矩陣，若 H H 中中任意任意 S 列線性無關(guān)，而列線性無關(guān)，而 H H 中存在中存在 (S+1) 列線性相關(guān)，則列線性相關(guān)，則碼的最小距離為碼的最小距離為 (S+1)。定理定理2：若碼的最小距離為若碼的

37、最小距離為 (S+1)，則該碼監(jiān)督矩陣的任，則該碼監(jiān)督矩陣的任意意 S 列線性無關(guān)，而必存在有相關(guān)的列線性無關(guān)，而必存在有相關(guān)的 (S+1)列。列。定理定理3：在二元線性碼的監(jiān)督矩陣在二元線性碼的監(jiān)督矩陣 H H 中，如果任一列都中，如果任一列都不是全不是全“0”，且任兩列都不相等，則該碼能糾一個錯誤。，且任兩列都不相等，則該碼能糾一個錯誤。（S=2，dmin=3）7.1線性分組碼第32頁2022-6-12(1) 如何譯碼？如何譯碼？ 用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個碼用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個碼字字 R R 后，校驗后，校驗 HH R R T=0 0T 是否成立

38、：是否成立：若關(guān)系成立，則認(rèn)為若關(guān)系成立，則認(rèn)為 R R 是一個碼字；是一個碼字；否則，判碼字在傳輸中發(fā)生了錯誤；否則，判碼字在傳輸中發(fā)生了錯誤；HH R R T 的值是否為的值是否為 0 0 是校驗碼字出錯與否的依據(jù)。是校驗碼字出錯與否的依據(jù)。(2) 伴隨式伴隨式/監(jiān)督子監(jiān)督子/校驗子：校驗子：S S=R R H H T 或或 S S T=HH R R T1. 伴隨式和錯誤檢測伴隨式和錯誤檢測7.1線性分組碼第33頁2022-6-12(3) 伴隨式的計算伴隨式的計算 發(fā)送碼字：發(fā)送碼字：C C=(cn1,cn2,c0) 信道錯誤圖樣：信道錯誤圖樣：E E=(en1,en2,e0) q ei=

39、0，表示第，表示第 i 位無錯；位無錯；q ei=1，表示第，表示第 i 位有錯。位有錯。i=n1,n2,0 接收字：接收字：R R=(rn1,rn2,r0)=C C+E E=(cn1+en1,cn2+en2,c0 +e0) 求接收字的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗）求接收字的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗） S S T=HH R R T=HH (C C+E E )T=HH C C T+HH E E T H H C C T=0 0T，所以，所以 S S T=HH E E T 設(shè)設(shè) HH=(h h1,h h2,h hn)，（，（h hi 表示表示 H H 的列）。代入上式得：的列）。代入上式

40、得：S S T=h h1 en1+ h h2 en2+ + h hn e07.1線性分組碼的譯碼第34頁2022-6-12(4) 伴隨式的特性伴隨式的特性 伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯誤圖樣決定；即伴隨式僅由錯誤圖樣決定； 伴隨式是錯誤的判別式：伴隨式是錯誤的判別式：q 若若 S S=0 0，則判為沒有出錯，接收字是一個碼字；，則判為沒有出錯，接收字是一個碼字；q 若若 S S0 0，則判為有錯。，則判為有錯。 不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對

41、二元碼，伴隨式是對二元碼，伴隨式是 H H 陣中與錯誤碼元對應(yīng)列之和。陣中與錯誤碼元對應(yīng)列之和。7.1線性分組碼的譯碼S T=h1 en1+ h2 en2+ + hn e0第35頁2022-6-12(5) 舉舉 例：例：(7,3) 碼接收字碼接收字 R R 的伴隨式計算的伴隨式計算 若接收字中沒有錯誤：若接收字中沒有錯誤：q 設(shè)發(fā)送碼字設(shè)發(fā)送碼字 C C=1010011，接收碼字，接收碼字 R R1010011，R R 與與 C C 相同：相同：q 但接收端譯碼器并不知道就是發(fā)送的碼字；但接收端譯碼器并不知道就是發(fā)送的碼字；q 根據(jù)接收字根據(jù)接收字R R 計算伴隨式：計算伴隨式：S S T=

42、HR HR T =0 0Tq 因此，譯碼器判接收字無錯。因此，譯碼器判接收字無錯。 1000110010001100101110001101H7.1線性分組碼的譯碼第36頁2022-6-12(5) 舉舉 例：例：(7,3) 碼接收矢量碼接收矢量 R R 的伴隨式計算的伴隨式計算 若接收字中有若接收字中有 1 位錯誤：位錯誤：q 發(fā)送碼字發(fā)送碼字C C=1010011，接收碼字，接收碼字R R=1110011，伴隨式為：，伴隨式為：q (7,3) 碼是糾單個錯誤的碼，且碼是糾單個錯誤的碼，且S S T 等于等于HH 的第二列，因此判定接收的第二列，因此判定接收字字R R 的第二位是錯的。的第二位

43、是錯的。q 由于接收字由于接收字R R 中錯誤碼元數(shù)與碼的糾錯能力相符，所以譯碼正確。中錯誤碼元數(shù)與碼的糾錯能力相符，所以譯碼正確。 111011001111000110010001100101110001101TTR RHHS S譯譯碼碼器器判判為為有有錯錯由由于于0 0S S T7.1線性分組碼的譯碼第37頁2022-6-12(5) 舉舉 例：例：(7,3) 碼接收矢量碼接收矢量 R R 的伴隨式計算的伴隨式計算 當(dāng)碼元錯誤多于當(dāng)碼元錯誤多于 1 個時：個時：q 發(fā)送碼字發(fā)送碼字C C=1010011，接收碼字，接收碼字R R=0011011，伴隨式為：，伴隨式為：q 由于由于S S T

44、是第一列和第四列之和，不等于是第一列和第四列之和，不等于0 0；q 但但S S T 與與 HH 陣中任何一列都不相同無法判定錯誤出在哪些位上，陣中任何一列都不相同無法判定錯誤出在哪些位上，只是發(fā)現(xiàn)有錯。只是發(fā)現(xiàn)有錯。 011011011001000110010001100101110001101TTR RHHS S7.1線性分組碼的譯碼第38頁2022-6-12(6) 伴隨式計算電路伴隨式計算電路伴隨式的計算可用電路來實現(xiàn)。伴隨式的計算可用電路來實現(xiàn)。(7,3) 碼為例：接收字碼為例：接收字 R R =(r6r5r4r3r2r1r0)，伴隨式：，伴隨式： 0123045156345634601

45、234561000110010001100101110001101ssssrrrrrrrrrrrrrrrrrrrrTTR RHHS S7.1線性分組碼的譯碼第39頁2022-6-12(6) 伴隨式計算電路伴隨式計算電路7.1線性分組碼的譯碼64336543265115400TrrrsrrrrsrrrsrrrsS第40頁2022-6-12(1) 最佳譯碼準(zhǔn)則（最大似然譯碼）最佳譯碼準(zhǔn)則（最大似然譯碼） 通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。 對于對于 FEC 方式，采用糾錯碼后的碼字差錯概率為方式，采用糾錯碼后的碼字差錯概

46、率為 pwe：q p(C C)：發(fā)送碼字發(fā)送碼字C C 的先驗概率的先驗概率q p(C C/R R)：后驗概率后驗概率)()(RCCC/pppwe2. 糾錯譯碼糾錯譯碼若碼字?jǐn)?shù)為若碼字?jǐn)?shù)為 2k，對充分隨機(jī)的消息源有，對充分隨機(jī)的消息源有 p(C C)=1/ 2k，所以最小化的，所以最小化的 pwe等價為最小化等價為最小化 p(C C C C/R R )，又等價為最大化：，又等價為最大化：p(C C =C C/R R)；對于對于 BSC 信道：信道：最大化的最大化的 p(C C =C C/R R ) 等價于最大化的等價于最大化的 p(R R /C C) ，最大化的最大化的 p(R R /C C

47、) 又等價于最小化又等價于最小化 d(R R,C C)，所以使差錯概率最小的，所以使差錯概率最小的譯碼是使接收向量譯碼是使接收向量 R R 與輸出碼字與輸出碼字 C C 距離最小的譯碼。距離最小的譯碼。) ,(),(min: CRCRCCddii7.1線性分組碼的譯碼第41頁2022-6-12(2) 查表譯碼法查表譯碼法 按最小距離譯碼，對有按最小距離譯碼，對有 2k 個碼字的個碼字的 (n,k) 線性碼，為了找到與接線性碼，為了找到與接收字收字 R R 有最小距離的碼字，需將有最小距離的碼字，需將 R R 分別和分別和 2k 個碼字比較，求出最小個碼字比較，求出最小距離。其中利用距離。其中利

48、用“標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列”譯碼是最典型的方法。譯碼是最典型的方法。(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 碼字參數(shù)：碼字參數(shù)：發(fā)送碼字：取自于發(fā)送碼字：取自于 2k 個碼字集合個碼字集合 C C； 接收碼字：可以是接收碼字：可以是 2n 個個 n 重中任一個矢量。重中任一個矢量。 譯碼方法譯碼方法把把 2n 個個 n 重矢量劃分為重矢量劃分為 2k 個互不相交的子集個互不相交的子集 ，使得在，使得在每個子集中僅含一個碼字；每個子集中僅含一個碼字；根據(jù)碼字與子集間一一對應(yīng)的關(guān)系，若接收矢量根據(jù)碼字與子集間一一對應(yīng)的關(guān)系，若接收矢量 R Rl 落在子集落在子集 D Dl 中，中，就把就把 R Rl 譯為子集譯為子集

49、 D Dl 含有的碼字含有的碼字 C Cl；當(dāng)接收矢量當(dāng)接收矢量 R R 與實際發(fā)送碼字在同一子集中時，譯碼就是正確的。與實際發(fā)送碼字在同一子集中時，譯碼就是正確的。k221,DDD7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第42頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列構(gòu)造方法標(biāo)準(zhǔn)陣列構(gòu)造方法先將先將 2k 個碼字排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全個碼字排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全 0 碼字碼字 C C1=(000) 放在最左面的位置上；放在最左面的位置上；然后在剩下的然后在剩下的 (2n2k) 個個 n 重中選取一個重量最輕的重中選取一個重量最輕的 n 重重 E

50、 E2 放在放在全全 0 碼字碼字 C C1 下面，再將下面，再將 E E2 分別和碼字分別和碼字 相加，放在相加，放在對應(yīng)碼字下面構(gòu)成陣列第二行；對應(yīng)碼字下面構(gòu)成陣列第二行；在第二次剩下的在第二次剩下的 n 重中，選取重量最輕的重中，選取重量最輕的 n 重重 E E3，放在，放在 E E2 下面，下面，并將并將 E E3 分別加到第一行各碼字上，得到第三行；分別加到第一行各碼字上，得到第三行；，繼續(xù)這樣做下去，直到全部，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到下表所示給定重用完為止。得到下表所示給定 (n,k) 線性碼的標(biāo)準(zhǔn)陣列。線性碼的標(biāo)準(zhǔn)陣列。k232,CCC7.1線性分組碼的譯碼

51、2. 糾錯譯碼糾錯譯碼第43頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列構(gòu)造方法標(biāo)準(zhǔn)陣列構(gòu)造方法7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第44頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性定理定理1：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個個 n 重中重中任一個任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。定理定理2（線性碼糾錯極限定理）：二元線性碼糾錯極限定理）：二元 (n,k) 線性碼能糾線性碼能糾 2nk 個錯誤個錯誤圖樣。這圖樣。這 2nk 個可糾的錯誤圖樣，包括個

52、可糾的錯誤圖樣，包括 0 0 矢量在內(nèi)，即把無錯的矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。情況也看成一個可糾的錯誤圖樣。陪集：陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個陪集。標(biāo)準(zhǔn)陣列的每一行叫做碼的一個陪集。陪集首：陪集首：每個陪集的第一個元素叫做陪集首。每個陪集的第一個元素叫做陪集首。(n,k) 線性碼的標(biāo)準(zhǔn)陣列有線性碼的標(biāo)準(zhǔn)陣列有 2k 列（和碼字?jǐn)?shù)量相等），列（和碼字?jǐn)?shù)量相等），2n/2k= 2nk 行，且任何兩列和兩行都沒有相同的元素。行，且任何兩列和兩行都沒有相同的元素。7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第45頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)

53、準(zhǔn)陣列的特性線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：一個可糾一個可糾 t 個錯誤的線性碼必個錯誤的線性碼必須滿足：須滿足：上式中等式成立時的線性碼稱為完備碼。即：上式中等式成立時的線性碼稱為完備碼。即：對于完備碼，由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤對于完備碼，由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的圖樣數(shù)，所以完備碼的 (nk) 個監(jiān)督碼元得到了充分的利用。個監(jiān)督碼元得到了充分的利用。 tiknintnnn02112 tiknin027.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第46頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣

54、列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性完備譯碼：完備譯碼：(n,k) 線性碼的所有線性碼的所有 2nk 個伴隨式，在譯碼過程中都用個伴隨式，在譯碼過程中都用來糾正所有小于等于來糾正所有小于等于 個隨機(jī)錯誤，以及部分大于個隨機(jī)錯誤，以及部分大于 t 的的錯誤圖樣。錯誤圖樣。限定距離譯碼：限定距離譯碼：任一個任一個 (n,k) 線性碼，能糾正線性碼，能糾正 個隨機(jī)個隨機(jī)錯誤，如果在譯碼時僅糾正錯誤，如果在譯碼時僅糾正 t t 個錯誤，而當(dāng)錯誤個數(shù)大于個錯誤，而當(dāng)錯誤個數(shù)大于 t 時，時，譯碼器不進(jìn)行糾錯而僅指出發(fā)生了錯誤。譯碼器不進(jìn)行糾錯而僅指出發(fā)生了錯誤。 21dt 21dt7.1線性分組碼的譯碼2.

55、 糾錯譯碼糾錯譯碼第47頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼從多維矢量空間的角度看完備碼q 假定圍繞每一個碼字假定圍繞每一個碼字 C Ci 放置一個半徑為放置一個半徑為 t 的球，每個球內(nèi)包含的球，每個球內(nèi)包含了與該碼字漢明距離小于等于了與該碼字漢明距離小于等于 t 的所有接收碼字的所有接收碼字 R R 的集合；的集合；q 在半徑為在半徑為 的球內(nèi)的接收碼字?jǐn)?shù)是：的球內(nèi)的接收碼字?jǐn)?shù)是：q 因為有因為有 2k 個可能發(fā)送的碼字，也就有個可能發(fā)送的碼字，也就有 2k 個不相重疊的半徑為個不相重疊的半徑為 t 的球。包含在的球。包含

56、在 2k 個球中的碼字總數(shù)不會超過個球中的碼字總數(shù)不會超過 2n 個可能的接收碼字。個可能的接收碼字。 tiin0 21dt7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第48頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼從多維矢量空間的角度看完備碼q 于是一個糾于是一個糾 t 個差錯的碼必然滿足不等式：個差錯的碼必然滿足不等式：q 如果上式中等號成立，表示所有的接收碼字都落在如果上式中等號成立，表示所有的接收碼字都落在 2k 個球內(nèi)，而個球內(nèi)，而球外沒有一個碼，這就是完備碼。球外沒有一個碼，這就是完備碼。 tikntinkinin002

57、22：即即7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第49頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼從多維矢量空間的角度看完備碼q 完備碼特性：完備碼特性：圍繞圍繞 2k 個碼字，個碼字，漢明距離為漢明距離為 t=INT(dmin1)/2 的的所有球都是不相交的，每一個接所有球都是不相交的，每一個接收碼字都落在這些球中之一，因收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為此接收碼與發(fā)送碼的距離至多為 t，這時所有重量這時所有重量 t 的錯誤圖樣都能的錯誤圖樣都能用最佳（最小距離）譯碼器得到用最佳（最小距離）譯碼器得到糾正

58、，而所有重量糾正，而所有重量t+1 的錯誤圖的錯誤圖樣都不能糾正。樣都不能糾正。7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第50頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性 從多維矢量空間的角度看完備碼從多維矢量空間的角度看完備碼q 舉例：舉例：對糾一個錯誤的對糾一個錯誤的 (7,4) 漢明碼：漢明碼：(7,4) 漢明碼是一個完備碼。漢明碼是一個完備碼。 所有漢明碼都是完備碼：所有漢明碼都是完備碼：（滿足（滿足2nk = 2r=n+1）。）。 112,811, 82nnknkn所所以以：7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第51頁2022-6-12(3)

59、 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性 標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列譯碼 = 最小距離譯碼最小距離譯碼 = 最佳譯碼最佳譯碼q 陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首；出現(xiàn)概率最大的錯誤圖樣作陪集首；q 重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時是選重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時是選取重量最輕的取重量最輕的 n 重作陪集首；重作陪集首；q 當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼字間的

60、距離（等于陪集首）最??；碼字間的距離（等于陪集首）最?。籷 因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼；小距離譯碼；q 所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。7.1線性分組碼的譯碼2. 糾錯譯碼糾錯譯碼第52頁2022-6-12(3) 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性定理定理3：在標(biāo)準(zhǔn)陣列中，一個陪集的所有在標(biāo)準(zhǔn)陣列中，一個陪集的所有 2k 個個 n 重有相同的伴隨式，重有相同的伴隨式，不同的陪集伴隨式互不相同。不同的陪集伴隨式互不相同。證明證明：設(shè)設(shè) H H 為給定為給