Title :
Verification of asynchronous circuits by Petri net unfoldings
Author :
Kondratyev, Alex ; Taubin, Alexander ; Ten, Sergey
Author_Institution :
Aizu Univ., Japan
Abstract :
In this paper we use the interpreted Petri nets (signal transition graph (STG) model) for a verification of asynchronous circuits. The main property in the analysis is the speed-independence of a circuit, i.e. the independence of circuit functioning from the delays of gates. The idea of analysis is based on the PN unfolding into an occurrence net. The improved method of unfolding is suggested, in which the size of the obtained description is always not larger than the size of a corresponding state graph. In terms of unfolding, the necessary and sufficient conditions for speed-independence are formulated. The algorithms of these conditions analysis are polynomial from the size of STG unfolding. The efficiency of the suggested algorithms is considered on the set of benchmarks.<>
Keywords :
Petri nets; asynchronous circuits; computational complexity; data compression; graph theory; logic design; logic testing; state assignment; Petri net unfoldings; asynchronous circuit verification; gate delays; necessary conditions; occurrence net; polynomial; signal transition graph; state graph; sufficient conditions; Algorithm design and analysis; Asynchronous circuits; Circuit analysis; Concurrent computing; Delay; Hardware; Petri nets; Polynomials; Signal analysis; Sufficient conditions;
Conference_Titel :
Emerging Technologies and Factory Automation, 1994. ETFA '94., IEEE Symposium on
Conference_Location :
Tokyo, Japan
Print_ISBN :
0-7803-2114-6
DOI :
10.1109/ETFA.1994.401983