Information Technology Reference
In-Depth Information
Proposition 2.
Any trace monomial term can be represented as a linear com-
bination of functions in
Π
k
for some
k
which is a coset leader modulo
2
n
−
1
,
and the following set is a basis of
F
n
:
Π
=
Π
k
.
(18)
k
∈
Γ
(
n
)
This is referred to as a
polynomial basis
of
F
n
.
Remark 1.
Let
a
k
=
a
kt
}
t≥
0
.Then
a
k
is an LFSR sequence, generated by
f
α
k
,
the minimal polynomial of
α
k
.Let
{
be the DFT of
a
k
.Then
A
k,j
=
A
k
if
j
=
k
0oth rw .
{
A
k,j
}
In other words, the trace representation of
a
can be considered as a direct sum
of the LFSR sequences with irreducible minimal polynomials for which the DFT
sequences of any two of them are orthogonal.
E
cient Computation of the Polynomial Bases of
F
n
3.2
Inthefollowing,weassumethat
a
=
{
a
t
}
is generated by
v
(
x
) which is primitive
over
F
2
of degree
n
, i.e.,
a
is an
m
-sequence of degree
n
. Then the period
a
is
N
=2
n
F
2
n
.Thenwehave
a
t
=
Tr
1
(
βα
t
)
−
1. Let
α
be a root of
v
(
x
)in
∈
F
2
n
.If
a
(
k
)
=
0
,the
k
-decimation of
a
,thenwemaychoose
r
as
the smallest integer such that the
k
-decimation of
L
i
a
is a zero sequence for
i
=0
,
1
,...,r
where
β
1, but the
k
-decimation of
L
r
a
is not a zero sequence. Let
β
k
be the element corresponding to this shift (i.e.,
β
k
in
Π
k
, defined in (17)). For
simplicity, we still denote such a decimation as
a
(
k
)
. Therefore, the elements of
a
(
k
)
are given by
a
kt
=
Tr
n
1
(
β
k
α
kt
)
,t
=0
,
1
,...
,where
n
k
is the size of the
coset
C
k
.Wedenote
−
⎡
⎣
⎤
⎦
a
(
k
)
0
,
0
,
L
a
(
k
)
P
k
=
(19)
.
0
,L
n
k
−
1
a
(
k
)
where
L
i
a
(
k
)
's are regarded as binary vectors of dimension 2
n
1, and each row
corresponds to a function in
Π
k
.Thus,foreach
k
, a coset leader modulo 2
n
−
1,
we only need to compute
a
(
k
)
,therestoftherowsin
P
k
can be obtained by the
shift operator which has no cost. Furthermore,
−
|
Γ
(
n
)
|
, the number of the coset
leaders modulo 2
n
−
1, is equal to the number of the irreducible polynomials
over
F
2
of degrees dividing
n
. Thus, for computing the polynomial basis of
F
n
,
one only need to compute
decimation sequences from
a
, approximately,
2
n
/n
decimation sequences from
a
, in order to get the polynomial basis of
|
Γ
(
n
)
|
F
n
,
compared it with the boolean basis, where we have to compute 2
n
vectors of
dimension 2
n
since there is no computational saving for these evaluations.
