基于GPU的RS碼并行譯碼算法研究

趙正偉，鄧劍鋒

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.西安衛星測控中心，陜西 西安 710043)

?

基于GPU的RS碼并行譯碼算法研究

趙正偉1，鄧劍鋒2

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.西安衛星測控中心，陜西 西安 710043)

摘要針對RS碼硬件譯碼器中常用的BMA譯碼算法并行性較差，導致譯碼延遲較大和譯碼速率較低的問題，研究了RS碼的高速并行譯碼算法及其軟件實現方式，設計和實現了一種基于GPU的RS碼并行譯碼算法cuPGZ。實驗結果表明，對CCSDS建議的RS(255,223)碼，在128 bits錯誤的情況下，cuPGZ可以達到590 Mbps的最大譯碼速率以及0.5ms的最小譯碼延遲，與BMA算法的GPU實現相比，譯碼速率提高1倍，譯碼延遲降低為1/60。實際工程應用表明，cuPGZ能夠滿足實際測控數傳的信道譯碼要求。

關鍵詞RS碼；譯碼；PGZ；并行；GPU

0引言

RS碼[1]是由Reed和Solomon在1960年發現的一種多進制循環糾錯碼，在糾正隨機符號錯誤和隨機突發錯誤方面非常有效，廣泛應用于數字通信和存儲系統以增強系統的可靠性，應用領域涵蓋從深空通信、無線通信到數字視頻廣播等多方面。隨著通信速率的逐步提高和虛擬無線電技術在測控通信領域的逐漸普及，研究RS碼高速譯碼器的軟件實現具有重要的實用價值。

本文設計和實現了一種基于GPU的RS碼高速并行譯碼方案，充分利用GPU強大的并行計算能力，獲得較大的譯碼速率和較低的譯碼延遲，能夠滿足高速測控數傳的譯碼要求。

1RS碼及其譯碼算法

1.1RS碼

RS碼是一種非二進制BCH碼，其碼系數從伽羅華域GF(2m)中取值。對于能糾正td個錯誤的RS碼，碼的零點是2td個α的連續次冪。由于在GF(2m)上最小多項式的形式為φi=(x-αi)，0≤i≤2m-1，并且生成多項式的因式是連續的，有

(1)

式中，b為一個整數，通常b=0或b=1。

由于m個信息比特分為一組，構成GF(2m)中

的一個符號，因此，該RS碼不僅能夠糾正最多td個隨機錯誤，還可以糾正任何長度不超過m(td-1)+1比特的單個突發錯誤[2-3]。

1.2RS碼通用譯碼算法

RS碼譯碼的主要思想是用元素β∈GF(2m)給碼字中的位置編號(也就是關聯多項式系數的階次)，應用GF(2m)算術，通過求解方程組來找到錯誤位置。方程組是從錯誤多項式e(x)和碼的零點αj,b≤j≤b+2td-1中得到的，如下所示：

令r(x)=v(x)+e(x)表示與接收碼字關聯的多項式，其中錯誤多項式定義為：

e(x)=ej1xj1+ej2xj2+…+ejvxjv。

(2)

v(x)=r(x)+e(x)。

(3)

具體譯碼過程包括5個步驟：

① 通過計算接收多項式在碼零點處的值得到校正子：

(4)

② 找出錯誤位置多項式σ(x)的系數：

定義錯誤位置多項式為：

(5)

它的根等于錯誤位置的倒數。于是，在σ(x)的系數和矯正子之間有下面的關系[4]：

(6)

③ 找出σ(x)的根的倒數，即錯誤位置，αj1,…,αjv。

④ 找出錯誤值ej,…,ejv。

⑤ 根據找到的錯誤位置和錯誤值糾正接收字。

1.3常用RS時域譯碼算法比較

求解式(6)給出的關鍵方程是RS譯碼過程中計算量最集中的步驟。求解關鍵方程的一般方法包括：Berlekamp-Massey算法、Euclidean算法和PCZ算法。

