信息論與編碼9

第九章卷積碼內(nèi)容提要卷積碼充分利用了前后碼段之間的相關(guān)性，是一種非常重要的差錯(cuò)控制編碼。。本章首先介紹卷積碼的基本概念，然后介紹卷積碼的數(shù)學(xué)描述方法和圖形描述方法，最后介紹一種最佳的卷積碼概率譯碼方法—Viterbi譯碼。第九章

卷積碼

卷積碼用(n，k，m)表示，編碼時(shí)n

k個(gè)檢驗(yàn)元不僅與當(dāng)前時(shí)刻的k個(gè)信息元有關(guān)，而且與前面m個(gè)時(shí)刻的信息段有關(guān)，因此卷積碼的編碼器中需要有存儲(chǔ)m個(gè)信息段的記憶部件。定義m為編碼存儲(chǔ)，代表了信息段需存儲(chǔ)的級(jí)數(shù)。定義(m+1)為編碼約束度，表明編碼過(guò)程中互相約束的碼段個(gè)數(shù)。卷積碼的k和n一般較小，碼率較低。卷積碼的冗余度高，糾錯(cuò)能力較強(qiáng)。9.1卷積碼的基本概念卷積碼編碼器的原理圖

例9.1

（2，1，2）卷積碼的編碼器

碼段長(zhǎng)n=2，每個(gè)碼段的信息位長(zhǎng)度k=1，編碼存儲(chǔ)m=2。第i時(shí)刻的碼段不僅與當(dāng)前的信息位ui有關(guān)，還與前2個(gè)碼段的信息位ui

1，ui

2有關(guān)。

u=[u0u1u2…]時(shí)鐘節(jié)拍輸入u移存器初態(tài)移存器次態(tài)輸出c110010112010011030010011設(shè)移位寄存器D0D1初始狀態(tài)為全0，當(dāng)輸入信息序列u=[100]時(shí)，編碼器的工作過(guò)程輸入信息序列u

=[100]時(shí)，輸出碼字c=[111011]。每個(gè)碼段的最左邊碼元與信息碼元不同，所以是非系統(tǒng)碼編碼器。

例9.2

（3，2，2）卷積碼的編碼器

第i時(shí)刻信息段，碼段，編碼器由2個(gè)移存器構(gòu)成。

輸入u=[100000]的編碼過(guò)程

時(shí)鐘節(jié)拍輸入ui移位寄存器初態(tài)移位寄存器次態(tài)輸出ci110000110120001000013000000000輸入u=[100000]的編碼輸出c

=[101001000]；同理輸入u

=[010000]的編碼輸出c

=[010001001]；碼段左邊2個(gè)碼元和輸入的信息元始終一致，所以是系統(tǒng)碼。9.２卷積碼的數(shù)學(xué)描述9.2.1卷積碼的矩陣描述討論例9.2的（2，1，2）卷積碼的生成矩陣

C=uG∞

，G

被稱(chēng)為（2，1，2）卷積碼的生成矩陣，這是一個(gè)半無(wú)限矩陣。=[1110001000101100…]

G

完全由矩陣的第一行確定。將第一行取出并表示為碼的基本生成矩陣

g

=[11101100…]g

其實(shí)就是當(dāng)輸入信息序列為沖激序列u

=[100…]時(shí)，卷積碼編碼器的沖激響應(yīng)。令信息序列u=[10101]，則輸出碼字討論例9.2（3，2，2）卷積碼的生成矩陣沖激響應(yīng)為u=

[100000…]時(shí)，c=

[101001000000…]；

u=

[010000…]時(shí)，c=

[010001001000…]得該碼的基本生成矩陣為：將g

經(jīng)移位得生成矩陣

基本生成矩陣g

=

[G0

G

1

G

2…G

m0…]

其中生成子矩陣生成矩陣中每一行的分組數(shù)（即碼段數(shù)）為編碼約束度m+1，矩陣的總行數(shù)取決于輸入信息序列的長(zhǎng)度。一般情況下，(n，k，m)卷積碼的生成矩陣表示為9.2.2卷積碼的多項(xiàng)式描述第j路輸出碼段延時(shí)算子x表示卷積碼編碼過(guò)程中一個(gè)時(shí)間單位的延時(shí)，第i路輸入信息段

將生成子矩陣Gl（0≤l≤m）的i行j列(1≤j≤n，1≤i≤k)取出，組合后得到生成序列表示成多項(xiàng)式為

表示u(i)～C(j)的生成情況，其中代表了編碼器中C(j)生成時(shí)u(i)的l次移位參與了異或，因此第j路輸出的碼多項(xiàng)式為生成多項(xiàng)式矩陣G(x)

