Accession Number:

ADA605380

Title:

Minimization Algorithms for Multiple-Valued Programmable Logic Arrays

Descriptive Note:

Journal article

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Report Date:

1991-02-01

Pagination or Media Count:

13.0

Abstract:

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 such PLAs are in sum-of-products form, where sum is ordinary addition truncated to the highest logic value, and where product represents the MIN operation on functions of the input variables which are the interval literal operations. We compare three previously published heuristics, Pomper and Armstrong 14, Besslich 3, and Dueck and Miller 6, over sets of random and random symmetric functions. We show an exact minimization method that is a tree search using backtracking. A considerable reduction in the search space is achieved by considering constrained implicant sets and by eliminating some implicants altogether. Even with this improvement, the time required for exact minimization is extremely high when compared to all three heuristics. We also examine the case where only prime implicants are considered and show that such implicants have marginal value compared to constrained implicant sets. Our basis of comparison is the average number of product terms. We show that the heuristic methods are reasonably close to minimal and produce nearly the same average number of product terms. Interestingly though, there is surprisingly little overlap in the set of functions where the best realization is achieved. Thus, there is a benefit to applying all three heuristics to a given function and then choosing the best realization.

Subject Categories:

  • Electrical and Electronic Equipment
  • Numerical Mathematics
  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE