View source for Correlation property for sequences

Complex-valued <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104302.png" />-periodic sequences (i.e. sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104303.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104304.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104305.png" />) with  "good"  correlation properties have many applications in signal processing (spread spectrum and code division multiple access communication systems, see [[#References|[a10]]]). A good survey is [[#References|[a9]]]. Periodic sequences are recurring or shift register sequences, see [[#References|[a2]]].

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104306.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104307.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104308.png" />-periodic sequences, one defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c1104309.png" />. These numbers are called the periodic correlation coefficients (in case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043010.png" />, periodic autocorrelation coefficients). Sometimes also the aperiodic correlation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043011.png" /> is of interest. The odd correlation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043013.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043015.png" />.

The goal is the design of large sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043016.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043017.png" />-periodic sequences such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043018.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043019.png" /></td> </tr></table>

(or the respective value for the aperiodic correlation) is small. Sequences with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043021.png" />, are called perfect. Perfect sequences whose entries are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043022.png" />th roots of unity (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043023.png" />) are known for many periods <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043024.png" />, but no example of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043025.png" />-sequence with period <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043026.png" /> is known (the perfect sequence conjecture: there are no perfect binary sequences with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043027.png" />). In the aperiodic case, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043028.png" />-sequences with odd period <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043029.png" /> and aperiodic correlation coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043031.png" /> (Barker sequences) have been classified [[#References|[a12]]]. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043032.png" /> is even, the existence of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043033.png" />-periodic Barker sequence implies the existence of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043034.png" />-periodic perfect <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043035.png" />-sequence.

If one assumes that the sequences are normalized, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043036.png" />, then it is known that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043037.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043038.png" /></td> </tr></table>

and, if the entries of the sequences are just <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043039.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043040.png" /></td> </tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043041.png" />. If the entries of the sequences are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043042.png" />th roots of unity (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043043.png" />), then the bound is

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043044.png" /></td> </tr></table>

The first bound is due to L.R. Welch, the second two bounds are due to V.M. Sidel'nikov. In all cases, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043045.png" /> is an integer. Some improvements of these bounds are known. Similar bounds hold for the maximum odd correlation coefficient [[#References|[a7]]].

Important classes of sequences are derived from so-called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043047.png" />-sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043048.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043049.png" /> is a primitive element of the [[Finite field|finite field]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043051.png" />. The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043052.png" /> is defined over a finite field. The complex-valued sequences corresponding to such finite field sequences are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043053.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043054.png" /> is a [[Homomorphism|homomorphism]] from the additive group of the field into the multiplicative group of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043055.png" />. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043056.png" />-sequences yield complex sequences with autocorrelation coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043057.png" />. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043060.png" />-decimation of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043061.png" />-periodic sequence is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043062.png" />. Systematic investigations of the correlation properties between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043063.png" />-sequences and their decimations can be found in [[#References|[a4]]] and [[#References|[a11]]]. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043064.png" />-sequences are recurring sequences of maximum period length. Their good autocorrelation properties show that they have good  "random"  properties (pseudo-noise sequences).

In many cases, variations of the construction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043065.png" />-sequences yield sets of sequences with optimal correlation properties with respect to the Welch and Sidel'nikov bounds: The cases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043067.png" /> have been investigated intensively. Regarding binary sequences, both the Gold sequences (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043068.png" />) and the Kasami sequences (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043069.png" />) are asymptotically optimal. (One says that a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043070.png" /> of sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043071.png" />-periodic sequences is asymptotically optimal if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043072.png" />, is best possible. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043073.png" />, the lower bounds show that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043074.png" /> for binary and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043075.png" /> for arbitrary complex valued sequences. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043076.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043077.png" />.) Sequences whose entries are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043078.png" />th roots of unity (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043079.png" />) and which are optimal have been constructed (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043081.png" /> prime [[#References|[a5]]]; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043082.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043083.png" /> [[#References|[a1]]]). The latter construction is of particular interest in view of its connection with Kerdock and Preparata codes (cf. [[Kerdock and Preparata codes|Kerdock and Preparata codes]]) and their linearity as codes over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043084.png" />, see [[#References|[a3]]]. More sequences with good correlation properties where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043085.png" /> is not a prime number can be constructed. In these constructions, sequences over Galois rings instead of finite fields are converted via homomorphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043086.png" /> into complex-valued sequences. A systematic investigation of shift register sequences over rings can be found in [[#References|[a6]]].

Other important classes of sequences with good correlation properties are bent function sequences, [[#References|[a8]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Boztas,   A.R. Hammons,   P.V. Kumar,   "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043087.png" />-phase sequence with near optimum correlation properties"  ''IEEE Trans. Inform. Th.'' , '''38'''  (1992)  pp. 1101–1113</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S.W. Golomb,   "Shift register sequences" , Aegean Park, Laguna Hills (California)  (1982)  (Edition: Revised)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.R. Hammons,   P.V. Kumar,   A.R. Calderbank,   N.J.A. Sloane,   P. Solé,   "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110430/c11043088.png" />-linearity of Kerdock, Preparata, Goethals, and related codes"  ''IEEE Trans. Information Th.'' , '''40'''  (1994)  pp. 301–319</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  T. Helleseth,   "Some results about the cross-correlation function between two maximal linear sequences"  ''Discrete Math.'' , '''16'''  (1976)  pp. 209–232</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P.V. Kumar,   O. Moreno,   "Prime-phase sequences with periodic correlation properties better than binary sequences"  ''IEEE Trans. Information Th.'' , '''37'''  (1991)  pp. 603–616</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  V.L. Kurakin,   A.S. Kuzmin,   A.V. Mikhalev,   A.A. Nechaev,   "Linear recurring sequences over rings and modules"  ''J. Math. Sci.'' , '''76'''  (1995)  pp. 2793–2915</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  W.H. Mow,   "On the bounds on odd correlation of sequences"  ''IEEE Trans. Information Th.'' , '''40'''  (1994)  pp. 954–955</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J.D. Olsen,   R.A. Scholtz,   L.R. Welch,   "Bent-function sequences"  ''IEEE Trans. Information Th.'' , '''28'''  (1982)  pp. 858–864</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  D.V. Sarwate,   M.B. Pursley,   "Crosscorrelation properties of pseudorandom and related sequences"  ''Proc. IEEE'' , '''68'''  (1980)  pp. 593–619</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  M. Simon,   J. Omura,   R. Scholtz,   B. Levitt,   "Spread Spectrum Communications" , '''I''' , Computer Sci. Press  (1985)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  H.M. Trachtenberg,   "On the cross-correlation functions of maximal recurring sequences"  ''Ph.D. Thesis, Univ. Southern California''  (1970)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  R. Turyn,   J. Storer,   "On binary sequences"  ''Proc. Amer. Math. Soc.'' , '''12'''  (1961)  pp. 394–399</TD></TR></table>