A SAT-Based Encoding for Finding a Minimal Automated Test Pattern Generation Test-Suite
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F21%3A00354103" target="_blank" >RIV/68407700:21730/21:00354103 - isvavai.cz</a>
Result on the web
<a href="https://www.hsu-hh.de/imb/wp-content/uploads/sites/677/2021/09/DX-2021_paper_16.pdf" target="_blank" >https://www.hsu-hh.de/imb/wp-content/uploads/sites/677/2021/09/DX-2021_paper_16.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A SAT-Based Encoding for Finding a Minimal Automated Test Pattern Generation Test-Suite
Original language description
Existing methods for Automated Test Pattern Generation (ATPG) for digital Integrated Circuits (ICs) typically have two phases: (1) computation of test-vectors for all faults and (2) compaction of the test-vectors into a test-suite. The compaction is needed, because, the main cost of testing is the time necessary to apply all test-vectors one after another. This paper proposes a novel encoding that can calculate the whole ATPG test-suite in one go, thus solving together both (1) and (2). To the best of our knowledge, our method and encoding are the first to provide theoretical lower bounds on the size of the test-suite. We experiment extensively on the ISCAS-85 benchmark. Our method solves circuits of non-trivial size. For example, we find a test-suite of only 13 vectors that tests all 942 stuck-at-0 and stuck-at-1 possible faults for the c880 arithmetic-logic unit and control circuit. Similarly, all 2000 stuck-at-1 faults in the c6288 16x16-bit multiplier can be covered by only 3 vectors. Our method is capable of generating proofs showing that the generated test-suites are of minimal size
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů