《編碼理論》課件第8章

第8章卷積碼和其他糾錯碼

8.1卷積碼8.2秩距離碼8.3突發(fā)錯誤的糾正8.4級聯(lián)碼及交織碼8.5

Turbo碼 8.1卷積碼

8.1.1離散卷積表述

分組碼和卷積碼兩者主要差異在于卷積碼編碼器在任意給定的時段，編碼器的n0個輸出不僅與此時段的k0個輸入有關(guān)，而且也與前m0個輸入(記憶器件中存儲的)有關(guān)。因此卷積碼一般可采用(n0，k0，m0)來表示，其中k0為輸入碼元數(shù)，n0為輸出碼元數(shù)，而m0則為編碼器的存儲器數(shù)。典型的卷積碼一般選n0和k0(k0<n0)值較小，但存儲器m0可取較大值(m0<10)，以獲得既簡單又高性能的信道編碼。卷積碼的編碼器是由一個有k0個輸入端、n0個輸出端，且具有m0節(jié)移位寄存器所構(gòu)成的有限狀態(tài)的有記憶系統(tǒng)，通常稱它為時序網(wǎng)絡。

描述這類時序網(wǎng)絡的方法很多，它大致可分為兩大類型，解析表示法與圖形表示法。在解析法中又可分為離散卷積法、生成矩陣法、碼多項式法等；在圖形表示法中也可分為狀態(tài)圖法、樹圖法、格圖法等。描述卷積碼編譯碼的過程，可以用不同的描述方法，如矩陣法、碼樹法、狀態(tài)圖法和籬狀圖法等。采用何種方法與卷積碼的譯碼方法有很大關(guān)系。例如，在代數(shù)譯碼時，用矩陣法對譯碼原理的敘述和理解較方便。而借助樹碼和籬狀圖能更為清晰地分析和了解概率譯碼的過程和碼的性能。卷積碼(n0，k0，m0)在任何一段規(guī)定時間內(nèi)編碼器產(chǎn)生的n0個碼元，不僅取決于這段時間中的k0個信息碼元，而且還取決于前m0段規(guī)定時間內(nèi)的信息碼元，設N=m0+1,編碼過程中相互關(guān)聯(lián)的碼元為Nn0個。它表明編碼過程中互相約束的碼元數(shù)，這時，監(jiān)督位監(jiān)督著這N段時間內(nèi)的信息。這N段時間內(nèi)的碼元數(shù)目Nn0稱為這種卷積碼的約束長度。其編碼效率為R＝k0/n0。

設卷積碼編碼器輸入碼序列（待編碼的信息序列）為U＝u0(1)u0(2)…u0（k0）u1(1)u1(2)…u1(k0)…us(1)us(2)…us(k0)…設編碼器輸出碼序列為C＝c0(1)c0(2)…c0(n0)c1(1)c1(2)…c1(n0)…cs(1)cs(2)…cs(n0)…則編碼器輸出碼序列中任一子碼可以由如下卷積關(guān)系給出：（j＝1，2，…，n0）(8－1)式中：g(i，j)——非系統(tǒng)卷積碼的生成序列。系統(tǒng)卷積碼的碼序列中任一子碼Cs

，也是有n0個碼元，其前k0位與待編碼的信息序列中的第s信息組us(i)相同，而后n0-k0位監(jiān)督元由生成序列生成。由于每個碼中的前k0位就是此時刻待編碼的k0位信息元，所以在生成序列g(shù)(i,j)中有k0×k0個生成序列是固定的，即:只有k0×(n0-k0)個生成序列需要給定,以便確定每個子碼中n0-k0個監(jiān)督元,則碼字:cs(j)＝us（i）；(i＝j＝1，2，…，k0)(j＝k0＋1，…，n0)（8－2）式中：g(i，j)——系統(tǒng)卷積碼的生成序列。

