Information Technology Reference
In-Depth Information
A
a
(
τ
)=
T
.Otherwise
a
and
b
(
τ
)
Proof.
If the
τ
shift of
b
equals
a
,then
C
are
,
b
b
(
τ
)
is an integer only
distinct periodic sequences. In particular, by Lemma 2
a
−
a, b
(
τ
)
if
{
.
First we consider the autocorrelation. Let
}
=
{
0
,
−
1
}
Z
(
N
T−τ
c
f,τ
.
N
T
−
1
−
1)
f
S
=
−
N
T
−
1
f
=0
It follows from equation (2) that the expected arithmetic autocorrelation is
E
[
(
τ
)] =
S/N
T
.
By the first paragraph of this proof
a
A
a
A
a
(
τ
)
is an integer only if
a
(
τ
)
−
=
a
.
When it is not an integer, the periodic part of
(
N
T−τ
−
1)
f
−
c
f,τ
N
T
−
1
is the same as the periodic part of
(
N
T−τ
mod
N
T
−
1)
f
−
1
,
N
T
−
1
where we take the reduction modulo
N
T
(
N
T
−
1 in the set of residues
{−
−
(
N
T
2)
,
. In particular, this latter rational number has a strictly
periodic
N
-adic expansion, so we can compute its contribution to
S
by consid-
ering the first
T
coecients.
Let
d
=gcd(
T,T
−
−
3)
,
···
,
−
1
,
0
}
τ
)=gcd(
T,τ
). Then gcd(
N
T
1
,N
T−τ
1) =
N
d
−
−
−
−
1.
Then the set of elements of the form (
N
T−τ
1)
f
mod
N
T
−
−
1isthesameas
the set of elements of the form (
N
d
1)
f
mod
N
T
−
−
1. Thus
Z
(
N
d
.
N
T
−
1
mod
N
T
−
1)
f
−
1
S
=
N
T
−
1
f
=0
Now consider the contribution to
S
from the
i
th term in the expansion in each
element in the sum, say corresponding to an integer
f
. If we multiply
f
by
N
T−i
modulo
N
T
1, this corresponds to cyclically permuting the corresponding
sequence to the right by
T
−
i
places. This is equivalent to permuting to the left
by
i
positions, so the elements in the
i
th place become the elements in the 0th
place. Moreover, multiplying by
N
T−i
is a permutation modulo
N
T
−
−
1, so the
distribution of values contributing to
S
from the
i
th terms is identical to the
distribution of values from the 0th term.
To count the contribution from the 0th position, let
D
=
N
T
−
1
N
d
−
1
v<N
d
1. Then (
N
d
and
f
=
u
+
vD
with 0
<u<D
and 0
≤
−
−
1)
f
mod
N
T
1=(
N
d
1)
u
mod
N
T
1=(
N
d
(
N
T
−
−
−
−
1)
u
−
−
1). Thus
(
N
d
mod
N
T
(
N
d
−
1)
f
−
1
−
1)
u
=
1
−
1
.
(3)
N
T
−
1
N
T
−
