JPH083819B2

JPH083819B2 - 論理回路の製造システム

Info

Publication number: JPH083819B2
Application number: JP61140041A
Authority: JP
Inventors: 和彦松本; 隆夫新舎; 幸夫碇谷; 隆重久保
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1986-06-18
Filing date: 1986-06-18
Publication date: 1996-01-17
Anticipated expiration: 2011-01-17
Also published as: JPS62297974A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は論理回路の製造システムに関し、特に、ディ
ジタルシステムの論理設計において、ブール関数からゲ
ート段数最小，かつ、ゲート数最小の論理回路を自動的
に製造することが可能な論理回路の製造システムに関す
る。

〔従来技術〕

ゲート・レベルの論理設計では、ブール関数の回路構
成を行う場合、回路コストを低下させるためには、ブー
ル式レベルの機能論理からゲート論理を自動生成するこ
と，ゲート数を最小とすること等が必要であり、様々の
方法が提案されている。

例えば、特開昭59−201143号公報に記載の方法では、
ブール式の多分木構造変換を実施した後、その多分木構
造を変形せずに部品を割りあて、ゲート論理を生成して
いるが、人手で行う場合よりもゲート段数やゲート数が
増加するという点については配慮されていない。

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

上記従来技術では、ブール式を二分木構造に変換し、
さらに二分木上で連続する同一の論理オペレータを、実
現すべき回路系固有のファイン数毎に出現順にまとめ、
多分木構造に変換していた。ところが、この変換の際、
生成されるゲート論理のゲート段数は考慮されておら
ず、必ずしも最小のゲート段数によるゲート論理が生成
されないという問題があった。

本発明の目的は、このような問題点を改善し、ゲート
段数最小の条件下で、ブール式からゲート数最小となる
任意の回路系のゲート論理を自動的に生成することが可
能な論理回路の製造システムを提供することにある。

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

上記目的を達成するために、本発明の論理回路の製造
システムは、回路指定情報とともに与えられたブール式
の出力と変数の極性を正，または負論理に論理部品によ
り統一する処理手段（処理装置）と、論理積・論理和等
の論理機能，およびファンイン数・入力極性等の物理制
約を表現し、任意の回路系の製造単位となる部品を蓄積
する手段（ゲートテーブル）を有し、上記二分木構造
を、該ブール式の出力極性をキーとして、該蓄積手段を
参照し、該処理手段を用いて、論理機能・出力極性の一
致を満足する部品を探し、該部品のファンイン数に応じ
て、実現される組み合わせ回路のゲート段数が最小，か
つ、ゲート数が最小となるように上記多分木構造を変換
して、順次、ゲート段数管理を行い、該多分木構造にお
ける各ノードを該部品に写像することで、該ブール式を
満足する組み合わせ回路を製造することに特徴がある。

〔作用〕

処理装置は、任意回路情報とともに与えられたブール
式から任意の回路のゲート論理を生成するために、まず
ブール式を二分木構造に変換し、次に二分木構造で連続
する同一論理オペレータを１つにまとめる多分木構造に
変換する。この多分木構造上の最も出力側のノードから
入力側へ向かって、出力極性をキーとして、順次、物理
ゲート割り当てを行う。割り当てる物理ゲートはゲート
テーブルにて検索を行い、選択した物理ゲートが割り当
て可能となるように、その多分木構造を変形し、ゲート
段数管理を行って、物理ゲートを割り当てる。すなわ
ち、その多分木構造にゲート割り当てを試行し、生成さ
れるゲート論理のゲート段数を求め、その結果によりゲ
ート段数最小で、かつ、ゲート数が最小となるように、
その多分木構造を変形してから物理ゲート構造に変換す
る。

さらに、この物理ゲート構造において、物理ゲートを
対応する基本ゲートごとにブロッキングして、基本ゲー
ト構造に変換し指定された回路系の論理回路を得る。

〔実施例〕

以下、本発明の一実施例を第１図〜第６図により説明
する。

第１図は、本発明の一実施例における論理回路の製造
システムのブロック図である。

本実施例の論理回路の製造システムは、入出力装置12
・16,処理装置14,設計マスタファイル（機能論理）13,
設計マスタファイル（ゲート論理）17,ゲートテーブル1
5より構成される。

