Information Technology Reference
In-Depth Information
Games-Chan Algorithm ([4]).
Let
S
be a 2
n
-periodic binary sequence.
(i) If
S
(2
n
−
1
)
L
=
S
(2
n
−
1
)
R
,then
L
(
S
)=
L
(
S
L
).
(ii) If
S
(2
n
−
1
)
L
=
S
(2
n
−
1
)
R
,then
L
(
S
)=2
n−
1
+
L
(
S
L
+
S
R
).
(iii) Apply the above procedure recursively to the 2
n−
1
-periodic binary se-
quence
S
L
in (i), or the 2
n−
1
-periodic binary sequence
S
L
+
S
R
in (ii).
We make some observations and establish notation we use for the rest of the
section. We note that the procedure of the Games-Chan algorithm as stated
here is executed a total of
n
+ 1 times to compute the linear complexity of any
S
∈A
,n
, the algorithm computes the linear
complexity of a 2
n−i
-periodic binary sequence. Let
ψ
i
(
S
),
i
=0
,
(
L
). In the
i
th step,
i
=0
,
···
,n
,denote
the first period of the 2
n−i
-periodic binary sequence considered in the
i
th step
of the algorithm when run with input sequence
S
.Let
ψ
i
L
(
S
)and
ψ
i
R
(
S
) denote,
respectively, the left and right halves of
ψ
i
(
S
). Let
m
i
(
S
) denote the total value
contributed to
L
(
S
) in the algorithm during the execution from the 0-th step
to the
i
-th step of the algorithm. For any two finite binary sequences of same
length,
S
and
S
,let
d
H
(
S
,
S
) denote the Hamming distance between
S
and
S
. We slightly abuse the notation because we also use
d
H
(
S
,
S
)todenotethe
Hamming distance between the first periods of
S
,
S
∈
···
A
(
L
). The next lemma
follows from the Games-Chan algorithm.
Lemma 6.
Let
S
be a
2
n
-periodic binary sequence. For any
t
integers
r
1
,
···
,r
t
such that
0
<r
1
<r
2
<
···
<r
t
≤
n
, we have
L
(
S
)=2
n
(2
n−r
1
+2
n−r
2
+
+2
n−r
t
)
−
···
(5)
if and only if
ψ
u−
1
L
(
S
)=
ψ
u−
1
R
(
S
)
exactly when
u
∈{
r
1
,
···
,r
t
}
.
(6)
Theorem 2.
Let
S
∈A
(
L
)
where
2
n
(2
n−r
1
+2
n−r
2
)
<L<
2
n
(2
n−r
1
+2
n−r
2
−
1
)
,
−
−
(7)
for some
r
1
,r
2
∈{
2
,
···
,n
−
1
}
satisfying
1
<r
1
≤
r
2
. Then, any sequence
2
n
S
i,j,k,l
∈A
1
, if and only if the positions
i
,
j
,
k
,and
l
are in exactly one of the following two forms.
(i) For any
i, j
(
L
)
,
0
≤
i, j, k, l
≤
−
,set
k
=(
i
+
m
1
2
n−r
1
+1
)mod2
n
∈{
0
,
···
,
2
n
−
1
}
l
=(
j
+
m
2
2
n−r
1
+1
)mod2
n
,
and
(8)
2
r
1
−
1
where
1
≤
m
1
,m
2
≤
−
1
.
(ii) For any
t
∈{
0
,
···
,
2
n
−
}
,set
i
=(
t
+
b
1
2
n−r
1
+1
)mod2
n
,
j
=(
t
+
g
2
n−r
2
+
b
2
2
n−r
1
+1
)mod2
n
,
k
=(
t
+2
n−r
1
+
b
3
2
n−r
1
+1
)mod2
n
,
and
l
=(
t
+
g
2
n−r
2
+2
n−r
1
+
b
4
2
n−r
1
+1
)mod2
n
,
where
1
(9)
2
r
2
−r
1
2
r
1
−
1
1
≤
g
≤
−
1
,
0
≤
b
1
,b
2
,b
3
,b
4
≤
−
1
.
