Minimization algorithms for multiple-valued programmable logic arrays

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 PLA’s 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 implicunt 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 implicunfs 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.