Stochastic switching circuits are relay circuits that consist of stochastic switches called pswitches. The study of stochastic switching circuits has widespread applications in many fields of computer science, neuroscience, and biochemistry. In this paper, we discuss several properties of stochastic switching circuits, including robustness, expressibility, and probability approximation. First, we study the robustness, namely, the effect caused by introducing an error of size Є to each pswitch in a stochastic circuit. We analyze two constructions and prove that simple series-parallel circuits are robust to small error perturbations, while general series-parallel circuits are not. Specifically, the total error introduced by perturbations of size less than Є is bounded by a constant multiple of Є in a simple series-parallel circuit, independent of the size of the circuit. Next, we study the expressibility of stochastic switching circuits: Given an integer q and a pswitch set S = 1 q,2 q,...,q-1 q , can we synthesize any rational probability with denominator q^n (for arbitrary n) with a simple series-parallel stochastic switching circuit? We generalize previous results and prove that when q is a multiple of 2 or 3, the answer is yes. We also show that when q is a prime number larger than 3, the answer is no. Probability approximation is studied for a general case of an arbitrary pswitch set S = s_1, s_2,... , s_(|S|) . In this case, we propose an algorithm based on local optimization to approximate any desired probability. The analysis reveals that the approximation error of a switching circuit decreases exponentially with an increasing circuit size.
There are a number of studies focusing on synthesizing a simple physical device to generate desired probabilities. Gill @cite_3 @cite_14 discussed the problem of generating rational probabilities using a sequential state machine. Motivated by neural computation, provided an algorithm to generate binary sequences with probability @math from a set of stochastic binary sequences with probabilities in @math @cite_8 . Their method can be implemented using the concept of linear feedback shift registers. Recently, inspired by PCMOS technology @cite_13 , considered the synthesis of decimal probabilities using combinational logic @cite_1 . They have considered three different scenarios, depending on whether the given probabilities can be duplicated, and whether there is freedom to choose the probabilities. In contact to the foregoing contributions, we consider the properties and probability synthesis of stochastic switching circuits. Our approach is orthogonal and complementary to that of Qian and Riedel, which is based on combinational logic. Generally, each switching circuit can be equivalently expressed by a combinational logic circuit. All the constructive methods of stochastic switching circuits in this paper can be directly applied to probabilistic combinational logic circuits.
@cite_14 @cite_8 @cite_1 @cite_3 @cite_13
1987683681 2116676915 2013098447 2000617148 2030020312
The paper describes techniques for constructing statistically independent binary sequences with prescribed ratios of zeros and ones. The first construction is a general recursive construction, which forms the sequences from a class of "elementary" sequences. The second construction is a special construction which can be used when the ratio of ones to zeros is expressed in binary notation. The second construction is shown to be optimal in terms of the numbers of input sequences required to construct the desired sequence. The paper concludes with a discussion of how to generate independent "elementary" sequences using simple digital techniques. > Schemes for probabilistic computation can exploit physical sources to generate random values in the form of bit streams. Generally, each source has a fixed bias and so provides bits with a specific probability of being one. If many different probability values are required, it can be expensive to generate all of these directly from physical sources. This paper demonstrates novel techniques for synthesizing combinational logic that transforms source probabilities into different target probabilities. We consider three scenarios in terms of whether the source probabilities are specified and whether they can be duplicated. In the case that the source probabilities are not specified and can be duplicated, we provide a specific choice, the set 0.4, 0.5 ; we show how to synthesize logic that transforms probabilities from this set into arbitrary decimal probabilities. Further, we show that for any integer n ≥ 2, there exists a single probability that can be transformed into arbitrary base-n fractional probabilities. In the case that the source probabilities are specified and cannot be duplicated, we provide two methods for synthesizing logic to transform them into target probabilities. In the case that the source probabilities are not specified, but once chosen cannot be duplicated, we provide an optimal choice. Abstract The purpose of this paper is to show how one random-symbol generator (such as used for implementing Monte Carlo programs or for simulating probabilistic discrete-state systems) can be converted into a different random-symbol generator. Specifically, given the characteristics of an available source and of a desired source, a device is sought which would transform the available source into the desired one, within a prescribed accuracy level. It is shown, constructively, that such a “transformer” can always be realized in the form of a deterministic sequential machine. As a possible realization, a machine is chosen which can be constructed by means of conventional computer components and circuits; it also features adaptability to a wide variety of input, output and accuracy specifications.The characteristics of the machine are described through equations and graphs which facilitate practical design by relating the source specifications to the accuracy and the rate at which the output of the transformer is to be sampled. Also, a method is presented for minimizing the number of states in the machine—a vital step in simplifying the structure and increasing the output rate of the synthesized transformer. Parameter variations, noise susceptibility, and increasing energy dissipation of cmos devices have been recognized as major challenges in circuit and microarchitecture design in the nanometer regime. Among these, parameter variations and noise susceptibility are increasingly causing cmos devices to behave in an “unreliable” or “probabilistic” manner. To address these challenges, a shift in design paradigm from current-day deterministic designs to “statistical” or “probabilistic” designs is deemed inevitable. To respond to this need, in this article, we introduce and study an entirely novel family of probabilistic architectures: the probabilistic system-on-a-chip (psoc). psoc architectures are based on cmos devices rendered probabilistic due to noise, referred to as probabilistic CMOS or PCMOS devices. We demonstrate that in addition to harnessing the probabilistic behavior of pcmos devices, psoc architectures yield significant improvements, both in energy consumed as well as performance in the context of probabilistic or randomized applications with broad utility. All of our application and architectural savings are quantified using the product of the energy and performance, denoted (energy × performance): The pcmos-based gains are as high as a substantial multiplicative factor of over 560 when compared to a competing energy-efficient cmos-based realization. Our architectural design is application specific and involves navigating design space spanning the algorithm (application), its architecture (psoc), and the probabilistic technology (pcmos).