Description and verification of RTL designs using multiway decision graphs

Abstract

Traditional OBDD-based methods of automated verification suffer from, the drawback that they require a binary representation of the circuit. Multiway Decision Graphs (MDGs) combine the advantages of OBDD techniques with those of abstract types. RTL designs can be compactly described by MDGs using abstract data values and uninterpreted function symbols. We have developed MDG-based techniques for combinational verification, reachability analysis, verification of behavioral equivalence, and verification of a microprocessor against its instruction set architecture. We report on the results of several verification experiments using our MDG package.