第三章線性分組碼

1、State Key Laboratory of Integrated Services Networks 第三章第三章 線性分組碼線性分組碼要求掌握的內(nèi)容要求掌握的內(nèi)容線性分組碼的定義及性質(zhì)線性分組碼的定義及性質(zhì)碼的一致校驗(yàn)矩陣和生成矩陣碼的一致校驗(yàn)矩陣和生成矩陣碼的伴隨式、標(biāo)準(zhǔn)陣列及譯碼碼的伴隨式、標(biāo)準(zhǔn)陣列及譯碼漢明碼及譯碼漢明碼及譯碼第一節(jié)第一節(jié) 線性分組碼基本概念線性分組碼基本概念線性分組碼定義線性分組碼定義生成矩陣生成矩陣校驗(yàn)矩陣校驗(yàn)矩陣對(duì)偶碼、系統(tǒng)碼和縮短碼對(duì)偶碼、系統(tǒng)碼和縮短碼編碼與譯碼編碼與譯碼對(duì)對(duì) 二進(jìn)制二進(jìn)制(n, k)碼，信息數(shù)量（或合法碼字?jǐn)?shù)）為碼，信息數(shù)量（或合法碼字?jǐn)?shù)

2、）為2k，可用編碼空間的點(diǎn)數(shù)為，可用編碼空間的點(diǎn)數(shù)為2n個(gè)。個(gè)。任一種任一種2k信息集合到二進(jìn)制序列集合信息集合到二進(jìn)制序列集合(2n)的映射都的映射都是一種是一種(n, k)碼。因此總共可能的編碼方案有碼。因此總共可能的編碼方案有 種。如，共有種。如，共有1029種種(100,50)碼。碼。譯碼運(yùn)算量：如果直接用最大似然序列譯碼，對(duì)譯碼運(yùn)算量：如果直接用最大似然序列譯碼，對(duì)一般性的編碼而言，正比于一般性的編碼而言，正比于n* 2k ，對(duì)，對(duì)(100,50)碼，碼，則為則為1017。幾乎是不可能譯碼的。幾乎是不可能譯碼的。22nk為什么要引入線性碼為什么要引入線性碼發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究

3、的主要問(wèn)題發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問(wèn)題編碼方案太多，以至全局搜索是不可能的編碼方案太多，以至全局搜索是不可能的現(xiàn)實(shí)的做法是對(duì)編碼方案加以一定的約束，在一個(gè)子集中現(xiàn)實(shí)的做法是對(duì)編碼方案加以一定的約束，在一個(gè)子集中尋找局部最優(yōu)尋找局部最優(yōu)這種約束即要能包含盡可能好的碼，又要便于分析，便于這種約束即要能包含盡可能好的碼，又要便于分析，便于譯碼譯碼目前對(duì)線性系統(tǒng)的研究遠(yuǎn)比非線性系統(tǒng)充分目前對(duì)線性系統(tǒng)的研究遠(yuǎn)比非線性系統(tǒng)充分State Key Laboratory of Integrated Services Networks 一、線性一、線性分組碼分組碼基本概念基本概念(P52-54)2k2

