Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Embedding of large Boolean functions for reversible logic
Soeken M., Wille R., Keszocze O., Miller D., Drechsler R. ACM Journal on Emerging Technologies in Computing Systems12 (4):1-26,2015.Type:Article
Date Reviewed: Feb 22 2016

In this paper, the authors present solutions to embedded large irreversible functions, which are considered a problem in reversible circuit synthesis. The main contributions include three algorithms for determining the number of additional lines of large irreversible functions (one heuristic cube-based algorithm and two exact cube-based and binary decision diagram (BDD)-based ones) and two algorithms for embedding large irreversible functions (one exact cube-based algorithm and one heuristic BDD-based algorithm). The details are described in sections 5 and 6.

Since most Boolean functions of practical interest are irreversible, such functions are embedded into reversible ones prior to synthesis. Determining an efficient embedding for large irreversible functions is an open research problem that affects the synthesis performance for reversible logic. This paper provides algorithms that enable embedding of functions containing up to hundreds of variables, although efficient embedding of irreversible functionality has been restricted to very small functions.

Some experimental results using these algorithms are illustrated in section 7. Instead of implementing these proposed functions as circuits and showing the performance as gate count, maximum of frequency, latency, and power/energy consumption, the authors list experimental results as the number of additional lines. The reason is explained in this section.

In conclusion, the algorithms are novel. The implementation and evaluation are thorough and indeed show that the algorithms can be used effectively for compact embeddings of functions containing a large number of variables.

Reviewer:  Xiaokun Yang Review #: CR144182 (1607-0499)
Bookmark and Share
 
Design Aids (B.6.3 )
 
 
Combinatorics (G.2.1 )
 
 
Computer-Aided Engineering (J.6 )
 
Would you recommend this review?
yes
no
Other reviews under "Design Aids": Date
Some results on the design of regular structured sequential circuits
Grass W. Integration, the VLSI Journal 3(3): 189-210, 1985. Type: Article
Nov 1 1986
Specification and design of embedded systems
Gajski D., Vahid F., Narayan S., Gong J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1994. Type: Book (9780131507319)
Nov 1 1995
Leakage power minimization for the synthesis of parallel multiplier circuits
Shin K., Kim T.  VLSI (Proceedings of the 14th ACM Great Lakes Symposium on VLSI, Boston, MA, USA, Apr 26-28, 2004)166-169, 2004. Type: Proceedings
Jul 22 2004
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy