An Efficient Method for Finding an Optimal Bi-Decomposition
-
- YAMASHITA Shigeru
- NTT Communication Science Laboratories
-
- SAWADA Hiroshi
- NTT Communication Science Laboratories
-
- NAGOYA Akira
- NTT Communication Science Laboratories
この論文をさがす
説明
This paper presents a new efficient method for finding an "optimal" bi-decomposition form of a logic function. A bi-decomposition form of a logic function is the form : f (X) = α (g_1(X^1), g_2 (X^2)). we call a bi-decomposition form optimal when the total number of variables in X^1 and X^2 is the smallest among all bi-decomposition forms of f. This meaning of optimal is adequate especially for the synthesis of LUT (Look-Up Table) networks where the number of function inputs is important for the implementation. In our method, we consider only two bi-decomposition forms ; (g_1・g_2) and (g_1【◯!+】g_2). We can easily find all the other types of bi-decomposition forms from the above two decomposition forms. Our method efficiently finds one of the existing optimal bi-decomposition forms based on a branch-and-bound algorithm. Moreover, our method can also decompose incompletely specified functions. Experimental results show that we can construct better networks by using optimal bi-decompositions than by using conventional decompositions.
収録刊行物
-
- IEICE transactions on fundamentals of electronics, communications and computer sciences
-
IEICE transactions on fundamentals of electronics, communications and computer sciences 81 (12), 2529-2537, 1998-12-01
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1573387452278459136
-
- NII論文ID
- 110003216437
-
- NII書誌ID
- AA10826239
-
- ISSN
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles