Based on the new concept of permissible functions, a heuristic procedure to design logic networks with as few gates as possible, without guaranteeing the minimality of designed networks, is developed. This procedure, which is drastically different from conventional logic-design procedures, is called the transduction method, because an initial network designed by any conventionally known logic-design method is first transformed into a different network configuration and then reduced to a simpler network by calculating permissible functions at the outputs of gates and connections throughout the network.>

If a logic gate in a logic network of MOS transistors expresses a negative function, which is a logic function that can be expressed as the complement of a disjunctive form of only noncomplemented variables, it is called a negative gate. An algorithm, DIMN, for the design of a MOS logic network with a minimum number of negative gates and irredundant connections among negative gates for a completely specified function was published by the authors in 1985. DIMN is extended here to the case of an incompletely specified function, and an example is given.>

Design of logic networks, in single-rail input logic, with a minimum number of NOR gates for parity functions of an arbitrary number of variables is described. This is partly based on minimum networks for parity functions of a small number of variables which are designed by the integer programming logic design method. Although it is generally difficult to design minimum networks for functions of an arbitrarily large number of variables, we have previously designed minimum networks for adders of an arbitrary number of variables. The minimum networks for parity functions of an arbitrary number of variables discussed in this paper is another case. Many unique properties of minimum NOR networks for parity functions are shown. Minimum networks with NAND gates for parity functions can be easily obtained from those with NOR gates because of duality relationship between NAND and NOR.

logic networks of carry–save adders such as high-speed multipliers, multioperand adders, and double-rail input parallel adders are designed based on the parallel adders with a minimum number of NOR gates discussed in [1]. After a discussion of the derivation of carry–save adder modules (CSAM's) by the integer programming logic design method, general design procedures are illustrated with example networks. Compared to conventional networks of carry–save adders, the derived networks of carry–save adder modules (NOCSAM's) have the advantages of fewer gates, fewer connections, and faster operation. In particular, the parallel adder of NOR gates in double-rail input logic obtained has six gates and 15½ connections per stage, whereas the previously known best design under the same condition requires six gates and 17 connections per stage with the same carry propagation delay.

Parallel binary adders of n bits long in single-rail input logic which have a minimum number of NOR gates are derived in this paper. The minimality of the number of NOR gates is proved for an arbitrary value of n. Also, it is proved that the adders must be a cascade of basic modules and that there exist many different types of basic modules. These adders have fewer gates and shorter net gate delays (or fewer connections) than the widely used carry-ripple adders which are a cascade of one-bit full adders. Design procedures of such adders are described, based on the integer-programming logic design method. There are many solutions but adders with few connections and those with few net gate delays (all these adders have the minimum number of gates) are shown as important examples. Altbough these adders are designed with NOR gates, the results in this paper are applicable to adders with NAND gates by duality conversion.

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.