第三章線性分組碼

第四章線性分組碼第四章

4.1線性分組碼基本概念

4.2生成矩陣和校驗矩陣

4.3伴隨式與譯碼

4.4碼的糾、檢錯能力與MDC碼

4.5完備碼與漢明碼

4.6擴展碼、縮短碼與刪信碼

4.7分組碼的性能限

（n,k）線性分組碼是把信息流的每k個碼元（symbol）分成一組，通過線性變換，映射成由n個碼元組成的碼字（codeword）。從空間的角度，每個碼字可以看成是n維線性空間中的一個矢量，n個碼元正是n

個矢量元素。碼元取自字符集X={當q=2時是二進制碼，q>2時是q進制（q元）碼。多進制q一般取素數(shù)或素數(shù)的冪次，實用中多見的是q=3或q=(b是正整數(shù))。當q=時，每碼元可攜帶bbit

信息，長度為n的q元分組碼碼字可以映射成長度N=bn的二元分組碼碼字。糾錯編碼的任務是在n維n重矢量空間的種組合中選擇個構(gòu)成一個子空間，或稱許用碼碼集C，然后設法將k比特信息組一一對應的映射到許用碼碼集C。不同的編碼算法對應不同的碼集C以及不同的映射算法，把這樣的碼稱為(n,k)線性分組碼。不編碼時，一個二進制碼元可攜帶1b信息（傳輸率為1b/符號）；編碼后，n個二進制碼元攜帶kb信息（傳輸率為（k/n）b/符號）。定義k/n=為二元分組碼的碼率，或者說是效率。4.1線性分組碼基本概念綜上所述，編碼算法的核心問題是：

①尋找最佳的碼空間，或者等效地說，尋找最佳的一組（k個）基底，以張成一個碼空間。

②k維k重信息組空間的個矢量以何種算法一一對應的映射到k維n

重碼空間C。

由于上述映射是兩個線性空間之間的線性交換，“線性分組碼”由此得名。又因為這些矢量在加法運算下構(gòu)成交換群，所以也稱之為“群碼”。返回4.1線性分組碼基本概念在討論生成矩陣之前，先看一個例題。例4.1（6，3）二進制分組碼的輸入信息組是m=(),碼組輸出是c=()。已知輸入、輸出碼元之間的關(guān)系式是，求碼集

C以及編碼時的映射算法。解：將關(guān)系式列成線性方程組，然后寫成矩陣形式如下：4.2生成矩陣和校驗矩陣二進制碼取值于GF(2),6位二進制有=64種組合，而3位的信息組只有8種組合，一一對應到8個碼字。可見，碼集C包含64種組合中的8種。分別令信息組為（000），（001），…，（111），帶入上面的矩陣算式，不難算得各信息組對應的碼字如下表所示：信息組()碼字（)0000000000000010110100101100110111011001001111011011001101100011111110104.2生成矩陣和校驗矩陣在以上編碼過程中，核心的因素是矩陣G，它決定了變換規(guī)則，也決定了碼集C。矩陣G可以看成是由3個行矢量組成的，所有碼字是這3個行矢量的線性組合：

可以驗證，這里的3個行矢量線性無關(guān)，可以作為基底張成一個三維6重的碼空間，該空間是六維6重空間的子空間。從上例得到的啟示是：碼集其實是一個子空間，只要找到一組合適的基底，它們的線性組合就能產(chǎn)生整個碼集。不失一般性，C也可以擴展為k維n重碼空間,即：

c=[]=mG=式中，G稱為該碼的生成矩陣，是k行n列矩陣：4.2生成矩陣和校驗矩陣4.2生成矩陣和校驗矩陣

