c(0) c(1) -1)
…
Figure 2.1: General model of LFSR used as PRNG
LFSR which was introduced by the authors in
[9],
[19],
[4] as an alternative source of
pseudo–random digital noise in SC system. A general model of LFSR which
is shown in Fig.2.1 includes
n stages (or taps) consecutively connected. At each clock cycle,
a bit will be right–shifted from this state to its next one and one
output bit will be received at the state nth. Note that the first
stage is computed by a linear function of other stages, and normally,
this function is constructed by XOR gates. The chain of XOR gates in
Fig.2.1 is to carry out the
computation of the linear feedback path (or linear feedback function),
i.e. value of s(0), given as
n−1
s(0) = . c(i)s(i) (2.1)
i=0
where c(i) = 0 or 1, i = 1, 2, …,
n−1, are the coefficients of the polynomial which describes the
feedback function. For more clearly, the arrangement of stages for
feedback path in an LFSR can be expressed in F2 or ttF (2)
as a polynomial mod 2. This is called the feedback polynomial. For
instance, given that stages are at the 18th, 17th,
16th, 13th, that such polynomial is
f (x) = x18 +
x17 + x16 + x11 + 1 (2.2)
It is also noted that the initial value of LFSR, called the seed, must
be initialised at the beginning. Because of the use of XOR gate , this
one can be any value instead of 0 for all stages s(i),
i =
0, 1, …, n − 1. Besides, each LFSR has a finite number
of possible states, i.e., enters in a repeating
cycle, due to finite number of taps. Nevertheless, with a well–choosen
feedback polynomial, a LFSR
can generate a sequence of bits which are appear random and have a
suitably long cycle. A LFSR which produce the maximum length, a cycle of
2n − 1, of a LFSR is denoted m–sequence or LFSR with
primitive polnomial. One from
(2.2) is an example for such
polinomial which will generate a sequence of output bits with cycle of
218 − 1.
Classical LFSR approach
In this approach, only one LFSR is considered. The normal behavior of
LFSR is investigated: bits are right–shifted and the output one will be
received at the stage nth at each clock cycle. Therefore, each
m–bit random number is received after m clock cycles.
However, parallel processing is currently essential in the various
applications which requires PRNG generating multiple random number per
cycle. Classical LFSR approach will be not consequently suitable for
this requirement.
Multiple LFSR approach
.
.
.
Figure 2.2: Multiple
LFSR configuration to generate m–bits at each clock cycle
To overcome the drawback of the classical LFSR–based PRNG, the
multipe LFSRs approach was proposed as a solution. In this architecture,
there are m LFSRs which are simultaneously implemented, and
m–bits are obtained at the output at each clock cycle. The
behavior of this configuration is shown in
Fig.2.2. Nevertheless, it deals with the
hardware complexity problem due to the LFSR duplication, as well as the
difficulty in innitializing all LFSRs at the beginning.
Leap–Ahead LFSR approach
m-bit Output
s(0)
…\label{section-7}
Figure 2.3: Leap–Ahead LFSR model
One another solution has been introduced to solve effectively the
hardware complexity in the multiple LFSR approach is
Leap-Ahead LFSR architecture
[24] which is illustrated in
Fig.2.3. In this configu- ration,
only one LFSR is used, and at each clock cycle, m bits from
n taps of LFSR are extracted as the output. First, two
consecutive cycles will be represented as the following formula:
X(t + 1) =
AX(t) (2.3)
where X(t) is the output of all n stages at current
time, X(t + 1) represents their output at next clock
cycle, and A is the transform matrix. However, there are the correlation
between the generated
random numbers in case of using m bits from Xn−m−1 to
Xn due to the inherent characteristic of LFSR. Hence, the
m cycles late output which is partly reduces such correlation can
be received by repeating recurrence equation
(2.3) m times as
X(t + m) =
AX(t + m − 1) = A(AX(t +
m − 2)) = … = AmX(t) (2.4)
where X(t) is the output of all states at current time,
X(t + m) represents the output of them at next
clock cycle, and Am is the transform matrix to obtain m
cycle late output, given by
, (2.5)
C1×n × A
I(n−m)×(n−m) 0(n−m)×m
n×n
where where C1×n is the vectors of coefficients
corresponding to stages of LFSR as shown in
Fig.2.1,
I(n−1)×(n−1) is an identity matrix and
0(n−m)×m is a zero matrix.
Equation 2.4 show that the
correlation between the neighboring random numbers can be effectively
decreased. One thing that must be noted in this architecture is that the
maximum period of the random number generated, given as
[24]: