1 Introduction

In the current scenario with increasing complexity in VLSI circuits; managing power dissipation is an important issue in digital circuit design. With higher levels of integration and increasing scaling; Moore’s law seems to be valid yet, but in traditional (irreversible) technologies heat produced by each IC doubles [44]. Lossless computing offers an alternative, where logical operations do not yield information loss called reversible operation [36, 69]. Reversible logic realizes n-input n-output functions where a bijective relation exists between input and output vector. In a reversible logic, every input pattern can be uniquely recovered from its output pattern, so no information is lost during computation. Reversible logic circuits take care of heat loss due to information erase. Thus reversibility will become an inherent property that will help to broaden low power design [66] and quantum computation [23, 46] horizon, and also have applications to fault-tolerant designs, nanotechnology, DNA computing, optical computing, cryptography, and informatics [36, 37, 46]. Work by Landauer [22] showed that, regardless of the underlying technology, Conventional logic circuits dissipate heat in an order of kTln2 joules for every bit of information that is lost, where k is the Boltzmann constant and T is the operating temperature. Since today’s computing devices are usually built of elementary gates like AND, OR, NAND, etc., they are subject to this principle and, hence, dissipate this amount of power in each computational step.

Synthesis of reversible logic circuits differs from the conventional one in many ways. Firstly, in reversible circuit, only once every output will be taken so that no fan-out should exist. Secondly, every input pattern there should have a distinctive output pattern. In last, an acyclic circuit must be as a result. The reversible gate performs the permutation of only input functions and synthesizes the reversible functions. If a reversible gate contains k inputs and k outputs, then it is addressed as a a \(k \times k\) reversible gate. The reversible gates are only included in reversible-based layouts. In reversible designs, the input lines which has constants are known as constant inputs and the outputs which are not used as primary outputs are known as garbage outputs. An optimal design is used to keep minimal number of constant inputs and garbages. Traditional Boolean logic synthesis approaches like Karnaugh Map, Quine–McCluskey, etc. are not allowed to apply directly to synthesize a reversible-based design due to the parameters like Fan-outs, feedback from output gates to input gates are not allowed, number of inputs equal to the numbers of outputs, existence of ancilla inputs and garbage outputs, etc. So implementation only could be possible in the form of cascading of reversible gates.

Classification of synthesis algorithms is shown in Fig. 1; where we have taken the milestone works in this area. All the existing reversible logic synthesis approaches that have been proposed previously can be divided into two major groups: (a) exact approach which produces the optimal solutions, suffered from huge computation time; and (b) heuristic approaches, on the other side which provides near-optimal solutions in short computation time. They can be described in different representations like BDDs [65], positive polarity Reed–Muller expansion [14], truth-tables [38], matrix representations, permutations [59].

Fig. 1
figure 1

Classification of synthesis algorithms

Full size image

Some of these approaches perform well on smaller designs, but fails when the input count increases, either in requirement of huge computation time and memory, or failure in terms of reaching to the solution. Although having encouraging progress in the field of reversible logic synthesis, still search of best possible synthesis solution remains an open challenge for the researchers. Number of results show the practicability and extend of synthesis are generally not sufficient [25]. So, EA-based algorithm can be used to bolster the potential and efficiency of reversible-based synthesis methods.

In this survey, we present a comparative study of several metaheuristic approaches, algorithms, benchmarks, and future aspects emphasizes to the realization of reversible logic designs. This chapter is organized in following way: Sect. 2 preliminaries are introduced. Section 3 outlines evolutionary approaches. Section 4 includes algorithmic details. Section 5 presents comparison of available benchmarks and discussion which manifest the feasibility of different approaches. Finally, Sect. 6 summarizes this work.

2 GA-Based Synthesis Algorithm

Genetic Algorithm (GA) is based on heuristic search approach and optimization tool for inheriting the method of natural evolution. A GA has the ability for evolving a solution, by exploring the search space with evolutionary heuristics, in same way of genetic information transference known from the Nature [13]. GA related to the broader area of evolutionary algorithms that produces optimal solutions, which are inspired from Darwin’s theory of natural evolution, such as fitness function, selection, mutation, and crossover. GA uses an initial population, where each individual within this population is a possible solution for the problem. In GA, an initial population evolves in direction of optimal solutions. GA starts with randomly generated population of individuals and occurs in generations. Each individual of this population evolved in various steps (mutation, crossover or repeated) to produce new generation of individuals for getting a better solution. The fitness function of every individual is evaluated in every generation. Selection considered the fitness function for selecting the individuals from the current population and modified to generate a next population. This new generation is then used in upcoming iterations of the process. Usually, the process terminates after reaching maximum generations or best fitness level has been achieved for the population.

