Further improvements in the Boolean domain / edited by Bernd Steinbach.

Format:

Book

Contributor:

Steinbach, Bernd, editor.

Language:

English

Subjects (All):

Algebra, Boolean--Congresses.

Algebra, Boolean.

Digital electronics--Design and construction.

Digital electronics.

Physical Description:

1 online resource (xli, 494 pages)

Edition:

1st ed.

Place of Publication:

Newcastle upon Tyne, UK : Cambridge Scholars Publishing, 2018.

Summary:

The amount of digital systems supporting our daily life is increasing continuously. Improved technical facilities for their production have led to growing challenges for engineers and scientists working in the Boolean domain. A Boolean variable can only carry 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 reason for 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 volume represents the third book in a series that provides further insights into the Boolean domain.Part 1 explores powerful models, methods and techniques which improve the efficiency in solving Boolean problems of extreme complexity. The universality of Boolean equations as a model to solve Non-deterministic Polynomial-time (NP) hard problems, as well as special properties of index generation functions, spectral techniques, or relational approaches, is discussed here. Both hardware devices, such as Field Programmable Gate Arrays (FPGAs) or Graphics Processing Units (GPUs), and optimized algorithms realized in software contribute to the acceleration of Boolean calculations. Part 2 contributes to the synthesis and visualization of digital circuits, and provides interesting new solutions for several types of circuits. A comprehensive collection of benchmarks supports the evolution of both existing and new synthesis approaches. The continuous reduction of the size of the transistors increases the challenges with regard to the reliability of the circuits. Part 3 describes several new

approaches for the synthesis of reversible circuits. These approaches, as well as a classification of reversible functions, extend the basis of future quantum computers.

Contents:

Intro

Contents

List of Figures

List of Tables

Foreword

Preface

Acknowledgments

List of Abbreviations

I Extensions in Theory and Computations

1 Models, Methods, and Techniques

1.1. NP-Problems and Boolean Equations

1.1.1. Classes of Hard Problems

1.1.2. Boolean Functions and Equations

1.1.3. Boolean Equations and Ternary Vectors

1.1.4. NP-Complete Problems

1.1.5. Boolean Equations - a Unifying Instrument

1.2. Analysis of the Number of Variables to Represent Index Generation Functions

1.2.1. Background

1.2.2. An Index Generation Unit

1.2.3. Notation

1.2.4. Expected Number of Variables in the Minimal Distinguishing Set

1.2.5. Distribution of the Expected Number of Distinguishing Columns

1.2.6. Expected Number of Balanced Columns in Random Binary Matrices

1.2.7. Found Results

1.3. Computational Complexity of Error Metrics in Approximate Computing

1.3.1. Approximate Computing

1.3.2. Preliminaries

1.3.3. Error Metrics

1.3.4. Complexity of Computing Error Metrics

1.4. Spectral Techniques - Origins and Applications

1.4.1. Origins and Evolution of Spectral Techniques

1.4.2. Digital System Design

1.4.3. Signal processing

1.4.4. Towards FFT

1.4.5. Towards Alternative Spectral Techniques

1.4.6. Applications of Spectral Techniques

1.5. A Relational Approach to Finite Topologies

1.5.1. Experimentation as Motivation

1.5.2. Relation Algebra

1.5.3. Modeling Sets and Finite Topologies

1.5.4. Closures, Interiors and Boundaries

1.5.5. Topological Relations and Random Topologies

1.5.6. Implementation and Related Work

1.6. A Real-World Model of Partially Defined Logic

1.6.1. Real-World Asynchronous Feedback

1.6.2. Related Topics

1.6.3. Use Case: Low-Active RS-Latch

1.6.4. Functionally Stabilized Dual-Rail Implementation.

1.6.5. Results

2. Accelerated Computations

2.1. Bent Function Enumeration by a Circular Pipeline Implemented on an FPGA

2.1.1. Background

2.1.2. Properties of Bent Functions

2.1.3. Architecture for Bent Function Discovery

2.1.4. Circular Pipeline Architecture

2.1.5. Circuit of the Circular Pipeline

2.1.6. Experimental Results

2.1.7. Analytical Results

2.1.8. Practical Aspects

2.2. Efficient Random Generation of Bent Functions Using a GPU Platform

2.2.1. Discovery of Bent Functions

2.2.2. Bent Functions in Reed-Muller and Walsh Domains

2.2.3. Random Generation of Bent Functions in the Reed-Muller Domain

2.2.4. Implementation of Random Generation of Bent Functions on a GPU Platform

2.2.5. Comparison of Random Generation of Bent Functions on CPU and GPU Platforms

2.3. Multi-GPU Approximation for Silent Data Corruption of AN Codes

2.3.1. Error Detection and Correction

2.3.2. Computing Distance Distribution of AN Codes

2.3.3. Results

2.3.4. Summary

2.4. Orthogonalization of a TVL in Disjunctive or Conjunctive Form

2.4.1. Orthogonality

2.4.2. Ternary Vector List (TVL)

2.4.3. Orthogonal Operations for Ternary Vectors

2.4.4. Orthogonalization of a TVL in Disjunctive or Conjunctive Form

