基于RADIX-4的Turbo碼全并行譯碼算法*

趙瑞祥，潘克剛，王欣婷

(中國人民解放軍陸軍工程大學 通信工程學院，南京210007)

0 引 言

Turbo碼是一種性能優(yōu)異的信道編碼方式，編碼復雜度低，糾錯性能好，通用性較強，技術成熟，在3G、4G地面移動通信系統(tǒng)、衛(wèi)星移動通信系統(tǒng)和深空通信系統(tǒng)等領域中得到了廣泛應用。但是，Turbo碼通用譯碼算法采用串行迭代的譯碼方式，在更高業(yè)務速率、更低傳輸時延的應用場景中面臨巨大的挑戰(zhàn)[1]。

LTE(Long Term Evolution)系統(tǒng)中Turbo碼采用分塊并行譯碼思想，通過QPP(Quadratic Permutation Polynomials)交織器[2]實現(xiàn)了譯碼過程的部分并行，但是譯碼算法固有的串行性使吞吐量仍受到極大限制。

為了提高吞吐量，Turbo碼主要采用的譯碼架構有PMAP(Parallel MAP)和XMAP(Pipelined MAP)[3]。PMAP即傳統(tǒng)的分塊并行譯碼方式，然而面對長度較小的碼塊和較高的碼率會造成性能的下降；XMAP架構主要是源于狀態(tài)度量值遞歸時構造的X形狀的結構，實現(xiàn)了功能上的并行。但是這兩種架構都受到譯碼并行度的限制，可實現(xiàn)的最高吞吐量為1～2 Gb/s[4-6]。為了實現(xiàn)Turbo碼最高的譯碼并行度，提高吞吐量，文獻[7]提出了全并行譯碼最小和算法，但是該方法只能應用在很有限的Turbo碼字結構中；文獻[8]提出了一種利用模擬電流表示軟信息的全并行譯碼器，但是它只支持非常短的信息長度；文獻[9]提出了一種基于隨機序列的全并行譯碼架構，但是它比傳統(tǒng)的Log-MAP算法的時延和處理吞吐量性能上都要差。

直到Turbo碼全并行譯碼算法(Fully-Parallel MAP,FPMAP)[10]的提出，將整個碼塊的每個子塊大小分割成了1 b，獲得了最大的并行度，在吞吐量和時延上比Turbo碼最先進的譯碼算法[4]要好6.86倍。對于FPMAP算法，后續(xù)又進行了深入研究和完善，包括改進的外信息轉移(Extrinsic Information Transfer,EXIT)圖[11]、Turbo均衡算法的研究[12]以及在圖形處理器(Graphics Processing Unit,GPU)、超大規(guī)模集成電路(Very Large Scale Integration,VLSI)等各種硬件上的實現(xiàn)[13-14]。通過對FPMAP算法硬件架構的改進，證實其可以實現(xiàn)超過15 Gb/s的高吞吐量和低至0.42 μs的時延。但是，F(xiàn)PMAP算法要達到傳統(tǒng)譯碼算法的性能，需要增加約6倍的譯碼迭代次數(shù)，并且需要消耗大量的硬件資源。

針對FPMAP算法存在的問題，本文提出了一種基于RADIX-4的全并行譯碼算法。改進算法將狀態(tài)轉移圖上前后兩個時刻狀態(tài)轉移過程合并，在保留最大并行效率的同時增加了FPMAP算法的串行性。譯碼時以“比特對”的形式操作進行迭代，將計算單元減少一半，顯著降低了運算復雜度和存儲開銷；在相同迭代次數(shù)條件下，該方法的譯碼性能較FPMAP算法顯著提高。

1 Turbo碼的并行譯碼

1.1 LTE系統(tǒng)中的Turbo碼譯碼算法

Turbo碼譯碼器的基礎運算是MAP算法，其本質(zhì)是串行處理的，在譯碼過程中需要遞推計算后向狀態(tài)度量值，因此需要等到一個完整的碼塊全部接收才能進行譯碼。碼塊越長，譯碼時延就越大。LTE系統(tǒng)中采用分塊并行譯碼來提高吞吐量，具體如圖1所示。在這種譯碼架構下，將長度為K的碼塊分成長度相等的M個子碼塊，每個子碼塊配備一個單獨的子譯碼器，M被稱為譯碼并行度。一個子碼塊同時又分成若干個窗，在窗的層面上譯碼是串行的。譯碼時，上面的M個子譯碼器獨立進行譯碼，譯碼完成后統(tǒng)一將外信息經(jīng)交織器傳遞給下面子譯碼器，下面的M個子譯碼器再進行相同的操作，完成一次迭代過程。每個子譯碼器完成一次譯碼迭代后，需要保留邊界處的狀態(tài)度量值α和β，作為下一次迭代開始時相鄰子塊的狀態(tài)度量值的初始值。LTE中的Turbo碼分塊并行譯碼，實現(xiàn)了譯碼并行度為M的部分并行運算，譯碼時延大致為串行算法的1/M。

圖1 分塊并行譯碼算法

編碼交織器采用QPP交織器。QPP交織器作為一種確定型交織器，采用兩個二次多項式進行交織和解交織運算。對于碼長為K的碼塊中第i個比特，交織后的順序變?yōu)棣?i)=mod[(f1·i+f2·i2),K]，f1和f2為交織參數(shù)，均小于K。交織地址的計算可以采用遞歸的方式，無需乘法或者取模運算，并且數(shù)據(jù)經(jīng)過QPP交織器后的位置信息仍具有相同的奇偶性。較為簡單的生成多項式使其復雜度低，易于實現(xiàn)。QPP交織器可以實現(xiàn)并行譯碼的無沖突交織，大大增強譯碼器的并行處理能力，能夠給LTE中Turbo碼提供更高的譯碼速率。

1.2 Turbo碼的全并行譯碼算法

全并行譯碼算法實際是分塊并行譯碼算法的一種極端情況，即把每個碼塊的大小減小到1，然后分別對應一個譯碼計算單元進行譯碼，并將這些單元分為上下兩路。其基本譯碼結構如圖2所示。

圖2 全并行譯碼算法

不同于LTE中的部分并行譯碼算法，全并行譯碼算法關鍵在于迭代計算時充分利用了QPP交織器的特性——數(shù)據(jù)經(jīng)過QPP交織器后的位置信息仍具有相同的奇偶性。于是將整個數(shù)據(jù)分為兩組，上路奇數(shù)位置和下路偶數(shù)位置的數(shù)據(jù)為一組，如圖中白色譯碼塊所示；上路偶數(shù)位置和下路奇數(shù)位置的數(shù)據(jù)為另一組，如圖中陰影譯碼塊所示。一次迭代過程就分為了兩個半次迭代過程，在上半次迭代過程中，第一組白色譯碼塊進行計算并交換外信息和傳遞狀態(tài)度量值；下半次迭代過程中，第二組陰影譯碼塊進行計算并交換外信息和傳遞狀態(tài)度量值，每次操作上下兩路都有一半的碼字進行譯碼。綜合來看，每半次迭代就可以交換一半外部信息，而且上下兩路互相交換的是固定對應位置的外部信息。相比于傳統(tǒng)的Log-MAP算法，全并行譯碼算法的譯碼并行度為N，大大減少了譯碼時延。

全并行譯碼算法中的每一個比特都要配置一個相應的計算單元，消耗的資源過多，計算復雜度偏大[15]。同時每個算法塊置信度不是依靠前向和后向遞歸計算傳播，而是依靠足夠數(shù)量的譯碼迭代來完成，迭代次數(shù)較少會造成狀態(tài)度量值α和β的不可靠。在相同迭代次數(shù)下性能會下降，一般達到相同性能需要調(diào)用的迭代次數(shù)是Log-MAP算法的6倍左右。

2 基于RADIX-4的全并行譯碼算法

2.1 譯碼基本結構

