Publication:
On the design of cost-tables for realizing multiple-valued circuits

Loading...
Thumbnail Image
Authors
Schueller, Kriss A.
Butler, Jon T.
Subjects
Cost-table
logic design
minimization
multiple-valued logic
synthesis
Advisors
Date of Issue
1992-02
Date
February 1992
Publisher
Language
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.
Type
Article
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
Series/Report No
Department
Department of Electrical and Computer Engineering
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
On the design of cost-tables for realizing multiple-valued circuits," IEEE Transactions on Computers, Vol. 41, No. 2, February 1992, pp. 178-189
Distribution Statement
Rights
Collections