Decomposition of Boolean Functions Specified by Cubes:
Part I: Theory of Serial Decompositions Using Blankets

J. A. Brzozowski
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

T. Luba
Institute of Telecommunications
Warsaw Institute of Technology
Nowowiejska 15/19
00-665 Warsaw, Poland

Abstract
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.

In Part I of the paper we develop a comprehensive theory of serial decompositions for multiple-output, partially specified, Boolean functions represented by cubes. A function f(x_1,...,x_n) has a serial decomposition if it can be expressed as h(u_1,...,u_r,g(v_1,...,v_s)), where U = {u_1,...,u_r} and V = {v_1,...,v_s} are subsets of the set X = {x_1,...,x_n} 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.

In Part II we describe a tool called DEMAIN, which uses many ideas from Part I. We discuss implementation issues, present experimental results, and compare our results to those of other decomposition tools.

Keywords: blanket, Boolean function, cube, decomposition, disjoint, "don't care," multiple-output, set system