Besides using Randomizer unit
[18] as an ideal random bit
stream generator, for the purpose of reducing the system cost in
practice, the synthesizing techniques has been recently considered. The
first approach is to synthesize combinational logic that transforms
source probabilities into different target probabilities. Weikang et al.
[20] investigated this
technique in considering three scenarios with respect to the input set
S. Nevertheless, the efficacy of transforming probabilities with
combinational logic is bounded by the cost of the input stochastic
sources. For instance, it is shown in Fig.5 in
[20] that seven independent
input stochastic sequences are required to generate the disired
probability 0.119, i.e, the domination of random sources in
combinational circuit.
As a result, the authors in
[21] has lately proposed a
novel synthesizing approach based on sequential logic or Finite State
Machine (FMS) that emulate Reversible Markov chains. A Markov
chain is defined as a discrete-time stochastic process that satisfies
the following Markov property: given the present state Xn, the
transition probability to the next state Xn+1 depends only on the
present state. This feature is illustrated as
P {Xn+1 = j |Xn = i, Xn−1 =
in−1, …, X0 = i0} = Pij , n ≥
0. (2.16)
Reversible property indicates that Markov chain follows the
Detailed Balance condition that illustrates relation between
stationay probabilities and transition probabilities
[21]:
πiPij = πj Pji, ∀i, j ∈ S, i ƒ= j (2.17)
where S is state space of the system. Saraf et al.
[21] also concluded that the
amenable number of independent input random sources is three.
Therefore, this approach gives the capacity to reduce hardware cost of
random sources (or controllable) used in stochastic system. It is trully
considerable in comparison with the approach relied on combinational
logic.
As an example, we will implement this technique with expected
probability Poutput = 0.7 = 7/10 = a/b, and
allowed number of random sources K = 3. The transition
probability ratios are consequently powers of two upto 2K−1 =
23−1 = 4, and we have
a = 7 = 1 + 2 + 4
b = 10 = 1 + 1 + 2 + 2 + 4.
Hence,
a0 = 1, a1 =
1, a2 = 2, a3 = 2, a4 = 4
Son = {0, 2, 4} =
{0, 3, 4} = … =
{1, 2, 4}.
(2.18)
1/2
0
1/4 0
3/4