Department of Electrical and Computer Engineering

The Computer Engineering and Systems Group

Noise Based Logic

Noise based logic utilizes uncorrelated noise sources to represent a variable. With this choice, an exponential sized logic hyperspace can be constructed with a linear number of noise sources. Any additive superposition of hyperspace elements can be transmitted along a wire, making it effectively as expressive as 2^N wires. Multi-valued logic can be implemented easily in a sense.

We have formulated the SAT problem solution using noise-based logic, and can show that SAT is solved without a traditional search, in n steps (where n is the number of problem variables). Each step grows exponentially in n in the worst case. We are currently implementing this new way of doing SAT, to test if it is faster than traditional solvers in practical instances.

Instead of uncorrelated noise, any uncorrelated set of signals is acceptable to implement these ideas. We have designed a CMOS implementation of several gates, and simulated them in SPICE to validate the operation of the sinusoidal basis based gate realizations.

 

 

Publications, patents and artefacts:

  • “Boolean Satisfiability using Noise Based Logic”, Lin, Mandal, Khatri. ArXiv:1110.0550v1. In this paper, we formulate the problem of solving SAT using noise based logic. This yields a SAT based solution without traditional search, in n steps (where n is the number of variables in the problem). We are currently implementing this approach to compare it with traditional SAT solvers on large problems.
  • “Implementing Digital Logic with Sinusoidal Supplies”, Bollapalli, Khatri, Kish. Design Automation and Test in Europe (DATE) conference, 2010, Dresden, Germany. Mar 8-12, 2010.
  • Book chapter “Digital Logic Using Non-DC Signals”, Bollapalli, Khatri, Kish. pp 383-400. In “Advanced Techniques in Logic Synthesis Optimizations and Applications”, Khatri, Gulati, ed. Springer Publishers. This paper reports the use of anticorrelated sinusoids to represent logic values, and implements several gates in SPICE in a contemporary fabrication process, to prove the validity of the sinusoidal basis based circuit design.
  • “Computation using Noise-based Logic: Efficient String Verification over a Slow Communication Channel”, Kish, Khatri, Horvath. European Journal of Physics B 79 (2011). pp 85-90. In this paper, we use noise based logic to perform a hash operation, to verify identity of two strings in an efficient manner.
  • “Noise-based deterministic logic and computing: a brief survey”, Kish, Khatri, Bezrukov, Peper, Gingl, Horvath. International Journal of Unconventional Computing 7, Feb 2011. pp 101-113. This survey paper on noise based logic presents the different flavors of this logic.
  • “Towards brain-inspired computing”, Gingl, Khatri, Kish. Fluctuation and Noise Letters 9 (2010). pp 403-412. Instead of using noise sources or even sinusoids, orthogonal signals can be constructed out of pulse trains as well. This paper reports on some experiments with such random pulses.
  • “Instantaneous noise-based logic”, Kish, Khatri, Peper. Fluctuation and Noise Letters 9 (2010). pp 323-330. Noise based logic typically requires a correlation and averaging operation to test for the logic value on a wire. This paper describes instantaneous noise-based logic, in which intermediate gates in the computation do not require correlation to be done. Such a correlation is only needed at the circuit outputs.
  • “Noise-based Logic Hyperspace with the Superposition of 2^N States in a Single Wire”. Kish, Khatri, Sethuraman. Physics Letters A. Vol 373, number 22, May 2009. pp 1928-1934. In this paper, we show how, with a linear number of noise sources, an exponential number of hyperspace elements can be constructed. We also demonstrate a means to generate the complete hyperspace by using the analog of the Achille’s heel function in logic.
  • “Noise-based Computation”, Bezrukov, Gingl, Horvath, Kish, Khatri, Peper. Contract for this Research Monograph submitted to Springer Publishers. The book is expected to be published in 2012
  • Invited Paper, “Noise-based logic and computing: what do we have so far?”, Kish, Khatri, Bezrukov, Peper, Gingl, Horvath. 21st International Conference on Noise and Fluctuations. June 12-16 2011, Toronto, Canada. This is a summary paper describing our work in this area to date.
  • Invited Paper “Noise-based logic and computing: from Boolean logic gates to brain circuitry and its possible hardware realization”, Kish, Bezrukov, Khatri, Gingl, Sethuraman. International Workshop on Natural Computing (IWNC) 2009, Himeji, Japan. September 23-25, 2009. This paper motivates and describes noise based logic, comparing its variants.