Multiple-valued programmable logic array minimization by solution space search
Loading...
Authors
Wendt, Charles G.
Subjects
MVL (multiple-valued logic) minimization
PLA (programmable logic array)
HAMLET
Solution space search
PLA (programmable logic array)
HAMLET
Solution space search
Advisors
Butler, Jon T.
Date of Issue
1993-12
Date
December 1993
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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.
Type
Thesis
Description
Series/Report No
Department
Department of Electrical and Computer Engineering
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
vi, 53 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.