【例8－1】已知(3，1，2）系統(tǒng)卷積碼的生成序列為：g（1，1）＝[100]g（1，2）＝[g0（1，2）g1（1，2）g2（1，2）]＝[100]g（1，3）＝[g0（1，3）g1（1，3）g2（1，3）]＝[101]其任一子碼為:cs（1）＝us（1）【例8－2】已知（3，2，2）系統(tǒng)卷積碼的生成系列為：

g（1，3）＝[g0（1，3）g1（1，3）g2（1，3）]＝[101]

g（2，3）＝[g0（2，3）g1（2，3）g2（2，3）]＝[110]

該碼的任一子碼Cs中前兩位與us（1）、us（2）相同，而后一位的監(jiān)督元由式（8-2）確定,即

cs(1)＝us(1)

cs(2)＝us(2)8.1.2矩陣表述

類似(n，k)線性分組碼，卷積碼也用生成矩陣和監(jiān)督矩陣來描述。對于任意一個(n0,k0,m0)卷積碼，其生成矩陣G∞是一個半無限矩陣，即（8－3）

【例8－3】設(3，1，2)卷積碼的生成子矩陣求:（1）卷積碼的生成矩陣G∞。（2）若輸入信息序列U=［1011010100…］，求卷積碼的輸出碼字序列。

解已知基本生成矩陣 則(3，1，2)卷積碼的生成矩陣G∞為當已知卷積碼的生成矩陣G∞時，進行C=UG∞運算即可實現(xiàn)編碼。當輸入信息序列為U=［1011010100…］時，(3，1，2)卷積碼的輸出碼字序列為=[111010110101011…]

【例8－4】設(3，2，1)卷積碼生成子矩陣分別為：

求:（1）卷積碼的生成矩陣G∞。（2）若輸入信息序列U=［1011010100…］，求卷積碼的輸出碼字序列。

解該碼的基本生成矩陣 ，則(3，2，1)卷積碼的生成矩陣為當輸入信息序列為U=［1011010100…］時，(3，2，1)卷積碼輸出碼字序列為即

以上兩個卷積碼的碼字序列中，各子碼都具有系統(tǒng)碼的特征。例如(3，2，1)卷積碼的碼字序列=101110010011001…中，每個子碼的前兩位就是輸入信息序列U中的對應信息組11010100…。

由卷積碼的定義可知，(n0，k0，m0)碼的任意N個連續(xù)的子碼之間有著相同的約束關(guān)系，此外，在卷積碼的代數(shù)譯碼中，也只考慮一個編碼約束長度內(nèi)的碼序列。所以，不失一般性，只考慮編碼器初始狀態(tài)全為0時，編碼器輸入N個信息組，即N.k0個信息元后，編碼器輸出的首N個子碼，即Nn0個碼元之間的約束關(guān)系即可，這首N個子碼組成的碼組稱為卷積碼的初始截短碼組C，即：（8－5）式中：Ci＝ci(1)ci(2)…ci(n0)(i＝0，1，2，…，m0)。根據(jù)初始截短碼組的定義，C可以表示成矩陣方程：C＝UG

（8－6）式中:U＝[U0U1U2…],且Ui＝ui(1)ui(2)…ui(k0),i＝0,1,2,…,m0；（8-7）稱G為初始截短碼組的生成矩陣，相應的基本生成矩陣g為：

在系統(tǒng)碼條件下，由于k0k0個生成序列是已知的，即當i＝j時，g(i，j)＝1；當ij時，g(i，j)＝0，i＝1，2，…，k0；j＝1，2，…，k0。且每個子碼中的前k0個碼元與相應的k0個信息元相同。而后n0—k0個監(jiān)督元則由信息序列與生成序列的卷積運算得到(見式(8-2)。由此可知，系統(tǒng)碼的初始截短碼組的Nk0Nn0生成矩陣為（8-9）（8-10）系統(tǒng)卷積碼初始截短碼組的基本生成陣為：(8-11)[例8-5](3，1，2)系統(tǒng)碼的生成序列為：它的初始截短碼組的基本生成矩陣是=[111010001]生成矩陣為若設U＝[u0(1)u1(1)u2(1)]＝[101]，則初始截短碼組C為C＝UG＝[111010llO](n0，k0，m0)碼的基本監(jiān)督矩陣為(8-12)式中：h－(n0—k0)n0N階矩陣。(n0，k0，m0)碼的監(jiān)督矩陣：(8-13)式中：Ｈ－(n0—k0)N×n0N階矩陣。由以上關(guān)于生成矩陣G，監(jiān)督矩陣H的討論可以看到，它們與碼的生成序列g(shù)(i，j)有密切的聯(lián)系，只不過是以矩陣的方式描述了卷積碼的卷積關(guān)系式(8-1)或(8-2)。所以，在卷積碼的應用中，經(jīng)常是給定碼的g(i，j)，有了生成序列g(shù)(i,j)后，就可以確定卷積碼的編碼電路及其矩陣表示式。

[例8-6]設(3，1，2)系統(tǒng)碼的生成序列：

g(1,1)＝1

g(1,2)＝[g0(1,2)g1(1,2)g2(1,2)]

g(1,3)＝[g0(1,3)g1(1,3)g2(1,3)]

求該碼的監(jiān)督矩陣？

解：由式（8-13）得(3，1，2)碼的監(jiān)督矩陣為：也可以得到如下矩陣方程：CT＝0T

其中：CT

－初始截短碼組的轉(zhuǎn)置，C＝[c0(1)c0(2)c0(3)c1(1)

c1(2)c1(3)

c2(1)c2(2)c2(3)]；0T－是一個6×1階全0陣；它的基本監(jiān)督陣是一個2×9階陣，即：則

編碼后輸出n0個多項式，分別代表并行輸出的門路碼元信號。最后經(jīng)并／串變換，n0路編碼信號合為一路輸出，碼多項式為C(D)，如圖8-1所示。圖8-1卷積碼的轉(zhuǎn)移函數(shù)矩陣卷積編碼器可視做一個k0端入口、n0端出口的線性多端口網(wǎng)絡。網(wǎng)絡理論可以用轉(zhuǎn)移函數(shù)矩陣來描述卷積編碼器的輸入/輸出關(guān)系。所不同的是這里的輸入、輸出均是多項式，因此相應的轉(zhuǎn)移函數(shù)矩陣也是由多項式元素構(gòu)成的多項式矩陣。

若定義多項式并行輸入矩陣、輸出矩陣為：(8-14)（8-15）

這里，Up(D)，Cp(D)的下標p表示它們是U(D)，C(D)的并行形式，雖然U(D)和在數(shù)量上有對應關(guān)系，然而在數(shù)學表達上不能等同。

編碼系統(tǒng)k0路輸入、n0路輸出的轉(zhuǎn)移關(guān)系(即編碼關(guān)系)可寫成：（8－16）G(D)是k0×n0多項式矩陣，稱為轉(zhuǎn)移函數(shù)矩陣，即（8－17）其中:由式（8-17）和（8-18）可知，第j個支路的輸出是所有輸入支路對它影響的總和，即：（8-19）最后，利用并／串變換公式將n個輸出多項式合并成一個多項式：（8－20）[例8-7]

二進制(3，1，2)卷積生成序列如果輸入信息流是101101011100…，求輸出碼字序列。

解:本題為1路輸入、3路輸出，因此轉(zhuǎn)移函數(shù)矩陣是13的多項式矩陣。1路輸入由（8-17）得卷積編碼器的轉(zhuǎn)移函數(shù)矩陣：由（8-19）得它們的系數(shù)序列分別是：利用并／串變換，即從左上角開始按列的順序送出，得輸出序列為：或者利用公式(8-20)化為多項式形式：其系數(shù)正是輸出碼元序列。[例8-8]某二進制(3，2，1)卷積生成序列：如輸入信息流是 ，求輸出碼字序列。解：本題為兩路輸入、三路輸出，因此轉(zhuǎn)移函數(shù)矩陣是23的多項式矩陣。原輸入為輸入序列經(jīng)串／并變換后分成兩個并行輸入，則該卷積編碼器的轉(zhuǎn)移函數(shù)矩陣是：由式(8-19)得：它們的系數(shù)序列分別是：利用并／串變換，即從左上角開始按列的順序送出，得輸出序列為：或者利用公式(8-20)化為多項式形式：其系數(shù)正是輸出碼元序列。[例8-8]某二進制(3，2，1)卷積生成序列：如輸入信息流是，求輸出碼字序列。

解：本題為兩路輸入、三路輸出，因此轉(zhuǎn)移函數(shù)矩陣是23的多項式矩陣。原輸入為輸入序列經(jīng)串／并變換后分成兩個并行輸入，則該卷積編碼器的轉(zhuǎn)移函數(shù)矩陣是：由式(8-19)得：利用公式(8-20)并／串變換得其系數(shù)正是輸出碼元序列：101001000111010011…。8.1.4卷積碼的編碼

1．串行輸入、串行輸出的編碼電路。

構(gòu)造這種類型編碼電路的基礎是式(8-1)和(8-2)。根據(jù)式(8-1)構(gòu)造的是非系統(tǒng)編碼器，而式(8-2)則是系統(tǒng)碼編碼電路的依據(jù)。圖8-2所示的是(n0，k0，m0)非系統(tǒng)卷積碼的串行編碼電路，圖8-3是系統(tǒng)碼的編碼電路。圖8-2(n0，k0，m0)非系統(tǒng)碼卷積碼串行編碼電路圖8-3(n0，k0，m0)系統(tǒng)碼卷積碼串行編碼電路圖8-4（2，1，3）碼編碼電路

該式表明任一時刻編碼器的輸出可以由信息元與生成序列的離散卷積運算求出。這就是卷積碼名稱的由來。設則編碼器的兩個輸出端的序列分別為：而碼序列C為

【例8－10】二進制(3，1，2)卷積生成序列為：要求畫出對應的編碼器。解：編碼電路如圖8-5所示。圖8－5二元(3,1,2)卷積編碼電路[例8-11]二進制(3，2，1)卷積生成序列：要求畫出對應的編碼器？

解：編碼電路如圖8-6所示。圖8-6二元(3,2，1)卷積編碼電路

2．(n0—k0)m0級移位寄存器構(gòu)成的并行編碼電路

(n0—k0)m0這是系統(tǒng)碼形式的一種編碼電路，又稱I型編碼電路。將式(8-2)展開后可以改寫成如下形式:cs(j)＝us(i),

j＝i＝1,2,…,k0

j=k0+1,…,n0

(8-21)式(8-21)表明，在并入并出方式下，為了獲得第s個子碼的(n0—k0)個監(jiān)督元，需要(n0—k0)個移位寄存器組，每一組移位寄存器的數(shù)目為m0級。它們根據(jù)生成序列g(shù)(i，j)所確定的關(guān)系存儲了第s個信息組相鄰的前m0個信息組。(n0，k0，m0)碼Ⅰ型編碼電路如圖8-7所示。圖8－7

(n0，k0，m0)碼Ⅰ型編碼電路式中：j＝k0＋1，…,n0。由式(8－22)可見，只需將第s時刻的k0個信息元與前m0個時刻的諸信息元按生成序列所確定的關(guān)系模2相加，就可以得到此時此刻的n0-k0個監(jiān)督元。Ⅱ型編碼電路由k0個移位寄存器組構(gòu)成，每一組有m0級移位寄存器，它們分別寄存了前m0時刻進入編碼器的第一個到第k0個信息元。(n0，k0，m0)碼Ⅱ型編碼電路如圖8－8所示。圖8－8

(n0，k0，m0)碼Ⅱ型編碼電路8.1.5狀態(tài)流圖

以上的卷積碼描述方法將矩陣、多項式與編碼器結(jié)構(gòu)的關(guān)系揭示得清清楚楚，但并沒能揭示卷積碼的內(nèi)在特性。在這一點上，狀態(tài)圖和網(wǎng)格圖提供了很好的描述工具。

卷積編碼器在i時刻編出的碼字不僅取決于本時刻的輸入信息組，而且取決于i之前存入記憶陣列的個信息組，換言之，取決于記憶陣列的內(nèi)容，稱之為編碼器的狀態(tài)。如圖8-5所示的卷積編碼器中，除本時刻的輸入外還有兩個存儲器存放i—1和i—2時刻的輸入，即和內(nèi)容，其內(nèi)容的組合有四種可能，即00，01，10和11，就說這種編碼器有四個狀態(tài)。更一般地，移存器陣列分割成兩塊，（8-23）式中：(8－24)編碼矩陣第i行第j列的元素表示由狀態(tài)轉(zhuǎn)移到下一狀態(tài)時發(fā)送的碼字，矩陣元素“．”說明這種狀態(tài)轉(zhuǎn)移是不可能事件。比如從狀態(tài)轉(zhuǎn)移到下一狀態(tài)就不可能，因為輸入比特(狀態(tài)機觸發(fā)信號)只有0或1兩種，對應的轉(zhuǎn)移也只能有兩種。從編碼矩陣看出，狀態(tài)只能轉(zhuǎn)移到狀態(tài)或。

(3，1，2)卷積碼的狀態(tài)流圖如圖8-9所示。圖8-9（3，1，2）卷積碼狀態(tài)流圖圖中圓圈代表狀態(tài)節(jié)點，因需標注狀態(tài)號，所以沒有像一般的信號流圖那樣用一個黑點表示節(jié)點。箭頭代表轉(zhuǎn)移，與箭頭對應的標注，比如0／010，表示輸入信息0時的編出碼字010。每個狀態(tài)都有兩個箭頭發(fā)出，對應輸入分別是0，1兩種情況下的轉(zhuǎn)移路徑。假如輸入信息序列是1011010111…，從狀態(tài)流圖可以輕易地找到輸入／輸出和狀態(tài)的轉(zhuǎn)移關(guān)系?？蓮臓顟B(tài)出發(fā)，根據(jù)輸入找到相應箭頭，隨箭頭在狀態(tài)流圖上移動，得到以下結(jié)果：

【例8－13】某二進制(3，2，1)卷積編碼器電路如圖8－6所示，試分別用編碼矩陣和狀態(tài)流圖來描述該碼。如果輸入信息流是101101011100，求輸出碼字序列。

解圖8－6所示的編碼器有2路輸入、3路輸出，2個移存器、4種狀態(tài)。由于i時刻并行輸入2b，相當于有限狀態(tài)機的觸發(fā)信號由2b組成，所以從某一狀態(tài)出發(fā)，下一個狀態(tài)可以是4種狀態(tài)之一，則(3，2，1)卷積編碼器的編碼矩陣為由上可知其狀態(tài)流圖如圖8－10。若初始狀態(tài)是S0，則將輸入序列劃分成2b組(10，11，01，01，11，00，…)。

在圖8－10所示的狀態(tài)流圖中，根據(jù)2bit輸入信息組尋找其狀態(tài)轉(zhuǎn)移路徑，并確定轉(zhuǎn)移過程中發(fā)出的碼字序列，可得到如下轉(zhuǎn)移：可見，碼字序列為（101，001，000，111，010，011，…）。圖8-10（3，2，1）卷積碼狀態(tài)流圖8.1.6網(wǎng)格圖

狀態(tài)流圖展示了狀態(tài)轉(zhuǎn)移的去向，但不能記錄狀態(tài)轉(zhuǎn)移的軌跡。網(wǎng)格圖(或稱格柵圖)可以彌補這一缺陷。它可以將狀態(tài)轉(zhuǎn)移展開在時間軸上，使編碼的全過程躍然紙上，是分析卷積碼的有力工具。網(wǎng)格圖以狀態(tài)為縱軸，以時間(抽樣周期T)為橫軸，將平面分割成格狀。狀態(tài)和狀態(tài)轉(zhuǎn)移的定義畫法與流圖法一樣，也是用一個箭頭表示轉(zhuǎn)移，伴隨轉(zhuǎn)移的表示轉(zhuǎn)移發(fā)生時的輸入信息組／輸出碼組。所不同的是，網(wǎng)格圖還體現(xiàn)時間的變化，一次轉(zhuǎn)移與下一次轉(zhuǎn)移在圖上頭尾相連。

[例8-14]二進制(3，1，2)卷積編碼器如圖8-5所示，試用網(wǎng)格圖來描述該碼。如果輸入信息序列是(1011010…)，求輸出碼字序列。

解：參見例8-12所得的編碼矩陣和狀態(tài)流圖，可得網(wǎng)格圖和編碼軌跡如圖8-11所示。圖中，當輸入5位信息10110時，輸出碼字和狀態(tài)轉(zhuǎn)移是：圖8－11

(3，1，2)卷積碼網(wǎng)格圖

從圖8-11看到，網(wǎng)格圖分成兩部分，一部分是對編碼器的描述，告訴人們從本時刻的各狀態(tài)可以轉(zhuǎn)移到下一時刻的哪些狀態(tài)，伴隨轉(zhuǎn)移的輸入信息／輸出碼字是什么；另一部分是對編碼過程的記錄，一條半無限的水平線(縱軸上的常數(shù))標志某一個狀態(tài)，一個箭頭代表一次轉(zhuǎn)移，每隔時間T(相當于移存器一位移存D)轉(zhuǎn)移一次，轉(zhuǎn)移的軌跡稱為路徑。兩部分可以合畫在一起，也可單獨畫。比如，在描述卷積編碼器本身而并不涉及具體編碼時，只需第一部分網(wǎng)格圖就夠了；當狀態(tài)很多、轉(zhuǎn)移線很密，網(wǎng)格圖上難以標全伴隨所有轉(zhuǎn)移的輸入／輸出碼字信息時，利用編碼矩陣可看得更清楚。

[例8-15]

某二進制(3，2，1)卷積編碼器如圖8-6所示，試用網(wǎng)格圖來描述該碼。如果輸入信息流是，求輸出碼字序列。

解：由[例8-13]所得的編碼矩陣和狀態(tài)流圖，可得網(wǎng)格圖和編碼軌跡如圖8-12所示。圖8－12

(3，2，1)卷積碼網(wǎng)格圖和編碼軌跡當輸入信息(10，11，01，01，11，00，…)時，輸出碼字和狀態(tài)轉(zhuǎn)移是：

至此，介紹了描述卷積碼的五種方法：離散卷積描述、生成矩陣、多項式轉(zhuǎn)移函數(shù)矩陣、狀態(tài)流圖和網(wǎng)格圖。這幾種方法從不同的側(cè)面來描述卷積碼，各有所長。其中，生成矩陣和多項式轉(zhuǎn)移函數(shù)矩陣可視為同一類，這兩種方法沿用了表示分組碼的基本思想，建立了代數(shù)與卷積編碼器的聯(lián)系。它們的特點是物理意義清楚，代數(shù)量(多項式系數(shù)、矩陣元素)與編碼電路連接線之間的對應關(guān)系十分明確，非常有利于用VHDL等硬件描述語言來表達，以及用FPGA、DSP等來物理實現(xiàn)。狀態(tài)流圖和網(wǎng)格圖屬于另外一類表示法，狀態(tài)流圖可借助信號流圖等圖論工具或理論來分析卷積碼的特性；網(wǎng)格圖則特別適合用于計算機的窮盡搜索，它使狀態(tài)能在時域展開，所得的狀態(tài)軌跡是研究差錯事件、卷積碼距離特性以及維特比最大似然序列譯碼最得力的工具。

8.2秩距離碼

8.2.1基本概念

1．矩陣的秩及矢量秩的性質(zhì)

設H是GF(qm)上的ab階矩陣（8－25）H在GF(q)上的秩定義為GF(q)上的最大線性無關(guān)的列數(shù)或行數(shù)，用r(H，q)表示。（8－26）則r(aX，q)＝r(X，q)，X∈GFn(qm)即對X乘以常數(shù)，不會改變X的秩。

2.秩距離及性質(zhì)

兩個矢量X，Y∈GFn(qm)之間的秩距離定義為dr(X，Y)＝r(X-Y，q)（8－27）秩距離dr(X，Y)有以下性質(zhì)：

(1)對稱性即若X，Y是特征不為2域中的元素，則秩距離不滿足對稱性，但在特征為2的域中，則滿足對稱性。(2)非負性

dr(X，Y)≥0。

(3)滿足距離三角不等式。

可見，除了對稱性以外，秩距離的性質(zhì)與漢明距離的性質(zhì)相同。8.2.2矩陣表述

下面先介紹秩距離碼的定義，然后介紹最大秩距離碼以及它的校驗矩陣和生成矩陣。

秩距離度量下的GF(q)上n維線性空間中的k維子空間，定義為GF(q)上的（n，k)秩距離碼。可見秩距離碼也是一個線性碼，除距離度量不同之外，與以前介紹的線性分組碼沒有根本不同。

GF(q)上的秩距離碼C的最小距離定義為：（8-28）

設Cl，C2是二個秩距離為dr，碼長為n的秩距離碼。設它們的碼字數(shù)目分別為

|C1|＝M1(n，dr)和＝M2(n，dr)。ri(X)(i＝1，2)表示碼Ci中碼字X的秩距離。若對所有碼字X，有r1(X)≤r2(X)，則M1(n，dr)≤M2(n，dr)（8-29）

類似漢明距離度量，對所有線性分組碼有，同樣對秩距離碼也有相同的限。因此對于任何線性(n，k)秩距離碼，秩距離dr≤n—k＋1。事實上，選擇rl＝(X，q)，r2＝rH(X)為漢明意義上的矢量X的重量。顯然r(X，q)≤rH(X)（8-30）若使d＝n-k＋1，則這種碼稱為最大秩距離碼，用MRD表示。由于MRD碼在構(gòu)造各種密碼體制和認證系統(tǒng)中起著重大作用，因此下面主要介紹這類碼的一些基本性質(zhì)。

設H和G分別是秩距離碼C的校驗矩陣和生成矩陣。

定理8-1

當且僅當對GF(q)上任何秩距離為dr－1的（dr－1）n階矩陣Y，有r(YHT，qm)＝dr—1(8-31)則碼C的最小秩距離為dr，且必在GF(q)上存在一個dr×n階矩陣Y0，有r(Y0HT，qm)<d

(8-32)

定理8-2

當且僅當GF(q)上的（n—k)×n階矩陣Y的秩為n一k時，即r(YHT，qm)＝n—k

