Published In

Proceedings of Reed-Muller 2007

Document Type

Conference Proceeding

Publication Date

2007

Subjects

Computer algorithims, Quantum computers

Abstract

There is a need to convert non-reversible functions to their corresponding reversible functions to be realized as reversible cascades. The original MMD (D.M.Miller, D. Maslov, and G.W.Dueck) algorithm for synthesis of reversible functions using cascades of reversible gates [1] can be modified to allow for the inclusion of “don't cares” within the given function's truth table (reversible or irreversible). This was achieved in the approach presented, by first initializing the “don't cares” to binary values, synthesizing the network using the base MMD algorithm, comparing the cost, and iterating to find an implementation with the smallest possible cost. The “don't care” assignment leading to the circuit with the minimal cost can be determined. This paper discusses this algorithm that is an additional module to the MMD algorithm, the results, the pros and cons of using such an algorithm, and future work to improve the proposed algorithm. A heuristic is also covered, that is superior to the traditional backtracking algorithm and can quickly find an MMD solution with minimum cost for circuits that don’t have large number of “don’t cares”.

Description

This is the author's version of a paper which was presented at Reed-Muller 2007, Oslo University, May 16, 2007, Oslo, Norway. Subsequently published in Proceedings of Reed-Muller 2007 (2007): 59-65.

Persistent Identifier

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

Download

Share

COinS