Challenges and advances in Toffoli network optimisation. Issue 4 (1st July 2014)

• Record Type: Journal Article
• Authors: Dueck, Gerhard W.
• Is Part Of: IET computers & digital techniques. Volume 8:Issue 4(2014)
• Page Start: 172
• Page End: 177
• Publication Date: 2014-07-01
• Subjects: circuit optimisation -- logic design -- logic gates -- pattern matching; exact template matching algorithm -- template generation -- two phase synthesis -- reversible logic -- multiple‐control Toffoli gate -- reversible circuits -- reversible logic synthesis -- Toffoli network optimisation; Computers -- Periodicals; Digital electronics -- Periodicals; Computer engineering -- Periodicals; Computer architecture -- Periodicals; Computer organization -- Periodicals; 621.39
• DOI: 10.1049/iet-cdt.2013.0055
• Languages: English
• ISSNs: 1751-8601

Abstract

Abstract : This study gives a brief overview of the current trends in reversible logic synthesis with emphasis on template matching. The basic building block for reversible circuits considered here is the multiple‐control Toffoli gate. Some approaches to synthesis are reviewed and the challenges are explained. Since many practical functions are not reversible, they must be embedded into reversible ones, if they are to be implemented using reversible logic. The complexity of such embeddings is expounded. A two phase synthesis is described where particular attention is devoted to the optimisation phase via template matching. Insights into the properties of the templates, have led to algorithms that aid the generation of templates. Until recently, the application of templates has been guided by different heuristics. A review of an exact template matching algorithm with a discussion of the implications of such an algorithm is given. Exact matching affects both the generation as well as the application of templates. Results from a prototype implementation are encouraging.