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.