1. Field of the Invention
The present invention relates to asynchronous reversible logic elements, a method for constructing asynchronous and reversible circuits using the elements and a method for constructing computers using the elements.
2. Description of Related Art
Microscopic physical phenomena are fundamentally reversible. To realize efficient and practical computers with ideally zero energy dissipation, reversible logic has been extensively studied but usually under the assumption that the underlying system is synchronous; i.e., all logic elements switch simultaneously in accordance with a central clock (Fredkin E and Toffoli T 1982 Conservative logic Int. J. Theoret. Phys. 21, 219–253). Because of the randomness of the operations that may occur within systems, a synchronous mode of timing seems hardly compatible with the backward determinism that accompanies reversible computing. Still, micro scale physical interactions are usually asynchronous. Asynchronous timing tends to reduce the energy dissipation per logic operation for different reasons: Logic elements in an asynchronous system can go into a sleeping state if they have no work to do; in synchronous system, idle logic elements have to engage in dummy switching whenever they receive clock signals (Hauck S 1995 Asynchronous design methodologies: an overview Proc. IEEE 83 (1) 69–93, Patra P 1995 Approaches to design of circuits for low-power computation Ph. D. Thesis University of Texas at Austin). The elements of an asynchronous system do not require a central clock signal and the hardware construction of a logic circuit may be simpler if an asynchronous mode of timing is adopted.
Universal reversible computer models that can conduct their computational tasks asynchronously have been proposed by Morita (Kenichi Morita, ‘A Simple Universal Logic Element and Cellular Automata for Reversible Computing’ MCU 2001, LNCS 2055, pp. 102–113, 2001), based on a reversible logic element called a Rotary Element (RE). Any reversible Turing machine (Turing machine is the prototype of modern electrical computers) can be constructed by using a network of REs, in which there is at most one particle moving around the entire circuit at any time. Since delays in any of the REs or lines do not affect the correctness of the computing process of the entire circuit, this circuit is called delay-insensitive (see e.g. Hauck S 1995 Asynchronous design methodologies: an overview Proc. IEEE 83 (1) 69–93, Patra P 1995 Approaches to design of circuits for low-power computation Ph. D. Thesis University of Texas at Austin). Thus, reversible computers consisting of REs can work in asynchronous mode, without needing a central clock signal to drive the operations of each RE (Kenichi Morita, ‘A Simple Universal Logic Element and Cellular Automata for Reversible Computing’ MCU 2001, LNCS 2055, pp. 102–113, 2001).
An RE has four input lines, four output lines, and two internal states. Although the RE can be used to realize reversible computers that operate asynchronously, it is somewhat complex, especially regarding the number or input and output lines. Intuitively, the less complex logic element is, the more opportunities it may offer for physical implementation. The purpose of this invention is thus to provide reversible elements that have less input and output lines than the conventional RE.