Built-in Self-test Technique for Selective Detection of Neighbourhood Pattern

Sensitive Faults in Memories

Rajeshwar S. Sable1, Ravindra P. Saraf2, Rubin A. Parekhji3 and Arun N. Chandorkar4
1
Tejas Networks Pvt. Ltd. , Bangalore, India. Email: [email protected]
2
Intel Technology India Pvt. Ltd., Bangalore, India. Email: [email protected]
3
Texas Instruments (India) Pvt. Ltd., Bangalore, India. Email: [email protected]
4
Indian Institute of Technology, Mumbai, India. Email: [email protected]

Abstract the neighbourhood size. Traditional March tests are not adequate
Traditional tests for memories are based on conventional for detection of such NPSFs [1,5]. Hence the proposed BIST
fault models, involving the address decoder, individual mechanism for detecting NPSFs is designed to correspondingly
memory cells and a limited coupling between them. The match the faults being considered. The salient features of this
algorithms used in these tests have been successively BIST implementation are: (a) It uses the well-known tiling
augmented to consider stronger coupling conditions. Built-in method and employs a parallel access mechanism to memories
self-test (BIST) solutions for testing memories today to reduce the cycle count. (b) It employs a bit-slice architecture
incorporate hardware for test pattern generation and for the test pattern generator to generate a Eulerian sequence for
application for a variety of these algorithms. This paper covering the cells in the neighbourhood. (c) The BIST
presents a BIST implementation for detection of implementation, based on the proposed address and test pattern
neighbourhood pattern sensitive faults (NPSFs) in random generation schemes, is scaleable for four different NPSF models,
access memories (RAMs). These faults are of different classes (based on distance 1 and 2, and types 1 and 2), for active,
and types. More specifically, active, passive and static faults passive and static faults. This implementation covers stuck-at
for distance 1 and 2 neighbourhoods, of types 1 and 2, are faults, transition faults, inversion coupling faults, idempotent
considered. It is shown how the proposed address generation coupling faults and static coupling faults, besides the NPSFs
and test pattern generation schemes can be made scaleable mentioned above. As complete rows of cells are accessed for
for the given fault type under consideration. read and write operations, this test is better suited for wider
memories. (According to the authors, this is the first time that
Keywords: Built-in self-test for memories, neighbourhood such a BIST implementation for NPSFs is being reported).
pattern sensitive faults, programmable BIST. This paper is organized into six sections. Section 2 provides
an overview of NPSFs, their classes and types, and challenges in
1. Introduction their detection. Section 3 describes the basic BIST technique for
Shrinking feature sizes and increase in the levels of detection for one class of NPSFs, together with its
integration have significantly impacted the design and test of implementation. This implementation is extended in Section 4 to
random access memories (RAMs). While memory cells and include other types of NPSFs. The overall BIST operation is
architectures have become increasingly compact, they are summarised in Section 5. Section 6 concludes the paper.
now also susceptible to increasingly diverse failure
mechanisms. This has rendered the traditional memory test 2. Overview of Neighbourhood Pattern Sensitive Faults
methods inadequate, either in terms of their defect coverage A pattern sensitive fault is a conditional coupling fault in
or in terms of the test application time. Built-in self-test which the content of a memory cell or the ability to change its
(BIST) methods for testing RAMs, based on conventional content is influenced by a certain bit pattern in other cells in the
March tests and their extensions, are becoming popular. These memory [1]. Here the data retention and transition of the victim
tests are easy to implement, have a cycle count complexity cell are affected by a set of aggressor cells. A neighbourhood
which is linear to the number of bits or words addressed, and pattern sensitive fault (NPSF) is a special case of pattern
provide good fault coverage for functional faults and some sensitive faults, wherein the influencing (coupling) cells are in
structural faults, covering the address decoder, individual the neighbourhood of the influenced (coupled) cell. The coupled
memory cells and a limited coupling between them [1]. BIST cell is called the base (or victim) cell and the coupling cells are
also offers other well-known advantages, which will not be called the deleted neighbourhood cells. (The neighbourhood
repeated here [2,3]). Existing BIST implementations for includes all the cells in the deleted neighbourhood as well as the
memories are, however, inadequate for some other fault base cell). Refer to Figure 1. Here the cell V represents the base
models like stronger and widespread coupling faults. Hence, or victim cell, while the cells B, W and C represent the deleted
to ensure the desired defect coverage in a memory core, it is neighbourhood.
necessary to consider these newer fault models and provide a
matching BIST implementation for effective test generation. 2.1. Classification of NPSFs
It is also important to make this implementation Different NPSFs can be grouped based on the nature of
programmable for the desired combination of fault coverage faults in the base cell and on the neighbourhood:
and test time so that BIST can be efficiently used. Active NPSF: The base cell changes its content due to a change
This paper describes a BIST technique for the detection in the deleted neighbourhood pattern. To test these faults, the
of neighbourhood pattern sensitive faults (NPSFs) in random base cell should be read in state 0 and state 1 for all possible
access memories. Although the NPSF model is not new, it is transitions in the deleted neighbourhood.
now becoming important in deep-submicron processes, Passive NPSF: The content of the base cell cannot be changed
especially for DRAMs [4]. Also, the fault model scales with due to a certain neighbourhood pattern. Every base cell has to be

