卷積碼的維特比譯碼卷積編碼器自身具有網(wǎng)格結(jié)構(gòu)，基于此結(jié)構(gòu)我們給出兩種譯碼算法：Viterbi譯碼算法和BCJR譯碼算法。基于某種準(zhǔn)則，這兩種算法都是最優(yōu)的。1967年,Viterbi提出了卷積碼的Viterbi譯碼算法，后來(lái)Omura證明Viterbi譯碼算法等效于在加權(quán)圖中尋找最優(yōu)路徑問(wèn)題的一個(gè)動(dòng)態(tài)規(guī)劃(DynamicProgramming)解決方案，隨后，F(xiàn)omey證明它實(shí)際上是最大似然(ML,MaximumLikelihood)譯碼算法，即譯碼器選擇輸出的碼字通常使接收序列的條件概率最大化。BCJR算法是1974年提出的，它實(shí)際上是最大后驗(yàn)概率(MAP,MaximumAPosterioriprobability)譯碼算法。這兩種算法的最優(yōu)化目標(biāo)略有不同：在MAP譯碼算法中,信息比特錯(cuò)誤概率是最小的，而在ML譯碼算法中，碼字錯(cuò)誤概率是最小的，但兩種譯碼算法的性能在本質(zhì)上是相同的。由于Viterbi算法實(shí)現(xiàn)更簡(jiǎn)單，因此在實(shí)際應(yīng)用比較廣泛，但在迭代譯碼應(yīng)用中，例如逼近Shaimon限的TUrbo碼，常使用BCJR算法。另外，在迭代譯碼應(yīng)用中，還有一種Viterbi算法的變種：軟輸出Viterbi算法(SOVA,Soft-OutputViterbiAlgoritlmi),它是Hagenauer和Hoelier在1989年提出的。為了理解Viterbi譯碼算法，我們需要將編碼器狀態(tài)圖按時(shí)間展開(kāi)(因?yàn)闋顟B(tài)圖不能反映出時(shí)間變化情況)，即在每個(gè)時(shí)間單元用一個(gè)分隔開(kāi)的狀態(tài)圖來(lái)表示。例如(3,1,2)非系統(tǒng)前饋編碼器，其生成矩陣為：G(D)=[1+D1+D21+D+D2](I)(a)圖1(a)(3,1,2)編碼器(b)網(wǎng)格圖(h=5)假定信息序列長(zhǎng)度為h=5,則網(wǎng)格圖包含有h+m4-l=8個(gè)時(shí)間單元，用0到h+m=7來(lái)標(biāo)識(shí)，如圖1(b)所示。假設(shè)編碼器總是從全0態(tài)％開(kāi)始，乂回到全0態(tài)，前m=2個(gè)時(shí)間單元對(duì)應(yīng)于編碼器開(kāi)始從S。"啟程"，最后m=2個(gè)時(shí)間單元對(duì)應(yīng)于向％“返航〃。從圖中我們也可以看到，在前m個(gè)時(shí)間單元或最后m個(gè)時(shí)間單元，并不是所有狀態(tài)都會(huì)出現(xiàn)，但在網(wǎng)格圖的中央部分，在每個(gè)時(shí)間單元都會(huì)包含所有狀態(tài)，且在每個(gè)狀態(tài)都有2k=2個(gè)分支離開(kāi)和到達(dá)。離開(kāi)每個(gè)狀態(tài)的上面分支表示輸入比特為1(即4=1,i表示第i個(gè)時(shí)間單元)，下面的分支表示輸入比特為Oo每個(gè)分支的輸出由11個(gè)比特組成，共有2h=32個(gè)碼字,每個(gè)碼字都可用網(wǎng)格圖中的唯一路徑表示，碼字長(zhǎng)度N=n(h+m)=21。例如當(dāng)信息序列為U=(11101)時(shí)，對(duì)應(yīng)的碼字如圖1(b)中紅線(xiàn)所示，v=(111,010,001, 110,100,101,011)o在一般的(n,k,v)編碼器情況下，信息序列長(zhǎng)度K*=kli,離開(kāi)和進(jìn)入每個(gè)狀態(tài)都有2*個(gè)分支，有2匕個(gè)不同路徑通過(guò)網(wǎng)格圖，對(duì)應(yīng)著2卅個(gè)碼字。假設(shè)長(zhǎng)度K*二kh的信息序列u=(uo,uiUh-i)被編碼成長(zhǎng)度為N二n(h+m)的碼字v=(v0,Vivh+m+1),在經(jīng)過(guò)一個(gè)二進(jìn)制輸入、Q?ary輸出的離散無(wú)記憶信道(DMC,DiscreteMemoiylessChannel)后，接收序列為r=(ro3'ii'h+in+i)o也可表示為：U=(UO,U1UK*-1),v=(vo,ViVN-1)?r=(ro,rii'N-i)?譯碼器對(duì)接收到的序列I*進(jìn)行處理，得到V的估說(shuō)。在離散無(wú)記憶信道情況下，最大似然譯碼器是按照最大化對(duì)數(shù)似然函數(shù)logP(rIv)作為選擇◎的準(zhǔn)則。因?yàn)閷?duì)于DMC,P(r|v)=nF擴(kuò)ip(吋刃)=n￡ip(r仙)(2)兩邊取對(duì)數(shù)后為：logP(r|v)=S?JiJn-1logP(rf|vr)=S&logPfrd^)(3)其中P(n|V1)是信道轉(zhuǎn)移概率，當(dāng)所有碼字等概時(shí)，這是個(gè)最小錯(cuò)誤概率譯碼準(zhǔn)則。對(duì)數(shù)似然函數(shù)logP(rIv),用M(r|v)表示，稱(chēng)為路徑度量(pathmetric)；logP(ri|Vi),稱(chēng)為分支度量(branchmetric),用M(n|Vi)表示；logP(n|Vi)稱(chēng)為比特度量(bitmetric),用M(n|vi)表示，這樣(3)式可寫(xiě)為：M(r|v)=廉『5(咁vz)= 可)(4)如果我們只考慮前t個(gè)分支，則部分路徑度量可表示為：M(r|v)=SUM(rz|vz)=跚可)(5)對(duì)于接收序列r,Viterbi算法就是通過(guò)網(wǎng)格圖找到具有最大度量的路徑，即最大似然路徑(碼字)。在每個(gè)時(shí)間單元的每個(gè)狀態(tài)，都增加2*個(gè)分支度量到以前存儲(chǔ)的路徑度量中(加)；然后對(duì)進(jìn)入每個(gè)狀態(tài)的所有2*個(gè)路徑度量進(jìn)行比較(比)，選擇具有最大度量的路徑(選)，最后存儲(chǔ)每個(gè)狀態(tài)的幸存路徑及其度量。Viterbi算法：Step1:在t=m時(shí)間單元開(kāi)始，計(jì)算進(jìn)入每個(gè)狀態(tài)的單個(gè)路徑的部分度量，存儲(chǔ)每個(gè)狀態(tài)的路徑(幸存)及其度量；Step2:tet+l,對(duì)進(jìn)入每個(gè)狀態(tài)的所有2k個(gè)路徑計(jì)算部分度量，并加上前一時(shí)間單元的度量。對(duì)于每個(gè)狀態(tài)，比較進(jìn)入該狀態(tài)的所有2k個(gè)路徑度量，選擇具有最大度量的路徑，存儲(chǔ)其度量，并刪掉其他路徑。Step3:如果t<h+m,返回step2；否則，就停止。Viterbi算法的基本計(jì)算"加、比、選"體現(xiàn)在step2o注：實(shí)際工程中，在每個(gè)狀態(tài)存儲(chǔ)(在stepl和step2)的是對(duì)應(yīng)于幸存路徑的信息序列，而不是幸存路徑自身，這樣當(dāng)算法結(jié)束時(shí)，就無(wú)需再通過(guò)估計(jì)碼字◎來(lái)恢復(fù)信息序列@從時(shí)間單元m到h,有2^個(gè)幸存路徑，每個(gè)狀態(tài)(共有2V個(gè)狀態(tài))一個(gè)。隨后，幸存路徑數(shù)就會(huì)變少，因?yàn)楫?dāng)編碼器回到全0態(tài)時(shí)，狀態(tài)數(shù)就會(huì)變少。最后，在時(shí)間單元h+m,就只有一個(gè)狀態(tài)(即全0態(tài))，因此，也就只有一個(gè)幸存路徑了，算法中止。定理1：在Viterbi算法中最后的幸存路徑0是最大似然路徑，即M(r\v)>M(r\v),forv(6)從實(shí)現(xiàn)的角度看，用正整數(shù)度量來(lái)表示要比用實(shí)際的比特度量表示更方便。比特度量M(n|V1)二logP(n|V1)可用C2【logP(I*1|V1)+C1]來(lái)代替，其中C1是任意實(shí)數(shù)，C2是任意正實(shí)數(shù)。可證明，如果路徑V最大化M(r|v)= V[)=S^logPCrJ^),則它也最大化c2|logP(n|vi)+ci],因此可以使用修正的度量,且不影響Viterbi算法的性能。如果選擇C1使最小度量為0,則C2可選擇為使所有度量近似為整數(shù)。這樣，由于用整數(shù)來(lái)近似表示度量，Viterbi算法的性能變成了次最優(yōu)算法，但通過(guò)選擇C1和C2可使得這種性能降低非常小。例1：對(duì)于二輸入、4-ary輸出的DMC信道下的Viterbi算法二輸入、4?ary輸出的DMC如圖2所示。該信道的比特度量如圖3(a)所示(按照底為10的對(duì)數(shù)計(jì)算)，選擇ci=l,c2=173,得到整數(shù)度量表如圖3(b)所示。圖2二輸入、4?ary輸出DMC信道模型X01X010212110-0.4-0.52-0.7-1.011.0-0.7-0.52-0.4X01021211010850105810(a)(b)圖3度量表假設(shè)圖1中的一個(gè)碼字在這樣的信道中傳輸，接收到的序列為：r=(I1I2O1,I1I1O2,liiiOi,liiiii,O1I2O1,12O2I1,12O1I1) (7)對(duì)該序列進(jìn)行Viterbi譯碼如圖4所示。每個(gè)狀態(tài)上的數(shù)字表示幸存路徑的度量，另一個(gè)路徑就將被刪除(綠線(xiàn)部分)。這樣最后的碼字(紅線(xiàn)部分的輸出)判決為：0=(111,010,110,011,000,000,000) (5.8)它對(duì)應(yīng)的輸入序列為0=(11000)。注意：網(wǎng)格圖中最后的m=2個(gè)分支是清空寄存器的，不能算作為輸入信息序列。

36 60 70 104r=(l]12°i36 60 70 104r=(l]12°i，1111O2,11110)11111p OJ2O1，I2O2119I2O111)圖4DMC信道下的Viterbi算法在BSC信道情況下,轉(zhuǎn)移概率為p<l/2,接收序列r是2?在BSC信道情況下,對(duì)數(shù)似然函數(shù)為:logP(rIv)二d(r,v)logp/(l?p)+Nlog(l-p)(9)其中d(r,v)是I*和V之間的Hamming距離。由于logp/(l-p)<0,且Nlog(l-p)對(duì)所有V來(lái)說(shuō)都是一個(gè)常數(shù)，因此最大似然譯碼(maxlogP(r|v))就