在Turbo碼傳統(tǒng)譯碼過程中，計算狀態(tài)轉移度量值時，一個時鐘處理一個比特,RADIX-4算法則是將前后兩個相鄰時刻狀態(tài)轉移過程合并，提高了吞吐量和譯碼速度，并且算法的正確性和可靠性在理論上同傳統(tǒng)算法保持了基本一致。以LTE系統(tǒng)中Turbo碼(15/13)8為例，合并相鄰兩個時刻的狀態(tài)轉移路徑，可以得到RADIX-4算法[18]狀態(tài)轉移圖如圖3所示，其中S2k(0,1,…,7)表示輸入變化的8個狀態(tài)。

圖3 RADIX-4狀態(tài)轉移圖

改進后的全并行譯碼算法如圖4所示，相鄰的兩個比特合并成一個數(shù)據(jù)塊進行處理，一共組成了N組“比特對”，數(shù)據(jù)塊內(nèi)部的兩個比特本質(zhì)是串行的，增加的串行性能夠在一定程度上減少全并行算法的迭代次數(shù)。同時數(shù)據(jù)塊之間仍然采用QPP交織器，最大限度地保留全并行譯碼算法的并行度。整個碼塊同樣分成兩組計算，上路奇數(shù)塊和下路偶數(shù)塊為一組，上路偶數(shù)塊和下路奇數(shù)塊為另一組，每半次迭代時間里每組分別進行譯碼操作。整個譯碼時鐘周期與碼長無關，一次迭代都是需要2個時鐘。

圖4 改進算法框圖

2.2 算法過程

(1)

在傳統(tǒng)部分并行算法中，輸入數(shù)據(jù)為3路，即系統(tǒng)信息、校驗信息和先驗信息，外信息需要在碼塊前、后向狀態(tài)度量值傳遞過來后才能開始計算，但改進算法每個計算單元的前向、后向狀態(tài)度量值的傳遞和外信息的計算是同時進行的。

通過對文獻[10]中式(2)～(5)的改進，推導出改進算法的計算流程，即每個計算單元按照式(2)～(6)進行執(zhí)行。式(2)～(4)是譯碼塊前向和后向狀態(tài)度量值的計算，式(5)和(6)是外信息的拆分計算。譯碼開始時，上路和下路的白色譯碼塊首先進行譯碼，具體計算過程按式(2)～(6)進行，將輸出結果進行儲存、交織，然后所有陰影譯碼塊執(zhí)行相同操作，完成一次完整迭代過程。

β2k+2(S2k+2)，

(2)

β2k+2(S2k+2)，

(3)

(4)

(5)

(6)

式(3)～(6)都使用了Log-MAP算法中的max*函數(shù)，其定義為

max*(δ1,δ2)=max(δ1+δ2)+ln(1+e-|δ1-δ2|)。

(7)

max*函數(shù)具有如下性質(zhì)：

max*(δ1-δ3,δ2-δ3)=max*(δ1,δ2)-δ3。

(8)

式(3)和式(4)利用式(8)得到，將每個碼塊前向和后向狀態(tài)度量值結合計算，實現(xiàn)最大并行度。初始參數(shù)中與FPMAP相同，若編碼寄存器在編碼結束時狀態(tài)未知，上下兩路的前向和后向狀態(tài)度量值分別初始化為α0=[0,-∞,-∞,…,-∞]N和βN=[0,0,0,…,0]N。這是由于編碼器初始S0、結束SN狀態(tài)已知時，狀態(tài)度量值α0和βN在該狀態(tài)取值概率為1，其他狀態(tài)概率為0，取對數(shù)后分別變?yōu)榱?和負無窮；結束狀態(tài)未知時β初值一般都設為0。不同的是，狀態(tài)轉移圖的初始狀態(tài)S0=0，在決定下一狀態(tài)時,FPMAP算法的初始輸入比特為[0,1]兩種情況；改進算法初始輸入比特的取值為[00，01，10，11]4種情況，確定輸入比特后直接計算出S2狀態(tài)，省去了由S0經(jīng)S1再到S2的過程。同樣地，初始參數(shù)中前向和后向度量值經(jīng)過分支度量值取值后直接計算出α2和βN-2。

對于式(5)、(6)外信息的拆分計算，按照下面步驟進行：

由MAP算法可以得到每個碼塊的對數(shù)似然比輸出信息為

(9)

式中：XY的取值為00、01、10、11。為方便拆分計算碼塊中每個比特的對數(shù)似然比信息，令

