Complementary sequences
≈ 5 min read
Names in other languages
- caSeqüències complementàries
- EspañolSecuencias complementarias
- EnglishComplementary sequences
- 中文互补序列
- 中文互补序列
- 简体中文互补序列
- 繁體中文互補序列
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
: For complementary sequences in biology, see complementarity (molecular biology). For integer sequences with complementary sets of members see Lambek–Moser theorem. In applied mathematics, complementary sequences (CS) are pairs of sequences with the useful property that their out-of-phase aperiodic autocorrelation 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 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.
For complementary sequences in biology, see complementarity (molecular biology). For integer sequences with complementary sets of members see Lambek–Moser theorem. In applied mathematics, complementary sequences (CS) are pairs of sequences with the useful property that their out-of-phase aperiodic autocorrelation 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 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. R_\mathbf{x}(k)=\sum_{j=0}^{N-k-1} x_jx_{j+k}.\, Then the pair of sequences a and b is complementary if: R_a(k) + R_b(k) = 2N,\, for k = 0, and R_a(k) + R_b(k) = 0,\, for k = 1, ..., N − 1.
Or using Kronecker delta we can write: 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 pulse compression and spread spectrum telecommunications. 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 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 for . CS spectra is upper bounded. As S a and S b are non-negative values we can write S_a = C_S - S_b also S_b If either of the sequences of the CS pair is inverted (multiplied by −1) they remain complementary.
More generally if any of the sequences is multiplied by e jφ 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 (real or complex) they remain complementary; If alternating bits of both sequences are inverted they remain complementary.
In general for arbitrary complex sequences if both sequences are multiplied by e jπkn/N (where k is a constant and n is the time index) they remain complementary; A new pair of complementary sequences can be formed as [a b] and [a −b] where [..] denotes concatenation and a and b are a pair of CS; A new pair of sequences can be formed as {a b} and {a −b} 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(z) = a(0) + a(1)z + ... + a(N − 1)z N−1 and similarly for B(z). The complementarity property of the sequences is equivalent to the condition \vert A(z) \vert^2 + \vert B(z) \vert^2 = 2N \, 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.
See also
Binary Golay code (Error-correcting code) Gold sequences Kasami sequences Polyphase sequence Pseudorandom binary sequences (also called maximum-length sequences or M-sequences) Ternary Golay code (Error-correcting code) Walsh-Hadamard sequences Zadoff–Chu sequence
Text derived from https://en.wikipedia.org/w/index.php?oldid=1366887575 under CC BY-SA 4.0; modifications have been made.