從FPGA實現(xiàn)的角度對大約束度Viterbi譯碼器中路徑存儲

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

1 引言

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

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

2 算法簡述及系統(tǒng)結(jié)構(gòu)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3 路徑度量同址存儲的原理與實現(xiàn)

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

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

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

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

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

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

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

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

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

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

4 仿真與實現(xiàn)

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

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

5 結(jié) 語

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