(57)【要約】【課題】近似精度がよく且つ安定性が保証された伝達関数の縮約を行う回路解析技術を提供する。【解決手段】線形回路の状態方程式をモーメント展開し第１近似伝達関数を算出するモーメント演算手段３、モーメント展開された第１近似伝達関数をパデ近似により縮約する縮約手段４、特性多項式がフルヴィッツ多項式か判別する安定性判別手段５、特性多項式がフルヴィッツ多項式でない場合、特性多項式がフルヴィッツ多項式であることを制約条件、第１近似伝達関数との間のモーメント空間の距離を目的関数とし、非線形計画法により目的関数が最小となる第２近似伝達関数の各次数のモーメントを算出する伝達関数安定化手段８、第２近似伝達関数をパデ近似により縮約する縮約手段４を備えた。これにより縮約した近似伝達関数を安定性と精度の両面で保証する。【選択図】        図２
2007094736.tif 000002
【特許請求の範囲】
【請求項１】
入力された線形回路の状態方程式の係数行列に基づき、当該線形回路の伝達関数をテイラー（Taylor）展開したときの各次数のモーメントを算出するモーメント演算手段；
並びに、前記各次数のモーメントにより表される展開された前記伝達関数（以下「第１の近似伝達関数」という。）をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第１の縮約手段；
を備えた線形回路の伝達関数の縮約を行う回路解析装置において、
前記特性多項式がフルヴィッツ（Hurwitz）多項式であるか否かを判別する安定性判別手段；
前記安定性判別手段が前記特性多項式はフルヴィッツ多項式と判別した場合、前記第１の縮約手段により算出された前記縮約伝達関数の各係数を出力する第１の出力手段；
前記安定性判別手段が前記特性多項式はフルヴィッツ多項式と判別しない場合、前記第１の近似伝達関数を近似する第２の近似伝達関数の特性多項式がフルヴィッツ多項式であることを制約条件、前記第１及び第２の近似伝達関数の間のモーメント空間の距離を目的関数とし、数理計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出する伝達関数安定化手段；
前記第２の近似伝達関数をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第２の縮約手段；
並びに、前記第２の縮約手段により算出された前記縮約伝達関数の各係数を出力する第２の出力手段；
を備えた回路解析装置。
【請求項２】
前記第１（第２）の縮約手段は、（２ｎ−１）次のモーメント（ｎ＞１）で前記伝達関数を近似した第１（第２）の近似伝達関数を、パデ近似により、分母多項式の次数がｎ、分子多項式の次数が（ｎ−１）の有理多項式で表した縮約伝達関数の分母多項式（特性多項式）及び分子多項式の各係数を算出するものであり、
前記安定性判別手段は、
前記特性多項式の各係数がすべて正値であるか否かを判定する係数判定手段；
（数１）により表されるｎ個の行列式（以下「主座小行列式」という。）Ｈ１，Ｈ２，…，Ｈｎ（但し、ｎは特性方程式の次数）を算出し、それらがすべて正値であるか否かを判定する行列式判定手段；
及び、前記特性多項式の各係数がすべて正値で且つ前記各主座小行列式Ｈ１，Ｈ２，…，Ｈｎがすべて正値の場合に、前記特性多項式がフルヴィッツ多項式であると判別する総合判定手段；
を備えていることを特徴とする請求項１記載の回路解析装置。
【数１】
2007094736.tif 000039
【請求項３】
前記伝達関数安定化手段は、前記安定性判別手段が前記特性多項式はフルヴィッツ多項式と判別しない場合、
前記特性多項式の各係数がすべて正値で且つ前記各主座小行列式Ｈ１，Ｈ２，…，Ｈｎがすべて正値であることを制約条件、
（２ｎ−１）次の前記第１の近似伝達関数のモーメント（数２）及び（２ｎ−１）次の前記第２の近似伝達関数のモーメント（数３）に対して（数４）で表される累積二乗誤差Ｏを目的関数とし、
数理計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出するものであること
を特徴とする請求項２記載の回路解析装置。
【数２】
2007094736.tif 000040
【数３】
2007094736.tif 000041
【数４】
2007094736.tif 000042
【請求項４】
前記伝達関数安定化手段は、前記制約条件に基づき、逐次２次計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出すること
を特徴とする請求項１乃至３の何れか一に記載の回路解析装置。
【請求項５】
入力された線形回路の状態方程式の係数行列に基づき、当該線形回路の伝達関数をテイラー（Taylor）展開したときの各次数のモーメントを算出するモーメント演算ステップ；
並びに、前記各次数のモーメントにより表される展開された前記伝達関数（以下「第１の近似伝達関数」という。）をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第１の縮約ステップ；
を有する線形回路の伝達関数の縮約を行う回路解析方法において、
前記特性多項式がフルヴィッツ（Hurwitz）多項式であるか否かを判別する安定性判別ステップ；
前記安定性判別ステップにおいて前記特性多項式はフルヴィッツ多項式であると判別された場合、前記第１の縮約ステップにおいて算出された前記縮約伝達関数の各係数を出力する第１の出力ステップ；
前記安定性判別ステップにおいて前記特性多項式はフルヴィッツ多項式であると判別されなかった場合、前記第１の近似伝達関数を近似する第２の近似伝達関数の特性多項式がフルヴィッツ多項式であることを制約条件、前記第１及び第２の近似伝達関数の間のモーメント空間の距離を目的関数とし、数理計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出する伝達関数安定化ステップ；
前記第２の近似伝達関数をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第２の縮約ステップ；
並びに、前記第２の縮約ステップにおいて算出された前記縮約伝達関数の各係数を出力する第２の出力ステップ；
を有する回路解析方法。
【請求項６】
コンピュータに読み込んで実行させることにより、コンピュータを請求項１乃至４の何れか一記載の回路解析装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線形回路の伝達関数の縮約を行う回路解析装置であって、特に、近似精度がよく且つ安定性が保証された伝達関数の縮約を行う回路解析装置に関する。
【背景技術】
【０００２】
近年、ディープ・サブミクロン化が進むＶＬＳＩの設計においては、ゲート遅延に対して配線遅延が相対的に増大している。そのため、特に、レイアウト後のタイミング設計においては、配線に関するより高精度な遅延解析が行えるようにすることが急務となっている。
【０００３】
そこで、高精度の解析を短時間で行う手法として、各種のモデル次数削減（Model Order Reduction： 以下「ＭＯＲ」という。）法が提案されている（非特許文献１，２参照）。ＭＯＲ法では、配線部分を伝達関数でモデル化して高精度の解析を実現し、その伝達関数の特性を近似したまま伝達関数の次数を低減する。つまり伝達関数を縮約する。これにより、解析時間の短縮が図られる。
【０００４】
ＭＯＲ法の一つに、漸近的波形評価（Asymptotic Waveform Evaluation：以下「ＡＷＥ」という。）法がある（特許文献１参照，非特許文献３，４参照）。ＡＷＥ法は、線形回路の伝達関数をテイラー（Taylor）展開したときのｓの係数（ｓはラプラス（Laplace）変数）、すなわちモーメントを計算し、その情報を元にパデ（Pade）近似（非特許文献１，２参照）を用いて縮約された伝達関数を求める手法である。
【０００５】
一方、行数と列数が、それぞれ縮約前後の状態変数の数に等しい縦長長方形をした射影行列（projection matrix）を用いて伝達関数の縮約を図るProjection Framework法（射影構成法）がある（非特許文献６参照）。Projection Framework法としては、例えば、Arnoldi法（非特許文献７参照）やPRIMA法（非特許文献８参照）が公知である。
【特許文献１】特開平８−５０１５２号公報
【非特許文献１】Mustafa Celik, Lawrence Pileggi, and Altan Odabasioglu, "IC Interconnect Analysis", Kluwer Academic Publishers, 2002, pp.17-20, 119-150.
【非特許文献２】Chung-Kuan Cheng, John Lillis, Shen Lin, and Norman Chang, "Interconnect Analysis and Synthesis", Wiley & Sons, October 1999, pp.72-79.
【非特許文献３】Yehea I. Ismail, and Eby G. Friedman, "On-Chip Inductance in High Speed Integrated Circuits", Kluwer Academic Publishers, Massachusetts, 2001.
【非特許文献４】L. Pillage and R. Rohrer. "Asympototic Waveform Evaluation for Timing Analysis", IEEE Transactions on Computer-Aided Design, 9(4):352-366, April 1990.
【非特許文献５】鈴木五郎，下村勇希，伊藤富裕美，「AWE法を用いたVLSI配線遅延解析」，第67回情報処理学会全国大会，4A-1，２００５年３月．
【非特許文献６】下村勇希，鈴木五郎，伊藤富裕美，「Framework法を用いたVLSI配線遅延解析」，第67回情報処理学会全国大会，4A-2，２００５年３月．
【非特許文献７】L. Miguel Silveira, Mattan Kamon, and Jacob K. White, "Efficient reduced-order modeling of frequency-dependent coupling inductances associated with 3D interconnect structure", Proc. Design Automation Conf., pp.376-380, San Francisco, CA, June 1995.
【非特許文献８】A. Odabasioglu, M. Celik, and L. T. Pileggi, "PRIMA: Passive reduced-order interconnect macromodeling algorithm," IEEE Transactions On Computer -Aided Design of Integrated Circuits and Systems, vol. 17, pp. 645-654, 1998.
【非特許文献９】前田肇，「線形システム」，初版，株式会社朝倉書店，２００１年１２月１０日，ｐｐ．１６５−１６７．
【非特許文献１０】Schittkowski, K., "NLQPL: A FORTRAN-Subroutine Solving Constrained Nonlinear Programming Problems", Annals of Operations Research, Vol. 5, pp 485-500, 1985.
【非特許文献１１】A. Hurwitz, "Uber die Bedingungen unter welchen eine Gleichung nur Wurzeln mitnegativen reellen Teilen besitzt," Mathematicshe Annalen, 46, pp.273284, 1895.
【非特許文献１２】矢部博，八巻直一，「応用数値計算ライブラリ  非線形計画法」，朝倉書店，１９９９年６月１０日，ｐｐ．５７−８０．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記ＡＷＥ法は、実用化を図る上で、縮約された伝達関数の不安定性が問題となる。実際に、１５０ｎｍプロセス上に実装したマイクロ・プロセッサのデータ・パス系配線に関するレイアウト設計データを用いた評価でも、縮約された伝達関数が不安定な振る舞いをしてしまうことが多々あることが確認されている（非特許文献５参照）。
【０００７】
遅延解析のために１０ＭＨｚのパルス入力時の時間応答を解析した例を図１に示す。図１において、繰り返されている波形（波線Ａ）が、縮約前の伝達関数の時間応答である。一方、実線Ｂは、従来のＡＷＥ法を用いて縮約した伝達関数の時間応答である。図１から明らかなように、従来のＡＷＥ法を用いて縮約した伝達関数の時間応答は、発散していることが分かる。
【０００８】
このように、ＡＷＥ法では、縮約された伝達関数の安定性が保証できないことが、実用化を図る上での大きな障害となっている。
【０００９】
一方、上述したArnoldi法やPRIMA法等のProjection Framework法においては、縮約伝達関数の安定性を完全に保証することができる。
【００１０】
しかしながら、縮約される前後の伝達関数のモーメントを比較した場合、縮約された伝達関数の分母多項式の次数（Laplace変数ｓの次数のこと。以下同じ。）をｎとすると、ＡＷＥ法ではｓ０の係数から２ｎ個分のモーメントを一致させることが可能であるのに対し、Arnoldi法やPRIMA法ではｎ個分しか一致させることができない。すなわち、近似精度の観点からすると、Projection Framework法はＡＷＥ法に比べて劣る。
【００１１】
そこで、本発明の目的は、上記従来のＡＷＥ法の安定性保証の問題を解決し、近似精度がよく且つ安定性が保証された伝達関数の縮約を行う回路解析技術を提供することにある。
【課題を解決するための手段】
【００１２】
本発明に係る回路解析装置の第１の構成は、入力された線形回路の状態方程式の係数行列に基づき、当該線形回路の伝達関数をテイラー（Taylor）展開したときの各次数のモーメントを算出するモーメント演算手段；  並びに、前記各次数のモーメントにより表される展開された前記伝達関数（以下「第１の近似伝達関数」という。）をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第１の縮約手段；を備えた線形回路の伝達関数の縮約を行う回路解析装置において、  前記特性多項式がフルヴィッツ（Hurwitz）多項式であるか否かを判別する安定性判別手段；  前記安定性判別手段が前記特性多項式はフルヴィッツ多項式と判別した場合、前記第１の縮約手段により算出された前記縮約伝達関数の各係数を出力する第１の出力手段；  前記安定性判別手段が前記特性多項式はフルヴィッツ多項式と判別しない場合、前記第１の近似伝達関数を近似する第２の近似伝達関数の特性多項式がフルヴィッツ多項式であることを制約条件、前記第１及び第２の近似伝達関数の間のモーメント空間の距離を目的関数とし、数理計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出する伝達関数安定化手段；  前記第２の近似伝達関数をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第２の縮約手段；  並びに、前記第２の縮約手段により算出された前記縮約伝達関数の各係数を出力する第２の出力手段；を備えたことを特徴とする。
【００１３】
この構成によれば、安定判別手段において、縮約された伝達関数の特性多項式がフルヴィッツ多項式か否かを判定することによって、比較的少ない計算量で縮約された伝達関数の安定性を判別できる。そして、縮約された伝達関数が不安定な場合には、伝達関数安定化手段により、もとの第１の近似伝達関数とのモーメント空間での距離が最小で、且つ特性多項式がフルヴィッツ多項式である第２の近似伝達関数が、数理計画法により計算される。この第２の近似伝達関数は、特性多項式がフルヴィッツ多項式であるため、安定性が保証されており、また、第１の近似伝達関数とのモーメント空間での距離が最小なので、高い精度が保証される。そして、この第２の近似伝達関数をパデ近似により縮約することで、安定性が保証され且つ近似精度が高い縮約された近似伝達関数を求めることができる。
【００１４】
ここで、安定性判別手段は、フルヴィッツ多項式であるか否かの判別を行う手法として、ラウス（Routh）−フルヴィッツの安定判別法（Routh-Hurwitz stability criterion）、ジュリー（Jury）テスト等の各種代数的安定判別法を使用することができる（非特許文献９，１１参照）。
【００１５】
また、「数理計画法」としては、線形計画法や非線形計画法を用いることができる。また、非線形計画法を用いる場合には、ペナルティ法、内点法、逐次２次計画（ＳＱＰ）法、非単調逐次２次計画（ＳＱＲ）法、信頼領域法、主双対内点法等の各種方法を使用することができる（非特許文献１０，１１参照）。
【００１６】
本発明に係る回路解析装置の第２の構成は、前記第１の構成において、前記第１（第２）の縮約手段は、（２ｎ−１）次のモーメント（ｎ＞１）で前記伝達関数を近似した第１（第２）の近似伝達関数を、パデ近似により、分母多項式の次数がｎ、分子多項式の次数が（ｎ−１）の有理多項式で表した縮約伝達関数の分母多項式（特性多項式）及び分子多項式の各係数を算出するものであり、  前記安定性判別手段は、  前記特性多項式の各係数がすべて正値であるか否かを判定する係数判定手段；  式（１）により表されるｎ個の行列式（以下「主座小行列式」という。）Ｈ１，Ｈ２，…，Ｈｎ（但し、ｎは特性方程式の次数）を算出し、それらがすべて正値であるか否かを判定する行列式判定手段；  及び、前記特性多項式の各係数がすべて正値で且つ前記各主座小行列式Ｈ１，Ｈ２，…，Ｈｎがすべて正値の場合に、前記特性多項式がフルヴィッツ多項式であると判別する総合判定手段；を備えていることを特徴とする。
【００１７】
【数１】
2007094736.tif 000003
【００１８】
本発明に係る回路解析装置の第３の構成は、前記第２の構成において、前記伝達関数安定化手段は、前記安定性判別手段が前記特性多項式はフルヴィッツ多項式と判別しない場合、前記特性多項式の各係数がすべて正値で且つ前記各主座小行列式Ｈ１，Ｈ２，…，Ｈｎがすべて正値であることを制約条件、（２ｎ−１）次の前記第１の近似伝達関数のモーメント（式（２））及び（２ｎ−１）次の前記第２の近似伝達関数のモーメント（式（３））に対して式（４）で表される累積二乗誤差Ｏを目的関数とし、数理計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出するものであることを特徴とする。
【００１９】
【数２】
2007094736.tif 000004
【００２０】
【数３】
2007094736.tif 000005
【００２１】
【数４】
2007094736.tif 000006
【００２２】
本発明に係る回路解析装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記伝達関数安定化手段は、前記制約条件に基づき、逐次２次計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出することを特徴とする。
【００２３】
本発明に係る回路解析方法は、入力された線形回路の状態方程式の係数行列に基づき、当該線形回路の伝達関数をテイラー（Taylor）展開したときの各次数のモーメントを算出するモーメント演算ステップ；  並びに、前記各次数のモーメントにより表される展開された前記伝達関数（以下「第１の近似伝達関数」という。）をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第１の縮約ステップ；を有する線形回路の伝達関数の縮約を行う回路解析方法において、  前記特性多項式がフルヴィッツ（Hurwitz）多項式であるか否かを判別する安定性判別ステップ；  前記安定性判別ステップにおいて前記特性多項式はフルヴィッツ多項式であると判別された場合、前記第１の縮約ステップにおいて算出された前記縮約伝達関数の各係数を出力する第１の出力ステップ；  前記安定性判別ステップにおいて前記特性多項式はフルヴィッツ多項式であると判別されなかった場合、前記第１の近似伝達関数を近似する第２の近似伝達関数の特性多項式がフルヴィッツ多項式であることを制約条件、前記第１及び第２の近似伝達関数の間のモーメント空間の距離を目的関数とし、数理計画法により前記目的関数が最小となる前記第２の近似伝達関数の各次数のモーメントを算出する伝達関数安定化ステップ；  前記第２の近似伝達関数をパデ（Pade）近似により有理多項式で表した縮約伝達関数の分母多項式（以下「特性多項式」という。）及び分子多項式の各係数を算出する第２の縮約ステップ；  並びに、前記第２の縮約ステップにおいて算出された前記縮約伝達関数の各係数を出力する第２の出力ステップ；を有することを特徴とする。
【００２４】
本発明に係る回路解析方法のプログラムは、コンピュータに読み込んで実行させることにより、コンピュータを前記第１乃至４の何れか一の構成の回路解析装置として機能させることを特徴とする。
【発明の効果】
【００２５】
以上のように本発明によれば、縮約された伝達関数が不安定な場合には、伝達関数安定化手段により、もとの第１の近似伝達関数とのモーメント空間での距離が最小で、且つ特性多項式がフルヴィッツ多項式である第２の近似伝達関数を算出し、この第２の近似伝達関数をパデ近似により縮約することで、安定性が保証され且つ近似精度が高い縮約された近似伝達関数を求めることができる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００２７】
図２は、本発明の実施例１に係る回路解析装置１の構成を示すブロック図である。回路解析装置１は、回路特性行列記憶手段２、モーメント演算手段３、縮約手段４、安定性判別手段５、出力手段６、伝達関数記憶手段７、及び伝達関数安定化手段８を備えている。
【００２８】
回路特性行列記憶手段２は、解析を行う線形回路の各回路特性行列を記憶する。ここで、「回路特性行列」とは、解析を行う回路の回路定数として回路の状態方程式に現れる各係数行列である。
【００２９】
モーメント演算手段３は、回路特性行列記憶手段２に記憶された各回路特性行列に基づき、当該線形回路の伝達関数をテイラー展開したときの０〜（２ｎ−１）次（ｎ＞１）までの各次数のモーメントを算出する。これらのモーメントにより表される近似された伝達関数を、以下では「近似伝達関数」といい、Ｔ~（ｓ）と記す。
【００３０】
縮約手段４は、近似伝達関数をパデ近似により有理多項式で表した縮約伝達関数の分母多項式（特性多項式）φ（ｓ）及び分子多項式ξ（ｓ）の各係数を算出する。
【００３１】
安定性判別手段５は、特性多項式φ（ｓ）がフルヴィッツ多項式であるか否かを判別する。
【００３２】
出力手段６は、縮約伝達関数の各係数を伝達関数記憶手段７に格納する。
【００３３】
伝達関数安定化手段８は、特性多項式がフルヴィッツ多項式でない場合に、第１近似伝達関数Ｔ~（ｓ）を近似する第２近似伝達関数Ｔ~~（ｓ）の特性多項式がフルヴィッツ多項式であることを制約条件、前記第１近似伝達関数Ｔ~（ｓ）及び第２近似伝達関数Ｔ~~（ｓ）の間のモーメント空間の距離を目的関数Ｏとし、非線形計画法により目的関数Ｏが最小となる第２近似伝達関数Ｔ~~（ｓ）の各次数のモーメントを算出する。
【００３４】
尚、上記各構成ブロックは、ハードウェア的に専用回路で構成してもよいが、プログラム・モジュールとして構成し、コンピュータに当該プログラムを読み込んで実行させることによって各機能ブロックを実現するようにしてもよい。
【００３５】
以上のように構成された本実施例１に係る回路解析装置１において、以下その動作を説明する。
【００３６】
図３は、本発明に係る伝達関数の縮約方法を表すフローチャートである。ここでは、例として、線形回路として、図４に示すような配線の分布定数による等価回路を考える。入力される回路特性行列としては、当該線形回路のキャパシタンス行列Ｃ，コンダクタンス行列Ｇ，電源接続行列Ｂ，及びプロービング行列Ｌが与えられる。各行列は、それぞれ次式（５）〜（８）によって表される。尚、「プロービング行列」とは、所望のノードにおける電圧波形を取り出すために用いられる行列である。
【００３７】
【数５】
2007094736.tif 000007
【００３８】
【数６】
2007094736.tif 000008
【００３９】
【数７】
2007094736.tif 000009
【００４０】
【数８】
2007094736.tif 000010
【００４１】
このとき、線形回路の状態方程式は式（９）により与えられる。ここで、状態変数ベクトルｘは、各ノードにおけるノード電圧であり、式（１０）で表される。また、ｖｓ＝ｖｓ（ｔ）は入力電圧である。
【００４２】
【数９】
2007094736.tif 000011
【００４３】
【数１０】
2007094736.tif 000012
【００４４】
また、波形を観測するノードの電圧を表すプロービング電圧ベクトルｖｏｕｔは、次式（１１）で与えられる。
【００４５】
【数１１】
2007094736.tif 000013
【００４６】
以下では、電源電圧ｖｓとして単一パルスを入力する。すなわち、
【００４７】
【数１２】
2007094736.tif 000014
とする。
【００４８】
（ステップＳ１）伝達関数ベクトルの計算
式（９），（１２）の両辺をラプラス変換すると、
【００４９】
【数１３】
2007094736.tif 000015
となる。ここで、Ｘ（ｓ），Ｖｓ（ｓ），Ｖｏｕｔ（ｓ）は、それぞれ、ｘ（ｔ），ｖｓ（ｔ），ｖｏｕｔ（ｔ）のラプラス変換である。Ｖｓ（ｓ）＝１なので、伝達関数ベクトルは、次式（１５）により求められる。
【００５０】
【数１４】
2007094736.tif 000016
【００５１】
モーメント演算手段３は、まず、式（１５）により、伝達関数ベクトルＴ（ｓ）を算出する。
【００５２】
（ステップＳ２）伝達関数ベクトルのテイラー（Taylor）展開とモーメント・ベクトルの計算
次に、モーメント演算手段３は、式（１５）の伝達関数Ｔ（ｓ）をテイラー展開したときの（２ｎ−１）次のモーメントまでを算出する。伝達関数Ｔ（ｓ）を（２ｎ−１）次のモーメントまでで打ち切ってＴ（ｓ）を近似した伝達関数ベクトルを
【００５３】
【数１５】
2007094736.tif 000017
又はＴ~（ｓ）と記す（以下同様に、数式以外ではティルド（tilde）が付された記号は、その記号の後に「~」を付して表す）。Ｔ~（ｓ）は、次式（１６）により表される。
【００５４】
【数１６】
2007094736.tif 000018
【００５５】
式（１３）より、状態方程式は次式（１７）で表される。
【００５６】
【数１７】
2007094736.tif 000019
【００５７】
式（１７）の両辺のｓの係数を比較することにより、各次数のモーメントｍ０，ｍ１，ｍ２，…，ｍ２ｎ−１が次のように順に求められる。
【００５８】
【数１８】
2007094736.tif 000020
【００５９】
（ステップＳ３）パデ近似による縮約された伝達関数の計算
縮約手段４は、波形観測を行うノードについて、パデ近似による縮約された伝達関数の各係数を次のようにして算出する。
【００６０】
まず、ある一つのノードｉに注目し、当該ノードに対応する近似された伝達関数Ｔｉ~（ｓ）を、式（１６）のＴ~（ｓ）から抽出する。Ｔｉ~（ｓ）は次式（１９）で表される。
【００６１】
【数１９】
2007094736.tif 000021
【００６２】
パデ近似による縮約された伝達関数を求めるため、Ｔｉ~（ｓ）を以下のよう置く。
【００６３】
【数２０】
2007094736.tif 000022
【００６４】
式（２０）の左辺第１段の有利多項式の分母多項式を式（２０）の両辺に掛けると式（２１）が得られる。
【００６５】
【数２１】
2007094736.tif 000023
【００６６】
式（２１）の両辺をｓの係数で比較すると、式（２２），（２３）の連立方程式が得られる。
【００６７】
【数２２】
2007094736.tif 000024
【００６８】
そこで、縮約手段４は、式（２３）から、次式（２４）により係数ａ~１，ａ~２，…，ａ~ｎを算出する。
【００６９】
【数２３】
2007094736.tif 000025
【００７０】
さらに、式（２２）に係数ａ~１，ａ~２，…，ａ~ｎを代入して、係数ｂ~０，ｂ~１，…，ｂ~ｎ−１を算出する。同様の演算を各ノードについて行うことで、パデ近似によって縮約された伝達関数Ｔ~（ｓ）が求められる。
【００７１】
ここで、縮約された伝達関数Ｔ~（ｓ）は、分母多項式（特性多項式）を０と置いた特性方程式φ（ｓ）＝０の根（以下「特性根」という。）の実部が正になるか負になるかによって、安定・不安定が左右される。従来のＡＷＥ法においては、複素平面上における特性根の配置位置が全く考慮されていないため、特性根の一部が複素平面上で右反面に属してしまう可能性がある。これが、伝達関数が不安定な振る舞いを生じる原因である。
【００７２】
そこで、ステップＳ４以降では、ここで算出された伝達関数Ｔ~（ｓ）に関して、まずその安定性を判定し、不安定と判定された場合には、ステップＳ３でパデ近似を行った際の元となった初期モーメントとの差分を最小にし、且つ安定性を保証する新たなモーメントを求める。そして、この新たなモーメントから、もう一度パデ近似を用いて縮約された伝達関数
【００７３】
【数２４】
2007094736.tif 000026
（以下、二重のティルドは、Ｔ~~（ｓ）のように「~~」を付して表す。）を計算する。
【００７４】
（ステップＳ４〜Ｓ６）フルヴィッツの安定判別
安定性判別手段５は、縮約された伝達関数Ｔ~（ｓ）の特性多項式φ（ｓ）について、すべての特性根の実数部分が負、すなわち、フルヴィッツ多項式となっているか否かを用いて判定する。ここで、「フルヴィッツ多項式」とは、連続時間システムにおいて、特性方程式φ（ｓ）＝０の根（特性根）ｓｉがすべて開左半平面にある（すなわちＲｅ［ｓｉ］＜０である）特性多項式φ（ｓ）をいう（非特許文献９参照）。
【００７５】
この判定には、以下のフルヴィッツの安定判別法（又はラウス−フルヴィッツの安定判別法）を使用する。
【００７６】
〔定理〕（フルヴィッツの安定判別法）
特性多項式
【００７７】
【数２５】
2007094736.tif 000027
がフルヴィッツ多項式であるための必要十分条件は、次の（ｉ），（ｉｉ）を同時に満足することである：
（ｉ）総ての係数ａ~１，ａ~２，…，ａ~ｎが正である。
【００７８】
【数２６】
2007094736.tif 000028
（ｉｉ）下式（２７）の行列Ｈの総ての主座小行列式Ｈｉ（ｉ＝１，２，…，ｎ）が総て正（Ｈｉ＞０）である。
【００７９】
【数２７】
2007094736.tif 000029
但し、ａ~ｋの添字ｋが負になったり、ｎを越えた場合にはａ~ｋ＝０とおく。
（定理終わり）
【００８０】
まず、ステップＳ４において、安定性判別手段５は、特性多項式の係数ａ~１，ａ~２，…，ａ~ｎがすべて正か否かを判定する。すべて正であればステップＳ５に移行し、そうでなければ、縮約された伝達関数Ｔ~（ｓ）は不安定なのでステップＳ７に移行する。
【００８１】
ステップＳ５において、安定性判別手段５は、式（２７）の行列Ｈの主座小行列式Ｈｉ（ｉ＝１，２，…，ｎ）を算出する。ここで、主座小行列式Ｈｉ（ｉ＝１，２，…，ｎ）は、下式（２８）のように表される。
【００８２】
【数２８】
2007094736.tif 000030
【００８３】
ステップＳ６において、安定性判別手段５は、すべての主座小行列式Ｈｉ（ｉ＝１，２，…，ｎ）が正か否かを判定する。すべて正であれば、特性多項式φ（ｓ）はフルヴィッツ多項式であり、縮約された伝達関数Ｔ~（ｓ）は安定なので、ステップＳ９で縮約された伝達関数Ｔ~（ｓ）の各係数ａ~１，ａ~２，…，ａ~ｎ，ｂ~０，ｂ~１，…，ｂ~ｎ−１を伝達関数記憶手段７に保存して処理を終了する。
【００８４】
一方、主座小行列式Ｈｉの一部が０以下の場合、縮約された伝達関数Ｔ~（ｓ）は不安定なので、ステップＳ７に移行する。
【００８５】
（ステップＳ７）非線形計画法を用いた伝達関数の安定化
伝達関数安定化手段８は、ステップＳ３で求めた縮約された伝達関数Ｔ~（ｓ）のモーメント｛ｍ０，ｍ１，ｍ２，…，ｍ２ｎ−１｝を初期値とし、
【００８６】
（Ｉ）フルヴィッツの安定判別法における主座小行列式Ｈｉ（ｉ＝１，２，…，ｎ）が正であることを制約条件；
【００８７】
【数２９】
2007094736.tif 000031
（ＩＩ）次式（３０）で表されるＯを最小化すべき目的関数；
【００８８】
【数３０】
2007094736.tif 000032
として、非線形計画法を用いて新たなモーメント｛ｍ~０，ｍ~１，ｍ~２，…，ｍ~２ｎ−１｝を求める。
【００８９】
〔例１〕
例えば、ｎ＝２の場合、
【００９０】
【数３１】
2007094736.tif 000033
がフルヴィッツ多項式になる条件を求めると、
【００９１】
【数３２】
2007094736.tif 000034
一方、
【００９２】
【数３３】
2007094736.tif 000035
であるから、制約条件と目的関数は以下のようになる。
【００９３】
【数３４】
2007094736.tif 000036
（例終わり）
【００９４】
尚、非線形計画法としては、逐次２次計画（ＳＱＰ）法、非単調逐次２次計画（ＳＱＲ）法などの各種周知の方法を使用することができる（非特許文献１０，１１参照）。
【００９５】
（ステップＳ８）パデ近似による伝達関数の再計算
縮約手段４は、ステップＳ７で求められたモーメント｛ｍ~０，ｍ~１，ｍ~２，…，ｍ~２ｎ−１｝から、再びステップＳ３と同様の演算を行い、パデ近似を用いて安定で縮約された伝達関数Ｔ~~（ｓ）を計算し、各係数ａ~１，ａ~２，…，ａ~ｎ，ｂ~０，ｂ~１，…，ｂ~ｎ−１を求める。そして、ステップＳ９において、各係数ａ~１，ａ~２，…，ａ~ｎ，ｂ~０，ｂ~１，…，ｂ~ｎ−１を伝達関数記憶手段７に保存し処理を終了する。
【００９６】
〔例２〕
１５０ｎｍプロセス上に実装したマイクロ・プロセッサのデータ・パス系配線に関するレイアウト設計データの中で、不安定になった５種類の回路に関して、本実施例に示した回路解析方法を用いて安定化の処理を行った。図１に示した不安定な振る舞いに対応する等価回路を図５に示す。２２０セグメントの回路（（表１）の回路１）であり、端子Ａと端子Ｂとの間が不安定となる。
【００９７】
評価に用いた等価回路では、２６．８Ωの抵抗と０．８２ｆＦの容量で配線分割の最小単位である１セグメントを表現している。非線形計画法のアルゴリズムとしては、Schittowskiらが提案し、現在最先端の技法とされている逐次２次計画法（sequential quadratic programming method）を採用した（非特許文献１０，１２参照）。また、縮約後の分母多項式の最大次数としては２次を設定している。安定化した後の伝達関数に関して、５０％遅延時間における精度評価を行った。比較の基準は縮約前の伝達関数の応答である。精度の計算式は、次式（３２）を用いている。
【００９８】
【数３５】
2007094736.tif 000037
【００９９】
評価結果を（表１）に示す。平均精度は約０．０２％であり、従来からＳＴＡ（Static Time Analysis）や論理合成ツールで使用されているElmore法（非特許文献１参照）による遅延計算の精度（上記の精度計算式において縮約後の遅延時間の代わりにElmore法による遅延計算時間を代入）の平均精度である約３２％と比較すると、ＶＬＳＩ配線遅延計算としては十分良好な精度を実現できることが分かる。
（例終わり）
【０１００】
【表１】
2007094736.tif 000038
【図面の簡単な説明】
【０１０１】
【図１】１０ＭＨｚのパルス入力時の伝達関数の時間応答を解析した例である。
【図２】本発明の実施例１に係る回路解析装置の構成を示すブロック図である。
【図３】本発明に係る伝達関数の縮約方法を表すフローチャートである。
【図４】配線の分布定数による等価回路の例である。
【図５】図１に示した不安定な振る舞いに対応する等価回路である。
【符号の説明】
【０１０２】
１  回路解析装置
２  回路特性行列記憶手段
３  モーメント演算手段
４  縮約手段
５  安定性判別手段
６  出力手段
７  伝達関数記憶手段
８  伝達関数安定化手段
【図１】
2007094736.tif 000043
【図２】
2007094736.tif 000044
【図３】
2007094736.tif 000045
【図４】
2007094736.tif 000046
【図５】
2007094736.tif 000047