碼多項(xiàng)式為c(x)=u(x)﹒G(x)=[u(1)(x)u(2)(x)…

u(k)(x)]﹒G(x)=[c(1)(x)c(2)(x)…

c(n)(x)]=c(1)(xn)+x

c(2)(xn)+x2

c(3)(xn)+…

+xn

1c(n)(xn)例9.2（3，2，3）卷積碼的多項(xiàng)式描述當(dāng)u

=

[10110111]時(shí)，c(x)=u(x)﹒G(x)=

=[1+x+x3

x+x2+x31+x3+x4+x5]=[1+x2+x3+x4+x7+x9

+x10+x11+x14+x17]與碼序列[101110010111001001000…]一致。9.3卷積碼的圖形表示方法

9.3.1狀態(tài)圖輸入u

初態(tài)Si次態(tài)Sj

輸出C000100010110001101011111

00001011011011010011100001011110

在卷積碼編碼器中，寄存器任一時(shí)刻存儲(chǔ)的數(shù)據(jù)稱(chēng)為編碼器的一個(gè)狀態(tài)，隨著信息序列的不斷輸入，編碼器的狀態(tài)在不斷變化，同時(shí)輸出的碼元序列也相應(yīng)地發(fā)生改變。例9.1（2，1，2）卷積碼的狀態(tài)表

狀態(tài)圖中，用實(shí)線表示信息0輸入，虛線表示1輸入，若輸入信息u

=[10101]，狀態(tài)轉(zhuǎn)移為S0→S1→S2→S1→S2→S1→S2→S0，相應(yīng)輸出碼元序列為[11100010001011]。編碼器輸出的碼元序列是在信息序列的第一個(gè)碼元輸入直到最后一個(gè)碼元完全移出移位寄存器所產(chǎn)生的。要求有用信息序列輸入完畢后，應(yīng)再向編碼器輸入mk個(gè)全0碼元，所以最終狀態(tài)應(yīng)回到初始狀態(tài)S0。9.3.2樹(shù)圖

樹(shù)圖中，節(jié)點(diǎn)處符號(hào)為移存器狀態(tài)，分支上的數(shù)據(jù)為輸出碼段，上分支為輸入信息0，下分支為輸入信息1。

從碼樹(shù)圖上觀察，輸入無(wú)限長(zhǎng)信息序列，就可以得到一個(gè)無(wú)限延伸的樹(shù)狀結(jié)構(gòu)圖。輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼元序列。

碼樹(shù)圖的最大特點(diǎn)是時(shí)序關(guān)系清晰，且對(duì)于每一個(gè)輸入信息序列都有一個(gè)唯一的不重復(fù)的樹(shù)枝結(jié)構(gòu)相對(duì)應(yīng)。缺點(diǎn)是進(jìn)行到一定時(shí)序后，狀態(tài)將產(chǎn)生重復(fù)且樹(shù)圖越來(lái)越復(fù)雜。

狀態(tài)圖從狀態(tài)上看最為簡(jiǎn)潔，但時(shí)序關(guān)系不清晰。

一般地，對(duì)于(n，k，m)卷積碼來(lái)說(shuō)，從每個(gè)節(jié)點(diǎn)發(fā)出2k條分支，每條分支上標(biāo)有n長(zhǎng)輸出數(shù)據(jù)，最多可有2km種不同狀態(tài)。

9.3.3網(wǎng)格圖

樹(shù)圖中，從某一階節(jié)點(diǎn)開(kāi)始所長(zhǎng)出的分支從縱向看是周期重復(fù)的。因此在第m+1階節(jié)點(diǎn)以后，將樹(shù)圖上處于同一狀態(tài)的同一節(jié)點(diǎn)折疊起來(lái)加以合并，就可以得到網(wǎng)格圖。

網(wǎng)格圖中實(shí)線表示輸入為0的分支，虛線表示輸入為1的分支，分支上標(biāo)志的n位數(shù)據(jù)表示相應(yīng)的編碼輸出C。

網(wǎng)格圖中每一種信息序列有唯一的網(wǎng)格編碼路徑。

從第m至

l節(jié)點(diǎn)，編碼器處于穩(wěn)定的狀態(tài)轉(zhuǎn)移中，并且各節(jié)點(diǎn)的網(wǎng)格結(jié)構(gòu)均相同。在l節(jié)點(diǎn)后m個(gè)移存器尚需轉(zhuǎn)移m個(gè)狀態(tài)，才能回到初始狀態(tài)S0。由于l

到l+m節(jié)點(diǎn)過(guò)程中輸入補(bǔ)充0，所以只有實(shí)線分支。9.4Viterbi譯碼

Viterbi譯碼基于碼的網(wǎng)格圖結(jié)構(gòu)，是一種極大似然譯碼方法。它具有以下優(yōu)點(diǎn)：①有固定的譯碼時(shí)間；②適于譯碼器的硬件實(shí)現(xiàn)，運(yùn)行速度快；③譯碼的錯(cuò)誤概率可以達(dá)到很?。虎苋菀讓?shí)現(xiàn)，成本低。Viterbi譯碼步驟（1）在j=m節(jié)點(diǎn)處，對(duì)進(jìn)入每一狀態(tài)的長(zhǎng)度為j=m

的部分路徑，計(jì)算輸出數(shù)據(jù)與對(duì)應(yīng)接收的j個(gè)n長(zhǎng)碼段的漢明距離。將部分路徑存儲(chǔ)作為被留選的幸存路徑。（2）j增加1，把此時(shí)進(jìn)入每一狀態(tài)的所有分支與前一階節(jié)點(diǎn)處留選的幸存路徑累積計(jì)算與相應(yīng)接收碼段的漢明距離，每個(gè)狀態(tài)留選漢明距離最小者為對(duì)應(yīng)的幸存路徑，其余路徑則刪除。（3）重復(fù)步驟②，直至j=l+m，最終整個(gè)網(wǎng)格圖中只剩一條幸存路徑，譯碼結(jié)束。Viterbi譯碼方法采用分段處理，每個(gè)碼段根據(jù)接收的碼元序列，在網(wǎng)格圖上尋找與接收碼相比差距最小的可行路徑。對(duì)于BSC信道，可等價(jià)為確定與接收碼段具有最小漢明距離的路徑。由m至l階節(jié)點(diǎn)，網(wǎng)格圖中2km個(gè)狀態(tài)中每一個(gè)狀態(tài)有一條幸存路徑；但在l階節(jié)點(diǎn)后，狀態(tài)數(shù)目減少，幸存路徑隨之相應(yīng)減少；至l+m階節(jié)點(diǎn)時(shí)，僅剩一條幸存路徑，它就是譯碼器輸出的最佳估值碼元序列的路徑。如果在某階節(jié)點(diǎn)，某狀態(tài)的兩條路徑具有相同的漢明距離，這時(shí)需觀察下一階節(jié)點(diǎn)累積的漢明距離，再選定最小距離的路徑。輸入信息序列u

=[10101]至例10.1編碼器，通過(guò)BSC送入譯碼器的序列y=[11100111001011]，采用Viterbi譯碼

yi為接收碼段，d為漢明距離，為信息估值。在圖(a)中，從初始狀態(tài)到達(dá)j=2階節(jié)點(diǎn)的4種狀態(tài)有4條路徑，它們與接收序列y0y1=[1110]的漢明距離分別為3，3，0，2，依次作為4種狀態(tài)的幸存路徑。j=2y0=11y1=10d0000

S0=003001111

S1=1030110

S2=0101001

S3=11211(a)

j=3時(shí)，沿前一階節(jié)點(diǎn)的幸存路徑到達(dá)S0狀態(tài)有2條路徑和，與y0y1y2=[111001]的漢明距離分別為4和1，選取后者為S0狀態(tài)的幸存路徑。同樣S1，S2，S3狀態(tài)也都有2條路徑，分別留選距離最小者為幸存路徑，其余路徑則刪除。j=3y0=11y1=10y2=01d00S011001111

11S111011000

S20101211001S33011(b)

由j=3的S0,S1,S2狀態(tài)轉(zhuǎn)移到j(luò)=4的S0，S1，S2，S3狀態(tài)，有4條路徑與y0y1y2y3=[11100111]比較，具有最小漢明距離，被留選下來(lái)。j=4y0=11y1=10y2=01y3=11dS0

1111

11

1121100

S111001100010S2210100101

01

S321011(c)j=5y0=11y1=10y2=01y3=11y4=00d00S02110001111

S111112101010010001010S2210010

0101

01S3210011(d)j=6時(shí)，有用信息已輸入完畢，輸入端補(bǔ)充0至編碼器，所以只剩下S0，S2兩種狀態(tài)，而S0狀態(tài)的2條路徑與y0y1y2

y3y4

y5=[111001110010]的距離都是3，因此都被留存。j=6y0=11y1=10y2=01y3=11y4=00y5=10d00003110000S01001001111

11

11

11

S1

1010

1010

S200