Decomposition of Boolean Functions Specified by Cubes
J.A. Brzozowski and T. Luba
We study the problem of decomposing a Boolean function into a set of functions with fewer arguments. This problem has considerable practical importance in VLSI, for example, for designs using field-programmable gate arrays. The decomposition problem is old, and well understood when the function to be decomposed is specified by a truth table, or has one output only. However, modern design tools handle functions with many outputs and represent them by cubes, for reasons of efficiency. We develop a comprehensive theory of serial decompositions for multiple-output, partially specified, Boolean functions represented by cubes. A function f (x1, . . . , xn) has a serial decomposition if it can be expressed as h(u1, . . . , ur, g(v1, . . . , vs)), where U = {u1, . . . , ur} and V = {v1, . . . , vs} are subsets of the set X = {x1, . . . , xn} of input variables, and g and h have fewer input variables than f. The theory uses generalized set systems (which, in turn, are generalized partitions), which we call blankets.