信息論與編碼-卷積碼

卷積碼本章節(jié)教學(xué)內(nèi)容、基本要求、重點與難點1.

教學(xué)內(nèi)容：卷積碼的基本概念。卷積碼的編碼與譯碼。卷積碼的矩陣描述。卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述。維特比譯碼的基本原理。維特比譯碼的性能與應(yīng)用。2.

教學(xué)基本要求：掌握卷積碼的編碼方法。

了解卷積碼的生成矩陣的表示法。

掌握卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述。

掌握卷積碼的維特比譯碼的基本原理和算法實現(xiàn)。

3.

重點與難點：

卷積碼的編碼。卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述。

維特比譯碼的基本原理。

卷積碼（又稱連環(huán)碼）首先由麻省理工學(xué)院于1955年提出。卷積碼與分組碼的不同之處：在任意給定單元時刻，編碼器輸出的n個碼元中，每一個碼元不僅和此時刻輸入的k個信息元有關(guān)，還與前連續(xù)m個時刻輸入的信息元有關(guān)。在同樣的編碼效率R下，卷積碼的性能優(yōu)于分組碼，至少不低于分組碼。卷積碼的譯碼方法代數(shù)譯碼：門限譯碼。譯碼延時是固定的。概率譯碼：序列譯碼。譯碼延時是隨機的。維特比譯碼。譯碼延時是固定的。卷積碼的基本概念卷積碼的生成序列、約束度和約束長度[例1](2,1,3)碼該碼的編碼原理圖示于下頁圖；設(shè)待編碼的信息序列為M；在對信息序列M進(jìn)行編碼之前，先將它每k個碼元分成一組，在每單元時刻內(nèi)，k個碼元串行輸入到編碼器；編碼器由(m+1)個移位寄存器組構(gòu)成，每個移位寄存器組內(nèi)有k級寄存器；g(i,j)：表示常數(shù)乘法器，i=1,2,…,k；j=1,2,…,n；共有n?k

個序列。當(dāng)g(i,j)=1時，常數(shù)乘法器為一條直通的連接線；當(dāng)g(i,j)=0時，連接線斷開。每一個碼元都是k?(m+1)個數(shù)據(jù)組合，每一個碼字需用n?k?(m+1)

個系數(shù)才能描述；開關(guān)K在每一節(jié)拍中移動n次，每一節(jié)拍輸入k個信息元而輸出n個碼元。信息序列M=[m0(1)m1(1)…]；ml(1)表示第l個時刻的第k=1個信息元；卷積碼的生成序列

g(1,1)=[g0(1,1)g1(1,1)g2(1,1)g3(1,1)]=[1011]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)g3(1,2)]=[1111]g(1,1)表明：任一時刻l時，輸出端1的碼元Cl(1)是由此時刻l輸入的信息元ml(1)與前兩個時刻輸入的信息元ml－2(1)以及前三個時刻ml－3(1)輸入的信息元模2加后的和；g(1,2)表明：Cl(2)是由ml(1)、ml－1(1)、ml－2(1)和ml－3(1)的模2和。只要給定g(i,j)以后，就可以生成編碼器輸出的碼元。稱g(1,1)和g(1,2)為(2,1,3)卷積碼的生成序列。第l個時刻的編碼器輸出為：上式表明：任一時刻編碼器的輸出可以由信息元與生成序列的離散卷積運算求出。這就是卷積碼名稱的由來。設(shè)M=[m0(1)m1(1)m2(1)m3(1)]=[1011]，則編碼器兩個輸出端的序列分別是子碼：在任一時刻單元，送入編碼器一個信息元(k=1)，編碼器輸出由2個(n=2)碼元組成的一個碼組，稱之為子碼。每個子碼中的碼元不僅與此時此刻的信息元有關(guān)，而且還與前m個(m=3)時刻的信息元有關(guān)。m：編碼存儲（本例

m=3）

。N=m+1：為編碼的約束度。（本例N=4）。N

n：編碼約束長度。（本例N

n=8）。本例是非系統(tǒng)碼，在碼序列C中的每個子碼不是系統(tǒng)碼字結(jié)構(gòu)。[例2](3,2,1)碼n=3,k=2,m=1；它的任一子碼有3個碼元。每個碼元由此時此刻的2個信息元和前一個時刻進(jìn)入編碼器的2個信息元模2運算和求出。這些信息元參加模2運算的規(guī)則由[n(m+1)]=3×2=6個生成序列{[n

k

(m+1)]=3×2×2=12個系數(shù)}所確定，每個輸出序列含有2個元素。這6個輸出序列是

g(1,1)=[g0(1,1)

g1(1,1)]=[11]g(1,2)=[g0(1,2)

g1(1,2)]=[01]g(1,3)=[g0(1,3)

g1(1,3)]=[11]g(2,1)=[g0(2,1)

g1(2,1)]=[01]g(2,2)=[g0(2,2)

g1(2,2)]=[10]g(2,3)=[g0(2,3)

g1(2,3)]=[10]若待編碼的信息序列M=[m0(1)m0(2)m1(1)m1(2)…ml(1)ml(2)…]則碼序列C中的任一子碼為g(1,1)=[g0(1,1)

g1(1,1)]=[11]g(2,1)=[g0(2,1)

g1(2,1)]=[01]g(1,2)=[g0(1,2)

g1(1,2)]=[01]g(2,2)=[g0(2,2)

g1(2,2)]=[10]g(1,3)=[g0(1,3)

g1(1,3)]=[11]g(2,3)=[g0(2,3)

g1(2,3)]=[10]每個時刻單元輸入編碼器k=2個信息元，它們與前一個時刻進(jìn)入編碼器的2個信息元按卷積關(guān)系進(jìn)行運算后，在輸出端1，2，3分別得到該時刻子碼中的3個碼元。編碼器由N=2個移位寄存器組和模2加法器構(gòu)成，每個移位寄存器組含有k=2級移位寄存器，每級移位寄存器的輸出按一定規(guī)則引出后進(jìn)行模2加的運算。本例也是非系統(tǒng)碼形式的卷積碼。推論：(n,k,m)碼完全由(n

k)個生成序列所生成，每個生成序列中含有(N=m+1)

個元素。碼序列C=[C0(1)C0(2)…C0(n)C1(1)C1(2)…C1(n)…Cl(1)Cl(2)…Cl(n)…]

任一子碼可以由待編碼的信息序列M=[m0(1)m0(2)…m0(k)m1(1)m1(2)…m1(k)…ml(1)ml(2)…ml(k)…]

按如下卷積關(guān)系求出系統(tǒng)碼形式的卷積碼系統(tǒng)卷積碼：是卷積碼的一類。它的碼序列中任一子碼Cl，也是有n個碼元，其前k位與待編碼信息序列中的第l信息組ml(i)相同，而后(n－k)

位監(jiān)督元由生成序列生成；每個碼中的前k位就是此時刻待編碼的k位信息元，所以在生成序列g(shù)(i,j)中有(k

k)

個生成序列是固定的,即任一子碼由下式計算上式表明：在約束長度N內(nèi)，每個子碼中的(n－k)個監(jiān)督元與信息元的卷積關(guān)系。[例3](3,1,2)系統(tǒng)卷積碼：g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[110]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]任一時刻子碼為[例4](3,2,2)系統(tǒng)卷積碼：g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110]該碼的任一子碼Cl

中前兩位與ml(1)、ml(2)相同，后一位的監(jiān)督元由卷積

確定，即g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]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](1)串行輸入、串行輸出的編碼電路非系統(tǒng)碼編碼器：根據(jù)下式構(gòu)造的是非系統(tǒng)編碼器。卷積碼的編碼系統(tǒng)碼編碼器：根據(jù)下式構(gòu)造的是系統(tǒng)編碼器；(2)(n－k)

