信息論與編碼第五講

信息論與編碼第五講第一頁，共一百零三頁，編輯于2023年，星期六主要內(nèi)容RS編譯碼卷積編譯碼第二頁，共一百零三頁，編輯于2023年，星期六5.1RS碼第三頁，共一百零三頁，編輯于2023年，星期六5.1.1RS編碼RS碼=Reed-Solomoncode=里德-索洛蒙碼是BCH碼最重要的一個子類?？梢暈锽CH碼的特例,是m=1,m0=1時的q元本原BCH碼。由于最小多項式的次數(shù)不會超過m,當(dāng)m=1時，2t個連續(xù)冪次的根(x-)(x-2)…(x-2t)既是q元擴(kuò)域GF(q1)上的根多項式，又是q元基域GF(q)上的最小多項式。這種性質(zhì)給多元BCH碼的設(shè)計帶來了很多的方便，因為我們在前面已經(jīng)看到，由擴(kuò)域i次冪根i求基域?qū)?yīng)的最小多項式是十分麻煩的事，而RS碼的一次根式(x-)就是最小多項式，無需另外再去計算。第四頁，共一百零三頁，編輯于2023年，星期六本原RS碼具有如下參數(shù)：碼長：n=q-1校驗位：n-k=2t最小距離：dmin=2t+1生成多項式：g(x)=(x-)(x-2)…(x-2t)=an-kxn-k+an-k-1xn-k-1+…+a1x+a0(4-32)

式中，g(x)的各次系數(shù)ai取自擴(kuò)域GF(q1)ai

{0,1,,2,…,q-2}(i=0…n-k) (4-33)由以上參數(shù)可見

dmin=2t+1=n-k+1

因此，RS碼也是MDC碼（極大最小距離）第五頁，共一百零三頁，編輯于2023年，星期六注意：GF(q)和GF(q1)含義不同GF(q)是數(shù)域，q必須是素數(shù)GF(q1)是多項式域，q不一定是素數(shù)，工程上，q通常取為2的冪次。GF(8)???01234567表4-9用x3+x+1產(chǎn)生的GF(81)GF(81)多項式3重0000011001010221003+101142+11052++111162+11014+5=1mod83+

4=64的乘法逆元？第六頁，共一百零三頁，編輯于2023年，星期六例4.10

試設(shè)計一個(7,3,5)本原RS碼。解：由于碼長n=q-1＝7，可斷定碼元是8進(jìn)制的。8進(jìn)制域元素可以用根的冪次、多項式或3重矢量表示。

若令是本原多項式p(x)=x3+x+1的根，即3=+1，我們可以列出表4-9。因題中要求dm=5∴t=INT[(dm-1)/2]=2這說明生成多項式g(x)有4個連續(xù)根、2、3、4。由(式4-32):g(x)=(x-)(x-2)(x-3)(x-4)=[x2-(+2)x+3][x2-(3+4)x+7]=[x2-4x+3][x2-6x+1]

=x4-(6+4)x3+(1+10+3)x2-(4+9)x+

10

=

x4+

3x3+x2+

x+

3

在上式運算中用到了關(guān)系式3=+1以及二元擴(kuò)域的一些運算規(guī)則，比如i+

i=0、7=1等。第七頁，共一百零三頁，編輯于2023年，星期六此8進(jìn)制(7,3,5)RS碼的生成矩陣為：

G=

通過矩陣行運算可以將它系統(tǒng)化,得G=13

1

3

0

0第①行013

1

3

0第②行0013

1

3

第③行

100

41

45

①+②×3+③×201021

66②+③×300131

3③生成多項式的運算同樣可用除法器實現(xiàn)，只是所作的運算是GF(81)域的乘、加運算。第八頁，共一百零三頁，編輯于2023年，星期六例：用上面設(shè)計的(7,3,5)本原RS碼，對一個二元序列（111011010……）實行編碼。解：將二元序列化作GF(81)元素，得

m:（111011010）(53)

C=mG=(53)=(5,3,,9+5+4,5+3+,2+2+2,

3+2+4)=(5,

3,

,6,

4,

2,

1)對應(yīng)的(21,9)二進(jìn)制衍生碼字是：（111011010101110100001）100

41

4501021

6600131

3第九頁，共一百零三頁，編輯于2023年，星期六(7,3,5)RS碼的t=2,能糾2個差錯。衍生為(21,9)二元碼后，糾隨機(jī)差錯能力與原(7,3)RS碼一樣t=2，還能糾長度≤4的任何突發(fā)差錯。這是因為信道上長度為4的突發(fā)差錯最多影響到兩個二進(jìn)制3重矢量，相當(dāng)于兩個8進(jìn)碼元出錯，仍在t=2范圍之內(nèi)。

(5,

3,

,6,

4,

2,

1)（111,011,010,101,110,100,001）能糾的隨機(jī)差錯

（111,011,010,101,110,100,001）能糾的突發(fā)差錯（111,011,010,101,110,100,001）（111,011,010,101,110,100,001）不能糾第十頁，共一百零三頁，編輯于2023年，星期六

上述這種用二進(jìn)制碼表示的q進(jìn)制RS碼稱為該RS碼的二進(jìn)衍生碼，衍生指GF(q1)和GF(2)兩個域間的映射。可以證明，這種映射是把線性碼映射成線性碼，映射后的二進(jìn)衍生碼一定是線性分組碼，但不一定是循環(huán)碼。一般來說，一個隨機(jī)差錯能力為t的RS碼，其二進(jìn)衍生碼可以糾正小于等于t個隨機(jī)差錯，或者糾正單個長度為b的突發(fā)差錯，

b≤(t-1)m+1 (4-35)以及其它大量錯誤圖樣。

可見，二進(jìn)衍生碼特別適用于糾突發(fā)差錯，這就是它在無線通信中被廣泛采用的原因。

第十一頁，共一百零三頁，編輯于2023年，星期六

q進(jìn)制RS碼也可以擴(kuò)展。對于(n,k,d)RS碼(n=q-1)，我們可以給每個碼字：(C0,C1,…,Cn-1)增加一個全校驗位Cn(modq) (4-36)使此擴(kuò)展RS碼字的全體碼元C0,C1,…,Cn-1之和為零。可以證明：如果該碼字生成多項式g(x)不含(x-1)因子

(或1不是g(x)的根)，那么加了一個全校驗位后，能使擴(kuò)展碼的最小距離增加1，即得到(n+1,k,d+1)擴(kuò)展RS碼。比如上例

(7,3,5)RS碼擴(kuò)展出來的(8,3,6)碼，其二進(jìn)衍生碼是(24,9)二元碼。

第十二頁，共一百零三頁，編輯于2023年，星期六IBM3370磁盤存儲系統(tǒng)采用256進(jìn)制(255,252)RS碼的縮短碼，并對應(yīng)成8比特(1字節(jié))一組的二進(jìn)制衍生碼。該碼的基本參數(shù)是：q=28=256,n=q-1=255,t=1。

該RS碼的碼元取自本原多項式P(x)=x8+x4+x3+x2+1生成的擴(kuò)域GF(28),通過列出類似表4-9那樣的對照表，可以找出域元素運算及與二進(jìn)制8重矢量映射（衍生）關(guān)系，其生成多項式是： g(x)=(x--1)(x-1)(x-)使用時，一個扇區(qū)的512字節(jié)加一個0字節(jié)變?yōu)?13字節(jié)，分成3組、每組5133＝171字節(jié)，編成3個由(255，252)縮短下來的(174，171)RS碼字。實際介質(zhì)中使用的是（8×174，8×171）RS衍生碼。

第十三頁，共一百零三頁，編輯于2023年，星期六在CD唱片中，采用了兩級糾錯加交織器的差錯控制方案。糾錯碼用的是q=28=256進(jìn)制的(255，251)RS碼，糾錯能力t=2。使用時，將它縮短為(28,24)的外碼和(32,28)的內(nèi)碼兩種。每秒44.1k采樣、每采樣16比特的數(shù)字音頻碼流(16×44.1k=1.41Mb/s)被分割成24字節(jié)（192bit）的信息組，每字節(jié)對應(yīng)一個256進(jìn)制的碼元，經(jīng)（28，24）RS編碼器編出28字節(jié)（224bit）一組的256進(jìn)制的外碼碼元。這些碼元經(jīng)4行5列(4×5字節(jié)交織器)交織后由(32，28)RS編碼器二次編碼，輸出32字節(jié)（256bit）一組內(nèi)碼碼元，每碼元寫入CD盤的一個字節(jié)。讀出是寫入的逆過程，包括RS（32，28）內(nèi)碼譯碼、去交織和RS（28，24）外碼譯碼。第十四頁，共一百零三頁，編輯于2023年，星期六

整個過程中，24字節(jié)音頻信號轉(zhuǎn)為32字節(jié)磁盤存儲，碼率為0.75，要求CD盤的讀出速率至少大于1.410.75=1.88Mb/s(沒考慮其它任何開銷)。具體譯碼中，當(dāng)內(nèi)碼遇到一個可檢不可糾的差錯時將會對外碼發(fā)送一個信息以提高外碼的糾錯能力；當(dāng)差錯超過外碼的糾錯能力時，會對播放系統(tǒng)發(fā)送一個信息，將該譯碼樣值刪除而改用前、后樣值的插值(interpolating)。如果差錯太多而超出了插值運算的能力，播放系統(tǒng)將插入一段靜音(mute)替代這個突發(fā)差錯。

第十五頁，共一百零三頁，編輯于2023年，星期六

在宇航中，RS碼和卷積碼是一對黃金搭配，用于深空(deepspace)通信中的糾錯編碼。

深空信道屬隨機(jī)差錯信道，用卷積碼比較合適。但一旦信道噪聲超出卷積碼的糾錯能力，就將導(dǎo)致突發(fā)性質(zhì)的譯碼差錯，這時用RS碼來對付將是最佳選擇。

在“探險者號”(Voyager)飛向木星和土星的旅程中，信息就是以RS碼為外碼、卷積碼為內(nèi)碼的級聯(lián)碼實現(xiàn)信道編碼的。這種級聯(lián)碼性能優(yōu)良，已被認(rèn)為是一種宇航通信標(biāo)準(zhǔn)而稱為‘NASA’碼，可帶來5～7dB的編碼增益。第十六頁，共一百零三頁，編輯于2023年，星期六

探險者Voyager采用了(255,223)RS碼，在誤比特率Pb=10-6時可獲得2.5dB額外編碼增益（與僅用卷積碼相比）。該RS碼每碼字的255個碼元取值于256進(jìn)制GF（256）的衍生二進(jìn)制擴(kuò)域GF（28），生成擴(kuò)域元素的本原多項式是P(x)=x8+x4+x3+x2+

1，生成多項式是g(x)=（x-）（x-2）（x-3）…（x-32）式中是本原多項式P(x)的根。由于生成多項式含32個連續(xù)冪次的根，可知該碼的糾錯能力t=16碼元（256進(jìn)制），或長度121(式4-35)的二進(jìn)制突發(fā)差錯。第十七頁，共一百零三頁，編輯于2023年，星期六5.1.2RS碼迭代譯碼

RS碼是BCH碼的子類，必然存在某些構(gòu)碼特點和能最大程度發(fā)揮其糾錯潛力的專用譯碼方法。RS碼譯碼方法主要有：迭代譯碼和快速譯碼。RS碼是MDC碼，碼的最小距離d=n-k+1=2t-1，因此g(x)有2t個即d-1個連續(xù)冪次的根。RS碼可以用類似于BCH碼的迭代方式來譯碼，但必須增加一個步驟：確定了差錯碼元位置后還要確定差錯幅度。第十八頁，共一百零三頁，編輯于2023年，星期六假設(shè)有個差錯分布在j1、j2、…、j位上，而差錯幅值分別是ej1

、ej2…

ej

，則

E(x)=ej1xj1+ej2

xj2

+…ej

xj (4-80)

（0

j1<j2…<j

n-1）

令xjl=l

（l=1,2…,是差錯位置序號）

E(x)=ej11+ej2

2+…ej

(4-81)將2t個連續(xù)根依次代入式(4-79)，由于C()=C(2)=…=C(2t)=0，可得2t個伴隨式元素：

S1=R()=E()=ej11+ej22+…ejS2=R(2)=E(2)=ej112+ej222+…ej2(4-82)

┇S2t

=R(2t)=E(2t)=ej112t+ej222t+…ej2t第十九頁，共一百零三頁，編輯于2023年，星期六上式含1、2…

和ej1

、ej2…

ej

共2個未知數(shù)，而方程有2t個。只要

t，方程就可解。因此譯碼方法就是先求出2t個伴隨式元素S1、S2、…S2t(P121）

，然后解方程算出所有未知數(shù)。由于RS碼的根所在的域與碼元取值的域相同，根i對應(yīng)的最小多項式必是一次項(x+i)。令bi是R(x)除以(x+i)的余式，即R(x)=qi(x)(x+i)+bi，由式(4-62)，必有

Si=R(i)=bi(4-83)用圖4-22的(x+i)除法電路可方便地完成Si的計算。

R(x)

模q加模q乘

q元寄存器圖4-22(x+i)除法電路i第二十頁，共一百零三頁，編輯于2023年，星期六已知Si后分兩步求解2個未知數(shù)，先計算差錯位置1、2…

，再差錯幅值第一步：利用錯誤位置多項式求出差錯位置數(shù)1、2…，令(x)=(1-1x)(1-2x)…(1-x)=1+1x+…+x

與式(4-66)相同，可利用伯利坎普迭代解牛頓恒等式，得1、2、…、，進(jìn)而求出1、2、…、。第二十一頁，共一百零三頁，編輯于2023年，星期六第二步：利用伴隨式和的系數(shù)求出差錯幅值。此時，差錯個數(shù)和(x)系數(shù)1、2、…、，以及差錯位置1、2、…均為已知數(shù)。

(4-66)(4-84)其中，0=1。定義如下函數(shù)

(4-85)(4-86)

第二十二頁，共一百零三頁，編輯于2023年，星期六j(x)是去除了第j個根后(x)的剩余式。上式可寫成比較它們同次項系數(shù)，或者寫作

(4-88)這是解的遞推公式，變?yōu)橐阎?。第二十三頁，共一百零三頁，編輯?023年，星期六由式(4-83)，

Si=R(i)=1i+2i+…i=

代入下式

=對照式(4-86)，

(4-89)第二十四頁，共一百零三頁，編輯于2023年，星期六由于j(x)有除了j-1外的-1個根，的值僅當(dāng)k=j時不為零（不是根），k為其余值時均是0，所以式(4-89)可以簡化為單項

==最后得：

(4-91)第二十五頁，共一百零三頁，編輯于2023年，星期六5.2卷積碼第二十六頁，共一百零三頁，編輯于2023年，星期六

卷積碼是一個有限記憶系統(tǒng)。當(dāng)信息序列切割成長度k的一個個分組后，分組碼單獨對各分組編碼，而卷積碼不僅根據(jù)本時刻的分組，而且根據(jù)本時刻以前的L個分組共同來決定編碼。由于編碼過程受L+1個信息分組的制約，因此稱L+1為約束長度（ConstraintLength），也有的人直接把L稱為約束長度。約束長度是卷積碼的一個基本參數(shù)，我們常用(n，k，L)來表示某一碼長n、信息位k、約束長度L+1的卷積碼。約束長度的單位用“分組”而不用“碼元”，是因為編碼和譯碼時的約束分組數(shù)是一樣的，而約束碼元數(shù)卻是不同的，編、譯碼時的約束碼元數(shù)分別是(L+1)k與(L+1)n。第二十七頁，共一百零三頁，編輯于2023年，星期六

卷積編碼器（線性組合器）ci0c

i1…cin-2cin-1

第i分組第i-1分組第i-2分組……第i-L分組mi0mi1…mik-1mi-10…mi-1k-1m

i-20…m

i-2k-1…mi-L

0mi-L

1…mi-L

k-1輸入編碼輸出Ci圖5-1卷積編碼示意第二十八頁，共一百零三頁，編輯于2023年，星期六串/

并變換并/

串變換線性組合器m

i0mi-10mi-20…mi-L

0mi1mi-11mi-21…mi-L

1m

ik-1mi-1k-1m

i-2k-1…mi-L

k-1信號入

m

i

編碼輸出

Ci

┇┇……┇┇圖5-2卷積編碼器的一般結(jié)構(gòu)

第二十九頁，共一百零三頁，編輯于2023年，星期六

圖5-2記憶陣列中的每一存儲單元都有一條連線將數(shù)據(jù)送到線性組合器，但實際上無需每個單元都有連接。這是因為二元域線性組合時的系數(shù)只能選“0”或者“1”，選“0”時表示該項在線性組合中不起作用，對應(yīng)存儲單元就不需要連接到線性組合器。從圖上看到，每一個碼元都是k×(L+1)個數(shù)據(jù)線性組合的結(jié)果，需要有k×(L+1)個系數(shù)來描述組合規(guī)則，于是每一個碼字需用

n×k×(L+1)個系數(shù)才能描述。顯然，只有將這些系數(shù)歸納為矩陣才能理順?biāo)鼈兊年P(guān)系和便于使用。

第三十頁，共一百零三頁，編輯于2023年，星期六設(shè)（n,k,L）卷積碼在時刻i及i之前L個時刻的輸入、輸出矢量分別是：時刻輸入矢量(信息) 輸出矢量(碼字)i

Mi=(mi0,mi1

,…,mik-1) Ci=(ci0,ci1

,…,cin-1)i-1Mi-1=(mi-10,mi-11…mi-1k-1) Ci-1=(ci-10,ci-11…ci-1n-1)┇

┇

┇i-LMi-L=(mi-L0,mi-L1…mi-Lk-1)Ci-L=(ci-L0,ci-L1…ci-Ln-1)這里,大寫字母表示碼組，小寫字母表示碼元，上標(biāo)表示碼字中的碼元順序，下標(biāo)表示時序。在任意時刻i,卷積碼碼字的第j個碼元是約束長度內(nèi)所有信息比特的線性組合，寫作：第三十一頁，共一百零三頁，編輯于2023年，星期六

j=0,1,2,…n-1

(5-1)式中，{0,1}表示圖5-2中第l列（l時刻的信息組,l=0,…,L）、第k行（信息組的第k個碼元，k=0,…,K-1）對第j個輸出碼元的影響。

=0表示該位不參與線性組合，

=1表示該位參與線性組合。

第三十二頁，共一百零三頁，編輯于2023年，星期六例5.1

某二進(jìn)制(3,1,2)卷積編碼器如圖5-3所示，寫出表達(dá)其線性組合關(guān)系的全部系數(shù)。解：本例為碼率R=1/3的卷積碼，n=3,k=1,L=2。由編碼器電路圖，可寫出nk(L+1)=9個系數(shù)如下：

=1=0=0=1=1=0=1 =1=1

信號 ci0入Mi

輸出

ci1C

i

c

i2

圖5-3二元(3,1,2)卷積編碼器mi0mi-10mi-20輸入信息行時延列輸出碼元行第三十三頁，共一百零三頁，編輯于2023年，星期六例5.2某二進(jìn)制(3,2,1)卷積編碼器如圖5-4，寫出表達(dá)線性組合關(guān)系的全部系數(shù)。解：本例為碼率R=2/3的卷積碼,n=3,k=2,L=1。由編碼器電路圖，可寫出nk(L+1)=12個系數(shù)如下：

=1,=1,=0,=1=0,=1,=1,=0=1,=1,=1,=0

輸入信息行時延列輸出碼元行

c

i0

信號 Ci

入Mi

ci1輸出

c

i2圖5-4二進(jìn)制(3,2,1)卷積編碼器mi

0mi-10mi

1m

i-11第三十四頁，共一百零三頁，編輯于2023年，星期六上面兩例表明，

從已知的編碼電路可以找出對應(yīng)的系數(shù)，反之，已知系數(shù)即可畫出相應(yīng)的編碼電路。因此，從電路結(jié)構(gòu)角度，(5-1)是很好的表達(dá)形式。但是，我們通常需要從另外各種不同的角度去研究卷積碼，或側(cè)重于卷積碼的物理意義，或強(qiáng)調(diào)卷積碼的距離特性，或研究編碼器的狀態(tài)變遷等。在不同角度，存在著描述卷積碼的不同方法。以下我們將介紹四種卷積碼的描述方法：生成矩陣表示法，轉(zhuǎn)移函數(shù)矩陣表示法，狀態(tài)流圖法，網(wǎng)格圖表示法。

第三十五頁，共一百零三頁，編輯于2023年，星期六5.2.1生成矩陣表示法

由式(5-1)，

CiT

┇┇┇┇

=

=

=

+…第三十六頁，共一百零三頁，編輯于2023年，星期六 … … = … +…+…

┇┇┇┇ … …=

求轉(zhuǎn)置，上式寫成：

(5-2)式中，G0、G1、…GL

是k×n矩陣，稱作生成子矩陣：

…

Gl

= …l=0,1,…,L(5-3)

┇┇…第三十七頁，共一百零三頁，編輯于2023年，星期六時刻i=0 C0=M0G0

時刻i=1 C1=M0G1+M1G0

時刻i=2 C2=M0G2+M1G1+M2G0┆┆時刻i=L

CL=M0GL+M1GL-1+…+ML-1G1+MLG0

時刻i=L+1 CL+1=M1GL+M2GL-1+…+MLG1+ML+1G0

式(5-2)可寫成： (5-4)式(5-4)說明：輸出碼字Ci是i時刻之前(含i時刻)的信息組(MiMi-1…Mi-L)與生成子矩陣組(G0G1…GL)的卷積，這也就是卷積碼名稱的來歷。(5-2)第三十八頁，共一百零三頁，編輯于2023年，星期六39

令

G0 G1G2…GL00……

gG= G0G1G2…GL0……

=

Dg

(5-6) G0G1G2…GL

0… D2g ┆ ┆

定義g

為基本生成矩陣，定義G為生成矩陣若碼字序列是一個從0時刻開始的無限長右邊序列，可寫成有頭無尾的半無限矩陣形式：C=C0,C1,

…，CL,CL+1,…）

G0G1G2…GL0

……=(M0,…,ML,ML+1,…)

G0G1G2…GL0…

(5-5)

G0G1G2…GL0

…

┆第三十九頁，共一百零三頁，編輯于2023年，星期六例5.1(續(xù)1)

