Initializable asynchronous circuit design

A method of synthesizing an initializable asynchronous circuit design from a signal transition graph defining circuit functional behavior comprising the steps of:

• (a) deriving an asynchronous state graph from the signal transition graph;
• (b) determining whether the asynchronous state graph defines a circuit design which is functionally initializable;
• (c) if step (b) determines that the design is functionally initializable performing the steps of:
• i. specifying the circuit functional behavior in terms of K-maps for input signals and non-input signals;
• ii. forming an initialization sequence tree having as its top level a respective root node corresponding to each non-input signal;
• iii. applying an INIT function for each node in sequence to form branches having nodes corresponding to non-input signals;
• iv. repeating steps (c)(ii) and (c)(iii) for each branch until reaching a success node or a failure node;
• v. forming an initialization sequence corresponding to a branch reaching a success node;
• (d) if step (b) determines that the design is other than functionally initializable, performing the steps of:
• i. deriving an asynchronous state graph from the signal transition graph where each state is encoded with a state vector having a determined portion and an undetermined portion;
• ii. identifying inconsistent states for a specified non-input signal from the determined portion of the state vector;
• iii. classifying each state identified in step (d)(ii) using StateClass procedure;
• iv. selecting a non-input signal and removing any inconsistent state;
• v. modifying the asynchronous state graph such that inconsistent states removed in step (d)(iv) result in a modified asynchronous state graph which behaves equivalent to the unmodified signal transition graph with minimal loss in concurrency;
• vi. updating the determined portion of the state vector to correspond to the modified asynchronous state graph;
• vii. repeating steps (d)(ii) to (d)(vi) until all non-input signals are initialized, and
• (e) synthesizing the initializable synchronous circuit corresponding to the initializable signal transition graph or the modified signal transition graph.