論理式簡単化アルゴリズム:A5

石川 啓二  笹尾 勤  寺田 浩詔  

誌名
電子情報通信学会論文誌 D   Vol.J66-D   No.1   pp.41-48
発行日: 1983/01/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
近年,LSI/VLSIの設計が大規模化し,論理設計も自動化が必須となってきた.このため,多変数の論理式を能率良く簡単化する手法が望まれている.本論文では,特に,デコーダ付きプログラマブル・ロジック・アレーを設計する際に必要な,多値入力二値関数を表わす論理式の簡単化アルゴリズム(A5)を提案する.A5は以下の特長をもつ.(1)必須項を検出し,その周辺の項を,未被覆の最小項をできるだけ多く含むように変形するので,多くの疑似必須項が解に入り,項数の少ない論理式を得る,(2)隣接関係により項を類別し,項の検索回数を減少している,(3)拡大可能な変数を検出するので,変数が多い場合でも項を能率良く拡大できる,(4)多出力関数の場合,項の出力変数をなるべく拡大しない方策により,良い解を得る.又,実験により以下の結果を示す.(1)真理値表濃度の小さい関数に対して,高速に(擬似)最簡形式を得る,(2)簡単化アルゴリズムMINIよりも少ない記憶容量で,比較的良い解を得る.