江南

(福建信息职业技术学院软件工程系，福建福州350003)

降低RS码算法复杂度的改进KV算法

江南

(福建信息职业技术学院软件工程系，福建福州350003)

提出对Koetter-Vardy(KV)算法进行改进后的重编码算法，利用Reed-Solomon(RS)码的线性性质对重数矩阵进行预处理，改进了插值算法的初始多项式条件，降低插值算法的复杂度，从而降低了KV算法的总体复杂度，带来的复杂度的节省因子是n2(n-k)2．对该算法的软件实现以及仿真结果显示，对高码率的RS码，重编码算法几乎不牺牲译码性能．

KV算法；重编码算法；RS码；复杂度

KV算法是Koetter和Vardy于2003年在Guruswami-Sudan算法的基础上提出来的[1-2]、实现Reed-Solomon(RS)码代数软译码的算法简称.它将信道软信息转化成代数约束条件，然后再利用GS算法的部分步骤，相对于传统的Berlekamp-Massey硬判决算法有着0.28～1.23 dB的增益.假设RS码码长为n，信息长度为k，KV算法复杂度与n成多项式关系，是目前较为有效的RS码软译码算法．经过改进后的Koetter-Vardy算法[3-4]可以达到更好的译码效果，但其复杂度也不能忽视.重编码算法[5]是降低KV算法复杂度的重要算法，能够在几乎不损失性能的情况下将复杂度较高的插值算法的复杂度降低n2(n-k)2因子，有着广泛的潜在应用[6]．

1 Koetter-Vardy算法实现步骤

1.1 重数分配

发送符号从有限域GF(Q)取出，在无记忆信道传输．信道输入输出是随机变量X和Y．观察信道输出的软信息是后验概率：

其中1≤i≤Q,1≤j≤n．这个可靠性矩阵Π就是KV算法的输入．

从可靠性矩阵计算出一个(Q×n)的整数矩阵M,此矩阵称为重数矩阵，矩阵中的元素用mi,j表示.其Q行代表一个符号的Q种不同取值，即αi,1≤i≤Q.n列代表一个码字中n个符号位置，即支持集中的xj，1≤j≤n.文本只考虑Gross提出的简单重数分配方案[7]，即这是目前KV算法研究中较为常用的方案，更好的方案见文献[8]．

1.2 插值

寻找一个二元多项式Q(x,y)，使其满足下面两个条件：①对重数矩阵中每个非零的元素mi,j，Q(x,y)以重数mi,j通过GF(Q)×GF(Q)平面上的点(xj,αi)，或者说(xj,αi)是Q(x,y)的mi,j重零点；②Q(x,y)的(1,k-1)-加权阶数尽可能小．要求加权阶数尽可能小的原因是这样算法的搜索半径最大，纠错能力最强．该步骤是KV算法复杂度的主要来源，本文所要介绍的重编码算法也就是要降低这一步算法的复杂度．不难看出，上述条件①说明二元多项式Q(x,y)需要满足C(M)=个线性约束条件．Koetter提出一种插值算法[9]，其基本步骤如下，假定C=C(M)：

(1)将二元多项式的集合FL[x,y]按照首单项式的y-阶数进行划分，划分成L个子集，初始化L个多项式．这里FL[x,y]指的是所有y阶数低于L的二元多项式．

(2)每次迭代，更新分别来自上面划分出来的L个集合的L个多项式，i次迭代后，L个多项式都能满足第1到i个线性约束，而且在各自的所在的划分集合中，它是最小的．

(3)C次迭代后，L个多项式都能满足C个条件，并且在各自集合中加权阶数最低，在这L个里面再选出最小的那个，作为结果输出．

1.3 因式分解

找出二元多项式Q(x,y)的所有形式为y-f(x)的因式，degf(x)＜k，这些因式是预选的消息多项式，将他们重新编码，就得到预选码字列表．

1.4 ML判决

根据极大似然估计Maximum Likelihood准则，在列表上寻找一个与接收矢量y→最接近的码字，作为译码结果输出．

从以上步骤中可以看出，KV算法的复杂度在很大程度上取决于插值的复杂度，而插值的复杂度则取决于所需要满足的线性条件的总个数．因此，降低插值算法的复杂度就可以降低KV算法的复杂度，从而提高算法效率．

2 重编码算法

