Making an Automatic Test Pattern Generator

Another semester is over, which means I have at least a  few weeks to work on my personal projects before being thrown back into the meat grinder. There is already a large heap of unfinished projects that deserve more progress (see previous posts), but a new problem has entered my mind that stubbornly refuses to be ignored. This is a bonus project that I never had time to work on from one of the classes that I just finished, Fault Detection in Digital Circuits. The objective is to write a program for automatic test pattern generation (ATPG). The high-level flow will look something like the diagram below.

High-level flow for ATPG, by Dr. Jia Wang

   The input to the program is to be a circuit netlist. For this development, circuits from the ISCAS89 benchmark are being used. Some of these designs are pretty huge, so it's important that this program be fast and efficient. Another thing to consider is that these designs contain sequential elements (flip-flops), which can really complicate the process since the state of the circuit has to be considered. For now, I'm assuming that all registers are scan-enabled, which means that inputs and outputs can be serially read and loaded directly. This enables ATPG and simulation techniques to be used for the combinational part of the circuit.

   The thing that's really giving me headaches at this point is extracting the functional model of a circuit from the structural model, which is the provided netlist. I can most likely achieve this by constructing a reduced ordered binary-decision diagram (ROBDD) using an algorithm explained in Algorithms for VLSI Design automation by Gerez. Once that's done though, it needs to be exclusive-OR'd with a copy of the circuit with errors inserted. Then it needs to be converted to conjunctive normal form (CNF) so it can be analyzed by a SAT solver (in this case, MiniSAT) for the actual test pattern generation. And I haven't even started thinking about fault simulation yet.

   Suddenly, that AVR LCD library is looking a lot more attractive.