A COMPLEMENT-BASED FAST ALGORITHM TO GENERATE UNIVERSAL TEST SETS FOR MULTIOUTPUT FUNCTIONS

Abstract

In this paper, a fast universal test set (UTS) generation algorithm for multi-output functions is presented. The algorithm first generates the UTS for single-output functions by directly Shannon-expanding and complementing the function. This significantly reduces the time complexity and the usage of temporary memory. Also, it stores tests in test cubes to save the size of memory for test storing. Two-six orders of magnitude in computation efficiency improvement and 1-1800 fold for memory saving over the conventional method are achieved. It then merges the generated test cubes for each single-output function into a set of mutually disjoint test cubes to be the UTS for a multi-output function by employing a new compaction technique. The size of UTS thus obtained is 1-20 times smaller than that of UTS without compaction.