Boolean Minimization and Algebraic Factorization Procedures for Fully Testable Sequential Machines.

摘要

In this paper we continue to investigate the impact of logic synthesis on the testability of sequential circuits that can be modeled as finite state machines. Complete testability of a sequential circuit is ensured by guaranteeing that each invalid state has an unperturbable distinguishing sequence. To accomplish this we present a novel Boolean minimization procedure of prime implicant generation and constrained covering based on the Quine-McCluskey algorithm that ensures that no single fault can both produce an invalid state and corrupt the distinguishing sequence by which that invalid state can be identified. On completion, it guarantees a prime and irredundant, fully testable Moore or Mealy finite state machine. Given a two-level circuit with these properties we then use constrained algebraic factorization techniques that retain the invariant that no single fault can both produce an invalid state and corrupt the distinguishing sequence by which that invalid state is detected. Besides offering a more detailed understanding of the sources of untestability in sequential circuits than previous approaches, this approach offers significant practical advantages as well. It is applicable to a wider range of circuits than optimal synthesis procedures whose utility is often limited by prohibitively high CPU requirements, and its less restrictive synthesis constraints result in lower area overhead than other constrained synthesis approaches. These observations are supported by experimental results. (rrh)