On the design of cost-tables for realizing multiple-valued circuits
Abstract
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.
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.
IEEE Transactions on Computers, Vol. 41, No. 2, February 1992, pp. 178-189
Collections
Related items
Showing items related by title, author, creator and subject.
-
On the equivalence of cost functions in the design of circuits by cost-tables
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 ... -
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 ... -
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, ...