A SAT-Based Encoding for Finding a Minimal Automated Test Pattern Generation Test-Suite

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

A SAT-Based Encoding for Finding a Minimal Automated Test Pattern Generation Test-Suite

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

A SAT-Based Encoding for Finding a Minimal Automated Test Pattern Generation Test-Suite

Popis výsledku anglicky

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

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů