TEST FUNCTION EMBEDDING ALGORITHMS WITH APPLICATION TO INTERCONNECTEDFINITE-STATE MACHINES

We present new algorithms for embedding test functions into the state diagram of a finite state machine. We first identify the cases where t est functions can be embedded into the state diagram of the given obje ct machine without using an extra input line. When such embedding is p ossible, our method finds it. In other cases, an extra input line must be added to the object machine to make the embedding possible. For th e extra input case, we use partition theory and state variable depende ncies in the object machine to obtain a mapping of the test machine st ates onto the object machine states. This mapping introduces a minimum number of extra state variable dependencies in the augmented machine as compared to the dependencies in the object machine. Experimental re sults on several MCNC benchmarks show that our method yields augmented machine implementations that have lower area than corresponding full scan designs. The test generation complexity for the augmented machine implementation is the same as that for a full scan design. We further consider the embedding of test functions into machines specified as a n interconnection of finite state machines. We incorporate test functi ons into each component finite state machine such that the augmented i nterconnected machine has the same testability properties as the produ ct machine with test function.