Accurate logic simulation in the presence of unknowns

Abstract

The authors address the problem of accurate logic simulation in the presence of unknowns. Algorithms to perform exact simulation using high-level descriptions are presented. The complexity of these algorithms is shown to be considerably less than that of existing algorithms. An analysis of realistic programmable logic arrays (PLAs) and some random functions is used to compare the complexity of the two algorithms presented. Data on the SN74181 ALU suggest that function blocks of similar size can be easily dealt with. The feasibility of the approach is demonstrated by a programmed implementation of the algorithms as part of a high-level test generation system.