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.