Minimization of Logic Networks Under a Generalized Cost Function

Open Access
Publisher Website
Google Scholar
Abstract
Based on the intuitive observation that smaller numbers of gates and connections would usually lead to a more compact network on an integrated circuit (IC), a monotonically increasing function of gate count and connection count is concluded to be a reasonable cost function to be minimized in the logical design of a network implemented in IC. Then it is shown that all minimal solutions of such a cost function always can be found among the following: minimal networks with a minimal number of gates as the first objective and a minimal number of connections as the second objective; minimal networks with a minimal number of connections as the first objective and a minimal number of gates as the second objective; and minimal networks which are associated with the above two types of minimal networks. All three of these types of minimal networks of NOR gates, as an example, are calculated by logical design programs based on integer programming, for all functions of 3 or less variables and also some functions of 4 variables which require 5 or less NOR gates. According to the computational results, for the majority of the functions the first type of minimal networks is identical to the second type, and for no function were networks of the third type found to exist.

This publication has 8 references indexed in Scilit: