On polynomial-time testable classes of combinational circuits

N. S.V. Rao; S. Toida

doi:10.1109/VTEST.1991.208154

On polynomial-time testable classes of combinational circuits

N. S.V. Rao, S. Toida

Research output: Contribution to conference › Paper › peer-review

1 Scopus citations

Abstract

The problem of test generation for detecting stuck-at faults in combinational circuits is computationally intractable. Consequently, the identification of classes of circuits that support polynomial-time test generation algorithms is very important from testing and design viewpoints. The authors discuss several classes of polynomially-time testable circuits. First, they consider the existing polynomial classes obtained by using decompositions of the circuits. Another type of decomposition is proposed, based on fanout-reconvergent (f-r) pairs, which also lead to classes of polynomial-time testable circuits. Then, the authors present the classes of polynomial-time testable circuits that are formed by the Boolean formulae belonging to the classes of weakly positive, weakly negative, bijunctive and affine.

Original language	English
Pages	172-177
Number of pages	6
DOIs	https://doi.org/10.1109/VTEST.1991.208154
State	Published - 1991
Externally published	Yes
Event	1991 IEEE VLSI Test Symposium: Chip-to-System Test Concerns for the 90''s, VTEST 1991 - Atlantic City, United States Duration: Apr 15 1991 → Apr 17 1991

Conference

Conference	1991 IEEE VLSI Test Symposium: Chip-to-System Test Concerns for the 90''s, VTEST 1991
Country/Territory	United States
City	Atlantic City
Period	04/15/91 → 04/17/91

Keywords

NP-completeness
combinational circuits
polynomial-time testability
test generation

Access to Document

10.1109/VTEST.1991.208154

Cite this

@conference{51385411ad78417fbdd8b25d32961a47,

title = "On polynomial-time testable classes of combinational circuits",

abstract = "The problem of test generation for detecting stuck-at faults in combinational circuits is computationally intractable. Consequently, the identification of classes of circuits that support polynomial-time test generation algorithms is very important from testing and design viewpoints. The authors discuss several classes of polynomially-time testable circuits. First, they consider the existing polynomial classes obtained by using decompositions of the circuits. Another type of decomposition is proposed, based on fanout-reconvergent (f-r) pairs, which also lead to classes of polynomial-time testable circuits. Then, the authors present the classes of polynomial-time testable circuits that are formed by the Boolean formulae belonging to the classes of weakly positive, weakly negative, bijunctive and affine.",

keywords = "NP-completeness, combinational circuits, polynomial-time testability, test generation",

author = "Rao, \{N. S.V.\} and S. Toida",

note = "Publisher Copyright: {\textcopyright} 1991 IEEE.; 1991 IEEE VLSI Test Symposium: Chip-to-System Test Concerns for the 90''s, VTEST 1991 ; Conference date: 15-04-1991 Through 17-04-1991",

year = "1991",

doi = "10.1109/VTEST.1991.208154",

language = "English",

pages = "172--177",

}

TY - CONF

T1 - On polynomial-time testable classes of combinational circuits

AU - Rao, N. S.V.

AU - Toida, S.

PY - 1991

Y1 - 1991

N2 - The problem of test generation for detecting stuck-at faults in combinational circuits is computationally intractable. Consequently, the identification of classes of circuits that support polynomial-time test generation algorithms is very important from testing and design viewpoints. The authors discuss several classes of polynomially-time testable circuits. First, they consider the existing polynomial classes obtained by using decompositions of the circuits. Another type of decomposition is proposed, based on fanout-reconvergent (f-r) pairs, which also lead to classes of polynomial-time testable circuits. Then, the authors present the classes of polynomial-time testable circuits that are formed by the Boolean formulae belonging to the classes of weakly positive, weakly negative, bijunctive and affine.

AB - The problem of test generation for detecting stuck-at faults in combinational circuits is computationally intractable. Consequently, the identification of classes of circuits that support polynomial-time test generation algorithms is very important from testing and design viewpoints. The authors discuss several classes of polynomially-time testable circuits. First, they consider the existing polynomial classes obtained by using decompositions of the circuits. Another type of decomposition is proposed, based on fanout-reconvergent (f-r) pairs, which also lead to classes of polynomial-time testable circuits. Then, the authors present the classes of polynomial-time testable circuits that are formed by the Boolean formulae belonging to the classes of weakly positive, weakly negative, bijunctive and affine.

KW - NP-completeness

KW - combinational circuits

KW - polynomial-time testability

KW - test generation

UR - https://www.scopus.com/pages/publications/85066890433

U2 - 10.1109/VTEST.1991.208154

DO - 10.1109/VTEST.1991.208154

M3 - Paper

AN - SCOPUS:85066890433

SP - 172

EP - 177

T2 - 1991 IEEE VLSI Test Symposium: Chip-to-System Test Concerns for the 90''s, VTEST 1991

Y2 - 15 April 1991 through 17 April 1991

ER -

On polynomial-time testable classes of combinational circuits

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this