Aperiodic Crosscorrelation of Sequences Derived From Characters

It is shown that the pairs of maximal linear recursive sequences (m-sequences) typically have mean square aperiodic crosscorrelation on par with that of random sequences, but that if one takes a pair of m-sequences where one is the reverse of the other, and shifts them appropriately, one can get significantly lower mean square aperiodic crosscorrelation. Sequence pairs with even lower mean square aperiodic crosscorrelation are constructed by taking a Legendre sequence, cyclically shifting it, and then cutting it (approximately) in half and using the halves as the sequences of the pair. In some of these constructions, the mean square aperiodic crosscorrelation can be lowered further if one truncates or periodically extends (appends) the sequences. Exact asymptotic formulas for mean squared aperiodic crosscorrelation are proved for sequences derived from additive characters (including m-sequences and modified versions thereof) and multiplicative characters (including Legendre sequences and their relatives). Data are presented that show that the sequences of modest length have performance that closely approximates the asymptotic formulas.