Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
446 lines (280 sloc) 45.8 KB

COST logo Action logo

COST Action IC1405: Reversible Computation - Extending Horizons of Computing

State of the Art Report Working Group 3: Reversible logic synthesis

Mathias Soeken, Integrated Systems Laboratory, EPFL, Switzerland (Editor)

Contributors

  • Nabila Abdessaied, University of Bremen, Germany
  • Pawel Kerntopf, University of Lodz, Poland
  • Claudio Moraga, Technical University of Dortmund, Germany
  • Krzysztof Podlaski, University of Lodz, Poland
  • Mathias Soeken, Integrated Systems Laboratory, EPFL, Switzerland
  • Robert Wille, Department for Integrated Circuit and System Design, Johannes Kepler University Linz, Austria

Table of Contents

Preface

This report presents the state of the art within reversible logic synthesis. The work was initiated by Working Group 3 of the COST Action IC 1405 on reversible computations. The contents have been provided by leading experts of the different research fields that are covered.

More on the project:

Overview

Overview

We classify reversible synthesis algorithms using 4 levels of categorization:

  1. Reversibility of the input: we distinguish between nonreversible and reversible functions. Embedding is not part of this categorization and need to be applied as a preprocess if needed. Columns in the overview figure refer to this level.
  2. Manipulation of the input: if the synthesis algorithm modifies the input during execution or emphasizes on the underlying function of the input rather than its structure, we refer to the synthesis approaches as functional synthesis, otherwise as structural synthesis. Functional synthesis algorithms guarantee optimum lines during synthesis and may also allow optimum number of gates. Rows in the overview figure refer to this level.
  3. Algorithm: For each category several algorithms may be proposed which differ in their conceptual methodology. Items in boxes refer to this level.
  4. Implementation: Each algorithm can be implemented in several different ways using several different data structures for the input representation. This level is not visible in the overview figure but discussed in the following text.

Example: The original transformation-based synthesis algorithm from D.M. Miller, D. Maslov and G.W. Dueck [DAC 40, 2003, 318-323.] starts from a reversible input function (1) and it is functional (2). Obviously, it falls in the category of transformation-based synthesis algorithms (3) and the specific works marks one of many implementations in this category (4).

Function representations

We differentiate representations based on whether they are used to represent irreversible or reversible functions. Of course, irreversible functions include the reversible ones, but the function representation is not capturing this in the sense that it does not allow for dedicated treatment. Instead, function representations for reversible functions naturally reflect the reversibility of the function.

Representations for irreversible functions

Truth tables

A truth table for a single Boolean function over n variables can be considered as a bitstring of size 2n, in which each bit represents the truth value for an assignment. The input assignments are lexicographically ordered from 0...0 to 1...1.

Binary decision diagram

A binary decision diagram (BDD) is based on Shannon's expansion. Nodes represent functions and are labeled with a variable. Two children represent the negative and positive children of the node's function with resect to the node's variable. Reduction rules can compress the size of the BDD: a node can be skipped if both children are the same and if two nodes represent the same function only one needs to be kept. If co-factors are applied in the same order on each path and if reductions are applied as long as possible, one reaches a canonical representation, i.e., for any given function from each starting point the same representation is finally reached.

Representations for reversible functions

Truth tables

With n truth tables for Boolean functions over n variables one can represent a reversible function. In such a setting, it is easier to consider the mapping of input to output patterns. Only if all output patterns occur, the truth tables represent a reversible function.

Permutations in S2n and permutation cycles

A reversible function always implements a bijective mapping between input and output binary signals. That means a reversible function is an permutation of its inputs. It is known that any permutation can be decomposed into a product of cycles. Any permutation can be represent uniquely, up to the order, as product of disjoint cycles. Two cycles are called disjoint if they have no common members. Additionally any permutation cycle of length at least 4 can be written as a product of 3-cycle and 2-cycles. For example function f=[1,0,3,2,6,4,5,7] can be written in cycle form as (0,1)(2,3)(4,6,5).

Gate libraries

NCT (Not, CNOT, Toffoli)

NOT CNOT Toffoli
NOT CNOT Toffoli

The NCT library consists of the three gates NOT, CNOT, and Toffoli. The Toffoli gate is a double-controlled NOT gate. These gates are universal in a sense, that every Boolean function can be realized if an arbitrary number of variables (lines) is permitted. Given n variables, the NCT gate library can realize all permutations over n ≤ 3 variables and all even permutations over n > 3 variables.

MCT (Multiple-controlled Toffoli gates)

MCT
MCT

The MCT library consist of NOT, CNOT, Toffoli, and multi-controlled NOT gates. An MCT gate with n variables has (n-1) controls and one target. Each of the control line values pass through the gate unaltered while the target line value is inverted if all the control lines are set to 1.

MPMCT (Mixed-polarity Multiple-controlled Toffoli gates)

MPMCT
MPMCT

The MPMCT library is more general than the MCT library. The controls of the MPMCT gates cannot only have positive polarity but also negative polarity. In this case, the target line value is inverted if all the positive control lines are set to 1 and all the negative control lines are set to 0.

STG (Single-target gates)

Single-target-gate
STG

Given n variables, a single-target gate (ST) has a control function c instead of control variables. The control function is a Boolean function with (n-1) inputs and one output. The target line is inverted if and only if c evaluates to true. All other variables remain unchanged. The target line cannot be in the support of c.

Embedding

