信道編碼理論

1、1線性分組碼基本概念線性分組碼基本概念碼的生成矩陣與校驗矩陣碼的生成矩陣與校驗矩陣對偶碼，系統(tǒng)碼，縮短碼與漢明碼對偶碼，系統(tǒng)碼，縮短碼與漢明碼標準陣列譯碼標準陣列譯碼2定義定義n, k線性分組碼是線性分組碼是GF(q)上的上的n維線性空間中的一個維線性空間中的一個k維子空間。該子空間在加法運算下構成維子空間。該子空間在加法運算下構成Abelian群，群，所以線性分組碼又稱群碼。若碼字的最小距離為所以線性分組碼又稱群碼。若碼字的最小距離為d，則記為則記為n, k, d碼，碼率碼，碼率R=k / n；或記為；或記為(n, M, d)碼，碼，其中其中M表示可用碼字個數(shù)，此時碼率表示為表示可用碼字個數(shù)

2、，此時碼率表示為R= (logqM) / n2k2n3例子例子簡單重復碼簡單重復碼n, 1, n；簡單奇偶校驗碼簡單奇偶校驗碼n, n-1, 27, 3, 4碼碼 120nccc, 1,2,icc in信息組碼字00000101001110010111011100000000011101010011101110101001110101001111010011110100表表1 7, 3, 4碼字碼表碼字碼表4性質性質 n, k, d碼中碼中d等于非零碼字的最小重量，即等于非零碼字的最小重量，即 GF(2)上上n, k, d碼中，任何兩個碼字碼中，任何兩個碼字C1，C2之間有如下關系：之間有如下

3、關系： w(C1 + C2)=w(C1)+w(C2)-2w(C1 C2) 或或 d(C1, C2) w(C1)+w(C2) 式中，式中， C1 C2是兩個碼字的內積。是兩個碼字的內積。 GF(2)上線性分組碼任上線性分組碼任3個碼字個碼字C1，C2 ，C3之間的漢明距離滿足：之間的漢明距離滿足： d(C1, C3) d(C1, C2) d(C2, C3) 任何任何n, k, d碼，碼字的重量或全部為偶數(shù)，或者奇、偶重量碼，碼字的重量或全部為偶數(shù)，或者奇、偶重量碼字數(shù)相等。碼字數(shù)相等。 , min()iiCn kdw C5編碼問題編碼問題給定參數(shù)給定參數(shù)n、k，如何根據(jù)，如何根據(jù)k個信息比特來確

4、定對應的個信息比特來確定對應的n-k個校驗比特？個校驗比特？利用校驗矩陣或生成矩陣。利用校驗矩陣或生成矩陣。利用生成矩陣利用生成矩陣由于由于n, k, d線性分組碼是一個線性分組碼是一個k維線性空間，因此，必維線性空間，因此，必可找到可找到k個線性無關的矢量，能個線性無關的矢量，能張成張成該線性空間。設該線性空間。設 是是k個線性無關的矢量，則對任意的碼字個線性無關的矢量，則對任意的碼字C，有有G稱為該分組碼的生成矩陣。稱為該分組碼的生成矩陣。12,kC CC11221212 , kkTkkmmmm mmCCCCC CCmG6Remarks 生成矩陣生成矩陣G中的每一行都是一個碼字；中的每一行

5、都是一個碼字； 任意任意k個線性獨立的碼字都可以作為生成矩陣；個線性獨立的碼字都可以作為生成矩陣； 給定一個給定一個n, k, d線性分組碼，其生成矩陣可有多個。線性分組碼，其生成矩陣可有多個。 例子例子 如表1中的7, 3, 4碼，可從8個碼字中任意挑k = 3個線性無關的碼字作為碼的生成矩陣1 0 0 1 1 1 00 1 0 0 1 1 10 0 1 1 1 0 1G1 1 1 0 1 0 00 1 0 0 1 1 10 0 1 1 1 0 1G7從線性方程組的角度描述線性分組碼從線性方程組的角度描述線性分組碼n-k個校驗位可用k個已知的信息位表示出來：個校驗位個信息位knknknkkn

6、nncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 118000100010001021)(,011, 0, 21, 2, 11, 1ccchhhhhhnnnknknnknknnknknknnkn列行，校驗矩陣校驗矩陣的各行之間是線性無關的，即校驗矩陣的行秩為校驗矩陣的各行之間是線性無關的，即校驗矩陣的行秩為n-k。以校驗矩陣的以校驗矩陣的n-k行為基底，可張成一個行為基底，可張成一個n-k維線性子空間。維線性子空間。9

7、例子：表例子：表1的的7, 3, 4碼的碼的4個校驗元可由如下線性個校驗元可由如下線性方程組求得：方程組求得：因此，校驗矩陣為：因此，校驗矩陣為：36542654165406541101111111101011cccccccccccccccc 1011000111010011000100110001H10Remarks校驗矩陣的各行之間是線性無關的，即校驗矩陣的行校驗矩陣的各行之間是線性無關的，即校驗矩陣的行秩為秩為n-k；校驗矩陣的校驗矩陣的n-k行為基底，可張成一個行為基底，可張成一個n-k維線性子空間；維線性子空間；任意一個合法碼字任意一個合法碼字C均滿足均滿足 HCT=0T；交換校驗矩

8、陣的各列并不影響其糾錯能力。交換校驗矩陣的各列并不影響其糾錯能力。校驗矩陣和生成矩陣的關系校驗矩陣和生成矩陣的關系校驗矩陣校驗矩陣H與任意一個碼字之積為零，因此有與任意一個碼字之積為零，因此有校驗矩陣校驗矩陣H中各行張成的子空間的零空間即為生成矩陣中各行張成的子空間的零空間即為生成矩陣G各行張成的子空間。各行張成的子空間。TTTTH CHG m0HG011定理定理: n, k, d線性分組碼最小漢明距離等于線性分組碼最小漢明距離等于d的充的充要條件是：要條件是：H的任意的任意d-1列線性無關。列線性無關。Proof . hint: 必要性：采用反證法；充分性：將H中某些d列線性相關的列的系數(shù)作

9、為碼字中對應的非0分量推論推論: n, k, d線性分組碼的線性分組碼的最大可能的最小漢明最大可能的最小漢明距離為距離為n-k+1。Proof: 由于校驗矩陣H的n-k行是線性無關的，也就是說H的行秩為n-k，從而可推出H的列秩最大是n-k，即H最多有任意n-k列線性無關，由定理得到n-kd-1,有dn-k+1。12對偶碼對偶碼設n, k, d線性分組碼C的生成矩陣為G，校驗矩陣為H，以H作為生成矩陣，G為對應的校驗矩陣，可構造另一個n, n-k, d線性分組碼C1，我們稱C1為C的對偶碼。系統(tǒng)碼系統(tǒng)碼縮短碼縮短碼從n, k, d線性分組碼的所有碼字中，把前面i位全為零的碼字挑選出來構成一個新

10、的子集，該子集即為n, k, d的縮短碼。傳輸時，僅傳輸后面的n-i位碼元，記為n-i, k-i, d碼，其糾錯能力至少與原n, k, d碼相同。kGI PTn k HP I13例子：例子：表表1的的7, 3, 4碼：碼：0000000，0011101，0100111，0111010，1001110，1010011，1101001，11101006, 2, 4縮短碼為：縮短碼為： 000000，011101，100111，111010原碼和縮短碼的生成矩陣分別為：原碼和縮短碼的生成矩陣分別為：去掉去掉G的第一列第一行，就得到縮短碼的生成矩陣的第一列第一行，就得到縮短碼的生成矩陣Gs。10111

11、0111001sG101110011100100111001G14原碼和縮短碼的校驗矩陣分別為：原碼和縮短碼的校驗矩陣分別為：對系統(tǒng)碼而言，去掉對系統(tǒng)碼而言，去掉G的前的前i列和前列和前i行行就可得到縮短碼就可得到縮短碼的生成矩陣的生成矩陣Gs。去掉校驗矩陣的前。去掉校驗矩陣的前i列，可得到縮短碼列，可得到縮短碼的校驗矩陣的校驗矩陣Hs 。1000110010001100101110001101H100011010001001011000110sH15定義碼長：碼長： n=2m-1信息位長度：信息位長度： k=2m-1-m碼率：碼率： R=(n-m) / n最小漢明距離：最小漢明距離：d=3校

12、驗矩陣有校驗矩陣有 m行，行，2m-1列，取互不相同的列，取互不相同的m重構成。重構成。例子：例子： GF(2)上的上的7,4,3漢明碼，漢明碼，8個個3重為重為001, 010, 011, 100, 101, 110, 111, 000校驗矩陣為：校驗矩陣為：000111101100111010101H16伴隨式伴隨式設發(fā)送碼字：設發(fā)送碼字：接收序列：接收序列：根據(jù)錯誤圖樣的概念，根據(jù)錯誤圖樣的概念，R=C+E.S 稱為稱為伴隨式（或校正子），伴隨式（或校正子），是校驗矩陣是校驗矩陣H中某幾列數(shù)中某幾列數(shù)據(jù)的線性組合，因而是據(jù)的線性組合，因而是n-k維向量，有維向量，有2n-k種可能。種可能

13、。錯誤圖樣錯誤圖樣E是是n維向量，共有維向量，共有2n種可能，因而每種可能，因而每2k種錯種錯誤圖樣對應一種伴隨式。誤圖樣對應一種伴隨式。021,rrrnnRTTTEHHECRHS)(120,nncccC17例子例子7,3,4碼的校驗矩陣碼的校驗矩陣H為：為：錯誤圖樣及其相應的伴隨式：錯誤圖樣及其相應的伴隨式：1000110010001100101110001101HE2=(1100000)E3=(0010100)E1=(1000000)S1T=HE1T =(1110)TS2T=HE2T =(1001)TS3T=HE3T =(1001)T18標準陣列步驟標準陣列步驟: 1): 由接收到的序列由

