RS(255，223)编译码器的实现

摘  要 本文介绍了RS(255，223)编译码器的实现，其中RS编码器的设计中，利用有限域常数乘法器的特性对编码电路进行优化，将所有的乘法器转化为加法器。RS译码器采用欧几里德算法，同时考虑到并行结构所需的硬件资源较多，译码器均采用串行结构实现。这些技术的采用大大提高了RS编译码器的效率，在保证速度的同时最大限度地减少了资源占用。     关键词 RS码；卷积码；欧几里德算法；FPGA   1  引言     RS码是一种有很强纠错能力的多进制BCH码，也是一类典型的代数几何码。它首先由里德(Reed)和索洛蒙(Solomon)应用MS多项式于1960年构造出来的。它不但可以纠正随机差错，而且对突发错误的纠错能力也很强，因此广泛用于差错控制系统中，以提高数据传输的可靠性。如今，RS(255，223)已被美国航天局和欧洲空间站在太空卫星通信的级联码系统中作为标准的外码以采用。 2  RS(255，223)编码器设计 2.1  RS(255，223)编码原理     RS(n，k)码是一种非二进制的BCH码，工程上的RS纠错编码方式为RS(255，223)，该码的基本特性如下：     ·码类型：系统码，非透明     ·码字长度：每个RS码字中包含n=2J-1=255个RS符号=255×8bit；     ·检验位数：n-k=2t     ·纠错能力：可纠任一个RS码字中的t=16个RS符号差错；     ·码最小距离：dmin=2t+1     ·码的符号：有限域GF（2J）中的元素，每个RS符号由J=8bit构 成，即GF（2）上的8维行向量；     ·码字中信息符号数目：k=n-2t=223个；     ·码字格式：d1d2d3…di…d223 p1p2…pk…p32，其中di为第i个数据符号，pk为第k个校验符号；     ·域生成多项式：有限域GF(28)在其特征域GF(2)上的生成多项式为： F（X）=X8+X4+X3+X2+1     其中F（X）为域生成多项式，X为多项式变量；     · 码生成多项式：g(x)=(x+a)(x+a2)...(x+a32)     式中，g(x) 是码生成多项式；     ai是GF(a8)中一个元素。 2.2  RS(255，223)编码的FPGA实现     应用Matlab中的符号乘法，得到RS（255，223）生成多项式中的32项乘法系数。结合域生成多项式 生成的监督矩阵表[a0，a1，a2……a254]，通过查表得到32项码生成多项式的系数[a18，a251，a215……a11]，即     因此，RS（255，223）编码器示意图如图1所示。 图1  RS（255，223）编码器示意图     由于GF(28)上的RS码是2m进制码，GF(28)中的每个元素均可表示成它的自然基底1， 的线性组合：     以乘 a8为例可以表示为：     a8(a0+a1a+a2a2+a3a3+a4a4+a5a5+a6a6+a7a7)=a7(a5+a2+a)+a6(a4+a+1)+a5(a7+a2+a+1)+a4(a7+a6+a3+a2+1)+a3(a7+a6+a5+a3)+a2(a6+a5+a4+a2)+a1(a5+a4+a3+a)+a0(a4+a3+a2+1)=a7(a5+a4+a3)+a6(a4+a3+a2)+a5(a7+a3+a2+a1)+a4(a6+a2+a1+a0)+a3(a4+a3+a1+a0)+a2(a7+a5+a4+a2+a0)+a1(a7+a6+a5+a1)+a0(a6+a5+a4+a0)     综上推导，我们可以把所有的乘法器变化为加法器，即模二和的形式。如图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   的加法器表示 3  RS(255，223)译码器设计     译码器的实现主要包括下面四个流程：伴随式计算、关键方程求解、钱搜索计算错误位置、福尼算法计算错误值。原理参考 HYPERLINK "http://book.studa.com/" 文献[1]-[4]。 3.1 伴随式计算     定义伴随多项式为 其系数为     其中，n=255，i=1~32，α为x8+x4+x3+x2+1=0所生成的GF(28)中的本原元。 3.2  关键方程求解     定义错误位置多项式为 错位值多项式为 结合上一步求出的伴随多项式，根据RS码的性质，我们有 称它为关键方程。 上式可写成     由Euclid算法[3]可以知道ω(x)是S(x)与x2t+1的最大公因子。同时，由简单的证明可知，只要假设U-1=1，U0=0，V-1=0，V0=1，即可利用每一次求到的qj(x)，来求出当前时刻的Uj(x)和Vj(x)，因此可以得到Euclid译码算法流程图如图3所示。当求出σ(x)和ω(x)后，利用它们可以求出错误值，从而利用钱搜索，可找出错误位置，求出错误图样，从而实现译码。 3.3 钱搜索计算错误位置     在上一步关键方程中求得σ(x)后，接下来的问题是从工程观点看，如何简单地求出它的根即错误位置。1964年钱闻天提出了一个求σ(x)根的使用方法，解决了这个问题。     解σ(x)的根，就是确定R(x)中哪几位产生了错误。设R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0，为了要检验第k位rn-k是否错误，相当于译码器要确定αn-k是否是错误位置数，这等于检验α-(n-k)是否是σ(x)的根。若α-(n-k)是σ(x)的根，则     这样依此对每一个rn-k(k=1，2，…，n)进行检验，就求得了σ(x)的根，这个过程称为钱搜索。   图3  Euclid译码算法流程 3.4  福尼算法计算错误值     RS译码的最后一步就是求错误值Yi。设实际产生的错误个数γ≤t，则 由 可知： 所以 由于恒等式左边最高次数为2γ，故上式成为 求σ(x)的导数形式 另x=xi-1，则上式成为   所以 令x= xi-1，则上式成为 所以错误值 注意上式可写成    其中xi是错误位置对应的本原形式，σ(x)和ω(x)分别是错误位置多项式和错误值多项式，σ’(x)为σ(x)的一次导数。     其中 ，σ1，σ3……为错误位置多项式奇数项系数 3.5  RS(255，223)译码的FPGA实现 3.5.1伴随式计算的实现     伴随式计算电路结构如图4所示。 图4中R0~R254为译码输入。为了节省硬件资源，同时考虑到每个伴随式系数在计算上相互没有关系，故采用串行计算得到Si。具体做法为：首先将译码输入R0~R254写入到一个片内RAM，每计算一个伴随式，将其从RAM中串行读出，并进行迭代运算。 图4  伴随式计算电路 3.5.2关键方程求解的实现     在欧几里德(Euclid)算法[3]中，用到了多项式的除法和乘法运算，为了节省资源，必须利用一个有效的刷新办法对该除法器和乘法器进行实时刷新，使得每进行一次迭代后，除法器和乘法器中的内容及时更新，我们把[3]中的算法结构上做如下的改进：在做多项式除法和乘法之前，先进行数据的并串转换。这样只要一个多项式除法器和一个乘法器就可完成该算法，在保证运算速度的同时也最大限度地节省了硬件资源。在下面的部分给出这两个模块的实现。     1) 多项式除法器     假设多项式A(x)除以B(x)的商为q(x)，余数为r(x)。若某次迭代时A(x)的阶数为m，B(x)的阶数为n，m≥n。由多项式除法原理可知，q(x)=Bn-1Amxm-n，每次同m-n一起输出；而r(x)=A(x)-B(x)q(x)是一个降次的过程，每降一次都需要将A(x)用r(x)刷新，直到它的阶数小于B(x)的阶数时，表明此次除法运算结束，用B(x)和r(x)分别对A(x)和B(x)进行同步刷新，继续进行下一次除法运算。当r(x)的阶数小于或等于t时，算法中的除法迭代运算结束。在实现中有两点需要注意：第一点是我们用两组固定长度的寄存器来存放A(x)和B(x)的系数，除了第一次初始化的时候需要给出它们的阶数外，以后每次它们的阶数都是由r(x)或上一次的B(x)的阶数直接赋值，而由于每次r(x)是串行得到的，其阶数能通过判断每次的值是否为零累加得到；第二点是每次在对存放B(x)系数的寄存器进行更新时，应将B(x)的最高位和A(x)的最高位对齐，从而方便r(x)的求解，同时在用B(x)对存放A(x)系数的寄存器进行更新时应注意该操作带来的影响。整个多项式除法器的实现如图5所示。     2) 多项式乘法器     多项式乘法器：将多项式除法运算的结果q和deg(q)实时输入多项式乘法器，A(x)赋初值1，B(x)赋初值0，每完成一次除法运算，多项式除法器模块给此模块一个控制信号，A(x)与B(x)互换。迭代运算时代门关闭，输出无效；当除法迭代结束时，多项式除法器模块的控制信号控制门打开，输出有效。多项式乘法器如图6所示。 3.5.3钱搜索计算错误位置的实现 在工程上，钱搜索过程可用图7所示的电路实现，它的工作过程如下：     (1) t个寄存器寄存σ1，σ2，…，σt，当错误个数γ分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析