1、信道編碼理論信道編碼理論 邢莉娟，李卓，西安電子科技大學(xué)邢莉娟，李卓，西安電子科技大學(xué)Lecture 4Lecture 4 信道編碼理論信道編碼理論 2基本概念基本概念生成矩陣與校驗矩陣生成矩陣與校驗矩陣對偶碼、系統(tǒng)碼、縮短碼對偶碼、系統(tǒng)碼、縮短碼漢明碼、極長碼漢明碼、極長碼伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式與標(biāo)準(zhǔn)陣列譯碼Lecture 4Lecture 4 信道編碼理論信道編碼理論 3線性分組碼線性分組碼 ： 一個一個 n, k 線性分組碼線性分組碼 , 是把信息劃成是把信息劃成 k 個碼元為一段個碼元為一段(稱為信息組稱為信息組),通過編碼器變成長為通過編碼器變成長為 n 個碼元的一組，作為個碼元

2、的一組，作為n, k 線性分組碼的一個碼字。若每位碼元的取值有線性分組碼的一個碼字。若每位碼元的取值有 q 種種( q 為素數(shù)冪為素數(shù)冪) , 則共有則共有 qk 個碼字。個碼字。n 長的數(shù)組共有長的數(shù)組共有 qn 組，組，在二進(jìn)制情況下，有在二進(jìn)制情況下，有 2n 個數(shù)組。個數(shù)組。 顯然，顯然，qn 個個 n 維數(shù)組維數(shù)組( n重重)組成一個組成一個GF(q)上的上的 n 維線維線性空間。如果性空間。如果 qk (或或 2k)個碼字集合構(gòu)成了一個個碼字集合構(gòu)成了一個 k 維線性子維線性子空間，則稱它是一個空間，則稱它是一個 n, k 線性分組碼。線性分組碼。Lecture 4Lecture

3、4 信道編碼理論信道編碼理論 4n, k線性分組碼是線性分組碼是 GF(q)上的上的 n維線性空間維線性空間 Vn 中中的一個的一個 k 維子空間維子空間 Vn,k。由于該線性子空間在加法運(yùn)算下構(gòu)成阿貝爾群，由于該線性子空間在加法運(yùn)算下構(gòu)成阿貝爾群，所以線性分組碼又稱為群碼。所以線性分組碼又稱為群碼。通常用通常用 n, k, d 或或 n, k，而，而 n, M, d 表示碼字?jǐn)?shù)表示碼字?jǐn)?shù)目為目為 M 的任何碼，此時碼率的任何碼，此時碼率 R=n-1logqM。Lecture 4Lecture 4 信道編碼理論信道編碼理論 5u 簡單重復(fù)碼n, 1, n；u 簡單奇偶校驗碼n, n-1, 2u

4、 7, 3, 4碼(漢明碼的對偶碼) 120nccc, 1,2,icc in信息組信息組碼字碼字00000101001110010111011100000000011101010011101110101001110101001111010011110100表表1 7, 3, 4碼字碼表碼字碼表Lecture 4Lecture 4 信道編碼理論信道編碼理論 6 n, k, d 線性分組碼的最小距離等線性分組碼的最小距離等于非零碼字的最小重量。GF(2)上上n, k, d線性分組碼中，任何兩個碼字線性分組碼中，任何兩個碼字C1，C2之間有如下關(guān)系：之間有如下關(guān)系： w(C1 + C2)=w(C1)

5、+w(C2)-2w(C1 C2) 或 d(C1, C2) w(C1)+w(C2)其中其中 C1 C2 是兩個碼字的內(nèi)積。是兩個碼字的內(nèi)積。 , min()iiCn kdw CLecture 4Lecture 4 信道編碼理論信道編碼理論 7GF(2)上線性分組碼任上線性分組碼任 3 個碼字個碼字C1，C2 ，C3 之間之間的漢明距離，滿足以下三角不等式的漢明距離，滿足以下三角不等式 d(C1, C3) d(C1, C2) d(C2, C3) 任何任何 n, k, d 線性分組碼，碼字的重量或全部為線性分組碼，碼字的重量或全部為偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)等于偶數(shù)重量的碼偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)

