通用快速RS編譯碼的設計

摘 要：提出一種針對通用伽羅華域的快速RS編譯碼技術。該編譯碼技術利用了時域編碼、頻域譯碼，適用于通用的RS碼本原生成表達式。分析表明，該技術與傳統的時域編譯碼相比，復雜度明顯降低，但仍具有相同的編譯碼能力，同時b=1本原生成表達式的RS編譯碼整系統的復雜度最低，仿真結果與理論分析一致。



關鍵詞：RS碼； 時域編碼； 頻域譯碼; 伽羅華域

中圖分類號：TN911-34

文獻標識碼：A

文章編號：1004-373X(2012)01-0071-04

Design of fast RS encoding and decoding



WANG Lei1，2，3， FU Yao-xian1，2， WANG Ying-guan1，2

(1. Shanghai Institute of Microsystem and Information Technology， Chinese Academy of Science， Shanghai 200050，China；

2. Key Lab of Wireless Sensor Network and Communications， Chinese Academy of Science， Shanghai 201800， China; 

3. Graduate University of Chinese Academy of Sciences， Beijing 100049， China)



Abstract： A universal scheme of fast RS encoding and decoding is proposed. This scheme with time domain encoding and frequency domain decoding is suitable for all RS generator polynomials. Simulation suggests that the scheme has lower complexity and the same encoding and decoding compared with conventional encoding and decoding in time domain. The total RS encoding and decoding complexity is minimized choosing generator polynomial with b=1.



Keywords： RS code; encoding in time domain; decoding in frequency domain; Galois field





收稿日期：2011-09-16

基金項目：國家重大專項(2009ZX03006-006-01;2010ZX03006-003-02)資助課題

0 引 言

現代通信系統中，前向糾錯碼技術是實現可靠通信的基本方法。非二進制循環糾錯碼RS(Reed-Solomon)碼是一種性能優良的線性分組碼，在同樣的編碼冗余度下，RS碼有最強的糾錯能力。由于可以糾正隨機錯誤和突發錯誤，常作為級聯編碼的外碼，以糾正其他編譯碼造成的突發錯誤。RS碼已廣泛應用于數字通信各領域及數據存儲系統中，主要應用于實時性較高的移動通信系統、深空通信、數字衛星電視、磁記錄系統等方面。

RS碼的編譯碼存在時域和頻域兩種算法[1-2]。其中，時域編譯碼算法出現的比較早，由于比較成熟而被廣泛采用；頻域編譯碼算法雖然出現較晚[3]，但是可以借助快速傅里葉變換(Fast Fourier Transform，FFT)及快速傅里葉反變換(Inverse Fast Fourier Transform，IFFT)提高編譯碼速度，具有較大的發展潛力。

目前有關時域編碼、頻域譯碼[4-8]的研究，僅針對b=1時的RS碼本原生成表達式的編譯碼進行，而沒有針對更一般的本原生成表達式。本文提出一種針對通用伽羅華域的快速RS編譯碼技術，適用于所有RS碼本原生成表達式，與傳統的時域編譯碼相比，復雜度明顯降低，但仍具有相同的編譯碼能力。

1 伽羅華域中的算術運算

RS碼的編譯碼均在伽羅華域(Galois Field，GF)上進行，在此先研究伽羅華域中的算術運算。若運算為雙目運算符，則兩個操作數為A，B；若運算為單目運算符，則操作數為A，結果記為C。其中：

A=∑7i=0aiαi

B=∑7i=0biαi

C=∑7i=0ciαi

1.1 伽羅華域的加減運算

伽羅華域上加減運算等同，結果為對應位進行異或運算。即：

ci=ai⊕bi， i=0，1，2，…，7

1.2 伽羅華域的乘法運算

考慮伽羅華域GF(28)中，每個符號由m =8位數字來表示。其本原多項式為：

p(x)=x8+x4+x3+x2+1

(1)

則有C=(A×B)mod p(x)，不難推出：

di=(a0bi)⊕(a1bi－1)⊕…⊕(ai－1b1)⊕(aib0)

c7=d7⊕d11⊕d12⊕d13

c6=d6⊕d10⊕d11⊕d12

c5=d5⊕d9⊕d10⊕d11

c4=d4⊕d8⊕d9⊕d10⊕d14

c3=d3⊕d8⊕d9⊕d11⊕d12

c2=d2⊕d8⊕d10⊕d12⊕d13

c1=d1⊕d9⊕d13⊕d14

c0=d0⊕d8⊕d12⊕d13⊕d14



1.3 伽羅華域的求逆運算

除法運算可以分為兩部分，先對除數求逆，再與被除數相乘。因此除法運算的重點在于求逆。

由費馬小定理及級數展開可得：

B－1=B#8226;B－2=B2m－2=∑m－1i=1B2i

