This animated GIF that I created shows how an Automated Test Equipment (ATE) Algorithmic Pattern Generator (APG) works to generate a common Memory Test Pattern. Each and every location in a memory must be tested and an APG makes it relatively easy to write patterns to test every memory cell. Memories are often organized in a matrix of an equal number of Rows and Columns. Having an equal number of rows and columns makes the memory square, but this is not always the case, but this is what I assume in this example.

This example is typical of an advanced APG, not all of them work this well, as I will point out. The APG really just consists of just a few registers. The most important are the address registers, XR and YR. These registers are controlled by microinstructions that I show in pseudocode at the top of the example. In addition to the address registers there are also ancilliary registers like XMax and YMax. These registers allow the user to set the maximum test size of the memory. In this example the X and Y Max are set to a smaller value than the maximum size of the memory, mostly so I didn't have to simulate all 64 states of this 8 by 8 memory. To test the whole memory I would set the XMax and YMax to 111. If my memory gets larger (which happens every 18 months according to Moore's Law) I simply increase the value of X and Y max, and the same pattern continues to work as long as I don't run out of bits in my registers.

The most common method of addressing memories is to increase the column address until we hit the end of the row, then return back to the start of the next row, and so on, just like a typewriter works (if you are old enough to know what that looks like). To do this we use the opcode:
Increment YR; if Equal(YR, YMax) {YR=0; Increment XR;};
This code says to increment the Y address register each cycle, and if the YR is equal to YMax (the end of the row) then set YR back to 0 and increment the X address register to start back at the first cell of the next row. Using a conditional statement like IF allows the same flow to be used for any size memory. If a bigger memory comes along, just change the Max register to allow the same statement to cover more rows (XMax) or more columns (YMax). To know when we hit the end of the memory we have to look at both XR and YR compared to their Max registers. Once we have YR equal to YMax and XR equal to XMax, we know we have hit the end of the memory and it's time to go to the next statement for the next test. In the animation when an address register equals the Max register both turn RED. By the way, not every tester's APG has Max registers.

In addition to addressing the cells, you have to generate the data to test the memory cells. You would like to make sure that each cell can hold both a one and a zero and make sure that writing a cell does not cause cells around it to also to change state. A checkerboard pattern does a pretty good job of this, but there are actually many other patterns that can be used to perform a "surround disturb" but the checkerboard is easy to understand so I use it here.
To create the checkerboard pattern we use an internal ALU (computing section) in the APG to calculate the XOR of each bit of the XR and YR. XOR says that if the two bits match, then the result is 0, if the bits are different, the result is a 1. This creates our checkerboard pattern easily. Note that I run both versions of the checkerboard simply by inverting the XOR statement into a NOT XOR (!XOR) statement.

The animation is running at high speed. To watch it at a slower speed put your mouse over the animation.

Finally, in the pseudo code I show how this is a "Test." On each cycle the data from the DR is written into the memory cell, then read back and if the result from the memory is not the same as the value we wrote into the memory, we set the FAIL flag in the tester and stop the test with an END command. Of course the only place this tester exists is in my mind, but it is a simplified composite of the best APGs I have worked on. But if you can understand this APG you wouldn't have any trouble understanding a real testers APG.

Any number of test patterns can be generated easily if the engineer has some imagination and knowledge of math. For example another very cool pattern is a butterfly pattern. This pattern starts at cell zero, writes the bit, reads it back, then inverts the XR and YR which addresses the very last cell in the memory, writes the bit, then reads it, inverts XR and YR again, then uses the same statements as above to increment to the next bit (cell #1), tests it, then inverts the XR and YR again, but now this takes us to the last cell minus 1. On each iteration the pattern moves slowly but surely to the center by hitting cell(2), cell(max-2), cell(3), cell(max-3) etc. I'll save that simulation for another day.

Here is the first day of my GR16 APG Training Course in PDF.