Accession Number:



Multiple-Valued Programmable Logic Array Minimization by Solution Space Search

Personal Author(s):

Corporate Author:


Report Date:



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 CPUs 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. MVL Multiple-Valued Logic minimization, PLA Programmable Logic Array, HAMLET, Solution space search

Descriptive Note:

Master's thesis



Subject Categories:

Communities Of Interest:

Distribution Statement:

Approved for public release; distribution is unlimited.

File Size: