Stochastic Switching Circuit Synthesis

Wilhelm, Daniel and Bruck, Jehoshua (2009) Stochastic Switching Circuit Synthesis. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2008.ETR089]

Full text available as:

	PDF - Requires Adobe Acrobat Reader or other PDF viewer.
	PDF (Revised, 19 May 2009) - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

In his 1938 Master’s Thesis, Shannon demonstrated that any Boolean function can be realized by a switching relay circuit, leading to the development of deterministic digital logic. Here, we replace each classical switch with a probabilistic switch (pswitch). We present algorithms for synthesizing circuits closed with a desired probability, including an algorithm that generates optimal size circuits for any binary fraction. We also introduce a new duality property for series-parallel stochastic switching circuits. Finally, we construct a universal probability generator which maps deterministic inputs to arbitrary probabilistic outputs. Potential applications exist in the analysis and design of stochastic networks in biology and engineering.

EPrint Type:	Monograph (Technical Report)
Additional Information:	Daniel Wilhelm was supported by the U.S. Department of Homeland Security (DHS) Scholarship and Fellowship Program, administered by the Oak Ridge Institute for Science and Education (ORISE). Also available http://www.paradise.caltech.edu/papers/etr089.pdf
Subjects:	All Records
ID Code:	118
Deposited By:	Caltech Library System
Deposited On:	11 September 2008
Record Number:	CaltechPARADISE:2008.ETR089
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2008.ETR089
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record