Detection of Pattern-Sensitive Faults in RAM by Use of M-Sequencers

This invention is related to the fault detection of IC memories by use of M-sequences. According to the recent development of data processing devices and information related devices, the demand for IC memories is greatly increasing. Among them, random-access-memories(RAM), in which the content is read or written arbitrarily, are becoming major memories by the use of integration technology; RAM with 4M bits per chip is now widely used and 16M bits per chip RAM is expected to appear in the near future. In this way, when the integration of RAM becomes of high density, the detection of faults of RAM becomes an important technology in the course of manufacturing and checking processes of IC memories. Among various faults of RAM, the so called pattern sensitive faults (PSF) are usually difficult to detect because the PSF are the faults in which the content of the memory cell is affected by the influence of the neighboring cells. In order to detect PSF, there is much time and labor and an easy and simple method for detection of PSF has not yet been found. This invention offers an effective method for the detection of PSF by use of M-sequences, known as one of the pseudorandom sequences.

Before the explanation of the invention, let's explain a little bit about the M-sequence.

M-sequence, which is the abbreviation of maximum length sequence, is defined as the sequence {a.sub.i } which is generated by a shift register circuit with a certain feedback as shown in FIG. 3. The M-sequence can be generated from the equation a.sub.i+n. Although there exists a multi-level M-sequence, the M-sequence, widely used is of two-levels having either 0 or 1; in FIG. 3, h.sub.i =0 or 1 and a.sub.i =0 or 1. We consider hereafter only the two-level M-sequence unless otherwise stated. M-sequence has the following properties:

(1) The period is 2.sup.n -1 (n=1,2, . . . ), where n is the number of the stages of the shift register.

(2) Every possible n-tuple except all zero appears exactly once in a period. That is, when we take an n-tuple (a.sub.i, a.sub.i+1, . . . a.sub.i+n-1)(i=0,1, . . . ,2.sup.n -2), every possible n-tuple except an all zero pattern appears once and only once in a period. So when the content of the n-tuple is considered to be a binary number, all integers except zero from 1 to 2.sup.n -1 appear once in a period.

(3) In a period 2.sup.n -1, there are 2.sup.n-1 -1 zeros and 2.sup.n-1 ones. That is, the number of ones and zeros in a period is nearly equal. This invention uses the property (1) and (2) together with the two dimensional property of M-sequence when the M-sequence is arranged in two dimensional fashion.

Now, the outline of the detection method of pattern-sensitive-faults is described. FIG. 1 shows a two-dimensional array of a memory where B denotes the cell under consideration (called base cell). The neighboring cells are denoted as N,S,W,E. The pattern-sensitive-fault is such a fault as the content of cell B, originally supposed to be 0 (or 1), changes to 1 (or 0) when the content of NSWE is, say 1110. In order to detect PSF, it is necessary to check if the content of B is changed for all 16 patterns of neighboring cells NSWE from 0000 to 1111. Various researchers have tried to find some method for PSF detection as to what kind of sequences should be used and how the sequence are used for writing each memory cell effectively. However, those previous methods are very complicated from the point of view of algorithm and are not suited for built in test. This invention covers those defects by use of pseudorandom M-sequence.

This invention proposes three methods for PSF detecting by use of M-sequences. The summary is as follows. Here M.sub.j denotes the M-sequence of fourth or fifth order starting from a.sub.j ; M.sub.j ={a.sub.j, a.sub.j+1, . . . }.

Method (a)

At first the entire memory array is cleared. It is then read and checked if it is cleared. Then, fill the first row of the memory array with M.sub.0 of the fifth order M-sequence, the second row with M.sub.L, and the third row with M.sub.2L and so on. The delay L between the rows is theoretically determined beforehand in order for all the patterns from 0000 to 1111 to appear in the neighboring cells (Here the neighboring cells are defined as four neighboring cells around a base cell; up and down, left and right). Then the content of each cell is read and checked for the correct content. The procedure up to this point is called one phase. After this is over, the input sequence to the memory array M.sub.O, M.sub.L, M.sub.2L and so on are shifted one bit to the left and repeat the procedure until all the 31 phases are over. Thus the PSF in RAM are completely checked.

Method (b)

At first, clear the entire memory array, read the memory array and then check if it is cleared. The memory cells are tiled into group A and group B in order for adjacent neighboring cells to be in A and B. At first, write 1 into B cells and read B cells for 1. Then write the fourth order M-sequence M.sub.O, M.sub.L, M.sub.2L, and so on into A cells of each row with appropriate lag L between the consecutive rows in order for all patterns from 0000 to 1111 to appear in the neighboring cells. Then B cells are read and checked if they are 1. Shift the row sequence one bit to the left and repeat the procedure until all the 31 phases are over. Next, write 0 into B cells and repeat the procedure. And change the roles of A and B and repeat the procedure. Thus the PSF in RAM are completely checked.

Method (c)

