Sequential Logic Synthesis

Inhaltsverzeichnis

Acknowledgments.- 1 Introduction.
- 1.1 Computer-Aided VLSI Design.
- 1.2 The Synthesis Pipeline.
- 1.3 Sequential Logic Synthesis.
- 1.4 Early Work in Sequential Logic Synthesis.
- 1.5 Recent Developments.
- 1.5.1 State Encoding.
- 1.5.2 Finite State Machine Decomposition.
- 1.5.3 Sequential Don't Cares.
- 1.5.4 Sequential Resynthesis at the Logic Level.
- 1.6 Organization of the Book.- 2 Basic Definitions and Concepts.
- 2.1 Two-Valued Logic.
- 2.2 Multiple-Valued Logic.
- 2.3 Multilevel Logic.
- 2.4 Multiple-Valued Input, Multilevel Logic.
- 2.5 Finite Automata.- 3 Encoding of Symbolic Inputs.
- 3.1 Introduction.
- 3.2 Input Encoding Targeting Two-Level Logic.
- 3.2.1 One-Hot Coding and Multiple-Valued Minimization.
- 3.2.2 Input Constraints and Face Embedding.
- 3.3 Satisfying Encoding Constraints.
- 3.3.1 Definitions.
- 3.3.2 Column-Based Constraint Satisfaction.
- 3.3.3 Row-Based Constraint Satisfaction.
- 3.3.4 Constraint Satisfaction Using Dichotomies.
- 3.3.5 Simulated Annealing for Constraint Satisfaction.
- 3.4 Input Encoding Targeting Multilevel Logic.
- 3.4.1 Kernels and Kernel Intersections.
- 3.4.2 Kernels and Multiple-Valued Variables.
- 3.4.3 Multiple-Valued Factorization.
- 3.4.4 Size Estimation in Algebraic Decomposition.
- 3.4.5 The Encoding Step.
- 3.5 Conclusion.- 4 Encoding of Symbolic Outputs.
- 4.1 Heuristic Output Encoding Targeting Two-Level Logic.
- 4.1.1 Dominance Relations.
- 4.1.2 Output Encoding by the Derivation of Dominance Relations.
- 4.1.3 Heuristics to Minimize the Number of Encoding Bits.
- 4.1.4 Disjunctive Relationships.
- 4.1.5 Summary.
- 4.2 Exact Output Encoding Targeting Two-Level Logic.
- 4.2.1 Generation of Generalized Prime Implicants.
- 4.2.2 Selecting a Minimum Encodeable Cover.
- 4.2.3 Dominance and Disjunctive Relationships to Sat-isfy Constraints.
- 4.2.4 Constructing the Optimized Cover.
- 4.2.5 Correctness of the Procedure.
- 4.2.6 Multiple Symbolic Outputs.
- 4.2.7 The Issue of the All Zeros Code.
- 4.2.8 Reduced Prime Immplicant Table Generation.
- 4.2.9 Covering with Encodeability Constraints.
- 4.2.10 Experimental Results Using the Exact Algorithm.
- 4.2.11 Computationally Efficient Heuristic Minimization.
- 4.3 Symbolic Output Don't Cares.
- 4.4 Output Encoding for Multilevel Logic.
- 4.5Conclusion.- 5 State Encoding.
- 5.1 Heuristic State Encoding Targeting Two-Level Logic.
- 5.1.1 Approximating State Encoding as Input Encoding.
- 5.1.2 Constructing Input and Dominance Relations.
- 5.1.3 Heuristics to Minimize the Number of Encoding Bits.
- 5.1.4 Alternate Heuristic State Encoding Strategies.
- 5.2 Exact State Encoding for Two-Level Logic.
- 5.2.1 Generation of Generalized Prime Implicants.
- 5.2.2 Selecting a Minimum Encodeable Cover.
- 5.2.3 Constructing an Optimized Cover.
- 5.2.4 Reduced Prime Implicant Table Generation.
- 5.2.5 The Covering Step.
- 5.2.6 Heuristics to Minimize the Number of Encoding Bits.
- 5.2.7 Encoding Via Boolean Satisfiability.
- 5.3 Symbolic Next State Don't Cares.
- 5.4 State Encoding for Multilevel Logic.
- 5.4.1 Introduction.
- 5.4.2 Modeling Common Cube Extraction.
- 5.4.3 A Fanout-Oriented Algorithm.
- 5.4.4 A Fanin-Oriented Algorithm.
- 5.4.5 The Embedding Algorithm.
- 5.4.6 Improvements to Estimation Strategies.
- 5.5 Conclusion.- 6 Finite State Machine Decomposition.
- 6.1 Introduction.
- 6.2 Definitions for Decomposition.
- 6.3 Preserved Covers and Partitions.
- 6.4 General Decomposition Using Factors.
- 6.4.1 Introduction.
- 6.4.2 An Example Factorization.
- 6.4.3 Defining An Exact Factor.
- 6.4.4 Exact Factorization.
- 6.4.5 Identifying Good Factors.
- 6.4.6 Limitations of the Factoring Approach.
- 6.5 Exact Decomposition Procedure for a Two-Way General Topology.
- 6.5.1 The Cost Function.
- 6.5.2 Formulation of Optimum Decomposition.
- 6.5.3 Relationship to Partition Algebra.
- 6.5.4 Relationship to Factorization.
- 6.5.5 Generalized Prime Implicant Generation.
- 6.5.6 Encodeability of a GPI Cover.
- 6.5.7 Correctness of the Exact Algorithm.
- 6.5.8 Checking for Output Constraint Violations.
- 6.5.9 Checking for Input Constraint Violations.
- 6.5.10 Relative Complexity of Encodeability Checking.
- 6.5.11 The Covering Step in Exact Decomposition.
- 6.6 Targeting Arbitrary Topologies.
- 6.6.1 Cascade Decompositions.
- 6.6.2 Parallel Decompositions.
- 6.6.3 Arbitrary Decompositions.
- 6.6.4 Exactness of the Decomposition Procedure.
- 6.7 Heuristic General Decomposition.
- 6.7.1 Overview.
- 6.7.2 Minimization of Covers and Removal of Constraint Violations.
- 6.7.3 Symbolic-expand.
- 6.7.4 Symbolic-reduce.
- 6.8 Relationship to State Assignment.
- 6.9 Experimental Results.
- 6.10 Conclusion.- 7 Sequential Don't Cares.
- 7.1 Introduction.
- 7.2 State Minimization.
- 7.2.1 Generating the Implication Table.
- 7.2.2 Completely-Specified Machines.
- 7.2.3 Incompletely-Specified Machines.
- 7.2.4 Dealing with Exponentially-Sized Input Alphabets.
- 7.3 Input Don't Care Sequences.
- 7.3.1 Input Don't Care Vectors.
- 7.3.2 Input Don't Care Sequences to Minimize States.
- 7.3.3 Exploiting Input Don't Care Sequences.
- 7.3.4 Early Work on Input Don't Care Sequences.
- 7.4 Output Don't Cares to Minimize States.
- 7.4.1 Exploiting Output Don't Cares.
- 7.5 Single Machine Optimization at the Logic Level.
- 7.5.1 Introduction.
- 7.5.2 Invalid State and Unspecified Edge Don't Cares.
- 7.5.3 Equivalent State Don't Cares.
- 7.5.4 Boolean Relations Due To Equivalent States.
- 7.5.5 Minimization With Don't Cares and Boolean Re-lations.
- 7.6 Interconnected Machine Optimization at the Logic Level.
- 7.6.1 Unconditional Compatibility.
- 7.6.2 Conditional Compatibility.
- 7.6.3 Invalid States and Edges.
- 7.6.4 Searching for Unreachability and Compatibility.
- 7.7 Conclusion.- 8 Conclusions and Directions for Future Work.
- 8.1 Alternate Representations.
- 8.2 Optimization at the Logic Level.
- 8.3 Don't Cares and Testability.
- 8.4 Exploiting Register-Transfer Level Information.
- 8.5 Sequential Logic Synthesis Systems.