二進(jìn)制(3,1,2)卷積編碼器如圖5-3。如果輸入信息流是(101101011100…),求輸出碼字序列。解：對照例5.1算得的系數(shù)及式(5-3)生成子矩陣的定義，可知本題G0=[]=[111]，G1=[ ]=[011]G2=[ ]=[001] 111011001 111011001Ci=(101101011100…)111011001 111011001 ┆=(111,011,110,100,010,110,011,110,100,101,010,001┄)

第四十頁，共一百零三頁，編輯于2023年，星期六例5.2(續(xù)1)

某二進(jìn)制(3,2,1)卷積編碼器如圖5-4,若輸入信息流是(101101011100…)，求輸出碼字序列解：對照例5.2算得的系數(shù)及式(5-3)生成子矩陣的定義，可知本題G0= =，G1==于是

101111 011100C=(10,11,01,01,11,00…) 101111 011100 101111 011100┄=(101,001,000,111,010,011,…)101011111100第四十一頁，共一百零三頁，編輯于2023年，星期六5.2.2多項式及轉(zhuǎn)移函數(shù)矩陣表示法若M(D)=m0+m1D…+mkDk+mk+1Dk+1+…

…

+m2kD2k+m2k+1D2k+1+…，則串/并變換后M0

(D)=m0+mkD+m2kD2+…M1

(D)=m1+mk+1

D+m2k+1D2+…┇

MP(D) CP(D)

M0(D) C0(D) M1(D) C1(D)M(D)┆ C(D)Mk-1(D) Cn-1(D)

圖5-5卷積碼的轉(zhuǎn)移函數(shù)矩陣串/并卷積編碼器G(D)并/串第四十二頁，共一百零三頁，編輯于2023年，星期六卷積編碼器可視作一個k端口入、n端口出的線性多端口網(wǎng)絡(luò)，可以用轉(zhuǎn)移函數(shù)矩陣來描述其輸入、輸出間的數(shù)量關(guān)系。卷積編碼器的特殊之處，在于其輸入、輸出均是無限長多項式，轉(zhuǎn)移函數(shù)矩陣元素也是多項式。定義輸入、輸出多項式矩陣MP(D)、CP(D)為：

M(D)串/并

MP(D)=[M0

(D),M1

(D),…Mk-1

(D)]C

(D)串/并

CP(D)=[C0

(D),C1

(D),…Cn-1

(D)]

這里，MP(D)、CP(D)的下標(biāo)P表示“并行”。雖然M

(D)和

MP(D)數(shù)量上有對應(yīng)關(guān)系，然而在數(shù)學(xué)上有不同含義，M

(D)是多項式而MP(D)是矩陣第四十三頁，共一百零三頁，編輯于2023年，星期六編碼器k路輸入和n路輸出之間的轉(zhuǎn)移關(guān)系為

CP(D)

=MP(D)G

(D) (5-8)G(D)是k×n

轉(zhuǎn)移函數(shù)矩陣，

g00(D)g10(D)…gn-10(D)

G

(D)= g01(D)g11(D)…gn-11(D)(5-9)┆┆┆

g0k-1(D)g1k-1(D)…gn-1k-1(D)矩陣G

(D)的第i行第j列元素gji(D)描述了第i個輸入支路如何對第j個輸出支路產(chǎn)生影響的轉(zhuǎn)移關(guān)系，也稱子多項式，而第j個輸出支路最終輸出由全體k個輸入支路共同決定。

第四十四頁，共一百零三頁，編輯于2023年，星期六由于約束長度是L+1,任何一個子多項式gji(D)的階次不會大于L，可用通式表示為

=+…+ (5-10)式(5-10)定義的子多項式gji(D)的各次系數(shù)與式(5-1)(5-3)中的系數(shù)是一致的，代表第k個輸入支路中第l個移存器對第j個輸出支路的影響?？梢姸囗検奖硎痉ㄅc矩陣表示法本質(zhì)是一樣的，只是多項式表示法通過時延因子D將L+1個生成子矩陣(式5-3)合成一個，而使矩陣元素由“數(shù)”變?yōu)椤岸囗検健?。其?yōu)點是能夠一目了然地看到并行輸入序列和輸出序列之間的轉(zhuǎn)移關(guān)系，而這正是卷積編碼器的主要特征第四十五頁，共一百零三頁，編輯于2023年，星期六由式(5-9)、(5-10)，可知第j個支路的輸出是所有輸入支路對它影響的總和，即

(5-11)最后，利用并/串變換公式將n個輸出多項式合并成一個多項式

(5-12)轉(zhuǎn)移函數(shù)矩陣用法歸納如下①輸入信息序列經(jīng)串/并變換得并行的輸入多項式②用式(5-11)算出各并行支路的輸出多項式③用并/串轉(zhuǎn)換公式(5-12)算出輸出多項式C(D)。

第四十六頁，共一百零三頁，編輯于2023年，星期六例5.1(續(xù)2)

二進(jìn)制(3,1,2)卷積編碼器如圖5-3。如果輸入信息流(101101011100…),求輸出碼字序列。解：本題為一路輸入(k=1)、三路輸出(n=3)，因此轉(zhuǎn)移函數(shù)矩陣是1×3的多項式矩陣。一路輸入為M0(D)=1+D2+D3+D5+D7+D8+D9+…根據(jù)例5.1中算出的系數(shù)及通式(5-10)定義，

g00(D)=+D+D2=1

g10(D)=+D+ D2=1+D

g20(D)=+D+ D2=1+D+D2由式(5-9)，該卷積編碼器的轉(zhuǎn)移函數(shù)矩陣是：