（8-33）則由此H矩陣所確定的碼C是MRD碼。

定理8-3MRD碼的對偶碼也是MRD碼。

上述三個定理的證明，請參閱有關(guān)資料，這里不再介紹。下面介紹最大秩距離碼的構(gòu)造。

設hi∈GF(qm)(i＝1，2，…，n)，且假定這些元素在GF(q)上線性無關(guān)。設drn，則有以下監(jiān)督矩陣（8-34）

事實上對于dr＝n-1這是非常明顯的,因為由定理8-1在GF(q)上存在有一組線性無關(guān)的元素 滿足以下關(guān)系(s＝1，2,…,n-2)(8-36)8.2.3.秩循環(huán)碼

設GF（qN)上的所有N重集合{(x0，x1，…，xN—1)｜xi∈GF（qN)}為FN。令X＝（x0，x1，…,xN-1）∈FN

（8-37）稱（8-38）為X的[s]循環(huán)移位。其中[s]＝qs，顯然是由X右循環(huán)移位，且X的每一分量同時升高qs冪得到的。一個秩距離分組碼M中任一碼組Ｃ的[s]循環(huán)移位后得到的，若也是該碼的碼字，則稱M是[s]循環(huán)碼。當然，Ｃ與有相同的秩。下面主要介紹GF(q)上的[1]循環(huán)碼。

