Complementary sequences

Let (a₀, a₁, ..., a_N − 1) and (b₀, b₁, ..., 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 of the sequence x be defined by

${\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:

${\displaystyle R_{a}(k)+R_{b}(k)=2N,\,}$

for k = 0, and

${\displaystyle R_{a}(k)+R_{b}(k)=0,\,}$

for k = 1, ..., N − 1.

Or using Kronecker delta we can write:

${\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.

• 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).

• 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

${\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 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 = e^jω.

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

${\displaystyle S_{a}=C_{S}-S_{b}<C_{S},}$

also

${\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 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.

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

${\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.

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

• 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