• Images
• Videos
• Documents
• Books
• Articles

Definition

Let (a0, a1, ..., aN − 1) and (b0, b1, ..., bN − 1) be a pair of bipolar sequences, meaning that a(k) and b(k) have values +1 or −1. Let the aperiodic 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 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 pulse compression and spread spectrum 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 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 CS is a constant. Sa and Sb 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 Z = ejω.

• CS spectra is upper bounded. As Sa and Sb are non-negative values we can write

S a = C S − S b < C S , {\displaystyle S_{a}=C_{S}-S_{b}<C_{S},} also S b < C S . {\displaystyle S_{b}<C_{S}.}

• 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 ejφ 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 ejπ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)zN−1 and similarly for B(z). The complementarity property of the sequences is equivalent to the condition

| A ( z ) | 2 + | B ( z ) | 2 = 2 N {\displaystyle \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.

Applications of complementary sequences

• Multislit spectrometry
• Ultrasound measurements
• Acoustic measurements
• radar pulse compression
• Wi-Fi networks,
• 3G CDMA wireless networks
• OFDM communication systems
• Train wheel detection systems¹²
• Non-destructive tests (NDT)
• Communications
• coded aperture masks are designed using a 2-dimensional generalization of complementary sequences.

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

• Golay, Marcel J.E. (1949). "Multislit spectroscopy". J. Opt. Soc. Am. 39 (6): 437–444. doi:10.1364/JOSA.39.000437. PMID 18152021.
• Golay, Marcel J.E. (April 1961). "Complementary series". IRE Trans. Inf. Theory. 7 (2): 82–87. doi:10.1109/TIT.1961.1057620.
• Golay, Marcel J.E. (1962). "Note on "Complementary series"". Proc. IRE. 50: 84. doi:10.1109/JRPROC.1962.288278.
• Turyn, R.J. (1974). "Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings". J. Comb. Theory A. 16 (3): 313–333. doi:10.1016/0097-3165(74)90056-9.
• Borwein, Peter (2002). Computational Excursions in Analysis and Number Theory. Springer. pp. 110–9. ISBN 978-0-387-95444-8.
• Donato, P.G.; Ureña, J.; Mazo, M.; De Marziani, C.; Ochoa, A. (2006). "Design and signal processing of a magnetic sensor array for train wheel detection". Sensors and Actuators A: Physical. 132 (2): 516–525. Bibcode:2006SeAcA.132..516D. doi:10.1016/j.sna.2006.02.043.

References

1. Donato, P.G.; Ureña, J.; Mazo, M.; Alvarez, F. "Train wheel detection without electronic equipment near the rail line". 2004. doi:10.1109/IVS.2004.1336500 /wiki/Doi_(identifier) ↩

2. J.J. Garcia; A. Hernandez; J. Ureña; J.C. Garcia; M. Mazo; J.L. Lazaro; M.C. Perez; F. Alvarez. "Low cost obstacle detection for smart railway infrastructures". 2004. http://geintra-uah.org/system/files/private/IV04_I.pdf ↩