m級移位寄存器構(gòu)成的并行編碼電路（Ⅰ型編碼電路）這是系統(tǒng)碼形式的一種編碼電路，又稱Ⅰ型編碼電路；將上面的系統(tǒng)碼形式展開后可以改寫為式(6.4.5)。式(6.4.5)表明：在并入并出方式下，為了獲得第l個子碼的(n－k)個監(jiān)督元，需要(n－k)個移位寄存器組，每一組移位寄存器的數(shù)目為m級；它們根據(jù)生成序列g(shù)(i,j)所確定的關(guān)系存儲了第l個信息組相鄰的前m個信息組。2.卷積碼的編碼[例5](3,2,2)碼Ⅰ型編碼電路解：生成序列為g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110]根據(jù)式(6.4.5)，第l個子碼的監(jiān)督元為Cl(3)=ml(1)g0(1,3)+ml(2)g0(2,3)+ml－1(1)g1(1,3)+ml－1(2)g1(2,3)+ml－2(1)g2(1,3)+ml－2(2)g2(2,3)將生成序列諸元素帶入后有Cl(3)=ml(1)+ml(2)+ml－1(2)+ml－2(1)(3,2,2)碼的Ⅰ型編碼電路如圖6.4.7所示。圖6.4.8是(n,k,m)系統(tǒng)碼Ⅰ型編碼電路。2.卷積碼的編碼(3)k

m級移位寄存器編碼電路（Ⅱ型編碼電路）將上面系統(tǒng)形式展開后可以另外改寫為式(6.4.6)。式(6.4.6)表明：只需將第l時刻的k個信息元與前m個時刻的諸信息元按生成序列所確定的關(guān)系模2相加，就可以得到此時刻的(n－k)個監(jiān)督元。Ⅱ型編碼電路由k個移位寄存器組構(gòu)成，每一組有m級移位寄存器。它們分別寄存了前m時刻進(jìn)入編碼器的第一個到第k個信息元。[例6](3,1,2)碼，碼的生成序列為g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]由式(6.4.6)，該碼任一子碼的監(jiān)督元為Cl(2)=ml(1)g0(1,2)+ml－1(1)g1(1,2)+ml－2(1)g2(1,2)=ml(1)+ml－1(1)

Cl(3)=ml(1)g0(1,3)+ml－1(1)g1(1,3)+ml－2(1)g2(1,3)=ml(1)+ml－2(1)其編碼電路如圖6.4.9所示。[例7](3,2,2)碼，已知碼的生成序列為g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[110]由式(6.4.6)，該碼任一子碼的監(jiān)督元為Cl(3)=ml(1)g0(1,3)+ml－1(1)g1(1,3)+ml－2(1)g2(1,3)+ml(2)g0(2,3)+ml－1(2)g1(2,3)+ml－2(2)g2(2,3)=ml(1)+ml－2(1)+ml(2)+ml－1(2)其編碼電路如圖6.4.10所示。圖6.4.11所示的是(n,k,m)碼的Ⅱ型編碼電路。Cl(3)=ml(1)+ml－2(1)+ml(2)+ml－1(2)(4)結(jié)論

以上三種形式電路各有不同的特點。在一般的串行通信方式下，用串行編碼電路比較方便，雖然它所需的電路級數(shù)較多；在并行通信時，若(n－k)<k，采用Ⅰ型編碼電路較Ⅱ型更為簡單；否則，應(yīng)采用Ⅱ型編碼電路。描述卷積碼編譯碼的過程，可以用不同的描述方法：如矩陣法、碼樹法、狀態(tài)圖法、籬笆圖法等。采用何種方法與卷積碼的譯碼方法有很大關(guān)系。代數(shù)譯碼時：用矩陣法對譯碼原理的敘述和理解較方便。概率譯碼時：借助碼樹和籬笆圖能更清晰地分析和了解譯碼過程和碼的性能。(1)卷積碼的生成矩陣(2)卷積碼的監(jiān)督矩陣卷積碼的矩陣描述(1)卷積碼的生成矩陣以(2,1,3)碼為例說明它的生成矩陣是如何得到的g(1,1)=[g0(1,1)g1(1,1)g2(1,1)g3(1,1)]=[1011]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)g3(1,2)]=[1111]其中：將上式表示成矩陣方程，則有：即C∞T=G∞TM∞T=(M∞G∞)T或者C∞=M∞G∞碼的生成矩陣G∞：G∞稱為(2,1,3)碼的生成矩陣。當(dāng)輸入的信息序列是有頭無尾的半無限序列時，生成矩陣也是半無限矩陣，G∞的下標(biāo)就是這個含義，這時碼序列C∞亦為半無限序列。由式(6.4.7)可以看出，生成矩陣G∞中，只要第一行G0G1G2G3確定以后，生成矩陣G∞也就確定了?；旧删仃噂∞