Proceedings of the 17th International Conference on VLSI Design (VLSID’04)

1063-9667/04 $ 20.00 © 2004 IEEE
 written and read for 0 and 1 for all possible combinations of rows in horizontal tiles simultaneously. This method reduces
the deleted neighbourhood pattern for testing these faults. write operations from n*2k to (n/k)*.2k for static NPSFs, and
Static NPSF: The content of the base cell is forced to a from n*k*2k to n*2k operations for active and passive NPSFs
certain state due to a certain deleted neighbourhood pattern. together, where k is the size of neighbourhood and n is the total
For all possible combinations of the deleted neighbourhood number of memory cells [1]. The incomplete tiles as well as the
pattern, the base cell should be read in state 0 and state 1 for overlapping tiles are also completely covered by the test
testing these faults. patterns. This is formally proved in [10].
We now consider two neighbourhoods for NPSFs,
leading to five possible fault models. Refer to Figure 1. 3.1. Address Generation Mechanism
B1 C1 C2 B1 C3 C4 B1 In this implementation, a complete row of cells is accessed
B1 C1

W1
B1

V
C2

W2
B2 C5 C6 B2 C7 C8 C1 B2 C2
from the outputs of sense amplifiers. This enables writes and
W1 V W2 W1 W2 V W3 W4 W1 W2 V W3 W4 W1 W2 V W3 W4

B2 C3 B2 C4 B3 C9 C1 0 B3 C1 1 C1 2 C3 B3 C4
reads to the complete row of the memory cell array. The address
B4 C1 3 C1 4 B4 C1 5 C1 6 B4 generation and data application mechanism is shown in Figure 2.
(a) D 1 T 1 (b) D 1 T 2 (c) D 2 T 1 (d) D 2 T 2 (e) D 2 RT 2 Since there is only one transition between two consecutive
V= Vict im cell B1 -B4 = Bit lin e N eigh bo urh o o d cells W 1 -W 4 = W o rdlin e N eigh bo urh o o d cells C1 -C1 6 = Co rn er cells
patterns, the data in only one of the three rows of a tile changes.
Figure 1. NPSF models for BIST implementation. Hence a counter is used for generating the row address, such that
D1T1: Neighbourhood of Distance 1 and Type 1. The the next state is obtained by incrementing the present state by
neighbourhood includes five cells, namely the base cell and three. Two consecutive data patterns are compared and the
four cells physically adjacent to it. (Figure 1(a)). comparator output is used to derive the initial state of the
D1T2: Neighbourhood of Distance 1 and Type 2. Here eight counter through the combinational logic. Depending upon the
cells physically adjacent to the base cell are considered, to row of a tile in which the pattern changes, the initial state of the
have a neighbourhood with a total of nine cells. (Figure 1(b)). counter can either be zero, one or two. The counter then
D2T1: Neighbourhood of Distance 2 and Type 1. The generates the next set of addresses, three rows apart, until it
neighbourhood includes nine cells, namely the base cell and overflows.
eight cells physically adjacent to it. (Figure 1(c)). 0 1 2 0 1 2
D2T2: Neighbourhood of Distance 2 and Type 2. Here 3 4 5 C o m p a r a to r 3 4 5

twenty-four cells physically adjacent to the base cell are 6 7 8 6 7 8

P r e v io u s d a ta p a tte r n N e x t d a ta p a tte r n
considered, to have a neighbourhood with a total of twenty-
five cells. (Figure 1(d)). C o m b in a tio n a l lo g ic
fo r s e ttin g in itia l

D2RT2: Neighbourbood of Distance 2 and Reduced Type 2. c o n d itio n o f c o u n te r

The D2T2 model is reduced to consider only twelve C o u n te r fo r

