Information Technology Reference
In-Depth Information
where
A
i
∈
GF
(2) are binary coecients,
α
= 1 is the unique root with
multiplicity
p
of the polynomial (
x
+1) ofdegree
r
=1andthe
i
(0
≤
i<p
)
are binomial coecients mod 2. Remark that the sequence
is just the bit-
wise XOR logic operation of primary sequences weighted by the corresponding
coecients
A
i
.
It must be noticed that not all the solutions
{
z
n
}
{
z
n
}
of (10) are generalized
self-shrinking sequences although all generalized self-shrinking sequences are so-
lutions of (10). From (12), particular features of the solution sequences and con-
sequently of the generalized self-shrinking sequences can be easily determined.
All of them are related with the choice of the
p
-tuple (
A
0
,A
1
,A
2
,...,A
p−
1
)of
binary coecients.
Periods of the Solution Sequences
According to Table 1, the periods of the primary sequences are just powers of 2.
Moreover, according to (12)
is the bit-wise XOR of sequences with different
periods all of them powers of 2. Thus, the period of
{
z
n
}
is the maximum period
of the primary sequences involved in (12), that is the
T
i
{
z
n
}
corresponding to the
primary sequence with the greatest index
i
such that
A
i
=0.
Concerning the generalized self-shrinking sequences, we have:
-
A generalized self-shrinking sequence:
{
b
(
G
)
}
= 11111111
∼
,
with period
T
= 1 corresponding to
A
0
=0
,A
i
=0
∀
i>
0in(12).
-
A generalized self-shrinking sequence:
{
b
(
G
)
}
= 01010101
∼
,
i>
1in(12).
-
Different generalized self-shrinking sequences with period
T
=2
L−
1
with period
T
= 2 corresponding to
A
1
=0
,A
i
=0
∀
corre-
sponding to any
A
i
=0(2
L−
2
≤
i<
2
L−
1
)
,A
j
=0
∀
j
≥
2
L−
1
in (12).
Linear Complexity of the Solution Sequences
According to [9], the linear complexity of a sequence equals the number and mul-
tiplicity of the characteristic polynomial roots that appears in its linear recur-
rence relationship. Therefore coming back to (12) and analyzing the coecients
A
i
, the linear complexity of
can be computed. In fact, we have a unique
root 1 with maximal multiplicity
p
.Thus,if
i
is the greatest index (0
≤ i<p
)
for which
A
i
{
z
n
}
= 0, then the linear complexity
LC
of the sequence
{
z
n
}
will be:
LC
=
i
+ 1
(13)
as it will be the multiplicity of the root 1.
Concerning the generalized self-shrinking sequences, the main result related
to their linear complexity can be stated as follows:
Theorem 2.
The linear complexity
LC
of the generalized self-shrinking
sequences with period
T
i
=2
L−
1
satisfies:
2
L−
2
<LC
2
L−
1
.
≤
(14)
Search WWH ::
Custom Search