入出力装置12は、ブール式とその出力，および変数の
極性等を表現した機能論理図11を入力し、設計マスタフ
ァイル（機能論理）13に渡して、この設計マスタファイ
ル（機能論理）13から機能論理情報を受け、処理装置14
に出力する。

処理装置14は、この設計マスタファイル（機能論理）
13からのブール式や回路指定情報等の機能論理情報と、
ゲートテーブル15に予め準備された実現すべき回路系の
部品群をもとに、論理ゲート構造変換，物理ゲート構造
変換を行い、論理設計の対象となるブール式の論理回路
の基本ゲート割り当てを決める。

入出力装置16は、この基本ゲート割り当てと設計マス
タファイル（ゲート論理）17のゲート論理情報に基づ
き、ゲート論理図18を出力する。

第２図は、本発明の一実施例における論理回路の製造
システムの動作フローチャートである。

まず、入出力装置12は入力された論理回路図11からの
情報を設計マスタファイル（機能論理）13に伝え、該設
計マスタファイル（機能論理）13より、論理設計の対象
となるブール式と回路指定情報を得て、処理装置14に出
力する（201）。

処理装置14は、それらの情報を受け（202）、論理設
計の対象となるブール式に対して論理ゲート構造変換を
行う（203）。すなわち、そのブール式を二分木構造に
変換し、二分木上で連続する同一論理オペレータを１つ
にまとめる多分木構造に変換する。次に、論理ゲート構
造変換によって多分木構造に変換された上記ブール式に
対して物理ゲート構造変換を行う（204）。すなわち、
物理ゲート構造変換で得られた多分木構造の各ノードに
ついて、出力側から順次極性伝搬を行い、また、必要に
より多分木構造を変形し、設計制御を満足する物理ゲー
トをゲートテーブル15から検索して、結線論理割り当
て，複合ゲート割り当て，通常ゲート割り当て，優先順
序つきファンイン振り分け等の割り当てを行う（第３図
参照）。さらに、こうして割り当てられた物理ゲートを
対応する基本ゲートごとにブロッキングして、基本ゲー
ト構造に変換し、ゲート段数最小，かつ、ゲート数最小
の指定された回路系の論理回路構成を得る（205）。こ
うして得られた指定された回路系の論理回路は、入出力
装置16に出力される（206）。

入出力装置16は、その論理回路を設計マスタファイル
17,あるいは論理回路図18に出力する（207）。

第３図は、本発明における物理ゲート構造変換の手順
を示すフローチャートである。

第１図，第２図のように、処理装置14は、論理設計の
対象となるブール式を論理ゲート構造変換によって多分
木構造に変換し、次に、この多分木上の最も出力側にあ
るノードから入力側に向かい、出力極性をキーとして、
ゲートテーブル15に準備された各回路系の部品群（第６
図参照）の中から、設計制御を満足する指定された回路
系の物理ゲートを検索し、それぞれのノードに割り当て
る。こうして検索・選択した物理ゲートが割り当て不可
能な場合は、多分木構造を変形して割り当てる。物理ゲ
ートのタイプは、結線論理ゲート，複合ゲート，通常ゲ
ートに大別され、それらの検索順序は、ゲート段数最
小，かつ、その条件下でゲート数最小とするために、結
線論理ゲート＞複合ゲート＞通常ゲートの順に行う。

それらの検索手順については、第６図のようなゲート
テーブル15の部品群の中から、まず、結線論理検索を行
う（301）。結線論理割り当て条件は、上記ノードと上
記ノードよりも出力側にある物理ゲートとの論理オペレ
ータ種の一致（論理オペレータ種別条件），同様にそれ
らの出力極性の一致（出力極性条件），上記ノードの子
ノードの出力数が上記ノードのファンイン数以内である
こと（ファンイン数条件），上記ノードの後段の物理ゲ
ートが結線論理ではないこと（後段条件），その子ノー
ドが全て入力変数ではないこと（前段条件）である。こ
れらの条件をチェックし（302）、全てを満足する場合
は、結線論理割り当てを行い（309）、ファンイン数条
件のみを満足しない場合は、優先前序つきファイン振り
分けを行う（308）。

