Title :
Equivalence checking of integer multipliers
Author :
Chen, Jiunn-Chem ; Chen, Yirng-An
Author_Institution :
Dept. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsinchu, Taiwan
Abstract :
In this paper, we address on equivalence checking of integer multipliers, especially for the multipliers without structure similarity. Our approach is based on Hamaguchi´s backward substitution method with the following improvements: (1) automatic identification of components to form proper cut points and thus dramatically improve the backward substitution process; (2) a layered-backward substitution algorithm to reduce the number of substitutions; and (3) Multiplicative Power Hybrid Decision Diagrams (*PHDDs) as our word-level representation rather than *BMD in Hamaguchi´s approach. Experimental results show that our approach can efficiently check the equivalence of two integer multipliers. To verify the equivalence of a 32×32 array multiplier versus a 32×32 Wallace tree multiplier, our approach takes about 57 CPU seconds using 11 Mbytes, while Stanion´s approach took 21027 seconds using 130 MBytes. We also show that the complexity of our approach is upper bounded by O(n4), where n is the word size, but our experimental results show that the complexity of our approach grows cubically O(n3)
Keywords :
binary decision diagrams; circuit analysis computing; computational complexity; digital arithmetic; integrated logic circuits; multiplying circuits; Wallace tree multiplier; array multiplier; backward substitution method; complexity bound; equivalence checking; integer multipliers; layered-backward substitution algorithm; multiplicative power hybrid decision diagrams; word-level representation; Boolean functions; Central Processing Unit; Circuits; Computer bugs; Costs; Data structures; Delay; Error correction; Information science; Very large scale integration;
Conference_Titel :
Design Automation Conference, 2001. Proceedings of the ASP-DAC 2001. Asia and South Pacific
Conference_Location :
Yokohama
Print_ISBN :
0-7803-6633-6
DOI :
10.1109/ASPDAC.2001.913299