Linearized shift-register synthesis

Vladimir Sidorenko, Gerd Richter, Martin Bossert

Research output: Contribution to journalArticlepeer-review

23 Citations (SciVal)


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.

Original languageEnglish
Article number6006607
Pages (from-to)6025-6032
Number of pages8
JournalIEEE Transactions on Information Theory
Issue number9
Publication statusPublished - Sep 2011
Externally publishedYes


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


Dive into the research topics of 'Linearized shift-register synthesis'. Together they form a unique fingerprint.

Cite this