Reversible Logic Synthesis

Computing structures have been evolving since early times of mankind. Such structures evolved from simple systems that use simple mechanical elements such as ropes and pulleys, to mechanical systems that use carefully designed elements, to machines that use discrete electronic elements, to nowadays computing machinery that uses highly complex integrated electronic elements [256]. The power of the computing machinery has been growing with the growing of the complexity of such machines for processing, storage, and interfacing capabilities. This is observed in the fact that the pre-electronic computing machines were able only to perform basic arithmetic calculations, while modern computing machines that are made up of highly complex electronic integrated circuits (ICs) are capable of performing many more tasks such as three-dimensional graphics (i.e., 3-D visualizations) and networking. This evolution of computing has been driven by the need to fulfill the increasingly demanding design specifications of more speed, less power consumption, smaller size, better testability, better reliability, and more regularity.

This Chapt. presents the necessary mathematical background and the fundamental formalisms of the work that will be introduced and further developed in the next Chapts. This includes the main reversible decompositions in Chapt. 5 that will be used to construct reversible primitives, from which reversible structures are built in Chapts. 6, 7 and 8, respectively. Also, the foundations that are introduced in this Chapt. will be used to construct the quantum gates and their associated quantum circuits and computing in Chapt. 11.

Economical and highly testable implementations of Boolean functions [99,198,199,204,217], based on Reed-Muller (ANDEXOR) logic, play an important role in logic synthesis and circuit design. AND-EXOR circuits include canonical forms (i.e., expansions that are unique representations of a Boolean function). Several large families of canonical forms: Fixed Polarity Reed- Muller (FPRM) forms, Generalized Reed-Muller (GRM) forms, Kronecker (KRO) forms, and Pseudo-Kronecker (PSDKRO) forms, referred to as the Green/Sasao hierarchy, have been described [4,9]. Because canonical families have higher testability and some other properties desirable for efficient synthesis, especially of some classes of functions, they are widely investigated. A similar ternary version of the binary Green/Sasao hierarchy was developed in [4]. This new hierarchy will find applications in minimizing Galois field Sum-Of-Product (GFSOP) expressions (i.e., expressions that are in the sum-of-product form which uses the additions and multiplications of arbitrary radix Galois field that was introduced in Chapt. 2), creation of new forms, decision diagrams, and regular structures (Such new structures will be discussed in details in Appendix D.)

This Chapt. presents a new type of regular structures that will be used to produce regular reversible lattice structures in Chapt. 6. With future logic realization in technologies that are scaled down rapidly in size, the emphasis will be increasingly on the mutually linked issues of regularity, predictable timing, high testability, and self-repair. For the current leading technologies with the activedevice count reaching the hundreds of millions, and most of the circuit areas occupied by local and global interconnects, the delay of interconnects is responsible for about 40–50% or more of the total delay associated with a circuit [51,229]. In future technologies, interconnects will take an even higher percent of area and delay which creates interest in cellular (regular) structures [109,209], especially for nano technologies [109].

Due to the anticipated failure of Moore’s law around the year 2020, quantum computing will hopefully play an increasingly crucial role in building more compact and less power consuming computers [93,107,167,248,253]. Due to this fact, and because all quantum computer gates (i.e., building blocks; primitives) must be reversible [37,38,39,73,74,75,95,97,139,150,167,203,245,246], reversibility in computing will have increasing importance in the future design of regular, compact, and universal structures and machines (systems). (n,k) reversible circuits are circuits that have (n) inputs and (k) outputs and are one-to-one mappings between vectors of inputs and outputs, thus the vector of input states (values) can be always uniquely reconstructed from the vector of output states (values). (k,k) reversible circuits are circuits that have the same number of inputs (k) and outputs (k) and are one-to-one mappings between vectors of inputs and outputs, thus the vector of input states (values) can be always uniquely reconstructed from the vector of output states (values). Conservative circuits [98,210,211,212] are circuits that have the same number of values in inputs and outputs (e.g., the same number of ones in inputs and outputs for binary, the same number of ones and twos in inputs and outputs for ternary, etc). Conservativeness exists naturally in physical laws where no energy is created or destroyed.

This Chapt. will introduce a methodology of synthesizing binary and multiple-valued logic functions using a regular reversible structure. This will be done by utilizing the new reversible binary and multiple-valued Shannon primitives that were introduced in Theorem 5.1, and the use of the process of permutation of cofactors that resulted from the new reversible Shannon primitives. The new idea in this Chapt. is:

This Chapt. will introduce another new type of reversible structures called Reversible Modified Reconstructability Analysis (RMRA). Reconstructability Analysis (RA) is an important decomposition technique that is used widely in system science area to decompose qualitative data [133,134,135,138,273,275]. This kind of decomposition is commonly used in the decomposition of data obtained in the social and system science fields, and overlaps with other decomposition techniques used in the social sciences as well like the Log-Linear (LL) decomposition method [138]. RA decomposition aims at the simplest decomposition of qualitative data using Lattice-Of-Structure (LOS) (cf. Fig. 7.1) as representation (generation) and contingency tables (for probabilistic data) for evaluation (minimization of error).

In Chapts. 6 and 7 two reversible decompositions were created: reversible lattice structures and reversible Modified Reconstructability Analysis. While these reversible structures exhibit certain regularities, yet they generate a big “garbage” at the output which requires the use of the mirror image (i.e., inverse) reversible circuit to eliminate such “garbage”. This Chapt. will provide a variety of new reversible structures, which can possess advantages that the previous reversible structures did not have like the use of minimal garbage or no garbage at all in some cases. Since garbage is a big issue in reversible logic synthesis, search heuristics for reversible logic synthesis should include the following: (1) do not create many outputs of gates and sub-circuits, (2) re-use these outputs as inputs in other gates or sub-circuits, (3) apply re-usability properties of these common sub-functions and symmetry is one of such properties, (4) the method must be general, and (5) use regularity and algebraic properties (e.g., group, field, or linear properties) to create more powerful reversible structures. The new contributions of this Chapt. are:

This Chapt. introduces an initial evaluation of the implementation of the reversible structures that have been presented in Chapts. 6, 7, and 8 to realize logic functions. Although this evaluation is for functions with relatively small number of arguments, it still gives an important first look to some of the weaknesses, strengths, and new properties of the previously introduced reversible structures.

The reversible structures that are introduced in previous Chapts. can be implemented, utilizing the garbageless circuits of such structures, using many possible technologies, including optical [17,24,62,63,64,65,222], and CMOS [35,68,70,206,262,263]. We are interested in this Chapt. with the implementation of the reversible structures using quantum logic circuits. This will be a second step, after the reversibility step from Chapts. 6, 7, and 8, towards quantum computing of such structures (that will be introduced in Chapt. 11). The main contribution of this Chapt. is the introduction of the quantum circuits for two-valued and multiplevalued reversible structures using the corresponding quantum notation.

Trends in computer hardware are leading toward higher density and lower energy dissipation. Ultimately, some approaches should result in packing extremely high densities in excess of 1017 logic devices in a cubiccentimeter. The trend towards higher packing density strongly influences energy dissipation. Conventional devices must dissipate more than K·T·ln(2) Joules in switching (cf. Fig. 1.1), and thus enormous amounts of power will be needed for computing using classical methods of computations [116]. Even an idealized device, which uses a one Volt power supply and dissipatively discharges a single electron to ground during the switching operation, would dissipate one electron Volt per switching operation. At T = 300 Kelvins, this is 40·K·T per switching operation or about 160,000,000 Watts for a computer with 10¹⁷ logic elements operating at 10 GHz. If each switching operation involves hundreds of electrons then the energy dissipation enters the multi gigaWatt range.

The biggest problems in system design today, and in the future, are the high rate of power consumption and the emergence of quantum effects for highly dense ICs. The real challenge is to design reliable systems that consume as little power as possible and in which the signals are processed and transmitted at very high speeds with very high signal integrity. The tools that are used to design ICs using the conventional design methodologies apply the area, delay, and power constraints. The synthesis approaches that are implemented using such computer-aided design tools are only for the classical type of synthesis.