Information Technology Reference
In-Depth Information
In particular, the contribution to
S
from the 0th position depends only on
u
.
Thus we can count the contributions over all
g
with 0
<u<D
,andthen
multiply by
N
d
1. The contribution from the 0th position for a particular
u
is
given by reducing the right hand side of equation (3) modulo
N
.Wehave
−
(
N
d
−
1)
u
1=(1+
N
T
+
N
2
T
+
)(
N
d
1
−
···
−
1)
u
−
1
N
T
−
≡−
u
−
1mod
N.
(1 +
N
d
+
N
2
d
+
+
N
T−d
)
Since
−
···
≤−
u
−
1
≤−
2, as
u
varies its reduction
exactly
N
d−
1
+
N
2
d−
1
+
modulo
N
takes each value in
{
0
,
1
,
···
,N
−
1
}
···
+
N
T−d−
1
times.
It follows that the contribution to
S
from the sequences that are not equal to
their
τ
shifts is a multiple of 1 +
ζ
+
+
ζ
N−
1
=0.
Thus we need to count the number of sequences that are equal to their
τ
shifts.
These are the sequences whose minimal periods are divisors of
τ
.Ofcoursethe
minimal periods of such sequences are also divisors of
T
,soitisequivalentto
counting the sequences whose minimal period divides
d
.Thenumberofsuch
sequences is exactly
N
d
. Thus the expected autocorrelation is
···
N
d
T
N
T
A
a
E
[
A
(
τ
)] =
.
The derivation of the expected arithmetic cross-correlation uses similar
methods.
Theorem 5.
For any shift
τ
, the second moment of the arithmetic cross-
correlation, averaged over all pairs of sequences
a
and
b
is
(
τ
)
2
]=
T
N
T
+1
−
T
A
a
E
[
C
.
,
b
N
T
Thevarianceis
(
τ
)] =
T
(
N
T
+1)(
N
T
−
T
)
A
a
V
[
C
.
,
b
N
2
T
Proof.
The proof uses methods which are similar to those used in the proof of
Theorem 4.
4 Computing Arithmetic Cross-Correlations
If
b
and
c
are two periodic sequences with associated
N
-adic numbers
b
and
c
,
respectively, then the sequence associated with the difference
b
c
may not be
strictly periodic (although it must be eventually periodic). Thus at first glance
computing the arithmetic cross-correlation of two sequences is problematic. How
many symbols of the difference must be computed before we reach the periodic
part? As it turns out, however, the number of symbols needed is well bounded.
−