可見求逆的基本操作為冪次運算與乘法運算，而冪次結果的各個系數可由上節中乘法運算推出。考慮伽羅華域GF(28)，其原理框圖[9]如圖1所示。

圖1 伽羅華域求逆原理框圖

2 RS碼的編碼方法

對于RS編碼，時域和頻域算法都比較簡單，時域編碼需要做一次多項式求模運算，頻域編碼需要做一次IFFT運算。不同的是，用時域編碼編出的碼字是系統碼，可用于截短編碼，而頻域編碼編出的碼字是非系統碼，不能用于截短編碼。因此，對于截短編碼，只能用時域編碼的方法。

2.1 時域編碼原理

令α為GF(2m)域中的本原元素，則長為n=2m－1，且糾正t=(n－k)/2個錯誤的RS(n，k)碼，其本原RS碼的生成多項式是：

g(x)=∏b+2t－1i=b(x－αi)=∑2ti=0gixi

(2)

式中：gi為GF(2m)域中的元素；b為任意整數。

記待編碼的信息多項式：

m(x)=mk－1xk－1+mk－2xk－2+…+m1x+m0

編碼后的信息多項式為：

c(x)=cn－1xn－1+cn－2xn－2+…+c1x+c0

則RS碼可以用式(3)進行編碼：

c(x)=m(x)x2t+［m(x)x2t］mod g(x)

(3)

上式可以由伽羅華域加法器、乘法器及2t級的移位寄存器來實現。典型的RS編碼器結構如圖2所示。

圖2 典型的RS編碼器結構

將g(x)中的各個常系數gi轉換成自然基，即可求得伽羅華域乘法器系數，可以簡化掉中間結果為0的結構，且當b=(k+1)/2時，生成多項式的系數具有對稱性，即gi=g2t－i，且g0=g2t=1，可以減少近1/2的伽羅華域乘法器的設計。

2.2 時域編碼工作原理

RS編碼電路的工作原理如下：

(1) 2t級移位寄存器初始狀態全部清零，開關1閉合，開關2處于下面的位置。按照從高次位到低次位的順序將m(x)的系數輸入，一部分直接輸出，另一部分進入移位寄存器。

(2) k次移位后，m(x)已全部輸出，開關1斷開，開關2移到上面位置。此時移位寄存器內保留的數據即為校驗位，共n - k位，逐位輸出后，與最初的k位信息組成長為n的碼字。

(3) 對于縮短碼，可使用相同的步驟。

3 RS碼的譯碼方法

對于RS譯碼，時域譯碼算法要比頻域譯碼算法復雜得多。在時域譯碼算法中，解出錯位多項式σ(x)后，還需要求出σ(x)的根，以找到錯誤位置，再根據錯誤位置求出錯誤樣式；而在頻域譯碼算法中，解出錯誤多項式后，直接利用簡單的線性遞歸擴展方法就可求得錯誤圖樣的頻譜，計算步驟比時域譯碼算法少。借助于FFT算法，相比時域譯碼，頻域譯碼更為簡單快捷。

3.1 頻域譯碼原理

RS碼的頻域譯碼涉及伽羅華域的FFT/IFFT，定義如下：

設x={xi|i=n－1，n－2，…，0}為GF(2m)域內的一個矢量，其伽羅華域的FFT為GF(2m)域上的另一個矢量X={Xj|j=n－1，n－2，…，0}，則有：

Xj=∑n－1i=0xiαij， j=0，1，2，…，n－1

(4)

xi=∑n－1j=0Xjα－ij， i=0，1，2，…，n－1

(5)

式(4)為伽羅華域的FFT公式，式(5)為伽羅華域的IFFT公式。

設編碼端輸出的碼字為:

c(x)=∑n－1i=0cixi

由式(2)知，g(αi)=0，i=b，b+1，…，b+2t－1，則：

c(αj)=∑n－1i=0ciαij=Cj=0，

j=b，b+1，…，b+2t－1

(6)

即RS碼FFT的第b至第b + 2t -1譜分量為0。

若信道中有s個可糾正的錯誤(0 ≤ s ≤ t)，令錯誤圖樣為e(x)=ei0xi0+ei1xi1+…+eisxis，接收到的碼字為r(x)，其FFT滿足：Rj=Cj+Ej。由式(6)定義接收碼字的伴隨式為：

Sj=Ej=Rj， j=b，b+1，…，b+2t－1

(7)

若伴隨式全為零，則接收碼字無錯誤。否則，引入錯誤位置多項式：

σ(x)=∏sj=1(1－xαij)=∑sj=0σjxj

(8)

記Λ={0，0，…，0，σs，σs－1，…，σ0}，其IFFT為：

λi=∑sj=0σjα－ij， i=0，1，2，…，n－1

(9)

由式(8)，式(9)得：

λi=∏sj=1(1－αij－i)

若第i位未出錯，則ei=0；若第i位出錯，則 λi=0。因此λ#8226;e=0，則其FFT有ΛE=0。易得:

Ej=∑si=1Ej－iσi

Ej=σ－1s∑si=1Ej+iσs－i

σ(x)的各系數σj(j=1，2，…，s)可由BM(Berlekamp-Massey)[10] 算法或RiBM(Reformed inverse-free Berlekamp-Messey)算法[11]求出，則:

Ej=σ－1s∑si=1Ej+iσs－i， j=1，2，…，b－1

Rj，j=b，b+1，…，b+2t－1

∑si=1Ej－iσi，j=b+2t，b+2t+1，…，n

(10)

正確的碼字{dn－1，dn－2，…，d0}為R-E的IFFT，dn－1位至dn－k位為信息位，dn－k－1位至d0位為校驗位。

當b = 1時，生成多項式g(x)的系數gi將不具有對稱性，在時域編碼設計時會略增加工作量。而在頻域譯碼時，由式(10)可知，由于不再需要伽羅華域求逆，以及低位頻域錯誤圖樣遞歸的模塊，可以有效降低頻域譯碼的復雜度。

3.2 頻域譯碼工作原理

RS頻域譯碼的流程圖如圖3所示。

圖3 RS頻域譯碼流程圖

將接收碼元序列進行FFT，得到伴隨式s(x)，由BM算法求解關鍵方程，解得σ(x)，經遞歸求得頻域錯誤圖樣Ej，糾除頻域錯誤后，再進行IFFT，其輸出即為譯碼碼元序列[2]。

頻域錯誤圖樣遞歸原理框圖如圖4，圖5所示。其中對σs求逆可由圖1所示的原理框圖得到。

圖4 高位頻域錯誤圖樣遞歸原理框圖

圖5 低位頻域錯誤圖樣遞歸原理框圖

4 仿真及仿真分析

在Xilinx ISE 12.2及ModelSim SE 6.5下，完成對RS(255，239)時域編碼的實現與驗證。當輸入為1~239連續遞增的239個自然數時，其16位校驗位輸出如圖6所示，與理論編碼結果輸出完全相同。

圖6 RS時域編碼仿真的校驗位

采用Matlab 7.11進行RS(255，239)頻域譯碼的仿真。每個信噪比仿真10 000幀，每一幀內系數b取1~239的隨機數，采用QPSK調制，同時仿真Matlab提供的時域譯碼算法的誤碼率性能，并與RS(255，239)在QPSK調制下的誤碼率性能的理論值進行對比。仿真結果如圖7所示，復雜度較低的頻域譯碼與復雜度較高的時域譯碼的誤碼率性能完全相同。

圖7 頻域譯碼、傳統時域譯碼及理論值的誤碼率曲線

5 結 論

本文提出一種針對通用伽羅華域的快速RS編譯碼技術，適用于所有RS碼本原生成表達式。仿真結果表明，b=1本原生成表達式時RS編譯碼整系統的復雜度最低，資源占用最小。

參 考 文 獻

［1］王新梅，肖國鎮.糾錯碼:原理與方法［M］.西安:西安電子科技大學出版社，2001.



［2］LIN S， COSTELLO D J JR. Error control coding [M]. Second Edition. New Jersey: Prentice Hall， 2004.



［3］ BLAHUT R E.差錯控制碼的理論與實踐［M］.徐秉錚，譯.廣州:華南理工大學出版社，1998.



［4］韓作生，袁東風.RS碼頻域編譯碼的計算機模擬［J］.通信學報，1994，15(6):104-112.



［5］侯正信，胡浩.RS碼的時域編碼/頻域譯碼技術［J］.電視技術，2002(1):32-34.



［6］董昌孝.RS碼的時域編碼頻域譯碼技術［J］.西安航空技術高等專科學校學報，2008，26(5):48-49.



［7］余亞芳，張勇，王化深.RS碼的譯碼算法及軟件實現［J］.現代電子技術，2003，26(22):99-104.



［8］張定云.一種減少RS截短碼譯碼延時的優化設計［J］.現代電子技術，2010，33(23):33-38.



［9］沈曉強.有限域乘除法研究與實現［D］.長沙：國防科學技術大學，2006.



［10］MASSEY J L. Shift-register synthesis and BCH decoding [J]. IEEE Transactions on Information Theory， 1969， 15(1):122-127.



［11］陳曦，謝軍，邱琪.基于RiBM算法的RS譯碼器設計和實現［J］.光通信技術，2008，32(11):48-50.



作者簡介：

汪 磊 男，1987年出生，山東聊城人，碩士。主要研究方向為無線傳感器網絡。

付耀先 女，1978年出生，重慶人，博士。主要研究方向為無線傳感器網絡。

王營冠 男，1970年出生，陜西富平人，研究員。主要研究方向為無線傳感器網絡。