優先順序つきファンイン振り分けについては、ファン
イン振り分けの対象となる各子ノードをルートとするサ
ブ・トリー構造の各ノードに対して、物理ゲート割り当
てを試行し、そのサブ・トリー構造における各ノードの
ゲート段数を求め、そのゲート段数の大きい順にこれら
の子ノードに優先順序をつけ、ゲート段数の多い子ノー
ドを元のノードの子ノードとし、ゲート段数の少い子ノ
ードを、元のノードの子ノードとして挿入した元のノー
ドと同一論理オペレータ種のノードの子ノードとして振
り分ける。

これらの場合以外は、次に、複合ゲート検索を行う
（303）。複合ゲート割り当て条件は、上記ノードと複
合ゲートの出力側物理ゲートとの論理オペレータ種の一
致（論理オペレータ種別条件），同じく出力極性の一致
（出力極性条件），上記ノードのファンイン数が複合ゲ
ートの入力側物理ゲートの個数以下であること（ファン
イン数条件），その子ノードが全て入力変数でない場合
は、その子ノードと複合ゲートの入力側物理ゲートとの
論理オペレータ種の一致（前段条件１），およびその子
ノードのファンイン数が複合ゲートの入力側物理ゲート
のファンイン数以下であること（前段条件２）である。
これらの条件をチェックし（304）、全てを満足する場
合は、複合ゲート割り当てを行い（309）、前段条件２
を満足せず、かつ、前段条件２において、子ノードの論
理オペレータ種が少くとも１つ一致する場合は、複合ゲ
ート拡張割り当てを行う（305）。

複合ゲートの拡張割り当てについては、まず、上記前
段条件１を満足しない場合は、割り当てようとしている
複合ゲートの入力側物理ゲートと同一の論理オペレータ
種を有する１入力１出力のノードを挿入して、その子ノ
ードの論理オペレータ種を全てそろえる。次に、上記フ
ァンイン条件を満足しない場合は、優先順序つきファン
イン振り分けを行って、そのノードのファンイン数をそ
の条件に満足させ、上記前段条件２を満足しない場合
は、同じく優先順序つきファンイン振り分けを行って、
その子ノードのファンイン数を調整する。さらに、この
調整されたトリー構造に基づいて複合ゲート割り当てが
なされた展開形と、最初に与えられたトリー構造に基づ
き、複合ゲート割り当て以外で始まる展開形とを比較す
る。そして、よりゲート段数が少い展開形を採用する
が、ゲート段数が同一の場合は、よりゲート数が少い展
開形を採用し、ゲート段数，ゲート数が共に同一の場合
は、複合ゲート割り当てから始まる展開形を採用する。

これらの場合以外は、さらに、通常ゲート検索を行う
（306）。通常ゲート割り当て条件は、上記ノードと上
記ノードよりも出力側にある物理ゲートとの論理オペレ
ータ種の一致（論理オペレータ種別条件），同じく出力
極性の一致（出力極性条件），上記ノードの子ノードの
出力数が上記ノードのファンイン数以内であること（フ
ァンイン数条件）である。これらの条件をチェックし、
全てを満足する場合は、通常ゲート割り当てを行い（30
9）、ファンイン数オーバーの場合は（307）、優先順序
つきファンイン振り分けを行う（308）。また、出力極
性条件を満足しない場合は、後段（出力側）に出力極性
を合わせるめの極性合わせアンプを挿入する。

第４図は、本発明における優先順序つきファンイン振
り分けが生じるゲート展開例であり、第６図は本発明の
ゲートテーブルに格納される回路系の部品群例図であ
る。

処理装置14（第１図参照）は、第４図において、論理
設計の対象となるブール式（ａ）を、まず、二分木構造
（ｂ）に変換し、この二分木構造（ｂ）のノード409〜4
16は、論理オペレータ種が‘・’（AND）であるため、
これらを１つにまとめ、（ｃ）のように多分木構造とす
る。

こうして論理ゲート構造変換された多分木構造（ｃ）
の最も出力側のノード416に割り当てるゲートを、第６
図におけるゲートテーブル15の部品群から選択する。こ
のノード416は、論理オペレータ種‘・',出力極性N,フ
ァンイン数８であるため、結線論理検索を行い、ゲート
No.1のゲート（WAND）を選択するが、ファンイン数条件
（ファンイン数６）を満足せず、ファンインオーバーと
なるので、優先順序つきファンイン振り分けを行う。

この優先順序つきファンイン振り分けでは、（ｃ）の
ように各ノード‘−',およびＢ〜Ｂをノード416の子ノ
ードとする場合（ケース１）と、（ｄ）のように各ノー
ドＢ〜Ｂを挿入ノード‘・’の子ノードとする場合（ケ
ース２）とについて、物理ゲート割り当てを試行しゲー
ト段数を比較する。

ノード‘・'417のゲート段数を比較すると、ケース１
は１段であり、ケース２は挿入ノードを含めて２段であ
る。

ノードＢ〜Ｂについては、ケース１は１段である。ケ
ース２は、後段ゲートがWANDであり、入力変数ノードＢ
〜Ｂが入力変数ノードであるので、結線論理割り当て時
の前段条件を満足させるためのアンプゲートをＢに挿入
した場合は１段となる。

このように、ケース１では、全ての子ノードのゲート
段数は１段であり、ケース２では、ノード‘−’のゲー
ト段数は２段で、その他の子ノードのゲート数は１段で
あるため、ケース２において、ノード‘−’の優先順序
を１とし、その他の子ノードの優先順序を２とし、ファ
ンイン振り分けを行う。

従って、ケース２におけるファンイン振り分けのパタ
ーンについては、（ｄ）のように、優先順序が１のノー
ド‘−'417はノード416の子ノードとし、ノードＢ〜Ｂ
は、ノード416の子ノードとすると各々のノードに１個
ずつアンプゲートが生成されるため、ノード‘・'420を
挿入し、ノードＢ〜Ｂをその子ノードとし、ノードＢは
ノード416の子ノードとして振り分ける。

さらに、（ｄ）の多分木構造におけるノード416に対
して、WANDを割り当て、WANDの入力極性はＮ極であるた
め、Ｎ極をノード417,420,およびＢの出力極性とし、こ
れらの子ノードに対して物理ゲートの検索・割り当てを
行う。また、ノード418に対しても物理ゲートの検索・
割り当てを行う。

このように物理ゲート構造変換を行い、（ｄ）に物理
ゲートを割り当てて、（ｅ）のような物理ゲート構造を
得る。なお、（ｄ）のノード416には結線論理が割り当
てられるため、（ｅ）においては、ノードＢにアンプゲ
ート423が挿入され、また、ノード417にはインバータ42
4が割り当てられる。

最後に、（ｅ）の物理ゲート構造の各ゲートを基本ゲ
ートに置換し、（ｆ）のような基本ゲート構造を生成す
る。なお、この基本ゲート構造においては、（ｅ）にお
けるインバータ424は削除される。

第５図は複合ゲートの拡張割り当てが生じる展開例
図、第６図はゲートテーブルに格納される回路系の部品
例図である。

第１図，第２図のように、処理装置14は、論理設計の
対象となるブール式の論理ゲート構造変換を行い、第５
図のブール式（ａ）から多分木構造（ｂ）を得る。

次に、この多分木構造（ｂ）に対して、第６図のよう
なテーブル15の回路系の部品群を検索・割り当てして、
物理ゲート構造変換を行う。

まず、（ｂ）において最も出力側のノード525に割り
当てる物理ゲートを検索する。ノード525の論理オペレ
ータ種は‘・',出力極性はＰ極，ファンイン数は２であ
る。結線論理検索では、結線論理WANDの出力極性がＮ極
で極性不一致となるため、次に、複合ゲート検索を行
う。ノード525とその子ノード526・527は複合ゲートの
割り当て条件を満足するので、複合ゲートの拡張割り当
てを行う。割り当ての候補となるゲートは、第６図No.2
の複合ゲートである。

ノード525の子ノード527は論理オペレータ種が‘−’
であり、複合ゲートの入力側オペレータ種‘＋’と一致
しないため、（ｃ）のように、１入力１出力のノード
‘＋'529を挿入し、子ノード526・529の論理オペレータ
種を全て‘＋’にそろえる。また、（ｃ）におけるノー
ド526のファンイン数８に対して、入力側物理ゲートの
最大ファンイン数は３であるので、この数になるように
優先順序つきファンイン振り分けを行い、（ｄ）のよう
なトリー構造を得る。そして、このトリー構造（ｄ）に
基づいて、複合ゲート割り当てから始まる物理ゲート割
り当てを行い、（ｅ）のような物理ゲート構造を得る。

