第三章 線(xiàn)性分組碼

第3章線(xiàn)性分組碼3.1線(xiàn)性分組碼的基本概念3.2碼的一致校驗(yàn)矩陣與生成矩陣3.3伴隨式與標(biāo)準(zhǔn)陣列及其它譯碼3.4線(xiàn)性碼的覆蓋半徑3.5由一個(gè)已知碼構(gòu)造新碼的簡(jiǎn)單方法習(xí)題3.1線(xiàn)性分組碼的基本概念

第一章已敘述了分組碼的某些重要概念，如分組碼的表示、碼率、距離、重量等。如果我們把每一碼字看成是一個(gè)n維數(shù)組或n維線(xiàn)性空間中的一個(gè)矢量，則可以從線(xiàn)性空間的角度，比較深入地討論線(xiàn)性分組碼。

一個(gè)［n，k］線(xiàn)性分組碼，是把信息劃成k個(gè)碼元為一段(稱(chēng)為信息組)，通過(guò)編碼器變成長(zhǎng)為n個(gè)碼元的一組，作為［n，k］線(xiàn)性分組碼的一個(gè)碼字。若每位碼元的取值有q種(q為素?cái)?shù)冪)，則共有qk個(gè)碼字。n長(zhǎng)的數(shù)組共有qn組，在二進(jìn)制情況下，有2n個(gè)數(shù)組。顯然，qn個(gè)n維數(shù)組(n重)組成一個(gè)GF(q)上的n維線(xiàn)性空間。如果qk(或2k)個(gè)碼字集合構(gòu)成了一個(gè)k維線(xiàn)性子空間，則稱(chēng)它是一個(gè)［n，k］線(xiàn)性分組碼。

定義3.1.1［n，k］線(xiàn)性分組碼是GF(q)上的n維線(xiàn)性空間Vn中的一個(gè)k維子空間Vn,k。由于該線(xiàn)性子空間在加法運(yùn)算下構(gòu)成阿貝爾群，所以線(xiàn)性分組碼又稱(chēng)為群碼。為簡(jiǎn)單起見(jiàn)，今后若沒(méi)有特別說(shuō)明，所說(shuō)的分組碼均指線(xiàn)性分組而言，且用(cn-1，cn-2，…，c1，c0)表示［n，k］碼的一碼字，其中每一分量ci∈GF(q)。例3.1n=7，k=3的［7，3］線(xiàn)性分組碼的8個(gè)碼字和信息組如表3-1所示。這8個(gè)碼字在模2加法運(yùn)算下構(gòu)成一個(gè)阿貝爾加群。信息組碼字00000101001110010111011100000000011101010011101110101001110101001111010011110100

由于線(xiàn)性分組碼是分組碼的一類(lèi)，因此第一章中有關(guān)分組碼的參數(shù)，如碼率R=k／n、碼字的距離與碼的最小距離、碼字的重量等定義，以及說(shuō)明最小距離與糾錯(cuò)能力之間關(guān)系的定理1.3.1，對(duì)線(xiàn)性分組碼均適用，這里不再贅述。顯然，R和d是分組碼的兩個(gè)最重要的參數(shù)，因此今后我們用［n，k，d］(或［n，k］)表示線(xiàn)性分組碼。而用(n，M，d)表示碼字?jǐn)?shù)目為M的任何碼，此時(shí)碼率R=n–1logqM。

［n，k，d］分組碼是一個(gè)群碼，因此若碼字C1∈［n，k，d］、C2∈［n，k，d］，則由群的封閉性可知，碼字C1與C2之和C1+C2∈［n，k，d］，即C1+C2也必是［n，k，d］分組碼的一個(gè)碼字。所以，兩碼字C1和C2之間的距離d(C1，C2)必等于第三個(gè)碼字C1+C2的漢明重量。

如例3.1中的兩個(gè)碼字：(1010011)，(1101001)，它們之間的距離是4，它就是(0111010)碼字的重量，即d(C1，C2)=w(C1+C2)因此，一個(gè)［n，k，d］分組碼的最小距離必等于碼中非零碼字的最小重量，由此可得如下定理。

定理3.1.1［n，k，d］線(xiàn)性分組碼的最小距離等于非零碼字的最小重量。

定理3.1.2GF(2)上［n，k，d］線(xiàn)性分組碼中，任何兩個(gè)碼字C1，C2之間有如下關(guān)系：w(C1+C2)=w(C1)+w(C2)-2w(C1·C2)(3.1.1)或d(C1，C2)≤w(C1)+w(C2)(3.1.2)式中，C1·C2是兩個(gè)碼字的內(nèi)積。

證明設(shè)C1=(c1，n-1，c1，n-2，…，c1，0))

C2=(c2，n-1，c2，n-2，…，c2，0)且令對(duì)所有i=0，1，…，n-1，則

推論3.1.1GF(2)上線(xiàn)性分組碼任3個(gè)碼字C1，C2，C3之間的漢明距離，滿(mǎn)足以下三角不等式d(C1，C2)+d(C2，C3)≥d(C1，C3)(3.1.3)證明設(shè)碼字Ca=C1+C2，Cb=C2+C3，由式(3.1.2)可知：w(Ca+Cb)=w(C1+C2+C2+C3)=w(C1+C3)=d(C1，C3)≤w(Ca)+w(Cb)=w(C1+C2)+w(C2+C3)。所以d(C1，C3)≤d(C1，C2)+d(C2，C3)

定理3.1.3任何［n，k，d］線(xiàn)性分組碼，碼字的重量或全部為偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)等于偶數(shù)重量的碼字?jǐn)?shù)。請(qǐng)讀者自行證明該定理?！?.2碼的一致校驗(yàn)矩陣與生成矩陣

一、碼的校驗(yàn)矩陣與生成矩陣［n，k，d］分組碼的編碼問(wèn)題就是在n維線(xiàn)性空間Vn

中，如何找出滿(mǎn)足一定要求的，有2k個(gè)矢量組成的k維線(xiàn)性子空間Vn，k

?；蛘哒f(shuō)，在滿(mǎn)足給定條件(碼的最小距離d或碼率R)下，如何從已知的k個(gè)信息元求得r=n-k個(gè)校驗(yàn)元。

這相當(dāng)于建立一組線(xiàn)性方程組，已知k個(gè)系數(shù)，要求n-k個(gè)未知數(shù)，使得到的碼恰好有所要求的最小距離d。上例中的［7，3，4］碼，若c6，c5，c4代表3個(gè)信息元，則c3，c2，c1，c0這4個(gè)校驗(yàn)元，可由以下線(xiàn)性方程組求得：

1·c3=1·c6+0·c5+1·c41·c2=1·c6+1·c5+1·c41·c1=1·c6+1·c5+0·c41·c0=0·c6+1·c5+1·c4(3.2.1)c6

+c4+c3=0

c6+c5+c4

+c2=0

c6+c5+c1=0c5+c4

+c0=0

例3.2c6=1，c5=0，c4=1，求c3，c2，c1，c0。由上述線(xiàn)性方程組可知：c3=c6+c4=1+1=0c2=c6+c5+c4=1+0+1=0c1=c6+c5=1+0=1c0=c5+c4=0+1=1由此得到的碼字為：(1010011)。

可以檢驗(yàn)例3.1中的［7，3，4］碼的8個(gè)碼字均滿(mǎn)足式(3.2.1)和式(3.2.2)。若用矩陣形式表示這些線(xiàn)性方程組，則式(3.2.1)或式(3.2.2)可表示為：或

稱(chēng)上式中的4行7列矩陣為［7，3，4］碼的一致校驗(yàn)矩陣，通常用H表示，該碼的

它是一個(gè)(n-k)×n階矩陣。由此H矩陣可以很快地建立碼的線(xiàn)性方程組：(3.2.3)

它是一個(gè)(n-k)×n階矩陣。由此H矩陣可以很快地建立碼的線(xiàn)性方程組：(3.2.4)或

(3.2.5)簡(jiǎn)寫(xiě)為H·CT=0T

(3.2.6)或C·HT=0(3.2.7)

可知H矩陣的每一行代表一個(gè)線(xiàn)性方程組的系數(shù)，它表示求一個(gè)校驗(yàn)元的線(xiàn)性方程。因此任何一個(gè)［n，k，d］碼的H矩陣必須有n-k行，且每行必須線(xiàn)性獨(dú)立。若把H的每一行看成一個(gè)矢量，則這n-k個(gè)矢量必然張成了n維線(xiàn)性空間中的一個(gè)n-k維子空間

Vn，n-k

。

由于［n，k，d］碼的每一碼字必須滿(mǎn)足式(3.2.6)或式(3.2.7)，即它的每一碼字必然在由H矩陣的行所張成的Vn，n-k空間中的零空間中。由定理2.6.10可知，Vn，n-k

的零空間必然是一個(gè)k維子空間Vn

，k

，而這正是［n，k，d］碼的碼字集合全體。所以，Vn，n-k與［n，k，d］碼的每一碼字均正交，也就是H矩陣的每一行與它的碼的每一碼字的內(nèi)積均為0。

［n，k，d］分組碼的2k

個(gè)碼字組成了一個(gè)k維子空間，因此這2k

個(gè)碼字完全可由k個(gè)獨(dú)立矢量所組成的基底而張成。設(shè)基底為C1=(g1，n-1，g1，n-2，…，g1，0)C2=(g2，n-1，g2，n-2，…，g2，0)…Ck

=(gk，n-1，gk，n-2，…，gk，0)若把這組基底寫(xiě)成矩陣形式，則有

g1，n-1，g1，n-2，…，g1，0

g2，n-1，g2，n-2，…，g2，0…gk，n-1，gk，n-2，…，gk，0

G=

(3.2.8)

［n，k，d］碼中的任何碼字，都可由這組基底的線(xiàn)性組合生成，即C=m·G=［mn

-1mn

-2…mn

-k

］

g1，n-1，g1，n-2，…，g1，0

g2，n-1，g2，n-2，…，g2，0…gk，n-1，gk，n-2，…，gk，0

(3.2.9)

式中，m=(mn

-1，mn

-2，…，mn

-k

)是k個(gè)信息元組成的信息組。因此，若已知信息組m，通過(guò)式(3.2.9)可求得相應(yīng)的碼字，稱(chēng)式(3.2.8)的G為［n，k，d］碼的生成矩陣。

如表3-1中的［7，3，4］碼，可從它的8個(gè)碼字中任意挑出k=3個(gè)線(xiàn)性無(wú)關(guān)的碼字：(1001110)，(0100111)，(0011101)作為碼的生成矩陣的行，則

(3.2.10)若已知信息組m=(011)，則相應(yīng)的碼字為

顯然，一個(gè)矢量空間的基底可以不止一個(gè)，因此作為碼的生成矩陣G也可以不止一種形式。但不論哪一種形式，它們都生成相同的矢量空間，即生成同一個(gè)［n，k，d］碼。G中的每一行及其線(xiàn)性組合均為［n，k，d］碼的一個(gè)碼字，所以由式(3.2.6)和式(3.2.7)可知G·HT=0(3.2.11)或H·GT=0T(3.2.12)

二、對(duì)偶碼［n，k，d］碼是n維線(xiàn)性空間中的一個(gè)k維子空間Vn，k

，由一組基底即G的行張成。由前可知，它的零空間必是一個(gè)n-k維的線(xiàn)性子空間Vn

，n-k

，并由n-k個(gè)獨(dú)立矢量張成。由式(3.2.11)和式(3.2.12)可知，這n-k個(gè)矢量就是H矩陣的行。因此，若把H矩陣看成是［n，n-k，d］碼的生成矩陣G，而把［n，k，d］碼的G看成是它的校驗(yàn)矩陣H，則我們稱(chēng)由G生成的［n，k，d］碼C與由H生成的［n，n-k，d］碼C⊥互為對(duì)偶碼。相應(yīng)地，稱(chēng)Vn，k與Vn

，n-k空間互為對(duì)偶空間。由此可如下定義對(duì)偶碼。

定義3.2.1設(shè)C是［n，k，d］碼，則它的對(duì)偶碼C⊥是

C⊥{x∈Vn，(n-k)；對(duì)所有y∈C使x·y=0}式中，x·y為x與y的內(nèi)積。

如例3.1中的［7，3，4］碼，它的對(duì)偶碼必是［7，4，3］碼，其生成矩陣G［7，4］就是［7，3，4］碼的校驗(yàn)矩陣H［7，3］G［7，4］=H［7，3］=

由此生成矩陣，已知信息組m，根據(jù)式(3.2.9)就可求得［7，4，3］碼的16個(gè)碼字。

若一個(gè)碼的對(duì)偶碼就是它自己，即C=C⊥則稱(chēng)C碼為自對(duì)偶碼。顯然，自對(duì)偶碼必定是［2m，m，d］形式的分組碼。如［2，1，2］重復(fù)碼就是一個(gè)自對(duì)偶碼。如果自對(duì)偶碼的最小距離d是4的倍數(shù)，則稱(chēng)為雙偶自對(duì)偶碼，可以證明雙偶自對(duì)偶碼的碼長(zhǎng)n必是8的整數(shù)倍。

三、系統(tǒng)碼定義3.2.2若信息組以不變的形式在碼組的任意k位(通常在最前面：cn

-1，cn

-2，…，cn

-k

)中出現(xiàn)的碼稱(chēng)為系統(tǒng)碼，否則為非系統(tǒng)碼。系統(tǒng)碼的一種結(jié)構(gòu)形式如圖3-1所示。表3-1中所列的［7，3，4］碼就是系統(tǒng)碼形式。顯然，系統(tǒng)碼的信息位與校驗(yàn)位很容易區(qū)分開(kāi)，所以這種碼也稱(chēng)可分碼。

由于系統(tǒng)碼的碼字前k位是原來(lái)的信息組，故由式(3.2.8)可知，G矩陣左邊k列必組成一個(gè)單位方陣Ik

，因此系統(tǒng)碼的生成矩陣通常為G=［IkP］(3.2.13)k位信息位n-k位校驗(yàn)位

圖3-1系統(tǒng)碼的一種結(jié)構(gòu)形式

式中，P是k×(n-k)階矩陣。如果信息組不在碼字的前k位，而在碼字的后k位，則G矩陣中的Ik方陣在P矩陣的右邊。因?yàn)镚與H矩陣所組成的空間互為零空間，所以與式(3.2.13)相應(yīng)的H矩陣為H=［-PTIn

-k

］(3.2.14)

式中，-PT是一個(gè)(n-k)×k階矩陣，它是P矩陣的轉(zhuǎn)置，“-”號(hào)表示-PT陣中的每一元素是P陣中對(duì)應(yīng)元素的逆元，在二進(jìn)制情況下，仍是該元素自己。顯然，由此得到的H滿(mǎn)足

通常，我們稱(chēng)式(3.2.13)與式(3.2.14)中的G和H矩陣為碼的典型(標(biāo)準(zhǔn))生成矩陣和典型校驗(yàn)矩陣。如［7，3，4］碼的典型生成矩陣相應(yīng)地，典型校驗(yàn)矩陣由式(3.2.14)為

系統(tǒng)碼的編碼相對(duì)而言較為簡(jiǎn)單，且由G可以方便地得到H(反之亦然)，容易檢查編出的碼字是否正確。同時(shí)，對(duì)分組碼而言，系統(tǒng)碼與非系統(tǒng)碼的糾錯(cuò)能力完全等價(jià)。因此，今后若無(wú)特別聲明，僅討論系統(tǒng)碼形式。

