循环码译码的Dixon结式方法  

Decoding Cyclic Codes by Using Dixon Resultant Method

作　　者：李耀辉[1] 赵海豹[1] 马春芽[1] 

机构地区：[1]天津工程师范学院计算机科学系,天津300222

出　　处：《应用数学学报》2011年第4期602-617,共16页Acta Mathematicae Applicatae Sinica

基　　金：国家973计划(NKBRSF-2004CB318003);天津工程师范学院引进人才基金(KYQD06005);天津工程师范学院科研基金(KJ20080039)资助项目

摘　　要：针对纠错码译码就是非线性方程组的求解问题,提出利用Dixon结式方法对译码方程进行消元以得到接收数据中的错位多项式.首先,根据纠错码的纠错能力和接收数据得到伴随式矩阵并通过该矩阵的秩确定接收码字中错误位的个数.然后,根据错位个数和伴随多项式构造译码方程.译码时,将其中一个错位变元作为隐藏变元,利用Dixon结式方法进行消元.最后,得到的Dixon结式就是关于隐藏变元的多项式.该多项式去掉多余因子后就是错位多项式,利用Chien搜索法即可求解出错误位置.当错位较多时,采用逐次计算结式的方法以筛除计算过程中的多余因子和重因子.另外,根据不同错位个数得到的错位多项式,提出了构造一类循环码错位多项式符号解的猜想,该猜想可以大大提高译码效率.实验验证了结式理论在纠错码译码方面的应用是有效的且有助于降低对芯片性能的要求.In order to solve the nonlinear equations in the decoding of error-correcting codes,a new method,based on Dixon resultant,is proposed for computing the error locator polynomial.In the process of computation,a syndrome matrix should be generated according to error-correcting capability of the code and the received codeword firstly.Then, the number of errors in the received codeword is decided by the rank of a syndrome matrix. After that,the decoding equations can be constructed directly based on the number of errors and are eliminated by Dixon resultant,in which one of variables is regarded as a parameter.Finally,a univariate polynomial in the variable of error locator is computed out. When extraneous factors and repeated factors in the polynomial are deleted,the left is the error locator polynomial.Then error location can be known by using Chien search.If there are many errors in the received codeword,the system is divided into several subsystem for computing error locator polynomial by Dixon resultant step by step so as to improve the efficiency of algorithm.Thus,the extraneous factors and repeated factors in Dixon resultant can be sifted out and the computation is simplified.Besides this,from the error locator polynomial in different errors,a guess,which improves decoding efficiency greatly,of general error locator polynomial of a class of cyclic codes is proposed.However,its correctness should be proven theoretically.Contrast with other symbolic computation method,because the number of errors in codeword is decided directly and error locator polynomial can be computed out by using Dixon resultant only once.It can improve the efficiency of decoding and is benefit to simplify the design of decoding chip.

关 键 词：Dixon结式 纠错码 译码 伴随式 

分 类 号：O236.2[理学—运筹学与控制论]