《編碼理論》課件第8章

第8章卷積碼和其他糾錯(cuò)碼

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

Turbo碼 8.1卷積碼

8.1.1離散卷積表述

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

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

設(shè)卷積碼編碼器輸入碼序列（待編碼的信息序列）為U＝u0(1)u0(2)…u0（k0）u1(1)u1(2)…u1(k0)…us(1)us(2)…us(k0)…設(shè)編碼器輸出碼序列為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個(gè)碼元，其前k0位與待編碼的信息序列中的第s信息組us(i)相同，而后n0-k0位監(jiān)督元由生成序列生成。由于每個(gè)碼中的前k0位就是此時(shí)刻待編碼的k0位信息元，所以在生成序列g(shù)(i,j)中有k0×k0個(gè)生成序列是固定的，即:只有k0×(n0-k0)個(gè)生成序列需要給定,以便確定每個(gè)子碼中n0-k0個(gè)監(jiān)督元,則碼字:cs(j)＝us（i）；(i＝j(luò)＝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)督矩陣來(lái)描述。對(duì)于任意一個(gè)(n0,k0,m0)卷積碼，其生成矩陣G∞是一個(gè)半無(wú)限矩陣，即（8－3）

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

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

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

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

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

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

由卷積碼的定義可知，(n0，k0，m0)碼的任意N個(gè)連續(xù)的子碼之間有著相同的約束關(guān)系，此外，在卷積碼的代數(shù)譯碼中，也只考慮一個(gè)編碼約束長(zhǎng)度內(nèi)的碼序列。所以，不失一般性，只考慮編碼器初始狀態(tài)全為0時(shí)，編碼器輸入N個(gè)信息組，即N.k0個(gè)信息元后，編碼器輸出的首N個(gè)子碼，即Nn0個(gè)碼元之間的約束關(guān)系即可，這首N個(gè)子碼組成的碼組稱為卷積碼的初始截短碼組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為初始截短碼組的生成矩陣，相應(yīng)的基本生成矩陣g為：

在系統(tǒng)碼條件下，由于k0k0個(gè)生成序列是已知的，即當(dāng)i＝j(luò)時(shí)，g(i，j)＝1；當(dāng)ij時(shí)，g(i，j)＝0，i＝1，2，…，k0；j＝1，2，…，k0。且每個(gè)子碼中的前k0個(gè)碼元與相應(yīng)的k0個(gè)信息元相同。而后n0—k0個(gè)監(jiān)督元?jiǎng)t由信息序列與生成序列的卷積運(yùn)算得到(見式(8-2)。由此可知，系統(tǒng)碼的初始截短碼組的Nk0Nn0生成矩陣為（8-9）（8-10）系統(tǒng)卷積碼初始截短碼組的基本生成陣為：(8-11)[例8-5](3，1，2)系統(tǒng)碼的生成序列為：它的初始截短碼組的基本生成矩陣是=[111010001]生成矩陣為若設(shè)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)。所以，在卷積碼的應(yīng)用中，經(jīng)常是給定碼的g(i，j)，有了生成序列g(shù)(i,j)后，就可以確定卷積碼的編碼電路及其矩陣表示式。

[例8-6]設(shè)(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－是一個(gè)6×1階全0陣；它的基本監(jiān)督陣是一個(gè)2×9階陣，即：則

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

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

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

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

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

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

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

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

構(gòu)造這種類型編碼電路的基礎(chǔ)是式(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）碼編碼電路

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

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

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

2．(n0—k0)m0級(jí)移位寄存器構(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個(gè)子碼的(n0—k0)個(gè)監(jiān)督元，需要(n0—k0)個(gè)移位寄存器組，每一組移位寄存器的數(shù)目為m0級(jí)。它們根據(jù)生成序列g(shù)(i，j)所確定的關(guān)系存儲(chǔ)了第s個(gè)信息組相鄰的前m0個(gè)信息組。(n0，k0，m0)碼Ⅰ型編碼電路如圖8-7所示。圖8－7

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

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

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

卷積編碼器在i時(shí)刻編出的碼字不僅取決于本時(shí)刻的輸入信息組，而且取決于i之前存入記憶陣列的個(gè)信息組，換言之，取決于記憶陣列的內(nèi)容，稱之為編碼器的狀態(tài)。如圖8-5所示的卷積編碼器中，除本時(shí)刻的輸入外還有兩個(gè)存儲(chǔ)器存放i—1和i—2時(shí)刻的輸入，即和內(nèi)容，其內(nèi)容的組合有四種可能，即00，01，10和11，就說(shuō)這種編碼器有四個(gè)狀態(tài)。更一般地，移存器陣列分割成兩塊，（8-23）式中：(8－24)編碼矩陣第i行第j列的元素表示由狀態(tài)轉(zhuǎn)移到下一狀態(tài)時(shí)發(fā)送的碼字，矩陣元素“．”說(shuō)明這種狀態(tài)轉(zhuǎn)移是不可能事件。比如從狀態(tài)轉(zhuǎn)移到下一狀態(tài)就不可能，因?yàn)檩斎氡忍?狀態(tài)機(jī)觸發(fā)信號(hào))只有0或1兩種，對(duì)應(yīng)的轉(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é)點(diǎn)，因需標(biāo)注狀態(tài)號(hào)，所以沒有像一般的信號(hào)流圖那樣用一個(gè)黑點(diǎn)表示節(jié)點(diǎn)。箭頭代表轉(zhuǎn)移，與箭頭對(duì)應(yīng)的標(biāo)注，比如0／010，表示輸入信息0時(shí)的編出碼字010。每個(gè)狀態(tài)都有兩個(gè)箭頭發(fā)出，對(duì)應(yīng)輸入分別是0，1兩種情況下的轉(zhuǎn)移路徑。假如輸入信息序列是1011010111…，從狀態(tài)流圖可以輕易地找到輸入／輸出和狀態(tài)的轉(zhuǎn)移關(guān)系?？蓮臓顟B(tài)出發(fā)，根據(jù)輸入找到相應(yīng)箭頭，隨箭頭在狀態(tài)流圖上移動(dòng)，得到以下結(jié)果：

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

解圖8－6所示的編碼器有2路輸入、3路輸出，2個(gè)移存器、4種狀態(tài)。由于i時(shí)刻并行輸入2b，相當(dāng)于有限狀態(tài)機(jī)的觸發(fā)信號(hào)由2b組成，所以從某一狀態(tài)出發(fā)，下一個(gè)狀態(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)格圖(或稱格柵圖)可以彌補(bǔ)這一缺陷。它可以將狀態(tài)轉(zhuǎn)移展開在時(shí)間軸上，使編碼的全過程躍然紙上，是分析卷積碼的有力工具。網(wǎng)格圖以狀態(tài)為縱軸，以時(shí)間(抽樣周期T)為橫軸，將平面分割成格狀。狀態(tài)和狀態(tài)轉(zhuǎn)移的定義畫法與流圖法一樣，也是用一個(gè)箭頭表示轉(zhuǎn)移，伴隨轉(zhuǎn)移的表示轉(zhuǎn)移發(fā)生時(shí)的輸入信息組／輸出碼組。所不同的是，網(wǎng)格圖還體現(xiàn)時(shí)間的變化，一次轉(zhuǎn)移與下一次轉(zhuǎn)移在圖上頭尾相連。

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

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

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

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

[例8-15]

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

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

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

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

8.2秩距離碼

8.2.1基本概念

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

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

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

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

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

dr(X，Y)≥0。

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

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

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

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

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

設(shè)Cl，C2是二個(gè)秩距離為dr，碼長(zhǎng)為n的秩距離碼。設(shè)它們的碼字?jǐn)?shù)目分別為

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

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