G(D)=[11+D1+D+D2]第四十七頁，共一百零三頁，編輯于2023年，星期六由式(5-11)C0(D)=M0(D)g00(D)=(1+D2+D3+D5+D7+D8+D9…)1=1+D2+D3+D5+D7+D8+D9…C1(D)=M0(D)g10(D)=(1+D2+D3+D5+D7+D8+…)(1+D)=(1+D)+(D2+D3)+(D3+D4)… =1+D+D2+D4+D5+D6+D7…C2(D)=M0(D)g20(D)=(1+D2+D3+D5+D7+…)(1+D+D2)=(1+D+D2)+(D2+D3+D4)+(D3+D4+D5)+(D5+D6+D7)…=1+D+D6+D9+…它們的系數(shù)序列分別是：C0(D):10110101┅

C1(D):11101111┅

C2(D):11000010┅并/串變換，得輸出序列

C＝{111,011,110,100,010,110,011,110┅}第四十八頁，共一百零三頁，編輯于2023年，星期六例5.2(續(xù)2)

二進(jìn)制(3,2,1)卷積編碼器如圖5-4，若輸入信息流是(101101011100…)，求輸出碼字序列。解：本題k=2,n=3,轉(zhuǎn)移函數(shù)矩陣是2×3多項式矩陣。輸入M0(D)=1+D2+D3+D5+D7+D8+D9+D12+D13+D14…串/并變換后的兩個并行輸入是：(101101011100…)M(D)=1+D2+D3+D5+D7+D8+D9+…(110010…)M0(D)=1+D+D4+…(

011110…)M1(D)=D+D2+D3+D4+…該卷積編碼器的轉(zhuǎn)移函數(shù)矩陣是：

G(D)=g00(D)g10(D)g20(D)=1+DD1+D g01(D)g11(D)g21(D)=D11第四十九頁，共一百零三頁，編輯于2023年，星期六C0(D)=M0(D)g00(D)+M1(D)g01(D)=(1+D+D4+…)(1+D)+(D+D2+D3+…)D=1+D3+D6+…C1(D)=M0(D)g10(D)+M1(D)g11(D)=(1+D+D4+…)D+(D+D2+D3+…)1=D3+D4+D5+D6+…C2(D)=M0(D)g20(D)+M1(D)g21(D)=(1+D+D4+…)(1+D)+(D+D2+D3+…)1=1+D+D3+D5+…利用公式(5-12)并/串變換

=[1+(D3)3+(D3)6+…]+[(D3)3+(D3)4+(D3)5+(D3)6…]D+[1+(D3)+(D3)3+(D3)5+…]D2 =1+D2+D5+D9+D10+D11+D13+D16+D17+…其系數(shù)正是輸出碼元序列(101001000111010011┅)。

第五十頁，共一百零三頁，編輯于2023年，星期六5.2.3卷積碼編碼矩陣和狀態(tài)流圖生成矩陣、轉(zhuǎn)移函數(shù)矩陣重在描述編碼器結(jié)構(gòu)，狀態(tài)流圖和網(wǎng)格圖則利于揭示卷積碼內(nèi)在特性。狀態(tài)：編碼器記憶陣列的內(nèi)容，記作Si

比如圖5-3卷積編碼器，除本時刻輸入外還有兩個存儲器存放前兩時刻的輸入，其內(nèi)容組合有00,01,10,11四種可能，該編碼器有四種狀態(tài)。一般地，圖5-2的移存器陣列有k行L列共k×L個存儲單元，如果這些單元都參與編碼，最多可以有2kL個狀態(tài)?？梢哉J(rèn)為輸出碼組Ci

是本時刻輸入信息組Mi

和本時刻編碼器狀態(tài)Si

的函數(shù)，表示為：Ci=f(Mi,Mi-1,…,Mi-L

)=f(Mi,Si

) (5-13)第五十一頁，共一百零三頁，編輯于2023年，星期六狀態(tài)Si=h(Mi-1,…,Mi-L+1,Mi-L

),如圖5-6所示

圖5-6

狀態(tài)和狀態(tài)轉(zhuǎn)移串/

并變換線性組合器m

i0mi-10…mi-L

0m

i1mi-11…mi-L

1m

ik-1mi-1k-1…mi-L

k-1┇┇MiSiLMi-1

Mi-L…

時刻i的狀態(tài)Si向下一時刻狀態(tài)Si+1的過渡稱為狀態(tài)轉(zhuǎn)移。從圖5-6可見，卷積編碼器狀態(tài)的轉(zhuǎn)移不是任意的，因為移存的規(guī)則決定了下一個狀態(tài)必然是：第五十二頁，共一百零三頁，編輯于2023年，星期六Si+1=h(Mi,Mi-1,…,Mi-L+1

)將Si與Si+1作比較，可知Si+1中的(Mi-1,…,Mi-L+1)是在Si中就已確定的，Si+1的可變因素只有Mi即本時刻輸入信息組一項。對于二進(jìn)碼，Mi可以有2k種組合，所以狀態(tài)轉(zhuǎn)移也只能有2k種。于是，同樣可以把狀態(tài)轉(zhuǎn)移寫成是本時刻信息組Mi

和本時刻編碼器狀態(tài)Si

的函數(shù)

Si+1=h(Mi,Si

) (5-14)式(5-13)、(5-14)的含義是：本時刻輸入信息組Mi和編碼器狀態(tài)Si一起決定了編碼輸出Ci和下一狀態(tài)Si+1。由于編碼器狀態(tài)和信息組花樣都是有限數(shù)量的，所以卷積編碼器可以看成是一個有限狀態(tài)機(jī)，用輸入信息組Mi觸發(fā)的狀態(tài)轉(zhuǎn)移圖來描述。第五十三頁，共一百零三頁，編輯于2023年，星期六

在式(5-14)決定狀態(tài)轉(zhuǎn)移的同時，式(5-13)也決定了輸出碼組，因此確定的狀態(tài)轉(zhuǎn)移必定伴隨著確定的碼組。二元碼的kL個移存器最多可以有2kL個狀態(tài)，但是作為狀態(tài)機(jī)觸發(fā)信號的k重信息分組Mi只能有2k種組合方式，