四、縮短碼在某些情況下，如果不能找到一種比較合適的碼長(zhǎng)或信息位個(gè)數(shù)，則可把某一［n，k，d］碼進(jìn)行縮短，以滿(mǎn)足要求。

在［n，k，d］碼的碼字集合中，挑選前i個(gè)信息位數(shù)字均為0的所有碼字，組成一個(gè)新的子集。由于該子集的前i位信息位均取0，故傳輸時(shí)可以不送它們，僅只要傳送后面的n-i位碼元即可。這樣該子集組成了一個(gè)［n-i，k-i，d］分組碼，稱(chēng)它為［n，k，d］碼的縮短碼。由于縮短碼是k維子空間Vn，k中取前i位均為0的碼字組成的一個(gè)子集，顯然該子集是Vn，k空間中的一個(gè)k-i維的子空間Vn，k-i，因此［n-i，k-i，d］縮短碼的糾錯(cuò)能力至少與原［n，k，d］碼相同。

如例3.1中的［7，3，4］碼，若挑出第一個(gè)信息位均為0的碼字：(0000000)，(0011101)，(0100111)，(0111010)，則可組成一個(gè)［6，2，4］縮短碼：(000000)，(011101)，(100111)，(111010)?？s短碼的G矩陣只要在原［n，k，d］碼的G矩陣中，去掉左邊i列和上邊i行即可。如上例中，［6，2，4］縮短碼的G矩陣可由［7，3，4］碼的G矩陣(式(3.2.10))去掉第一行及左邊第一列得到G［6，2］=

而H矩陣，只要在原碼的H矩陣中去掉第一列即可。如該例的H矩陣為

［n-i，k-i］縮短碼是［n，k］碼縮短i位得到的，因而碼率R比原碼要小，但糾錯(cuò)能力不一定比原碼強(qiáng)。因此總的看來(lái)，縮短碼比原碼的性能要差。

§3.3伴隨式與標(biāo)準(zhǔn)陣列及其它譯碼

一、伴隨式(校正子)本節(jié)討論如何譯碼。設(shè)發(fā)送的碼字C=(cn

-1，

cn

-2，…，c1，c0)，通過(guò)有擾信道傳輸，信道產(chǎn)生的錯(cuò)誤圖樣E=(en

-1，en

-2，…，e1，e0)。接收端譯碼器收到的n重為R=(rn

-1，rn

-2，…，r1，r0)，R=C+E，ri=ci+ei，ci，ri，ei∈GF(q)或GF(2)中。

［n，k，d］碼的每一碼字C，都必須滿(mǎn)足式(3.2.6)或式(3.2.7)。因此，收到R后用該兩式之中的任一式進(jìn)行檢驗(yàn)：R·HT=(C+E)·HT=C·HT+E·HT=E·HT

(3.3.1)若E=0，則R·HT=0，E≠0則R·HT≠0。說(shuō)明R·HT僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的是什么碼字

無(wú)關(guān)。令S=R·HT=E·HT或ST=H·RT=H·ET

(3.3.2)由前知，［n，k，d］碼的校驗(yàn)矩陣

式中，hn

-i為H矩陣的第i列，它是一個(gè)n-k重列矢量。設(shè)E=(en

-1，en-2，…，e1，e0)

=(0，…，ei1，0，…，ei2，0，…，ei3，0，…，eit，0，…，0)第i1，i2，…，it位有錯(cuò)，則

從上面分析看出，一個(gè)［n，k，d］碼要糾正≤t個(gè)錯(cuò)誤，則要求≤t個(gè)錯(cuò)誤的所有可能組合的錯(cuò)誤圖樣，都應(yīng)該有不同的伴隨式與之對(duì)應(yīng)。這等效于：若(0，…，0，ei1，ei2，…，eit，0，…，0)≠(0，…，0，ej1，ej2，…，eit，0，…，0)

則要求：ei1hi1+ei2hi2+…+eithit≠ej1hj1+ej2hj2+…+ejthjt(3.3.4)或ei1hi1+ei2hi2+…+eithit-ej1hj1-ej2hj2-…-eithjt≠0T(3.3.5)由此可得到如下重要結(jié)論。

結(jié)論一個(gè)［n，k，d］線(xiàn)性分組碼，若要糾正≤t個(gè)錯(cuò)誤，則其充要條件是H矩陣中任何2t列線(xiàn)性無(wú)關(guān)。由于d=2t+1，所以也相當(dāng)于要求H矩陣中d-1列線(xiàn)性無(wú)關(guān)。由此結(jié)論可得到以下重要定理。定理3.3.1［n，k，d］線(xiàn)性分組碼有最小距離等于d的充要條件是，H矩陣中任意d-1列線(xiàn)性無(wú)關(guān)。證明先證明必要性。即碼有最小距離為d，證明H中的任意d-1列線(xiàn)性無(wú)關(guān)。用反證法。若H中某一d-1列線(xiàn)性相關(guān)，則由線(xiàn)性相關(guān)定義可知：ci1hi1+ci2hi2+…+ci(d-1)hi(d-1)=0T式中，cij∈GF(q)，hij是H矩陣的列矢量?，F(xiàn)作一個(gè)碼字C，它在i1，i2，…，i(d-1)位處的值分別等于ci1，ci2，…，ci(d-1)，而其它各位取值均為0，所以得到的碼字C是:(0，…，ci1，0，…，0，ci2，0，…，0，ci(d-1)，0，…，0)，由此H·CT=ci1hi1+ci2hi2+…+ci(d-1)hi(d-1)=0T故C是一個(gè)碼字，而C的非0分量個(gè)數(shù)只有d-1個(gè)，這與碼有最小距離為d的假設(shè)相矛盾，故H中的任意d-1列必線(xiàn)性無(wú)關(guān)。下面證明：若H中任意d-1列線(xiàn)性無(wú)關(guān)，則［n，k，d］碼有最小距離為d。若H中任意d-1列線(xiàn)性無(wú)關(guān)，則H中至少需要d列才能線(xiàn)性相關(guān)。我們將能使H中某些d列線(xiàn)性相關(guān)的列的系數(shù)，作為碼字中對(duì)應(yīng)的非0分量，而碼字的其余分量均為0，則該碼字至少有d個(gè)非0分量，故［n，k，d］碼有最小距離為d。

定理3.3.1異常重要，它是構(gòu)造任何類(lèi)型線(xiàn)性分組碼的基礎(chǔ)。由該定理看出，交換H矩陣的各列，并不會(huì)影響碼的最小距離。因此，所有列相同但排列位置不同的H所對(duì)應(yīng)的分組碼，在糾錯(cuò)能力和其它碼參數(shù)上完全等價(jià)。推論3.3.1(Singleton限)［n，k，d］線(xiàn)性分組碼的最大可能的最小距離等于n-k+1，即d≤n-k+1。推論的證明讀者可自行進(jìn)行。若系統(tǒng)碼的最小距離d=n-k+1，則稱(chēng)此碼為極大最小距離可分碼，簡(jiǎn)稱(chēng)MDS碼。構(gòu)造MDS碼是編碼理論中一個(gè)重要課題。

二、漢明碼與極長(zhǎng)碼漢明碼是1950年由漢明首先構(gòu)造，用以糾正單個(gè)錯(cuò)誤的線(xiàn)性分組碼。由于它的編譯碼非常簡(jiǎn)單，很容易實(shí)現(xiàn)，因此用得很普遍，特別是在計(jì)算機(jī)的存貯和運(yùn)算系統(tǒng)中更常用到。此外，它與某些碼類(lèi)的關(guān)系很密切，因此這是一類(lèi)特別引人注意的碼。

由定理3.3.1知，糾正一個(gè)錯(cuò)誤的［n，k，d］分組碼，要求其H矩陣中至少兩列線(xiàn)性無(wú)關(guān)，且不能全為0。若為二進(jìn)制碼，則要求H矩陣中每列互不相同，且不能全為0。一個(gè)［n，k，d］分組碼有n-k位校驗(yàn)元，在二進(jìn)制碼情況下，這n-k個(gè)校驗(yàn)元能組成2n-k列不同的n-k重，其中有2n

-k

-1列不全為0。所以，如果用這2n

-k

-1列作為H矩陣的每一列，則由此H就產(chǎn)生了一個(gè)糾正單個(gè)錯(cuò)誤的［n，k，3］碼，它就是漢明碼。

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

例3.3構(gòu)造GF(2)上的［7，4，3］漢明碼。這時(shí)取m=3，所有23=8個(gè)三重為：000，100，010，001，011，101，110，111。挑出其中7個(gè)非0的三重構(gòu)成

若碼字傳輸中第一位發(fā)生錯(cuò)誤，則相應(yīng)的伴隨式S=(001)，它就是“1”的二進(jìn)制表示，若第五位發(fā)生錯(cuò)誤，伴隨式S=(101)，是“5”的二進(jìn)制表示。因此，哪一位發(fā)生錯(cuò)誤，它的伴隨式就是該位號(hào)碼的二進(jìn)制表示，所以能很方便地進(jìn)行譯碼。

由前知，任意調(diào)換H中各列位置，并不會(huì)影響碼的糾錯(cuò)能力。因此，漢明碼的H矩陣形式，除了上述表示外，還可以有其它形式。若把漢明碼化成系統(tǒng)碼形式，則其(3.3.6)相應(yīng)地(3.3.7)

可以把GF(2)上的漢明推廣到GF(q)上，得到多進(jìn)制漢明碼，此時(shí)碼有如下參數(shù)：碼長(zhǎng)n=(qm-1)／(q-1)信

息

位k=n-m碼率R=(n-m)／n最小距離d=3顯然，當(dāng)n→∞時(shí)，R→1，因此漢明碼是糾正單個(gè)錯(cuò)誤的高效碼。

二進(jìn)制［2m-1，2m-1-m，3］漢明碼的對(duì)偶碼C⊥H是一個(gè)［2m-1，m，2m-1］碼，也稱(chēng)為單純碼或極長(zhǎng)碼。以后將看到，它可以由m級(jí)線(xiàn)性移存器產(chǎn)生，所以也稱(chēng)最長(zhǎng)線(xiàn)性移存器碼。

三、標(biāo)準(zhǔn)陣列由前面的討論中可知，［n，k，d］分組碼的譯碼步驟可歸結(jié)為以下三步：(1)由接收到的R，計(jì)算伴隨式S=R·H

T；(2)若S=0，則認(rèn)為接收無(wú)誤。若S≠0，則由S找出錯(cuò)誤圖樣；(3)由和R找出。

［n，k，d］碼的2k

個(gè)碼字，組成了n維線(xiàn)性空間中的一個(gè)k維子空間，顯然是一子群。若以此子群為基礎(chǔ)，把整個(gè)n維空間的2n

個(gè)元素劃分陪集，則得到如表3-2所示的譯碼表。其中，2k

個(gè)碼字放在表中的第一行，該子群的恒等元素C1(全為0碼字)放在最左邊，然后在禁用碼組中挑出一個(gè)n重E2放在恒等元素C1的下面，并相應(yīng)求出E2+C2，E2+C3，…，E2+C2k

，分別放在C2，C3，…，C2k

碼字的下邊構(gòu)成第二行，這是碼空間的一個(gè)陪集。

再選一個(gè)未寫(xiě)入表中前一行的n重E3，用以上方法構(gòu)成另一陪集成為表中的第三行，依此類(lèi)推，一共構(gòu)成2n

-k

個(gè)陪集，把所有2n

個(gè)矢量劃分完畢，稱(chēng)C1，E2，E3，…，

為陪集首。按這種方法構(gòu)成的表稱(chēng)為標(biāo)準(zhǔn)陣譯碼表，簡(jiǎn)稱(chēng)標(biāo)準(zhǔn)陣。

表3-2標(biāo)準(zhǔn)陣譯碼表

收到的n重R落在某一列中，則譯碼器就譯成相應(yīng)于該列最上面的碼字。因此，若發(fā)送的碼字為Ci，收到的R=Ci+Ej(1≤j≤2n

-k

，E1是全0矢量)，則能正確譯碼。如果收到的R=Ck

+Ej，則產(chǎn)生了錯(cuò)誤譯碼?，F(xiàn)在的問(wèn)題是：如何劃分陪集使譯碼錯(cuò)誤概率最小？這歸結(jié)到如何挑選陪集首。因?yàn)橐粋€(gè)陪集的劃分主要決定于子群，而子群就是2k

個(gè)碼字，這已決定，因此余下的問(wèn)題就是如何決定陪集首。

在第一章中已提出，在pe≤0.5的BSC中，產(chǎn)生1個(gè)錯(cuò)誤的概率比產(chǎn)生2個(gè)的大，產(chǎn)生2個(gè)的比3個(gè)的大……總之，錯(cuò)誤圖樣重量越小的產(chǎn)生的可能性越大。因此，譯碼器必須首先保證能正確糾正這種可能性出現(xiàn)最大的錯(cuò)誤圖樣，也就是重量最輕的錯(cuò)誤圖樣。這相當(dāng)于在構(gòu)造譯碼表時(shí)要求挑選重量最輕的n重為陪集首，放在標(biāo)準(zhǔn)陣中的第一列，而以全為0碼字作為子群的陪集首。這樣得到的標(biāo)準(zhǔn)陣，能得到最小的譯碼錯(cuò)誤概率。由于這樣安排的譯碼表使得C

i+Ej與Ci的距離保證最小，因而也稱(chēng)為最小距離譯碼，在BSC下，它們等效于最大似然譯碼。

在標(biāo)準(zhǔn)陣中，所有陪集首重量之和稱(chēng)為陪集首的總重量。應(yīng)當(dāng)指出，在給定的n、k條件下，如果在2n

組中選擇不同的2k

組作為子群，則相應(yīng)的標(biāo)準(zhǔn)陣中，陪集首元素的總重量不一定相同。若所選的Vn

，k

子空間，能做到使標(biāo)準(zhǔn)陣中陪集首元素的總重量最輕，則此碼能得到最大正確譯碼概率，因而稱(chēng)該Vn

，k子空間構(gòu)成的［n，k，d］碼為最佳碼。如果在n維空間中，能找到兩個(gè)或更多個(gè)Vn

，k子空間，都能做到使標(biāo)準(zhǔn)陣中陪集首元素的總重量最輕，則這些子空間構(gòu)成的不同的［n，k，d］碼均為最佳碼，因此對(duì)固定的n和k來(lái)說(shuō)，最佳碼不是唯一的。

例3.4［7，4，3］漢明碼的縮短碼［6，3，3］碼，它的8個(gè)碼組，可由式(3.3.7)的G矩陣中去掉第一行和第一列后的G［6,3］中的行線(xiàn)性組合而得到。該碼的標(biāo)準(zhǔn)陣如表3-3所示。

表3-3［6，3］碼標(biāo)準(zhǔn)陣

該［6，3，3］碼標(biāo)準(zhǔn)陣陪集首的總重量為8，而表1-2中碼標(biāo)準(zhǔn)陣陪集首的總重量也為8，這說(shuō)明這兩個(gè)［6，3］碼均是最佳碼。由該表可以看到，用這種標(biāo)準(zhǔn)陣譯碼，需要把2n

個(gè)n重存儲(chǔ)在譯碼器中。所以，這種譯碼方法譯碼器的復(fù)雜性隨n指數(shù)增長(zhǎng)，很不實(shí)用。

表3-4［6，3］碼簡(jiǎn)化譯碼表

由于［n，k，d］分組碼的n、k通常都比較大，即使用這種簡(jiǎn)化譯碼表，譯碼器的復(fù)雜性還是很高的。例如，一個(gè)［100，70］分組碼，一共有230≈109個(gè)伴隨式及錯(cuò)誤圖樣，譯碼器要存貯如此多的圖樣和(n-k)重是不太可能的。因此，在線(xiàn)性分組碼理論中，如何尋找簡(jiǎn)化譯碼器是最中心的研究課題之一，這將在以后有關(guān)章節(jié)討論。

四、完備譯碼與限定距離譯碼例3.4中的［6，3，3］碼利用標(biāo)準(zhǔn)陣譯碼時(shí)，能糾正所有單個(gè)錯(cuò)誤及一種兩個(gè)錯(cuò)誤，碼的所有23=8個(gè)伴隨式都與某種類(lèi)型的錯(cuò)誤圖樣對(duì)應(yīng)。因此，譯碼器必然要對(duì)收到的R進(jìn)行判決發(fā)送的是何碼字，這種譯碼方法稱(chēng)為完備譯碼。定義3.3.2［n，k，d］線(xiàn)性分組碼的所有2n-k個(gè)伴隨式，在譯碼過(guò)程中若都用來(lái)糾正所有小于等于t=［(d-1)／2］個(gè)隨機(jī)錯(cuò)誤，以及部分大于t的錯(cuò)誤圖樣，則這種譯碼方法稱(chēng)為完備譯碼。否則，稱(chēng)為非完備譯碼。任一個(gè)［n，k，d］碼，能糾正t≤［(d-1)／2］個(gè)隨機(jī)錯(cuò)誤。如果在譯碼時(shí)僅糾正t′＜t個(gè)錯(cuò)誤，而當(dāng)錯(cuò)誤個(gè)數(shù)大于t′時(shí)，譯碼器不進(jìn)行糾錯(cuò)而僅指出發(fā)生了錯(cuò)誤，稱(chēng)這種譯碼方法為限定距離譯碼。如［15，4，8］極長(zhǎng)碼，它能糾正3個(gè)錯(cuò)誤及部分4個(gè)錯(cuò)誤。如果設(shè)計(jì)譯碼器時(shí)，僅使它糾正1個(gè)錯(cuò)誤，而在≥2個(gè)錯(cuò)誤時(shí)，只指出接收的R有錯(cuò)，但不進(jìn)行糾正；則這種譯碼器就稱(chēng)為限定距離譯碼器?？芍薅ň嚯x譯碼，就是設(shè)計(jì)譯碼器時(shí)，在0至t=［(d-1)／2］范圍內(nèi)，事先由設(shè)計(jì)者指定糾錯(cuò)能力t′。當(dāng)實(shí)際產(chǎn)生的錯(cuò)誤個(gè)數(shù)≤t′時(shí)，譯碼器進(jìn)行糾錯(cuò)譯碼；當(dāng)大于t′時(shí)，譯碼器進(jìn)行檢錯(cuò)而不糾錯(cuò)?？梢?jiàn)，限定距離譯碼可以是完備譯碼，也可以是非完備譯碼，它完全由譯碼設(shè)計(jì)者決定。應(yīng)當(dāng)指出，無(wú)論是何種譯碼方法，為了使譯碼錯(cuò)誤概率最小，在設(shè)計(jì)譯碼器時(shí)都必須遵循最大似然譯碼準(zhǔn)則(碼字為等概發(fā)送時(shí))，在對(duì)稱(chēng)無(wú)記憶信道中也就是最小漢明距離譯碼準(zhǔn)則?！?.4線(xiàn)性碼的覆蓋半徑從幾何上講，碼的陪集劃分就是把n維線(xiàn)性空間Vn

，按［n，k，d］碼C劃分空間。標(biāo)準(zhǔn)陣譯碼表中的第j列，相當(dāng)于Vn

中球心為碼字C

j、半徑為ρ=d(Cj，Cj+E)=w(Ei)的一個(gè)球Bj(C)，球中的點(diǎn)也就是Cj列中的n重：{V∈Vn

｜d(v，Cj)≤ρ}j=0，1，2，…，2k

-1表中共有2k

列，相當(dāng)于有2k

個(gè)這種互不相交的球，把整個(gè)Vn空間覆蓋完畢?？芍狟j(C)球的半徑ρ，就是碼C的最大可能的糾錯(cuò)數(shù)目。表3-3中［6,3］碼的ρ是2，也就是它至多可能糾正兩個(gè)錯(cuò)誤，但不能糾正所有兩個(gè)錯(cuò)誤的圖樣。如果在Vn

空間中，以碼字為圓心，t=［(d-1)／2］為半徑作球，如圖1-15所示，則也有2k

個(gè)互不相交的球，但這些球一般并不能把整個(gè)Vn

空間全部覆蓋完畢。稱(chēng)這些球的半徑為碼C的球半徑s(C)?？芍aC的球半徑S(C)=［(d-1)／2］(3.4.1)能把整個(gè)Vn