4、n利用線性空間中的子空間作為許用碼字的編碼利用線性空間中的子空間作為許用碼字的編碼稱線性碼稱線性碼當(dāng)線性空間為有限維空間時(shí)即為線性分組碼當(dāng)線性空間為有限維空間時(shí)即為線性分組碼GF(q)上的上的n維線性空間維線性空間Vn中的一個(gè)中的一個(gè)k維子空間維子空間Vn,k稱為稱為(n,k)線性分組碼線性分組碼)(min,iknCCwdi性質(zhì)：性質(zhì)：n, k, d線性分組碼的最小距離等于非線性分組碼的最小距離等于非零碼字的最小重量零碼字的最小重量碼的最小距離碼的最小距離在大部分情況下，碼的最小距離是碼設(shè)計(jì)在大部分情況下，碼的最小距離是碼設(shè)計(jì)的首選目標(biāo)的首選目標(biāo)它代表了漸近性能它代表了漸近性能大部分分組譯碼算

5、法的譯碼能力也限于最小距大部分分組譯碼算法的譯碼能力也限于最小距離離線性分組碼的特點(diǎn)線性分組碼的特點(diǎn)全零序列是許用碼字全零序列是許用碼字與任一碼字的距離譜都相同與任一碼字的距離譜都相同只須考慮重量譜只須考慮重量譜自由距就是最小碼重量自由距就是最小碼重量平均差錯(cuò)概率就是當(dāng)發(fā)全零序列時(shí)的條件差錯(cuò)概率：平均差錯(cuò)概率就是當(dāng)發(fā)全零序列時(shí)的條件差錯(cuò)概率：Pe= x1P(x1)P(e|x1)= P(e|全零全零)State Key Laboratory of Integrated Services Networks 如何根據(jù)如何根據(jù)k個(gè)信息比特來(lái)確定對(duì)應(yīng)的個(gè)信息比特來(lái)確定對(duì)應(yīng)的n-k個(gè)校驗(yàn)比特？個(gè)校驗(yàn)比特？

6、利用校驗(yàn)矩陣?yán)眯ｒ?yàn)矩陣?yán)蒙删仃嚴(yán)蒙删仃嚱o定參數(shù)給定參數(shù)n、k和和dState Key Laboratory of Integrated Services Networks 三、碼的生成矩陣三、碼的生成矩陣(P56)從線性空間的角度描述分組碼從線性空間的角度描述分組碼由于由于n,k,d線性分組碼是一個(gè)線性分組碼是一個(gè)k維線性空間維線性空間因此，必可找到因此，必可找到k個(gè)線性無(wú)關(guān)的矢量，能張成該線性空間個(gè)線性無(wú)關(guān)的矢量，能張成該線性空間kCCC,21是是k個(gè)線性無(wú)關(guān)的矢量，則對(duì)任意個(gè)線性無(wú)關(guān)的矢量，則對(duì)任意C，可有：，可有：kkmmmCCCC2211mGCCCkkmmm2121,G稱為該

7、分組碼的生成矩陣稱為該分組碼的生成矩陣設(shè)設(shè)注：注：1)生成矩陣生成矩陣G中的每一行都是一個(gè)碼字中的每一行都是一個(gè)碼字2)任意任意k個(gè)線性獨(dú)立的碼字都可以作為生成矩個(gè)線性獨(dú)立的碼字都可以作為生成矩陣陣3)給定一個(gè)給定一個(gè)n,k,d線性分組碼，其生成矩陣可線性分組碼，其生成矩陣可有多個(gè)有多個(gè) State Key Laboratory of Integrated Services Networks 四、碼的校驗(yàn)矩陣四、碼的校驗(yàn)矩陣(P54)從線性方程組的角度描述分組碼從線性方程組的角度描述分組碼n-k個(gè)校驗(yàn)位可用個(gè)校驗(yàn)位可用k個(gè)已知的信息位表示出來(lái)個(gè)已知的信息位表示出來(lái)個(gè)校驗(yàn)位個(gè)信息位knknknk

