Multi-Level Logic Simplification Using Local Don't Care Extraction Based on Stepwise Enhancement

朱 強(9851134)


Combinational logic circuits are usually implemented as multi-level networks of logic gates, and the simplification of multi-level networks is very important. A basic algorithm for the simplification of multi-level networks is to optimize the components by utilizing don't care set due to the structure of the networks. However, the size of don't care set is very large and therefore the calculation of the don't care set needs huge computational cost. In the paper, we consider an adaptive subnetwork for each simplified node in the network and introduce a stepwise enhancement method of the subnetwork considering the memory area and the structure of the Boolean network. Don't cares extracted from the adaptive subnetworks is called the local don't cares. We have implemented our method for SDC and ODC based simplification and applied for MCNC89 benchmarks. We compare the experimental results with those of the SIS system. The results demonstrate the superiority of our method with respect to the SIS simplify command in the most circuits and got the simplified results for those circuits which can not be simplified by SIS full_simplify command.


組合せ回路の多段化では、用いる簡単化手法により大きく素子の数が異なる。 多段論理回路の簡単化では、ネットワークの接続関係によるドントケアを 抽出し、二段最小化アルゴリズムを用いて節点の関数の簡単化を行なう。しか し、すべてのドントケアを考慮しようとすると、ドントケアのサイズが大きく なり、回路の簡単化には莫大な記憶容量と計算コストを必要とする。これまで は、回路の外部入力を変数としたグローバル関数を用いて、ドントケアを計 算する手法が提案されたが、グローバル関数がメモリ容量の制限によって求め られない場合には、簡単化できないという問題があった。本研究では、回路の構造及 び計算環境を考慮し、与えられた制約のもとで最適に近い簡単化結果を保証す る手法を提案する。本手法では、回路を簡単化するため、ネットワークの各節 点のローカルネットワークを切り出し、ローカルネットワーク内のドントケア だけ考慮する。それをMCNC89ベンチマーク回路に適用し、SISシステムの結果 との比較を行なった。多くの回路では、SISのsimplifyコマンドより優れた結 果が得られ、full\_simplifyで処理出来ない大規模の回路についても処理可能と なっ た。