Information Technology Reference
In-Depth Information
mentioned sequences. Section 6 is dedicated to bounds on the aperiodic auto-
correlation. Section 7 extends Section 5 to
r
−
tuples of symbols.
2 Preliminaries
Let
R
=
GR
(2
l
,m
) denote the Galois ring of characteristic 2
l
. It is the unique
Galois extension of degree
m
of
Z
2
l
,with2
lm
elements.
R
=
GR
(2
l
,m
)=
Z
2
l
[
X
]
/
(
h
(
X
))
.
where
h
(
X
) is a basic irreducible polynomial of degree
m
.Let
ξ
be an ele-
ment in
GR
(2
l
,m
) that generates the Teichmuller set
of
GR
(2
l
,m
)which
T
F
0
,
1
,ξ,ξ
2
,...,ξ
2
m
−
2
T
∗
=
reduces to
2
m
modulo 2. Specifically, let
T
=
{
}
and
1
,ξ,ξ
2
,...,ξ
2
m
−
2
.Weusethe
convention
that
ξ
∞
=0
.
The 2-adic expansion of
x
{
}
GR
(2
l
,m
)isgivenby
∈
+2
l−
1
x
l−
1
,
x
=
x
0
+2
x
1
+
···
where
x
0
,x
1
,...,x
l−
1
∈T
.TheFrobeniusoperator
F
is defined for such an
x
as
+2
l−
1
x
l−
1
)=
x
0
+2
x
1
+
+2
l−
1
x
l−
1
,
F
(
x
0
+2
x
1
+
···
···
Z
2
l
,as
and the trace Tr, from
GR
(2
l
,m
)to
m−
1
F
j
.
Tr :=
j
=0
F
F
We also define another trace tr from
2
m
to
2
as
m−
1
x
2
j
.
tr(
x
):=
j
=0
n
2
l
n
2
Throughout this note, we put
n
=2
m
and
R
∗
=
R
Z
→
Z
\
2
R
.LetMSB:
be the most-significant-bit map, i.e.
MSB(
y
)=
y
l−
1
,
where
y
=
y
0
+2
y
1
+
...
+2
l−
1
y
l−
1
∈
Z
2
l
,
is its 2-adic expansion.
3 DFT and the Local Weil Bound
We assume henceforth in the whole paper that
l
≥
3. Let
l
be a positive integer
and
ω
=
e
2
πi/
2
l
C
be a primitive 2
l
-th root of 1 in
.Let
ψ
k
be the additive
Z
2
l
such that
character of
ψ
k
(
x
)=
ω
kx
.