A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes
A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes
复制标题
DOI：
10.1109/18.133246
复制
发表时间：
1991-09
期刊：
影响因子：
--
通讯作者：
G. Feng;K. Tzeng
中科院分区：
文献类型：
--
作者：
G. Feng;K. Tzeng
提出了Berlekamp-Massey算法的概括，用于合成最小长度线性反馈移位寄存器，以生成规定的多个序列。首先考虑了一个更普遍的问题，即在任意字段上找到矩阵中最小的初始依赖列集，其中包括多次问题问题作为特殊情况。提出了一种简单的迭代算法，即基本迭代算法（FIA），用于解决此问题。然后，通过FIA的细化得出了广义算法。考虑到将这种广义算法应用于将循环代码解码为Hartmann-Tzeng（HT）结合和Roos Bound的使用，并考虑使用多个综合征序列。确保该算法获得的最短反馈移位寄存器的连接多项式的条件将是错误局限器的多项式，而不是解码到ROOS结合的HT结合和特殊情况。 >
A generalization of the Berlekamp-Massey algorithm is presented for synthesizing minimum length linear feedback shift registers for generating prescribed multiple sequences. A more general problem is first considered, that of finding the smallest initial set of linearly dependent columns in a matrix over an arbitrary field, which includes the multisequence problem as a special case. A simple iterative algorithm, the fundamental iterative algorithm (FIA), is presented for solving this problem. The generalized algorithm is then derived through a refinement of the FIA. Application of this generalized algorithm to decoding cyclic codes up to the Hartmann-Tzeng (HT) bound and Roos bound making use of multiple syndrome sequences is considered. Conditions for guaranteeing that the connection polynomial of the shortest linear feedback shift register obtained by the algorithm will be the error-locator polynomial are determined with respect to decoding up to the HT bound and special cases of the Roos bound. >