Heuristic minimization of Boolean relations using testing techniques

摘要

A Boolean relation is a one-to-many multioutput Boolean mapping and is a generalization of incompletely specified logic functions. Boolean relations arise in several contexts (for instance, in a finite state machine with sets of equivalent states). Minimization of Boolean relations is important from the point of view of synthesis, especially synthesis for testability. A fast heuristic procedure for finding an optimal sum-of-products representation for a function compatible with a Boolean relation is described. Starting with an initial function compatible with the relation, a process of iterative logic improvement based on test generation techniques is used to derive a minimal function.