2.4.5. Experimental Results

II Digital Circuits

3. Synthesis, Visualization, and Benchmarks

3.1. Vectorial Bi-Decompositions for Lattices of Boolean Functions

3.1.1. Synthesis of Combinational Circuits

3.1.2. Vectorial and Single Derivative Operations

3.1.3. Generalized Lattices of Boolean Functions

3.1.4. Vectorial Bi-Decompositions

3.1.5. Application of the Vectorial Bi-Decomp

3.1.6. Comparison with Other Synthesis Approaches

3.2. Hardware/Software Co-Visualization: The Lost World

3.2.1. The Lost World

3.2.2. Visualization Techniques

3.2.3. Core Issues.

3.2.4. Enabling the Fiddlers and Tinkerers

3.2.5. A Brave New World

3.3. Synthesis of Complemented Circuits

3.3.1. Decomposition with Two-Input Boolean Operators

3.3.2. Previous Work

3.3.3. Boolean Relations

3.3.4. Complemented Circuits

3.3.5. Minimization of Complemented Circuits

3.3.6. Structure of Complemented Circuits

3.3.7. Experimental Results

3.4. Design of Multipliers Using Fourier Transformations

3.4.1. Approaches for Multiplication on Hardware

3.4.2. Design of Monolithic Multipliers

3.4.3. The Adder Tree in Multiplication

3.4.4. Discussion of the Results

3.5. Race-Free State Assignment for Low Power Asynchronous Automaton

3.5.1. Synthesis for Low Power Consumption

3.5.2. A Behavioral Model of an Asynchronous Automaton

3.5.3. The Condition for Absence of Critical Races

3.5.4. Minimizing the Length of State Codes

3.5.5. Minimizing the Switching Activity of Memory Elements

3.5.6. A Heuristic Method

3.6. Boolean Discrete Event Modeling of Circuit Structures

3.6.1. Different Abstraction Levels for Modeling

3.6.2. Theoretical Foundation

3.6.3. Syntax for Discrete Event Modeling Based on Partially and Totally Specified Propositions

3.6.4. Use Case: Discrete Event Modeling and Composition of a CMOS Inverter

3.6.5. Results

3.7. A Prudent Approach to Collection of Examples for Logic Synthesis and Optimization

3.7.1. The Reasons to be Prudent

3.7.2. Benchmarks to Compare Design Tools

3.7.3. Origins of Benchmarks

3.7.4. Transformations to Improve the Usability of Benchmarks

3.7.5. A Provided Collection of Benchmarks

3.7.6. Examples and Statistical Properties

4. Reliability and Linearity of Circuits

4.1. Low Complexity High Rate Robust Codes

4.1.1. The Hardware Security Problem

4.1.2. Security Versus Reliability

4.1.3. Robust Codes.

4.1.4. The Shortened QS Code

4.1.5. The Triple QS and Triple Sum Codes

4.2. Synthesis Techniques for Reliability Using Bi-Decompositions

4.2.1. Methods to Improve the Reliability of Circuits

4.2.2. Synthesis for Reliability

4.2.3. Experimental Results

4.2.4. Reliability

4.3. On Linearization of Partially Defined Boolean Functions and Applications to Linear Codes

4.3.1. Partially Defined Boolean Functions

4.3.2. The Linearization Method

4.3.3. An Efficient Method of Finding a Linear Transform Injective on S

4.3.4. Existence of an Injective Linear Transformation

4.3.5. Connections to Linear Error-Correcting Codes

III Towards Future Technologies

5. Reversible and Quantum Logic

5.1. Procedure for FDD-Based Reversible Synthesis by Levels

5.1.1. Methods to Synthesize Reversible Circuits

5.1.2. Post-Order FDD-Based Reversible Synthesis

5.1.3. FDD-Based Reversible Synthesis by Levels

5.1.4. Experimental Results

5.2. Distributed Evolutionary Design of Reversible Circuits

5.2.1. Extending RIMEP2 to DRIMEP2

5.2.2. Background

5.2.3. The Hierarchical Model Based on RIMEP2

5.2.4. The Islands Model Based on RIMEP2

5.2.5. Hybrid Models

5.2.6. Experiments and Interpretation of the Results

5.2.7. Relevant Features

5.3. Towards Classification of Reversible Functions

5.3.1. Reversible Boolean Functions

5.3.2. Preliminaries

5.3.3. Homogeneous Component Functions

5.3.4. Motivation for Future Work

5.4. The CnF Logic Functions Derived from CnNOT Gates

5.4.1. Reconfigurable Reversible Processors

5.4.2. Background

5.4.3. C3NOT Gate and C3F Functions

5.4.4. Analysis of C4NOT and C4F

5.4.5. Generalizations and Remarks

Bibliography

List of Authors

Index of Authors

Index.

Notes:

"This is the third book of a series that summarizes the best scientific results of contributions to the International Workshop on Boolean Problems (IWSBP)"--Acknowledgments.

Description based on print version record.

Description based on publisher supplied metadata and other sources.

ISBN:

1-5275-2638-0

OCLC:

1083545199