A Fourier Transform Approach to the Linear Complexity of Nonlinearly Filtered Sequences
- 2.3k Downloads
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.
KeywordsDiscrete Fourier Transform Linear Complexity Stream Cipher Primitive Element Inverse Discrete Fourier Transform
- R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company, 1983.Google Scholar