Multiple-valued programmable logic array minimization by solution space search
Wendt, Charles G.
Butler, Jon T.
Erickson, David A.
MetadataShow full item record
A minimal realization of a multiple-valued programmable logic array can only be achieved by exhaustive search. However, an exhaustive search is unrealistic even with the high speed CPU's in use today. Heuristic algorithms have been developed that provide near-minimal solutions, using significantly less CPU time. This thesis investigates a new type of heuristic that uses implicant operations (combine, reshape, and cut) to move through the solution space. The choice of move is dynamically controlled by feedback from a queue of previous moves, called a TABU queue. This new heuristic performs better than existing heuristics, in certain situations, but requires more CPU time than direct cover methods. in addition, this heuristic provides a unique capability to fix the move acceptance probabilities associated with the basic implicant operations. Fixing move acceptance probabilities allows a study of the solution space of multiple-valued logic functions under controlled conditions. For example, tile results of a preliminary study into the solution space of a four- valued, three variable special function (SF) are presented. This suggests that the search space is not homogeneous; rather it suggests that the space is segmented with restrictive access between segments. The results of such studies will be a basis for improving the performance of current and future minimization heuristics.
Approved for public release; distribution is unlimited.
Showing items related by title, author, creator and subject.
Oral, Sabri Onur (Monterey, California. Naval Postgraduate School, 1991-09);The process of finding an exact minimization for a multiple-valued logic (MVL) expression requires an extensive search and enormous computation time. One of the heuristics to reduce this computation time is the Neighborhood ...
Multiple-valued programmable logic array minimization by concurrent multiple and mixed simulated annealing. Yildirim, Cem (Monterey, California. Naval Postgraduate School, 1992-12);The process of finding a guaranteed minimal solution for a multiple-valued programmable logic expression requires an exhaustive search. Exhaustive search is not very realistic because of enormous computation time required ...
Earle, Robert C. (1991);Guaranteed minimal realizations of multi-valued programmable logic arrays can only be accomplished by an exhaustive search. Exhaustive search is not very realistic for complex expressions due to the immense amount of CPU ...