Research Initiation: An Investigation of Test Compaction Algorithms and On-Chip Test Generation Schemes

Chakravarty博士建议研究VLSI测试领域的计算问题。他特别关注当电路设计使用可测试性设计规则时测试刺激的产生和压缩，例如“扫描-输入/扫描-输出”和内置自检（BIST）设计。考虑了四个问题：测试生成、随机测试、测试数据的压缩和片上测试生成。他使用几种故障模型来解决这些问题：卡在、晶体管卡开、反馈/非反馈桥接故障。这些问题被称为np困难问题。对晶体管卡开和桥接故障的随机测试引发了许多这样的问题。查克拉瓦蒂博士正在研究为这些问题提供精确和近似解决方案的算法。他也在研究NP-hard最小化问题，因为需要压缩测试数据，寻找近似算法，并研究模拟退火技术来解决这些问题。

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.