a d d r e s s g e n e r a tio n
physically adjacent cells, to have a neighbourhood with a total
of thirteen cells. (This may also be termed as neighbourhood A d d r e s s to
m e m o r y u n d e r te s t
of Distance 2 and Extended Type 1 – D2ET1. Refer to Figure Figure 2. Address generation mechanism.
1(e)). The same pattern sequence is applied to every tile. Hence
From a proximity point of view, the D2T1 all the cells in a particular row for each horizontal tile can be
neighbourhood is not considered in this paper. compared together. In the fault free condition, all the
corresponding cells have the same data. Dissimilar data
2.2. Detection of NPSFs indicates an error. The number of cycles required for this test is
Some attempts have been reported in the literature to 4609*r read cycles and 4609*r/3 write cycles, i.e. a total of
supplement traditional March tests. Instead of only the all (4/3)*r*4609, where r is the number of rows in a memory cell
zeros and all ones background patterns, the modified March array. For a RAM with multiple array architecture, this test can
tests proposed in [6] use multiple data background patterns be applied in parallel to all arrays. Hence a larger memory can
and have test lengths of either 96.n and 100.n for type 1 be tested in the same number of test cycles as required for a
neighbourhood, (where n is the number of bits addressed). single array. The total number of test patterns required is 4609
This number increases for the type 2 neighbourhood. The for a 3x3 tile and the total number of cycles required is 198187
technique of parallel testing, proposed in [7] uses a restricted for a 32x32 bit memory.
type 2 neighbourhood that divides the eight cells of distance 1
neighbourhood into three groups based on their location, i.e. 3.2. Test Pattern Generation Mechanism
horizontal, vertical and diagonal neighbours. All the cells For detecting all possible NPSFs, a 0o1 and 1o0
across groups are read and written simultaneously. The test transition must be generated for the each deleted neighbourhood
length is reduced; however, a lesser number of NPSFs are cell in each tile for all possible patterns of other cells including
covered as a result of this cell grouping. The row March the base cell in the deleted neighbourhood. An efficient set of
algorithm in [8] has high coverage of conventional faults, but, test patterns can be created by having only one transition in the
additionally, only S-NPSFs are covered. Pseudorandom tests neighbourhood between two successive patterns. Such a set can
[9] typically have a huge complexity for an acceptably low be generated by using a Eulerian sequence [1]. A Eulerian
escape probability. sequence is a walk over a Eulerian graph, (i.e. a graph in which
nodes correspond to individual bit patterns, and there exists a
3. BIST Implementation for NPSFs bidirectional edge between any two nodes with Hamming
We first illustrate the BIST implementation for the D1T2 distance of one), which traverses each arc (in each direction)
neighbouhood. The memory bitmap is covered using the tiling exactly once. The length of a k-bit Eulerian sequence is (k*2k)+1
method [1,7] in which a memory is completely covered by [1]. In this implementation, a 9-bit Eulerian sequence is required
tiles of 3x3 cells, and the test patterns are applied to all the

Proceedings of the 17th International Conference on VLSI Design (VLSID’04)

1063-9667/04 $ 20.00 © 2004 IEEE
 for the nine cells in a 3x3 tile and hence the number of test one or more rotate operations must be performed for the desired
patterns is 4609. test pattern, the control circuit provides an equal number of
The implementation of a deterministic test pattern successive rot_clk signals to rotate the contents of shift register.
generation (TPG) unit is described in Section 3.3. The
proposed unit generates the 9-bit Eulerian sequence by
implementing Hay’s algorithm [1]. A part of this sequence is
presented in Table 1 and is constructed by reading the
contents of the first pattern column, (shown by arrow),
followed by the second pattern column and so on. (X, G and T
denote the pattern (in G), the Gray code group and the
transformation, respectively). The first column of 512 patterns
is generated using a 9-bit Gray counter. This column, by
exploiting the above algorithm, can generate the patterns in Figure 4. Rotate and output circuit.
the other columns. The patterns in the next column are The output of the Gray counter is directly fed to the output
generated from those in the present column by performing register to generate the first column of patterns. For the second
one bit right shift followed by inversion of Most and Least column, the output of the Gray counter is loaded into the shift
Significant Bits (MSB, LSB). register and shifted out by one bit before being sent to the output
Table 1. Nine bit Eulerian sequence register under the control of rot_clk, rotate and mux_ctl signals.
The patterns for the rest of the columns are similarly generated.

3.3.2. Control Circuit

