{'fraction_non_alphanumeric': 0.019830028328611898, 'fraction_numerical': 0.0, 'mean_word_length': 5.639097744360902, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Models and Algorithms for Optimization Problems in Digital Circuits Testing

The field of automatic test pattern generation (ATPG) presents a large number of challenging optimization problems of key significance that impact testing time, built-in self-test (BIST), power dissipation, among others. Unfortunately, the vast majority of these problems are most often solved using heuristic approaches that do not guarantee an optimum solution. Discrete algorithms, in particular satisfiability search algorithms (SAT), are a promising technique for solving optimization problems cast as integer linear programming (ILP) instances, however, for most ATPG problems no formal optimization models existed, so far. In this dissertation we derive several optimization models for ATPG problems concerning test set compaction, BIST and power dissipation. We present models for test set compaction which minimize the total number of test patterns that detect all detectable faults in a combinational circuit. We define a new optimization model for computing test patterns with don’t cares, that identifies test patterns with the least number of specified input assignments that detect a target fault. We propose a model to identify a minimal BIST test generator circuit, which detects all detectable faults, assuming that some primary circuit inputs can be declared equivalent for testing purposes. Finally, we develop a model for optimum pattern sequence reordering and don’t care assignment that impacts directly the power dissipation during test set application. We have implemented all the models and algorithms that have reasonable representation size and present results using the ISCAS and IWLS benchmark circuits which confirm the practical applicability of our models.