Information Technology Reference
In-Depth Information
where
z
n
∈
that satisfies the
previous equation. The symbol
E
denotes the shifting operator that operates on
the terms
z
n
of a solution sequence, i.e.
E
j
z
n
=
z
n
+
j
. The coecients
c
j
GF
(2) is the
n
-th term of a binary sequence
{
z
n
}
are
binary coecients
c
j
∈
GF
(2),
r
is an integer and the symbol
⊕
represents the
XOR logic operation. The
r
-degree characteristic polynomial of (3) is:
r
P
(
x
)=
x
r
+
c
j
x
r−j
.
(4)
j
=1
If
P
(
x
) is a primitive polynomial [9] and
α
is one of its roots, then
α, α
2
,α
2
2
,..., α
2
(
r
−
1)
GF
(2)
r
∈
(5)
are the
r
different roots of such a polynomial. In this case, it can be proved [3]
that the solution of (3) is a sequence of the form:
z
n
=
r−
1
A
2
j
α
2
j
n
,
n
≥
0
(6)
j
=0
where
A
is an arbitrary element in
GF
(2)
r
.Thatis
{
z
n
}
is an
m
-sequence [7]
of characteristic polynomial
P
(
x
)andperiod2
r
−
1 whose starting point is
determined by the value of
A
.
Let us generalize the previous difference equations to a more complex type
of linear difference equations whose roots have a multiplicity greater than 1. In
fact, we are going to consider difference equations of the form:
r
(
E
r
⊕
c
j
E
r−j
)
p
z
n
=0
,
n
≥
0
(7)
j
=1
p
being an integer
p>
1. The characteristic polynomial
P
M
(
x
)ofthistypeof
equations is:
r
P
M
(
x
)=
P
(
x
)
p
=(
x
r
+
c
j
x
r−j
)
p
.
(8)
j
=1
In this case, the roots of
P
M
(
x
) are the same as those of the polynomial
P
(
x
),
that is (
α, α
2
,α
2
2
,..., α
2
(
r
−
1)
), but with multiplicity
p
. Now the solutions of (7)
are [3]:
(
n
i
r−
1
z
n
=
p−
1
A
2
j
i
α
2
j
n
)
,
n
≥
0
(9)
i
=0
j
=0
are binomial coecients modulo 2.
In brief, the
n
-th term of a solution sequence
GF
(2)
r
and the
i
where
A
i
∈
{
z
n
}
is the bit-wise XOR logic
r−
1
A
2
j
i
α
2
j
n
}
operation of the
n
-th term of
p
sequences
{
(0
≤
i<p
)weighted
j
=0
by binomial coecients.
Search WWH ::
Custom Search