A linear algebraic approach to multisequence shift-register synthesis

V. R. Sidorenko; G. Schmidt

doi:10.1134/S0032946011020062

A linear algebraic approach to multisequence shift-register synthesis

V. R. Sidorenko, G. Schmidt

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

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λN) O(KN ²), where N is the length of a longest sequence and λ is the linear complexity of the sequences.

Original language	English
Pages (from-to)	149-165
Number of pages	17
Journal	Problems of Information Transmission
Volume	47
Issue number	2
DOIs	https://doi.org/10.1134/S0032946011020062
State	Published - Jun 2011
Externally published	Yes

Access to Document

10.1134/S0032946011020062

Cite this

@article{1935885a3d2d40e593ea92c0a80e165b,

title = "A linear algebraic approach to multisequence shift-register synthesis",

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λN) O(KN 2), where N is the length of a longest sequence and λ is the linear complexity of the sequences.",

author = "Sidorenko, {V. R.} and G. Schmidt",

note = "Funding Information: 1 Supported in part by the German Research Council (DFG), project nos. BO 867/14 and BO 867/21-1.",

year = "2011",

month = jun,

doi = "10.1134/S0032946011020062",

language = "English",

volume = "47",

pages = "149--165",

journal = "Problems of Information Transmission",

issn = "0032-9460",

publisher = "Pleiades Publishing",

number = "2",

}

TY - JOUR

T1 - A linear algebraic approach to multisequence shift-register synthesis

AU - Sidorenko, V. R.

AU - Schmidt, G.

N1 - Funding Information: 1 Supported in part by the German Research Council (DFG), project nos. BO 867/14 and BO 867/21-1.

PY - 2011/6

Y1 - 2011/6

N2 - 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λN) O(KN 2), where N is the length of a longest sequence and λ is the linear complexity of the sequences.

AB - 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λN) O(KN 2), where N is the length of a longest sequence and λ is the linear complexity of the sequences.

UR - http://www.scopus.com/inward/record.url?scp=80051684992&partnerID=8YFLogxK

U2 - 10.1134/S0032946011020062

DO - 10.1134/S0032946011020062

M3 - Article

AN - SCOPUS:80051684992

SN - 0032-9460

VL - 47

SP - 149

EP - 165

JO - Problems of Information Transmission

JF - Problems of Information Transmission

IS - 2

ER -

A linear algebraic approach to multisequence shift-register synthesis

Abstract

Access to Document

Other files and links

Fingerprint

Cite this