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