In [70], the authors proposed an array model of reversible- based designs. This paper used universal gates such as wire gate, NOT gate, Toffoli gate and Feynman gates for configuring reversible- based functions. The model consists of cascade of gate-level reversible-based units in a \(n \times m\) rectangular array fashion without the feedback and the fan-out as shown in Fig. 2, where n represents maximum input or output wire counts, m represents maximum number of cascade gate-level reversible-based units. Each chromosome generated by the cascade of T types of designable reversible functions and can be encoded by \(E = (n \cdot A + n \cdot (p_{max}+ q_{max})\cdot B)\) bits, where A \(=\left\lceil log_2T \right\rceil \) bits, B \(= \left\lceil log_2n \right\rceil \) bits, \(p_{max}\) and \(q_{max}\) are the maximum controlled wire bit-count and controlling wire bits for all designable function respectively. New individuals are generated by BSAGA [70]. A pre-bit priority mechanism has been considered to ignore multiplexing error, which happens due to multiplexing between controlling wires and controlled wires.

Fig. 2
figure 2

Array model

Full size image

In literature [27], GA algorithm is used to synthesize an exclusive-or sum-of-product (ESOP)-based structure. This method emphasizes the importance of well-designed encoding method and how it helps in fast convergence of GA. The fitness function can handle any number of inputs and outputs, and suitable for incompletely specified functions. In this work stochastic universal sampling operator is used for selection of individuals because of its population diversity.

In literature [41, 42], aiming at the genetic algorithm (GA) to optimize a given specification. The method also synthesizes incompletely-defined functions. This optimization works more efficiently if the truth table of the given specification contain don’t-care conditions and don’t-care outputs (garbage outputs). In this chapter, the music line style is used for schematic of design, and a new coding method is proposed to encode a generalized \(n \times n\) circuit with m gates, where n is maximum number of parallel input/output lines, and m represents maximum number of columns or gates placed on the parallel lines.

Fig. 3
figure 3

a Coding of a generalized reversible gate. b Chromosome of a circuit with m gates. c Toffoli gate coding

Full size image

As shown in Fig. 3a some fields are associated with each gate. The first field shows the type of gate (If T types of configurable reversible logic gates available then this field need maximum \(\left\lceil log_2T \right\rceil \) bits). The second field indicates the position of its main input or output. The line number of the main output given by this code, in number range from 0 to \({n-1}\). The r fields give information about the position of the gate inputs. For instance a \(3 \times 3\) Toffoli gate shown in Fig. 3c is encoded with 01, 10, 00, 01 (01 is considered as code of Toffoli gate). Figure 3b shows a chromosome, which represents a reversible circuit that contains m gates.

An improved ESOP-based realization of reversible function using genetic algorithm given in [10]. In this Pseudo Kronecker Expressions (PSDKROs) are used for very compact representation and the given algorithm is effective for functions having variables greater than 20.

Manna et al. [28] introduced a searching algorithm based on GA for realizing reversible layouts. This algorithm generates Toffoli gates network for realization of a reversible structure.

Table 1 Comparisons of figure of metrics based on GA
Full size table

In [4] author’s proposed a similar algorithm, which is valid for any gate library of reversible-based logic. So, this chapter encoded generalized Toffoli gates to represent solution. This algorithm is suitable up to 4 or 5 variables and fails to provide solution for larger circuits. To avoid this, factor-based permutation cycles are used. Table 1 shows various functions name and the gate count for each implementation.

3 PSO-Based Synthesis Algorithm

PSO is a stochastically optimization method introduced by Kennedy and Eberhart [18], inspired from the social behavior of creatures such as bird flocking or fish shoaling. In PSO method, particles shows the solution, wander through a multidimensional search space, at every instance each particle modify its position based upon its own experience, and as per the experience of a neighboring particles, maximizing the usage of best positions confronted by itself and its neighboring particles. The method has basic attempt to merge local and global searching techniques in order to detect best feasible solutions.

Datta et al. [3] presented a PSO-based searching methods to realizing a reversible-based design. The method has ability to find near-optimal solution without searching the complete search space. Each particle in swarm creates a network structure represented as an array of generalized Toffoli gate. The array can be codified as a string of integer [0 to \(n \times 2^{n-1}\)]. For a reversible design with n line, there are \(n \times 2^{n-1}\) possible generalized Toffoli gates. For given specification f this algorithm generates N solutions each of k gates. At the initialization stage, each particle is initialized randomly. Fitness function accounts length of gates, mismatch, hamming distance between present and desire permutation for particles in the swarm. On each iteration the positions of particles changed using well- chosen random function. To accept the new positions for the next iteration, fitness function at new and old position is compared. In [28] similar synthesis algorithm is considered. Fitness function calculated as the ratio of number of matches and the length of the permutation. Table 2 shows various function name and the gate count for each implementation.

