Linear Shift-Register Synthesis for Multiple Sequences of Varying Length
Linear Shift-Register Synthesis for Multiple Sequences of Varying Length
复制标题
不同长度的多个序列的线性移位寄存器综合
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
V. Sidorenko
中科院分区：
文献类型：
--
作者：
G. Schmidt;V. Sidorenko
考虑寻找能够在某个域F上生成t个有限长度序列的最短线性移位寄存器的问题。 Feng 和 Tzeng 已经解决了类似的问题。他们提出了一种迭代算法来解决这个多序列移位寄存器综合问题，该算法可以被视为众所周知的 Berlekamp-Massey 算法的推广。如果所有 t 序列具有相同的长度，则 Feng-Tzeng 算法确实有效。本文重点研究用于生成不同长度序列的多序列移位寄存器综合。据透露，在这种情况下，Feng-Tzeng 算法并不总是给出正确的解决方案。提出并正式证明了一种改进的算法，克服了这个问题。
The problem of finding the shortest linear shift-register capable of generating t finite length sequences over some field F is considered. A similar problem was already addressed by Feng and Tzeng. They presented an iterative algorithm for solving this multi-sequence shift-register synthesis problem, which can be considered as generalization of the well known Berlekamp-Massey algorithm. The Feng-Tzeng algorithm works indeed, if all t sequences have the same length. This paper focuses on multi-sequence shift-register synthesis for generating sequences of varying length. It is exposed, that the Feng-Tzeng algorithm does not always give the correct solution in this case. A modified algorithm is proposed and formally proved, which overcomes this problem.