Namespaces
Variants
Actions

Difference between revisions of "Correlation property for sequences"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (→‎References: latexify)
 
Line 152: Line 152:
  
 
====References====
 
====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>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Boztas,  A.R. Hammons,  P.V. Kumar,  "$4$-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 $\ZZ_4$-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>

Latest revision as of 11:02, 26 March 2023


Complex-valued $ n $- periodic sequences (i.e. sequences $ a = ( a _ {i} ) _ {i = 0 } ^ \infty $ with $ a _ {i + n } = a _ {i} $, $ a _ {i} \in \mathbf C $) with "good" correlation properties have many applications in signal processing (spread spectrum and code division multiple access communication systems, see [a10]). A good survey is [a9]. Periodic sequences are recurring or shift register sequences, see [a2].

If $ a $ and $ b $ are $ n $- periodic sequences, one defines $ C _ {a,b } ( t ) = \sum _ {i = 0 } ^ {n - 1 } a _ {i} { {b _ {i + t } } bar } $. These numbers are called the periodic correlation coefficients (in case $ a = b $, periodic autocorrelation coefficients). Sometimes also the aperiodic correlation $ A _ {a,b } ( t ) = \sum _ {i = 0 } ^ {n - 1 - t } a _ {i} { {b _ {i + t } } bar } $ is of interest. The odd correlation of $ ( a _ {i} ) $ and $ ( b _ {i} ) $ is $ O _ {a,b } ( t ) = A _ {x,y } ( t ) - A _ {x,y } ( t - n ) $, $ t = 1 \dots n $.

The goal is the design of large sets $ {\mathcal S} = \{ a ^ {( 1 ) } \dots a ^ {( m ) } \} $ of $ n $- periodic sequences such that

$$ m ( {\mathcal S} ) = \max \left \{ { \left | {C _ {a ^ {( i ) } ,b ^ {( j ) } } ( t ) } \right | } :\right . $$

$$ \left . {t = 0 \dots n - 1, i,j = 1 \dots s, t \neq 0 \textrm{ if } i = j } \right \} $$

(or the respective value for the aperiodic correlation) is small. Sequences with $ C _ {a,a } ( t ) = 0 $, $ t = 1 \dots n - 1 $, are called perfect. Perfect sequences whose entries are $ t $ th roots of unity ( $ t > 2 $) are known for many periods $ n $, but no example of a $ \pm 1 $- sequence with period $ n > 4 $ is known (the perfect sequence conjecture: there are no perfect binary sequences with $ n > 4 $). In the aperiodic case, the $ \pm 1 $- sequences with odd period $ n $ and aperiodic correlation coefficients $ 0 $ and $ \pm 1 $( Barker sequences) have been classified [a12]. If $ n $ is even, the existence of an $ n $- periodic Barker sequence implies the existence of an $ n $- periodic perfect $ \pm 1 $- sequence.

If one assumes that the sequences are normalized, i.e. $ C _ {a ^ {( i ) } ,a ^ {( i ) } } = n $, then it is known that for $ k \geq 0 $,

$$ m ( {\mathcal S} ) ^ {2k } \geq { \frac{1}{nm ( nm - 1 ) } } \left \{ { \frac{n ^ {2k } ( nm ) ^ {2} }{\left ( \begin{array}{c} {k + n - 1 } \\ {n - 1 } \end{array} \right ) } } - mn ^ {2k + 1 } \right \} $$

and, if the entries of the sequences are just $ \pm 1 $:

$$ m ( {\mathcal S} ) ^ {2} > ( 2k + 1 ) ( n - k ) + { \frac{k ( k + 1 ) }{2} } - { \frac{2 ^ {k} n ^ {2k + 1 } }{m ( 2k ) ! \left ( \begin{array}{c} n \\ k \end{array} \right ) } } $$

for $ 0 \leq k < { {2n } / 5 } $. If the entries of the sequences are $ t $ th roots of unity ( $ t > 2 $), then the bound is

$$ m ( {\mathcal S} ) > { \frac{k + 1 }{2} } ( 2n - k ) - { \frac{2 ^ {k} n ^ {2k + 1 } }{m ( k! ) ^ {2} \left ( \begin{array}{c} {2n } \\ k \end{array} \right ) } } , k \geq 0. $$

The first bound is due to L.R. Welch, the second two bounds are due to V.M. Sidel'nikov. In all cases, $ k $ is an integer. Some improvements of these bounds are known. Similar bounds hold for the maximum odd correlation coefficient [a7].

