Bounds on the OBDD-size of integer multiplication via universal hashing

摘要

Bryant [On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication, IEEE Trans. Comput. 40 (1991) 205–213] has shown that any OBDD for the function MULn-1,n, i.e. the middle bit of the n-bit multiplication, requires at least 2n/8 nodes. In this paper a stronger lower bound of essentially 2n/2/61 is proven by a new technique, using a universal family of hash functions. As a consequence, one cannot hope anymore to verify e.g. 128-bit multiplication circuits using OBDD-techniques because the representation of the middle bit of such a multiplier requires more than 3·1017 OBDD-nodes. Further, a first non-trivial upper bound of 7/3·24n/3 for the OBDD-size of MULn-1,n is provided.