A finite-field algebraic description of a built-in self-test (BIST) design based on primitive feedback shift registers (LFSRs) implementing the test generator and the signature analyzer (SA) is presented. That the BIST schemes that use the TG and the SA with the same feedback polynomial detect errors which distort the output functions of the circuits-under-test for a set of the input vectors forming a coset of a subspace. The authors term this type of error the 'single coset error'. Signature schemes which detect the coset errors of multiplicity r are further described, (r>

An analysis and design of a pseudorandom pattern generator, (PRPG), based on a linear recurrence, for built-in self-test (BIST) boundary scan design is presented. The authors present for the case when r>or=s, a design of an s-stage PRPG capable of producing 2/sup s/-1 distinct r-bit patterns within 2/sup s/-1 clock pulses independent of the hardware realization of the PRPG. For the case when r>

A compression of test responses technique for a built-in self-test (BIST) VLSI design is presented. The authors introduce the notion of a robust compression technique which incorporates prior knowledge of the statistics of fault-free responses under pseudorandom testing to achieve a guaranteed error detectability independent of a distribution of errors. The presented robust quadratic compressor requires two r-bit registers (r-bit signature) more than a multiple-input linear feedback shift register; however, it provides for equal protection against all error patterns. Therefore, quadratic compressors are optimal and robust with respect to a statistics of errors in a device under test.>

Nonlinear quadratic codes that are optimal for the minimax error detection are presented. Characteristic functions for these codes are asymptotically bent. For a given block size n and the number of codewords mod C mod , these codes minimize max Q(e), e not=0, where Q(e) is the conditional error-masking probability, given the error pattern e. The codewords are blocks of n symbols from GF(q). Encoding and decoding procedures for the codes are described.>

Board-level diagnostic techniques by signature analysis based on single-error-correcting Hamming codes over GF(2/sup M/) (where M is the number of outputs per chip) are presented. Two techniques are considered: the space-time compressor technique for the case when responses from N chips on the board are wired to the compressor; and the time compressor technique for the case when test responses from each chip are transferred to the compressor via system bus. Assuming a single-faulty-chip model, a faulty chip on the board under test is located by an analysis of the relationship between the distortions in the obtained signatures. Both techniques for board-level diagnosis require less hardware than the straightforward diagnostic techniques using a built-in signature analyzer for every chip or selective testing of each chip via the system bus, hence offering an efficient approach for a design of a built-in-self-test board for for manufacturing testing.>