Information Technology Reference
In-Depth Information
,say
N
, is a factor of 2
n
Then the period of
{
a
t
}
−
1. The discrete Fourier
transform of
a
f
is defined by
2
n
−
2
a
t
α
−tk
,
0
k<
2
n
A
k
=
≤
−
2
(13)
t
=0
and the inverse DFT is
2
n
−
2
Tr
n
k
1
A
k
α
kt
=
(
A
k
α
kt
)
,
0
t<
2
n
a
t
=
≤
−
2
.
(14)
k
=0
k
∈
Γ
(
n
)
By selecting
α
as a root of the primitive polynomial which defines
F
2
n
for com-
puting the DFT of
f
in (8), then we have
k<
2
n
A
k
=
F
k
,
0
≤
−
2
.
Inthefollowing,wekeepthenotation
{
A
k
}
for both
f
and
a
f
, since they are
k<
2
n
equal (with respect to
α
)for1
1 except for
A
0
=
F
0
+
F
2
n
−
1
.
However, this difference does not effect any discussions proceeded in this paper.
Note that the spectral sequence
≤
−
2
n
{
A
k
}
has period
N
|
−
1. Therefore, any
function from
F
2
, or equivalently a boolean function in
n
variables, cor-
responds a binary sequence with period
N
F
2
n
to
2
n
1. Thus a boolean function and
its associate sequence, given by (12), are related by their identical DFT spectra
which results in the same polynomial representation in (10). This leads to an-
other linearized method for finding multipliers
g
of
f
such that
fg
|
−
=0,which
will be shown in the next section.
D. DFT Convolution and Product Sequences
-
Let
a
and
b
be two sequences of period
N
with their respective DFTs
A
=
{
.
-
For the term-by-term product
c
=
a
A
k
}
and
B
=
{
B
k
}
·
b
where
c
t
=
a
t
b
t
,0
≤
t<N
,letthe
DFT of
{
c
t
}
be
C
=
{
C
k
}
.Then
C
is a convolution of
A
and
B
, denoted as
C
=
A
∗
B
where
C
k
=
A
i
B
j
,
0
≤
k<N.
(15)
i
+
j
=
k
(mod
N
)
From the above treatment, we will not distinguish the set
F
n
, the set consist-
ing of all functions from
B
n
, the set of all boolean functions
in
n
variables. For the theory of sequences and their trace representations, the
reader is referred to [14].
F
2
n
to
F
2
and the set
3 Polynomial Bases of
F
n
in Terms of LFSR Sequences
In this section, we introduce polynomial bases of
F
n
after we give a review for
its boolean bases, and show a method for computing those bases in terms of
