基于 Vertibi算法的卷積碼解碼設(shè)計(jì)實(shí)現(xiàn)

本文主要是基于 Vertibi算法的卷積碼解碼設(shè)計(jì)實(shí)現(xiàn)的相關(guān)介紹，并就卷積編碼展開(kāi)了詳盡的闡述。

卷積編碼

在信道編碼研究的初期，人們探索、研究出各種各樣的編碼構(gòu)造方法，其中包括卷積碼。早在1955年，P.Elias首先提出了卷積碼。但是它又經(jīng)歷了十幾年的研究以后，才開(kāi)始具備應(yīng)用價(jià)值。在這十幾年期間，J.M.Wozencraft提出了適合大編碼約束度的卷積碼的序列譯碼，J.L.Massey提出了實(shí)現(xiàn)簡(jiǎn)單的門(mén)限譯碼，A.J.Viterbi提出了適合小編碼約束度的卷積碼Viterbi算法。20年后，即1974年，L.R.Bahl等人又提出一種支持軟輸入軟輸出（SISO，Soft-Input Soft-Output）的最大后驗(yàn)概率（MAP，Maximum A Posteriori）譯碼——BCJR算法。其中，Viterbi算法有力地推動(dòng)了卷積碼的廣泛應(yīng)用，BCJR算法為后續(xù)Turbo碼的發(fā)現(xiàn)奠定了基礎(chǔ)。

淺談卷積編碼

實(shí)際上編碼過(guò)程就可以應(yīng)用一個(gè)經(jīng)典的“狀態(tài)機(jī)模型”，而狀態(tài)機(jī)模型的不同表達(dá)方式也使得整個(gè)編碼過(guò)程在時(shí)間和空間兩個(gè)維度展現(xiàn)出來(lái)。例如，狀態(tài)圖，即是一個(gè)很好的表示狀態(tài)變化的圖形。但是由于循環(huán)反復(fù)的利用狀態(tài)信息，但在時(shí)間上，并未很好的體現(xiàn)卷積碼的編碼過(guò)程。相比，樹(shù)形圖，在時(shí)間上進(jìn)行延展，很直觀的表現(xiàn)出狀態(tài)變化的過(guò)程，但是狀態(tài)信息未重復(fù)利用，使得存儲(chǔ)空間大小得到限制（指數(shù)增加）。最后，網(wǎng)格圖很好的展現(xiàn)了時(shí)間和空間兩個(gè)維度信息，很適合分析卷積碼的編碼過(guò)程。而用Matlab實(shí)現(xiàn)卷積碼編碼的時(shí)候，我按照傳統(tǒng)卷積碼編碼方法（只考慮實(shí)現(xiàn)，未考慮算法的優(yōu)化），中規(guī)中矩的編碼思路，但在速度上，并未得到很好的保證。而老師給的編程思想則是：給出每個(gè)以為寄存器中隨時(shí)間變化存儲(chǔ)的二進(jìn)制信息。例如，4個(gè)移位寄存器，則每個(gè)移位寄存器存儲(chǔ)的信息分別為：[abcdefg000；0abcdefg00；00abcdefg0；000abcdefg]，所以矩陣的縱列信息即為所有寄存器中瞬時(shí)狀態(tài)信息，而生成多項(xiàng)式中數(shù)值為‘1’的移位寄存器存儲(chǔ)比特信息將參與mod2運(yùn)算。這樣利用矩陣的乘法直接完成查找移位寄存器中對(duì)應(yīng)生成多項(xiàng)式數(shù)值為‘1’位置的信息。相比我的編碼思路（循環(huán)查找寄存器里對(duì)應(yīng)生成多項(xiàng)式數(shù)值為‘1’的信息），運(yùn)算速度大大提升。同時(shí)，在對(duì)狀態(tài)機(jī)模型的認(rèn)識(shí)也進(jìn)一步深入，即，編碼過(guò)程為移位寄存器中狀態(tài)不斷變化的過(guò)程。（編碼用‘狀態(tài)’描述，并且將‘狀態(tài)’融入到算法實(shí)現(xiàn)中）

在完成解碼的過(guò)程中，找了許多關(guān)于Viterbi算法的papers，但在編碼過(guò)程對(duì)狀態(tài)機(jī)模型的認(rèn)識(shí)過(guò)程中，意識(shí)到，解碼過(guò)程對(duì)狀態(tài)機(jī)模型的依賴。實(shí)際上，Viterbi算法就是一個(gè)在狀態(tài)機(jī)模型基礎(chǔ)上不斷減少可能路徑的一個(gè)過(guò)程。因?yàn)榻獯a是編碼的一個(gè)逆序過(guò)程，接受比特和初始狀態(tài)是我們已知的信息，我們無(wú)法找到一個(gè)逆序的算法來(lái)計(jì)算輸入比特信息。

所以Viterbi算法利用的就是‘重新編碼’的思想，計(jì)算每條路徑可能的概率值大小，用概率最大的路徑來(lái)模擬編碼過(guò)程。從而得到輸入比特信息。而狀態(tài)機(jī)模型的應(yīng)用大大提升了解碼過(guò)程尋找正確路徑的速度。而在用matlab算法實(shí)現(xiàn)的過(guò)程中，老師用initial state和next state作為矩陣的行列號(hào)，查找輸入比特的速度比我實(shí)現(xiàn)時(shí)不斷循環(huán)查找狀態(tài)表提升很多，也使最后所畫(huà)的誤碼率對(duì)比圖達(dá)到理想的接受比特個(gè)數(shù)（提高了系統(tǒng)的運(yùn)算能力）。

還記得答辯時(shí)候老師問(wèn)我的那個(gè)問(wèn)題：如果接受比特中錯(cuò)誤比特的數(shù)量一定（假設(shè)都是10個(gè)），那么錯(cuò)誤比特均勻分布和集中分布兩種方式哪個(gè)誤碼率性能比較好？聽(tīng)到問(wèn)題的時(shí)候，腦袋想過(guò)的編碼過(guò)程，錯(cuò)誤比特的分布情況，所以回答的一塌糊涂。后來(lái)才在老師的解釋下，明白了題目的意思。老師想問(wèn)的是，錯(cuò)誤比特（信道噪聲影響）的排列分布對(duì)解碼時(shí)誤碼率性能的影響。卷積碼編碼的時(shí)候就假設(shè)，每個(gè)block是相對(duì)獨(dú)立的，而瞬時(shí)編碼的時(shí)候，輸出比特不僅僅與當(dāng)前的輸入比特信息有關(guān)，還與之前的若干blocks里的信息有關(guān)（聯(lián)合概率）。所以在解碼的時(shí)候，每組接收比特的信息也與之前的若干比特信息是相關(guān)聯(lián)的。

所以，如果誤碼比較集中，在Viterbi時(shí)，權(quán)值的計(jì)算時(shí)就會(huì)相對(duì)增加權(quán)值的比重（大的越大，小的越小），容易將該條路徑淘汰。而誤碼分散排列時(shí)，一些權(quán)值有可能比較接近，無(wú)法淘汰。因此誤碼集中分布的情況，系統(tǒng)的誤碼率性能較好。老師的問(wèn)題，一定程度上又深化了我對(duì)整個(gè)系統(tǒng)認(rèn)識(shí)的深度。不僅僅在編碼上，而且在解碼端理解卷積碼的意義：用相鄰信息編碼、解碼，使得信息能在信道中準(zhǔn)確傳輸。

而拋開(kāi)狀態(tài)機(jī)模型的應(yīng)用，Viterbi算法的關(guān)鍵在于路徑選擇的權(quán)值（metric）問(wèn)題。權(quán)值的計(jì)算的優(yōu)化能大大提升系統(tǒng)誤碼率的大小。這樣，就到了最后一個(gè)問(wèn)題，硬判決和軟判決對(duì)系統(tǒng)誤碼率的提升能力分析。從星座圖的角度看，誤碼率性能體現(xiàn)在是否能夠找到正確的接收比特組合信息，即糾正錯(cuò)碼的距離（糾正錯(cuò)碼的能力）。

硬判決在解調(diào)時(shí)直接將接受比特映射到‘0’，‘1’的星座圖空間上，那么使用漢明距離（100%的概率決定接收比特信息）就可以將接收比特投射到相應(yīng)的星座圖位置，這樣，如果產(chǎn)生錯(cuò)碼，硬判決解碼的糾正錯(cuò)碼的距離將很大（正方形的邊長(zhǎng)或?qū)蔷€）。

