On finding a minimal functional description of a finite-state machine for test generation for adjacent machines

摘要

In some applications, it is desirable to find for a circuit a minimal partial description that allows a certain task to be carried out. A partial circuit description allows the task to be carried out more efficiently since fewer decision points exist based on a partial description compared to the full circuit description. We consider this problem with respect to finite state machines and the following tasks. Starting from a functional description of a finite state machine M in the form of a state table ST, we select a minimal subset of state-transitions ST/sub part//spl sub/ST such that every output sequence that can be produced using state-transitions out of ST can also be produced using state-transitions out of ST/sub part/. We also formulate a similar problem related to the propagation of fault effects from the inputs to the outputs of M and describe a procedure for solving this problem. Applications of these tasks include test generation for circuits described as interconnections of finite-state machines. Experimental results presented show that ST/sub part/ contains a small fraction of the state-transitions of ST.