Test-cubes Compaction for Digital Circuits
Alessio Signorini
University of Iowa, Computer Science
alessio-signorini@uiowa.edu		   Santiago Remersaro
University of Iowa, Eletrical Engineering
santiago-remersaro@uiowa.edu


Download the article
  PDF Version     PS Version
Abstract
The generation of minimal sets for faults detection in digital circuits, is an important problem in the industry. Unfortunately, the problem has been demonstrated to be NP-hard. In this report we present six heuristics capable to reduce a given sets of test-cubes to a minimal set of test-cases, with an average compression of about the 95\%. The methods that we propose, combine together personal intuitions and known heuristic methods as GRASP or TABU search. Even if the results obtained are not excellent, the reported experiments demonstrate the effectiveness of the proposed algorithms.
Introduction
In practical industry environments the faults test of electronic circuits is an important part of the production chain. Discover faults that "may" occur, before releasing a product, is crucial to maintain customers confidence and to avoid future expenses for customer support.

To discover those faults, the digital circuit has to be tested with specific inputs. Due to the complexity of the circuit, some input lines may not be relevant for the detection of certain faults and can assume any value. This allows to combine several test-cubes together and test more than one fault with a single input, simplifying the testing procedure, and saving time and resources.

Thus, given a set of test-cubes capable to test all the faults of a circuit, we would like to find the minimal set of test-cases derivable from it. This is a known NP-hard problem and optimal solutions are computable only for small sets of test-cubes, due to the large amount of possible combination sequences that might be follow.

In this report we describe and compare six different heuristic approaches developed by our research group.
Download
You can download the complete package, with all the heuristic described in the report and the test-sets used, from the following address

     Test-Cubes-Compaction - v0.9
Bibliography
Updated soon...