Reversible Logic Synthesis: From Fundamentals to Quantum Computing

ISBN-13: 9783540009351 / Angielski / Twarda / 2003 / 427 str.

Anas N. Al-Rabadi; A. N. Al-Rabadi

Opis

For the first time in book form, this comprehensive and systematic monograph presents the methods for the reversible synthesis of logic functions and circuits. This methodology offers designers the capability to solve major problems in system design now and in the future, such as the high rate of power consumption, and the emergence of quantum effects for highly dense ICs. The challenge addressed here 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. Researchers in academia or industry and graduate students, who work in logic synthesis, computer design, computer-aided design tools, and low power VLSI circuit design, will find this book a valuable resource.

Spis treści

1 Introduction.- 1.1 Scope of the Work.- 1.2 Organization of the Book.- 2 Fundamentals.- 2.1 Normal Galois Forms in Logic Synthesis.- 2.2 Invariant Multi-Valued Families of Generalized Spectral Tranforms.- 2.2.1 General Notation for Operations on Transform Matrices.- 2.2.2 Invariant Families of Multi-Valued Spectral Transforms.- 2.3 Summary.- 3 New Multiple-Valued S/D Trees and their Canonical Galois Field Sum-Of-Product Forms.- 3.1 Green/Sasao Hierarchy of Binary Canonical Forms.- 3.2 Binary S/D Trees and their Inclusive Forms.- 3.3 Ternary S/D Trees and their Inclusive Forms and Generalized Inclusive Forms.- 3.3.1 Ternary S/D Trees and Inclusive Forms.- 3.3.2 Enumeration of Ternary Inclusive Forms.- 3.4 Properties of TIFs and TGIFs.- 3.4.1 Properties of TIFs.- 3.4.2 Properties of TGIFs.- 3.5 An Extended Green/Sasao Hierarchy with a New Sub-Family for Ternary Reed-Muller Logic.- 3.6 Quaternary S/D Trees.- 3.7 An Evolutionary Algorithm for the Minimization of GFSOP Expressions Using IF Polarity from Multiple-Valued S/D Trees.- 3.8 Summary.- 4 Novel Methods For the Synthesis of Boolean and Multiple-Valued Logic Circuits Using Lattice Structures.- 4.1 Symmetry Indices.- 4.2 Fundamental (2,2) Two-Dimensional Lattice Structures.- 4.3 (3,3) Two-Dimensional Lattice Structures.- 4.4 New Three-Valued Families of (3,3) Three-Dimensional Shannon and Davio Lattice Structures.- 4.4.1 Three-Dimensional Lattice Structures.- 4.4.2 New (3,3) Three-Dimensional Invariant Shannon Lattice Structures.- 4.4.3 New (3,3) Three-Dimensional Invariant Davio Lattice Structures.- 4.5 An Algorithm for the Expansion of Ternary Functions Into (3,3) Three-Dimensional Lattice Structures.- 4.6 Example of the Implementation of Ternary Functions Using the New Three-Dimensional Lattice Structures.- 4.7 ISID: Iterative Symmetry Indices Decomposition.- 4.8 Summary.- 5 Reversible Logic: Fundamentals and New Results.- 5.1 Fundamental Reversible Logic Primitives and Circuits.- 5.2 The Elimination of Garbage in Two-Valued Reversible Circuits.- 5.3 Combinational Reversible Circuits.- 5.4 Novel General Methodology for the Creation and Classification of New Families of Reversible Invariant Multi-Valued Shannon and Davio Spectral Transforms.- 5.5 The Elimination of Garbage in Multiple-Valued Reversible Circuits.- 5.6 Summary.- 6 Reversible Lattice Structure.- 6.1 A General Algorithm for the Creation of Two-Valued and Multiple-Valued Reversible Lattice Structures.- 6.2 Summary.- 7 Novel Reconstructability Analysis Structures and their Reversible Realizations.- 7.1 New Type of Reconstructability Analysis: Two-Valued Modified Reconstructability Analysis (MRA).- 7.2 Multiple-Valued MRA.- 7.3 Reversible MRA.- 7.4 Summary.- 8 New Reversible Structures: Reversible Nets, Reversible Decision Diagrams, and Reversible Cascades.- 8.1 Reversible Nets.- 8.2 Reversible Decision Diagrams.- 8.3 Reversible Cascades.- 8.3.1 The Realization of GFSOP Expressions Using Reversible Cascades.- 8.4 Summary.- 9 Initial Evaluation of the New Reversible Logic Synthesis Methodologies.- 9.1 Complete Examples.- 9.2 Initial Comparison.- 9.3 Summary.- 10 Quantum Logic Circuits for Reversible Structures.- 10.1 Notation for Two-Valued and Multiple-Valued Quantum Circuits.- 10.2 Quantum Circuits.- 10.3 Summary.- 11 Quantum Computing: Basics and New Results.- 11.1 Fundamentals of Two-Valued Quantum Evolution Processes and Synthesis.- 11.1.1 Mathematical Decompositions for Quantum.- 11.2 New Two-Valued Quantum Evolution Processes.- 11.3 Novel Representations for Two-Valued Quantum Logic: Two-Valued Quantum Decision Trees and Diagrams.- 11.4 Fundamentals of Multiple-Valued Quantum Computing.- 11.5 New Multiple-Valued Quantum Chrestenson Evolution Process, Quantum Composite Basis States, and the Multiple-Valued Einstein-Podolsky-Rosen (EPR) Basis States.- 11.6 New Multiple-Valued Quantum Evolution Processes, Generalized Permuters, and their Circuit Analysis.- 11.7 Novel Representations for Multiple-Valued Quantum Logic: Multiple-Valued Quantum Decision Trees and Diagrams.- 11.8 Automatic Synthesis of Two-Valued and Quantum Logic Circuits Using Multiple-Valued Evolutionary Algorithms.- 11.9 Quantum Computing for the New Two-Valued and Multiple-Valued Reversible Structures.- 11.10 Summary.- 12 Conclusions.- Appendices.- A Count of the New Invariant Shannon and Davio Expansions.- B Circuits for Quaternary Galois Field Sum-Of-Product (GFSOP) Canonical Forms.- D Universal Logic Modules (ULMs) for Circuit Realization of Shannon/Davio (S/D) Trees.- E Evolutionary Computing: Genetic Algorithms (GA) and Genetic Programming (GP).- F Count for the New Multiple-Valued Reversible Shannon and Davio Decompositions.- G NPN Classification of Boolean Functions and Complexity Measures.- H Initial Evaluation of the New Modified Reconstructability Analysis and Ashenhurst-based Decompositions: Ashenhurst, Curtis, and Bi-Decomposition.- I Count for Reversible Nets.- J New Optical Realizations for Two-Valued and Multiple-Valued Classical and Reversible Logics.- K Artificial Neural Network Implementation Using Multiple-Valued Quantum Computing.

Blurb

This book presents for the first time comprehensive and systematic methods for the reversible synthesis of logic functions and multi-dimensional logic circuits. This methodology is able to solve major problems in system design today and in the future, namely the high rate of power consumption, and the emergence of quantum effects and properties for highly dense and nano-scale ICs. The challenge is to design nano-scale 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. Researchers in academia or industry and graduate students, who work in logic synthesis, computer design, computer-aided design tools, and low power VLSI circuit design, will be interested in this book