An Approach to the Assignment of Input Codes

Abstract

This paper presents an approach to the problem of assigning binary input codes so that the combinatorial circuits necessary to realize the given output functions may be minimized. The approach is based on binary partitions and binary set systems, which provide a natural language for dealing with the problem. First, a lower bound is established for the realization of each output function, with the assumption that the function will not be realized directly. Then, the output partitions determined by the output functions are found and those output partitions that can be used together in a valid assignment are established. This provides a number of assignment schemes which, in turn, can be evaluated in terms of a lower bound for the realization cost. For the scheme with the smallest lower bound, the actual realization cost is established. This provides a measure by which a number of schemes can be eliminated, since it is necessary to consider only those schemes having a lower bound smaller than the least actual cost already obtained. Using set systems, the method is extended to include output functions containing don't cares. It is also shown how the method can be applied to the minimization of combinatorial circuits in sequential machines.