Lower bounds on error complexity measures for periodic LFSR and FCSR sequences

Ramakanth Kavuluru, Andrew Klapper

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Non-trivial lower bounds on the linear complexity are derived for a sequence obtained by performing a combination of up to k substitutions, insertions, and deletions. The bounds derived are similar to those previously established for either k substitutions, k insertions or k deletions within a single period. The bounds are useful when T/2k < λ < T/k, where λ is the linear complexity of the original sequence and T is its period. It is shown that similar bounds hold for the joint linear complexity of periodic multisequences. Similar results are obtained for the N-adic complexity of periodic sequences over {0,... , N - 1}. New non-trivial lower bounds on the minimum number of operations needed to decrease the complexity are also given. The derivations are simpler compared to those in previous work on these problems.

Original languageEnglish
Pages (from-to)95-116
Number of pages22
JournalCryptography and Communications
Issue number1
StatePublished - Apr 2009

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. CCF-0514660. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.


  • FCSR
  • LFSR
  • Linear complexity
  • N-adic complexity
  • k-error complexity

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Lower bounds on error complexity measures for periodic LFSR and FCSR sequences'. Together they form a unique fingerprint.

Cite this