Information Technology Reference
In-Depth Information
The inverse DFT of
f
is given as follows:
2
n
−
1
F
k
x
k
,x
∈
F
2
n
.
f
(
x
)=
(9)
k
=0
Fact 1
(Lemma 6.3, [14])
F
k
∈
F
2
n
,and
F
2
i
k
=
F
2
i
k
,i
=0
,
1
,...,n
−
1
.
B. Trace Representation.
In the following, we show the trace representation
of boolean functions in terms of their DFT. For doing so, we need the concept
of cyclotomic cosets. A
(cyclotomic) coset
C
s
modulo 2
n
−
1 is defined by
2
n
s
−
1
C
s
=
{
s, s
·
2
,...,s
·
}
,
s
2
n
s
(mod 2
n
where
n
s
is the smallest positive integer such that
s
1). The
subscript
s
is chosen as the smallest integer in
C
s
,and
s
is called the
coset leader
of
C
s
. For example, for
n
= 4, the cyclotomic cosets modulo 15 are:
≡
−
C
0
=
{
0
}
,C
1
=
{
1
,
2
,
4
,
8
}
,C
3
=
{
3
,
6
,
12
,
9
}
,C
5
=
{
5
,
10
}
,C
7
=
{
7
,
14
,
13
,
11
}
where
are coset leaders modulo 15.
We then group monomial terms according to Fact 1, which results in a sum
of trace monomial terms (see Theorem 6.1 [14]).
{
0
,
1
,
3
,
5
,
7
}
Proposition 1.
(Trace Representation of Functions of Boolean
Functions)
Any non-zero function
f
(
x
)
from
F
2
n
to
F
2
can be represented
as
f
(
x
)=
k∈Γ
(
n
)
Tr
n
1
(
F
k
x
k
)+
F
2
n
−
1
x
2
n
−
1
,F
k
∈
F
2
n
k
,F
2
n
−
1
∈
F
2
,x
∈
F
2
n
(10)
where
Γ
(
n
)
is the set consisting of all coset leaders modulo
2
n
−
1
,
n
k
|
n
and
n
k
is the size of the coset
C
k
,and
Tr
n
1
(
x
)
the trace function from
F
2
.
Recall that
w
(
k
) denotes the Hamming weight of a positive integer
k
.If
f
is
a boolean function with degree
deg
(
f
)=
r<n
, from Proposition 1, the trace
representation of
f
is given by
f
(
x
)=
w
(
k
)
≤r
F
2
n
k
to
Tr
n
1
(
F
k
x
k
)
,
(11)
where
F
k
=0foratleastone
k
∈
Γ
(
n
) such that
w
(
k
)=
r
.
C. Relation to DFT of Sequences.
Next we investigate the relationship
between the DFTs of a boolean function and its associated binary sequence.
Let
α
be a primitive element in
F
2
n
. We assume that
f
(0) = 0 (if
f
(0)
=0,
we replace
f
by
g
=
f
−
f
(0) where
g
(0) = 0). We associate
f
with a binary
sequence
a
f
=
{
a
t
}
whose elements are given by
a
t
=
f
(
α
t
)
,t
=0
,
1
,...,
2
n
−
2
.
(12)
