Generation of universal series-parallel Boolean functions

F. Y. Young*, Chris C. N. Chu, D. F. Wong

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique 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., series-parallel or SP functions). Thakur and Wong [1996a; 1996b] studied this issue and they demonstrated the advantages of designing logic modules as universal SP functions, that is, SP functions which can implement all SP functions with a certain number of inputs. The number of variables in the universal 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 functions. 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 variables in the generated functions grows exponentially. In this paper, we present an algorithm to generate, for each n > 0, a universal SP function fn for implementing all SP functions with n inputs or less. The number of variables in fn is less than n2.376 and the constructions are the smallest possible when n is small (n ≤ 7). We also derived a nontrivial lower bound on the sizes of the optimal universal SP functions (Ω(n log n)).

Original languageEnglish
Pages (from-to)416-435
Number of pages20
JournalJournal of the ACM
Issue number3
Publication statusPublished - May 1999

Scopus Subject Areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

User-Defined Keywords

  • FPGA
  • Series-parallel boolean functions
  • Technology mapping
  • Universal functions


Dive into the research topics of 'Generation of universal series-parallel Boolean functions'. Together they form a unique fingerprint.

Cite this