Analysis of minimization algorithms for multiple-valued programmable logic arrays
Abstract
We compare the performance of three heuristic algorithms [3,6,13] for the minimization of
sum-of-products expressions realized by the newly
developed multiplevalued programmable logic arrays [9]. Heuristic methods are important because exact minimization is extremely time consuming. We compare the heuristics to the exact solution, showing that heuristic methods are reasonably close to minimal. We use as a basis of comparison the average number of product terms over a set of randomly generated functions. All three heuristics produce nearly the same average number of product terms. Although the averages are close, there is surprisingly little overlap among the set of functions where the best realization is achieved. Thus, there is a benefit to applying different heuristics and then choosing the best realization.
Description
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.
Proceedings of the 18th International Symposium on Multiple-Valued Logic, May 1988, pp. 226-236
Collections
Related items
Showing items related by title, author, creator and subject.
-
HAMLET - An expression compiler/optimizer for the implementation of heuristics to minimize multiple-valued programmable logic arrays
Yurchak, John M.; Butler, Jon T. (1990-05);HAMLET is a CAD tool that translates a user specification of a multiple-valued expression into a layout of a multiple-valued programmable logic array (MVL-PLA) which realizes that expression. It is modular to accommodate ... -
Minimization algorithms for multiple-valued programmable logic arrays
Tirumalai, Parthasarathy; Butler, Jon T. (1991-02);We analyze the performance of various heuristic algorithms for minimizing realizations of multiple-valued functions by the newly developed CCD 191 and CMOS [W] programmable logic arrays. The functions realized by ... -
Application of the constrained implicants set concept to the minimization of binary functions
Ozkan, Ugur (Monterey, California. Naval Postgraduate School, 1990);Several heuristics and algorithms have been developed to find minimal sum-of-products expressions in binary logic. Most of them use prime implicants during minimization process. An efficient search strategy has been developed ...