Exact algorithms for output encoding, state assignment, and four-level Boolean minimization

Abstract

A novel minimization procedure of prime implicant generation and covering that operates on symbolic outputs, rather than binary-valued outputs, is proposed for solving the output encoding problem. An exact solution to this minimization problem is also an exact solution to the encoding problem. While this covering problem is more complex than the classic unate covering problem, a single logic minimization step replaces O(N-factorial) minimizations. The input encoding problem can be exactly solved using multiple-valued Boolean minimization. An exact algorithm is presented for state assignment by generalizing the proposed output encoding approach to the multiple-valued input case. Four-level Boolean minimization entails finding a cascaded pair of two-level logic functions that implement another logic function, such that the sum of the product terms in the two cascaded functions or truth tables is minimum. Four-level Boolean minimization can be formulated as an encoding problem and solved exactly using the proposed algorithms. Preliminary experimental results are presented which indicate that this approach is significantly more efficient than exhaustive search. Computationally efficient heuristic approaches based on the exact algorithms are proposed for output encoding, state assignment, and four-level Boolean minimization.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>