Information Technology Reference
In-Depth Information
Results on the Crosscorrelation and
Autocorrelation of Sequences
Faruk Gologlu
and Alexander Pott
Institute for Algebra and Geometry
Otto-von-Guericke-University
39016 Magdeburg, Germany
goeloglu@student.uni-magdeburg.de, alexander.pott@ovgu.de
Abstract.
Inthispaperweinvestigatesomepropertiesofthecross-
correlation spectrum of an
m
-sequence
a
with period 2
m
−
1anda
d
-decimation
b
. Recently, Lahtonen et. al. [1] calculated the crosscor-
relation value
Θ
d
(1) for specific exponents (i.e. for Gold and Kasami
type). In this paper we generalize this result to all known almost bent
exponents. In [1], the authors also prove that Gold functions are bent on
some hyperplanes with respect to the base field
F
2
. We also generalize
this result and show that Gold functions are bent on all hyperplanes
with respect to any subfield
F
2
k
. We also show that
Θ
d
(1)
=0formany
exponents
d
, and conclude that many sequences of type
a
+
b
(including
m
-sequences added to an almost bent decimation) do not have perfect
autocorrelation.
1
Introduction
Consider binary sequences
a
:= (
a
i
)
,
b
:= (
b
i
) with period
v
, i.e.
a
i
+
v
=
a
i
,b
i
+
v
=
b
i
. Quantifying the similarity between two periodic binary sequences
is important in many applications, and a lot of research has been done on the
analysis of the correlation of sequences. The
crosscorrelation
of a sequence
a
with a sequence
b
at shift
τ
is defined as C
a
,
b
(
τ
):=
i
:=1
(
1)
a
i
+
b
i
+
τ
,
where
−
v
is the period. When the period
v
=2
m
−
1 for some integer
m
,onecanuse
F
q
be the finite field with
q
=2
m
several algebraic tools. Let
F
=
elements.
F
∗
of
is cyclic and has cardinality 2
m
The multiplicative group
F
−
1, and any
binary sequence of period 2
m
[
x
].
The polynomial is called the
trace representation
of the sequence, and has
−
1 can be generated by a polynomial in
F
the form
a
i
:=
Tr
1
β
1
α
d
1
i
+
+
β
s
α
d
s
i
,where
β
j
∈
F
∗
,
α
is a generator
···
,andthetracemap
Tr
k
F
∗
,
d
j
∈{
1
,...,q
−
}
F
2
m
→
F
2
k
defined as
of
1
:
Tr
k
(
α
):=
m
k
−
1
i
=0
α
2
ki
. When we omit the sub- and superscripts it should be
understood that
k
= 1, and we have the so-called absolute trace. Note that the
trace representation is not unique, however one can choose the exponents from
the so-called cyclotomic coset leaders to make the representation unique (see for
instance [2]).
