Test pattern generation using Boolean satisfiability

Author

Larrabee, Tracy

Author_Institution

Dept. of Comput. Sci., Stanford Univ., CA, USA

Volume

11

Issue

1

fYear

1992

fDate

1/1/1992 12:00:00 AM

Firstpage

4

Lastpage

15

Abstract

The author describes the Boolean satisfiability method for generating test patterns for single stuck-at faults in combinational circuits. This new method generates test patterns in two steps: first, it constructs a formula expressing the Boolean difference between the unfaulted and faulted circuits, and second, it applies a Boolean satisfiability algorithm to the resulting formula. This approach differs from previous methods now in use, which search the circuit structure directly instead of constructing a formula from it. The new method is general and effective. It allows for the addition of heuristics used by structural search methods, and it has produced excellent results on popular test pattern generation benchmarks

Keywords

Boolean algebra; combinatorial circuits; logic testing; Boolean satisfiability; combinational circuits; single stuck-at faults; test pattern generation; Automatic test pattern generation; Circuit faults; Circuit testing; Combinational circuits; Data structures; Logic testing; Performance evaluation; Search methods; System testing; Test pattern generators;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.108614

Filename

108614