空間覆蓋完畢的Bj(C)球的半徑ρ稱(chēng)為碼的覆蓋半徑t(C)?？芍猼(C)與s(C)均是碼的重要的幾何參數(shù)。定義3.4.1碼C的覆蓋半徑t(C)=max{min{d(v，Cj)｜Cj∈C}；v∈Vn

}(3.4.2)通常稱(chēng)Cj+v為碼字Cj的平移(Cj∈C，v∈Vn

)，稱(chēng)有minw(v)的v為平移首，因此t(C)就是有最大重量的平移首的重量。對(duì)線(xiàn)性碼來(lái)說(shuō)，就是陪集首的最大重量，而球半徑s(C)是碼一定能全部糾正的錯(cuò)誤數(shù)目。顯然s(C)≤t(C)≤d-1(3.4.3)如果碼C的t(C)=s(C)，則稱(chēng)C碼是完備碼，如果t(C)=s(C)+1(3.4.4)則稱(chēng)為準(zhǔn)完備碼。當(dāng)n為奇數(shù)時(shí)，［n，1，n］重復(fù)碼是完備碼；而當(dāng)n為偶數(shù)時(shí)是準(zhǔn)完備碼。重復(fù)碼又稱(chēng)為平凡碼。由最大似然譯碼原理可知，要使譯碼錯(cuò)誤概率最小，必須使譯碼表中陪集首的重量最輕。因此，在同樣的碼參數(shù)下，t(C)越小的碼譯碼錯(cuò)誤概率越小，因而最好?？芍猼(C)是衡量糾錯(cuò)碼性能的又一重要參數(shù)。在同樣的n與碼字?jǐn)?shù)目下，完備碼與準(zhǔn)完備碼都能使t(C)最小，因而是最佳碼。一般情況下，我們希望在同樣的n，k下，構(gòu)造出具有最大距離的碼，并且具有最小的t(C)。但是，由于構(gòu)造方法的不同，這二者之間并不完全一致，有最大距離的碼，其覆蓋半徑不一定小。在同樣的n，k下，碼所能達(dá)到的最小覆蓋半徑用t(n，k)表示，線(xiàn)性碼用t［n，k］表示。下面幾個(gè)定理說(shuō)明了二進(jìn)制分組碼的s(C)與t(C)的關(guān)系。定理3.4.1對(duì)任何二進(jìn)制(n，k)碼C，必滿(mǎn)足：(3.4.5)式中，K是碼字?jǐn)?shù)目。若C為［n，k］線(xiàn)性碼，且n為偶數(shù)，則必須滿(mǎn)足：(3.4.6)該定理稱(chēng)為球包和球包覆蓋限，證明它比較容易。由該定理不難得到t(C)的下限。定理3.4.2二進(jìn)制(n，k，d)碼的覆蓋半徑：(3.4.7)和(3.4.8)(3.4.9)下面給出t(C)的上限。定理3.4.3若2≤k≤1+ln

n，則［n，k］線(xiàn)性碼的(3.4.10)定理3.4.4對(duì)某一給定的k，存在有整數(shù)n1，n2，…，nq使(3.4.11)則當(dāng)n≥k時(shí)有式中，［x］表示不小于x的最小整數(shù)，［x］表示x的整數(shù)部分。有關(guān)這些限的證明，和其它各種情況下的上、下限及目前已知的各種碼的覆蓋半徑，以及t(n，k)和

t［n，k］，請(qǐng)參閱文獻(xiàn)［6-9］。如同尋求一個(gè)碼的實(shí)際最小距離一樣，當(dāng)碼長(zhǎng)和信息位較大時(shí)，如何分析尋求一個(gè)碼的覆蓋半徑是一個(gè)很困難的問(wèn)題。覆蓋半徑不僅與譯碼錯(cuò)誤概率及碼的最小距離有關(guān)，而且還涉及到其它問(wèn)題，如好碼的構(gòu)造、數(shù)據(jù)壓縮中的失真度等問(wèn)題，近來(lái)日益引起人們的廣泛注意?！?.5由一個(gè)已知碼構(gòu)造新碼的簡(jiǎn)單方法

一、擴(kuò)展碼設(shè)C是一個(gè)最小距離為d的二進(jìn)制［n，k，d］線(xiàn)性分組碼，它的碼字有奇數(shù)重量也有偶數(shù)重量。若對(duì)每一個(gè)碼字(cn

-1，cn

-2，…，c1，c0)增加一個(gè)校驗(yàn)元c′0，滿(mǎn)足以下校驗(yàn)關(guān)系：cn

-1+cn

-2+…+c1+c0+c′0=0(3.5.1)稱(chēng)c′0為全校驗(yàn)位。

若原碼的校驗(yàn)矩陣為H，則擴(kuò)展碼的校驗(yàn)矩陣為

［2m-1，2m-1-m，3］漢明碼的擴(kuò)展碼是［2m，2m-1-m，4］碼，它的中的H是漢明碼的校驗(yàn)矩陣。

例3.5對(duì)例3.3中的［7，4，3］漢明碼，附加一個(gè)全校驗(yàn)，則得到了一個(gè)［8，4，4］擴(kuò)展?jié)h明碼，它的校驗(yàn)矩陣由式(3.3.6)可得：(3.5.3)可以檢驗(yàn)它是一個(gè)雙偶自對(duì)偶碼。

二、刪余碼刪余碼是由擴(kuò)展碼的逆過(guò)程而得到的。它在原［n，k］碼C的基礎(chǔ)上，刪去一個(gè)校驗(yàn)元而構(gòu)成，變?yōu)椋踤-1，k］刪余碼C*。C*碼的最小距離可能比原碼小1，也可能不變。