(10)

δ2k(S2k,S2k+2)=α2k(S2k)+γ2k,2k+1(S2k,S2k+2)+

β2k+2(S2k+2),

(11)

則第一個比特的對數(shù)似然比為

Rj,2k=

max*[Rj,(2k,2k+1)(10),Rj,(2k,2k+1)(11)]-

max*[Rj,(2k,2k+1)(01),Rj,(2k,2k+1)(00)]=

max*[LLR2k(10),LLR2k(11)]-

max*[LLR2k(01),LLR2k(00)]。

同理，可以求得第二個比特的對數(shù)似然比為

Rj,2k+1=max*[LLR2k(11),LLR2k(01)]-

max*[LLR2k(10),LLR2k(00)]。

(12)

2.3 復雜度分析

結合式(2)～(6)對本文算法與全并行譯碼算法和LTE系統(tǒng)中經(jīng)典譯碼算法的運算量進行對比。為方便比較，傳統(tǒng)算法給出的是每個碼字需要的運算量。在分析過程中，為使數(shù)據(jù)更加準確，遵循以下兩個原則：一是可以重復利用的值不再重復計算，如狀態(tài)轉移過程中相同的γ2k,2k+1值；二是取值為0 的值不算入加減法中。改進算法狀態(tài)轉移圖中S2k到S2k+2有32種情況，式(2)中α和β的加法則需要計算32次；編碼前后數(shù)據(jù)共4組，代入等式后的加法數(shù)為7+12+16+12=47個，則式(2)總計79個加法運算。狀態(tài)總數(shù)一共8種，則式(3)、(4)各需要8個加法和8個max*運算，式(5)、(6)一共需要4個加法運算和8個max*運算。

對于單個碼塊而言，全并行譯碼算法的運算量最小，但是以消耗大量的計算單元為代價；改進算法的運算量最大，這是因為在一個碼塊中需要處理2 b信息，增加了運算復雜度，但其總的碼塊數(shù)卻是全并行算法的一半。

表1總結了總運算復雜度、并行度、寄存器消耗等性能，其中對LTE系統(tǒng)中使用的最先進的部分并行算法[4]也進行了比較，N為碼長，譯碼滑動窗長度為32，具體計算過程見文獻[10]。

表1 四種算法性能比較

由表1可見：

(1)在總運算復雜度方面，改進算法的運算復雜度最小。表1給出了每個碼塊的平均運算量，進行一次譯碼迭代時，部分并行算法的運算復雜度最高，并且與Log-MAP、全并行譯碼算法一樣，需要進行操作的碼塊數(shù)是改進算法的2倍，因此改進算法需要的總運算復雜度最低。

(2)在并行計算方面，改進算法保留了全并行譯碼算法的并行度，一次迭代過程只需要2個時鐘。傳統(tǒng)的Log-MAP算法的運算是與總的碼塊長度相關的，上下兩路數(shù)據(jù)各需要2N個時鐘來傳遞計算狀態(tài)度量值α和β，部分并行算法由于采用了長度為32的窗進行計算，因此只需要N/32的時鐘數(shù)。

(3)在迭代次數(shù)方面，全并行譯碼算法和改進算法譯碼收斂速度較慢，迭代次數(shù)是傳統(tǒng)算法的6～7倍，采用滑動窗技術的部分并行算法迭代次數(shù)與傳統(tǒng)算法一致。Log-MAP算法中，由于每個碼塊內(nèi)的數(shù)據(jù)是串行譯碼的，狀態(tài)度量值α和β的可靠性通過傳遞來不斷提高。采用滑動窗技術的部分并行算法譯碼本質(zhì)上與傳統(tǒng)算法一樣，只是通過部分并行操作實現(xiàn)吞吐量的提高。全并行算法只能依靠足夠數(shù)量的譯碼迭代來完成。改進算法“比特對”的譯碼形式，增加了一定的譯碼串行性，可以減少全并行譯碼算法需要的迭代次數(shù)。

(4)在寄存器使用方面，改進的算法減少了全并行譯碼算法近一半的使用量。寄存器主要用來存儲前向、后向狀態(tài)度量值和外信息的LLR值。在全并行算法和改進算法中，兩組數(shù)據(jù)交錯進行譯碼，寄存器可以重復使用。全并行算法中，需要存儲N個外信息LLR值、8N個前向狀態(tài)度量值和8N個后向狀態(tài)度量值，以及3N個接收到的先驗信息LLR值，總共需要20N個寄存器。改進算法需要存儲N個外信息LLR值、4N個前向狀態(tài)度量值和4N個后向狀態(tài)度量值，以及3N個先驗LLR值，總共需要12N個寄存器。傳統(tǒng)Log-MAP算法的寄存器用量很小，是因為在譯碼過程中一次迭代可以多次重復使用同一寄存器，該算法通過使用RAM儲存訪問地址和LLR值。

3 仿真對比

對改進算法和全并行譯碼算法性能進行了Matlab仿真，采用LTE標準下的Turbo碼(15/13)8，主要仿真了不同碼長、碼率和不同迭代次數(shù)等條件下的性能差異，仿真具體參數(shù)值見表2。

表2 仿真條件

圖5仿真的碼塊長度分別為6 144和960，迭代次數(shù)均為8和10次，碼率分別為1/3和1/2。BER表示誤碼率，Eb/N0為信噪比，F(xiàn)PMAP表示全并行譯碼算法，NEW表示改進算法。從圖中可以看出，基于RADIX-4算法的改進算法的誤碼性能整體好于全并行譯碼算法。圖5(a)中碼率為1/3、迭代8次時，改進算法在相同BER條件下性能改善約0.6 dB；迭代10次時，性能改善約0.5 dB；碼率為1/2性能改善分別為0.9 dB和0.7 dB。在圖5(b)中碼率為1/3、迭代8次時，改進算法在相同BER條件下性能改善約0.5 dB；迭代10次時，性能改善約0.3 dB；碼率為1/2性能改善分別為0.7 dB和0.5 dB。碼長越長、碼率越高，改進算法的性能提升越明顯。

(a)碼長為6 144

圖6在QPSK調(diào)制方式下對960碼長、1/3碼率的Turbo碼進行了仿真，兩種算法性能稍有下降，改進算法的性能提升與BPSK調(diào)制方式基本相差不大，在迭代8次、10次條件下BER性能分別提升0.5 dB和0.2 dB。

圖6 QPSK調(diào)制方式下的誤碼率對比

圖7在Rayleigh衰落信道條件下進行了仿真，此時FPMAP算法的信道條件與文獻[10]保持一致，在該信道條件下兩種算法譯碼性能均下降較為明顯，但改進算法仍保持了對FPMAP算法性能的提升。

圖7 Rayleigh衰落信道條件下的誤碼率對比

圖8對比了三種算法在碼長為960時達到相同性能界所需要的迭代次數(shù)，改進算法比FPMAP算法平均要少2次迭代左右。傳統(tǒng)Log-MAP算法在迭代1次、2次時達到的誤碼性能，F(xiàn)PMAP算法分別需要7次和14次迭代才能達到，迭代次數(shù)大約為7倍，而改進算法則分別需要5次和12次迭代就能達到，一定程度上減少了迭代次數(shù)。

圖8 不同迭代次數(shù)對比

綜合來說，在相同迭代次數(shù)條件下，改進算法的譯碼性能得到了較大的提升，或達到相同的性能時有效減少了全并行譯碼算法的迭代次數(shù)。

4 結束語

本文提出的全并行譯碼的改進算法，結合了RADIX-4算法的優(yōu)勢，以“比特對”的形式增加了一定的譯碼串行性，有效降低了全并行譯碼算法的運算復雜度和存儲開銷，特別是減少了近一半的寄存器使用量。仿真結果表明，在相同迭代次數(shù)條件下，該算法的譯碼性能顯著提高，能夠更好地應用在不同場景之中。但是，Turbo 碼全并行譯碼算法在高碼率下譯碼性能不佳，并且在譯碼硬件架構上還有較大提升空間，改進算法在迭代次數(shù)增多后性能提升不明顯，這些問題有待進一步研究。