We analyze the computational complexity of the cost-table approach to designing multiple-valued logic circuits that is applicable to I/sup 2/L, CCDs, current-mode CMOS, and RTDs. We show that this approach is NP-complete. An efficient algorithm is shown for finding the exact minimal realization of a given function by a given cost-table.

A heuristic is proposed 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. The authors 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. A study is made of 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. Two additional results on cost-table design are given.>

In the cost-table 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 cost-table functions are defined by a cost function which represents chip area, speed, power dissipation, or a combination of these factors. It is shown that there is an arbitrarily large set S of cost functions which yield the same cost-table. 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. With any cost function, if the cost of combining functions from a cost-table F is sufficiently large, the realizations behave as if the cost function belonged to S. That is, any minimal realization of a function f, using cost-table F, is one of the minimal realizations of f using F and a cost function in S. The interpretation of these results is that there are not as many distinct cost-tables as originally thought.>