論理関数の主項を高速に導出する手法―部分マップ法について―

松田 秀雄  宮腰 隆  

誌名
電子情報通信学会論文誌 D   Vol.J67-D   No.2   pp.208-215
発行日: 1984/02/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
本論文では大量に与えられた論理関数の主項を計算機で高速に導出する手法として部分マップ法を提案する.手法は論理設計で使われるカルノー図などのマップの部分マップの概念を用いて説明できる.基本部分マップ法では,与えられた論理関数の主項は各部分マップごとに許容キューブを発生して,関数の内項かどうかを調べることにより求められる.分割法では与えられたn(=n1n2)変数の論理関数を3n2個のより小さなn1変数の論理関数に分割し,それぞれに基本部分マップ法を適用して主項を求め,これからもとの関数の主項を合成していく方法をとって,40%近くの計算時間の短縮を行っている.この分割法の導入により,いまはやりの再帰的プログラムが組めるようになり,再帰法の検討も行っている.主項を導出するアルゴリズムでは途中で得られる主項候補と既に得られている主項との包含関係の照合にかなりの計算時間が費やされる.改善分割法ではn2変数のマップのキューブの包含関係の情報をあらかじめ用意しておくことによりこの点の改善を試みたもので,例えば12変数の論理関数の場合で,節展開法に比べ10倍も早く主項が求まるという非常に強力な方法である.