doi: 10.7873/DATE.2015.0171

Using Structural Relations for Checking Combinationality of Cyclic Circuits

Wan-Chen Weng1, Yung-Chih Chen2, Jui-Hung Chen1, Ching-Yi Huang1 and Chun-Yao Wang2

1Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.

2Department of Computer Science and Engineering, Yuan Ze University, Chungli, Taiwan, R.O.C.


Functionality and combinationality are two main issues that have to be dealt with in cyclic combinational circuits, which are combinational circuits containing loops. Cyclic circuits are combinational if nodes within the circuits have definite values under all input assignments. For a cyclified circuit, we have to check whether it is combinational or not. Thus, this paper proposes an efficient two-stage algorithm to verify the combinationality of cyclic circuits. A set of cyclified IWLS 2005 benchmarks are performed to demonstrate the efficiency of the proposed algorithm. Compared to the state-of-the-art algorithm, our approach has a speedup of about 4000 times on average.

Full Text (PDF)