而軟判決解調(diào)時(shí)則在‘0’和‘1’直接設(shè)置多個(gè)門(mén)限，使得接收比特可以投射到范圍內(nèi)的某個(gè)區(qū)域里，而通過(guò)區(qū)域比特的組合信息，使用歐幾何距離（用一定概率值分析接收比特信息）計(jì)算最準(zhǔn)確的接收比特，這樣，如果產(chǎn)生錯(cuò)碼，軟判決糾正錯(cuò)碼的距離將變?。▓Db中實(shí)點(diǎn)位置，糾正錯(cuò)碼距離提升），從而得到相對(duì)準(zhǔn)確的接收比特。因此，軟判決的解碼過(guò)程誤碼率性能將優(yōu)于硬判決。

基于 Vertibi算法的卷積碼解碼設(shè)計(jì)實(shí)現(xiàn)

關(guān)于Vertibi算法的原理，網(wǎng)上相關(guān)的資料很多，況且來(lái)看這篇文章的同學(xué)對(duì)原理應(yīng)該不陌生，在這里只是簡(jiǎn)單提提。我們以（2,1）卷積編碼器為例，其核心可用下面幾幅圖表示

每個(gè)卷積編碼器可用狀態(tài)轉(zhuǎn)移來(lái)表示，因此圖中a,b,c,d代表編碼器所處的4個(gè)狀態(tài)，而j表示時(shí)刻，實(shí)線表示輸入為1，虛線表示輸入為0，而線上的數(shù)字表示輸入對(duì)應(yīng)的輸入；打個(gè)比方，圖中(a,0)點(diǎn)到(c,1)點(diǎn)的連接表示：當(dāng)輸入為0時(shí)，寄存器的狀態(tài)從0時(shí)刻的a（我們?cè)O(shè)為兩個(gè)寄存器的狀態(tài)全為0，記為00）到1時(shí)刻的c（記為10），且伴隨著輸出為11

而Vertibi譯碼則是從上圖中找出一條路，使這條路徑對(duì)應(yīng)的輸出序列與輸入序列的漢明距離最小（既“最像”）

面對(duì)這種問(wèn)題，我們首先想到的便是樹(shù)的深度遍歷，既找出所有路徑然后看看誰(shuí)“最像”。然而。Vertibi就是靠這個(gè)成為南加州大學(xué)知名校友，創(chuàng)立高通公司，并且成功讓系主任花半節(jié)課將他的生平，自然有其妙♂處。

請(qǐng)看下圖

它闡述了一個(gè)定理：如果P是最短路徑，對(duì)于P上任意一點(diǎn)x，P1一定是最短路徑。
這個(gè)定理可以很輕松的用反證法證明

之后的東西好難用語(yǔ)言描述所以我們直接看偽代碼吧

在這里做些解釋

首先定義路徑長(zhǎng)度為兩個(gè)狀態(tài)轉(zhuǎn)移時(shí)的輸出序列與相應(yīng)的輸入序列的漢明距離

u[j][s]代表J時(shí)刻到達(dá)s狀態(tài)的累計(jì)路徑長(zhǎng)度

l[t][s]代表從t狀態(tài)轉(zhuǎn)到l狀態(tài)的的路徑長(zhǎng)度

B[s]代表s狀態(tài)的對(duì)應(yīng)解碼序列

由于最后路徑會(huì)回到a狀態(tài)（既寄存器為00狀態(tài)），因此按照以上方法執(zhí)行后，B(a)即為結(jié)果

