Information Technology Reference
In-Depth Information
3
-Sequences
In this section we consider the arithmetic autocorrelations of
-sequences. These
are the arithmetic analogs of m-sequences, a class of sequences that have been
used in many applications. Recall that an m-sequence over a finite field
F
is the
coecient sequence of the power series expansion of a rational function
f
(
x
)
/q
(
x
)
such that the degree of
f
is less than the degree of
q
,
q
is irreducible, and
x
is a
primitive element in the multiplicative group of
F
[
x
]
/
(
q
). It is well known that
the classical shifted autocorrelations of an m-sequence all equal
1. However,
the cross-correlations of m-sequences are only known in a few special cases.
An
N
-ary
-sequence
a
is the
N
-adic expansion of a rational number
f/q
where gcd(
q, N
)=1,
−
q<f<
0(sothat
a
is strictly periodic), and
N
is
a primitive element in the multiplicative group of integers modulo
q
.Thislast
condition means that the multiplicative order of
N
modulo
q
,ord
q
(
N
), equals
φ
(
q
) (Euler's function). In particular it implies that
q
isapowerofaprime
number,
q
=
p
t
. For the remainder of this section we assume that
N
,
a
,
q
,
p
,
t
and
f
satisfy all these conditions.
Quite a lot is known about
-sequences, especially in the binary (
N
=2)case.
For example, we have the following remarkable fact about binary
-sequences [6].
−
Theorem 1.
Suppose the
a
is a binary
-sequence. If
c
and
b
are decimations
of
a
, then the arithmetic cross-correlation of
c
and
b
with shift
τ
is zero unless
τ
=0
and
b
=
c
.
Our goal here is to determine the arithmetic autocorrelations of not necessarily
binary
-sequences. First we look at their imbalances.
Theorem 2.
Let
a
be an
N
-ary
-sequence based on a connection integer
q
=
p
e
,
p
prime,
e
≥
1
.Then
⎧
⎨
≤
2
for all
q
≤
1
if
q
is prime
1mod
N
or
p
e−
1
|
Z
(
a
)
|
≤
1
if
e
≥
2
and either
q
≡
≡
1mod
N
⎩
=0
if
q
is prime and
q
≡
1mod
N
1mod
N
,and
p
e−
1
=0
if
e
≥
2
,
q
≡
≡
1mod
N.
One of the last two cases always holds when
N
=2
.
We can apply this result to estimate the autocorrelations of
-sequences.
Theorem 3.
Let
a
be an
N
-ary
-sequence with period
T
based on a prime
connection integer
q
.Let
τ
be an integer that is not a multiple of
T
.Then
|A
A
a
A
a
(
τ
)
|≤
1
.If
q
≡
1mod
N
,then
A
(
τ
)=0
. This last statement holds when
N
=2
.
Proof.
The
N
-adic number associated with
a
is a fraction
f/q
as above. By
an argument similar to the one in Section 3.1, the arithmetic autocorrelation of
a
with shift
τ
is the imbalance of the rational number
(
N
T−τ
−
−
1)
f
mod
q
,
q
