Synthesis of hazard-free asynchronous circuits based on characteristic graph

Author

Lin, Kuan Jen ; Kuo, Chi Wen ; Lin, Chen Shang

Author_Institution

Dept. of Electron. Eng., Chinese Inst. of Technol. & Commerce, Taipei, Taiwan

Volume

46

Issue

11

fYear

1997

fDate

11/1/1997 12:00:00 AM

Firstpage

1246

Lastpage

1263

Abstract

To synthesize hazard-free asynchronous circuits from Signal Transition Graphs (STGs), we present a new Characteristic Graph (CG) to encapsulate all feasible solutions of the original STG in reduced size, which compares favorably with the state graph approach. Based on CG, we are able to explore the design space, as well as develop a necessary and sufficient condition for hazard-free realization on a predefined general circuit model, which has not yet been reported. The exact optimization for synthesis is shown to be NP hard. A heuristic method is thus proposed which results in efficient solutions while requiring very little CPU time

Keywords

asynchronous circuits; hazards and race conditions; logic design; Signal Transition Graphs; characteristic graph; hazard-free asynchronous circuits; heuristic method; state graph; Asynchronous circuits; Central Processing Unit; Character generation; Circuit synthesis; Clocks; Concurrent computing; Design optimization; Signal synthesis; Space exploration; Sufficient conditions;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.644299

Filename

644299