Data compression in space under generalized mergeability based on concepts of cover table and frequency ordering

Journal Article (Journal Article)

The synthesis of space-efficient support hardware for built-in self-testing (BIST) is of critical importance in the design and manufacture of today's sophisticated VLSI circuits, and a number of efficient algorithms have been proposed in the literature for this purpose. The subject paper reports new techniques that facilitate designing such space-efficient BIST support circuits using knowledge of compact test sets, with the target objective of minimizing the storage requirements for the circuit under test (CUT), while retaining the fault coverage information as best as possible. The suggested techniques take advantage of some well-known concepts of conventional switching theory, particularly those of cover table and frequency ordering, as commonly utilized in the minimization of switching functions, in conjunction with a new measure of failure probability in case of stochastic dependence of line errors, besides knowledge of Hamming distance, sequence weights, and derived sequences as previously used by the authors in sequence characterization, in the selection of specific logic gates for merger of an arbitrary number of output bit streams from the CUT. The outputs coming out of the space compactor may eventually be fed into a time compactor to derive the CUT signatures. The developed techniques guarantee good design with high fault coverage for single stuck-line faults, with low CPU simulation time, and acceptable area overhead. Design algorithms are provided in the paper, and the simplicity and ease of their implementations are demonstrated with various examples. In particular, the paper gives results on extensive simulation runs on the ISCAS 85 combinational benchmark circuits with ATALANTA, FSIM, and COMPACTEST programs which confirm the merit of the approaches under conditions of both stochastic independence and dependence of multiple line output errors. A performance comparison of the designed space compactors with conventional linear parity tree space compactors as benchmark is also provided, which demonstrates the enhanced tradeoff for the new circuits in terms of fault coverage and the CUT resources consumed in comparison with the existing design methodologies.

Full Text

Duke Authors

Cited Authors

  • Das, SR; Liang, JY; Petriu, EM; Assaf, MH; Jone, WB; Chakrabarty, K

Published Date

  • February 1, 2002

Published In

Volume / Issue

  • 51 / 1

Start / End Page

  • 150 - 172

International Standard Serial Number (ISSN)

  • 0018-9456

Digital Object Identifier (DOI)

  • 10.1109/19.989919

Citation Source

  • Scopus