On the Linear Complexity of Sequences Obtained by State Space Generators

Author

Limniotis, Konstantinos ; Kolokotronis, Nicholas ; Kalouptsidis, Nicholas

Author_Institution

Nat. & Kapodistrian Univ. of Athens, Athens

Volume

54

Issue

4

fYear

2008

fDate

4/1/2008 12:00:00 AM

Firstpage

1786

Lastpage

1793

Abstract

Binary sequences generated from finite state automata are studied in this correspondence by utilizing system theoretic concepts. We develop a new unified approach for analyzing the linear complexity of such sequences, via controllability and observability conditions. A vectorial trace representation of sequences with arbitrary period is provided, which leads to a new generalized discrete Fourier transform allowing the generation of sequences with prescribed linear complexity. Furthermore, we introduce new classes of nonlinear filters, using the proposed approach, which generalize currently known classes and guarantee the same lower bound on the linear complexity.

Keywords

binary sequences; discrete Fourier transforms; filtering theory; finite state machines; nonlinear filters; state-space methods; binary sequences; controllability conditions; discrete Fourier transform; finite state automata; linear complexity; nonlinear filters; observability conditions; state space generators; vectorial trace representation; Controllability; Cryptography; Discrete Fourier transforms; Feedback; Fourier transforms; Galois fields; Nonlinear filters; Observability; Shift registers; State-space methods; Complexity; discrete Fourier transform; feedback shift registers; nonlinear filters; sequences; state space generators;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2008.917639

Filename

4475379