skip to main content
10.1145/1120725.1120798acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

Bridging fault detection in Double Fixed-Polarity Reed-Muller (DFPRM) PLA

Published: 18 January 2005 Publication History

Abstract

Testable design for detecting stuck-at and bridging faults in Programmable Logic Arrays (PLAs) based on Double Fixed-Polarity Reed-Muller Expression (DFPRM) is proposed. DFPRMs are generalized expressions of FPRM. It has advantages of compactness and easy testability. The EXOR part in the proposed design is implemented with tree structure that admits a universal test set. For an n-variable function, this design can be tested by (2n+8) test vectors, which are independent of the function and the circuit-under-test (CUT). Excepting a few intergate bridging faults in the EXOR-tree, it detects all other single bridging (both OR-and AND-type) and all single stuck-at faults. This tree based implementation reduces circuit delay significantly compared to cascaded EXOR-part.

References

[1]
S. M. Reddy, "Easily testable realizations for logic functions", IEEE TC, vol. 21, no. 11, pp. 1183--1188, Nov. 1972.
[2]
D. K. Pradhan, "Universal test sets for multiple fault detection in AND-EXOR arrays", IEEE TC, vol. 27, no. 2, pp. 181--187, Feb. 1978.
[3]
U. Kalay, D. V. Hall, and M. A. Perkowski, "A minimal universal test set for self-test of EXOR sum-of-products circuits", IEEE TC, vol. 49, no. 3, pp. 267--276 March 2000.
[4]
K. K. Saluja, and S. M. Reddy, "Fault detecting test sets for Reed-Muller Canonic networks", IEEE TC, vol. 24, pp. 995--998, 1975.
[5]
T. Sasao, Logic Synthesis and Optimization. Norwell, Mass, Kluwer Academic Publishers, 1993.
[6]
T. Sasao, "Easily testable realizations for generalized Reed-Muller expressions", IEEE TC, vol. 46, no.6, pp. 709--716, June 1997.
[7]
B. B. Bhattacharya, B. Gupta, S. Sarkar, and A. K. Choudhury, "Testable design of RMC networks with universal tests for detecting stuck-at and bridging faults", IEE Proceedings, Part E, vol. 132, pp. 155--161, May 1985.
[8]
H. Wu, M. A. Perkowski, X. Zeng, and N. Zhuang, "Generalized partially-mixed-polarity Reed-Muller expansion and its fast computation", IEEE TC, vol. 45, pp. 1084--1088, 1996.
[9]
R. Drechsler, H. Hengster, H. Schfer, J. Hartmann, and B. Becker, "Testability of 2-level AND/EXOR circuits", Journal of Electronic Testing, vol. 14, pp. 219--225, 1999.
[10]
H. Rahaman, D. K. Das, and B. B. Bhattacharya, "Testing of stuck-open faults in generalized Reed Muller and EXOR sum-of-products CMOS circuits", IEE Computers & Digital Techniques, Vol. 131, Issue 1, Jan. 2004.
[11]
P. Zhongliang, "Bridging fault detections for testable realizations of logic functions", Proc. of VLSI Design, pp. 423--427, January 2003.
[12]
H. Rahaman, D. K. Das, and B. B. Bhattacharya, "Easily testable realization of GRM and ESOP networks for detecting stuck-at and bridging faults", Proc. of VLSI Design, January 2004.
[13]
D. Debnath and T. Sasao, "GRMIN: A heuristic simplification algorithm for generalized Reed-Muller expressions", IEE Computers and Digital Techniques, vol. 143, no. 6, pp. 376--384, 1996.
[14]
V. Ciriani, "Logic minimization using exclusive OR gates", Proc. Design Automation Conference (DAC), pp. 115--120, 2001.
[15]
T. Sasao, "Representations of Logic Functions using EXOR Operators," IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995, pp. 11--20.
[16]
T. Sasao, and P. Besslich, "On the Complexity of Mod-2 Sum PLAs," IEEE TC, Vol.39, No.2, pp.262--266 (1990).
[17]
J. Saul, "logic synthesis for arithmetic circuits using the Reed-Muller representations," European Conf. On Design Automation, 1992, pp. 109--113.
[18]
H. Wu, M. A. Perkowski, X. Zeng, and N. Zhuang, "Generalized partially-mixed-polarity Reed-Muller expansion and its fast computation", IEEE TC, vol. 45, pp. 1084--1088, 1996.
[19]
H. Rahaman, D. K. Das, and B. B. Bhattacharya, "Testable Design of GRM Network with EXOR-Tree for Detecting Stuck-at and Bridging Faults," Proc. of ASPDAC, pp. 224--229, January 2004.
[20]
Fujiwara, H.: Logic Testing and Design for Testability, MIT Press (1985).
[21]
T. Hirayama, K. Nagasawa, Y. Nishitani, and K. Shimizu, "Double Fixed-Polarity Reed-Muller Expressions: A new Class of AND-EXOR Expressions for Compact and Testable Realization," IPSJ Journal, vol. 42, no. 4, pp.983--991, April 2001.
  1. Bridging fault detection in Double Fixed-Polarity Reed-Muller (DFPRM) PLA

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference
    January 2005
    1495 pages
    ISBN:0780387376
    DOI:10.1145/1120725
    • General Chair:
    • Ting-Ao Tang
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 18 January 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Article

    Conference

    ASPDAC05
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 466 of 1,454 submissions, 32%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 126
      Total Downloads
    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 18 Jan 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media