Linearized shift-register synthesis

Vladimir Sidorenko; Gerd Richter; Martin Bossert

doi:10.1109/TIT.2011.2162173

Linearized shift-register synthesis

Vladimir Sidorenko, Gerd Richter, Martin Bossert

University of Ulm

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

23 Scopus citations

Abstract

An efficient algorithm synthesizing all shortest q-linearized-feedback shift-registers generating a given sequence of length N over a finite field double-struk F sign_qm is derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity script O sign(lN) ≲ script O sign(N²) operations in double-struk F sign_qm, where l is the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.

Original language	English
Article number	6006607
Pages (from-to)	6025-6032
Number of pages	8
Journal	IEEE Transactions on Information Theory
Volume	57
Issue number	9
DOIs	https://doi.org/10.1109/TIT.2011.2162173
State	Published - Sep 2011
Externally published	Yes

Keywords

Gabidulin codes
key equation
linearized complexity
linearized-feedback
shift-register synthesis

Access to Document

10.1109/TIT.2011.2162173

Cite this

@article{ac5d648fc5df4755b1a0bb4f6cc3eac0,

title = "Linearized shift-register synthesis",

abstract = "An efficient algorithm synthesizing all shortest q-linearized-feedback shift-registers generating a given sequence of length N over a finite field double-struk F signqm is derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity script O sign(lN) ≲ script O sign(N2) operations in double-struk F signqm, where l is the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.",

keywords = "Gabidulin codes, key equation, linearized complexity, linearized-feedback, shift-register synthesis",

author = "Vladimir Sidorenko and Gerd Richter and Martin Bossert",

note = "Funding Information: Manuscript received November 06, 2009; revised November 25, 2010; accepted January 09, 2011. Date of current version August 31, 2011. This work was supported by the DFG (German Research Council) under Grant BO 867/21-1. The material in this paper was presented at the 8th International ITG Conference on Source and Channel Coding, Siegen, Germany, January 2010.",

year = "2011",

month = sep,

doi = "10.1109/TIT.2011.2162173",

language = "English",

volume = "57",

pages = "6025--6032",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

T1 - Linearized shift-register synthesis

AU - Sidorenko, Vladimir

AU - Richter, Gerd

AU - Bossert, Martin

N1 - Funding Information: Manuscript received November 06, 2009; revised November 25, 2010; accepted January 09, 2011. Date of current version August 31, 2011. This work was supported by the DFG (German Research Council) under Grant BO 867/21-1. The material in this paper was presented at the 8th International ITG Conference on Source and Channel Coding, Siegen, Germany, January 2010.

PY - 2011/9

Y1 - 2011/9

N2 - An efficient algorithm synthesizing all shortest q-linearized-feedback shift-registers generating a given sequence of length N over a finite field double-struk F signqm is derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity script O sign(lN) ≲ script O sign(N2) operations in double-struk F signqm, where l is the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.

AB - An efficient algorithm synthesizing all shortest q-linearized-feedback shift-registers generating a given sequence of length N over a finite field double-struk F signqm is derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity script O sign(lN) ≲ script O sign(N2) operations in double-struk F signqm, where l is the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.

KW - Gabidulin codes

KW - key equation

KW - linearized complexity

KW - linearized-feedback

KW - shift-register synthesis

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

U2 - 10.1109/TIT.2011.2162173

DO - 10.1109/TIT.2011.2162173

M3 - Article

AN - SCOPUS:80052347300

SN - 0018-9448

VL - 57

SP - 6025

EP - 6032

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 9

M1 - 6006607

ER -

Linearized shift-register synthesis

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this