At first, clear the entire memory array, read the memory array and then check if it is cleared. The memory cells are tiled into group A and group B. Write 1 into B cells of both even and odd rows. Write the fourth order M-sequence M.sub.E into A cells of even rows and M.sub.O into A cells of the odd rows. The lag between the sequence M.sub.E and M.sub.O is theoretically chosen beforehand in order for all the patterns from 0000 to 1111 appear in the four neighboring cells around a base cell. Then read B cells and check them for 1. Shift the M.sub.E and M.sub.O one bit to the left and repeat the procedure until all the fifteen patterns are over. Write 0 into B cells and repeat the procedure. And change the roles of A and B cells and repeat the procedure. Thus the PSF in RAM are completely checked.

FIG. 1 shows the state of a memory which is the object of a test by a first method of the present invention and is composed of a base cell B and four neighboring cells NSWE.

FIG. 2 shows the state of a memory which is the object of a test by second and third methods of the present invention, in which each A cell is in the neighborhood of each B cell and vice-versa.

FIG. 3 shows a block diagram for generation of the M-sequence.

FIG. 4 is a flow chart diagram of one embodiment of the method of the present invention.

FIG. 5 is a flow chart diagram of another embodiment of the method of the present invention.

FIG. 6 is a flow chart diagram of another embodiment of the method of the present invention.

The three methods described in the summary of the invention are explained individually.

The method (a) is the PSF detection method using 5th order M-sequence. As denoted in FIG. 1, all the patterns appearing in NWBES are 2.sup.5 patterns from 00000 to 11111. Therefore the sequence to be input to memories must have the period of at least 2.sup.5. But when the memory cells are cleared at first and then checked for 0 before we start the procedure, the sequence having the period of 2.sup.5 -1 is sufficient. The M-sequence of fifth order is the right sequence suitable for this purpose. The lag between row sequences must be determined beforehand in order for all the patterns to appear in the neighboring cells NWSE. How to select this lag is one of the most important points of this invention. Let the fifth order M-sequence be M.sub.0.

When this sequence M.sub.0 is written into the first row of the memory array, the sequence written in the second row is the L bit delayed version M.sub.L as follows:

Then the sequence written in the third row is

Then the test procedure is as follows with reference to FIG. 4:

(1) Clear the entire memory arrays in step 4A.

(2) Read the memory cells in step 4B and check if they are cleared in step 4C.

(3) Fill the first row with sequence M.sub.O, the second row with M.sub.L, the third row with M.sub.2L and so on in step 4D.

(4) Read and check if the written message exists in step 4F.

(5) (3) and (4) together represent one phase. Now shift M.sub.O, M.sub.L, M.sub.2L . . . one bit to the left in step 4G and repeat steps (3) and (4) till all the 31 phases are over in step 4H.

Determining the theoretical delay L between rose so that all patterns from 0000 to 1111 appear in neighboring cells around the base cell, as shown in step 4E, will now be described. Now suppose the base cell under test is the (i+1)th position of the memory array. Then the four neighboring cells in NWBES are written as follows. ##EQU1##

When we use such a delay operator X as X.sub.i which represent m.sub.i, then the generalized pattern of NWBES would be of the form: ##EQU2##

Note that the powers of X are taken modulo period length of the sequence. In order for all the pattern to appear in array (4), every term in (4) must be linearly independent. As we supposed earlier, the memory array is first cleared and checked for zero. So all the patterns of 2.sup.5 -1 must appear in (4). If there exist any linear dependence between any terms in (4), we cannot have all the patterns. This is obvious if we consider the following example. Suppose there exist the linear relation.

Then if X.sup.i =1 and X.sup.i+1 =1, X.sup.i+2l must be zero. So the pattern X.sup.i =X.sup.i+l =X.sup.i+2 =1 cannot appear at all. In order for every term in (4) is linearly independent, the following conditions must be satisfied.

Condition 1: For a chosen lag, two or more terms should not have the same power; otherwise, in any phase, the same elements appear in those cells and consequently all the required patterns are not generated.

Condition 2: No term can be expressed as a linear combination of two or more of the remaining terms. If any term is expressed as a linear combination of other terms, they are linearly dependent. In order to check this condition, we form set S of polynomials taking three or more terms in array (4) at a time. ##EQU3## where each element of set S is taken for i=0, since the linear independence among terms of array (4) has no relation to i. Now let p(x) be the characteristic polynomial of the M-sequence. Then let us check equation(6) for linear independence. If any term of S modulo P(X) is equal to zero, where P(X) is the characteristic polynomial of the M-sequence, then the terms are linear dependent. Hence for linearly independence, we check

In Table 1, the results of search for lags which satisfy the condition 1 and 2 are shown, where *A denotes the case where all the pattern exist, and *B denotes the case of linear dependence. s denotes the case where all the pattern exist, t denotes the case where same elements appear in (4), and q denotes the case where condition 2 is not satisfied. From Table 1, we see the usable lags for the existence of linear independence between NWBES are 2,3,7,9,11,12,15,16,19,20,22,24,28, and 29.