Table 2 Comparisons of figure of metrics based on PSO
Full size table

4 Ant Colony Optimization-Based Synthesis Algorithm

ACO algorithms are most efficient and widely used algorithm motivated by the foraging behavior of ant colonies [9]. Behavioral patterns exhibited by ants can be explored to find shortest paths in graphs and similar application. They establish a communication between individuals based on a chemical substance called pheromones, which they deposit and smell during their search of food from source to nest. This behavior can be used to develop an algorithm for the solution of optimization problems. The convergence of ACO depends on pheromone deposit on their forward and backward travel.

In literature [24], the author’s introduced an ACO-based technique for reversible-based units to formulate the best-path search problem. The approach is capable to hand massive reversible operations and efficiently produces near-optimal design or optimal design having less number of gates. A generalized Toffoli gate library \(\left\{ TOF_{k}| k\le n \right\} \) is proposed to implement an n-input reversible-based operation. Each Toffoli gates is designated as \(g(\overrightarrow{c}, t)\), where c represents a vector of control bit out of n input bits, \(\overrightarrow{c}=\left\{ [c_1,c_2,\ldots ,c_n] |c_i\varepsilon \left\{ 0,1,2 \right\} , i= 1, 2,\ldots ,n \right\} \). \(c_i =\) 0 indicates positive control bit i ; \(c_i\) = 1 represents negative control bit i, and \(c_i= 2\) shows neither positive nor negative control line. t represents target bit \(t \varepsilon \left( 1, 2, \ldots ,n \right) \). Two graphs have been proposed. First a probabilistic state transition graph G(V, E) that correlates the gate selection to help the ants during efficient path search process, which dynamically updated by pheromone levels and gate count after all the ants completed their tour. Second a weighted graph G(C, A) called as an ant system graph (ASGraph) where \(C = \left\{ c_1, c_2,\ldots ,c_n \right\} \) is a finite set of elements (reversible operation). Set comprises of all the arcs (gates) linking the elements. So, the synthesis of reversible operation able to phrase like a minimization problem on an ASGraph, in which each arc weight \(w_{ij}\) is defined as the lowest cost of gates in \(a_{ij}\).

Key steps in the algorithm:

  • Speculative model for gate selection (DFS and BFS algorithm are used in local search to choose a gate \(g(\overrightarrow{c}, t)\). The speculative model decides the target bit and the value of each control bit).

  • Initialization of \(\tau _{pq}\) (Ant takes decision based on set of pheromone values \(\tau _{pq} = (\psi _{pq},\phi _{pq})\), where \(\tau _{pq}\) is the amount of pheromone for choosing bit t as target bit, and \(\phi _{pq}\) is the amount of pheromone to set control bit i as \(c_i\) for target bit t if an ant moves from state p to state q. The updated pheromone values are stored in a hash table to optimize memory utilization).

  • Pheromone update (The pheromone graph G(V, E) get updated each time after all the ants completed their tour. Gates with less quantum cost get more pheromones than other) (Figs. 4a, b and 5).

Sarkar et al. [57] presented a modified version of classical Quine–McCluskey method under the guidance of ACO techniques has been proposed. Table 3 shows various function name and the gate count for each implementation.

Fig. 4
figure 4

a State transition graph b weighted graph for reversible function

Full size image
Fig. 5
figure 5

Realization of reversible function [2, 6, 0, 5, 7, 3, 4, 1] using Toffoli gates

Full size image
Table 3 Comparisons of figure of metrics based on ACO
Full size table

5 Comparison and Discussion

To evaluate the effectiveness of EA-based synthesis algorithms, we have taken the best results available for each benchmark functions [14, 29, 52]. Table 4 shows the function name and the gate count for each implementation. We compare the best announced algorithm outputs for the NCT library. From Table 4 it is clear that the EA-based algorithm provides better results in terms of gate count (GC) in most of the cases. In other cases, synthesizing circuit using EA results with identical gates. For instance, rand_3_1, rand_3_2, which are implemented with identical gates.

Table 4 Benchmark comparison
Full size table

6 Summary

In this paper, a brief algorithmic overview on different types of EA- based synthesis approach has been provided. Comparison with existing work shows EA-based method has better performance in GC, QC, and computational cost. In the last decade, study of reversible circuits and its synthesis methods has received significant attention and the results obtained are quite encouraging, still new efficient synthesis algorithm will remain an open challenge for the researchers.