Lecture5

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

稱為全校驗(yàn)位若d為偶數(shù)，[n,k,d]碼變成了[n+1,k,d]若d為奇數(shù)，[n,k,d]碼變成了[n+1,k,d+1]校驗(yàn)矩陣5擴(kuò)展(Expanded)碼校驗(yàn)矩陣6擴(kuò)展(Expanded)碼例子：[7,4,3]Hamming碼的校驗(yàn)矩陣增加一個全校驗(yàn)位后得到的[8,4,4]擴(kuò)展Hamming碼的校驗(yàn)矩陣7刪余(Punctured)碼基本原理：在原碼基礎(chǔ)上刪去一個校驗(yàn)元，得到[n-1,k]碼。是擴(kuò)展碼的逆過程在軟判決譯碼和糾錯糾刪碼中，將刪去的符號看作不可靠符號最小漢明距離可能比原碼小1，也可能不變例如把上例中的[8,4,4]碼的最后一個校驗(yàn)位后，便得到了[7,4,3]Hamming碼。此時刪余碼的校驗(yàn)矩陣可直接從原碼的校驗(yàn)矩陣上刪去第1行和最后1列得到一般的，若刪掉的校驗(yàn)位只參與了其中一個校驗(yàn)方程，則在原碼校驗(yàn)矩陣中刪掉上述校驗(yàn)位對應(yīng)的行和列，即可得到新碼的校驗(yàn)矩陣8增廣(Augmented)碼基本原理在原碼基礎(chǔ)上，增加一個信息元，刪去一個校驗(yàn)元得到[n,k+1,da]碼基本實(shí)現(xiàn)方法在原碼生成矩陣G的基礎(chǔ)上，再選擇一個與G中各行都不相關(guān)的n維向量，得到新矩陣Ga，該矩陣有n列，k+1行，即得到一個[n,k+1,da]碼若原碼中沒有全1碼，可在其G矩陣上增加一組全為1的行，得到增廣碼的生成矩陣為：且da=min{d,n-dmax(C)}9增廣(Augmented)碼生成矩陣最小Hamming重量10增余刪信(Expurgated)碼基本原理在原碼基礎(chǔ)上刪去一個信息元，增加一個校驗(yàn)元。和增廣碼構(gòu)造過程相反基本實(shí)現(xiàn)方法刪掉原碼生成矩陣G中的一行，得到新矩陣Ge，該矩陣有n列，k-1行，即得到一個[n,k-1,de]碼若[n,k,d]碼的最小漢明距離d為奇數(shù)，則挑選所有偶數(shù)重量的碼字，即可構(gòu)成[n,k-1,d+1]增余刪信碼[Recall:任何[n,k,d]線性分組碼，碼字的重量或全部為偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)等于偶數(shù)重量的碼字?jǐn)?shù)]11延長(Lengthened)碼與RM碼延長碼對增廣碼再填加一個全校驗(yàn)位得到[n+1,k+1]碼，此時碼率R=(k+1)/(n+1)>k/n。和縮短(Shortened)碼的構(gòu)造過程相反RM碼如果把(2m-1,2m-1-m,3)Hamming碼的對偶碼，即單純碼(2m-1,m,2m-1)進(jìn)行延長，就得到一個(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的行構(gòu)成13RM碼例子：m=3如果以V0到V3的4行作為G矩陣的行，則得到一個RM(1,3)碼的生成矩陣若以V0到V2V1的7個矢量作為G矩陣的行，則得到一個RM(2,3)碼的生成矩陣14修正的線性碼改變線性碼參數(shù)n,k,n-k的任意兩個縮短碼Shorten:刪除信息符號延長碼lengthen:增加信息符號刪余碼Puncture:刪除校驗(yàn)符號擴(kuò)展碼Expand:增加校驗(yàn)符號增余刪信碼Expurgate:刪除碼字，增加校驗(yàn)符號增廣碼Augment:增加碼字，刪除校驗(yàn)符號修正的線性碼[7,3,4]漢明碼的各類修正碼之間的關(guān)系1516線性碼的重量分布碼的性能不僅由碼的最小漢明距離決定，還可由碼的重量分布有關(guān)定義設(shè)Ai是[n,k,d]分組碼中重量為i的碼字?jǐn)?shù)目，則集合{A1,A2,…,An}稱為該分組碼的重量分布也可以把碼的重量分布寫成如下的多項(xiàng)式形式稱A(x)為碼的重量估值算子，或簡稱重量算子如[3,1,3]重復(fù)碼的重量分布為{1,0,0,1}，重量算子為17線性碼的糾錯能力Singletonbound

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

即

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

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

19線性碼的糾錯能力Hammingbound

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