著者

松永 裕介

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.37, pp.57-63, 2000-05-11

被引用文献数

10

---

本稿では,与えられた論理関数に対して直交でない関数分解を求める効率の良いアルゴリズムについて述べる.このアルゴリズムは著者が以前開発した二分決定グラフを用いて直交分解を行うアルゴリズムを利用したものである.通常,直交でない関数分解は多数存在するので無制限に関数分解の列挙を行うことは難しいので,重複した変数の個数が規定値以下の関数分解のみを列挙する様になっている.7入力程度の論理関数に対して適用したところ,ナイーブなアルゴリズムに比べて5?6倍の高速化が達成されている.This paper describes an efficient algorithm enumerating all the non-disjunctive decomposition of a given function. The algorithm utilizes the disjunctive decomposition algorithm using binary decision diagrams that the authors have previously developed. Since, in general, there exist too many non-disjunctive decompositions for ordinary logic functions, the algorithm restricts to enumerate only decompositions whose duplicated variables are less than the given limit. Comparing to the existing naive algorithm, about 5 or 6 times acceleration has been observed for a case of applying to 7-inputs functions.