3値カルノー図に基づくCAI向きブール関数簡単化アルゴリズム

苫米地 宣裕  

誌名
電子情報通信学会論文誌 D   Vol.J80-D1   No.7   pp.605-614
発行日: 1997/07/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: ソフトウェア基礎
キーワード: 
ブール関数,  簡単化,  3値カルノー図,  CAI,  

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




あらまし: 
本研究は,論理回路演習用CAIソフトを開発する一環として行ったもので,ブール関数簡単化問題の正解をコンピュータを用いて求める一つの方法を提案している.このCAI応用においては,論理変数の個数は2~5個と限定されるが,処理時間が数秒以内であることが要求される.本論文では,まず,ブール関数の表現法として,論理値が3値をとる3値カルノー図を提案している.次に,本図の特長を生かしたブール関数簡単化アルゴリズムを提案している.簡単化は,はじめに,与式より生じ得るすべての項を3値カルノー図に作成し,次いで,冗長な項を削除していくという手順で行われる.本論文では,第1段階として,与式より主項を求めるまでのアルゴリズムを示している.提案した方法を従来のクワイン-マクラスキ法と比較した結果,提案した方法によれば,処理時間の最大値が従来のクワイン-マクラスキ法による場合の1/9に短縮できることがわかった.