由有限域上循環(huán)碼的理論可知，循環(huán)碼是模xn－1多項式剩余類環(huán)中的一個主理想。同樣[1]循環(huán)碼也是模z[N]－z線性化多項式剩余類環(huán)LN[z]上的一個主理想。它的生成元G(z)是z[N]－z的一個因子，它就是[1]循環(huán)碼的生成多項式：z[N]－z＝G(z)H(z)（8-39）式中：它們是GF(q)上的線性化多項式，分別稱為[1]循環(huán)碼的生成多項式與校驗多項式。若G(z)為N—K次多項式，則由它生成一個[n，k]秩距離循環(huán)碼，它的每一碼字：C(z)＝U(z)·G(z)（8-40）式中：U(z)＝u0z[0]十ulz[l]＋…＋uk—1zk-1是GF(q)上的線性化信息多項式。該碼的生成矩陣與監(jiān)督矩陣分別為：（8-41）（8-42）式中：r＝N－K，且G（z）＝G0z[0]＋G1z[1]＋…＋Grz[r]H(z)＝H0z[0]＋H1z[1]＋…＋Hkz[k]

8.3突發(fā)錯誤的糾正

8.3.1基本概念

對于給定的糾突發(fā)錯誤能力b和碼長n，當然希望它能有最小的冗余度n－k。下面的結(jié)論將給出這種基本關(guān)系。

