黃增先，王進華
(福州大學 電氣工程與自動化學院，福建 福州 350108)
摘要：針對維特比譯碼器譯碼過程中速度制約的問題，設計了一種結構優化的維特比譯碼器。該結構通過蝶形單元的直通互連，使得在狀態轉移過程中不需要對路徑度量值進行大范圍存儲，簡化了路徑度量值的存儲與讀取邏輯。并且可以根據不同的應用要求靈活配置蝶形處理單元的復用次數。最后，結合FPGA平臺，利用Verilog硬件描述語言和Vivado軟件對譯碼器進行設計與實現。綜合實現結果表明，該譯碼器占用1 564個LUT單元，能夠在100 MHz系統時鐘下進行有效譯碼。
關鍵詞：維特比;回溯;蝶形單元;加比選;狀態轉移因子;FPGA
中圖分類號：TN919文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.05.019
引用格式：黃增先，王進華.結構優化的維特比譯碼器的實現方案［J］.微型機與應用，2017,36（5）：6064.
0引言
在現代數字通信中，為降低數據傳輸的誤碼率，提高通信的質量及其可靠性，常在通信系統中采用糾錯編碼技術，其中卷積碼就是一種具有較強糾錯能力的糾錯碼［1］。由于維特比譯碼算法簡單，易于實現，能夠得到較大的編碼增益，因此基于維特比譯碼算法的卷積碼得到了廣泛的應用。卷積碼在編碼過程中，充分地利用了各碼組之間的相關性，且k和n都比較小，因此，在與分組碼同樣的碼率和設備復雜性條件下，從理論和實際兩個方面，均已證明卷積碼的性能至少不比分組碼差［2］。
維特比譯碼在算法實現過程中，蝶形單元運算需要對路徑度量值按照一定的規則進行讀取和存儲［35］，這不僅增加了存儲資源的消耗還延長了譯碼周期。本文首先設計了一種蝶形單元直通互連的結構，基于這種結構，可以簡化針對路徑度量值的邏輯控制。最后，在蝶形單元直通互連結構的基礎上，利用部分并行的思想對蝶形單元進行復用，設計了(2,1,7)維特比譯碼器，結果表明該譯碼器資源消耗較少。
1維特比譯碼算法
維特比譯碼算法的基本思想是利用編碼網格圖，在其中搜索一條路徑，使其最接近實際路徑，搜索到的這條路徑稱為幸存路徑［6］。維特比譯碼算法實質上就是最大似然譯碼，它是逐步去除網格圖上不可能成為最大似然路徑者來搜索幸存路徑［7］。維特比譯碼算法的一般步驟為：
（1)計算進入每一狀態的各個分支度量值(Branch Metric, BM)，此過程主要是比較期望碼字與輸入碼字間的漢明距離，把這個距離稱為分支度量值。
（2)把各分支度量值和前一時刻狀態路徑度量值相加，得到當前時刻新的狀態路徑度量值(Path Metric , PM)。在每個狀態中，從到達這一狀態的路徑度量值中選出最小的那個作為當前時刻的PM。同時存儲與之相應的路徑作為幸存路徑，這個過程稱為加比選(Add Compare Select, ACS)。
（3)輸入碼字達到一定深度后，任選一個狀態為起始狀態，根據步驟（2）中所選出的幸存路徑進行回溯［89］。其中回溯操作分為兩個步驟，首先回溯尋找根節點，接著從根節點繼續回溯進行倒序的譯碼輸出。
圖1所示的(2,1,3)卷積碼網格圖可以看作是由2個不同蝶形單元構成，其中S0和S2構成一個蝶形單元，S1和S3構成一個蝶形單元。假設在t時刻S0和S2的PM值分別為2和3，這時輸入碼字為10，則通過計算漢明距離可以得到該蝶形單元4個分支度量值從上到下分別為BM1=1、BM2=1、BM3=1、BM4=1。在t+1時刻，從上到下計算得到的路徑度量值分別為PM1=3、PM2=4、PM3=3、PM4=4，最終通過比較選出t+1時刻S0狀態的路徑度量值為PM1=3，幸存路徑為上分支路徑，S1狀態路徑度量值為PM3=3，幸存路徑為上分支路徑。
2結構優化的維特比譯碼電路
2.1分支度量值計算單元
分支度量值單元比較期望碼字與輸入碼字間的漢明距離，便于之后的“加比選”單元選出該時刻的幸存路徑［10］。
卷積碼網格圖中狀態之間的轉移是由卷積編碼器的結構決定的，如圖2所示的(2,1,7)卷積編碼電路圖，通過移位輸入待編碼字產生相應的輸出并且改變編碼電路中狀態寄存器的值。
卷積碼編碼器狀態之間的轉移有一定的規則，如圖3所示。
編碼狀態寄存器中的高五位相同的兩個狀態，編碼輸入相同的信息后狀態的轉移也相同，并且它們的輸出也有一定的對應關系。結合圖2所示的編碼電路圖可以看出，兩個平行支路輸出相同，兩個交叉支路輸出相同，并且平行支路與交叉支路的輸出互為相反(0—1，1—0)。以狀態(100000)和狀態(100001)為例，具體如圖4所示。
（小方塊顯示為編碼輸出）因此如果可以得到其中一個平行支路的編碼輸出，就可以推斷出其他三個支路的編碼輸出。結合圖2所示的編碼電路和圖3所示的狀態轉移蝶形單元圖可知，蝶形單元上支路的水平輸出可以通過讀取狀態信息獲得，即Symbolout0=④^③^①，Symbolout1=⑤^④^③。得到蝶形單元的輸出后只需要相應的判斷就可以得到漢明距離的輸出。漢明距離是表征兩個碼間不同位數的數量，可以用異或運算來實現，由異或運算的性質：
if (Symbolout0==1)
bm00_0=~symbolin0;
bm01_0= symbolin0;
bm10_0= symbolin0;
bm11_0=~symbolin0;
else
bm00_0= symbolin0;
bm01_0=~symbolin0;
bm10_0=~symbolin0;
bm11_0= symbolin0;
end
其中Symbolout0是編碼輸出，symbolin0是譯碼輸入，再由Symbolout1的值判斷另一部分的分支度量值，最后將兩部分相加就可以得到完整的分支度量值。
2.2加比選單元
加比選模塊主要實現的功能是將路徑度量值與分支度量值相加，對結果采用二進制補碼取模法(Modulo Normalization)進行尺度調整［1112］。將得到的到達同一狀態的兩個新的路徑度量值進行比較，選出較小的那個作為下一狀態的路徑度量值，同時存儲狀態轉移因子。
觀察圖5，每個狀態轉移單元中下一時刻的狀態有兩條路徑到達，ACS單元的主要功能是比較這兩條路徑的路徑度量值，選出較小的那個作為新的路徑度量值，并給出狀態轉移因子。
因為前一狀態只有最低位是不一樣的，所以以最低位來區分，如果轉移路徑是由最低位為0的狀態轉移而來，則狀態轉移因子輸出為0；如果轉移路徑是由最低位為1的狀態轉移而來，則狀態轉移因子輸出為1。這樣得到現態之后結合狀態轉移因子就可以知道這個狀態的前一狀態是什么，將現態值左移一位并以狀態轉移因子代替最后的空出位就可得到前一狀態，例如：假設0A5A4A3A2A1的狀態轉移因子為1，則它的前一狀態為A5A4A3A2A11，并且A5A4A3A2A11狀態是通過輸入0得到0A5A4A3A2A1，即現態的最高位代表前一狀態的輸入。
2.3蝶形處理單元直通互連結構
(2,1,7)卷積碼有64個狀態，狀態轉移之間對應有32個蝶形單元。圖6以8狀態為例來說明蝶形單元直通互連結構，具有64狀態的卷積碼蝶形單元的互連結構與之相似。
圖6中對應8狀態卷積碼的3種不同譯碼處理方式，分別為分立的蝶形處理單元、并行互連的蝶形處理單元和部分并行互連的蝶形處理單元。分立的蝶形單元需外加存儲單元對相應的路徑度量值進行存儲和讀取，而互連的蝶形單元可以隨著輸入持續地進行狀態之間的轉移，不需要對路徑度量值進行存儲，從而降低譯碼的延遲與存儲資源的消耗。如圖6左邊第一列的8狀態轉移圖中分為4個蝶形單元，平行支路代表輸入0，交叉支路代表輸入1，用4個PE(Process Element)單元表示4個蝶形單元，分立結構需要控制PE1單元去讀取PE0單元的第二個寫入值PM4的同時還需要去讀取PE2單元的寫入值PM5，當狀態數很多時，這套讀取控制的復雜度隨之增加，并且每個譯碼輸入都要進行頻繁的讀取，功耗勢必增加，同時譯碼延遲也會增加。圖6中間一列表示并行互連的PE結構，并行互連的PE結構不需要對路徑度量值進行存儲與讀取，通過互連結構相應的路徑度量值可以正確地進入對應的PE單元。圖6第三列表示部分并行互連的PE結構，通過對PE單元進行復用降低了PE單元連線的復雜度，資源消耗也降低到一半，譯碼速率較并行互連的PE結構略有降低。部分并行互連結構用兩個PE處理8個狀態轉移，即一個PE單元分時處理狀態之間的轉移。按如下規則對部分并行互連處理單元的狀態進行分配：狀態標志位的最低位為0表示蝶形單元的上支路，為1表示下支路；狀態標志位的最高位表示PE單元分時處理周期，0表示第一周期，1表示第二周期；狀態標志位除去最高位與最低位后剩下的位表示PE序號。比如：圖6中狀態S5的最高位為1、最低位為1，除去最高位與最低位后為0，表示狀態S5是 PE0復用單元第二周期的下支路輸入。這部分難點在于如何分配輸入與輸出使得復用的PE模塊可以流暢地運行下去。下面重點介紹PE復用機制輸入輸出的分配處理。
本設計輸入輸出分配處理應用的是同地址寫回技術(Same Address Write Back)［13］，即讀出地址和寫入地址一致，運用這種技術可以有效地減少對存儲空間的占用。
圖7用來表示圖6第三列中PE0的讀寫操作。初始化時寄存器內容為0，為方便描述，圖中寄存器中寫入的路徑度量值直接用狀態標志表示。隨之譯碼輸入按以下步驟進行：
（1)開始從上到下讀取圖7中第一列存儲器中的值，在讀取完畢后PE0模塊輸出到達狀態S0和S4的路徑度量值，利用同地址寫回技術將S0和S4狀態的路徑度量值寫回到原先被讀取的空間，即從上到下寫入到第一列存儲器。
（2)讀取第二列存儲器中的值，注意此時的讀取順序是從下到上，讀取完畢后將產生的S6和S2狀態的路徑度量值按同地址寫回到第二列的存儲空間中，此時同樣按照從下到上寫入。
（3)接著左斜著讀取存儲器中的值，按照從上到下的原則，讀取出S0和S2的路徑度量值，從而實現圖6復用結構中PE0的第一列輸出，同時將隨之產生的S0和S4路徑度量值存入原先讀取的地址，同樣按照從上到下的順序。
（4)右斜著讀取寄存器中的值，按照從下到上的原則讀取出S4和S6狀態的路徑度量值，從而實現圖6復用結構PE0的第二列輸出，同時將此時PE0產生的S2和S6路徑度量值寫入原先讀取的地址，同樣按照從下到上。最后回到步驟（1），按照上述讀寫步驟循環進行下去，就可以實現圖6復用結構中所示的輸入輸出變化。
上面討論了8狀態的PE互連結構，64狀態的(2,1,7)卷積碼的PE互連結構原理及規則與8狀態的相似。
2.4回溯處理單元
當回溯進行到一定深度（本次設計選擇為32個譯碼深度）確定了根節點后，就要從根節點開始繼續回溯進行譯碼輸出，輸出32個譯碼后一個完整的回溯操作結束。所以一次回溯的深度是64個譯碼深度，前32個回溯深度用來確定根節點，此部分不進行譯碼輸出，后32個深度回溯才開始譯碼輸出。回溯操作根據狀態轉移因子進行一步步回溯，因此需要分配一定的存儲空間對狀態轉移因子進行存儲［14］，進行回溯操作時再從存儲空間讀取這些狀態轉移因子。回溯輸出的譯碼結果是倒序的，所以最終要對譯碼的結果進行倒序恢復才能得到真正有效的譯碼結果。
如圖8，從地址64開始將狀態轉移因子寫入存儲空間中，由于PE單元的復用關系，一個時鐘周期只會產生32個狀態轉移因子，但是64個狀態一次完整的狀態轉移會產生64個狀態轉移因子，也就是整個PE模塊需要2個時鐘周期才能完成一次完整的狀態轉移。將整個互連的PE模塊第一個時鐘周期產生的狀態轉移因子存儲在地址64，第二個時鐘周期產生的狀態轉移因子存儲在地址65，以此類推。所以要完成32次完整的狀態轉移（即32個譯碼深度）需要64×32 bit的存儲空間，將每64×32 bit的存儲空間劃分為一個小存儲單元。當完成64次完整的狀態轉移后，也就是當狀態轉移因子寫入到地址191時，開始從S0狀態進行回溯，當回溯到32深度時，即回溯到地址128或者129時，此時已經確定了根節點，接著從根節點進行回溯譯碼輸出，當譯碼輸出32 bit的數據，即回溯譯碼32個深度時，一個回溯操作窗結束。一個回溯操作窗結束之后，將回溯操作窗向前移動一個小存儲單元（向前64個地址），重復上述步驟進行回溯尋根節點和回溯譯碼輸出。
如圖9所示，從地址64開始存儲，互連PE模塊第一個操作周期產生的狀態轉移因子以狀態的低5位為位地址存寫入字地址64，第二周期產生的狀態轉移因子以狀態的低5位為位地址寫入地址65，完成一次完整的狀態轉移。所以每個狀態轉移因子都對應一個字地址和位地址，并且第一個操作周期產生的狀態轉移因子的字地址為偶數，第二個操作周期產生的狀態轉移因子的字地址為奇數。
現以第一個操作窗為例描述回溯過程。在完成上述存儲器的配置后回溯過程主要分為以下幾個步驟：取狀態字地址，取轉移因子位地址，完成一次回溯操作確定前狀態。
在完成64次完整的狀態轉移后，開始第一個回溯窗的操作（此時地址從64開始寫到191）。由回溯理論知，任意狀態回溯到一定深度后的根節點狀態是一致的，所以每次回溯操作的起始狀態設置(000000)狀態。由于(000000)狀態是由PE單元第一個操作周期產生的，因此它的字地址為偶數，即要讀取地址190以取得狀態轉移因子。要讀取狀態(000000)對應的狀態轉移因子還需要位地址才可以取到，觀察圖10的回溯操作圖，發現將位于蝶形右邊的狀態循環左移一位可以得到蝶形左邊的狀態，因此要取得相應狀態轉移因子的位地址，需要先將狀態循環左移一位后取移位后狀態的低5位即可得到。如：狀態(000000)循環左移一位后變為(000000)，即其對應的轉移因子的位地址為0，所以依次讀取字地址190、位地址0可以得到狀態(000000)的狀態轉移因子。假如此時讀取到的轉移因子dec=1，將原狀態左移一位用dec的值代替最低位就可以得到該狀態的前態，即狀態(000000)的dec=1則狀態(000000)的前態為(000001)，要繼續回溯下去就要取得狀態(000001)的字地址和位地址，將狀態(000001)循環左移一位得到狀態(000010)，其高位為0即該蝶形是在PE模塊第一個操作周期產生的，其地址為偶地址，因此在190的基礎上減去2就可以得到該狀態的字地址188，狀態(000010)的低5位為相應的位地址2，所以從字地址188、位地址2中就可以讀取到狀態(000001)的轉移因子。當回溯進行到32個深度后就可以進行回溯譯碼輸出。觀察圖10蝶形的右端，狀態的最高位表示前一狀態的輸入，對應蝶形的左端狀態的最低位，因此可以在完成循環左移步驟后讀取得到狀態的最低位，該位對應的就是譯碼輸出。
3維特比譯碼器電路的實現
設計采用Verilog硬件描述語言對維特比譯碼器進行硬件描述，通過Xilinx公司的Vivado［15］進行綜合與實現，并利用Xilinx xc7k70tfbg484-1 FPGA進行電路實現。在100 MHz時鐘約束下建立時間與保持時間都留有裕量，說明譯碼器的工作頻率至少可以達到100 MHz。最終，整個譯碼器資源占用情況如表1所示。
4結束語
本文基于蝶形單元直通互連結構，設計了(2,1,7)維特比譯碼器。它利用部分并行結構的思想對蝶形單元進行復用，結合同地址寫回技術，簡化了對路徑度量值的邏輯控制，節省了存儲資源。為適應蝶形單元的復用結構，設計了狀態轉移因子的存儲結構，通過結合字地址與位地址進行讀取，加快了狀態回溯的速度。
參考文獻
［1］ 溫學東. 卷積碼編碼及其Viterbi譯碼算法的FPGA實現［J］. 信息與電子工程, 2005, 3(3):176-178.
［2］ 張增良. 基于FPGA的卷積編碼和維特比譯碼的研究與實現［D］. 天津:天津大學, 2007.
［3］ 黃華柱, 劉榮科, 王閏昕. 一種串行結構的2,1,7卷積碼維特比譯碼器的FPGA實現［J］. 遙測遙控, 2009, 30(3):54-58.
［4］ 韓可, 鄧中亮, 施樂寧. (2,1,7)卷積碼Viterbi譯碼器FPGA實現方案［J］. 現代電子技術, 2007, 30(15):90-92.
［5］ 傅民倉, 馮立杰, 李文波. 基于FPGA的高速Viterbi譯碼器優化設計和實現［J］. 現代電子技術, 2006, 29(7):52-54.
［6］ 元鋒剛, 許海濤. 802.11b中卷積碼和Viterbi譯碼的FPGA設計實現［J］. 無線電工程, 2012, 42(1):51-53.
［7］ 林舒. 差錯控制編碼［M］. 北京：機械工業出版社, 2007.
［8］ KAMUF M, -WALL V, ANDERSON J B. Survivor path porocessing in Viterbi decoders using register exchange and traceforward［J］. Circuits & Systems II Express Briefs IEEE Transactions on, 2007, 54(6):537-541.
［9］ 王建新, 于貴智. Viterbi譯碼器回溯算法實現研究［J］. 電子與信息學報, 2007, 29(2):278-282.
［10］ BLACK P J, MENG T H. Hybrid survivor path architectures for Viterbi decoders［C］. IEEE International Conference on Acoustics, 1993(1):433-436.
［11］ HEKSTRA A P. An alternative to metric rescaling in Viterbi decoders［J］. IEEE Transactions on Communications, 1989, 37(11):1220-1222.
［12］ SHUNG C, SIEGEL P, UNGERBOECK G, et al. VLSI architectures for metric normalization in the Viterbi algorithm［C］. IEEE International Conference on Communications, 1990:1723-1728.
［13］ B-O M, ARG-ELLO F, BRUGUERA J D, et al. High-performance VLSI architecture for the Viterbi algorithm［J］. IEEE Transactions on Communications, 1997, 45(2):168-176.
［14］ FEYGIN G, GULAK P G. Survivor sequence memory management in Viterbi decoders［C］. IEEE International Sympoisum on Circuits and Systems， 1991:2967-2970.
［15］ 孟憲元. Xilinx新一代FPGA設計套件Vivado應用指南［M］. 北京：清華大學出版社, 2014.