：生成矩陣G∞的第一行為該碼的基本生成矩陣。(2,1,3)碼的基本生成矩陣g∞為：g∞=[G0G1G2G300…]g∞中的每一個元素完全由碼生成序列g(shù)(i,j)諸元素所確定。編碼器的輸出碼序列C∞可根據(jù)生成矩陣得到。(2,1,3)碼：基本生成矩陣中的每個元素G0,G1,G2,G3都是(1×2)階矩陣(k

n,k=1,n=2)，元素的數(shù)目共4個(m+1=N=4)。[例9](3,2,2)非系統(tǒng)卷積碼。它的6個生成序列為：g(1,1)=[g0(1,1)

g1(1,1)g2(1,1)]=[110]g(1,2)=[g0(1,2)

g1(1,2)g2(1,2)]=[010]g(1,3)=[g0(1,3)

g1(1,3)g2(1,3)]=[100]g(2,1)=[g0(2,1)

g1(2,1)g2(2,1)]=[001]g(2,2)=[g0(2,2)

g1(2,2)g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)g2(2,3)]=[111]設(shè)信息序列

M=[m0(1)m0(2)m1(1)m1(2)m2(1)m2(2)m3(1)m3(2)…]由式(6.4.3)，編碼器的輸出C為：6.4.3卷積碼的矩陣描述寫成矩陣方程，可得到(3,2,2)碼的生成矩陣和基本生成矩陣(n,k,m)碼的基本生成矩陣和生成矩陣(1)卷積碼譯碼的種類：卷積碼的譯碼可分為代數(shù)譯碼和概率譯碼。(2)代數(shù)譯碼：從碼的代數(shù)結(jié)構(gòu)出發(fā)，以一個約束度的接收序列為單位，對該接收序列的信息碼組進(jìn)行譯碼。大數(shù)邏輯譯碼是代數(shù)譯碼的主要方法。代數(shù)譯碼中，用矩陣描述比較方便。(3)概率譯碼：從信道的統(tǒng)計特性出發(fā)，以遠(yuǎn)大于約束度的接收序列為單位，對信息碼組進(jìn)行最大似然的判決。維特比譯碼和序列譯碼是其最主要的方法。在維特比譯碼中，用籬笆圖來描述碼的譯碼更為方便。卷積碼的譯碼(1)卷積碼的狀態(tài)定義：卷積碼編碼器要存儲m段消息，這些消息數(shù)據(jù)既要因新的輸入而改變，又要影響當(dāng)前的編碼輸出，因此稱存儲表達(dá)這些數(shù)據(jù)的參量為卷積編碼器的內(nèi)部狀態(tài)，簡稱狀態(tài)。有效存儲單元M：M≤km狀態(tài)向量σ(l)/σ：σ(l)=(σM(l),σM－1(l),…,σ2(l),σ1(l))二元(n,k,m)卷積碼共有2M個不同的狀態(tài)，記為新的狀態(tài)σ(l+1)/σ’轉(zhuǎn)移分支(σ(l),σ(l+1))/(σ,σ’)輸入段U(l)/U輸出段V(l)/V狀態(tài)轉(zhuǎn)移方程：σ’=φ(σ,U)輸出方程：V=ψ(σ,U)卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述[例1](2,1,2)碼的狀態(tài)向量為σ=(σ2σ1)，共有4種狀態(tài)S0,S1,S2,S3，如圖所示。g(1,1)=[g0(1,1)g1(1,1)g2(1,1)]=[111]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)]=[101]其狀態(tài)變化表如表6.4.1所示。該碼的狀態(tài)轉(zhuǎn)移方程和輸出方程分別為

σ1’=Uσ2’=σ1

V1=U+σ1+σ2V2=U+σ2其狀態(tài)轉(zhuǎn)移圖如圖6.4.14和圖5.4.15所示。[例2](3,2,1)碼的狀態(tài)向量為σ=(σ2σ1)，共有4種狀態(tài)S0,S1,S2,S3，如圖6.4.13所示。g(1,1)=[g0(1,1)g1(1,1)]=[11]g(1,2)=[g0(1,2)g1(1,2)]=[01]g(1,3)=[g0(1,3)g1(1,3)]=[11]g(2,1)=[g0(2,1)g1(2,1)]=[01]g(2,2)=[g0(2,2)g1(2,2)]=[10]g(2,3)=[g0(2,3)g1(2,3)]=[10]其狀態(tài)為

S=(σ2σ1)S0=(00),S1=(01),S2=(10),S3=(11)

V=(V1V2V3)U=(U1U2)狀態(tài)方程和輸出方程為

σ1’=U1

σ2’=U2

V1=U1+σ1+σ2V2=U2+σ1V2=U1+U2+σ1(3)卷積碼的柵格圖(籬笆圖)狀態(tài)圖不能反映出狀態(tài)轉(zhuǎn)移與時間的關(guān)系柵格圖/籬笆圖：將開放型的狀態(tài)轉(zhuǎn)移圖按時間順序級聯(lián)形成一個柵格圖。編碼路徑：狀態(tài)序列σ在柵格圖中形成的一條有向路徑。當(dāng)有向路徑始于全“0”狀態(tài)S0，又終于S0時，表明此時編碼器又回到全“0”狀態(tài)，這條始于S0又首次終于S0的路徑是一個卷積碼碼字。紅實線表示U=0時輸入產(chǎn)生的轉(zhuǎn)移分支；黃虛線表示U=1時輸入產(chǎn)生的轉(zhuǎn)移分支。維特比譯碼的基本原理Viterbi譯碼的特點維特比算法是最大似然的序列譯碼算法譯碼復(fù)雜度與信道質(zhì)量無關(guān)運算量和存貯量都與碼長呈線性關(guān)系運算量和存貯量都與狀態(tài)數(shù)呈線性關(guān)系狀態(tài)數(shù)隨k及m呈指數(shù)關(guān)系(1)維特比譯碼的度量待編碼的信息序列M：M=[M0,M1,…,ML－1]；編碼器輸入序列的總長度：k(L+m)；編碼器輸出的碼序列C：C=[C0,C1,…,CL－1]，其中每個子碼Ci含有n個碼元；經(jīng)離散無記憶信道(DMC)傳輸后，譯碼器接收的序列R：R=[R0,R1,…,RL－1]；對于DMC信道：碼序列C的路徑度量

M(R/C)：計算第l時刻到達(dá)狀態(tài)i的最大似然路徑的相似度logp(R/C)；子碼Ci

度量M(Ri/Ci)：計算第l時刻接收子碼Ri

相對于各碼字的相似度logp(Ri/Ci)，也稱為分支度量。(2)維特比譯碼和籬笆圖在維特比譯碼中，用狀態(tài)圖和籬笆圖描述碼的譯碼比較方便。以(2,1,2)碼為例說明

g(1,1)=[g0(1,1)g1(1,1)g2(1,1)]=[111]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)]=[101]圖6.4.20所示的是(2.1.2)碼的籬笆圖：它由結(jié)點和分支構(gòu)成。共有8個結(jié)點（單元時刻），在圖中的上方以0,1,2,…7標(biāo)號，0結(jié)點表示第0個時刻。編碼器的工作過程：在起始的第0個到第2個時刻內(nèi)，編碼器根據(jù)輸入的信息元不同從S0狀態(tài)向四個可能的狀態(tài)之一行進(jìn)；本例假定信息序列長為L=5個信息組，最后m個信息組是全0，所以在籬笆圖上的最后兩個時刻向S0狀態(tài)返回；籬笆圖上各連續(xù)分支組成了可能的路徑，它們代表了各種可能的碼序列；由于可能的輸入信息序列有2kL=25=32個，可能的路徑有32條；每個分支上的數(shù)字表示輸出的子碼。(3)碼參數(shù)和籬笆圖的關(guān)系對(n,k,m)碼而言，編碼器的可能狀態(tài)數(shù)目為2km個，進(jìn)入每個狀態(tài)的分支數(shù)為2k個，從每個狀態(tài)輸出的分支數(shù)2k

個，若輸入信息序列長為k(L+m)（后mk個碼元全為0），則籬笆圖上共有2kL條不同的路徑，相應(yīng)于編碼器輸出的2kL個碼序列。(4)最大似然譯碼/最小距離譯碼譯碼器接收到R序列后，按最大似然法則力圖尋找編碼器在籬笆圖上原來走過的路徑，也就是尋找具有最大度量的路徑；因此，譯碼器必須計算max[M(R/Cj)]，j=1,2,…,2Lk，對BSC信道，就是尋找與R有最小距離的路徑，即計算和尋找min[d(R,Cj)]。譯碼的實現(xiàn)(續(xù)下頁…….)：譯碼的實現(xiàn)：最大似然譯碼方法只是提供了一個譯碼準(zhǔn)則，實現(xiàn)起來尚有一定困難。因為它是考慮了長度為(L+m)n的接收序列來譯碼的，這樣的序列可能有2Lk條；若實際接收序列中，L=50，k=2，則可能的路徑有2100條。譯碼器每接收一個序列R，就要計算1030個似然函數(shù)才能做出譯碼判決。若kL

再大一些，譯碼器按最大似然譯碼準(zhǔn)則譯碼將是很困難的。(5)舉例說明維特比譯碼工作原理維特比提出了一種算法：譯碼器不是在籬笆圖上一次就計算和比較2Lk條路徑，而是接收一段，就計算、比較一段，從而在每個狀態(tài)時，選擇進(jìn)入該狀態(tài)的最可能的分支。維特比譯碼的基本思想：將接收序列R與籬笆圖上的路徑逐分支地比較，比較的長度一般取(5~6)mn，然后留下與R距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐次分支地延長并存儲起來。幸存路徑的數(shù)目等于狀態(tài)數(shù)：2km

以(2,1,2)非系統(tǒng)碼為例說明維特比譯碼的基本思想：設(shè)發(fā)送序列C為全0；接收序列R=[10,00,01,00,00,00,00,…]假設(shè)譯碼器的初始狀態(tài)為全0；第0個時刻：接收序列的第0個分支R0=10進(jìn)入譯碼器。從S0狀態(tài)有兩個分支，它們是00和11，R0與這兩個分支比較，比較的結(jié)果和到達(dá)的狀態(tài)如表6.4.2所示：每個狀態(tài)/節(jié)點都有兩個存儲器：路徑存儲器：存儲該狀態(tài)的部分路徑；路徑值存儲器：存儲達(dá)到該狀態(tài)的部分路徑值(累加距離)。第一個時刻：進(jìn)入譯碼器的接收碼組R1=00和此時刻出發(fā)的四條分支比較，比較結(jié)果和達(dá)到狀態(tài)如表6.4.3所示：從第一個時刻到第二個時刻：共有四條路徑，到達(dá)S0,S1,S2和S3。在第二個時刻以前譯碼器不做任何選擇和判決。每個狀態(tài)的路徑存儲器存儲下此時刻的幸存路徑：0000,0011,1110,1101；每個狀態(tài)的路徑值存儲器存儲了此時刻到達(dá)該狀態(tài)的幸存路徑累加值(累加距離)。從第二個時刻起：第二個接收碼組R2=01進(jìn)入譯碼器，從籬笆圖上可見，從第二個時刻到第三個時刻，進(jìn)入每個狀態(tài)的分支有兩個（或者說在第三個時刻，進(jìn)入每個狀態(tài)的路徑有兩條）。譯碼器將接收碼組R2與進(jìn)入每個狀態(tài)的兩個分支進(jìn)行比較和判決，選擇一個累加距離（部分路徑值）最小的路徑作為進(jìn)入該狀態(tài)的幸存路徑。這樣的幸存路徑共四條，比較和判決的過程如下：經(jīng)過比較后選擇：部分路徑

000000為到達(dá)S0

狀態(tài)的幸存路徑；部分路徑000011為到達(dá)

S1狀態(tài)的幸存路徑；部分路徑110101為到達(dá)

S2狀態(tài)的幸存路徑；部分路徑001101為到達(dá)

S3

狀態(tài)的幸存路徑。按照上述方法，接收序列的諸碼組依次進(jìn)入譯碼器，每個時刻進(jìn)入一個