Most of the practical relevant functions are irreversible, but most of the existing reversible synthesis algorithms require a reversible function as input in some representation. Embedding is a technique that refers to algorithms that extend irreversible functions by additional inputs and outputs such that they are reversible, but under some given projection equal the initial irreversible function. A projection assigns some input variables to constants and discards some output variables. Every irreversible n-input/m-output function can be embedded by a reversibe function over n+m variables, however, often better embeddings are possible. In order to compute the optimum number of variables in a reversible embedding one needs to count the occurrance of the most frequent output pattern. It has been shown that finding an optimum embedding is coNP-hard. Both truth table based embedding algorithms and symbolic embedding alrogithms that work on the BDD representation of the function have been presented.

Synthesis algorithms for reversible functions

Functional exact algorithms

Exact synthesis algorithms guarantee minimality in number of gates (time) and number of lines (space).

SAT-based synthesis

Given a truth table of a Boolean function f, the decision problem “Does there exist a reversible circuit with k gates that represents f?” is translated into a SAT problem. A circuit can be extracted from a satisfying assignment to the problem. Asking the question, starting from k being 0 and incrementing it until the problem is satisfiable, gives the gate-optimum circuit.

Input representations: truth table

Gate libraries: MCT, MPMCT

Implementations: RevKit (command: exs --mode 1), RevKit (command: exs --mode 0)

References:

Enumerative synthesis

Due to the use of a precomputed database of all gate-optimal 4-input reversible circuits up to 8 or 9 gates, generated by exhaustive calculations, it is possible to develop a tool for gate-optimal synthesis of any 4- variable reversible function (4-input gate-optimal circuits require at most 15 gates). In a similar way a tool for reducing quantum cost of 4-input reversible circuits can be developed. Such tools has been implemented and also used for constructing provably gate-optimal reversible circuits of any number of inputs by extrapolating properties of 3-input and 4-input optimal circuits.

Input representations: truth table

Gate libraries: MCT, MPMCT

References:

Functional heuristic algorithms

Functional heuristic synthesis algorithms guarantee minimality in number of lines (space).

Transformation-based synthesis

Starting from a reversible function, transformation-based synthesis applies gates and adjusts the function representation accordingly in a way that each gate application gets the function closer to the identity function. If the identity function has been reached, all applied gates make up for the circuit that realizes the initial function.

Input representations: truth table, RCBDD

Gate libraries: MCT, MPMCT (only negative controls), MCT+F

Implementations: RevKit (command: tbs), RevKit (command: tbs -b and tbs -s)

References:

Cycle-based synthesis

Every reversible function can be written in the form of disjoint cycles. For every cycle one can create a circuit that represents the cycle. By concatenating all cascades for each cycle, a reversible circuit can be created.

Input representations: truth table, permutation, cycles

Gate libraries: MCT, MPMCT

References:

Decomposition-based synthesis

In decomposition-based synthesis the reversible function is iteratively decomposed into simpler functions based on the Young subgroup decomposition: Given a line i, every reversible function f can be decomposed into three functions f = g1f'g2, where g1 and g2 can be realized with a single-target gate on line i and f' is a reversible function that does not change in line i. Based on this decomposition, synthesis algorithms determine the gates for g1 and g2 and then recur on f'.

Input representations: truth table, RCBDD

Gate libraries: STG

Implementations: RevKit (command: dbs), RevKit (command: dbs -s)

References:

Metaheuristic synthesis

Synthesis in these category synthesize a circuit based on a metaheuristic such as genetic algorithms, genetic programming, ant colony optimization, or particle swarm optimization.

Input representation: truth table

Gate libraries: MCT, MCT+P (in principle, any functionally complete set of gates may be used)

References:

Greedy synthesis

Greedy synthesis is similar to transformation-based synthesis. At each step it applies a set of gates to the current function to be synthesized and chooses the gate that brings the function closest to the identity function.

Input representation: BDD

Gate libraries: arbitrary

References:

Synthesis algorithms for nonreversible functions

Structural algorithms

Structural algorithms do neither guarantee optimality for number of gates nor for number of lines.

ESOP-based synthesis

An ESOP expression of a function f is an exclusive sum of products. Given an ESOP expression of a function, it can easily be translated into a cascade of Toffoli gates by adding one additional circuit line to store the result. This line is initialized with 0 and for each product term in the ESOP expression a MPMCT gate is added with controls according to the produc term and a target on the additional line. If MCT circuits are targeted, negative controls can be realized using NOT gates. In this case, the aim is to minimize the number of NOT gates.

Gate libraries: MCT, MPMCT

Implementations: RevKit (command: esopbs)

References:

Hierarchical synthesis

In hierarchical synthesis the function is represented in a structural way, e.g., using a logic network. Then, small subparts of the structure are considered functionally, embedded into reversible functions and synthesized using functional algorithms. The resulting reversible circuits are combined with respect to the structural representation of the function. This combination of subcircuits leads to an additional number of lines, which are essentially required to store intermediate computation steps.

Input representation: BDD, AIG, XMG

Gate libraries: imposed by the underlying functional synthesis algorithm

Implementations: RevKit (command: hdbs), RevKit (command: cbs), RevKit (command: lhrs), RevKit (command: dxs)

References:

Building block synthesis

Building block synthesis relies on existing realizations of frequently used functions/operations as well as a higher level description of the functionality to be synthesized, e.g., in terms of hardware description languages (HDLs). It represents a complementary approach to the synthesis approaches reviewed above: The function to be synthesized is described in HDL terms, while existing building blocks are employed to create the corresponding netlists. Main challenges remain the composition of the respectively described data and control flow.

Input representation: SyReC description

Gate libraries: MCT, MPMCT

References:

References