Totally undecomposable functions: applications to efficient multiple-valued decompositions
作者： T. Sasao
DOI: 10.1109/ISMVL.1999.779696
关键词: Mathematics 、 Discrete mathematics 、 Symmetric function 、 Function (mathematics) 、 Functional decomposition 、 Lookup table 、 Space (mathematics)
摘要: A function f:P/sup n//spl rarr/P, P={0, 1, ..., p-1} is k-decomposable iff f can be represented as f(X/sub 1/, X/sub 2/)=g(h/sub 1/(X/sub 1/), h/sub 2/(X/sub k/(X/sub 2/), where (X/sub 2/) a bipartition of input variables. This paper introduces the notion totally k-undecomposable functions. By using this concept, we drastically reduce search space to find k-decompositions. systematic method bipartitions variables that will not produce any k-decompositions presented. combining it conventional decomposition methods, build an efficient functional system. promising design LUT-based FPGAs.
sci-hub.se 参考文章(15)
T. Sasao, Munehiro Matsuura, DECOMPOS : An integrated system for functional decomposition 1998 International Workshop on Logic Synthesis, Lake Tahoe, June 1998. ,(1998)
Logic Synthesis and Optimization Kluwer Academic Publishers. ,(1997) , 10.1007/978-1-4615-3154-8
T. Sasao, Application of multiple-valued logic to a serial decomposition of PLAs international symposium on multiple-valued logic. pp. 264- 271 ,(1989) , 10.1109/ISMVL.1989.37794
C. Files, R. Drechsler, M.A. Perkowski, Functional decomposition of MVL functions using multi-valued decision diagrams international symposium on multiple-valued logic. pp. 27- 32 ,(1997) , 10.1109/ISMVL.1997.601370
S. Devadas, A.R. Wang, A.R. Newton, A. Sangiovanni-Vincentelli, Boolean decomposition in multilevel logic optimization IEEE Journal of Solid-state Circuits. ,vol. 24, pp. 399- 408 ,(1989) , 10.1109/4.18601
Tsutomu Sasao, Jon T. Butler, On Bi-Decompositions of Logic Functions Defense Technical Information Center. ,(1997) , 10.21236/ADA593005
Claude. E. Shannon, The synthesis of two-terminal switching circuits Bell System Technical Journal. ,vol. 28, pp. 59- 98 ,(1949) , 10.1002/J.1538-7305.1949.TB03624.X
J. Paul Roth, R. M. Karp, Minimization over Boolean graphs Ibm Journal of Research and Development. ,vol. 6, pp. 227- 238 ,(1962) , 10.1147/RD.62.0227
Marek A. Perkowski, Wei Wan, A new approach to the decomposition of incompletely specified multi-output functions based on graph coloring and local transformations and its application to FPGA mapping european design automation conference. pp. 230- 235 ,(1992) , 10.5555/159754.161757
Y.-T. Lai, M. Pedram, S.B.K. Vrudhula, EVBDD-based algorithms for integer linear programming, spectral transformation, and function decomposition IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 13, pp. 959- 975 ,(1994) , 10.1109/43.298033