【事件の表示】
　特許第２７５２５９７号「消費電力の推定方法，消費電力の推定装置，配置配線の決定方法及び配置配線設計装置」の請求項１ないし４、９、１１に係る特許に対する特許異議の申立てについて、次のとおり決定する。
【結論】
　訂正を認める。
　特許第２７５２５９７号の請求項１ないし３に係る特許を維持する。
【理由】
１．手続の経緯
　本件特許第２７５２５９７号の請求項１〜１２に係る発明についての出願は、平成７年４月１３日に出願され、平成１０年２月２７日に設定登録され、その後、特許異議申立人三浦俊郎により請求項１〜４、９及び１１に係る発明について特許異議の申立てがなされ、取消理由通知がなされ、その指定期間内である平成１１年４月２７日に訂正請求がなされたものである。
２．訂正の適否についての判断
　ア．訂正の内容
▲１▼．訂正事項ａ
　特許請求の範囲の請求項１を、訂正前の請求項５の発明特定事項を追加するように訂正し、請求項６〜８を、請求項２の択一的な引用を削除した上で請求項１の引用に代えその内容を組み込んで独立形式に変更すると共に、各請求項の項番号６〜８を下記の訂正事項ｃにおける請求項４、５の削除に伴いそれぞれ項番号４〜６に繰り上げる。
　また、下記の訂正事項ｃにおける請求項４、５、９、１１の削除に伴い、請求項１０の項番号を７に、請求項１２の項番号を８にそれぞれ繰り上げる。
▲２▼．訂正事項ｂ
　特許請求の範囲の請求項１、４〜７中に、各ステップの時系列を明確にする事項を追加する。
▲３▼．訂正事項ｃ
　特許請求の範囲の請求項４、５、９、１１を削除する。
▲４▼．訂正事項ｄ
　特許明細書の段落【００４８】の「上記式（３）を一般化すると、各入力信号ＩＰｉが変化する確率ＰｖＩｉが与えられているとすれば、一般に、出力信号が変化する確率ＰｖＯｊは、」を、「一般にある要素にｎ個の入力信号があったとき、各入力信号ＩＰｉが変化する確率ＰｖＩｉが与えられているとすれば、出力信号が変化する確率ＰｖＯｊは、」と訂正する。
▲５▼．訂正事項ｅ
　特許明細書の段落【００５４】の第３文中の「加算する」を、「掛ける」と訂正する。
▲６▼．訂正事項ｆ
　特許明細書の段落【００７２】の第１文中の「積で与えられる。」を、「積によって近似することができる。」と訂正する。
▲７▼．訂正事項ｇ
イ．訂正の目的の適否、新規事項の有無、および拡張・変更の存否
　上記訂正事項ａにより訂正された請求項１は、訂正前の請求項１に訂正前の請求項５の発明特定事項を追加し、訂正された請求項４〜６は、実質的に、訂正前の請求項２の択一的な引用を削除するとともに、項番号を単に繰り上げるものであり、訂正事項ｃは、請求項の削除であるから、これらの訂正事項は、特許請求の範囲の減縮に相当する。
　訂正事項ｂは、各ステップの時系列関係を明確にするものであり、訂正事項ｄは、式３と式４との関係を明瞭にするものであるから、これらの訂正事項は、明瞭でない記載の釈明に相当する。
　訂正事項ｅ、ｆ及びｇは、式５ないし１１に関する説明の誤りを正すものであるから、誤記の訂正に相当する。
　そして、上記各訂正事項は、いずれも願書に添付した明細書又は図面に記載した事項の範囲内の訂正であり、実質上特許請求の範囲を拡張し又は変更するものでもない。
　なお、訂正事項ａにより訂正された請求項７、８は、請求項の削除に伴い項番号を繰り上げたにすぎず、実質的な訂正ではない。
ウ．独立特許要件の判断
（本件発明）
　本件特許第２７５２５９７号の請求項１〜６に係る発明は、訂正された特許明細書及び図面の記載からみて、その特許請求の範囲の請求項１〜６に記載された事項により特定される次のとおりのものと認める。
　【請求項１】少なくとも１つの要素と、上記要素に接続され少なくとも１つの入力信号及び少なくとも１つの出力信号をそれぞれ伝達するための少なくとも２つの信号線とを備えた電気回路の消費電力を推定する方法であって、上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、上記第１のステップの後に、上記入力信号の変化確率を与える第２のステップと、上記式を利用して、上記第２のステップで与えられた変化確率を有する入力信号が上記電気回路に入力されたときの各信号における信号の変化確率を求める第３のステップと、上記第３のステップにおいて与えられた上記各信号線の変化確率と各信号線の負荷との積を総和して、電気回路の消費電力を推定する第４のステップとを備え、上記第２のステップでは、上記入力信号が複数ビットのデータからなる信号である場合に、上記入力信号の分布状態と１クロック信号毎の入力信号のデータ変化量の上限とを指定して、１クロック信号入力後の各ビット値の変化確率を求めることを特徴とする消費電力の推定方法。
　【請求項２】請求項１記載の消費電力の推定方法において、上記要素は、互いに直列に接続される少なくとも２つの要素からなり、上記第３のステップでは、電気回路の入力側に配置された要素に接続される各信号線の入力信号の変化確率と出力信号の変化確率とから順次算出していくことを特徴とする消費電力の推定方法。
　【請求項３】請求項１又は２記載の消費電力の推定方法において、上記第１ステップでは、上記各要素の入力信号と出力信号との真理値表を用いて上記式を求めることを特徴とする消費電力の推定方法。
　【請求項４】少なくとも１つの要素と、上記要素に接続され少なくとも１つの入力信号及び少なくとも１つの出力信号をそれぞれ伝達するための少なくとも２つの信号線とを備えた電気回路の消費電力を推定する方法であって、上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、上記第１のステップの後に、上記入力信号の変化確率を与える第２のステップと、上記式を利用して、上記第２のステップで与えられた変化確率を有する入力信号が上記電気回路に入力されたときの各信号における信号の変化確率を求める第３のステップと、上記第３のステップにおいて与えられた上記各信号線の変化確率と各信号線の負荷との積を総和して、電気回路の消費電力を推定する第４のステップとを備え、上記第２ステップでは、上記入力信号のデータ変化量の上限が大きい場合に、上記各ビット値の変化する確率Ｐｖｒを下記式
　ＰＶｒ−２×Ｐ×（１）×Ｐ（０）
（ただし、Ｐ（１），Ｐ（０）は、各ビット値が“１”，“０”である確率）により求めることを特徴とする消費電力の推定方法。
　【請求項５】少なくとも１つの要素と、上記要素に接続され少なくとも１つの入力信号及び少なくとも１つの出力信号をそれぞれ伝達するための少なくとも２つの信号線とを備えた電気回路の消費電力を推定する方法であって、上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、上記第１のステップの後に、上記入力信号の変化確率を与える第２のステップと、上記式を利用して、上記第２のステップで与えられた変化確率を有する入力信号が上記電気回路に入力されたときの各信号における信号の変化確率を求める第３のステップと、上記第３のステップにおいて与えられた上記各信号線の変化確率と各信号線の負荷との積を総和して、電気回路の消費電力を推定する第４のステップとを備え、上記第２ステップでは、上記入力信号のデータ変換量の上限が小さい場合に、入力信号の分布領域を変数の所定幅毎にｎ個の領域に区画し、各領域１（ｉ＝１〜ｎ）ごとに、各ビット値が“１”〜１クロック信号入力後に“０”に変化する確率Ｐ１ｉ（０）とビット値が“０”から１クロック信号入力後に“１”に変化する確率ＰＯｉ（１）とを求め、各ビット値の変化する確率Ｐｖｒを下記式
により求めることを特徴とする消費電力の推定方法。
　【請求項６】少なくとも１つの要素と、上記要素に接続され少なくとも１つの入力信号及び少なくとも１つの出力信号をそれぞれ伝達するための少なくとも２つの信号線とを備えた電気回路の消費電力を推定する方法であって、上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、上記第１のステップの後に、上記入力信号の変化確率を与える第２のステップと、上記式を利用して、上記第２のステップで与えられた変化確率を有する入力信号が上記電気回路に入力されたときの各信号における信号の変化確率を求める第３のステップと、上記第３のステップにおいて与えられた上記各信号線の変化確率と各信号線の負荷との積を総和して、電気回路の消費電力を推定する第４のステップとを備え、上記第２ステップでは、入力信号がランダムな論理値を有するデータからなる信号である場合には、ビット値が変化する確率を１／２とすることを特徴とする消費電力の推定方法。
（引用刊行物）
　訂正明細書の請求項１〜６に係る発明（以下、「本件請求項１〜６に係る発明」という。）に対して、当審が通知した取消理由で引用した刊行物１（Ｔｒａｎｓｉｔｉｏｎ　Ｄｅｎｓｉｔｙ，Ａ　Ｓｔｏｃｈａｓｔｉｃ　Ｍｅａｓｕｒｅｏｆ　Ａｃｔｉｖｉｔｙ　ｉｎ　Ｄｉｇｉｔａｌ　Ｃｉｒｃｕｉｔｓ（１９９１ＡＣＭ　０−８９７９１−３９５−７））には、ＣＭＯＳゲートにおいて消費される平均電力を、回路の各ノードにおけるスイッチングする平均割合（ＴＤ）により算出すること（第６４４頁右上欄４行ないし第２５行参照）、出力信号の変化確率は、入力信号の変化に応じて出力信号が変化する確率と入力信号の変化確率との積によって表され、各信号線の変化確率と容量Ｃとの積に基づいて電気回路の消費電力を推定すること（第６４７頁左欄１１行ないし３７行参照）、ＢＤＤを使用して、入力信号の変化に応じて出力信号が変化する確率を算出すること（第６４９頁左欄１行ないし右欄１４行）が記載され、
　同じく当審が通知した取消理由通知で引用した刊行物２（Ｃｉｒｃｕｉｔ　Ａｃｔｉｖｉｔｙ　Ｂａｓｅｄ　Ｌｏｇｉｃ　Ｓｙｎｔｈｅｓｉｓ　ｆｏｒ　Ｌｏｗ　Ｐｏｗｅｒ　Ｒｅｌｉａｂｌｅ　Ｏｐｅｒａｔｉｏｎｓ（１９９３　ＩＥＥＥ））には、回路を構成する各回路要素のノードにおける信号変化確率により、回路全体のノードにおける信号変化確率を算出すること、入力の信号変化確率に基づいて各回路要素の出力の信号変化確率を回路の左から右へと順次算出して、最終的に回路の出力での信号変化確率を算出することが記載されている（第５０６頁左欄２４行ないし、２８行、及びＦｉｇ３参照）。
（対比・判断）
　本件請求項１〜６に係る発明と、上記刊行物１、２に記載された各発明とを対比すると、刊行物１に記載された発明は、入力信号の変化に応じて出力信号が変化する確率と入力信号の変化確率との積により出力信号の変化確率を求め、出力信号の変化確率と出力信号線の容量の積により、消費電力を推定すること、及び、ＢＤＤを使用して入力信号の変化に応じて出力信号が変化する確率を算出することを開示するにすぎず、また、刊行物２に記載された発明は、回路の入力側から順次に出力側の信号変化確率を求めること、及び、回路の入出力における信号の変化確率から回路全体の信号変化確率を算出することを開示するにすぎず、
　本件請求項１〜３に係る発明が共通に要件とする「上記第２のステップでは、上記入力信号が複数ビットのデータからなる信号である場合に、上記入力信号の分布状態と１クロック信号毎の入力信号のデータ変化量の上限を指定して、１クロック信号入力後の各ビット値の変化確率を求めること」、
　本件請求項４が要件とする「上記第２ステップでは、上記入力信号のデータ変化量の上限が大きい場合に、上記各ビット値の変化する確率Ｐｖｒを下記式
　Ｐｖｒ−２×Ｐ×（１）×Ｐ（０）
（ただし、Ｐ（１），Ｐ（０）は、各ビット値が“１”，“０”である確率）により求めること」、
　本件請求項５が要件とする「上記第２ステップでは、上記入力信号のデータ変換量の上限が小さい場合に、入力信号の分布領域を変数の所定幅毎にｎ個の領域に区画し、各領域１（ｉ＝１〜ｎ）ごとに、各ビット値が“１”〜１クロック信号入力後に“０”に変化する確率Ｐ１ｉ（０）とビット値が“０”から１クロック信号入力後に“１”に変化する確率Ｐ０ｉ（１）とを求め、各ビット値の変する確率Ｐｖｒを下記式
により求めること」、
　及び本件請求項６が要件とする「上記第２ステップでは、入力信号がランダムな論理値を有するデータからなる信号である場合には、ビット値が変化する確率を１／２とすること」については、開示も示唆もしない。
　そして、本件請求項１〜６に係る発明は、上記構成を備えることにより、明細書に記載された格別の効果を奏するものである。
　したがって、本件請求項１〜６に係る発明は、上記刊行物１、及び２に記載された発明と同一であるとも、また、これらの発明から当業者が容易に発明をすることができたものともすることはできない。
　したがって、本件請求項１〜６係る発明は、特許出願の際独立して特許を受けることができるものである。
（むすび）
　以上のとおりであるから、上記訂正は、特許法第１２０条の４第３項において準用する第１２６条第２−４項の規定に適合するので、当該訂正を認める。
３．特許異議の申立てについて
ア．申立ての理由の概要
　特許異議申立人三浦俊郎は、証拠として甲第１号証（上記刊行物１）、甲第２号証（上記刊行物２）を提出し、本件請求項１〜４、９及び１１に係る各発明は、甲第１号証及び甲第２号証に記載された発明と同一、又は同記載の各発明に基いて当業者が容易に発明をすることができたものであり、特許法第２９条第１項第３号、又は同第２９条第２項の規定に違反してなされたものであるから、特許を取り消すべき旨主張している。
イ．判断
　異議申立ての対象となった本件請求項１〜３（訂正前の請求項１〜３に対応）に係る発明は、上記２．ウで示したように、取消理由通知で示した刊行物に記載された発明と同一であるとも、それらから容易に発明をすることができたものともすることはできない。
　また、他に本件請求項１〜３にかかる特許を取り消すべき理由を発見しない。
　なお、異議申立ての対象となった訂正前の請求項４、９及び１１は、訂正により削除された。
ウ．むすび
　　したがって、特許異議申立ての理由及び証拠　によっては、本件請求項１〜３（訂正前の請求項１〜３に対応）に係る発明の特許を取り消すことはできない。
　　よって、結論のとおり決定する。
【異議決定日】
平成１１年７月１５日（１９９９．７．１５）
【訂正の要旨】
▲１▼．訂正事項ａ
　特許請求の範囲の請求項１を、訂正前の請求項５の発明特定事項を追加するように訂正し、請求項６〜８を、請求項２の択一的な引用を削除した上で請求項１の引用に代えその内容を組み込んで独立形式に変更すると共に、各請求項の項番号６〜８を下記の訂正事項ｃにおける請求項４、５の削除に伴いそれぞれ項番号４〜６に繰り上げる。
　また、下記の訂正事項ｃにおける請求項４、５、９、１１の削除に伴い、請求項１０の項番号を７に、請求項１２の項番号を８にそれぞれ繰り上げる。
▲２▼．訂正事項ｂ
　特許請求の範囲の請求項１、４〜７中に、各ステップの時系列を明確にする事項を追加する。
▲３▼．訂正事項ｃ
　特許請求の範囲の請求項４、５、９、１１を削除する。
▲４▼．訂正事項ｄ
　特許明細書の段落【００４８】の「上記式（３）を一般化すると、各入力信号ＩＰｉが変化する確率ＰｖＩｉが与えられているとすれば、一般に、出力信号が変化する確率ＰｖＯｊは、」を、「一般に、ある要素にｎ個の入力信号があったとき、各入力信号ＩＰｉが変化する確率ＰｖＩｉが与えられているとすれば、出力信号が変化する確率ＰｖＯｊは、」と訂正する。
▲５▼．訂正事項ｅ
　　特許明細書の段落【００５４】の第３文中の「加算する」を、「掛ける」と訂正する。
▲６▼．訂正事項ｆ
　特許明細書の段落【００７２】の第１文中の「積で与えられる。」を、「積によって近似することができる。」と訂正する。
▲７▼．訂正事項ｇ
　特許明細書の段落【００７２】の式（１１）に
（５４）【発明の名称】
消費電力の推定方法，消費電力の推定装置，配置配線の決定方法及び配置配線設計装置
（５７）【特許請求の範囲】
　　【請求項１】　少なくとも１つの要素と、上記要素に接続され少なくとも１つの入力信号及び少なくとも１つの出力信号をそれぞれ伝達するための少なくとも２つの信号線とを備えた電気回路の消費電力を推定する方法であって、
　上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号の変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、
　
上記第１のステップの後に、
　上記式を使用して、
上記第２のステップで与えられた
　
上記第３のステップにおいて与えられた
　上記第２のステップでは、上記入力信号が複数ビットのデータからなる信号である場合に、上記入力信号の分布状態と１クロック信号毎の入力信号のデータ変化量の上限とを指定して、１クロック信号入力後の各ビット値の変化確率を求めることを特徴とする消費電力の推定方法。
　　【請求項２】　請求項１記載の消費電力の推定方法において、
　上記要素は、互いに直列に接続される少なくとも２つの要素からなり、
　上記第３のステップでは、電気回路の入力側に配置された要素に接続される各信号線の入力信号の変化確率と出力信号の変化確率とから順次算出していくことを特徴とする消費電力の推定方法。
　　【請求項３】　請求項１又は２記載の消費電力の推定方法において、
　上記第１のステップでは、上記各要素の入力信号と出力信号との真理値表を用いて上記式を求めることを特徴とする消費電力の推定方法。
　　【請求項
４
　上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号の変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、
　
上記第１のステップの後に、
　上記式を使用して、
上記第２のステップで与えられた
　
上記第３のステップにおいて与えられた
　上記第２のステップでは、上記入力信号のデータ変化量の上限が大きい場合に、上記各ビット値の変化する確率Ｐｖｒを下記式
　Ｐｖｒ＝２×Ｐ（１）×Ｐ（０）
（ただし、Ｐ（１），Ｐ（０）は、各ビット値が“１”，“０”である確率）により求めることを特徴とする消費電力の推定方法。
　　【請求項
５
　上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号の変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、
　
上記第１のステップの後に、
　上記式を使用して、
上記第２のステップで与えられた
　
上記第３のステップにおいて与えられた
　上記第２のステップでは、上記入力信号のデータ変化量の上限が小さい場合に、入力信号の分布領域を変数の所定幅毎にｎ個の領域に区画し、各領域ｉ（ｉ＝１〜ｎ）ごとに、各ビット値が“１”から１クロック信号入力後に”０”に変化する確率Ｐ１ｉ（０）とビット値が“０”から１クロック信号入力後に“１”に変化する確率Ｐ０ｉ（１）とを求め、各ビット値の変化する確率Ｐｖｒを下記式
により求めることを特徴とする消費電力の推定方法。
　　【請求項
６
　上記少なくとも１つの要素への上記入力信号の変化に応じて出力信号が変化する確率と上記入力信号の変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、
　
上記第１のステップの後に、
　上記式を使用して、
上記第２のステップで与えられた
た
　
上記第３のステップにおいて与えられた
　上記第２のステップでは、入力信号がランダムな論理値を有するデータからなる信号である場合には、ビット値が変化する確率を１／２とすることを特徴とする消費電力の推定方法。
　　【請求項
７
　上記各要素への入力信号の変化に応じて当該要素からの出力信号が変化する確率と上記入力信号の変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を求める第１のステップと、
　
上記第１のステップの後に、
　上記式を使用して、
上記第２のステップで与えられた
　
上記第３のステップの後に、
　変化確率の高い信号線の負荷を下げることで上記第４のステップで推定される消費電力を抑制するように配置配線を決定する第５のステップとを備えたことを特徴とする配置配線の決定方法。
　　【請求項
８
　上記各要素への入力信号の変化に応じて当該要素からの出力信号が変化する確率と上記入力信号の変化確率との積に基づき、上記出力信号の変化確率を入力信号の変化確率の関数として表す式を予め記憶する記憶手段と、
　上記入力信号の変化確率を設定する変化確率設定手段と、
　上記記憶手段に記憶される式を使用して、上記変化確率設定手段で設定される入力信号の変化確率に対する各信号線の変化確率を求め、上記各信号線の変化確率と各信号線の負荷との積を総和して、電気回路の消費電力を推定演算する推定演算手段と、
　該推定演算手段の演算結果を用いて、上記変化確率の高い信号線の負荷を下げることで消費電力を抑制するように配置配線を決定する配置配線決定手段とを備えたことを特徴とする配置配線の設計装置。
【発明の詳細な説明】
　　【０００１】
　　【産業上の利用分野】
　本発明は、ＣＭＯＳ・ＬＳＩ等の電気回路に配置される各要素の配置配線を設計するのに利用される消費電力の推定方法，消費電力の推定装置，配置配線の決定方法及び配置配線の設計装置に係り、特に消費電力の推定の簡易，迅速化対策に関する。
　　【０００２】
　　【従来の技術】
　近年、半導体集積回路等の高密度化に伴い、回路内に配置される要素数は飛躍的に増大しており、各要素をどのように配置しどのように配線するかは、重要な課題となっている。すなわち、同じ数の要素数を同じ数の信号線で接続しても、配置配線の相違によって消費電力に差が生じ、消費電力の高い場合には、電力の無駄を生じたり、発熱をどのように外部に放出するか等の問題が生じる。
　　【０００３】
　そこで、ある回路の消費電力を予め正確に推定することができれば、この推定結果を基に最適な配置配線の設計を行うことが容易となる。かかる消費電力の推定方法として、例えば刊行物「ＶＬＳＩの設計Ｉ：岩波講座マイクロエレクトロニクスシリーズ（岩波書店）」に開示されるように、回路の多点間を接続する信号線の近似的な仮想配線長を求め、この仮想配線長に基づき評価関数を設定し、繰り返し改善法によって、目的関数を最小化する方法が知られている。すなわち、配線の断面積をほぼ一定とすれば配線の負荷は配線の長さに比例するので、仮想配線長によって消費電力や信号の遅延等を総合的に評価し得るからである。
　　【０００４】
　また、例えば特開平２−１７１８６１号公報に開示されるごとく、回路に所定のテストパターンを与え、論理シミュレータ等を用いて各信号線のスイッチ回数を求め、上記信号線の配線容量とスイッチ回数との積の総和を求めることで回路の消費電力を推定しようとするものが知られている。
　　【０００５】
　　【発明が解決しようとする課題】
　しかしながら、上記刊行物に記載の消費電力の推定方法のように、単に近似的な配線長だけを考慮しても、消費電力の正確な値を見積もることは困難である。
　すなわち、同じ総配線長を有する回路であっても、ある使用期間内に、各信号線のうち長い信号線のスイッチング回数が多い回路では、長い信号線のスイッチング回数が少ない回路よりも消費電力が大きくなる。したがって、単に配線長を考慮して消費電力を推定しただけでは、消費電力の推定結果に相当の誤差が生じることになる。
　　【０００６】
　一方、上記公報の方法は、信号が切換わるときに特に大きな電流が流れることを利用する方法であり、このようにスイッチ回数を考慮することで消費電力の推定精度を高めることができる。しかるに、論理シミュレーションを行うにはその回路に適したテストパターンをも用いる必要があり、このテストパターンを作成するために多大の労力が費やされている。また、論理シミュレーションの実行に際しても膨大な時間を要するという問題がある。
　　【０００７】
　本発明は斯かる点に鑑みてなされたものであり、以下の目的を有する。
　　【０００８】
　第１の目的は、テストパターンを用いた論理シミュレーションによることなく、簡易かつ迅速に、かつ比較的高精度で電気回路の消費電力を推定しうる方法を提供することにある。
　　【０００９】
　第２の目的は、上記第２の目的に加えて、電気回路の消費電力を最小にするように電気回路の配置配線を決定する方法を提供することにある。
　　【００１０】
　第３の目的は、テストパターンを用いた論理シミュレーションにを行うことなく、迅速かつ比較的高精度で電気回路の消費電力を推定しうる装置を低コストで提供
するに加えて、
　　【００１１】
　　　【課題を解決するための手段】
　本
は、出
ようにしている。
　　【００１２】
　請
１
上記第１のステップの後に、
上記第２のステップで与えられた
た
上記第３のステップにおいて与えられた
　　【００１３】
　請求項
２が
　　【００１４】
　請求項３が講じた手段は、請求項１又は２において、上記第１のステップでは、上記各要素の入力信号と出力信号との真理値表を用いて上記式を求める方法である。
　　【００１５】
　請求項
４
上記第１のステップの後に、
上記第２のステップで与えられた
た
上記第３のステップにおいて与えられた
　Ｐｖｒ＝２×Ｐ（１）×Ｐ（０）
（ただし、Ｐ（１），Ｐ（０）は、各ビット値が“１”“０”である確率）により求める方法である。
　　【００１６】
　請求項
５
上記第１のステップの後に、
上記第２のステップで与えられた
た
上記第３のステップにおいて与えられた
により求める方法である。
　　【００１７】
　請求項
６
上記第１のステップの後に、
上記第２のステップで与えられた
た
上記第３のステップにおいて与えられた
　　【００１８】
　請
７
上記第１のステップの後に、
上記第２のステップで与えられた
上記第３のステップの後に、
　　【００１９】
　請
項８
　　【００２０】
　　【作用】
　請求項１では、入力信号の変化確率と出力信号の変化確率との間の式を利用して、ある要素への入力信号の変化確率が与えられると、当該要素からの出力信号を伝達する各信号線における信号の変化確率が求められる。一般的に、トランジスタを配置した電気回路では、各信号線が容量をもっており、信号のオン・オフの切換わりによって消費される電力が最も大きい。したがって、信号が変化する頻度を考慮した正確な消費電力の推定が行われる。すなわち、テストパターンを用いた論理シミュレーションを実行しなくても、迅速，簡易かつ比較的高精度で消費電力の推定が行われる。
しかも、
　　【００２１】
　請求項２では、第３のステップで、入力側に配置された第１の要素に対する入力信号の変化確率を変数として当該第１の要素の出力信号の変化確率が求められる。次に、上記第１の要素から出力された信号を入力信号とする第２の要素について、上記第１の要素からの出力信号を第２の要素への入力信号とし、すでに求められているこの入力信号の変化確率に基づき第２の要素の出力信号の変化確率が求められる。そして、順次全ての要素に接続される信号線における信号の変化確率が求められることになる。
　　【００２２】
　請求項３では、各要素の真理値表から各信号線における信号の変化確率が容易かつ確実に求められる。
　　【００２３】
　請求項
４
　　【００２４】
　請求項
５
　　【００２５】
　請求項
６
　　【００２６】
　請求項
７
　　【００２７】
　請求項
８
それに加えて、
　　【００２８】
　　【実施例】
　以下、本発明の実施例について、図面に基づき説明する。
　　【００２９】
　　（第１実施例）
　図１は第１実施例に係るＬＳＩ設計装置の一部の構成を示すブロック図である。図１に示すように、ＬＳＩ設計装置は、セルライブラリ１１，ネットリスト部１２，ネット信号統計情報部１３等を内蔵する記憶手段としての記憶装置１と、該記憶装置１の記憶情報に基づいて回路の消費電力を推定演算する消費電力推定演算手段としての消費電力解析システム２と、該消費電力解析システム２で推定された回路の消費電力に基づき最適な配置配線を決定する配置配線決定手段としての計算機３と、解析，演算結果を表示する表示装置４とを備えている。上記記憶装置１及び消費電力解析システム２により本発明にいう消費電力推定装置が構成されている。
　　【００３０】
　ここで、上記セルライブラリ１１には、ピン情報，各要素の入出力信号間の真理値表，各信号線における信号の変化確率，ピンのデータ，コントロールの区別等が記憶されている。図３は、セルライブラリ１１に登録されているある要素の入出力信号の真理値表及び各ピン間における信号の変化確率の例を示し、図４はネット信号統計情報部１３の記憶内容の例を示す。ただし、これらは、図５に示すように、要素４１に、各々入力信号ＩＰ１，ＩＰ２が入力される２つの入力端子４２ａ，４２ｂと、制御信号ＱＰ１が入力される１つの制御入力端子４３と、各々出力信号ＯＰ１，ＯＰ２が出力される２つの出力端子４４ａ，４４ｂとが設けられている電気回路についての例である。
　　【００３１】
　また、図２は上記ＬＳＩ設計装置による最適配置配線の決定手順を示すフローチャートである。まず、ステップＳＴ１で、セルライブラリ１１，ネット情報部１２等の記憶内容に基づいて、入力信号の変化確率を変数とし出力信号の変化確率を入力信号の変化確率の関数とする式を算出し、ステップＳＴ２で電気回路への入力信号の変化確率を与え、ステップＳＴ３で各信号線における信号の変化確率を算出し、ステップＳＴ４で、消費電力の推定演算を行った後、ステップＳＴ５で消費電力をも考慮して最適な配置配線を決定する。
　　【００３２】
　次に、上記フローチャートの各ステップにおける具体的な処理について、詳細に説明する。ここで、処理対象となる電気回路として、上記図３に示すような電気回路をさらに一般化して、入力信号ＩＰｉと出力信号ＯＰｊとを有する電気回路を想定する。
　　【００３３】
　まず、ステップＳＴ１の式を計算するステップにおける処理について説明する。各要素に対して、電気回路の入力信号の変化確率と出力信号の変化確率との間の式を計算するが、この式は、以下の方法で求める。例えば要素のある入力信号ＩＰｉとある出力信号ＯＰｊとの組み合わせ（つまり起こりうる事象）は下記表１に示す入力信号一出力信号間の論理の真理値表によって記述され、各事象が生じる確率Ｐ１〜Ｐ４とする。
　　【００３４】
　【表１】
　　【００３５】
　上記入力信号一出力信号間の論理の真理値表に基づき、入力信号が“１”である時に出力信号が“１”となる確率Ｐ１、同様に、入力信号が“０”で出力信号が“１”となる確率Ｐ２、入力信号が“１”で出力信号が“０”となる確率Ｐ３、入力信号が“０”で出力信号が“０”となる確率Ｐ４をそれぞれ求める。
　　【００３６】
　この時、入力信号が“１”から“０”に変化した時に出力信号が変化する確率は、下記式（１）
　Ｐｖ０１−０＝Ｐ１×Ｐ４＋Ｐ２×Ｐ３　　　　　　　　　　　　　　　（１）
で表される。同様に、入力信号が“０”から“１”に変化した時に出力信号が変化する確率は、下記式（２）
　Ｐｖ００−１＝Ｐ４×Ｐ１＋Ｐ３×Ｐ２　　　　　　　　　　　　　　　（２）
で表される。すなわち、入力信号ＩＰｉが変化した時に出力信号が変化する確率Ｐｖ０ｉ−ｊは、下記式（３）
　Ｐｖ０ｉ−ｊ＝２×（Ｐ４×Ｐ１＋Ｐ３×Ｐ２）　　　　　　　　　　　（３）
で与えられる。
　　【００３７】
　
一般に、ある要素にｎ個の入力信号があったとき、
で与えられる。ただし、上記式（４）中の文字Σは、当該要素への入力信号の数ｎに対して、ｉ＝１〜ｎについて加算を行なうことを意味する。上記式（４）は、各入力信号ＩＰｉの変化に応じて各出力信号ＯＰｊが変化する確率Ｐｖ０ｉ−ｊを真理値表から求め、この変化確率Ｐｖ０１−ｊと各入力信号ＩＰｉの変化確率ＰＩｉとの積を各入力信号線について加算したものである。すなわち、出力信号の変化確率を入力信号の変化確率の関数として表す式である。
　　【００３８】
　なお、現実に消費電力を推定する際には、信号の変化確率から信号の変化回数に換算しておくほうが計算上都合がよい。上記式（４）から容易に換算し得るように、各入力信号ＩＰｉが変化する回数ＣｖＩｉが与えられているとすれば、一般に、出力信号ＯＰｊが変化する回数Ｃｖ０ｊは、下記式（５）
で与えられる。したがって、実際の計算では、入力信号の変化回数ＣｖＩｉを変数とし出力変化回数Ｃｖ０ｊをその関数とする式（５）を使用するのが好ましい。
　　【００３９】
　ここで、上記表１に示す真理値表を有する電気回路（図５参照）に対する計算例を説明する。まず、入力信号ＩＰ１の変化に応じて出力信号ＯＰ１が変化する確率Ｐｖ０１−１を計算する。図３からわかるように、入力信号ＩＰ１が“１”で出力信号ＯＰ１が“１”である確率Ｐ１は「１／４」であり、入力信号ＩＰ１が“０で出力信号ＯＰ１が“１”である確率Ｐ２は「１／８」であり、入力信号ＩＰ１が“１”で出力信号ＯＰ１が“０”である確率Ｐ３は「１／４」であり、入力信号ＩＰ１が“０”で出力信号ＯＰ１が“０”である確率Ｐ４は「３／８」である。したがって、入力信号ＩＰ１が変化したときに出力信号ＯＰ１が変化する確率Ｐｖ０１−１は、上記式（３）を利用して下記のように算出される。ただし、入力信号の各状態の発生確率は、セルライブラリ１１内への設定時には決定することができないので、すべて均等である（１／８）としている。
　　【００４０】
　Ｐｖ０１−１＝２×（Ｐ４×Ｐ１＋Ｐ３×Ｐ２）
　　　　　＝２×｛（３／８）×（１／４）＋（１／４）×（１／８）｝
　　　　　＝１／４＝０．２５
　以下、上述の手順と同様に計算することで、上記図３の下段に示すような入力信号ＩＰｉの変化に応じて出力信号ＯＰ１，ＯＰ２が変化する確率Ｐｖ０ｉ−１，Ｐｖ０ｉ−２が算出される。そして、各入力信号ＩＰ１，ＩＰ２が変化する確率ＰｖＩ１，ＰｖＩ２が分かれば、上記式（４）を利用して、各入力端子ＩＰ１，ＩＰ２からの入力信号の変化に応じて出力信号ＯＰ１が変化する確率Ｐｖ０１と、各入力信号ＩＰ１，ＩＰ２の変化に応じて出力信号ＯＰ２が変化する確率Ｐｖ０２とが求められることになる。
　　【００４１】
　次に、入力信号の変化確率を与えるステップＳＴ２における処理内容について説明する。入力信号の変化確率は、入力データの種類等に応じて、次の（Ｉ）、（ＩＩ）のいずれかの方法により求める。
（Ｉ）入力信号が複数ビットで表現された数値データである場合
　入力信号の分布状態つまり正規分布であるか均一分布であるか等と、１クロック当たりの入力信号の変化量の上限とを指定することにより、１クロック分の時間が経過した時の入力信号値の変化確率を統計的に求める。例えば、入力信号の分布状態によって、下記のように、ＭＳＢからＬＳＢに至る各ビットの値を示す信号の論理値（以下、単に「ビット値」という）が変化する確率が求まる。
　　【００４２】
　▲１▼　信号値の変化量の上限が十分大きく、変化後の信号値が変化前の信号値の影響を受けない場合
　この場合には、変化後の信号値は変化前の信号値に依存しない。つまり変化前の信号値の束縛を受けることなく変化しうる。従って、信号値が“１”となる確率は、変化前に“１”で変化後に“０”となる確率と、変化前に“０”で変化後に“１”となる確率とを
掛ける
　Ｐｖｒｋ＝２×Ｐｋ（１）×Ｐｋ（０）　　　　　　　　　　　　　　　（６）
で表される。
　　【００４３】
　▲２▼　入力データ値の変化幅が小さい場合つまり変化後の値が変化前の値の影響を受ける場合
　例えば図８に示すような入力信号の分布状態を示すグラフを、変数の分布方向に対して、均等な変化幅で区切り、各領域Ｒｅｉ毎に、上記ビット値が“１”で１クロック信号が入力された後に上記ビット値が“０”に変化する確率Ｐｖｒｋ（０）と、上記ビット値が“０”で１クロック信号が入力された後に上記ビット値が“１”である確率Ｐｖｒｋ（１）とをそれぞれの変化幅ごとに求める。上記ビット値が変化する確率Ｐｖｒｋは、下記式（７）
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
で表される。
（ＩＩ）入力データ（１ビット）がランダムな論理値である場合
　上記各ビット値が“１”である確率Ｐｋ（１）と“０”である確率Ｐｋ（０）はともに１／２である。故に、上記ビット値が変化する確率Ｐｖｒｋは、下記式（８）
　Ｐｖｒｋ＝２×Ｐｋ（１）×Ｐｋ（０）＝１／２　　　　　　　　　　　（８）
で表される。これは、例えば自動制御を行う電気回路においてしばしば生じる現象である。
　　【００４４】
　そして、入力信号の変化回数は、上述の方法により、入力信号の変化確率が求められると、その変化確率に均一な数値（全変化回数）をかけることにより求められる。
　　【００４５】
　以下、上述の基本的方法に従い入力信号の変化確率を求める手順を具体的に説明する。
　　【００４６】
　例えば、図６に示すような電気回路を想定する。つまり、各々“１”又は“０”からなる４つのビット値ＳＡ０〜ＳＡ３で表されるデータＤＡからなる入力信号と、各々論理値“１”又は“０”からなる４つのビット値ＳＢ０〜ＳＢ３で表されるデータＤＢからなる入力信号とが入力され、各要素４５〜４７で信号の変換を受けた後、各々論理値“１”又は“０″からなる４つのビット値Ｓ０〜Ｓ０３で表されるデータＤ０からなる出力信号が得られる電気回路である。ただし、ビット値ＳＡ０，ＳＢ０，Ｓ００がＬＳＢであり、ビット値ＳＡ３，ＳＢ３，Ｓ０３がＭＳＢである。そして、上記データＤＡについては、図７に示すように、発生確率ＰＡが均一値１／１６となる分布状態を示し、データＤＢについては、図８に示すように、データＤＢが大きくなるほど発生確率ＰＢが小さくなるような分布状態を示しているものとする。
　　【００４７】
　ここで、値の変化量が大きい場合における各ビット値ＳＡ０〜ＳＡ３，ＳＢ０〜ＳＢ３が論理値“１”となる確率Ｐｋ（１）（ｋ＝Ａ０〜Ａ３，Ｂ０〜Ｂ３）と、各ビット値ＳＡ０〜ＳＡ３，ＳＢ０〜ＳＢ３が論理値“１”のときに入力データ値ＤＡ，ＤＢが取りうる値（場合の数）とを下記表２に示す。
　　【００４８】　　　　　　　
　【表２】
　　【００４９】
　また、データＤＢの各値に対し、同データをとり得る確率ＰＢを下記表３に示す。
　　【００５０】
　【表３】
　　【００５１】
　上記表３のうちデータＤＢの値がそれぞれ「８」〜「１５」となる確率の総和が、入力信号のＭＳＢであるビット値ＳＢ３が論理値“１”となる確率に相当し、この場合、表２に示すように、ビット値ＳＢ３が“１”となる確率は「０．２４」となる。
　　【００５２】
　上述のように、各ビット値ＳＡ０〜ＳＡ３，ＳＢ０〜ＳＢ３が論理値“１”となる確率が求まると、これに基づき入力信号の変化確率が求められる。また、各ビット値ＳＡ０〜ＳＡ３，ＳＢ０〜ＳＢ３が論理値“０”となる確率Ｐｋ（０）は、各ビット値ＳＡ０〜ＳＡ３，ＳＢ０〜ＳＢ３が論理値“１”となる事象の余事象の確率であるから、下記式（９）
　Ｐｋ（０）＝１−Ｐｋ（１）　　　　　　　　　　　　　　　　　　　　（９）
で表される。したがって、上記式（６）から、各ビット値ＳＡ０〜ＳＡ３が変化する確率ＰｖｒＡ０〜ＰｖｒＡ３及びビット値ＳＢ０〜ＳＢ３が変化する確率ＰｖｒＢ０〜ＰｖｒＢ３は、それぞれ、以下のように計算される。
　　【００５３】
　ＰｖｒＡ０＝２×ＰＡ０（１）×ＰＡ０（０）
　　　　　　＝２×０．５×０．５＝０．５
　ＰｖｒＡ１＝２×ＰＡ１（１）×ＰＡ１（０）
　　　　　　＝２×０．５×０．５＝０．５
　ＰｖｒＡ２＝２×ＰＡ２（１）×ＰＡ２（０）
　　　　　　＝２×０．５×０．５＝０．５
　ＰｖｒＡ２＝２×ＰＡ３（１）×ＰＡ３（０）
　　　　　　＝２×０．５×０．５＝０．５
　ＰｖｒＢ０＝２×ＰＢ０（１）×ＰＢ０（０）
　　　　　　＝２×０．５×０．５＝０．５
　ＰｖｒＢ１＝２×ＰＢ１（１）×ＰＢ１（０）
　　　　　　＝２×０．５×０．５＝０．５
　ＰｖｒＢ２＝２ＸＰＢ２（１）×ＰＢ２（０）
　　　　　　＝２×０．４×０．６＝０．４８
　ＰｖｒＢ３＝２×ＰＢ３（１）×ＰＢ３（０）
　　　　　　＝２×０．２４×０．７６＝０．３６
　すなわち、図６に示す要素４５，４６への各入力信号線における入力信号の変化確率が求まることになる。
　　【００５４】
　次に、信号値の変化量が小さい場合における入力信号の変化確率の具体的な算出手順について説明する。この場合も、上記図６〜図８に示す信号状態を前提として考える。また、信号値の変化は１クロック当り「４」以下であるとつまり信号値の変化の上限が「４」であると仮定し、ビット値ＳＡ３についての算出手順を説明する。図９に示すように、入力データＤＡの値「０」〜「１５」間での領域を変化幅「４」で、４つの領域Ｒｅ１〜Ｒｅ４に区画する。すると、各領域Ｒｅ１〜Ｒｅ４におけるビット値ＳＡ３が論理値“１”である確率ＰＡ３（１）と、１クロック信号が入力された後に“０”である確率Ｐ１Ａ３（０）とは、下記表４に示される値となる。
　　【００５５】
　【表４】
　　【００５６】
　ただし、上記表４において、１クロック信号が入力された後に“０”である確率Ｐ１Ａ３（０）は、下記のように算出される。すなわち、ビット値ＳＡ３が“０”のときとはデータ値ＤＡが「０」〜「７」のときであるから、領域Ｒｅ１では、データ値の変化量が「４」であっても「７」であることから、Ｐ１Ａ３（０）は「１」になる。領域Ｒｅ２では、Ｐ１Ａ３（０）は、現在データＤＡが「４」，「５」，「６」，「７」である確率（いずれも均一値１／１６）と、この各データ値から最大「４」しか移動しないとして１クロック信号が入力された後に“０”となる確率８／９，７／９，６／９，５／９とを乗じた後、各積を総和したものになる。領域Ｒｅ３では、Ｐ１Ａ３（０）は、現在データＤＡが「８」，「９」，「１０」，「１１」である確率（いずれも１／１６）と、この各データ値から最大「４」しか移動しないとして１クロック信号が入力された後に“０”となる確率４／９，３／９，２／９，１／９とを乗じた後、各積を加算したものになる。また、領域Ｒｅ４では、現在のデータ値が最小値「１２」のときでも、１クロック信号が入力された後に「８」よりも小さくなることはないので、Ｐ１Ａ３（０）は「０」になる。
　　【００５７】
　従って、上記表４を用いて、各領域Ｒｅ１〜Ｒｅ４においてビット値ＳＡ３が論理値“１”から“０”に変化する確率ＰｖｒＲｉ（０）（ｉ＝１〜４）は、下記のように算出される。
　　【００５８】
　ＰｖｒＲ１（０）＝０×１＝０
　ＰｖｒＲ２（０）＝０×（２６）／（１６×９）＝０
　ＰｖｒＲ３（０）＝１０／（１６×９）＝５／７２
　ＰｖｒＲ４（０）＝１×０＝０
　したがって、ビット値ＳＡ３が“１”から１クロック信号が入力された後に“０”に変化する確率ＰｖｒＡ３（０）は、下記のように算出される。
　　【００５９】
　同様に、ビット値ＳＡ３が“０”から１クロック信号が入力された後に“１”に変化する確率ＰＡ３（１）は、下記のように算出される。
　　【００６０】
　よって、ビット値ＳＡ３が変化する確率ＰｖｒＡ３は、式（７）を用いて下記のように算出される。
　　【００６１】
　次に、図２のフローチャートの消費電力を推定するステップＳＴ４における処理内容について説明する。
　　【００６２】
　各信号線の消費電流Ｉｎは、上記信号線の信号の変化回数Ｓｎと上記信号線の配線容量Ｃｎ（Ｃｎは配線に接続するゲート容量も含む）
と電圧との積によって近似することができる。
で表される（ただし、電圧Ｖは一定であると仮定）。ここで、上記式（５）を用いることで、信号の変化確率を信号の変化回数に容易に換算し得る。
　　【００６３】
　そして、上記図２のフローチャートのステップＳＴ５における処理で、消費電力Ｗを考慮して、最適な配置配線が決定されることになる。
　　【００６４】
　図１０は、上記図２のステップＳＴ５の詳細を示すサブフローを示す。この配置配線の最適化処理では、まず目的関数を設定し、繰り返し改善法によって、目的関数を最小化する。繰り返し改善方法とは、セルの移動あるいは交換等の１回の変化をランダムあるいはある評価規準のもとで選択し、上記の変化を起こした場合の目的関数の変化を観測し、ある条件のもとで、その変化を受理するというプロセスを繰り返し、目的関数の最適化を図ろうとするものである。図１０は、繰り返し改善法の１種であるシミュレーティッド・アレーリング法による配置配線の最適化処理を示している（［２１］Ｓ．Ｋｉｒｋｐａｔｒｉｃｋ，Ｃ．Ｄ．Ｇｅｌａｔｔ　ａｎｄ　Ｍ．Ｐ．Ｖｅｃｃｈｉ，“Ｏｐｔｉｍｉｚａｔｉｏｎ　ｂｙ　Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ”，Ｓｃｉｅｎｃｅ，Ｖｏｌ．２２０，Ｎ．４５９８，ｐｐ．６７１−６８０，Ｍａｙ１９８３．参照）。本実施例では、上述の繰り返し改善法によって用いられる配置配線の評価関数を以下のように設定することによって実現する。
　　【００６５】
　まず、上記配置配線の評価関数Ｆとして、下記式（１２）
を設定する。ここで、式（１２）において、Ａ１、Ａ２はパラメータ、ΣＬｎは配線長、Ｗは上記のステップＳＴ１〜ＳＴ４で求めた消費電力である。本実施例では、２項目の最適化を優先するために、Ａ１＝１、Ａ２＝１００を用いる（ただし、この評価式において、信号線からクロック配線は除外する）。
　　【００６６】
　図１０のフロー中、Ｔ、α、Ｋはシミュレーティッドアニーリング法の最適効果に影響を与えるパラメータであり、本発明の本実施例においては、Ｔ０＝１、α＝０．９、Ｋ＝３０００を用いた。
　　【００６７】
　まず、ステップＳＴ５１でＴ＝Ｔ０と設定し、ステップＳＴ５２で電気回路内の要素をランダムに配置して配置配線の評価関数Ｆを求める。次に、ステップＳＴ５３でＩ＝０と設定してから、ステップＳＴ５４で要素又は要素のペアをランダムに交換し、移動又は交換を行ったと仮定した場合の増分ΔＦを計算する。
　　【００６８】
　そして、ステップＳＴ５５でΔＦ≧０か否かを判別し、ΔＦ≧０であれば、要素の移動又は交換によって改善効果が生じると判断し、ステップＳＴ５６に進んで上記ステップＳＴ５４で仮定した要素の移動又は交換を実行した後、ステップＳＴ５７でＩ＝Ｉ＋１と更新をする。一方、上記ステップＳＴ５５の判別で、ΔＦ≧０でない場合には、要素の移動又は交換による改善効果が疑わしいと判断してステップＳＴ５７に移行する。そして、ステップＳＴ５８で乱数Ｒ（０＜Ｒ＜１）を発生し、ステップＳＴ５９で、Ｒ＜ｅｘｐ（−ΔＦ／Ｔ）か否かを判別する。そして、Ｒ＜ｅｘｐ（−ΔＦ／Ｔ）でなければステップＳＴ５６に進んで要素の移動又は交換を行ってから上記ステップＳＴ５７でＩの更新を行い、Ｒ＜ｅｘｐ（−ΔＦ／Ｔ）であれば要素の移動又は交換を行うことなくステップＳＴ５７に進んでＩの更新を行う。つまり、このステップＳＴ５８，ＳＴ５９の処理を行うことで、局所最適解に陥るのを回避している。
　　【００６９】
　次に、ステップＳＴ６０に進み、Ｉ≧Ｋか否かを判別し、Ｉ≧ＫでなければステップＳＴ５４に戻って、上記ステップＳＴ５４〜５７の処理を繰り返し、Ｉ≧Ｋになると、ステップＳＴ６１で、ステップＳＴ５３の初期値の設定以降、要素の移動又は交換が起こったか否かを判別し、要素の移動又は交換が起こっていればステップＳＴ６２に進んで、まだ改善し得る可能性があると判断して、Ｔ＝αＴとパラメータＴを所定割合だけ小さくするよう再設定してから、上記ステップＳＴ５２に戻る。
　　【００７０】
　そして、上記ステップＳＴ６１の判別で、ステップＳＴ５３の処理以降、要素の移動又は交換が起こっていなければ、配置配線の改善の余地はないと判断し、最適化のための処理を終了する。
　　【００７１】
　次に、本実施例で行った具体的な配置配線の最適化の例について、図１１に示す論理回路を用いて説明する。図１１に示すように、論理回路には、２つの入力端予Ｐｘ，Ｐｙと各々信号線６１，６２を介して接続され２つの入力信号がいずれも“１”のときにのみ論理信号“０”を出力する第１ＮＡＮＤ回路５１と、該第１ＮＡＮＤ回路５１の出力側と出力端子Ｐｚとに各々信号線６３，６４を介して接続され２つの入力信号がいずれも“１”のときにのみ論理信号“０”を出力する第２ＮＡＮＤ回路５２と、該第２ＮＡＮＤ回路５２と信号線６５を介して接続され入力信号を一時的に保持した後出力するフリップフロップ５３とが配置されている。図１１の（）内の数字は、上述の解析で求められた所定時間内における信号の変化回数である。
　　【００７２】
　図１２は、本実施例の配置配線の最適化処理方法を用いて、配置配線を最適化した論理集積回路のレイアウトの例を示す図である。図中の（）内の数値は各信号線の配線容量を示している。
　　【００７３】
　上記評価関数の適用範囲は極めて広く、アレー状の配置配線のみならず、データパスレイアウト等に用いられる線形配置や、形状の異なるゼネラルブロックの配置配線等の、あらゆる配置配線問題に用いることができる。
　　【００７４】
　したがって、上記実施例では、電気回路の消費電力を推定するに際し、信号線の総延長となる配線長だけでなく、各信号線における信号の変化回数を考慮することで、消費電力の推定精度が高くなる。特に、ＣＭＯＳ型半導体集積回路の場合、消費電力はほとんどが信号線の充放電に要する電力で占められるので、前述した配線容量と、各信号線の信号が変化する回数に基づいて消費電力を算出することで、推定精度が極めて高くなる。
　　【００７５】
　その場合、上記従来の消費電力の推定方法のごとく、テストパターンを用いる方法では、テストパターンの準備とシミュレーションの実行とに膨大な時間を要したが、上記実施例のごとく、高速かつ精度の高い消費電力の推定を行うことができ、もって、電気回路の最適な配置配線を行うことができる。
　　【００７６】
　　（第２実施例）
　次に、第２実施例について説明する。本実施例においても、上記第１実施例の図１に示す装置の全体構成や、図２に示すフローチャートに示す基本的な処理手順は、そのまま適用される。
　　【００７７】
　ここで、本実施例では、出力信号の変化確率を入力信号の変化確率の関数として求めるステップ（図２のステップＳＴ１）において、論理の真理値表ではなく、ＢＤＤ（Ｂｉｎａｒｙ　Ｄｅｃｉｓｉｏｎ　Ｄｉａｇｒａｍ）を利用する。図１３（ａ），（ｂ）は、上記図５に示す電気回路でかつ図３に示す真理値表に示すと同じ入力信号一出力信号の対応関係を有する場合について、入力信号の変化に応じて出力信号ＯＰ１，ＯＰ２が変化する確率を求めるためのＢＤＤをそれぞれ示す。図中の円で示される各頂点ＣＲ１〜ＣＲ８は、１個のバイナリー関数を表現しており、そこから出るパス７０Ａ〜７０Ｈ，７１Ａ〜７１Ｈは、その入力変数の値が“０”の場合，“１”の場合の関数をそれぞれ表現する頂点に向かって延びている。また、図中矩形で示される頂点ＳＱ１，ＳＱ２は出力信号ＯＰ１の値がそれぞれ“１”，“０”の場合を示し、頂点ＳＱ３，ＳＱ４は出力信号ＯＰ２の値がそれぞれ“１”，“０”の場合を示す。
　　【００７８】
　例えば図１３（ａ）の場合、
　ＩＰ１＝０ａｎｄ　ＩＰ２＝０ａｎｄ　ＱＰ１＝１のときと、
　ＩＰ１＝１ａｎｄ　ＩＰ２＝０のとき（つまりＱＰ１の値に拘らず）
に出力信号ＯＰ１が“１”になることを示している。
　　【００７９】
　また、図１３（ｂ）の場合、
　ＩＰ１＝０ａｎｄ　ＩＰ２＝１のとき（ＱＰ１の値に拘らず）と、
　ＩＰ１＝１ａｎｄ　ＩＰ２＝０ａｎｄ　ＱＰ１＝１のとき
に出力信号ＯＰ２が“１”になることを示している。
　　【００８０】
　つまり、上記第１実施例における図３に示す真理値表と同じ内容を表現している。
　　【００８１】
　次に、このＢＤＤを利用して、入力信号ＩＰ１，ＩＰ２，ＱＰ１の変化に応じて出力信号ＯＰ１，ＯＰ２が変化する確率Ｐｖ０ｉ−ｊを求める手順を説明する。
（Ａ）　入力信号ＩＰ１が“１”で出力信号ＯＰ１が“１”となる確率
　各入力信号ＩＰ１，ＩＰ２が“１”である確率も“０”である確率も等しいので、ＩＰ１＝１の確率つまり７０Ｆを通過する確率は１／２である。次に、頂点ＣＲ３から頂点ＳＱ１に延びるパス全てについて確率を求めれば、入力信号ＩＰ１が“１”で出力信号ＯＰ１が“１”となる確率が求まる筈である。結局、頂点ＣＲ３から頂点ＳＱ１に到達するパスは７０Ｇのみなので、出力信号ＯＰ１が“１”となる確率は、
　（１／２）×（１／２）＝１／４
となる。
（Ｂ）　入力信号ＩＰ２が“１”で出力信号ＯＰ１が“０”となる確率
　パス７０Ａ及びパス７０Ｆを通って頂点ＳＱ２に到達する場合と、パス７０Ｄ及びパス７０Ｅを通って頂点ＳＱ２に到達する場合との２通りである。従って、出力信号ＯＰ１が“０”となる確率は、
　（１／２）×（１／２）＋（１／２）×（１／２）＝１／２
となる。
（Ｃ）　入力制御信号ＱＰ１が“１”で出力信号ＯＰ１が“０”となる確率
　頂点ＣＲ４から頂点ＳＱ２に至る場合はないので、頂点ＣＲ４を通らずに頂点ＳＱ２に到達する場合のみである。したがって、この場合の確率は、
　（１／２）×（１／２）＋（１／２）×（１／２）＝１／２
となる。
（Ｄ）　その他
　以上の例と同様に計算することにより、各入力信号ＩＰ１，ＩＰ２の値“１”，“０”に対して出力信号ＯＰ１，ＯＰ２の値“１”，“０”が対応する確率を求めることができる。その値を以下にまとめて示す。
１．入力信号ＩＰ１と出力信号ＯＰ１との間
　入力信号ＩＰ１が“１”で出力信号ＯＰ１が“１”となる確率　　１／４
　人力信号ＩＰ１が“０”で出力信号ＯＰ１が“１”となる確率　　１／８
　人力信号ＩＰ１が“１”で出力信号ＯＰ１が“０”となる確率　　１／４
　人力信号ＩＰ１が“０”で出力信号ＯＰ１が“０”となる確率　　３／８
２．入力信号ＩＰ１と出力信号ＯＰ２との間
　入力信号ＩＰ１が“１”で出力信号ＯＰ２が“１”となる確率　　１／８
　人力信号ＩＰ１が“０”で出力信号ＯＰ２が“１”となる確率　　１／４
　人力信号ＩＰ１が“０”で出力信号ＯＰ２が“１”となる確率　　３／８
　人力信号ＩＰ１が“０”で出力信号ＯＰ２が“０”となる確率　　１／４
３．入力信号ＩＰ２と出力信号ＯＰ１との間
　入力信号ＩＰ２が“１”で出力信号ＯＰ１が“１”となる確率　　０
　人力信号ＩＰ２が“０”で出力信号ＯＰ１が“１”となる確率　　３／８
　人力信号ＩＰ２が“１”で出力信号ＯＰ１が“０”となる確率　　１／２
　人力信号ＩＰ２が“１”で出力信号ＯＰ１が“１”となる確率　　１／８
４．入力信号ＩＰ２と出力信号ＯＰ２との間
　入力信号ＩＰ２が“１”で出力信号ＯＰ２が“１”となる確率　　１／４
　人力信号ＩＰ２が“０”で出力信号ＯＰ２が“１”となる確率　　１／８
　人力信号ＩＰ２が“１”で出力信号ＯＰ２が“０”となる確率　　１／４
　人力信号ＩＰ２が“０”で出力信号ＯＰ２が“０”となる確率　　３／８
　そして、最終的に、上記第１実施例と同様に、上記図３の下段に示すごとく入力信号ＩＰｉの変化に応じて出力信号ＯＰ１，ＯＰ２が変化する確率Ｐｖ０ｉ−１，Ｐｖ０ｉ−２が算出される。そして、各入力信号ＩＰ１，ＩＰ２が変化する確率ＰｖＩ１，ＰｖＩ２が分かれば、上記式（４）を利用して、各入力信号ＩＰ１，ＩＰ２の変化に応じて出力信号ＯＰ１が変化する確率Ｐｖ０１と、各入力信号ＩＰ１，ＩＰ２の変化に応じて出力信号ＯＰ２が変化する確率Ｐｖ０２とが求められることになる。
　　【００８２】
　なお、説明は省略するが、入力信号の変化確率を求める手順，方法や消費電力を最小にするための配置配線の最適化処理については、上記第１実施例で述べた方法が適用される。
　　【００８３】
　本実施例では、上記第２実施例と比較して、各信号線の変化確率の計算時間を短縮できるという利点がある。すなわち、第１実施例のごとく真理値表を利用すると、入力信号線がｎ個で出力信号線がｎ個の場合には２ｎ個の真理値表を作成する必要があるが、本実施例のごとくＢＤＤを利用する場合には、多くの場合においてｎ×Ｋ（Ｋは定数）個の頂点を有するＤｉａｇｒａｍに圧縮できるので、要素数が多くなればなるほど計算時間が大幅に短縮できるのである。
　　【００８４】
　　【発明の効果】
　以上説明したように、請求項
１，４又は５
とともに、
　　【００８５】
　請求項２によれば、複数の直列に配置される要素を有する回路の場合には、入力側に配置された要素の入出力信号の変化確率から順次各要素の入出力信号の変化確率を求めるようにしたので、全ての要素に接続される信号線における信号の変化確率を迅速に求めることができる。
　　【００８６】
　請求項３によれば、各要素の真理値表を用いて各信号線における信号の変化確率を求めるようにしたので、演算の容易化と確実化とを図ることができる。
　　【００８７】
　請求項
６
　　【００８８】
　請求項
７
　　【００８９】
　請求項
８
【図面の簡単な説明】
　　【図１】
　第１及び第２実施例に係るＬＳＩ設計装置の一部の構成を示すブロック図である。
　　【図２】
　第１及び第２実施例に係る配置配線の決定方法の手順を示すフローチャート図である。
　　【図３】
　第１実施例に係るＬＳＩ設計装置のセルライブラリの登録内容を示す図である。
　　【図４】
　第１及び第２実施例に係るＬＳＩ設計装置のネット信号統計情報部の登録内容を示す図である。
　　【図５】
　第１及び第２実施例で入力信号の変化に応じて出力信号が変化する確率を求めるために例として用いた基本的な要素の構成を概略的に示す模式図である。
　　【図６】
　第１実施例に係る４ビットの入力信号が入力される論理回路の例を示すブロック図である。
　　【図７】
　第１実施例に係る均一な分布状態を有する入力データの特性図である。
　　【図８】
　第１実施例に係る数値が大きくなるほど発生確率が小さくなる入力データの特性図である。
　　【図９】
　第１実施例において４ビットの信号からなるデータを複数の領域に区画する方法を説明するための図である。
　　【図１０】
　シミュレーデッド・アニーリング法による配置配線最適化処理の手順を示すフローチャート図である。
　　【図１１】
　第１実施例に係る配置配線の最適化処理に使用した論理回路の例を示す電気回路図である。
　　【図１２】
　第１実施例に係る最適化処理を行った論理集積回路のレイアウトを示す図である。
　　【図１３】
　第２実施例に係るＢＤＤを示す模式図である。
　　【符号の説明】
　１　　記憶装置（記憶手段）
　２　　消費電力解析システム（推定演算手段）
　３　　計算機（配置配線決定手段）
　４　　表示装置
　１１　セルライブラリ
　１２　ネットリスト部
　１３　ネット信号統計情報部