Automatic test generators available today work at the logic gate level, with perhaps a few higher-level primitives such as flip-flops and counters included. It would be advantageous to offer automatic test generation for circuits described at a higher level for two reasons: first, for increased efficiency; and second, because gate-level models do not exist for some circuits.

The high-level functionality of a circuit can be described in several ways. One is by using Boolean equations; another is by use of a hardware description language. A third way is by use of a binary decision diagram (BDD). This paper describes a test generation technique for circuits described using BDDs.

The first question is whether a BDD is the best descriptive technique. The reason given by the authors for using this approach is that it is closer to an actual implementation than a functional description. This might be true if functional models were actually “black boxes” as claimed here, only matching the input/output behavior of the real circuit. Actually, in order to model the functional behavior of the circuit more easily, the writers of functional models match internal data and control paths as much as possible; thus, functional models are more like “gray” boxes. In my experience it is possible to model a circuit quite well with functional models. However, no good test generation approach exists as yet for functional models, so the provision of test generation for BDDs would provide a good reason for their use. BDDs can model sequential circuits, which is necessary for practical test generation, unless scan design is used. However, the authors assume that the state of each internal memory element of a module is one of the outputs of the module. If this is not the case, smaller modules are defined. This reduces the size of functional blocks and eliminates an advantage of this technique. The various alterations to a circuit description needed to satisfy this requirement also reduce modeling accuracy.

The authors present their test generation algorithm for BDDs in detail. In sequential circuit test generation, the major problem is to limit the number of time frames for which circuit state information must be stored. Marlett’s extended back trace algorithm [1] limits to two the number of time frames for which information must be kept. In the algorithm described in this paper, however, propagation is done from the fault site to a primary output, and then justification is done. The number of time frames involved can become very large, which makes this algorithm impractical. Another problem is that an exhaustive search of the search space is done for each time frame before moving either forward or backward in time, even if adding a time frame could lead to a faster solution. I suspect that this is done to reduce the number of time frames to be considered.

Unfortunately, it appears that this algorithm has never been implemented, and no analysis of the expected run time of the algorithm is given. I suspect that this is not a practical test generation strategy. The authors claim that this strategy is useful for circuit boards containing SSI and MSI devices, and that VLSI can be handled if it is broken into smaller modules. I very much doubt that this is true. I am not sure if BDDs are a practical model for sequential test generation, but even if they are, state-of-the-art test generation algorithms should be used.