大約束度Viterbi譯碼器中路徑存儲單元的設計

1 引言

Viterbi譯碼算法是一種最大似然譯碼算法，目前廣泛應用于各種數據傳輸系統，特別是衛星通信和移動通信系統中。近年來隨著FPGA技術的迅速發展，使得基于FPGA實現Viterbi譯碼的算法成為研究的熱點。

由于Viterbi譯碼器的復雜性隨約束長度k成指數增加，大約束度不但使Viterbi譯碼器硬件復雜度大為增加，同時也限制了譯碼速度。而其中以加比選(Add Compareselect，ACS)運算為最主要的瓶頸，的遞歸運算使流水線結構的應用變得困難。本文以(2，1，9)卷積碼為例，用FPGA實現大約束度Viterbi譯碼器，其中ACS設計采用串并結合的方法來兼顧面積和速度，并用流水線結構來提高譯碼速度，對路徑度量存儲則采用同址存儲方法，實現了在占用少量硬件資源的前提下，提高譯碼速度。

2 算法簡述及系統結構分析

Viterbi譯碼原理詳見文獻[1，2],下面僅作簡要說明。

圖1為(2，1，9)卷積碼的2個狀態之間的狀態轉移圖。根據輸入路徑的不同(圖中實線表示輸入為0，虛線表示輸入為1)，僅僅首位不同的兩個狀態可轉移到僅僅末位不同的兩個狀態。將所有狀態的狀態轉移圖按時間往前衍生，即可得到(2，1，9)卷積碼的網格(Trellis)圖。Viterbi譯碼過程就是：根據接收序列，按照最大似然法則，分段地在網格圖上計算尋找有最大度量的路徑的過程。一般來說，維特比澤碼器主要有4個單元所組成，其結構框圖如圖2所示。
 

分支度量單元(BMU) 主要是計算分支度量值。所謂分支度量值就是碼字與接收碼之間的距離。

加-比較-選擇單元(ACSU) 主要是做路徑度量值與分支度量值的疊加，并決定幸存路徑度量值及決定位元(decision bit)。

路徑度量存儲單元(PMMU) 主要用來存儲幸存路徑度量值。

幸存路徑存儲單元(SMU) 主要用來存儲決定位元。

如圖2所示，接收序列先通過分支度量單元計算出各狀態所有分支度量，然后經過ACS單元，將上一時刻的路徑度量值與當前時刻的分支度量值作加-比較-選擇等運算，計算出當前時刻的幸存路徑和路徑度量值，并找出決定位元(decision bit)，把新的路徑度量值存儲到路徑度量存儲單元(PMMU)，并把相應的幸存路徑的決定位元(de-cision bit)存儲到幸存路徑存儲單元(SMU)，當譯碼到譯碼深度后，判決輸出單元輸出譯碼序列。由此可見：

(1) 每計算一接收序列，所有狀態的路徑度量都要更新一次。若這些路徑度量存儲于一塊RAM中，則RAM讀寫的次數為待譯卷積碼的狀態數，當卷積碼的約束度比較大時，對RAM的讀寫周期要求將會很高，很可能成為限制譯碼速度的瓶頸；

(2) 在ACS單元，要完成路徑度量的累加，比較并選擇有最大度量的路徑，是算法實現的關鍵電路，也是硬件資源耗費最大的部分。所以ACS單元的數目太多會大大增加譯碼器的硬件規模，太少則影響譯碼速度。因此，合理安排ACS單元與路徑度量RAM是提高譯碼速度，減少硬件消耗的關鍵所在。

針對問題(1)，本文從改進Viterbi譯碼算法和路徑度量RAM分塊兩方面同時人手。首先，表示Viterbi算法過程的網格圖可以進行分解與折疊。圖3所示為(2，1，9)卷積碼的部分網格圖的分解與折疊。可以看出折疊后，ACS計算時由讀寫狀態路徑度量，得出一步后的更新結果，變為讀寫四狀態路徑度量，得出兩步后的更新結果。省去了中間路徑度量的讀寫，減少了RAM的讀寫次數。

當然，這種分解與折疊很容易擴展為基8或基16的網格圖，RAM的讀寫次數將進一步減少，但此時ACS要同時處理8個或16個路徑度量，復雜性幾乎成指數增加，其計算速度也可能成為新的瓶頸。綜合考慮，本文采用4個基4算法，每次同時處理16個狀態。在基于4個基4算法的16個狀態路徑度量讀寫中，本文將路徑度量RAM分為16塊，每塊存儲16個狀態的路徑度量。16塊RAM并行工作時，對每塊RAM的讀寫周期要求降為原來的1／16。

針對問題(2)，綜合考慮資源占用與譯碼速度，并兼顧基4算法的實現，決定采用4個基4蝶形單元并行工作，每個蝶形單元(ACS)串行處理16個狀態的串并結合方式。

在Viterbi譯碼器的實現過程中，計算當前時刻的路徑度量需用到前一時刻的路徑度量，所以必須對路徑度量加倍緩存。本文提出了一種同址的路徑度量存儲方法，可以減少存儲單元數量，而不影響譯碼速度。下面將詳述該方法的原理及實現過程。

3 路徑度量同址存儲的原理與實現

Viterbi譯碼器的復雜性及所需存儲器容量隨著約束長度K成指數增加，Viterbi譯碼器每解碼一位信息位就需對2K-1=28=256個寄存器進行路徑度量，并對相應的存儲單元進行讀寫，這樣度量路徑的存儲管理就成了提高譯碼速度的一個重要環節。

通常，計算出來的度量路徑可以存儲在RAM中或者是寄存器中。對于約束度很大的Viterbi譯碼器而言，在VLSI應用中使用RAM來存儲比使用寄存器更節省芯片面積，所以本文采用RAM存儲的方式。狀態度量的更新有兩種模式，一種是ping-pong模式，即乒乓模式，一種是同址存儲模式。乒乓模式是使用兩塊存儲器，一塊存儲前一時刻的路徑度量，另一塊則存儲更新后的路徑度量。當前時刻ACS從一塊存儲器中讀取前一時刻的路徑度量，然后進行加比選運算，更新完的路徑度量存入另一塊存儲器中。這種模式的缺點是需要兩塊路徑度量存儲器，優點是控制電路比較簡單。另一種同址存儲模式只需要一塊路徑度量存儲器來進行度量的更新，每一次的更新度量都覆蓋前一時刻的路徑度量。因此這種模式所需的存儲器容量只是乒乓模式的一半。

在維特比算法中，譯碼狀態的轉移導致路徑度量的讀出和寫人狀態不同，這樣在用FPGA實現時，可以用雙口RAM來實現。同時，為配合4個基4蝶形單元同時讀出和寫入16個路徑度量的需要，應將各個路徑狀態分組，因此，我們采用16塊雙口Block RAM。

根據上面分析結果，16塊RAM的RAM1～RAM16分別存儲狀態的路徑度量，這里以狀態來代替其相應的路徑度量。設第n時刻路徑度量在各RAM的存儲示意如表1所示。

(1) 從n時刻到n+1時刻路徑度量更新過程如下：

首先，讀表1中RAM1，5，9，13，RAM2，6，10，14，RAM3，7，11，15，RAM4，8，12，16的數據，對應第1～第4個基4；例如從RAM1，5，9，13中讀取第0位的狀態0，64，128，192，經過第1個基4單元運算后，得到狀態0，1，2，3，存入原來的狀態0，64，128，192的位置(如表2所示)。這樣從第1～16位依次讀取數據，經過相應的基4蝶形單元運算，寫入RAM1～RAM16中相應的位置，這樣，從n時刻到n+1時刻的所有狀態的路徑度量都得到了更新，但存儲于各RAM中的狀態位置發生了變化，其路徑度量如表2所示。
 

(2) 從n+l時刻到n+2時刻的路徑度量的更新

此時，讀表2中RAM1，2，3，4，RAM5，6，7，8，RAM9，10，11，12，RAM13，14，15，16的數據，對應第1～第4個基4。例如讀RAM1～4的第0，4，8，2位的狀態0，64，128，192，經過第一個基4單元運算后，得到數據0，1，2，3，存入原來的狀態0，64，128，192的位置(如表3所示)。讀寫的過程與寫回RAM時的原理同上(同址存儲)，不同之處是讀寫RAM時的地址廁序，其讀寫地址如表5所示。更新后的n+2時刻的路徑度量存儲于各RAM的示意圖如表3所示。

(3) 從n+2時刻到n+3時刻的路徑度量的更新

此時，讀表3中RAM1，2，3，4，RAM5，6，7，8，RAM9，10，11，12，RAM13，14，15，16的數據，對應第1～第4個基4。例如讀RAM1～4的第0，1，2，3位的狀態0，64，128，192，經過第一個基4單元運算后，得到狀態0，1，2，3，存入原來的狀態0，64，128，192的位置(如表4所示)。讀寫的過程與寫回RAM時的原理同上(同址存儲)，不同之處是讀寫RAM時的地址順序，其讀寫地址如表6所示。更新后的n+3時刻的路徑度量存儲于各RAM的示意圖如表3所示。
 

同理，從n+3時刻到n+4時刻的路徑度量的更新可得到如表1所示的形式。可以發現，表4運算后的路徑度量在各RAM的存儲結構與表1完全相同。也就是說以后的過程只是上面四步的循環而已。

本文在FPGA實現時，路徑度量RAM采用了FPGA內的雙口Block RAM，故可在同一時間內對存儲器執行讀和寫操作，因此可有效地降低讀寫次數和提高譯碼速度。RAM讀寫地址的產生：RAM1～RAM16的讀地址用查找表產生。而RAM1～RAM16的寫地址分別為讀地址延時1個時鐘周期得到，用FPGA實現非常簡單。

4 仿真與實現

根據本文提出的結構，用Verilog語言完成上述結構設計，用ModelSim 6.0a對其進行波形仿真，地址產生的波形如圖4所示。

選擇Xilinx spartan3為目標器件，利用ISE軟件完成設計的綜合及布局布線等設計流程，圖5列出了XilinxISE對本設計提供的綜合布線參數。
 

5 結 語

本文重點從FPGA實現的角度對Viterbi譯碼器的路徑度量進行了討論，從譯碼速度和硬件資源消耗兩方面考慮，探討了Viterbi譯碼器的優化，提出了一種串并行結構和同址路徑度量存儲的方法，顯著提高了譯碼器速度和減小了電路規模，并以(2，1，9)卷積碼為例給出了實現過程。該譯碼器通過了ModelSim 6.0a的功能仿真，并已在ISE 7.1i環境中，用Xilinx的spartan3實現。對實現的結果進行了復雜度分析，發現資源的利用相當合理，其不足之處就是連線較多。