Information Technology Reference
In-Depth Information
sub-sequence is associated to an automaton. Then, the generation of the
d
sub-
sequences of
S
uses
d
automata which operate in parallel. Parallelism has two
benefits, it can increase the throughput or reduce the power consumption of the
automaton generating a sequence.
Throughput —
The throughput
T
of a PRSG is defined by:
T
=
n × f
,with
n
is the number of bits produced every cycle and
f
is the clock frequency of
the PRSG. Usually, we have
n
= 1, which is often the case with LFSRs. The
decimation achieves a very interesting tradeoff for the throughput:
T
d
=
d
×
γf
with 0
<γ
1 the degradation factor of the original automaton frequency. The
decimation provides an improvement of the throughput if and only if
γd >
1.
It is then highly critical to find good automata for the generation of the sub-
sequences. In an ideal case, we would have
γ
=1andthena
d
-decimation would
imply a multiplication of the throughput by
d
.
≤
Power consumption —
The power consumption of a CMOS device can be es-
timated by the following equation:
P
=
C
V
dd
×
f
,with
C
the capacity of
the device and
V
dd
the supply voltage. The sequence decimation can be used
to reduce the frequency of the device by interleaving the sub-sequences. The
sub-sequences generator will be clocked at frequency
γf
d
and the outputs will
be combined with a
d
-input multiplexer clocked at frequency
γf
. The original
power consumption can then be reduced by the factor
×
γ
d
,where
γ
must be close
to 1 to guarantee that the final representation of
S
is generated at frequency
f
.
The study of the
γ
parameter is out of the scope of this paper since it is
highly related to the physical characteristics of the technology used for the im-
plementation. In the following, we consider
m
-sequences and
-sequences which
are produced respectively by LFSRs and FCSRs.
Throughout the paper, we detail different representations of several automata.
We denote by
x
i
a memory cell and by (
x
i
)
t
the content of the cell
x
i
at time
t
.
The internal state of an automaton at time
t
is denoted by
X
t
.
2.1 LFSRs
An LFSR is an automaton which generates linear recursive sequences. A de-
tailed description of this topic can be found in the monographs of Golomb and
McEliece [15,16]. Let
s
(
x
)=
i
=0
s
i
x
i
define the power series of the sequence
S
=(
s
0
,s
1
,s
2
,...
) produced by an LFSR. Then, there exists two polynomials,
such that
s
(
x
)=
p
(
x
)
q
(
x
)
where
q
(
x
)isthe
connection polynomial
defined by the feedback positions of
the automaton. Let
m
be the degree of
q
(
x
), then the reciprocal polynomial
Q
(
x
)=
x
m
q
(1
/x
)isnamedthe
characteristic polynomial
. An output sequence
of an LFSR is called an
m-sequence
if it has the maximal period of 2
m
1.
This is the case if and only if
q
(
x
) is a primitive polynomial. There exists two
different representations of an LFSR, the so-called Galois and Fibonacci setup,
−
