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

Lecture5

線性分組碼(II)2內(nèi)容修正的線性碼擴(kuò)展碼，刪余碼增廣碼，增余刪信碼延長(zhǎng)碼，Reed-Muller碼線性碼的重量分布線性碼的糾錯(cuò)能力SingletonboundHamming(spherepacking)boundVarshamov-GilbertboundMcEliece-Rodemich-Rumsey-Welchupperbound3修正的線性碼糾錯(cuò)碼的設(shè)計(jì)碼長(zhǎng)通常由矩陣或多項(xiàng)式的代數(shù)和組合特性決定線性分組碼的設(shè)計(jì)碼長(zhǎng)通常不等于理想碼長(zhǎng)例如：二進(jìn)制Hamming碼的設(shè)計(jì)碼長(zhǎng)為2m-1(7,15,31,…)修正方法線性分組碼三個(gè)參數(shù)(n,k,n-k):增大一個(gè)參數(shù)，降低另一個(gè)參數(shù)，保持第三個(gè)參數(shù)不變。共有6種方法4擴(kuò)展(Expanded)碼基本原理：對(duì)[n,k,d]線性分組碼中的每一個(gè)碼字，增加一個(gè)校驗(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)矩陣增加一個(gè)全校驗(yàn)位后得到的[8,4,4]擴(kuò)展Hamming碼的校驗(yàn)矩陣7刪余(Punctured)碼基本原理：在原碼基礎(chǔ)上刪去一個(gè)校驗(yàn)元，得到[n-1,k]碼。是擴(kuò)展碼的逆過(guò)程在軟判決譯碼和糾錯(cuò)糾刪碼中，將刪去的符號(hào)看作不可靠符號(hào)最小漢明距離可能比原碼小1，也可能不變例如把上例中的[8,4,4]碼的最后一個(gè)校驗(yàn)位后，便得到了[7,4,3]Hamming碼。此時(shí)刪余碼的校驗(yàn)矩陣可直接從原碼的校驗(yàn)矩陣上刪去第1行和最后1列得到一般的，若刪掉的校驗(yàn)位只參與了其中一個(gè)校驗(yàn)方程，則在原碼校驗(yàn)矩陣中刪掉上述校驗(yàn)位對(duì)應(yīng)的行和列，即可得到新碼的校驗(yàn)矩陣8增廣(Augmented)碼基本原理在原碼基礎(chǔ)上，增加一個(gè)信息元，刪去一個(gè)校驗(yàn)元得到[n,k+1,da]碼基本實(shí)現(xiàn)方法在原碼生成矩陣G的基礎(chǔ)上，再選擇一個(gè)與G中各行都不相關(guān)的n維向量，得到新矩陣Ga，該矩陣有n列，k+1行，即得到一個(gè)[n,k+1,da]碼若原碼中沒(méi)有全1碼，可在其G矩陣上增加一組全為1的行，得到增廣碼的生成矩陣為：且da=min{d,n-dmax(C)}9增廣(Augmented)碼生成矩陣最小Hamming重量10增余刪信(Expurgated)碼基本原理在原碼基礎(chǔ)上刪去一個(gè)信息元，增加一個(gè)校驗(yàn)元。和增廣碼構(gòu)造過(guò)程相反基本實(shí)現(xiàn)方法刪掉原碼生成矩陣G中的一行，得到新矩陣Ge，該矩陣有n列，k-1行，即得到一個(gè)[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延長(zhǎng)(Lengthened)碼與RM碼延長(zhǎng)碼對(duì)增廣碼再填加一個(gè)全校驗(yàn)位得到[n+1,k+1]碼，此時(shí)碼率R=(k+1)/(n+1)>k/n。和縮短(Shortened)碼的構(gòu)造過(guò)程相反RM碼如果把(2m-1,2m-1-m,3)Hamming碼的對(duì)偶碼，即單純碼(2m-1,m,2m-1)進(jìn)行延長(zhǎng)，就得到一個(gè)(2m,m+1,2m-1)碼，稱之為一階Reed-Muller碼，用RM(1,m)表示。一般，r階RM碼RM(r,m)是[2m,k,2m-r]，其中其對(duì)偶碼為RM(m-r-1,m)碼12RM碼Hadamard變換碼長(zhǎng)為2m

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

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

即

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

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

19線性碼的糾錯(cuò)能力Hammingbound

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