重编码算法是降低KV算法复杂度的重要算法，它能够在几乎不损失性能的情况下将插值算法的复杂度降低n2(n-k)2因子．下面先介绍其步骤和原理，再通过算例和仿真结果做进一步了解．

重编码算法利用了RS码的线性性质和广义系统码编码，线性分组码具有线性性质，即如果是码字集合，则这个性质在译码中可以得到应用，比如在硬判决译码中，可以将接收码字加上一个码字，或者可以叫做偏移量，则得到的结果仍然是一个码字，对其进行译码，译码输出再加上(GF(2m)上加减法是一样的)，就可以得到原接收码字的译码输出．这是因为，和的错误图样是一样的．设发送码字为，错误图样为，则：

下面讨论RS码的系统码编码．所谓系统码，就是消息码元“显式”地在编码后码字中出现．常提到的系统码，消息码元都是连续地在码字的前k位或者后k位出现，这叫做严格的系统码．这里要用到的是，k个编码前码元任意地出现在码字中任何k个位置的系统码，可以称之为广义系统码．这种广义系统码编码也可以看作已知一个码字任意k个位置的码元，要求出这个码字．由于RS码是Maximum Distance Separable码，总是可以用一个纠删译码器来求出这个码字．

重编码算法的步骤是：

(1)当译码器接收到软信息时，首先做硬判决，得到硬判决码字r→．

(2)由可靠性矩阵Π求出重数矩阵M，这里采用简单的分配方案，即

(3)根据的M元素值，选择出含有最大重数mmax(即可靠性较高)的k个码元位置，设为集合R，其余码元位置设为集合U(假定可以找到k个这样的位置，找不满k个的情况在后面讨论)．

(4)将r→中k个对应于R中元素位置的码元看作消息码元，对其进行重编码，使编码后码字在这k个位置上与相同，将此码字记为(用了广义系统码编码)．

(6)对重数矩阵插值，这样处理的重数矩阵可以减少插值算法的迭代次数.

(7)对插值多项式进行因式分解，后面的步骤和原KV算法相同．

分析重编码算法的原理：第(5)步中对重数矩阵的偏移类似于上面提到的对接收硬判码字进行偏移．只不过，KV是软判决译码算法，这里要偏移的不仅是一个码字，而是整个重数矩阵．重数矩阵的Q行代表着GF(Q)上的符号，n列代表一个码字中n个码元的位置．矩阵中某列各行代表的符号加上ψ→中对应位置的符号，就得到新的符号，该符号又对应了新的矩阵行号．矩阵中每个元素都要按照这种关系进行变换．例如，对GF(8),(7,5)RS码，M中某个元素：m7,3=3，说明第三个符号位置，对应于α6的重数为3，而ψ→的第三个符号为α1，α1+α6=α5，则m7,3的值移到m6,3，原先m6,3的值也根据此规则进行移动，如果把行号视为正整数集合：NQ:{0,1,…,Q-1}，则可以把这种变换关系视为一个映射NQ↦NQ，这个映射是一一映射，也就是说不会出现某个值被其它值覆盖的情况．

再看这种偏移带来的效果．重数矩阵中最大的重数为mmax，用m来简化表示．重数为m的位置说明了该位置可靠性较高．在重数矩阵对应的k列中，m所在的行对应的符号就是硬判决的符号．对矩阵做偏移时，偏移码字ψ→在这k个可靠符号位置上和硬判决码字是一样的(因为做的是广义系统码编码)．这样，偏移之后，这k个m就被移到了第0行，即对应GF(Q)零元所在的行上．注意到，由于m是最大的重数，把C(M)'/C(M)个m移到零元位置就相当于把相当多的重数移到了y分量为零的插值点上，这个插值点集合可以记为：

对这些插值点的插值，可以直接求得满足这些点的多项式．

对PR中的k个重数均为m点，一个满足这些插值重数要求且次数最低的多项式是p(x)m，其中

同时，不难看出，p(x)m-jyj也是满足各点的重数要求，且次数最低，因此可以将本文第一部分插值算法中的初始条件设为：

这样，这些初始条件已经满足(1-k n) C(M)个重数为m的插值点的要求，后面的插值就不需要再在这些点上进行迭代，这就是重编码算法降低复杂度的原理．

上面假定了重数矩阵中存在k个重数为m的点，如果没有这么多个点该怎么办？在此做个近似，将重数m-1的点(如果还不够的话就采用重数m-2的点)的重数升为m，这样就一样能使用重编码算法了．当然，这样的修改重数可能会带来一些性能上的降低，但是从仿真结果上看，几乎没有什么影响，特别是在高信噪比的情况下，这种修正重数的情况是很少的．

重编码算法能降低插值算法的复杂度，而插值算法的复杂度使用线性约束条件的个数C(M)来表示的．采用Gross的重数分配方案，C(M)的上界是：

这实际上是将每个硬判决符号分配重数C(M)'的GS算法的C(M)．而现在，重数矩阵里去掉了k个m，C(M)'的上界是：

这样可以估计出迭代次数的节省，在高码率情况下是很可观的．后面通过仿真能够看到更直观的数据．

另外，这里还讨论一下“可靠性较高”的含义．选取重编码位置的集合R时，选取k个可靠性较高的位置作为重编码位置．这里的可靠性较高，并不是要求这些位置上的码元实现了无误传输，而只是说在接收机看来，可靠性较高而已．从前文提到的线性分组码性质可以知道，其实随便设定一个偏移码字ψ→，对重数矩阵按照这个偏移码字进行偏移，再进入KV算法译码，译码后再偏移回来，如果原先码字是KV算法可译的，这样偏移一下也一样还是可以译出来的．选择可靠性较高是因为这些位置对应有最大的重数m，能够最大程度地把最大重数移动到y坐标为零的点上，降低插值复杂度．换句话说，如果这些“可靠性高”的码字实际上是有误的，但通过KV算法，仍然能够把它纠正．

3 算例及性能仿真

下面的算例突出了和重编码有关的步骤．考虑一个(7,5)码，消息码字是:

编码后发送码字为:

经过BPSK调制，AWGN信道，SNR=4.0．

从可靠性矩阵能得到硬判决码字：

可以看到，这里有2个错误．

设C(M)，用Gross重数分配方法得到重数矩阵：

可以选择前5个重数均为4的位置作为重编码位置集合R，即

以此为偏移量，对重数矩阵偏移，得到：

同时，可以计算出：

将M'首行5个4全部置为0，同时将(2)作为插值初始条件，进行插值，可以得到多项式QM(x,y)，该多项式较长，这里不再写出．进行因式分解，可以得到2个预选消息码字：

将它们编码后：

这时候，要将它们恢复到偏移前的码字，然后再进行ML判决：

进行ML判决选出c2作为译码输出，译码成功．

图1和图2分别仿真了RS(15,11)和RS(63,55)两种码型，ReEn表示重编码算法，KV表示原KV算法，复杂度因子m一律取4．可以看到，重编码和原KV算法的性能确实是十分接近的，在长码字表现得甚至略好些，这说明，使用重编码算法在性能上是不会受到损失的．

图1 BPSK调制,AWGN信道下,RS(15,11)码重编码算法性能

图2 BPSK调制,AWGN信道下,RS(63,55)码重编码算法性能

