On the design of cost-tables for realizing multiple-valued circuits
Schueller, Kriss A.
Butler, Jon T.
MetadataShow full item record
We propose a heuristic for finding minimal cost- tables for use in the design of multiple-valued logic circuits. It is an iterative approach, in which a good table of size t is composed of a good table of size t - 1, etc. We analyze its performance, comparing it with three other heuristics. The importance of finding good cost-tables is demonstrated by an analysis that shows there is a wide variation in both cost-table performance and in the performance of heuristics for generating cost-tables. We study linear cost, a general cost function of which two previously studied cost functions are special cases. It is shown that the minimal cost-table using one of the (infinitely many) linear cost functions is identical to a minimal cost-table using any other linear cost function. Thus, a heuristic for finding the minimal cost-table using the linear cost function is independent of the specific cost function parameters. This result and our observation of well-studied nonlinear cost functions indicate that cost-table design is only marginally dependent on the cost function. We show two additional results on cost-table design. First, it is demonstrated that a search for minimal cost-tables cannot exclude certain seemingly useless functions called composite func- tions. Second, while the complexity of cost-table design appears to preclude a computationally efficient general algorithm for finding the minimal cost-table, a special case allows efficient design. For the case of a small cost-table, we show how to find the minimal cost-table.
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. 41, No. 2, February 1992, pp. 178-189
Showing items related by title, author, creator and subject.
Schueller, Kriss A.; Butler, Jon T. (1990-06);n the costtable approach to logic design, a function is realized as a combination of functions from a table. The objective of the synthesis is to find the least cost realization, where realization cost is the sum of ...
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 ...
A Comparative analysis of multiplexer techniques for the minimization of function cost using the cost-table approach Kerkhoff, Hans G.; Butler, Jon T.; Onneweer, Siep (1990-05);In the costtable approach to logic design, a given function is realized by selecting functions from a table and combining them. Associated with each function is a cost, and the goal is to find, among all realizations, ...