Article

Static logic implication with application to redundancy identification

Authors:

J. H. PatelAuthors Info & Claims

VTS '97: Proceedings of the 15th IEEE VLSI Test Symposium

Page 288

Published: 27 April 1997 Publication History

Abstract

This paper presents a new static logic implication algorithm. An improved implication procedure that fully takes advantage of the special context of static implication, the iterative method, and set algebra is described. The algorithm discovers at low cost many indirect implications which are not discovered by dynamic learning without tremendous time cost. The experimental results show that a very large number of indirect implications are found by our algorithm. The static implication procedure has many useful applications, one of which is static redundancy identification. Use of the static implications obtained from the algorithm in static redundancy identification for ISCAS85 combinational circuits resulted in a larger number of redundant faults identified than in previous methods.

References

[1]

M. H. Schulz and E. Auth, "Improved Deterministic Test Pattern Generation with Applications to Redundancy Identification," IEEE Trans. Computer-Aided Design, pp. 811-816, July 1989.

[2]

W. Kunz and D. K. Pradhan, "Accelerated Dynamic Learning for Test Pattern Generation in Combinational Circuits," IEEE Trans. Computer-Aided Design, pp. 684-694, May 1993.

[3]

M. H. Schulz, E. Trischler, and T. M. Sarfert, "SOCRATES: A Highly Efficient Automatic Test Pattern Generation System," IEEE Trans. Computer-Aided Design, pp. 126-136, January 1988.

Digital Library

[4]

W. Kunz and P. Menon, "Multi-Level Logic Optimization by Implication Analysis," Proc. IEEE Int. Conf. Computer-Aided Design, pp. 6-13, 1994.

Digital Library

[5]

H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," IEEE Trans. Computers, pp. 1137-1144, December 1983.

Digital Library

[6]

P. Wohl and J. Waicukauski, "Test Generation for Ultra-Large Circuits Using ATPG Constraints And Test-Pattern Templates," Proc. Int. Test Conf., pp. 13-20, October 1996.

Digital Library

[7]

P. R. Menon and M. Harihara, "Redundancy Identification and Removal in Combinational Circuits," Proc. Int. Conf. Computer Design, pp. 290-293, October 1989.

[8]

P. R. Menon and H. Ahuja "Redundancy Removal and Simplification of Combinatinal Circuits," Proc. IEEE VLSI Test Symp., pp. 268-273, April 1992.

[9]

J. Rajski and H. Cox, "A Method to Calculate Necessary Assignments in Algorithmic Test Pattern Generation," Proc. IEEE Int. Test Conf., pp. 25-34, September 1990.

[10]

S. T. Chakradhar and V. D. Agrawal, "A Transitive Closure Based Algorithm for Test Generation," Proc. ACM/IEEE Design Automation Conf., pp. 353-358, June 1991.

Digital Library

[11]

S. T. Chakradhar, V. D. Agrawal, and S. G. Rothweiler, "A Transitive Closure Algorithm for Test Generation," IEEE Trans. Computer-Aided Design, pp. 1015-1028, July 1993.

[12]

W. Kunz and D. Pradhan, "Recursive Learning: An Attractive Alternative to the Decision Tree for Test Generation in Digital Circuits," Proc. Int. Test Conf., pp. 816-825, September 1992.

Digital Library

[13]

M. A. Iyer and M. Abramovici, "Low Cost Redundancy Identification for Combinational Circuits," Proc. Int. Conf. VLSI Design, pp. 315-318, January 1994.

[14]

M. A. Iyer and M. Abramovici, "FIRE: A Fault-Independent Combinational Redundancy Identification Algorithm," IEEE Trans. VLSI Systems, pp. 295-301, June 1996.

Digital Library

[15]

D.B. Armstrong, "A Deductive Method for Simulating Faults in Logic Circuits," IEEE Trans. Computers, pp. 464-471, May 1972.

Digital Library

[16]

T. M. Niermann, W. T. Cheng, and J. H. Patel, "PROOFS: A Fast, Memory-Efficient Sequential Circuit Fault Simulator," IEEE Trans. Computer-Aided Design, pp. 198-207, February 1992.

Digital Library

[17]

J. A. Newquist, "Fast Logic Implication Discovery," M.S. Thesis, University of Illinois at Urbana-Champaign, 1997.

Cited By

Elbayoumi MHsiao MElNainay MAyala JJones AMadden PCoskun A(2013)Set-cover-based critical implications selection to improvesat-based bounded model checkingProceedings of the 23rd ACM international conference on Great lakes symposium on VLSI10.1145/2483028.2483128(331-332)Online publication date: 2-May-2013
https://dl.acm.org/doi/10.1145/2483028.2483128
Alves NNepal KDworak JBahar RBenini LDe Micheli GAl-Hashimi BMueller W(2009)Detecting errors using multi-cycle invariance informationProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874815(791-796)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874815
Wu WHsiao MSentovich E(2006)Mining global constraints for improving bounded sequential equivalence checkingProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147098(743-748)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147098
Show More Cited By

Recommendations

A SAT-based implication engine for efficient ATPG, equivalence checking, and optimization of netlists
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

The paper presents a flexible and efficient approach to evaluating implications as well as deriving indirect implications in logic circuits. Evaluation and derivation of implications are essential in ATPG, equivalence checking, and netlist optimization. ...
Surprises in Sequential Redundancy Identification
EDTC '96: Proceedings of the 1996 European conference on Design and Test

This paper addresses some misconceptions about redundancy in synchronous sequential circuits. We provide examples to illustrate the differences between untestability and redundancy and discuss existing techniques to identify sequential redundancy. We ...
Does retiming affect redundancy in sequential circuits?
VLSID '96: Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication

Retiming is used to optimize logic and improve the speed of operation in sequential circuits keeping the circuit behavior unchanged. In this paper, we show with various examples that retiming affects redundancy of faults. It may change an operationally ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

VTS '97: Proceedings of the 15th IEEE VLSI Test Symposium

April 1997

ISBN:0818678100

Copyright © Copyright (c) 1997 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 27 April 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Elbayoumi MHsiao MElNainay MAyala JJones AMadden PCoskun A(2013)Set-cover-based critical implications selection to improvesat-based bounded model checkingProceedings of the 23rd ACM international conference on Great lakes symposium on VLSI10.1145/2483028.2483128(331-332)Online publication date: 2-May-2013
https://dl.acm.org/doi/10.1145/2483028.2483128
Alves NNepal KDworak JBahar RBenini LDe Micheli GAl-Hashimi BMueller W(2009)Detecting errors using multi-cycle invariance informationProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874815(791-796)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874815
Wu WHsiao MSentovich E(2006)Mining global constraints for improving bounded sequential equivalence checkingProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147098(743-748)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147098
Vimjam VHsiao MSentovich E(2006)Fast illegal state identification for improving SAT-based inductionProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1146972(241-246)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1146972
Wu QHsiao M(2006)A New Simulation-Based Property Checking Algorithm Based on Partitioned Alternative Search Space TraversalIEEE Transactions on Computers10.1109/TC.2006.17055:11(1325-1334)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TC.2006.170
Parthasarathy GIyer MCheng KBrewer FJoyner WMartin GKahng A(2005)Structural search for RTL with predicate learningProceedings of the 42nd annual Design Automation Conference10.1145/1065579.1065698(451-456)Online publication date: 13-Jun-2005
https://dl.acm.org/doi/10.1145/1065579.1065698
Vimjam VSyal MHsiao MLach JQu GIsmail Y(2005)Untestable fault identification through enhanced necessary value assignmentsProceedings of the 15th ACM Great Lakes symposium on VLSI10.1145/1057661.1057705(176-181)Online publication date: 17-Apr-2005
https://dl.acm.org/doi/10.1145/1057661.1057705
Liu XHsiao M(2005)A Novel Transition Fault ATPG That Reduces Yield LossIEEE Design & Test10.1109/MDT.2005.12622:6(576-584)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1109/MDT.2005.126
Chandrasekar KHsiao M(2005)Integration of Learning Techniques into Incremental Satisfiability for Efficient Path-Delay Fault Test GenerationProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.187(1002-1007)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/DATE.2005.187
Mehta VDave KAgrawal VBushnell M(2003)A Fault-Independent Transitive Closure Algorithm for Redundancy IdentificationProceedings of the 16th International Conference on VLSI Design10.5555/832285.835568Online publication date: 4-Jan-2003
https://dl.acm.org/doi/10.5555/832285.835568
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents