Polynomial algorithms for the synthesis of hazard-free circuits from signal transition graphs
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Methods for the synthesis of asynchronous circuits from signal transition graphs (STGs) have commonly used the state graph to solve the two main steps of this process: the state assignment problem and the generation of hazard-free logic. The size of the state graph can be of order O(2/sup n/), where n is the number of signals of the circuit. As synthesis tools for asynchronous systems start to mature, the size of the STGs increases and the exponential algorithms that work on the state graph become obsolete. This paper presents alternative algorithms that work in polynomial time and, therefore, avoid the generation of the SG. With the proposed algorithms, STGs can be synthesized and hazard-free circuits generated in extremely low CPU times. Improvements in two or three orders of magnitude (from hours to seconds) with respect to existing algorithms are achieved when synthesizing fairly large STGs.Keywords
This publication has 10 references indexed in Scilit:
- Automatic synthesis and verification of hazard-free control circuits from asynchronous finite state machine specificationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An asynchronous architecture model for behavioral synthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Linear programming for optimum hazard elimination in asynchronous circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Solving the state assignment problem for signal transition graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Synthesis and optimization of asynchronous controllers based on extended lock graph theoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An efficient unique state coding algorithm for signal transition graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Synthesis of hazard-free asynchronous circuits from graphical specificationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimized synthesis of asynchronous control circuits from graph-theoretic specificationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A generalized state assignment theory for transformations on signal transition graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Petri nets: Properties, analysis and applicationsProceedings of the IEEE, 1989