Perfect and almost perfect sequences Original Research Article

The autocorrelation function of a sequence is a measure for how much the given sequence differs from its translates. Periodic binary sequences with good correlation properties have important applications in various areas of engineering. In particular, one needs sequences with a two-level autocorrelation function, that is, all nontrivial autocorrelation coefficients equal some constant γ. The case where γ is as small as theoretically possible in absolute value has turned out to be especially useful; such sequences are called perfect. Unfortunately, in many cases perfect sequences cannot exist, and so one has also considered “almost perfect” sequences, where one allows one nontrivial autocorrelation coefficient to be different from γ. In this paper, we concentrate on the existence problem for perfect and almost perfect binary periodic sequences; such sequences are actually equivalent to certain cyclic difference sets and cyclic divisible difference sets, respectively, structures which have been studied in Design Theory for a long time. This connection allows one to obtain strong results on the existence of (almost) perfect sequences. We also discuss some related questions, namely the aperiodic case, ternary perfect sequences, binary perfect arrays, and the merit factor of a sequence. Finally, we conclude the paper with a simplified description of an interesting real-world application, namely “coded aperture imaging”. Our paper serves mainly as a survey of the area just outlined, but it also contains some new results.