1.3.1BMA算法

從所需的伽羅華域中運算量的角度看，BMA[2]算法是求解關鍵方程的高效計算方法。文獻[5-7]表明，在RS譯碼器的軟件仿真和FPGA實現中，BMA應用比較廣泛。

1.3.2EA算法

EA[8]算法具有規則的結構，在RS譯碼器的硬件實現中獲得較多應用。

1.3.3PGZ算法

PGZ[9]算法又稱為直接求解法，即將式(6)作為線性方程組求解，然后直接找出σ(x)的系數。PGZ算法以矩陣運算的方式求解關鍵方程和計算錯誤值，矩陣運算在GPU上能獲得非常好的并行加速比，因此我們選擇PGZ算法來實現RS譯碼。

2基于GPU的RS碼PGZ譯碼算法

2.1CUDA

Compute Unified Device Architecture(CUDA)[10]是NVIDIA公司于2007年發布的基于GPU的編程框架，不需要借助圖形API就可以直接用C語言來操作GPU，與之前的GPGPU相比，極大地簡化了GPU的編程開發，因此，CUDA一經推出就受到了工業界和學術界的廣泛關注，被大量應用于各領域的并行計算中。

CUDA是單指令多線程(Single Instruction Multiple Thread，SIMT)模型[11-12]，GPU內部的多個硬件核可以并行執行同一條指令，核之間共享存儲器，具有較高的通信效率。

2.2cuPGZ譯碼算法設計與實現

本文設計和實現的cuPGZ算法的核心思想是利用GPU強大的并行計算能力來加速RS譯碼計算。算法主要包括2個層次的并行：幀間并行和幀內并行。幀間并行指的是同時譯多個幀，幀內并行是指修改經典的PGZ算法實現，通過并行來加速譯碼過程。

由于幀間并行是通過在啟動kernel函數時配置線程塊的數目來實現的，這里不再贅述。這里主要介紹幀內并行的設計與實現，具體步驟如下：

① 計算校正子。在這個階段，可以用2td個CUDA核，根據式(4)，每個核計算一個校正子。

② 計算錯誤位置多項式σ(x)的系數。根據式(6)，(σ1,σ2,…,σv)T可以通過式(7)的線性方程組求解：

(7)

矩陣相乘時采用td個線程同時處理，每個線程計算一個元素。

③ 找出錯誤位置αj1,…,αjv，即σ(x)的根的倒數。這里采用Chein搜索法來尋找σ(x)的根，這是逐個檢驗的方法。GF(2m)中所有非零元素β按照序列1,α1，α2，…生成，然后逐個檢驗是否滿足σ(β-1=α-jl)=0。

對于CCSDS建議的RS(255,223)或RS(255,239)[13]，所有的運算都是在伽羅華域GF(28)上進行的。因為GF(28)上一共有256個元素，σ(x)的根必然在1,α1,α2,…,α255這256個元素之中，所以直接使用256個核，每個核檢驗GF(28)中的一個元素是否為σ(x)的根。

在計算錯誤位置向量(ej1,ej2,…,ejv)T時，需要從伽羅華域256個元素中找到td個根，采用規約操作，避免采用循環查找導致譯碼時間增加。

④ 找出錯誤值ej,…,ejv。通常采用Forney算法來計算錯誤值，對于較小的td值，該算法可以直接求出錯誤值。對于1≤l≤v，錯誤值ejl通過線性方程組與校正子Si聯系起來。令βl=αjl表示錯誤計數器，1≤l≤v。那么，

(8)

式中，1≤i≤2td。

由已知項βl(b+i-1)構成的v×v子矩陣是范德蒙矩陣。已知所有的v個錯誤位置jl，任何具有形式(8)的含有v個方程的方程組都可以用于尋找錯誤值。特別的，選擇前v個校正子：

(9)

(10)

