On the equivalence of cost functions in the design of circuits by cost-tables
Schueller, Kriss A.
Butler, Jon T.
MetadataShow full item record
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 the costs of the functions used, plus the cost of combining them. The costs of costtable functions are defined by a cost function, which represents chip area, speed, power dissipation, or a combination of these factors. We show that there is an arbitrarily large set S of cost functions all of which yield the same minimal realization from a given costtable. This implies, for example, that every minimal realization of any function over a cost function in S is independent of the actual cost function used. Furthermore, we show that, with any cost function, if the cost of combining functions from a costtable F is sufficiently large, the realizations behave as if the cost function belongs to S. That is, any minimal realization of a functionf, using costtable F, is one of the minimal realizations off using F and a cost function in S. Our interpretation of these results is that there are not as many distinct costtables as originally thought.
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, C39, June 1990, pp. 842-845
Showing items related by title, author, creator and subject.
On the design of cost-tables for realizing multiple-valued circuits Schueller, Kriss A.; Butler, Jon T. (1992-02);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, ...
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, ...
Complexity analysis of the cost-table approach to the design of multiple-valued logic circuits Schueller, Kriss A.; Butler, Jon T. (1995-10);We analyze the computational complexity of the cost-table approach to designing multiple alued logic circuits that is applicable to I L, CCD’s, current-mode CMOS, and RTD’s. We s 2 how that this approach is NP-complete. ...