趙正偉，鄧劍鋒

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

?

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

趙正偉1，鄧劍鋒2

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

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

關(guān)鍵詞RS碼；譯碼；PGZ；并行；GPU

0引言

RS碼[1]是由Reed和Solomon在1960年發(fā)現(xiàn)的一種多進(jìn)制循環(huán)糾錯(cuò)碼，在糾正隨機(jī)符號(hào)錯(cuò)誤和隨機(jī)突發(fā)錯(cuò)誤方面非常有效，廣泛應(yīng)用于數(shù)字通信和存儲(chǔ)系統(tǒng)以增強(qiáng)系統(tǒng)的可靠性，應(yīng)用領(lǐng)域涵蓋從深空通信、無(wú)線通信到數(shù)字視頻廣播等多方面。隨著通信速率的逐步提高和虛擬無(wú)線電技術(shù)在測(cè)控通信領(lǐng)域的逐漸普及，研究RS碼高速譯碼器的軟件實(shí)現(xiàn)具有重要的實(shí)用價(jià)值。

本文設(shè)計(jì)和實(shí)現(xiàn)了一種基于GPU的RS碼高速并行譯碼方案，充分利用GPU強(qiáng)大的并行計(jì)算能力，獲得較大的譯碼速率和較低的譯碼延遲，能夠滿足高速測(cè)控?cái)?shù)傳的譯碼要求。

1RS碼及其譯碼算法

1.1RS碼

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

(1)

式中，b為一個(gè)整數(shù)，通常b=0或b=1。

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

的一個(gè)符號(hào)，因此，該RS碼不僅能夠糾正最多td個(gè)隨機(jī)錯(cuò)誤，還可以糾正任何長(zhǎng)度不超過(guò)m(td-1)+1比特的單個(gè)突發(fā)錯(cuò)誤[2-3]。

1.2RS碼通用譯碼算法

RS碼譯碼的主要思想是用元素β∈GF(2m)給碼字中的位置編號(hào)(也就是關(guān)聯(lián)多項(xiàng)式系數(shù)的階次)，應(yīng)用GF(2m)算術(shù)，通過(guò)求解方程組來(lái)找到錯(cuò)誤位置。方程組是從錯(cuò)誤多項(xiàng)式e(x)和碼的零點(diǎn)αj,b≤j≤b+2td-1中得到的，如下所示：

令r(x)=v(x)+e(x)表示與接收碼字關(guān)聯(lián)的多項(xiàng)式，其中錯(cuò)誤多項(xiàng)式定義為：

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

(2)

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

(3)

具體譯碼過(guò)程包括5個(gè)步驟：

① 通過(guò)計(jì)算接收多項(xiàng)式在碼零點(diǎn)處的值得到校正子：

(4)

② 找出錯(cuò)誤位置多項(xiàng)式σ(x)的系數(shù)：

定義錯(cuò)誤位置多項(xiàng)式為：

(5)

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

(6)

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

④ 找出錯(cuò)誤值ej,…,ejv。

⑤ 根據(jù)找到的錯(cuò)誤位置和錯(cuò)誤值糾正接收字。

1.3常用RS時(shí)域譯碼算法比較

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

1.3.1BMA算法

從所需的伽羅華域中運(yùn)算量的角度看，BMA[2]算法是求解關(guān)鍵方程的高效計(jì)算方法。文獻(xiàn)[5-7]表明，在RS譯碼器的軟件仿真和FPGA實(shí)現(xiàn)中，BMA應(yīng)用比較廣泛。

1.3.2EA算法

EA[8]算法具有規(guī)則的結(jié)構(gòu)，在RS譯碼器的硬件實(shí)現(xiàn)中獲得較多應(yīng)用。

1.3.3PGZ算法

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

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

2.1CUDA

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

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

2.2cuPGZ譯碼算法設(shè)計(jì)與實(shí)現(xiàn)

本文設(shè)計(jì)和實(shí)現(xiàn)的cuPGZ算法的核心思想是利用GPU強(qiáng)大的并行計(jì)算能力來(lái)加速RS譯碼計(jì)算。算法主要包括2個(gè)層次的并行：幀間并行和幀內(nèi)并行。幀間并行指的是同時(shí)譯多個(gè)幀，幀內(nèi)并行是指修改經(jīng)典的PGZ算法實(shí)現(xiàn)，通過(guò)并行來(lái)加速譯碼過(guò)程。

由于幀間并行是通過(guò)在啟動(dòng)kernel函數(shù)時(shí)配置線程塊的數(shù)目來(lái)實(shí)現(xiàn)的，這里不再贅述。這里主要介紹幀內(nèi)并行的設(shè)計(jì)與實(shí)現(xiàn)，具體步驟如下：

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

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

(7)

矩陣相乘時(shí)采用td個(gè)線程同時(shí)處理，每個(gè)線程計(jì)算一個(gè)元素。

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

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

在計(jì)算錯(cuò)誤位置向量(ej1,ej2,…,ejv)T時(shí)，需要從伽羅華域256個(gè)元素中找到td個(gè)根，采用規(guī)約操作，避免采用循環(huán)查找導(dǎo)致譯碼時(shí)間增加。

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

(8)

式中，1≤i≤2td。

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

(9)

(10)

接下來(lái)計(jì)算矩陣的逆以及矩陣相乘，具體計(jì)算方法同步驟②。

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

2.3優(yōu)化

2.3.1常量數(shù)據(jù)的存儲(chǔ)

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

2.3.2合并訪存

2.3.3無(wú)錯(cuò)處理

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

3實(shí)驗(yàn)結(jié)果

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

RS碼的錯(cuò)誤碼字越多，其譯碼過(guò)程的計(jì)算量就越大。對(duì)RS(255,223)碼，理論上最多能糾正128bits錯(cuò)誤，取128 bits錯(cuò)誤進(jìn)行實(shí)驗(yàn)，測(cè)試了同時(shí)譯碼幀數(shù)和譯碼性能之間的關(guān)系。

表1　128 bits錯(cuò)誤時(shí)譯碼性能

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

表2　同時(shí)譯碼1 024幀情況下譯碼性能

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

對(duì)BMA譯碼算法的并行實(shí)現(xiàn)cuBMA，其最小譯碼延遲27.32ms，這是因?yàn)锽MA譯碼算法的幀內(nèi)并行性較低，其譯碼速率的提升的主要原因是幀間并行性。當(dāng)同時(shí)譯碼8 192幀時(shí)，達(dá)到297 Mbps的最大譯碼速率。

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1]王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼—原理與方法[M].西安：西安電子科技大學(xué)出版社，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]朱愛軍，肖永輝.氣象衛(wèi)星數(shù)據(jù)傳輸中RS編譯碼器的設(shè)計(jì)[J].無(wú)線電通信技術(shù)，2007，33(1)：59-61.

[5]郭勇，何軍.基于RSIP核編譯碼器的設(shè)計(jì)與FPGA實(shí)現(xiàn)[J].無(wú)線電通信技術(shù)，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)編譯碼器的設(shè)計(jì)與FPGA實(shí)現(xiàn)[J].無(wú)線電通信技術(shù)，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高性能運(yùn)算之CUDA[M].北京：中國(guó)水利水電出版社，2009：2-141.

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

[12]SANDERSJason,KANDROT Edward.GPU高性能編程—CUDA實(shí)戰(zhàn)[M].聶雪軍譯.北京：機(jī)械工業(yè)出版社，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解碼算法的高速優(yōu)化方法研究[D].西安：西安電子科技大學(xué)，2014.

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

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

[17]龔政輝.RS碼高速譯碼實(shí)現(xiàn)及其軟判決譯碼算法的研究[D].長(zhǎng)沙：國(guó)防科技大學(xué)，2012.

doi:10.3969/j.issn.1003-3106.2016.07.05

收稿日期：2016-03-11

基金項(xiàng)目：國(guó)家部委基金資助項(xiàng)目。

中圖分類號(hào)TN919

文獻(xiàn)標(biāo)志碼A

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

作者簡(jiǎn)介

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

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

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].無(wú)線電工程,2016,46(7):17-20，92.