Complementary Sequences
   HOME

TheInfoList



OR:

: ''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 The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two Complement (set theory), complementary sets. For instance, it applies to the partition of numbers into even number, even and odd number, odd, or ...
.'' 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 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 variable ...
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 variable ...
of the sequence x be defined by :R_x(k)=\sum_^ x_jx_.\, 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 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: :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 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, w ...
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 dom ...
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 :: 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 A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed, ...
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 In mathematics and signal processing, the Z-transform converts a discrete-time signal, which is a sequence of real or complex numbers, into a complex frequency-domain (z-domain or z-plane) representation. It can be considered as a discrete-tim ...
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 < C_S, : also :: 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 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 Interleaving may refer to: * Interleaving, a technique for making forward error correction more robust with respect to burst errors * An optical interleaver, a fiber-optic device to combine two sets of dense wavelength-division multiplexing (DW ...
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 In mathematics, the Shapiro polynomials are a 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 polynomials have good auto ...
, 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-negative ...
.


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, w ...
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 wave ...
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 communication ...
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 commun ...
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 Coded apertures or coded-aperture masks are grids, gratings, or other patterns of materials opaque to various wavelengths of electromagnetic radiation. The wavelengths are usually high-energy radiation such as X-rays and gamma rays. By blocking ra ...
masks are designed using a 2-dimensional generalization of complementary sequences.


See also

*
Binary Golay code In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection ...
(
Error-correcting code In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
) * Gold sequences * Kasami sequences *
Polyphase sequence In mathematics, a polyphase sequence is a sequence whose terms are complex roots of unity: : a_n = e^ \, where ''x'n'' is an integer. Polyphase sequences are an important class of sequences and play important roles in synchronizing 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 rando ...
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 the ...
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 distance ...
(
Error-correcting code In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
) * 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 shi ...


References

* * * * * * {{refend Sequences and series Signal processing Pseudorandom number generators