第三章 線性分組碼

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

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

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

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

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

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

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

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

定理3.1.2GF(2)上［n，k，d］線性分組碼中，任何兩個碼字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是兩個碼字的內(nèi)積。

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

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

推論3.1.1GF(2)上線性分組碼任3個碼字C1，C2，C3之間的漢明距離，滿足以下三角不等式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］線性分組碼，碼字的重量或全部為偶數(shù)，或者奇數(shù)重量的碼字?jǐn)?shù)等于偶數(shù)重量的碼字?jǐn)?shù)。請讀者自行證明該定理?！?.2碼的一致校驗矩陣與生成矩陣

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

中，如何找出滿足一定要求的，有2k個矢量組成的k維線性子空間Vn，k

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

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

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。由上述線性方程組可知：c3=c6+c4=1+1=0c2=c6+c5+c4=1+0+1=0c1=c6+c5=1+0=1c0=c5+c4=0+1=1由此得到的碼字為：(1010011)。

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

稱上式中的4行7列矩陣為［7，3，4］碼的一致校驗矩陣，通常用H表示，該碼的

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

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

(3.2.5)簡寫為H·CT=0T

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

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

Vn，n-k

。

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

的零空間必然是一個k維子空間Vn

，k

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

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

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

個碼字完全可由k個獨立矢量所組成的基底而張成。設(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)若把這組基底寫成矩陣形式，則有

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］碼中的任何碼字，都可由這組基底的線性組合生成，即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個信息元組成的信息組。因此，若已知信息組m，通過式(3.2.9)可求得相應(yīng)的碼字，稱式(3.2.8)的G為［n，k，d］碼的生成矩陣。

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

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

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

二、對偶碼［n，k，d］碼是n維線性空間中的一個k維子空間Vn，k

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

，n-k

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

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

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

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

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

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

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

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

-1，cn

-2，…，cn

-k

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

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

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

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

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

-k

］(3.2.14)

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

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

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

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

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

如例3.1中的［7，3，4］碼，若挑出第一個信息位均為0的碼字：(0000000)，(0011101)，(0100111)，(0111010)，則可組成一個［6，2，4］縮短碼：(000000)，(011101)，(100111)，(111010)。縮短碼的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比原碼要小，但糾錯能力不一定比原碼強。因此總的看來，縮短碼比原碼的性能要差。

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

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

-1，

cn

-2，…，c1，c0)，通過有擾信道傳輸，信道產(chǎn)生的錯誤圖樣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，都必須滿足式(3.2.6)或式(3.2.7)。因此，收到R后用該兩式之中的任一式進行檢驗：R·HT=(C+E)·HT=C·HT+E·HT=E·HT

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

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

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

式中，hn

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

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

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

從上面分析看出，一個［n，k，d］碼要糾正≤t個錯誤，則要求≤t個錯誤的所有可能組合的錯誤圖樣，都應(yīng)該有不同的伴隨式與之對應(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é)論一個［n，k，d］線性分組碼，若要糾正≤t個錯誤，則其充要條件是H矩陣中任何2t列線性無關(guān)。由于d=2t+1，所以也相當(dāng)于要求H矩陣中d-1列線性無關(guān)。由此結(jié)論可得到以下重要定理。定理3.3.1［n，k，d］線性分組碼有最小距離等于d的充要條件是，H矩陣中任意d-1列線性無關(guān)。證明先證明必要性。即碼有最小距離為d，證明H中的任意d-1列線性無關(guān)。用反證法。若H中某一d-1列線性相關(guān)，則由線性相關(guān)定義可知：ci1hi1+ci2hi2+…+ci(d-1)hi(d-1)=0T式中，cij∈GF(q)，hij是H矩陣的列矢量?，F(xiàn)作一個碼字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是一個碼字，而C的非0分量個數(shù)只有d-1個，這與碼有最小距離為d的假設(shè)相矛盾，故H中的任意d-1列必線性無關(guān)。下面證明：若H中任意d-1列線性無關(guān)，則［n，k，d］碼有最小距離為d。若H中任意d-1列線性無關(guān)，則H中至少需要d列才能線性相關(guān)。我們將能使H中某些d列線性相關(guān)的列的系數(shù)，作為碼字中對應(yīng)的非0分量，而碼字的其余分量均為0，則該碼字至少有d個非0分量，故［n，k，d］碼有最小距離為d。

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

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

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

-k

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

-k

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

定義3.3.1GF(2)上漢明碼的H矩陣的列，是由不全為0，且互不相同的二進制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］漢明碼。這時取m=3，所有23=8個三重為：000，100，010，001，011，101，110，111。挑出其中7個非0的三重構(gòu)成

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

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

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

息

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

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

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

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

［n，k，d］碼的2k

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

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

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

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

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

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

-k

個陪集，把所有2n

個矢量劃分完畢，稱C1，E2，E3，…，

為陪集首。按這種方法構(gòu)成的表稱為標(biāo)準(zhǔn)陣譯碼表，簡稱標(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)生了錯誤譯碼?，F(xiàn)在的問題是：如何劃分陪集使譯碼錯誤概率最??？這歸結(jié)到如何挑選陪集首。因為一個陪集的劃分主要決定于子群，而子群就是2k

個碼字，這已決定，因此余下的問題就是如何決定陪集首。

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

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

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

組中選擇不同的2k

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

，k

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

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

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

例3.4［7，4，3］漢明碼的縮短碼［6，3，3］碼，它的8個碼組，可由式(3.3.7)的G矩陣中去掉第一行和第一列后的G［6,3］中的行線性組合而得到。該碼的標(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，這說明這兩個［6，3］碼均是最佳碼。由該表可以看到，用這種標(biāo)準(zhǔn)陣譯碼，需要把2n

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

表3-4［6，3］碼簡化譯碼表

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

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

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

中球心為碼字C

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

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

-1表中共有2k

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

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

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

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

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

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

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

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

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

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

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

-1，cn

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

-1+cn

-2+…+c1+c0+c′0=0(3.5.1)稱c′0為全校驗位。

若原碼的校驗矩陣為H，則擴展碼的校驗矩陣為

［2m-1，2m-1-m，3］漢明碼的擴展碼是［2m，2m-1-m，4］碼，它的中的H是漢明碼的校驗矩陣。

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

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