Information Technology Reference
In-Depth Information
correlations. However, we do not as yet know of any significant applications
of arithmetic correlations. Nonetheless, it is worthwhile studying properties of
arithmetic correlations in hope that applications will come.
In previous work we have studied arithmetic auto- and cross-correlations
(defined below) of a class of binary sequences called
-sequences [4,6,7]. The
arithmetic autocorrelations of these sequences were previously studied in the
context of arithmetic coding [9,10]. It is known that the shifted arithmetic au-
tocorrelations of binary
-sequences are identically zero and that the arithmetic
cross-correlations of any two distinct decimations of a binary
-sequence is iden-
tically zero.
In this paper we study the arithmetic correlations of possibly non-binary
sequences. We show that the arithmetic autocorrelations of
-sequences are at
most one for a prime connection integer and at most two for a prime power
connection integer. We also analyze the expected arithmetic auto- and cross-
correlations of sequences with fixed shift. Finally, we define a notion of arithmetic
shift and add sequence, generalizing the classical notion of shift and add sequence
[1,2,3,5], and prove that the arithmetic shift and add sequences are exactly the
-sequences with prime connection integer.
2 Arithmetic Correlations
Let
N
2 be a natural number. In this section we define a with carry analog of
the usual notion of cross-correlations for
N
-ary sequences.
A fundamental tool we use is the notion of
N
-adic numbers
.An
N
-adic num-
ber is a formal expression
≥
a
=
∞
a
i
N
i
,
i
=0
.Theset
ˆ
where
a
i
∈{
Z
n
of
N
-adic numbers forms an
algebraic ring and has been the subject of extensive study for over 100 years [7,8].
The algebra — addition and multiplication — is defined with carries propagated
to higher and higher terms, just as it is for ordinary nonnegative integers, but
possibly involving infinitely many terms. It is easy to see that
0
,
1
,
···
,N
−
1
}
,
i
=0
,
1
,
···
ˆ
Z
n
contains all
rational numbers
u/q
,
u, q
,with
q
relatively prime to
N
and no other rational
numbers. There is a one to one correspondence between
N
-adic numbers and
infinite
N
-ary sequences. Under this correspondence the rational numbers
u/q
with
q
relatively prime to
N
correspond to the eventually periodic sequences. The
rational numbers
u/q
with
q
relatively prime to
N
and
∈
Z
0 correspond to
the (strictly) periodic sequences. If
a
is periodic (resp., eventually periodic) then
we say that the associated
N
-adic number is periodic (resp., eventually periodic).
Note that, unlike power series, the sum and difference of strictly periodic
N
-adic
numbers are eventually periodic but may not be strictly periodic.
Let
a
be an eventually periodic
N
-ary sequence and let
a
=
∞
−
q
≤
u
≤
a
i
N
i
i
=0
