On the equivalence of cost functions in the design of circuits by cost-tables

Abstract

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.