Minimization algorithms for multiple-valued programmable logic arrays
Butler, Jon T.
MetadataShow full item record
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 , Besslich , and Dueck and Miller , 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.
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.IEEE Transactions on Computers, Vol. 40, No. 2, pp. 167-177, February 1991
Showing items related by title, author, creator and subject.
Characteristics of the binary decision diagrams of Boolean Bent Functions Schafer, Neil Brendan. (Monterey, California: Naval Postgraduate School, 2009-09);Boolean bent functions have desirable cryptographic properties in that they have maximum nonlinearity, which hardens a cryptographic function against linear cryptanalysis attacks. Furthermore, bent functions are extremely ...
Minimization of SOPs for bi-decomposable functions and non-orthodox/orthodox functions Ulker, Birol (Monterey, Calif. Naval Postgraduate School, 2002-03);A logical function f is AND bi-decomposable if it can be written as f x1, x2)= h1 (x1) h2(x2), where x1 and x2 are disjoint. Such functions are important because they can be efficiently implemented. Also many benchmark ...
An analysis of bent function properties using the transeunt triangle and the SRC-6 reconfigurable computer Shafer, Jennifer L. (Monterey, California: Naval Postgraduate School, 2009-09);Linear attacks against cryptosystems can be defeated when combiner functions are composed of highly nonlinear Boolean functions. The highest nonlinearity Boolean functions, or bent functions, are not common- especially ...