第三章線性分組碼

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

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

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

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

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

6、利用校驗矩陣利用校驗矩陣利用生成矩陣利用生成矩陣給定參數(shù)給定參數(shù)n、k和和dState Key Laboratory of Integrated Services Networks 三、碼的生成矩陣三、碼的生成矩陣(P56)從線性空間的角度描述分組碼從線性空間的角度描述分組碼由于由于n,k,d線性分組碼是一個線性分組碼是一個k維線性空間維線性空間因此，必可找到因此，必可找到k個線性無關的矢量，能張成該線性空間個線性無關的矢量，能張成該線性空間kCCC,21是是k個線性無關的矢量，則對任意個線性無關的矢量，則對任意C，可有：，可有：kkmmmCCCC2211mGCCCkkmmm2121,G稱為該

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

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

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

10、式伴隨式漢明碼漢明碼標準陣列標準陣列State Key Laboratory of Integrated Services Networks 一、伴隨式一、伴隨式(P59)設發(fā)送碼字設發(fā)送碼字021,cccnnC接收序列接收序列021,rrrnnR根據(jù)錯誤圖樣的概念，根據(jù)錯誤圖樣的概念，R=C+ETTTEHHECRHS)(S是校驗矩陣是校驗矩陣H中某幾列數(shù)據(jù)的線性組合中某幾列數(shù)據(jù)的線性組合兩個定理兩個定理定理定理1：n,k,d線性分組碼有最小漢明距離線性分組碼有最小漢明距離d的充要條件是，的充要條件是，H矩陣中任意矩陣中任意d-1列線性無關列線性無關定理定理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，則此碼為極大最，則此碼為極大最小距離可分碼，簡稱小距離可分碼，簡稱MDS碼碼State Key Laboratory of Integrated Services Networks 二、漢明碼二、漢明碼參數(shù)參數(shù) 碼長：碼長： n=2m-1 信息位長度：信息位長度：k=2m-1-m 最小漢明距離：最小漢明距離：d=3 校驗矩陣有校驗矩陣有

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

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

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

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

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

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

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