# Complementary sequences > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Complementary_sequences > Markdown URL: https://mediated.wiki/source/Complementary_sequences.md > Source: https://en.wikipedia.org/wiki/Complementary_sequences > Source revision: 1254065717 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Pairs of sequences - *For complementary sequences in biology, see [complementarity (molecular biology)](/source/Complementarity_(molecular_biology)). For integer sequences with complementary sets of members see [Lambek–Moser theorem](/source/Lambek%E2%80%93Moser_theorem).* In applied mathematics, **complementary sequences** (**CS**) are pairs of [sequences](/source/Sequence) with the useful property that their out-of-phase aperiodic [autocorrelation](/source/Autocorrelation) coefficients sum to zero. Binary complementary sequences were first introduced by [Marcel J. E. Golay](/source/Marcel_J._E._Golay) in 1949. In 1961–1962 Golay gave several methods for constructing sequences of length 2*N* 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 2*N*10*K*26*M*. 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. ## Definition Let (*a*0, *a*1, ..., *a**N* − 1) and (*b*0, *b*1, ..., *b**N* − 1) be a pair of bipolar sequences, meaning that *a*(*k*) and *b*(*k*) have values +1 or −1. Let the aperiodic [autocorrelation function](/source/Autocorrelation_function) of the sequence **x** be defined by - R x ( k ) = ∑ j = 0 N − k − 1 x j x j + k . {\displaystyle R_{x}(k)=\sum _{j=0}^{N-k-1}x_{j}x_{j+k}.\,} Then the pair of sequences *a* and *b* is complementary if: - R a ( k ) + R b ( k ) = 2 N , {\displaystyle R_{a}(k)+R_{b}(k)=2N,\,} for *k* = 0, and - R a ( k ) + R b ( k ) = 0 , {\displaystyle R_{a}(k)+R_{b}(k)=0,\,} for *k* = 1, ..., *N* − 1. Or using [Kronecker delta](/source/Kronecker_delta) we can write: - R a ( k ) + R b ( k ) = 2 N δ ( k ) , {\displaystyle R_{a}(k)+R_{b}(k)=2N\delta (k),\,} So we can say that the sum of autocorrelation functions of complementary sequences is a delta function, which is an ideal autocorrelation for many applications like [radar](/source/Radar) [pulse compression](/source/Pulse_compression) and [spread spectrum](/source/Spread_spectrum) [telecommunications](/source/Telecommunications). ## Examples - As the simplest example we have sequences of length 2: (+1, +1) and (+1, −1). Their autocorrelation functions are (2, 1) and (2, −1), which add up to (4, 0). - As the next example (sequences of length 4), we have (+1, +1, +1, −1) and (+1, +1, −1, +1). Their autocorrelation functions are (4, 1, 0, −1) and (4, −1, 0, 1), which add up to (8, 0, 0, 0). - One example of length 8 is (+1, +1, +1, −1, +1, +1, −1, +1) and (+1, +1, +1, −1, −1, −1, +1, −1). Their autocorrelation functions are (8, −1, 0, 3, 0, 1, 0, 1) and (8, 1, 0, −3, 0, −1, 0, −1). - An example of length 10 given by Golay is (+1, +1, −1, +1, −1, +1, −1, −1, +1, +1) and (+1, +1, −1, +1, +1, +1, +1, +1, −1, −1). Their autocorrelation functions are (10, −3, 0, −1, 0, 1,−2, −1, 2, 1) and (10, 3, 0, 1, 0, −1, 2, 1, −2, −1). ## Properties of complementary pairs of sequences - Complementary [sequences](/source/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 - - S a + S b = C S , {\displaystyle S_{a}+S_{b}=C_{S},} - where *C**S* is a constant. - *S**a* and *S**b* are defined as a squared magnitude of the [Fourier transform](/source/Fourier_transform) of the sequences. The Fourier transform can be a direct DFT of the sequences, it can be a DFT of zero padded sequences or it can be a continuous Fourier transform of the sequences which is equivalent to the [Z transform](/source/Z_transform) for *Z* = *e**j*ω. - CS spectra is upper bounded. As *S**a* and *S**b* are non-negative values we can write - - S a = C S − S b < C S , {\displaystyle S_{a}=C_{S}-S_{b}