其中,i=k-1,,0,是G中第i行的行矢量。與任何一個（n,k）線性碼的碼空間C相對應，一定存在一個對偶空間D。事實上，碼空間基底數(shù)k只是n維n重空間的全部n個基底的一部分，若能找出另外n-k個基底，也就找到了對偶空間D。既然用K個基底能產(chǎn)生一個（n-k）線性碼，那么也能用n-k個基底產(chǎn)生一個有個碼矢的（n,n-k）線性碼，稱之為（n-k）線性碼的對偶碼。將D空間的n-k個基底排列起來，可構(gòu)成一個（n-k）n矩陣，稱為碼空間C的校驗矩陣

H，它正是（n,n-k）對偶碼的生成矩陣，它的每一行是對偶碼的一個碼字。C和D的對偶是相互的，G和C的生成矩陣，又是D的校驗矩陣；而H

是D的生成矩陣，又是C的校驗矩陣。

由于C的基底和D的基底正交，空間C和空間D也正交，它們互為零空間。因此，（n-k）線性碼的任意碼字c一定正交于其對偶碼的任意一個碼字，也必定正交于校驗矩陣H的任意一個行矢量，即

式中，0代表零陣，它是全零矢量。式可以用來檢驗一個n重矢量是否為碼字：若等式成立（得零矢量），該n重必為碼字，否則必不是碼字。

由于生成矩陣的每個行矢量都是一個碼字，因此必有：

這里，0代表一個尺寸為的零矩陣。驗證H的方法是看它的行矢量是否與G的行矢量正交，即式是否成立。此處，

式中，兩個相同的矩陣模2加后為全零矩陣。這就證明了H確實校驗矩陣。4.2生成矩陣和校驗矩陣例4.2考慮一個（7，4）碼，其生成矩陣是：

①對于信息組m=(1011),編出的碼字是什么？

②畫一個（7，4）分組碼編碼器原理圖。

③若接收到一個7位碼r=(1001101),檢驗它是否碼字？解：設輸入信息組，編碼后的碼字碼集C。

①由c=mG可知，將m和G的值代入，可得對應碼字是（1011000）。本題由于是系統(tǒng)碼

，，前4位不必計算，后3個校驗位可以根據(jù)生成矩陣G的分塊陣P列出現(xiàn)行方程組如下4.2生成矩陣和校驗矩陣將代入方程組，得。所以碼字為c=[1011000]。

②一個二進制（n,k）系統(tǒng)線性分組碼的編碼器可用k級移存器和連接到移存器適當位置（由P決定）的n-k個模2加法器組成。加法器生成校驗位后按順序暫存在另一個長度為n-k的移存器。K比特信息組移位輸進k級移存器，加法器計算n-k校驗比特，然后先是k位信息、緊接著是n-k位校驗比特從兩個移存器中移位輸出。本題的編碼原理圖如下：

4.2生成矩陣和校驗矩陣首先是信息位輸入，再是，，順序輸入。編碼后，開關(guān)S在輸出前4位時上撥，先再~順序輸出；輸出后面3

位時，開關(guān)S下?lián)?，將~順序輸出。

③H矩陣如下：根據(jù)式，如果接受到的r是屬于碼集C的某碼字，必有；反之，如，說明r必定不是碼字。將H和

r=[1001101]代入式，得：

說明r與H不正交，接收的r=(1001101)不是碼字。返回

4.2生成矩陣和校驗矩陣由于信道干擾的緣故，使得接收端的接受碼R=不一定等于發(fā)送碼C=,定義差錯圖案E為：

E==R-C

差錯圖案是信道干擾圖案的反應。對二進制碼，模2加與模2減等同，因此有：

E=R+C及R=C+E

利用式所示碼字與校驗矩陣的正交性,可通過下列運算來判斷接受碼R是否有錯：

如果接受碼無誤，必有R=C即E=0及=0,此時上式滿足

=0。如果信道產(chǎn)生差錯，必有=0。保持不變，則僅與差錯圖案E有關(guān)，而與發(fā)送什么碼C無關(guān)。為此定義伴隨式S為：