因此從Si出發(fā)，轉(zhuǎn)移到的下一狀態(tài)只可能是2k種之一，而不是所有的2kL個狀態(tài)。若某卷積編碼器有n個移存器(nkL)，那么編碼器的狀態(tài)數(shù)是2n個。我們可以構(gòu)造一個2n×2n的編碼矩陣，其i行j列的元素cij代表從i狀態(tài)出發(fā)轉(zhuǎn)移到下一時刻j狀態(tài)時發(fā)出的碼組。如果從i狀態(tài)出發(fā)不可能轉(zhuǎn)移到j(luò)狀態(tài)，則相應(yīng)的矩陣元素用“.”來表示第五十四頁，共一百零三頁，編輯于2023年，星期六

根據(jù)編碼矩陣，可以畫出卷積編碼器的狀態(tài)流圖。以狀態(tài)為節(jié)點、狀態(tài)轉(zhuǎn)移為分支、伴隨轉(zhuǎn)移的輸入/輸出碼元與各分支對應(yīng)，就不難得到卷積碼的狀態(tài)流圖。下面舉兩個例子：

例5.1(續(xù)3)二進(jìn)制(3,1,2)卷積編碼器如圖5-3。試分別用編碼矩陣和狀態(tài)流圖來描述該碼。如果輸入信息流是

(101101011100…),求輸出碼字序列。

第五十五頁，共一百零三頁，編輯于2023年，星期六狀態(tài)mi-10mi-20S0 0 0S1 0 1S2 1 0S3 1 1

表5-1(a)編碼器狀態(tài)定義

狀態(tài)輸入

m0i=0m0i=1S0 000 111S1 001 110S2 011 100S3 010 101

表5-1(b)不同狀態(tài)與輸入時編出的碼字狀態(tài)輸入

m0i=0m0i=1S0 S0 S2S1 S0 S2S2 S1 S3S3 S1 S3

表5-1(c)不同狀態(tài)Si與輸入時的下一狀態(tài)Si+1信號 ci0入Mi

輸出

ci1C

i

c

i2

mi0mi-10mi-20第五十六頁，共一百零三頁，編輯于2023年，星期六由表5-1(a)(b)(c)，可用比表更為簡練和直觀的編碼矩陣來表示該卷積碼：編碼矩陣

若輸入信息序列是1011010111…結(jié)果是：S0

1/111S2

0/011

S11/110S2

1/100S30/010

S1……

0/000S01/1110/0011/110S2S10/0111/1000/010S31/101

圖5-7(3,1,2)卷積碼狀態(tài)流圖第五十七頁，共一百零三頁，編輯于2023年，星期六

例5.2(續(xù)3)

某二進(jìn)制(3,2,1)卷積編碼器如圖5-4，分別用編碼矩陣和狀態(tài)流圖來描述該碼。如果輸入信息流是(101101011100…),求輸出碼字序列。解：本題k=2,n=3,有2個移存器、4種狀態(tài)。由于每次并行輸入2比特，即有限狀態(tài)機(jī)觸發(fā)信號2比特，所以從某一狀態(tài)出發(fā)，下一個狀態(tài)可以是4種狀態(tài)之一。由圖5-4列出類似于表5-1(a)(b)(c)的表后可得(3,2,1)卷積碼的編碼矩陣如下。

S0 S1 S2 S3

S0

000 101 011 110 C=S1 111 010 100 001

S2

100 001 111 010

S3

011 110 000 101第五十八頁，共一百零三頁，編輯于2023年，星期六狀態(tài)流圖

00/000

S000/10001/01100/11110/10100/01111/11001/11110/00110/010

S2

S101/10001/00011/01010/11011/001

S311/101

輸入序列(10,11,01,01,11,00,┅)2bit/信息組S0

10/101S111/001S301/000S2

01/111S211/010S300/011S0

…對應(yīng)碼字序列為(101,001,000,111,010,011,…)第五十九頁，共一百零三頁，編輯于2023年，星期六5.2.4卷積碼的網(wǎng)格圖狀態(tài)流圖展示了狀態(tài)轉(zhuǎn)移去向，但不能記錄下狀態(tài)轉(zhuǎn)移軌跡。網(wǎng)格圖可彌補(bǔ)這一缺陷。它可將狀態(tài)轉(zhuǎn)移展開在時間軸上，使編碼全過程躍然紙上，是分析卷積碼有力工具。網(wǎng)格圖以狀態(tài)為縱軸，以時間（抽樣周期T）為橫軸，將平面分割成格狀。狀態(tài)和狀態(tài)轉(zhuǎn)移的定義畫法與流圖法一樣，也是用一個箭頭表示轉(zhuǎn)移，伴隨轉(zhuǎn)移的Mi/Ci表示轉(zhuǎn)移發(fā)生時的輸入信息組/輸出碼組。所不同的是網(wǎng)格圖還體現(xiàn)時間變化，一次轉(zhuǎn)移與下一次轉(zhuǎn)移在圖上頭尾相聯(lián)。第六十頁，共一百零三頁，編輯于2023年，星期六例5.1(續(xù)4)用網(wǎng)格圖描述圖5-3二進(jìn)制(3,1,2)卷積編碼器。若信息序列是(1011010…),求輸出碼字序列。解：由例5.1(續(xù)3)所得的編碼矩陣和狀態(tài)流圖，可得1/1100/0110/0101/1010/0001/1000/0000/0000/0000/0000/0000/0001/1111/1100/0011/1110/0101/1000/0010/0111/110S0S1

S2S3網(wǎng)格圖編碼軌跡圖第六十一頁，共一百零三頁，編輯于2023年，星期六當(dāng)輸入5位信息10110時，輸出碼字和狀態(tài)轉(zhuǎn)移是

