Fast skew-feedback shift-register synthesis

Vladimir Sidorenko, Martin Bossert

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


A skew-feedback shift-register is a generalization of a linear-feedback shift-register and can be applied in decoding (interleaved) Reed-Solomon codes or Gabidulin codes beyond half their code distance. A fast algorithm is proposed which synthesizes all shortest skew-feedback shift-registers generating L sequences of varying length over a field. For fixed L, the time complexity of the algorithm is {{\mathcal O}(M(N) \log N)} operations, where N is the length of a longest sequence and M(N) is the complexity of the multiplication of two skew polynomials of maximum degree N.

Original languageEnglish
Pages (from-to)55-67
Number of pages13
JournalDesigns, Codes, and Cryptography
Issue number1-2
Publication statusPublished - 2014
Externally publishedYes


  • Decoding
  • Gabidulin codes
  • Interleaved codes
  • Multiple sequences
  • Reed-Solomon codes
  • Shift-register synthesis
  • Skew-feedback


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

Cite this