基于MapReduce框架的BCH碼并行譯碼研究

陸忠敏， 孫 建， 張家精

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

1 前言

BCH碼［1，2］的譯碼問題一直是研究的熱點，同時也是BCH碼應用中的關鍵問題。經典的BCH譯碼算法一般采用迭代方法計算錯誤多項式的根，如BM迭代算法［3］，迭代算法涉及大量的線性方程組的分解計算。在實踐上一般采用串行譯碼的方式，有著電路設計復雜，譯碼速度慢的特點。

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

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

2．1 譯碼原理

BCH 碼［1，2］是循環(huán)碼的一個非常重要的子集，先 后 由 Hocquenghem、Bose和 Reychaudhuri幾乎同時并獨立提出以他們三人名字的首字母而命名的循環(huán)糾錯碼。由循環(huán)碼的定義可知，GF（q）（q為素數(shù)或素數(shù)的冪）上的［n，k］循環(huán)碼中，存在并且唯一存在有n－k次的首一多項式

（1）BCH碼的結構

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

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

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

2．2 迭代譯碼算法

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

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

則x1，x2，…，xe錯誤位置

有關鍵方程

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

計算得出dj＋1，并以此為基礎進行下一步的迭代。

經過2t次迭代即可求出σ（2t）（x）和w（2t）（x）即為σ（x）和w（x）。

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

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

2．4 MapReduce框架

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

（1）Map過程:接受一個鍵值對（key－value pairs），產生一組中間鍵值對，中間鍵值對由框架傳遞給Reduce過程。

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

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

3 分組并行譯碼算法原理

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

3．1 構造譯碼表

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

（1）求所設計碼的生成多項式

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

（2）由生成多項式計算得到生成矩陣和校驗矩陣，具體有:

這樣即可確定伴隨矩陣與錯誤圖樣之間的關系，經計算可得伴隨矩陣與錯誤圖樣的對應關系。表1中所列出的為BCH（7，4）的伴隨陣與錯誤圖樣對照關系表。其中h＊（x）為h（x）的逆多項式

表1 BCH（7，4）的伴隨陣與錯誤圖樣對照關系

3．2 分組查表譯碼

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

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

具體步驟如下:

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

1），計算伴隨式:

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

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

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

4 譯碼性能對比分析

4．1 譯碼時間對比

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

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

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

4．2 計算量對比分析

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

表3 BCH 譯碼計算量和空間消耗對比表

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

5 結束語

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

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

1 趙曉群．現(xiàn)代編碼理論［M］．武漢:華中科技大學出版社，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＿McK ＿Clouds＿big＿data＿and%20smart%20assets．pdf．2010－08－01．

5 孔 挺，宮 芳，方揚揚．基于查找表的BCH碼快速譯碼算法［J］．哈爾濱商業(yè)大學學報（自然科學版），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 王新梅，肖國鎮(zhèn)．糾錯碼－原理與方法 ［M］．西安:西安電子科技大學出版社，2001．

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