
Synthesis of Finite State Machines
Functional Optimization
Kluwer Academic Publishers
Published on 31. December 1996
Book
Hardback
XIV, 282 pages
978-0-7923-9842-4 (ISBN)
Description
Synthesis of Finite State Machines: Functional Optimization
is one of two monographs devoted to the synthesis of Finite State Machines (FSMs). This volume addresses functional optimization, whereas the second addresses logic optimization. By functional optimization here we mean the body of techniques that:
The result is a symbolic description of the FSM representing the chosen sequential function. By logic optimization here we mean the steps that convert a symbolic description of an FSM into a hardware implementation, with the goal to optimize objectives like area, testability, performance and so on.
Synthesis of Finite State Machines: Functional Optimization is divided into three parts. The first part presents some preliminary definitions, theories and techniques related to the exploration of behaviors of FSMs. The second part presents an implicit algorithm for exact state minimization of incompletely specified finite state machines (ISFSMs), and an exhaustive presentation of explicit and implicit algorithms for the binate covering problem. The third part addresses the computation of permissible behaviors at a node of a network of FSMs and the related minimization problems of non-deterministic finite state machines (NDFSMs).
Key themes running through the book are the exploration of behaviors contained in a non-deterministic FSM (NDFSM), and the representation of combinatorial problems arising in FSM synthesis by means of Binary Decision Diagrams (BDDs).
Synthesis of Finite State Machines: Functional Optimization will be of interest to researchers and designers in logic synthesis, CAD and design automation.
- compute all permissible sequential functions for a given topology of interconnected FSMs, and
- select a `best' sequential function out of the permissible ones.
The result is a symbolic description of the FSM representing the chosen sequential function. By logic optimization here we mean the steps that convert a symbolic description of an FSM into a hardware implementation, with the goal to optimize objectives like area, testability, performance and so on.
Synthesis of Finite State Machines: Functional Optimization is divided into three parts. The first part presents some preliminary definitions, theories and techniques related to the exploration of behaviors of FSMs. The second part presents an implicit algorithm for exact state minimization of incompletely specified finite state machines (ISFSMs), and an exhaustive presentation of explicit and implicit algorithms for the binate covering problem. The third part addresses the computation of permissible behaviors at a node of a network of FSMs and the related minimization problems of non-deterministic finite state machines (NDFSMs).
Key themes running through the book are the exploration of behaviors contained in a non-deterministic FSM (NDFSM), and the representation of combinatorial problems arising in FSM synthesis by means of Binary Decision Diagrams (BDDs).
Synthesis of Finite State Machines: Functional Optimization will be of interest to researchers and designers in logic synthesis, CAD and design automation.
More details
Edition
1997 ed.
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Research
Illustrations
XIV, 282 p.
Dimensions
Height: 240 mm
Width: 161 mm
Thickness: 22 mm
Weight
617 gr
ISBN-13
978-0-7923-9842-4 (9780792398424)
DOI
10.1007/978-1-4757-2622-0
Schweitzer Classification
Other editions
Additional editions

Timothy Kam | Tiziano Villa | Robert K. Brayton
Synthesis of Finite State Machines
Functional Optimization
E-Book
03/2013
Springer
€149.79
Available for download

Timothy Kam | Tiziano Villa | Robert K. Brayton
Synthesis of Finite State Machines
Functional Optimization
Book
12/2010
Springer
€160.49
Shipment within 15-20 days
Content
1 Introduction.- 2 Taxonomy and Theory of Behaviors.- 3 Implicit Techniques.- 4 Compatible Generation.- 5 Binate Covering.- 6 Permissible Behaviors in a Network of FSMs.- 7 State Minimization of Non-Deterministic FSMs.- 8 State Minimization of PNDFSMs in Networks of FSMs.- 9 Conclusions.- References.