|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.