-
General model of LFSR used as PRNG
9
-
Multiple LFSR configuration to generate
m–bits at each clock cycle 10
-
Leap–Ahead LFSR model 10
-
A One–dimensional two–neighbor
CA 11
-
Behavior of the mixed rule CA in
which each cell is considered including two virtual
cells: Upper cell and Lower cell
13
-
Histogram of three approaches of
LFSR–based SNG with the expected probability 0.7 .14
-
Empirical CDFs of three approaches
of LFSR–based SNG corresponding to the expected
probability 0.7 15
-
Histogram of three implementation
of CA–based SNG with the expected probability 0.715
-
Histogram of three approaches of
LFSR–based SNG with the expected probability 0.7 .16
-
Empirical CDF of five SNGs relied
on LFSR and CA 17
-
Digital to stochastic converter 17
-
Histogram and statistic parameters
of the output when using Digital to Stochastic con-
verter to generate the
expected probability 0.625 18
-
Binary to stochastic converter
proposed using converters and NAND gates 19
-
Histogram and statistic parameters
of the output when using Variable probability gen-
erator to generate the
expected probability 0.625 20
-
Multiplexer (MUX structure)
includes two ANDs, one NOT and one OR gates 20
-
10–bit Weighted Binary SNG
21
-
Apply 10–bit Weighted Binary SNG
in stochastic computation 22
-
Stochastic scale adder based on
10–bit Weighted Binary SNG in stochastic computation22
-
State transition diagram of FSM
based SNG 24
-
State transition diagram of FSM
based SNG after mapping transition probability into
state of 3 −
tuples 24
-
Histogram and statistic parameters
of the output value when using FSM to generate
in case of injecting different
ratios of soft errors 44
Abstract
Although there are critical requirements in terms of the development of
CMOS technology such as high fault-tolerance possibility, low-cost
implementation, conventional computing is sensitive to meet these
constraints. As a result, an unconventional computing method was
proposed as a solution called Stochastic computing (SC) which is
a novel way of doing computation and representing numbers. Basically,
the bit sequences, which are used to represent information, are
expressed under a probabilistic
form. This form, interpreted by the conventional number p (0
≤ p ≤ 1), is a probability of observing
logic 1 in the bit sequences.
Theoretically, stochastic numbers (SNs) are considered as a Bernoulli
random process [19] which has
the probability of a bit being logic 1 is independent from the values of
any previous bits. Furthermore, the information that SN carries only
depends on the number of bit 1, not on position as conventional binary
number. It is consequently different from traditional ways to express a
number.
It’s important to note that SC was initially introduced as a low cost
alternative in comparison with conventional computing as arithmetic
operation (addition, subtraction, multiplication, division, etc.) can be
simply implemented. Beside that, it also was seen as a method of high
fault–tolerance, especially for soft error come from process
variations. Despite being a reasonable solution for development of
current technology, SC still confronts some drawbacks such as low
accuracy and very long computation time. Consequently, studies or
applications relying on this technique will deal with the trade–off
between the accuracy and processing time. In addition, it must be
considered other problems of SC, such as stochastic number generator
(SNG), stochastic arithmetic, etc.
SC has been studied significantly in many domains, e.g, neural
computation, digital filter, image processing for its potential capacity
to deal with incident defects in nano scale device. Since this approach
has received some initially reliable results, it promises to be an
appealing concern for future research.
The main objective of this Master thesis is to study and design
computing architecture paradigms following the concepts of stochastic
computing. Besides the related concepts will be conducted on, the basic
components will be designed as a VHDL library for FPGA and ASIC.
Considering this unconventional computing, we expect to achieve an
ameanable solution for the issues of the current CMOS technology.
Our work in this thesis is organized as follows. Chapter 1 gives an
overview of stochastic system: related concepts, main components,
principal issues, exist works and recent studies as well as its promised
applications. After that, the most important part in SC,
Stochastic Number Generator (SNG), will be discussed in Chapter 2
by using various approaches based on Linear Feedback Shift
Register (LFSR) and One–Dimensional Cellular Automata (1–D
CA). Chapter 3 continues focusing on the stochastic operators which are
relied on both combinational logic and sequential logic. About the
stochastic applications, edge detection and median filter in image
processing will be considered as case studies in Chapter 4. Eventually,
chapter 5 gives conclusions and perspectives.
Acknowledgement
I would like to express my deep gratitude to Professor Olivier SENTIEYS,
my research supervisor, for his patient guidance, enthusiastic
encouragement and useful critiques of this research work. Fur- thermore,
I would also like to thank Professor Arnaud TISSERAND, for his useful
and constructive recommendations in understanding on random number
generators. My grateful thanks are also ex- tended to Professor Weikang
QIAN and Professor Peng LI for their help in implementing stochastic
functions based on Finite State Machine, and to David H.K. Hoe, who
helped me studying on Stochas- tic Number Generator using Cellular
Automata.
I would also like to extend my thanks to the technicians of CAIRN
Laboratory, especially to Raphael BARDOUX for his assistance on FPGA
implementation and to Nicolas VEYRAT-CHARVILLON for his help on the idea
to stochastic constant generator based on Linear Feedback Shift
Register.
My completion of this project could not have been accomplished without
the support of my classmates, Minh, Tin, Hung, Nejla; and my vietnamese
friends in Lannion. To Benjamin, Albert and Guillaume for helping me in
understanding more french language and for the trips to Rennes in the
master course work.
Finnaly, I wish to thank my family for their support and encouragement
throughout my study in France.
Chapter
1
State of the art in Stochastic computing
Stochastic Computing (SC) was firstly introduced by Gaines
[8] in 1967 as a promissed
alternative in
comparison with conventional computing. In this new way of computation,
any quantity is mapped into the interval [0, 1] or
[−1, 1] by using two mappings Unipolar and
Bipolar which are of particular interest
because they lead to computations similar to those of the conventional
computing. SC’s operators are
also early proposed by using basic logic elements
[8],
[9],
[19]: AND gate for
Multiplication, NOT gate for Invertor, Multiplexer (MUX)
for Addition/Subtraction, etc. A stochastic computer model was
equally introduced, however, it was seen as impractical approach because
SC requires a very long computation time and causes relatively low
accuracy. Nevertheless, the probability in computation has recently been
considered since the current technology trends, in particular CMOS
technology, tend to increase uncertainty in circuit behavior. Therefore,
SC has lately gained attention from reseachers due to its benefits over
conventional computing [4]: