JPS62274367A - 自動論理設計システムの論理最適化方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ３、発明の詳細な説明 〔産業上の利用分野〕 本発明は、ディジタル論理システムの論理設計を計算機
で行う自動論理設計システムの論理最適化方法に関する
。

〔従来の技術〕

従来、カルノー図を用いた論理式簡単化方法は。

文献「コンピュータサイエンス大学講座計算機の論理設
計（中用圭介著、近代科学社刊）」に記載されているよ
うに１つの論理式を対象としておこなわれてきた。

しかし、複数の論理式を同時に取り扱いカルノー図を用
いて簡単化をおこなうことはなされてこなかった。

〔発明が解決しようとする問題点〕

従来、カルノー図を用いた論理式簡単化は、１つの論理
式を対象になされてきた。しかし、複数の論理式をその
相互の関連を考えながら同時に簡単化を行うと、ゲート
数削減効果が大きくなる場合があり、その点については
従来の方法では配慮がなされていなかった。

本発明の目的は、上述した問題に鑑み、複数の論理式を
対象に、その相互の関連を考慮しながらカルノー図を用
いて論理式の簡単化を行いゲート数の削減効果をもたら
す論理最適化方法を提供することにある。

〔問題点を解決するための手段〕

本発明では、生成された複数の論理式と同時にカルノー
図に展開し、加えてカルノー図同志を比較することによ
り、カルノー図上で論理式間の重複を見い出し、１つに
統合することで上記目的を達生する。

゛〔作用〕 簡単化の対象となる論理式を各々カルノー図に展開する
。各カルノー図中、共通に１が立つ部分を検出し、それ
に対応する論理式を先の簡単化の対象となった複数の論
理式の共通部分として抽出する。抽出された論理式をも
とに簡単化の対象となった複数の論理式を重複した部分
と重複していない部分とに分け１重複している部分を１
つに統合し、論理を再構成する。これにより、各論理式
の重複部分が統合されるためゲート数が削減される。

〔発明の実施例〕

以下、本発明の一実施例を図面を用いて詳細に説明する
。

第２図は、論理式を内容として持つ、最適化しようとす
る計算機の２つの論理要素１１０，１２０の例であり、
その概要は次のとおりである。

論理要素１１０には、Ａ１３０．Ｂ１４０．Ｃ１５０，
０１６０の４種類の信号が入力し、含まれる論理式によ
って信号を形成し、出力信号０１１９０となって出力す
る。論理要素１２０には、Ａ１３０．Ｂ１４０．Ｃ１５
０，Ｄ１６０＋７１４種類の信号が入力し、含まれる論
理式によって信号を形成し、出力信号０２１９５となっ
て出力する。

これらの論理要素は、たとえば、特開昭６０−１６７０
６０号あるいは、特開昭６０−２０４０７８号に公知の
次に示す自動論理設計システムによって生成される。

第１図は、自動論理設計システムの概要を示す図である
。自動論理設計システムは、大別して。

入力部６１５、構文解析部６２０．論理生成部６２５、
出力部６３０とからなる。

本論理最適化処理部６５０は、論理生成部６２５の一部
として存在し、論理式格納テーブル６４０に格納されて
いる論理生成部で生成された論理式を入力とし、論理式
最適化を行い、出力する。

次に、論理最適化処理方法の詳細について記述する０本
名処理方法は、統合可能性検査処理部、論理式カルノー
図展開処理部、重複論理統合処理部の３処理部とからな
る。

［統合可能性検査処理部」′ 論理式格納テーブル６４０に格納されている論理式を複
数個選択し、本処理方法の統合可能性検査処理部に入力
する。ここでは、複数個の論理式の中で統合できる可能
性の高い論理式を選択する。

「論理式カルノー図展開処理部」 統合可能性検査処理部で、統合可能性が高いと判定され
た論理式の組は、論理式カルノー図展開処理部によって
カルノー図に展開される。この時。

あとの処理に便利なように、複数のカルノー図において
、同じ信号名は、カルノー図上同じ位置に占めるように
する。

「重複論理統合処理部」 次に、論理式カルノー図展開処理部によって得られたカ
ルノー図を重複論理統合処理部で処理する。即ち、カル
ノー図上で、共通に１が立つ部分に対応する論理式を重
複とする論理式としてくくり出す。

以下、具体的な処理手順を第２図の論理要素１１０．１
２０を例に、第３図に従って説明する。

第３図は、計算機の記憶装置に記憶されて作動する本最
適化処理プログラムのフローチャートを示す、第２図の
論理要素１１０，１２０が内容として持つ論理式を、現
在着目している２つの論理式の組として、統合可能性検
査５２０に入力する。

統合可能性検査５２０では、入力された２つの論理式が
、統合される可能性が高いか否かの検査をする。

統合可能性検査５２０で、統合可能性が高いと判定され
た論理式の組は、次に論理式の変形処理５３０で処理さ
れる。ここで、各論理式はカッコを展開され積和形とな
り、共通していない信号名をリテラルとして含む項は、
削除される。その結果をカルノー図に展開する。

第４図、カルノー図３１０は、第２図論理要素１１０に
含まれる論理式をカルノー図に展開したものであり、第
４図、カルノー図３２０は、第２図論理要素１２０に含
まれる論理式をカルノー図に展開したものである０本図
は、カルノー図を主記憶上の２次元テーブルに表現した
ものである。

第４図において、両輪理要素に共通な信号、たとえば、
Ａ３３０．Ａ３４０は、カルノー図上で同じ位置を占め
るようにする。又、カルノー図３１０において、領域３
５０は、論理式の１つの項Ａ・Ｂを表現する。

次に、第３＠において、カルノー図に展開された論理を
論理式の重複部分の統合処理５４０に入力する。ここで
、各カルノー図間で共通に１が立つ領域を検出する。第
４図で、カルノー図３１０とカルノー図３２０を比較し
た場合、領域３５０と領域３６０、及び領域３７０と領
域３８０とが、共通に１が立つ領域として検出される。

検出の範囲は、カルノー図上縦・横２項とした。検出の
範囲の規定はプログラムとして実現する場合にパラメー
タで変更できるようにしておけばよい。

次に、上で検出された共通に１が立つ領域に対応する論
理式を求める。求められた論理式が、各論理式間の共通
部分に当る。第４図において、領域３５０と領域３６０
とから、Ａ−Ｂが求まる。

又領域３７０と領域３８０とからＢ−Ｃが求まる。

これらを１つにまとめ、新たに１つの論理要素とする。

第５図は１以上の処理によって第２図の論理要素１１０
と論理要素１２０の論理式の共通部分を１つの論理要素
にまとめた結果である。論理要素４１０が、新しく統合
されてできた論理要素である。さらに第２図の論理要素
１１０に含まれる論理式から、論理要素４１０に含まれ
る論理式の共通部分を除いた残りが、論理要素４２０に
含まれる論理式となる。又第１図の論理要素１２０に含
まれる論理式から、論理要素４１０に含まれる論理式の
共通部分を除いた残りが、論理要素４３０に含まれる論
理式となる。さらに論理要素４２０と論理要素４１０と
の出力をＯＲゲート４４０で結ぶことによって、その出
力信号０１４９０は、出力信号０１１９０と同一となる
。出力信号０２４９５についても、第１図、出力信号０
２１９５と同一となる。

〔発明の効果〕

以上述べたように１本発明によれば、複数の論理式を同
時にカルノー図に展開し、論理式間の重複部分を検出し
、１つにまとめるので、自動的に生成された回路内で冗
長な論理を削除し、ゲート数の削減に効果がある。

【図面の簡単な説明】 第１図は、本発明による自動論理設計システムの構成例
を示す図、第２図は、最適化しようとする計算機論理の
例を示す図、第３図は１本最適化処理プログラムの処理
手順の一例を示すフローチャート、第４図は、第２図の
論理をカルノー図に展開した結果を示す図、第５図は、
第２図の計算機論理を１本最適化処理方法で処理した結
果を示す図。 ６２０・・・構文解析部、６２５・・・論理生成部、６
５０・・・論理最適化処理部、６４ｏ・・・論理式路内
テーブル。 冨　１　国 寄　Ｚ　図 ／／ρ ｆＪ　３　図 ￥Ｊ　４　図 （Ｌ） （ｂン ９９９Ｅ）

Claims (1)

【特許請求の範囲】
1. １、設計すべきディジタル論理システムの構成要素の種
   別を示すデータと、該構成要素間のデータ転送仕様を示
   すデータを入力し、複数の構成要素のそれぞれを制御す
   る制御論理を示す論理式を生成する論理設計システムに
   おいて、該生成された複数の論理式を、論理的な共通部
   分が検出できるように変形し、共通部分を検出し、１つ
   にまとめることを特徴とする自動論理設計システムの論
   理最適化方法。