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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)上面分析結(jié)果，16塊RAM的RAM1～RAM16分別存儲(chǔ)狀態(tài)的路徑度量，這里以狀態(tài)來(lái)代替其相應(yīng)的路徑度量。設(shè)第n時(shí)刻路徑度量在各RAM的存儲(chǔ)示意如表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的數(shù)據(jù)，對(duì)應(yīng)第1～第4個(gè)基4；例如從RAM1，5，9，13中讀取第0位的狀態(tài)0，64，128，192，經(jīng)過(guò)第1個(gè)基4單元運(yùn)算后，得到狀態(tài)0，1，2，3，存入原來(lái)的狀態(tài)0，64，128，192的位置(如表2所示)。這樣從第1～16位依次讀取數(shù)據(jù)，經(jīng)過(guò)相應(yīng)的基4蝶形單元運(yùn)算，寫入RAM1～RAM16中相應(yīng)的位置，這樣，從n時(shí)刻到n+1時(shí)刻的所有狀態(tài)的路徑度量都得到了更新，但存儲(chǔ)于各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的數(shù)據(jù)，對(duì)應(yīng)第1～第4個(gè)基4。例如讀RAM1～4的第0，4，8，2位的狀態(tài)0，64，128，192，經(jīng)過(guò)第一個(gè)基4單元運(yùn)算后，得到數(shù)據(jù)0，1，2，3，存入原來(lái)的狀態(tài)0，64，128，192的位置(如表3所示)。讀寫的過(guò)程與寫回RAM時(shí)的原理同上(同址存儲(chǔ))，不同之處是讀寫RAM時(shí)的地址廁序，其讀寫地址如表5所示。更新后的n+2時(shí)刻的路徑度量存儲(chǔ)于各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的數(shù)據(jù)，對(duì)應(yīng)第1～第4個(gè)基4。例如讀RAM1～4的第0，1，2，3位的狀態(tài)0，64，128，192，經(jīng)過(guò)第一個(gè)基4單元運(yùn)算后，得到狀態(tài)0，1，2，3，存入原來(lái)的狀態(tài)0，64，128，192的位置(如表4所示)。讀寫的過(guò)程與寫回RAM時(shí)的原理同上(同址存儲(chǔ))，不同之處是讀寫RAM時(shí)的地址順序，其讀寫地址如表6所示。更新后的n+3時(shí)刻的路徑度量存儲(chǔ)于各RAM的示意圖如表3所示。
 

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

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

4 仿真與實(shí)現(xiàn)

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

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

5 結(jié) 語(yǔ)

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