Information Technology Reference
In-Depth Information
applying shift and decimation operators to an
m
-sequence. We conclude this
section by pointing out a relationship between the Reed-Muller code and the
sequences with index bounded spectral sequences.
Note that
F
n
can be considered as a linear space of dimension 2
n
over
F
2
when
∈F
n
,
therearetwocommonwaystorepresent
f
as a binary vector of dimension
q
(
q
=2
n
). One is the so-called the boolean bases, reviewed as follow.
Let
f
be of a boolean representation. We list the elements in
F
n
is represented by a binary vector of dimension
q
.For
f
each function in
2
in the same
F
order as the truth table of
f
.Thus,
f
(
x
0
,x
1
,...,x
n−
1
)=(
f
(
t
0
)
,f
(
t
1
)
,...,f
(
t
q−
1
))
,
+
t
i,n−
1
2
n−
1
,
0
where
t
i
=(
t
i,
0
,t
i,
1
,...,t
i,n−
1
)
,t
ij
∈
F
2
with
i
=
t
i,
0
+
t
i,
1
2+
···
≤
i<q.
For
x
=(
x
0
,...,x
n−
1
)and
c
=(
c
0
,...,c
n−
1
)in
2
,wedenote
F
x
c
n−
1
x
c
=
x
c
0
x
c
1
···
n−
1
.
Then, the basis
Δ
of
F
n
, regarded as a linear space over
F
2
, consists of all
monomial terms:
x
c
|
n
2
Δ
=
{
c
∈
F
}
.
Thisbasisisreferredtoasa
boolean basis
of
F
n
.
3.1
Polynomial Bases
Let
f
be of the polynomial form. We use the cyclic multiplicative group of
F
2
n
,
i.e.,
f
(
x
)=(
f
(0)
,f
(1)
,f
(
α
)
,...,f
(
α
2
n
−
2
)) = (
f
(0)
,a
0
,a
1
,...,a
2
n
−
2
)
(16)
where
a
t
=
f
(
α
t
) is defined by (14). Let
Tr
n
1
(
β
k
(
α
i
x
)
k
)
Π
k
=
{
|
,i
=0
,
1
,...,n
k
−
1
}
,β
k
∈
F
2
n
k
(17)
where
n
k
is the size of the coset containing
k
(how to select
β
k
willbegiveninthe
next subsection). Note that
{α
ik
| i
=0
,
1
,...,n
k
−
1
}
is a basis of
F
2
n
k
over
F
2
,
so is
{cα
ik
| i
=0
,
1
,...,n
k
−
1
}
for any nonzero
c ∈
F
2
n
k
. From Proposition 1,
any function in
F
n
can be represented as a sum of the trace monomial terms.
For each trace monomial term
Tr
n
k
1
(
A
k
x
k
), since
A
k
∈
F
2
n
k
,wehave
A
k
=
n
k
−
1
i
=0
c
i
β
k
α
ik
,c
i
∈
F
2
. Using the linear property of the trace function, we have
n
k
−
1
Tr
n
k
1
(
A
k
x
k
)=
Tr
n
k
1
(
c
i
β
k
(
α
i
x
)
k
)
.
i
=0
Thus, we have showed the following result.
