scientific article; zbMATH DE number 3902554
The object of this book is the area of logic (function) minimization and the presentation of new algorithms appropriate for VLSI applications. The automated synthesis of a combinational circuit system can be partitioned into several tasks: functional design, logic design and physical design. The functional description of the VLSI circuits can be effectively done within a special language, Programmable Logic Arrays (PLA), whose macros are largely used to describe the physical implementation of logic functions. The technological advantage of PLA relies on the straight- forward mapping between the symbolic representation and the physical implementation. The functional description is transformed into a logic description in terms of Boolean variables (functions). Optimal logic design, the major topic of this book, transforms the logic representation to obtain a convenient implementation. Among the important programs created for automated logic minimization should be mentioned: MINI (developed at IBM in the middle of the 70s), PRESTO (D. W. Brown, 1981), SHRINK (J. P. Roth, 1980), SPAM - a version of MINI (S. Kang, 1981). PRESTO differs from MINI in the way the expansion process is carried out. MINI generates the complement of the logic function to check if the expansion of an implicant does not change the coverage of the function. PRESTO does not compute the complement but the expansion process requires a check on whether all the minterms covered by the expanded implicant are covered by some other implicant of the cover, which, in general, costs more computation time. ESPRESSO-I (1981), created by the authors of the present book, uses the MINI's technique of computing the complement of the PLA representation since it proved to be superior: on the average, the initial cost involved by the complement computing (reduced also by the discovery of better complementation algorithms) was offset by the more efficient expansion procedure that is allowed. Iteration as used by MINI is generally worthwhile for VLSI design. The initial investment in computing the complement is then amortized over the additional steps required by the iterations. ESPRESSO-II (1982) basically follows the sequence of top-level transformations of iterated expansion-reduction pioneered by MINI. In January 1984 a new version of ESPRESSO-II was implemented in C (by Richard Rudell). The algorithms of ESPRESSO-II achieve a high level of efficiency, mainly through the use of a common theme, the unate recursive paradigm. This means, roughly, that a logic function is recursively divided until each part becomes unate (monotone). The required operation (e.g. complement, reduction, irredundant cover) is then performed on the unate function in a highly efficient way. Finally, the results are merged appropriately to obtain the required result. The book is organized as follows: Chapter 1 is an efficient introduction to the problem. Chapters 2 and 3 provide the theoretical foundations (notations, basic definitions) for logic and logic function manipulation. In particular, chapter 3 introduces the unate (monotone) functions and basic results concerning them. The unate recursive paradigm is presented and illustrated with the SIMPLIFY algorithm. All algorithms are based on a single fundamental strategy: a recursive divide and conquer. The decomposition is based on the Shannon expansion. The definition is given for matrix representation of logic functions and the corresponding algorithms are described. The authors use, for the algorithm description, a pseudo-computer language which allows to a competent reader to implement the algorithms directly. Chapter 4 is the technical heart of the book. Each of the algorithms of ESPRESSO-II is described in detail along with the supporting theorems and proofs. The algorithms are outlined as structured procedures. COMPLEMENT, EXPAND, ESSENTIAL-PRIMES, IRREDUNDANT-COVER, REDUCE, LAST-GASP, MAKE- SPARSE are the basic routines. Many of them rely heavily on the TAUTOLOGY algorithm. The way these routines fit together to form ESPRESSO-II is also described. Chapter 5 presents a new method for using any two-valued logic minimizer for functions with multiple-valued inputs: it involves a particular encoding of the multiple-valued inputs and the creation of a don't care set before the use of the two-valued logic minimizer. In this way, ESPRESSO-II can be effectively used to minimize multiple-valued logic functions. The method is efficient and practical as far as the number of possible values for a given input is not very large. Chapter 6 reports the results of testing ESPRESSO-IIAPL and ESPRESSO-IIC on different PLAs. The final size, the sparsity and the amount of computation time expanded to achieve the result were the most important parameters of the experiments. The correlations among these parameters make the reader acquainted with the degree of optimization that can be achieved by the two versions of ESPRESSO-II, in APL and C. Chapter 7 summarizes the new ideas incorporated in ESPRESSO-II and documents their effectiveness in comparison with other logic minimizers: MINI, POP, PRESTO. Some modifications introduced in the C-language version of ESPRESSO-II are also discussed. Other applications of logic minimization and directions for further research are presented and an updated bibliography of 164 titles is provided. The book is of great interest for all those working in or being related to the new computer technologies: from the theoretical computer scientist to the hardware design engineer. It offers a concrete description of the logic minimization algorithms for VLSI design and an effective possibility, by ESPRESSO-II procedures, to work with them. In short, a quite remarkable realization in the field.
- Random sequence generation by cellular automata
- Continuous reductions among combinatorial optimization problems
- Polynomial-time algorithms for generation of prime implicants
- Horn functions and their DNFs
- Characterizing diagnoses and systems
- Principles of logic optimization for a Moore microprogrammed automaton
- Simplification in a satisfiability checker for VLSI applications
- A method for minimization design of two-level-logic networks using multiplexer universal logic modules
- Inference of a minimum size Boolean function from examples by using a new efficient branch-and-bound approach
- Variable and term removal from Boolean formulae
- Experimental comparison of decomposition methods for systems of Boolean function
- Approximation techniques for hypergraph partitioning problems
- Running time experiments on some algorithms for solving propositional satisfiability problems
- Implementation of a fuzzy inference system using a normalized fuzzy neural network
- Extracting reaction systems from function behavior
- Optimal symmetry breaking for graph problems
- Enhancing probabilistic model checking with ontologies
- Characterization and computation of ancestors in reaction systems
- Minimization of mealy finite-state machines by internal states gluing
- Computing AES related-key differential characteristics with constraint programming
- Decomposing a system of Boolean functions into subsystems of connected functions
- Optimization on the complementation procedure towards efficient implementation of the index generation function
- Synthesizing cubes to satisfy a given intersection pattern
- Fuzzy modelling through logic optimization
- NEQR: a novel enhanced quantum representation of digital images
- Algebraic methods for optimizing constant multiplications in linear systems
- BerkMin: A fast and robust SAT-solver
- A multiple-valued logic approach to the design and verification of hardware circuits
- A lattice-based approach to the problem of recruitment in multiagent systems
- An Equivalence-Preserving Transformation of Shift Registers
- scientific article; zbMATH DE number 4133829 (Why is no real title available?)
- Binary decision diagrams
- An Algorithm to Derive the Complement of a Binary Function with Multiple-Valued Inputs
- Input Variable Assignment and Output Phase Optimization of PLA's
- scientific article; zbMATH DE number 3871193 (Why is no real title available?)
- A purely map procedure for two-level multiple-output logic minimization
- SAT-Based Formula Simplification
- Matching Integer Intervals by Minimal Sets of Binary Words with don’t cares
- Decomposition-based logic synthesis for PAL-based CPLDs
- scientific article; zbMATH DE number 3906401 (Why is no real title available?)
- A method for minimizing Moore finite-state machines by merging two states
- Compact DSOP and partial DSOP forms
- Generation of full cycles by a composition of NLFSRs
- ULM Implicants for Minimization of Univers Logic Module Circuits
- Two-level logic minimization: an overview
- Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes
- The gene expression matrix: Towards the extraction of genetic network architectures
- Dynamic processor allocation in scalable multiprocessors using boolean algebra*
- ESCT minimization for incompletely specified functions
- scientific article; zbMATH DE number 910866 (Why is no real title available?)
- Local feature point extraction for quantum images
- scientific article; zbMATH DE number 7199588 (Why is no real title available?)
- Nonlinear Codes for Test Patterns Compression: The Old School Way
- FSM Encoding for BDD Representations
- The Decomposition Tree for analyses of Boolean functions
- Computing preimages and ancestors in reaction systems
- Hardware implementation of code converters designed to reduce the length of binary encoded words
- Partially unate Boolean functions: properties of their sum-of-products representations
- Exact Synthesis of ESOP Forms
- A flexible representation of quantum images for polynomial preparation, image compression, and processing operations
- Fast computation of the prime implicants by exact direct-cover algorithm based on the new partial ordering operation rule
- Feature necessity \& relevancy in ML classifier explanations
- Distinguisher and related-key attack on HALFLOOP-96
- Feature necessity and relevancy in machine learning explanations
- A continuous approach to inductive inference
- Exploring the optimal differential characteristics of SM4. Improving automatic search by including human insights
- Gröbner bases for Boolean function minimization
- An efficient ESOP minimization-based quantum image encryption scheme using chaotic quantum substitution and permutation boxes
- Cnf characterization of sets over \(\mathbb{Z}_2^n\) and its applications in cryptography
- Operads for complex system design specification, analysis and synthesis
- An excursion in reaction systems: from computer science to biology
- Broadcast encryption using sum-product decomposition of Boolean functions
- Efficient algorithm for generating optimal inequality candidates for MILP modeling of Boolean functions
- Bivalent semantics, generalized compositionality and analytic classic-like tableaux for finite-valued logics
- The potential of fuzzy neural networks in the realization of approximate reasoning engines
- Modeling and integer programming techniques applied to propositional calculus
- Optimal complexity reduction of polyhedral piecewise affine systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3680754)