search for books and compare prices
Tables of Contents for Synthesis of Finite State Machines
Chapter/Section Title
Page #
Page Count
PREFACE
xi
 
Part I FROM SYMBOLIC TO LOGIC REPRESENTATIONS
1
138
1 INTRODUCTION
3
10
1.1 Logic Synthesis of Sequential Behaviors
3
2
1.2 The Encoding Problem: From Symbolic to Boolean Domain
5
4
1.3 Overview of the Book
9
4
2 DEFINITIONS
13
26
2.1 Sequential Functions and Their Representation
13
1
2.2 Finite State Machines
14
5
2.3 Taxonomy of Encoding Problems
19
4
2.4 Behavior vs. Structure in Encoding Problems
23
1
2.5 Boolean Algebras and Boolean Functions
24
1
2.6 Discrete Functions as Boolean Functions
25
5
2.7 Two-level Minimization of Multi-Valued Functions
30
3
2.8 Multi-level Multi-Valued Functions
33
2
2.9 Multi-Valued Relations
35
1
2.10 Binary Decision Diagrams
36
1
2.11 Hypercubes
37
2
3 COMPLEXITY ISSUES
39
12
3.1 Computational Complexity
39
9
3.2 Counting State Assignments
48
3
4 ENCODING FOR SYNTHESIS
51
88
4.1 Algorithms for Optimal Encoding
51
45
4.2 Combinational Encoding Problems
96
15
4.3 State Assignment and FSM Decomposition
111
13
4.4 State Assignment for Testability
124
6
4.5 Sequential Optimization at the Gate Level
130
9
Part II CONSTRAINED ENCODING
139
80
5 SYMBOLIC MINIMIZATION
141
42
5.1 Introduction
141
2
5.2 Encoding for Two-level Implementations
143
5
5.3 A New Symbolic Minimization Algorithm
148
7
5.4 Symbolic Reduction
155
4
5.5 Symbolic Oring
159
2
5.6 Ordering of Symbolic Minimization
161
3
5.7 Symbolic Minimization by Example
164
12
5.8 Experimental Results
176
6
5.9 Conclusions
182
1
6 ENCODING CONSTRAINTS
183
36
6.1 Introduction
183
2
6.2 Statement and Complexity of the Encoding Problems
185
3
6.3 Definitions
188
1
6.4 Abstraction of the Problem
189
2
6.5 Input Constraint Satisfaction
191
3
6.6 Input and Output Constraint Satisfaction
194
11
6.7 Bounded Length Encoding
205
5
6.8 Other Applications
210
3
6.9 Results
213
5
6.10 Conclusions
218
1
Part III GENERALIZED PRIME IMPLICANTS
219
80
7 GENERALIZED PRIME IMPLICANTS
221
24
7.1 Introduction
221
1
7.2 Definition of GPIs
221
3
7.3 GPIs by Consensus Operation
224
3
7.4 Encodeability of GPIs
227
2
7.5 Sufficiency of GPIs
229
2
7.6 GPIs by Computation of MV Primes
231
11
7.7 A Procedure for Analysis of GPIs
242
3
8 MINIMIZATION OF GPIS
245
32
8.1 Reduction of GPI Minimization to Unate Covering
245
16
8.2 Reduction of GPI Minimization to Binate Covering
261
4
8.3 GPIs and Non-Determinism
265
12
9 ENCODEABILITY OF GPIS
277
22
9.1 Introduction
277
1
9.2 Efficient Encodeability Check of GPIs
277
6
9.3 Encoding of a Set of Encodeable GPIs
283
1
9.4 Updating Sets and Raising Graphs
284
8
9.5 Choice of a Branching Column
292
3
9.6 Computation of a Lower Bound
295
4
Part IV IMPLICIT TECHNIQUES FOR ENCODING
299
56
10 IMPLICIT FORMULATION OF UNATE COVERING
301
22
10.1 Introduction
301
1
10.2 Implicit Representations and Manipulations
301
4
10.3 A Fully Implicit Unate Covering Solver
305
5
10.4 Quantifier-Free Reduction of Unate Tables
310
10
10.5 An Application to Encoding Dichotomies
320
3
11 IMPLICIT MINIMIZATION OF GPIS
323
32
11.1 Introduction
323
1
11.2 Useful Relations
323
2
11.3 Implicit Generation of GPIs and Minterms
325
3
11.4 Implicit Selection of GPIs
328
14
11.5 An Example of Implicit GPI Minimization
342
3
11.6 Verification of Correctness
345
3
11.7 Implementation Issues
348
2
11.8 Experiments
350
1
11.9 Conclusions
351
4
Part V CONCLUSIONS
355
4
12 CONCLUSIONS
357
2
REFERENCES
359
20
INDEX
379