接下來計算矩陣的逆以及矩陣相乘，具體計算方法同步驟②。

⑤ 糾正接收字。根據幀的長度選擇使用的CUDA線程數，對RS(255,223)或RS(255,239)，使用256個核，每個核根據式(3)糾正一個碼字，得到最終的譯碼結果v(x)。

2.3優化

2.3.1常量數據的存儲

伽羅華域GF(2m)上的對數表、反對數表以及對偶基的2個轉換表是全局常量，譯碼過程需要查找這4個表。由于對這4個表的訪問是隨機的，不滿足合并訪存的條件，所以將這4個表放入共享存儲器中，在不發生沖突的情況下，理論延遲為全局存儲器的1/100[11-12]，能夠降低譯碼延遲。

2.3.2合并訪存

2.3.3無錯處理

由于衛星測控通信的誤碼率一般都不大于10-5，該誤碼率下，對于CCSDS推薦的RS(255,223/239)碼，平均50個幀出現1 bit誤碼，因此在統計意義上，絕大多數幀都是正確的，不需要解碼，直接提出信息即可。

3實驗結果

在GeForce GTX TITAN Black GPU上對cuPGZ算法進行了測試，該GPU一共有2 880個流處理器，核心頻率980MHz。針對CCSDS的RS(255,223)碼，一個幀指的是255×8=2 040 bits，測試結果如表1所示。

RS碼的錯誤碼字越多，其譯碼過程的計算量就越大。對RS(255,223)碼，理論上最多能糾正128bits錯誤，取128 bits錯誤進行實驗，測試了同時譯碼幀數和譯碼性能之間的關系。

表1　128 bits錯誤時譯碼性能

同時譯碼1 024幀，不同錯誤數目下，cuPGZ和cuBMA譯碼算法性能的比較，如表2所示。

表2　同時譯碼1 024幀情況下譯碼性能

表1中的同時譯碼幀數反映的是譯碼過程中幀間并行程度。對cuPGZ算法，隨著同時譯碼幀數的增大，譯碼延遲和速率都增大，當同時譯碼96幀時，能達到0.51ms的譯碼延遲和380 Mbps的譯碼速率。同時譯碼1 024幀時，達到3.63ms的譯碼延遲和573 Mbps的譯碼速率，之后，隨著同時譯碼幀數增加，譯碼延遲大幅增加，而譯碼速率小幅增加。這說明，同時譯碼1 024幀已基本達到該GPU的最大能力，再增加同時譯碼幀數，任務就有明顯的排隊等待延遲。

對BMA譯碼算法的并行實現cuBMA，其最小譯碼延遲27.32ms，這是因為BMA譯碼算法的幀內并行性較低，其譯碼速率的提升的主要原因是幀間并行性。當同時譯碼8 192幀時，達到297 Mbps的最大譯碼速率。

由表2可以看出，cuPGZ算法在譯碼延遲和譯碼速率上比cuBMA算法都有大幅提升。

4結束語

本文設計并實現了一種基于GPU的RS碼并行算法cuPGZ，通過幀間并行和幀內并行，利用GPU強大的并行計算能力加速譯碼處理過程。實驗結果表明，與cuBMA算法相比，cuPGZ算法在譯碼速率和譯碼延遲上均有大幅性能提升，可以滿足實際工程要求。為了更好地發揮軟件譯碼器的優勢，下一步打算在此算法基礎上實現RS碼軟判決譯碼，從而獲得比目前譯碼器中采用的硬判決譯碼算法更高(2～3 dB)的編碼增益。

參考文獻

[1]王新梅，肖國鎮.糾錯碼—原理與方法[M].西安：西安電子科技大學出版社，2006.

[2]BERLEKAMP E R.Key Papers in the Development of Coding Theory[C]∥ IEEE Press,1974:109-120.

[3]MORELOS-ZARAGOZA R H.The Art of Error Correcting Coding (2nd Edition)[M].John Wiley & Sons Ltd,2006:39-84.

