陸忠敏， 孫 建， 張家精

（1．安徽城市管理職業(yè)學(xué)院基礎(chǔ)部，合肥 230011；2．安徽省電力科學(xué)研究院，合肥 230609，3．安徽建筑大學(xué)數(shù)理學(xué)院 合肥 230601）

1 前言

BCH碼［1，2］的譯碼問題一直是研究的熱點(diǎn)，同時(shí)也是BCH碼應(yīng)用中的關(guān)鍵問題。經(jīng)典的BCH譯碼算法一般采用迭代方法計(jì)算錯(cuò)誤多項(xiàng)式的根，如BM迭代算法［3］，迭代算法涉及大量的線性方程組的分解計(jì)算。在實(shí)踐上一般采用串行譯碼的方式，有著電路設(shè)計(jì)復(fù)雜，譯碼速度慢的特點(diǎn)。

在大數(shù)據(jù)［4］環(huán)境下，由于數(shù)據(jù)量巨大，數(shù)據(jù)的串行、迭代譯碼的方式顯然無法滿足應(yīng)用的要求。本文提出了一種基于分布式并行框架（MapRe－duce）［5］的BCH 碼查找表譯碼算法［6］、設(shè)計(jì)了該算法的譯碼方案并進(jìn)行了對(duì)比分析。

2 BCH碼譯碼算法與分布式框架

2．1 譯碼原理

BCH 碼［1，2］是循環(huán)碼的一個(gè)非常重要的子集，先 后 由 Hocquenghem、Bose和 Reychaudhuri幾乎同時(shí)并獨(dú)立提出以他們?nèi)嗣值氖鬃帜付难h(huán)糾錯(cuò)碼。由循環(huán)碼的定義可知，GF（q）（q為素?cái)?shù)或素?cái)?shù)的冪）上的［n，k］循環(huán)碼中，存在并且唯一存在有n－k次的首一多項(xiàng)式

（1）BCH碼的結(jié)構(gòu)

令α是擴(kuò)域GF（2m）中的本原元素，應(yīng)將糾t個(gè)差錯(cuò)的BCH碼的生成多項(xiàng)式選取連續(xù)的2t個(gè)α，α2，…，α2t都是它的根，即它們也是每個(gè)碼字的根。按上述定義得到的碼叫做本原BCH碼。對(duì)于任何正整數(shù)m和t，存在一個(gè)下列參數(shù)的二元BCH碼:碼長(zhǎng):n＝2m－1；一致校驗(yàn)位數(shù)目:n－k≤mt；最小距離:dmin≥2t＋1。

（2）一般迭代譯碼算法［7］

若接收序列總長(zhǎng)度（L）大于預(yù)先設(shè)定的譯碼長(zhǎng)度，則一般將接收序列按譯碼長(zhǎng)度n分成若干組，譯碼算法一般分為下面幾個(gè)步驟 ① 獲取接收序列的第i（0＜i≤［L／n］）組；② 由該接收序列計(jì)算出伴隨式；③ 由伴隨式計(jì)算差錯(cuò)定位多項(xiàng)式的系數(shù)；④ 求差錯(cuò)定位多項(xiàng)式的根，找出錯(cuò)誤位置；⑤ 進(jìn)行糾錯(cuò)；⑥ 重復(fù)以上步驟直至完成整個(gè)接收序列的譯碼。如何由伴隨式計(jì)算差錯(cuò)定位多項(xiàng)式的系數(shù)是BCH譯碼中最為復(fù)雜、關(guān)鍵的一步，不同的實(shí)現(xiàn)方法導(dǎo)致了不同的算法。

2．2 迭代譯碼算法

在BCH碼的代數(shù)譯碼算法中，譯碼的復(fù)雜度和譯碼的速度往往取決于求σ（x）的根。Massey于1969年提出一種較為簡(jiǎn)單的算法求解錯(cuò)誤位置多項(xiàng)式。在BM算法［3］中，將求解錯(cuò)誤位置多項(xiàng)式的問題轉(zhuǎn)化為解線性方程組的問題。

設(shè)S為伴隨式，S＝ （S1，S2，…，S2t），其中Sk＝R（βk），

則x1，x2，…，xe錯(cuò)誤位置

有關(guān)鍵方程

根據(jù)關(guān)鍵方程，通過修正逐步求出修正項(xiàng)dj，最終得出σ（2t）（x）。具體迭代步驟如下:

計(jì)算得出dj＋1，并以此為基礎(chǔ)進(jìn)行下一步的迭代。

經(jīng)過2t次迭代即可求出σ（2t）（x）和w（2t）（x）即為σ（x）和w（x）。

