Structural methods for the synthesis of speed-independent circuits

Asynchronous circuits can be modeled as concurrent systems in which events are interpreted as signal transitions. The synthesis of concurrent systems implies the analysis of a vast state space that often requires computationa lly expensive methods. This work presents new methods for the synthesis of speed-independent circuits from a new perspective, overcoming both the anal ysis and computation complexity bottlenecks. The circuits are specified by free-choice signal transition graphs (STG's), a subclass of interpreted Petri nets. The synthesis approach is divided in to the following steps: correctness, binary coding, implementability condit ions, and logic synthesis. Each step is efficiently implemented by applying a set of structural techniques that analyze STG's without explicitly enume rating the underlying state space. Experimental results show that circuits can be generated from specification s that exceed in several orders of magnitude the largest STG's ever synthes ized-with over 10(27) states. Computation times are also dramatically reduc ed. Nevertheless, the quality of results does not suffer from the use of st ructural techniques.