RS译码的软件实现与优化

摘要：RS码的编/译仿真程序或软件在算法验证和硬件设计调试中起非常重要的作用。为了弥补目前专门介绍RS 码译码的资料很少，而相应的程序实现性能效率不高，提出了对BM迭代算法运用多线程技术和数据并发方法对其进行性能的优化。通过在不同的多核处理环境中进行了验证，说明了方法的可行性和有效性。

关键词：RS译码; BM迭代; 多线程; 数据并发; 对偶基

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)01-0161-04

RS Decoding Software Implementation and Optimization

ZHI Jia, YAO Guo-qing

(China University of Geosciences in Beijing, Beijing 100083, China)

Abstract: RS code simulation program or software(encoding/decoding) plays a very important role in algorithm validation and hardware design debugging method. To make up for the situation that the RS decoding devoted information is little, and the corresponding program to achieve performance efficiency is not high. Using the BM iterative algorithm in multi-threading technology and data concurrency optimize the methods to own a high performance. By different multi-core processing environment was verified that the method is feasible and effective.

Key words: RS decoding; BM iteration; multithreading; data concurrency; dual basis

1 伽罗华域

伽罗华域(即有限域) ：对于有限个符号，若符号的数目是一素数的幂，可以定义有加法和乘法，则构成符号域为有限域；若它是2m个符号的域．则称之为伽罗华域GF(2m)。

例如，两个符号0、1，定义有模2加法和模2乘法，即 0+0=0，0+1=1，1+1=0； 0•0=0，0•1=1，1•1＝1，则称之为二元域，也是伽罗华域。

从两个符号0和1及一个m次多项式p(x)开始，并引入一个新符号α，设p(α)=0。若适当地选择p(x)。就可得到α的各次幂，一直到2m-2次幂都不相同，并且αm-1=1。这样一来，构成GF(2m)的所有元素。域中每个非零元素还可以用上面元素的和来表示。

例如，m = 4和p(x)=x4+x+1，则得到GF(24)的所有元素，详见表1。

2 RS码

RS码是一种非二进制分组码。首先说明一下一般的二进制线性分组码的概念。一个（n,k）码字的含义是这样的：前k比特位是信息码，后（n-k）位是监督码，监督码是信息码通过线性方程组获得，该线性方程组的各系数由监督/生成矩阵确定，如图1所示。

这种线性二进制分组码的译码过程是这样进行的：接收码字与监督矩阵相乘获得的结果称为伴随式，如果伴随式的图样（即其二进制结果序列）为全0，说明接收码字无误；若计算结果不为全0，则说明码字有误，将伴随式与误码图样相对照，从而找出错误码元，完成对该码字的纠检错，其过程见图2。

3 RS码译码原理及算法

相对于编码而言，RS码的译码问题一直是纠错理论研究中最感兴趣的问题之一。RS码的译码通常可以分为三种方法：PGZ算法( Peterson-Gorenstein-Zierler) 、BM (Berlekamp-Massey)迭代算法和Euclidean (欧几里德)算法。这三种方法的译码步骤相似,均分为以下四步：

1）由接收到的R (x)计算出伴随式S=(S1,S2,…,S2t) ；

2）由伴随式S求错误位置多项式σ(x)，错误位置多项式的根提供错误的位置。（选择不同的算法。）；

3）用钱（Chien）搜索解出σ(x)的根，得到错误位置数，确定出错位置；

4）由错误位置数求得错误图样E(x)，由R(x)- E(x)得到最可能发送的码字C(x)，完成译码。

决定译码器的复杂性和速度的主要因素在于如何求σ(x)，如何简化和加快这一步是RS码译码的关键。求σ(x)有许多方法,常用的有PGZ直接算法（通常对于t≤ 4），BM迭代译码算法（也称BM算法,通常对于t≥ 4）和Euclidean算法。PGZ算法要解线性方程组，它的计算量和系数矩阵阶数的三次方成正比。因此当码长和纠错能力较大时，计算量很大，要求译码器的运算速度很高。RS(255, 223)码的码长较大，t = 16即t > 10，所以PGZ算法不适用于此码的译码。BM迭代译码算法极大的加快了求σ(x)的速度，利用迭代的方式求错误位置多项式，易于用计算机完成，因此从工程上解决了RS码的译码问题。Euclidean算法是另一种主要的RS码译码算法，其实质是通过求解两个多项式最大公因式，获得错误位置多项式及错值多项式。但是Euclidean算法需要保存大量的中间量，占用大量存储空间，而通信资源相对较少。因此综合而言，RS( 255, 223)码采用BM迭代译码算法最合适。

3.1 计算伴随式

设GF(q)上的[n,k] RS码以αm0, αm0+1,…, αm0+d-2为根，则它的生成多项式

（1）

α∈GF(qm)为n级域元素。发送的码字C(x)=q(x)g(x)，接收的n重为R(x)=C(x)+E(x)。假设错误图样：

E(x)=en-1xn-1+en-2xn-2+…+e1x+e0

若信道产生t个错误，则：

（2）

式中，Yi∈GF(q)， xli称为错误位置数，说明错误发生在R(x)中第n-li（xn-1的系数算第一位），错误值是Yi。如果R(x)中有t个错误，则E(x)共有t项Yixli，i=1,2,…,t，伴随式的值为：

（3）

3.2 迭代生成错误位置多项式及错误值多项式

要由伴随式的值求出错误位置，首先假设一个“错误位置多项式”：

（4）

方程σ(x)=0以所有的错误位置为根，求出多项式系数σ1, σ2,…, σt就得到错误位置多项式。

若xk-1为错误位置，则σ(xk-1)=1+σ1xk-1+σ2xk-2+…+σtxk-t，两边乘以xktYkxkj(j = 1,2,…,2t),得Ykxki+1+σ1Ykxkj+t-1+…+σtYkxkj=0, k=1,2,…,t

对k求和并写成矩阵形式为：

（5）

该方程组有解的充分必要条件是系数矩阵为满秩。实际上，只有当错误个数为t时系数矩阵为满秩；当错误个数r

设： 其中S0=1。

令ω(x)=S(x)σ(x)=1+ω1x+ω2x2+…，将S(x)和σ(x)代入其中并展开，可得关键方程：

S(x)σ(x) ω(x)(mod x2t+1) （6）

迭代译码算法，就是用迭代的方法求得满足方程（6）的σ(x)。为了进行迭代，首先选择1组或2组合理的初值如σ(0)(x)和ω(0)(x)，然后开始计算，依次由σ(i)(x)和ω(i)(x)求得σ(i+1)(x)和ω(i+1)(x)，直到第2t次迭代求得满足式（6）的以x2t+1为模的σ(2t)(x)和ω(2t)(x)时为止。在迭代过程中，定义第j+1步与第j步的差值为dj，设σi(j)(x)为第j次迭代后求得的σ(x)中xi项的系数，则：

（7）

其中：?鄣•σ(j)(x)为σ(j)(x)的次数，可表示为D(j)。且：

σ(j+1)(x)= σ(j)(x)-djdi-1xj-iσ(i)(x)

ω(j+1)(x)= ω(j)(x)-djdi-1xj-iω(i)(x) （8）

这里i是j前面的某一行，并满足i-D(i)最大，且di≠0，而

D(j+1)=max(D(j),j-i+D(i))（9）

迭代译码算法每一步求出σ(j)(x)和ω(j)(x)后，需计算dj。由式（8）可以看出，若dj=0，则σ(j+1)(x)= σ(j)(x)，ω(j+1)(x)= ω(j)(x)。

ω(x)是求σ(x)过程中得到的辅助多项式，在求解错误值时将用到，故称ω(x)为错误值多项式。

3.3 钱搜索

求出错误位置多项式σ(x)后，解方程σ(x)=0就得到错误位置。当方程次数较高时，直接求解比较复杂。一般用钱氏搜索方法求解，具体如下：

设R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0，为了检验第i位rn-i是否错误，就是要确定αn-i是否是错误位置数，即要确定α-(n-i)是否是σ(x)=0的根。

若σ(α-(n-i))=0，则rn-i有错；若不为0，则rn-i无错。

这样依次对rn-i(i=1,2,…,n)进行检验，就可求得σ(x)=0的根。

要注意的是，当差错个数大于t时，迭代译码算法也可能得到次数为t或小于t的错误位置多项式，当这种情况出现时，要及时返回状态，并不进行纠错译码，因为此时纠错会出现更多的错误。

3.4 错误值的计算

RS码译码的最后一步就是求错误值Yi。这一步对二进制码来说可省略，但对多进制码来说是必需的。我们实现的译码都是针对m0=1时的情况，若m0≠1，则应稍作修正。

由式（3）与式（6）经推导可得：

（10）

其中的xi-1为σ(xi-1)=0，即错误位置数。

3.5 小结

RS码的译码步骤和一般线性码的译码步骤基本相同：首先由接收码多项式R(x)计算出伴随多项式S(x)，再有伴随式计算出错误多项式E(x)，最后由R(x)- E(x)实现纠错。对于RS码，由于错误不仅要定位到符号，还要定位到符号中的比特位置，即错误符号的错误值，所以计算E(x)包括三个内容：有伴随式分量求出错误位置多项式σ(x)，解多项式σ(x)确定错误位置数x1,x2, …,xt，再确定错误值Y1,Y2, …,Yt。当t值较大时，用BM迭代算法求出σ(x)，然后用Chien搜索法求解σ(x)的根，确定错误位置数。

4 RS码译码软件实现

基于CCSDS标准开发的RS译码过程，对于一般的译码过程有较大部分的修改实现，以下介绍设计中的软件实现译码的过程与要点。

4.1 数据预处理

设计中所要处理的数据是RS（255，223）码，每个字符都是GF(28)中的元素，所以一个字符为8bit。数据的交织深度为2，每512个字节为一帧，包括两个数据和同步帧（前四个字节）。即在数据帧中，同步帧是不参加纠错过程的。这就意味着每组纠错数据少一个字节，即一个字符（称为虚拟填充字符）。可将虚拟填充字符设为0。最后将数据保存在数组data[2][255]中。