The method (b) uses M-sequence of fourth order. In method (a), the test sequence is written into NWBES cells of a memory array in each phase. Hence during read and check operation of each phase, it is necessary to regenerate the test sequence for a compare operation. This is rather tedious work. The method (b) is a method to avoid this. In method (b), we fix the contents of the base cell B to 1 or 0 and use the fourth order M-sequence to create all patterns in the neighboring NEWS. The memory array here is tiled into group A and group B as shown in FIG. 2. The test procedure is as follows:

(1) Clear the entire memory array in step 5a.

(2) Read and check if the memory cells are cleared in steps 5B and 5C.

(2a) tiling memory cells into groups A and B in step 5D.

(3) Write a 1 into base cells (B cells) in step 5E.

(4) Read B cells and check them for a 1 in step F.

(5) Write the chosen test sequence M.sub.O into A cells in the first row, M.sub.L in the second row, M.sub.2L in the third row and so on in step 5G. The lag L between rows is theoretically determined beforehand.

(6) Read B cells and check them for a 1 in step 5H.

(7) Shift the row sequences one bit to the left in step 5I and repeat the steps (5) and (6) in step 5J till all the test patterns are covered.

(8) Write 0 into B cells and repeat step (4)-(7) in step 5K, but this time read B cells for a 0 in all read operations.

(9) Change the roles of A and B cells and repeat the step (3)-(8) in step 5L.

In steps in (3)-(8), 1's are written into B cells first, and then 0's are used. But, of course, we can also use 0's first and then 1's. For any base cells, the possible generalized pattern are: ##EQU4##

As in array (5), we form a set S as follows:

For array (7),

For array (8),

As in method (a), the conditions 1 and 2 are checked for linear independence, and we get the results as shown in Table 2.

Here we see that the usable lags in this case are 6,7,8,9. In methods (a) and (b), it was necessary to apply appropriate lag L between consecutive rows to obtain a complete test pattern. In practice, the row length is of the form 8,16, 32, . . .

Therefore, when we use the fourth order M-sequence (N=15) and write it continuously into consecutive rows, we have automatic lag 1,2,4,8 depending on the row length 16,32,64,128. So if we take advantage of this fact, we don't have to apply artificial lag between each row, which leads to method (c). In method (c), the memory cells are tiled as shown in FIG. 2 as in the method (b). Let E-array be the array of even rows and O-array be the arrays of odd rows. Then, the fourth order test sequence M.sub.E for the E-array and M.sub.0 for the O-array are formed.

where k is the lag between M.sub.E and M.sub.O. The test procedure is as follows.

(1) Clear the entire memory array in step 6A.

(2) Read and check if the memory cells are cleared in steps 6B and 6C.

(2a) tiling memory groups into groups A and B in step 6D.

(3) Write a 1 into base cells (B cells) of both E-array and O-array in step 6E.

(4) Read B cells of both arrays for a 1.

(5) Write M.sub.E sequentially into A cells of E-array in step 6F and M.sub.O sequentially into A cells of O-array in step 6G.

(6) Read B cells of both arrays in step 6H and check for a 1 in step 6I.

(7) Advance the sequence M.sub.E and M.sub.O by one bit in step 6J and repeat steps (5) and (6) till all the fifteen patterns are over in step 6K.

(8) Write a 0 into B cells in step 6L and repeat steps (4)-(6) and (7) in step 6M, but this time read B cells for a 0.

(9) Change the roles of A and B cells in step 6N and repeat steps (3)-(8) in step 6O.

Now the problem is how to select the lag k in order for all the patterns to appear in the neighboring cells.

When the base cell is taken in A cells, the sequence of B cells are represented in the generalized pattern as; ##EQU5##

When the base cell is taken in B cells, the sequence of A cells are represented in generalized pattern as; ##EQU6##

Now, we form set S as in method(a) and (b).

For array (11)

For array (12)

As in methods (a) and (b), conditions 1 and 2 are checked for linear independence. The results are shown in Table 3-1.

As is seen from Table 3-1, the lag k between even rows and odd rows should be taken to be 11, since when k=11 the neighboring cells are linearly independent for all L, the automatic lag between even rows and odd rows. In the same way, we form set S for arrays (13) and (14). For arrays (13),

For array (14),

The results of checking conditions 1 and 2 for arrays (17) and (18) are shown in Table 3-2.

In this case, k should be taken to be 10 since the neighboring cells are linearly independent for all L. The M-sequence has the property that it is very easy to generate and, in addition, it has uniformly distributed patterns. Taking advantage of this property and using a suitably chosen value of lag between memory rows, it is possible to generate all the patterns in the neighboring cells around any cell. And this can be done during the same number of phases as the period of M-sequence. In other words, it is possible to generate the ideal patterns in the neighboring cells around any base cell, in the sense that the patterns appearing in the neighboring cells around any cell in one phase are all different and the patterns appearing in the neighboring cells around a specified cell is all different in every phase; there are no redundancy. Therefore, this method provides a very simple, efficient and epoch-making method for pattern sensitive fault detection of RAM.