Information Technology Reference
In-Depth Information
Some Results on the Arithmetic Correlation of
Sequences
(Extended Abstract)
Mark Goresky
1
,
and Andrew Klapper
2
,
1
Department of Mathematics, Institute for Advanced Study
Princeton, N.J. 08540, USA
http://www.math.ias.edu/~goresky/
2
Department of Computer Science, University of Kentucky,
Lexington, KY 40506-0046, USA
http://www.cs.uky.edu/~klapper/
Abstract.
In this paper we study various properties of arithmetic cor-
relations of sequences. Arithmetic correlations are the with-carry analogs
of classical correlations. Here we analyze the arithmetic autocorrelations
of non-binary
-sequences, showing that they are nearly optimal. We an-
alyze the expected auto- and cross-correlations of sequences with fixed
shift. We study sequences with the arithmetic shift and add property,
showing that they are exactly the
-sequences with prime connection
element.
Keywords:
feedback with carry shift register, pseudo-randomness, cor-
relation, sequences.
1
Introduction
Sequences with good correlation properties are essential ingredients in a wide
range of applications including CDMA systems and radar ranging. On the plus
side, a great deal is known about the design and generation of sequences with
good correlation properties. Unfortunately, we also know that there are funda-
mental limits on the sizes of families of sequences with such properties.
The purpose of this paper is to study properties of an arithmetic or “with-
carry” analog of the classical correlation function. This notion of correlation is
interesting in part because it is known (in the binary case) that they do not
suffer from some of the constraints on families of sequences with good classical
Research partially supported by DARPA grant no. HR0011-04-1-0031.
Parts of this work were carried out while the author visited the Fields Inst. at the
University of Toronto; The Inst. for Advanced Study; and Princeton Universiy. This
material is based upon work supported by the National Science Foundation under
Grant No. CCF-0514660. Any opinions, findings, and conclusions or recommenda-
tions expressed in this material are those of the author and do not necessarily reflect
the views of the National Science Foundation.