4.2 计算伴随式值

经过上面的步骤后可知dat中保存的ri,i=0,1,…,254 。

ri为：R(x)=r254x254+r253x253+…+r1x+r0

而此时CCSDS要求的码生成多项式为并非之前介绍的公式，所以经计算可得：

sj=r0(α212+j-1)254+r1(α212+j-1)253+…+r254其中α112*11=α212

将编写代码完成sj的计算，并保存在数组Sj[33]中，Sj[0]不做使用。如果经计算，数组中值全为零，则没有错误，可以返回。但此时数据有一个虚拟填充字符，所以必然要进行纠错过程。

4.3 计算错误位置多项式

迭代开始前要先假设合理的初值：

σ(-1)(x)=1 , ω(-1)(x)=1; σ(0)(x)=1,ω(0)(x)=1; d0=s1 然后按照公式编程迭代。

其中dj的计算按照公式进行。在迭代过程中，公式的编程做了以下优化：

1）在当选出合适的σ(i)(x)时，同时将其除以了di。

2）在将xj-i与σ(i)(x)相乘再与σ(j)(x)异或的过程看做是将σ(i)(x)移位异或，错位相加的过程。

通过这两点优化，大大的简化了迭代过程，节约了运算资源，提高了运算效率。在求得σ(x)后并计算其导数保存，用于计算错误值。同时迭代错误值多项式ω(x)过程，则通过用公式S(x) σ(x)= ω(x)编程计算。

4.4 确定错误位置和错误数

使用钱搜索方法确定错误位置，将域中元素逐个代入错误位置多项式。当σ(x)=0时，说明此代表的位置有错存在。在记录错误位置时，同时记录错误个数，但由于参与纠错过程的数据有一个虚拟填充字符，所以错误数目应将其忽略。因为其并不是在信道过程中的错误。

由于数据的码生成多项式是特殊的，所以在这个过程中也也要做适当的修改来求出正确的错位位置。经过推导和大量数据证明，如果xi位置有错，则σ(α254-11*(254-i)(mod255))=0，其中11为生成多项式原根的本原元素次数。

在完成以上两样工作后，要判断错误数目是否大于σ(x)的次数。当错误数>σ(x)的次数时，则有不可纠的错误；当错误数

4.5 错误值的计算

先将错误位置代入σ'(x)和ω(x)计算出结果，因为CCSDS的特殊性，在计算错误值时需要进行部分的修改，最后得出若错误位置为xi，则：

其中112为生成多项式根的第一个次数。

4.6 纠错数据并输出

此过程只要将接收多项式数组与错误值多项式数组进行模2加（异或）即可完成纠错，然后再将修改后的数据返回给数据帧。

5 RS码译码的优化

由于数据是以512字节为一帧，每一帧的前四个字节为同步字节，前一帧与后一帧没有丝毫联系，每次译码过程以帧为单位进行。所以这是典型的数据并发实例，可按某种方法分配每个线程所要处理的固定数据帧。这里设计将模8方式来确定线程要处理的数据帧。

例如：线程0处理数据1、9、17… ；线程1处理数据2、10、18…，依次类推。

线程同步与互斥

设计运用VC++中的临界区变量来实现线程的同步与互斥。

CRITICAL_SECTION cs_rd; 读文件的互斥量

CRITICAL_SECTION cs_w;写文件的互斥量

CRITICAL_SECTION cs_log;写日志文件的互斥量

6 结束语

最后通过对功能和性能的测试，说明了BM迭代算法适用于计算机对RS译码的实现，多线程技术在提高程序效率上有很大效果。在一定范围内和程序代码的优化基础上，多线程可优化算法的执行效率，更快的完成程序任务，性能得到了提高。

此过程分别对单线程和多线程的代码进行用例测试测试程序的运行效率。用例采用107MB 的嫦娥一号的科学数据，具有实际的代表效果。

由于一般的PC机是使用的IDE硬盘，在使用多线程时，由于硬盘的瓶颈会使代码的效率下降，所以以下的测试是在SCSI硬盘的服务器上得到的结论。结果如图4。

参考文献：

[1] 王新梅,肖国镇.纠错码――原理与方法[M].西安：西安电子科技大学出版社,2001.

[2] 马秀莲,李廷芳,吕淑香.数字通信差错控制技术[M].北京：中国铁道出版社,1991

[3] 余亚芳,张勇,王化深.RS码的译码算法及软件实现[J].现代电子技术,2003(22):99-101.

[4] 刘悦,刘明业,尚振宏.RS(255,223)码的编译码软件实现[J].计算机应用与软件,2006,23(11):46-47.

[5] Recommendation for Space Data System Standards Telemetry Channel Coding[M].CCSDS 101.0-B-5 Blue Book,2001:3-7.

[6] 谭维炽,顾莹琦.空间数据系统[M].北京：中国科学技术出版社,2004.

[7] SWEENEY P. 差错控制编码[M].俞越,张丹,译.北京：清华大学出版社,2004.

[8] 周贤伟.差错控制编码与安全[M].北京：国防工业出版社,2006.