基于CUDA的雙二進制Turbo碼并行譯碼方法

賈鐵燕

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

0 引言

雙二進制Turbo碼是在DVB-RCS標準(ETSI EN 301 790 V1.5.1[1]，以下簡稱790標準)中回傳信道采用的前向糾錯編碼方式。Turbo 譯碼器采用2個SISO 軟譯碼單元進行譯碼，2個 SISO 軟譯碼單元在譯碼時要進行信息交互，不斷在迭代中達到最大似然比[2-5]。對于雙二進制Turbo碼的譯碼算法，從性能上講，最大后驗概率[6](Maximum A Posteriori，MAP)算法是最優的，但是由于其存在大量的指數和乘法運算，復雜度較高，增加了實現的難度，Max-Log-MAP[7]算法在損失了一定性能的前提下對MAP算法進行了近似，可以降低一定的算法復雜度，從而更易實現。

Turbo碼作為分組碼，各分組間的譯碼算法可實現并行化，且單一分組內譯碼計算也存在可并行設計部分。目前Turbo碼譯碼算法主要由FPGA實現[8-10]。隨著集成電路的發展，原先僅用于加速圖形計算的GPU 逐步應用于信號處理[11]。CUDA[12]作為NVIDIA 推出的運算平臺，是一種通用并行計算架構，可使用C語言編寫顯示芯片上的執行程序。相對于FPGA實現更加靈活。本文提出了基于CUDA的對雙二進制Turbo碼的GPU并行加速譯碼方法。

1 編碼原理

790標準的雙二進制Turbo碼編碼器原理如圖1所示，采用并行級聯結構，由2個循環遞歸系統卷積碼編碼器(Circular Recursive System Code，CRSC)、1個隨機交織器和1個刪余器組成。對于碼流輸入順序，最高有效位(Most Significant Bit,MSB)對應著A，最低有效位(Least Significant Bit，LSB)對應B。每一個分組長度中k比特或N比特對(k=2×N)。其中，N是4的倍數(k是8的倍數)。

圖1 編碼器原理[1]

雙二進制Turbo碼采用CRSC結構，反饋支路的多項式為1+D+D3，Y校驗比特多項式為1+D2+D3，W校驗比特多項式為1+D3。

圖1中,3個寄存器狀態定義為S1，S2和S3，則編碼器狀態定義為S，S=S1×4+S2×2+S3。

確定2個編碼器的初始狀態Sc1、Sc2的方法如下：

② 查表1確定Sc；

之后再使用Sc做初始狀態進行編碼，得到Y、W為校驗位結果。

表1 循環狀態對照表[1]

S0NN(mod7)012345671Sc=0Sc=6Sc=4Sc=2Sc=7Sc=1Sc=3Sc=52Sc=0Sc=3Sc=7Sc=4Sc=5Sc=6Sc=2Sc=13Sc=0Sc=5Sc=3Sc=6Sc=2Sc=7Sc=1Sc=44Sc=0Sc=4Sc=1Sc=5Sc=6Sc=2Sc=7Sc=35Sc=0Sc=2Sc=5Sc=7Sc=1Sc=3Sc=4Sc=66Sc=0Sc=7Sc=6Sc=1Sc=3Sc=4Sc=5Sc=2

雙二進制Turbo碼的交織器由二級組成，第一級進行輸入比特對內部(A/B)的交織，第二級在比特對間進行交織。

定義默認交織參數P0，P1，P2和P3如表2所示。

表2 交織參數

分組長度(N對)P0{P1,P2,P3}4811{24,0,24}647{34,32,2}21213{106,108,2}22023{112,4,116}22817{116,72,188}42411{6,8,2}43213{0,4,8}44013{10,4,2}84819{2,16,6}85619{428,224,652}86419{2,16,6}75219{376,224,600}

對于第j對(j=0，1，…N-1)輸入比特：

第一層交織：如果jmod 2=0，交換此比特對中A、B；

第二層交織：如果jmod 4 =0，則P=0；如果jmod 4=1，則P=N/2+P1；如果jmod 4=2，則P=P2；如果jmod 4=3，則P=N/2+P3。新位置i=P0×j+P+1 modN。

在790標準中，提到了7種速率的刪余器：1/3，2/5，1/2，2/3，3/4，4/5，6/7。7種速率的刪余圖案[1]如圖2所示。

1/3YW11[]2/5YW1110[]1/2YW10[]2/3YW1000[]3/4YW100000[]4/5YW10000000[]6/7YW100000000000[]

圖2 刪余圖案(1表示保留)

2 譯碼原理

2.1 MAP及Max-Log-MAP算法

圖3 譯碼器原理[13]

后驗對數似然比：

lnP(uk|y)=ln(∑exp(Bk(s)+Γk(s′,s)+Ak(s′)))，

式中，

外信息：

式中，Lc為信道的可信值，計算方法為：

但是由于MAP算法存在大量指數和乘法運算，復雜度太高，不利于實現，于是采用了性能較好的Max-Log-MAP算法。Max-Log-MAP算法主要基于這樣一種近似：

