Complementary sequences

<h2 id="definition">Definition</h2>
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 <a href="/facts/Autocorrelation_function/dm4MqK0A">autocorrelation function</a> 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 <a href="/facts/Kronecker_delta/gcGAy0bm">Kronecker delta</a> 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 <a href="/facts/Radar/jk9BTbFA">radar</a> <a href="/facts/Pulse_compression/a8PE1dA1">pulse compression</a> and <a href="/facts/Spread_spectrum/0NKdJX1S">spread spectrum</a> <a href="/facts/Telecommunications/vxoj1cxR">telecommunications</a>.

<h2 id="examples">Examples</h2>
<ul><li>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).</li>
<li>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).</li>
<li>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).</li>
<li>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).</li></ul>
<h2 id="properties-of-complementary-pairs-of-sequences">Properties of complementary pairs of sequences</h2>
<ul><li>Complementary <a href="/facts/Sequences/gV2S4uqp">sequences</a> 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</li></ul>

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 <a href="/facts/Fourier_transform/XXhKJtc8">Fourier transform</a> 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 <a href="/facts/Z_transform/ERNvDJqt">Z transform</a> for Z = ejω.
<ul><li>CS spectra is upper bounded. As Sa and Sb are non-negative values we can write</li></ul>

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}.}

<ul><li>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;</li>
<li>If either of the sequences is reversed they remain complementary;</li>
<li>If either of the sequences is delayed they remain complementary;</li>
<li>If the sequences are interchanged they remain complementary;</li>
<li>If both sequences are multiplied by the same constant (real or complex) they remain complementary;</li>
<li>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;</li>
<li>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;</li>
<li>A new pair of sequences can be formed as {a b} and {a −b} where {..} denotes <a href="/facts/Interleave_sequence/l48lvNEU">interleaving</a> of sequences.</li>
<li>A new pair of sequences can be formed as a + b and a − b.</li></ul>
<h2 id="golay-pair">Golay pair</h2>
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 <a href="/facts/Shapiro_polynomials/hEeacDHC">Shapiro polynomials</a>, which give rise to complementary sequences of length a <a href="/facts/Power_of_two/MA6WEpTt">power of two</a>.

<h2 id="applications-of-complementary-sequences">Applications of complementary sequences</h2>
<ul><li>Multislit spectrometry</li>
<li>Ultrasound measurements</li>
<li>Acoustic measurements</li>
<li><a href="/facts/Radar/jk9BTbFA">radar</a> <a href="/facts/Pulse_compression/a8PE1dA1">pulse compression</a></li>
<li><a href="/facts/Wi-Fi/u94quCsx">Wi-Fi</a> networks,</li>
<li><a href="/facts/3G/kCh1eR7y">3G</a> <a href="/facts/CDMA/o2RLKE4M">CDMA</a> wireless networks</li>
<li><a href="/facts/OFDM/YhPkx5ql">OFDM</a> communication systems</li>
<li>Train wheel detection systems<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li>Non-destructive tests (NDT)</li>
<li>Communications</li>
<li><a href="/facts/Coded_aperture/5nc897I9">coded aperture</a> masks are designed using a 2-dimensional generalization of complementary sequences.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Binary_Golay_code/UY04RQEC">Binary Golay code</a> (<a href="/facts/Error-correcting_code/cLUTUJrA">Error-correcting code</a>)</li>
<li><a href="/facts/Gold_code/a0FsE0Mc">Gold sequences</a></li>
<li><a href="/facts/Kasami_code/q5QNFUCS">Kasami sequences</a></li>
<li><a href="/facts/Polyphase_sequence/aFEBILks">Polyphase sequence</a></li>
<li><a href="/facts/Pseudorandom_binary_sequence/fFSVtEE4">Pseudorandom binary sequences</a> (also called <a href="/facts/Maximum_length_sequence/VqXvnRvs">maximum length sequences</a> or M-sequences)</li>
<li><a href="/facts/Ternary_Golay_code/QrluWweb">Ternary Golay code</a> (<a href="/facts/Error-correcting_code/cLUTUJrA">Error-correcting code</a>)</li>
<li><a href="/facts/Hadamard_code/HAArwLV1">Walsh-Hadamard sequences</a></li>
<li><a href="/facts/Zadoff%25E2%2580%2593Chu_sequence/vKYfrag7">Zadoff–Chu sequence</a></li></ul>

<ul><li><a href="/facts/Marcel_J._E._Golay/8BJ8gj2T">Golay, Marcel J.E.</a> (1949). "Multislit spectroscopy". J. Opt. Soc. Am. 39 (6): 437–444. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1364%2FJOSA.39.000437">10.1364/JOSA.39.000437</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/18152021">18152021</a>.</li>
<li>Golay, Marcel J.E. (April 1961). "Complementary series". IRE Trans. Inf. Theory. 7 (2): 82–87. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTIT.1961.1057620">10.1109/TIT.1961.1057620</a>.</li>
<li>Golay, Marcel J.E. (1962). "Note on "Complementary series"". <a href="/facts/Proc._IRE/qhBDIIQd">Proc. IRE</a>. 50: 84. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FJRPROC.1962.288278">10.1109/JRPROC.1962.288278</a>.</li>
<li>Turyn, R.J. (1974). <a href="https://doi.org/10.1016%2F0097-3165%2874%2990056-9">"Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings"</a>. J. Comb. Theory A. 16 (3): 313–333. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0097-3165%2874%2990056-9">10.1016/0097-3165(74)90056-9</a>.</li>
<li><a href="/facts/Peter_Borwein/dJtVFCLg">Borwein, Peter</a> (2002). <a href="https://books.google.com/books?id=A_ITwN13J6YC&pg=PA110">Computational Excursions in Analysis and Number Theory</a>. Springer. pp. 110–9. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-95444-8.</li>
<li>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. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2006SeAcA.132..516D">2006SeAcA.132..516D</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.sna.2006.02.043">10.1016/j.sna.2006.02.043</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn: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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="http://geintra-uah.org/system/files/private/IV04_I.pdf" target="_blank">http://geintra-uah.org/system/files/private/IV04_I.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Complementary sequences open-in-new

Complementary sequences