In applied mathematics, complementarysequences are pairs of sequences with the useful property that their out-of-phase aperiodicautocorrelation coefficients sum to zero. Binary complementary sequences were first introduced by Marcel J. E. Golay in 1949. In 1961–1962 Golay gave several methods for constructing sequences of length 2N and gave examples of complementary sequences of lengths 10 and 26. In 1974 R. J. Turyn gave a method for constructing sequences of length mn from sequences of lengths m and n which allows the construction of sequences of any length of the form 2N10K26M. Later the theory of complementary sequences was generalized by other authors to polyphase complementary sequences, multilevel complementary sequences, and arbitrary complex complementary sequences. Complementary sets have also been considered; these can contain more than two sequences.
As the simplest example we have sequences of length 2: and. Their autocorrelation functions are and, which add up to.
As the next example, we have and. Their autocorrelation functions are and, which add up to.
One example of length 8 is and. Their autocorrelation functions are and.
An example of length 10 given by Golay is and. Their autocorrelation functions are and.
Properties of complementary pairs of sequences
Complementary sequences have complementary spectra. As the autocorrelation function and the power spectra form a Fourier pair, complementary sequences also have complementary spectra. But as the Fourier transform of a delta function is a constant, we can write
CS spectra is upper bounded. As Sa and Sb are non-negative values we can write
If either of the sequences of the CS pair is inverted they remain complementary. More generally if any of the sequences is multiplied byejφ they remain complementary;
If either of the sequences is reversed they remain complementary;
If either of the sequences is delayed they remain complementary;
If the sequences are interchanged they remain complementary;
If both sequences are multiplied by the same constant they remain complementary;
If both sequences are decimated in time by K they remain complementary. More precisely if from a complementary pair, b) we form a new pair, b) with skipped samples discarded then the new sequences are complementary.
If alternating bits of both sequences are inverted they remain complementary. In general for arbitrary complex sequences if both sequences are multiplied by ejπkn/N they remain complementary;
A new pair of complementary sequences can be formed as and where denotes concatenation and a and b are a pair of CS;
A new pair of sequences can be formed as and where denotes interleaving of sequences.
A new pair of sequences can be formed as a + b and a − b.
Golay pair
A complementary pair a, b may be encoded as polynomials A = a + a'z +... + a'zN−1 and similarly for B. The complementarity property of the sequences is equivalent to the condition for all z on the unit circle, that is, |z| = 1. If so, A and B form a Golay pair of polynomials. Examples include the Shapiro polynomials, which give rise to complementary sequences of length a power of two.
