Document Type

Conference Proceeding

Publication Date



Reversible computing, Cellular automata, Logic circuits -- Design and construction, Quantum computers


This paper presents a cellular-automatic model of a reversible regular structure called Davio lattice. Regular circuits are investigated because of the requirement of future (nano-) technologies where long wires should be avoided. Reversibility is a valuable feature because it means much lower energy dissipation. A circuit is reversible if the number of its inputs equals the number of its outputs and there is a one-to-one mapping between spaces of input vectors and output vectors. It is believed that one day regular reversible structures will be implemented as nanoscale 3-dimensional chips. This paper introduces the notion of the Toffoli gate and its cellular-automatic implementation, as well as an example of the Davio lattice built exclusively of Toffoli gates and run on a special cellular automaton called CAM-Brain Machine (CBM).


Peper presented at the 12th International Workshop on Post-Binary ULSI Systems, May 16, 2003, at Meiji University.

Persistent Identifier