On discrete Fourier transform, ambiguity, and Hamming-autocorrelation of pseudorandom sequences

摘要

We estimate discrete Fourier transform, ambiguity, and Hamming-auto-correlation of m-ary sequences in terms of their (periodic) correlation measure of order 4. Roughly speaking, we show that every pseudorandom sequence, that is, any sequence with small correlation measure up to a sufficiently large order, cannot have a large discrete Fourier transform, ambiguity, or Hamming-autocorrelation. Conversely, there are sequences, for example the two-prime generator, with large correlation measure of order 4 but small discrete Fourier transform, ambiguity, autocorrelation, and Hamming-autocorrelation.