The 9-bit status register with its LSB input permanently
connected to logic 1, holds the rotation status of the TPG,
indicating the number of rotate operations that must be applied
to every pattern generated by the Gray counter according to the
progress of the test pattern generation process. The number of
bits inside the status register with value 1 indicates the number
of rotate operations that must be performed on shift register.
Thus the state 000000000 in the status register means no rotate
operation, while states 000000001, 000000011, …, 011111111
mean one, two, …, and eight rotate operations, respectively. The
MSB of the status register going to 1 indicates the completion of
the test pattern generation process, and pat_end signal is
activated. The status register is shifted out by signal up_clk each
time the Gray counter returns to its initial state, i.e. 000000000.
Figure 3. Test pattern generator. The 8-bit step register is used to generate the appropriate
3.3. Implementation of Test Pattern Generator number of successive rot_clk signals for right shift of each
The block diagram of proposed TPG unit is shown in pattern generated by the Gray counter based on the current status
Figure 3. The unit consists of a 9-bit Gray counter, 9-bit of the TPG. The pat_en signal initiates the shift process under
parallel input/output right shift register, control circuit, and the control of clk signal. In each step of the shift operation inside
output register. The unit has three input signals, namely the step register, when a 1 is encountered from the LSB to the
pat_en (pattern enable), clk (clock) and reset. It has two MSB, the rot_clk signal is activated depending upon the
output signals; pat_out (pattern output) which gives the 9-bit contents of the status register, using the And-Or array shown in
pattern and pat_end (end pattern) which indicates the Figure 5.
termination of the pattern generation process. A BIST
controller controls the testing process. The BIST controller
uses pat_en to send a request to the TPG to provide the next
test pattern of the Eulerian sequence. This pattern is used for
the subsequent test data write operation to the memory array.
The BIST controller uses reset during the initialization phase
of the testing process in order to reset the internal counter and
registers of the TPG unit. The operation of each block of the
TPG unit is explained below.

3.3.1. Rotate and Output Circuit Figure 5. Control circuit.

The rotate and output circuit is shown in Figure 4. The 4. BIST Implementation for Selective NPSFs
Gray counter provides 512 sequential patterns of the second The implementation described in Section 3 can be extended
column of Table 1 under the control of pat_en signal. Every to generate another Eulerian sequence with a different number
pat_en signal enables the counter to count up in order to of bits. This scaleability is exploited to generate sequences for 5-
provide a new pattern. When the final pattern of the sequence bits, 13-bits and 25-bits to additionally target D1T1, D2RT2 and
has been reached, i.e. 100000000, the counter restarts. These D2T2 faults, respectively. The block diagram for the complete
patterns are sent either to the output register or loaded into the BIST implementation, incorporating the address generator, test
shift register under the control of pat_en and up_clk signals. If pattern generator and test response evaluator, is shown in Figure

Proceedings of the 17th International Conference on VLSI Design (VLSID’04)

1063-9667/04 $ 20.00 © 2004 IEEE
 6. Note that the select input line to the BIST controller must
be set to target the specific fault model. As an illustration, the number of test patterns and clock
cycles required to test a 32x32 memory for various NPSF
The mechanism for D1T2 fault detection can be extended models is given in Table 2. It can be seen from the above table
to detect D1T1 and D2T2 faults. The mechanism for D2T2 that the proposed BIST implementation is amenable for large
fault detection can further be extended to detect D2RT2 word length, i.e. wide memories. BIST provides a convenient
faults. Generic extensions include changing the value of k=n, mechanism for off-line testing, wherein the tester infrastructure
for an n-bit Eulerian sequence, and correspondingly changing is not dedicated to the device under test. Under this condition,
the number of D flipflops in the rotate and output circuit. Also test times constraints can be relaxed. Also, in several cases, it
the width of the status and step registers will change, together may be adequate to detect D2RT2 faults as against D2T2 faults,
with the size of the And-Or array in the control circuit. Based effectively reducing the test time by a factor over one thousand.
on the tiling method, the rows are changed and the address
incremented. (Additional details can be found in [12]. These 6. Conclusion
are not included here for lack of space). This paper describes a new BIST methodology for the
detection of neighbourhood pattern sensitive faults in random
Tes t s tart
Clock
Test respons e
Tes t end
access memories. The highlights of this technique include (a) a
BIST controller evaluator
Select0
Select1
bit-slice BIST implementation which is scaleable both for
Control s ignals implementation and test application depending upon the faults of
Addres s and data Address and data Memory under
interest, (b) low cost implementation of the address generator
generator multiplexer test and test pattern generator, and (c) ability to detect distance 1 and
System write data lines
2 faults of types 1 and 2. This programmability is important
Sys tem addres s lines Sys tem read data lines since NPSF detection is costly in terms of the number of cycles.
Figure 6. Block diagram for BIST implementation. Future work in this direction includes the definition of a
5. BIST Operation programmable architecture for memory BIST to encompass
A generic algorithm for BIST operation has been traditional March tests with NPSF tests, optimizations in the test
developed. It supports a scaleable BIST implementation for pattern generation logic, and optimizations in the address
the detection of D1T1, D1T2, D2T2 and D2RT2 faults. (More generation logic for large memories.
details on the algorithm can be found in [12]. These details
are again not included here for lack of space). Note: This work was done when the first two authors were
students at Indian Institute of Technology, Mumbai, India.
The BIST implementation proposed in Section 3 for
D1T2 faults has been realized in VHDL and simulated [11]. References
The approximate gate count for this implementation 1. A.J.Van De Goor, Testing of Semiconductor Memories:
Theory and Practice, ComTex Publishing, The
consisting of the next address generation logic and test pattern Netherlands, 1999.
(Eulerian sequence) generation logic is about 900 gates. This 2. P.H.Bardell, W.H.McAnney and J.Savir, Built-in Test for
number does not include the logic in the BIST controller, VLSI:Pseudorandom Techniques, John Wiley& Sons, 1987.
generic portions of the address generator and test response 3. C.E.Stroud, A Designer’s Guide to Built-In Self-Test,
Kluwer Academic Publishers, 2002.
evaluator. The latter are not considered as an additional 4. B.F.Cockburn, “Tutorial on DRAM Fault Modeling and
overhead, since they are necessary for any BIST operation. Test Pattern Design”, Proc. Intl. Workshop on Memory
The number of comparators for test response evaluation will Technology, Design and Testing, 1998, pp. 66.
depend on the memory word size, and this logic is also not 5. R.Dekker et al., “A Realistic Fault Model and Test
Algorithm for SRAMs”, IEEE Trans. on CAD, 1990,
included. Simulation has been performed to confirm the pp.567-572.
suitability of this implementation [11]. We now make three 6. K-L.Cheng, et. al., “Efficient Neighbourhood Pattern
observations: Sensitive Fault Test Algorithms for Semiconductor
(a) The logic overhead in the proposed BIST implementation Memories”, Proc. VLSI Test Symposium, 2001, pp.225-
230.
is notably low. This is due to the algorithmic nature of the test 7. P.Mazumder, “An Efficient Built-in Self Test for RAMs”,
pattern generator and address generator. Proc. Intl. Test Conference, 1987, pp.1072-1077.
(b) While the gate count is low, it can be seen that the cycle 8. M.Franklin and K.K.Saluja, “Testing Reconfigured RAMs
count for the full BIST operation is notably high. This and Scrambled Address RAMs for Pattern Sensitive
Faults”, IEEE Trans. on CAD, 1996, pp. 1081-1087.
highlights the fact that BIST for NPSFs is relatively costly in 9. R.David et. al., “Random Pattern Testing Versus
terms of the test cycles as against the extra test logic. Deterministic Testing of RAMs”, IEEE Trans. on
(c) The implementation scales almost linearly to the number Computers, 1989, pp. 637-649.
of bits in the neighbourhood, due to the bit-slice (scaleable) 10. R.P.Saraf, An Architecture for Programmable Memory
BIST, M.Tech. Dissertation, Indian Institute of Technology,
architecture used in this technique. Mumbai, 2002.
Table 2. Cycle count for NPSF detection for different fault 11. R.S.Sable, Memory Testing: BIST and Iddq Test
models Techniques, M.Tech. Dissertation, Indian Institute of
Fault Number of Number of Number of Approximate test Technology, Mumbai, 2003.
model test patterns write cycles read cycles time 12. R.S.Sable, R.P.Saraf, R.A.Parekhji and A.N.Chandorkar,
@100 @500 “Built-in Self-test Technique for Selective Detection of
MHz MHz
D1T1 161 5313 15456 0.208ms 0.042ms
Neighbourhood Pattern Sensitive Faults in Memories”,
D1T2 4609 50699 147488 2ms 0.4ms Internal communication, 2003.
D2RT2 106497 3727395 17039520 200ms 40ms
D2T2 838860801 5872025607 26843545632 330s 66s

Proceedings of the 17th International Conference on VLSI Design (VLSID’04)

1063-9667/04 $ 20.00 © 2004 IEEE