A Fourier Transform Approach to the Linear Complexity of Nonlinearly Filtered Sequences

  • James L. Massey
  • Shirlei Serconek
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


A method for analyzing the linear complexity of nonlinear filterings of PN-sequences that is based on the Discrete Fourier Transform is presented. The method makes use of “Blahut’s theorem”, which relates the linear complexity of an N-periodic sequence in GF(q)N and the Hamming weight of its frequency-domain associate. To illustrate the power of this approach, simple proofs are given of Key’s bound on linear complexity and of a generalization of a condition of Groth and Key for which equality holds in this bound.


Discrete Fourier Transform Linear Complexity Stream Cipher Primitive Element Inverse Discrete Fourier Transform 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. [1]
    R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company, 1983.Google Scholar
  2. [2]
    E. J. Groth “Generation of binary sequences with controllable complexity,” IEEE Trans. Inform. Theory, vol. IT-17, no. 3, pp. 288–296, May 1971.CrossRefMathSciNetGoogle Scholar
  3. [3]
    E. L. Key “An analysis of the structure and complexity of nonlinear binary sequence generators,” IEEE Trans. Inform. Theory, vol. IT-22, no. 6, pp. 732–736, Nov. 1976.CrossRefMathSciNetGoogle Scholar
  4. [4]
    R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge: Cambridge Univ. Press, 1986.zbMATHGoogle Scholar
  5. [5]
    J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Trans. Inform. Theory, vol. IT-15, pp. 122–127, Jan. 1969.CrossRefMathSciNetGoogle Scholar
  6. [6]
    J. L. Massey, “Review of R. E. Blahut, Theory and Practice of Error Control Codes”, IEEE Trans. Inform. Theory, vol. IT-31, no. 4, p. 553, Jul. 1985.CrossRefMathSciNetGoogle Scholar
  7. [7]
    R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986.zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • James L. Massey
    • 1
  • Shirlei Serconek
    • 1
  1. 1.Signal and Information Processing Laboratory Swiss Federal Institute of TechnologyETH-ZentrumZürichSwitzerland

Personalised recommendations