(1)一個(n，k)線性碼，若要發(fā)現(xiàn)長度不大于b的突發(fā)錯誤，其充要條件是n－k≥b,因為能發(fā)現(xiàn)錯誤的充分條件是伴隨式不為零。

可以證明，對于任何長度不大于b的突發(fā)Eb，可使Sb＝EbHT≠0，故可檢錯。其次,長度不大于b的突發(fā)Eb不能作為一個碼字，否則無法區(qū)分錯誤與正確。為做到這一點，在任意給定位置上的兩個突發(fā)Eb1和Eb2不能出現(xiàn)在標準陣列的同一陪集中，否則Eb1＋Eb2＝Eb3就要成為一個碼字。因此包括零長度突發(fā)錯誤在內(nèi)的共2b個突發(fā)錯誤必須分布在不同陪集中，因此2n-k≥2b，即n-k≥b。

(2)一個(n，k)線性碼，若要糾正所有長度不大于b的突發(fā)錯誤，則n－k≥2b。

若要糾正不大于b的突發(fā)錯誤，則任何長度為b的兩個突發(fā)E1和E2不能出現(xiàn)在同一陪集中，否則若E1放在陪集首，E2就無法糾正。E1和E2不能放在同一陪集中，這不僅意味著E1和E2的組合不能作為碼字，還意味著在任意給定的兩個位置上的所有不大于b的突發(fā)錯誤的不同組合不能出現(xiàn)在同一陪集中，這種組合共有22b種，所以應有2n-k≥22b，即n-k≥2b。

