Research of Weikang Qian

From The Circuits and Biology Lab at UMN
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

(My research while at UMN.)

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?

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

title: Synthesizing Logical Computation on Stochastic Bit Streams
authors: Weikang Qian and Marc Riedel
submitted to: Communications of the ACM Research Highlight.

Pdf.jpg
Paper

title: An Architecture for Fault-Tolerant Computation with Stochastic Logic
authors: Weikang Qian, Xin Li, Marc Riedel, Kia Bazargan, and David Lilja
appeared in: IEEE Transactions on Computers, vol. 60, no. 1, pp. 93-105, 2011.

Pdf.jpg
Paper

title: The Synthesis of Robust Polynomial Arithmetic with Stochastic Logic
authors: Weikang Qian and Marc Riedel
presented at: Design Automation Conference, Anaheim, CA, 2008

Pdf.jpg
Paper

Ppt.jpg
Slides

title: Uniform Approximation and Bernstein Polynomials with Coefficients in the Unit Interval
authors: Weikang Qian, Marc Riedel, and Ivo Rosenberg
appeared in: European Journal of Combinatorics, vol. 32, no. 3, pp. 448-463, 2011.

Pdf.jpg
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.

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

title: Transforming Probabilities with Combinational Logic
authors: Weikang Qian, Marc Riedel, Hongchao Zhou, and Jehoshua Bruck
will appear in: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.

Pdf.jpg
Paper

title: The Synthesis of Combinational Logic to Generate Probabilities
authors: Weikang Qian, Marc Riedel, Kia Bazargan, and David Lilja
presented at: International Conference on Computer-Aided Design, San Jose, 2009
nominated for IEEE/ACM William J. McCalla ICCAD Best Paper Award

Pdf.jpg
Paper

Ppt.jpg
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 minterms and having a sum-of-product expression with the minimum number of products.

The 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

title: Two-Level Logic Synthesis for Probabilistic Computation
authors: Weikang Qian and Marc Riedel
presented at: International Workshop on Logic and Synthesis, Irvine, CA, 2010

Pdf.jpg
Paper

Ppt.jpg
Poster

title: Synthesizing Cubes to Satisfy a Given Intersection Pattern
authors: Weikang Qian and Marc Riedel
presented at: International Workshop on Logic and Synthesis, Irvine, CA, 2010

Pdf.jpg
Paper

Ppt.jpg
Slides