US5493505A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Initializable asynchronous circuit design
Assignee: NEC Corp
•
Filing: 1993-10-28
•
Granted: 1996-02-20
•
Expires: 2013-10-28
Abstract
Abstract A method of asynchronous circuit synthesis of initializable circuits from signal transition graphs (STG) that are either functionally initializable or functionally uninitializable is described. For functionally initializable cases, an initializable implementation can be achieved by proper assignment of don't care values. If the STG is not functionally initializable, the sources of uninitializability in the STG are identified and the STG is transformed into a functionally initializable specification by exploiting concurrency. Initializability is achieved at the expense of minimal removal of concurrency. Moreover, the transformation does not violate liveness and unique state coding properties of the STG. When the STG is functionally initializable or after an uninitializable STG is transformed to become functionally initializable the result is an initializable circuit design.
Inventors
- 👤 Savita Banerjee
- 👤 Srimat T. Chakradhar
- 👤 Rabindra K. Roy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 07:54
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/35
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
316 words
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.
Claim 2
Independent Claim
316 words
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.
Claim 3
Dependent Claim
27 words
A method of synthesizing an initializable asynchronous circuit design as set forth in claim 1, further comprising step (f) fabricating a circuit corresponding to the synthesized circuit.
Claim 4
Dependent Claim
27 words
A method of synthesizing an initializable asynchronous circuit design as set forth in claim 2, further comprising step (g) applying the initialization sequence to the fabricated circuit.
Claim 5
Independent Claim
102 words
A method of synthesizing an initializable asynchronous circuit design comprising the steps of: (a) specifying the circuit functional behavior in terms of K-maps for input signals and non-input signals; (b) forming an initialization sequence tree having at its top level a respective root node corresponding to each non-input signal; (c) performing a INIT function for each node in sequence to form branches having nodes corresponding to non-input signals; (d) repeating the steps (b) and (c) for each branch until reaching a success node or a failure node, and (e) forming an initialization sequence signal corresponding to a branch reaching a success node.
Claim 6
Independent Claim
102 words
A method of synthesizing an initializable asynchronous circuit design comprising the steps of: (a) specifying the circuit functional behavior in terms of K-maps for input signals and non-input signals; (b) forming an initialization sequence tree having at its top level a respective root node corresponding to each non-input signal; (c) performing a INIT function for each node in sequence to form branches having nodes corresponding to non-input signals; (d) repeating the steps (b) and (c) for each branch until reaching a success node or a failure node, and (e) forming an initialization sequence signal corresponding to a branch reaching a success node.
Claim 7
Dependent Claim
32 words
A method of synthesizing an initializable asynchronous circuit design as set forth in claim 4, further comprising (f) synthesizing the initializable asynchronous circuit corresponding to the success node reached in step (e).
Claim 8
Dependent Claim
28 words
A method of synthesizing an intializable asynchronous circuit design as set forth in claim 5, further comprising the step (g) fabricating a circuit corresponding to the synthesized design.
Claim 9
Dependent Claim
27 words
A method of synthesizing an intializable asynchronous circuit design as set forth in claim 6, further comprising step (h) applying the initialization sequence to the fabricated circuit.
Claim 10
Independent Claim
198 words
A method of synthesizing an initializable asynchronous circuit design comprising the steps of: (a) specifying the circuit functional behavior in terms of a signal transition graph; (b) 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; (c) identifying inconsistent states for a specified non-input signal from the determined portion of the state vector; (d) classifying each state identified in step (c) using StateClass procedure; (e) selecting a non-input signal and removing any inconsistent state; (f) modifying the asynchronous state graph such that inconsistent states removed in step (e) results in a modified asynchronous state graph which behaves equivalent to the unmodified signal transition graph with minimal loss in concurrency; (g) updating the determined portion of the state vector to correspond to the modified asynchronous state graph; (h) repeat steps (c) to (g) until all non-input signals are initialized and the state vector contains no undetermined portion; and (i) synthesizing, after all non-input signals are initialized, the initializable asynchronous circuit corresponding to the modified asynchronous state graph where the determined portion is useable for initializing the asynchronous circuit for subsequent testing.
Claim 11
Independent Claim
198 words
A method of synthesizing an initializable asynchronous circuit design comprising the steps of: (a) specifying the circuit functional behavior in terms of a signal transition graph; (b) 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; (c) identifying inconsistent states for a specified non-input signal from the determined portion of the state vector; (d) classifying each state identified in step (c) using StateClass procedure; (e) selecting a non-input signal and removing any inconsistent state; (f) modifying the asynchronous state graph such that inconsistent states removed in step (e) results in a modified asynchronous state graph which behaves equivalent to the unmodified signal transition graph with minimal loss in concurrency; (g) updating the determined portion of the state vector to correspond to the modified asynchronous state graph; (h) repeat steps (c) to (g) until all non-input signals are initialized and the state vector contains no undetermined portion; and (i) synthesizing, after all non-input signals are initialized, the initializable asynchronous circuit corresponding to the modified asynchronous state graph where the determined portion is useable for initializing the asynchronous circuit for subsequent testing.
Claim 12
Dependent Claim
69 words
A method as set forth in claim 8, where said identifying inconsistent states comprises the steps of: identifying all states having a predetermined determined portion of its associated state vector; checking the next-state value of each identified state for a predetermined non-input signal; and identifying those states which fail to provide a desired next-state value responsive to the state vector of the determined portion and a predetermined non-input signal.
Claim 13
Dependent Claim
96 words
A method as forth in claim 8, where said classifying each state comprises the steps of: identifying in a first class each state the removal of which does not disconnect the asynchronous state graph and the asynchronous state graph remains strongly-connected even after removal of the state; identifying in a second class each state the removal of which does not disconnect the asynchronous state graph and another state must be removed for the asynchronous state graph to remain strong-connected; and identify in a third class each state the removal of which disconnects the asynchronous state graph.
Claim 14
Dependent Claim
30 words
A method as set forth in claim 10, where said modifying the asynchronous state graph removes states identified in the first class before removing states identified in the second class.
Claim 15
Dependent Claim
30 words
A method as set forth in claim 11, where said modifying the asynchronous state graph removes states indentified in the second class in order of states removing fewest additional states.
Claim 16
Dependent Claim
21 words
A method as set forth in claim 12, where said removing of additional states is performed by a State Removal procedure.
Claim 17
Dependent Claim
20 words
A method as set forth in claim 10, where said identifying inconsistent states removes identified states in the third class.
Claim 18
Dependent Claim
77 words
A method as set forth in claim 8, where said modifying the signal transition graph comprises the steps of: traversing the state graph in a depth-first manner until an inconsistent state is reached; deleting from the state graph incoming and outgoing edges of a node corresponding to the inconsistent state; backtracking along the path of the node's ancestors and deleting nodes until reaching a node at which concurrency occurs; and removing redundant arcs from the state graph.
Claim 19
Dependent Claim
32 words
A method as set forth in claim 8, where the determined portion of the state vector includes primary input signals and initialized non-input signals and the undetermined portion includes uninitialized non-input signals.
Claim 20
Dependent Claim
24 words
A method as set forth in claim 16, where said updating updates the determined portion of the state vector to include initialized non-input signals.
Claim 21
Dependent Claim
16 words
A method as set forth in claim 8, where the signal transition graph is functionally uninitializable.
Claim 22
Dependent Claim
20 words
A method as set forth in claim 8, further comprising step (j) fabricating a circuit corresponding to the synthesized circuit.
Claim 23
Dependent Claim
24 words
A method as set forth in claim 19, further comprising step (k) applying the determined portion of the state vector to the fabricated circuit.
References Cited (Backward Citations)
US4167789A
Cited
US4845633A
Cited
US4922413A
Cited
US4862399A
Cited
US5005136A
Cited
US5036473A
Cited
US5163016A
Cited
US5331569A
Cited
US5337255A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-19 | 1999-08-21 | 2000-02-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-19 | 2003-08-21 | 2004-02-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-19 | 2007-08-21 | 2008-02-20 | $7700.00 | Window Closed / Lapsed |