|
Problemy Peredachi Informatsii, 2011, Volume 47, Issue 2, Pages 72–89
(Mi ppi2046)
|
|
|
|
This article is cited in 10 scientific papers (total in 10 papers)
Automata Theory
A linear algebraic approach to multisequence shift-register synthesis
V. R. Sidorenkoab, G. Schmidtc a Ulm University, Germany
b aKharkevich Institute for Information Transmission Problems,
Russian Academy of Sciences, Moscow
c bEsslingen University of Applied Sciences, Germany
Abstract:
An efficient algorithm which synthesizes all shortest linear-feedback shift registers generating $K$ given sequences with possibly different lengths over a field is derived, and its correctness is proved. The proposed algorithm generalizes the Berlekamp–Massey and Feng–Tzeng algorithms and is based on Massey's ideas. The time complexity of the algorithm is $O(K\lambda N)\lesssim O(KN^2)$, where $N$ is the length of a longest sequence and $\lambda$ is the linear complexity of the sequences.
Received: 31.03.2008 Revised: 29.12.2010
Citation:
V. R. Sidorenko, G. Schmidt, “A linear algebraic approach to multisequence shift-register synthesis”, Probl. Peredachi Inf., 47:2 (2011), 72–89; Problems Inform. Transmission, 47:2 (2011), 149–165
Linking options:
https://www.mathnet.ru/eng/ppi2046 https://www.mathnet.ru/eng/ppi/v47/i2/p72
|
Statistics & downloads: |
Abstract page: | 342 | Full-text PDF : | 85 | References: | 45 | First page: | 14 |
|