Important classes of sequences are derived from so-called $ m $- sequences $ ( a _ {i} ) = ( { \mathop{\rm trace} } ( \alpha ^ {i} ) ) $, where $ \alpha $ is a primitive element of the finite field $ { \mathop{\rm GF} } ( q ^ {e} ) $ and $ { \mathop{\rm trace} } ( x ) = \sum _ {i = 0 } ^ {e - 1 } x ^ {q ^ {i} } $. The sequence $ ( a _ {i} ) $ is defined over a finite field. The complex-valued sequences corresponding to such finite field sequences are $ ( \chi ( a _ {i} ) ) $, where $ \chi $ is a homomorphism from the additive group of the field into the multiplicative group of $ \mathbf C $. The $ m $- sequences yield complex sequences with autocorrelation coefficients $ - 1 $. The $ s $- decimation of an $ n $- periodic sequence is $ a _ {s \cdot i ( { \mathop{\rm mod} } n ) } $. Systematic investigations of the correlation properties between $ m $- sequences and their decimations can be found in [a4] and [a11]. The $ m $- 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 $ m $- sequences yield sets of sequences with optimal correlation properties with respect to the Welch and Sidel'nikov bounds: The cases $ m \approx n $ and $ m \approx \sqrt n $ have been investigated intensively. Regarding binary sequences, both the Gold sequences ( $ m = n + 2 = 2 ^ {e} + 1 $) and the Kasami sequences ( $ m = \sqrt {n + 1 } = 2 ^ {e/2 } $) are asymptotically optimal. (One says that a family $ {\mathcal S} _ {n} $ of sets of $ n $- periodic sequences is asymptotically optimal if $ {\lim\limits } _ {n \rightarrow \infty } { {m ( {\mathcal S} _ {n} ) } / {\sqrt n } } = b $, is best possible. If $ | { {\mathcal S} _ {n} } | \approx n $, the lower bounds show that $ b \geq \sqrt 2 $ for binary and $ b \geq 1 $ for arbitrary complex valued sequences. For $ | { {\mathcal S} _ {n} } | \approx \sqrt n $, one has $ b \geq 1 $.) Sequences whose entries are $ t $ th roots of unity ( $ t \neq 2 $) and which are optimal have been constructed ( $ m \approx n $, $ t $ prime [a5]; $ m \approx n $, $ t = 4 $[a1]). The latter construction is of particular interest in view of its connection with Kerdock and Preparata codes (cf. Kerdock and Preparata codes) and their linearity as codes over $ \mathbf Z _ {4} $, see [a3]. More sequences with good correlation properties where $ t $ is not a prime number can be constructed. In these constructions, sequences over Galois rings instead of finite fields are converted via homomorphisms $ \chi $ into complex-valued sequences. A systematic investigation of shift register sequences over rings can be found in [a6].

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

References

[a1] S. Boztas, A.R. Hammons, P.V. Kumar, "$4$-phase sequence with near optimum correlation properties" IEEE Trans. Inform. Th. , 38 (1992) pp. 1101–1113
[a2] S.W. Golomb, "Shift register sequences" , Aegean Park, Laguna Hills (California) (1982) (Edition: Revised)
[a3] A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, P. Solé, "The $\ZZ_4$-linearity of Kerdock, Preparata, Goethals, and related codes" IEEE Trans. Information Th. , 40 (1994) pp. 301–319
[a4] T. Helleseth, "Some results about the cross-correlation function between two maximal linear sequences" Discrete Math. , 16 (1976) pp. 209–232
[a5] 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
[a6] 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
[a7] W.H. Mow, "On the bounds on odd correlation of sequences" IEEE Trans. Information Th. , 40 (1994) pp. 954–955
[a8] J.D. Olsen, R.A. Scholtz, L.R. Welch, "Bent-function sequences" IEEE Trans. Information Th. , 28 (1982) pp. 858–864
[a9] D.V. Sarwate, M.B. Pursley, "Crosscorrelation properties of pseudorandom and related sequences" Proc. IEEE , 68 (1980) pp. 593–619
[a10] M. Simon, J. Omura, R. Scholtz, B. Levitt, "Spread Spectrum Communications" , I , Computer Sci. Press (1985)
[a11] H.M. Trachtenberg, "On the cross-correlation functions of maximal recurring sequences" Ph.D. Thesis, Univ. Southern California (1970)
[a12] R. Turyn, J. Storer, "On binary sequences" Proc. Amer. Math. Soc. , 12 (1961) pp. 394–399
How to Cite This Entry:
Correlation property for sequences. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Correlation_property_for_sequences&oldid=46527
This article was adapted from an original article by D. JungnickelA. Pott (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article