RS系列编译码器的设计与FPGA实现(1)

    RS码是一种有很强纠错能力的多进制BCH码，也是一类典型的代数几何码。它首先由里德(Reed)和索洛蒙(Solomon)应用MS多项式于1960年构造出来的。它不但可以纠正随机差错，而且对突发错误的纠错能力也很强，因此广泛用于差错控制系统中，以提高数据传输的可靠性。如今，RS(255，223)已被美国航天局和欧洲空间站在太空卫星通信的级联码系统中作为标准的外码以采用。

    RS(n，k)码是一种非二进制的BCH码，工程上的RS纠错编码方式为RS(255，223)，该码的基本特性如下：

    ·码类型：系统码，非透明

    ·码字长度：每个RS码字中包含n=2^J-1=255个RS符号=255×8bit；

    ·检验位数：n-k=2t

    ·纠错能力：可纠任一个RS码字中的t=16个RS符号差错；

    ·码最小距离：d_min=2t+1

    ·码的符号：有限域GF（2^J）中的元素，每个RS符号由J=8bit构 成，即GF（2）上的8维行向量；

    ·码字中信息符号数目：k=n-2t=223个；

    ·码字格式：d1d2d3…di…d223 p1p2…pk…p32，其中d_i为第i个数据符号，p_k为第k个校验符号；

    ·域生成多项式：有限域GF(2⁸)在其特征域GF(2)上的生成多项式为：

F（X）=X⁸+X⁴+X³+X²+1

    其中F（X）为域生成多项式，X为多项式变量；

    · 码生成多项式：g(x)=(x+a)(x+a²)...(x+a³²)

    式中，g(x) 是码生成多项式；

    aⁱ是GF(a⁸)中一个元素。

    应用Matlab中的符号乘法，得到RS（255，223）生成多项式中的32项乘法系数。结合域生成多项式 生成的监督矩阵表[a⁰，a¹，a²……a²⁵⁴]，通过查表得到32项码生成多项式的系数[a¹⁸，a²⁵¹，a²¹⁵……a¹¹]，即

    因此，RS（255，223）编码器示意图如图1所示。

图1  RS（255，223）编码器示意图

    由于GF(2⁸)上的RS码是2^m进制码，GF(2⁸)中的每个元素均可表示成它的自然基底1， 的线性组合：

    以乘 a⁸为例可以表示为：

    a⁸(a₀+a₁a+a²a₂+a₃a³+a₄a⁴+a₅a⁵+a₆a⁶+a₇a⁷)=a₇(a⁵+a²+a)+a₆(a⁴+a+1)+a₅(a⁷+a²+a+1)+a₄(a⁷+a⁶+a³+a²+1)+a₃(a⁷+a⁶+a⁵+a³)+a₂(a⁶+a⁵+a⁴+a²)+a₁(a⁵+a⁴+a³+a)+a₀(a⁴+a³+a²+1)=a⁷(a₅+a₄+a₃)+a⁶(a₄+a₃+a₂)+a⁵(a₇+a₃+a₂+a₁)+a⁴(a₆+a₂+a₁+a₀)+a³(a₄+a₃+a₁+a₀)+a²(a₇+a₅+a₄+a₂+a₀)+a¹(a₇+a₆+a₅+a₁)+a⁰(a₆+a₅+a₄+a₀)

    综上推导，我们可以把所有的乘法器变化为加法器，即模二和的形式。如图2所示。

    用输入数据信息实例进行了仿真。即输入信息为0，1，2…222，时，32个校验位输出为102，212，116，164，159，61，229，39，17，244，245，67，253，18，156，217，115，73，31，174，27，140，69，159，104，219，254，187，173，169，10，116。

图2   的加法器表示

    译码器的实现主要包括下面四个流程：伴随式计算、关键方程求解、钱搜索计算错误位置、福尼算法计算错误值。原理参考文献[1]-[4]。

    定义伴随多项式为

其系数为

    其中，n=255，i=1~32，α为x⁸+x⁴+x³+x²+1=0所生成的GF(2⁸)中的本原元。

    定义错误位置多项式为

错位值多项式为

结合上一步求出的伴随多项式，根据RS码的性质，我们有

称它为关键方程。

上式可写成

    由Euclid算法[3]可以知道ω(x)是S(x)与x^2t+1的最大公因子。同时，由简单的证明可知，只要假设U_-1=1，U₀=0，V_-1=0，V₀=1，即可利用每一次求到的q_j(x)，来求出当前时刻的U_j(x)和V_j(x)，因此可以得到Euclid译码算法流程图如图3所示。当求出σ(x)和ω(x)后，利用它们可以求出错误值，从而利用钱搜索，可找出错误位置，求出错误图样，从而实现译码。

    在上一步关键方程中求得σ(x)后，接下来的问题是从工程观点看，如何简单地求出它的根即错误位置。1964年钱闻天提出了一个求σ(x)根的使用方法，解决了这个问题。

    解σ(x)的根，就是确定R(x)中哪几位产生了错误。设R(x)=r_n-1x^n-1+r_n-2x^n-2+…+r₁x+r₀，为了要检验第k位r_n-k是否错误，相当于译码器要确定α^n-k是否是错误位置数，这等于检验α^-(n-k)是否是σ(x)的根。若α^-(n-k)是σ(x)的根，则

    这样依此对每一个r_n-k(k=1，2，…，n)进行检验，就求得了σ(x)的根，这个过程称为钱搜索。

 

图3  Euclid译码算法流程

    RS译码的最后一步就是求错误值Y_i。设实际产生的错误个数γ≤t，则

由

可知：

所以

由于恒等式左边最高次数为2γ，故上式成为

求σ(x)的导数形式

另x=x_i^-1，则上式成为

所以

所以错误值

注意上式可写成