2．3 分組查找表譯碼［6］

BCH是循環(huán)碼的一個(gè)重要子類，同時(shí)也是線性分組碼的一種，因此線性分組碼的查譯碼表［5］的譯碼方式同樣適合用BCH碼。分組查找表譯碼算法［6］基本步驟與BCH碼一般譯碼算法基本相同，僅針對(duì)計(jì)算復(fù)雜的第二步進(jìn)行優(yōu)化，采用查譯碼表的方式進(jìn)行譯碼。因此分組查找表譯碼算法主要包括:（1）構(gòu)造伴隨式與錯(cuò)誤圖樣對(duì)應(yīng)關(guān)系的查找譯碼表；（2）計(jì)算所接收序列中一個(gè)分組的伴隨式；（3）通過分組查找表找到對(duì)應(yīng)的錯(cuò)誤圖樣，進(jìn)行譯碼。其中構(gòu)造譯碼表為譯碼之前一次性構(gòu)造并且一旦確定BCH碼的碼字多項(xiàng)式后譯碼表也唯一確定。

2．4 MapReduce框架

MapReduce是一個(gè)用于大數(shù)據(jù)集并行處理的編程模型，主要由Map（過濾排序）和一個(gè)Reduce過程（執(zhí)行總結(jié)操作）組成。

（1）Map過程:接受一個(gè)鍵值對(duì)（key－value pairs），產(chǎn)生一組中間鍵值對(duì)，中間鍵值對(duì)由框架傳遞給Reduce過程。

（2）Reduce過程:接受一個(gè)主鍵及該主鍵對(duì)應(yīng)的值組將這些值組進(jìn)行運(yùn)算，從而合并為一組規(guī)模更小的值。

作業(yè)執(zhí)行過程可以簡(jiǎn)化為:

3 分組并行譯碼算法原理

查表譯碼需要構(gòu)建出所有錯(cuò)誤圖樣與其所對(duì)應(yīng)伴隨式組成的譯碼查找表，將伴隨式值的大小作為查找表的索引值。由所接收到的碼字可以計(jì)算出伴隨式，以該伴隨式的值作為索引值查找譯碼表，經(jīng)過有限次的查找可以很快確定錯(cuò)誤圖樣從而找到錯(cuò)誤位置完成接收碼字的糾錯(cuò)。與迭代譯碼算法相比，查表譯碼方式有著邏輯實(shí)現(xiàn)簡(jiǎn)單、譯碼速度快、易于分組并行的優(yōu)點(diǎn)，但要占有較大的存儲(chǔ)空間，適合于軟件譯碼的方式。

3．1 構(gòu)造譯碼表

生成BCH碼的譯碼表的步驟如下:

（1）求所設(shè)計(jì)碼的生成多項(xiàng)式

如［15，7，5］BCH 碼的生成多項(xiàng)式，碼以α，α3為根，α3的最小多項(xiàng)式為

（2）由生成多項(xiàng)式計(jì)算得到生成矩陣和校驗(yàn)矩陣，具體有:

這樣即可確定伴隨矩陣與錯(cuò)誤圖樣之間的關(guān)系，經(jīng)計(jì)算可得伴隨矩陣與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系。表1中所列出的為BCH（7，4）的伴隨陣與錯(cuò)誤圖樣對(duì)照關(guān)系表。其中h＊（x）為h（x）的逆多項(xiàng)式

表1 BCH（7，4）的伴隨陣與錯(cuò)誤圖樣對(duì)照關(guān)系

3．2 分組查表譯碼

在大數(shù)據(jù)環(huán)境中，數(shù)據(jù)的讀取速率往往很高，甚至達(dá)到G比特每秒，在大速率的情況下，設(shè)計(jì)復(fù)雜，譯碼緩慢的迭代譯碼算法很難處理。根據(jù)MapReduce的分片（分組）處理“分而治之”的思想將大數(shù)據(jù)量的信息按照一定長(zhǎng)度進(jìn)行分組，再利用并行框架［5］進(jìn)行譯碼是解決的途徑之一，采用 MapReduce框架的并行譯碼［8］算法如圖1所示。

圖1 分布式并行BCH碼譯碼原理圖

具體步驟如下:

（2）針對(duì)每一接收片段Ri（x）（i＝d－1，d－2，…

1），計(jì)算伴隨式:

（3）若Si（x）＝0（i＝d－1，d－2，…1）則該片段接收序列無誤；

（5）將片段碼字的估值還原為＾C（x）。

信息串R（x）譯碼完畢。

4 譯碼性能對(duì)比分析

4．1 譯碼時(shí)間對(duì)比

為了驗(yàn)證本文提出的改進(jìn)算法在譯碼速度上的優(yōu)勢(shì)，采用了MapReduce環(huán)境下對(duì)40萬字節(jié)BCH（31，21，5）編碼的接收序列進(jìn)行譯碼仿真。單機(jī)仿真計(jì)算機(jī)的性能為:Intel?CoreTM雙核CPU、2．10GHz主頻、2G內(nèi)存、200G磁盤空間。分布式環(huán)境采用4臺(tái)Intel?CoreTM雙核CPU、2．10GHz主頻、2G內(nèi)存、200G磁盤空間的計(jì)算機(jī)，其中一臺(tái)計(jì)算機(jī)作為NameNode和Job－Tracker，其余3臺(tái)負(fù)責(zé)具體計(jì)算任務(wù)。

表2 分布式并行查表譯碼與傳統(tǒng)迭代譯碼時(shí)間對(duì)比

從表2可以看出，采用本文提出的分布式并行查表譯碼算法在譯碼時(shí)間上較傳統(tǒng)的迭代算法有著較大地提升，譯碼速率比傳統(tǒng)迭代譯碼算法快66．11%。因此本文提出的分布式并行查表譯碼算法在譯碼速度上具有較大的優(yōu)勢(shì)。

4．2 計(jì)算量對(duì)比分析

由于查表譯碼算法譯碼前已生成譯碼表，在譯碼時(shí)無需再計(jì)算位置多項(xiàng)式的根，僅需計(jì)算伴隨式查表即可獲得錯(cuò)誤圖樣，從而操作數(shù)大大降低。表3給出了迭代譯碼和查表譯碼的操作數(shù)（左移、右移等位操作）和所占空間資源對(duì)比分析。

表3 BCH 譯碼計(jì)算量和空間消耗對(duì)比表

從表3可以看出，迭代算法操作數(shù)隨著分組長(zhǎng)度t增加操作數(shù)顯著增加，而查表算法操作數(shù)當(dāng)t的增大時(shí)影響較小。傳統(tǒng)迭代譯碼算法所占的存儲(chǔ)空間較少，分布式查表譯碼算法也隨著碼字的增加需要占用更多的存儲(chǔ)空間。

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

綜上所述，BCH碼查表并行譯碼算法充分利用了分組碼和BCH碼的特點(diǎn)，顯著提高了譯碼的速度、降低了譯碼計(jì)算量。相比較于傳統(tǒng)的迭代譯碼算法，并行查表法有著更好的性能，更適合于大數(shù)據(jù)環(huán)境下的編譯碼。

由于查表譯碼算法需要存儲(chǔ)伴隨式和錯(cuò)誤圖樣的關(guān)系組成的查找表，隨著碼字的增長(zhǎng)，譯碼表將迅速增大從而占用大量的存儲(chǔ)空間，在較長(zhǎng)碼字的情況下，此種算法將不再適用。但考慮到分組碼的信息位分組長(zhǎng)度t可以根據(jù)需要調(diào)整大小，因此可以選擇適當(dāng)?shù)拈L(zhǎng)度t來避免過長(zhǎng)的碼字，從而避免占用過大的存儲(chǔ)空間。

1 趙曉群．現(xiàn)代編碼理論［M］．武漢:華中科技大學(xué)出版社，2008．

2 萬哲先．代數(shù)和編碼［M］．北京:高等教育出版社，2007．

3 Berlekamp，Elwyn R，F(xiàn)actoring Polynomials Over Finite Fields［J］．Bell System Technical Journal，1967，46:1853－1859．

4 Jacques Bughin， Michael Chui，James Manyika，Clouds，big data，and smart assets［EB／OL］．http:／／www．itglobal－services．de／files／100810＿M(jìn)cK ＿Clouds＿big＿data＿and%20smart%20assets．pdf．2010－08－01．

5 孔 挺，宮 芳，方揚(yáng)揚(yáng)．基于查找表的BCH碼快速譯碼算法［J］．哈爾濱商業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，27（6）:819－823．

6 Jeffrey Dean，Sanjay Ghemawat．MapReduce:Simplifed Data Processing on Large Clusters［EB／OL］．http:／／research．google．com／archive／map－reduce－osdi04．pdf．2004:1－5．

7 王新梅，肖國(guó)鎮(zhèn)．糾錯(cuò)碼－原理與方法 ［M］．西安:西安電子科技大學(xué)出版社，2001．

8 冷芳玲，鮑玉斌．基于MapReduce的數(shù)據(jù)聚集運(yùn)算算法［J］．中國(guó)科技論文在線，2011，7（7）:469－481．