(3)一個(n，k)線性碼，若能糾正不大于b的所有突發(fā)錯誤，同時又能發(fā)現(xiàn)所有長度不大于s的突發(fā)錯誤，其中s≥b，則n-k≥b+s。

因為s≥b，所以n-k≥s＋b≥2b，所以能糾正長度不大于b的所有錯誤。如果在糾正上述突發(fā)錯誤的同時還要發(fā)現(xiàn)長度不大于s的所有突發(fā)錯誤，則這兩種突發(fā)錯誤的組合不能成為一個碼字，這意味著在任意給定位置上的兩種突發(fā)錯誤的不同組合不能出現(xiàn)在陣列的同一陪集中，而這種組合共有2b＋s種，它們應處在不同陪集中，所以n-k≥b＋s。8.3.2糾突發(fā)錯誤的碼

1.法爾(Fire)碼

法爾碼是最大的一類用分析方法構(gòu)造的糾單個突發(fā)錯誤的二進制循環(huán)碼。它的構(gòu)造方法和譯碼都比較簡單，因此是一類比較實用的碼。

令P(x)是指數(shù)為e的m次不可約多項式，即e是使P(x)|x6-1的最小正整數(shù)。法爾碼的生成多項式和碼長分別為：g(x)＝P(x).(x2b-1＋1)n＝lcm（2b-1,e）(8-43)(8-44)顯然n一k＝m＋2b一1。

【例8－16】設b＝5，P(x)＝x5＋x2＋1。求對應法爾碼生成多項式和碼長。

解由于P(x)是本原多項式，所以e＝25－1＝31。

因此g(x)＝(x9＋1)(x5＋x2十1)＝x14＋x11＋x9＋x5＋x2＋1n＝lcm(9,31)＝279因此該法爾碼是一個(279，265)的糾正不大于5位的單個突發(fā)錯誤的循環(huán)碼。

2.伯頓(Burton)碼

伯頓碼是一種糾單個定段突發(fā)錯誤的循環(huán)碼，b個相鄰碼元為一個碼段。設P(x)是指數(shù)為e的b次不可約多項式，且與xb＋1互素，則伯頓碼的生成多項式和碼長分別為：

g(x)＝P(x)·(xb＋1)（8-45）（8-46）它的構(gòu)造方法完全與法爾碼類似，是能糾正單個定段突發(fā)錯誤的(n，n－2b)碼。 8.4級聯(lián)碼及交織碼

8.4.1級聯(lián)碼

級聯(lián)碼是一種由短碼構(gòu)造長碼的一類特殊的、有效的方法。它首先是由范尼(Forney)于1966提出的。用這種方法構(gòu)造出的長碼不像一般長碼那樣需要復雜的譯碼設備。通常采用一個二進制的(n1，k1)碼C1作內(nèi)編碼，另一個非二進制的(n2，k2)碼C2作外編碼就能組成一個簡單的級聯(lián)碼。一般的外編碼C2采用的是RS碼，而內(nèi)編碼C1既可采用分組碼亦可采用卷積碼。其原理性方框圖如圖8－13所示。圖8－13串聯(lián)級聯(lián)碼原理性方框圖