log(ex+ey)≈max(x,y)。

2.2 循環譯碼方法

由于DVB-RCS采用的是循環碼，所以需要確定初始狀態，采用環形譯碼可以消除這一影響。在算法初始化時，將所有狀態取相同的初始度量，由于MAP算法可以在迭代中消除初始狀態錯誤選擇帶來的影響，從第二次迭代開始，狀態的初始度量取上次迭代時的度量值，即

2.3 硬判決方法

對于滿足迭代次數后的第二個SISO譯碼器輸出的后驗對數似然比，進行解交織送入判決器。對每一輸入比特對y，根據后驗對數似然比，取最大值即可得到最大可能的輸入y，從而完成譯碼判決。

3 基于CUDA的并行譯碼方法

3.1 CUDA模型原理

CUDA是NVIDIA的通用計算圖形處理器(General Purpose GPU，GPGPU)模型，使用C語言為基礎。CUDA 的編程模型將CPU 作為主控制器，GPGPU 作為數據處理器即協處理器[14]。CPU 和GPGPU協同來完成任務[15]。在CUDA的架構下，一個程序分為兩部分：host端和device端，host端是指在CPU上執行的部分，而device端則是在顯示芯片上執行的部分。device端的程序又稱為“kernel”。通常host端程序會將數據準備好后，復制到顯卡的內存中，再由顯示芯片執行device端程序，完成后再由host端程序將結果從顯卡的內存中取回。

在CUDA架構下，顯示芯片執行時的最小單位是thread(線程)。數個thread可以組成一個block(塊)。一個block中的thread能存取同一塊共享的內存，而且可以快速進行同步的動作。

每一個block所能包含的thread數目是有限的。但執行相同程序的block可以組成grid(格)。不同block中的thread無法存取同一個共享的內存，因此無法直接互通或進行同步。因此，不同block中的thread能合作的程度比較低。利用這個模式，可以讓程序不用擔心顯示芯片實際上能同時執行的thread數目限制。

CUDA假設 CUDA 線程可在物理上獨立的設備上執行，此類設備作為運行 C 語言程序的主機的協同處理器操作。例如，當內核在 GPU 上執行，而C語言程序的其他部分在 CPU 上執行時，就是這種情況。

此外，CUDA 還假設主機和設備均維護自己的動態隨機存儲器(Dynamic Random Access Memory，DRAM)，分別稱為主機存儲器和設備存儲器。因而，一個程序通過調用 CUDA 運行時來管理對內核可見的全局、固定和紋理存儲器空間，包括設備存儲器分配和取消分配，還包括主機和設備存儲器之間的數據傳輸。

3.2 Max-Log-MAP譯碼算法的CUDA實現

實現高效的加速效果，關鍵在于CUDA 內部資源的合理分配:實驗通過最大化并行線程的分配，以充分隱藏流水線延時[16]。為了解決Max-Log-MAP算法的并行化問題，設計了兩級并行的譯碼算法。兩級并行化設計實現了分組間并行與分組內并行，如圖4所示。對于Turbo碼這種分組碼結構，各分組譯碼算法相互獨立，利用并行化算法可以同時處理多個分組的譯碼，所以算法并行度至少為分組數。分組間并行實現，只需要將所有變量空間按分組數量進行擴展，各線程按自己所在分組，對所需變量空間的相應分組位置進行尋址即可。

對于一個分組，譯碼算法整個算法流程與圖3相同，是由各子模塊串行組成，各模塊由于計算的類型不同，可并行度也有差別，最理想的情況是可全部并行處理，最差的情況為不能并行，即進行串行處理。將各模塊單獨進行并行化處理優化，根據自身的算法計算步驟，將相互無關聯的計算進行并行算法設計，例如狀態轉移的路徑權值可并行計算，而遞歸則不能并行計算。

圖4 Turbo碼并行譯碼算法

交織器與解交織器的以一比特為并行單元。交織矩陣在程序運行階段初在主機端計算完成，并復制到設備端。每一個thread對一個比特進行置換操作，該thread根據所處理比特所在分組和在分組的位置，并讀取交織矩陣相應位置得到置換下標，進行置換操作。

分配每個thread完成一個s′到s狀態轉移的度量值計算，其中狀態s共8種，輸入共4種。為了方便代碼書寫，采用三維定義blockDim(partSize，8，4)，第一維表示block完成輸入比特對的數量，第二維表示當前狀態，第三維表示第幾種輸入情況。所以這個kernel需要定義的gridDim大小為(分組數×分組長度/partSize)。

由于這是一個遞歸運算，所以同一分組中輸入位之間的計算無法并行，而同一輸入位的狀態轉移的度量值計算與求最大值操作是可以并行的。綜上，分配一個二維thread，大小為(8，4)，即s為8種，相應s′為4種，每一thread完成一個分組的所有輸入位的相應s到s′的度量值計算。對于求最大值操作，采用二分法thread間協作并行處理。此kernel需要定義的gridDim即為分組數。

二分法計算如圖5所示。

