SNG
without using
Comparator
\label{sng-without-using-comparator}
In this section, we will implement the SNGs which will investigate
simple logic gates instead of com- parator in generating SNs. The ideas
for this approach was early introduced by Gaines
[9], Brown and Card
[4], and Gupta et al.
[12] in employing the basic
logic elements, such as NANDs,ORs, MUXes,… as well as LFSR. It has
been recently considered by the work in
[21] by using Markov chain
properties to generate any probability in fractional form.
Digital
to Stochastic
Converter
\label{digital-to-stochastic-converter}
.
. . . . . .
\label{section-12}
PRNG PRNG PRNG
tochastic Output
Figure 2.11: Digital to stochastic converter
Based on the implicit feature of a real number when represented by
binary format, Brown and Card
[4] introduced a converter
which generate stochastic sequence from specific binary number. By
considering a real number X in the interval [0, 1]
represented as X = BN −1…B1B0, a binary
number in which
Bi = 0 or 1, and Xreal = 1 .BN 1 +…+
1 .B +
1 .B , a simple circuit for
realizing a binary number
2 − 2N −1 1 2N 0
to stochastic encoding is illustrated in
Fig.2.11. This approach investigates a
chain of weighted adders
(2–input multiplexers). The selection signal in each MUX is
handled by an PRNG which independently generates random bit with
probability 1/2 of observing a bit beging logic 1. These PRNGs
can be LFSR–based PRNG or CA–based PRNG as we previously mentioned. It
can be obviously seen that at each clock cycle, an output probability at
each MUX’s output that is one half of the sum of the
probability from the next early stage in the chain and a conveted bit is
obtained. This idea can be mathematically described as
P (Y = 1) =
1 .
2 . BN −1 +
1
2 .(BN −2 + ….
1 .
2 . (B0 + 0) …
(2.12)
In this configuration, it is essential to use the good PRNGs to receive
a precise result. Hence, we certainly have the accurate stochastic
number in case of ideal random source.
Now we will consider LFSRs as PRNGs in this circuit. Each LFSR includes
10 stage and its feedback path satisfies maximum length condition
(or m–sequence) with a primitive polynomial f
(x) = x9 + x8 + x6 + x5.
8000
7000
6000
5000
4000
3000
2000
1000
0
0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85
Figure 2.12: Histogram and statistic parameters of the output when using
Digital to Stochastic converter to generate the expected
probability 0.625
Fig.2.14 shows statistic parameters
as well as distribution of the stochastic output value when using this
approach to generate probability 0.625. It can be concluded that
this circuit is achieved by its simple structure so as to produce SNs
with a considerable precision when comparing to other methods. Moreover,
this approach trully gives a very high processing speed in comparison
with LFSR–based PRNG. Nevertheless, there is a drawback regarding to
number of PRNGs (random problem is always complicated) used in this
method.
Variable
Probability
Converter
\label{variable-probability-converter}
A similar approach is equally investigated by Gaines
[9]. However, the variation is
in using different
logic elements. By assuming a set of independent random number sources
P = {P1, P2, …} that generate random
bits with probability 1/2 of a bit being 1, the temporary
variables Ti will be considered
as Boolean functions of these sources as
T1 = P1 T2 = P¯1P2
T3 = P¯1P¯2P3
….
Ti = P¯1…P¯i−1Pi, i ∈ N.
(2.13)
It is easy to notice that the property that no more than one of elements
in these variables may be logic 1 at each clock cycle, in another word,
Pi.Pj = 0 for i ƒ= j where i, j ∈ N .
Moreover, each Pi will
generate a random sequence with probability 2−i of observing a
bit being logic 1. This fact reminds
us of paying attention on binary number representation, consequently, in
this context it is given as
Y = B1.T1 +
B2T2 + B3T3 + … (2.14)
where Y is binary variable which represents a generating
probability x = B1B2B3…, a number
in binary number format(Bi = 0 or Bi = 1).