### Generation of universal series-parallel Boolean functionsGeneration of universal series-parallel Boolean functions

Access Restriction
Subscribed

 Author Young, F. Y. ♦ Chu, Chris C N ♦ Wong, D. F. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1999 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword FPGA ♦ Series-parallel Boolean functions ♦ Technology mapping ♦ Universal functions Abstract 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 FTGA design, it is desirable to design FPGA logic modules based on Boolan 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; 1966b] 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 $\textit{n}$ > 0, a universal SP function $\textit{fn}$ for implementing all SP functions with $\textit{n}$ inputs or less. The number of variables in $\textit{fn}$ is less than $\textit{n}2.376$ and the constructions are the smallest possible when $\textit{n}$ is small $(\textit{n}$ ≤ 7). We also derived a nontrival lower bound on the sizes of the optimal universal SP functions $(&OHgr;(\textit{n}$ log $\textit{n})).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1999-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 46 Issue Number 3 Page Count 20 Starting Page 416 Ending Page 435

#### Open content in new tab

Source: ACM Digital Library