Synthesis of reversible logic

Abhinav Agrawal, Niraj K. Jha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations

Abstract

A function is reversible if each input vector produces a unique output vector. Reversible functions find applications in low power design, quantum computing, and nanotechnology. Logic synthesis for reversible circuits differs substantially from traditional logic synthesis. In this paper, we present the first practical synthesis algorithm and tool for reversible functions with a large number of inputs. It uses positive-polarity Reed-Muller decomposition at each stage to synthesize the function as a network of Toffoli gates. The heuristic uses a priority queue based search tree and explores candidate factors at each stage in order of attractiveness. The algorithm produces near-optimal results for the examples discussed in the literature. The key contribution of the work is that the heuristic finds very good solutions for reversible functions with a large number of inputs.

Original languageEnglish (US)
Title of host publicationProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 04
EditorsG. Gielen, J. Figueras
Pages1384-1385
Number of pages2
DOIs
StatePublished - Jul 12 2004
EventProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 04 - Paris, France
Duration: Feb 16 2004Feb 20 2004

Publication series

NameProceedings - Design, Automation and Test in Europe Conference and Exhibition
Volume2

Other

OtherProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 04
CountryFrance
CityParis
Period2/16/042/20/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Synthesis of reversible logic'. Together they form a unique fingerprint.

Cite this