Information Technology Reference
In-Depth Information
One can also consider the correlation of a sequence with itself. The
auto-
correlation
of a sequence is the crosscorrelation of the sequence with itself,
and defined as follows. A
a
(
τ
):=
v
1)
a
i
+
a
i
+
τ
.NotethatA
a
(0) =
v
.Ifthe
i
:=1
(
−
A
a
:=
{
A
a
(
τ
):
τ
∈{
0
,...,v
−
}}
−
autocorrelation spectrum
1
and
v
, then the sequence
a
is said to be a sequence with
perfect autocorre-
1
, consists of
lation
. For instance
m
-sequences, which are defined to be
a
i
:=
Tr
βα
i
,with
β
F
∗
, have perfect autocorrelation. There are many
known types of perfect autocorrelation sequences when the period is 2
m
∈
F
∗
,and
α
a generator of
1. It
is not known whether the following list of perfect autocorrelation sequences is
complete:
m
-sequences, Dillon-Dobbertin-sequences [3], Legendre-sequences [4],
twin-prime-sequences [4], GMW-construction [2].
Let us return to the discussion of the crosscorrelation. The crosscorrelation
of an
m
-sequence
a
with a decimation
b
, (i.e.
b
i
:=
a
di
) is well studied [5,6].
Note that neither the crosscorrelation spectrum nor
C
a
,
b
(1) depends on the
choice of the primitive element
α
.When
i
runs through
−
,then
α
i
{
1
,...,q
−
1
}
:
C
a
,
b
(
τ
)=
q−
1
1)
Tr
(
α
di
+
α
i
+
τ
)
=
F
∗
of
runs through all nonzero elements
F
i
:=1
(
−
1+
x∈
F
1)
Tr
(
x
d
+
βx
)
,
where
β
=
α
τ
. In this paper we will be interested
in
Θ
d
(
β
)=
x∈
F
−
(
−
1)
Tr
(
x
d
+
βx
)
,
which satisfy
C
a
,
b
(
τ
)+1 =
Θ
d
(
α
τ
),
1
for the
chosen
α
.When
d
has some specific values it was proved that (for odd
m
)the
crosscorrelation function is optimal (i.e.
max
α∈
F
{
(
−
is minimal), and it has
a 3-valued spectrum. These pairs of sequences are called
preferred pairs
and
they satisfy:
Θ
d
(
α
)
Θ
d
(
α
)
}
2
(
m
+1)
/
2
.
Note also that the crosscorrelation spectrum of
d
-th decimation is basically the
Walsh spectrum of the function
f
:
∈{
0
,
±
}
for all
α
∈
F
x
d
.Wedenotethe
Wal sh
F
→
F
,x
→
transform
of a function at (
β, γ
)by
W
f
(
β, γ
):=
x∈
F
1)
Tr
(
βf
(
x
)+
γx
)
.
When
we are dealing with monomials we will abuse the notation and write
W
f
(
γ
)in-
stead of
W
f
(1
,γ
). The functions above with optimal 3-valued Walsh spectra are
called
almost bent (AB)
. The functions
f
:
(
−
F
→
F
for which the derivatives
have cardinality 2
m−
1
are called
almost perfect
nonlinear (APN)
. AB functions are necessarily APN. Known AB exponents are:
{
f
(
x
)+
f
(
x
+
α
):
x
∈
F
}
-Gold:
2
e
+1,where
gcd
(
e, m
)=1,
- Kasami:
2
2
e
2
e
+1,where
gcd
(
e, m
)=1,
-Welch:
2
t
+3, where
m
=2
t
+1,
-Niho:
•
−
2
t
+2
t/
2
−
1, if
t
even and
m
=2
t
+1,
2
t
+2
(3
t
+1)
/
2
•
−
1, if
t
odd and
m
=2
t
+1.
In this paper the sets
Gold
,
Kasami
,
Welch
and
Niho
will denote the sets of
exponents which are AB in
of the mentioned type. The reader can consult [7]
for more on AB and APN functions.
We need some elementary results on finite fields. For more on finite fields, the
reader can consult [8,9]. The
cyclotomic coset
containing
α
F
∈
F
is defined as:
θ
d
(
β
)=
x
∈
F
∗
(
−
1)
Tr
(
x
d
+
βx
)
. In this paper we have
1
In the literature, generally,
Θ
d
(
β
)=
θ
d
(
β
)+1.
