Research of Weikang Qian - Revision history

MarcRiedel at 15:03, 7 July 2023

2023-07-07T15:03:19Z

← Older revision		Revision as of 10:03, 7 July 2023
Line 1:		Line 1:
	~~<sidebar>~~		(My research while at UMN.)
	* Navigation
	** Weikang_Qian\|About Weikang
	** Research_of_Weikang_Qian\|Research
	** Publications_of_Weikang_Qian\|Publications
	** Main_Page\|My ~~Advisor's Group~~
	~~</sidebar>~~
	Most digital circuits are designed to map ''deterministic'' inputs of zero and one to deterministic outputs of zero and one. In my research, I consider an alternative paradigm: digital circuits that operate on '''random Boolean variables'''. A random Boolean variable with probability ''p''		Most digital circuits are designed to map ''deterministic'' inputs of zero and one to deterministic outputs of zero and one. In my research, I consider an alternative paradigm: digital circuits that operate on '''random Boolean variables'''. A random Boolean variable with probability ''p''
	(0 ≤ ''p'' ≤ 1) of being one represents a real-valued number ''p''. Thus, circuits can be viewed as constructs that accept real-valued probabilities as inputs and compute real-valued probabilities as outputs.		(0 ≤ ''p'' ≤ 1) of being one represents a real-valued number ''p''. Thus, circuits can be viewed as constructs that accept real-valued probabilities as inputs and compute real-valued probabilities as outputs.
Line 25:		Line 20:
	{\| style="background:#F0E68C"		{\| style="background:#F0E68C"
	\|- valign="top"		\|- valign="top"
	\| width="100" \| '''title''':		\| width="100" \| '''title''':
	\| width="500"\| [[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf \| Synthesizing Logical Computation on Stochastic Bit Streams]]		\| width="500" \| [[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf \| Synthesizing Logical Computation on Stochastic Bit Streams]]
	\|- valign="top"		\|- valign="top"
	\| '''authors''':		\| '''authors''':
Line 34:		Line 29:
	\| [http://cacm.acm.org/ Communications of the ACM '''Research Highlight'''].		\| [http://cacm.acm.org/ Communications of the ACM '''Research Highlight'''].
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://cadbio.com/wiki/images/6/64/Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://cadbio.com/wiki/images/6/64/Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>		<br>
	[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf \| Paper]]		[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf \| Paper]]
Line 54:		Line 49:
	\| [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5601694 IEEE Transactions on Computers], vol. 60, no. 1, pp. 93-105, 2011.		\| [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5601694 IEEE Transactions on Computers], vol. 60, no. 1, pp. 93-105, 2011.
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://cadbio.com/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://cadbio.com/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>		<br>
	[[Media:Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf \| Paper]]		[[Media:Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf \| Paper]]
Line 95:		Line 90:
	\| [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-51WP38J-1&_user=10&_coverDate=04%2F30%2F2011&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_searchStrId=1678369105&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=057c5b37ffe293c8c2fa1d00b17d26c7&searchtype=a European Journal of Combinatorics], vol. 32, no. 3, pp. 448-463, 2011.		\| [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-51WP38J-1&_user=10&_coverDate=04%2F30%2F2011&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_searchStrId=1678369105&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=057c5b37ffe293c8c2fa1d00b17d26c7&searchtype=a European Journal of Combinatorics], vol. 32, no. 3, pp. 448-463, 2011.
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://cadbio.com/wiki/images/a/ab/Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://cadbio.com/wiki/images/a/ab/Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>		<br>
	[[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf \| Paper]]		[[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf \| Paper]]
Line 124:		Line 119:
	\| [http://tcad.polito.it/ IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems].		\| [http://tcad.polito.it/ IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems].
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://cadbio.com/wiki/images/d/db/Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://cadbio.com/wiki/images/d/db/Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>		<br>
	[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf \| Paper]]		[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf \| Paper]]
Line 152:		Line 147:
	\| nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award'''		\| nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award'''
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://www.cctbio.ece.umn.edu/wiki/images/5/5d/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://www.cctbio.ece.umn.edu/wiki/images/5/5d/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>[[Media:Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf \| Paper]]		<br>[[Media:Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf \| Paper]]
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">[http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>		<span class="plainlinks">[http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
	<br> [http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]		<br> [http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]
Line 181:		Line 176:
	\| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010		\| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://www.cctbio.ece.umn.edu/wiki/images/4/4c/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://www.cctbio.ece.umn.edu/wiki/images/4/4c/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>[[Media:Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf \| Paper]]		<br>[[Media:Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf \| Paper]]
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">[http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>		<span class="plainlinks">[http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
	<br> [http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt Poster]		<br> [http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt Poster]
Line 203:		Line 198:
	\| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010		\| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010
	\|}		\|}
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">		<span class="plainlinks">
	[http://www.cctbio.ece.umn.edu/wiki/images/2/2f/Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>		[http://www.cctbio.ece.umn.edu/wiki/images/2/2f/Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
	<br>[[Media:Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf \| Paper]]		<br>[[Media:Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf \| Paper]]
	\| align=center width="70" \|		\| align="center" width="70" \|
	<span class="plainlinks">[http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>		<span class="plainlinks">[http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
	<br> [http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt Slides]		<br> [http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt Slides]
	\|}		\|}

	<!--== The Synthesis of Stochastic Circuits for Nanoscale Computation ==		<!--== The Synthesis of Stochastic Circuits for Nanoscale Computation ==

Student at 01:58, 7 August 2011

2011-08-07T01:58:48Z

New page

<sidebar>
* Navigation
** Weikang_Qian|About Weikang
** Research_of_Weikang_Qian|Research
** Publications_of_Weikang_Qian|Publications
** Main_Page|My Advisor's Group
</sidebar>
Most digital circuits are designed to map ''deterministic'' inputs of zero and one to deterministic outputs of zero and one. In my research, I consider an alternative paradigm: digital circuits that operate on '''random Boolean variables'''. A random Boolean variable with probability ''p''
(0 ≤ ''p'' ≤ 1) of being one represents a real-valued number ''p''. Thus, circuits can be viewed as constructs that accept real-valued probabilities as inputs and compute real-valued probabilities as outputs.

I consider three topics pertaining to circuit synthesis in this probabilistic domain. The first is how to synthesize circuits that implement arbitrary arithmetic functions. The second is how to synthesize circuits that transform a set of source probabilities into target probabilities. The third is a special case of the second one, in which the source inputs are independent random Boolean variables with probability 0.5.



== The Synthesis of Logical Computation on Random Boolean Variables ==

Logical computation on random Boolean variables implements a function mapping real values into real values. For example, given an input probability ''x'', an inverter will have an output with probability 1-''x''. In this work, I consider a general synthesis problem: how can we implement an arbitrary arithmetic function ''y''=''f''(''x'') by logical computation on random Boolean variables?

[[File:Computation_Random_Boolean_Variable_Example.png|center|frame|Logical computation on random Boolean variables. (a): Given input probability ''x'', an inverter implements the function ''f''(''x'')=1-''x''. (b): A general synthesis problem is how to implement an arbitrary arithmetic function ''y''=''f''(''x'') by logical computation on random Boolean variables.]]

=== Selected Publications ===

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500"| [[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf | Synthesizing Logical Computation on Stochastic Bit Streams]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''' and [[Marc Riedel]]
|- valign="top"
| '''submitted to''':
| [http://cacm.acm.org/ Communications of the ACM '''Research Highlight'''].
|}
| align=center width="70" |

[http://cadbio.com/wiki/images/6/64/Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 
[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf | Paper]]
|}

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf | An Architecture for Fault-Tolerant Computation with Stochastic Logic]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''', [http://www.arctic.umn.edu/people.shtml Xin Li], [[Marc Riedel]], [http://www.ece.umn.edu/users/kia/ Kia Bazargan], and [http://www.arctic.umn.edu/lilja.shtml David Lilja]
|- valign="top"
| '''appeared in''':
| [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5601694 IEEE Transactions on Computers], vol. 60, no. 1, pp. 93-105, 2011.
|}
| align=center width="70" |

[http://cadbio.com/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 
[[Media:Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf | Paper]]
|}

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.pdf | The Synthesis of Robust Polynomial Arithmetic with Stochastic Logic]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''' and [[Marc Riedel]]
|- valign="top"
| '''presented at''':
| [http://www.dac.com/events/eventdetails.aspx?id=77-37 Design Automation Conference], Anaheim, CA, 2008
|}
| align="center" width="70" |
[http://cctbio.ece.umn.edu/wiki/images/0/07/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 [[Media:Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.pdf | Paper]]
| align="center" width="70" |
[http://cctbio.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]
 [http://cctbio.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt Slides]
|}

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf | Uniform Approximation and Bernstein Polynomials with Coefficients in the Unit Interval]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''', [[Marc Riedel]], and [http://dms.umontreal.ca/Professeurs/rosenb/index.html Ivo Rosenberg]
|- valign="top"
| '''appeared in''':
| [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-51WP38J-1&_user=10&_coverDate=04%2F30%2F2011&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_searchStrId=1678369105&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=057c5b37ffe293c8c2fa1d00b17d26c7&searchtype=a European Journal of Combinatorics], vol. 32, no. 3, pp. 448-463, 2011.
|}
| align=center width="70" |

[http://cadbio.com/wiki/images/a/ab/Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 
[[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf | Paper]]
|}

==The Synthesis of Combinational Logic to Generate Probabilities==

In probabilistic computation that requires many different probability values, it is expensive to generate all of the probabilities directly from random sources. In this work, I demonstrate novel techniques for synthesizing combinational logic that transforms a set of source
probabilities into different target probabilities.


[[File:Generate_Probabilities_Example.png|center|frame|Given a set ''S'' of source probabilities {0.4, 0.5}, we can synthesize a combinational circuit to generate an arbitrary ''decimal'' output probability. The example shows how to generate 0.119. Each AND gate performs a multiplication of its input probabilities and each inverter performs a one-minus operation of its input probability.]]

=== Selected Publications ===
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Transforming Probabilities with Combinational Logic]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''', [[Marc Riedel]], [http://paradise.caltech.edu/~hzhou/ Hongchao Zhou], and [http://paradise.caltech.edu/bruck.html Jehoshua Bruck]
|- valign="top"
| '''will appear in''':
| [http://tcad.polito.it/ IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems].
|}
| align=center width="70" |

[http://cadbio.com/wiki/images/d/db/Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 
[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Paper]]
|}

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf | The Synthesis of Combinational Logic to Generate Probabilities]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''', [[Marc Riedel]], [http://www.ece.umn.edu/users/kia/ Kia Bazargan], and [http://www.arctic.umn.edu/lilja.shtml David Lilja]
|- valign="top"
| '''presented at''':
| [http://www.iccad.com/events/eventdetails.aspx?id=106-5-C International Conference on Computer-Aided Design], San Jose, 2009

|- valign="top"
|
| nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award'''
|}
| align=center width="70" |

