《武汉工程大学学报》  2009年12期 73-78   出版日期：2009-12-28   ISSN:1674-2869   CN:42-1779/TQ

---

数字电视译码电路中改进型欧几里德算法



0引言1960年由麻省理工学院林肯实验室的Reed和Solomon提出的RS码是非二元BCH码的一个重要子类，它是一类最大距离可分码.在伽罗瓦域（Galois Field, GF） GF(2m)上的RS(n,k)码中，输入信号码长为n，被分成k×m个比特一组，每组包括k个信息符号，每个符号由m个比特组成，它具有同时纠正0.5(n-k)个突发错误和0.5(n-k)个随机错误的能力［12］.RS码是一种重要的分组码，目前被广泛运用于数字电视、移动电视、空间卫星通信中.由于RS码具有诸多优点，它在信息可靠传输中的良好应用前景已经引起世界各国学术界以及IT业界的高度重视.目前在纠错编码领域，RS码已成为继Turbo码之后最受瞩目的又一研究热点［36］.在RS译码的过程中，最重要的是关键方程的求解，通常采用的是BerlekampMassey算法和传统欧几里德算法.BerlekampMassey算法需要很多下标传递的操作，所以该算法的实现过程比较复杂.传统欧几里德算法是对BCH码提出的译码算法，但该算法没有运用到RS码是一种特殊的BCH码这一特性，它需要许多的乘法操作和控制电路［79］.本文提出一种改进型欧几里德算法，通过矩阵的列变换来求解关键方程，可以减少迭代运算的次数，能够减少硬件电路的复杂性，提高RS码的译码速度.1 RS译码的基本流程RS译码的基本流程如图1所示.图1RS译码的基本流程
Fig.1Basic process of RSdecodingRS译码过程的分析思路为：（1）利用接收到的码元多项式r(x)，计算出伴随值Si(i=0,1,…,2t-1)，进而构造出综合多项式S(x).（2）设Λ(x)为错误位置多项式，结合关键方程Ω（x）=Λ(x)S(x)modx2t，利用改进型欧几里德算法，经过迭代求出错误位置多项式Λ(x)和错误值多项式Ω(x).（3）对错误位置多项式Λ(x)，利用钱搜索（Chien Search）算法求出其错误位置.（4）利用Forney公式，求出错误值进而纠错，错误值的表达式为
Yj=Ω(X-1j)-X-1jΛ′(X-1j)(Xj=αj,1≤j≤v, 0≤v≤t)
(1)
式（1）中，t为错误容限，即最多能纠正的错误字节的个数.具体的译码步骤如下：（1）伴随值的计算求解伴随值的电路如图2所示.由于RS码的根所在的伽罗瓦域与码元取值的伽罗瓦域相同，都为GF(2m)，所以根αi对应的极小多项式为一次多项式x-αi.设bi为r(x)除以x-αi的余式，则r(x)=qi(x)(x+αi)+bi，所以Si=r(αi)=bi，从而得到综合多项式为S(x)=S0+S1x+…S2t-1x2t-1(2)定义错误位置多项式为
Λ(x)=(1-αj1x)(1-αj2x)…(1-αjvx)=
Λ0+Λ1x+…+Λvxv(3)其中错误位置多项式的v个根可表示为α-j1，α-j2,…,α-jvΛ(x)各次项的系数Λ0,Λ1,…,Λv与α-j1,α-j1,α-j２,…，α-jv,Λ(x)都是未知的.图2求解伴随值的电路
Fig.2Circuit of solving syndrome values（2）错误位置的计算通过计算错误位置多项式的根即可确定错误位置，这通常用钱搜索算法来实现，钱搜索算法的电路图如图3所示.钱搜索算法是把伽罗瓦域中的元素α0,α1,…,αn-1逐一代入错误位置多项式中，检验是否为其根.可以证明，要判断接收到的码元多项式rn-l是否有错，只要检验Λ1(αl)+…+Λv(αl)v=-1,(v≤t)是否成立即可.图3钱搜索算法的电路图
Fig.3Circuit diagram of Chien search algorithm（3）错误值的计算利用Forney公式，错误值由式（1）确定.第12期张天瑜：数字电视译码电路中改进型欧几里德算法
武汉工程大学学报第31卷
2传统欧几里德算法传统的欧几里德算法中迭代运算的示意图如图4所示.图4传统欧几里德算法中迭代运算的示意图
Fig.4Iterative operation schematic diagram in
traditional Euclidean algorithm传统欧几里德算法是对关键方程Ω(x)=Λ(x)S(x)modx2t进行逐次迭代，直到deg(Ω(i)(x))<t为止，然后求解Ω(x)、Λ(x).由关键方程可知，存在θ(x)，使得Ω(x)=x2tθ(x)+S(x)Λ(x)成立，按下列条件进行初始化：Ω(-1)(x)=x2t,θ(-1)(x)=1, Λ(-1)(x)=0
Ω(0)(x)=S(x), θ(0)(x)=0, Λ(0)(x)=1假定Ω(i-2)(x)、Ω(i-1)已知，Ω(i-2)(x)除以Ω(i-1)的商式为q(i)(x)，余式为Ω(i)(x)，则关键方程的迭代式可表示为Ω（i）(x)=Ω(i-2)(x)+Ω(i-1)(x)q(i)(x)(4)同时Λ(i)按Λ(i)x=Λ(i-2)(x)+Λ(i-1)(x)q(i)(x)进行迭代，直到deg(Ω(i)(x))<t为止，此时求解出的Ω(i)(x)、Λ(i)(x)就是最终要求解的Ω(x)、Λ(x).由于传统欧几里德算法需要计算出Ω(i-2)与Ω(i-1)(x)的商式q(i)(x)，而求商式运算的电路其实现过程特别复杂.为了减少硬件电路的复杂性，提高芯片的译码速度，需要对传统欧几里德算法进行改进.3改进型欧几里德算法由多项式带余除法可知，若被除式的次数小于除式的次数时，根据商式和余式的唯一性可知，此时所得的商式为零，余式就是被除式.所以如果被除式和除式满足上述关系时，商式和余式便可以很容易确定［1012］.不过在传统欧几里德算法中，需要迭代相除的多项式未必满足这一条件.为了利用上述结论，可以将被除式减去除式，然后再与构造出的一个多项式相乘，把它们的乘积作为新的被除式，使得该被除式的次数小于除式的次数，而这里需要构造出的多项式可以根据原来被除式和除式的特征经过若干次迭代来确定.把经过迭代之后所得到的被除式和除式相除，所得到的商式就是构造出的多项式，余式就是最后生成的被除式.在改进型欧几里德算法中，前一过程的迭代方程称为预处理方程，后一过程的迭代方程称为更新方程.为了明确改进型欧几里德算法中的迭代原理，首先引入多项式带余除法，即对任意两个多项式f(x)、g(x)而言，存在唯一的多项式q(x)、r(x)，使得f(x)=g(x)q(x)+r(x)成立，其中deg((r(x))<deg(g(x))，或者r(x)=0. q(x)、r(x)分别称为f(x)除以g(x)的商式和余式.由多项式带余除法可得出这样一个推论：对任意两个多项式f(x)、g(x)而言，存在多项式u(x)、q(x)、r(x)，使得f(x)-u(x)g(x)=g(x)q(x)+r(x)成立，其中deg(r(x))<deg(g(x))，或者r(x)=0，deg(f(x)-u(x)g(x))<deg(g(x))，进而得到u(x)+q(x)、r(x)分别就是f(x)除以g(x)的商式和余式.改进型欧几里德算法的主要思路也是把迭代后错误值多项式的次数作为是否向下迭代的判据，若继续向下迭代，则把错误值多项式的商式用于错误位置多项式的迭代，否则迭代运算结束.改进型欧几里德算法的框架如图5所示.图5改进型欧几里德算法的框架
Fig.5Frame of modified Euclidean algorithm改进型欧几里德算法中迭代运算的硬件结构如图6所示.在图6中虚线的上半部分为错误值处理单元，下半部分为错误位置处理单元.图6改进型欧几里德算法中迭代运算的硬件结构
Fig.6Hardware structure of iterative
operation in modified Euclidean algorithm从上述分析可以看出，传统欧几里德算法在求解商式的过程中需要进行多次的迭代运算，这会导致RS码出现较大的时间延迟，从而影响RS码的译码性能，因此，需要对传统欧几里德算法进行改进.为了减少迭代运算的次数，考虑在求解关键方程的过程中，如何能够较快地计算出Ω(i-2)(x)与Ω(i-1)(x)的商式q(i)(x).为了叙述方便，将Ω(i-2)(x)与Ω(i-1)(x)分别用f(x)与g(x)代替.设
f(x)=a0xn+a1xn-1+…+an-1x+an
g(x)=b0xm+b1xm-1+…+bm-1x+bm
CF=［a0,a1,…,an-1,an］T为f(x)的系数向量.
G=b00…00
b0
bm-10
bmbm-1b00
0bmb0
0bm-1
bmbm-1
00…0bm
为g(x)的系数矩阵，CQ和CR分别为f(x)除以g(x)的商式q(x)和余式r(x)的系数矩阵.
由f（x）=g(x)q(x)+r(x)可知，CF=G(CQ)+CR.构造n-m+2阶可逆矩阵
T=In-m+1-CQ
01由此可得
（GCF）T=（GCF）In-m+1-CQ
01=(GCR) (5)
(-In-m+10)T=(-In-m+10)In-m+1-CQ
01=
(-In-m+1CQ）(6)从式（5）和式（6）中可以看出，(GCF)通过列变换可得(GCR)，同样(-In-m+10)通过列变换可得(GCQ)，即
GCF
-In-m+10列变换GCR
-In-m+1CQ(7)改进型欧几里德算法与传统欧几里德算法的不同之处是，传统欧几里德算法在求解关键方程时，用到的商式是通过多项式相除得到的，而改进型欧几里德算法在求解关键方程时，用到的商式则是通过矩阵的列变换直接得到的，这样就可以减少迭代运算的次数.由于迭代运算不但会造成大的时间延迟，而且还因为里面包含大量的乘法器和除法器，从而造成硬件电路的实现非常困难.因此改进型欧几里德算法能够较少时间延迟，降低硬件电路的复杂性，提高RS码的译码速度.以RS（204,188）码为例，BerlekampMassey算法、传统欧几里德算法和改进型欧几里德算法所需要的硬件资源和译码速度的对比如表1所示.
表13种算法中硬件资源和译码速度的对比
Tab.1Comparison of hardware resources and
decoding speed in three algorithms
算法类型欧几里德
单元的个数乘法器
总数除法器
总数延迟周期
的个数BerlekampMassey算法0244770传统欧几里德算法41632420改进型欧几里德算法4128340由表1可以看出，与BerlekampMassey算法和传统欧几里德算法相比，改进型欧几里德算法能够节省更多的乘法器和除法器，并且可以减少更多延迟周期的个数.由于在伽罗瓦域中的乘法器电路和除法器电路非常复杂，因此改进型欧几里德算法能够降低硬件电路的复杂性，提高RS码的译码速度.4仿真实验与结果分析基于功能强大的MATLAB/Simulink平台，构建一个RS编译码的系统仿真架构，以产生RS编码数据.RS（204,188）编译码的系统仿真架构如图7所示，其中加入误码模块和译码模块是为了验证RS编码的正确性.然后把得到的编码数据加入错误用VCS软件来进行FPGA仿真实验.图7基于MATLAB/Simulink平台的RS编译码的系统仿真架构
Fig.7System simulation framework of RS encoding and decoding based on MATLAB/Simulink platform在利用改进型欧几里德算法来进行译码时，由于RS（204,188）的错误容限为8，即一帧数据最多能纠正8个错误字节.所以分以下3种情况来进行仿真实验.（1）误码个数在错误容限以内假设受到干扰的影响，原来经过编码后的204个字节中有4个错误字节，错误值依次为十六进制数01、01、02、02，利用改进型欧几里德算法得到的仿真图如图8所示.从图8可以看出，经过译码后能够确定错误位置和错误值.误码经过纠错后，原来的4个错误字节得到了纠正，即错误字节的个数在RS（204，188）的错误容限以内时，误码能够得到全部的纠正.（2）误码个数达到错误容限假设受到干扰的影响，原来经过编码后的204个字节中有8个错误字节，错误值依次为十六进制数01、02、03、04、05、06、07、08，利用改进型欧几里德算法得到的仿真图如图9所示.从图9可以看出，经过译码后也能够确定错误位置和错误值.误码经过纠错后，原来的8个错误字节得到了纠正，即RS（204，188）的错误容限是能够达到的.（3）误码个数超过错误容限假设受到干扰的影响，原来经过编码后的204个字节中有9个错误字节，错误值依次为十六进制数01、02、03、04、05、06、07、08、09，利用改进型欧几里德算法得到的仿真图如图10所示.从图10可以看出，经过译码后不能确定错误位置和错误值，原来的9个错误字节没有得到纠正，这是由于误码个数超过了RS（204，188）的错误容限所导致的.
图8误码个数为4时RS译码的仿真图
Fig.8Simulation figure of RS decoding with 4 error code numbers图9误码个数为8时RS译码的仿真图
Fig.9Simulation figure of RS decoding with 8 error code numbers图10误码个数为9时RS译码的仿真图
Fig.10Simulation figure of RS decoding with 9 error code numbers5结语由于BerlekampMassey算法和传统欧几里德算法的硬件电路实现复杂，译码速度较慢，本文通过多项式带余除法的相关推论，提出一种改进型欧几里德算法，该算法的创新之处在于通过矩阵的列变换来求解关键方程，可以减少迭代运算的次数，能够减少硬件电路的复杂性，提高RS码的译码速度.这对于RS码在数字电视中的应用具有一定的实用价值.