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

1 引言

Viterbi譯碼算法是一種最大似然譯碼算法，目前廣泛應用于各種數據傳輸系統，特別是衛星通信和移動(dòng)通信系統中。近年來(lái)隨著(zhù)FPGA技術(shù)的迅速發(fā)展，使得基于FPGA實(shí)現Viterbi譯碼的算法成為研究的熱點(diǎn)。

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

2 算法簡(jiǎn)述及系統結構分析

Viterbi譯碼原理詳見(jiàn)文獻[1，2],下面僅作簡(jiǎn)要說(shuō)明。

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

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

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

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

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

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

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

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

針對問(wèn)題(1)，本文從改進(jìn)Viterbi譯碼算法和路徑度量RAM分塊兩方面同時(shí)人手。首先，表示Viterbi算法過(guò)程的網(wǎng)格圖可以進(jìn)行分解與折疊。圖3所示為(2，1，9)卷積碼的部分網(wǎng)格圖的分解與折疊?？梢钥闯稣郫B后，ACS計算時(shí)由讀寫(xiě)狀態(tài)路徑度量，得出一步后的更新結果，變?yōu)樽x寫(xiě)四狀態(tài)路徑度量，得出兩步后的更新結果。省去了中間路徑度量的讀寫(xiě)，減少了RAM的讀寫(xiě)次數。

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

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

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

3 路徑度量同址存儲的原理與實(shí)現

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

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

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

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

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

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

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

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

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

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

同理，從n+3時(shí)刻到n+4時(shí)刻的路徑度量的更新可得到如表1所示的形式?？梢园l(fā)現，表4運算后的路徑度量在各RAM的存儲結構與表1完全相同。也就是說(shuō)以后的過(guò)程只是上面四步的循環(huán)而已。

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

4 仿真與實(shí)現

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

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

5 結 語(yǔ)

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