摘 要： 在深入研究Turbo譯碼算法" title="譯碼算法">譯碼算法的基礎(chǔ)上，重點(diǎn)分析了Log-MAP算法，并針對下一代移動通信系統(tǒng)" title="移動通信系統(tǒng)">移動通信系統(tǒng)B3G(Beyond 3G)數(shù)據(jù)業(yè)務(wù)高傳輸速率" title="傳輸速率">傳輸速率的要求，提出了一種高效的基于Log-MAP譯碼算法的FPGA并行實(shí)現(xiàn)方法，并利用Xilinx公司的FPGA芯片并行實(shí)現(xiàn)100Mbps的譯碼。實(shí)驗(yàn)表明，對B3G系統(tǒng)中高速數(shù)據(jù)進(jìn)行譯碼時(shí)，具有較好的誤碼性能和較理想的譯碼時(shí)延" title="時(shí)延">時(shí)延。
關(guān)鍵詞： Log-MAP算法 下一代移動通信系統(tǒng) FPGA實(shí)現(xiàn) 100Mbps并行譯碼
Turbo碼[1]自1993年提出以來，由于其接近Shannon極限的優(yōu)異性能，被廣泛應(yīng)用于無線通信系統(tǒng)中，已被確定為第三代移動通信系統(tǒng)的信道編譯碼方案之一。在下一代移動通信系統(tǒng)中，要求更高的傳輸速率和更好的誤碼性能，對信道編譯碼的要求也相應(yīng)提高。然而，由于Turbo碼迭代譯碼算法的限制，使得譯碼復(fù)雜度和譯碼時(shí)延成為硬件實(shí)現(xiàn)" title="硬件實(shí)現(xiàn)">硬件實(shí)現(xiàn)的重要問題，性能和資源上的折衷考慮是實(shí)現(xiàn)Turbo碼的關(guān)鍵。本文對Turbo碼進(jìn)行了深入的研究，提出了適合于FPGA實(shí)現(xiàn)的改進(jìn)的Log-MAP[2]算法，并采用Xilinx公司的XC2VP70芯片實(shí)現(xiàn)了譯碼功能，該譯碼模塊用于B3G系統(tǒng)上行鏈路。實(shí)驗(yàn)表明，在高速率傳輸下譯碼的誤碼率以及譯碼輸出時(shí)延能滿足B3G業(yè)務(wù)要求。
1 Log-MAP算法
從Turbo碼的提出至今，其譯碼算法目前主要有最大后驗(yàn)概率(MAP)算法和軟輸出維特比譯碼算法(SOVA)算法[3]。SOVA算法運(yùn)算量最小，較適合硬件實(shí)現(xiàn)，但性能較差。目前而言，MAP算法被認(rèn)為是最佳的譯碼算法，但是由于其包含大量的乘法和指數(shù)運(yùn)算，不利于硬件實(shí)現(xiàn)。在此基礎(chǔ)上簡化而來的是Max-Log-MAP[4]算法：
ln(ex+ey)≈MAX(x,y) (1)
Max-Log-MAP算法將MAP算法轉(zhuǎn)移到對數(shù)域中可以大大降低計(jì)算量：在對數(shù)域中，不再需要指數(shù)運(yùn)算，原來的乘法轉(zhuǎn)變成加法。然而，這種近似卻引來了一定的性能損失。文獻(xiàn)[2]中的實(shí)驗(yàn)表明，Max-Log-MAP算法相對于MAP算法有0.5dB的損失。實(shí)際上，根據(jù)Jacobian展開式，ln(ex+ey)≈MAX(x,y）+ln(1+e-|x-y|)，就是Log-MAP算法?？梢钥吹?，Log-MAP算法僅僅是將MAP算法轉(zhuǎn)換到對數(shù)域中進(jìn)行運(yùn)算，因此其性能相對于MAP算法是一致的。然而在Log-MAP算法中，對數(shù)和指數(shù)運(yùn)算仍然存在，這對于硬件實(shí)現(xiàn)還是不利的。文獻(xiàn)[2]提出將Log-MAP算法中的加項(xiàng)利用查找表的方法來實(shí)現(xiàn)，以減小運(yùn)算復(fù)雜度，同時(shí)改善(1)式的性能，即：
ln(ex+ey)≈MAX(x,y)+f(x,y) (2)
=MAX*(x,y)
其中，f(x,y)是關(guān)于x-y的分段函數(shù)。
下面簡要介紹一下Log-MAP算法，其中各分量均為對數(shù)域表示。
通過迭代運(yùn)算，對最后一次迭代得到的LLR進(jìn)行硬判決，可以得到譯碼輸出的結(jié)果。
2 譯碼器硬件實(shí)現(xiàn)時(shí)的改進(jìn)
從式(6)、(7)中可以看到每次迭代時(shí)都需要先計(jì)算LLR，再通過LLR來計(jì)算下一次迭代時(shí)需要的外信息Le。但是LLR實(shí)際上在最后判決時(shí)才會用到，而對于每一級迭代而言，外信息Le才是最關(guān)心的。于是，將上面算法作一改進(jìn)，讓系統(tǒng)在每次迭代時(shí)僅計(jì)算Le，直到判決時(shí)再計(jì)算LLR，以減少運(yùn)算復(fù)雜度。推導(dǎo)可知：
通過以上改進(jìn)，使得在迭代過程中不依賴于LLR，既減少了計(jì)算量，又減少了計(jì)算過程中存儲LLR所需要的RAM空間。
從式(8)看到，對于整個(gè)Log-MAP譯碼算法而言，由于后向迭代，需要大量的RAM來存儲已經(jīng)計(jì)算得到的前向狀態(tài)度量α。對于碼長為L具有N狀態(tài)的Turbo碼，假設(shè)每個(gè)狀態(tài)度量用K比特量化，那么存儲所需的空間則為L×N×K。同時(shí)，每次迭代的輸出時(shí)延隨著碼長L增長。這對于硬件實(shí)現(xiàn)而言是不可取的，于是采用了文獻(xiàn)[4][5]提出的滑動窗技術(shù)：對所有狀態(tài)度量的初始值設(shè)為某一任意值，根據(jù)網(wǎng)格收斂原理，可認(rèn)為遞歸運(yùn)算一定步數(shù)得到的狀態(tài)度量值是可靠的。假設(shè)滑動窗口長度為l，則存儲α所需的空間變?yōu)閘×N×K，由于l=L，可見滑動窗大大減少了存儲空間，縮短了每次迭代的輸出時(shí)延。對于β而言，設(shè)窗口總數(shù)為M，窗口編號為i，則β變?yōu)椋?BR> 
滑動窗的使用在一定程度上影響了系統(tǒng)性能，但是對于FPGA實(shí)現(xiàn)而言這是必要的，并且正因?yàn)榛瑒哟坝?jì)數(shù)減少的存儲空間，于是可以同時(shí)將N個(gè)狀態(tài)度量并行計(jì)算且相應(yīng)存儲。
3 譯碼器的硬件實(shí)現(xiàn)方案
根據(jù)前面針對硬件實(shí)現(xiàn)所改進(jìn)的Log-MAP算法，譯碼器的硬件實(shí)現(xiàn)如圖1所示。
圖1中部虛線框圖所示即為一次Log-MAP譯碼操作，可以看到其中由于計(jì)算狀態(tài)度量以及外信息時(shí)所需的輸入信號在時(shí)間上是不同的，于是需要有相應(yīng)的存儲空間存儲這些信息，使進(jìn)入各模塊的數(shù)據(jù)時(shí)間上一致。圖1中的數(shù)據(jù)處理與控制模塊完成了以上的功能，為計(jì)算前、后向狀態(tài)度量以及外信息提供了時(shí)序上的保證。
?
3.1 分支度量計(jì)算
由式(4)、式(5)以及根據(jù)第2節(jié)中的分析，圖2、圖3分別給出了并行計(jì)算[6] 前向、后向狀態(tài)度量的結(jié)構(gòu)圖。從式(3)計(jì)算分支度量γ可以看到，每次迭代時(shí)的值只與輸入的信息比特和校驗(yàn)比特有關(guān)，且對應(yīng)每個(gè)輸入信息的分支度量γ只有4種可能，于是本應(yīng)計(jì)算2N個(gè)分支度量被減少到4次，大大減少了RAM空間。在圖2和圖3中，根據(jù)式(4)和式(10)，選擇相應(yīng)的分支度量和狀態(tài)度量進(jìn)行求和操作并取最大值，得到下一組狀態(tài)度量。其中，由于FPGA實(shí)現(xiàn)時(shí)受到量化位數(shù)的限制，需要對每次迭代后輸出的狀態(tài)度量進(jìn)行判決，一旦超出量化后可以表示的最大數(shù)，則需要對該次迭代輸出的N個(gè)狀態(tài)度量減去某一常數(shù)，進(jìn)行歸一化處理。
3.2 前后向狀態(tài)度量的計(jì)算
從式(4)和式(10)中可以看到，前、后向狀態(tài)度量在計(jì)算時(shí)需要利用上一次計(jì)算得到的結(jié)果作為下一次迭代的輸入，如果數(shù)據(jù)流不斷地輸入，即每個(gè)時(shí)鐘對應(yīng)一個(gè)輸入數(shù)據(jù)，則這種迭代運(yùn)算無法進(jìn)行流水線計(jì)算，一旦運(yùn)算復(fù)雜度過大，必然造成在一個(gè)時(shí)鐘內(nèi)不能完成運(yùn)算的現(xiàn)象。由式(3)，計(jì)算分支度量需要2次加(減)法運(yùn)算；計(jì)算狀態(tài)度量時(shí)，該時(shí)刻的狀態(tài)度量與分支度量相加需要1次加法運(yùn)算，并且根據(jù)式(2)，對結(jié)果進(jìn)行修正，又需要1次加法，此外如果數(shù)據(jù)溢出則還需要1次減法歸一化操作。由上面分析可見，在一個(gè)時(shí)鐘里需要2次加法運(yùn)算來計(jì)算分支度量，同時(shí)1個(gè)時(shí)鐘里還需要2～3次加(減)法運(yùn)算來計(jì)算狀態(tài)度量。
對于高速率、高性能譯碼而言，系統(tǒng)時(shí)鐘頻率相當(dāng)高，且加(減)法的位數(shù)也比較大，要在一個(gè)時(shí)鐘里完成上述操作是不可能的。反之，如果將每次加法都用寄存器型的變量來運(yùn)算，即每個(gè)時(shí)鐘周期只完成一次加法運(yùn)算，使用2～3個(gè)時(shí)鐘周期完成一次計(jì)算，這樣局部實(shí)現(xiàn)加法流水線操作，更容易使FPGA運(yùn)算滿足時(shí)鐘約束。但是，從前面的分析可以看到，迭代運(yùn)算使得數(shù)據(jù)流的連續(xù)性在這種流水加法時(shí)必然造成加法的錯(cuò)位。
為了解決上述兩個(gè)矛盾，輸入數(shù)據(jù)就不能按照每個(gè)時(shí)鐘進(jìn)行輸入，而必須降低輸入數(shù)據(jù)的頻率。假設(shè)在a(a≤3)個(gè)時(shí)鐘周期內(nèi)完成一次迭代運(yùn)算，于是輸入數(shù)據(jù)的頻率也必須為原始頻率的1/a。這樣，為了整體上達(dá)到系統(tǒng)速率，就需要a個(gè)同樣的模塊并行運(yùn)算，即利用FPGA資源來換取速度。為保證譯碼速度，只能犧牲面積來實(shí)現(xiàn)上述的復(fù)雜加法運(yùn)算。另外從分析可知，計(jì)算前、后向狀態(tài)度量時(shí)最多需要3次加法操作，而一般情況僅需要2次加法運(yùn)算，折衷面積和速度，選用2個(gè)時(shí)鐘完成一次迭代運(yùn)算較為理想。這樣，利用了雙倍的資源，實(shí)現(xiàn)了高時(shí)鐘頻率的運(yùn)算。圖4給出了實(shí)現(xiàn)框圖，其中n為輸入譯碼塊的序號。
?
4 仿真與測試
為了滿足B3G系統(tǒng)中對數(shù)據(jù)業(yè)務(wù)高傳輸速率、高性能的要求，對Turbo碼的碼長、碼狀態(tài)數(shù)以及迭代次數(shù)都有較高的要求。折衷性能和實(shí)現(xiàn)代價(jià)，在系統(tǒng)實(shí)現(xiàn)中采用了4 416的編碼長度，編碼器約束長度為4，編碼器碼率為1/3，5次迭代譯碼。
首先在系統(tǒng)仿真平臺SPW下完成系統(tǒng)浮點(diǎn)仿真，并采用適當(dāng)?shù)牧炕椒ㄒ约暗?節(jié)中提到的硬件實(shí)現(xiàn)改進(jìn)方法對系統(tǒng)進(jìn)行定點(diǎn)仿真。其中信源由隨機(jī)數(shù)產(chǎn)生，并對其進(jìn)行QPSK調(diào)制。整個(gè)系統(tǒng)在AWGN信道下進(jìn)行仿真測試，圖5給出了浮點(diǎn)仿真和定點(diǎn)仿真的性能曲線。從圖中可以看到，定點(diǎn)化后的性能和浮點(diǎn)仿真有0.1dB左右的衰減，但在0.95dB左右其誤碼率已達(dá)到10-6 數(shù)量級，滿足了B3G系統(tǒng)對于信道編譯碼的性能要求。
其次采用Xilinx公司的XC2VP70芯片對FPGA實(shí)現(xiàn)單個(gè)Turbo譯碼進(jìn)行了驗(yàn)證。對于少量的譯碼塊，采用與SPW平臺仿真對比的方法進(jìn)行驗(yàn)證。對于連續(xù)大量的譯碼塊，采用Xilinx公司Virtex2系列芯片內(nèi)嵌的CPU核PowerPC405進(jìn)行輔助測試。利用FPGA實(shí)現(xiàn)編碼和譯碼功能，通過PowerPC405核模擬一個(gè)AWGN信道將編譯碼模塊相連接，構(gòu)成一個(gè)片上系統(tǒng)，在單板上實(shí)現(xiàn)Turbo編譯碼系統(tǒng)的驗(yàn)證。圖6給出了單板驗(yàn)證的框圖，圖7是該單板系統(tǒng)下仿真曲線。
最后，在上一步測試的基礎(chǔ)上，使用4片XC2VP70芯片實(shí)現(xiàn)B3G系統(tǒng)的信道譯碼運(yùn)算。其中系統(tǒng)時(shí)鐘頻率為100MHz，進(jìn)入整個(gè)Turbo譯碼系統(tǒng)的數(shù)據(jù)速率為100Mbps，在整個(gè)B3G系統(tǒng)上行全鏈路狀態(tài)下完成測試。表1給出了每片F(xiàn)PGA的資源使用狀況。
?
本文深入研究了Turbo碼的Log-MAP譯碼算法，對其FPGA實(shí)現(xiàn)做了優(yōu)化和改進(jìn)，提出了一種高性能、高速率的基于Log-MAP算法的Turbo碼硬件譯碼算法，并利用FPGA予以實(shí)現(xiàn)。該改進(jìn)的實(shí)現(xiàn)算法在保證系統(tǒng)低誤碼率和短輸出時(shí)延的情況下，提高了譯碼速率、降低了運(yùn)算復(fù)雜度、減少系統(tǒng)消耗資源。實(shí)驗(yàn)表明，該算法實(shí)現(xiàn)的Turbo譯碼在B3G系統(tǒng)中具有良好的性能，對于實(shí)現(xiàn)其他速率的Turbo譯碼也具有一定的參考價(jià)值。
參考文獻(xiàn)
1 Berrou C, Glavieux A, and Thitimajshima P.Near shannon limit error-correcting coding and decoding: turbo codes. In: Proc of ICC′93:1064～1070
2 Robertson P, Villebrun E, Hoeher P. A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain. Communications,1995;ICC 95 Seattle,1009～1013
3 Hagenauer J, Hoeher P. A viterbi algorithm with soft decision outputs and its applications. 10.1109/GLOCOM: 1680～1686
4 Viterbi A J. An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes. IEEE Select. Areas in Commun, 1998;16(2):260～264
5 徐韋峰,秦東,李志勇.滑動窗在Turbo碼解碼系統(tǒng)中的應(yīng)用及改進(jìn). 電子學(xué)報(bào),2000;(9)
6 Thul, M.J., Wehn, N. FPGA implementation of parallel turbo-decoders. Integrated Circuits and Systems Design, In:SBCCI 2004. 17th Symposium on 7-11 Sept.2004:198～203