Information Technology Reference
In-Depth Information
=2
m−
1
,
sequence with Singer parameters, then it should be the case that
|
D
|
hence
Θ
d
(1) = 0 should be satisfied.
For the remaining let
s
i
=
Tr
α
i
,t
i
=
Tr
α
di
and
u
i
=
s
i
+
t
i
=
Tr
α
di
+
α
i
,
and
gcd
(
d, q
−
1) = 1. The following relation is also in [13]: A
u
(
τ
)=
−
1+
x∈
F
1)
Tr
(
x
d
+
ψ
d
(
α
τ
)
x
)
,
where
ψ
d
:
F
∗
→
F
(1 +
β
)(1 +
β
d
)
e
(
−
,β
→
and
e
=
d
−
1
,thatis
de
q
1). Note that the values of the autocorre-
lation spectrum of
u
depends on the image of the map
ψ
d
and the kernel of the
crosscorrelation function
Θ
d
.Notealsothat
ψ
d
maps 1 to 0, and
Θ
d
(0) = 0 for
all
d
. Next two proposition follows from these arguments:
−
1
−
≡−
1(mod
q
−
→
x
d
+(
x
+1)
d
e
,
Proposition 1.
[13] Let
φ
d
:
F
\
F
2
→
F
\
F
2
denote the map
x
(1 +
x
)(1 +
x
d
)
e
.Then
Im
(
φ
d
)=
Im
(
ψ
d
)
,where
Im
denotes the image of a map, and
e
=
q
and
ψ
d
:
F
\
F
2
→
F
\
F
2
denote the map
x
→
d
−
1
.
Proposition 2.
The sequence
Tr
α
di
+
α
i
has perfect autocorrelation if and
only if
Θ
d
(1) = 0
and
Im
(
φ
d
)
−
1
−
⊆
Ker
(
Θ
d
)
,where
Ker
denotes the zeroes of a
function.
The following theorem shows that for many
d
and
m
,
Θ
d
(1)
=0.
Theorem 5.
Let
gcd
(
d, q −
1) = 1
,and
F
=
F
2
m
.If
m
is
p
e
,
2
p
e
,or
3
p
e
,where
p
is an odd prime,
e
0
.Then
Θ
d
(1)
=0
.
Proof.
For cases
m
=
p
e
and
m
=3
p
e
, we will make use of Lemma 1. Let
a
i
and
b
i
denote the number of intersecting cosets
/k
,where
k
will be clear
from the context. First consider
m
=
p
e
. We must show
a
e
p
e
+
a
e−
1
p
e−
1
+
|
H
∩
H
d
∩C
k
|
···
+
=2
p
e
−
2
.
If the theorem is not true then again considering modulo
p
we
would have
a
e
p
e
+
a
e−
1
p
e−
1
+
a
1
p
+1
2
p
e
−
2
(mod
p
)and1
2
−
1
(mod
p
),
···
+
a
1
p
+1
≡
≡
which is a contradiction.
Now let
m
=2
p
e
.Notethatif
α
∈
F
4
\
F
2
,then
Tr
1
(
α
)=
p
e
Tr
1
(
α
) = 1, and
∈
F
p
e
,then
Tr
1
(
α
)=2
Tr
1
(
α
) = 0. Hence we should show:
a
e
2
p
e
+
if
α
···
+
a
1
2
p
+2
p
e
=2
2
p
e
2
2(
p
e
−
2
.
The equation modulo
p
is 2
−
1)
≡
≡
1(mod
p
)
,
which
cannot hold.
Finally let
m
=3
p
e
. Now we have to show
a
e
3
p
e
+
+
a
1
3
p
+
a
0
3+
b
e
p
e
+
···
=2
3
p
e
−
2
.
Note that
···
+
b
1
p
+1
|
H
∩C
3
|
=3,whichmeans
a
0
∈{
0
,
1
}
and
2
3(
p
e
−
1)+1
therefore the modulo
p
reduction
a
0
3+1
≡
≡
2(mod
p
)
,
cannot
hold.
Remark 3.
If
m
=4
k
,thenwehaveexponents
d
with
gcd
(
d, q
1) = 1, satisfying
Θ
d
(1) = 0. The theorem covers all odd
m
(resp.
m
=2
k
,
k
odd), for
m<
35
(resp.
m<
30). We believe that there are exponents
d
with
gcd
(
d, q
−
−
1) = 1 in
larger fields like
F
2
35
, satisfying
Θ
d
(1) = 0, that is, we believe the above
theorem is as general as possible.
F
2
30
or
Corollary 3.
If
-
d
is AB, or
-
d
satisfies
gcd
(
d, q
1) = 1
and
m
is
p
e
,
2
p
e
,or
3
p
e
,where
p
is an odd prime
−
and
e
0
,