[4]朱愛軍，肖永輝.氣象衛星數據傳輸中RS編譯碼器的設計[J].無線電通信技術，2007，33(1)：59-61.

[5]郭勇，何軍.基于RSIP核編譯碼器的設計與FPGA實現[J].無線電通信技術，2015，41(1)：90-93.

[6]LIN S,COSTELLO D J.Error Control Coding:Fundamentals and Applications (2nd Edition)[M].Prentice-Hall,2005:234-269.

[7]郭勇，楊歡.RS(63，45)編譯碼器的設計與FPGA實現[J].無線電通信技術，2011，37(3)：54-57.

[8]SUGIYAMA Y,KASAHARA Y,HIRASAWA S,et al.A Method for Solving Key Equation for Goppa Codes[J].Inf.Control,1975(27):87-99.

[9]PETERSON W W.Encoding and Error Correction Procedures for the Bode-Chaudhuri Codes[J].IRE Trans.Inf.Theory,1960(IT-6):459-470.

[10]張舒，褚艷利.GPU高性能運算之CUDA[M].北京：中國水利水電出版社，2009：2-141.

[11]KIRKD B,HWU Wen-mei W.大規模并行處理器編程實戰[M].趙開勇，汪朝輝，程亦超，譯.北京：清華大學出版社，2013：35-124.

[12]SANDERSJason,KANDROT Edward.GPU高性能編程—CUDA實戰[M].聶雪軍譯.北京：機械工業出版社，2011：42-83,119-170.

[13]CCSDS 131.0-B-2.Recommendation for Space Data System Standards:TM Synchronization and Channel Coding[S].Blue Book,2011.

[14]陶柳.基于GPU的RS解碼算法的高速優化方法研究[D].西安：西安電子科技大學，2014.

[15]郝永杰，蔣建國.改進的RS時域譯碼算法[J].計算機工程，2008，34(14)：104-106.

[16]顧久祥，楊仁忠，韋宏衛.基于GPU的RS譯碼處理技術研究[J].微電子學與計算機，2013，30(4)：119-122.

[17]龔政輝.RS碼高速譯碼實現及其軟判決譯碼算法的研究[D].長沙：國防科技大學，2012.

doi:10.3969/j.issn.1003-3106.2016.07.05

收稿日期：2016-03-11

基金項目：國家部委基金資助項目。

中圖分類號TN919

文獻標志碼A

文章編號1003-3106(2016)07-0017-04

作者簡介

趙正偉男，(1982—)，博士，工程師。主要研究方向：航天測控技術、算法設計與分析。

鄧劍鋒男，(1979—)，工程師。主要研究方向：航天測控。

Research on GPU-Based RS-code Parallel Decoding Algorithm

ZHAO Zheng-wei1,DENG Jian-feng2

(1.The54thResearchInstituteofCECT,ShijiazhuangHeibei050081,China;2.Xi’anSatelliteControlCenter,Xi’anShaanxi710043,China)

AbstractThe low parallel performance of BMA decoding algorithm in RS-code hardware decoder results in high decoding delay and low decoding speed.Aiming at this problem,this paper studies RS-code high-speed parallel decoding algorithm and software implement method,designs and implements a GPU-based RS-code parallel decoding algorithm cuPGZ.The experimental results show that by leveraging the massive cores inside a GPU card,590 Mbps in decoding rate and 0.5ms in decoding delay for RS code (255,223) recommended by CCSDS can be obtained with 128 bits error.Compared to GPU-based BMA,cuPGZ increases one times in decoding rate and decreases 60x in deoding delay.The practical engineering application shows that the cuPGZ can meet the actual engineering requirements in high speed channel decoding.

Key wordsRS-code;decoding;PGZ;parallel;GPU

引用格式：趙正偉,鄧劍鋒.基于GPU的RS碼并行譯碼算法研究[J].無線電工程,2016,46(7):17-20，92.