tput
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

LFSR 1

\label{lfsr-1}


. . .

\label{section-1}

LFSR 2

\label{lfsr-2}
.
.
.

LFSR m

\label{lfsr-m}


. . .

\label{section-5}

. . .

\label{section-6}

m-bit Output

\label{m-bit-output}
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}
s(n-m-1)
…\label{section-8}
) s(n-2) s(n-1)
c(0) c(n-m-1) c(n-3) c(n-2) c(n-1)
… … \label{section-9}
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
Am = 
C1×n × A C1×n × A
· · ·
m− 1 m−2


 , (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]:
T =