Exact Algorithms for Output Encoding, State Assignment and Four-Level Boolean Minimization
Abstract
In this paper we present efficient, exact algorithms for the problems of output encoding, state assignment and four-level Boolean minimization. All previous automatic approaches to encoding problems have involved the use of heuristic techniques. Other than the straightforward, exhaustive search procedure, no exact solution methods have been proposed. The problems of output encoding and state assignment targeting two-level logic implementations involve finding appropriate binary codes for the symbolic outputs of states so a minimum number of product terms results after two-level Boolean minimization. A straightforward, exhaustive search procedure requires O(N) exact Boolean minimization, where N is the number of symbolic outputs or states. We propose a novel minimization procedure of prime implicant generation and covering that operates symbolic outputs, rather than binary-valued outputs, for solving the output encoding problem. An exact solution to this minimization problem is also an exact solution to the encoding problem. While our covering problem is more complex than the classic unate covering problem, a single logic minimization step replaces O(N) minimization. The input encoding problem can be exactly solved using multiple-valued Boolean minimization. We present an exact algorithm for state assignment by generalizing our output encoding approach to the multiple-valued input case.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1989
- Accession Number
- ADA217121
Entities
People
- A. R. Newton
- Srinivas Devadas
Organizations
- Massachusetts Institute of Technology