CA2129390C - Method and apparatus for testing electronic memories for the presence of multiple cell coupling faults - Google Patents

Abstract

A method of testing a random access memory (RAM) for single V-coupling faults by establishing a first current value for each cell, for each cell and for each of m data backgrounds, generating a data bit corresponding to an element of an (n, V - 1)-exhaustive matrix, and for each of m data backgrounds:
(1) applying a read write sequence to each cell; and (2) for each background except the mth background, updating the current value of all cells according to the data bits corresponding to that cell; reading each cell of the RAM; and discarding or repairing the RAM
if a cell coupling fault is apparent from the series of values read from the cells of the RAM. Data bits are generated by a matrix reconstruction method or a pseudo-random generator using a hashing of the address of the cell to which the data bit is to be applied.
The logical function may be the element of the (n, V -1)-exhaustive matrix irrespective of the current of the cell or an exclusive-or of the complement of the background code logic bit and the first current value of the cell. Apparatus for testing a random access memory (RAM) has a PROM containing background code logic bits corresponding to an (n0, V - 1)-exhaustive matrix where n0 n, the matrix having n0 rows and m0 columns; and a data bit generator for generating data bits from the matrix stored in the PROM. A built in apparatus for testing a random access memory (RAM) having n cells includes a data bit generator that generates pseudo-random data bits from a hashing of the address of the RAM cell to which the data bit is to be applied.

Description

2 12 ~3 ~ e~ ~

TITLE OF THE INVENTION:
Method and Apparatus for Testing Electronic Memories for the Presence of Multiple Cell Coupling Faults NAME OF INVENTOR:
Bruce F. Cockburn FIELD OF THE INVENTION
This invention relates to methods and apparatus for testing electronic memories.

~CKGROUND OF THE INVENTION
Electronic memories suffer several types of faults when data is written to them. Testing for these faults is very difficult, and particularly poses a problem when it is desired to build testing capability into the electronic memory itself.
A very general fault type that can model most of the reported erroneous interactions involving V 2 2 arbitrary RAM storage cells is the single V-coupling fault defined by Nair, Thatte, and Abraham ~"Efficient Algorithms for Testing Semiconductor Random-Access Memories," IEEE Trans. on Comp., v.
C-27, no. 6, pp. 572-576, June 1978). Nair, Thatte, and Abraham defined the single V-coupling fault to represent the situation when V > 2 cells, say cells i1,...,iv, interact erroneously as follows: if cells i1,...,iv contain V particular values b1,...,bV and if cell i1 is written to -b1, then the contents of both cells i1 and i2 are changed. A particular case, the 5-coupling fault, can be used to model active neighborhood pattern-sensitive faults (ANPSFs) as defined by Suk and Reddy ("Test Procedures for a Class - 2~2939û

of Pattern-Sensitive Faults in Semiconductor Random-Access Memories," IEEE Trans. on Comp., v.
C-29, no. 6, pp. 419-429, June 1980); this follows because every ANPSF is also a 5-coupling fault.
Testing for 5-coupling faults is in fact equivalent to testing for ANPSFs when there is no knowledge of the mapping from logical cell addresses to physical cell locations.
Efficient tests for detecting ANPSFs, such as Suk and Reddy's TANPSF1, presuppose knowledge of the address mapping. However, the mapping is often not readily available due to vendor secrecy and unannounced layout changes. A further complication is that the widespread use of redundant rows and/or columns to repair defective RAMs disturbs the address mapping in different ways for each RAM die. Indeed, in RAMs with multiple sub-arrays, the address mapping is likely to be different in each sub-array. Testing for V-coupling faults avoids the address mapping problem altogether because the fault model is independent of the physical arrangement of the cells.
In addition, RAMs are often embedded in larger integrated circuits (ICs) such as microprocessors and digital communications ICs; this practice can cause problems at test time because access to the RAM inputs and outputs for testing purposes is often difficult or impractical. RAMs provided with built-in self-test (BIST) such as the design proposed by Dekker et al (R. Dekker, F.
Beenker, and L. Thijssen, "A Realistic Self-Test Machine for Static Random Access Memories," Proc. 1988 Int. Test Conf., Sept.12-14,1988, pp. 353-361, Wash-ington, DC, U.S.A., (IEEE Comp. Soc.)), tackle this problem by avoiding the necessity of routing test data to and from the RAM through intervening logic. A
second RAM testing challenge is that it is often desirable to increase a system's effective reliability by periodically testing its memory while the system is S in service. Nicolaidis ("Transparent BIST for RAMs,"
Proc. 1992 Int. Test.Conf., Baltimore, MD, U.S.A., Sept. 20-24, (IEEE Comp. Soc., Washington,1992), pp.
598-607) tackled this additional problem by developing a method whereby the self-test routine produced by a BIST RAM is made transparent, that is, the contents of the RAM initially present when the self-test was started are restored, if the RAM is fault-free, by the end of the test. RAMs with transparent BIST can thus be tested periodically in a running system, without requiring that the stored data be first copied out and stored elsewhere for the duration of the test, and then rewritten back to the RAM once the test has completed.
Nicolaidis' method requires that a proposed RAM self-test be first transformed in a series of steps. Essentially these steps ensure that the data in each RAM cell is complemented an even number of times during the application of the test. The transformed test is applied in two phases: In the first phase, only read operations are applied to the RAM as a first data-dependent signature is computed.
In the second phase, both read and write operations are applied while a second signature is computed. The RAM is deemed fault-free if the two signatures agree.
The scheme is vulnerable to the small but finite chance of aliasing, when the two signatures are the same in the presence of a fault. Aliasing is possible even if the original memory test is deterministic, i.e., has 100% fault coverage over the assumed fault ~12~390 universe. However, the probability of aliasing can always be reduced by using longer signatures. When a deterministic test is used to construct a transparent test, we call the resulting test near-deterministic.
By a probabilistic test we will mean either a nontransparent test that has less than 100% fault coverage, or a transparent test based on such a nontransparent test.

