Generation of universal series-parallel Boolean functions

The structural tree-based mapping algorithm is an efficient and popular tec hnique for technology mapping. In order to make good use of this mapping te chnique in FPGA design, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e., ser ies-parallel or SP functions). Thakur and Wong [1996a; 1996b] studied this issue and they demonstrated the advantages of designing logic modules as un iversal SP functions, that is, SP functions which can implement all SP func tions with a certain number of inputs. The number of variables in the unive rsal function corresponds to the number of inputs to the FPGA module, so it is desirable to have as few variables as possible in the constructed funct ions. The universal SP functions presented in Thakur and Wong [1996a; 1996b ] were designed manually. Recently, there is an algorithm that can generate these functions automatically [Young and 'Wong 1997], but the number of va riables in the generated functions grows exponentially. In this paper, we p resent an algorithm to generate, for each n > 0, a universal SP function f( n), for implementing all SP functions with n inputs or less. The number of variables in f(n) is less than n(2.376),,and the constructions are the smal lest possible when n is small (n less than or equal to 7). We also derived a nontrivial lower bound on the sizes of the optimal universal SP functions (Omega(n log n)).