出力変数の分割による大規模回路の特徴関数生成手法

概要

論文の詳細を見る
本稿では組合せ回路の出力変数をいくつかのグループに分割することにより、出力変数がとりうる論理値の集合を表す特徴関数を高速に生成するための手法を提案する。特徴関数は有限集合を表現する手段の一つであり、集合の要素を2進符号化して論理関数で表現したものである。近年、二分決定グラフ(以下BDD)を用いた技術の発展により論理関数処理を効率的に行うことができ、大規模な組合せ回路に対する特徴関数を生成することが可能となってきている。しかし、依然として扱える回路規模には限界がある。本手法では、論理関数の出力変数を相互に関連の強いものから構成されるグループに分割して特徴関数を生成する。これにより、必要となるBDDのノード数は少なくなり、従来よりも大規模な回路の特徴関数を生成することができる。この方法で得られた特徴関数は真の解を持つ特徴関数とは異なる。しかし、論理検証などにおいて周辺回路から入力の制約を求める場合など、必ずしも真の解を求める必要はない。本手法により、真の解に近い解を持つ特徴関数を大規模な回路から取り出すことが可能となる。
一般社団法人情報処理学会の論文
1997-02-14