Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1997 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Synthesis of Finite State Machines

Functional Optimization

verfasst von: Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli

Verlag: Springer US

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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: 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.

Inhaltsverzeichnis

Frontmatter

Preliminaries

Frontmatter
Chapter 1. Introduction
Abstract
VLSI (Very large scale integrated) circuits are widely used in modern electronic products. Since the invention of the planar integrated circuit by Robert Noyce and Jack Kelby in 1959, the number of transistors that can be successfully fabricated on a single chip has doubled almost every year. As the complexity and performance requirements of VLSI circuits are increasing exponentially, the design process has to be automated by using computer-aided design (CAD) tools. A CAD tool is a computer program that can help an IC designer in the VLSI design process. This book is concerned with the problem of automatically synthesizing a class of digital circuits.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Chapter 2. Taxonomy and Theory of Behaviors
Abstract
The goal of this chapter is to provide a unified notational framework for the book, and to introduce key elements of a theory for functional synthesis of FSMs. First we define some useful classes of finite state machines (FSMs) and finite automata (FAs), and investigate their inter-relationship. We will show that a non-deterministic FSM (NDFSM) can be used to specify a set of behaviors. Then we will describe how different behaviors can be explored within an NDFSM specification. These concepts are central to exact algorithms for state minimization for FSMs. At the end of the chapter, the correctness of our state minimization algorithms will be proved for a class of FSMs called pseudo non-deterministic FSMs.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Chapter 3. Implicit Techniques
Abstract
In this chapter, we shall introduce techniques for efficient representation and manipulation of objects. We say that a representation is explicit if the objects it represents are listed one by one internally. Objects are manipulated explicitly, if they are processed one after another. An implicit representation means a shared representation of the objects, such that the size of the representation is not linearly proportional to the number of objects in it. In an implicit manipulation many objects are processed simultaneously in one step.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli

State Minimization of Incompletely Specified FSMs

Frontmatter
Chapter 4. Compatible Generation
Abstract
State minimization of FSMs is a well-known problem [60]. State minimization of completely specified FSMs (CSFSMs) has a complexity subquadratic in the number of states [50, 45]. This makes it an easy problem when the starting point is a two-level description of an FSM, because the number of states is usually less than a few hundred. The problem becomes difficult to manage when the starting point is an encoded sequential circuit with a large number of latches (in the hundreds). In that case the traditional method would be required to extract a state transition graph from the encoded network and then apply state minimization to it. But when latches are more than a dozen, the number of reachable states may be so huge to make state extraction and/or state minimization unfeasible. Recently it has been shown [90, 70, 73] how to bypass the extraction step and compute equivalence state pairs and equivalence classes of states implicitly. Equivalence classes are basically all that is needed to minimize a completely specified state machine. A compatible projection operator uniquely encodes each equivalence class by selecting a unique representative of the class to which a given state belongs. This implicit technique allows state minimization of sequential networks outside the domain of standard state minimization.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Chapter 5. Binate Covering
Abstract
At the core of the exact solution of various logic synthesis problems lies often a so-called covering step that requires the choice of a set of elements of minimum cost that cover a set of ground items, under certain conditions. Prominent among these problems are the covering steps in the Quine-McCluskey procedure for minimizing logic functions, selection of a minimum number of encoding columns that satisfy a set of encoding constraints, selection of a set of encode-able generalized prime implicants, state minimization of finite state machines, technology mapping and Boolean relations. Let us review first how covering problems are defined formally.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli

Flexibility in Networks of FSMs and Non-Deterministic FSMs

Frontmatter
Chapter 6. Permissible Behaviors in a Network of FSMs
Abstract
A behavior is a set of input/output strings that can be produced or represented by a DFSM. An NDFSM will represent in general more than one behavior and more than one DFSM may represent the same behavior. Given a synchronous system of interacting FSMs and a specification, consider the problem of finding the complete set of permissible behaviors at a particular component of the system 1. The problem is illustrated in Figure 6.1, where M 1 is the FSM associated with the component to be optimized, M 2 represents the behavior of the rest of the system, and M gives the specification. In a variant of the problem, the roles of M 1 and M 2 are inverted. Figures 6.2-(a) and 6.2-(b) show how the variant is reduced to the original problem. Although x is a direct input to M 2 in Figure 6.2-a, one can view x as feeding through M 1 via a straight wire connection, as drawn in Figure 6.2-b; similarly the output z can be seen as passing through M 1.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Chapter 7. State Minimization of Non-Deterministic FSMs
Abstract
We have seen that PNDFSMs are a subclass of NDFSMs sufficient to capture the flexibility of an FSM at a node in a network of interacting FSMs. Therefore the extraction from a PNDFSM of a behavior corresponding to a DFSM with a minimum number of states is an important synthesis objective, that generalizes the problem of state minimization of ISFSMs.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Chapter 8. State Minimization of PNDFSMs in Networks of FSMs
Abstract
A behavior is permissible at a node of an interconnection, say at M 1, if the system obtained by placing at that node a DFSM that represents the behavior works according to the original specification. Such a replacement is allowed if the composition is well-defined and the global behavior is the one expected. Unfortunately not any behavior contained in a PNDFSMs is permissible, i.e., it is valid candidate for implementation. The reason is that it may not yield a well-defined feedback composition. Watanabe proposed in [119] a sufficient condition in the form of acyclicity, for a behavior to be permissible. In the previous chapter, we have presented a comprehensive analysis of the conditions for the existence of a correct feedback composition, and described how to find all valid candidate behaviors. Since a valid candidate is preferred if it minimizes the number of states of the related FSM, here we will discuss the problem of the combined objective of finding a state-minimum and well-defined behavior.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Chapter 9. Conclusions
Abstract
This book has focused on synthesis of FSMs at the functional level, that is the exploration and selection of behaviors in various kinds of finite state machines (FSMs). In particular, implicit algorithms were presented for state minimization of ISFSMs, PNDFSMs, and a PNDFSM within a network of FSMs.
Timothy Kam, Tiziano Villa, Robert Brayton, Alberto Sangiovanni-Vincentelli
Backmatter
Metadaten
Titel
Synthesis of Finite State Machines
verfasst von
Timothy Kam
Tiziano Villa
Robert Brayton
Alberto Sangiovanni-Vincentelli
Copyright-Jahr
1997
Verlag
Springer US
Electronic ISBN
978-1-4757-2622-0
Print ISBN
978-1-4419-5170-0
DOI
https://doi.org/10.1007/978-1-4757-2622-0