Sequential Logic Synthesis

1992
ISBN: 978-0-7923-9187-6
Verlag: Springer US

Buch, Englisch, Band 162, 225 Seiten, Format (B × H): 160 mm x 241 mm, Gewicht: 1180 g

Reihe: The Springer International Series in Engineering and Computer Science

3. 2 Input Encoding Targeting Two-Level Logic. 27 3. 2. 1 One-Hot Coding and Multiple-Valued Minimization 28 3. 2. 2 Input Constraints and Face Embedding 30 3. 3 Satisfying Encoding Constraints. 32 3. 3. 1 Definitions. 32 3. 3. 2 Column-Based Constraint Satisfaction 33 3. 3. 3 Row-Based Constraint Satisfaction. 37 3. 3. 4 Constraint Satisfaction Using Dichotomies. 38 3. 3. 5 Simulated Annealing for Constraint Satisfaction 41 3. 4 Input Encoding Targeting Multilevel Logic. 43 3. 4. 1 Kernels and Kernel Intersections. 44 3. 4. 2 Kernels and Multiple-Valued Variables 46 3. 4. 3 Multiple-Valued Factorization. 48 3. 4. 4 Size Estimation in Algebraic Decomposition. 53 3. 4. 5 The Encoding Step. 54 3. 5 Conclusion. 55 4 Encoding of Symbolic Outputs 57 4. 1 Heuristic Output Encoding Targeting Two-Level Logic. 59 4. 1. 1 Dominance Relations. 59 4. 1. 2 Output Encoding bythe Derivation of Dominance Relations. 60. 4. 1. 3 Heuristics to Minimize the Number of Encoding Bits. 64 4. 1. 4 Disjunctive Relationships. 65 4. 1. 5 Summary. 66. 4. 2 Exact Output Encoding Targeting Two-Level Logic. 66 4. 2. 1 Generation of Generalized Prime Implicants. 68 4. 2. 2 Selecting a Minimum Encodeable Cover. 68 4. 2. 3 Dominance and Disjunctive Relationships to S- isfy Constraints. 70 4. 2. 4 Constructing the Optimized Cover 73 4. 2. 5 Correctness of the Procedure. 73 4. 2. 6 Multiple Symbolic Outputs.

Zielgruppe

Research

Autoren/Hrsg.

Ashar, Pranav

Newton, A. Richard

Devadas, S.

Fachgebiete

• Technische Wissenschaften Elektronik | Nachrichtentechnik Elektronik Bauelemente, Schaltkreise
• Technische Wissenschaften Elektronik | Nachrichtentechnik Elektronik Mikroprozessoren
• Mathematik | Informatik EDV | Informatik Professionelle Anwendung Computer-Aided Design (CAD)
• Technische Wissenschaften Technik Allgemein Computeranwendungen in der Technik
• Geisteswissenschaften Design Produktdesign, Industriedesign
• Technische Wissenschaften Technik Allgemein Konstruktionslehre und -technik
• Mathematik | Informatik EDV | Informatik Angewandte Informatik Computeranwendungen in Wissenschaft & Technologie

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.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.3 Satisfying Encoding Constraints.- 3.4 Input Encoding Targeting Multilevel Logic.- 3.5 Conclusion.- 4 Encoding of Symbolic Outputs.- 4.1 Heuristic Output Encoding Targeting Two-Level Logic.- 4.2 Exact Output Encoding Targeting Two-Level Logic.- 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.2 Exact State Encoding for Two-Level Logic.- 5.3 Symbolic Next State Don’t Cares.- 5.4 State Encoding for Multilevel Logic.- 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.5 Exact Decomposition Procedure for a Two-Way General Topology.- 6.6 Targeting Arbitrary Topologies.- 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.3 Input Don’t Care Sequences.- 7.4 Output Don’t Cares to Minimize States.- 7.5 Single Machine Optimization at the Logic Level.- 7.6 Interconnected Machine Optimization at the Logic Level.- 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.