圖5 8個點二分法計算示意

可以利用此法進行求和、連乘、最大值和最小值等運算。對于N個點需要進行ceil(lbN)次運算，即每次運算將所有點分成兩組，每組對應兩點進行計算。采用此方法，需要將所有點復制到block內的共享內存，即要保證所有數據不大于每個block的共享內存的最大值，且點數不能大于每個block最大并發線程數，并組在每一次計算后需要進行線程同步。

對于每一個輸入位，計算是不相互獨立的，分配一個二維thread，大小為(8,4)，即s為8種，相應s′為4種，每一thread完成一個輸入位的相應s到s′的度量值計算。此kernel需要定義的gridDim即為(分組數*分組長度)。

各輸入位以及不同輸入y的計算是相互獨立的，可由每個thread單獨完成。

硬判決器是根據后驗對數似然比，得到取最大值的位置，從而完成譯碼。對于每一個輸入比特對，相互之間計算是沒有關聯可并行的，且實際上完成的是求最大值位置的操作。由于輸入只有4種，數量較少，該操作可并行度不高，這里直接由一個thread完成全部操作，無需thread間合作，代碼依然采用二分法比較，可減少一次比較操作。

4 實驗結果

實驗在一個GPU工作站完成，配置如下：

CPU：Intel Xeon X5650@2.67GHz，

GPU：NVIDIA Tesla C2050。

實驗了4種分組長度N下，在8次迭代時，對于分組平均譯碼時間，GPU加速后程序與CPU運行時間比，實現結果如表3所示。

表3 分組平均譯碼時間(8次迭代)

分組長度CPU運行時間/msGPU運行時間/ms運行時間比641.28070.051524.882124.28390.190122.534409.07960.449820.1986417.52500.879819.92

由實現結果可見運行速度提高了大約20倍，而且可以看出，分組長度最小，加速性能越好。這是因為在采用二分法設計時，分組長度越小，并行化率越高。

5 結束語

本文介紹了雙二進制Turbo碼的編譯碼算法，提出了基于CUDA的GPU并行計算加速譯碼算法。基于Max-Log-MAP算法，設計了GPU實現的方法 ，并給出了實現并給出了進行GPU加速前后的運算速度對比。實驗結果表明，采用GPU加速后程序運行速度提高了大約20倍，說明該算法能夠有效提高譯碼速度。

[1] ETSI EN 301 790 V1.3.1,European Telecommunication Standards Institute,Digital Video Broadcasting:Interactive Channel for Satellite Distribution Systems[S],2003.

[2] BENEDETTO S,DIVSALAR D,MONTORSI G,et al. Serial Concatenation of Interleaved Codes:Peorfmrnace Anyalsis. Design and Iterative Decoding[J].IEEE Trans.on inf.Theory,1999,44(3):909-926.

[3〗 ROBERTSON P.Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Tubro) Codes[J]. Proc.GLOBECOM,1994(12):1298-1303.

[4] PEERZL C, SEGHERS J,DNAIEL J,et al. A Distnace Specutrum Interpretation of Tubro Codes.Trnas.[J].IEEE Trans.on inf.Theory,1996,42(6):1698 -1709.

[5] 劉東華.Turbo碼原理與應用技術[M].北京:電子工業出版社,2004.

[6] BAHLL R, COCKE J,JELINEK F. et al. Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate[J]. IEEE Transaction on Information Theory,1974,IT-20(2):284-287.

[7] ERFANIANJ A, PASUPATHY S,GULAK G. Reduced Complexity Symbol Dectectors with Parallel Structures for ISI Channels[J].IEEE Transactions on Communications,1994,42:1661-1671.

[8] 祁棟生,陳自力,白勇博.Turbo碼編碼器的FPGA設計與實現[J]鄭州輕工業學院學報,2010,25(6):115-117.

[9] 曾健平,張亦馳,李玉國.Turbo 編碼的并行設計與優化[J].宇航計測技術,2010,30(2):75-78.

[10] 栗安定,陳寅健,胡豪,等.并行Turbo編碼器[P].中國:ZL200910201488,2011.

[11] 成亞勇,閆冬,孫曉鋒,等. 基于GPU實現的調頻遙測解調方法[J].無線電工程,2016,46(4):35-38.

[12] 張舒，楮艷利，趙開勇，等. GPU 高性能運算之CUDA[M].北京:中國水利水電出版社,2009.

[13] ZHANC, ARSLAN T,ERDOGAN A T,et al. An Efficient Decoder Scheme for Double Binary Circular Turbo Codes[C]∥IEEE International Conference on Accoustics,Speech and Signal Processing,2006:IV-229-IV-232.

[14] 張喜明,陳旸.基于VPX標準總線的GPGPU平臺的圖像幾何校正[J].無線電工程,2014,44(1):53-55.

[15] 傅丹，馮衛東，于起峰，等．一種攝像機自標定的線性方法[J]．光電工程， 2008，35(1):71-75．

[16] 夏良正．數字圖像處理[M]．南京:東南大學出版社,1999．