Abstract:
Apparatus consisting of combinations of interconnected logic elements for generating preselected sequences of addresses for the listing of a matrix memory as a function of preset constants and variable timing impulses, wherein there are first and second X and Y address generators with controlled selection means for selecting the first or the second of the X and Y address pairs, each of the address generators being settably controllable to generate a preselected sequence of addresses in ascending or descending order, with settable increments within the sequence, settable masking, and settable displacements from a fixed reference origin.

Description:
DESCRIPTION 
     1. Technical Field 
     This invention relates in general to logic circuits and more specifically to logic circuits for producing any one of a plurality of sequences of addresses for use with an apparatus for testing the operation of a memory. 
     2. Background Art 
     It has been found that intermittent malfunctions of very large scale integrated circuit memories occur when the memories are installed in data processing equipment and subjected to certain sequences of memory operations. Since these malfunctions are application sensitive, studies have been made of typical memory failure modes leading to the design of test protocols that can be economically employed on the production line. 
     One such study is reported in an article entitled &#34;Selecting Test Patterns for 4K Rams&#34; by Wayne E. Sohl, which was published in the IEEE Transactions on Manufacturing Technology, Vol MFT-6, No. 3, September 1977, beginning on page 51. 
     As discussed in that article, very large scale integrated (VLSI) circuit memories are subject to various failure modes which are set forth in tabular form and correlated with the various test protocols designed to test for the faults, some of which protocols will detect more than one fault. The relativity of the test times of each of the test protocols is set forth as a ratio compared with the longest test, wherein the test time factor is 2(2N 2  +N), where N is the number of test cells. For a 4K memory the article computes the number of test iterations as 67,117,056 cycle points. 
     It will readily be appreciated that the number of cycle points required to test a larger memory, i.e. 16K, becomes extremely large (1.17×10 9 ). If the testing frequency is too slow, the test time becomes prohibitively long to be used for one hundred percent production testing. Therefore, the test protocols must be chosen to utilize the minimum number of cycle points to detect the potential faults and the frequency of the test equipment must be as high as possible. 
     An apparatus for testing memories according to the protocols discussed in the above-identified publication is described in U.S. Pat. No. 3,751,649 issued Aug. 7, 1973 to Thomas William Hart. That apparatus is primarily controlled by a stored program which gives it great flexibility to adopt to a variety of memory configurations and test protocols. 
     However, as memories become larger the requirements for storage capacity in memory become prohibitively large so as to preclude the use of small computers and microprocessors. Also, the use of memory to store instructions that require frequent repetitive access slows the effective frequency of the apparatus and so prolongs the test time as to be unacceptable for production purposes. 
     The generation of address sequences is one the principal areas that have heretofore required frequent repetitive access to memory to determine which cells in the memory should be next addressed for testing. However, examination of the address sequence of the various protocols reveals that the sequences obey fixed arithmetic progressions, which, although differing among the various test protocols obey fixed rules within any one protocol. This commends the use of combinations of logic elements which can be preconditioned to generate the required address sequences with a minimum of inputs and controls from the controlling computer&#39;s memory. 
     OBJECTS OF THE INVENTION 
     With the foregoing desiderata as a goal, it is therefore an object of this invention to provide combinations of digital logic circuit elements which may be preconditioned by the entry of predetermined data thereinto and operable responsive to patterns of timing pulses to generate a desired sequence of numerical values for controlling the addressing of a memory under test. 
     Yet another object is to provide an address generating apparatus having a plurality of identical combinations of logic instrumentalities which are operative in combination to selectively produce address sequences for the whole or any selected area of a matrix. 
     These and other objects, features and advantages of the invention will be apparent from the following more particular description of the preferred embodiment of the invention as illustrated in the accompanying drawings. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic of the interconnection of the combination of elements shown in FIG. 2. 
     FIG. 2 is a schematic of the combination of logic elements necessary to produce a desired sequence for one coordinate address of a matrix. 
    
    
     THEORY OF OPERATION 
     Before describing the preferred embodiment it is expedient to digress and define some terms, and examine the arithmetic rules that govern the production of the desired sequences of addresses. 
     The memories for which this apparatus is particularly adapted to address for test purposes are two dimensional matrix memories. Thus, each cell or memory position can be defined by the coordinates of its position in the matrix. The memory matrix size is usually 2 n  ×2 m  where n and m are integers. With these dimensions the X and Y addresses may conveniently be encoded by means of 2 n  -1 and 2 m  -1 binary bits. The addresses of the cells in a row of the matrix run from 0 to 2 n  -1, and the column cells from 0 to 2 m  -1. Thus memories commonly called 2K, 4K, 16K, etc. actually contain 2 11 , 2 12 , and 2 14  cells, respectively. These may be organized in a square or rectangular matrix so long as the both dimensions are an integral power of two. 
     The geometry of the memory and the restriction on the dimensions of the matrix to integral powers of two make it convenient to employ combinations of simple binary logic elements to develop any desired sequence of memory addresses. 
     These addresses may be incremented or decremented by any desired fixed amount. They may be masked to prevent an address from exceeding a predetermined value, and if desired, repeating the sequence of values up to the value of the mask. Addresses may be offset by the addition of a constant to the sequence of base addresses so as to direct the testing to an area of the memory displaced from the origin by the value of the constant. Also the testing may be so controlled to alternate between cells obeying one sequence and cells obeying a second sequence. 
     DECREMENTING 
     To decrement a sequence of ascending binary values one need only to logically EXCLUSIVE OR each binary bit in the ascending binary value series with all binary 1&#39;s. This will cause the derived series of binary numbers to decrease in value. For example, the ascending numerical series 000(0); 001(1); 010(2) . . . 111(7) will yield the descending series 111(7); 110(6); 101(5); . . . 000(0). If this were extrapolated to the full capacity (16 bits) the decremented addresses would be decremented starting with the maximum value of the sixteen bits. However, because of the binary nature of the values, those derived binary values in the descending sequence which exceed the maximum address of the memory under test can be rendered ineffective by masking. 
     MASKING 
     Masking involves combining each binary bit in the desired address in a logical AND function with the binary bits representing that binary address beyond which further addressing is blocked. For example if it is desired to limit addresses to no greater than 111(7) the addresses from 000 through 111 would be reproduced without change. However, when the next count of 1000 is ANDED bit-by-bit with 0111, the derived address will be 000 and the sequence 000 through 111 will be repeated for all binary values greater than 1000. 
     HOME AND AWAY ADDRESSES 
     A further relationship which is exploited is the so-called &#34;home&#34; and &#34;away&#34; address. This permits a testing sequence wherein one memory cell (the &#34;home&#34; cell) may be repeatedly interrogated alternating with a succession of &#34;away&#34; cells. The &#34;home&#34; cell is then advanced to a new cell and alternately tested with a new succession of &#34;away&#34; cells. The succession of both the &#34;home&#34; and &#34;away&#34; cells may be either an ascending or descending series which may be incremented by any integral amount. If the &#34;home&#34; cell lies in the middle of an array, the succession of &#34;away&#34; cells will on occasion include cell addresses greater than the memory capacity. Through masking the &#34;away&#34; cell addresses will increase to the maximum return to zero and then approach the &#34;home&#34; cell by means of an increasing succession of lesser addresses. For example, if there were a linear array of 64 cells and the &#34;home&#34; cell had an address of 31, the succession of &#34;away&#34; cells would run from 32 to 63 followed by 0 through 30, the masking at 64 preventing access to a nonexistent cell and returning the series to 0. 
     OFFSET 
     A final relationship is the &#34;offset&#34; feature. This allows the same relative succession of cells to be tested in any desired area of the memory by adding a constant to the X and Y addresses, the constant being the X and Y displacement of the area under test relative to the origin (X=0, Y=0) of the memory matrix. The &#34;offset&#34; feature also permits the alternating testing of a succession of cells occupying the same relative geometric position in two different areas of a memory. This is usually reserved for exercising sense amplifiers which are shared by a plurality of memory cells. 
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The specific test protocol chosen for any given memory is dictated by the potential fault sought to be detected and the size and geometry, including the disposition of sense amplifiers, of the memory. The address generator now to be described is preset with the necessary parameters of a constant for changing the address, whether the constant is to be effective additively or subtractively (increment/decrement), the starting point for the numerical series (base address), and the selection of the area to be tested. This is effected individually for each of the X and Y addresses. The relative times at which the addresses are changed are controlled by external cycle counters which are also preset for the desired test. 
     In FIG. 1 four identical address generators A, B, C and D are shown schematically, each of which is constructed in accordance with the component arrangement of FIG. 2. Inputs to the A, B, C and D units are multi-wire cables 90A, 90B 90C and 90D the individual wires, or multi-bit cables, of which are identified in detail in FIG. 2. 
     All of the logic units employed in FIG. 2 are standard commercially available items, which in the preferred embodiment were obtained from Texas Instruments Incorporated, whose catalogs and technical bulletins may be referred to for detailed descriptions. Each unit will be identified as TI plus its type number. Equivalent functional units from other sources may of course be substituted. 
     The A and B units are used to generate the X addresses, and the C and D units are used to generate the Y addresses. The A and C units produce the &#34;home&#34; addresses and the B and D units produce the &#34;away&#34; addresses. Selection of the &#34;home&#34; or &#34;away&#34; addresses is controlled by the selection units 50 (for X) and 60 (for Y) under control of an appropriately timed potential on line 55. Each of the selection units, 50 or 60, is the solid state equivalent of a 16 pole double-throw relay which has the capability of selecting 16 bits of a &#34;home&#34; or &#34;away&#34; address in the X and Y directions. 
     With this capability it will be intuitively appreciated that given the appropriate preset data and timing pulses any cell in a memory can be accessed in a desired sequence. 
     In FIG. 2 the units 61, 62, 63 and 64 consist of four four-bit buffer storage units which when strobed with an appropriate timing pulse are receptive to receive and store a total of 16 bits of binary data and to produce a corresponding composite 16 bit output. Typical of these is TI type Ser. No. 74S175. Units 67 and 68 contain four arithmetic logic units (ALU&#39;s) like TI type Ser. No. 74S381 cascaded to provide a 16 bit capacity with carry propagation. These ALU&#39;s may be conditioned for any one of eight logic functions by combinations of control potentials on three input lines (e.g. lines 69 and 70). In the application of this invention only the add function is employed. 
     The unit 71 is an EXCLUSIVE OR logic unit composed of four four-bit units such as TI type 74S86. The individual bit orders are individually combined so that non-alike inputs to the order will yield a &#34;1&#34; output on that order and like inputs will yield a &#34;0&#34; output. Except for the logic performed (AND) the gate 72 is similarly structured to provide sixteen outputs as the logical AND function of sixteen pairs of inputs. It is typically constructed of four TI type Ser. No. 74S08. The selectors 50 and 51 are fabricated from 4 each of TI type Ser. No. 74S157. 
     In FIG. 1 the cables 90A through 90D consist of the cables 69, 70, 81, 82, 83, 84 and wires 65 and 66 grouped under the bracketed designation 90 in FIG. 2. The encircled number in the individual cables signifies the number of wires within the respective cables. The capacity of the address generator in the preferred embodiment is 16X and 16Y address bits, which if fully utilized could address a memory of 2 16  ×2 16  bits, if square. Through masking, any memory of smaller capacity or nonsquare matrix array can be addressed. For example, a 64K (65,536) by 1 bit memory (improbable) would utilize the total X capacity but only one Y address. 
     In the descriptions to follow it should be recalled that addresses run from 0 to 2 n-1  where n is an integer. 
     So as not to be confused by large numbers, a simple memory of 8 by 16 will be used in the following examples. The principles can be extrapolated by expanding the memory size by powers of two. 
     The buffer stores 63 and 64 and the arithmetic logic unit 67 generate the sequence of base addresses independent of memory size. In essence it is a counter which counts in increments of an integral number, set as a constant into the buffer store 63, whenever a clock timing pulse is entered to strobe the buffer store to receive an input. If, for example, buffer store 63 is preset to a binary value of 1, the ALU 67 will immediately manifest a binary 1 in the low order and all zeros in the fifteen higher orders. The buffer store is initially set to all ones, which when added to the single one in ALU 67 produces a sum of all zeroes. When the output from the ALU has been utilized, a clock pulse on line 65 strobes the buffer store 64 to receive the all zeros from the ALU 67, which then adds the constant &#34;1&#34; from buffer store 63 to the &#34;0&#34; in buffer store 64 to produce a base address of 1. By activating buffer store 64 the value of the number in the ALU 67 may be increased by the constant amount stored in buffer store 63. The incrementing occurs only when the clock pulse on line 65 allows the output from the ALU 67 to be entered in the buffer store 64. This combination of the ALU 67 and buffer store 64 is the equivalent of a counter which can be preset to count by any desired increment. 
     As stated there are four duplicate FIG. 2 units interconnected as shown in FIG. 1. The timing pulses applied to the 65A, 65B, 65C or 65D wire in cables 90A, 90B, 90C or 90D will differ in their frequency of occurrence as a function of the relative rates at which the X-home, X-away, Y-home and Y-away addresses are to be altered. 
     The 16-bit output from ALU 67 is applied as one input to a 16-position EXCLUSIVE OR gate 71 which receives a second 16-bit input on cable 83 to cause the output of gate 71 to be incremented or decremented as explained above in the section entitled &#34;Decrementing&#34;. 
     The incremented or decremented binary values are combined bit by bit (16 bits) with the masking bits from buffer store 62 and preset by entry on cable 82 into each of the A, B, C and D units. The manner of masking has been explained above under that section heading. 
     Finally, the output of AND 72 is added to the offset value stored in buffer store 61 which is preset to the desired value. The ALU 68 performs this addition under control of combinations of potentials on cable 70. The specific combination for adding for the chosen ALU&#39;s is 011. The 16-bit output from ALU 68 is the X (home/away) or Y (home/away) address employed to access the memory. 
     EXAMPLES OF USAGE 
     Galloping Pattern 
     In this test each successive cell becomes a &#34;home&#34; cell. This &#34;away&#34; cells are a succession of cells starting with the first cell in the array and ending with the last cell in the array. The &#34;home&#34; and &#34;away&#34; cells are tested in alternate succession and the operative &#34;home&#34; cell is actually tested twice, once as a &#34;home&#34; cell and again as an &#34;away&#34; cell. This simplifies the circuitry and controls and provides the same testing integrity as the more complicated &#34;home&#34; and &#34;away&#34; sequences described in the foregoing referenced publication. 
     The number of &#34;away&#34; cells is a constant and equal to the number of cells in the array. In the simple illustrative 8×16 memory (128 cells) the first home address is that of the first cell (X=0, Y=0). The succession of &#34;away&#34; cells is 0 through 127, which in this instance actually tests cell 0 twice. 
     The &#34;home&#34; and &#34;away&#34; ALU&#39;s 67A, 67B, 67C and 67D are initially preset to begin addressing at the 0-0 origin. The cables 83A through 83D potentialized with all 0&#39;s to effect incrementing. Cables 69A through 69D and 70A through 70D potentialized to control the ALU&#39;s to add. Mask registers 62A and 62C are set to a value of 0111 (the maximum X address, and the registers 62B and 62D are set to 01111 (the maximum Y address). 
     External counters, counting the X home and away cycles are preset to 0111. The counter for Y home and away are preset to 01111. Every interrogation cycle the Y-away counter is decremented by one count. When it recycles from 0 to its preset value of 15 it decrements the X-away counter by one count. This advances the interrogation downward in a column to the bottom, steps to the next, and proceeds in each successive column until the bottom of the last column when both the X and Y away counters will have been decremented to a zero value. This conicidence causes the Y-home counter to be decremented by one count. 
     The X and Y away counters recycle to 0 to begin tracking the next interrogation cycle for a new &#34;home&#34; cell. Each time an X and Y &#34;home&#34; or &#34;away&#34;  counter is decremented, the corresponding ALU 67 is incremented. The Y-home counter, when it completes its cycle from 15 to 0, decrements the X home counter in the same manner as the Y-away counter stepped the X-away counter. 
     Even though the X &#34;home&#34; and &#34;away&#34; ALU&#39;s and Y &#34;home&#34; and &#34;away&#34; ALU&#39;s will have been stepped many times and manifest respective values in excess of an available address, the preset values in the mask registers will prevent the output address from exceeding the value of an available address. The counters merely provide the frequency division to effect the column stepping and cycle point counting. 
     Actually, in the chosen example, each one of the 128 cells becomes a &#34;home&#34; cell. Each &#34;home&#34; cell has a corresponding 128 &#34;away&#34; cells for a total 16,384 steps, but only 1024 repeat cycles of 16 counts each. Correspondingly the X away counter will have been decremented 1024 times, or experienced 128 repeat cycles. 
     Thus, while the Y-away ALU 67D will have a maximum count of 16,384 (2 14 ) the output from the ALU 68D will never exceed 15 (01111). 
     As the Y-away counter progressively steps the X-away counter and both collaborate (at 0-0) to step the Y-home counter and it in turn steps the X-home counter, the end of test will be signalled when both the Y-home and X-home counters decrement to 0. At this point the maximum address of X=7, Y=15 will have been achieved. 
     Diagonal Pattern 
     Another example of memory address sequencing is the diagonal mode. All diagonals are 45° diagonals and the number of cells in any one diagonal sequence is the same for any one memory. The cells in a diagonal may be aligned, as in the major diagonal of a square, or they may be disposed in two parallel diagonal lines. Again, using the 8×16 memory for illustrative purposes, the number of diagonals will be equal to the greater of the two dimensions (16) and the number of cells in each respective diagonal will be equal to the lesser of the two dimensions (8). There will be nine continuous diagonals and seven discontinuous diagonals wherein the sum of the cells in the two discontinuous diagonals will be eight. 
     Initially the X and Y address generators are set with zero offset and an increment constant of one. The mask for the X addresses will be set to a binary value of seven and the Y mask will be set to a binary value of fifteen. Both address generators will be concurrently incremented by one count. This will provide successive addresses of cells along the 45° diagonal. By virtue of the masking of the X address, the X addresses will repeat the series 0-7 sixteen times even though the base address produced by the ALU 67A and buffer store 64A will advance from 0 through 127, the masking inhibiting usage of any address in excess of seven. 
     The Y-address generator will cycle concurrently with the X generator from zero upward by means of clock pulses applied to line 65C. However, to prevent a recycling of the Y addresses along the same diagonal it is necessary to add an additional count to the Y address after every sixteen counts so as to precess the diagonal one matrix position. This necessity is illustrated by the following tabular succession of matrix positions. 
     
         ______________________________________ADDRESS SEQUENCEX      Y        X     Y      X   Y      X   Y______________________________________0      0        0     2      0   4      0   6↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓7      7        7     9      7   11     7   130      8        0     10     0   12     0   14↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓7      15       7     1      7   3      7   50      1        0     3      0   5      0   7↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓7      8        7     10     7   12     7   140      9        0     11     0   13     0   15↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓7      0        7     2      7   4      7   6______________________________________ 
    
     If the successive values of the X and Y cycle counters, which are respectively preset to 7 and 15 and decremented, are set forth in similar tabular form they will appear as follows: 
     
         ______________________________________X      Y        X     Y      X   Y      X   Y______________________________________7      15       7     15     7   15     7   15↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓0      8        0     8      0   8      0   87      7        7     7      7   7      7   7↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓0      0        0     0      0   0      0   07      15       7     15     7   15     7   15↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓0      8        0     8      0   8      0   87      7        7     7      7   7      7   7↓  ↓ ↓                 ↓                        ↓                            ↓                                   ↓                                       ↓0      0        0     0      0   0      0   0______________________________________ 
    
     It will be noted that both counters achieve a simultaneous count of 0 at the end of each diagonal or eight times in the chosen example. This occurrence causes an additional count to be entered in the Y-ALU to precess the diagonal by one Y position. The only remaining timing function is to detect the end of test. This can be accomplished in a variety of ways, either by counting the number of accesses, or by counting the number of diagonals. In the former a counter preset to 127 and decremented would signal the end of test when it decremented to 0. The other would be to preset a counter to 7 and decrement it each time the X and Y counters had simultaneous zeros. When this counter receives its final decrementing pulse at the last pair of zeros to recycle it to its preset value of 7, the cycle is finished. 
     The foregoing example may be extrapolated to larger memories by appropriate adjustment of the parameters, taking cognizance of the rules governing the number of cells in a diagonal and the number of diagonals. Also, a discrete small area of a larger memory may be tested by using the same addressing principles and sequences, and adding an offset to the X and Y addresses. 
     By virtue of knowing the matrix geometry, the preset data set into the address generator and the cycle counters can be adjusted to define the area of the memory to be tested and the pattern of the test. 
     The home and away feature need not be confined to individual cell sequences, but may also be used to test corresponding areas of a memory which share sense amplifiers. The home and away addresses would then follow the same sequence, having identical incremental values, masking and cycle counting controls but differ only in their offsets. Alternate home and away addressing would test a succession of cells occupying the same relative positions with respect to two different geometric areas of the memory. 
     As has been demonstrated with the foregoing examples logic elements interconnected as hereinabove described provide for a very large variety of memory address sequences without requiring a large external memory to provide the sequences. The external memory need only provide the input data to the address generator and the cycle counters. The address generator then proceeds to produce the sequence of addresses without further reference to the external memory. In addition to utilizing a smaller external memory, the &#34;hard-wired&#34; address generator provides faster testing by eliminating the constant need to interrogate the external memory for further instructions. 
     While the invention has been particularly shown and described with reference to the preferred embodiment thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.