(57)【特許請求の範囲】
【請求項１】
ＦＥＴモデル回路からゲートモデル回路を抽出するための方法であって、コンピュータが、
（ａ）前記ＦＥＴモデル回路の接続状態を表すネットリストのデータを読み込むステップと、
（ｂ）前記ＦＥＴモデル回路の前記ネットリストから、電源およびグラウンドを検出して、該コンピュータの記憶装置に保存するステップと、
（ｃ）前記ＦＥＴモデル回路の前記ネットリストから、すべての論理信号を検出して、前記記憶装置に保存するステップと、
（ｄ）１つまたは複数の構造ベースのブールの部分木を生成するステップであって、
ｉ）前記保存された論理信号のそれぞれを、該部分木の根に設定し、
Ａ）前記根に設定した論理信号に、ソースまたはドレインを介して接続されたＦＥＴを、前記ネットリストから識別して、該部分木の幹に設定し、
Ｂ）ソースおよび／またはドレインの接続を介して、前記幹に設定されたＦＥＴに接続されたＦＥＴを、前記ネットリストから識別して、該幹の枝に設定し、
Ｃ）前記枝が、前記保存された論理信号、前記電源、または前記グラウンドに達したとき、該枝を終端させる、ことにより該部分木を生成し、
該生成された部分木は、Ａ）論理信号を低に駆動するＦＥＴを表す０−木と、Ｂ）論理信号を高に駆動するＦＥＴを表す１−木と、を含む、ステップと、
（ｅ）前記生成された１つまたは複数の構造ベースのブールの部分木に対し、発見的に枝刈りするステップであって、該枝刈りは、該部分木によって表されるＦＥＴおよびポートの方向を見極めつつ、所定の規則に従って不要と判断される枝を、該部分木から削除することを含み、該部分木によって表されるすべてのＦＥＴおよびポートの方向を見極めたことに応じて、該枝刈りを完了する、ステップと、
（ｆ）前記枝刈りが完了した１つまたは複数の構造ベースのブールの部分木を、ブールの論理方程式に変換するステップと、
（ｇ）前記論理方程式に従ってゲートのプリミティブをマップすることにより、前記ゲートモデル回路のネットリストのデータを生成するステップと、
を含む方法。
【請求項２】
前記ステップ（ｄ）に先だって、前記ＦＥＴモデル回路のネットリストにおけるそれぞれのＦＥＴについて、前記電源またはグラウンドから開始して該ＦＥＴのソースおよびドレインの接続を横断することによって、最初のＦＥＴ方向を推定するステップを含み、
該ＦＥＴの駆動される端が、他の１つのＦＥＴのみに接続されていると共に、ポート、ＦＥＴゲート、または非ＦＥＴインスタンスに接続されていない限り、該横断は、該ＦＥＴに続いて該他の１つのＦＥＴについても行われる、
請求項１に記載の方法。
【請求項３】
前記ステップ（ｄ）に先だって、冗長なＦＥＴを削除するステップをさらに含む、
請求項１または２に記載の方法。
【請求項４】
さらに、
ａ）前記部分木のそれぞれについて、最大の強さを計算するステップであって、該最大の強さは、該部分木において枝が直列になっているパスのうちの、最も低い抵抗を示すパスの抵抗に対応する、ステップと、
ｂ）前記ステップ（ｆ）に先立ち、前記部分木において帰還木を検出することにより、該部分木を、弱くない部分木と弱い部分木とに分類するステップであって、該帰還木は、２つの交差結合される部分木であり、該２つの交差結合される部分木のそれぞれは、該２つの交差結合される部分木の他方の根を入力として有する、ステップと、
を含む、請求項１または２に記載の方法。
【請求項５】
前記保存された論理信号のそれぞれについて、
ａ’）弱い部分木であって１−木である部分木を併合するステップと、
ｂ’）弱い部分木であって０−木である部分木を併合するステップと、
ｃ’）弱くない部分木であって１−木である部分木を併合するステップと、
ｄ’）弱くない部分木であって０−木である部分木を併合するステップと、
をさらに含み、該併合によって出力されるａ’）からｄ’）の４つの構造ベースのブール木を、それぞれの該論理信号について生成し、
前記ステップ（ｆ）は、該４つの構造ベースのブール木のそれぞれを、前記論理方程式に変換するステップを含む、
請求項４に記載の方法。
【請求項６】
前記ステップ（ｆ）に先立ち、前記部分木に含まれるサブツリーの並列の組み替えを実行するステップであって、該組み替えは、該部分木における重複したノードの上方にある木構造を組み合わせることによって達成される、
請求項５に記載の方法。
【請求項７】
共通の前記論理信号を根に持つ前記弱い部分木および弱くない部分木について、論理関数を決定するステップをさらに含む、
請求項６に記載の方法。
【請求項８】
さらに、前記決定した論理関数を、対応するゲートのプリミティブにマップすることを含む、
請求項７に記載の方法。
【請求項９】
前記ステップ（ｅ）は、矛盾するゲート信号を有するＦＥＴによって駆動される部分木の枝を削除することを含む、
請求項１または２に記載の方法。
【請求項１０】
前記ステップ（ｅ）は、さらに、
ａ）前記部分木に表されるポートのポート方向を見極めるステップと、
ｂ）前記部分木に表されるＦＥＴのＦＥＴ方向を見極めるステップと、
ｃ）前記ポート方向または前記ＦＥＴ方向を見極めることができないとき、ユーザに該ポート方向または該ＦＥＴ方向の提供を促すステップと、
を含む請求項１に記載の方法。
【請求項１１】
さらに、前記ＦＥＴモデル回路の前記ネットリストから、クロック信号を検出して、該コンピュータの記憶装置に保存するステップを含み、
前記ステップ（ｆ）は、該検出されたクロック信号に少なくとも部分的に基づいて、該ブールの部分木を、該論理方程式に変換する、
請求項１に記載の方法。
【請求項１２】
さらに、前記ＦＥＴモデル回路の前記ネットリストから、インバータを検出して、該コンピュータの記憶装置に保存するステップを含み、
前記ステップ（ｆ）は、該検出されたインバータに少なくとも部分的に基づいて、該ブールの部分木を、該論理方程式に変換する、
請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ＦＥＴモデル回路からゲートモデル回路を抽出する方法と装置に関し、特に、ＦＥＴモデル回路と構造上の一致を保持するゲートモデル回路を抽出する方法と装置に関する。
【０００２】
【従来の技術】
集積回路(ＩＣ)は電界効果トランジスタ(ＦＥＴ)を用いて設計され、組み立てられるが、多くのツールはＩＣのゲートレベル・モデル(または少なくとも非常に制限された数のＦＥＴを用いるモデル)を必要とする。ＩＣのＦＥＴモデルは、ＦＥＴ、ワイヤおよび他の構造素子(非ＦＥＴインスタンス(non-fet instances))を含むが、ゲートモデルは、相互接続される論理ゲート(およびできる限り制限された数のＦＥＴ)を含むＩＣの機能的な抽象概念である。ＦＥＴモデルからゲートモデルを抽出することは時間がかかり、間違いやすいプロセスである。そこである設計者は、コンピュータを使用してプロセスを自動化しようと試みた。
【０００３】
ゲートモデルを抽出する一つの方法は、イグゾースティブ(exhaustive)・ベクトルの使用による。イグゾースティブ・ベクトル組が回路の入力から導き出され、ＦＥＴレベル・シミュレータによって実行される。各々のベクトルは１組の期待される出力を作り出し、そこからゲートモデルが合成されうる。そのような方法の不利益は、１)およそ１４より多い入力をもつ回路は非常に多くのベクトルを必要とするので、方程式が事実上扱いにくいこと、および２）状態素子(格納または帰還)をもつ回路はイグゾースティブ・ベクトルによって十分に特徴付けられることができないことを含む。これは、それらの回路が各々の状態について付加のベクトルを必要とし、付加のベクトルを導き出す現在の方法は扱いにくく、効果的でないからである。
【０００４】
ゲートモデルのイグゾースティブ・ベクトル方法の別の不利益は、結果として生じるゲートモデルが、入力ＦＥＴモデルと構造上の類似をもたないことである。それゆえ結果として生じるゲートモデルは、回路、入力および出力を保持するが、入力と出力の間にＦＥＴモデルの構造との類似点をもたない。したがって、ツールがゲートモデル回路で誤りを示すとき、ＦＥＴモデル回路をデバッグすることは非常に困難になりうる。
【０００５】
ゲートモデルを抽出する別の方法は、単純な回路の認識に基づく再モデル化変換を含む。この解法は、ＦＥＴ構造を相補形ＣＭＯＳ構造に置き換え、ゲートをもつ回路をプリチャージ(precharge)することを試みる。しかしこの方法は、少数の単純な回路タイプのみの認識に限られる。ＣＰＵ(中央処理装置)またはＡＳＩＣ(特定用途向け集積回路)のような複雑なＩＣには非常に多くの「規則の例外」が存在し、単純な回路の認識はもはや可能ではない。単純な回路の認識は、ＦＥＴモデルの構造上の特性を保持するのに役立つが、大規模なＩＣの回路図で使用するには全く実用的ではない。
【０００６】
【発明が解決しようとする課題】
したがってこの発明の主な目的は、２つのモデル間の構造上の一致を保持しながら、ＦＥＴモデル回路からゲートモデル回路を抽出する方法と装置を提供することである。
【０００７】
この発明の別の目的は、ゲートモデル回路を抽出するために必要とされる時間を大幅に減少させる方法と装置を提供することである。
【０００８】
またこの発明の別の目的は、正確で、実証可能な方法および装置を提供することである。
【０００９】
さらにこの発明の別の目的は、大半の抽出プロセスから設計者を引き離すために使用されうる方法と装置を提供することである。
【００１０】
【課題を解決するための手段】
上述の目的の達成において、発明者は、ＦＥＴモデル回路からゲートモデル回路を抽出するコンピュータ実現の方法と装置を発明した。
【００１１】
方法は、「エキスパートシステム」としてプログラムされるコンピュータによって実行される。エキスパートシステムは、コンピュータの典型的なアルゴリズム方法(解法に至る命令のシーケンスの実行)を、通常人間のエキスパートによって提供される知識ベースの方法と結びつけることを試みるシステムである。
【００１２】
エキスパートシステムは一般に、知識ベース、推論エンジンおよびユーザー・インタフェースという３つの部分を含む。知識ベースは、典型的に人間のエキスパートによって供給される規則、事実および発見的手法(hueristics)を含む。知識ベースは、推論エンジンによって新しい事実(学習)を推論する(導き出す)ために使用される。推論エンジンが、必要とされる事実を知識ベースから推論することができないとき、システムのユーザーは欠けている情報を供給するように促される。
【００１３】
開示される方法と装置(エキスパートシステム)がどのように機能するかということの完全な理解を助けるために、エキスパートシステムの概要およびProlog(開示されるシステムが実現されるコンピュータ言語)が後に続く。当業者であれば、すでにこれらの分野には精通しているはずである。
【００１４】
エキスパートシステムの知識ベースは、多数の規則グループ(またはクラス)を含む。Prologのターム(項)で、規則グループは次のステートメントによって表されることができる。
【００１５】
【表１】
inference_control (Name, Type, Control)
ここで、Nameは規則グループの名前であり、Typeは推論タイプであり、Controlは規則のリストを含む構造である。規則推論タイプは、順次(基本エンジン)、前向きチェーン(前向きエンジン)、および後ろ向きチェーン(後ろ向きエンジン)を含む。
【００１６】
順次規則グループが開かれると、その規則は規則グループ内に示される順序で一度に一つずつ発火(fire, 処理開始)する。前向きチェーン規則グループの規則は、グループが開かれて開始されると活動状態になり、規則グループが閉じられるまで任意の時間に(任意の順序で、規則自体の条件の合致が成功することによってのみトリガされて)発火することができる。後ろ向きチェーン規則グループはいつも活動状態である。しかし後ろ向きチェーン規則はデマンド駆動されるので、そうするように要求されるときにだけ発火する。後ろ向きチェーン規則は、「膨らんで」貴重なコンピュータ処理時間を浪費しうる計算を制御するために使用される。
【００１７】
すべてのProlog規則は基本形式に従う。形式は以下の通りである。
【００１８】
【表２】
rule Name if Conditions then Actions [because Notes]
Prolog規則の例は次のように表されることができる。
【００１９】
【表３】
0003949764.tif 000002
条件は、論理積「and」または論理和「or」によって区分される一つまたは複数の節である。条件節は、エキスパートシステムのデータベースにアクセスすることも、ユーザ定義の述語を呼び出すこともできる。後ろ向きチェーン規則照会は、条件に表される「?」演算子によって行われることができる。一般に規則の条件とは、規則の左側を言う。
【００２０】
規則条件は、結論または決定(規則の右側を言う)を従える。順次または前向きチェーン規則の右側は、エキスパートシステム・データベースに情報をアサート(assert)し(以下の記述でデータベースとはゲートモデル・データベースのこと)、データベースから情報を取り消し、任意の他のユーザ定義の関数を実行することができる１つまたは複数の動作である。後ろ向きチェーン規則の右側は、後ろ向きチェーン照会の結果を定義する一つのタームである。
【００２１】
because節は任意であるので、エキスパートシステムの演算に入らない。それは、規則の関数に関する文書化(documantation)に使用される。
【００２２】
例えば上述の規則「Power Connected Fet」は次のように機能する。データベースで冗長としてマークされず、そのソース/ドレイン(Prolog述語fet_source_drain_signals/3)が指示される電源信号に接続されるデータベースの各々のインスタンス(instance_type/3)について、エントリが「signal_driven_to_Power(Sig,Fet)」のPrologのデータベースにアサートされる(加えられる)。ここで、変数FetはＦＥＴのインスタンス名であり、Sigは電源信号と反対のＦＥＴの信号名である。
【００２３】
ここで開示されるエキスパートシステムを含む方法および装置は、電源、グラウンド(接地)およびクロック信号を認識するステップと、インバータを認識するステップと、ＦＥＴモデル回路に含まれるすべての論理信号を認識し、保存するステップと、認識される論理信号の各々について、一つまたは複数の構造ベースのブールの部分的トリー組み立てるステップと、一つまたは複数のブールの部分的トリーを発見的に枝刈り(pruning)するステップと、一つまたは複数のブールの部分的トリーから論理方程式を組み立てるステップを含む。
【００２４】
この方法は、抽出されるゲートモデルの構造上の整合性を保持する際の論理信号の重要性と、構造ベースのブール・トリーの使用を認識する。構造ベースのブール・トリーは、以下の記述で開示される新しい概念である。部分的トリーは、論理方程式を簡略化し、ゲートモデルをより高いレベルに抽象化することを助ける。以前のゲートモデル抽出ツールは、大規模でこれらの仕事を達成することができなかった。
【００２５】
構造ベースのブールの部分的トリーの生成によると(ここで部分的トリーの枝はＦＥＴを表す)、上述の方法によって作り出されるゲートモデルは、そのＦＥＴモデルと構造上の一致をもち、テストツールがゲートモデルで誤りを示すときにデバッグするのがより簡単なＦＥＴモデルを作る。
【００２６】
前もって人間に任せられる多くの推論プロセスを通ることによって、発明はゲートモデル回路を抽出するに必要とされる時間を著しく減少させる。さらに、エキスパートシステムの方法および装置は保守的(conservative)であって、それが適度に信頼できるときにＦＥＴ方向、ポート方向または回路関数を推論するにすぎない。
【００２７】
ＦＥＴ方向、ポート方向、または回路関数がいくぶん曖昧であるとき、エキスパートシステムは、最も正しく効率的なモデルを作り出すように、選択肢の間で選ぶようにユーザーを促す。しかし開示される方法は、ユーザープロンプトを少しだけ用いて、多くのゲートモデルを抽出することができる。
【００２８】
【発明の実施の形態】
ＦＥＴモデル回路からゲートモデル回路を抽出するコンピュータ実現される方法が以下に記述され、概して図１に示される。方法は、電源、グラウンドおよびクロック信号を認識するステップ(44)と、インバータを認識するステップ(46)と、ＦＥＴモデル回路のすべての論理信号を認識し、保存するステップ(48)と、認識される論理信号の各々について、一つまたは複数の構造ベースのブールの部分的トリーを組み立てるステップ(50)と、一つまたは複数のブールの部分的トリーを発見的に枝刈りするステップ(52)と、一つまたは複数のブールの部分的トリーの各々から論理方程式を組み立てるステップ(54)とを含む。
【００２９】
方法は、プログラマブル・コンピュータ40(またはコンピュータ40をプログラムすることができる物理記憶媒体42に格納されるエキスパートシステムによって実現されることが好ましく、エキスパートシステムは一般にＦＥＴモデル回路入力、推論エンジン、規則ベース、ユーザー入力およびゲートモデル回路出力を含む。図３４および図３５を参照されたい。推論エンジンは規則を処理し、ゲートレベル・モデルを(出力ネットリストの形式で)推論する際に、ＦＥＴモデル回路入力を(入力ネットリストの形式で)使用する。
【００３０】
このように方法と装置を大体説明したが、それらをさらに詳細に説明する。ここで開示される方法と装置は、Prologコンピュータ・プログラミング言語を使用して開発されている。しかし特定のプログラミング言語の使用は、開示される方法と装置を使用するために必ずしも必要ではなく、当業者であれば異なったプログラミング言語を使用して開示される方法と装置を実現することを選択することができる。
【００３１】
好ましい実施例で、方法は図２に示される拡張されたステップのシーケンスを含む。方法は、ＦＥＴモデル回路に含まれる情報が入力ネットリストの形式でエキスパートシステムに提供されることを必要とする。ネットリストは、回路の各々のネット(ノード)に接続される端子のリストを提供する。
【００３２】
システムの外側層(またはシェル)は、引数を確認し、ファイルの存在を確認し、入力ネットリストをデータベースに読み込み、それをPrologタームに変換し、任意に出力ネットリストを交互にフォーマットされるネットリストに変換する役割を果たす。外側層が入力ネットリストをPrologタームに変換した後に、推論エンジンが始まる。方法のどのステップがいつ実行されるかを実際に決定するのは推論エンジンである。規則が推論エンジンによって発火されると、ゲートモデルの作成を助けるという事実が、エキスパートシステムのデータベースにアサートされる。
【００３３】
推論エンジンは、最初に一連の順次規則グループを開く。これらの第１のものは、電源、グラウンドおよびクロック信号を認識する役割を果たす規則グループである。電源、グラウンド、およびクロック信号に使用される信号の命名規則は次の通りである。
【００３４】
【表４】
0003949764.tif 000003
この方法はこれらの規則を認識して、エキスパートシステムのデータベースにこれらの信号について事実をアサートする(44)。しかし規則は、入力ネットリストに(またはネットリストに関連する個別のファイルに)含まれる特性によって無視されることがありえる。
【００３５】
次に推論エンジンは、冗長なＦＥＴの除去規則グループに引き続きチェーンする。強制のステップではないが、冗長なＦＥＴを除去するプロセスは後の計算と抽象化ステップをかなり簡略化する。
【００３６】
冗長な並列ＦＥＴの除去は非常に簡単である。２つまたはそれ以上のＦＥＴが共通のソース、ドレインおよびゲート接続を共有する場合、それらの１つを除いて全てが除去される。図４を参照されたい。しかし方法は、さらに一つのステップに進み、冗長な「ＦＥＴ構造」を除去する。冗長な「ＦＥＴ構造」の除去は、それほど簡単ではない。ＦＥＴ構造を等価性(または冗長性)について検査する疑似符号で実現する発見的手法は、次のように与えられる。
【００３７】
【表５】
0003949764.tif 000004
簡略化のために、上述の冗長除去プロセスは、1)一つのＦＥＴ構造のトリーのすべてのＦＥＴゲート信号が、冗長なＦＥＴ構造の対応するＦＥＴゲート信号と同一であること、および2)ＦＥＴ構造が帰還ループを含まないこと、を要求する。
【００３８】
除去プロセスは、それらのソースおよび/またはドレインを通って共通のノードに接続される２つのＦＥＴで開始する(図５のノードＳを参照)。接続されているＦＥＴは同じタイプ(両方ともｐ−ＦＥＴか両方ともｎ−ＦＥＴ)でなければならない。さらに、接続されるＦＥＴのゲート信号が同一でなければならない。ＦＥＴ構造トリーは、共通のノードに接続されるＦＥＴの各々について生成される。トリーは、ＦＥＴソース/ドレイン接続を通って、２つのトリーが共通のノード(図５のノードＴ)で再集結するまでパスを横断することによって生成される。
【００３９】
回路の注記または特性が入力ネットリストに加えられて、インスタンスを冗長であると言明したり(その除去を強制する)、または冗長なＦＥＴの除去プロセスがＦＥＴを除去しないようにすることもできる。
【００４０】
続いて推論エンジンは、方法のこの時点で２つの付加の規則グループにチェーンすることができる。第１に、キャパシタとして使用されるＦＥＴが発見的に認識され、これらのＦＥＴに関する事実がエキスパートシステムのデータベースにアサートされることができる。ＦＥＴは、１)そのソースとドレインが両方とも電源に(または両方ともグラウンドに)接続される(図６４を参照)、あるいは２)それが永久に動作不能である(つまりゲートがグラウンドに配線されたｎ−ＦＥＴ、またはゲートが電源に配線されたｐ−ＦＥＴ)(図６５を参照)場合、キャパシタであるとアサートされる。第２に、レールに配線されるソースまたはドレイン(電源またはグラウンド)のどちらかを有するすべてのＦＥＴは、データベースにそのように注記される。これらのステップは両方とも、後の発見的な部分的トリーの枝刈りのステップを簡略化する。
【００４１】
方法の次のステップはインバータの認識(46)である。再び推論エンジンは、このステップの規則グループに引き続きチェーンする。最も基本の論理ゲートとして、インバータを認識して、抽象化が行われ、ゲートモデルの論理が最小限にされることができることが重要である。インバータは、１)ＦＥＴの各々が共通の論理信号へのソース/ドレイン接続をもち、２)一方のＦＥＴのｐ−ＦＥＴが、電源に接続されるソース/ドレインをもち、他方のＦＥＴのｎ−ＦＥＴが、グラウンドに接続されるソース/ドレインをもち、３)ＦＥＴのゲート信号が共通の論理信号に接続される、という一対のＦＥＴのパターンの合致によって認識される。また反転の関係は、信号名N<sig>をもつネットリストの入力ポートは入力ポート<sig>の反転であるという取り決めによって認識される。
【００４２】
インバータを認識した後に(46)、できる限り多くのＦＥＴについて最初のＦＥＴ方向が決定される(58)。最初のＦＥＴ方向は、電源またはグラウンド信号から、該電源またはグラウンド接続に直列に接続されそこから離れる方へ進み、一つまたは複数のＦＥＴのソース/ドレイン接続を横断することによって決定される。一端(ソース/ドレイン)が電源またはグラウンドに接続されているＦＥＴは、その他端(ソース/ドレイン)で信号を駆動するものとして、データベースにアサートされる。ＦＥＴのソース/ドレイン接続は、ＦＥＴの駆動される端が他の一つのＦＥＴのみに接続され、ポート、ＦＥＴゲート、または非ＦＥＴインスタンスが遭遇されない限り、横断される(横断される各々のＦＥＴが電源またはグラウンドから遠ざかる方へ駆動することをデータベースにアサートする)。最初のＦＥＴ方向を決定するために使用される規則グループは、前向きチェーン規則グループでなければならない。
【００４３】
上述のステップは、順次または前向きのチェーン規則グループを開くことを含んでいる。次のいくつかのステップは、後ろ向きチェーン規則グループを開くことを含む。
【００４４】
この方法の重要なステップは、回路の中のすべての論理信号の認識および保存(48)である。論理信号は、論理が生成される信号のサブセットを表す。他のすべての回路信号は中間物と考えられ、ゲートモデル抽出プロセスの間に包含されうる。論理信号は、ポート(電源およびグラウンドのポートを除く)、ＦＥＴゲート、あるいは非ＦＥＴインスタンスに接続される任意の信号として定義される。非ＦＥＴインスタンスは、設計者がＦＥＴ実現の代わりの抽象化を与えるインスタンスをＦＥＴモデル回路に含む。例えば加算機または比較器への接続は、非ＦＥＴインスタンスへの接続である。図６で、認識される論理信号は、Ａ、Ｂ、Ｃ、Ｄ、ＷおよびＺである。Ｖ、ＸおよびＹは中間信号と考えられ、抽出プロセスの中に包含されることができる。
【００４５】
論理信号を認識して、結果として生じるゲートモデルがそのＦＥＴモデルと構造上の一致をもつことが重要である。他のゲートモデル抽出方法では論理信号を認識せず、その結果全てではないとしてもほとんどの論理信号がゲートモデルから外される。他のゲート抽出モデルは、パス/失敗の原理で回路のテストを可能にしたが、ＦＥＴ回路は一度誤りが注意されると、テストされるゲートモデルへの構造上の類似がないために、デバッグするのが難しかった。
【００４６】
方法の次のステップは、認識される論理信号の各々について、一つまたは複数の構造ベースのブールの部分的トリー（部分木、以下同様）を組み立てることを含む(50)。部分的トリーの構造の基礎(basis)は、入力ネットリストのソース/ドレインＦＥＴ接続である。部分的ブール・トリー（ブール部分木、以下同様）は、論理信号に接続される各々のＦＥＴについて構築される。トリーのルート（根、以下同様）は論理信号である。接続しているＦＥＴは幹と考えることができる。幹の他方の側に接続される全ての他のＦＥＴは、別の論理信号または電源/グラウンド信号が到達されるまで(リーフ(leaf))、(ＦＥＴの端と端を接続して)扇形に広がる枝を開始する。したがって特定の論理信号は、それに関連する(各々のＦＥＴのトリーはそれに接続される)いくつかの部分的トリー(森)をもつことができる。
【００４７】
部分的トリーは構造ベースであるので、枝は単なる論理パスではなく、ＦＥＴモデルにおけるＦＥＴを表す。構造ベースのブールの部分的トリーは、BDD(boolean decision diagrams、ブールの決定図)に類似しているが、構造の基礎をトリーに加える際にさらに一つのステップへ進む。以前のトリーはこれを行わなかった。BDDは論理ベースであり、いかなる構造とも一致しない。
【００４８】
部分的トリーは他の論理信号で終わるので、それらは比較的小さく、従って管理し、推理するのが容易である。一方、BDDおよびその他の同様の方法は成長して非常に大きく扱いにくくなり、時間および空間の両方で管理するのに費用がかかる。
【００４９】
いくつかの部分的トリーは1-トリー（１−木、以下同様）であり、(電源に対し)高い論理信号を駆動することができるＦＥＴを表す。トリーのいくつかは0-トリー（０−木、以下同様）であり、(グラウンドに対し)低い論理信号を駆動することができるＦＥＴを表す。したがって、ＮＯＲゲートは２つの1-部分的トリーをもち、ＮＡＮＤゲートは２つの0-部分的トリーをもつ。
【００５０】
図７の論理信号Ｚは、図８で説明されるような３つの部分的トリーに関連する。
【００５１】
部分的トリーは、論理信号で始まり、その論理信号に接続されるＦＥＴを(部分的トリーの幹になる)そのソースまたはドレインによって識別し、ソースおよび/またはドレイン接続を介して端から端まで幹に接続されるＦＥＴを部分的トリーに加わえることによって組み立てられる。部分的トリーの枝は、電源、グラウンドまたは論理信号のいずれかに直面したときに終わる。
【００５２】
この段階で、部分的トリーはＦＥＴまたはポートの方向を考慮せずに組み立てられるので、トリーの枝は様々な部分的トリーに複製されることが可能である。例えば、図１５のＦＥＴ Ｆ１を含み、論理信号Ｙで終わる論理信号Ｚの部分的トリーは、Ｚで終わるＹの部分的トリーのようにも見える。
【００５３】
部分的トリーは組み立てられるとき、単純な規則によって枝刈りされることができる。矛盾するゲート信号がトリーの枝に見つけられる(論理反転の以前の識別によって)場合、その枝は枝刈りされる。例えばゲート信号ＡをもつＦＥＴがゲート信号 〜Ａ(Ａの否定またはＡの反転)をもつＦＥＴと直列である場合、その枝は論理的に不可能を表すので枝刈りされる。
【００５４】
各々の部分的トリーについて、最大の強さを計算することができる。計算はレール(電源およびグラウンド)で強さ63から始まり、そして直列の枝パスの各々のＦＥＴについて計算されるＦＥＴ「抵抗」を減ずる。強さは１以下に下がることができない。抵抗はR=max(K*L/W,L)として計算され、ここでＷおよびＬはそれぞれのＦＥＴの幅および長さである。Ｋは、ｐ−ＦＥＴおよびｎ−ＦＥＴについてユニークな値をもつプロセスに特有の係数である。より低い抵抗をもつゲートは、より大きい強さをパスに加える。部分的トリーの最大の強さは、部分的トリーの最強の枝パスの強さに等しい。強さの計算は、帰還パスの識別のような後の規則に関連して使用されうる。
【００５５】
構造ベースの部分的トリーが組み立てられたあと(50)、多数の付加の後ろ向きチェーン規則グループを使用して発見的に枝刈りされる(52)(図３)。規則グループは、第１および第２フェーズのグループに小分割される。枝刈りは第１フェーズの規則から始まって、必要に応じて第２フェーズの規則へ進む。最後に(また必要に応じて)、ユーザーは情報について促される。第１および第２フェーズの規則グループの各々はさらに、部分的トリー枝刈り規則68、74、ＦＥＴ方向規則70、76、およびポート方向規則72、78に小分割される。ＦＥＴおよびポート方向規則は、後ろ向きチェーンによって部分的トリー枝刈り規則からアクセスされる。規則フェーズの背後の理論は、方法がユーザを促すことなく、できる限り多く成し遂げなければならないということである。エキスパートシステムが十分な情報を入力ネットリストまたはそれ自身の推論規則から得ることができない場合は、情報をユーザから得ることができる。
【００５６】
第１フェーズの部分的トリー枝刈り規則(68)が発火されるとき、ゲートモデルに関する事実がデータベースにアサートされる。事実は、ＦＥＴ方向、ポート方向および論理的フロー・パスに関する情報を含む(つまり実現不可能なパスは枝刈りされる)。
【００５７】
入力、出力あるいは双方向のいずれのポート方向も、必ずしも入力ネットリストで指示されるとは限らない。その結果、方法はしばしばこの情報を回路から推論しなければならない。同様に通常全てのＦＥＴの方向は与えられないので、決定されなければならない。これは、トリー枝刈り規則が多くの情報を必要とするので、方法のこの時点でなされる。
【００５８】
第１フェーズの部分的トリー枝刈り規則は、必要とされる場合はいつでもＦＥＴまたはポートの方向について照会する。照会が行われるとき、推論エンジンはその照会が以前に行われたかどうか決定し、もし行われたのであればＦＥＴまたはポート方向がデータベースに存在するかどうか決定する。もし存在しないならば、推論エンジンは第１フェーズのＦＥＴ70またはポート72の方向規則グループに後ろ向きにチェーンする。ＦＥＴまたはポート方向が決定できないならば、照会は満足されずに戻される。付加の情報がデータベースにアサートされるとき、再び質問が行われ、満足される。さもなければＦＥＴまたはポート方向の決定は、第２フェーズの規則が開かれて、第２フェーズの規則またはユーザーの入力のどちらかが照会を満足するまで待たなければならない。
【００５９】
第１フェーズの規則が可能な限り多く達成すると、第２フェーズの部分的トリー枝刈り規則74が推論エンジンによって開かれる。第２フェーズ規則74は、第１または第２フェーズのＦＥＴ70、76またはポート72、78の方向規則をどちらも照会することができる。第２フェーズでＦＥＴまたはポート方向が規則グループを使用して推論されることができないとき、ユーザーは方向について促される。方向が提供されると、規則は、新しい情報を使用して発火しうる全ての規則が発火するまで、重ねて発火する。任意に、ユーザーが方法の実行に随伴することができないとき、方法は非相互作用モードで実行させるように命令されうる。非相互作用のモードで実行するとき、方法は未知のポートまたはＦＥＴ方向が双方向であるとアサートしなければならない。
【００６０】
部分的トリーの構造の基礎によって、推論エンジンは部分的トリーの枝刈りがいつ完了するかを決定することができる。部分的トリーの枝刈りは、すべてのＦＥＴの方向(部分的トリーの枝)が知られ、それ以上のトリー枝刈り規則68、74が発火し得ないとき完了する。
【００６１】
論理的トリー構造(あるモデル化プロセスによって使用される従来のBDDのような)を用いる場合、双方向のＦＥＴおよびポート方向を分解できないことは、結果として生じるゲートモデルに付加の複雑さを加える。論理的トリーを使用するとき、ＦＥＴまたはポート方向の決定を強制することは不可能である。これはＦＥＴ構造が表されず、多数の論理信号がゲートモデル化プロセスに包含されるからである。
【００６２】
構造ベースのブール・トリーの使用は、ゲートモデルに構造上の一致を加えるだけでなく、ゲートモデルの論理を簡略化する助けになる。
【００６３】
発見的な部分的トリー枝刈り規則は次の通りである。
【００６４】
１．第１フェーズの部分的トリー枝刈り規則
部分的トリーは、そのルートの論理信号が入力ポートであり、部分的トリーの全ての枝が共通の論理信号で終わる場合、その全体を枝刈りされる。第１フェーズのポート方向規則は、部分的トリーのルートが入力ポートであるかどうかを決定する後ろ向きチェーン照会によって発火されることができる。この規則の背後にある論法は、入力ポートと一つの論理信号の間の流れが、入力ポートから遠ざかるものでなければならないということである。部分的トリーによって示される流れの方向は入力ポートに向いているので、入力ポートでルートした(rooted、入力ポートを根に持つ)トリーは間違った論理パスを表しており、枝刈りされなければならない。図９は、この規則の適用を示している。入力ポートＡは、枝刈りされる論理信号Ｓに基づく部分的トリーを持つ。
【００６５】
ある論理信号の部分的トリーが論理信号の「安定した(sound)」トリーのグループよりも弱い場合、その全体が枝刈りされる。安定したトリーとは、完全な相補形ＣＭＯＳゲート(例えばＮＡＮＤゲート)のような常に駆動しているゲートを表す。この規則の理由は、安定したゲートより弱い部分的トリーは、そのルートの論理信号の値に影響を与えることができないことである。例えば図１０で、ＹからＺまで組み立てられた部分的トリーは、ＺがＹからＺへのパスよりも安定したＮＡＮＤゲートによって駆動されると決定される場合に枝刈りされる。
【００６６】
部分的トリーの枝は、それがＦＥＴでありえるとき枝刈りされる。部分的トリーで示されるＦＥＴの方向は、それが部分的トリーのルートに向かって駆動するということである。従って、ＦＥＴが事実上部分的トリーのルートから遠ざかる方へ駆動すると決定される場合、枝は論理パスではなく、枝刈りされなければならない。第１フェーズのＦＥＴ方向規則は後ろ向きチェーン照会によって呼び出される。図１１で、ＦＥＴのＦ２を含むＺの部分的トリーは、Ｆ２がＢに向かって(質問における部分的トリーのルートであるＺではなく)事実上駆動すると決定されると、枝刈りされる。
【００６７】
部分的トリーは、同じ論理信号にルートした別の部分的トリーがそれを包含する場合にその全体を枝刈りされる。この枝刈りステップは、構造上の部分的トリーの論理的な枝刈りを含む。例えば、ある部分的トリーが「Ａ and Ｂ」という論理関数を表し、別の部分的トリーが「Ａ and Ｂ and Ｃ」という論理関数を表す場合、後者の部分的トリーは論理的に前者によって包含されるので枝刈りされる。図１２を参照されたい。
【００６８】
最後に、部分的トリーの枝は、そのＦＥＴのゲート信号の２つが互いに相反する場合に枝刈りされる。例えば、ある枝のＦＥＴがゲート信号Ａをもち、同じ枝のもう一つのＦＥＴがゲート信号ＮＡ(Ａの否定)をもつ場合、そのようなパスは実現することが不可能であるので、枝は枝刈りされなければならない。Ｚの部分的トリーを含む図１３のＦＥＴの場合、ＦＥＴ  Ｆ１で始まる枝は相反するゲート信号ＡおよびＮＡによって枝刈りされる。
【００６９】
２．第１フェーズのＦＥＴ方向規則
以下の規則は後ろ向きチェーンであり、特定のＦＥＴの方向が質問の中にあるときにのみ発火される。
【００７０】
ＦＥＴが特別なタイプの方向性のないＦＥＴである場合、それは方向性のないＦＥＴのライブラリのＦＥＴと比較されうる。その方向がライブラリから引き出され、データベースにアサートされる。
【００７１】
ＦＥＴの方向がＦＥＴモデル・ネットリスト(入力ネットリスト)に含まれる場合、ＦＥＴモデル・ネットリストで提供される方向がデータベースにアサートされる。
【００７３】
電源またはグラウンドに接続されるＦＥＴは、電源またはグラウンドの接続から遠ざかる方へ駆動する。図１４を参照されたい。
【００７４】
上述したように、示されるＦＥＴ方向は、それが部分的トリーのルートに向かって駆動するということである。示されるＦＥＴ方向が、それが属する全ての部分的トリーで一貫している場合、その示される方向はその実際の方向であるとアサートされる。図１５で、ＦＥＴ Ｆ１は論理信号ＹおよびＺの部分的トリーの一部である。Ｆ１がＹの部分的トリーから枝刈りされる場合、この規則の適用は、Ｆ１がＺに向かって駆動することを示す(他のいかなる部分的トリーも相反する方向を示唆しない)。
【００７５】
ＦＥＴがポートへの唯一の接続を含み、そのソースまたはドレインを介してポートに接続されている場合、それが入力ポートであるならばポートから遠ざかる方へ、それが出力ポートであるならばポートに向かってＦＥＴは駆動する。ポートが双方向であるとき、ＦＥＴ方向に関する結論は(この規則によって)導かれない。ポートから遠ざかる方へまたはポートに向かって駆動するとアサートされるＦＥＴの例は、図１６および図１７に示されている。
【００７６】
ある部分的トリーが、論理信号を一方向に(つまり電源へまたはグラウンドへ)引くことができる唯一の部分的トリーである場合、その部分的トリーのＦＥＴはその論理信号を駆動するはずであり、ＦＥＴの示される方向はそれらの実際の方向であるとアサートされる。この発見的手法は、ポートに接続されないすべての論理信号は、それらを駆動するＦＥＴによって、両方のレール(電源とグラウンド)へ駆動されることが可能でなければならないと仮定する。ポートに接続される論理信号は、回路の外の論理がそれらに影響を与えることができるので、この規則から除外される。この規則は、ＦＥＴが双方向でありうるという事実を無視する。しかし双方向ＦＥＴはまれであるために、それはめったに失敗しない。図１８で、ＦＥＴ Ｆ１はＺを「１」に駆動することができる唯一のＦＥＴであり、従ってＦ１はＺに向かって駆動するとアサートされる。
【００７７】
ＦＥＴが、それに対向して駆動することができる他のいかなる可能なトリーよりも強い「安定した」論理ゲート(インバータすなわち完全な相補形ＮＡＮＤゲートのような)によって駆動される場合、ＦＥＴはより大きい論理ゲートから遠ざかる方へ駆動するとアサートされる。例えばマスタースレーブ・レジスタで、マスターインバータは、スレーブの帰還インバータよりもずっと大きいので、マスターとスレーブの間の転送ＦＥＴの方向はスレーブに向かって駆動すると決定される。図１９の転送ＦＥＴを参照されたい。
【００７８】
３．第１フェーズのポート方向規則
ポート方向特性が入力ネットリストに存在する場合、ポート方向は指示される通りである。
【００７９】
電源およびグラウンドは常に入力の方向を持つ。
【００８０】
ポートがパススルー・ポートである場合、その方向は入力である。パススルー・ポートは回路への接続を持たず、整合性のためにＦＥＴモデルからゲートモデルへ単にコピーされる。
【００８１】
駆動されないポート(単にＦＥＴゲートに接続されるポート)の方向は、図２０のＡのように入力である。
【００８２】
ポートを駆動する論理が安定している場合、ポートは帰還パスと関連せず、ポートの方向は図２１のポートＺのように出力である。
【００８３】
４．第２フェーズの部分的トリー枝刈り規則
ＦＥＴの実際の方向がその部分的トリーの枝によって示される方向と反対であるならば、そのＦＥＴを含む枝は枝刈りされる。この規則は、第１フェーズの枝刈り規則と同一である。ＦＥＴおよびポートの方向は、第２フェーズのＦＥＴ(76)およびポート(78)方向規則への後ろ向きチェーン照会から得られる。ＦＥＴまたはポート方向に関する新しい情報を得た後、後ろ向きチェーン照会が任意の第１フェーズの規則グループに対して行われる。
【００８４】
５．第２フェーズのＦＥＴ方向規則
第２フェーズのＦＥＴ方向規則は、ＦＥＴ方向についてユーザーを単に促すことである。ユーザーは、ＦＥＴが特定の信号を駆動する、またはＦＥＴが本当に双方向であると応答することができる。
【００８５】
促すことについてユーザーが利用可能でない場合、ＦＥＴは双方向であると仮定される。
【００８６】
６．第２フェーズのポート方向規則
ポートの部分的トリーのすべてが排除される場合、駆動されないポートは入力の方向を持つ(図２２）。
【００８７】
ポートがある部分的トリーのルートに現れるが、他の全ての部分的トリーから「リーフ」として排除される場合、ポートの方向は出力または双方向のどちらかでなければならない。ポート(図２３のポートＹ)が回路によって両方のレールに駆動される場合、その方向は出力であるとアサートされる。そうでない場合、それは図２４のポートＺのように双方向であるとアサートされる(この双方向の発見的手法は、テストパターン・ジェネレータがポートをより試験可能にする)。
【００８８】
ポートの方向が依然として未知である場合、ユーザーは方向について促される。
【００８９】
エキスパートシステム装置の代替実施例で、システムは、所与の「努力(effort)」をＦＥＴまたはポート方向を得ることに注ぐように命令されうる。例えば非常に大きいＦＥＴモデルからゲートモデルを抽出するとき、ユーザーがＦＥＴまたはポート方向について促される前に、システムはある程度の仕事しか出さないように命令されうる。こうして、コンピュータで実行される計算の数を低減させることができ、方法の実行時間を減らすことができる。
【００９０】
推論エンジンによってアクセスされる規則グループの残りは(論理関数の決定がなければ)順次の規則グループである。
【００９１】
この方法の重要な特徴は、弱い部分的トリーを弱くない(強い/支配的な)部分的トリーから分割する(60)能力である。分割は、ゲートモデルの論理関数を抽出する際の助けとなる。例えば、ラッチを駆動する強い部分的トリーから、ラッチの弱い帰還インバータを表す弱い部分的トリーを切り離すことによって、ラッチがそのままの状態で抽出されることができ、従ってゲートモデルでラッチをより本来的にモデル化する。他の方法は、多数のＦＥＴを使用して実現される状態インスタンスを捕獲するが、オリジナルのＦＥＴ構造または回路の記憶信号との一致を保持しない。
【００９２】
上述したように、部分的トリーの最大の強さは、部分的トリーを通る最も強いパスの強さに等しい。弱いおよび弱くないトリーは、多様な部分的トリーの最大の強さの比較によって切り離される。
【００９３】
弱い部分的トリーは、論理信号の弱くない1および0-トリーから切り離される。部分的トリーが弱いとマークされるとき、「全体の」部分的トリーは弱い。部分的トリーは、弱い部分と弱くない部分にさらに小分割されるべきではない。
【００９４】
帰還が存在しないならば、弱い部分的トリーをつくる必要はないと仮定する。この仮定は、弱くないトリーから弱いトリーを分割する仕事を大いに簡略化する。仮定は必ずしも正しくはないが(例えば、帰還は、モデル化された回路の外に存在することがありえる)、その利益がその損失よりはるかに重要である場合には正しい。
【００９５】
切り離しプロセスを開始するために、帰還トリーが認識されなければならない。部分的トリーは、交差結合(cross-coupled)される２本のトリーについて吟味される。すなわち各々の部分的トリーの論理信号は、他のトリーへの入力である。これは２路帰還の例である。図２５で、ＦＥＴ Ｆ１、Ｆ４およびＦ５は信号Ａのトリーにあり、ＦＥＴ Ｆ２、Ｆ３およびＦ６は信号Ｂのトリーにある。したがって、ＡとＢの間には帰還が存在する。また３路および４路帰還は、この方法(２本のトリーの間の帰還が実際に他のトリーを通過する)を使用して認識される。図２６で、論理信号ＡとＢの間の帰還は、信号Ｃの部分的トリーを通過する。
【００９６】
より強い「反対側」に別の部分的トリーが存在し、２本の部分的トリーが「解体されて(disjoint)」いない場合、帰還と関係する部分的トリーは弱い部分的トリーである。「反対側」という用語は、反対のレールへ駆動する部分的トリー(1-トリー対0-トリー)を言う。「解体」は、部分的トリーが(トリーの論理によって決定される)同じ時間に駆動することが不可能であることを意味する。解体の制約は、フィードフォワード・インバータのｎ−ＦＥＴが、同じインバータのｐ−ＦＥＴの足のように強くないからといって弱いと類別されることを防ぐ。図２５で、部分的トリーＦ４およびＦ５は、信号Ａをいずれのレールにも駆動することができるＦ１よりも弱いので、弱いとマークされる。
【００９７】
また、反対側に部分的トリーが存在せず、論理信号(すなわち帰還トリーのルート)がポートであるかまたは非ＦＥＴインスタンスによって駆動されるかのどちらかである場合、帰還と関係する部分的なトリーは弱い部分的トリーである。図２７でＦＥＴ  Ｆ１は、ポートＺおよび信号Ｙの間の帰還に含まれているので、この規則によって弱いとマークされる。
【００９８】
部分的トリーが、(電源またはグラウンドからでななく別の論理信号から来る)転送トリーであり、転送信号が反対のレールへ駆動されることができる帰還信号である場合、弱い。図２６でＦＥＴ Ｆ７は、この規則によって弱い部分的トリーとしてマークされる。
【００９９】
最終的に部分的トリーは、弱い部分的トリーが他方の側に存在し、部分的トリーの入力が他の部分的トリーの入力のサブセットであれば、弱いトリーである。この規則は、強いＦＥＴを一方の側にのみ駆動する弱い論理の他方の側を拾い上げる。一方の側にだけ強いＦＥＴがあると、他の弱い側は、この規則なしでは認識されない。図６６の例を参照されたい。ＦＥＴ Ｆ２は、ＦＥＴ Ｆ３がすでに弱いとマークされているので、この規則によって弱いと認識される。すなわちＦ６よりも弱いということである。
【０１００】
部分的トリーが枝刈りされ、弱いおよび弱くないグループに切り離されたので、それらは、完全な構造ベースのブール・トリーを形成するように併合される。この点に先立ち、方法は部分的トリーによって厳格に機能している。識別される各々の論理信号は、最高４本のトリーを持つことができる。論理信号について可能なトリーは、強い1-トリー、強い0-トリー、弱い1-トリーおよび弱い0-トリーを含む。1-トリーは論理信号を電源へ引く役割を果たし、0-トリーは信号をグラウンドまで引く役割を果たす。
【０１０１】
完成されるブール・トリーは、各々の論理信号についてブール論理方程式を組み立てるために使用される(54)。単純な変換を使用して、各々のブール・トリーを論理方程式に変える。直列のＦＥＴはブールのＡＮＤ節「*節」を形成し、枝(またはサブ・トリー)を分岐させることは、ブールのＯＲ節(「＋」節)を形成する。例えば、ＣＭＯＳ ＮＯＲゲートは、２つのサブ・トリー(ブールのＯＲ節)をもつ0-トリーを含み、それぞれのサブ・トリーはゲート出力をグラウンドに引くことができる。ＮＯＲゲートの1-トリーは、ゲートの出力を電源に引くことができる２つの直列のＦＥＴ(ブールのＡＮＤ節)を含む。論理方程式は、ド・モルガン(反転)形式で1-トリーについて組み立てられる。したがって、ＮＯＲゲートの方程式(入力ＡおよびＢを仮定する)は以下で表される。
【０１０２】
【数１】
0-方程式 = A+B
1-方程式 = 〜(〜A*〜B) (ド・モルガン形式)
A+B  (最終の簡略化された形式)
反転は、トリーの中のＦＥＴのタイプによって命令される。ｐ−ＦＥＴは反転を引き起こすが、ｎ−ＦＥＴは反転を引き起こさない。ド・モルガン形式を使用する理由は、安定した論理の検出(0-および1-論理方程式は両方とも同一になる)を簡略化するためである。
【０１０３】
上で述べたように、ＦＥＴ構造と厳密に一致するゲートモデルを抽出することがこの方法の目的である。これは時々最適より少し劣る論理方程式を与えるが、それは回路の問題をデバッグする際にユーザーを大いに助ける。例えば、方程式(A+B)*(C+D)をもつＣＭＯＳ相補形ＡＮＤ-ＯＲゲートを考える。ゲートの下半分が図２８に示されている。ブール論理を使用すると、この方程式は、A*C + B*C + A*D + B*Dという同等の方程式に操作されることができる。しかし、ＦＥＴ構造が第１の方程式を直接に与える場合、その方程式を保持することが好ましい(ＦＥＴ  ＡおよびＢが並列で、ＦＥＴ ＣおよびＤが並列であり、一つの並列構造は他方と直列である)。操作される方程式は、ＦＥＴ構造を「逆に設計する」こと、およびＦＥＴ構造を含む回路をデバッグすることを困難にする。
【０１０４】
ＦＥＴモデルの物理的構造をたどるために、トリーから方程式への変換にはわずかな修正が必要である。これは、トリーが格納されている態様のためである。図２８に示されるＡＮＤ-ＯＲゲートの格納されているトリーが、図２９に表されている。方程式の変換に対する率直なトリーは、方程式A*(C+D)＋B*(C+D)をもたらす。この方程式は、部分的トリーの並列の組換えを行っていないので、方程式(A+B)*(C+D)とは形式が異なる。並列の組換えを実行するために、サブ・トリーを開始するノード80の信号名がデータベースに格納される。図２９で、ノード80の名前はＸ１である。ノード名は、(C+D)サブ・トリー構造とともに格納される。したがって、並列のサブ・トリーを組み換えるために、第１のステップはトリーのノードのリストを作り、複製（重複）を保有することである。複製は、それらのノードの下方の構造が１またはそれ以上の倍数で重複していることを意味する。この情報を用いて、複製される（重複した、以下同様）ノードの上方のトリーが組み合わせられる。
【０１０５】
図２９で、複製されたノード80はＸ１である。従ってノード80の上方のトリー、すなわちＡおよびＢが組み合わせられることができる。これは、図３０のトリーと図２８の並列のＦＥＴ構造を模倣する方程式(A+B)*(C+D)を与える。
【０１０６】
最後のケースは、並列の組換えに関してよく考えられる必要がある。図３１のＦＥＴ構造を考える。このＦＥＴ構造について組み立てられる構造ベースのブール・トリーが最初に図３２に表されている。複製されるノード82、Ｙ１の存在に注意されたい。しかし部分的トリー枝刈りプロセスの間に、相補的な枝が枝刈りされる(上述の部分的トリー枝刈り規則を参照されたい)。これは、複製されるノード(Ｙ１)を持つが、複製されるサブ・トリーをもたない図３３のトリーをもたらす。このケースでは並列の組換えの試みを防ぐために、複製されるノード82の一つが名前を付け替えられる。例えば複製されるノード82は、Ｙ２として名前を付け替えられる。
【０１０７】
トリーは方程式に変換されると(54)、発見的に簡略化される。方程式は、行われるべき簡略化が残らなくなるまで、一連の象徴的な簡略化を通る。これらの簡略化は、方程式の構造上の一致に重要な影響を与えない。好ましい簡略化規則グループは、以下の通りである。
【０１０８】
【数２】
0003949764.tif 000005
上記の構文の簡略化に加えて、関数の簡略化も同様に行われる。例えばNAがAの反転である場合、NAが 〜Aに置き換えられ、Aが 〜NAに置き換えられることができる。さらに、BAがNAの反転であるならば、BAおよびAは同等であり、入れ替えられる(X op X => X 規則を使用して、A + BA => A)。
【０１０９】
すべての論理信号について論理方程式(弱い方程式と弱くない方程式の両方)を決定した(54)後、ゲートモデル・ネットリストが抽出されうるように、十分な情報がデータベースにアサートされる。しかし、さらに論理関数を決定すること(62)が有利である。論理関数の決定(62)は、抽出されるゲートモデルを大いに簡略化する抽象化である。
【０１１０】
単純な相補形ＣＭＯＳ論理の場合、論理信号の1-および0-方程式が同等であり、ゲートが信号1-または0-方程式のどちらからも導き出されうることを理解することは容易である。プリチャージ・モデル(後述される)を抽出するときのように、ある信号についてゲートモデルが使用される他のケースもある。しかし、ゲート変換がより複雑であるケース(すなわち、論理信号がチャージを蓄えることができる時)もある。これらのケースで、簡略化されたＦＥＴ実現が行われる。簡略化されたＦＥＴ実現は、全体の0-方程式を、一つのｎ−ＦＥＴ(引き下げＦＥＴ)を駆動する１つまたは複数のゲートと置き換えること、および全体の1-方程式を、一つのｐ−ＦＥＴ(引き上げＦＥＴ)を駆動する１つまたは複数のゲートと置き換えることを含む。
【０１１１】
方法はいくつかの発見的手法を実行して、ある信号について弱い論理関数と弱くない論理関数の両方を決定する際に、1-方程式、0-方程式、あるいは両方の方程式(簡略化されたＦＥＴの実現)のどれが使用されるかを決定する。以下の規則は、前向きチェーンまたは後ろ向きチェーンのどちらでもありえる。
【０１１２】
1-および0-方程式が同一であるならば、0-方程式が論理関数を決定するために使用される。1-方程式は、完全に相補形のゲートが0-および1-方程式の合致をもつように、ド・モルガン形式で保有されることを思い出されたい。図３６を参照して、信号Ｚについての方程式は以下の通りである。
【０１１３】
【数３】
0-方程式 : A*B
1-方程式 : A*B
ルートした1-および0-方程式が同一である場合、0-方程式が論理関係を決定するために使用される。典型的な論理方程式は、他の論理信号に関して定義される。しかしルートした方程式は、他の論理信号ではなくポートに関して、その方程式を拡張しようとするものである。例えば、図３７の信号GTOUTについて以下の方程式を考える。
【０１１４】
【数４】
0-方程式：NGTIN * EQ ＋ B * NA
1-方程式：(NGTIN ＋ NEQ) * (B ＋ NA)
NA=〜A、NB=〜BおよびNEQ=〜EQがわかっていても、２つの方程式が合致することは明らかではない。しかし方程式が拡張され、EQについての論理が方程式に挿入される場合(EQ = A * B + 〜A * 〜B)、上記の方程式は次のようになる。
【０１１５】
【数５】
ルートした0-論理：NGTIN * A * B + NGTIN * NA * NB + B * NA
ルートした1-論理：NGTIN * B     + NGTIN * NA      + B * NA
ルートした方程式は同一であり、同じ方程式に簡略化する。証明は与えられないが、タームB * NAを用いて、タームNGTIN * A * BがNGTIN * Bに簡略化することに注意されたい。
【０１１６】
ＦＥＴおよび非ＦＥＴインスタンスが論理信号を駆動している場合、簡略化されるＦＥＴの実現は両方の論理方程式を使用して行われる。この規則が適用可能な状況は図３８に示されており、ここで信号Ｚは非ＦＥＴインスタンス、例えばADD4によって駆動されることができる。
【０１１７】
1-方程式がまさに(NMOS設計のような)引き上げＦＥＴを表すならば、論理が抽出され、0-方程式がゲートとして実現される。引き上げＦＥＴは、常にONである弱いｐ−ＦＥＴ(ゲート接地を持つ)として認識される。図３９で、信号Ｚについての1-方程式は引き上げＦＥＴを含み、従って0-方程式(A*B)がゲートとして実現される。
【０１１８】
論理信号が、Andされるプリチャージ(Anded-Precharge)またはAndされる放電(Anded-Discharge)のケースであり、クロックされるプリチャージ/チャージをもつポートではなく、また記憶ノードではない(すなわち弱い帰還インバータが存在する)場合、ゲートは、プリチャージ/チャージの他方の側の方程式を使用して抽出される(例えばAndされるプリチャージ(Anded-Precharge)のケースでは、0-方程式を使用する)。Andされるプリチャージ(Anded-Precharge)のケースでは、0-方程式は、余分なタームがANDされることを除いて1-方程式と同じである。例えば、図４０のAndされるプリチャージ(Anded-Precharge)回路の信号Ｚは次の方程式を持つ。
【０１１９】
【数６】
1-方程式：PRE
0-方程式：A * B * PRE
回路は、入力Ａ、ＢおよびＰＲＥ、および出力ＺをもつＮＡＮＤゲートとして抽出される。論理信号がポートである場合、この規則は発火しないようにされる。リーフセル(leaf cell)設計者は、その値に影響を与えることができる信号に外部ＦＥＴをフック(hook)することが知られているからである。論理信号が記憶ノードの一部分である場合、ゲートは抽出されない。その代わり方程式はラッチのセット/リセット論理の一部分になる。
【０１２０】
論理信号が、プリチャージ(Precharge)または放電(Discharge)のケースであり、ポートではなく、また記憶ノードではない(すなわち弱い帰還インバータが存在する)場合、ゲートはプリチャージ(Precharge)/放電(Discharge)の他方の側の方程式を使用して抽出される(例えばプリチャージ(Precharge)のケースでは、0-方程式を使用する)。この規則は、プリチャージ(Precharge)/放電(Discharge)のケースがプリチャージャー(precharger)/ディスチャージャー(discharger)にクロック信号になることを要求し、他方の側でANDされることを要求されるタームはないことを除いて、上記のAndされるプリチャージ(Anded-Precharge)/Andされる放電(Anded-discharge)規則と同様である。例えば、プリチャージ(Precharge)のケースは図４１に示されており、そこで信号Ｚについて方程式は次式で示される。
【０１２１】
【数７】
0-方程式：A * B
1-方程式：NCK
またこの規則は、別の論理信号からの転送ＦＥＴとともにクロック・プリチャージャーのケースを支持する。例えば図４２について考える。そこでＣＫはＺをプリチャージしており、信号Ｂは、ＡからＺまで転送ｎ−ＦＥＴをゲートしている。これは、結果として生じる実現がＮＡＮＤゲートであるプリチャージ(Precharge)のケースである(Z =   〜(X * 〜A))。
【０１２２】
論理信号が３状態(tristate)のドライバであって単純な転送ＦＥＴではない場合、３状態のゲート実現が使用される。３状態のドライバは図４３で示されるように、論理信号についてルートした方程式が次の形式で示されるものである。
【０１２３】
【数８】
ルートした0-方程式： 〜DATA * EN
ルートした1-方程式： 〜DATA + 〜EN
(ここで、ENはイネーブル信号である)
論理信号が３状態のＣＭＯＳドライバ(図４４を参照)である場合、ＣＭＯＳ ＦＥＴの実現が行われる。この規則は、２つのイネーブル(E1およびE2)が相補的である必要がないという事実がなければ、３状態のドライバに類似している。この規則の条件での間違った合致を制限するために、論理信号は一つの引き上げおよび引き下げＦＥＴによって駆動される必要がある。
【０１２４】
論理信号が「クロックされる論理」であって、３状態のドライバでない場合、実現は転送ＦＥＴに従うゲートを使用して行われる。クロックされる論理では、他の方程式で相補されるタームのすべてが削除される場合に1-および0-方程式が安定する。例えば図４５で、以下の信号Ｚの方程式はクロックされる論理を表す。
【０１２５】
【数９】
0-方程式：D * (EN1 + EN2)
1-方程式：D + (〜EN1 * 〜EN2)
EN1およびEN2は0-方程式と1-方程式の間で相補的であり、(EN1およびEN2の全てのタームが取り除かれる)残りの方程式は、自明であるが安定している。クロックされる論理は転送ＦＥＴとして実現され、除去される「相補形式」論理(上記の例のEN1およびEN2の形式)によってゲートされ、(相補形式が除去される)残りの安定した論理によって駆動される。図４５の例で、結果として生じる実現は(EN1＋EN2)によってゲートされる転送ＦＥＴであり、Ｄのインバータ(図４６)によって駆動される。
【０１２６】
論理信号がシングルエンドのクロックされる論理のケースであり、それが記憶入力ノード(すなわちラッチへの入力)であり、入力がシングルエンドであるならば、適当な実現は、クロックされる論理を実現する論理ゲートからの転送ＦＥＴである。シングルエンドのクロックされる論理で、方程式は次の形式である。
【０１２７】
【数１０】
1-方程式：A
0-方程式：CK + A
図４７の信号Ｚはこれらの方程式から導き出される。両方の方程式は、一方の側の直列のクロック・タームがなければ、同じものである(クロック・タームが1-方程式にあれば、類似の状況が存在する)。論理信号は、Ａを生成する１つまたは複数のゲート(Ａがただ一つの信号である場合はインバータ)を用いて実現され、ＣＫによって記憶ノードにゲートされる転送ＦＥＴに従う。図４７についての実現が、図４８に示されている。入力はシングルエンドであることが要求され、そうでないとこの規則は発火されない。シングルエンドとは、クロック・タームがoffであるので、全部の信号が(両側で)offである間、「非活動に」なることが保証されていることを意味する。クロック・タームがonである間、実現は相補形論理ゲートと全く同様であることに注意されたい。
【０１２８】
論理信号が示される記憶ノードであるならば、それはＦＥＴとして実現される。示される記憶ノードは、記憶入力ノードでないポートであり(すなわち、交差結合されたインバータのような定義されたラッチではない)、ただ一つの方程式をもち(他方の側はＦＥＴトリーを持たない)、一つの方程式はクロックである。ＣＫの唯一の1-方程式を持つ図４９の信号Ｚは、示される記憶ノードの例である。
【０１２９】
論理信号が記憶入力ノードではないが、３状態であると知られているポートからの転送ゲートを持つ場合には、それはＦＥＴを用いて実現される。主要な３状態が可能なポート・インスタンスは、それが入力または双方向のポートであり、それを駆動すると知られているＦＥＴが存在する時である(データベースのＦＥＴ方向から取られる)。図５０の論理信号Ｚは、信号Ｙが３状態可能なドライバであると決定されるとき、この規則の必要条件を満足する。このケースでは(および論理関数上の適用可能な規則がないとき)、信号が３状態になるように、論理信号への転送ゲートをＦＥＴとして実現することが好ましい。
【０１３０】
論理信号がポートであり、一つのレールにのみ引くＦＥＴがあり、ポートは厳密に出力であるかまたは他の可能なレシーバをもたない双方向であるかのどちらかである場合、ＦＥＴ実現が行われる。この規則の発火を引き起こすケースについて図５１を参照されたい。ポートがレシーバと双方向である場合、ユーザは、ＦＥＴが一体必要とされるかを理解するように促されることがありえる。
【０１３１】
論理信号が両側の論理方程式をもつ入力または双方向ポートであって、記憶ノードではない場合、ＦＥＴ実現が行われる。この規則は、ゲートが入力ポートに対向して駆動するように(それはある試験装置に問題を引き起こす)使用されないようにする。図５２でこの規則は、ゲートＡおよびＢが入力ポートＩＮに対向して駆動することを防ぐ。
【０１３２】
論理信号が他の論理信号から転送ＦＥＴへ接続されるだけであり、それが記憶ノードでないならば、ＦＥＴ実現が行われる。これは、図５３の信号Ｚについて示されるような変換関数を表すための最も自然な方法である。
【０１３３】
論理信号の一方の側の方程式が１または０のどちらかであり、他方の方程式が反対(ドライブファイトを示す)でなければ、ゲート実現(例えばバッファ)は常に1 (「通電している(hot)」側)である方程式を使用して行われる。図５４は、VDDの反転である信号Ｚの実現を示す。信号Ｚの0-方程式は、VDDに結びつけられるゲートをもつＦＥＴのために常に「通電している」。
【０１３４】
弱い帰還がゲート実現をもつ論理信号について存在するならば(上述の規則の１つからの実現による)、その弱い帰還は、ゲートモデル・ネットリストから切り捨てられる。方法によって弱いと認識される図５５のＦＥＴ  Ｆ１は、実現から切り捨てられる。この規則は、単に電気的理由のためにだけ存在する帰還を切り捨てる。
【０１３５】
ルートした方程式が論理信号の一方の側について生成されることができないならば、その側は切り捨てられ、論理関数はその側について生成されない。図５６の信号Ｚの0-方程式は、Ｙを論理信号にもってくる道がないので切り捨てられる。標準的な方程式が論理信号について存在するが、ルートした方程式が生成されることができない場合、論理的な矛盾が見つけられる(A * 〜Aのように)。
【０１３６】
弱い帰還がインバータの一方の側だけに一つのＦＥＴを含む場合、弱い帰還は無視される(切り捨てられる)。図５７の実現で、弱い帰還インバータであるＦ１は無視される。弱い帰還は、単に電気的目的(例えば信号を「支える」)のために存在する。
【０１３７】
記憶ノード(交差結合されたインバータのような)が、ＦＥＴ論理によって前後両方で設定され(図５８の記憶ノードのＦＥＴ Ｆ１およびＦ２のように両方のインバータの入力で設定され)、設定方程式の一方が他方を包含する場合、包含される方程式は切り捨てられる。
【０１３８】
論理信号が記憶ノードであり、弱い帰還が無視されなかった場合、セット/リセット・ラッチを示すＦＥＴ実現が行われる。
【０１３９】
上述の論理関数規則が論理信号を実現することができない場合、ユーザーが促される。ユーザーは、１)実現のために1-または0-方程式のどちらかを選択し、それによってゲート実現をもたらす、２)ＦＥＴ実現を選択する、３)方程式を切り捨て、論理関数の実現を全体で不要にする、という選択を与えられることができる。これらの選択は、弱い論理信号と弱くない論理信号の両方に関連して与えられる。
【０１４０】
特性を入力ネットリストに加えて、上で述べられた規則の実現を受け付けないようにしてもよい(この方法の全ての規則によくあることである)。
【０１４１】
論理関数が決定され(62)、各々の論理信号について使用される実現のタイプがわかると、論理関数がゲートとしてマップされる(64)。
【０１４２】
1-または0-方程式だけを使用してその関数を決定する各々の論理信号の場合、ゲートは示されるゲート出力の反転があること記憶して、直接にマップされることができる。例えば、0-方程式Z = A * Bを使用する実現は、入力ＡおよびＢをもつＮＡＮＤゲートを生成する。弱い方程式から実現されるゲートは、そういうものとしてマークされる(出力ネットリストの強さの指定を含む)。
【０１４３】
ＦＥＴを使用して実現される各々の論理信号の場合には、1-および0-方程式が、それぞれｐ−ＦＥＴおよびｎ−ＦＥＴに置き換えられる。そしてゲートが方程式から生成されて、各々のＦＥＴゲート信号を駆動する。転送ＦＥＴの場合には、転送ＦＥＴが来る各々の論理信号の方程式が分離され、別々に実現される。この規則を使用して行われる模範的な変換が図５９に示されており、そこで信号Ｚは、ｐ−ＦＥＴおよびｎ−ＦＥＴを駆動するゲートを用いて実現される。
【０１４４】
(実現される)論理関数をゲートとしてマップした後、ゲートは以下の規則を使用して最適化される。
【０１４５】
ゲートの実現(A * 〜B) + (〜A * B)はＸＯＲゲートとして認識され、そのようなものによって置き換えられる。
【０１４６】
ＦＥＴがラッチの両端を駆動する(すなわち、帰還インバータの両端を駆動するＦＥＴがある)場合、それが生じる信号を反転させることによって一端から他端にＦＥＴを動かす試みがなされる。これを行うときの制約は、１)その駆動ＦＥＴが動かされると考えられる弱い帰還ゲートは、インバータであるか、または帰還グループの外のゲートによってその出力を受け取らせるかのどちらかである(そうでないと、その関数はそれを動かすことによって改悪されうる)、および２)ラッチの端を駆動するＦＥＴトリーは双方向でありえない(RAMセルによくあることである)、ということである。ＦＥＴを動かすことによって、ラッチの端を駆動するＦＥＴトリーに冗長をつくる場合、それは取り除かれる。この規則を使用して実行される模範的な最適化が、図６０に示されている。ＦＥＴ Ｆ２の動きに注意されたい。
【０１４７】
チェーンが奇数の長さであるならば、インバータのチェーンは一つのインバータに納められる。チェーンが偶数の長さであるならば、インバータのチェーンは１つのバッファに納められる。
【０１４８】
インバータが全ての入力を単純な論理ゲートに駆動するならば、ゲートおよびインバータは、全ての入力の反転された意味を使用して、それらの論理「二重(dual)」よって置き換えられる。例えば、ＮＯＲゲートへの全ての入力が反転されるならば、ＮＯＲゲートおよびインバータは反転された入力を使用してＡＮＤゲートによって置き換えられる(図６１)。この規則を使用することに対する制約は、どの入力もゲートを通る帰還と関係し得ないということである。
【０１４９】
バッファは削除され、以下の一つが真であることが与えられる(それによって、バッファは、両側の可能な３状態のノードの目前で保持されるようになる)。1)出力はポートでなく、ＦＥＴによって受け取られず、記憶ノードでない。2)入力はポートでなく、ＦＥＴによって受け取られず、記憶ノードでない。
【０１５０】
ゲートおよび以下のインバータ(中間信号を受け取るゲートをもたない)は、相補的なゲートによって置き換えられる。例えば、インバータ(ＮＯＴゲート)に続くＮＡＮＤゲートは、ＡＮＤゲートによって置き換えられる。
【０１５１】
ゲート最適化の後に使われないで残されるゲートは、出力ネットリストから除去される。
【０１５２】
多くの特性を、出力ネットリストのインスタンスおよび信号に加えることは有用である。特性は、弱いゲート、記憶ノード、相補的入力のような信号に関わる仮定(上述されたN<sig>取り決め)、プリチャージ、その他の識別を含むことができる。
【０１５３】
上で実現されるゲート(ゲート・プリミティブ)は、当業者によって他のゲート・プリミティブにマップされてもよい(66)。
【０１５４】
上で開示される方法の保守的な性質は、非常に正確なゲートモデル(すなわち出力ネットリスト)の抽出をもたらす。通常ＦＥＴおよびポートの方向は推論されうるが、そうすることができない場合、それらの方向はユーザーからリクエストされる。方法は、大胆な仮定を作るのではなく、事実を推論するように設計される。
【０１５５】
ＦＥＴモデル、および上述の方法を使用してそこから抽出されるゲートモデルは、図６２および図６３にそれぞれ示されている。
【０１５６】
本発明は例として次の実施態様を含む。
（１）a)ＦＥＴモデル回路の電源、グラウンドおよびクロック信号を認識するステップ(44)と、
b)ＦＥＴモデル回路のインバータを認識するステップ(46)と、
c)ＦＥＴモデル回路のすべての論理信号を認識し、保存するステップ(48)と、
d)認識される論理信号の各々について、一つまたは複数の構造ベースのブールの部分的トリーを組み立てるステップ(50)と、
e)一つまたは複数のブールの部分的トリーを発見的に枝刈りするステップ(52)と、
f)一つまたは複数のブールの部分的トリーから論理方程式を組み立てるステップ(54)と、
を含む、ＦＥＴモデル回路からゲートモデル回路を抽出する方法。
【０１５７】
（２）さらに、一つまたは複数のブールの部分的トリーを組み立てるに先立ち、各々のＦＥＴについて最初のＦＥＴ方向を決定するステップ(58)を含む、上記(1)の方法。
（３）さらに、一つまたは複数のブールの部分的トリーを組み立てるに先立ち、冗長なＦＥＴを削除するステップ(56)を含む、上記(2)の方法。
（４）さらに、一つまたは複数のブールの部分的トリーから論理方程式を組み立てるに先立ち、弱い部分的トリーを弱くない部分的トリーから分けるステップ(60)を含む、上記(3)の方法。
（５）さらに、共通の論理信号にルートした一つまたは複数の弱いおよび弱くないサブセットのそれぞれについて、論理関数を決定するステップ(62)を含む、上記(4)の方法。
（６）さらに、上記(5)で決定される論理関数を、対応するゲート・プリミティブにマップするステップ(64)を含む、上記(5)の方法。
【０１５８】
（７）一つまたは複数のブールの部分的トリーを発見的に枝刈りする上記ステップ(52)は、
a)ＦＥＴモデル回路のポートのポート方向を分解するステップ(72、78)と、
b)ＦＥＴモデル回路のＦＥＴのＦＥＴ方向を分解するステップ(70、76)と、
c)ポートとＦＥＴの両方の方向を分解するために、必要なところで、方法のユーザーを促すステップと、
を含む上記(1)の方法。
【０１５９】
（８）プログラマブル・コンピュータ(40)において、ＦＥＴモデル回路をゲートモデル回路に変えるエキスパートシステムであって、
a)ＦＥＴモデル入力ネットリストと、
b)推論エンジンと、
c)規則ベースと、
d)ユーザー入力と、
e)ゲートモデル出力ネットリストと、
を含む、上記エキスパートシステム。
【０１６０】
（９）上記規則ベースが、
a)少なくとも一つの発見的なトリー枝刈り規則ベース(68、74)と、
b)少なくとも一つのポート方向規則ベース(72、78)と、
c)少なくとも一つのＦＥＴ方向規則ベース(70、76)と、
を含む、上記(8)のエキスパートシステム。
【０１６１】
（１０）上記ＦＥＴモデル入力ネットリストが、ネットリスト・インタープリタを含む、上記(8)のエキスパートシステム。
【０１６２】
【発明の効果】
本発明によると、ＦＥＴモデル回路からゲートモデル回路を抽出する方法において、２つのモデル間の構造上の一致を保持し、抽出する時間を減少させることができる。
【図面の簡単な説明】
【図１】ＦＥＴモデルからゲートモデルを抽出する方法のフローチャートである。
【図２】図１に示されるＦＥＴモデルからゲートモデルを抽出する方法のより詳細なフローチャートである。
【図３】図１および図２の方法で使用される部分的トリーの枝刈り、ＦＥＴ方向、およびポート方向規則グループの間で起こるチェーンのフローチャートである。
【図４】冗長な並列のＦＥＴ  Ａを示す回路図である。
【図５】ＦＥＴ  Ａ、Ｂ、ＣおよびＤの複雑なＦＥＴの冗長を示す回路図である。
【図６】多様な論理および中間信号を示す回路図である。
【図７】論理信号Ｚに接続される多様なＦＥＴを示す回路図である。
【図８】図１または図２の方法によって図７の論理信号Ｚについて生成される部分的トリーを示す図である。
【図９】唯一の論理信号Ｓに接続されている入力ポートへのすべての接続を示す回路図である。
【図１０】安定したＮＡＮＤゲートによって駆動される信号を示す回路図である。
【図１１】示される方向と反対の方向をもつＦＥＴ Ｆ２を示す回路図である。
【図１２】代替の論理経路によって包含される論理パスを示す回路図である
【図１３】一致しないゲート信号をもつＦＥＴ  ＡおよびＮＡをもつ論理パスの回路図である。
【図１４】グラウンドに接続されたＦＥＴ Ｄを示す回路図である。
【図１５】論理信号ＹおよびＺの部分的トリーに含まれるＦＥＴ Ｆ１を示す回路図である。
【図１６】入力ポートから遠ざかる方へ駆動するＦＥＴを示す回路図である。
【図１７】出力ポートの方へ向かって駆動するＦＥＴを示す回路図である。
【図１８】信号Ｚを論理１へ駆動することが可能な唯一のＦＥＴであるＦＥＴ  Ｆ１を示す回路図である。
【図１９】マスター/スレーブ・レジスタの転送ＦＥＴ Ｆ１を示す回路図である。
【図２０】駆動されないポートＡを示す回路図である。
【図２１】ポートＺを駆動する安定した論理を示す回路図である。
【図２２】駆動されない入力ポートＺを示す回路図である。
【図２３】出力ポートＹを示す回路図である。
【図２４】双方向ポートＺを示す回路図である。
【図２５】２路帰還を示す回路図である。
【図２６】３路帰還を示す回路図である。
【図２７】ポートＺと信号Ｙの間の帰還に含まれる弱いＦＥＴ  Ｆ１を示す回路図である。
【図２８】ＣＭＯＳ相補形ＡＮＤ-ＯＲゲートの下半分を示す回路図である。
【図２９】図２８のゲート部分のブール(boolean)・トリーを示す図である。
【図３０】並列の組換えが図１および図２の方法によって実行されたあとの、図２８のゲート部分のブール・トリーを示す図である。
【図３１】並列の組換えを受けないブール・トリーと関連する図２８と同様のＦＥＴ構造を示す回路図である。
【図３２】図３１の回路図のブール・トリーを示す図である。
【図３３】図１および図２の方法によって枝刈りが実行されたあとの、図３２のブール・トリーを示す図である。
【図３４】図１および図２の方法が実現されうるコンピュータを示す図である。
【図３５】図１および図２の方法を実現するために図３４のコンピュータをプログラムすることができる物理記憶媒体を示す図である。
【図３６】同一の1-および0-論理方程式をもつ信号Ｚを示す回路図である。
【図３７】同一のルートした1-および0-論理方程式をもつ信号Ｚを示す回路図である。
【図３８】非ＦＥＴインスタンスによって駆動される信号Ｚを示す回路図である。
【図３９】引き上げＦＥＴである1-論理方程式をもつ信号Ｚを示す回路図である。
【図４０】Andされるプリチャージ(Anded-Precharge)回路を示す回路図である。
【図４１】プリチャージ(Precharge)回路を示す回路図である。
【図４２】クロック・プリチャージャーを示す回路図である。
【図４３】ＦＥＴモデルの３状態のドライバに対応するゲートモデルを示す図である。
【図４４】ＦＥＴモデルの３状態のＣＭＯＳドライバに対応するゲートモデルを示す図である。
【図４５】クロックされる論理を示す回路図である。
【図４６】図１および図２の方法によって抽出される、図４５のクロックされる論理のゲートモデルである。
【図４７】シングルエンドのクロックされる論理を示す回路図である。
【図４８】図１および図２の方法によって抽出される、図４７の回路図のゲートモデルである。
【図４９】示される記憶ノードを示す回路図である。
【図５０】既知の３状態可能なポートからの転送ゲートをもつ信号Ｚを示す回路図である。
【図５１】一つのレールのみへ引くＦＥＴに接続されたポートを示す回路図である。
【図５２】1-および0-論理方程式をもつ、記憶ノードでない論理信号を示す回路図である。
【図５３】転送ＦＥＴのみに接続される論理信号Ｚを示す回路図である。
【図５４】図１および図２の方法によって「熱い」側をもつ論理信号について抽出されるゲートモデルを示す図である。
【図５５】弱い帰還ＦＥＴ  Ｆ１を示す回路図である。
【図５６】ルートした1-論理方程式が導き出されることができない信号Ｚを示す回路図である。
【図５７】別の弱い帰還ＦＥＴ  Ｆ１を示す回路図である。
【図５８】ＦＥＴ論理によってその前後で設定される記憶ノードを示す回路図である。
【図５９】1-および0-論理方程式のＦＥＴを使用して実現される信号Ｚについて生成されるゲートモデルを示す。
【図６０】第１のゲート最適化プロセスを示す図である。
【図６１】第２のゲート最適化プロセスを示す図である。
【図６２】ＦＥＴモデル回路の回路図である。
【図６３】図１および図２の方法によって抽出される、図３６のＦＥＴモデル回路に対応するゲートモデル回路である。
【図６４】第１の対のＦＥＴ実現されるキャパシタを示す図である。
【図６５】第２の対のＦＥＴ実現されるキャパシタを示す図である。
【図６６】２路帰還を示す別の回路図である。
【図１】
0003949764.tif 000006
【図２】
0003949764.tif 000007
【図３】
0003949764.tif 000008
【図４】
0003949764.tif 000009
【図５】
0003949764.tif 000010
【図６】
0003949764.tif 000011
【図７】
0003949764.tif 000012
【図８】
0003949764.tif 000013
【図９】
0003949764.tif 000014
【図１０】
0003949764.tif 000015
【図１１】
0003949764.tif 000016
【図１２】
0003949764.tif 000017
【図１３】
0003949764.tif 000018
【図１４】
0003949764.tif 000019
【図１５】
0003949764.tif 000020
【図１６】
0003949764.tif 000021
【図１７】
0003949764.tif 000022
【図１８】
0003949764.tif 000023
【図１９】
0003949764.tif 000024
【図２０】
0003949764.tif 000025
【図２１】
0003949764.tif 000026
【図２２】
0003949764.tif 000027
【図２３】
0003949764.tif 000028
【図２４】
0003949764.tif 000029
【図２５】
0003949764.tif 000030
【図２６】
0003949764.tif 000031
【図２７】
0003949764.tif 000032
【図２８】
0003949764.tif 000033
【図２９】
0003949764.tif 000034
【図３０】
0003949764.tif 000035
【図３１】
0003949764.tif 000036
【図３２】
0003949764.tif 000037
【図３３】
0003949764.tif 000038
【図３４】
0003949764.tif 000039
【図３５】
0003949764.tif 000040
【図３６】
0003949764.tif 000041
【図３７】
0003949764.tif 000042
【図３８】
0003949764.tif 000043
【図３９】
0003949764.tif 000044
【図４０】
0003949764.tif 000045
【図４１】
0003949764.tif 000046
【図４２】
0003949764.tif 000047
【図４３】
0003949764.tif 000048
【図４４】
0003949764.tif 000049
【図４５】
0003949764.tif 000050
【図４６】
0003949764.tif 000051
【図４７】
0003949764.tif 000052
【図４８】
0003949764.tif 000053
【図４９】
0003949764.tif 000054
【図５０】
0003949764.tif 000055
【図５１】
0003949764.tif 000056
【図５２】
0003949764.tif 000057
【図５３】
0003949764.tif 000058
【図５４】
0003949764.tif 000059
【図５５】
0003949764.tif 000060
【図５６】
0003949764.tif 000061
【図５７】
0003949764.tif 000062
【図５８】
0003949764.tif 000063
【図５９】
0003949764.tif 000064
【図６０】
0003949764.tif 000065
【図６１】
0003949764.tif 000066
【図６２】
0003949764.tif 000067
【図６３】
0003949764.tif 000068
【図６４】
0003949764.tif 000069
【図６５】
0003949764.tif 000070
【図６６】
0003949764.tif 000071