近接関数を用いた多出力論理関数の最小化について

スポンサーリンク

概要

論文の詳細を見る
論理関数最小化問題、すなわち論理関数の最小積和形を求める問題は、論理設計における基本的問題として古くから研究されている。また、その拡張である多出力論理関数最小化問題は、PLAの最小化問題とあいまって、論理設計における重要な問題の1つとなっている。しかしQuine-McCluskey法に代表される従来の論理関数最小化アルゴリズムは、最小化を全素項の組み合わせ問題として解いているため、莫大な計算量が必要となる。本稿では、近接関数を用いた多出力論理関数の最小化アルゴリズムを提案する。本稿のアルゴリズムは近接関数を用いることにより、全素項の生成をおこなうことなく、必須項、選択項を直接生成できる。また近接関数は、解の項数の下界の算出にも有効であることから、分枝限定法における枝刈りにも効果がある。したがって、従来のアルゴリズムに較べて、高速であると考えられる。
1989-10-16

著者

関連論文

もっと見る

スポンサーリンク