Information Technology Reference
In-Depth Information
-Sequences of Lengths 2
2
k
−
1and2
k
−
m
1with
at Most Four-Valued Cross Correlation
Tor Helleseth and Alexander Kholosha
The Selmer Center
Department of Informatics, University of Bergen
P.O. Box 7800, N-5020 Bergen, Norway
{
Tor.Helleseth, Alexander.Kholosha
}
@uib.no
Abstract.
Considered is the distribution of the cross correlation be-
-sequences of length 2
m
−
tween
-sequences of
a shorter length 2
m/
2
−
1. Pairs of this type with at most four-valued cross
correlation are found and the complete correlation distribution is deter-
mined. These results cover the two-valued Kasami case and all three-
valued decimations found earlier. Conjectured is that there are no other
cases leading to at most four-valued cross correlation apart from the ones
proven here and except for a single, seemingly degenerate, case.
m
1, where
m
is even, and
m
Keywords:
m
-sequences, cross correlation, linearized polynomials.
1
Introduction and Preliminaries
Let
be two binary sequences of length
p
. The cross-correlation
function between these two sequences at shift
τ
,where0
{
a
t
}
and
{
b
t
}
≤
τ<p
, is defined by
p−
1
1)
a
t
+
b
t
+
τ
C
(
τ
)=
(
−
.
t
=0
Recently, Ness and Helleseth [1] studied the cross correlation between any
m
-
sequence
of length
p
=2
m
{
s
t
}
−
1andany
m
-sequences
{
u
dt
}
of shorter length
2
m/
2
1, where
m
is even and gcd(
d,
2
m/
2
is se-
lected to be the
m
-sequence used in the small Kasami sequence family. The only
known families of
m
-sequences of these periods giving a two-valued cross corre-
lation are related to the Kasami sequences [2] and are obtained taking
d
=1.
Further, families with three-valued cross correlation have been constructed by
Ness and Helleseth in [1] and [3]. These results were generalized by Helleseth,
Kholosha and Ness [4] who covered all known cases of three-valued cross corre-
lation and conjectured that these were the only existing. The first family with
four-valued cross correlation was described in [5].
In this paper, we consider pairs of sequences with at most four-valued cross
correlation. We completed a full search for all values of
m
−
−
1) = 1. For convenience,
{
u
t
}
≤
32 and revealed a