int vertibi（int *seq， int seqLen， int outnum，int innum，int stat［］［MAXSTAT］， int statRow， int out［］［MAXSTAT］［MAXBLOCK］，int *res ， int *fixed） {

/*seq為輸入序列，seqLen為輸入序列長(zhǎng)度，outnum為輸出數(shù)（對(duì)于（2，1）卷積碼而言為2），innum位輸入數(shù)（對(duì)于（2，1）卷積碼而言為1），stat為二維的狀態(tài)轉(zhuǎn)移表（比如說(shuō)，若狀態(tài)a轉(zhuǎn)到狀態(tài)c需要輸入1，則stat［1］［3］=1，無(wú)法轉(zhuǎn)移的值設(shè)為-1），statRow為狀態(tài)轉(zhuǎn)移表的列數(shù)（既狀態(tài)數(shù)量），out［］［］［］為三維的數(shù)組，存儲(chǔ)兩個(gè)狀態(tài)間轉(zhuǎn)換時(shí)的輸出序列，res為解碼結(jié)果序列，fixed為糾正后的輸入序列*/

int u［MAXJ］［MAXSTAT］;

int B［MAXSTAT］［MAXLEN/2］;

int BB［MAXSTAT］［MAXLEN］; /*BB［s］表示s狀態(tài)對(duì)應(yīng)的糾正后序列*/

memset（u， 0， sizeof（u））;

memset（B， 0， sizeof（B））;

memset（BB， 0， sizeof（BB））; /*置零*/

for （int j = 0; j 《 statRow; j++） {

if （！j） u［0］［j］ = 0;

else u［0］［j］ = 100;

}

/*因?yàn)闋顟B(tài)的起點(diǎn)為狀態(tài)a，所以在0時(shí)刻除了狀態(tài)a（即u［0］［0］）外其它值都設(shè)為無(wú)窮大（此處定義為100）*/

int curSeq［MAXBLOCK］; //當(dāng)前用于計(jì)算路徑距離的輸入序列段

for （int J = 1; J 《 seqLen/（outnum*innum）; J++） {//此處的J代表時(shí)刻

for （int ii = 0; ii 《 outnum*innum; ii++） {

curSeq［ii］ = seq［（J-1）*outnum*innum+ii］;

} //從輸入中取出當(dāng)前段

for （int i = 0; i 《 statRow; i++） { //遍歷J時(shí)刻的狀態(tài)

int min = 100;

int minj = 0; //記錄下保留路徑的起點(diǎn)

for （int j = 0; j 《 statRow; j++） { //遍歷J-1時(shí)刻的狀態(tài)

int l=0;

for （int jj = 0; jj 《 outnum*innum; jj++） { //遍歷當(dāng)前段的每個(gè)字符來(lái)計(jì)算路徑距離

if （stat［j］［i］ 《 0） { //若兩個(gè)狀態(tài)本來(lái)就無(wú)轉(zhuǎn)移關(guān)系，則將l設(shè)為無(wú)窮大，這樣這條路徑就不可能被選擇了

l = 100;

break;

}

if （curSeq［jj］ ！= out［j］［i］［jj］） //計(jì)算漢明距離

l++;

}

if （（u［J - 1］［j］ + l） 《 min） { min = u［J - 1］［j］ + l; minj = j; } //選出累計(jì)路徑長(zhǎng)度最小的

}

u［J］［i］ = min; //將最小的累計(jì)路徑賦給J時(shí)刻的i狀態(tài)

for （int ii = 0; ii 《 （J - 1） *outnum* innum; ii++） {

BB［i］［ii］ = BB［minj］［ii］;

}

for （int jj = 0; jj 《 outnum*innum; jj++） {

BB［i］［（J - 1）*outnum*innum + jj］ = out［minj］［i］［jj］;

}

//上面兩個(gè)for循環(huán)實(shí)現(xiàn)從狀態(tài)minj繼承糾正序列，再往上面填上對(duì)應(yīng)于當(dāng)前段的糾正段

for （int ii = 0; ii 《 （J - 1） * innum; ii++） {

B［i］［ii］ = B［minj］［ii］;

}

for （int jj = 0; jj 《 innum; jj++） {

B［i］［（J - 1）*innum + jj］ = stat［minj］［i］;

}

//尾加對(duì)應(yīng)于糾正段的輸入段，原理同上

}

}

for （int i = 0; i 《 seqLen/outnum; i++） {

res［i］ = B［0］［i］;

}

for （int i = 0; i 《 seqLen; i++） {

fixed［i］ = BB［0］［i］;

}

//賦值給res和fixed

return 1;

}

結(jié)語(yǔ)

關(guān)于Vertibi算法的卷積碼解碼設(shè)計(jì)應(yīng)用介紹就到這了，如有不足之處歡迎指正。

相關(guān)閱讀推薦：什么是卷積碼

相關(guān)閱讀推薦：什么是卷積