設(shè)H和G分別是秩距離碼C的校驗(yàn)矩陣和生成矩陣。

定理8-1

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

(8-32)

定理8-2

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

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

定理8-3MRD碼的對(duì)偶碼也是MRD碼。

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

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

事實(shí)上對(duì)于dr＝n-1這是非常明顯的,因?yàn)橛啥ɡ?-1在GF(q)上存在有一組線性無(wú)關(guān)的元素 滿足以下關(guān)系(s＝1，2,…,n-2)(8-36)8.2.3.秩循環(huán)碼

設(shè)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的每一分量同時(shí)升高qs冪得到的。一個(gè)秩距離分組碼M中任一碼組Ｃ的[s]循環(huán)移位后得到的，若也是該碼的碼字，則稱M是[s]循環(huán)碼。當(dāng)然，Ｃ與有相同的秩。下面主要介紹GF(q)上的[1]循環(huán)碼。

由有限域上循環(huán)碼的理論可知，循環(huán)碼是模xn－1多項(xiàng)式剩余類環(huán)中的一個(gè)主理想。同樣[1]循環(huán)碼也是模z[N]－z線性化多項(xiàng)式剩余類環(huán)LN[z]上的一個(gè)主理想。它的生成元G(z)是z[N]－z的一個(gè)因子，它就是[1]循環(huán)碼的生成多項(xiàng)式：z[N]－z＝G(z)H(z)（8-39）式中：它們是GF(q)上的線性化多項(xiàng)式，分別稱為[1]循環(huán)碼的生成多項(xiàng)式與校驗(yàn)多項(xiàng)式。若G(z)為N—K次多項(xiàng)式，則由它生成一個(gè)[n，k]秩距離循環(huán)碼，它的每一碼字：C(z)＝U(z)·G(z)（8-40）式中：U(z)＝u0z[0]十ulz[l]＋…＋uk—1zk-1是GF(q)上的線性化信息多項(xiàng)式。該碼的生成矩陣與監(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ā)錯(cuò)誤的糾正

8.3.1基本概念

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

(1)一個(gè)(n，k)線性碼，若要發(fā)現(xiàn)長(zhǎng)度不大于b的突發(fā)錯(cuò)誤，其充要條件是n－k≥b,因?yàn)槟馨l(fā)現(xiàn)錯(cuò)誤的充分條件是伴隨式不為零。

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

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

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

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

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

1.法爾(Fire)碼

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

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

【例8－16】設(shè)b＝5，P(x)＝x5＋x2＋1。求對(duì)應(yīng)法爾碼生成多項(xiàng)式和碼長(zhǎng)。

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

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

2.伯頓(Burton)碼

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

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

8.4.1級(jí)聯(lián)碼

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

在編碼時(shí)，首先將k1、k2個(gè)二進(jìn)制信息元?jiǎng)澐譃閗2個(gè)字節(jié)，每一個(gè)字節(jié)有k1個(gè)信息元。同時(shí)每一個(gè)字節(jié)內(nèi)的k1個(gè)信息元按照二進(jìn)制分組碼或卷積碼編成(n１，k1)的內(nèi)碼C1，即字節(jié)間共有k2個(gè)字節(jié)，則一般按照非二進(jìn)制RS碼編成(n2

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

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

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

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

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

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

因?yàn)閄＝［x1x2x3x4……x23x24x25］

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

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

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