der Martin-Luther-Universitaet Halle-Wittenberg



Title  Prove that a faulty multiplier is faulty !?


Authors  S. Wefel and P. Molitor.


How published  In Proceedings of 10th Great Lakes Symposium on VLSI, GLS-VLSI, Chicago, Illinois, U.S.A., March 2000.



Formal verification of integer multipliers was an open problem for a long time as the size of any reduced ordered binary decision diagram (BDD) which represents integer multiplication is exponential in the width of the operands. In 1995, Bryant and Chen introduced multiplicative binary moment diagrams (*BMD) which is a canonical data structure for pseudo Boolean functions allowing a linear representation of integer multipliers. Based on this data structure, Bryant/Chen and Hamaguchi experimentally showed that integer multipliers up to a word size of 64 bits can be formally verified. However, all these results only handle the problem of proving a faultless integer multiplier to be correct. But, what happens if the multiplier is faulty? Does the backward construction method stop after a short time? After what time can I be sure that the integer multiplier under consideration is faulty? In this paper, we show that these questions are relevant in practice. In particular, we investigate simple add-step multipliers and show that simple design errors can lead to exponential growth of the *BMDs occuring during backward construction. This proves that the backward construction method can only be applied as filter during formal logic combinational verification unless sharp upper bounds for the sizes of the *BMDs occuring during the backward construction have been proven for the various circuit types as Keim did it for Wallace tree multipliers.




E-Mail, 4.12.1999