TY - CHAP
T1 - On the construction of universal series-parallel functions for logic module design
AU - Young, F.Y.
AU - Wong, D.F.
N1 - Publisher Copyright:
© 1997 IEEE
PY - 1997/10
Y1 - 1997/10
N2 - 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, 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). In [5], the authors studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented in [5] were designed manually and an automatic generation of universal SP functions was left as an open problem. In this paper, we present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. We also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, we developed an algorithm to generate alternative universal SP functions. In particular, we have found all universal SP functions for n-input SP functions, when n≤6.
AB - 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, 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). In [5], the authors studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented in [5] were designed manually and an automatic generation of universal SP functions was left as an open problem. In this paper, we present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. We also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, we developed an algorithm to generate alternative universal SP functions. In particular, we have found all universal SP functions for n-input SP functions, when n≤6.
UR - http://www.scopus.com/inward/record.url?scp=0031357426&partnerID=8YFLogxK
U2 - 10.1109/ICCD.1997.628912
DO - 10.1109/ICCD.1997.628912
M3 - Chapter
AN - SCOPUS:0031357426
SN - 081868206X
T3 - Proceedings of 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors
SP - 482
EP - 488
BT - 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors
PB - IEEE
T2 - 1997 IEEE International Conference on Computer Design, ICCD 1997: VLSI in Computers and Processors
Y2 - 12 October 1997 through 15 October 1997
ER -