4.3伴隨式與譯碼從物理意義看，伴隨式S并不反映發(fā)送的碼字是什么，而只反應信道對碼字造成怎樣的干擾?？梢钥吹剑喊殡S式S是一個n-k重矢量，只有種可能的組合；而差錯圖案E是n重矢量，共有個可能的組合。因此，同一伴隨式可能對應若干個不同的差錯圖案。在接受端，并不知道發(fā)送碼C究竟是什么，但可以知道和接受碼

R，從而算出S。譯碼最重要的任務是從伴隨式S找出C的估值，具體方法是：先算出S，再由S算出E，最后令=R+E而求出：

=SE=R+E

最關(guān)鍵的是從S找出E,只要E正確，譯出的碼也就是正確的。展開成線性方程組形式后：4.3伴隨式與譯碼

會發(fā)現(xiàn)很難解，所以這里提供了在一般情況下構(gòu)造標準陣列譯碼表的方法。（1）第一步：用概率譯碼確定各伴隨式對應的差錯圖案（2）第二步：確定標準陣列譯碼表的第一列和第一行（3）第三步：在碼表的第j行第i列填入

4.3伴隨式與譯碼例4.3某一個（5，2）系統(tǒng)線性碼的生成矩陣

,設接收碼R=(10101),請先構(gòu)造該碼的標準陣列譯碼表，然后譯出發(fā)送碼的估值。解：分別以信息組m=（00），（01），（11）及已知的G代入式：，求得4個許用碼字為。由式求得校驗矩陣為：4.3伴隨式與譯碼展開后得：

伴隨式有8種組合；而差錯圖案除了代表無差錯的全零圖案外，代表一個差錯的圖案有5種，代表兩個差錯的圖案有10種。要把8個伴隨式對應到8個最輕的差錯圖案，無疑先應選擇全零差錯圖案和5種一個差錯的圖案。剩下的兩個伴隨式不得不在10種兩個差錯的圖案中選取兩個。先將

代入上面的線性方程組，解得對應的分別是（000），（111），（101），（100），（010），（001）。剩下的兩個伴隨式是（011）和（110），每個有

種解，對應有個差錯圖案。本例中，伴隨式（011）的4個解（差錯圖案）是（00011），（10100），（01110），（11001），其中（00011）和（10100）并列最小重量，只能選擇其中之一作為解。4.3伴隨式與譯碼

至此，根據(jù)4個碼字和8個差錯圖案，畫出標準陣列譯碼表如下所示：

=000=00000=10111=01101=11010

=111=10000001111110101010=101=01000111110010110010=100=00100100110100111110=010=00010101010111111000=001=00001101100110011011=011=00011101000111011001=110=001101000101011111004.3伴隨式與譯碼若接收碼R=(10101)，可用以下三種方法之一譯碼。

①直接搜索碼表，查得（10101)所在列的子集頭是（10111），因此取譯碼輸出為（10111）。

②可以先求伴隨式，找到伴隨式所在行數(shù)，再搜索碼表的第5行找到（10101），最后順著該列向上找出碼字（10111）③先求出伴隨式，在表中查出對應的陪首集（差錯圖案）=（00010），再將陪集首與接收碼相加，得到碼字C=R+=(10101)+(00010)=(10111)。返回

4.3伴隨式與譯碼4.4碼的糾、檢錯能力與MDC碼例4.3的（5，2）分組碼中，如果碼字有一位誤碼，譯碼后該差錯能被糾正；如果有兩位誤碼，可以檢測出差錯的存在，但不一定能糾正它。顯然，任何一種信道編碼的糾、檢錯能力都有一定的限度，這種限度與碼距有關(guān)的。為此，有必要引入相關(guān)的定義和定理，適用于GF(2)域。

