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

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

10 Zitate (Scopus)

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.

Originalsprache	Englisch
Seiten (von - bis)	149-165
Seitenumfang	17
Fachzeitschrift	Problems of Information Transmission
Jahrgang	47
Ausgabenummer	2
DOIs	https://doi.org/10.1134/S0032946011020062
Publikationsstatus	Veröffentlicht - Juni 2011
Extern publiziert	Ja

Zugriff auf Dokument

10.1134/S0032946011020062

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@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 - https://www.scopus.com/pages/publications/80051684992

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

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren