Fourier transforms and the 2-adic span of periodic binary sequences

摘要: In this paper we develop an arithmetic analog of Blahut's theorem (Blahut 1979, Massey 1986) which says that the linear complexity (or equivalent span) /spl lambda/(S) a periodic binary sequence S=a/sub 0/,a/sub 1/,... is equal to number nonzero coefficients in discrete Fourier transform (DFT) S. If S used as key stream cipher then measure security against cryptoanalytic attack: feedback shift register (LFSR) generates can be determined from 2/spl bits by using Berlekamp-Massey algorithm, and resulting will have length lambda/(S). So makes precise common observation "complex" signal one with many components.