在編碼時，首先將k1、k2個二進制信息元劃分為k2個字節(jié)，每一個字節(jié)有k1個信息元。同時每一個字節(jié)內(nèi)的k1個信息元按照二進制分組碼或卷積碼編成(n１，k1)的內(nèi)碼C1，即字節(jié)間共有k2個字節(jié)，則一般按照非二進制RS碼編成(n2

，k2)的外碼。最后將兩者串接構(gòu)成總共有n１n2碼元的編碼(n１n2

，k1k2)＝(n１k1)·(n2

k2)。若內(nèi)碼與外碼的最小距離分別為d1和d2，則它們級聯(lián)后的級聯(lián)碼最小距離至少為d1·d2

，級聯(lián)碼編譯碼亦可分為兩步進行，其設備僅是C1與C2直接組合，顯然,它比直接采用一個長碼構(gòu)成時設備要簡單得多。

1984年美國NASA給出一種用于空間飛行數(shù)據(jù)網(wǎng)的級聯(lián)碼編碼方案，以后被人們稱為標準級聯(lián)碼系統(tǒng)，它采用(2，1，7)卷積碼作為內(nèi)碼、(255，223)RS碼作為外碼，并加上交織器與去交織器。該級聯(lián)碼在AWGN信道的深空通信中，當Eb/N0=2.53dB時，Pb≤10-6，其方框圖如圖8－14所示。圖8－14標準級聯(lián)碼系統(tǒng)8.4.2交織碼

在某種意義上說，交織編碼是一種信道改造技術(shù)，它通過信號設計將一個原來屬于突發(fā)差錯的有記憶信道改造為基本上是獨立差錯的隨機無記憶信道。交織編碼原理方框圖如圖8－15所示。圖8－15交織編碼原理方框圖下面，通過一個簡單的例子來討論交織器與去交織器的設計，以及如何利用交織與反交織變換，將一個突發(fā)錯誤的有記憶信道改造為獨立差錯的無記憶信道。假若發(fā)送一組信息X＝［x1x2…x24x25］，首先將X送入交織器，同時將交織器設計成按列寫入、按行取出的5×5陣列存儲器；然后從存儲器中按行輸出送入突發(fā)差錯的有記憶信道，并將其送入反交織器，便完成了交織器的相反變換，即按行寫入、按列取出的仍是一個5×5陣列存儲器。反交織器的輸出，即陣列存儲器中按列輸出信息的差錯規(guī)律就變成了獨立差錯。其示意圖如圖8－16所示。圖8－16分組交織編碼實現(xiàn)方框圖

因為X＝［x1x2x3x4……x23x24x25］

(8-47)則交織矩陣:（8-48）對此矩陣按列寫入、按行讀出，得：(8-49)假設突發(fā)信道產(chǎn)生以下兩個突發(fā):第一個突發(fā)產(chǎn)生于x1至x21連錯5個；第二個突發(fā)產(chǎn)生于x13至x4連錯4個。故(8－50)則去交織矩陣為（8-51）對此矩陣按行寫入、按列讀出，得:X[3]＝[y1x2x3y4x5y6x7x8x9x10y11x12y13x14

x15y16x17x18x19x20y21x22y23x24x25]由上述分析可見，經(jīng)過交織矩陣與反交織矩陣的信號設計變換后，原來信道中產(chǎn)生的突發(fā)錯誤，即5個連錯和4個連錯變成了無記憶隨機性的獨立差錯。推廣至一般情況，則稱這類交織器為周期性的分組交織器，其分組長度為L＝M×N

(8-53)故又稱之為(M，N)分組交織器。它將分組長度L分成M列N行并構(gòu)成一個交織矩陣，該交織矩陣存儲器是按列寫入按行讀出，讀出后送至發(fā)