Article

Free access

CATAPULT: concurrent automatic testing allowing parallelization and using limited topology

Authors:

Rhonda Kay Gaede,

Kenneth M. ButlerAuthors Info & Claims

DAC '88: Proceedings of the 25th ACM/IEEE Design Automation Conference

Pages 597 - 600

Published: 01 June 1988 Publication History

Abstract

This paper deals with an improved algorithm for identifying redundant faults and finding tests for “hard faults” in combinational circuits. A new, concurrent approach is proposed which is based upon the concepts of functional decomposition, explicit representation of fanout stems and the Boolean difference. The data structure to be used is the Binary Decision Diagram as developed by Lee, Akers and Bryant. This algorithm operates as a backend to test generators which use random patterns or heuristics or a combination of the two.

References

[1]

Sheldon B. Akers Jr.,"On a Theory of Boolean Functions", Journal of the Society of Industrial and applied MathematicS, No. 4,December 1959,pp. 487-498.

[2]

Sheldon B. Akers,Jr.,"Binary Decision Diagrams", IEEE Transactions on Computers,Vol. C-27,No. 6, June 1978, pp. 509-516.

[3]

M. Abramovici, P. R. Menon and D. T. Miller, "Check~int Faults are not Sufficient Target Faults for Test Generation", IEEE Tmnsaction~ on (7omput~r~, Vol. C-35, No. 8, August 1986, pp. 769-771.

Digital Library

[4]

D. B. Armstrong,"On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets", IEEE Transactions on Electronic Computers, Vol. EC-15, Feb. 1966, pp.66-73.

[5]

M.A. Breuer and A.D. Friedman, Dia_maosis & Reliable Design of Digital Systems,Computer Science Press, 1976.

Digital Library

[6]

F. Brglez and H. Fujiwara, "A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran",Proceedings of the IEEE International Symposium on Circuits and Systems, June 1985.

[7]

Randal E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Com- ~, Volume C-35, No. 8, August 1986, pp. 677-691.

Digital Library

[8]

E. B. Eichelberger and T. W. Williams," A Logic Design Structure for LSI Testability ", 14th Design Automation Conference Proceedings, 1977, pp. 462-467.

Digital Library

[9]

H. Fujiwara and T. S himono, "On the Acceleration of Test Generation Algorithms", IEEE Transactions on Comp_.uter__As, Vol. C-32, No. 12, December 1983.

[10]

Prabhakar Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", IEEE Transactions on Computers, Vol. C-30, No. 3, March 1981, pp. 215-222.

[11]

Ki Soo Hwang and M. Ray Mercer, "Derivation and Refinement of Fan-Out Constraints to Generate Tests in Combinational Logic Circuits", IEEE Transactions on Comouter- Aided Design, Vol. CAD-5, No. 4, October 1986, pp. 564-572.

[12]

Tom Kirkland and M. Ray Mercer, "A Topological Search Algorithm for ATPG", Proceedings ofthe 24th ACM/ IEEE Design Automation Conference,June 1987, pp. 502-508.

Digital Library

[13]

C. Y. Lee, "Representation of Switching Circuits by Binary-Decision Programs", Bell System Technical Journal, Vol. 38, July 1959, pp. 985-999.

[14]

J. Paul Roth, "Diagnosis of Automata Failures: A Calculus and a Method", IBM Journal of Research and Develoomen.__!t, Vol. 10, July 1966, pp. 278-291.

Digital Library

[15]

M. H. Schulz, E. Trischler and T. M. Sarfert, IEEE Transactions on Computer-Aided Design, Vol. CAD-7, No. 1, January 1988, pp. 126-137.

[16]

C. Eo Shannon, "A Symbolic Analysis of Relay and Switching Circuits", Transactions of the AIEE, Vol. 57, 1938, pp. 713-723.

[17]

J.A. Waicukauski, E.B. Eichelberger, D.O. Forlenza, E. Lindbloom and T. McCarthy, "Fault Simulation for Structured VIii", ~SI Systems Design, December 1985, pp. 20-32.

Cited By

Bushnell MGiraldi J(1997)A Functional Decomposition Method for Redundancy Identification and Test GenerationJournal of Electronic Testing: Theory and Applications10.1023/A:100820742385910:3(175-195)Online publication date: 1-Jun-1997
https://dl.acm.org/doi/10.1023/A%3A1008207423859
Mukherjee RJain JFujita MAbraham JFussell D(1996)On More Efficient Combinational ATPG Using Functional LearningProceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication10.5555/525699.834799Online publication date: 3-Jan-1996
https://dl.acm.org/doi/10.5555/525699.834799
Drechsler RMermet J(1994)BiTeSProceedings of the conference on European design automation10.5555/198174.198276(322-327)Online publication date: 23-Sep-1994
https://dl.acm.org/doi/10.5555/198174.198276
Show More Cited By

Index Terms

CATAPULT: concurrent automatic testing allowing parallelization and using limited topology

Recommendations

Optimized reversible binary-coded decimal adders

Babu and Chowdhury [H.M.H. Babu, A.R. Chowdhury, Design of a compact reversible binary coded decimal adder circuit, Journal of Systems Architecture 52 (5) (2006) 272-282] recently proposed, in this journal, a reversible adder for binary-coded decimals. ...
Hardware Designs for Decimal Floating-Point Addition and Related Operations

Decimal arithmetic is often used in commercial, financial, and Internet-based applications. Due to the growing importance of decimal floating-point (DFP) arithmetic, the IEEE 754 Draft Standard for Floating-Point Arithmetic (IEEE P754) includes ...
Logic Networks of Carry-Save Adders

logic networks of carry-save adders such as high-speed multipliers, multioperand adders, and double-rail input parallel adders are designed based on the parallel adders with a minimum number of NOR gates discussed in [1]. After a discussion of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '88: Proceedings of the 25th ACM/IEEE Design Automation Conference

June 1988

730 pages

ISBN:0818688645

Chairmen:
Dennis W. Shaklee
AT&T/ISL, Denver, CO
,
A. Richard Newton
Univ. of California, Berkeley

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE: Institute of Electrical and Electronics Engineers

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 June 1988

Check for updates

Qualifiers

Article

Conference

DAC88

Sponsor:

SIGDA
IEEE

DAC88: Design Automation Conference

June 12 - 15, 1988

New Jersey, Atlantic City, USA

Acceptance Rates

DAC '88 Paper Acceptance Rate 125 of 400 submissions, 31%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
191
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)5

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bushnell MGiraldi J(1997)A Functional Decomposition Method for Redundancy Identification and Test GenerationJournal of Electronic Testing: Theory and Applications10.1023/A:100820742385910:3(175-195)Online publication date: 1-Jun-1997
https://dl.acm.org/doi/10.1023/A%3A1008207423859
Mukherjee RJain JFujita MAbraham JFussell D(1996)On More Efficient Combinational ATPG Using Functional LearningProceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication10.5555/525699.834799Online publication date: 3-Jan-1996
https://dl.acm.org/doi/10.5555/525699.834799
Drechsler RMermet J(1994)BiTeSProceedings of the conference on European design automation10.5555/198174.198276(322-327)Online publication date: 23-Sep-1994
https://dl.acm.org/doi/10.5555/198174.198276
Minato SDunlop A(1993)Zero-suppressed BDDs for set manipulation in combinatorial problemsProceedings of the 30th international Design Automation Conference10.1145/157485.164890(272-277)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/157485.164890
Butler KMercer MSmith R(1991)The influences of fault type and topology on fault model performance and the implications to test and testable designProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123436(673-678)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123436
Giraldi JBushnell MSmith R(1991)ESTProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123434(667-672)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123434

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents