糾錯碼Lecture5-線性分組碼(II)

Lecture5

線性分組碼(II)2內容修正的線性碼擴展碼，刪余碼增廣碼，增余刪信碼延長碼，Reed-Muller碼線性碼的重量分布線性碼的糾錯能力SingletonboundHamming(spherepacking)boundVarshamov-GilbertboundMcEliece-Rodemich-Rumsey-Welchupperbound3修正的線性碼糾錯碼的設計碼長通常由矩陣或多項式的代數和組合特性決定線性分組碼的設計碼長通常不等于理想碼長例如：二進制Hamming碼的設計碼長為2m-1(7,15,31,…)修正方法線性分組碼三個參數(n,k,n-k):增大一個參數，降低另一個參數，保持第三個參數不變。共有6種方法4擴展(Expanded)碼基本原理：對[n,k,d]線性分組碼中的每一個碼字，增加一個校驗元，滿足：

稱為全校驗位若d為偶數，[n,k,d]碼變成了[n+1,k,d]若d為奇數，[n,k,d]碼變成了[n+1,k,d+1]校驗矩陣5擴展(Expanded)碼校驗矩陣6擴展(Expanded)碼例子：[7,4,3]Hamming碼的校驗矩陣增加一個全校驗位后得到的[8,4,4]擴展Hamming碼的校驗矩陣7刪余(Punctured)碼基本原理：在原碼基礎上刪去一個校驗元，得到[n-1,k]碼。是擴展碼的逆過程在軟判決譯碼和糾錯糾刪碼中，將刪去的符號看作不可靠符號最小漢明距離可能比原碼小1，也可能不變例如把上例中的[8,4,4]碼的最后一個校驗位后，便得到了[7,4,3]Hamming碼。此時刪余碼的校驗矩陣可直接從原碼的校驗矩陣上刪去第1行和最后1列得到一般的，若刪掉的校驗位只參與了其中一個校驗方程，則在原碼校驗矩陣中刪掉上述校驗位對應的行和列，即可得到新碼的校驗矩陣8增廣(Augmented)碼基本原理在原碼基礎上，增加一個信息元，刪去一個校驗元得到[n,k+1,da]碼基本實現(xiàn)方法在原碼生成矩陣G的基礎上，再選擇一個與G中各行都不相關的n維向量，得到新矩陣Ga，該矩陣有n列，k+1行，即得到一個[n,k+1,da]碼若原碼中沒有全1碼，可在其G矩陣上增加一組全為1的行，得到增廣碼的生成矩陣為：且da=min{d,n-dmax(C)}9增廣(Augmented)碼生成矩陣最小Hamming重量10增余刪信(Expurgated)碼基本原理在原碼基礎上刪去一個信息元，增加一個校驗元。和增廣碼構造過程相反基本實現(xiàn)方法刪掉原碼生成矩陣G中的一行，得到新矩陣Ge，該矩陣有n列，k-1行，即得到一個[n,k-1,de]碼若[n,k,d]碼的最小漢明距離d為奇數，則挑選所有偶數重量的碼字，即可構成[n,k-1,d+1]增余刪信碼[Recall:任何[n,k,d]線性分組碼，碼字的重量或全部為偶數，或者奇數重量的碼字數等于偶數重量的碼字數]11延長(Lengthened)碼與RM碼延長碼對增廣碼再填加一個全校驗位得到[n+1,k+1]碼，此時碼率R=(k+1)/(n+1)>k/n。和縮短(Shortened)碼的構造過程相反RM碼如果把(2m-1,2m-1-m,3)Hamming碼的對偶碼，即單純碼(2m-1,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)碼12RM碼Hadamard變換碼長為2m

，最小距離為d=2m-r的RM(r,m)碼的生成矩陣由中的那些重量大于等于d的行構成13RM碼例子：m=3如果以V0到V3的4行作為G矩陣的行，則得到一個RM(1,3)碼的生成矩陣若以V0到V2V1的7個矢量作為G矩陣的行，則得到一個RM(2,3)碼的生成矩陣14修正的線性碼改變線性碼參數n,k,n-k的任意兩個縮短碼Shorten:刪除信息符號延長碼lengthen:增加信息符號刪余碼Puncture:刪除校驗符號擴展碼Expand:增加校驗符號增余刪信碼Expurgate:刪除碼字，增加校驗符號增廣碼Augment:增加碼字，刪除校驗符號修正的線性碼[7,3,4]漢明碼的各類修正碼之間的關系1516線性碼的重量分布碼的性能不僅由碼的最小漢明距離決定，還可由碼的重量分布有關定義設Ai是[n,k,d]分組碼中重量為i的碼字數目，則集合{A1,A2,…,An}稱為該分組碼的重量分布也可以把碼的重量分布寫成如下的多項式形式稱A(x)為碼的重量估值算子，或簡稱重量算子如[3,1,3]重復碼的重量分布為{1,0,0,1}，重量算子為17線性碼的糾錯能力Singletonbound

[n,k,d]線性分組碼的最大可能的最小距離等于n-k+1，

即

若系統(tǒng)碼的最小距離滿足d=n-k+1,稱這類碼為極大最小距離可分碼，簡稱MDS碼。構造MDS碼是編碼理論中的一個重要課題。18線性碼的糾錯能力Plotkinbound

GF(q)上的(n,M,d)分組碼的最小距離d滿足

19線性碼的糾錯能力Hammingbound

長為n糾正t個錯誤的q進制分組碼的碼字數M滿足20線性碼的糾錯能力Varshamov-Gilbertbound若碼的校驗元數目n-k滿足的最小整數，則一定可以構造出一個長為n，最小距離為d的[n,k]線性分組碼。21線性碼的糾錯能力Plokin限和Hamming限都是必要條件，也就是說任何線性或非線性碼都是必需滿足的，否則碼就構造不出。越接近這個限越有效，等于時碼達到最佳。V－G限是充分條件，并限定于線性碼，滿足這一條件必存在一個最小距離為d的[n,k]線性碼。線性碼的糾錯能力當n→∞時，比較3個限所表示的n、R、d之間的關系（只限于二進制碼）當n→∞時由P限可推出由漢明限可