Information Technology Reference
In-Depth Information
By Lemma 1 the linear complexity of any 2
n
-periodic sequence
S
with 2
n−
1
<
L
(
S
)
<
2
n
and
merr
(
S
)=2
m
+1
,
m
∈{
1
,
···
,n
−
2
}
, can be uniquely
expressed as
m
+1
L
(
S
)=2
n
2
n−r
i
,
−
(3)
i
=1
where 1
<r
1
<
n
. From equation (3), the linear complexity of any
2
n
-periodic binary sequence
S
with 2
n−
1
···
<r
m
+1
≤
<L
(
S
)
<
2
n
and
merr
(
S
)
2
m
+1
,
≥
m
∈{
1
,
···
,n
−
2
}
, can be bounded as
m−
1
m
2
n
2
n−r
i
+2
n−r
m
+1
)
<L
(
S
)
<
2
n
2
n−r
i
,
−
(
−
(4)
i
=1
i
=1
for some
r
i
∈{
<r
m
.Wenotethat
the lower bound in inequality (4) can never be less than 2
n−
1
conforming to the
original condition 2
n−
1
<L
(
S
)
<
2
n
. Also, for any sequence
S
satisfying the
inequality (4), we have
merr
(
S
)
2
,
···
,n
}
,
i
=1
···
m
, satisfying 1
<r
1
<
···
2
m
+1
. We also note that the bounds in (4)
are unique in the sense that the linear complexity of any 2
n
-periodic sequence
S
with
merr
(
S
)
≥
2
m
+1
≥
satisfies exactly one inequality of the particular form
given in equation (4).
For a 2
n
-periodic sequence
S
and two integers
i
and
j
with 0
2
n
1,
denote by
S
i,j
the 2
n
-periodic binary sequence with corresponding polynomial
S
i,j
(
x
)=
S
(
x
)+
x
i
+
x
j
. We use the following result by Fu et al. [3] for the main
result of this section.
≤
i, j
≤
−
(
L
)
,where
2
n
2
n−r
<L<
2
n
2
n−r−
1
for
Lemma 5.
For any sequence
S
∈A
−
−
2
n
some
1
≤
r
≤
n
−
2
, and for any integer
0
≤
i
≤
−
1
, the number of sequences
2
n
=
i
,isexactly
2
r
S
i,j
∈A
(
L
)
,where
0
≤
j
≤
−
1
and
j
−
1
corresponding
t
2
n−r
2
r
to all
j
∈{
i
⊕
:1
≤
t
≤
−
1
}
where
⊕
is the operation of addition
modulo
2
n
.
The rest of this section deals with extending Lemma 5 to the case when four
symbols per period are changed. For a 2
n
-periodic binary sequence
S
and four
integers
i, j, k
,and
l
with 0
≤ i, j, k, l ≤
2
n
−
1, denote by
S
i,j,k,l
the 2
n
-periodic
binary sequence with the corresponding polynomial
S
i,j,k,l
(
x
)=
S
(
x
)+
x
i
+
x
j
+
x
k
+
x
l
.
The Games-Chan algorithm [4] is a fast algorithm to compute the linear com-
plexity of a 2
n
-periodic binary sequence, which we use for the rest of this section.
For any
S
∈A
(
L
) with period
S
(2
n
)
=(
s
0
,
···
,s
2
n
−
1
), denote the left and
right halves of
S
(2
n
)
by
S
(2
n
−
1
)
L
,s
2
n
−
1
−
1
)and
S
(2
n
−
1
)
=(
s
0
,
···
=(
s
2
n
−
1
,
···
,s
2
n
−
1
)
.
R
Let
S
L
and
S
R
denote the 2
n−
1
periodic sequences
,s
2
n
−
1
−
1
)
∞
and
S
R
=(
s
2
n
−
1
,
,s
2
n
−
1
)
∞
.
S
L
=(
s
0
,
···
···
