摘 要： 在深入研究Turbo譯碼算法" title="譯碼算法">譯碼算法的基礎上，重點分析了Log-MAP算法，并針對下一代移動通信系統" title="移動通信系統">移動通信系統B3G(Beyond 3G)數據業務高傳輸速率" title="傳輸速率">傳輸速率的要求，提出了一種高效的基于Log-MAP譯碼算法的FPGA并行實現方法，并利用Xilinx公司的FPGA芯片并行實現100Mbps的譯碼。實驗表明，對B3G系統中高速數據進行譯碼時，具有較好的誤碼性能和較理想的譯碼時延" title="時延">時延。
關鍵詞： Log-MAP算法 下一代移動通信系統 FPGA實現 100Mbps并行譯碼
Turbo碼[1]自1993年提出以來，由于其接近Shannon極限的優異性能，被廣泛應用于無線通信系統中，已被確定為第三代移動通信系統的信道編譯碼方案之一。在下一代移動通信系統中，要求更高的傳輸速率和更好的誤碼性能，對信道編譯碼的要求也相應提高。然而，由于Turbo碼迭代譯碼算法的限制，使得譯碼復雜度和譯碼時延成為硬件實現" title="硬件實現">硬件實現的重要問題，性能和資源上的折衷考慮是實現Turbo碼的關鍵。本文對Turbo碼進行了深入的研究，提出了適合于FPGA實現的改進的Log-MAP[2]算法，并采用Xilinx公司的XC2VP70芯片實現了譯碼功能，該譯碼模塊用于B3G系統上行鏈路。實驗表明，在高速率傳輸下譯碼的誤碼率以及譯碼輸出時延能滿足B3G業務要求。
1 Log-MAP算法
從Turbo碼的提出至今，其譯碼算法目前主要有最大后驗概率(MAP)算法和軟輸出維特比譯碼算法(SOVA)算法[3]。SOVA算法運算量最小，較適合硬件實現，但性能較差。目前而言，MAP算法被認為是最佳的譯碼算法，但是由于其包含大量的乘法和指數運算，不利于硬件實現。在此基礎上簡化而來的是Max-Log-MAP[4]算法：
ln(ex+ey)≈MAX(x,y) (1)
Max-Log-MAP算法將MAP算法轉移到對數域中可以大大降低計算量：在對數域中，不再需要指數運算，原來的乘法轉變成加法。然而，這種近似卻引來了一定的性能損失。文獻[2]中的實驗表明，Max-Log-MAP算法相對于MAP算法有0.5dB的損失。實際上，根據Jacobian展開式，ln(ex+ey)≈MAX(x,y）+ln(1+e-|x-y|)，就是Log-MAP算法。可以看到，Log-MAP算法僅僅是將MAP算法轉換到對數域中進行運算，因此其性能相對于MAP算法是一致的。然而在Log-MAP算法中，對數和指數運算仍然存在，這對于硬件實現還是不利的。文獻[2]提出將Log-MAP算法中的加項利用查找表的方法來實現，以減小運算復雜度，同時改善(1)式的性能，即：
ln(ex+ey)≈MAX(x,y)+f(x,y) (2)
=MAX*(x,y)
其中，f(x,y)是關于x-y的分段函數。
下面簡要介紹一下Log-MAP算法，其中各分量均為對數域表示。
通過迭代運算，對最后一次迭代得到的LLR進行硬判決，可以得到譯碼輸出的結果。
2 譯碼器硬件實現時的改進
從式(6)、(7)中可以看到每次迭代時都需要先計算LLR，再通過LLR來計算下一次迭代時需要的外信息Le。但是LLR實際上在最后判決時才會用到，而對于每一級迭代而言，外信息Le才是最關心的。于是，將上面算法作一改進，讓系統在每次迭代時僅計算Le，直到判決時再計算LLR，以減少運算復雜度。推導可知：
通過以上改進，使得在迭代過程中不依賴于LLR，既減少了計算量，又減少了計算過程中存儲LLR所需要的RAM空間。
從式(8)看到，對于整個Log-MAP譯碼算法而言，由于后向迭代，需要大量的RAM來存儲已經計算得到的前向狀態度量α。對于碼長為L具有N狀態的Turbo碼，假設每個狀態度量用K比特量化，那么存儲所需的空間則為L×N×K。同時，每次迭代的輸出時延隨著碼長L增長。這對于硬件實現而言是不可取的，于是采用了文獻[4][5]提出的滑動窗技術：對所有狀態度量的初始值設為某一任意值，根據網格收斂原理，可認為遞歸運算一定步數得到的狀態度量值是可靠的。假設滑動窗口長度為l，則存儲α所需的空間變為l×N×K，由于l=L，可見滑動窗大大減少了存儲空間，縮短了每次迭代的輸出時延。對于β而言，設窗口總數為M，窗口編號為i，則β變為：
滑動窗的使用在一定程度上影響了系統性能，但是對于FPGA實現而言這是必要的，并且正因為滑動窗計數減少的存儲空間，于是可以同時將N個狀態度量并行計算且相應存儲。
3 譯碼器的硬件實現方案
根據前面針對硬件實現所改進的Log-MAP算法，譯碼器的硬件實現如圖1所示。
圖1中部虛線框圖所示即為一次Log-MAP譯碼操作，可以看到其中由于計算狀態度量以及外信息時所需的輸入信號在時間上是不同的，于是需要有相應的存儲空間存儲這些信息，使進入各模塊的數據時間上一致。圖1中的數據處理與控制模塊完成了以上的功能，為計算前、后向狀態度量以及外信息提供了時序上的保證。
?
3.1 分支度量計算
由式(4)、式(5)以及根據第2節中的分析，圖2、圖3分別給出了并行計算[6] 前向、后向狀態度量的結構圖。從式(3)計算分支度量γ可以看到，每次迭代時的值只與輸入的信息比特和校驗比特有關，且對應每個輸入信息的分支度量γ只有4種可能，于是本應計算2N個分支度量被減少到4次，大大減少了RAM空間。在圖2和圖3中，根據式(4)和式(10)，選擇相應的分支度量和狀態度量進行求和操作并取最大值，得到下一組狀態度量。其中，由于FPGA實現時受到量化位數的限制，需要對每次迭代后輸出的狀態度量進行判決，一旦超出量化后可以表示的最大數，則需要對該次迭代輸出的N個狀態度量減去某一常數，進行歸一化處理。
3.2 前后向狀態度量的計算
從式(4)和式(10)中可以看到，前、后向狀態度量在計算時需要利用上一次計算得到的結果作為下一次迭代的輸入，如果數據流不斷地輸入，即每個時鐘對應一個輸入數據，則這種迭代運算無法進行流水線計算，一旦運算復雜度過大，必然造成在一個時鐘內不能完成運算的現象。由式(3)，計算分支度量需要2次加(減)法運算；計算狀態度量時，該時刻的狀態度量與分支度量相加需要1次加法運算，并且根據式(2)，對結果進行修正，又需要1次加法，此外如果數據溢出則還需要1次減法歸一化操作。由上面分析可見，在一個時鐘里需要2次加法運算來計算分支度量，同時1個時鐘里還需要2～3次加(減)法運算來計算狀態度量。
對于高速率、高性能譯碼而言，系統時鐘頻率相當高，且加(減)法的位數也比較大，要在一個時鐘里完成上述操作是不可能的。反之，如果將每次加法都用寄存器型的變量來運算，即每個時鐘周期只完成一次加法運算，使用2～3個時鐘周期完成一次計算，這樣局部實現加法流水線操作，更容易使FPGA運算滿足時鐘約束。但是，從前面的分析可以看到，迭代運算使得數據流的連續性在這種流水加法時必然造成加法的錯位。
為了解決上述兩個矛盾，輸入數據就不能按照每個時鐘進行輸入，而必須降低輸入數據的頻率。假設在a(a≤3)個時鐘周期內完成一次迭代運算，于是輸入數據的頻率也必須為原始頻率的1/a。這樣，為了整體上達到系統速率，就需要a個同樣的模塊并行運算，即利用FPGA資源來換取速度。為保證譯碼速度，只能犧牲面積來實現上述的復雜加法運算。另外從分析可知，計算前、后向狀態度量時最多需要3次加法操作，而一般情況僅需要2次加法運算，折衷面積和速度，選用2個時鐘完成一次迭代運算較為理想。這樣，利用了雙倍的資源，實現了高時鐘頻率的運算。圖4給出了實現框圖，其中n為輸入譯碼塊的序號。
?
4 仿真與測試
為了滿足B3G系統中對數據業務高傳輸速率、高性能的要求，對Turbo碼的碼長、碼狀態數以及迭代次數都有較高的要求。折衷性能和實現代價，在系統實現中采用了4 416的編碼長度，編碼器約束長度為4，編碼器碼率為1/3，5次迭代譯碼。
首先在系統仿真平臺SPW下完成系統浮點仿真，并采用適當的量化方法以及第3節中提到的硬件實現改進方法對系統進行定點仿真。其中信源由隨機數產生，并對其進行QPSK調制。整個系統在AWGN信道下進行仿真測試，圖5給出了浮點仿真和定點仿真的性能曲線。從圖中可以看到，定點化后的性能和浮點仿真有0.1dB左右的衰減，但在0.95dB左右其誤碼率已達到10-6 數量級，滿足了B3G系統對于信道編譯碼的性能要求。
其次采用Xilinx公司的XC2VP70芯片對FPGA實現單個Turbo譯碼進行了驗證。對于少量的譯碼塊，采用與SPW平臺仿真對比的方法進行驗證。對于連續大量的譯碼塊，采用Xilinx公司Virtex2系列芯片內嵌的CPU核PowerPC405進行輔助測試。利用FPGA實現編碼和譯碼功能，通過PowerPC405核模擬一個AWGN信道將編譯碼模塊相連接，構成一個片上系統，在單板上實現Turbo編譯碼系統的驗證。圖6給出了單板驗證的框圖，圖7是該單板系統下仿真曲線。
最后，在上一步測試的基礎上，使用4片XC2VP70芯片實現B3G系統的信道譯碼運算。其中系統時鐘頻率為100MHz，進入整個Turbo譯碼系統的數據速率為100Mbps，在整個B3G系統上行全鏈路狀態下完成測試。表1給出了每片FPGA的資源使用狀況。
?
本文深入研究了Turbo碼的Log-MAP譯碼算法，對其FPGA實現做了優化和改進，提出了一種高性能、高速率的基于Log-MAP算法的Turbo碼硬件譯碼算法，并利用FPGA予以實現。該改進的實現算法在保證系統低誤碼率和短輸出時延的情況下，提高了譯碼速率、降低了運算復雜度、減少系統消耗資源。實驗表明，該算法實現的Turbo譯碼在B3G系統中具有良好的性能，對于實現其他速率的Turbo譯碼也具有一定的參考價值。
參考文獻
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碼解碼系統中的應用及改進. 電子學報,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