Difference between revisions of "Research"

From The Circuits and Biology Lab at UMN
Jump to: navigation, search
(Computing with Random Bit Streams)
 
(40 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
"''You see things; and you say, 'Why?' But I dream things that never were; and I say, 'Why not?'"––'' '''George Bernard Shaw''' (1856 –1950)
 
"''You see things; and you say, 'Why?' But I dream things that never were; and I say, 'Why not?'"––'' '''George Bernard Shaw''' (1856 –1950)
  
Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be ''inductive'' (as opposed to ''deductive'') and ''conceptual'' (as opposed to ''applied''). A recurring theme is building systems that compute in novel ways with novel types of technology. For a variety of new technologies, knowledge of how to ''analyze'' existing circuit constructs exists; however, systematic techniques for ''synthesizing'' new constructs remain elusive.  
+
Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be ''inductive'' (as opposed to ''deductive'') and ''conceptual'' (as opposed to ''applied''). A recurring theme is building systems that compute in novel or unexpected ways with new and emerging technologies. Often, the task of ''analyzing'' the way things work in a new technology is straightforward; however the task of ''synthesizing'' new computational constructs is more challenging.  
  
==Computing with Molecules==
+
==Computing with Random Bit Streams==
  
''If I can’t create it, I don’t understand it.''–– '''Richard Feynman''' (1918–1988)
+
"''To invent, all you need is a pile of junk and a good imagination.''–– '''Thomas A. Edison''' (1847–1931)
  
The theory of [http://en.wikipedia.org/wiki/Chemical_kinetics reaction kinetics] underpins our understanding of biological and chemical systems. It is a simple and elegant formalism: molecular reactions define ''rules'' according to which reactants form products; each rule fires at a ''rate'' that is proportional to the quantities of the corresponding reactants that are present. Just as electronic systems implement computation in terms of '''voltage''' (''energy per unit charge''), molecular systems compute in terms of '''chemical concentrations''' (''molecules per unit volume''). We are studying techniques for implementing a variety of computational constructs with molecular reactions such as logic, memory, arithmetic, and signal processing.
+
Humans are accustomed to counting in a positional number system &ndash; [http://en.wikipedia.org/wiki/Decimal decimal] radix.  Nearly all computer systems operate on another positional number system &ndash; [http://en.wikipedia.org/wiki/Binary_numeral_system binary] radix. From the standpoint of ''representation'', such positional systems are compact: given a radix ''b'', one can represent ''b<sup>n</sup>'' distinct numbers with ''n'' digits. However, from the standpoint of ''computation'', positional systems impose a burden: for each operation such as addition or multiplication, the signal must be "''decoded''", with each digit weighted according to its position. The result must be "''encoded''" back in positional form. Any student who has designed a [http://en.wikipedia.org/wiki/Binary_multiplier binary multiplier] in a course on [[EE2301 | logic design]] can appreciate all the complexity that goes into wiring up such an operation.
[http://pubs.acs.org/doi/pdfplus/10.1021/ja906987s DNA Strand Displacement] is our experimental chassis.
 
  
The impetus for this research is not computation ''per se''. Molecular computation will never compete with conventional computers made of [http://en.wikipedia.org/wiki/Integrated_circuit silicon integrated circuits] for tasks such as number crunching. Chemical systems are inherently slow and messy, taking minutes or even hours to finish, and producing fragmented results. Rather, the goal is to create “'''embedded controllers'''” &ndash; viruses and bacteria that are engineered to perform useful molecular computation ''in situ'' where it is needed, for instance for drug delivery and biochemical sensing.<br>
+
==== Logic that Operates on Probabilities ====
 +
 
 +
We advocate an alternative representation: random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. For instance, multiplication can be performed with a single AND gate; scaled addition can be performed with a multiplexer (MUX).
  
 
{| align="center"
 
{| align="center"
||[[Image:molecular-reactions-are-rules.gif|center|thumb|300px|Molecular reactions define ''rules'' according to which reactants form products. Here molecules of type A combine with molecules of type B to form molecules of type C, at a rate proportional to the molecular concentrations of A and B as well as a rate constant ''k''.]]
+
| [[Image:stochastic-multiplier.png|center|thumb|350px|'''Multiplication''' with an AND gate. Here the variables represents the ''probabilities'' of obtaining a 1 versus a 0 in stochastic bit streams. The AND gate produces an output probability <math>c</math> that is the product of the of the input probabilities <math>a</math> and <math>b</math>.]]
 
||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 
||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
||[[Image:ecoli-embedded-controller.gif|center|thumb|450px|Molecular computation is applicable to the design of ''embedded controllers'': engineered bacteria and viruses for tasks such as drug delivery.]]
+
|| [[Image:stochastic-adder.png|thumb|320px|'''Scaled addition''' with a multiplexer (MUX).
 +
Given input probabilities <math>a</math>, <math>b</math> and <math>s</math>, the MUX produces an output probability <math>c = a s + (1 - s) b</math>.]]
 
|}
 
|}
  
====Digital Signal Processing====
+
We have developed a general method for synthesizing digital circuitry that computes on such stochastic bit streams. Our method can be used to synthesize arbitrary polynomial functions. Through polynomial approximations, it can also be used to synthesize non-polynomial functions. Because the representation is uniform, with all bits weighted equally, the resulting circuits are highly tolerant of [http://en.wikipedia.org/wiki/Soft_error soft errors] (i.e., bit flips).  
 
 
We have developed a strategy for implementing signal processing with molecular reactions including operations such as filtering. We have demonstrated robust designs for both [http://en.wikipedia.org/wiki/Finite_impulse_response Finite-Impulse Response (FIR)], [http://en.wikipedia.org/wiki/Infinite_impulse_response Infinite-Impulse Response (IIR)] filters, and [http://en.wikipedia.org/wiki/Fast_Fourier_transform Fast Fourier Transforms (FFTs)].
 
[[Image:moving-average-filter-simulation.gif|center|thumb|400px|Simulations of DNA implementation of a '''moving-average FIR filter'''. This filter removes the high-frequency component from an input signal, producing an output signal consisting of only the low-frequency component. Here the "signals" are molecular concentrations.]]
 
 
{|
 
{|
|
+
|  
 
{| style="background:#F0E68C"
 
{| style="background:#F0E68C"
 
|- valign="top"
 
|- valign="top"
 
| width="100" | '''title''':
 
| width="100" | '''title''':
| width="500" | [[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf | Discrete-Time Signal Processing with DNA]]
+
| 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''':
| [[Hua Jiang]], Ahmed Salehi, [[Marc Riedel]] and [http://www.ece.umn.edu/users/parhi Keshab Parhi]
+
| [[Weikang Qian]] and [[Marc Riedel]]
 
|- valign="top"
 
|- valign="top"
| '''to appear&nbsp;in''':
+
| '''appeared as''':
| [http://pubs.acs.org/doi/abs/10.1021/sb300087n ACS Synthetic Biology], 2013.<br>[[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA_Appendix.pdf | Supplementary Information: List of Reactions]]
+
| Techincal Report, UMN
 
|- valign="top"
 
|- valign="top"
| '''appeared&nbsp;in''':
 
| [http://www.computer.org/portal/web/dt IEEE Design & Test of Computers], Vol. 29, No. 3, pp. 21&ndash;31, 2012.
 
|- valign="top"
 
| '''presented at''':
 
| [http://www.iccad.com/ International Conference on Computer-Aided Design], San Jose, CA, 2010.
 
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf http://mriedel.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://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf Paper]
+
<br>
| align=center width="70" |  
+
[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf | Paper]]
<span class="plainlinks">
+
| align="center" width="70" |  
[http://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
+
<span class="plainlinks">[http://mriedel.ece.umn.edu/files/Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx Slides]
+
<br>[http://mriedel.ece.umn.edu/files/Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pptx Slides]
 
|}
 
|}
Please see our "[[Papers,_Theses,_and_Slides |Publications]]" page for more of our papers on these topics.
 
 
====Digital Logic====
 
 
We have developed a strategy for implementing digital logic with molecular reactions. Based on a bistable mechanism for representing bits, we implement a constituent set of logical components, including combinational components such as '''AND''', '''OR''', and '''XOR gates''', as well as sequential components such as '''D latches''' and '''D flip-flops'''. Using these components, we build full-fledged digital circuits such as a ''binary counters'' and a ''linear feedback shift registers''.
 
<!-- All the constructs consist of sets of coupled chemical reactions with only coarsely specified rate categories (“fast” and “slow”). Given such categories, the computation is robust regardless of the specific reaction rates. The designs are validated through simulations of the chemical kinetics. The simulations show that the constructs produce nearly perfect digital signal values.-->
 
[[Image:dna-logic-gates.gif|center|thumb|550px| Simulations of DNA implementation of logic gates. The input signals are molecular concentrations X and Y; the output signal is a molecular concentration Z. (A) AND gate. (B) OR gate. (C) NOR gate. (D) XOR gate.]]
 
 
{|
 
{|
 
|
 
|
Line 62: Line 49:
 
|- valign="top"
 
|- valign="top"
 
| width="100" | '''title''':
 
| width="100" | '''title''':
| width="500" | [[Media:Jiang_Riedel_Parhi_Synchronous_Sequential_Computation_with_Molecular_Reactions.pdf | Synchronous Sequential Computation with Molecular Reactions]]
+
| width="500" | [[Media:Li_Lilja_Qian_Riedel_Bazargan_Logical_Computation_on_Stochastic_Bit_Streams_with_Linear_Finite_State_Machines.pdf | Logical Computation on Stochastic Bit Streams with Linear Finite State Machines]]
 
|- valign="top"
 
|- valign="top"
 
| '''authors''':
 
| '''authors''':
| [[Hua Jiang]], [[Marc Riedel]] and [http://www.ece.umn.edu/users/parhi Keshab Parhi]
+
| [http://www.ece.umn.edu/~lipeng/ Peng Li], [http://www.arctic.umn.edu/lilja.shtml David Lilja], [[Weikang Qian]],[http://www.ece.umn.edu/users/kia/ Kia Bazargan] and [[Marc Riedel]]
|- valign="top"
+
|- valign="top"
 +
| '''appeared in''':
 +
| [http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6307798 IEEE Transactions on Computers], Vol. 63, No. 6., pp. 1474&ndash;1486, 2014
 +
|- valign="top"  
 
| '''presented at''':
 
| '''presented at''':
| [http://www.dac.com/dac+2011+conference+program.aspx Design Automation Conference], San Diego, CA, 2011.
+
| [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6165056 IEEE/ACM Asia and South Pacific Design Automation Conference],<br>Sydney, Australia, 2012
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://cctbio.ece.umn.edu/wiki/images/0/07/Jiang_Riedel_Parhi_Synchronous_Sequential_Computation_with_Molecular_Reactions.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
+
[http://cctbio.ece.umn.edu/wiki/images/7/7c/Li_Lilja_Qian_Riedel_Bazargan_Logical_Computation_on_Stochastic_Bit_Streams_with_Linear_Finite_State_Machines.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br> [http://cctbio.ece.umn.edu/wiki/images/0/07/Jiang_Riedel_Parhi_Synchronous_Sequential_Computation_with_Molecular_Reactions.pdf Paper]
+
<br>
| align=center width="70" |
+
[[Media:Li_Lilja_Qian_Riedel_Bazargan_Logical_Computation_on_Stochastic_Bit_Streams_with_Linear_Finite_State_Machines.pdf | Paper]]
<span class="plainlinks">[http://cctbio.ece.umn.edu/wiki/images/9/9b/Jiang_Riedel_Parhi_Synchronous_Sequential_Computation_with_Molecular_Reactions.pptx http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
 
<br> [http://cctbio.ece.umn.edu/wiki/images/9/9b/Jiang_Riedel_Parhi_Synchronous_Sequential_Computation_with_Molecular_Reactions.pptx Slides]
 
 
|}
 
|}
  
====Arithmetic & Programming Constructs====
+
====Logic that Generates Probabilities====
  
We have developed a strategy for implementing arithmetic with molecular reactions &ndash; operations such as '''increments & decrements''', '''multiplication''', '''logarithms''', and '''exponentiation'''. Try out our [http://cctbio.ece.umn.edu/chem-compiler/chem-compiler.pl compiler]: it translates arbitrary constructs from a '''C-like language''' into a robust implementation with molecular reactions.
+
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 that have a specific probability of being one versus zero. If many different probability values are required, it can be difficult or expensive to generate all of these directly from physical sources. In this work, we demonstrate novel techniques for synthesizing combinational logic that transforms a set of ''source'' probabilities into different ''target'' probabilities.
 +
<!--The problem I consider is: given a set ''S'' of ''n'' probabilistic inputs with probabilities ''p''<sub>1</sub>, ..., ''p''<sub><I>n</I></sub> of being one and a target probability ''q'', how can we synthesize a combinational circuit that takes inputs from the set ''S'' and produces an output with probability ''q'' of being one?-->
  
[[Image:Logo.png|center|700px|thumb|[http://cctbio.ece.umn.edu/chem-compiler/chem-compiler.pl Platypus], a compiler that translates arbitrary constructs from a '''C-like language''' into a molecular reactions.]]
+
[[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 and each inverter performs a "one-minus" operation.]]
  
 
{|
 
{|
Line 90: Line 79:
 
|- valign="top"
 
|- valign="top"
 
| width="100" | '''title''':
 
| width="100" | '''title''':
| width="500" | [[Media:Senum_Riedel_Rate-Independent_Constructs_for_Chemical_Computation.pdf | Rate-Independent Constructs for Chemical Computation]]
+
| width="500" | [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Transforming Probabilities with Combinational Logic]]
|- valign="top"  
+
|- valign="top"
 
| '''authors''':
 
| '''authors''':
| [[Phil Senum]] and [[Marc Riedel]]
+
| [[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 Trans. on Computer-Aided Design of Integrated Circuits and Systems], 2012.
 
|- valign="top"
 
|- valign="top"
| '''appeared in''':
+
| '''presented&nbsp;at''':
| [http://dx.plos.org/10.1371/journal.pone.0021414 PLoS ONE], Vol. 6, No. 6, 2011.<br>[[Rate_Independent_Constructs_Supplementary_Information | Supplementary Information]]
+
| [http://www.iccad.com/events/eventdetails.aspx?id=106-5-C International Conference on Computer-Aided Design], San Jose, 2009<br>(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://cctbio.ece.umn.edu/wiki/images/d/db/Senum_Riedel_Rate-Independent_Constructs_for_Chemical_Computation.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://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br> [http://cctbio.ece.umn.edu/wiki/images/d/db/Senum_Riedel_Rate-Independent_Constructs_for_Chemical_Computation.pdf Paper]
+
<br>
| align=center width="70" |  
+
[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Paper]]
<span class="plainlinks">[http://cctbio.ece.umn.edu/wiki/images/d/d2/Senum_Riedel_Rate-Independent_Modules_for_Chemical_Computation.pptx http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
+
| align="center" width="70" |  
<br> [http://cctbio.ece.umn.edu/wiki/images/d/d2/Senum_Riedel_Rate-Independent_Modules_for_Chemical_Computation.pptx Slides]
+
<span class="plainlinks">[http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
 +
<br> [http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]
 
|}
 
|}
  
==Computing with Random Bit Streams==
+
====Computing with Crappy Clocks====
  
"''To invent, all you need is a pile of junk and a good imagination.''" &ndash;&ndash; '''Thomas A. Edison''' (1847&ndash;1931)
+
Clock distribution networks are a significant source of power consumption and a major design bottleneck for high-performance circuits. We have proposed a radically new approach: splitting clock domains at a very fine level, with domains consisting of only a handful of gates each. These domains are synchrnonized by "crappy clocks", generated locally with inverter rings. This is feasible if one adopts the paradigm of computing on randomized bit streams.
 +
[[File:polysynchronous-and.png|center|frame|thumb|Stochastic multiplication using an AND gate with unsynchronized random bit streams. The stochastic paradigm can tolerate arbitrarly high clock skew. Accordingly, one can replace an expensive global clock distribution network with cheap local clocks, generated by inverter rings &ndash; "crappy clocks".]]
 +
{|
 +
|
 +
{| style="background:#F0E68C"
 +
|- valign="top"
 +
| width="100" | '''title''':
 +
| width="500" | [[Media: Najafi_Lilja_Riedel_Bazargan_Polysynchronous_Stochastic_Circuits.pdf | Polysynchronous Stochastic Circuits]]
 +
|- valign="top"
 +
| '''authors''':
 +
| [[M. Hassan_Najafi]], [http://www.arctic.umn.edu/lilja.shtml David Lilja], [[Marc Riedel]], and [http://www.ece.umn.edu/users/kia/ Kia Bazargan]
 +
|- valign="top"
 +
| '''to appear in''':
 +
| [http://www.amsv.umac.mo/aspdac2016/ IEEE/ACM Asia and South Pacific Design Automation Conference], 2016
 +
|}
 +
| align="center" width="70" |
 +
<span class="plainlinks">
 +
[http://cctbio.ece.umn.edu/wiki/images/e/ec/Najafi_Lilja_Riedel_Bazargan_Polysynchronous_Stochastic_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 +
<br>
 +
[[Media:Najafi_Lilja_Riedel_Bazargan_Polysynchronous_Stochastic_Circuits.pdf | Paper]]
 +
|}
  
Humans are accustomed to counting in a positional number system &ndash; [http://en.wikipedia.org/wiki/Decimal decimal] radix.  Nearly all computer systems operate on another positional number system &ndash; [http://en.wikipedia.org/wiki/Binary_numeral_system binary] radix. From the standpoint of ''representation'', such positional systems are compact: given a radix ''b'', one can represent ''b<sup>n</sup>'' distinct numbers with ''n'' digits. However, from the standpoint of ''computation'', positional systems impose a burden: for each operation such as addition or multiplication, the signal must be "''decoded''", with each digit weighted according to its position. The result must be "''encoded''" back in positional form. Any student who has designed a [http://en.wikipedia.org/wiki/Binary_multiplier binary multiplier] in a course on [[EE2301 | logic design]] can appreciate all the complexity that goes into wiring up such an operation.
+
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on these topics.
  
==== Logic that Operates on Probabilities ====
+
==Computing with Molecules==
  
We advocate an alternative representation: random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. For instance, multiplication can be performed with a single AND gate; scaled addition can be performed with a multiplexer (MUX)
+
“''If I can’t create it, I don’t understand it.''” &ndash;&ndash; '''Richard Feynman''' (1918&ndash;1988)
  
 +
The theory of [http://en.wikipedia.org/wiki/Chemical_kinetics mass-action kinetics] underpins our understanding of biological and chemical systems. It is a simple and elegant formalism: molecular reactions define ''rules'' according to which reactants form products; each rule fires at a ''rate'' that is proportional to the quantities of the corresponding reactants that are present. Just as electronic systems implement computation in terms of '''voltage''' (''energy per unit charge''), we can conceive of molecular systems that compute in terms of '''chemical concentrations''' (''molecules per unit volume''). We are studying techniques for implementing a variety of computational constructs with molecular reactions such as logic, memory, arithmetic, and signal processing. Although conceptual, we target [http://pubs.acs.org/doi/pdfplus/10.1021/ja906987s DNA Strand Displacement] as our experimental chassis.
 +
<br>
 
{| align="center"
 
{| align="center"
| [[Image:stochastic-multiplier.png|center|thumb|350px|'''Multiplication''' with an AND gate. Here the variables represents the ''probabilities'' of obtaining a 1 versus a 0 in stochastic bit streams. The AND gate produces an output probability <math>c</math> that is the product of the of the input probabilities <math>a</math> and <math>b</math>.]]
+
||
||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+
[[Image:molecular-reactions-are-rules.gif|center|thumb|300px|Molecular reactions define ''rules'' according to which reactants form products. Here molecules of type A combine with molecules of type B to form molecules of type C, at a rate proportional to the molecular concentrations of A and B as well as a rate constant ''k''.]]
|| [[Image:stochastic-adder.png|thumb|320px|'''Scaled addition''' with a multiplexer (MUX).  
+
||
Given input probabilities <math>a</math>, <math>b</math> and <math>s</math>, the MUX produces an output probability <math>c = a s + (1 - s) b</math>.]]
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 +
||
 +
[[Image:branch-migration.png|center|thumb|300px|We map abstract molecular reactions to DNA reactions. Through a process
 +
called [http://pubs.acs.org/doi/pdfplus/10.1021/ja906987s DNA strand displacement], single strands of DNA displace parts of double strands, releasing other single strands.]]  
 
|}
 
|}
  
We have developed a general method for synthesizing digital circuitry that computes on such stochastic bit streams. Our method can be used to synthesize arbitrary polynomial functions. Through polynomial approximations, it can also be used to synthesize non-polynomial functions. Because the representation is uniform, with all bits weighted equally, the resulting circuits are highly tolerant of [http://en.wikipedia.org/wiki/Soft_error soft errors] (i.e., bit flips).  
+
'''Computational Constructs'''
 +
 
 +
We have developed a strategy for implementing digital logic with molecular reactions. Based on a bistable mechanism for representing bits, we implement a constituent set of logical components, including combinational components such as '''AND''', '''OR''', and '''XOR gates''', as well as sequential components such as '''D latches''' and '''D flip-flops'''. Using these components, we build full-fledged digital circuits such as a ''binary counters'' and ''linear feedback shift registers''.  
  
 
{|
 
{|
Line 130: Line 150:
 
{| 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:Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf | Digital Logic with Molecular Reactions]]
|- valign="top"  
+
|- valign="top"
 
| '''authors''':
 
| '''authors''':
| [[Weikang Qian]] and [[Marc Riedel]]
+
| [[Hua Jiang]], [[Marc Riedel]], [http://www.ece.umn.edu/users/parhi Keshab Parhi]
|- valign="top"
 
| '''submitted&nbsp;to''':
 
| [http://www.ieee.org/publications_standards/publications/proceedings/index.html Proceedings of the IEEE], 2011.
 
 
|- valign="top"
 
|- valign="top"
 
| '''presented&nbsp;at''':
 
| '''presented&nbsp;at''':
| [http://www.dac.com/events/eventdetails.aspx?id=77-37 Design Automation Conference], Anaheim, CA, 2008.<br>(Nominated as a '''Research Highlight''', [http://cacm.acm.org/ Communications of the ACM]).<br>
+
| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2013.
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
<span class="plainlinks">
+
<span class="plainlinks">[http://cctbio.ece.umn.edu/wiki/images/c/cf/Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf http://mriedel.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>[[Media:Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf | Paper]]
<br>
 
[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf | Paper]]
 
| align=center width="70" |
 
<span class="plainlinks">[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]</span>
 
<br> [http://cctbio.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt Slides]
 
 
|}
 
|}
  
====Logic that Generates Probabilities====
+
We have developed a strategy for implementing arithmetic with molecular reactions &ndash; operations such as '''increments & decrements''', '''multiplication''', '''logarithms''', and '''exponentiation'''. Try out our [http://mriedel.ece.umn.edu/chem-compiler/chem-compiler.pl compiler]: it translates arbitrary constructs from a '''C-like language''' into a robust implementation with molecular reactions.
  
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 that have a specific probability of being one versus zero. If many different probability values are required, it can be difficult or expensive to generate all of these directly from physical sources. In this work, we demonstrate novel techniques for synthesizing combinational logic that transforms a set of ''source'' probabilities into different ''target'' probabilities.  
+
{|
<!--The problem I consider is: given a set ''S'' of ''n'' probabilistic inputs with probabilities ''p''<sub>1</sub>, ..., ''p''<sub><I>n</I></sub> of being one and a target probability ''q'', how can we synthesize a combinational circuit that takes inputs from the set ''S'' and produces an output with probability ''q'' of being one?-->
+
|
 +
{| style="background:#F0E68C"
 +
|- valign="top"
 +
| width="100" | '''title''':
 +
| width="500" | [[Media:Senum_Riedel_Rate-Independent_Constructs_for_Chemical_Computation.pdf | Rate-Independent Constructs for Chemical Computation]]
 +
|- valign="top"
 +
| '''authors''':
 +
| [[Phil Senum]] and [[Marc Riedel]]
 +
|- valign="top"
 +
| '''appeared in''':
 +
| [http://dx.plos.org/10.1371/journal.pone.0021414 PLoS ONE], Vol. 6, No. 6, 2011.<br>[[Rate_Independent_Constructs_Supplementary_Information | Supplementary Information]]
 +
|}
 +
| align="center" width="70" |
 +
<span class="plainlinks">
 +
[http://mriedel.ece.umn.edu/wiki/images/d/db/Senum_Riedel_Rate-Independent_Constructs_for_Chemical_Computation.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 +
<br> [http://mriedel.ece.umn.edu/wiki/images/d/db/Senum_Riedel_Rate-Independent_Constructs_for_Chemical_Computation.pdf Paper]
 +
| align="center" width="70" |
 +
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/d/d2/Senum_Riedel_Rate-Independent_Modules_for_Chemical_Computation.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
 +
<br> [http://mriedel.ece.umn.edu/wiki/images/d/d2/Senum_Riedel_Rate-Independent_Modules_for_Chemical_Computation.pptx Slides]
 +
|}
  
[[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 and each inverter performs a "one-minus" operation.]]
+
We have developed a strategy for implementing signal processing with molecular reactions including operations such as '''filtering'''. We have demonstrated robust designs for [http://en.wikipedia.org/wiki/Finite_impulse_response Finite-Impulse Response (FIR)], [http://en.wikipedia.org/wiki/Infinite_impulse_response Infinite-Impulse Response (IIR)] filters, and [http://en.wikipedia.org/wiki/Fast_Fourier_transform Fast Fourier Transforms (FFTs)].
  
 
{|
 
{|
Line 164: Line 195:
 
|- valign="top"
 
|- valign="top"
 
| width="100" | '''title''':
 
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Transforming Probabilities with Combinational Logic]]
+
| width="500" | [[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf | Discrete-Time Signal Processing with DNA]]
 
|- valign="top"
 
|- valign="top"
 
| '''authors''':
 
| '''authors''':
| [[Weikang Qian]], [[Marc Riedel]], [http://paradise.caltech.edu/~hzhou/ Hongchao Zhou], and [http://paradise.caltech.edu/bruck.html Jehoshua Bruck]
+
| [[Hua Jiang]], Ahmed Salehi, [[Marc Riedel]] and [http://www.ece.umn.edu/users/parhi Keshab Parhi]
 +
|- valign="top"
 +
| '''appeared&nbsp;in''':
 +
| [http://pubs.acs.org/doi/abs/10.1021/sb300087n ACS Synthetic Biology], Vol. 2 no. 5, pp. 245&ndash;254, 2013.<br>[[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA_Appendix.pdf | Supplementary Information: List of Reactions]]
 +
|- valign="top"
 +
| '''appeared&nbsp;in''':
 +
| [http://www.computer.org/portal/web/dt IEEE Design & Test of Computers], Vol. 29, No. 3, pp. 21&ndash;31, 2012.
 
|- valign="top"
 
|- valign="top"
| '''will appear in''':
+
| '''presented at''':
| [http://tcad.polito.it/ IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems], 2012.
+
| [http://www.iccad.com/ IEEE/ACM International Conference on Computer-Aided Design],<br> San Jose, CA, 2010.
 
|- valign="top"
 
|- valign="top"
| '''presented&nbsp;at''':
+
| '''presented at''':
| [http://www.iccad.com/events/eventdetails.aspx?id=106-5-C International Conference on Computer-Aided Design], San Jose, 2009<br>(nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award''').
+
| [http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=7703&copyownerid=8242 IEEE Workshop on Signal Processing Systems], San Francisco, 2010
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |
 +
<span class="plainlinks">
 +
[http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 +
<br> [http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf Paper]
 +
| 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://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
 +
<br> [http://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx Slides]
 +
|}
 +
 
 
<br>
 
<br>
[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf  | Paper]]
+
{| align="center"
| 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>
+
|
<br> [http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]
+
[[Image:dna-logic-gates.gif|center|thumb|450px| Simulations of DNA implementation of logic gates. The input signals are molecular concentrations X and Y; the output signal is a molecular concentration Z. (A) AND gate. (B) OR gate. (C) NOR gate. (D) XOR gate.]]
 +
||
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 +
||
 +
[[Image:moving-average-filter-simulation.gif|center|thumb|400px|Simulations of DNA implementation of a '''moving-average FIR filter'''. This filter removes the high-frequency component from an input signal, producing an output signal consisting of only the low-frequency component. Here the "signals" are molecular concentrations.]]
 +
||
 
|}
 
|}
  
Please see our "[[Papers,_Theses,_and_Slides |Publications]]" page for more of our papers on these topics.
+
The impetus for this research is not computation ''per se''. Molecular computation will never compete with conventional computers made of [http://en.wikipedia.org/wiki/Integrated_circuit silicon integrated circuits] for tasks such as number crunching. Chemical systems are inherently slow and messy, taking minutes or even hours to finish, and producing fragmented results. Rather, the goal is to create “'''embedded controllers'''” &ndash; viruses and bacteria that are engineered to perform useful molecular computation ''in situ'' where it is needed, for instance for drug delivery and biochemical sensing.
 +
[[Image:embedded-controller.png|center|thumb|350px|Molecular computation is applicable to the design of ''embedded controllers'': engineered bacteria and viruses for tasks such as drug delivery.]]
 +
 
 +
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on these topics.
  
 
==Computing with Nanoscale Lattices==
 
==Computing with Nanoscale Lattices==
Line 192: Line 244:
  
 
In his seminal Master's Thesis, [http://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon] made the connection between Boolean algebra and switching circuits. He considered '''two-terminal''' switches corresponding to electromagnetic relays. A Boolean function can be implemented in terms of connectivity across a network of switches, often arranged in a series/parallel configuration.  We have developed a method for synthesizing Boolean functions with networks of '''four-terminal switches'''.  Our model is applicable for variety of nanoscale technologies, such as [http://www.sciencemag.org/content/302/5649/1377.short nanowire crossbar arrays], as [http://en.wikipedia.org/wiki/Molecular_switch molecular switch-based structures].
 
In his seminal Master's Thesis, [http://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon] made the connection between Boolean algebra and switching circuits. He considered '''two-terminal''' switches corresponding to electromagnetic relays. A Boolean function can be implemented in terms of connectivity across a network of switches, often arranged in a series/parallel configuration.  We have developed a method for synthesizing Boolean functions with networks of '''four-terminal switches'''.  Our model is applicable for variety of nanoscale technologies, such as [http://www.sciencemag.org/content/302/5649/1377.short nanowire crossbar arrays], as [http://en.wikipedia.org/wiki/Molecular_switch molecular switch-based structures].
{|align="center"
+
{| align="center"
 
|
 
|
 
[[Image:two-terminal.gif|center|thumb|none|315px|Shannon's model: '''two-terminal switches'''.  Each switch is either ON (closed) or OFF (open). A Boolean function is implemented in terms of connectivity across a network of switches, between the source S and the drain D.]]
 
[[Image:two-terminal.gif|center|thumb|none|315px|Shannon's model: '''two-terminal switches'''.  Each switch is either ON (closed) or OFF (open). A Boolean function is implemented in terms of connectivity across a network of switches, between the source S and the drain D.]]
Line 201: Line 253:
 
|
 
|
 
{| style="background:#F0E68C"
 
{| style="background:#F0E68C"
|- valign=top
+
|- valign="top"
 
| width="100" |'''title''':
 
| width="100" |'''title''':
| width="500"|[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Logic Synthesis for Switching Lattices]]
+
| width="500" |[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Logic Synthesis for Switching Lattices]]
 
|- valign="top"
 
|- valign="top"
 
| '''authors''':
 
| '''authors''':
Line 214: Line 266:
 
| [http://www.dac.com/47th/index.aspx Design Automation Conference], Anaheim, CA, 2010.
 
| [http://www.dac.com/47th/index.aspx Design Automation Conference], Anaheim, CA, 2010.
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://cadbio.com/wiki/images/c/ca/Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf   http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
+
[http://cadbio.com/wiki/images/c/ca/Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 
<br>
 
<br>
 
[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Paper]]
 
[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Paper]]
 
| align="center" width="70" |  
 
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
+
[http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
 
<br> [http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt Slides]
 
<br> [http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt Slides]
 
|}
 
|}
  
 
The impetus for nanowire-based technology is the potential density, scalability and manufacturability.  Many other novel and emerging technologies fit the general model of four-terminal switches.  For instance, researchers are investigating [http://en.wikipedia.org/wiki/Spin_wave spin waves]. A common feature of many emerging technologies for switching networks is that they exhibit high defect rates.  
 
The impetus for nanowire-based technology is the potential density, scalability and manufacturability.  Many other novel and emerging technologies fit the general model of four-terminal switches.  For instance, researchers are investigating [http://en.wikipedia.org/wiki/Spin_wave spin waves]. A common feature of many emerging technologies for switching networks is that they exhibit high defect rates.  
{|align="center"
+
{| align="center"
 
|
 
|
[[Image:nano-crossbar.gif|center|thumb|none|315px|A nanowire crossbar switch.  
+
[[Image:nano-crossbar.gif|center|thumb|315px|A nanowire crossbar switch.  
 
The connections between horizontal and vertical
 
The connections between horizontal and vertical
 
wires are FET-like junctions.  When high or low voltages are applied to input nanowires, the
 
wires are FET-like junctions.  When high or low voltages are applied to input nanowires, the
Line 234: Line 286:
 
]]
 
]]
 
|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 
|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|| [[Image:percolation.gif|center|thumb|none|315px| In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. Unless the defect rate exceeds an error margin, with high probability no connection forms between the top and bottom plates for logical zero ("OFF"); with high probability, a connection forms for logical one ("ON").]]
+
|| [[Image:percolation.gif|center|thumb|315px| In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. Unless the defect rate exceeds an error margin, with high probability no connection forms between the top and bottom plates for logical zero ("OFF"); with high probability, a connection forms for logical one ("ON").]]
 
|}
 
|}
 
We have devised a novel framework for digital computation with lattices of nanoscale switches with high defect rates, based on the mathematical phenomenon of [http://en.wikipedia.org/wiki/Percolation_theory percolation]. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly in the presence of defects.
 
We have devised a novel framework for digital computation with lattices of nanoscale switches with high defect rates, based on the mathematical phenomenon of [http://en.wikipedia.org/wiki/Percolation_theory percolation]. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly in the presence of defects.
Line 240: Line 292:
 
|
 
|
 
{| style="background:#F0E68C"
 
{| style="background:#F0E68C"
|- valign=top
+
|- valign="top"
 
| width="100" |'''title''':
 
| width="100" |'''title''':
| width="500"|[[Media:Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Synthesizing Logic with Percolation in Nanoscale Lattices]]
+
| width="500" |[[Media:Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Synthesizing Logic with Percolation in Nanoscale Lattices]]
 
|- valign="top"
 
|- valign="top"
 
| '''authors''':
 
| '''authors''':
Line 249: Line 301:
 
| '''appeared&nbsp;in''':
 
| '''appeared&nbsp;in''':
 
| [http://www.igi-global.com/Bookstore/TitleDetails.aspx?TitleId=1117&DetailsType=Description/ International Journal of Nanotechnology and Molecular Computation], <br>Vol. 3, No. 2, pp. 12&ndash;30, 2011.
 
| [http://www.igi-global.com/Bookstore/TitleDetails.aspx?TitleId=1117&DetailsType=Description/ International Journal of Nanotechnology and Molecular Computation], <br>Vol. 3, No. 2, pp. 12&ndash;30, 2011.
|- valign=top
+
|- valign="top"
 
| '''presented&nbsp;at''':
 
| '''presented&nbsp;at''':
 
| [http://www.dac.com/46th/index.aspx Design Automation Conference], San Francisco, CA, 2009.
 
| [http://www.dac.com/46th/index.aspx Design Automation Conference], San Francisco, CA, 2009.
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://cadbio.com/wiki/images/3/3b/Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf   http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
+
[http://cadbio.com/wiki/images/3/3b/Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 
<br>
 
<br>
 
[[Media:Altun_Riedel_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Paper]]
 
[[Media:Altun_Riedel_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Paper]]
 
| align="center" width="70" |  
 
| align="center" width="70" |  
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
+
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
 
<br> [http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt Slides]
 
<br> [http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt Slides]
 
|}
 
|}
 
<!-- [[Image:Lattice-defects-percolation.gif|center|thumb|none|700px|In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. Unless the defect rate exceeds an error margin, with high probability, no connection forms between the top and bottom plates for logical zero ("OFF"); with high probability, a connection forms for logical one ("ON").]] -->
 
<!-- [[Image:Lattice-defects-percolation.gif|center|thumb|none|700px|In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. Unless the defect rate exceeds an error margin, with high probability, no connection forms between the top and bottom plates for logical zero ("OFF"); with high probability, a connection forms for logical one ("ON").]] -->
  
Please see our "[[Papers,_Theses,_and_Slides |Publications]]" page for more of our papers on these topics.
+
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on these topics.
  
 
==Computing with Feedback==
 
==Computing with Feedback==
Line 294: Line 346:
  
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://cctbio.ece.umn.edu/wiki/images/9/94/Riedel_Bruck_Cyclic_Boolean_Circuits.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
+
[http://mriedel.ece.umn.edu/wiki/images/9/94/Riedel_Bruck_Cyclic_Boolean_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 
<br>
 
<br>
 
[[Media:Riedel_Bruck_Cyclic_Boolean_Circuits.pdf | Paper]]
 
[[Media:Riedel_Bruck_Cyclic_Boolean_Circuits.pdf | Paper]]
| align=center width="70" |  
+
| align="center" width="70" |  
 
<span class="plainlinks">
 
<span class="plainlinks">
[http://cctbio.ece.umn.edu/wiki/images/7/7a/Riedel_Cyclic_Combinational_Circuits.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
+
[http://mriedel.ece.umn.edu/wiki/images/7/7a/Riedel_Cyclic_Combinational_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 
<br>
 
<br>
 
[[Media:Riedel_Cyclic_Combinational_Circuits.pdf | PhD Dissertation]]
 
[[Media:Riedel_Cyclic_Combinational_Circuits.pdf | PhD Dissertation]]
| align=center width="70" |  
+
| align="center" width="70" |  
<span class="plainlinks">[http://cctbio.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
+
<span class="plainlinks">[http://mriedel.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://cctbio.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt Slides]
+
<br> [http://mriedel.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt Slides]
 
|}
 
|}
Please see our [[Papers,_Theses,_and_Slides | Publications]] page for more of our papers on this topic.
+
Please see our [[Papers,_Theses,_and_Presentations | Publications]] page for more of our papers on this topic.
  
 
==Algorithms and Data Structures==
 
==Algorithms and Data Structures==
Line 325: Line 377:
 
|- valign="top"
 
|- valign="top"
 
| width="100" | '''title''':
 
| width="100" | '''title''':
| width="500" | [[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf‎‎ | Reduction of Interpolants For Logic Synthesis]]
+
| width="500" | [[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf | Reduction of Interpolants For Logic Synthesis]]
 
|- valign="top"
 
|- valign="top"
 
| '''authors''':
 
| '''authors''':
Line 333: Line 385:
 
| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2010.
 
| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2010.
 
|}
 
|}
| align=center width="70" |  
+
| align="center" width="70" |  
<span class="plainlinks">[http://cadbio.com/wiki/images/b/b6/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
+
<span class="plainlinks">[http://cadbio.com/wiki/images/b/b6/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
 
<br>[[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf  | Paper]]
 
<br>[[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf  | Paper]]
| align=center width="70" |  
+
| align="center" width="70" |  
<span class="plainlinks">[http://cctbio.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
+
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://cctbio.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt Slides]
+
<br> [http://mriedel.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt Slides]
 
|}
 
|}
Please see our "[[Papers,_Theses,_and_Slides |Publications]]" page for more of our papers on this topic. (Papers on SAT-based circuit verification, that is, not on squids.)
+
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on this topic. (Papers on SAT-based circuit verification, that is, not on squids.)
  
 
==Mathematics==
 
==Mathematics==
Line 361: Line 413:
 
| [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&ndash;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&ndash;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://mriedel.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]]
 
|}
 
|}
  
Please see our "[[Papers,_Theses,_and_Slides |Publications]]" page for more of our papers on this topic.
+
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on this topic.

Latest revision as of 21:04, 20 December 2017

"You see things; and you say, 'Why?' But I dream things that never were; and I say, 'Why not?'"–– George Bernard Shaw (1856 –1950)

Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be inductive (as opposed to deductive) and conceptual (as opposed to applied). A recurring theme is building systems that compute in novel or unexpected ways with new and emerging technologies. Often, the task of analyzing the way things work in a new technology is straightforward; however the task of synthesizing new computational constructs is more challenging.

Computing with Random Bit Streams

"To invent, all you need is a pile of junk and a good imagination." –– Thomas A. Edison (1847–1931)

Humans are accustomed to counting in a positional number system – decimal radix. Nearly all computer systems operate on another positional number system – binary radix. From the standpoint of representation, such positional systems are compact: given a radix b, one can represent bn distinct numbers with n digits. However, from the standpoint of computation, positional systems impose a burden: for each operation such as addition or multiplication, the signal must be "decoded", with each digit weighted according to its position. The result must be "encoded" back in positional form. Any student who has designed a binary multiplier in a course on logic design can appreciate all the complexity that goes into wiring up such an operation.

Logic that Operates on Probabilities

We advocate an alternative representation: random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. For instance, multiplication can be performed with a single AND gate; scaled addition can be performed with a multiplexer (MUX).

Multiplication with an AND gate. Here the variables represents the probabilities of obtaining a 1 versus a 0 in stochastic bit streams. The AND gate produces an output probability <math>c</math> that is the product of the of the input probabilities <math>a</math> and <math>b</math>.
            
Scaled addition with a multiplexer (MUX). Given input probabilities <math>a</math>, <math>b</math> and <math>s</math>, the MUX produces an output probability <math>c = a s + (1 - s) b</math>.

We have developed a general method for synthesizing digital circuitry that computes on such stochastic bit streams. Our method can be used to synthesize arbitrary polynomial functions. Through polynomial approximations, it can also be used to synthesize non-polynomial functions. Because the representation is uniform, with all bits weighted equally, the resulting circuits are highly tolerant of soft errors (i.e., bit flips).

title: Synthesizing Logical Computation on Stochastic Bit Streams
authors: Weikang Qian and Marc Riedel
appeared as: Techincal Report, UMN

Pdf.jpg
Paper

Ppt.jpg
Slides

title: Logical Computation on Stochastic Bit Streams with Linear Finite State Machines
authors: Peng Li, David Lilja, Weikang Qian,Kia Bazargan and Marc Riedel
appeared in: IEEE Transactions on Computers, Vol. 63, No. 6., pp. 1474–1486, 2014
presented at: IEEE/ACM Asia and South Pacific Design Automation Conference,
Sydney, Australia, 2012

Pdf.jpg
Paper

Logic that Generates Probabilities

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 that have a specific probability of being one versus zero. If many different probability values are required, it can be difficult or expensive to generate all of these directly from physical sources. In this work, we 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 and each inverter performs a "one-minus" operation.
title: Transforming Probabilities with Combinational Logic
authors: Weikang Qian, Marc Riedel, Hongchao Zhou, and Jehoshua Bruck
will appear in: IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2012.
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

Computing with Crappy Clocks

Clock distribution networks are a significant source of power consumption and a major design bottleneck for high-performance circuits. We have proposed a radically new approach: splitting clock domains at a very fine level, with domains consisting of only a handful of gates each. These domains are synchrnonized by "crappy clocks", generated locally with inverter rings. This is feasible if one adopts the paradigm of computing on randomized bit streams.

Stochastic multiplication using an AND gate with unsynchronized random bit streams. The stochastic paradigm can tolerate arbitrarly high clock skew. Accordingly, one can replace an expensive global clock distribution network with cheap local clocks, generated by inverter rings – "crappy clocks".
title: Polysynchronous Stochastic Circuits
authors: M. Hassan_Najafi, David Lilja, Marc Riedel, and Kia Bazargan
to appear in: IEEE/ACM Asia and South Pacific Design Automation Conference, 2016

Pdf.jpg
Paper

Please see our "Publications" page for more of our papers on these topics.

Computing with Molecules

If I can’t create it, I don’t understand it.” –– Richard Feynman (1918–1988)

The theory of mass-action kinetics underpins our understanding of biological and chemical systems. It is a simple and elegant formalism: molecular reactions define rules according to which reactants form products; each rule fires at a rate that is proportional to the quantities of the corresponding reactants that are present. Just as electronic systems implement computation in terms of voltage (energy per unit charge), we can conceive of molecular systems that compute in terms of chemical concentrations (molecules per unit volume). We are studying techniques for implementing a variety of computational constructs with molecular reactions such as logic, memory, arithmetic, and signal processing. Although conceptual, we target DNA Strand Displacement as our experimental chassis.

Molecular reactions define rules according to which reactants form products. Here molecules of type A combine with molecules of type B to form molecules of type C, at a rate proportional to the molecular concentrations of A and B as well as a rate constant k.

            

We map abstract molecular reactions to DNA reactions. Through a process called DNA strand displacement, single strands of DNA displace parts of double strands, releasing other single strands.

Computational Constructs

We have developed a strategy for implementing digital logic with molecular reactions. Based on a bistable mechanism for representing bits, we implement a constituent set of logical components, including combinational components such as AND, OR, and XOR gates, as well as sequential components such as D latches and D flip-flops. Using these components, we build full-fledged digital circuits such as a binary counters and linear feedback shift registers.

title: Digital Logic with Molecular Reactions
authors: Hua Jiang, Marc Riedel, Keshab Parhi
presented at: The International Conference on Computer-Aided Design, San Jose, CA, 2013.

Pdf.jpg
Paper

We have developed a strategy for implementing arithmetic with molecular reactions – operations such as increments & decrements, multiplication, logarithms, and exponentiation. Try out our compiler: it translates arbitrary constructs from a C-like language into a robust implementation with molecular reactions.

title: Rate-Independent Constructs for Chemical Computation
authors: Phil Senum and Marc Riedel
appeared in: PLoS ONE, Vol. 6, No. 6, 2011.
Supplementary Information

Pdf.jpg
Paper

Ppt.jpg
Slides

We have developed a strategy for implementing signal processing with molecular reactions including operations such as filtering. We have demonstrated robust designs for Finite-Impulse Response (FIR), Infinite-Impulse Response (IIR) filters, and Fast Fourier Transforms (FFTs).

title: Discrete-Time Signal Processing with DNA
authors: Hua Jiang, Ahmed Salehi, Marc Riedel and Keshab Parhi
appeared in: ACS Synthetic Biology, Vol. 2 no. 5, pp. 245–254, 2013.
Supplementary Information: List of Reactions
appeared in: IEEE Design & Test of Computers, Vol. 29, No. 3, pp. 21–31, 2012.
presented at: IEEE/ACM International Conference on Computer-Aided Design,
San Jose, CA, 2010.
presented at: IEEE Workshop on Signal Processing Systems, San Francisco, 2010

Pdf.jpg
Paper

Ppt.jpg
Slides


Simulations of DNA implementation of logic gates. The input signals are molecular concentrations X and Y; the output signal is a molecular concentration Z. (A) AND gate. (B) OR gate. (C) NOR gate. (D) XOR gate.

                 

Simulations of DNA implementation of a moving-average FIR filter. This filter removes the high-frequency component from an input signal, producing an output signal consisting of only the low-frequency component. Here the "signals" are molecular concentrations.

The impetus for this research is not computation per se. Molecular computation will never compete with conventional computers made of silicon integrated circuits for tasks such as number crunching. Chemical systems are inherently slow and messy, taking minutes or even hours to finish, and producing fragmented results. Rather, the goal is to create “embedded controllers” – viruses and bacteria that are engineered to perform useful molecular computation in situ where it is needed, for instance for drug delivery and biochemical sensing.

Molecular computation is applicable to the design of embedded controllers: engineered bacteria and viruses for tasks such as drug delivery.

Please see our "Publications" page for more of our papers on these topics.

Computing with Nanoscale Lattices

"Listen to the technology; find out what it’s telling you.” –– Carver Mead (1934–  )

In his seminal Master's Thesis, Claude Shannon made the connection between Boolean algebra and switching circuits. He considered two-terminal switches corresponding to electromagnetic relays. A Boolean function can be implemented in terms of connectivity across a network of switches, often arranged in a series/parallel configuration. We have developed a method for synthesizing Boolean functions with networks of four-terminal switches. Our model is applicable for variety of nanoscale technologies, such as nanowire crossbar arrays, as molecular switch-based structures.

Shannon's model: two-terminal switches. Each switch is either ON (closed) or OFF (open). A Boolean function is implemented in terms of connectivity across a network of switches, between the source S and the drain D.
               
Our model: four-terminal switches. Each switch is either mutually connected to its neighbors (ON) or disconnected (OFF). A Boolean function is implemented in terms of connectivity between the top and bottom plates. This network implements the same function as the two-terminal network on the left.
title: Logic Synthesis for Switching Lattices
authors: Mustafa Altun and Marc Riedel
will appear in: IEEE Transactions on Computers, 2011.
presented at: Design Automation Conference, Anaheim, CA, 2010.

Pdf.jpg
Paper

Ppt.jpg
Slides

The impetus for nanowire-based technology is the potential density, scalability and manufacturability. Many other novel and emerging technologies fit the general model of four-terminal switches. For instance, researchers are investigating spin waves. A common feature of many emerging technologies for switching networks is that they exhibit high defect rates.

A nanowire crossbar switch. The connections between horizontal and vertical wires are FET-like junctions. When high or low voltages are applied to input nanowires, the FET-like junctions that cross these develop a high or low impedance, respectively.
               
In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. Unless the defect rate exceeds an error margin, with high probability no connection forms between the top and bottom plates for logical zero ("OFF"); with high probability, a connection forms for logical one ("ON").

We have devised a novel framework for digital computation with lattices of nanoscale switches with high defect rates, based on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly in the presence of defects.

title: Synthesizing Logic with Percolation in Nanoscale Lattices
authors: Mustafa Altun and Marc Riedel
appeared in: International Journal of Nanotechnology and Molecular Computation,
Vol. 3, No. 2, pp. 12–30, 2011.
presented at: Design Automation Conference, San Francisco, CA, 2009.

Pdf.jpg
Paper

Ppt.jpg
Slides

Please see our "Publications" page for more of our papers on these topics.

Computing with Feedback

"A person with a new idea is a crank until the idea succeeds." –– Mark Twain (1835–1910)

The accepted wisdom is that combinational circuits (i.e., memoryless circuits) must have acyclic (i.e., loop-free or feed-forward) topologies. And yet simple examples suggest that this need not be so. We advocate the design of cyclic combinational circuits (i.e., circuits with loops or feedback paths). We have proposed a methodology for synthesizing such circuits and demonstrated that it produces significant improvements in area and in delay.

A circuit that has feedback and yet is combinational.
title: Cyclic Boolean Circuits
authors: Marc Riedel and Shuki Bruck
appeared  in: Discrete Applied Mathematics, Vol. 160, No. 13–14, pp. 1877–1900, 2011.
dissertation: Ph.D., Electrical Engineering, Caltech, 2004
(winner of Charles H. Wilts Prize for the Best Ph.D. Dissertation in EE at Caltech).
presented at: Design Automation Conference, Anahiem, CA, 2003
(winner of DAC Best Paper Award).

Pdf.jpg
Paper

Pdf.jpg
PhD Dissertation

Ppt.jpg
Slides

Please see our Publications page for more of our papers on this topic.

Algorithms and Data Structures

"There are two kinds of people in the world: those who divide the world into two kinds of people, and those who don't." –– Robert Charles Benchley (1889–1945)

Consider the task of designing a digital circuit with 256 inputs. From a mathematical standpoint, such a circuit performs mappings from a space of <math>2^{256}</math> Boolean input values to Boolean output values. (The number of rows in a truth table for such a function is approximately equal to the number of atoms in the universe – <math>10^{77}</math> rows versus <math>10^{79}</math> atoms!) Verifying such a function, let alone designing the corresponding circuit, would seem to be an intractable problem. Circuit designers have succeeded in their endeavor largely as a result of innovations in the data structures and algorithms used to represent and manipulate Boolean functions. We have developed novel, efficient techniques for synthesizing functional dependencies based on so-called SAT-solving algorithms. We use Craig Interpolation to generate circuits from the corresponding Boolean functions.

A circuit construct for SAT-based verification.
            
A squid.
title: Reduction of Interpolants For Logic Synthesis
authors: John Backes and Marc Riedel
presented at: The International Conference on Computer-Aided Design, San Jose, CA, 2010.

Pdf.jpg
Paper

Ppt.jpg
Slides

Please see our "Publications" page for more of our papers on this topic. (Papers on SAT-based circuit verification, that is, not on squids.)

Mathematics

"Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true." –– Bertrand Russell (1872–1970)

The great mathematician John von Neumann articulated the view that research should never meander too far down theoretical paths; it should always be guided by potential applications. This view was not based on concerns about the relevance of his profession; rather, in his judgment, real-world applications give rise to the most interesting problems for mathematicians to tackle. At their core, most of our research contributions are mathematical contributions. The tools of our trade are discrete math, including combinatorics and probability theory.

Mathematics, before the era of LaTeX.
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

Please see our "Publications" page for more of our papers on this topic.