6、等于偶數(shù)重量的碼字?jǐn)?shù)。字?jǐn)?shù)。Lecture 4Lecture 4 信道編碼理論信道編碼理論 8編碼問題編碼問題 給定參數(shù)n、k，如何根據(jù)k個信息比特來確定n-k個校驗比特？ 利用校驗矩陣或生成矩陣?yán)蒙删仃嚴(yán)蒙删仃?由于n, k, d線性分組碼是一個k維線性空間，因此，必可找到k個線性無關(guān)的矢量，能張成該線性空間。設(shè) C1，C2 ,Ck是k個線性無關(guān)的矢量，則對任意的碼字C，有11221212 , kkTkkmmmm mmCCCCC CCmG稱為該分組碼的生成矩陣稱為該分組碼的生成矩陣GLecture 4Lecture 4 信道編碼理論信道編碼理論 9Remarks 生成矩陣G中的每一行

7、都是一個碼字 任意k個線性獨(dú)立的碼字都可以作為生成矩陣 給定一個n, k, d線性分組碼，其生成矩陣可有多個 表表 1 中的中的7, 3, 4碼，可從碼，可從8個碼字中任意挑個碼字中任意挑 k = 3個線個線性無關(guān)的碼字作為碼的生成矩陣性無關(guān)的碼字作為碼的生成矩陣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 1GLecture 4Lecture 4 信道編碼理論信道編碼理論 10從線性方程組的角度描述線性分組碼從線性方程組的角度描述線性分組碼n-k個校驗位可用k個已知的信息位表示出來個

