探析Viterbi改進算法
相關(guān)鏈接： 北京安全網(wǎng) 北京質(zhì)量網(wǎng) 北京論文網(wǎng) 北京資訊網(wǎng)
摘要：Viterbi譯碼算法是最大似然譯碼。本文所研究的改進Viterbi算法,不但保持了原有Viterbi算法的特性，而且在減少譯碼路徑的情況下，能較好地解決突發(fā)錯誤信道中，原Viterbi譯碼算法則性能急劇下降的問題。通過在編碼信道模型上的仿真表明，已知正確的約束位越多，分布的越密，則提高的性能越明顯。
論文關(guān)鍵詞：信道編碼,約束維特比譯碼,通信
卷積碼廣泛應用于各種數(shù)字通信系統(tǒng)中。其中衛(wèi)星通信中信道部分也大量采用卷積碼。描述卷積編碼的方法很多，如卷積碼的矩陣描述、生成多項式描述、樹圖(網(wǎng)格圖)描述、有限狀態(tài)圖描述等，并且卷積碼的描述方法與它所采用的譯碼方法密切相關(guān)。目前研究比較成熟的方法有卷積碼的生成多項式矩陣描述和網(wǎng)格圖描述。卷積碼的網(wǎng)格圖描述是一種形象的表示卷積碼編譯碼過程的方法，Viterbi基于網(wǎng)格圖提出著名的Viterbi譯碼算法成為目前解決卷積碼譯碼的最有效的算法。卷積碼的概率譯碼不僅利用碼自身的代數(shù)結(jié)構(gòu)，而且還考慮了信道的統(tǒng)計特性，因而能充分發(fā)揮卷積碼的特點，使譯碼錯誤概率達到最小。
1、 卷積碼原理
卷積碼是把k個信息比特的輸入經(jīng)編碼后。形成n個比特的輸出，通常k和n很小，特別適宜于以串行形式傳輸信息，延時小。與分組碼不同，卷積碼中編碼后的n個碼元不但與當前段的k個信息有關(guān)，而且與前面(N-1)段的信息有關(guān)，因此稱N為約束長度。編碼過程中相互關(guān)聯(lián)的碼元為Nk個。卷積碼的糾錯能力隨著N的增加而增大，而差錯率隨著N的增加而指數(shù)下降。在編碼器復雜性相同的情況下，卷積碼的性能優(yōu)于分組碼。
卷積碼的譯碼方法可分為兩大類。一類是代數(shù)譯碼，利用編碼本身的代數(shù)結(jié)構(gòu)進行譯碼，不考慮信道本身的統(tǒng)計特性。該方法的硬件實現(xiàn)簡單，但性能較差，其中具有典型意義的是門限譯碼。另一類是概率譯碼，這種譯碼通常建立在最大似然準則的基礎上。由于計算是用到了信道的統(tǒng)計特性。因而提高了譯碼性能，但這種性能的提高是以增加硬件的復雜度為代價的。常用的概率譯碼方法有維特比譯碼和序列譯碼。卷積碼概率譯碼的基本思路是：以斷續(xù)的接收碼流為基礎，逐個計算它與其他所有可能出現(xiàn)的、連續(xù)的網(wǎng)格圖路徑的距離，選出其中可能性(概率)最大的一條作為譯碼估值輸出。概率最大在大多數(shù)場合可解釋為距離最小，這種最小距離譯碼體現(xiàn)的正是最大似然的準則。
2、硬判決Viterbi譯碼算法原理
Viterbi算法是一種最大似然譯碼算法。它并不是在網(wǎng)格圖上一次比較所有可能的2枕條路徑(序列)，而是接收一段，計算、比較一段，選擇一段最有可能的碼段(分支)，從而達到整個碼序列是一個有最大似然函數(shù)的序列。
Viterbi算法的基本思路是:以斷續(xù)的接收碼流為基礎，逐個計算它與其他所有可能出現(xiàn)的、連續(xù)的格狀圖路徑的距離，選出其中可能性(概率)最大的一條作為譯碼估值輸出。
從時間單位m至L，網(wǎng)格圖中2mk個狀態(tài)中的每一個有一條幸存路徑，共有2mk條。但在L時間單位后，網(wǎng)格上的狀態(tài)數(shù)目減少，幸存路徑也相應減少。最后到第L十m單位時間，網(wǎng)格圖上的狀態(tài)數(shù)目減少，因此僅剩下一條幸存路徑。這條路徑就是要找的具有最大似然函數(shù)的路徑，也就是譯碼器輸出的估值序列。由此可知，在網(wǎng)格圖上用維特比算法得到的路經(jīng)一定是一條最大似然路徑，因此這種方法是最佳的。
3、改進Viterbi譯碼算法原理
在Viterbi譯碼中，對于長度為L的二進制序列的最佳譯碼，需要對有可能發(fā)送的2L個不同序列的2L條路徑的似然函數(shù)累加值（即路徑量度）進行比較，選取其中最大的一條。當該二進制序列的某位數(shù)據(jù)已經(jīng)確定為正確的時，那么，所有不符合該正確數(shù)據(jù)的路徑認為是錯誤的，這樣，可以使候選路徑減半，即為2L-1。所以我們每確定一位，就可以使候選路徑減半，當確定了m位后候選路徑數(shù)量變?yōu)?L-m。當一個位被確定為正確后，其不僅自身譯碼正確，同時可以影響其附近的位。
設編碼器含有N個狀態(tài)，其從0狀態(tài)開始，當經(jīng)過M時刻后，返回0狀態(tài)，其譯碼的網(wǎng)格圖見圖1。在J時刻的接收的數(shù)據(jù)，與從J-1時刻，第i個狀態(tài)，到J時刻，第k個狀態(tài)輸出的數(shù)據(jù)的漢明距離記為Cj(i,k)（i狀態(tài)與k狀態(tài)之間不存在連接的話，那么Cj(i,k)=∞）。從0時刻，0狀態(tài)，到達第J時刻，k狀態(tài)的所有路徑中，其中一條路徑具有最小漢明距離φj(k)，該路徑在每個時刻經(jīng)過的狀態(tài)記錄在εj(k)中，那么最終εM(0)就是譯碼的最優(yōu)路徑。
圖1 網(wǎng)格圖
4、兩種Viterbi譯碼算法性能的比較
在仿真中，令數(shù)據(jù)大小為250比特，信息位由隨機數(shù)產(chǎn)生，加6位的狀態(tài)歸零碼。共256比特。仿真的參數(shù)記錄在表1中。
表1 仿真參數(shù)
在仿真中，編碼后的數(shù)據(jù)包的格式如圖2所示，每個數(shù)據(jù)包被分為n個段S1-Sn，每段內(nèi)含有m個比特，B1-Bm。每段（最后一段Sn除外）的第m-1個比特為我們所知道的正確的約束位(圖中黑色部分)。這樣共有(256/m)-1個正確的約束位，且呈均勻分布。仿真中，m取2、4、8、16進行仿真，分別測試了譯碼后的誤碼率與誤包率。采用兩種算法進行譯碼，以進行比較，一種是采用改進算法進行譯碼；一種是未進行改進算法，僅在譯碼后將已知正確的比特填充進譯碼結(jié)果中，對此兩種算法進行比較，結(jié)果見圖3、圖4。
圖2 包結(jié)構(gòu)
圖3 誤包率性能曲線
圖4 誤碼率性能曲線
5、結(jié)束語
卷積碼己經(jīng)廣泛應用于衛(wèi)星通信和移動通信等無線通信系統(tǒng)中，其編譯碼技術(shù)研究不斷有新的進展，信道編碼技術(shù)已經(jīng)成為一門標準技術(shù)而被廣泛地應用于各種通信系統(tǒng)中。本文研究的Viterbi算法對卷積碼的譯碼是一種改進。糾錯編碼技術(shù)處于不斷的發(fā)展之中，新的編碼在實際中的應用，會給編碼分析人員提出新的課題，這就要求我們不斷研究新方法，去解決實際工作中出現(xiàn)的新問題。
參考文獻
[1]王新梅，肖國鎮(zhèn).糾錯碼——原理與方法.西安：西安電子科技大學出版社，2001
[2]張宗橙.糾錯編碼原理與應用.北京：電子工業(yè)出版社，2003.83-86
[3]游余新，王進祥，來逢昌，葉以正.高速低功耗維特比譯碼器的設計與實現(xiàn).計算機研究與發(fā)展. 2003，40(2):360一3651
[4]Lei Cao,Chang Wen Chen A Novel Product Coding and RecurrentAlternate Decoding Scheme for Image Transmission Over Noisy Channels[J] IEEE TRANSACTIONS ON COMMUNICATIONS,SEPTEMBER 2003 VOL.51,NO.9
[5]溫學東.卷積碼編碼及其Vietbri譯碼算法的FPGA實現(xiàn).信息與電子工程2005，3(9):176一179.