仿真表明了复杂度降低的情况．设RS码为(63,55)的RS码，码率为0.87，通过BPSK调制和AWGN信道后用KV算法进行译码，在每个信噪比上仿真100个码字，取插值迭代次数的平均值来估计实际迭代次数，得到表1(C(M)为原KV算法迭代次数，C(M)'为重编码算法迭代次数)．

表1 重编码算法与原KV算法迭代次数对比

从表1看出，实际上，迭代次数的节省比上面用上界得出的结论还要多，基本达到了90%的节省，这是很可观的，当然，要在码率较高的时候才会有如此可观的节省．插值的复杂度和迭代次数C呈二次方关系[10]，注意到重编码以后C已经减少了1-k n因子，因此，重编码带来的复杂度的节省因子是n2(n-k)2．

4 结语

本文讨论了KV算法的一种简单而且有效的改进——重编码算法．对高码率的RS码来说，使用重编码算法可以大大降低复杂度，同时几乎不牺牲性能．KV算法的复杂度虽然是多项式时间的，但和传统的硬判决算法相比还是复杂许多，这成为了它实际应用的一个瓶颈．重编码算法大大降低了插值算法的复杂度，可以想象，在大部分应用KV算法的实际系统中，该算

法将有广泛的应用．最新研究成果表明[11-12]，KV算法除了在信道编码方面的应用以外，还可以用于分布式信源编码，上述论文并未提及重编码算法．未来研究方向可以朝包括研究如何将重编码算法应用到分布式信源编码上的方向发展．

[1]Koetter R,Vardy A.Algebraic soft-decision decoding of Reed-Solomon codes[J].Information Theory,IEEE Transactions on,2003,49(11): 2809-2825.doi:10.1109/TIT.2003.819332.

[2]丁溯泉,杨知行,潘长勇.RS码软判决译码算法研究的最新进展[J].电子科学技术评论,2005(2):37-41.

[3]Jiang J,Narayanan K R.Algebraic soft-decision decoding of Reed-Solomon codes using bit-level soft information[C].Proc Allerton Conference on Communications,Control and Computing,2006.doi:10.1109/ TIT.2008.928238.

[4]El-Khamy M,McEliece R J.Iterative Algebraic soft-decision List decoding of Reed-Solomon codes[J].IEEE Journal on Selected Areas in Communications,2006,24(3):481-490.doi:10.1109/JSAC.2005.862399.

[5]Koetter R,Vardy A.A complexity reducing transformation in algebraic list-decoding of Reed-Solomon codes[C].Proc.IEEE Inform.Theory Workshop,Paris,France,April 2003.doi:10.1109/ITW.2003.1216682.

[6]Koetter R,Ma J,Vardy A.The re-encoding transformation in Algebraic list-decoding of Reed-Solomon codes[J].Information Theory,IEEE Transactions on,2011,57(2):633-647.

[7]Gross W J,Kschischang F R,Koetter R,et al.Applications of algebraic soft-decision decoding of Reed-Solomon codes[J].IEEE Trans Communication,2006,54(7):1224-1234.doi:10.1109/TCOMM.2006.877972.

[8]Huang Q,Wu J,Zhao C M,et al.Waterfilling-like multiplicity assignment algorithm for algebraic soft-decision decoding of Reed-Solomon codes[C].IEEE International Conference on Communications(ICC), 2007.doi:10.1109/ICC.2007.1028.

[9]Koetter R.Fast generalized minimum-distance decoding of algebraicgeometry and Reed-Solomon codes[J].IEEE Trans Inform Theory, 1996,42(3):721-737.doi:10.1109/18.490540.

[10]Cassuto Y,Bruck J;McEliece R J.On the average complexity of Reed-Solomon list decoders[J].Information Theory,IEEE Transactions on, 2013,59(4):2336-2351.doi:10.1109/TIT.2012.2235522.

[11]Li S Z,Ramamoorthy A.Algebraic code design for Slepian-Wolf codes [C].IEEE International Symposium on Information Theory(ISIT),Saint Petersburg,Russia,2011:1861-1865.

[12]Ali M,Kuijper M.Source coding with side information using list decoding[J].Information Theory Proceedings(ISIT),IEEE International Symposium on,2010:91-95.doi:10.1109/ISIT.2010.5513280.

【编校：王露】

Improved KV Algorithm with RS Code Algorithm Complexity Reduction

JIANG Nan
(Fujian Polytechnic of Information Technology,Fuzhou,Fujian 350003,China)

The reencoding algorithm,an improvement on the Koettery-Vardy(KV)algorithm for Reed-Solomon(RS)soft decoding was introduced.This algorithm takes advantage of the linearity of the Reed-Solomon codes.It preprocesses the multiplicity matrix,improve the initial polynomials in the interpolation algorithm and reduces the complexity of the interpolation algorithm. The overall complexity of the KV algorithm is reduced by a factor ofn2(n-k)2.Observed from the software implementation and simulations,for high rate RS codes,the algorithm reduces the complexity of the KV algorithm without sacrificing much performance.

Koetter-Vardy(KV)algorithm;reencoding algorithm;Reed-Solomon(RS)codes;complexity

TP301.6

A

1671-5365(2014)06-0094-05

2013-09-10修回：2013-10-20

2012年度福建省A类科技项目计划立项(JA12385)

江南(1972-)，女，副教授，工学学士，研究方向为计算机软件及项目管理

时间：2013-10-30 15:06

http://www.cnki.net/kcms/detail/51.1630.Z.20131030.1506.007.html