Lecture4

線性分組碼(I)2內(nèi)容基本概念生成矩陣與校驗矩陣對偶碼、系統(tǒng)碼、縮短碼漢明碼、極長碼伴隨式與標(biāo)準(zhǔn)陣列譯碼3基本概念線性分組碼：

一個[n,k]線性分組碼,是把信息劃成k個碼元為一段(稱為信息組),通過編碼器變成長為n個碼元的一組，作為[n,k]線性分組碼的一個碼字。若每位碼元的取值有q種(q為素數(shù)冪),則共有qk個碼字。n長的數(shù)組共有qn組，在二進(jìn)制情況下，有2n個數(shù)組。顯然，qn個n維數(shù)組(n重)組成一個GF(q)上的n維線性空間。如果qk(或2k)個碼字集合構(gòu)成了一個k維線性子空間，則稱它是一個[n,k]線性分組碼。4線性分組碼[n,k]線性分組碼是GF(q)上的n維線性空間Vn中的一個k維子空間Vn,k。由于該線性子空間在加法運(yùn)算下構(gòu)成阿貝爾群，所以線性分組碼又稱為群碼。通常用[n,k,d]或[n,k]，而[n,M,d]表示碼字?jǐn)?shù)目為M的任何碼，此時碼率R=n-1logqM。5線性分組碼簡單重復(fù)碼[n,1,n]；簡單奇偶校驗碼[n,n-1,2][7,3,4]碼(漢明碼的對偶碼)

信息組碼字00000101001110010111011100000000011101010011101110101001110101001111010011110100表1[7,3,4]碼字碼表6線性分組碼的性質(zhì)

[n,k,d]線性分組碼的最小距離等于非零碼字的最小重量。GF(2)上[n,k,d]線性分組碼中，任何兩個碼字C1，C2之間有如下關(guān)系：

w(C1

+C2)=w(C1)+w(C2)-2w(C1·C2)

或

d(C1,C2)≤w(C1)+w(C2)其中C1·C2

是兩個碼字的內(nèi)積。7線性分組碼的性質(zhì)GF(2)上線性分組碼任3個碼字C1，C2，C3之間的漢明距離，滿足以下三角不等式d(C1,C3)≤d(C1,C2)＋d(C2,C3)任何[n,k,d]線性分組碼，碼字的重量或全部為偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)等于偶數(shù)重量的碼字?jǐn)?shù)。8碼的生成矩陣編碼問題給定參數(shù)n、k，如何根據(jù)k個信息比特來確定n-k個校驗比特？利用校驗矩陣或生成矩陣?yán)蒙删仃囉捎赱n,k,d]線性分組碼是一個k維線性空間，因此，必可找到k個線性無關(guān)的矢量，能張成該線性空間。設(shè)C1，C2,…,Ck是k個線性無關(guān)的矢量，則對任意的碼字C，有稱為該分組碼的生成矩陣9碼的生成矩陣Remarks生成矩陣G中的每一行都是一個碼字任意k個線性獨立的碼字都可以作為生成矩陣給定一個[n,k,d]線性分組碼，其生成矩陣可有多個

