: ''For complementary sequences in biology, see
complementarity (molecular biology)
In molecular biology, complementarity describes a relationship between two structures each following the lock-and-key principle. In nature complementarity is the base principle of DNA replication and transcription as it is a property shared b ...
. For integer sequences with complementary sets of members see
Lambek–Moser theorem.''
In applied mathematics, complementary sequences (CS) are pairs of
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s 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.
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
Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variabl ...
of the sequence x be defined by
:
Then the pair of sequences ''a'' and ''b'' is complementary if:
:
for ''k'' = 0, and
:
for ''k'' = 1, ..., ''N'' − 1.
Or using
Kronecker delta
In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:
\delta_ = \begin
0 &\text i \neq j, \\
1 & ...
we can write:
:
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
Radar is a detection system that uses radio waves to determine the distance ('' ranging''), angle, and radial velocity of objects relative to the site. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, we ...
pulse compression Pulse compression is a signal processing technique commonly used by radar, sonar and echography to increase the range resolution as well as the signal to noise ratio. This is achieved by modulating the transmitted pulse and then correlating th ...
and
spread spectrum
In telecommunication and radio communication, spread-spectrum techniques are methods by which a signal (e.g., an electrical, electromagnetic, or acoustic signal) generated with a particular bandwidth is deliberately spread in the frequency d ...
telecommunications
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that fe ...
.
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
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
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
::
: 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
::
: also
::
* 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 both sequences are decimated in time by ''K'' they remain complementary. More precisely if from a complementary pair (''a''(''k''), ''b''(''k'')) we form a new pair (''a''(''Nk''), ''b''(''Nk'')) 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 ''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 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''(''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
:
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 In mathematics, the Shapiro polynomials are a polynomial sequence, sequence of polynomials which were first studied by Harold S. Shapiro in 1951 when considering the magnitude of specific trigonometric sums. In signal processing, the Shapiro polynom ...
, which give rise to complementary sequences of length a
power of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negativ ...
.
Applications of complementary sequences
* Multislit spectrometry
* Ultrasound measurements
* Acoustic measurements
*
radar
Radar is a detection system that uses radio waves to determine the distance ('' ranging''), angle, and radial velocity of objects relative to the site. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, we ...
pulse compression Pulse compression is a signal processing technique commonly used by radar, sonar and echography to increase the range resolution as well as the signal to noise ratio. This is achieved by modulating the transmitted pulse and then correlating th ...
*
Wi-Fi
Wi-Fi () is a family of wireless network protocols, based on the IEEE 802.11 family of standards, which are commonly used for local area networking of devices and Internet access, allowing nearby digital devices to exchange data by radio wav ...
networks,
*
3G CDMA
Code-division multiple access (CDMA) is a channel access method used by various radio communication technologies. CDMA is an example of multiple access, where several transmitters can send information simultaneously over a single communicatio ...
wireless networks
*
OFDM
In telecommunications, orthogonal frequency-division multiplexing (OFDM) is a type of digital transmission and a method of encoding digital data on multiple carrier frequencies. OFDM has developed into a popular scheme for wideband digital commu ...
communication systems
* Train wheel detection systems
[
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.
* 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 sequence
A pseudorandom binary sequence (PRBS), pseudorandom binary code or pseudorandom bitstream is a binary sequence that, while generated with a deterministic algorithm, is difficult to predict and exhibits statistical behavior similar to a truly rand ...
s (also called
maximum length sequence
A maximum length sequence (MLS) is a type of pseudorandom binary sequence.
They are bit sequences generated using maximal linear-feedback shift registers and are so called because they are periodic and reproduce every binary sequence (except th ...
s or M-sequences)
*
Ternary Golay code
In coding theory, the ternary Golay codes are two closely related error-correcting codes.
The code generally known simply as the ternary Golay code is an 1, 6, 53-code, that is, it is a linear code over a ternary alphabet; the relative distan ...
(
Error-correcting code)
*
Walsh-Hadamard sequences
*
Zadoff–Chu sequence
A Zadoff–Chu (ZC) sequence, also referred to as Chu sequence or Frank–Zadoff–Chu (FZC) sequence, is a complex-valued mathematical sequence which, when applied to a signal, gives rise to a new signal of constant amplitude. When cyclically sh ...
References
*
*
*
*
*
*
{{refend
Sequences and series
Signal processing
Pseudorandom number generators