A digital circuit is reversible if it maps each input vector into a unique output vector. Reversible circuits can lead to low-power CMOS implementations and are also of interest in optical and quantum computing. Non-reversible specifications can be implemented as reversible circuits at the cost of added constant inputs and added `garbage' outputs.
This talk will discuss the basic theory of reversible logic with emphasis on the construction of reversible circuits composed of primitive reversible devices such as Feynman, Toffoli and Fredkin gates. A novel synthesis approach employing Rademacher-Walsh spectral techniques will be presented. This method develops the circuit from the inputs towards the outputs and from the outputs toward the inputs simultaneously and thus represents a significant departure from conventional logic design methods. The application of this new synthesis method to reversible and nonreversible (conventional) logic specifications will be shown.