A General Decomposition for Reversible Logic

TLDR

Reversible logic synthesis differs from standard synthesis, with multi‑output gates producing unutilized outputs called garbage, and prior work has focused on minimizing either garbage or gate count. The authors aim to develop a method that simultaneously minimizes gate count, total delay, and garbage signals. The method combines standard logic synthesis techniques (Ashenhurst/Curtis decomposition, Dietmeyer’s composition, BDD preprocessing) with Reed–Muller logic tools (pseudo‑Kronecker decision and lattice diagrams) and novel reversible‑logic specific procedures to jointly reduce gates, delay, and garbage.

Abstract

Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis tasks is to reduce the number of garbage signals. Previous approaches to reversible logic synthesis minimized either only the garbage or (predominantly) the number of gates. Here we present for the first time a method that minimizes concurrently the number of gates, their total delay and the total garbage. Our method adopts for reversible logic many ideas developed previously for standard logic synthesis (such as Ashenhurst/Curtis Decomposition, Dietmeyer’s Composition, non-linear preprocessing for BDDs), methods created in ReedMuller Logic (such as Pseudo-Kronecker Decision Diagrams with Complemented Edges, Pseudo-Kronecker Lattice Diagrams and their generalizations) and introduces also new methods specific to reversible logic.