State Assignments in Combinational Networks

The problem of assigning codes to the output states of a multiple-output combinational circuit is considered. It is assumed that if the circuit has n inputs, then the 2ⁿ fundamental products, i.e., input states, are to be partitioned into disjoint groups, such that all members of the same group produce the same output state. The problem of coding the output states is studied here. Two algorithms for making the assignments are considered. The first gives those encodings for which the sum of the costs of all the output functions is minimum; the second minimizes the variable dependency of the output functions. In problems where reduced variable dependency is possible it has been found that the second algorithm yields minimum or near-minimum cost networks. Since this algorithm is easily applied it is useful for finding economical networks in situations where a large number of variables are involved since in such cases the first algorithm becomes lengthy. Attention is also directed to the problem of determining the optimum number of output variables to use for an encoding. An upper bound is derived and an example is presented which requires this bound.