Information Technology Reference
In-Depth Information
the term-by-term addition and multiplication, respectively. The elements 0 or
1 is the all zero or one vector in
2
depending on the context. In particular,
F
2
,1+
T
is the complement of
T
, denoted as
T
.
In this paper, the notation
w
(
s
) represents the Hamming weight of
s
, i.e.,
the number of nonzeros in
s
,where
s
could be a positive integer represented
in a binary form, or a
k
-dimensional binary vector, or a boolean function in
n
variables represented as a binary vector (
f
(
x
0
)
,f
(
x
1
)
,...,f
(
x
2
n
−
1
)) where
x
i
,i
=0
,...,
2
n
if
s
=1
∈
F
2
.
−
1 constitutes all elements in
F
2
is isomorphic to the finite field
F
2
n
, regarded as a linear space
over
F
2
of dimension
n
. Any boolean function can be represented by a polynomial
function from
Note that
F
F
2
n
to
F
2
. For a polynomial function from
F
2
n
to
F
2
,say
f
(
x
)=
2
n
−
1
i
=0
d
i
x
i
,d
i
∈
F
2
n
,the
algebraic degree
of
f
is given by max
i
:
d
i
=0
w
(
i
). In
this paper, the degree of a function
f
from
F
2
always means the degree
of its boolean form or equivalently, the algebraic degree of its polynomial form,
denoted by
deg
(
f
).
F
2
n
to
2.1
Linear Feedback Shift Register (LFSR) Sequences
Let
v
(
x
)=
x
n
+
c
n−
1
x
n−
1
+
···
+
c
1
x
+ 1 be a polynomial over
F
2
. A sequence
a
=
{
a
t
}
is an
LFSR sequence
of degree
n
if it satisfies the following recursive
relation
n−
1
a
n
+
t
=
c
i
a
t
+
i
,t
=0
,
1
,...,
(7)
i
=0
(
a
0
,...,a
n−
1
)isan
initial state
of the LFSR,
v
(
x
) is called a
characteristic
polynomial of
a
,the
reciprocal
of
t
(
x
)isreferredtoasa
feedback polynomial
of
a
, and we also say that
a
is
generated
by
v
(
x
). The
minimal polynomial
of
a
is the characteristic polynomial with the smallest degree. The sequence
a
is
an
m
-sequence
if
v
(
x
)isprimitiveover
F
2
(Golomb, 1954 [13]). For example,
a
= 1001011 is an
m
-sequence of period 7 where
t
(
x
)=
x
3
+
x
+1.
Let
L
denote the (left) shift operator of a sequence
a
, i.e.,
L
a
=
a
1
,a
2
,...
,
L
i
a
=
a
i
,a
i
+1
,...
.A
k
-decimation
of
a
is the sequence
a
(
k
)
=
a
kt
}
t≥
0
,where
the indices are reduced modulo
N
where
N
is the (least) period of
a
.
{
2.2
DFT and Trace Representations of Boolean Functions,
Polynomial Functions, and Sequences
A. DFT of Boolean Functions.
The content of this subsection can be found in
Chapter 6 in [14]. Using the Lagrange interpolation, we may define the (discrete)
Fourier transform of boolean functions through their polynomial forms. Let
f
be
a boolean function in
n
variables in a polynomial form. The
(discrete) Fourier
Transform (DFT)
of
f
is defined as
F
k
=
x∈
F
2
n
[
f
(
x
)+
f
(0)]
x
−k
,k
=0
,
1
,...,
2
n
−
1
.
(8)
