J4 ›› 2009, Vol. 36 ›› Issue (5): 877-884.

• Original Articles • Previous Articles     Next Articles

Combinational equivalence checking based on AIG reasoning

FAN Quan-run;DUAN Zhen-hua;XU Guo-pei   

  1. (School of Computer Science and Technology, Xidian Univ., Xi'an  710071, China)
  • Received:2008-12-16 Online:2009-10-20 Published:2009-11-30
  • Contact: FAN Quan-run E-mail:ynfqr@163.com

Abstract:

Most SAT based combinational equivalence checking algorithms combine two circuits into a miter, and then convert the miter into a CNF formula. After that, an SAT solver is invoked to check whether the CNF formula is satisfiable. However, when a miter is converted into a CNF formula, the structure information of the circuit is lost. In this paper, we assume the output of the miter is 1, and then the backtracking method is used for conflict checking to decide the satisfiability of the miter. By using the character of AIG, four input combinations of each node can be reduced into one to simplify the deducing procedure. Preliminary experiments demonstrate the efficiency of our approach.

Key words: combinational circuits, CEC, circuit reasoning, AIG

CLC Number: 

  • TN47