8、knnncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 11000100010001021)(,011, 0, 21, 2, 11, 1ccchhhhhhnnnknknnknknnknknknnkn列行，校驗(yàn)矩陣校驗(yàn)矩陣校驗(yàn)矩陣H與任意一個(gè)碼字之積為零，因此有與任意一個(gè)碼字之積為零，因此有0GHT45604561456245631101001111111011ccccccccccccccccExamples1000110

9、010001100101110001101HState Key Laboratory of Integrated Services Networks 五、幾個(gè)概念五、幾個(gè)概念(P57-58)對(duì)偶碼、系統(tǒng)碼和縮短碼對(duì)偶碼、系統(tǒng)碼和縮短碼對(duì)系統(tǒng)碼對(duì)系統(tǒng)碼PIGkknTIPH縮短碼縮短碼 從從n,k,d線性分組碼的所有碼字中，把前面線性分組碼的所有碼字中，把前面i位全為零的碼字挑選出來(lái)構(gòu)成一個(gè)新的子集，該位全為零的碼字挑選出來(lái)構(gòu)成一個(gè)新的子集，該子集即為子集即為n,k,d的縮短碼。的縮短碼。問(wèn)題：最小漢明距離有什么變化？問(wèn)題：最小漢明距離有什么變化？第二節(jié)第二節(jié) 線性分組碼的譯碼線性分組碼的譯碼伴隨

10、式伴隨式漢明碼漢明碼標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列State Key Laboratory of Integrated Services Networks 一、伴隨式一、伴隨式(P59)設(shè)發(fā)送碼字設(shè)發(fā)送碼字021,cccnnC接收序列接收序列021,rrrnnR根據(jù)錯(cuò)誤圖樣的概念，根據(jù)錯(cuò)誤圖樣的概念，R=C+ETTTEHHECRHS)(S是校驗(yàn)矩陣是校驗(yàn)矩陣H中某幾列數(shù)據(jù)的線性組合中某幾列數(shù)據(jù)的線性組合兩個(gè)定理兩個(gè)定理定理定理1：n,k,d線性分組碼有最小漢明距離線性分組碼有最小漢明距離d的充要條件是，的充要條件是，H矩陣中任意矩陣中任意d-1列線性無(wú)關(guān)列線性無(wú)關(guān)定理定理2：n,k,d線性分組碼最大可能的最

11、小線性分組碼最大可能的最小漢明距離漢明距離d等于等于n-k+1Singleton限限(n, k, d)線性分組碼的最大可能的最小距離小于等線性分組碼的最大可能的最小距離小于等于于n-k+1, 即即dn-k+1若系統(tǒng)碼的最小距離若系統(tǒng)碼的最小距離d=n-k+1，則此碼為極大最，則此碼為極大最小距離可分碼，簡(jiǎn)稱小距離可分碼，簡(jiǎn)稱MDS碼碼State Key Laboratory of Integrated Services Networks 二、漢明碼二、漢明碼參數(shù)參數(shù) 碼長(zhǎng)：碼長(zhǎng)： n=2m-1 信息位長(zhǎng)度：信息位長(zhǎng)度：k=2m-1-m 最小漢明距離：最小漢明距離：d=3 校驗(yàn)矩陣有校驗(yàn)矩陣有

12、m行，行，2m-1列，取互不相同的列，取互不相同的m重構(gòu)重構(gòu)成成漢明碼的對(duì)偶碼是一個(gè)漢明碼的對(duì)偶碼是一個(gè)2m-1, m, 2m-1碼，也稱為單純碼或碼，也稱為單純碼或極長(zhǎng)碼，也稱為最長(zhǎng)線性移存器碼。極長(zhǎng)碼，也稱為最長(zhǎng)線性移存器碼。如果用如果用BPSK，并看成，并看成2m進(jìn)制調(diào)制時(shí)，是一種自相關(guān)性最好的調(diào)制方式進(jìn)制調(diào)制時(shí)，是一種自相關(guān)性最好的調(diào)制方式GF(2)上的7,4,3漢明碼，001,010,011,100,101,110,111,000。校驗(yàn)矩陣為：Examples:101010111001101111000HState Key Laboratory of Integrated Servi

13、ces Networks 三、標(biāo)準(zhǔn)陣列譯碼(p63)線性分組碼的基本譯碼步驟線性分組碼的基本譯碼步驟 Step1: 由接收到的序列由接收到的序列R，計(jì)算伴隨式，計(jì)算伴隨式S=RHT； Step2: 若若S=0，正確接收；若，正確接收；若S不為零，尋找不為零，尋找錯(cuò)誤圖樣；錯(cuò)誤圖樣； Step3: 由錯(cuò)誤圖樣解出碼字由錯(cuò)誤圖樣解出碼字C=R-E。標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列 根據(jù)許用碼字將禁用碼字進(jìn)行分類，根據(jù)許用碼字將禁用碼字進(jìn)行分類， 分類的依據(jù)是錯(cuò)誤圖樣。分類的依據(jù)是錯(cuò)誤圖樣。C1C2kC2CiE2E3knE2C2+E2C2+E3Ci+E3Ci+E222ECk32ECkknkEC22C2+Ci+knE

14、2knE2碼字碼字禁用碼字禁用碼字標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列譯碼(陪集首陪集首)兩個(gè)概念兩個(gè)概念 完備譯碼完備譯碼:n,k,d線性分組碼的所有線性分組碼的所有2n-k個(gè)伴隨式在譯碼過(guò)程中都用來(lái)糾正所有個(gè)伴隨式在譯碼過(guò)程中都用來(lái)糾正所有小于等于小于等于t=(d-1)/2個(gè)隨機(jī)錯(cuò)誤以及部分個(gè)隨機(jī)錯(cuò)誤以及部分大于大于t的錯(cuò)誤圖樣。的錯(cuò)誤圖樣。 限定距離譯碼限定距離譯碼：譯碼時(shí)不能達(dá)到碼的糾：譯碼時(shí)不能達(dá)到碼的糾錯(cuò)能力錯(cuò)能力第三節(jié)第三節(jié) 由已知碼構(gòu)造新碼的方法由已知碼構(gòu)造新碼的方法擴(kuò)展碼擴(kuò)展碼刪余碼刪余碼增廣碼增廣碼(增信刪余碼增信刪余碼)增余刪信碼增余刪信碼延長(zhǎng)碼延長(zhǎng)碼一、擴(kuò)展碼00111HHn+1,k,

15、d 或或n+1,k,d+1增加一個(gè)全校驗(yàn)位增加一個(gè)全校驗(yàn)位二、刪余碼二、刪余碼在原碼基礎(chǔ)上刪去一個(gè)校驗(yàn)元。在原碼基礎(chǔ)上刪去一個(gè)校驗(yàn)元。n-1, k三、增廣碼三、增廣碼 在原碼基礎(chǔ)上，增加一個(gè)信息元，刪去一個(gè)校在原碼基礎(chǔ)上，增加一個(gè)信息元，刪去一個(gè)校驗(yàn)元驗(yàn)元 n,k+1,dGG111ada=mind, n-diaC1CCki2, 2 , 1四、增余刪信碼四、增余刪信碼刪去一個(gè)信息元，增加一個(gè)校驗(yàn)元?jiǎng)h去一個(gè)信息元，增加一個(gè)校驗(yàn)元 若若n,k,d碼的最小漢明距離碼的最小漢明距離d為奇數(shù)，則為奇數(shù)，則挑選所有偶數(shù)重量的碼字，即可構(gòu)成挑選所有偶數(shù)重量的碼字，即可構(gòu)成n,k-1,d+1增余刪信碼增余刪信碼