8、校驗位個信息位knknknkknnncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 11Lecture 4Lecture 4 信道編碼理論信道編碼理論 11000100010001021)(,011, 0, 21, 2, 11, 1ccchhhhhhnnnknknnknknnknknknnkn列行，校驗矩陣校驗矩陣的各行之間是線性無關(guān)的，即校驗矩陣的行秩為校驗矩陣的各行之間是線性無關(guān)的，即校驗矩陣的行秩為n-k以校驗矩陣

9、的以校驗矩陣的n-k行為基底，可張成一個行為基底，可張成一個n-k維線性子空間維線性子空間Lecture 4Lecture 4 信道編碼理論信道編碼理論 12例子：表例子：表1的的7, 3, 4碼碼(P5)的的4個校驗元可由如下個校驗元可由如下線性方程組求得線性方程組求得因此，校驗矩陣為因此，校驗矩陣為36542654165406541101111111001011cccccccccccccccc 1011000111010011000100110001HLecture 4Lecture 4 信道編碼理論信道編碼理論 13Remarks校驗矩陣的各行之間是線性無關(guān)的，即校驗矩陣的行秩為n-k校

10、驗矩陣的n-k行為基底，可張成一個n-k維線性子空間任意一個合法碼字C均滿足 HCT=0T交換校驗矩陣的各列并不影響其糾錯能力校驗矩陣和生成矩陣的關(guān)系校驗矩陣和生成矩陣的關(guān)系校驗矩陣H與任意一個碼字之積為零，因此有校驗矩陣H中各行張成的子空間的零空間即為生成矩陣G各行張成的子空間。TTTTmH CHG0HG0Lecture 4Lecture 4 信道編碼理論信道編碼理論 14定理定理: n, k, d線性分組碼最小漢明距離等于線性分組碼最小漢明距離等于d的充的充要條件是：要條件是：H的任意的任意d-1列線性無關(guān)列線性無關(guān)Proof . hint: 必要性：采用反證法；充分性：將必要性：采用反證

11、法；充分性：將H中某中某些些d列線性相關(guān)的列的系數(shù)作為碼字中對應(yīng)的非列線性相關(guān)的列的系數(shù)作為碼字中對應(yīng)的非0分量分量推論推論: n, k, d線性分組碼的線性分組碼的最大可能的最小漢明最大可能的最小漢明距離為距離為n-k+1Proof: 由于校驗矩陣由于校驗矩陣H的的n-k行是線性無關(guān)的，也就是行是線性無關(guān)的，也就是說說H的行秩為的行秩為n-k，從而可推出，從而可推出H的列秩最大是的列秩最大是n-k，即，即H最多有任意最多有任意n-k列線性無關(guān)，由定理得到列線性無關(guān)，由定理得到n-kd-1,有有dn-k+1Lecture 4Lecture 4 信道編碼理論信道編碼理論 15對偶碼：對偶碼：設(shè)設(shè)

12、 n, k, d 線性分組碼線性分組碼 C 的生成矩陣為的生成矩陣為 G，校驗，校驗矩陣為矩陣為 H,以以 H 作為生成矩陣作為生成矩陣, G 為對應(yīng)的校驗矩陣為對應(yīng)的校驗矩陣,可構(gòu)可構(gòu)造另一個造另一個 n, n-k, d 線性分組碼線性分組碼C1,我們稱我們稱 C1 為為 C 的對偶的對偶碼。碼。 7,3,4碼的對偶碼必是碼的對偶碼必是7,4,3碼，其生成矩陣碼，其生成矩陣G7,4就是就是7,3,4碼的校驗矩陣碼的校驗矩陣H7,3。7,47,31011000111010011000100110001GHLecture 4Lecture 4 信道編碼理論信道編碼理論 16系統(tǒng)碼：系統(tǒng)碼：若信息

13、組以不變的形式在碼組的任意若信息組以不變的形式在碼組的任意k位（通常位（通常在最前面在最前面 : cn-1 , cn-2 , , cn-k）中出現(xiàn)的碼稱為系統(tǒng)碼，否）中出現(xiàn)的碼稱為系統(tǒng)碼，否則為非系統(tǒng)碼。則為非系統(tǒng)碼。G = IkP (前前 k 位為信息位，后位為信息位，后 n-k 位為校驗位位為校驗位) H = -PTIn-k （-PT 是是 P 矩陣的轉(zhuǎn)置）矩陣的轉(zhuǎn)置）系統(tǒng)碼的特點(diǎn)系統(tǒng)碼的特點(diǎn) ：系統(tǒng)碼的編碼相對而言比較簡單，且由系統(tǒng)碼的編碼相對而言比較簡單，且由G可以方便的得到可以方便的得到 H（反之亦然），容易檢查編出的碼字是（反之亦然），容易檢查編出的碼字是否正確。同時，對分組碼而言

14、，系統(tǒng)碼與非系統(tǒng)碼的糾錯否正確。同時，對分組碼而言，系統(tǒng)碼與非系統(tǒng)碼的糾錯能力完全等價。能力完全等價。 Lecture 4Lecture 4 信道編碼理論信道編碼理論 17縮短碼縮短碼 : 在在 n, k, d 碼的碼字集合中，挑選前碼的碼字集合中，挑選前 i 個信息位個信息位數(shù)字均為數(shù)字均為 0 的所有碼字，組成一個新的子集。由于該子集的所有碼字，組成一個新的子集。由于該子集的前的前 i 位信息位均取位信息位均取 0 ，故傳輸時可以不送它們，僅只要，故傳輸時可以不送它們，僅只要傳送后面的傳送后面的 n-i 位碼元即可。這樣該子集組成了一個位碼元即可。這樣該子集組成了一個n-i, k-i, d

15、 分組碼，稱它為分組碼，稱它為 n, k, d 碼的縮短碼。碼的縮短碼。縮短碼的特點(diǎn)縮短碼的特點(diǎn) ：由于縮短碼是由于縮短碼是 k 維子空間維子空間 Vn,k中取前中取前 i 位位均為均為 0 的碼字組成的一個子集，顯然該子集是的碼字組成的一個子集，顯然該子集是 Vn,k空間中空間中的一個的一個 k-i 維的子空間維的子空間 Vn,k-i，因此，因此 n-i, k-i, d 縮短碼的糾縮短碼的糾錯能力至少與原錯能力至少與原 n, k, d 碼相同。碼相同。Lecture 4Lecture 4 信道編碼理論信道編碼理論 18表表1的的7, 3, 4碼：碼：0000000，0011101，01001

16、11，0111010，1001110，1010011，1101001，11101006, 2, 4縮短碼為：縮短碼為： 000000，011101，100111，111010原碼和縮短碼的生成矩陣分別為原碼和縮短碼的生成矩陣分別為去掉去掉G的第一列第一行，就得到縮短碼的生成矩陣的第一列第一行，就得到縮短碼的生成矩陣Gs100111011101sG100111001001110011101GLecture 4Lecture 4 信道編碼理論信道編碼理論 19原碼和縮短碼的校驗矩陣分別為原碼和縮短碼的校驗矩陣分別為對系統(tǒng)碼而言，去掉對系統(tǒng)碼而言，去掉G的前的前i列和前列和前i行就可得到縮短碼行就可

17、得到縮短碼的生成矩陣的生成矩陣Gs。去掉校驗矩陣的前。去掉校驗矩陣的前i列，可得到縮短碼列，可得到縮短碼的校驗矩陣的校驗矩陣Hs。1000110010001100101110001101H011000110100100010110001sHLecture 4Lecture 4 信道編碼理論信道編碼理論 20u 要糾正一個錯誤的要糾正一個錯誤的 n, k, d 分組碼，要求其分組碼，要求其 H 矩陣中矩陣中至少兩列線性無關(guān)，且不能全為至少兩列線性無關(guān)，且不能全為 0。若為二進(jìn)制碼，則要。若為二進(jìn)制碼，則要求求 H 矩陣中每列互不相同，且不能全為矩陣中每列互不相同，且不能全為 0。u 一個一個 n

18、, k, d 分組碼有分組碼有 n-k 位檢驗元，在二進(jìn)制碼情位檢驗元，在二進(jìn)制碼情況下，這況下，這 n-k 個校驗元能組成個校驗元能組成 2n-k 列不同的列不同的 n-k 重，其中重，其中有有2n-k-1列不全為列不全為0。所以用這。所以用這 2n-k-1 列作為列作為 H 矩陣的每一矩陣的每一列，則由此列，則由此 H 就產(chǎn)生了一個糾正單個錯誤的就產(chǎn)生了一個糾正單個錯誤的n, k, 3碼，碼，它就是漢明碼。它就是漢明碼。Lecture 4Lecture 4 信道編碼理論信道編碼理論 21u GF(2)上漢明碼的上漢明碼的 H 矩陣的列，是由不全為矩陣的列，是由不全為 0，且互不，且互不相同

19、的二進(jìn)制相同的二進(jìn)制 m 重組成。該碼有如下參數(shù)：重組成。該碼有如下參數(shù)：n=2m-1，k=2m-1-m，R=(2m-1-m)/(2m-1)，d=3。u 構(gòu)造構(gòu)造GF(2)上的上的7, 4, 3漢明碼，這時取漢明碼，這時取m=3，所有，所有23=8個三重為：個三重為：001, 010, 011, 100, 101, 110, 111, 000。挑出其。挑出其中中7個非個非 0 的三重構(gòu)成校驗矩陣為：的三重構(gòu)成校驗矩陣為：000111101100111010101HLecture 4Lecture 4 信道編碼理論信道編碼理論 22u 可以把可以把 GF(2) 上的漢明推廣到上的漢明推廣到 GF

20、(q) 上，得到多進(jìn)制上，得到多進(jìn)制漢明碼，此時碼有如下參數(shù)：漢明碼，此時碼有如下參數(shù)： 碼碼 長：長： n=(qm-1)/(q-1) 信信 息息 位：位： k=n-m 碼碼 率：率： R=(n-m) / n 最小距離：最小距離： d=3u 二進(jìn)制二進(jìn)制 2m-1，2m-1-m，3漢明碼的對偶碼漢明碼的對偶碼 是一個是一個2m-1，m，2m-1碼，也稱為單純碼或極長碼。碼，也稱為單純碼或極長碼。 HC Lecture 4Lecture 4 信道編碼理論信道編碼理論 23伴隨式伴隨式設(shè)發(fā)送碼字接收序列根據(jù)錯誤圖樣的概念，R=C+ES是校驗矩陣H中某幾列數(shù)據(jù)的線性組合，因而是n-k維向量，有2n-

21、k種可能錯誤圖樣E是n維向量，共有2n種可能，因而每2k種錯誤圖樣對應(yīng)一種伴隨式。021,rrrnnRTTTEHHECRHS)(120,nncccCLecture 4Lecture 4 信道編碼理論信道編碼理論 241,11,21,11,02,12,22,12,01210,1,2,1,0nnnnnnn k nn k nn kn khhhhhhhhhhhhHhhh h1210123(,)(0,0,0,0,0,0)nniiiiteee eeeeeEu 式中，式中，hn-i為為 H 矩陣的第矩陣的第 i 列，它是一個列，它是一個n-k重列矢量。重列矢量。u 表示第表示第 i1 ，i2 , . , i

22、t 位有錯。位有錯。Lecture 4Lecture 4 信道編碼理論信道編碼理論 25u S是是 H 矩陣中相應(yīng)于矩陣中相應(yīng)于eij 0（j=1,2，t）的）的那幾列那幾列 hn-ij 的線性組合，由于的線性組合，由于 hn-ij 是是 n-k重列矢量，重列矢量，故故 S 也是一個也是一個n-k重的矢量（重的矢量（s1，s2，sn-k)。若沒。若沒有錯誤，所有有錯誤，所有 si=0 ,則則 S 是一個零矢量。是一個零矢量。1212101122000nniiitiiiiititeeeeeehhSEHhhhhh Lecture 4Lecture 4 信道編碼理論信道編碼理論 267,3,4碼的校

23、驗矩陣H為錯誤圖樣及其相應(yīng)的伴隨式1000110010001100101110001101HE2=(1100000)E3=(0010100)E1=(1000000)S1T=HE1T =(1110)TS2T=HE2T =(1001)TS3T=HE3T =(1001)TLecture 4Lecture 4 信道編碼理論信道編碼理論 27一個一個 n, k, d 線性分組碼，若要糾正線性分組碼，若要糾正 t個錯誤，則其充要個錯誤，則其充要條件是條件是 H 矩陣中任何矩陣中任何 2t 列線性無關(guān)。由于列線性無關(guān)。由于 d=2t+1，所以，所以也相當(dāng)于要求也相當(dāng)于要求 H 矩陣中矩陣中 d-1列線性無關(guān)

24、。列線性無關(guān)。n, k, d 線性分組碼有最小距離等于線性分組碼有最小距離等于 d的充要條件是，的充要條件是，H 矩陣中任意矩陣中任意 d-1 列線性無關(guān)。列線性無關(guān)。(singleton限限) n, k, d 線性分組碼的最大可能的最小距離線性分組碼的最大可能的最小距離等于等于n-k+1，即，即 d n-k+1。MDS 碼碼 ：若系統(tǒng)碼的最小距離：若系統(tǒng)碼的最小距離 d=n-k+1, 則稱此碼為極大則稱此碼為極大最小距離可分碼，簡稱最小距離可分碼，簡稱 MDS 碼。碼。Lecture 4Lecture 4 信道編碼理論信道編碼理論 28標(biāo)準(zhǔn)陣列步驟標(biāo)準(zhǔn)陣列步驟 1): 由接收到的序列R，計算

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