Decomposition of Boolean Functions Specified by Cubes
Janusz Brzozowski, Tadeusz Łuba · 2003
(Recommended for publication by Dan Simovici) 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.