S0

1/111S2

0/011S11/110S2

1/100 S30/010S1如果繼續(xù)輸入第6位信息，信息為0或1時，狀態(tài)將分別轉(zhuǎn)移到S0或S2，而不可能轉(zhuǎn)移到S1或S3。網(wǎng)格圖頂上的一條路徑代表輸入全0信息/輸出全0碼字時的路徑，這條路徑在卷積碼分析時常被用作為參考路徑。

第六十二頁，共一百零三頁，編輯于2023年，星期六例5.2(續(xù)4)

二進(jìn)制(3,2,1)卷積編碼器如圖5-4，用網(wǎng)格圖描述該碼。對于輸入(101101011100…),求輸出碼字序列。解：由例5-2(續(xù)3)結(jié)果，可得網(wǎng)格圖如下

10/010001/10011/01010/10100/00001/11101/01111/11000/11111/00100/10010/00110/11001/00011/10100/01110/10111/00101/00001/11111/01000/011網(wǎng)格圖編碼軌跡圖第六十三頁，共一百零三頁，編輯于2023年，星期六卷積碼的生成矩陣、轉(zhuǎn)移函數(shù)矩陣、狀態(tài)流圖和網(wǎng)格圖從不同側(cè)面描述卷積碼。生成矩陣和轉(zhuǎn)移函數(shù)矩陣屬同一大類，它們沿用了分組碼的描述方法，建立了代數(shù)與編碼器的關(guān)聯(lián)。特點是物理意義清楚，代數(shù)量（多項式系數(shù)，矩陣元素）與編碼電路連接線之間的對應(yīng)關(guān)系十分明確，非常利于用VHDL等硬件描述語言來表達(dá)以及用FPGA、DSP等來物理實現(xiàn)。狀態(tài)流圖和網(wǎng)格圖屬于另外一類表示法，狀態(tài)流圖借助信號流圖等圖論工具或理論來分析卷積碼特性，網(wǎng)格圖則適合用于計算機(jī)的窮盡搜索上，它使?fàn)顟B(tài)能在時域展開，所得狀態(tài)軌跡是研究差錯事件、卷積碼距離特性以及維特比最大似然序列譯碼有力工具。

第六十四頁，共一百零三頁，編輯于2023年，星期六5.3

卷積碼的特性對于有限長信息序列如M個k重，當(dāng)M個分組全部輸入編碼器后，雖然再沒有新的信息分組輸入，但由于編碼器內(nèi)L組（約束長度）移存器的記憶效應(yīng)，編碼器將繼續(xù)輸出L個碼字才能將記憶陣列中的內(nèi)容完全移出，這就導(dǎo)致卷積碼碼率由R=k/n降低為。將碼率下降的相對值定義為碼率損失系數(shù)：碼率損失系數(shù)= (5-15)第六十五頁，共一百零三頁，編輯于2023年，星期六

顯然，M相對于L越大則效率損失越小。當(dāng)信息序列很長而使M>>L時，效率損失趨于0因而可忽略不計，每一個k位信息組產(chǎn)生一個n位碼字，卷積編碼碼率與分組碼碼率一樣為R=k/n。相反，M相對于L越小則效率損失越大，當(dāng)M=1時碼率損失系數(shù)接近1。由此可見，卷積碼的適用對象是電路交換的連續(xù)信息流，或包交換的“流媒體”，或復(fù)用級的信息流，而不適合短突發(fā)、目的地分散的用戶端包交換糾錯編碼。第六十六頁，共一百零三頁，編輯于2023年，星期六5.3.1

卷積碼的距離特性卷積碼的性能取決于卷積碼距離特性和譯碼算法。其中，距離特性是卷積碼本身的屬性，它決定了該碼的糾錯能力，而譯碼方法只是研究如何將這種潛在的糾錯能力轉(zhuǎn)化為現(xiàn)實的糾錯能力。表述距離特性的最好方法是利用網(wǎng)格圖。若序列C‘、C”是從同一時刻（不妨稱為0時刻）由零狀態(tài)出發(fā)的兩個不同的碼字序列，它們所對應(yīng)的信息序列分別是M’和M”，且M‘M”。對于二元碼，序列距離d(C’,C”)指漢明距離，等于C‘、C”的對應(yīng)項逐一模2加后所得的序列C的重量，也等于序列C和全零序列0的距離或序列C的重量。d(C',C”)=W(C'C”)=W(C0)=d(C,0)(5-16)第六十七頁，共一百零三頁，編輯于2023年，星期六

式(5-16)默認(rèn)：兩碼字序列之和仍是碼字序列，這樣任意兩碼字序列間最小距離才能等效于全零序列與某非全零序列的距離。全零序列在網(wǎng)格圖上表現(xiàn)為保持在零狀態(tài)的一條橫線，故兩序列的最小距離也就是非全零路徑與全零狀態(tài)路徑距離最小者。序列距離還與序列長度有關(guān)，同一序列對在不同長度比較時顯然距離也不同。將長度l的任意兩序列間的最小距離定義為l階列距離。以長度l為變量的列距離特性稱之為列距離函數(shù)，用dc(l)來表示：

dc(l)min{d([C']l,[C”]l):[M']0[M”]0}(5-17)＝第六十八頁，共一百零三頁，編輯于2023年，星期六所謂[M‘]0[M”]0即“不同”的兩序列，在網(wǎng)格圖上的表現(xiàn)就是從零時刻起兩序列軌跡從零狀態(tài)分道揚鑣形成分叉點。由式(5-16)，式(5-17)可改寫為dc(l)＝min{W([C']l＋[C”]l):[M']0[M”]0}=min{W([C]l):[M]00} (5-18)由于早期卷積碼譯碼方法與