Recent Progress in the Boolean Domain

In today's world, people are using more and more digital systems in daily life. Such systems utilize the elementariness of Boolean values. A Boolean variable can carry only two different Boolean values: FALSE or TRUE (0 or 1), and has the best interference resistance in technical systems. However, a Boolean function exponentially depends on the number of its variables. This exponential complexity is the cause of major problems in the process of design and realization of circuits. According to Moore's Law, the complexity of digital systems approximately doubles every 18 month. This requires comprehensive knowledge and techniques to solve very complex Boolean problems. This book summarizes the recent progress in the Boolean domain in solving such issues. Part 1 describes the most powerful approaches in solving exceptionally complex Boolean problems. It is shown how an extremely rare solution could be found in a gigantic search space of more than 10195 (this is a number of 196 decimal digits) different color patterns. Part 2 describes new research into digital circuits that realize Boolean functions. This part contains the chapters "Design" and "Test", which present solutions to problems of power dissipation, and the testing of digital circuits using a special data structure, as well as further topics. Part 3 contributes to the scientific basis of future circuit technologies, investigating the need for completely new design methods for the atomic level of quantum computers. This section also concerns itself with circuit structures in reversible logic as the basis for quantum logic Cover 1 Title 4 Copyright 5 Contents 6 List of Figures 12 List of Tables 16 Preface 20 Foreword 26 Introduction 30 I. Exceptionally Complex Boolean Problems 32 1. Boolean Rectangle Problem 34 1.1. The Problem to Solve and Its Properties 34 1.1.1. Motivation and Selection of the Problem 34 1.1.2. The Problem in Context of Graph Theory 36 1.1.3. Rectangle-Free Grids 40 1.1.4. Estimation of the Complexity 43 1.2. Search Space Restriction 45 1.2.1. Basic Approach: Complete Evaluation 45 1.2.2. Utilization of Rule Conflicts 51 1.2.3. Evaluation of Ordered Subspaces 55 1.2.4. Restricted Evaluation of Ordered Subspaces 57 1.2.5. Analysis of the Suggested Approaches 59 1.3. The Slot Principle 62 1.3.1. Utilization of Row and Column Permutations 62 1.3.2. The Head of Maximal Grids 65 1.3.3. The Body of Maximal Grids 69 1.3.4. Experimental Results 78 1.4. Restricted Enumeration 82 1.4.1. The Overflow Principle 82 1.4.2. Strategies for Improvements 88 1.4.3. Applying Heuristics 90 1.4.4. Experimental Results 91 1.5. Permutation Classes 94 1.5.1. Potential of Improvements and Obstacles 94 1.5.2. Sequential Evaluation of Permutation Classes 96 1.5.3. Iterative Greedy Approach 97 1.5.4. Unique Representative of a Permutation Class 100 1.5.5. Direct Mapping to Representatives 104 1.5.6. Soft-Computing Results 113 2. Four-Colored Rectangle-Free Grids 118 2.1. The Problem to Solve and Its Complexity 118 2.1.1. Extension of the Application Domain 118 2.1.2. The Multiple-Valued Problem 119 2.1.3. Multiple-Valued Model 124 2.1.4. Boolean Model 125 2.1.5. Estimation of the Complexity 126 2.2. Basic Approaches and Results 129 2.2.1. Solving Boolean Equations 129 2.2.2. Utilization of Permutations 130 2.2.3. Exchange of Space and Time 132 2.3. Power and Limits of SAT-Solvers 136 2.3.1. Direct Solutions for Four-Colored Grids 136 2.3.2. Restriction to a Single Color 137 2.4. Cyclic Color Assignments of Four-Colored Grids 141 2.4.1. Sequential Assignment of a Single Color 141 2.4.2. Reusable Assignment for Four Colors 143 2.5. Four-Colored Rectangle-Free Grids of the Size 12 × 21 152 2.5.1. Basic Consideration 152 2.5.2. Grid Heads of all Four Colors 158 2.5.3. Extended Models to Solve the Grid Using a SAT-Solver 168 2.5.4. Classes of Rectangle-Free Grids G12,21 170 3. Theoretical and Practical Concepts 176 3.1. Perceptions in Learning Boolean Concepts 176 3.1.1. Boolean Concept Learning 176 3.1.2. Complexity of Boolean Concepts 179 3.1.3. The Problem of Studying Human Concept Learning 181 3.1.4. New Methodology for Studying Human Learning of Boolean Concepts 183 3.1.5. Research Methodology 188 3.2. Generalized Complexity of ALC Subsumption 189 3.2.1. Preliminaries 190 3.2.2. Interreducibilities 194 3.2.3. Main Results 196 3.2.4. Discussion of the Very Difficult Problem 200 3.3. Using a Reconfigurable Computer to Compute Algebraic Immunity 201 3.3.1. Why Do We Need Algebraic Immunity? 201 3.3.2. Why Do We Need a Reconfigurable Computer? 204 3.3.3. Background and Notation 205 3.3.4. Computation of Algebraic Immunity 208 3.3.5. Results and Comments 212 II. Digital Circuits 218 4. Design 220 4.1. Low-Power Design Techniques for State-of-the-Art CMOS Technologies 220 4.1.1. Power Dissipation and the Continuing Rule of Moore's Law 220 4.1.2. Models for Power Consumption 222 4.1.3. Power Optimization 230 4.1.4. Application Example: Baseband Communication Circuits 237 4.1.5. How Low Can Power Go? 242 4.2. Permuting Variables to Improve Iterative Re-Synthesis 244 4.2.1. Iterative Logic Synthesis 244 4.2.2. Randomness in Logic Synthesis 245 4.2.3. The Influence of the Source File Structure 246 4.2.4. The Proposed Method 251 4.2.5. Experimental Results 254 4.2.6. Convergence Analysis 259 4.2.7. Advantages of Re-Synthesis with Permutations 259 4.3. Beads and Shapes of Decision Diagrams 262 4.3.1. Three Concepts 262 4.3.2. Basic Concepts: Beads, Switching Functions, and Decision Diagrams 263 4.3.3. Beads and Decision Diagrams 266 4.3.4. Generalizations for Word-Level Decision Diagrams 271 4.3.5. Beads and the Classification in Terms of Walsh Decision Diagrams 273 4.3.6. Approaches for Classification 277 4.4. Polynomial Expansion of Symmetric Boolean Functions 278 4.4.1. Polynomials of Boolean Functions 278 4.4.2. Main Definitions 279 4.4.3. Transeunt Triangle Method 281 4.4.4. Matrix Method to Generate γ(F) and μ(F) 286 4.4.5. Efficiency of the Matrix Method 293 4.5. Weighted Don't Cares in Logic Synthesis 294 4.5.1. Don't Care Conditions in Logic Synthesis 294 4.5.2. Weighted Don't Cares 295 4.5.3. Application 297 4.5.4. Weighted BOOM: a Synthesis Tool for Functions with Weighted Don't Cares 300 4.5.5. Experimental Results 304 4.5.6. Solutions Count Analysis 306 4.5.7. Future Applications 308 4.6. Determining Assignments of Incompletely Specified Boolean Functions 309 4.6.1. Incompletely Specified Boolean Functions 309 4.6.2. Decision Diagrams for Incompletely Specified Functions 310 4.6.3. A Method for Assignment of Unspecified Values 313 4.6.4. Implementation and Experimental Results 316 4.7. On State Machine Decomposition of Petri Nets 319 4.7.1. Petri Nets as a Model of Concurrent Digital Controllers 319 4.7.2. Petri Nets: Main Definitions 320 4.7.3. Conditions of SM-Coverability of Petri Nets 322 4.7.4. Calculation of SM-Decompositions of Petri Nets 328 4.7.5. Evaluation of the Results 331 5. Test 334 5.1. Boolean Fault Diagnosis with Structurally Synthesized BDDs 334 5.1.1. From Functional BDDs to Structural BDDs 334 5.1.2. Structurally Synthesized Binary Decision Diagrams 337 5.1.3. Fault Diagnosis in the General Case of Multiple Faults 343 5.1.4. Fault Masking in Digital Circuits 348 5.1.5. Topological View on Fault Masking 352 5.1.6. Test Groups and Hierarchical Fault Diagnosis 358 5.1.7. Experimental Data 360 5.1.8. General Comments About Proposed Methods 362 5.2. Blind Testing of Polynomials by Linear Checks 363 5.2.1. Functional Testing by Linear Checks 363 5.2.2. Walsh Spectrum of Polynomials 366 5.2.3. Spectral Testing of a Given Polynomial by Linear Checks 368 5.2.4. Universal Linear Checks 371 5.2.5. Computation Complexity of Universal Linear Checks 374 III. Towards Future Technologies 378 6. Reversible and Quantum Circuits 380 6.1. The Computational Power of the Square Root of NOT 380 6.1.1. Reversible Computing Versus Quantum Computing 380 6.1.2. One-Qubit Circuits 381 6.1.3. Two-Qubits Circuits 381 6.1.4. Many-Qubits Circuits 388 6.1.5. Increased Computational Power 389 6.2. Toffoli Gates with Multiple Mixed Control Signals and no Ancillary Lines 390 6.2.1. On the Evolution of Toffoli Gates Until the Present Day 390 6.2.2. Toffoli Gates with Three Mixed Control Signals 392 6.2.3. Efficient Toffoli Gates with n > 3 Mixed Control Inputs 396 6.3. Reducing the Quantum Cost of Pairs of Multi-Control Toffoli Gates 400 6.3.1. Reversible Circuits Synthesis 400 6.3.2. Background 401 6.3.3. NCVW Quantum Circuits 403 6.3.4. Optimal Circuit Synthesis 405 6.3.5. Experimental Results and Applications 406 Bibliography 412 List of Authors 444 Index of Authors 450 Index 452 In today's world, people are using more and more digital systems in daily life. Such systems utilize the elementariness of Boolean values. A Boolean variable can carry only two different Boolean values: FALSE or TRUE (0 or 1), and has the best interference resistance in technical systems. However, a Boolean function exponentially depends on the number of its variables. This exponential complexity is the cause of major problems in the process of design and realization of circuits. According to Moore's Law, the complexity of digital systems approximately doubles every 18 months. This requires comprehensive knowledge and techniques to solve very complex Boolean problems. This book summarizes the recent progress in the Boolean domain in solving such issues.Part 1 describes the most powerful approaches in solving exceptionally complex Boolean problems. It is shown how an extremely rare solution could be found in a gigantic search space of more than 10^195 (this is a number of 196 decimal digits) different color patterns. Part 2 describes new research into digital circuits that realize Boolean functions. This part contains the chapters “Design” and “Test”, which present solutions to problems of power dissipation, and the testing of digital circuits using a special data structure, as well as further topics. Part 3 contributes to the scientific basis of future circuit technologies, investigating the need for completely new design methods for the atomic level of quantum computers. This section also concerns itself with circuit structures in reversible logic as the basis for quantum logic.