Information Technology Reference
In-Depth Information
Theorem 6.
Let
b
and
c
be periodic sequences with period
T
.Let
b
and
c
be
the
N
-adic numbers associated with
b
and
c
.Let
d
=
d
0
,d
1
,
···
be the sequence
associated with
b
−
c
.Then
d
is strictly periodic from at least
d
T
on.
Proof.
As noted earlier, the strict periodicity of
b
and
c
implies that there are
integers
g
and
h
so that
b
=
g/
(
N
T
h/
(
N
T
N
T
−
−
1),
c
=
−
−
1), 0
≤
g
≤
−
1,
N
T
and 0
≤
h
≤
−
1. Thus
h
−
g
b
−
c
=
1
.
N
T
−
(
N
T
We either have
−
−
1)
≤
h
−
g
≤
0, in which case
b
−
c
is periodic, or
(
N
T
−
0. In the latter case we just show that adding 1 to a
period
T
sequence results in a sequence that is periodic from position
T
on.
−
1)
<h
−
g
−
1
≤
Consequently, the arithmetic cross-correlation of
b
and
c
can be computed by
computing the first 2
T
bits of the difference
b
c
, and finding the imbalance of
the last
T
of these 2
T
bits. This is a linear time computation in
T
(although not
easily parallelizable as is the case with standard cross-correlations).
−
5 Arithmetic Shift and Add Sequences
It is natural to consider an arithmetic analog of the shift and add property.
In this section we give some basic definitions and characterize the sequences
satisfying the arithmetic shift and add property.
Let
N
≥
2 be a natural number and let
a
=
a
0
,a
1
,
···
be an infinite
N
-ary
sequence. Let
a
=
∞
a
i
N
i
i
=0
be the
N
-adic number associated with
a
. As above, for any integer
τ
let
a
τ
=
a
τ
,a
τ
+1
,
be the left shift of
a
by
τ
positions and let
a
(
τ
)
be the
N
-adic
number associated with
a
τ
. We shall sometimes refer to the left shift of an
N
-
adic number
a
, meaning the
N
-adic number associated with the left shift of the
coecient sequence of
a
A first attempt would be to ask that the set of shifts of
a
be closed under
N
-
adic addition. This is impossible for eventually periodic sequences — multiples of
an
N
-adic number by distinct positive integers are distinct, so there are infinitely
many such multiples. If the set of shifts were closed under addition, all these
multiples of
a
would be shifts of
a
. But there are only finitely many distinct
shifts of an eventually periodic sequence.
The solution is to concern ourselves only with the periodic part of the sum of
two sequences, as we have done in defining arithmetic correlations.
···
Definition 2.
The sequence
a
is said to have the
arithmetic shift and add prop-
erty
if for any shift
τ
0
, either (1) some left shift of
a
+
a
(
τ
)
is zero or (2)
some left shift of
a
+
a
(
τ
)
equals
a
. That is, there is a
τ
so that
(
a
+
a
(
τ
)
)
(
τ
)
=
a
.
≥
