Information Technology Reference
In-Depth Information
Lemma 2 ([3]).
Let
(
L
)
denote, respectively, the number of and the
set of
2
n
-periodic binary sequences with given linear complexity
L
,
0
N
(
L
)
and
A
2
n
.
≤
L
≤
Then
(
L
)=2
L−
1
2
n
.
N
N
≤
L
≤
(0) = 1
and
for
1
2
n
, is equal to the set of
2
n
-periodic binary sequences
S
with the corresponding polynomials
Also,
A
(0) =
{
(0
,
0
,
···
)
}
and
A
(
L
)
,where
1
≤
L
≤
x
)
2
n
−L
a
(
x
)
,
S
(
x
)=(1
−
where
a
(
x
)
is a binary polynomial with
deg(
a
(
x
))
≤
L
−
1
and
a
(1)
=0
.
Recently, using algebraic and combinatorial methods Fu et al. [3] characterized
2
n
-periodic binary sequences with fixed 1-error linear complexity. They derived
some properties on the structure of the set
A
(
L
)thatdealwithtwosymbol
changes in sequences in
(
L
) and used them to obtain the characterization. In
this paper we extend and in some cases generalize those properties to handle four
symbol changes and use them to obtain the characterization of 2
n
-periodic binary
sequences with fixed 2-error or 3-error linear complexity
L
when
w
H
(2
n
A
=2.
Using the characterization we also give the counting function for the number of
2
n
-periodic binary sequences with fixed
k
-error linear complexity
L
for
k
=2
and 3 when
w
H
(2
n
−
L
)
−
L
)
=2.
2 Extended Properties of
A
(
L
)
(
L
)isthesetof2
n
-periodic sequences with fixed linear complex-
We recall that
A
2
n
. For any two 2
n
-periodic sequences
S
1
and
S
2
,let
d
H
(
S
1
,
S
2
)
denote the Hamming distance between the tuples
S
(2
n
)
1
ity
L
,0
≤
L
≤
and
S
(2
n
)
2
. In this sec-
tion we derive some properties of
(
L
) which extend those in Fu et al.'s paper
[3] using the Games-Chan algorithm [4]. First we state two well known related
results on 2
n
-periodic binary sequences.
A
Lemma 3 ([3]).
For any
2
n
-periodic sequence
S
,
L
(
S
)=2
n
if and only if
w
H
(
S
)
is odd.
Lemma 4 ([3]).
For any
2
n
-periodic sequence
S
,if
w
H
(
S
)
is even then
L
1
(
S
)=
L
(
S
)
.If
w
H
(
S
)
is odd, then
L
2
(
S
)=
L
1
(
S
)
<L
(
S
)=2
n
.
We give a generalization of [3, Theorem 1] using a more straightforward ap-
proach. The proof is given in the appendix.
L<
2
n−r
. Then for any
Theorem 1.
For a given
r
∈{
1
,
···
,n
−
1
}
,let
1
≤
two distinct sequences
S
1
,
S
2
∈A
(
L
)
we have
2
r
+1
,
2
n−r−
1
d
H
(
S
1
,
S
2
)=
t
·
for some
t
∈{
1
,
2
,
3
,
···
}
,
2
r
+1
.
which implies
d
H
(
S
1
,
S
2
)
≥