16、五、延長(zhǎng)碼五、延長(zhǎng)碼對(duì)增廣碼再添加一個(gè)全校驗(yàn)位。對(duì)增廣碼再添加一個(gè)全校驗(yàn)位。n+1,k+111nkR用多個(gè)已知碼構(gòu)造新碼用多個(gè)已知碼構(gòu)造新碼直和直和: n, k1+k2, dmind1, d2笛卡爾積：笛卡爾積：n1+n2, k1+k2, mind1,d2鏈接鏈接: n1+n2, k2, dmind1, d2C1, C1+C2構(gòu)造構(gòu)造: 2n, k1+k2, min2d1,d2直積：直積：n1n2, k1k2, d1d2第四節(jié)第四節(jié) 線性碼的糾錯(cuò)能力線性碼的糾錯(cuò)能力(p79)碼的重量分布碼的重量分布(p73)普洛特金限普洛特金限(P限限)漢明限漢明限V-G限限 State Key Labora

17、tory of Integrated Services Networks 一、碼重量分布一、碼重量分布 碼的性能不僅由碼的最小漢明距離決定，還可碼的性能不僅由碼的最小漢明距離決定，還可由碼的重量分布有關(guān)由碼的重量分布有關(guān) niiinnxAxAxAAxA010馬克威倫馬克威倫(MacWilliams)恒等式恒等式()11( )2(1)()n knxxA xxB0( )niiiA xAx0( )niiiB xB x設(shè)二進(jìn)制設(shè)二進(jìn)制n, k線性分組碼及其線性分組碼及其n, n-k對(duì)偶碼的對(duì)偶碼的重量算子分別是重量算子分別是則它們之間有如下關(guān)系：則它們之間有如下關(guān)系：線性分組碼的不可檢錯(cuò)誤概率線性分組

18、碼的不可檢錯(cuò)誤概率線性碼是同距離分布碼線性碼是同距離分布碼若碼字等概發(fā)送若碼字等概發(fā)送平均不可檢平均不可檢 錯(cuò)誤概率錯(cuò)誤概率211(1)kniniudjieejippA pp1(1)niniudieeipA pp()2(1(1) )nkkudepp譯碼錯(cuò)誤與譯碼失敗概率譯碼錯(cuò)誤與譯碼失敗概率teD譯碼器正確譯碼的概率譯碼器正確譯碼的概率譯碼錯(cuò)誤概率譯碼錯(cuò)誤概率譯碼失敗概率譯碼失敗概率誤碼率誤碼率0(1)tin iwceeinpppi 1(1)nin iweieei tpB pp 1wfwcweppp State Key Laboratory of Integrated Services Networks 普洛特金（普洛特金（P）限）限State Key Laboratory