Complete state encoding based on the theory of regions
- 1 January 1996
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Synthesis of asynchronous circuits from Signal Transition Graphs (STGs) and/or State Graphs (SGs) involves solving state coding problems. A well-known example of such problems is that of Complete State Coding (CSC), which happens when a pair of different states in an SG has the same binary encoding. A standard way to approach state coding conflicts is to add new state signals into the original specification in such a way that the original behaviour remains intact. Existing methods have not yet been able to provide such theoretical foundation for event insertion, that could yield efficient practical results when applied to large models.This paper aims at presenting such a general framework, which is based on two fundamental concepts. One is a region of states in an abstract labeled SG (called a Transition System). Regions correspond to places in the associated STG. The second concept is a speed-independence preserving set, which is strongly related to the implementability of the model in logic. Regions and their intersections offer ``nice'' structural properties that make them efficient ``construction blocks'' for event insertion. The application of our theory, through the software tool petrify, to state graphs of large size has proved to be successful.Keywords
This publication has 14 references indexed in Scilit:
- An efficient unique state coding algorithm for signal transition graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Formal method for self-timed designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Checking signal transition graph implementability by symbolic BDD traversalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimised state assignment for asynchronous circuit synthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient state assignment framework for asynchronous state graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Synthesizing Petri nets from state-based modelsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- Basic gate implementation of speed-independent circuitsPublished by Association for Computing Machinery (ACM) ,1994
- Algorithms for Synthesis and Testing of Asynchronous CircuitsPublished by Springer Nature ,1993
- Elementary transition systemsTheoretical Computer Science, 1992
- On the verification of state-coding in STGsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992