表1中的[7,3,4]碼，可從8個碼字中任意挑k=3個線性無關(guān)的碼字作為碼的生成矩陣10碼的校驗矩陣從線性方程組的角度描述線性分組碼n-k個校驗位可用k個已知的信息位表示出來11碼的校驗矩陣校驗矩陣的各行之間是線性無關(guān)的，即校驗矩陣的行秩為n-k以校驗矩陣的n-k行為基底，可張成一個n-k維線性子空間12碼的校驗矩陣?yán)樱罕?的[7,3,4]碼(P5)的4個校驗元可由如下線性方程組求得因此，校驗矩陣為13碼的校驗矩陣Remarks校驗矩陣的各行之間是線性無關(guān)的，即校驗矩陣的行秩為n-k校驗矩陣的n-k行為基底，可張成一個n-k維線性子空間任意一個合法碼字C均滿足HCT=0T交換校驗矩陣的各列并不影響其糾錯能力校驗矩陣和生成矩陣的關(guān)系校驗矩陣H與任意一個碼字之積為零，因此有校驗矩陣H中各行張成的子空間的零空間即為生成矩陣G各行張成的子空間。14最小漢明距離定理:[n,k,d]線性分組碼最小漢明距離等于d的充要條件是：H的任意d-1列線性無關(guān)Proof.[hint:必要性：采用反證法；充分性：將H中某些d列線性相關(guān)的列的系數(shù)作為碼字中對應(yīng)的非0分量]推論:[n,k,d]線性分組碼的最大可能的最小漢明距離為n-k+1Proof:由于校驗矩陣H的n-k行是線性無關(guān)的，也就是說H的行秩為n-k，從而可推出H的列秩最大是n-k，即H最多有任意n-k列線性無關(guān)，由定理得到n-k≥d-1,有d≤n-k+115對偶碼對偶碼：設(shè)[n,k,d]線性分組碼C的生成矩陣為G，校驗矩陣為H,以H作為生成矩陣,G為對應(yīng)的校驗矩陣,可構(gòu)造另一個[n,n-k,d]線性分組碼C1,我們稱C1為C的對偶碼。

[7,3,4]碼的對偶碼必是[7,4,3]碼，其生成矩陣G[7,4]就是[7,3,4]碼的校驗矩陣H[7,3]。16系統(tǒng)碼系統(tǒng)碼：若信息組以不變的形式在碼組的任意k位（通常在最前面:cn-1,cn-2,…,cn-k）中出現(xiàn)的碼稱為系統(tǒng)碼，否則為非系統(tǒng)碼。

G=[IkP](前k位為信息位，后n-k位為校驗位)

H=[-PTIn-k]（-PT是P矩陣的轉(zhuǎn)置）系統(tǒng)碼的特點：系統(tǒng)碼的編碼相對而言比較簡單，且由G可以方便的得到H（反之亦然），容易檢查編出的碼字是否正確。同時，對分組碼而言，系統(tǒng)碼與非系統(tǒng)碼的糾錯能力完全等價。

17縮短碼縮短碼:在[n,k,d]碼的碼字集合中，挑選前i個信息位數(shù)字均為0的所有碼字，組成一個新的子集。由于該子集的前i位信息位均取0，故傳輸時可以不送它們，僅只要傳送后面的n-i位碼元即可。這樣該子集組成了一個[n-i,k-i,d]分組碼，稱它為[n,k,d]碼的縮短碼?？s短碼的特點：由于縮短碼是k維子空間Vn,k中取前i位均為0的碼字組成的一個子集，顯然該子集是Vn,k空間中的一個k-i維的子空間Vn,k-i，因此[n-i,k-i,d]縮短碼的糾錯能力至少與原[n,k,d]碼相同。18縮短碼表1的[7,3,4]碼：0000000，0011101，0100111，0111010，1001110，1010011，1101001，1110100[6,2,4]縮短碼為：000000，011101，100111，111010原碼和縮短碼的生成矩陣分別為去掉G的第一列第一行，就得到縮短碼的生成矩陣Gs19縮短碼原碼和縮短碼的校驗矩陣分別為對系統(tǒng)碼而言，去掉G的前i列和前i行就可得到縮短碼的生成矩陣Gs。去掉校驗矩陣的前i列，可得到縮短碼的校驗矩陣Hs。20漢明碼

要糾正一個錯誤的[n,k,d]分組碼，要求其H矩陣中至少兩列線性無關(guān)，且不能全為0。若為二進(jìn)制碼，則要求H矩陣中每列互不相同，且不能全為0。一個[n,k,d]分組碼有n-k位檢驗元，在二進(jìn)制碼情況下，這n-k個校驗元能組成2n-k列不同的n-k重，其中有2n-k-1列不全為0。所以用這2n-k-1列作為H矩陣的每一列，則由此H就產(chǎn)生了一個糾正單個錯誤的[n,k,3]碼，它就是漢明碼。21漢明碼

GF(2)上漢明碼的H矩陣的列，是由不全為0，且互不相同的二進(jìn)制m重組成。該碼有如下參數(shù)：n=2m-1，k=2m-1-m，R=(2m-1-m)/(2m-1)，d=3。

