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

卷積編碼

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

淺談卷積編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

請看下圖

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

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

在這里做些解釋

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

u[j][s]代表J時刻到達s狀態(tài)的累計路徑長度

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

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

由于最后路徑會回到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為輸入序列長度，outnum為輸出數(shù)（對于（2，1）卷積碼而言為2），innum位輸入數(shù)（對于（2，1）卷積碼而言為1），stat為二維的狀態(tài)轉(zhuǎn)移表（比如說，若狀態(tài)a轉(zhuǎn)到狀態(tài)c需要輸入1，則stat［1］［3］=1，無法轉(zhuǎn)移的值設(shè)為-1），statRow為狀態(tài)轉(zhuǎn)移表的列數(shù)（既狀態(tài)數(shù)量），out［］［］［］為三維的數(shù)組，存儲兩個狀態(tài)間轉(zhuǎn)換時的輸出序列，res為解碼結(jié)果序列，fixed為糾正后的輸入序列*/

int u［MAXJ］［MAXSTAT］;

int B［MAXSTAT］［MAXLEN/2］;

int BB［MAXSTAT］［MAXLEN］; /*BB［s］表示s狀態(tài)對應(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;

}

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

int curSeq［MAXBLOCK］; //當前用于計算路徑距離的輸入序列段

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

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

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

} //從輸入中取出當前段

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

int min = 100;

int minj = 0; //記錄下保留路徑的起點

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

int l=0;

for （int jj = 0; jj 《 outnum*innum; jj++） { //遍歷當前段的每個字符來計算路徑距離

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

l = 100;

break;

}

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

l++;

}

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

}

u［J］［i］ = min; //將最小的累計路徑賦給J時刻的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］;

}

//上面兩個for循環(huán)實現(xiàn)從狀態(tài)minj繼承糾正序列，再往上面填上對應(yī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］;

}

//尾加對應(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é)語

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

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

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