Published In

Facta universitatis - series: Electronics and Energetics

Document Type

Conference Proceeding

Publication Date

12-2010

Subjects

Logic synthesis, Logic circuits -- Design and construction, Reversible logic

Abstract

This paper presents a new algorithmMP (multiple pass) to synthesize large reversible binary circuits without ancilla bits. The well-known MMD algorithm for synthesis of reversible circuits requires to store a truth table (or a Reed-Muller - RM transform) as a 2n vector to represent a reversible function of n variables. This representation prohibits synthesis of large functions. However, in MP we do not store such an exponentially growing data structure. The values of minterms are calculated in MP dynamically, one-by-one, from a set of logic equations that specify the reversible circuit to be designed. This allows for synthesis of large scale reversible circuits (30-bits), which is not possible with any existing algorithm. In addition, our unique multi-pass approach where the circuit is synthesized with various, yet specific, minterm orders yields quasi-optimal solution. The algorithm returns a description of the quasi-optimal circuit with respect to gate count or to its “quantum cost”. Although the synthesis process in MP is relatively slower, the solution is found in real-time for smaller circuits of 8 bits or less.

Description

This is the publisher's final PDF. Copyright 2010, University of Nis. Article may be found at http://scindeks.ceon.rs/article.aspx?artid=0353-36701003273A

Persistent Identifier

http://archives.pdx.edu/ds/psu/12961

Download

Share

COinS