(57)【要約】特に乗算器を備えることのできるデジタル回路を検証するための、デジタル回路（６）とその基準記述（５）との間の等価試験に関するものであり、まず、デジタル回路（６）内に実現される乗算器に対して、複数の所定の代替実現部（７）から、実現される代替実現部を決定し、この代替実現部を乗算機能の代わりに基準記述（５）に挿入する。次に、挿入によって改変された基準記述を用いて等価試験を実行する。このようにして、基準記述と検証対象であるデジタル回路との間の構造的な等価度を著しく高めることができ、これにより、検証方法の速度が全体的に早くなる。
2006500647.tif 000002
【特許請求の範囲】
【請求項１】
検証対象となるデジタル回路（６）と、このデジタル回路の基準記述（５）とを比較する等価試験を用いて、デジタル回路内のエラーを認識するデジタル回路の検証方法であって、
上記デジタル回路の基準記述（５）によって記述される特定の回路構造に対して、既知である異なる複数の代替実現部（７）から、上記の検証対象となるデジタル回路（６）と構造的な等価度が最も高い代替実現部（７）を決定する工程ａと、
デジタル回路の基準記述（５）内において上記の回路構造それぞれの記述を、上記の工程ａによって各回路構造に対して決められた構造的な等価度が最も高い代替実現部（７）によって置換する工程ｂと、
上記デジタル回路（６）と、工程ｂによって改変された基準記述（５）とを比較する等価試験を実行する工程ｃとを含むことを特徴とする方法。
【請求項２】
工程ａにおいて、等価度が最も高い代替実現部が決定される上記の特定の回路構造は、乗算器であることを特徴とする、請求項１に記載の方法。
【請求項３】
工程ａにおいて、等価度が最も高い代替実現部（７）が決定される上記の特定の回路構造は、整数乗算機能を実現する乗算器であることを特徴とする、請求項２に記載の方法。
【請求項４】
請求項１〜３のいずれか１項に記載の方法は、コンピュータを用いて行われることを特徴とする方法。
【請求項５】
上記の基準記述（５）が、ＲＴＬ回路記述、ＶＨＤＬ回路記述、およびＶｅｒｉｌｏｇ回路記述を含む群から選択されることを特徴とする請求項１〜４のいずれか１項に記載の方法。
【請求項６】
工程ｃでは、デジタル回路（６）にある実現部と、工程ｂによって改変された基準記述（５）とを比較する等価試験を実行することを特徴とする請求項１〜５のいずれか１項に記載の方法。
【請求項７】
上記の特定の回路構造に対する所定の代替実現部（７）には、デジタル回路を設計するための合成装置によって援用される、上記の特定の回路構造の他の構造が含まれることを特徴とする請求項１〜６のいずれか１項に記載の方法。
【請求項８】
工程ａでは、基準記述（５）に組み込まれた複数の異なる代替実現部（７）をそれぞれシミュレートし、このシミュレートした代替実現部と、デジタル回路（６）における対応するシミュレーションとを比較することによって、各特定の回路構造に対して、構造的な等価度が最も高い代替実現部（７）を決定し、
上記の代替実現部との構造的な等価度が最も高く、デジタル回路（６）のシミュレーションとの等価度が最も高いシミュレーションを有した代替実現部（７）を、上記の特定の回路構造に対して決定することを特徴とする請求項１〜７のいずれか１項に記載の方法。
【請求項９】
工程ａにおいて、各回路構造に対して、複数の互いに異なる代替実現部（７）を同時にシミュレートし、シミュレートした上記の代替実現部をデジタル回路（６）のシミュレーションと比較することを特徴とする、請求項８に記載の方法。
【請求項１０】
互いに接続された複数の互いに異なる代替実現部（７）の入力部と、共通出力部に接続された、この代替実現部（７）の対応する出力部とを用いることにより、各回路構造に対する複数の互いに異なる代替実現部（７）を同時にシミュレートして、各代替実現部の回路機能を維持することを特徴とする請求項９に記載の方法。
【請求項１１】
上記の代替実現部（７）の出力部を、論理ＯＤＥＲ回路部を用いて上記の共通出力部に接続することを特徴とする請求項１０に記載の方法。
【請求項１２】
工程ａでは、各代替実現部（７）に対して、デジタル回路（６）のシミュレーションとの等価度を、各代替実現部とともに、基準記述（５）の個々のシミュレーションパターンとして出力される値の数を用いて決定し、
デジタル回路（６）によって対応するシミュレーションパターンとして出力される値と一致する代替値は、各代替実現部（７）のいくつかのシュミレーションパターンとして決定されるとともに、対応する代替実現部（７）の等価度として用いられることを特徴とする請求項８〜１１のいずれか１項に記載の方法。
【請求項１３】
工程ａでは、同値類細分方法を用いて、構造的な等価度が最も高い代替実現部（７）を決定することを特徴とする請求項１〜１２のいずれか１項に記載の方法。
【請求項１４】
検証対象となるデジタル回路の記述を格納する第１記憶手段（６）と、
上記のデジタル回路の基準記述を格納する第２記憶手段（５）と、
検証手段（２）とを備え、
上記の検証手段が、上記の検証対象となるデジタル回路（６）の記述と、基準記述（５）とを比較する等価試験によってデジタル回路内のエラーを認識できる、デジタル回路を検証する装置であって、
さらに、上記のデジタル回路における特定の回路構造に対する様々な所定の代替実現部を格納する第３記憶手段（７）を備え、
上記の検証手段（２）は、特定の回路構造に対して、検証対象となるデジタル回路との構造的な等価度が高い代替実現部を決定する構成となっており、
上記の検証手段（２）は、個々の特定の回路構造に対して、構造的な等価度が最も高い所定の代替実現部をデジタル回路の基準記述に挿入するとともに、等価試験を実行するために、検証対象となるデジタル回路の記述と、改変された基準記述とを比較することができる構成となっていることを特徴とする装置。
【請求項１５】
上記の装置は、請求項１〜１３のいずれか１項に記載の方法を実行できる構成となっていることを特徴とする請求項１４に記載の装置。
【請求項１６】
請求項１〜１３のいずれか１項に記載の方法を実行するための、データ媒体（３）に格納されたプログラムコードを有するコンピュータプログラム製品であって、
このプログラムコードは、コンピュータシステム（１）で実行可能であることを特徴とするコンピュータプログラム製品。
【請求項１７】
請求項１〜１３のいずれか１項に記載の方法を実行するための、コンピュータシステムに関連する電気的に読み出し可能な制御信号を備えたデジタル記憶媒体（３）。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
本発明は、デジタル回路、特に乗算器を備えたデジタル回路の検証方法に関するものであるとともに、そのための装置、およびコンピュータプログラム製品に関するものである。
【０００２】
周知のように、プロセッサやデジタル信号プロセッサ（ＤＳＰ），グラフィックチップセット等のデジタル回路には、乗算器または乗算機能（Multipliziererstrukturen oder Multiplikationsfunktionen）が広く用いられている。このような乗算機能を有するチップ内でエラーが生じると、他の回路構造内で生じるエラーと同様に、チップ全体を破損させてしまう場合がある。
【０００３】
したがって、最も重要となるのは、例えば合成ツールを用いてコンピュータを援用することによりデジタル回路を開発（entwickelt）した後、そのデジタル回路を検証することである。この検証に関し、近年、いわゆる等価試験（Aequivalenzpruefung）の注目度が上がっている。この等価試験とは、デジタル回路内の乗算機能が、基準記述（Referenzbeschreibung）にあるような回路構造の機能と、どの程度等しいのかを試験するものである。なお、基準記述とは、例えば、操作モードに関するＲＴＬ（レジスタトランスファーレベル：Register Transfer Level）記述、ＶＨＤＬ（超高速ＩＣ ＨＷ記述ランゲージ：Very High Speed IC HW Description Language）記述、Ｖｅｒｉｌｏｇ記述等である。近年の等価試験器は、数百万ゲートを有するデジタル回路を処理できる。等価試験器では、特に、回路構造を互い比較した結果（つまり、検証対象となるデジタル回路と、このデジタル回路が基準としている上記の基準回路記述とを比較した結果）、これらの回路構造が互いに非常に類似している（等価である）とき、比較結果が非常によいと判断する。一方、検証対象のデジタル回路と基準記述との構造が、その程度に差はあっても実質的に異なり、これにより内部等価（interne Aequivalenzen）が非常に低くなる場合には、満足な結果ではないと判断する。この場合、乗算器または乗算機能の形式的な検証が、デジタル回路の等価試験に関する最も複雑な課題の１つとなる。
【０００４】
十進数ＡとＢとは、様々な方法によって乗算できることが知られている。つまり、例えば積Ａ×Ｂであってもよいし、積Ｂ×Ａであってもよい。さらに、乗算される２つの十進数の個々の桁を互いに乗算し、その結果生じる部分積を合計することにより、上記と同じ積となることも知られている。これらの部分積を互いに加算する順序は、場合によって異なっていてもよい。もちろん、十進数Ａと十進数Ｂとにおいて他の乗算結果が得られることはない。そこで、選択される十進数ＡとＢとの乗算方法に応じるために、乗算器は、様々な代替実現部（Implementierungsalternativen）や改変実現部（Implemtantierungsvarianten）を用いることができる。なお、これら全ての改変実現部による乗算結果は同じであるが、改変実現部の構造に関しては、内部等価が全くない場合や、あるいは僅かにある場合がある。また、他の構造（アーキテクチャ）を乗算器の実現部として用いることができることも自明である。
【０００５】
さらに問題となるのは、デジタル回路の乗算機能は、通常、単独で存在しておらず、外因ロジック（Umgebungslogik）に内蔵されているという点である。また、これと同時に考慮に入れておかなくてはならない事として、場合によって、乗算機能の限定（例えば、デジタル回路を最適化するための乗算機能の限定）が不十分であり＜ＳＯＧ（Sea of Gates）＞、よって、形式的にみると、乗算機能はもはや（実際には）存在しないという事である。
【０００６】
これまで、デジタル回路内の乗算器を早くかつ確実に認識する方法は知られていない。デジタル回路を設計する近年の合成プロセスは、機能的に最適化しようとするがゆえに、例えば上記した回路構造と基準回路構造とを簡単に比較するような簡単な「パターン照合」といった方法は、除外されている。乗算器の検証については、競合する様々な方法があることが知られている。
【０００７】
最も簡単な、一般的といえる方法として、デジタル回路の乗算器に、特別な処理を行うことができないようにすることが提案されており、これによれば、等価試験という形で、デジタル回路を検証する前にデジタル回路の乗算器または乗算機能を明確に認識する必要がなくなるというものである。しかしながら、この方法によると、等価試験で度々長時間を要し、さらに、検証に失敗してしまう場合があるという不都合が生じた。なお、等価試験に要する時間の長さは、個々の乗算器が、（ランダムに）選択する代替実現部（等価試験はこの代替実現部に基づいて行われる）の影響を強く受ける。
【０００８】
各乗算器または乗算機能の等価試験を実行する前に乗算器を検証するという別の方法は、物理的に選択される代替実現部を、使用者が確定（つまり特定）するという方法である。しかしながら、この方法の問題は、この確定するために必要となる情報を検証時点で（もはや）得られないことが頻繁にある、ということである。等価試験を実行する前に使用者によって誤ったデータが作成されれば、誤った代替実現部（等価試験の基となる）が用いられ、よって、上記した一般的な（検証）方法と同じように不都合が生じてしまう。
【０００９】
最後に、単独で存在しているようにみえる個々の乗算機能または乗算器に限定した様々な検証方法（つまり、デジタル回路の実現部を検証すること、および、上記実現と基準記述を比較することが、乗算によってのみ行われる）も、従来技術から知られている。つまり、これは、例えばY.T. ChangおよびK.-T. Cheng「乗算器の、誘導に基づくゲートレベル検証（Induction-based Gate-level Verification of multipliers）」（International Conference on Computer-Aided Design (ICCAD)、１９０ページ以下、２００１年）で知られているような、ｎビット乗算器の検証をｎ回の部分等価試験に分けるための、誘導に基づいた方法である。また、J.-C. ChenおよびY.-A. Chen「整数乗算器の等価試験（Equivalence Checking of Integer Multipliers）」（Asian-Pacific Design Automation Conference (ASPDAC)、２００１年）には、例えば、２つの整数乗算器（zwei ganzzahligen Multiplizierern）の等価を試験するための、データ要素レベルに説明図の形式で示した、いわゆる「乗算型Power Hybrid Decision Diagrams」（★ＰＨＤＤ）と呼ばれるｎｘｎ配列乗算器またはｎｘｎウォリスバウム乗算器（Wallace-Baum-multiplizierer）が提案されている。さらに、この文献には、いわゆる「二分決定グラフ（Binary Decision Diagrams）」（ＢＤＤ）の形式でのビットレベルの整数乗算器や、いわゆる「乗算型Binary Moment Diagrams」（★ＢＭＤ）の形式でのデータ要素レベルの整数乗算器が開示されている。最後に、D. StoffelおよびW. Kunz「演算ビットレベルにおける整数乗算器の検証（Verification of Integer Multipliers on the Arithmetic Bitlevel）」（International Conference on Computer-Aided Design (ICCAD),１８３−１８９ページ、２００１年）では、整数乗算器を検証するために、加算器回路のゲートネットリスト（Gatternetzliste）から半加算器（Halbaddierern）のネットワークを抽出するというブールマッピングアルゴリズムまたはイメージアルゴリズム（Boolschern Mapping- oder Abbildungsalgorithmus）を使用し、その後、簡単な算術演算によって、加算器回路のビットレベルにおいて知られた算術の場合は、等価試験を実行できるようになることが提案されている。この文献において提案された方法は、整数乗算が、実質的に、部分積を形成し、最後の乗算結果を出すために当該部分積を加算する、という２つの部分に分割できるという既に説明した考え方に基づいている。
【００１０】
最後に記載した検証方法はそれぞれ、個々に単独で存在する乗算機能に限定している。しかしながら、乗算機能は、通常、単独では存在していないため、この検証方法は、実際にはデジタル回路の検証（つまり総合結果の検証）に用いることはできない。
【００１１】
したがって、デジタル回路内に実現された乗算器または乗算機能を検証するための実用的な方法は、これまで知られていない。従来技術から知られている検証方法の能率は、通常、各乗算機能の物理的実現の影響を強く受ける。したがって、従来技術によれば、デジタル回路を効果的に検証するために、検証するデジタル回路内の乗算器の特性および構造に関する情報が不可欠であった。
【００１２】
そこで、本発明の目的は、デジタル回路を検証するための効果的な方法、および、そのための装置を提示することにあり、これによって、デジタル回路内に実現された乗算器の代替実現部に関する情報が明確に知ることなく、あるいは乗算器の具体的な代替実現部のみに検証を限定しなくても、上記した問題を解決でき、特に、乗算器を備えた複雑なデジタル回路であっても、この回路を、等価試験を通じて検証することができる。
【００１３】
この目的を、請求項１の特徴部分を有する検証方法、および／または、請求項１４の特徴部分を有する検証装置によって達成する。さらに、本発明の検証方法を実行するためのプログラムコードを有するコンピュータプログラム製品は、コンピュータシステムにおいてプログラムを実行する場合、請求項１６の特徴部分によって提供される。また、本発明の検証方法を実行するための電子的に読み出し可能な制御信号を有するデジタル記憶媒体（例えば、ディスクまたはＣＤ‐ＲＯＭ）は、請求項１７に記載のコンピュータシステムとともに提供される。また、従属請求項に、本発明の好適で、かつ有効な形態について明示している。
【００１４】
本発明では、初めに、特定の回路構造における複数からなる所定の代替実現部のうちのどれを、デジタル回路を検証するために用いるかを確定または決定する。そのために、複数の回路構造の複数の異なる所定の代替実現部が、デジタル回路の基準記述への埋め込みの間にシミュレート（simuliert）され、そして、デジタル回路の実現部のシミュレーションと比較される。なお、この基準記述とは、等価試験の際にデジタル回路の実現部と比較されるものである。すなわち、複数ある所定の代替実現部を並行してシミュレートできる。
【００１５】
このようにして、デジタル回路の各特定回路構造に対して、検証対象であるデジタル回路の実現部のシミュレーションと等価の度合いが高いシミュレーションを示した代替実現部が決定される。
【００１６】
次に、このようにして決定された回路構造の代替実現部は、この回路構造の基準記述内にこの基準記述の代わりに挿入され、これにより、挿入によって改変された基準記述との実等価試験（eigentliche Aequivalenzpruefung）が実行できる。つまり、改変された基準記述が、検証対象となるデジタル回路の実現部と比較される。基準記述に挿入された特定の回路構造の代替実現部は、最終的に、特別な方法によって分離して検証することができる。
【００１７】
本発明によれば、等価試験を行うにあたり、および／または重要な部分構造（kritischen Teilstrukturen）を含む基準回路と、この回路の実現部との等価比較を行うにあたり、上記の部分構造の複数ある既知の代替実現部のうちからどれを検証対象であるデジタル回路の実現部に用いるのか、および／または、用いられた実現部の既知の代替実現部のうちのいずれが構造的に最も類似しているのかということを、まず確定および／または決定する。この構造的な類似は、（基準記述のコンテキスト（Kontext）に挿入された後の）１つの代替実現部が、検証対象の実現部にある内部設計点（interne Berechnungspunkte）と同一の内部設計点を有している場合に与えられる。ここでは、複数の代替実現部と、実際に用いられる１つの実現部との構造的な類似度を、その複雑さがデジタル回路の大きさにのみ線形従属する、シミュレーションに基づく方法によって決定する。これは、デジタル回路のランダム形成された入力割当ての定数によって、デジタル回路の全ての内部設計点において値を計算する（「ランダムパターン」シミュレーション）ことにより可能になる。このことは、基準記述のコンテキストにおける非常に重要な部分構造の知られている全ての代替実現部に対しても、デジタル回路の全ての実現部に対しても生じる。
【００１８】
また、重要な部分構造の代替実現部の内部設計点と、検証対象のデジタル回路の実現部の内部設計点とを完全に一致させる代わりに、ランダム形成された全ての入力割当てにおける設計点の一致のみを測定することが好ましい。この統計的な方法によって、個々の重要な部分構造にとって、実現部に対して構造的に最も類似した代替実現部を十分に決定することができる。
【００１９】
機能的に同じであるが構造的には著しく異なっている、部分構造の複数の代替実現部が存在する場合、基準回路の部分構造は、通常、非常に重要である。このような重要な部分構造の例として、乗算器構造が挙げられる場合が多い。したがって、上記した統計的な方法を用いるためには、重要な部分構造用の代替実現部だけは知られている必要があるが、検証対象のデジタル回路の実現部においてどの代替実現部を実際に使用したかということは知られる必要はない。
【００２０】
上記の構造的に最も類似した代替実現部を、すなわち、シミュレートした全パターンにおける代替実現部の内部設計点と、検証対象である実現部の内部設計点とが一致（等価）している代替実現部を、その複雑さがデジタル回路の大きさに線形依存する方法によって効率的に決定できるようにするためには、同値類細分（Aequivalenzklassenverfeinerung）方法を使用することができる。この方法とは、全ての内部設計点（それらの一致の度合いはまだ証明されていない）を、それぞれ同値類に統合する。次に、ランダム形成された、デジタル回路の入力割当てを、シミュレートした後、各同値類は、シミュレートされた入力割当てにおける要素（Elemente）が一致している部分類に分割する。その後、所定の数のシミュレーション工程後もなお同じ同値類に位置している内部観測点（Interne Beobachtungspunkte）を、等価（一致している）と見なすことができる。
【００２１】
上記方法により決定される、デジタル回路のシミュレーションと一致度が最も高いシミュレーションがなされた代替実現部を有する特定の回路構造または重要な部分構造の場合、乗算機能または乗算器は特に、上記したような従来の方法では検証できない（あるいは十分に検証できない）可能性がある。ところで、本発明は、当然ながら、デジタル回路の乗算器の検証または認識に限定されず、基本的には、様々な所定の代替実現部が適用されることにより形成されるあらゆる回路構造に対して用いられる。
【００２２】
以上の説明に関連する様々な利点もさらに得られる。乗算器は、その乗算器の基準記述、およびこの基準記述に埋め込まれた実現部を評価するだけでよい。検証対象である合成デジタル回路において、実現部の制限と乗算器の位置とを知る必要がない。具体的には、合成デジタル回路内のこのような実現部制限が明確に存在する必要もなく、例えば、他の回路部分との合成最適化を通じてこの制限を「インターリーブ（verwoben）」してもよい。本発明の好ましい形態では、合成デジタル回路に含まれる全ての乗算器または乗算機能を同時に認識することができる。本発明は、低コストで実現でき、また、デジタル回路に用いられる、乗算器のための代替実現部を認識するための、本発明の認識度および認識信頼性は高い。本発明の方法を実現するために必要な時間は、検証対象であるデジタル回路の大きさに線形依存する。上述したように、本発明の方法を、基本的には他の回路機能の認識にも転用できる。
【００２３】
本発明から得られた検証対象となるデジタル回路に用いられる、または本発明によって得られる他の特定回路構造に用いられる乗算器の改変実現部（ここでは、様々な異なるおよび／または所定の改変実現部が問題となる）に関する情報が、デジタル回路の等価試験の所要時間を著しく早める。このとき、コンピュータおよび／またはそれを用いた等価試験を実行する際の付加的なコストはほとんど必要ない。デジタル回路に用いられる改変実現部を確定することにより、そして、認識された改変実現部をデジタル回路と比較される基準記述に挿入することにより、基準記述とデジタル回路とは、構造的に非常に類似することになる。これにより、検証方法の所要時間とそのための必要メモリを著しく低減できる。また、検証機能自体の実現部の検証は、乗算機能の実現部を分離して観察でき、かつこの実現部の方法および構造に関して周知であるため、著しく改善して実行することができる。合成最適化を通じて回路の一部（特に乗算器構造の入力／出力部）を発見できなかった場合であっても、本発明の方法は、実際、しっかりと、かつ正確に実施できる。
【００２４】
次に、本発明に関する好ましい実施形態について、添付図面を参照しながら詳述する。本発明は、コンピュータを用いることによる、乗算器および／または乗算機能を備えたデジタル回路の、検証に関するものである。以下では、デジタル回路内の乗算器に用いられる代替実現部を認識する工程と、既に述べたような対応する改変された基準記述との等価試験を、実行する工程とを説明しており、これらの工程はは、他の回路構造における、いくつかの異なる予め規定された、あるいは所定の改変実現部にも原則的に適用できる。
【００２５】
図に、デジタル回路をコンピュータを用いて検証するための本発明に係る装置１を示す。中心的な構成要素としての装置１には、プログラム制御された制御部２が設けられている。この制御部２は、自動化された検証方法を実行するために、プログラム記憶装置３に格納されたコンピュータプログラムによって制御される。プログラム記憶装置３に格納されたコンピュータプログラムとは、例えば、ディスクまたはＣＤ−ＲＯＭのような内部交換可能なデータ媒体から読み込まれたプログラムが挙げられる。さらに、この制御ユニット２は、例えば、ＲＴＬ記述やＶＨＤＬ記述やＶｅｒｉｌｏｇ記述といったデジタル回路の基準記述が格納された記憶装置５にアクセスしている。この基準記述は、対応するデジタル回路の開発に用いられ、このデジタル回路の実現部（例えばＶＨＤＬ記述やＶｅｒｉｌｏｇ記述やゲートネット記述といった形状で実現される実現部）は、制御部２がアクセス可能な別の記憶装置６に格納されている。さらに、装置１には、デジタル回路の開発を可能にする合成ツールとして機能する記憶装置７が設けられており、デジタル回路の（整数）乗算機能を合成ツールによって可能にする代替実現部が格納されている。また、上述したように、乗算機能または乗算器はそれぞれ、他の様々な方法、および、特に様々な構造であっても実現可能である。
【００２６】
したがって、記憶装置５〜７に格納された情報にアクセスすると、検証対象である（例えばゲートネットリストの形の）デジタル回路の実現部と、等価試験を用いて比較するデジタル回路の基準記述（例えばＲＴＬ記述の形）と、（例えば、各合成ツールにより可能になった構造に応じて）乗算機能または乗算器としての互いに異なる予め規定された代替実現部と、基準記述における乗算器の位置／埋め込みとに関する情報が制御部２に認識される。これらの情報を用いて、制御部２では、次に詳述するデジタル回路の実現部の等価試験を実行できる。上記した記憶装置５〜７に格納された情報は、例えば、いずれにしても標準的な合成の流れの中に存在している。しかしながら、制御部２には、例えば、検証対象となるデジタル回路の実現部内の乗算器の位置／埋め込みは、その型と同じく、認識される必要はない。
【００２７】
また、制御部２は、与えられた情報を用いて、基準記述の個々の乗算機能のための、予め規定した代替実現部のうちのどれが、デジタル回路の実現部に使用されるのかを決定する。このために、制御部２は、基準記述内に乗算機能が埋め込まれる間に、全ての乗算機能の様々な代替実現部を並行してシミュレートし、このシミュレーション結果を、検証対象のデジタル回路の実現部のシミュレーションと比較する。この場合、基準記述の全乗算機能の全ての代替実現部に対して、デジタル回路の実現部との等価（一致）の度合いが決定される。この等価の度合いは、全てのシミュレーションパターンに対するデジタル回路の実現部の（任意だが確実な）設計点と同じ値を算出する各代替実現部の（内部）設計点である、各代替実現部の等価点の総数と定義できる。このようにして、制御部２は、基準記述の全乗算機能に対して、実現されたデジタル回路のシミュレーションと等価の度合いが最も高い代替実現部を決定する。等価の度合いの計算は、比較対象である回路の大きさに応じた線形時間において、同値類細分を用いて行ってもよい。
【００２８】
このような情報に基づけば、検証タスクを著しく簡単にできる。そのためには、制御部２によって、各乗算機能または乗算器構造に対して決定された代替実現部は、デジタル回路の基準記述にこの乗算機能（例えばＲＴＬ乗算機能）の代わりに挿入される。そして、このようにして改変された基準記述と検証対象となるデジタル回路の実現部とが等価比較される。この改変された基準記述と、デジタル回路の実現部との間の構造的な一致度は高いため、続く等価試験を著しく早く行なうことができる。乗算に関する理想は、２つの回路記述が完全に一致（等価）していることである。そうすれば、等価試験を著しく簡単に実行できるからである。実際、非常に高度な構造的な一致が少なくとも得られる。
【００２９】
最後に、基準記述内で使用される乗算機能または乗算器としての代替実現部は、別々に検証することができる。つまり特殊な方法によって分離してもよい。
【００３０】
また、等価試験の結果を、出力部４を介して出力することができる（よって、スクリーンに映像化するといったことが可能となる）。
【００３１】
乗算機能や乗算器の機能の全代替実現部を同時にシミュレートすることは、技術的には非常に簡単に実現できる。したがって、例えば、乗算器の第１入力部を互いに接続することができ、かつ、第１出力部を、機能を維持したまま（つまり個々の全ての乗算器の乗算結果を誤る（Verfaelschung）ことなく）共通の出力部に供給することできる。これは、例えば、論理的なＯＤＥＲ結合（ODER-Verknuepfung）を用いることによって可能である。さらに、代替実現部およびデジタル回路記述のシミュレーションのために、従来のランダムパターンシミュレーションを使用することもできる。
【００３２】
デジタル回路記述における乗算器の様々な代替実現部を認識するための上記した方法には、合成検証を加速するために（つまり、ＲＴＬ記述から合成されるゲートネットリストとＲＴＬ記述とを比較するために）、重要な意味がある。形式的な回路比較のためのツールの実行時間と必要メモリとは、比較対象となる回路間、または、それに相当する回路記述間の等価の度合いの高さに著しく影響される。この等価の度合いを、一致する機能を算出する２つの回路からなる一対の内部設計点の個数として表すことができる。上記の方法により、乗算器において実現された代替実現部に対して非常に高い認識度が得られる。また、この方法は、非常に少ないシミュレーションによって、複数の異なる代替実現部を区別することができ、これによって、この方法の付加的な所要時間をさらに短くできるという点でも優れている。
【００３３】
本発明の方法の実験結果は、例外なく非常に好ましいものが得られている。したがって、２１個もの異なる（異なるビット幅、および異なる構造をもつ）乗算器の実現部を認識するために、わずか約２分間の所要時間を要した。各乗算器に対して４つの代替実現部を選択することができ、全ての場合に、適切な代替実現部が認識できた。また、これらの適切な代替実現部では、内部設計点の５０〜６０％一致が達成される一方で、この方法によれば誤った代替実現部は１０〜２０％しかなかった。この場合、１０２４シミュレーション（シミュレーション刺激（Simulations-Stimuli））のみが算出された。最後の検証工程（等価試験）を、この情報を用いて著しく加速でき、約４５分後に終了することができた。従来の手順、つまり、最後の分離した検証を有する乗算器構造用の代替実現部を認識する際には、約２４時間の事項時間が必要であった。
【００３４】
要約すれば、ほとんど無視できる程度しかコストがかからずに、用いた乗算器の代替実現部を非常に高い信頼度で認識でき、デジタル回路の形式的な検証を著しく早めることができる。
【図面の簡単な説明】
【００３５】
【図１】乗算器構造または乗算機能を備えたデジタル回路を、コンピュータを用いて検証するための装置の構成を示す図である。
2006500647.tif 000003
【手続補正書】
【提出日】平成16年7月14日(2004.7.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
検証対象となるデジタル回路（６）と、このデジタル回路の基準記述（５）とを比較する等価試験を用いて、デジタル回路内のエラーを認識するデジタル回路の検証方法であって、
上記デジタル回路の基準記述（５）によって記述される特定の回路構造に対して、既知である異なる複数の代替実現部（７）から、上記の検証対象となるデジタル回路（６）と構造的な等価度が最も高い代替実現部（７）を決定し、上記の異なる複数の実現代案（７）をそれぞれ基準記述（５）と組み合わせてシミュレートするとともに、シミュレートされた実現代案とデジタル回路（６）のシミュレーションとを比較することにより、デジタル回路（６）と構造的な等価度が最も高く、いくつかのシミュレーションパターンにおいてデジタル回路との設計点の一致度が最も高い実現代案（７）を決定する工程ａと、
デジタル回路の基準記述（５）内において上記の回路構造それぞれの記述を、上記の工程ａによって各回路構造に対して決められた構造的な等価度が最も高い代替実現部（７）によって置換する工程ｂと、
上記デジタル回路（６）と、工程ｂによって改変された基準記述（５）とを比較する等価試験を実行する工程ｃとを含むことを特徴とする方法。
【請求項２】
工程ａにおいて、等価度が最も高い代替実現部が決定される上記の特定の回路構造は、乗算器であることを特徴とする、請求項１に記載の方法。
【請求項３】
工程ａにおいて、等価度が最も高い代替実現部（７）が決定される上記の特定の回路構造は、整数乗算機能を実現する乗算器であることを特徴とする、請求項２に記載の方法。
【請求項４】
請求項１〜３のいずれか１項に記載の方法は、コンピュータを用いて行われることを特徴とする方法。
【請求項５】
上記の基準記述（５）が、ＲＴＬ回路記述、ＶＨＤＬ回路記述、およびＶｅｒｉｌｏｇ回路記述を含む群から選択されることを特徴とする請求項１〜４のいずれか１項に記載の方法。
【請求項６】
工程ｃでは、デジタル回路（６）にある実現部と、工程ｂによって改変された基準記述（５）とを比較する等価試験を実行することを特徴とする請求項１〜５のいずれか１項に記載の方法。
【請求項７】
上記の特定の回路構造に対する所定の代替実現部（７）には、デジタル回路を設計するための合成装置によって援用される、上記の特定の回路構造の他の構成が含まれることを特徴とする請求項１〜６のいずれか１項に記載の方法。
【請求項８】
工程ａにおいて、各回路構造に対して、複数の互いに異なる代替実現部（７）を同時にシミュレートし、シミュレートした上記の代替実現部をデジタル回路（６）のシミュレーションと比較することを特徴とする、請求項１〜７のいずれか１項に記載の方法。
【請求項９】
互いに接続された複数の互いに異なる代替実現部（７）の入力部と、共通出力部に接続された、この代替実現部（７）の対応する出力部とを用いることにより、各回路構造に対する複数の互いに異なる代替実現部（７）を同時にシミュレートして、各代替実現部の回路機能を維持することを特徴とする請求項８に記載の方法。
【請求項１０】
上記異なる代替実現部（７）の出力部を、論理ＯＤＥＲ回路部を用いて上記の共通出力部に接続することを特徴とする請求項９に記載の方法。
【請求項１１】
工程ａでは、各代替実現部に対して、デジタル回路（６）のシミュレーションとの等価度を、各代替実現部とともに、基準記述（５）の個々のシミュレーションパターンとして出力される値の数を用いて決定し、
デジタル回路（６）によって対応するシミュレーションパターンとして出力される値と一致する代替値は、各代替実現部（７）のいくつかのシュミレーションパターンとして決定されるとともに、対応する代替実現部（７）の等価度として用いられることを特徴とする請求項１〜１０のいずれか１項に記載の方法。
【請求項１２】
工程ａでは、同値類細分方法を用いて、構造的な等価度が最も高い代替実現部（７）を決定することを特徴とする請求項１〜１１のいずれか１項に記載の方法。
【請求項１３】
検証対象となるデジタル回路の記述を格納する第１記憶手段（６）と、
上記のデジタル回路の基準記述を格納する第２記憶手段（５）と、
検証手段（２）とを備え、
上記の検証手段が、上記の検証対象となるデジタル回路（６）の記述と、基準記述（５）とを比較する等価試験によってデジタル回路内のエラーを認識できる、デジタル回路を検証する装置であって、
さらに、上記のデジタル回路における特定の回路構造に対する様々な所定の代替実現部を格納する第３記憶手段（７）を備え、
上記の検証手段（２）は、特定の回路構造に対して、検証対象となるデジタル回路との構造的な等価度が高い代替実現部を決定する構成となっており、
上記の検証手段（２）は、個々の特定の回路構造に対して、構造的な等価度が最も高い所定の代替実現部をデジタル回路の基準記述に挿入するとともに、等価試験を実行するために、検証対象となるデジタル回路の記述と、改変された基準記述とを比較することができる構成となっていることを特徴とする装置。
【請求項１４】
上記の装置は、請求項１〜１２のいずれか１項に記載の方法を実行できる構成となっていることを特徴とする請求項１３に記載の装置。
【請求項１５】
請求項１〜１２のいずれか１項に記載の方法を実行するための、データ媒体（３）に格納されたプログラムコードを有するコンピュータプログラム製品であって、
このプログラムコードは、コンピュータシステム（１）で実行可能であることを特徴とするコンピュータプログラム製品。
【請求項１６】
請求項１〜１２のいずれか１項に記載の方法を実行するための、コンピュータシステムに関連する電気的に読み出し可能な制御信号を備えたデジタル記憶媒体（３）。
【国際調査報告】
2006500647.tif 000004
2006500647.tif 000005
2006500647.tif 000006
2006500647.tif 000007