Information Technology Reference
In-Depth Information
4 Sub-sequences Generators and
-Sequences
This section presents the main contribution of the paper. We apply the two
methods used in the previous section on the case of
-sequences.
Construction using FCSR synthesis.
There exists algorithms based on Euclid's
algorithm [5] or on lattice approximation [4], which can determine the smallest
FCSR to produce
S
d
. These algorithms use the first
k
bits of
S
d
to find
h
and
q
such that
h
/q
is the 2-adic representation of the sub-sequence,
q
<h
0
and gcd(
q
,h
) = 1. Subsequently, we can find the feedback positions and the
initial state of the FCSR in Galois or Fibonacci architecture. The value
k
is in
the range of twice the linear 2-adic complexity of the sequence. For our new
sequence
S
d
,let
h
and
q
define the values found by one of the algorithms
mentioned above. By
T
and
T
, we mean the periods of respectively
S
d
and
S
.
For the period of the decimated sequences, we can make the following state-
ment, which is true for all periodic sequences.
Lemma 1.
Let
S
=(
s
0
,s
1
,s
2
,...
)
be a periodic sequence with period
T
.Fora
given
d>
1
and
0
−
≤
1
,let
S
d
be the decimated sequence with period
T
.
≤
i
≤
d
−
Then, it must hold:
T
T
gcd(
T,d
)
.
(4)
If
gcd(
T,d
)=1
then
T
=
T
.
Proof.
The first property is given by:
s
d
[
j
+
T/gcd
(
T,d
)]+
i
=
s
dj
+
i
+
T
[
d/
gcd(
T,d
)]
=
s
dj
+
i
.
For the case gcd(
T,d
) = 1, there exits
x, y
such that
xT
+
yd
= 1 due to
Bezout's lemma. Since
S
is periodic, we define for any
j<
0and
k
∈
Z
≥
0,
s
j
=
s
k
such that
j
(mod
T
)=
k
. Thus, we can write for any
j
:
s
j
=
s
i
+(
j−i
)
xT
+(
j−i
)
yd
=
s
i
+(
j−i
)
yd
,
s
j
+
T
=
s
i
+(
j−i
)
xT
+
T
xT
+(
j−i
)
yd
+
T
yd
=
s
i
+(
j−i
)
yd
+
T
yd
.
However, since
T
is the period of
S
d
we get:
s
j
+
T
=
s
j
+(
j−i
)
yd
=
s
j
.
Therefore, it must hold that
T
|
T
which together with (4) proves that
T
=
T
if gcd(
T,d
)=1.
In the case of gcd(
T,d
)
>
1,
the real value of
T
might depend on
i
,
e.g.
for
S
being the 2-adic representation of
1
/
19 and
d
=3wehave
T/gcd
(
T,d
)=6,
however, for
S
3
the period
T
= 2 and for
S
3
the period
T
=6.
A critical point in this approach is that the size of the new FCSR can be
exponentially bigger than the original one. In general, we only know that for the
new
q
it must hold that
q
−
2
T
1 . From the previous paragraph we know that
T
can be as big as
T/gcd
(
T,d
). In the case of an
allowable decimation
[20],
i.e.
a decimation where
d
and
T
are coprime, we have more informations:
|
−