14、接收到的序列R，計算伴隨式，計算伴隨式S=RHT ； 2): 若若S=0，正確接收；若，正確接收；若S不為零，尋找錯誤圖樣；不為零，尋找錯誤圖樣； 3): 由錯誤圖樣解出碼字由錯誤圖樣解出碼字C=R-E。19C1C2kC2CiE2E3knE2C2+E2C2+E3Ci+E3Ci+E222ECk32ECkknkEC22C2+Ci+knE2knE2碼字禁用碼字標準陣列譯碼(陪集首)20標準陣列基本原理標準陣列基本原理:根據(jù)許用碼字將禁用碼字進行分類，分類的依據(jù)是錯根據(jù)許用碼字將禁用碼字進行分類，分類的依據(jù)是錯誤圖樣；誤圖樣；關鍵問題在于如何選擇錯誤圖樣，使錯誤概率盡可能關鍵問題在于如何選擇錯誤圖樣，

15、使錯誤概率盡可能??；??；應首先選擇重量最輕的錯誤圖樣。應首先選擇重量最輕的錯誤圖樣。21發(fā)送端經(jīng)過發(fā)送端經(jīng)過7,3,4碼編碼后的碼字序列，通過有噪信道后，碼編碼后的碼字序列，通過有噪信道后，在接收端觀測到的序列為在接收端觀測到的序列為R=(0001110)。采用標準陣列譯。采用標準陣列譯碼估計估計相應的信息序列。碼估計估計相應的信息序列。 101100011101000 0 0 1 1 1 011000100110001 1 1 1 0TTSRH當當E1=(1000000)時 S1T=HE1T =(1110)T因此，因此，C=R+E1= (1001110).22完備譯碼完備譯碼n, k, d線

16、性分組碼的所有線性分組碼的所有2n-k個伴隨式，在譯碼過程中個伴隨式，在譯碼過程中若都用來糾正所有小于等于若都用來糾正所有小于等于 個隨機錯誤，個隨機錯誤，以及部分大于以及部分大于t的錯誤圖樣，則這種譯碼方法稱為的錯誤圖樣，則這種譯碼方法稱為完備完備譯碼。譯碼。限定距離譯碼限定距離譯碼 任一任一n, k, d碼，能糾正碼，能糾正 個隨機錯誤。如個隨機錯誤。如果在譯碼時，僅糾正果在譯碼時，僅糾正t k/n。和縮短和縮短(Shortened) 碼的構造碼的構造過程相反。過程相反。RM碼碼如果把如果把(2m-1, 2m-1 -m, 3)Hamming碼的對偶碼，即單純碼的對偶碼，即單純碼碼(2m-1

17、, m, 2m-1)進行延長，就得到一個進行延長，就得到一個(2m, m+1, 2m-1)碼，碼，稱之為稱之為一階一階Reed-Muller碼碼，用，用RM(1, m)表示。表示。一般，一般，r階階RM碼碼RM(r, m)是是2m, k, 2m-r，其中，其中其對偶碼為其對偶碼為RM(m-r-1, m)碼。碼。1; 112121mmmmmmknkrmr 33Hadamard變換變換碼長為碼長為2m ，最小距離為，最小距離為d=2m-r的的RM(r, m)碼的生碼的生成矩陣由成矩陣由 中的那些重量大于等于中的那些重量大于等于d的行構成。的行構成。22mmHH21101H4111101010011

18、0001H81111111101010101001100110001000100001111000001010000001100000001H2mH34例子：例子：m=3如果以如果以V0到到V3的的4行作為行作為G矩陣的行，則得到一個矩陣的行，則得到一個RM(1, 3)碼的生成矩陣；碼的生成矩陣；若以若以V0到到V2 V1的的7個矢量作為個矢量作為G矩陣的行，則得到一個矩陣的行，則得到一個RM(2, 3)碼的生成矩陣。碼的生成矩陣。0321323121321(11111111) (00001111)(00110011) (01010101)(00000011) (00000101)(00010

19、001) (00000001)VVVVVVVVV VVV V35改變線性碼參數(shù)改變線性碼參數(shù)n, k, n-k的任意兩個的任意兩個 Shorten: 刪除信息符號刪除信息符號 lengthen: 增加信息符號增加信息符號 Puncture: 刪除校驗符號刪除校驗符號 Expand :增加校驗符號增加校驗符號 Expurgate: 刪除碼字，增加校驗符號刪除碼字，增加校驗符號 Augment: 增加碼字，刪除校驗符號增加碼字，刪除校驗符號 fixed, nkkn fixed, nkkn fixed, knkn fixed, knkn fixed, nknk fixed, nknk 36 漢明碼的

20、各類修正碼之間的關系圖 37碼的性能不僅由碼的碼的性能不僅由碼的最小漢明距離最小漢明距離決定，還與碼決定，還與碼的的重量分布密切相關。重量分布密切相關。定義：定義：設設Ai是是n, k ,d分組碼中重量為分組碼中重量為i的碼字數(shù)目，則集合的碼字數(shù)目，則集合A0, A1, , An稱為該分組碼的稱為該分組碼的重量分布。重量分布。也可以把碼的重量分布寫成如下的多項式形式也可以把碼的重量分布寫成如下的多項式形式: 稱稱A(x)為碼的為碼的重量估值算子重量估值算子，或簡稱，或簡稱重量算子。重量算子。如如 3, 1, 3重復碼的重量分布為重復碼的重量分布為1, 0, 0, 1，重量算子為，重量算子為01

21、0( )nniniiA xAA xA xAx3( )1.A xx 38 定理定理: 設二進制設二進制n， k線性分組碼及其線性分組碼及其 n，n-k對偶碼的重量算子分別是：對偶碼的重量算子分別是： iiniiinixBxBxAxA00)()(則它們之間有如下關系： xxBxxAnkn11)1 (2)()(稱此式為馬克威倫( MacWilliams)恒等式。 39等重碼：等重碼： 除了一個全除了一個全0碼字外，其余碼字的重量都相等。碼字外，其余碼字的重量都相等。 例：漢明碼的對偶碼例：漢明碼的對偶碼2m-1, m, 2m-1.信息組碼字000001010011100101110111000000

22、00011101010011101110101001110101001111010011110100表表1 7, 3, 4碼字碼表碼字碼表40任何一個二進制任何一個二進制n，k，d線性分組碼的碼字集合線性分組碼的碼字集合中，必有一個全中，必有一個全0碼字碼字;如果還有一個全如果還有一個全1碼字的話，則由于線性碼的封閉碼字的話，則由于線性碼的封閉性，該碼的重量分布必是性，該碼的重量分布必是對稱對稱的。的。 例：例：7, 4, 3漢明碼，漢明碼，Ai=1, 0, 0, 7, 7, 0, 0, 1.41根據(jù)不同的譯碼方法和譯碼器，一般譯碼錯誤根據(jù)不同的譯碼方法和譯碼器，一般譯碼錯誤概率分為概率分為不

23、可檢錯誤概率不可檢錯誤概率、譯碼失敗概率譯碼失敗概率和和譯譯碼錯誤概率碼錯誤概率。 42碼字通過碼字通過BSC傳輸時，傳輸時， 若由于干擾變成了另一若由于干擾變成了另一碼字，碼字， 則檢錯譯碼器就不能發(fā)現(xiàn)此種類型的錯則檢錯譯碼器就不能發(fā)現(xiàn)此種類型的錯誤，誤， 產生了產生了不可檢錯誤不可檢錯誤。碼長為碼長為n， 有有M個碼字，個碼字， 最小距離為最小距離為d的的(n， M， d)二進制分組碼的平均不可檢錯誤概率二進制分組碼的平均不可檢錯誤概率:,11(1)Mnin iudjj ieejiPPA pp43Aj, i是與第是與第j個碼字的距離為個碼字的距離為i的碼字數(shù)。的碼字數(shù)。 設設Aj(x)=A

24、j, 0+Aj, 1 x+Aj, 2 x2+Aj, nxn j=1, 2, , M.是是(n, M, d)碼中第碼中第j個碼字的個碼字的距離分布多項式距離分布多項式。若對碼中所有碼字恒有若對碼中所有碼字恒有 Aj(x)=A(x)=A0+A1x+A2x2+Anxn 則此碼稱為則此碼稱為不變距離分布碼不變距離分布碼或或同距離分布碼同距離分布碼。 44對線性碼而言，對線性碼而言， 由于碼的封閉性，由于碼的封閉性， 可知是同可知是同距離分布碼，距離分布碼， 且碼的距離分布就等于碼的重量且碼的距離分布就等于碼的重量分布。分布。 對對n, k, d二進制線性分組碼的不可檢錯誤二進制線性分組碼的不可檢錯誤概

25、率為概率為:ineieinijjudppAPPk)1 (121若碼字等概發(fā)送， 則上式成為 ineieiniudppAP)1 (145定理定理: 二進制二進制n, k線性分組碼集合中，線性分組碼集合中， 碼碼的平均不可檢錯誤概率的平均不可檢錯誤概率:)1 (1 (2)(keknudpP式中， pe是BSC的誤碼率。 通常情況下， 1-(1-pe)k1， 所以 ()2n kudP最佳檢錯碼最佳檢錯碼46如果如果n, k, d碼的譯碼器，碼的譯碼器， 用來糾用來糾t個錯誤，個錯誤， 同時檢測同時檢測e個錯誤，個錯誤， 則稱為則稱為teD譯碼器。譯碼器。 此時要求此時要求dt+e+1， et; 0eD是純檢錯譯碼器，是純檢錯譯碼器， 這時這時ed-1； t0D是純糾錯譯碼器，是純糾錯譯碼器， 此時此時t(d-1)2。 teD譯碼器是一類限定距離譯碼器。譯碼器是一類限定距離譯碼器。 teD譯碼器正確譯碼的碼字概率譯碼器正確譯碼的碼字概率:ineieticppinP)1 (0這里及以后pe均指BSC的誤碼率， 且碼字等概發(fā)送。 47譯碼中，若譯碼中，若teD譯碼器輸出的碼字與發(fā)送的碼譯碼器輸出的碼字與發(fā)送的碼字不相同，則產生了字不相同，則產生了譯碼錯誤譯碼錯誤。 如果譯碼器不能譯出碼字，如果譯碼器不能譯出碼字， 而僅指出