DECOMPOSITION OF BOOLEAN FUNCTIONS SPECIFIED BY CUBES

J. A. BRZOZOWSKI
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
email: brzozo@uwaterloo.ca

T. LUBA
Institute of Telecommunications
Warsaw University of Technology
Nowowiejska 15/19
00-665 Warsaw, Poland
email:luba@tele.pw.edu.pl

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 digital circuits designed with field-programmable gate arrays, it is necessary to express Boolean functions in terms of `smaller' functions that fit the cells of the array. The decomposition problem is old, and well understood when the function to be decomposed is specified by a truth table listing the function's minterms, or has one output only. However, modern design tools, such as Berkeley's Espresso, handle functions with many outputs and represent them by Boolean cubes rather than minterms, for reasons of efficiency. In this paper we develop a decomposition theory for multiple-output, partially specified Boolean functions represented by cubes. The theory uses ternary algebra and generalized set systems.

KEYWORDS: blanket, Boolean function, cube, decomposition, disjunctive, don't care, multiple-output, set system, ternary algebra, type fr

This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant No. OGP0000871. This work was done while T. Luba was a Visiting Professor at the University of Waterloo.