Information Technology Reference
In-Depth Information
Table 1.
Binomial coecients, primary sequences and periods
T
i
Binomial coeff.
Primary sequences
T
i
0
S
0
=
{
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
∼}
T
0
=1
1
S
1
=
{
0
,
1
,
0
,
1
,
0
,
1
,
0
,
1
∼}
T
1
=2
2
S
2
=
{
0
,
0
,
1
,
1
,
0
,
0
,
1
,
1
∼}
T
2
=4
3
S
3
=
{
0
,
0
,
0
,
1
,
0
,
0
,
0
,
1
∼}
T
3
=4
4
S
4
=
{
0
,
0
,
0
,
0
,
1
,
1
,
1
,
1
∼}
T
4
=8
5
S
5
=
{
0
,
0
,
0
,
0
,
0
,
1
,
0
,
1
∼}
T
5
=8
6
S
6
=
{
0
,
0
,
0
,
0
,
0
,
0
,
1
,
1
∼}
T
6
=8
7
S
7
=
{
0
,
0
,
0
,
0
,
0
,
0
,
0
,
1
∼}
T
7
=8
...
...
...
In fact, when
n
takes successive values each binomial coecient
i
(
n
0)
defines a
primary sequence
with constant period
T
i
. In Table 1, the first binomial
coecients with their corresponding primary sequences and periods are depicted.
Now the main results concerning generalized self-shrinking sequences and
linear difference equations are introduced.
Theorem 1.
The family of generalized self-shrinking sequences B(a) based on
the m-sequence
≥
i
≥
{
a
n
}
are particular solutions of the homogeneous linear difference
equation:
1)
p
z
n
=0
,
p
=2
L−
1
,
(
E
⊕
(10)
whose characteristic polynomial is
(
x
+1)
p
.
Sketch of proof:
According to [8], the periods of the generalized self-shrinking
sequences
B
(
a
)are
T
1
,
2
,
2
L−
1
∈{
}
. It is a well known fact in binary sequences
[9] that if the period
T
of a binary sequence is a power of 2, then its characteristic
polynomial
f
(
x
)isapowerof(
x
+1).Thus,
f
(
x
)=(
x
+1)
LC
(11)
where
LC
is its linear complexity (the shortest linear recursion satisfied by such
a sequence). At the same time, the linear complexity of a periodic sequence is less
than or equal to its period that is
LC
T
. Therefore, the characteristic poly-
nomial
f
(
x
) of any generalized self-shrinking sequence divides the characteristic
polynomial of (10). In addition, the generalized self-shrinking sequences satis-
fied (10) and consequently they are particular solutions of such an homogeneous
linear difference equation.
≤
Now the characteristics of the sequences that satisfy the previous linear difference
equation are analyzed in detail. According to (9), the solutions of the difference
equation given in (10) are of the form:
z
n
=
n
0
A
0
⊕
n
1
A
1
⊕
A
p−
1
,
n
...
⊕
n
≥
0
(12)
p
−
1
Search WWH ::
Custom Search