構(gòu)造GF(2)上的[7,4,3]漢明碼，這時取m=3，所有23=8個三重為：001,010,011,100,101,110,111,000。挑出其中7個非0的三重構(gòu)成校驗矩陣為：22漢明碼

可以把GF(2)上的漢明推廣到GF(q)上，得到多進(jìn)制漢明碼，此時碼有如下參數(shù)：碼長：n=(qm-1)/(q-1)信息位：k=n-m碼率：R=(n-m)/n最小距離：d=3二進(jìn)制[2m-1，2m-1-m，3]漢明碼的對偶碼是一個[2m-1，m，2m-1]碼，也稱為單純碼或極長碼。

23伴隨式伴隨式設(shè)發(fā)送碼字接收序列根據(jù)錯誤圖樣的概念，R=C+ES是校驗矩陣H中某幾列數(shù)據(jù)的線性組合，因而是n-k維向量，有2n-k種可能錯誤圖樣E是n維向量，共有2n種可能，因而每2k種錯誤圖樣對應(yīng)一種伴隨式。24伴隨式式中，hn-i為H矩陣的第i列，它是一個n-k重列矢量。表示第i1，i2,...,it

位有錯。25伴隨式

S是H矩陣中相應(yīng)于eij

≠0（j=1,2，…，t）的那幾列hn-ij的線性組合，由于hn-ij是n-k重列矢量，故S也是一個n-k重的矢量（s1，s2，…，sn-k)。若沒有錯誤，所有si=0,則S是一個零矢量。26伴隨式[7,3,4]碼的校驗矩陣H為錯誤圖樣及其相應(yīng)的伴隨式E2=(1100000)E3=(0010100)E1=(1000000)S1T=HE1T=(1110)TS2T=HE2T=(1001)TS3T=HE3T=(1001)T27重要的結(jié)論一個[n,k,d]線性分組碼，若要糾正≤t個錯誤，則其充要條件是H矩陣中任何2t列線性無關(guān)。由于d=2t+1，所以也相當(dāng)于要求H矩陣中d-1列線性無關(guān)。[n,k,d]線性分組碼有最小距離等于d的充要條件是，H矩陣中任意d-1列線性無關(guān)。(singleton限)[n,k,d]線性分組碼的最大可能的最小距離等于n-k+1，即d≤n-k+1。MDS碼：若系統(tǒng)碼的最小距離d=n-k+1,則稱此碼為極大最小距離可分碼，簡稱MDS碼。28標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列步驟1):

由接收到的序列R，計算伴隨式S=RHT；2):若S=0，正確接收；若S不為零，尋找錯誤圖樣；3):由錯誤圖樣解出碼字C=R-E。標(biāo)準(zhǔn)陣列基本原理根據(jù)許用碼字將禁用碼字進(jìn)行分類，分類的依據(jù)是錯誤圖樣。關(guān)鍵問題在于如何選擇錯誤圖樣，使錯誤概率盡可能小應(yīng)首先選擇重量最輕的錯誤圖樣,這樣的安排使得每一列中的元素與列首的碼字間距離最小，稱為最小距離譯碼，在BSC下，等效與最大似然譯碼。29標(biāo)準(zhǔn)陣列譯碼C1C2…Ci……………………E2E3C2+E2C2+E3Ci+E3Ci+E2C2+Ci+碼字禁用碼字標(biāo)準(zhǔn)陣列譯碼(陪集首)30標(biāo)準(zhǔn)陣列譯碼發(fā)送端經(jīng)過[7,3,4]碼編碼后的碼字序列，通過有噪信道后，在接收端觀測到的序列為R=(0001110)。采用標(biāo)準(zhǔn)陣列譯碼估計估計相應(yīng)的信息序列。

當(dāng)E1=(1000000)時S1T=HE1T=(1110)T因此，C=R+E1=(1001110)31標(biāo)準(zhǔn)陣列譯碼碼字000000（陪集首）100110010011001111110101101001011100111010禁用碼組1000000001101100111011110101010010011111000110100100001101100000110111111001011110010011001010100010001011100110110001111111011000010101001100100001001000100101