Dr. Chakravarty proposes to study computational problems in the domain of VLSI testing. He is especially concerned with the generation and compaction of test stimuli when the circuit is designed using design-for-testability rules, such as "Scan- In/Scan-Out", and Built-In Self-Test (BIST) design. Four problems are considered: test generation, random testing, compaction of test data, and on-chip test generation. He addresses these problems using several fault models: stuck-at, transistor stuck open, and feedback/non-feedback bridging faults. These problems are known to be NP-hard. Random testing for transistor stuck-open and bridging faults motivates a number of such problems. Dr. Chakravarty is investigating algorithms that lead to exact and to approximate solutions for these problems. He is also studying NP-hard minimization problems motivated by the need for compacting test data, looking for approximation algorithms and investigating the technique of simulated annealing to solve them.
