A Bist Circuit For Fault Detection Using Pseudo Exhaustive Two Pattern Generator

DOI : 10.17577/IJERTV1IS5228

Download Full-Text PDF Cite this Publication

Text Only Version

A Bist Circuit For Fault Detection Using Pseudo Exhaustive Two Pattern Generator



Department of Electronics & Communication Gyan Ganga Institute of Technology & Sciences.

achieved and the quality of the delivered ICs is

Built-in self test (BIST) has been accepted as an efficient alternative to external testing, since it provides for both test generation and response verification operations, on chip. Pseudo-exhaustive BIST generators provide 100% fault coverage for detectable combinational faults with much fewer test vectors than exhaustive testing. An (n, k) adjacent bit pseudo-exhaustive test set (PETS) is a set of n-bit vectors in which all 2k binary combinations appear to all adjacent k-bit groups of inputs. Pseudoexhaustive testing evolves applying all possible input test patterns to the each output cones to test the functionality of a combinational circuit. It provides high fault coverage of detectable combinational faults with minimum number of test patterns than the conventional exhaustive test pattern generation. In (n,k)-adjacent bit pseudo-exhaustive test sets, all 2k binary combinations appear to all adjacent k-bit of input groups. With recursive pseudoexhaustive generation, all (n,k) adjacent bit pseudoexhaustive test patterns are generated for k n and more than one modules can be tested in parallel. The two pattern test is used to detect sequential faults such as stuck-open faults in CMOS circuits. Delay testing is also used to assure correct circuit operation at regular clock speeds requires two pattern testing. Here pseudoexhaustive two pattern generator is presented and all (n,k) adjacent bit pseudoexhaustive tests are generated for k n recursively.

Keywords: BIT (built-in-test), generic pseudoexhaustive test & recursive pseudoexhaustive test, two pattern generation.

  1. Introduction

    Built-in self test (BIST) techniques add circuitry that allows a chip to test itself. The added circuitry, when activated, takes control, drives the inputs, observes the outputs and reports whether the result is correct. BIST is often used on portions of the circuit that cannot be easily tested using external testing. Furthermore, with BIST at speed testing can be

    greatly increased. BIST is a Design-for-Testability (DFT) technique, because it makes the electrical testing of a chip easier, faster, more efficient, and less costly. BIST is also the solution to the testing of critical circuits that have no direct connections to external pins, such as embedded memories used internally by the devices. BIST employs on-chip test generation and response verification. Advantages of implementing BIST include: 1) low cost of test, 2) better fault coverage, 3) minimal test time.

    BIST pattern generator classified into one-pattern generator and two-pattern generator. One-pattern generator detects the stuck-at faults in the combinational circuits. The two-pattern test is used to detect sequential faults such as stuck-open faults in CMOS circuits. It is to test the circuits at high speeds and also testing for the correct temporal behavior, it is known as delay testing.

    A generic pseudoexhaustive two-pattern generator generates an (n, k) – pseudoexhaustive two-pattern test for any value of k, by enabling an input signal P[k], 1 k n. The generic pseudoexhaustive two- pattern generator can be generalized into progressive two-pattern generator that generates all (n, k) pseudoexhaustive two-pattern test vectors for all values of k. This technique is called as recursive pseudo exhaustive two-pattern generation.

    In recursive pseudoexhaustive testing, (n, k)-PETS are generated for all k= 1,2,3,..,n. By the utilization of an array of XOR gates and binary counter we can recursively generate all (n, k) pseudoexhaustive test patterns for k n in minimal time.

  2. Test Pattern Generation

    In this paper two pattern generators like Generic pseudo exhaustive two pattern generator (GPET) and recursive pseudo exhaustive two pattern generator (RPET) are implemented to generate two pattern tests for modules having different cone sizes.


    The generic pseudo-exhaustive two-pattern generator is presented in Fig. 1. It consists of a generic counter, 1s complement adder, a controller and a carry generator (C_gen). The 7-bit pattern PE [7:1] is given as an input to the controller, generic counter and C_gen and the output A [7:1] is taken from the Accumulator.

    The operation of the GPET varies based on the PE value. If the value PE[4] is enabled, a (7,3)- pseudo- exhaustive test set is generated and a 3-bit exhaustive test set is applied to the 2-bit groups A[3:1] ,A[6:4] , and a single bit test set is generated at A[7].

    The proposed generic pseudo exhaustive two- pattern generator is presented in Fig. 1.

    Fig.1: Generic pseudo exhaustive two patterns Generator

    1. Generic Counter

      The input of the 7-stage generic counter are counter reset (C_reset), 7 bit signal PE[7:1] and counter disable(C_clk_disable).If the signals PE[1] is enabled, then the generic counter operates as an 7- stage binary counter. When PE [4] is enabled, then the generic counter operates as two 3-bit subcounter and a 1-bit subcounter from LSB. Therefore, the generic counter generates all 2k-1 × (2k – 1 – 1) combinations to all groups of k-1 adjacent bits. When the signal C_reset is enabled, the generic counter counts from the initial value. The signal C_clk_disable is used to keep the counter idle. The operation of the generic counter is shown in the table.

      TABLE I


      PE [7:1]

      (n, k)




      (7, 7)



      (7, 1)

      (x) (x) (x) (x)

      (x) (x) (x)


      (7, 2)

      (x) (xx) (xx) (xx)


      (7, 3)

      (x) (xxx) (xxx)


      (7, 4)

      (xxx) (xxxx)


      (7, 5)

      (xx) (xxxxx)


      (7, 6)

      (x) (xxxxxx)

      TABLE II

      PE [7:1]

      Operates as

      In each clock cycle increased



      1×7 stage counter



      7×1 stage counter



      1×1 stage counter + 3×2 stage




      1×1 stage counter + 2×3 stage




      1×3 stage counter + 1×4 stage




      1×2 stage counter +

      1×5 stage counter



      1×1 stage counter + 1×6 stage




    2. Carry Generator

      The C_gen is used to give the Cin input for the adder. The inputs of C_gen module are PE[7:1] and Cout[7:1]. If the signal PE[4] is enabled, the Cout[4] is given as a Cin. Based on the signal PE[7:1] the value of Cin changes.

    3. Control

      The control module is used to determine that a k stage two-pattern test is generated at the k low-order bits of the generator. The input signals of the control module are reset, ACC[7:1], C[7:1], PE[7:3], and generates the signals C_clk_disable, C_reset, A_reset0 and end_k_bit_test. The control logic controls the entire architecture of the pseudoexhaustive pattern generator. The purpose of control logic is to assure that a k-stage two-pattern test is generated at the k low-order stages of the generator. The operation of the control logic is explained in the Fig.5. In a C-like notation, table III.

      Figure. State diagram of control logic

    4. 1s Complement Adder

      The inputs of adder are cin, A[7:1], C[7:1] and its outputs are C_out[7:1], A[7:1]. It consists of 7 full adders, the carry output of the full adders are propagated to the next full adders as carry input. If the value of k is considered to be 3 then the accumulator operates as two 3-stage subaccumulator and one 1-stage accumulator. The carry output of each sub accumulator is given to the carry input of next sub accumulator. If there is any carry in the 3rd

      Phase St

      { int k = 2^k, A = K – 1 do {

      bit then it is added to the lowest order bit of the adder output. It performs one bit addition and output saves


      1 C = 0 ;

      1 2 do {

      3 C++; A = Acc (A, C, K);

      4 } while (C! = K-3);

      5 } while (A! = K-1); 2 6 C++;

      1. do {A = Acc (A, C, K); }

      2. while (A! = K-1);

    2 C = 0;

    1 do {

    2 C++;

    3 3 A = 0;

    4 A = Acc (A, C, K);

    5 } while (A! = K-1);

    6 }

    Int Acc (int A, C, K)

    { return (A + C < K ? A + C : (A + C) % K + 1); }

    Figure. Algorithm for control logic.

    in internal register. For n-stage operation carry is generated by carry generator. The adder gets input from the counter. Cout is given to the carry gen. when the clock signal is enabled adder performs one bit addition. The internal register is capable of storing output of the adder. The adder is reset by reset A signal and the register is also reset by separate reset signal. The input clock signal is disabled the adder remains idle. The operation of adder is shown in table.

    Table: operation of 1s complement adder



    1. RPET

      Recursive pseudoexhaustive two-pattern generator is also having the architecture similar to generic pseudoexhaustive two pattern generator. Additionally it have m = [log27] = 3-stage counter and 3- to- 7 decoder added to generic pseudoexhaustive two- pattern generators architecture. When the two- pattern (n, n)-PET is complete, the recursive

      pseudoexhaustive test is also complete.

      Fig. Recursive pseudo-exhaustive two-pattern generator.

      TableIV Output of RPET

  3. Circuit Under test

    The output from the two pattern test generator is applied to the CUT. In this paper two circuits, Wallace tree multiplier and cryptographic circuit are tested in parallel to increase the speed of the BIST.

      1. 4 bit Wallace tree multiplier

    A Wallace tree multiplier is an efficient hardware implementation of a digital circuit that multiplies two binary values. The 4 bit Wallace tree multiplier is shown in fig.

    The Wallace tree has three steps:

    Multiply each bit of one of the arguments, by each bit of the other, yielding 16 results. Depending on position of the multiplied bits, the wires carry different weights.

    Reduce the number of partial products to two by layers of full and half adders.

    Wallace Tree multiplier

    Group the wires in two numbers, and add them with a conventional adder.



    Comp- arator

    Fig: Proposed Block diagram of BIST


    BIST techniques usually combine a built-in binary pattern generator with circuitry for compressing the corresponding response data produced by the circuit under test. The compressed form of the response data is compared with a known fault-free response.


    BIST plays a vital role in modern VLSI technology. The BIST should occupy less area for compact design of digital circuit. When compared to the results of [4], [5] the test pattern generator proposed in [3] requires fewer hardware to implement. Based on the technique used in [3] a test pattern is generated. The comparison of the hardware overhead is shown in table

    Table 5: comparison of hardware overhead in gates


    Gate Equivalents

    No. of gates When n = 7


    12 x n



    15 x n + 8 x m


    GPET [4]

    16 x n



    18 x n + 8 x m



    7 x n + XOR

    gates + 3 x n

    +8 x m



    7 x n + XOR

    gates + 3 x n

    +8 x m


    Fig: Waveform of n stage counter

    Fig: Waveform of RPET

    Fig : Waveform of decoder

    Fig: Waveform of the generic counter

    Fig: Waveform of the counter

    Fig: Waveform of Adder


    A GPET and RPET based BIST is designed in this paper. Two circuits having different cone size are tested at a time using this BIST circuit. The proposed BIST is synthesized using Xilinx.


  1. Parag K. Lala, An introduction to logic circuit testing, Morgan&Claypool publishers.

  2. M. Abramovici, M. Breuer, and A. Freidman, Digital Systems Testing and Testable Design. New York: Computer Science Press, 1990.

  3. Ioannis Voyiatzis, Dimitris Gizopoulos and Antonis Paschalis, Recursive Pseudo- Exhaustive Two Pattern Generation, IEEE trans. Very Large Scale Integration (VLSI) sys, vol. 18, no. 1, jan 2010.

  4. J. Rajski and J. Tyszer, Recursive pseudoexhaustive test pattern generation, IEEE Trans. Comput., vol. 42, no. 12, pp. 15171521, Dec. 1993.

  5. P. Dasgupta, S. Chattopadhyay, P. P. Chaudhuri, and I. Sengupta, Cellular automata-based recursive pseudo-exhaustive test pattern generation, IEEE Trans. Comput., vol. 50, no. 2, pp. 177185, Feb. 2001.

  6. R. Wadsack, Fault modeling and logic simulation of CMOS and nMOS integrated circuits, Bell Syst. Techn. J., vol. 57, pp. 1449-1474, MayJun. 1978.

  7. C. Chen and S. Gupta, BIST test pattern generators for two-pattern testing-theory and design algorithms, IEEE Trans Comput., vol. 45, no. 3, pp. 257269, Mar. 1996.

  8. Chih-Ang Chen, Efficient BIST TPG Design and Test Set Compaction via Input Reduction, IEEE trans. on CADICS, vol. 17, NO. 8, AUG 1998.

  9. Dong Xiang, A Reconfigurable Scan Architecture with Weighted Scan-Enable Signals for Deterministic BIST, IEEE Trans. On CADICS, Vol. 27, No. 6, Jun 2008.

  10. K. Yang, K.T. Cheng, and L. C. Wang, TranGen: A SAT-based ATPG for path- oriented transition faults, in Proc. ASP- DAC, 2004, pp. 9297.


Please complete and sign the form and send it with the final version of your manuscript. It is required to obtain written conirmation from authors in order to acquire copyrights for papers

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278 – 0181

(ESRSA Publication)

published in the journal so as to index them to various repositories.



The undersigned hereby transfer any and all rights in and to the paper including without limitation all copyrights to the IJERT (ESRSA Publication). The undersigned hereby represents and warrants that the paper is original and that he/she is the author of the paper, except for material that is clearly identified as to its original source, with permission notices from the copyright owners where required. The undersigned represents that he/she has the power and authority to make and execute this assignment.

This agreement is to be signed by at least one of the authors who have obtained the assent of the co-author(s) where applicable.

Author's Signature & Date


Typed or Printed Name


Institution or Company Send to: editor@ijert.org

Leave a Reply