A Caltech Library Service

Transforming Probabilities With Combinational Logic

Qian, Weikang and Riedel, Marc D. and Zhou, Hongchao and Bruck, Jehoshua (2011) Transforming Probabilities With Combinational Logic. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 30 (9). pp. 1279-1292. ISSN 0278-0070.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Riedel, Marc D.0000-0002-3318-346X
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2011 IEEE. Manuscript received September 19, 2010; revised January 14, 2011; accepted March 8, 2011. Date of current version August 19, 2011. This work was supported by a grant from the Focus Center Research Program on Functional Engineered Nano-Architectonics, Semiconductor Research Corporation, under Contract 2003-NT-1107, and a CAREER Award, under Grant 0845650, from the National Science Foundation. This paper was recommended by Associate Editor I. Bahar. The authors would like to thank K. Bazargan and D. Lilja for their contributions. They were co-authors on a preliminary version of this paper [16].
Funding AgencyGrant Number
Semiconductor Research Corporation2003-NT-1107
Subject Keywords:Logic synthesis; probabilistic logic; probabilistic signals; random bit streams; stochastic bit streams
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12181857
Issue or Number:9
Record Number:CaltechAUTHORS:20110922-104607230
Persistent URL:
Official Citation:Weikang Qian; Riedel, M.D.; Hongchao Zhou; Bruck, J.; , "Transforming Probabilities With Combinational Logic," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.30, no.9, pp.1279-1292, Sept. 2011 doi: 10.1109/TCAD.2011.2144630 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:25397
Deposited By: Tony Diaz
Deposited On:27 Sep 2011 21:59
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page