Information Technology Reference
In-Depth Information
be the associated
N
-adic number. For each
i
=0
,
1
,
···
,N
−
1, let
μ
i
be the
number of occurrences of
i
in one complete period of
a
.Let
ζ
=
e
2
πi/N
be a complex primitive
N
th root of 1. Let
N
−
1
μ
i
ζ
i
,
Z
(
a
)=
Z
(
a
)=
i
=0
the
imbalance
of
a
or of
a
.
The periodic sequence
a
is said to be
balanced
if
μ
i
=
μ
j
for all
i, j
.Itis
weakly
balanced
if
Z
(
a
)=0.
For example, let
N
=3and
a
=3
/
5=0+2
3
2
+1
3
3
+2
3
4
+1
·
3+0
·
·
·
·
3
5
+0
. This sequence is periodic with period 4 from the 3
2
term
on. Thus
μ
0
=1,
μ
1
=2,and
μ
2
=1.Wehave
Z
(
a
)=1+2
ζ
+
ζ
2
3
6
+1
3
7
+
·
·
···
=
ζ
.The
sequence is not weakly balanced.
Lemma 1.
If the
N
-ary sequence
a
is balanced, then it is weakly balanced. If
N
is prime, then
a
is balanced if and only if it is weakly balanced.
For any
N
-ary sequence
b
,let
b
τ
be the sequence formed by shifting
b
by
τ
positions,
b
i
=
b
i
+
τ
. The ordinary cross-correlation with shift
τ
of two
N
-ary
sequences
a
and
b
of period
T
is the imbalance of the term by term difference
of
a
and
b
τ
, or equivalently, of the coecient sequence of the difference between
the power series associated with
a
and the power series associated with
b
τ
.In
the binary case this is the number of zeros minus the number of ones in one
period of the bitwise exclusive-or of
a
and the
τ
shift of
b
[2]. The arithmetic
cross-correlation is the with-carry analog of this [6].
Definition 1.
Let
a
and
b
be two eventually periodic sequences with period
T
and let
0
τ<T
.Let
a
and
b
(
τ
)
be the
N
-adic numbers whose coecients are
given by
a
and
b
τ
, respectively. Then the sequence of coecients associated with
a
≤
b
(
τ
)
is eventually periodic and its period divides
T
.The
shifted arithmetic
cross-correlation
of
a
and
b
is
−
A
a
,
b
b
(
τ
)
)
,
C
(
τ
)=
Z
(
a
−
(1)
where the imbalance is taken over a full period of length
T
.When
a
=
b
,the
arithmetic cross-correlation is called the
arithmetic autocorrelation
of
a
and is
denoted
A
a
A
(
τ
)
.
If for all
τ
such that
a
and
b
τ
A
a
,
b
(
τ
)=0,then
a
and
b
are
said to have
ideal arithmetic correlations
. A family of sequences is said to have
ideal arithmetic correlations if every pair of sequences in the family has ideal
arithmetic correlations.
are distinct we have
C