さらに、（ｂ）における多分木構造に対して、通常ゲ
ート割り当てから始まる物理ゲート割り当てを試行し、
この物理ゲート割り当てを可能とするようにその多分木
構造を変形して、（ｇ）のようなトリー構造を得る。そ
して、このトリー構造に基づき、（ｈ）のような物理ゲ
ート構造を得る。

こうして得られた（ｅ）と（ｈ）とのゲート展開図を
比較すると、（ｅ）ではゲート２段、（ｈ）ではゲート
３段となるため、（ｅ）の展開形を採用する。

最後に、基本ゲート構造変換を行い、（ｅ）における
物理ゲート構造から（ｆ）のような基本ゲート構造を得
る。なお、（ｇ）に対して基本ゲート構造変換を行った
場合は、（ｉ）のようになる。

本実施例によれば、論理設計の対象となるブール式か
ら、最小ゲート段数で、かつ、最小ゲート数である論理
回路を自動的に製造することができる。

〔発明の効果〕

本発明によれば、ゲート段数管理を行い、論理設計の
対象となるブール式の回路系における最小段数を選択す
ることにより、ブール式から任意回路系における最小ゲ
ート段数で、かつ、最小ゲート数を有する論理回路を自
動的に生成することが可能であり、論理設計品質の向
上，および論理設計工数の削減に効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例における論理回路の製造シス
テムのブロック図，第２図は本発明の一実施例における
論理回路の製造システムの動作フローチャート，第３図
は本発明における物理ゲート構造変換の手順を示すフロ
ーチャート，第４図は本発明における優先順序つきファ
ンイン振り分けが生じるゲート展開例図，第５図は本発
明における複合ゲートの拡張割り当てが生じるゲート展
開例図、、第６図は本発明のゲートテーブルに格納され
る回路系の部品群例図である。 11:機能論理図,12・16:入出力装置,13:設計マスタファ
イル（機能論理）,14:処理装置,15:ゲートテーブル、1
7:設計マスタファイル（ゲート論理）,18:ゲート論理
図,409〜418・420・525〜529:ノード、423:アンプゲー
ト,424:NOTゲート（インバータ）。

───────────────────────────────────────────────────── フロントページの続き (72)発明者久保隆重神奈川県川崎市麻生区王禅寺1099番地株式会社日立製作所システム開発研究所内 (56)参考文献特開昭59−201143（ＪＰ，Ａ) 特開昭59−168545（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】論理設計の対象となるブール式表現による
機能論理を入力する手段を備え、前記手段によって与え
られたブール式を満足し、かつ一群の論理部品の接続で
示される組合せ論理回路を製造する論理回路の製造シス
テムにおいて、採用可能な論理部品のそれぞれについて、その論理機能
の種類、入出力極性及びファンイン数等の物理制約、並
びに、結線論理、複合ゲート及び通常ゲートの区分を示
すデータを蓄積する蓄積手段と、前記与えられたブール式表現による機能論理を演算子・
変数の二本木構造に変換し、前記二本木構造上で連続す
る同一論理オペレータを１つにまとめて第１の多分木構
造に変換し、さらに前記蓄積手段を参照しながら前記第
１の多分木構造を変形して第２の多分木構造を作成し、
前記第２の多分木構造の各ノードを前記論理部品に写像
して前記組合せ論理回路を決定する処理装置と、決定した組合せ論理回路を出力する手段とを有し、前記処理装置は前記第１の多分木構造から第２の多分木
構造への変形の際に、１）前記第１の多分木構造の出力側のノードから順次部
品の割当てを行ない、２）部品の割当ては結線論理を最優先で行ない、さらに３）当該ノードのファンイン数がオーバしていることに
より部品の割当てができない場合は、各ノードのゲート
段数に応じた優先順序に従ってファンイン振り分けを試
行し、振り分けにより生じる子ノードのゲート段数が最
小になるファンイン振り分けを選択することを特徴とす
る論理回路の製造システム。
【請求項２】特許請求の範囲第１項に記載の論理回路の
製造システムにおいて、前記処理装置は、前記第１の多分木構造から第２の多分
木構造への変形の際に前記複合ゲートを割り当てる場合
は、まず複合ゲートの割り当てを試行し、前記通常ゲー
トを割り当てた場合とゲート段数及び部品数の比較を行
ない、これらが少ない方の多分木構造を選択することを
特徴とする論理回路の製造システム。