Worst case number of terms in symmetric multiple-valued functions
Abstract
A symmetric multiple-valued function can be realized as the disjunction of fundamental symmetric functions. A simpler disjunction can be formed when the latter functions combine in the same way that minterms combine to form simpler product terms for sum-of-products expressions. We solve a problem posed by Muzio [7], who seeks the worst case symmetric function in the
sense that the maximum number of fundamental symmetric functions is needed. The worst case is presented for 3- and 4-valued systems in 171, but the case for general radix is left open. We solve this problem for general radix, and show that the ratio of the maximum size of the disjunction to the total number of fundamental symmetric functions approaches one-half as the number of variables increases.
Description
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.
Proceedings of the 21st International Symposium on Multiple-Valued Logic, May 1991, pp. 94-101
Collections
Related items
Showing items related by title, author, creator and subject.
-
Minimization algorithms for multiple-valued programmable logic arrays
Tirumalai, Parthasarathy; Butler, Jon T. (1991-02);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 ... -
Average path length as a paradigm for the fast evaluation of functions represented by binary decision diagrams
Sasao, T.; Matsuura, M.; Butler, Jon T. (2002-11);This paper focuses on the average path length (APL) of BDD’s for switching functions. APL is a metric for the time it takes to evaluate the function by a computer program. We derive the APL for the AND, OR, parity, carry-out, ... -
Analysis of input and output configurations for use in four-valued programmable logic arrays
Kerkhoff, Hans G.; Butler, Jon T. (1987-07);As in binary, a multiple-valued programmable logic array (PLA) realises a sum-of-products, expression specified by the user. However, in multiple-valued logic, there are many more operations than in binary, and an important ...