2値論理関数簡単化の一手法―部分マップ法について―

宮腰 隆  松田 秀雄  

誌名
電子情報通信学会論文誌 D   Vol.J71-D   No.11   pp.2259-2265
発行日: 1988/11/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 計算機構成要素
キーワード: 


本文: PDF(592.5KB)>>
論文を購入




あらまし: 
ヒューリスティックな手続きで,論理関数の簡単化を行う二つのアルゴリズムSUB1およびSUB2を提案している.これらの手法では内項の生成,拡大,必須主項の検出に我々独自の部分マップ法を用いている.SUB1は必須主項,疑似必須主項を特異セルの有無より判定する厳密な方法であり,精度の高い解が求まる.一方,SUB2は周辺隣接セルより各Trueセルを評価し,その値が最小であるセルを優先的に選出し,主項にまで拡大した後,解に採用するという方法でSUB1より高速処理できる.SUB1およびSUB2のほかに,A5アルゴリズム,DIRECT法,QUAMINの五つの手法を,2値論理の場合に限定はしているが,同一言語,同一計算機で実行させた結果で性能を評価している.例えば,10変数関数70個の平均値で,SUB2はディスジョイント・シャープ演算を多用するA5と比較して100倍以上,比較的高速なQUAMINと対比しても,2倍ほど早く解が求まる.また,精度においても,SUB1が優れていることが確認できる.最後に,SUB2を多出力関数向きに拡張し,いくつかの関数例で,ESPRESSO-Cと比較してもそん色のないことを示す.