[http://www.cctbio.ece.umn.edu/wiki/images/5/5d/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 [[Media:Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf | Paper]]
| align=center width="70" |
[http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]
 [http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]
|}

== Two-Level Logic Synthesis for Probabilistic Computation ==

Assuming that we are given independent copies of probabilistic inputs with probability 0.5 of being one, how can we synthesize a ''two-level'' logic circuit that generates an arbitrary target output probability? This problem is equivalent to finding a Boolean function with ''m'' [[wikipedia:Canonical_form_(Boolean_algebra)#Minterms|minterms]] and having a sum-of-product expression with the minimum number of products.

[[File:Karnaugh_Map.png|center|thumb|none|350px|The [[wikipedia:Karnaugh_map|Karnaugh maps]] of two different Boolean functions both containing 7 minterms. (a): The optimal sum-of-product expression contains 3 product terms. (b): The optimal sum-of-product expression contains 2 product terms. Figure (b) gives a Boolean function with the minimum number of products to cover 7 minterms.]]

=== Selected Publications ===
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf |Two-Level Logic Synthesis for Probabilistic Computation]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''' and [[Marc Riedel]]
|- valign="top"
| '''presented at''':
| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010
|}
| align=center width="70" |

[http://www.cctbio.ece.umn.edu/wiki/images/4/4c/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 [[Media:Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf | Paper]]
| align=center width="70" |
[http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]
 [http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt Poster]
|}

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf |Synthesizing Cubes to Satisfy a Given Intersection Pattern]]
|- valign="top"
| '''authors''':
| '''[[Weikang Qian|Weikang Qian]]''' and [[Marc Riedel]]
|- valign="top"
| '''presented at''':
| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010
|}
| align=center width="70" |

[http://www.cctbio.ece.umn.edu/wiki/images/2/2f/Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]
 [[Media:Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf | Paper]]
| align=center width="70" |
[http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]
 [http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt Slides]
|}