SU~ARY OF THE INVENTION
In this patent disclosure is described an apparatus and method for test vector generation, the apparatus being suitable for embedding in a conventional memory tester, that produces both deterministic tests for detecting single 2-, 3-, 4-and 5-coupling faults, and probabilistic tests for detecting single V-coupling faults of arbitrary multiplicity V 2 2. The generator according to one aspect of the invention comprises a 6400 cell semi-custom test sequencer and a read-only memory (ROM) for storing compressed code data used by the sequencer to construct the tests on-the-fly. Although the test generator is capable of producing the shortest known deterministic tests for detecting single 4- and 5-coupling faults, it is too bulky to be used directlyin a BIST design. The BIST RAM design also proposed in this patent disclosure overcomes this limitation by using alternative codes that can be generated using compact circuitry; in addition, the proposed design can generate transparent tests.
While some individual process steps carried out by the apparatus described here are known in the art, there has not been proposed a complete device or - 2129~90 method with the entire function of the invention made by the inventor.
There is therefore provided in one aspect of the invention a method of testing a random access memory (RAM) having n cells, each cell being identified by an address, for single V-coupling faults where n 2 V 2 2, the method comprising the steps of:
establishing a first current value for each cell;
for each cell and for each of m data backgrounds, generating a background code logic bit corresponding to an element of an (n, V
exhaustive matrix;
for each of m data backgrounds;
(1) applying a sequence to each cell as follows:
(a) reading the current value of the cell, (b) writing to the cell a logical function of the background code logic bit and the first current value of the cell;
(c) reading the cell to determine the value of the cell after the writing operation in step b;
(d) writing the complement of the value of the cell determined in step b to the cell; and (2) for each background except the mth background, updating the current value of all cells according to the background code logic bits corresponding to that cell;
reading each cell of the RAM; and `- 212939Q

discarding or repairing the RAM if a cell coupling fault is apparent from the series of values read from the cells of the RAM.
According to one aspect of the invention, the background code logic bit is generated by initially constructing an (nO, V ~ exhaustive matrix where nO ~ n, the matrix having nO rows and mO
columns; and constructing at least a portion of the (n, V - 1)-exhaustive matrix from the (nO, V - 1)-exhaustive matrix. Generating a bit corresponding toan element of an (n, V - 1)-exhaustive matrix may include row rotating the stored (nO, V - l)-exhaustive matrix according to the background and cell address, or integer dividing the background by mO to produce a value i; integer dividing the cell address by nO to produce a value j; and row rotating the (nO, V - 1) matrix by the product of i and j modulo nO.
According to a further aspect of the invention, generating a background code logic bit may include pseudo-randomly selecting a background code logic bit from the address of the cell, in particular by a hashing of the cell address, as well as from logical zero and one. The hashing function may include selection of the bit under control of the data background value.
According to another aspect of the invention, the logical function may be the complement of the element of the (n, V - 1)-exhaustive matrix irrespective of the current background code logic bit of the cell or an exclusive-or of the complement of the background code logic bit and the first current value of the cell.
According to further aspects of the invention, hashing the address of the cell may include 212939~

summing bits in the address, or forming the XOR of at least two address bits. Forming the XOR of at least two address bits may include generating bit pairs in the address of the cell, each bit pair including a left bit and a right bit; applying the left bit, logical 0 and the cell address to a first multiplexer having a first output; applying the right bit, logical 0 and the cell address to a second multiplexer having a second output; and applying the first output and the second output to an XOR gate. The first and second multiplexers may be controlled by the data background, and a hashing of the data background may also be applied to the XOR gate.
Detection of cell coupling faults may be carried out by comparison of the read cell content with the cell content of a known perfect RAM, or by comparing values read from the cell at different parts of the test where the same value should be returned in a good memory.
According to a further aspect of the invention there is provided apparatus for carrying out the method of the invention. In one aspect there is provided apparatus for testing a random access memory (RAM) having n cells, each cell being identified by an address, for V-coupling faults where n 2 V 2 2, the apparatus comprising: a PROM containing background code logic bits corresponding to an (nO, V ~
exhaustive matrix where nO ' n, the matrix having nO
rows and mO columns; and generator means to generate a background code logic bit corresponding to an element of an (n, V - 1)-exhaustive matrix on-the-fly from the background code logic bits in the PROM and to selectively apply the generated background code logic bit to the RAM.

- 212939~

The generator means may include means to row rotate the stored (nO, V ~ exhaustive matrix according to the cell address, and means to integer divide the background by mO to produce a value i;
integer divide the cell address by nO to produce a value j; and row rotate the (nO, V - 1) matrix by the product of i and j modulo nO.
In a still further aspect of the apparatus according to the invention, there is provided a built-in apparatus for testing a random access memory (RAM)having n cells, each cell being identified by an address, for single V-coupling faults where n 2 V >
2, the apparatus comprising a RAM, a RAM address generator, a background code logic generator connected to receive RAM addresses from the address generator and having pseudo-random backgroun.d code logic bit output; a test pattern generator connected to receive RAM addresses from the RAM address generator and connected to receive output from the background code logic generator and having test pattern output forming an (n, V - 1)-exhaustive code including m data backgrounds for each cell of the RAM; a controller for sequentially writing the test pattern output to the RAM and reading the cells of the RAM; and a response analyzer connected to receive the read content of the cells of the RAM.
The background code logic generator may include means to select the background code logic bit for application to a cell from a hashing of the RAM
address of the cell, which may be responsive to the value of the data background, and may include means to form an XOR of at least two address bits.
In a still further aspect of the invention, the means to select the background code logic bit may -212Y39~

include an all bit pair generator for generating all bit pairs in the address of the cell, each bit pair including a left bit and a right bit; a first multiplexer having a first output, the first multiplexer being connected to receive the left bit, logical 0 and the cell address; a second multiplexer having a second output, the second multiplexer being connected to receive the right bit, logical 0 and the cell address; and an XOR gate connected to receive the first output and the second output.
The first and second multiplexers may be controlled by the data background, and a hashing of the data background may be applied to the XOR gate.
These and other aspects of the invention are described in the detailed description and claimed in the claims that follow the detailed description.

BRIEF DESCRIPTION OF THE DRAHINGS
There will now be described preferred embodiments of the invention, with reference to the drawings, by way of illustration, in which like numerals denote like elements and in which:
Fig. 1 is a system block diagram for a deterministic fault test apparatus according to the invention;
Fig. 2 is a normal mode state diagram for the apparatus of Fig.1;
Fig. 3 is a timing diagram for the test mode of the apparatus of Fig. 1;
Fig. 4 is a diagram showing parallel mode operation of an apparatus according to the invention;
Figs. 5A and 5B are diagrams showing the structure and mode of operation of a PROM for 10 ~2~yQ
reconstructing an ~n, V~ exhaustive matrix for application to a RAM;
Fig. 6 is a diagram showing how a test is formed from a test matrix;
Fig. 7 is a diagram showing a PROM address map for use in the apparatus of Fig. l;
Fig. 8 is a diagram showing the format for a code location record for use with the apparatus of Fig. l;
Fig. 9 is a diagram showing how sample elements in Fig. 8 are used;
Fig. 10 shows storage of (n, V-l)-exhaustive matrices (codes) in the PROM of Fig. l;
Fig. 11 shows the storage format for the code data in the PROM of Fig. l;
Fig. 12 shows an exemplary RAM tester system architecture according to the invention;
Fig. 13 shows a main controller connection diagram for use with the apparatus of Fig. l;
Fig. 14 shows a PROM address generator connection diagram for use with the apparatus of Fig.
l;
Fig. 15 shows a data queue connection diagram for use with the apparatus of Fig. l;
Fig. 16 shows a RUT address generator connection diagram for use with the apparatus of Fig.
l;
Fig. 17A shows an exemplary (n = 4, m = 5) test matrix formed of background code logic bits for application to a RAM;
Fig. 17B shows a timing diagram corresponding to the test matrix of Fig. 17A;
Fig. 17C shows the corresponding timing diagram after an exclusive-or transformation of the 212~3~

test from Figure 17B when it is assumed that cells 0, 1, 2 and 3 of an exemplary RAM initially contain data values 0, 1, 1 and 0, respectively;
Fig. 18A is a simplified schematic of the system architecture for an exemplary 8k x 8 BIST RAM
according to the invention;
Fig. 18B is a version of Fig. 18A showing detailed inputs and outputs for the examplary BIST
RAM;
Fig. 19 shows a simplified state diagram for the apparatus of Fig. 18A;
Fig. 20 shows a first exemplary background code logic bit generator for use with the apparatus of Fig. 18A;
Fig. 21 shows a second exemplary background code logic bit generator for use with the apparatus of Fig. 18A;
Fig. 22 is a schematic showing an address generator for the BIST RAM of Fig. 18A;
Fig. 23 is a schematic showing an address counter for the address generator of Fig. 22;
Fig. 24 is a schematic showing a last address detection circuit for the address generator of Fig. 22;
Fig. 25 is a schematic showing a background counter for the BIST RAM of Fig. 18A;
Fig. 26 is a schematic showing a 5-bit background counter for the background counter of Fig.
25;
Fig. 27 is a schematic showing a last bit background detection circuit for the background counter of Fig. 25;
Fig. 28 is a schematic showing a background code logic generator for the BIST RAM of Fig. 18A;

212~3~

Fig. 29 is a schematic showing present bit logic for the background code logic shown in Fig. 28;
Fig. 30 is a schematic showing next bit logic for the background code logic generator shown in Fig. 28;
Fig. 31 is a schematic showing zero summing logic for the background code logic generator shown in Fig. 28;
Fig. 32 is a schematic showing a sum zero 10block for the background code logic generator shown in Fig. 28;
Fig. 33 is a schematic showing a test pattern generator for the BIST RAM of Fig. 18A;
Fig. 34 is a schematic showing a data 15register for use in the test pattern generator of Fig.
33;
Fig. 35 is a schematic showing a write bit flipper circuit for use in the test pattern generator of Fig. 33;
20Fig. 36 is a schematic showing a 3-to-8 decoder for use in the test pattern generator of Fig.
33;
Fig. 37 is a schematic showing tri-state buffers for use in the test pattern generator of Fig.
33;
Fig. 38 is a schematic showing a response analyzer for the BIST RAM of Fig. 18A;
Fig. 39 is a schematic showing a read bit flip enabler for use in the response analyzer of Fig.
38;
Fig. 40 is a schematic showing a detail of the block invlog2 of Fig. 39;
Fig. 41 is a schematic showing a read data selector for use in the response analyzer of Fig. 38;

21293~

Fig. 42 is a schematic showing a 16-bit wide multiple input signature analyzer for use in the response analyzer of Fig. 38;
Fig. 43 is a schematic showing a 16-bit 5register for use in the response analyzer of Fig. 38;
Fig. 44 is a schematic showing a 16-bit comparator for use in the response analyzer of Fig.
38;
Fig. 45 shows a detailed state diagram for 10the BIST controller shown in Fig. 18A;
Fig. 46 is a detail showing the inputs and outputs of the BIST controller shown in Fig. 18A;
Fig. 47 is a schematic showing the control path of the BIST controller shown in Fig. 18A;
15Fig. 48 is a schematic showing output logic for the control path of the BIST controller shown in Fig. 18A;
Fig. 49 is a schematic showing next state logic for the control path of the BIST controller 20shown in Fig. 18A; and Fig. 50 is a schematic showing the datapath of the BIST controller of Fig. 18A.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
25Referring firstly to Figs. 1 - 17B there is described a first embodiment of the invention in which there is described an on-the-fly generator of a deterministic family of tests for detecting single V-coupling faults, for V 2 2. The structure of each of 30the generated tests is determined by an n x m binary matrix, where n is the number of words in the RAM
under test (RUT) and m is the number of data backgrounds used in the test. For example, Fig. 17A
is a matrix in which n = 4 and m = 5, and Fig. 17B is 212~3~Q

the timing diagram for the corresponding test. The short vertical bars in the diagram denote read operations.
For the application of the test, a background code logic bit (data bit) must be generated for each cell and for each of m data backgrounds. Each of the background code logic bits corresponds to an element of an (n, V~ exhaustive matrix. Generation of proper background code logic bits is not easy and is described in detail in this disclosure. However, firstly, a brief description of the test procedure is given.
The test begins by initializing the RUT with the first background, that is, according to the first matrix column, to establish a first current value for each cell of the RUT. In this disclosure and in the claims, the current value of a cell referred to during execution of a step of the process is the value of the cell at the time the step is carried out. The first current value is the value of the cell at the commencement of execution of the steps in the process.
After the first current value is established, a ~(rb wb rb wb) march is applied; that is, in ascending address order (or in any other exhaustive address order), each cell is read, then written with the complementary value, read a second time, and then written again with the original value. Next the second background is loaded according to the second matrix column, taking care to read each location that needs to be changed before writing the new value.
Loading the second background updates the current value of all cells. The same 4n march is then run through the second background. The process of loading a new background and then applying the 4n march is 212~3~ 0 repeated until all matrix columns have been considered (that is, the same sequence has been applied to each cell for m backgrounds). As a final sequence, each cell is read one last time. The test length corresponding to a relatively random matrix of width m will be approximately (5m + l)n.
A deterministic test with the structure described above will detect all single V-coupling faults in an n x 1 RAM if the rows of the underlying matrix form an (n,V-1)-exhaustive code. The rows of an n x m matrix A form an (n, V - 1)-exhaustive code if (1) n > V - 1 and (2) for all possible projections of A onto V - 1 rows, all 2V-1 possible binary (V - 1)-tuples will appear as column vectors. For example, the set of rows {01,01,01,01} is a (4,1)-exhaustive code because both 0 and 1 appear in every codeword.
The corresponding 48 operation test therefore detects all single 2-coupling faults in a 4-cell RAM. As another example, consider the matrix in Fig. 17A.
This matrix is (4,2)-exhaustive because, for all of the six possible choices of two rows, all four binary combinations (00, 01, 10, 11) appear in the columns.
Thus the 106 operation test in Fig. 17B detects all single 3-coupling faults in a 4-cell RAM.
Deterministic tests of approximate length 11.7(1Og2n)1 585 and 18.6(1Og2n)2 322 that detect all single 4- and 5-coupling faults, respectively, can be constructed using the (n,k)-exhaustive codes described by Tang and Chen ("Iterative Exhaustive Pattern Generation for Logic Testing," IBM J. Res. Develop., v. 28, no. 2, pp. 212-219, Mar. 1984).
These codes are generated using an iterative procedure. First, an (nO, k)-exhaustive base code, where typically nO n, must be constructed by any 212~3~

means. Tang and Woo-s ("Exhaustive Test Pattern Gen-eration with Constant Weight Vectors," IEEE Trans.
Comp., v. C-32, no. 12, pp. 1145-1150, Dec. 1983) method could be used, for example, to generate the base code. The size nO of the base code, typically much smaller than the size n of the desired code, must be chosen so that nO = mi, where m is a prime number, i > 1, nO > k, and m > L k2/4 ~. Next, a "growing"
step is applied as many times as is necessary to obtain the necessary number n of codewords. Each growth operation squares the number of codewords and extends their length by a factor of approximately q =
L k2/4 1 + I. In Tang and Chen it is shown that the length m of the resulting (n,k)-exhaustive codes grows according to the formula log2nO

where mO is the length of the (nOk)-exhaustive base code.
RAM tests are composed of a series of test patterns. Each code element is applied to a RAM under test (RUT) sequentially as part of a test pattern.
Each test pattern contains a RAM address, a read or write command and a data bit (background code logic bit) derived from a code element. Apparatus for generating the test pattern is shown in Fig. 1, which shows the general internal structure of the sequencer 10 along with the connections to the look-up PROM 12.
There are four subsystems: the main controller 14 is responsible for overseeing the operation of the - 21293#

sequencer 10, controlling the functions of each of the other three sub-modules. The PROM address generator 16 generates PROM addresses that fetch the code location records and the code matrices. The data queue 18 takes the raw PROM code data and outputs data bits with a corresponding increment request to the RUT address generator 20. The RUT address generator 20 assembles the complete test vectors, ensuring that they are correctly output. A clock generator 22 provides clock signals for use elsewhere in the sequencer 10.
The test generator as illustrated in Fig. 1 is partitioned across two integrated circuits: one standard 256 Kbit x 16 PROM 12 and one semicustom sequencer integrated circuit 10. The lowest 256 words of the PROM 12 are used to store control parameters for 32 different pre-defined tests; the remaining locations are used to store matrix data. The sequencer 10 is responsible for reconstructing the full-sized matrix on-the-fly from the PRO~ data and then producing the corresponding unformatted test vectors.
Approximately one new test vector can generated in every clock cycle (occasionally the sequencer is unable to maintain this pace).
The code matrices are stored in the PROM 12 in a compressed form which exploits the theorem under-lying Tang and Chen's construction. Instead of storing the final full matrix, it is the matrix corresponding to the preceding growth iteration that is stored. For example, a (1024,3)-exhaustive code rather than a (1048576, 3)-exhaustive code is stored when 1 Mbit RAMs are tested for single 4-coupling faults. The storage requirements in this case are reduced by a factor of approximately ~ x q = 3072. A PROM size 212~3~

of 4 Mbit precludes deterministic testing for 5-coupling faults in RAMs larger than 1 Mbit.
Probabilistic testing for these faults is still possible, however, for multi-megabit RAMs. The 32 control parameter records are used to define the characteristics of 32 different tests. Tests can share matrix data. Also, deterministic and probabilistic tests can be freely intermixed since they are treated identically by the sequencer. The PROM 12 can be easily replaced if a different selection of tests is desired, or if improved (n,k)-exhaustive codes are to be installed.
The electrical interface for the sequencer 10 includes 72 signal pins, one serial input and one serial output for the scan chain (included for testing purposes), and 16 power supply pins. As shown in Fig.
1, the sequencer comprises four major subsystems.
Overall control rests with the main controller 14.
During initialization, the PROM address generator 16 fetches one of 32 test control parameter records from the PROM 12 so that various sequencer registers can be initialized. The PROM address generator 16 then enters a semi-autonomous mode in which it prefetches matrix data from the PROM 12. Retrieved PROM words enter a four-stage pipeline contained in the data queue 18 (DQ) and RUT address generator (RAG) 20. The data queue 18 converts the matrix data from 16-bit words to code bits that are synchronized to the RUT addresses.
This task is complicated during background changes because the addresses of RUT cells that do not need to be modified are skipped. This optimization decreases the test time by approximately 17%. The RUT address generator 20 is responsible for assembling the 27 bit wide test vectors. Each vector contains 24 address 2129~9~

bits (ADDR0-23), a read/write bit (R/W), a data bit (DATA), and a wait signal (WAIT). The wait signal is used to flag the occasional times when the sequencer is unable to generate a new test vector for the current clock cycle. When wait is active, the remaining 26 test vector bits are repeated from the previous clock cycle.
In order to assure test integrity, a signature is recomputed by the RUT address generator 20 as each test is generated. When the done signal is asserted to signal the end of the test, the OK signal indicates whether or not the freshly recomputed signature matches the expected signature that was stored in the test's control parameter record.
The test generator could be used to test n x k RAMs, where k > 1, by using the same data bit stream for all k data lines. Such an approach, however, would not detect interactions among bits of the same data word. To deal with this problem, the generator has been provided with a parallel testing mode that is configured by data in the test control parameter records. Essentially, k different test generators can be synchronized to generate a modified version of the test in which the k generators use k disjoint subsets of the same matrix data. Several techniques are used within the sequencer 10 to obtain higher performance. One such technique is to use the PROM address generator 16 to prefetch data from the PROM 12 to anticipate the next data required by the data queue 18. In this way the PROM address generator 16 assumes it must generate the next address for the PROM 12, and goes ahead and does so. Then when the data queue 18 requests another word of data, it is already waiting to be latched. Another speed 212939~

optimization allows the sequencer to skip unnecessary read and write operations during background changes.
This feature enables the total number of operations performed by the sequencer 10 upon the RUT to be reduced by roughly 17%. When the sequencer 10 is generating test vectors occasionally it must assert the WAIT line indicating it was unable to generate a test vector for that clock period. The number of WAIT
states is typically 1/2 of one percent of the total number of test vectors.
It is preferred that the sequencer 10 uses a basic single phase, edge triggered clocking strategy throughout the design. With this clocking method, both internal control type signals and data registers are latched on the same edge of the clock, allowing for both control and data signals to settle during the same time.
The sequencer package is connected to its environment via 72 signal pins, 2 serial test lines, and 16 power supply pins. The 16 power supply pins are necessary for powering the high current drive output pads. All of the pins are connected to either a signal source/sink, power, or ground. The signal names and functions are given in table 1.
The sequencer 10 preferably has two basic modes of operation: test mode and normal mode. The mode is selected using a TMODE input line on the sequencer 10. When TMODE is asserted, i.e. in test mode, every flip-flop in the sequencer 10 is switched to scan mode, forming a single long scan chain (every flip-flop is connected serially as a single shift register). Also, when in this mGde, the internal clocking is altered to enable the test clock (which is derived in the clock generator 22 from the main CLOCK

21 ~12939Q
input). As the CLOCK runs, scan chain data is shifted in from the SDI line, and out the SDO line. One bit is read in/out every clock cycle. When the TMODE line is released, normal operation of the sequencer resumes.
In this way, the state of every flip-flop in the sequencer can be checked at any time during the operation of the sequencer 10, and the sequencer 10 can be placed in any desired state.
When TMODE is deasserted, the sequencer 10 is in normal mode. In this mode, the sequencer 10 preferably generates test vectors at a rate of nearly one vector per clock period. The basic state diagram in Fig. 2 illustrates the normal mode of operation.
When RESET is asserted, TEST0-4 are set to select which of 32 tests stored in the PROM 12 is to be executed. The TEST signals are latched by the sequencer 10 upon start-up (when the RESET signal is deasserted), and multiplied by 16 to produce the base address of the corresponding code location record stored in the PROM look-up table.
The sequencer 10 is in the running state when RESET is deasserted and ENABLE is asserted.
During the running state, test vectors are generated and output from the chip. The 27 bit test vectors should only be considered valid when the WAIT signal is low. The WAIT signal is the sequencer's means of stating whether or not a valid test vector is available to be used on the RUT.
After the sequencer 10 has output all test vectors for a particular test, the DONE line is asserted, informing the environment that it is in the "done state" awaiting further instructions. During this state the OK line should be checked to see whether it indicates that the freshly recomputed - 212939~

signature matches the expected signature stored in the PROM 12. In this way test integrity is assured. The signature is a 16 bit number generated using a multiple input feedback shift register (MISR) using the test vector outputs as inputs to the MISR. Using 16 register bits and several logic gates a unique number is generated in the MISR from a series of test operations. Providing the test operations for a given test are identical to the expected output, the sig-nature will match that which is loaded in the PROM 12.
If, at any time during the normal operation of the sequencer 10, it becomes necessary to tempo-rarily stop the output of the test vectors, the ENABLE
signal is deasserted. The clock period in which the ENABLE signal is dropped will continue to completion, then the generation of new test vectors will stop.
Normal operation is then resumed at the start of the next whole clock cycle when the ENABLE signal is asserted.
During test mode, the sequencer 10 shifts an input bit (from SDI) through 320 register bits. Thus, as is shown in Fig. 3, the data input on the SDI line is not output until 320 clock periods later (plus pad delays which should be less than one clock period long) on the SDO line. Note that the input SDI bits must shift through the entire scan chain of 320 flip-flops, but the exact amount of time until the bit input into the chain appears on the SDO line depends on when the SDI bit was entered relative to the clock signal. Since the system is falling edge clocked, there is a larger time delay between when the clock signal reaches the flip-flops than direct pad inputs.
Fig. 3 shows an example of how the chip could be forced into any specific state.

-23 2l2~9~
When an n x K RAM is being tested, then K
test vector generators can be run in parallel. Each generator chip is responsible for testing one bit of the word in the RUT. During changes in the RUT
"background" a K-fold speed-up is achieved. Thus, the test time can be reduced by a factor of K from 1/3 of the total test time.
For example, consider an RUT that contains 1024 words, with 4 bits per word. In this case 4 sequencers 10a, 10b, 10c and 10d must be connected in parallel to the RUT. Total speed-up is about 25~ over a single sequencer test system. Figure 4 illustrates the arrangement.
Each sequencer 10a, 10b, 10c and 10d supplies test vectors (including ADDR, DATA, R/W and WAIT bits) to the RAM under test 24 through a formatting circuit 26 and pin drivers 28. Overall control of functions is provided by digital controller 30, with clock (timing) generator 32 supply clock signals to the formatting circuit 26. Test results are produced through pin receivers 34 and a decision is made on the effect of the test in comparator 36.
Parallel mode operation is enabled by a bit in code location record in the PROMs 12. All of the PROMs 12 in this case should be nearly identical. The only difference will lie in some of the fields of the code location records. The control signals to the sequencers 10a, 10b, 10c and 10d should also be identical. The base matrices for each PROM 12 will be identical, as will the number of code location records. For this RAM size, the code size must be at least 64 (the square root of 1024x4~. The code length depends upon the code matrix used.

21293~

Figs. 5A and 5B illustrate a growth step in which a 25-row code (Fig. 5B) is constructed from a 5-row code (Fig. 5A). If the code in Fig. 5A is (5, 5)-exhaustive, then the code in Fig. 5B will be (25, 5)-exhaustive. A growth step "glues" together possibly row-rotated copies of the original code to get the next code. More precisely, consider an (ni k)-exhaustive code A of length mO that is to be grown into an (ni2,k)-exhaustive code A'. As before, let q = L k2/4 ~. An r-rotated copy of a code {vO,v1 vn_1~ is the code {Vr mod n, lV(r + 1) mod nl 'V(r+n-l) mod n} A growth iteration proceeds in four steps: First, ni x q copies of A are arranged in ni rows of q copies each. The copies are labelled according to their horizontal position, from 0 to q-1, and their vertical position, from 0 to nO -1 (as in Fig. 5B). Second, the copies are row-rotated so that the copy at position (i, j) is ((i x j) mod nO)-rotated. Third, the codes are attached together to form a code containing nO2 codewords of length q x mO.
Finally, if A contained columns containing all Os or all ls, then duplicate columns in the new code A' (containing all Os or all ls) may be removed. A zone is a set of columns in the grown matrix corresponding to one width of the underlying matrix. Thus the quantity q specifies the number of zones required in each growth iteration.
For 210 < n < 234, this procedure leads to (n,3)-exhaustive codes whose length lies within 20% of 2.34(1Og2n)l 585, and to (n,4)-exhaustive codes whose length lies within 40% of 3.72(1Og2n)2 322. These codes can be used to construct tests of approximate length 11.7(1Og2n)l 535 and 18.6(1Og2n)2 322 that detect all single 4-and 5-coupling faults, respectively.

~12939~
The test matrix for complete detection of 5-coupling faults is larger than the test matrix for detection of 4-coupling faults. A test for 4-coupling faults will also detect at least 50% of the 5-coupling faults. The total number of rows in the test matrix corresponds to the RUT size. The number of columns in the test matrix corresponds to the number of "backgrounds" which are to be applied to the RUT.
Effectively, the number of backgrounds is proportional to the number of operations which are applied to each bit in the RUT.
The sequencer 10 produces test vectors as it reconstructs the test matrix on the fly. The way in which RUT test operations are generated is illustrated by Fig. 6. The figure shows a small test matrix that is transformed into test operations (reads and writes). The legend describes the syntax of the graphical representation of the test operations.
The first sequence writes the first background to the RUT. The entire first column of the test matrix is written to the RUT. In subsequent background sequences, the cell values are read to ensure that they are correct before being written. The next sequence of operations is called a "march"
through the background state. These operations are performed using the same column of data as the background writes. A march involves first reading the contents of a cell to ensure that it is correct, and then writing to that cell the inverse of its original value, reading the cell again, and then writing the cell back to its original value. That way, the value of the cell should be the same as when the previous background operation was performed and can be checked at the beginning of the next background operation.

212~3~

This pattern of background-march-background-... is continued until the entire test matrix is exhausted.
The 256K x 16 look-up PROM 12 contains information that is required to construct each of the 32 possible different tests. The lower 512 bytes of PROM 12 memory are used to store each of 32 code location records. Each record specifies a different test. The remaining 523,774 bytes of memory in the address space of the PROM 12 are used to store the code matrices which are to be reconstructed into full test matrices by the sequencer chip. The address map of the PROM 12 address space is shown in Fig. 7.
Figure 8 shows the format of each 8 x 16 bit code location record. It is not necessary to completely store 32 different code location records to use a PROM 12 with the sequencer 10. Only those tests which will be performed need to be described by a record. The shaded area in the diagram shows bits in the record which are not used by the sequencer 10.
These bits may be set to any value, but should be padded with zeros. All of the bits in the record that are not used must be set to zeros. Table 2 describes each field of the code location records.
The upper address space of the PROM 12 stores the code matrices that are used to generate the tests. The special mapping format which must be used to load the codes into the PROM 12 is described by example in Figs. 10 and 11.
The sequencer 10 should be operable in parallel or stand alone mode by setting MAXBITNUM to a non-zero value (parallel mode) or zero value (stand alone mode). Fig. 10 shows the code matrix that is to be stored in the PROM 12 upper address space. Each cell in the diagram corresponds to one bit of the 27 21~93~
matrix. The numbers which appear in the cells are for identification purposes only. In Fig. 12 the mapping of the code matrix into the PROM 12 is shown. Fig. 11 shows duplication of the information stored in the PROM 12. Each PROM word stores up to 8 bits for the current background and the corresponding bits in the next background. This duplication of data reduces the number of PROM 12 accesses by a factor of two at the cost of doubling the required PROM capacity.
The sequencer 10 is designed to be used within a larger RAM testing system. The diagram in Fig. 12 shows the architecture of such a testing system that employs the sequencer 10. Sequencer 10 provides test vectors to formatting circuit 38, which are then applied to the RAM 40 through pin drivers 42.
The background code logic bit DATA is provided by PROM
12. The PROM functions as generator means to generate a background code logic bit corresponding to an element of an (n, V - 1)- exhaustive matrix on-the-fly from the background code logic bits in the PROM 12 and to selectively apply the generated background code logic bit to the RAM using the output of the address generator. Control of the system is provided by computer 44 with timing generator 46. Test results are provided by pin receivers 48 to comparator 50, which provides a signal to the computer 44 as to whether a fault was detected. The RAM may then be repaired or discarded or kept according to the result of the test.
The computer 44 initializes the sequencer 10, and controls the timing generator 46. The computer 44 only is involved in the operation of the sequencer 10 during the start-up and end phases of a test. A
single error found by the comparator 50 should be 28 '~1~9390 cause for the computer to terminate the current test, and record the RUT 40 as flawed.
The following is a typical sequence of events to set up a test.
1. Set-up the TEST0-4 signals to the desired state.
2. Assert the ENABLE signal.

3. Assert the RESET signal.

4. Deassert RESET when the system is ready to run the test.

5. Use the ENABLE signal to halt the test when desired.

6. When the DONE signal is asserted check the OK
line. 7. Sequence of events can now be repeated from (1).
The sequencer 10 employs a single-phase, edge-triggered clocking scheme. Internal global network names such as CLK in the figures are characterized by the exclamation mark (!). There are three such nets which are named CLK!, TCLK!, and CLR!.
Referring now to Figs. 1 - 16, the clock generator 22 takes the inputs CLK, ENABLE, and TMODE, and uses them to develop the global clock nets CLK!, and TCLK!. Preferably, the clock signals are driven through on-chip amplifiers before they reach the global networks.
The main controller 14 sub-module supervises the entire sequencer operation. Each of the other three sub-modules (PROM address generator 16, data queue 18, RUT address generator 20) operate under their own direction. However, the main controller 14 is responsible for the coordination of the other sub-modules so as to lead to the formation of a set of 29 212939~
test vectors. The main controller 14 sub-module is shown in Fig. 13.
The main controller 14 communicates with the PROM address generator 16 by sending it signals indicating when it is to point to the top of a column in the test matrix (using the TOPPRESCOL, TOPNEXTCOL, and TOPFIRSTCOL lines). In return, the PROM address generator 16 keeps the main controller 14 informed of the particular type of column it is pointing to, with respect to the current zone. The FIRSTZONECOL line is asserted when the PROM address generator 16 is pointing to the first column in the current zone. The LASTZONECOL line is asserted when the PROM address generator 16 is pointing to the last column in the current zone. The LASCOL line is asserted during the last column of the entire test matrix. When the main controller 14 detects that either of these two signals is being asserted, it modifies its background operation.
The main controller 14 requests two different initialization procedures from the PROM
address generator 16. They are STARTINIT and INIT.
STARTINIT is asserted at the very beginning of the initialization procedure, and requests the PROM
address generator 16 to initialize all of its internal registers to their starting value, and latch in the current test number tTEST0-4). Then, the INIT line is asserted for 8 clock cycles, during which time the code location record pointed to by the current test number is loaded by the PROM address generator 16 from the PROM 12.
Sequencer testability and diagnosability are assured by a scan chain that is formed by linking all of the internal register bits together in a continuous 212 939a chain. The TESTOUT line is used for this purpose. This line is the scan chain output from the main controller 14 sub-module, and is connected to the scan chain input (I) of the PROM address generator 16. Even-tually, the scan chain data is output to a pad. Duringtest mode, normal operation of the main controller 14 (and the other sub-modules) is halted, and the scan chain serially shifts test data iIl through the SDI
line, and out through the TESTOUT line which eventually leads to the SDO line. In this way, the internal state of the sequencer can be determined.
During normal operation, the main controller 14 sends signals to the data queue 18 via the N, INV, and SKIP lines. By asserting the N line, the main controller 14 informs the data queue 18 that it is to release another test vector (with data bit). The state of the INV line at this time determines whether or not the data bit output from the data queue 18 is to be inverted. It is inverted at times during RUT marches (described later). If the SKIP line is asserted, the data queue 18 is allowed to skip unnecessary RUT test vectors as it sees fit. The main controller 14 only asserts this line during normal background operations, when not in parallel mode. The data queue 18 returns status signals on the QRDY and DIFF lines. DIFF is asserted by the data queue 18 if the current data bit is different from the data bit that is loaded in the RUT at the current address location. The main controller 14 uses this information to decide if the data bit should be inverted or not. If the data queue 18 has a test vector ready to be sent to the RUT
address generator 20, then QRDY is asserted. QRDY will deassert when the data queue 18 is initializing and/or retrieving the next RUT test vector. In this way, the 31 212939~
N signal acts as a request for the data queue 18 to output its current test vector, and fetch the next one.
The main controller 14 must also communicate with the RUT address generator 20. It sends four different signals to the RUT address generator 20 on the R/W, ALLONES, WAIT, and DONE lines. R/W and WAIT
apply to the current test vector. These lines indicate whether the test vector data bit is to be written or read and compared with the RUT data. The WAIT signal represents the main controller 14~s vote for a wait state on the current test vector. This internal WAIT
signal may be overridden by the RUT address generator 20. ALLONES is asserted when the main controller 14 requires the RUT address generator 20 to reset its address counter. Finally, DONE is asserted by the main controller 14 when the current RUT test sequence is completed. In order for the main controller 14 to realize when it has reached the final address of the RUT, the RUT address generator 20 sends a signal called LASTRUTADDR to the main controller 14.
Another task of the main controller 14 is to oversee parallel mode operation. After loading the current code location record from PROM memory, the main controller 14 determines whether or not it is to run in parallel mode. If it is, it changes its operation accordingly to allow it to operate without skipping and thereby run in lock-step with the other parallel sequencer chips.
Table 2 contains descriptions of most of the interconnection lines between the chip sub-modules.
The lines which do not appear in table 2 are described later since they don~t involve the main controller 14.

2129~

The PROM address generator 16 generates PROM
addresses which fetch data that is used by the data queue 18 to form the test vectors. A maximum of 8 test vectors can be formed by each PROM fetch. This limitation is a result of the way code matrices are stored in the PROM look-up table. At most one test vector can be produced for each new bit in a PROM
word. Since there is duplication of code matrix storage in the PROM 12, there are only 8 new bits in each 16 bit PROM word. The PROM address generator 16 sub-module is shown in Fig. 14.
The PROM address generator 16 is operable in four states. Four states are necessary to allow the PROM 12 enough time to fetch its data when running at 36 MHz, assuming that each access requires approximately 120 ns. Reduction of the PROM 12 access time, reduces the amount of time the chip spends in a wait state. However, the improvement in performance would not be significant since typically only 0.5% of the clock cycles are spent in a wait state.
When in its initialization phase, the PROM
address generator 16 loads the code location record pointed to by 8 x TEST0-4. The record is loaded one 16-bit word at a time, and therefore takes 8 clock periods to complete. This operation is synchronized with the main controller 14 to allow the rest of the sub-modules to be able to latch in the record data which is pertinent to their operation.
The PROM address generator 16 primarily communicates with the data queue 18. Occasionally (at the start or finish of a column) the main controller 14 sends particular signals to the PROM address generator 16 (see main controller 14 description above). The data queue 18 signals the PROM address 212939~

generator 16 that it has latched the current PROM data word by asserting the GO line. This indicates to the PROM address generator 16 that it can now calculate the next PROM address (PADDR0-17), and wait for 4 clock cycles to allow the PROM data lines to settle.
The data queue 18 will not assert the GO line, however, until it recognizes that the PROM data lines are settled, which is indicated by the PROM address generator 16 asserting the RDY line. The PROM address generator 16 is constantly trying to keep ahead of the data queue 18 by prefetching the addresses, so before the GO line is even asserted, the PROM address generator 16 attempts to have the next PROM address ready to be sent out on the PADDR lines. Rarely, except at the beginning of a new column, is the PROM
address generator 16 ever caught without having a PROM
address pre-computed. In Table 3 the signals which did not appear in table 2 are described.
The conversion of raw PROM data words into test vectors usable by the RUT address generator 20 is the job of the data queue 18. The name data queue 18 suggests the way in which 16 bit words of data are latched from the PROM 12, and then released as requested by the main controller 14. By latching the entire data word into a queue register, the data queue 18 allows the PROM address generator 16 to change the PADDR lines to fetch what it expects to be the next data word. The data queue 18 sub-module is shown in Fig. 15.
The data queue 18 consists mainly of a complex state machine. When the main controller 14 asserts the N line, the data queue 18 responds by outputting a data bit and an associated RUT address increment value to be used by the RUT address 2l2939~J

generator 20; it also asserts the QRDY line. This task becomes difficult when "skipping" is introduced. By loading information about the last background operation at the same time as the current background data, the data queue 18 is able to calculate which bits of the current data word do not need to be rewritten to the RUT since they match the previous bit. That is, if the current state of a particular RUT
bit is zero, and the new background operation requires the bit to be set to zero, then that operation can be skipped. This optimization is largely responsible for the considerable complexity of the data queue 18.
In general, the data queue 18 starts forming test vectors by starting at the beginning of the current data word, and proceeds one bit at a time until all 8 new bits are exhausted. At that time, the GO line is asserted as soon as the RDY line goes high.
As the GO line is asserted, a new data word is loaded, and the process continues. Those signals not included in Tables 2 and 3 are included in Table 4.
The RUT address generator 20 compiles test vector information from the main controller 14 and the data queue 18, and outputs a valid test vector to the pads. To do this, the RUT address generator 20 must keep track of the RUT address, and increment it as requested by the data queue 18 (via the RUTINC, RUTAD-DRINC lines). The RUT address generator 20 sub-module is shown in Fig. 16.
A final test vector that is output to the pads consists of: a 24 bit RUT address, data value, R/W indicator, and a wait state signal. The address is formed by adding the value of the RUTADDRINC lines to the current RUT address. The data value is obtained from the data queue 18. The R/W indicator is given by 212~39~
the main controller 14. The external WAIT state signal must be generated by the RUT address generator 20 by checking the main controller 14's WAIT vote, and its own wait state circuitry. The RUT address generator 20 asserts its WAIT line if it detects that the current test vector being output is not valid, and/or the main controller 14 requests a wait state.
The tests described above can be made transparent by the application of Nicolaidis' transformation. Fig. 17C shows the result of transforming the test from Figure 17B when it is assumed that cells 0, 1, 2 and 3 initially contain data values 0, 1, 1 and 0, respectively. The initialization sequence has been dropped, and the number of write operations to each cell is even.
Essentially, the data backgrounds that are used in the transformed test are the bit-wise exclusive OR of the initial cell data values (first current values of the cells) and the corresponding data backgrounds in the original test (which are the columns of the underlying binary code). The transparent self-test consists of two phases: In the first phase, only the read operations of the transformed test are applied; e.g., only the horizontal sequence of vertical bars in Fig.
17C. In the second phase, the full transformed test, including all of the read and write operations, is applied. After both phases have been applied, the contents of a fault-free RAM are restored to the initial values by an additional background change sequence that returns to the first background. The length of the transparent test can be shown to be approximately (7.5m + 2)n.
The example in Figs. 17A, 17B and 17C
illustrates the situation when an n x 1 RAM is tested.

21293~

When the RAM words have width k > 1, the sequence of data words is more complex since one must also detect V-coupling faults involving different bits of the same word. The required modification involves the data background changes and the marches as follows: Data backgrounds can be changed one word at a time, with the old word being read before a new word is written.
The operations of the march sequence, however, must be repeated k times to allow each bit to be read and toggled separately.
There has thus far been described a test pattern generator that is suitable for a testing chip.
However, the size of the PROM makes it unsuitable for built in testing. There is now described a testing circuit (BIST RAM) that can be built into a RAM.
The architecture of the proposed BIST RAM
scheme is illustrated in Figs. 18A and Fig. 18B. A
brief description of the BIST RAM will first be given in relation to Fig. 18A, and then a more detailed description will be given in relation to Figs. 18B and 22 - 50. At the core of the system is a standard n x k random-access memory 52. This RAM is assumed to have an enable input EN, a read/write input R/W, e =
log2n address inputs ADDR0,...,ADDRe, and a k-bit-wide 25 bi-directional data bus DATA0,,DATA(k -1).
Multiplexers 54, 56 are used to isolate the RAM from the external environment during the execution of the self-test. Surrounding the RAM are the added BIST
sub-systems which are now described.
The BIST controller 58 sequences the operations of the BIST data path (sub-systems on the right-hand-side), receives internal status signals, and interfaces with external test control signals.
Eight states and two flip-flop flags, called test and 37 2~ 293Y~

done_read, are used to produce the required controller behavior, which is illustrated by the state diagram in Fig. 19. The controller behavior is described later in more detail.
The address generator (AG) 60 is a (log2n+1Og2k)-bit-wide up-counter in this implementation. The upper log2n bits from the AG form the word address (addr) that is used to address RAM
words, and the lower log2k bits form the bit number (bit_num) that is used to select a bit within the currently addressed word. The upper log2n bits could equally well be generated using a more compact linear feedback shift register (LFSR), a linear cellular automata register (LCAR), or any other (log2n)-bit-wide state machine with a maximum length exhaustive state sequence. A control input next_addr is used by the BIST controller 58 to increment the address generator 60. A status output last_addr is asserted by the address generator 60 when the last value of addr is reached in the count sequence.
The background counter (BC) 62 records the number dbgr of the data background currently being used, where 0 < dbgr < m-l and m is the total number of backgrounds present in the test. A control input next_dbgr is used by the BIST controller 58 to increment dbgr. A status output last_dbgr is asserted by the BC when dbgr = m-l. The current data background number dbgr is routed to the background code logic (BCL) 64, which is a combinational block that computes the binary value P of the (dbgr)th code bit for the (addr)th codeword, where addr is the current word address from the address generator 60.
A status signal P = N is asserted w~len bit P is equal 212939~

in value to the bit N of the (dbgr + l)st bit of the (addr)th codeword.
Fig. 20 illustrates an exemplary background code logic generator 64a that is used to generate the (n,2)-exhaustive code of length rlog2n1 + rlog2(1 +
rlog2nl)1 + 2. This code is required by the BIST
design to generate a near-deterministic test for detecting single 3-coupling faults. The block labelled Summing Logic 66 counts the number of 0s appearing in the word address addr. The two multiplexers 68, 70 are used to select the present background code logic bit P and the next code bit N
from among logic 0, logic 1 the bits of addr, and the bits of the binary number computed by the summing logic 66. An XNOR gate 72 is used to generate the P
= N status signal. Assuming a RAM cycle time of 100 ns, this self-test runs for 56 ms, 1.14 s and 21.4 s for n x 1 memories of size 4K, 64K and lM, respectively.
Fig. 21 illustrates a more complex background code logic generator 64b that generates an (n,3)-exhaustive code of length ([(log2n)])2 +
[(log]2n] + 2. This code is suitable for producing near-deterministic, transparent tests that detect single 4-coupling faults. The two left-most multiplexers 74, 76 select two single bit inputs to be routed to a 3-input XOR gate 78 that drives P; the third gate input to the XOR gate 78 is a signal, possibly the MSB of dbgr, that is 1 for the last m/2 data backgrounds. The two right-most multiplexers 80, 82 are used to produce the next bit N under control of the data background. To produce the next bit N, output from the multiplexers 80, 82 is supplied to XOR gate 79 along with the databackground. P and N are sent to 2129'39~

XNOR gate 81, which produces a signal indicative of P
= N, such that, in the case P = N, the next background code logic bit need not be updated, thus saving in computation. An all pairs generator 84 contains connections to all pairs of lines in the address addr.
Exiting the all pairs generator 84 are two buses 86, 88 that carry left and right members of each address bit pair to corresponding inputs of different multiplexers 74, 76, 80, 82. The resulting code is (n,3)-exhaustive. Assuming a RAM cycle time of 100 ns, this self-test runs for 486 ms, 13.5 s, 332 s and 126.3 min for n x 1 memories of size 4 K, 64 K, 1 M
and 16 M, respectively.
It is possible to reduce the size of the background code logic, at the cost of longer test time, by not providing circuitry dedicated to calculating the next background code logic bit N. The circuitry for calculating the current background code logic bit would then have to be used two separate times, to calculate P and then N.
Probabilistic tests result if the background code logic generators 64, 64a, 64b implement a hashing function that reduces the word address addr and data background dbgr down to a single bit P. A simple parity function would not be satisfactory for this application since the corresponding code matrix would be a checkerboard with only two distinct data backgrounds. A more suitable hashing function would be some prefix of either the (n,3)- or (n,4)-exhaustive codes. This way the data backgrounds wouldall be different from each other.
Referring to Fig. 18A, the test pattern generator (TPG) 90 produces k-bit-wide test data words that are written into the RAM 52 during the execution -~ 2129'~

of the BIST routine. In cases where a transparent test is applied to the RAM 52, the data bus must be bi-directional so that each new test data word can be derived by toggling bits in a data word previously read from the RAM 52. The test pattern generator 90 requires the current bit number bit_num from the address generator 60, and the current code bit P from the background code logic generator 64.
The response analyzer 92 contains a 16-bit multiple input feedback shift register (MISR), not shown, a 16-bit register, and a 16-bit comparator.
The MISR is used to compute the two signatures required in a transparent test. Data words must be bit-wise complemented before being input to the MISR
for all read operations that expect data complemented with respect to the originally stored data. A control input clrsig is used by the BIST controller 58 to clear the signature. The register is used to store the signature from phase 1 when a control signal load_reg is asserted by the controller. After the second signature is computed at the end of the test, the two signatures are compared. If they are the same, which would be the case in a good memory, then the PASS/FAIL status output signal is asserted high to indicate that the BIST routine detected no failures;
otherwise the signal is asserted low, and the RAM
under test may be discarded or repaired as desired. An alternative method for detection of cell coupling faults is to compare the values of each cell each time it is read with the cell content of a known perfect RAM.
Fig. 19 shows a simplified state diagram that specifies the behavior of the BIST controller 58 (not all signals have been shown). In normal ~1~93~

operation, the controller 58 remains in state S0 while system outputs BIST_BUSY and BIST_DONE are de-asserted. In state S0 the BIST RAM 52 behaves like a regular RAM accessible via the external address lines ADDR, the enable line EN, the read/write line R/W, and the k-bit-wide bidirectional data bus DATA. When system input START_BIST is asserted by the environment, the BIST controller 58 enters state S1 and begins executing the self-test routine, which is sequenced by states S1 - S6. While in these states, the BIST controller 58 asserts the system output BIST_ BUSY and disables externally initiated memory accesses.
The self-test routine computes a signature in each of two phases. Flip-flop test is cleared during phase 1 and set during phase 2. When test is cleared, the controller 58 is constrained to the three states S1, S3 and S5, which are states that generate only read operations. States S1 and S3 generate the read operations extracted from the marches, and state S5 generates the read operations extracted from the background changes. At the end of the first phase, load_reg and clr_sig are asserted in state S3 to store the signature and to clear the MISR in the response analyzer. Also, flag test is set to enable entry into states S2 and S4, which generate write operations.
In phase 2, the BIST controller 58 is constrained to states S1 - S6. States S1 - S4 generate the march sequences, while states S4 and S5 generate the background changes. As read and write operations are applied to the RAM 52, a second signature is computed by the MISR in the response analyzer 92.

2129'~

Once phase 2 of the self-test routine has com-pleted, the controller 58 enters state S7 and asserts the BIST_DONE system output while the response ana-lyzer 92 drives the PASS/FAIL signal to reflect whether or not the signature computed in phase 2 equals the signature computed in phase 1. The BIST
controller 58 remains in this state until the environment acknowledges by asserting the BIST_ACK
system input, whereupon the controller 58 returns to state S0 to re-enable normal memory operation.
There has thus been described a transparent BIST scheme that detects single V-coupling faults in RAMs. For the cases when V ~ {2, 3, 4}, it is possible to base the transparent tests on deterministic tests that have 100% fault coverage. The resulting transparent near deterministic tests have very high, but less than 100%, fault coverage because of the finite probability of aliasing inherent in the method.
Nevertheless, the defect coverage of the resulting tests is high because the probability of aliasing can be reduced by using longer signatures. To reduce the test time, it is possible to sacrifice fault coverage and base the transparent tests on the probabilistic tests for V-coupling faults obtained by constructing the tests using pseudorandom codes as opposed to (n, V-1)-exhaustive codes.
Area overhead resulting from the added BIST
circuitry is expected to be approximately 17% for a 64K RAM and under 2% for a lM RAM when using the (n, 2)-exhaustive code described earlier. As with most other BIST RAM designs, the overhead decreases with larger RAM sizes since the area of the BIST circuit grows slowly with RAM size. The precise overhead of the proposed scheme also varies depending on the code 2t 29~9~

generating circuit underlying the particular test. In general, larger values of V require more complex background code logic and hence lead to larger BIST
overhead.
5The BIST may also include means (not shown) responsive to an external signal to abort the BIST
routine at any time and safely restore the RAM data.
This would facilitate the periodic running of the BIST
routine in an on-line memory subsystem. There may also 10be means to provide more than one BIST routine to the user; for example, a relatively long (and extremely thorough) test and a relatively short (but less thorough) test may be provided according to a selection made by the user. The transparency property 15may also be sacrificed in favor of providing guaranteed 100% fault coverage; this could be done by using a deterministic BIST routine that overwrites the stored data.
The architecture of the proposed BIST RAM
20system is illustrated in Figure 18B assuming an 8K x 8 RAM size. The interface signals with the external environment, which are shown at the left side of Figure 18B, are as follows: The clk and clr signals are the system clock and system reset signals, 25respectively, that are routed to the various synchronous subsystems, including the BIST controller 58, the address generator 60, the background code logic 64, the background counter 62, the test pattern generator 90, and the response analyzer 92. When the 30 BIST RAM is operated in normal mode, inputs A12,,A0 supply the RAM address, input R supplies the read signal, input W supplies the write signal, and bi-directional signals DATA7,...,DATA0 convey 8-bit data words to and from storage cells in the RAM. The - 21293~g BIST RAM design shown may be modified to accept a read/write and an enable input rather than separate read R and write W inputs. The START_BIST input is asserted by the external environment to initiate the self-test routine. The BIST_BUSY output is asserted to inform the external environment that the self-test routine is currently executing and that normal RAM
read and write operations are disabled. The BIST_DONE
output is asserted by the BIST controller 58 to inform the external environment that the BIST routine has completed, and that normal RAM operation is still disabled until the BISTACK input is asserted. The PASS output, which originates from the response analyzer 92 as the pass signal, indicates whether or not the self-test routine detected a fault in the RAM.
At the core of the BIST RAM system shown in Figure 18B is an n x k random-access memory (RAM) 52.
This RAM 52 is assumed to have a read input RAM_R, a write input RAM_W, 13 address inputs RAM_Addrl2,...,RAM_AddrO, and an 8-bit-wide bi-directional data bus RAM_data7,..., RAMdataO. (The number of address lines and data lines must suit the size of the RAM 52.) Multiplexers are used to isolate the RAM 52 from the external environment during the execution of the self-test. Thus multiplexer I25 in Figure 18B selects the external read signal R from input pad I21 to be sent to the RAM 52 when the BIST
RAM is operated in normal mode, and selects the read signal read generated internally by the BIST
controller 58 when the BIST RAM is executing the self-test.
Surrounding the RAM 52 are the BIST
sub-systems which we now describe in turn. The BIST
controller 58 sequences the operations of the BIST

- 2129~

data path (sub-systems 60, 64, 62, 90, and 92 on the right-hand-side of Figure 18B), receives internal status signals, and interfaces with external test control signals. Eight states and two flip-flop flags, called phase2 and done_read, are used to produce the required controller behavior, which is illustrated by the simplified state diagram in Figure 19. The controller behavior is detailed later. The address generator 60 is a 16-bit wide counter in the current implementation (Note that here log_2 n +
log_2 k = log_2 8K + log_2 8 = 16). The upper log_2 8K
= 16 bits from the address generator 60 form the word address (Addrl2,...,AddrO) that is used by the RAM 52 to uniquely identify a word to be accessed, and the lower log_2 8 = 3 bits form the bit number (bit_num2,..,bit_numO) that is used by the background code logic 64, test pattern generator 90 and response analyzer 92 to identify select one bit within the currently accessed word. The address generator 60 could equally well be implemented using a more compact linear feedback shift register (LFSR) as in (Nicolaidis, ~Transparent BIST for RAMs,'' Proc. ITC, 1992, pp. 598-607), a linear cellular automata register (LCAR), or any other (log_2 n)-bit-wide state machine with a maximum length, exhaustive state sequence. A control input next_add is used by the BIST controller 58 to increment the address generator 60. Status outputs last_addr and alast_addr are asserted by the address generator 60 when the last value of Addr is reached in the count sequence.
Signal last_addr is the latched variant of signal alast_addr.
Figures 22, 23 and 24 provide internal details of the address generator 60. Figure 22 shows - 212~9~

how the address generator 60 is composed of a 16-bit synchronous address counter 100, a last address detection circuit 101, and a last address flag 102.
Counter outputs Q15,...,Q0 are the latched variants of asynchronous counter outputs aQ15,...,aQ0. Figure 23 shows how the address counter 100 is composed of four 4-bit counter slices 103, 104, 105, and 106. Counter outputs Q15,...,Q0 are separated into two fields:
field Q15,...,Q3 is used as the word address Addrl2,...,AddrO; field Q2,...,Q0 is used as the bit number bit_num. Figure 24 shows how the last address detection circuit 101 is constructed of NAND gates 107, 108, 109 and 110, and NOR gate 111. The output alast_addr of the last address detection circuit 101 is asserted as soon as the address aQ15,...,aQ0 is equal to the last total address (word address Addr concatenated with the bit number bit_num )of the RAM
52. For the example 8k x 8 RAM, the last address is given as a 16-bit binary number with all ls. The last address flag 102 is implemented as a D flip-flop.
The background counter 62, shown in Figure 25, records the number dbgr of the data background currently being used, where 0 <= dbgr <= m-1 and m is the total number of backgrounds present in the test.
In this example BIST RAM, m = 19. The control input next_dbgr is used by the BIST controller 58 to increment dbgr by enabling the count function of the background counter 62. The status output last_dbgr is asserted by the background counter 62 when dbgr = m, that is, when the last data background has been reached.
Figure 25 shows how the background counter 62 is composed of the background count state machine 112 and the last background detection circuit 113.

21 2939 ~i The last background detection circuit 113 monitors the data background dbgr and asserts the last_dbgr signal when dbgr reaches the last background m-1 = 18.
Figure 26 shows how the 5-bit background count state machine 112 is constructed using five D flip-flops 114, 115, 116, 117 and 118, and combinational next state logic implemented using standard logic gates.
Figure 27 shows how the last background detection circuit 113 is implemented using standard logic gates.
The background code logic 64 receives the word address Addr (and possibly also the bit number bit_num, as explained below) and produces the current background code logic bit P and the P=N and aP=N
status signals. Fig. 28 shows how the background code logic 64 is implemented. The signal aP corresponds to the value of the element at the (Addr,bit_num)-th column and the dbgr-th row of the underlying (n,V-1)-exhaustive matrix. By (Addr,bit_num) we mean the number obtained by concatenating the bits of Addr with the bits of bit_num. The signal aN corresponds to the value of the entry at the [((Addr,bit_num)+1) mod m]th column and the (dbgr)-th row of the underlying (n,V-1)-exhaustive matrix. Signals aP and aN are the unsynchronized variants of the current background code logic bit and the next background code logic bit, respectively. Output P is obtained by latching aP using D flip-flop 130. The signal aP=N is asserted as soon as it is determined by the comparator 122 that signals aP and aN have the same logic values.
The signal P=N is a latched variant of aP=N
implemented using D flip-flop 131. Multiplexer 132 is used to replace aP with aN at the input of D flip-flop 2129~9~3 130 when the control input next_dbgr is asserted, indicating the beginning of the next data background.
In the example 8K x 8 BIST RAM, the bit number bit_num is not shown communicating from the address generator 60 to the background code logic 64.
This will be the case when V-coupling faults are assumed not to involve different bits of the same RAM
word (the most general case is that different bits within the same RAM word can in fact be involved in the same V-coupling fault). The descriptions of aN
and aP in the preceding paragraph are for this case simplified by replacing all occurrences of (Addr,bit_num) with only Addr. The underlying matrix is also changed to be (n/k,V-1)-exhaustive rather than (n,V-1)-exhaustive. In the example 8K x 8 BIST RAM, the underlying matrix is thus (lK,2)-exhaustive.
Figure 28 shows how the background code logic is implemented for an 8K x 8 BIST RAM when testing for all 3-coupling faults, i.e., when V=3 and the matrix underlying the generated test is (lK,2)-exhaustive. The present bit logic 119 forms the current background code logic bit. Figure 29 shows how the present bit logic 119 is implemented in a straight- forward way using 2-to-1 multiplexers. The next bit logic 120 forms the next background code logic bit. Figure 30 shows how the next bit logic 120 is implemented using 2-to-1 multiplexers. The zero summing logic 121, which is required in this implementation of (n,2)-exhaustive codes, forms a binary number S3,...,S0 that expresses the number of 0 bits that appear in the address Addr. (If V-coupling faults can involve different bits of the same RAM word, then the zero summing logic 121 will determine the number of 0 bits that appear in the combined address (Addr,bit_num) obtained by concatenating the bits of Addr and bit_num.) The resulting signals S3,...,S0 are then input to the present bit logic 119 and the next bit logic 120.
Figure 31 shows how the zero summing logic 121 is implemented using four sumzero blocks 123, 124, 125 and 126, and adders slices 127, 128 and 129. The sumzero block, whose schematic is shown in Figure 32, uses combinational logic to determine the number of zeros present in a 3-bit section of the address Addr (or the combined address (Addr,bit_num)). The 2-bit adder slices 127 and 128 and the 3-bit adder slice 129 are all constructed using combinational logic gates.
Probabilistic tests result if the background code logic 64 implements a hashing function that reduces the address Addr (or the combined address (Addr,bit_numb)) and data background dbgr down to a single background code logic bit P. A simple parity function would not be satisfactory for this application since the corresponding code matrix would be a checkerboard with only two distinct data backgrounds. A more suitable hashing function would be some prefix of either the (n,3)- or (n,4)-exhaustive codes. However, other pseudo-random functions would also be satisfactory.
The test pattern generator 90 produces the k-bit-wide, in this example 8-bit-wide, test data words that are written into the RAM 52 during the second phase of the BIST routine. The data bus connection must be bi-directional so that each new test data word can be derived by toggling bits in a data word previously read from the RAM 52. The test pattern generator 90 also requires the present bit - ~12939~

number bit_num from the address generator 60, and the read and write signals from the BIST controller 58.
Figure 33 shows the implementation of the test pattern generator 90 in terms of a data register 134, a write bit flipper circuit 135, and tri- state drivers 136. The data register 134 is implemented as a stack of k = 8 D flip-flops, as shown in Figure 34.
Similarly, the tri-state drivers 136 are implemented as a stack of k = 8 single bit tri-state drivers, as shown in Figure 37. Figure 35 shows how the write bit flipper circuit 135 is implemented using a 3-to-8 decoder circuit 137 and a stack of k = 8 XOR gates.
The implementation of the decoder circuit 137 is given in terms of 2-to-1 muliplexers and an inverter in Figure 36. The write bit flipper circuit 135 inverts one bit in the data word reg_data according to the value of the bit number bit_num.
As illustrated in Figure 38, the response analyzer 92 contains a 16-bit multiple input signature register (MISR) 140, a 16-bit register 141, and a 16-bit comparator 142. The MISR 140 is used to compute signatures during each of the two test phases.
Data words must be bit-wise complemented before being input to the MISR for all read operations that expect data that is complemented with respect to the first current cell values. A control input load_reg is used by the BIST controller 58 at the end of phase 1 to load the register 141 with the first signature, and to clear the MISR 140 to prepare it to start calculating the second signature during phase 2. At the end of phase 2, the first signature stored in register 141 is compared by the 16-bit comparator 142 with the second signature stored in the MISR 140. If the two signatures are equal, then the pass is asserted high 2129~9~) to indicate that the self-test routine detected no failures; otherwise the pass signal is asserted low to indicate that an error was detected.
When the response analyser 92 is accumulating the signature in MISR 140 during phase 1, the data bits read from the RAM 52 must be selectively inverted using the elements of the (lK,2)-exhaustive code so that, in a fault-free memory, the modified data words read into MISR 140 during phase 1 are the same as the unmodified data words passed directly from the RAM 52 to the MISR 140 during phase 2. This operation ensures that the signatures calculated during phases 1 and 2 will be the same in a fault-free memory. The selective inversion operation is accomplished using the read bit flip enabler 138. The outputs inv_B7,...,inv_B0 from the bit flip enabler 138 are used to control the read data selector 139.
The structure of one bit slice of the the read data selector 139 is given in Figure 41. (The 8k x 8 BIST
RAM example requires eight instances of the slice in Figure 41.) When the phase2 signal is asserted by the BIST controller 58 during phase 2 of the test, the 2-to-1 multiplexer 188 passes the RAM data word unchanged to the bus lines B7,...,B0 that lead to the MISR 140. When the phase2 signal is de-asserted by the BIST controller 58 during phase 1 of the test, the 2-to-1 multiplexer 188 selects the output of the second 2-to-1 multiplexer 187. Multiplexer 187 and inverter 186 act together as an XOR gate. The signals inv_B7,..., inv_B0 from the read bit flip enabler select the bits in data7,...,dataO that are to be inverted before being passed on to the MISR 140.
The implementation of the read bit flipper is illustrated in Figure 39. The position of the 2123~

current bit within the current RAM word is decoded by the 3-to-8 decoder 143. XOR gates 145, 146, 147, 148, 149, 150, 151 and 152 are connected to the outputs of decoder 143 and the current background logic code bit P so as to form a mask pattern M7,...,M0 used in state S3 of the BIST controller 58. (State S3 controls the second reads in the march sequence.) If P = 0, then exactly one of M7,...,M0 is 1; if P = 1, then exactly one of M7,...,M0 is 0. XOR gates 170, 171, 172, 173, 174, 175, 176 and 177 are connected to the outputs Q7,...,Q0 of the invlog2 circuit 144 and the current background code logic bit P to form the mask pattern T7,...,T0 that is used in state S5 of the BIST
controller 58. (State S5 controls the reads during the background change operation.) The invlog2 circuit, illustrated in Figure 40, produces an 8-bit wide bit pattern consisting of bit_num ls followed by (8 - bit_num) 0s. This pattern allows a left-justified block of bits in the current RAM data word to selected to be inverted by the XOR gates 170, 171, 172, 173, 174, 175, 176 and 177. In the read bit flip enabler 138, NAND gates 153, 154, 155, 156, 157, 158, 159 and 160 are used to unmask bits M7,...,M0 whenever the BIST controller 58 enters state S3.
Similarly, NAND gates 178, 179, 180, 181, 182, 183, 184 and 185 are used to unmask bits T7,...,T0 whenever the BIST controller 58 is in state S5. NAND gate 161 asserts an active low signal Sl_flip whenever the BIST
controller is in state S1. (State S1 controls the first reads in the march sequence.) Finally, NAND
gates 162, 163, 164, 165, 166, 167, 168 and 169 are used to OR together (a) M7,...,M0 and (b) T7,..., T0 and (c) eight copies of Sl_flip to create the bit flip signals inv_B7,...,inv_B0.

212939~

Figure 42 shows an implementation of the 16-bit multiple input signature register MISR 140 using D flip-flops and XOR gates. Figure 43 shows the implementation of the 16-bit register 141 using 16 D
flip-flops. Figure 44 shows an implementation of the 16-bit comparator 142 that uses XOR gates 189,...,204 to detect any bit differences between the MISR 140 outputs A (that is, the second signature) and the register 141 outputs Q (that is, the first signature).
NOR gates 205, 206, 207 and 208, NAND gate 209, and inverter 210 together form a 16-input OR gate that receives the bit difference signals diffl5,..., diffO
and generates the pass output.
Figure 19 shows a simplified state diagram that specifies the behavior of the BIST controller 58 (not all signals have been shown). (The full state diagram is shown in Figure 45 in standard state diagram notation.) In normal operation, the BIST
controller 58 remains in state S0 while system outputs BIST_BUSY and BIST_ DONE are de-asserted. In state S0 the BIST RAM behaves like a regular RAM accessible via the external address lines A, the enable line EN, the read/write line R/W, and the data bus DATA. When system input START_BIST is asserted by the environment, the BIST controller 58 enters state S1 and begins executing the self-test routine, which is sequenced by states Sl,...,S6. While in these states, the BIST controller 58 asserts the system output BIST_BUSY and disables externally initiated memory accesses.
The self-test routine computes a signature in each of two phases. Flip-flop phase2 is cleared during phase 1 and set during phase 2. When pha8e2 is cleared, the BIST controller 58 is constrained to the 212939~

three states S1, S3 and S5, which are states that generate only read operations. States S1 and S3 generate the read operations extracted from the marches, and state S5 generates the read operations extracted from the background changes. At the end of the first phase, load_reg and clr_s:ig are asserted in state S3 to store the signature and to clear the MISR
in the response analyzer. Also, flag phase2 is set to enable entry into states S2 and S4, which generate write operations.
In phase 2, the BIST controller 58 is constrained to states Sl,...,S6. States Sl,...,S4 generate the march sequences, while states S4 and S5 generate the background changes. As read and write operations are applied to the RAM 52, a second signature is computed by the MISR in the response analyzer 92. Once phase 2 of the self-test routine has completed, the BIST controller 58 enters state S7 and asserts the BIST_DONE system output. Meanwhile, the response analyzer 92 drives the PASS signal to reflect whether or not the signatures computed in the two phases are equal. The BIST controller 58 remains in this state until the environment acknowledges by asserting the BISTACK system input, whereupon the BIST
controller 58 returns to state S0 to resume normal memory operation.
Figure 46 shows the internal structure of the BIST controller 58. The control path 211 produces the state signals A, B and C that are sent to the response analyzer 92. The control path 211 also produces the control signals next_add, next_dbgr, load_reg, read and write that are used in subsystems 60, 64, 62, 90 and 92. The datapath8kby8 circuit 212 generates the additional outputs BIST_DONE, BIST_BUSY

212939~

and phase2. Figure 47 shows how the control path 211 is in turn composed of next state logic 213, output logic 214, and eleven D flip-flops. The flip-flops drive the state bit signals A, B and C, the data path control signals next_addr, next_dbgr, load_reg, read and write, and the signals clear_read, latch_read and BIST_DONE. Figure 48 shows how the output control 214 is implemented using combinational gates and 2-to-1 multiplexers. Similarly, Figure 49 shows how the next state logic 213 is implemented using combinational gates and 2-to-1 multiplexers. Figure 50 shows how the datapath8kby8 circuit 212. The phase2 signal is driven by D flip-flop 213. The doneread signal is implemented using a set-reset latch 214. Thus doneread can be asynchronously set by latchread and asynchronously reset by clear_read. The control interface signals BIST_ BUSY and BIST_ DONE are in turn implemented using S-R latches 215 and 216, respectively.
A person skilled in ~he art could make immaterial modifications to the invention described and claimed in this patent without departing from the essence of the invention.

Table 1: Pin Descriptions ? 1 2 Q ~ ~ Q 56 Syrr~ol PinType Name and Function Ai~DR0-23 Output RANi UNDER TEST (RUT) ADDRESS: The RUT address lines are output from these pins. An address is valid only when the WAIT slgnal Is bw.
PADDR0-17 O PROM ADDRESS: The present look-up PROM address is selected by these lines.
PDATA0-15 Input PROM DATA: The 1 6bn PROM data is retumed to the chip via these lines.
TESTW I TEST SELECTION: One of 32 possible tests is selected by setting these lines to the correct state upon test start-up.
CLOCK I SYSTEM CLOCK: Ail intemal ciocking in the sequencer chip is derived from this signal. The CLOCK signal should be a 50% duty cyde free-running signal. A maximum frequency of 36 MHz is aliowed.
TMODE I TEST MODE SELECT: When asserted this pin places the chip in self-test mode. In test mode, scan chain data can be shrfted out of the chip, as new data is scanned in. This pin disables the nomlal cbcking of the chip, and enables the intemal test ciock.
ENABLE I CHIP ENABLE (PAUSE): While this pin is asserted (high), the chip is operational. If the pin is set iow, chip operation is haited at the next falling edge of the CLOCK line. Operation can be restarted by ~assening ENABLE.
RESET I CHIP RESET: This signal plàces the chip in ns initial start~up mode. The reset procedure is described later in this document.
SDI I SERlAi TEST DATA INPUT: Scan chain data is serially read in from this pin.
SDO O SERIAL TEST DATA OUTPUT: Scan chain data is serially driven ou~ from this pin.
DATA O RUT DATA BiT: The data which is to be compared to the data out-put from the RUT or written to the RUT is output on this pin. DATA
is only valid when the WAIT line is low.
OK O CHIP OK: When the chip completes a test, OK is asserted (hlgh) if the intemal signature register value matches the expected value as stored in the PROM look-up table. Otherwise, OK rernains deasserted.
DONE O TEST DONE: When the chip has finished sending test data, this line is asserted. At this point, the chip rernains in a wait state until it is reset in prepa,ttion for the next test.
R/W O RUT R/W: This line is high when the RUT is to be read, and is iow when the RUT Is to be written. The value of this pln Is only valid when the WAIT line Is active.
WAIT O IGNORE CURRENT RUT DATAIADDRESS: This pin informs the rest of the tes~er system that the sequenoer chip RUT outputs are currently invalid. This Is enher caused by chip reset and start-up, by the end of a test sequence, or if the chip Is unable to provide an RUT opert~lon for that ciock cycle.
VDDcore I CHIP CORE POWER

GNDoore I CHIP CORE GROUND
VDDring I CHIP RING POWER: The ring power supplies to the chip pads.
These are i"depenaierlt of the core power.
GNDrin~ I CHIP RING GROUND: The ring ground supplies to the chip pads.
These are Inci~p6nd~,lt of the core ground.

Table 2: Descriptlon of Code Location Record Fieæ~ 2 ~ 3 9 ~ 57 Field Name Description AXRUTADDR0-23 This field contains the largest RUT address; i.e., one less than the number of words in the RUrs address space.
TARTADDR0-17 This field contains the PROM address of the first word of the code to be used as the basis of test i. This is the start-ing address of the base matrix.
AXBGNUM0-10 This field contains the value of the largest background number, which is equal to one less than the length of the code. This value will be used to determine how many backgrounds are in each zone of the final test sequence.
BLKSIZE0-10 The BLKSIZE is the difference in the PROM addresses of adjacent bits within a codeword.
OFFSET0-10 This field holds the value of the offset into the code used when the chip is used in parallel mode. If the sequencer chip is used in stand-alone mode (as opposed to parallel mode) this field is all zeros. ~
MAXWORD0-10 This is the largest word offset from the STARTADDR that is to be used in the code. ~
VBIT If the VBIT is set to zero, then the test will contain 3 zones(when tests for 4-coupling faults are being generated).
Otherwise, if VBIT is set to one, then the test will contain 5 zones (when tests for 5-coupling fauHs are being gener-ated).
MAXBITNUM0-4 The is the maximum bit number in a word (1,2,,31 which is always one less than the total number of bits per word) of the RAM under test. This field is not used in stand-alone mode.
SIGNATURE0-15 The signature register value corresponding to an error-free generation of the stored test is kept in this field. This value is compared to the resulting signature after a test is completed to help determine if the sequ~ncer chip is per-forming properly.
MYBITNUM0-4 This field contains the bit number in the word space of the RUT that is being tested by this chip. That is, if there are 8 bits per RUT word, this chip could be testing any of the bits between 0 and 7. Seven other chips would also be needed to test the other bits in parallel. This field is only used in parallel mode.
~ The OFFSET field is used to determine the beginning offset address into a block which is to be used by the chip. Consider the example shown below in figure 9. The example shows locations for OFFSET and MAXWORD for a PROM that is for the bit 1 sequencer chip. A single block must be long enough to be divided equally into K parts, with no over-lapping of sub-blocks. The OFFSET field defines the beginning of the sub-block that is to be used by the chip in question.
~ The MAXWORD field defines the end of the sub-block that is to be used by the chip.
The sub-block size should be the same for each generator in the parallel system.

212~3~ 58 Table 3: Main Controller Slgnal Descrlptlons.
Symbol Typ~ Nameand Function SDI CLOCK inputs Seetable1.
TMODE from pads ENABLE
RESET

STARTINIToutput to START INlTlALiZE: Signals the PAG to begin initializing its registers.
PAG
TOPPRESCOLoutput to TOP OF PRESENT COLUMN: Signal to the PAG that it is to fetch PAG the data for the top of the present column in the test matrix.
TOPNEX~COLoutput to TOP OF NEXT COLUMN: Signal to the PAG that it is to fetch the PAG data for the top of the next column in the test matrix.
TOPFIRSTCOLoutput to TOP OF FIRST COLUMN: Signal to the PAG that it is to fetch the PAG data for the top of the first column of the current zone in the test matrix.
LASTZONECOLinput from LAST ZONE COLUMN: Status signal from the PAG indicating that it PAG is in the last column of the current zone.
FIRSTZONECOL- input ftom FIRSTZONE COLUMN: Status sbnai from the PAG Indicatlng that it PAG is in the first column of the current zone.
LASTCOL input from LASTCOLUMN: Status sbnaifrom the PAG i~ii~tl~ that a Is inthe PAG last coiumn of the test rnatrk.
TESTOUT output to SERiAi TEST DATA OUTPiJT: Scan chain data is serialiy output PAG from this iine.
INIT output to INlTlALiZE: Inciicates thatthe PAG is to ~ene~te the aW~es5es of PAG the code bcatbn recorci information polnted to by the TEST lines.
RDY input from READY: Status signai from the PAG inciicating that the PROM data PAG can be iatched and that the PAG can be requesteci to gene~le another PROM acidress.
QRDY input from QUEUE READY: Status signai ftom the DQ Inciicating that H is ready DQ to generate another bit of RUT ciata N output NEXT BiT: When this line is asserted by the MC the DQ will try to from DQ ~ene-~td anotherdata bK forthe RAG abng with tile cbnt7sponci~r~
amount to Increment the RUT aciciress.
DI FF input from DIFFERENT: Status signai from the DQ that inciicates whether the DQ curtent data bit is dil~e.t:nl ftom the same bit In the prevbus bac~-ground.
INV output to I~VERT DATA BIT: Output tells the DQ to Invert the present data bit.
DQ
SKIP output lo SKIP MODE: Output that enabies sidpplng In the DQ.
DQ
P/W output to READ/WRITE: This line indtcates to the RAG what type of test vector RAG operation to output either a read or a write.
ALLONES output to INlTiALiZE RUT ADDRESS: Assetted to request that the RAG reset RAG the RUT address counter.

21:~3~) Table 3: Maln Controller Slgnal Descrlptlons.
SyrnbolType Name and Functbn LASTRUTADDR ~nput from LAST RUT ADDRESS: If the RAG has baded an address which is RAG ~reater than or equal to the iargest RUT address, thls status line is assert~d.
WAIT output to WAIT: ThTs signal Is asserted when the MC votes for the external RAG WAlr slgnal to be asserted. The MC's request for a WAiT state can be ove,.ldcien by the RAG.
DONE output to TEST DONE: When the MC finds that the current test is completed, RAG thls signal is asserted and lefl 10r the RAG to output to the pads.
LDREGO-7 output to LOAD PROM REGISTER: These eight lines are sk-gnals that indicate RAG, DQ, which code location record address is valid on the PDATA lines. For PAG exarnple, when LDREGO is high, data from the first iocation in the code location record can be baded dufing that clock period.-TCLKI from Ci K TEST CLOCK: Gbbai network output for the test rnode clock.
GEN
CLKI from CLK GLOBAL SYSTEM CLOCK: Giobal network output for clock. (single GEN edge ciocking scheme) CLRI global net GLOBAL CLEAR: Globai network signal to dear all re~;ster~ (all clear operdl.ons done synchronous~

\~C~ ~C1d Table 4: PROM Address Generator Slgnal Desui~t~
Symbol Type Name and Function GO input from FETCH NEXT ADDRESS: The DQ asserts this line when it has DQ latched the current word and is requesting another to be fetched by the PAG.
STOPBIT0-3outputs to STOP BIT LOCATION: These lines indicate to the DQ which bit in DQ the current worci Is the last valid bit of the word.
BITOFFSET0-2outputs to BIT OFFSET VALUE: These nnes indicate to the DQ which bit In the DQ current word is the fir~t valid ba of the word.
FLUSH output to FLUSH QUEUE: When the PAG shffls to top of a column, or is initial-DQ izeci, 1t asserts the FLUSH slgnal which inciicates that the DQ should jump to Ite initial state.
TEST0-4, inputs See table 1.
PDATA0-15,from pads ZONE0-4 outputs to ZONE: Status lines which inciicate to the RAG which zone of the test RAG matrk that the PAG is in.

Table 5: Data Queue Slgnal Descrlptlons.
Symbol ~ype Name and Function RUTINC output to RUT ADDRESS COUNTER INCREiviENT: This siqnal is asserted RAG when the RAG is to ~ r"ern its RUT address counter by the amount indicateci bylhe RUTADDRINC lines.
RUTADDRINC0-2output to RUT ADDRESS INCREMENT VALUE: These lines hold the RAG amount that the RUT address counter is to be incremente~ by.
PDATABIToutput to PROM DATA BIT: This line is used to send the data bit for the cur-RAG rent test vector being referred to by the DQ. The RAG uses this l,d~.n"~lion when it outputs the test vector to the pads.

Table 6: RUT Address Generator Internal Signal Descriptions.
Symbol Type Name ar~ Function ADDR0-23~,outputs to See table 1 WAlr, RNV-, pads PDATABlr OK, DONE, SDOoutputs to See table 1.
pads These signals are combined to form cun ent the test vector.

Claims (30)

THE EMBODIMENTS OF THE INVENTION IN WHICH AN EXCLUSIVE
PROPERTY OR PRIVILEGE IS CLAIMED ARE DEFINED AS
FOLLOWS:

1. A method of testing a random access memory (RAM) having n cells, each cell being identified by an address, for single V-coupling faults where n V 2, the method comprising the steps of:
establishing a first current value for each cell;
for each cell and for each of m data backgrounds, generating a background code logic bit corresponding to an element of an (n, V - 1)-exhaustive matrix;
for each of m data backgrounds;
(1) applying a sequence to each cell as follows:
(a) reading the current value of the cell, (b) writing to the cell a logical function of the background code logic bit and the first current value of the cell;
(c) reading the cell to determine the value of the cell after the writing operation in step b;
(d) writing the complement of the value of the cell determined in step b to the cell; and (2) for each background except possibly the mth background, updating the current value of all cells according to the background code logic bits corresponding to that cell;
reading each cell of the RAM; and discarding or repairing the RAM if a cell coupling fault is apparent from the series of values read from the cells of the RAM.

2. The method of claim 1 in which generating a background code logic bit corresponding to an element of an (n, V - 1) - exhaustive matrix includes:
initially constructing an (n0, V - 1)-exhaustive matrix where n0 n, the matrix having n0 rows and m0 columns; and constructing at least a portion of the (n, V - 1)-exhaustive matrix from the (n0, V - 1)-exhaustive matrix.

3. The method of claim 1 in which the logical function is for each cell a bit corresponding to the complement of the element of the (n, V - 1)-exhaustive matrix irrespective of the current value of the cell.

4. The method of claim 2 in which detection of cell coupling faults is carried out at the time each cell is read by comparison with cell content of a known perfect RAM.

5. The method of claim 2 in which the logical function is an exclusive-or of the complement of the background code logic bit and the first current value of the cell.

6. The method of claim 5 in which detection of cell coupling faults is carried out by comparing values read from the cell at different parts of the test where the same value should be returned in a good memory.

7. The method of claim 2 in which generating a bit corresponding to an element of an (n, V - 1) -exhaustive matrix includes row rotating the stored (n0, V - 1)-exhaustive matrix according to the background and cell address.

8. The method of claim 7 in which generating a background code logic bit corresponding to an element of the (n, V - 1)-exhaustive matrix includes:
integer dividing the background by m0 to produce a value i;
integer dividing the cell address by n0 to produce a value j; and row rotating the (n0, V - 1) matrix by the product of i and j modulo n0.

9. The method of claim 1 in which generating a background code logic bit corresponding to an element of an (n, V - 1)-exhaustive matrix includes:
pseudo-randomly selecting a background code logic bit.

10. The method of claim 9 in which pseudo-randomly selecting a background code logic bit includes selecting the background code logic bit from the address of a cell, logical 0 and logical 1.

11. The method of claim 9 in which pseudo-randomly selecting a background code logic bit includes selecting the background code logic bit from a hashing of the address of the cell.

12. The method of claim 11 in which pseudo-randomly selecting a background code logic bit includes selecting the background code logic bit under control of the data background.

13. The method of claim 11 in which the logical function is for each cell a bit corresponding to the complement of the element of the (n, V - 1)-exhaustive matrix irrespective of the current of the cell.

14. The method of claim 11 in which detection of cell coupling faults is carried out at the time each cell is read by comparison with cell content of a known perfect RAM.

15. The method of claim 11 in which the logical function is an exclusive-or of the complement of the background code logic bit and the first current value of the cell.

16. The method of claim 11 in which hashing the address of the cell includes summing bits in the address.

17. The method of claim 11 in which the hashing of the address of the cell includes:
forming the XOR of at least two address bits.

18. The method of claim 17 in which forming the XOR of at least two address bits includes:
generating bit pairs in the address of the cell, each bit pair including a left bit and a right bit;

applying the left bit, logical 0 and the cell address to a first multiplexer having a first output;
applying the right bit, logical 0 and the cell address to a second multiplexer having a second output; and applying the first output and the second output to an XOR gate.

19. The method of claim 18 in which the first and second multiplexers are controlled by the data background, and a hashing of the data background is also applied to the XOR gate.

20. Apparatus for testing a random access memory (RAM) having n cells, each cell being identified by an address, for V-coupling faults where n V 2, the apparatus comprising:
a PROM containing background code logic bits corresponding to an (n0, V - 1)-exhaustive matrix where n0 n, the matrix having n0 rows and m0 columns;
and generator means to generate a background code logic bit corresponding to an element of an (n, V - 1)-exhaustive matrix on the fly from the background code logic bits in the PROM and to selectively apply the generated background code logic bit to the RAM.

21. The apparatus of claim 20 in which the PROM
forms a replaceable element separate from the generator means.

22. The apparatus of claim 20 further including multiple PROMS arranged in parallel.

23. The apparatus of claim 20 in which the generator means includes means to row rotate the stored (n0, V - 1) -exhaustive matrix according to the cell address.

24. The apparatus of claim 23 in which the generator means includes means to integer divide the background by m0 to produce a value i; integer divide the cell address by n0 to produce a value j; and row rotate the (n0, V - 1) matrix by the product of i and j modulo n0.

25. Built in apparatus for testing a random access memory (R) having n cells, each cell being identified by an address, for single V-coupling faults where n V 2, the apparatus comprising:
a RAM;
a RAM address generator;
a background code logic generator connected to receive RAM addresses from the address generator and having pseudo-random background code logic bit output;
a test pattern generator connected to receive RAM addresses from the RAM address generator and connected to receive output from the background code logic generator and having test pattern output forming an (n, V - 1)-exhaustive code including m data backgrounds for each cell of the RAM;
a controller for sequentially writing the test pattern output to the RAM and reading the cells of the RAM; and a response analyzer connected to receive the read content of the cells of the RAM.

26. The apparatus of claim 25 in which the background code logic generator includes:
means to select the background code logic bit for application to a cell from a hashing of the RAM address of the cell.

27. The apparatus of claim 26 in which the means to select the background code logic bit is responsive to the value of the data background.

28. The apparatus of claim 26 in which the means to select the background code logic bit forms an XOR
of at least two address bits.

29. The apparatus of claim 26 in which the means to select the background code logic bit includes:
an all bit generator for generating all bit pairs in the address of the cell, each bit pair including a left bit and a right bit;
a first multiplexer having a first output, the first multiplexer being connected to receive the left bit, logical 0 and the cell address;
a second multiplexer having a second output, the second multiplexer being connected to receive the right bit, logical 0 and the cell address; and an XOR gate connected to receive the first output and the second output.

30. The apparatus of claim 29 in which the first and second multiplexers are controlled by the data background, and a hashing of the data background is applied to the XOR gate.