Irredundant Sequential Machines Via Optimal Logic Synthesis

It is well known that optimal logic synthesis can ensure fully testable combinational logic design. In this paper we show that optimal sequential logic synthesis can produce irredundant, fully testable finite state machines. Test generation algorithms can be used to remove all the redundancies in sequential machines resulting in a fully testable design. However, this method may require exorbitant amounts of CPU time. The optimal synthesis procedure presented in this paper represents a more efficient approach to achieve 100% testability. Synthesizing a sequential circuit from a State Transition Graph description involves the steps of state minimization, state assignment and logic optimization. Previous approaches to producing fully and easily testable sequential circuits have involved the use of extra logic and constraints on state assignment and logic optimization. In this paper we show that 100% testability can be ensured without the addition of extra logic and without constraints on the state assignment and logic optimization. Unlike previous synthesis approaches to ensuring fully testable machines, there is no area/performance penalty associated with this approach. This technique can be used in conjunction with previous approaches to ensure that the synthesized machine is easily testable.