More Web Proxy on the site http://driver.im/

article

Free access

FILL and FUNI: algorithms to identify illegal states and sequentially untestable faults

Authors:

Mahesh A. Iyer,

Miron AbramoviciAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 5, Issue 3

Pages 631 - 657

https://doi.org/10.1145/348019.348311

Published: 01 July 2000 Publication History

Abstract

In this paper, we first present an algorithm (FILL) to efficiently identify a large subset of illegal states in synchronous sequential circuits, without assuming a global reset mechanism. A second algorithm, FUNI, finds sequentially untestable faults whose detection requires some of the illegal states computed by FILL. Although based on binary decision diagrams (BDDs), FILL is able to process large circuits by using a new functional partitioning procedure. The incremental building of the set of illegal states guarantees that FILL will always obtain at least a partial solution. FUNI is a direct method that identifies untestable faults without using the exhaustive search involved in automatic test generation (ATG). Experimental results show that FUNI finds a large number of untestable faults up to several orders of magnitude faster than an ATG algorithm that targeted the faults identified by FUNI. Also, many untestable faults identified by FUNI were aborted by the test generator.

References

[1]

ABRAMOVICI, M., BREUER, M., AND FRIEDMAN, A. D. 1990. Digital Systems Testing and Testable Design. Computer Science Press, Inc., New York, NY.

[2]

ABRAMOVICI, M. AND IYER, M.A. 1992. One-pass redundancy identification and removal. In Proceedings of the on IEEE International Test Conference (Sept. 1992), IEEE Computer Society Press, Los Alamitos, CA, 807-815.

[3]

ABRAMOVICI, M., KULIKOWSKI, g. g., AND ROY, R. K. 1991. The best flip-flops to scan. In Proceedings of the on IEEE International Test Conference (Oct. 1991), IEEE Computer Society Press, Los Alamitos, CA, 166-173.

[4]

ABRAMOVICI, M., KULIKOWSKI, J. J., MENON, P. R., AND MILLER, D. T. 1986. SMART and FAST: Test generation for VLSI scan-design circuits. IEEE Des. Test (Aug.).

[5]

ABRAMOVICI, M. AND BREUER, M.A. 1979. On redundancy and fault detection in sequential circuits. IEEE Trans. Comput. C-28, 11 (Nov.), 864-865.

Digital Library

[6]

AGRAWAL, V. D. AND CHAKRADHAR, S. T. 1993. Combinational ATPG theorems for identifying untestable faults in sequential circuits. In Proceedings of the on IEEE European Test Conference (Apr. 1993), IEEE Computer Society Press, Los Alamitos, CA, 249-253.

[7]

AGRAWAL, V. D. AND CHAKRADHAR, S. T. 1995. Combinational ATPG theorems for identifying untestable faults in sequential circuits. IEEE Trans. Comput.-Aided Des. 14, 9 (Sept.), 1155-1160.

Digital Library

[8]

BREUER, M.A. 1978. New concepts in automated testing of digital circuits. In Proceedings of the EEC Symposium on CAD of Digital Electronic Circuits and Systems (Nov.), North-Holland Publishing Co., Amsterdam, The Netherlands, 69-72.

[9]

BRGLEZ, F., BRYANT, D., AND KOZMINSKI, K. 1989. Combinational profiles of sequential benchmark circuits. In Proceedings of the IEEE International Symposium on Circuits and Systems (Portland, OR, May 1989), IEEE Press, Piscataway, NJ, 1929-1934.

[10]

BRYANT, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35, 8 (Aug. 1986), 677-691.

Digital Library

[11]

CHAKRABORTY, T. J., DAVIDSON, S., AND BENCIVENGA, B. 1991. GENTEST: The architecture of sequential circuit test generator. In Proceedings of the IEEE Conference on Custom Integrated Circuits (May 1991), IEEE Computer Society Press, Los Alamitos, CA.

[12]

CHAKRADHAR, S. T., AGRAWAL, V. D., AND ROTHWEILER, S. G. 1993. A transitive closure algorithm for test generation. IEEE Trans. Comput.-Aided Des. 12, 7 (July), 1015-1028.

Digital Library

[13]

CHO, H., HACHTEL, G. D., MACII, E., PLESSIER, B., AND SOMENZI, F. 1993a. Algorithms for approximate FSM traversal. In Proceedings of the 30th ACM/IEEE International Conference on Design Automation (DAC '93, Dallas, TX, June 14-18), A. E. Dunlop, Ed. ACM Press, New York, NY, 25-30.

[14]

CHO, H., HACHTEL, G. D., AND SOMENZI, F. 1993b. Redundancy identification/removal and test generation for sequential circuits using implicit state enumeration. IEEE Trans. Comput.- Aided Des. 12, 7 (July), 935-945.

Digital Library

[15]

CHO, H., JEONG, S. W., SOMENZI, F., AND PIXLEY, C. 1993c. Synchronizing sequences and symbolic traversal techniques in test generation. J. Electron. Test. 4, 1 (Feb.), 19-31.

[16]

COUDERT, O. AND MADRE, g. C. 1991. Symbolic computation of the valid states of a sequential machine: Algorithms and discussion. In Proceedings of the International Workshop on Formal Methods in VLSI Design (Jan. 1991),

[17]

COUDERT, O., BERTHET, C., AND MADRE, J. C. 1989. Verification of synchronous sequential machines based on symbolic execution. In Proceedings of the International Workshop on Automatic Verification Methods for Finite State Systems (Grenoble, France, June 12-14, 1989), J. Sifakis, Ed. Springer Lecture Notes in Computer Science, vol. 407. Springer-Verlag, New York, NY, 365-373.

Digital Library

[18]

IYER, M.A. 1991. One-pass redundancy identification and removal in combinational circuits. M.S. Thesis. Illinois Institute of Technology, Chicago, IL.

[19]

IYER, M.A. 1995. On redundancy and untestability in sequential circuits. Ph.D. Dissertation. Illinois Institute of Technology, Chicago, IL.

[20]

IYER, M. A. AND ABRAMOVICI, M. 1994a. Sequentially untestable faults identified without search (Simple implications beat exhaustive search!). In Proceedings of the on IEEE International Test Conference (Oct. 1994), IEEE Computer Society Press, Los Alamitos, CA, 259-266.

[21]

IYER, M. A. AND ABRAMOVICI, M. 1994b. Low-cost redundancy identification for combinational circuits. In Proceedings of the 7th International Conference on VLSI Design (India, Jan. 1994), 315-318.

[22]

IYER, M. A. AND ABRAMOVICI, M. 1996. FIRE: a fault-independent combinational redundancy identification algorithm. IEEE Trans. Very Large Scale Integr. Syst. 4, 2, 295-301.

Digital Library

[23]

IYER, M. A., LONG, D. E., AND ABRAMOVICI, M. 1996a. Surprises in sequential redundancy identification. In Proceedings of the IEEE European Conference on Design and Test (EDTC '96, Paris, France, Mar.), IEEE Press, Piscataway, NJ, 88-94.

[24]

IYER, M. A., LONG, D. E., AND ABRAMOVICI, M. 1996b. Identifying sequential redundancies without search. In Proceedings of the 33rd Annual Conference on Design Automation (DAC '96, Las Vegas, NV, June 3-7), T. P. Pennino and E. J. Yoffa, Eds. ACM Press, New York, NY, 457-462.

[25]

LIANG, H.-C., LEE, C. L., AND CHEN, J. E. 1994. A sequential redundant fault identification scheme and its application to test generation. In Proceedings of the IEEE Asian Symposium on Test, IEEE Computer Society Press, Los Alamitos, CA, 57-62.

[26]

LIANG, H.-C., LEE, C. L., AND CHEN, J. E. 1995. Identifying untestable faults in sequential circuits. IEEE Des. Test 12, 4 (Fall), 14-23.

[27]

LIN, B. AND TOUATI, H.J. 1990. Don't care minimization of multi-level sequential logic networks. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'90, Nov.), IEEE Computer Society Press, Los Alamitos, CA, 414-417.

[28]

LONG, D. E., IYER, M. A., AND ABRAMOVICI, M. 1995. Identifying sequentially untestable faults using illegal states. In Proceedings of the on 13th Annual IEEE VLSI Test Symposium (May 1995), IEEE Computer Society Press, Los Alamitos, CA, 4-11.

[29]

PIXLEY, C. 1990. A computational theory and implementation of sequential hardware equivalence. In Computer-Aided Verification, E. M. Clarke and R. P. Kurshan, Eds. 293-320.

[30]

POMERANZ, I. AND REDDY, S. M. 1992. The multiple observation time test strategy. IEEE Trans. Comput. 41, 5 (May 1992), 627-637.

Digital Library

[31]

POMERANZ, I. AND REDDY, S. M. 1993. Classification of faults in synchronous sequential circuits. IEEE Trans. Comput. 42 (Sept.), 1066-1077.

Digital Library

[32]

POMERANZ, I. AND REDDY, S. M. 1994. On identifying undetectable and redundant faults in synchronous sequential circuits. In Proceedings of the on 12th Annual IEEE VLSI Test Symposium (Apr.), IEEE Computer Society Press, Los Alamitos, CA, 8-14.

[33]

QADEER, S., BRAYTON, R. K., SINGHAL, V., AND PIXLEY, C. 1996. Latch redundancy removal without global reset. In Proceedings of the International Conference on Computer Design (ICCD'96, Austin, TX), IEEE Computer Society Press, Los Alamitos, CA.

[34]

RUTMAN, R.A. 1972. Fault detection test generation for sequential logic by heuristic tree search. IEEE Computer Group Repository, Paper No. R-72-187.

[35]

TOUATI, H. J., SAVOJ, H., LIN, B., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1990. Implicit state enumeration of finite state machines using BDDs. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'90, Nov.), IEEE Computer Society Press, Los Alamitos, CA, 130-133.

Cited By

Deligiannis NFaller TGuglielminetti ICantoro RBecker BReorda M(2023)Automatic Identification of Functionally Untestable Cell-Aware Faults in Microprocessors2023 IEEE 32nd Asian Test Symposium (ATS)10.1109/ATS59501.2023.10317988(1-6)Online publication date: 14-Oct-2023
https://doi.org/10.1109/ATS59501.2023.10317988
Bagbaba AAugusto da Silva FSonza Reorda MHamdioui SJenihhin MSauer C(2022)Automated Identification of Application-Dependent Safe Faults in Automotive Systems-on-a-ChipsElectronics10.3390/electronics1103031911:3(319)Online publication date: 20-Jan-2022
https://doi.org/10.3390/electronics11030319
Deligiannis NCantoro RSauer MBecker BReorda M(2021)New Techniques for the Automatic Identification of Uncontrollable Lines in a CPU Core2021 IEEE 39th VLSI Test Symposium (VTS)10.1109/VTS50974.2021.9441040(1-7)Online publication date: 25-Apr-2021
https://doi.org/10.1109/VTS50974.2021.9441040
Show More Cited By

Index Terms

FILL and FUNI: algorithms to identify illegal states and sequentially untestable faults
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Electronics
    2. Engineering
      1. Computer-aided design
2. Hardware

Recommendations

Identifying sequentially untestable faults using illegal states
VTS '95: Proceedings of the 13th IEEE VLSI Test Symposium

Abstract: In this paper, we first present an algorithm (FILL) which efficiently identifies a large subset of the illegal states in a synchronous sequential circuit, without assuming a global reset mechanism. A second algorithm, FUNI, finds sequentially ...
Untestable Fault Identification in Sequential Circuits Using Model-Checking
ATS '08: Proceedings of the 2008 17th Asian Test Symposium

Similar to test pattern generation, the problem of identifying untestable faults in sequential synchronous circuits remains unsolved. The previously published works in untestability identification operate at the logic-level and, thus, they do not scale ...
New techniques for untestable fault identification in sequential circuits

This paper presents two low-cost fault-independent techniques that can be used to identify significantly more untestable faults than could be identified by earlier fault-independent techniques. A new theorem and an efficient implementation of the theorem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 5, Issue 3

July 2000

483 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/348019

Editor:
Mary Jane Irwin
Pennsylvania State Univ., University Park

Issue’s Table of Contents

Copyright © 2000 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 July 2000

Published in TODAES Volume 5, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
546
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)8

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deligiannis NFaller TGuglielminetti ICantoro RBecker BReorda M(2023)Automatic Identification of Functionally Untestable Cell-Aware Faults in Microprocessors2023 IEEE 32nd Asian Test Symposium (ATS)10.1109/ATS59501.2023.10317988(1-6)Online publication date: 14-Oct-2023
https://doi.org/10.1109/ATS59501.2023.10317988
Bagbaba AAugusto da Silva FSonza Reorda MHamdioui SJenihhin MSauer C(2022)Automated Identification of Application-Dependent Safe Faults in Automotive Systems-on-a-ChipsElectronics10.3390/electronics1103031911:3(319)Online publication date: 20-Jan-2022
https://doi.org/10.3390/electronics11030319
Deligiannis NCantoro RSauer MBecker BReorda M(2021)New Techniques for the Automatic Identification of Uncontrollable Lines in a CPU Core2021 IEEE 39th VLSI Test Symposium (VTS)10.1109/VTS50974.2021.9441040(1-7)Online publication date: 25-Apr-2021
https://doi.org/10.1109/VTS50974.2021.9441040
Gursoy CJenihhin MOyeniran APiumatti DRaik JReorda MUbar R(2019)New categories of Safe Faults in a processor-based Embedded System2019 IEEE 22nd International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS)10.1109/DDECS.2019.8724642(1-4)Online publication date: Apr-2019
https://doi.org/10.1109/DDECS.2019.8724642
Cantoro RCarbonara SFloridia ASanchez ESonza Reorda MMess J(2019)Improved Test Solutions for COTS-Based Systems in Space ApplicationsVLSI-SoC: Design and Engineering of Electronics Systems Based on New Computing Paradigms10.1007/978-3-030-23425-6_10(187-206)Online publication date: 26-Jun-2019
https://doi.org/10.1007/978-3-030-23425-6_10
Cantoro RCarbonara SFloridia ASanchez EReorda MMess J(2018)An analysis of test solutions for COTS-based systems in space applications2018 IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)10.1109/VLSI-SoC.2018.8644846(59-64)Online publication date: Oct-2018
https://doi.org/10.1109/VLSI-SoC.2018.8644846
Hosokawa TNiseki MYoshimura MYamazaki HArai MYotsuyanagi HHashizume M(2018)A Sequentially Untestable Fault Identification Method Based on n-Bit State Cube Justification2018 IEEE 24th International Symposium on On-Line Testing And Robust System Design (IOLTS)10.1109/IOLTS.2018.8474268(43-46)Online publication date: Jul-2018
https://doi.org/10.1109/IOLTS.2018.8474268
Bernardeschi CCassano LDomenici ASterpone L(2016)UA2TPG: An untestability analyzer and test pattern generator for SEUs in the configuration memory of SRAM-based FPGAsIntegration10.1016/j.vlsi.2016.03.00455(85-97)Online publication date: Sep-2016
https://doi.org/10.1016/j.vlsi.2016.03.004
Cassano L(2014)Analysis and test of the effects of single event upsets affecting the configuration memory of SRAM-based FPGAs2014 International Test Conference10.1109/TEST.2014.7035366(1-10)Online publication date: Oct-2014
https://doi.org/10.1109/TEST.2014.7035366
Bernardeschi CCassano LDomenici ASterpone LAyala JJones AMadden PCoskun A(2013)Unexcitability analysis of SEus affecting the routing structure of SRAM-based FPGAsProceedings of the 23rd ACM international conference on Great lakes symposium on VLSI10.1145/2483028.2483050(7-12)Online publication date: 2-May-2013
https://dl.acm.org/doi/10.1145/2483028.2483050
Show More Cited By

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents