Information Technology Reference
In-Depth Information
Now we treat
ψ
r
1
(
S
)and
ψ
r
1
(
S
i,j,k,l
) as the first periods of 2
n−r
1
-periodic
binary sequences
S
and
S
i,j,k,l
, respectively, that differ at 2 positions. With
this notation, from equations (18) and (19) we have
S
=(
ψ
r
1
(
S
))
∞
,
S
i,j,k,l
=
(
ψ
r
1
(
S
i,j,k,l
))
∞
,and
S
i,j,k,l
(
x
)=
S
(
x
)+
x
c
1
+
x
c
2
.
(20)
From the procedure of the Games-Chan algorithm, since the left and right halves
are different in the first
r
1
−
2stepsforboth
S
and
S
i,j,k,l
,wehave
m
r
1
−
1
(
S
)=
m
r
1
−
1
(
S
i,j,k,l
)=2
n−
1
+
+2
n−r
1
+1
=2
n
2
n−r
1
+1
.
···
−
(21)
From Lemma 6 and equations (10), (20) and (21) we have
S
,
S
i,j,k,l
∈A
(
L
)wh e
L
=
L
(2
n
2
n−r
1
+1
)
.
−
−
(22)
From equations (7) and (22)
L
satisfies
2
n−r
1
−
2
n−r
2
<L
<
2
n−r
1
−
2
n−r
2
−
1
.
(23)
From Lemma 5 and equation (23), the positions
c
1
and
c
2
in equations (18) and
(20) must be in the form
c
i
=
u
+
g
i
2
n−r
2
,
2
n−r
2
2
r
2
−r
1
0
≤
u
≤
−
1
,
0
≤
g
1
<g
2
≤
−
1
.
(24)
From equations (18) and (24), the four positions, denoted
f
1
,
f
2
,
f
3
,and
f
4
,
where
ψ
r
1
−
1
(
S
)and
ψ
r
1
−
1
(
S
i,j,k,l
)differareoftheform
3
=
c
1
+2
n−r
1
,
f
4
=
c
2
+2
n−r
1
,
f
1
=
c
1
,
2
=
c
2
,
and
(25)
where
c
1
and
c
2
are as in equation (24).
Using equation (25) and the procedure of Games-Chan algorithm, it can be
shown that
i
,
j
,
k
,and
l
should be exclusively in the second form as given in
equation (9). This completes the proof of the theorem.
Remark 1.
The proof of Theorem 2 works even when
r
1
=1and
r
1
<r
2
,thatis
when 2
n−
2
≤ L<
2
n−
1
. In this case we see that the four changes made to obtain
a sequence of the same linear complexity as any given sequence are always in the
second form as in equation (9). Also, from equation (4) we can see that there
exist cases when
r
1
=
r
2
in Theorem 2 when expressing the linear complexity
uniquely as in equation (7).
3 Characterization When
w
H
(2
n
− L
)
=2
In this section we characterize the 2
n
-periodic binary sequences with fixed 2-error
linear complexity when the linear complexity is not of the form 2
n
(2
i
+2
j
),
−
1
≤
i<j
≤
n
−
1, by using the results from the previous section.
A
k
(
L
)thesetof2
n
-periodic binary
sequences with given
k
-error linear complexity
L
and let
2
n
and 1
2
n
,denoteby
For 0
≤
L
≤
≤
k
≤
N
k
(
L
)=
|A
k
(
L
)
|
,the