①漢明重量：n重矢量R中。非零元素的個數(shù)稱為n重的漢明重量，簡稱重量，用w(R)表示。②漢明距離：逐位比較兩個n重矢量和的對應各位，其中取值不同的元素的個數(shù)為與德漢明距離，用表示。③最小距離：分組碼碼集中，每兩兩碼字之間都存在一定距離，其中最小者稱為該分組碼的最小距離，用符號表示。如直接計算最小距離，含個碼字的碼集需計算個距離后才能找出。由于分組碼是群碼，利用群的封閉性，即兩個碼字之和仍是碼字，可得：于是得以下定理。

定理4.1線性分組碼的最小距離等于碼集中非零碼字的最小重量，即及距離和重量除了上述關(guān)系外，還滿足以下兩個不等式：這里采用符號R，是強調(diào)上面兩式適用于一切n重矢量，而不限于碼字。4.4碼的糾、檢錯能力與MDC碼定理4.2對于任何最小距離為的線性分組碼，其檢測隨機差錯的能力為。定理4.3對于任何最小距離等于的線性分組碼，其糾正隨機差錯的能力t為：式中，INT[.]表示取整。定理4.4（n,k）線性分組碼的最小距離等于充要條件是：校驗矩陣H中有列線性無關(guān)。定理4.5（n,k）線性分組碼的最小距離必定小于等于n-k+1,即

返回4.4碼的糾、檢錯能力與MDC碼4.5完備碼與漢明碼

4.5.1完備碼

4.5.2漢明碼

4.5.3高萊碼

返回4.5.1完備碼

二元（n,k)線性分組碼的伴隨式是一個n-k重矢量，有個可能的組合。如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應有惟一的伴隨式組合與之對應，才有可能實行糾錯譯碼。也就是說，伴隨式組合的數(shù)目必須滿足條件：

這個條件稱為漢明眼。任何一個糾t碼都應滿足漢明眼。

如果某二元（n,k）線性分組碼能使上式的等號成立，即該碼的伴隨式組合數(shù)目恰好和不大于t個差錯的圖案數(shù)目相等，相當于在標準陣列中能將所有重量不大于t的差錯圖案實現(xiàn)一一對應，嬌艷位得到最充分的利用。把滿足方程：

的二元（n,k）線性分組碼成為完備碼（PerfectCode）。迄今發(fā)現(xiàn)的二進制完備碼有t=1的漢明碼、t=2德（23，12，7）高萊（Golay）碼，以及長度n為奇數(shù)、由兩個碼字組成且滿足

=n的任何二進制（n,1）碼。已發(fā)現(xiàn)三進制完備碼有t=2的（11，6，5）高萊碼。返回4.5.1完備碼糾錯能力t=1的完備碼稱為漢明碼（HammingCode）。漢明碼的校驗矩陣H具有特殊的性質(zhì)，使得能以相對簡單的方法來構(gòu)造碼。例4.4構(gòu)造一個m=3的二元（7，4）漢明碼。解：由題知，就是求出它的生成矩陣或它的校驗矩陣。由于（7，4）漢明碼的校驗矩陣是3*7矩陣，而校驗矩陣的行矢量不能為全零（零與任何碼元的乘積為零，失去校驗功能），因此H的7個行矢量正好是除全零矢量外3重矢量的全部可能組合。H不是惟一的，由于交換列不會影響最小距離，所以可通過列置換將最初的H變?yōu)橄到y(tǒng)形式的H，稱為系統(tǒng)漢明碼：得系統(tǒng)漢明碼的生成矩陣G為：4.5.2漢明碼得系統(tǒng)漢明碼的生成矩陣G為：

上列中校驗矩陣的構(gòu)成方法具有一般性。由于H是（n-k）*n矩陣，可以看成由n個n-k重矢量構(gòu)成。這樣的行矢量除去全零后有-1中可能的組合，由=1+n知正好等于碼長n。返回

4.5.2漢明碼4.5.3高萊碼高萊碼（Golay）是二進制（23，12）線性碼，其最小距離

=7，糾錯能力t=3。

由于滿足

它也是完備碼。在（23，12）碼上添加一位奇偶位即得二進制（24，

12）擴展高萊碼，其最小距離=8。必須指出，從伴隨式與差錯圖案關(guān)系的角度來看，完備碼是“好碼”，是標準陣列最規(guī)則，因而譯碼最簡單的碼，但它并不一定是糾錯能力最強的碼。完備碼強調(diào)了n,k和t的關(guān)系，保證至少等于3（即t-1），但并未強調(diào)

最大化，即達到極大最小局里碼MDC中的程度。換言之，完備碼未必是MDC碼。比如，（63，57）漢明碼可保證t=1,而按

MDC碼的要求應有t=INT[(63-57+1)/2]=3,這才達到了極限糾錯能力。

返回

4.6擴展碼、縮短碼與刪信碼4.6.1擴展碼4.6.2縮短碼4.6.3刪信碼

返回4.6.1擴展碼如果給（n,k）分組碼添加一個奇偶校驗位，可得一個（n+1,k）擴展碼。由于信息位k沒變，碼集包含的碼字總數(shù)也不會變，只不過每個碼字的長度增加1。對于碼字，擴展后變?yōu)槿舨捎门夹ｒ?，校驗位的選擇應滿足校驗方程：

從校驗矩陣的角度看，擴展前校驗矩陣是（n-k）*n矩陣H，擴展后的校驗矩陣為（n-k+1）*（n+1）矩陣，多出了1行1列。

從最小距離角度看，若擴展前原碼的最小距離是奇數(shù)，即最輕碼字中包含奇數(shù)個1，則擴展后最輕碼字的碼重加1，擴展碼的最小距離因此比原來增加1，變成

+1；若原碼的最小距離是偶數(shù)，則偶校驗不改變其最小距離。返回4.6.2縮短碼碼字中的每個碼元都是信息元的線性組合。在生成矩陣一定的條件下，由于信息組中0與1結(jié)構(gòu)對稱、奇偶性對稱，因此在二進制

(n,k,)分組碼的個碼字中總有一半碼字(個)的第一位為0，而另一半碼字的第一位為1。在第一位為0的碼字中，又有一半碼字(個)得下一位為0，而另一半為1，以此類推。于是，若把第一位為0的

個碼字拿出來，去掉第一位的0，就縮短為長度為n-1的矢量。由于縮短時去掉的碼字第一位的0，對碼重沒有影響，因此這個(n-1,k-1)縮短碼的最小距離仍然是，稱為(n-1,k-1,)縮短碼。同樣，可得縮短碼為

從生成的角度看，去掉信息組和碼組的第一位，相當于去掉生成矩陣的第1行和第1列。若縮短前的生成矩陣是k*n矩陣，則去掉最上邊i行和最左邊后剩下的(k-i)*(n-i)矩陣就是縮短碼的生成矩陣校驗矩陣與原校驗矩陣H相比，行數(shù)不變，只是去掉了H矩陣左邊i列，由(n-k)*n矩陣變?yōu)?n-k)*(n-i)矩陣。

由于(k-i)/(n-i)<k/n，縮短碼的碼率總是比原碼小。返回4.6.3刪信碼

在二進制(n,k)分組碼的個碼字中，挑出碼重為偶數(shù)的那一半碼字，共個，組成一個新的碼集，這就是(n,k-1)刪信碼。取名刪信碼，是因為碼長n不變而信息位少1，相當于將一個信息位轉(zhuǎn)變?yōu)榕夹ｒ炍皇褂昧?，所以又稱之為增余刪信碼。從校驗矩陣的角度看，若原校驗矩陣是(n-k)*n矩陣H，則刪信碼的校驗矩陣為(n-k+1)*n矩陣，比原校驗矩陣多出了1行，形式是：

如果原碼的最小距離是奇數(shù)d，則刪信加上偶校驗后最小距離為1，成為偶數(shù)d+1。另一種情況，如果原碼的最小距離是偶數(shù)d，則刪信并加偶校驗后最小距離不變。返回

4.7分組碼的性能限