On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication

Abstract

Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity AT/sup 2/= Omega (n/sup 2/) also proves that any OBDD representation of the function has Omega (c/sup n/) vertices for some c>1 but that the converse is not true. An integer multiplier for word size n with outputs numbered 0 (least significant) through 2n-1 (most significant) is described. For the Boolean function representing either output i-1 or output 2n-i-1, where 1<or=i<or=n, the following lower bounds are proved: any VLSI implementation must have AT/sup 2/= Omega (i/sup 2/) and any OBDD representation must have Omega (1.09/sup i/) vertices.<<ETX>>