(57)【特許請求の範囲】
【請求項１】
逆階層構造を持つレイアウトデータに対する図形検証処理を行う図形検証装置であって、
前記逆階層構造を持つレイアウトデータには、各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存されており、前記複数の基本要素データ及び前記複数のセルデータは自身が直接参照される上位セルデータの情報である親セル情報をそれぞれ有することにより前記階層構造を逆方向で規定し、前記親セル情報が示す前記上位セルデータは複数の上位セルデータを含み、
前記レイアウトデータの前記親セル情報に基づき上位セルデータを検索する逆階層構造解析を行い、前記複数の基本要素データで規定される図形が用いられる実空間領域を決定する逆階層構造解析部と、
前記実空間領域における占有率の検証処理を行う図形検証部とを備える、
図形検証装置。
【請求項２】
第１種レイアウトデータを第２種レイアウトデータに変換するレイアウトデータ変換装置であって、
第１種及び第２種レイアウトデータには各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存されており、
前記第１種レイアウトデータにおける前記複数のセルデータは、自身が直接参照する下位セルデータあるいは前記基本要素データを示す情報である子セル情報が保存されることにより前記階層構造を正方向で規定し、
前記第２種レイアウトデータにおける前記複数の基本要素データ及び前記複数のセルデータは自身が直接参照される上位セルデータの情報である親セル情報が保存されることにより前記階層構造を逆方向で規定し、前記親セル情報が示す上位セルデータは複数の上位セルデータを含み、
前記レイアウトデータ変換装置は、
前記第１種レイアウトデータの前記子セル情報に基づき前記階層構造を解析する階層構造解析部と、
前記階層構造解析部による解析結果に基づき、前記複数の基本要素データ及び前記複数のセルデータにそれぞれ前記親セル情報を付加して前記第２種レイアウトデータを生成する逆階層構造生成部と、
を備えるレイアウトデータ変換装置。
【請求項３】
第２種レイアウトデータを第１種レイアウトデータに変換するレイアウトデータ変換装置であって、
前記第１種及び第２種レイアウトデータには、各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存され、
前記第１種レイアウトデータにおける前記複数のセルデータには、自身が直接参照する下位セルデータあるいは前記基本要素データを示す情報である子セル情報がそれぞれ保存されることにより前記階層構造を正方向で規定し、
前記第２種レイアウトデータにおける前記複数の基本要素データ及び前記複数のセルデータは自身が直接参照される上位セルデータの情報である親セル情報がそれぞれ保存されることにより前記階層構造を逆方向で規定し、前記親セル情報が示す前記上位セルデータは複数の上位セルデータを含み、
前記レイアウトデータ変換装置は、
前記第２種レイアウトデータの前記親セル情報に基づき前記階層構造を解析する逆階層構造解析部と、
前記逆階層構造解析部による解析結果に基づき、前記複数のセルデータにそれぞれ前記子セル情報を付加して前記第１種レイアウトデータを生成する階層構造生成部と、
を備えるレイアウトデータ変換装置。
【請求項４】
請求項１記載の図形検証装置であって、
前記実空間領域は複数のメッシュ領域で構成され、
前記図形検証部は、前記複数の基本要素データで規定される図形の前記複数のメッシュ領域それぞれでの占有率を計算する占有率計算部を含む、
図形検証装置。
【請求項５】
請求項１記載の図形検証装置であって、
前記実空間領域は複数のメッシュ領域で構成され、
前記図形検証部は、前記複数の基本要素データで規定される図形の前記複数のメッシュ領域上での占有領域に関してフーリエ解析するフーリエ解析部を含む、
図形検証装置。
【請求項６】
請求項１、請求項４及び請求項５のうち、いずれか１項に記載の図形検証装置であって、
前記図形検証部は、
前記実空間領域を占有する２以上の図形が同一領域上で重複して発生した場合に、一方の図形の占有領域から当該重複部分を除去する占有領域変形処理を実行する、
図形検証装置。
【請求項７】
請求項１、請求項４及び請求項５のうち、いずれか１項に記載の図形検証装置であって、
前記図形検証部は、
前記実空間領域上を占有する２以上の図形が同一領域上で重複して発生した場合に、重複部分に新たに減算用図形を発生する、
図形検証装置。
【請求項８】
請求項１、及び請求項４ないし請求項７のうち、いずれか１項に記載の図形検証装置であって、
前記レイアウトデータを第２種レイアウトデータとし、第１種レイアウトデータを受け、前記第１種レイアウトデータは各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存され、前記第１種レイアウトデータにおける前記複数のセルデータは、自身が直接参照する下位セルデータあるいは前記基本要素データを示す情報である子セル情報をそれぞれ保存することにより前記階層構造を正方向で規定し、
前記第１種レイアウトデータを受け、前記第２種レイアウトデータに変換して前記逆階層構造解析部に出力するレイアウトデータ変換部をさらに備える、
図形検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとを備えるレイアウトデータを用いた図形検証装置等に関する。
【背景技術】
【０００２】
従来、大規模集積回路（ＬＳＩ）の回路パターンをレイアウトしたデータ（レイアウトデータ）は、ＣＡＬＭＡ社からリリースされているＧＤＳ２ＳＴＲＥＡＭフォーマットに従う形式で保存されてきた。ＧＤＳ２ＳＴＲＥＡＭフォーマットは、現在世界中に広く普及し、事実上の標準フォーマットになっている。そのため、他社製のソフトウェアへデータを受け渡す際にも、一旦、ＧＤＳ２ＳＴＲＥＡＭフォーマットへ変換した上で受け渡すことが一般的な運用方法となっている。
【０００３】
このＧＤＳ２ＳＴＲＥＡＭフォーマットでは、まず、出発点となる最上位階層のトップセルを指定し、そのトップセルの中に図形データや参照する別のセルが指定されている。参照されたセルの中にも図形データや参照する別のセルが指定されている。この参照関係は、最下層のセル（図形データ）に到達するまで再帰的に繰り返されている。したがって、最上位のトップセルから順にセルの階層構造を辿っていくことで順次全てのデータを扱うことができる。このように、階層構造を記述することによりファイル全体が構成されていることが、ＧＤＳ２ＳＴＲＥＡＭフォーマットの特徴となる。
【０００４】
図１８は従来のレイアウトデータの保存例を示す説明図である。図１９は図１８で示す形式で保存されたレイアウトデータのツリー構造を示す説明図である。
【０００５】
これら図に示すように、データは階層構造を呈している。図１８は３つのセルデータcell1〜cell3によって以下のように記述されている。
【０００６】
cell1{cell2,cell2,cell2}
cell2{figD1,figD2,cell3,cell3}
cell3{figD3,figD4,figD5}
【０００７】
ここで、figD1〜figD5を図形データとする。図形データとは”基本要素データ”とも呼ばれ、実際には、正方形が１個とか、長方形が１個といったデータを意味する。例えば、横長の長方形と細い縦長の長方形と小さい正方形を３つ重ねると、トランジスタができ、それぞれの属性は、横長の長方形は活性領域、細い縦長の長方形はゲート、小さい正方形はソース、ゲート、ドレイン用のコンタクトホールとなる。このように、基本要素データ（図形データ）は、半導体装置の構成要素のレイアウトパターンとなる図形を規定している。
【０００８】
上記例では、最上位階層のセルデータcell1において、その下位のセルデータcell２が３回参照されているので、cell2に含まれるfigD1とfigD2は３回使用されることなる。さらに、cell2はさらに下位のセルデータcell3を２回参照しているため、cell3に含まれるfigD3〜figD5は、cell1として６回ずつ使用されることになる。もし、cell1のデータをフラットに（図形データのみに）展開すると以下に示すフラットデータを得ることができる。
【０００９】
｛figD1,figD2,figD3,figD4,figD5,figD3,figD4,figD5,figD1,figD2,figD3,figD4,figD5,figD3,figD4,figD5,figD1,figD2,figD3,figD4,figD5,figD3,figD4,figD5｝
【００１０】
このように、同じ図形データを何度も繰り返し記述することとなる。ＧＤＳ２ＳＴＲＥＡＭフォーマットは上記したフラットに展開した例に比べ、階層構造を利用している分コンパクトなデータ構造となっている。この傾向は、大規模なデータを扱うＬＳＩのレイアウトデータとして用いる場合、より顕著になる。
【００１１】
このように、階層構造を持つデータ形式は、ある一つの基本図形を繰り返し使用したり、比較的大きなデータ量の移動やコピーする作業が頻繁に発生することには、セルの参照内容を変更するだけですむため、非常に効率が良い。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
ＧＤＳ２ＳＴＲＥＡＭフォーマットで代表される通常の階層構造を用いたレイアウトデータは、前述の通り、セル内に参照すべきセルや図形データ（以下、単に「子セル」と呼ぶ。）は指定されている。しかし、逆に、セル内に自身が参照されるセル（以下、単に「親セル」と呼ぶ。）は指定されていない。すなわち、上位から下位のセルデータを指定して階層構造を実現している。
【００１３】
このため、あるセルの内部を修正したとき、その影響が上位のセルのどこまで及ぶかをチェックするには、いちいち全階層構造と逆に辿ってデータを展開してチェックしていく必要がある。また、別々のセルに含まれる図形の相互の位置関係を考慮するなどの用途に対しては、一旦階層構造を展開してフラットなデータ構造にする必要が生じるため、もともと階層構造を有さないフラットなデータよりも処理効率が悪くなっている。ＬＳＩのレイアウトデータ量は膨大な量となるため、階層構造を展開してフラットデータにする際、ディスクやメモリ等の記憶装置の容量を超えてしまい正常に処理できない問題点があった。
【００１４】
このような問題を回避するには、レイアウトデータ設計段階で、セル同士の参照関係に注意したり、隣のセルと重ならないように注意する等の特殊なノウハウが必要であった。
【００１５】
この発明は上記問題点を解決するためになされたもので、基本要素データが規定する図形の変更等の全体に与える影響を比較的簡単にチェック可能な構造のレイアウトデータを用いた図形検証装置を得ることを目的とする。
【課題を解決するための手段】
【００１６】
この発明に係る請求項１記載の図形検証装置は、前記逆階層構造を持つレイアウトデータには、各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存されており、前記複数の基本要素データ及び前記複数のセルデータは自身が直接参照される上位セルデータの情報である親セル情報をそれぞれ有することにより前記階層構造を逆方向で規定し、前記親セル情報が示す前記上位セルデータは複数の上位セルデータを含み、前記レイアウトデータの前記親セル情報に基づき上位セルデータを検索する逆階層構造解析を行い、前記複数の基本要素データで規定される図形が用いられる実空間領域を決定する逆階層構造解析部と、前記実空間領域における占有率の検証処理を行う図形検証部とを備えている。
【００１８】
この発明に係る請求項２記載のレイアウトデータ変換装置は、第１種レイアウトデータを第２種レイアウトデータに変換するレイアウトデータ変換装置であって、第１種及び第２種レイアウトデータには各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存されており、前記第１種レイアウトデータにおける前記複数のセルデータは、自身が直接参照する下位セルデータあるいは前記基本要素データを示す情報である子セル情報が保存されることにより前記階層構造を正方向で規定し、前記第２種レイアウトデータにおける前記複数の基本要素データ及び前記複数のセルデータは自身が直接参照される上位セルデータの情報である親セル情報が保存されることにより前記階層構造を逆方向で規定し、前記親セル情報が示す上位セルデータは複数の上位セルデータを含み、前記レイアウトデータ変換装置は、前記第１種レイアウトデータの前記子セル情報に基づき前記階層構造を解析する階層構造解析部と、前記階層構造解析部による解析結果に基づき、前記複数の基本要素データ及び前記複数のセルデータにそれぞれ前記親セル情報を付加して前記第２種レイアウトデータを生成する逆階層構造生成部と、を備えている。
【００１９】
この発明に係る請求項３記載のレイアウトデータ変換装置は、第２種レイアウトデータを第１種レイアウトデータに変換するレイアウトデータ変換装置であって、前記第１種及び第２種レイアウトデータには、各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存され、前記第１種レイアウトデータにおける前記複数のセルデータには、自身が直接参照する下位セルデータあるいは前記基本要素データを示す情報である子セル情報がそれぞれ保存されることにより前記階層構造を正方向で規定し、前記第２種レイアウトデータにおける前記複数の基本要素データ及び前記複数のセルデータは自身が直接参照される上位セルデータの情報である親セル情報がそれぞれ保存されることにより前記階層構造を逆方向で規定し、前記親セル情報が示す前記上位セルデータは複数の上位セルデータを含み、前記レイアウトデータ変換装置は、前記第２種レイアウトデータの前記親セル情報に基づき前記階層構造を解析する逆階層構造解析部と、前記逆階層構造解析部による解析結果に基づき、前記複数のセルデータにそれぞれ前記子セル情報を付加して前記第１種レイアウトデータを生成する階層構造生成部と、を備えている。
【００２０】
また、請求項４の発明は、請求項１記載の図形検証装置であって、前記実空間領域は複数のメッシュ領域で構成され、前記図形検証部は、前記複数の基本要素データで規定される図形の前記複数のメッシュ領域それぞれでの占有率を計算する占有率計算部を含む。
【００２１】
また、請求項５の発明は、請求項１記載の図形検証装置であって、前記実空間領域は複数のメッシュ領域で構成され、前記図形検証部は、前記複数の基本要素データで規定される図形の前記複数のメッシュ領域上での占有領域に関してフーリエ解析するフーリエ解析部を含む。
【００２２】
また、請求項６の発明は、請求項１、請求項４及び請求項５のうち、いずれか１項に記載の図形検証装置であって、前記図形検証部は、前記実空間領域を占有する２以上の図形が同一領域上で重複して発生した場合に、一方の図形の占有領域から当該重複部分を除去する占有領域変形処理を実行する。
【００２３】
また、請求項７の発明は、請求項１、請求項４及び請求項５のうち、いずれか１項に記載の図形検証装置であって、前記図形検証部は、前記実空間領域上を占有する２以上の図形が同一領域上で重複して発生した場合に、重複部分に新たに減算用図形を発生する。
【００２４】
さらに、請求項８の発明は、請求項１、及び請求項４ないし請求項７のうち、いずれか１項に記載の図形検証装置であって、前記レイアウトデータを第２種レイアウトデータとし、第１種レイアウトデータを受け、前記第１種レイアウトデータは各々が半導体装置の構成要素のレイアウトパターンとなる図形を直接規定する複数の基本要素データと、最終的に前記基本要素データを参照可能に階層構造で構築される複数のセルデータとが保存され、前記第１種レイアウトデータにおける前記複数のセルデータは、自身が直接参照する下位セルデータあるいは前記基本要素データを示す情報である子セル情報をそれぞれ保存することにより前記階層構造を正方向で規定し、前記図形検証装置は、前記第１種レイアウトデータを受け、前記第２種レイアウトデータに変換して前記逆階層構造解析部に出力するレイアウトデータ変換部をさらに備えている。
【発明の効果】
【００２５】
この発明における請求項１記載の図形検証装置の図形検証部は、下位から上位への階層関係を規定した逆方向の階層構造を規定して逆階層構造を持つレイアウトデータを用いている。このため、基本要素データの親セル情報を起点にして階層構造を逆方向に検索することにより、基本要素データが規定する図形の変更等の全体に与える影響を比較的簡単に調べることができる。
【００２６】
この発明における請求項２記載のレイアウトデータ変換装置は、第１種レイアウトデータを第２種レイアウトデータに変換できるため、既存の第１種レイアウトデータを第２種レイアウトデータとして有効に活用することができる。
【００２７】
この発明における請求項３記載のレイアウトデータ変換装置は、第２種レイアウトデータを第１種レイアウトデータに変換できるため、既存の第１種レイアウトデータと階層構造を逆方向で規定した第２種レイアウトデータとの互換性を図ることができる。
【００２８】
請求項４記載の図形検証装置は、基本要素データで規定される図形の複数のメッシュ領域上での占有率計算をより高速に行うことができる。
【００２９】
請求項５記載の図形検証装置は、基本要素データで規定される図形の複数のメッシュ領域上での占有領域に関するフーリエ解析を高速に行うことができる。
【００３０】
請求項６記載の図形検証装置は、２以上の図形が同一領域上で重複して発生した場合に、一方の図形の占有領域から重複部分を除去する占有領域変形処理を施しているため、２以上の図形が同一領域を占有した場合でも、占有領域を単純加算することによって総合的な占有領域を正確に認識することができる。
【００３１】
請求項７記載の図形検証装置は、２以上の図形が同一領域上で重複して発生した場合に、重複部分に新たに減算用図形を発生するため、２以上の図形が実間領域を占有した場合でも、占有領域を単純加算し後に上記減算用図形を減算することよって総合的な占有領域を正確に認識することができる。
【００３２】
請求項８記載の図形検証装置は、レイアウトデータ変換部をさらに備えることにより、階層構造を上位から下位へ規定した第１種レイアウトデータに対しても効率的に図形検証が行える。
【発明を実施するための最良の形態】
【００３３】
＜実施の形態１＞
図１はこの発明の実施の形態１であるレイアウトデータの保存形式を示す説明図である。同図の矢印は参照方向を示している。同図に示すように、基本要素データ記述部１１、セルデータ記述部１２、セルデータ記述部１３、最上位セルデータ記述部１４の順で下位から上位となる階層構造を呈している。
【００３４】
基本要素データ記述部１１はセルデータ記述部１２、セルデータ記述部１３あるいは最上位セルデータ記述部１４から直接参照され、直接参照されたセルデータを示す親セル情報（図中の矢印に相当）として有している。
【００３５】
セルデータ記述部１２はセルデータ記述部１３あるいは最上位セルデータ記述部１４から直接参照され、直接参照されたセルデータを示す親セル情報を有している。
【００３６】
セルデータ記述部１３は他のセルデータ記述部１３あるいは最上位セルデータ記述部１４から直接参照され、直接参照されたセルデータを示す親セル情報を有している。
【００３７】
最上位セルデータ記述部１４は最上階層のため親セル情報を有していない。
【００３８】
このように、実施の形態１のレイアウトデータの保存形式は、従来とは逆方向の下位から上位にかけての階層関係が明確になる逆階層構造で保存する保存形式である。以降、本明細書では、階層構造において上位から下位の方向を正方向、下位から上位の方向を逆方向と呼ぶ。
【００３９】
図２は逆階層構造のレイアウトデータ生成方法を示すフローチャートである。以下、図２を参照して、実施の形態１のレイアウトデータ構造の生成動作を説明する。
【００４０】
ステップＳ１１において、基本要素データＤＰを作成する。基本要素データＤＰは図形データであり、従来同様、図形自体を示す情報及び属性に加え、逆階層構造を満足すべく、直接参照されるセルデータを示す親セル情報を有している。この基本要素データＤＰは基本要素データ記述部１１に相当する。
【００４１】
ステップＳ１２において、基本要素データＤＰを参照する第１レベルセルデータＣＬ１を記述する。但し、第１レベルセルデータＣＬ１には参照する基本要素データＤＰとの階層関係を示す子セル情報は含ませず、その代わりに自身が直接参照される親セル情報を含ませている。
【００４２】
なお、第１レベルセルデータＣＬ１としては、一つまたは複数の基本要素データＤＰを参照して、ＡＮＤ，ＯＲ，ＮＯＴ，ＮＡＮＤ等の基本論理機能を有するセル等が挙げられる。
【００４３】
ステップＳ１３において、第１レベルセルデータＣＬ１を参照する第２レベルセルデータＣＬ２を記述する。第２レベルセルデータＣＬ２には参照する第１レベルセルデータＣＬ１との階層関係を示す子セル情報は含ませず、自身が直接参照される親セル情報を含ませている。なお、第２レベルセルデータＣＬ２が他の第２レベルセルデータＣＬ２に参照されることもあり得るため、セルデータデータ記述部１３による第２レベルセルデータＣＬ２の記述動作は再帰的に実行される。
【００４４】
なお、第２レベルセルデータＣＬ２としては、第１レベルセルデータＣＬ１、基本要素データＤＰを組み合わせて、より高機能のコマンドとなるセル等が挙げられる。また、第２レベルセルデータＣＬ２が一部、基本要素データＤＰを参照しても良い。
【００４５】
最後に、ステップＳ１４において、いずれのセルにも参照されない最上位レベルセルデータＣＬＸを記述する。なお、第１レベルセルデータＣＬ１、第２レベルセルデータＣＬ２が最上位レベルセルデータＣＬＸとなることもある。
【００４６】
なお、基本要素データＤＰ、第１レベルセルデータＣＬ１、及び第２レベルセルデータＣＬ２及び最上位レベルセルデータＣＬＸはそれぞれ自身で規定された空間上の大きさ、原点位置等を規定する領域情報を有している。
【００４７】
このように、実施の形態１のレイアウトデータの保存形式で保存されるレイアウトデータは、各セルデータが親セル情報を有している逆階層構造を呈している。
【００４８】
図３は実施の形態１であるレイアウトデータの保存状態を示す説明図である。図４は図３で示す形式で保存されたレイアウトデータのツリー構造を示す説明図である。なお、図３及び図４のレイアウトデータは図１８及び図１９で示すレイアウトデータに対応している。
【００４９】
図３及び図４に示すように、セルデータ（基本要素データを含む）が直接参照される上位のセルデータを示す親セル情報を有している。すなわち、基本要素データfigD１，figD2が共にセルデータcell2を親セル情報として有し、基本要素データfigD3〜figD5が共にセルデータcell3を親セル情報として有し、セルデータcell３が２つの同一セルデータcell2,cell2を親セル情報として有し、セルデータcell2が３つの同一セルデータcell1,cell1,cell1を親セル情報として有している。
【００５０】
したがって、figD4の親セル情報（cell3）を起点として、figD4が参照される全てのセルデータとの関係（cell3（１回参照）,cell2（cell3経由で２回参照）,cell1（cell2，cell3経由で６回参照））を効率的かつ正確に認識可能なことがわかる。
【００５１】
基本要素データＤＰの図形を修正した場合、その修正が基本要素データＤＰを直接あるいは間接的に参照する全てのセルに及ぶ。従来の階層構造のレイアウトデータの保存方法では、正方向の階層関係しか規定されていなかったため、最下位レベルの基本要素データＤＰの修正が全体に与える影響を正しく把握することは困難であった。
【００５２】
しかしながら、実施の形態１のレイアウトデータの保存形式は、階層関係が逆方向で規定されているため、基本要素データＤＰの親セル情報を起点として検索することにより、効率的かつ正確に基本要素データＤＰの修正の全体への影響を認識することができる。
【００５３】
図５は、レイアウトデータにおける階層構造を例示する説明図である。図５の例では、最上位セルデータとなる半導体チップ１に、その下位のセルデータとなるメモリ２、入出力インタフェース３、およびロジック（論理）回路４が配置されている。さらに、メモリ２には、その下位のセルデータとなる周辺回路５とメモリセルアレイ６とが配置されており、メモリセルアレイ６には、さらに下位のセルデータとなる多数のメモリセル７がマトリクス状に配置されている。メモリセル７には、階層構造の最下位に位置する基本要素データで規定される図形である基本要素Ｆ０，Ｆ１，Ｆ２が配置されている。
【００５４】
例えば、基本要素データＦ２を変更した場合、メモリセルアレイ６（すべてのメモリセル７）、メモリ２を介して半導体チップ１に影響を与えることが、実施の形態１の逆階層構造のレイアウトデータであれば、基本要素データＦ２の親セル情報を起点として親セル情報を辿ることにより、比較的簡単に半導体チップ１レベルでの影響を認識することができる。
【００５５】
＜実施の形態２＞
図６はこの発明の実施の形態２であるレイアウトデータ変換装置の構成を示すブロック図である。
【００５６】
同図に示すように、階層構造解析部２１は階層構造レイアウトデータＤＨに基づき階層構造を解析し階層構造解析情報Ｄ２１を出力する。逆階層構造生成部２２は階層構造解析情報Ｄ２１に基づき逆階層構造レイアウトデータＲＤＨを出力する。
【００５７】
図７は実施の形態２のレイアウトデータ変換装置の動作を示すフローチャートである。以下、同図を参照してその変換動作を説明する。まず、階層構造解析部２１による階層構造解析動作を説明する。
【００５８】
まず、ステップＳ２１で階層構造レイアウトデータＤＨから最上位のセルデータを検索し、ステップＳ２２で最上位のセルデータの子セル情報から下位のセルデータを検索する。
【００５９】
その後、ステップＳ２２で検出された下位のセルデータの子セル情報からより下位の階層データを検索する。検索した下位のセルデータがさらに子セル情報としてセルデータを有している場合はステップＳ２３の処理は再帰的に実行される。
【００６０】
そして、ステップＳ２４で最下位のセルデータとして基本要素データを検索する。なお、基本要素データは場合によってはステップＳ２１，Ｓ２２実行後に検索される場合もある。
【００６１】
ステップＳ２１〜Ｓ２４を経て、階層構造解析部２１は全ての基本要素データ及びセルデータの階層関係（親子関係）、各セルデータ固有の情報を含む階層構造解析情報Ｄ２１を得る。
【００６２】
次に、逆階層構造生成部２２による階層構造解析情報Ｄ２１に基づく逆階層構造レイアウトデータＲＤＨの生成動作に移行する。
【００６３】
ステップＳ２５において、基本要素データを作成する。基本要素データにおける図形データの情報等の固有情報は階層構造レイアウトデータＤＨの場合と変化はないが、新たに直接参照される親セル情報を付加することにより、逆階層構造の基本要素データを作成する。
【００６４】
その後、ステップＳ２６で基本要素データを参照するセルデータを作成する。この際、セルデータは基本要素データとの階層関係を示す子セル情報を持たさず、直接参照されるセルデータを示す親セル情報を付加する。
【００６５】
次に、ステップＳ２７でセルデータを参照するセルデータを作成する。この際、生成されるセルデータには参照するセルデータとの階層関係を示す子セル情報を持たさず、直接参照されるセルデータを示す親セル情報を付加する。生成したセルデータがさらに他のセルデータに参照される場合はステップＳ２７の処理は再帰的に実行される。
【００６６】
そして、ステップＳ２８で最上位のセルデータが生成される。この最上位のセルデータにも子セル情報を持たさない。
【００６７】
このように、実施の形態２のレイアウトデータ変換装置は、階層構造レイアウトデータＤＨを逆階層構造レイアウトデータＲＤＨに変換できるため、既存の階層構造のレイアウトデータを逆階層構造レイアウトデータとして活用することができる。
【００６８】
大多数の既存の設計レイアウトデータは、ＧＤＳ２ＳＴＲＥＡＭフォーマットに準拠した階層構造レイアウトデータとして保存されているため、実施の形態２のレイアウトデータ変換装置によって、既存の階層構造レイアウトデータとの互換性が確保できる。互換性が確保できれば、必要に応じて、従来の階層構造と本発明の逆階層構造との使い分けも可能となる。
【００６９】
＜実施の形態３＞
図８はこの発明の実施の形態３であるレイアウトデータ変換装置の構成を示すブロック図である。
【００７０】
同図に示すように、逆階層構造解析部３１は逆階層構造レイアウトデータＲＤＨに基づき逆階層構造を解析し逆階層構造解析情報Ｄ３１を出力する。階層構造生成部３２は逆階層構造解析情報Ｄ３１に基づき階層構造レイアウトデータＤＨを出力する。
【００７１】
図９は実施の形態３のレイアウトデータ変換装置の動作を示すフローチャートである。以下、同図を参照してその変換動作を説明する。まず、逆階層構造解析部３１による逆階層構造解析動作を説明する。
【００７２】
まず、ステップＳ３１で逆階層構造レイアウトデータＲＤＨから基本要素データを検索し、ステップＳ３２で基本要素データの親セル情報から、基本要素データを参照するセルデータを検索する。
【００７３】
その後、ステップＳ３２で検出されたセルデータの親セル情報から、より上位のセルデータを検索する。検索した上位のセルデータがさらに親セル情報としてセルデータを有している場合はステップＳ３３の処理は再帰的に実行される。
【００７４】
そして、ステップＳ３４において、セルデータの親セル情報を辿ることにより最上位のセルデータを検索する。なお、最上位のセルデータは場合によってはステップＳ３１，Ｓ３２実行後に検索される場合もある。
【００７５】
ステップＳ３１〜Ｓ３４を経て、逆階層構造解析部３１は全てのセルデータの階層関係（親子関係）、各セルデータ固有の情報を含む逆階層構造解析情報Ｄ３１を得る。
【００７６】
次に、階層構造生成部３２による逆階層構造解析情報Ｄ３１に基づく階層構造レイアウトデータＤＨ生成動作に移行する。
【００７７】
ステップＳ３５において、最上位のセルデータを作成する。この際、子セル情報を付加することにより、既存の階層構造に準拠した最上位セルデータを作成する。
【００７８】
その後、ステップＳ３６で最上位セルの子セル情報を参照して下位のセルデータを作成する。この際、セルデータには参照するセルデータの情報である子セル情報を付加する。
【００７９】
次に、ステップＳ３７でセルデータの子セル情報を参照して、より下位のセルデータを作成する。この際、参照するセルデータを示す子セル情報を付加する。生成したセルデータの子セル情報が他のセルデータを有する場合はステップＳ３７の処理は再帰的に実行される。
【００８０】
そして、ステップＳ３８で基本要素データを生成する。
【００８１】
このように、実施の形態３のレイアウトデータ変換装置は、逆階層構造レイアウトデータＲＤＨを階層構造レイアウトデータＤＨに変換できるため、既存の階層構造のレイアウトデータとの互換性が確保できる。互換性が確保できれば、必要に応じて、従来の階層構造と本発明の逆階層構造との使い分けも可能となる。
【００８２】
＜実施の形態４＞
図１０はこの発明の実施の形態４である占有率解析装置の構成を示すブロック図である。同図に示すように、逆階層構造解析部４１は逆階層構造レイアウトデータＲＤＨを受け、逆階層構造レイアウトデータＲＤＨに基づき逆階層構造解析情報Ｄ４１を出力する。図形検証部である占有率計算部４２は逆階層構造解析情報Ｄ４１に基づき占有率計算結果Ｄ４２を出力する。
【００８３】
なお、占有率解析装置は逆階層構造レイアウトデータＲＤＨを直接用いる構成でも、図１０に示すように、既存の階層構造レイアウトデータＤＨを正逆階層データ変換部２０によって変換された逆階層構造レイアウトデータＲＤＨを用いる構成のいずれでも良い。なお、正逆階層データ変換部２０としては実施の形態２のレイアウトデータ変換装置が該当する。
【００８４】
図１１は実施の形態４の占有率解析装置の占有率計算動作を示すフローチャートである。なお、図１１では既存の階層構造レイアウトデータＤＨを利用する図１０の構成に対応させている。以下、図１１を参照してその占有率計算動作を説明する。
【００８５】
まず、ステップＳ４１で、正逆階層データ変換部２０によって階層構造レイアウトデータＤＨを逆階層構造レイアウトデータＲＤＨに変換する。
【００８６】
続いて、逆階層構造解析部４１による逆階層構造レイアウトデータＲＤＨに基づく逆階層構造解析処理が行われる。
【００８７】
まず、ステップＳ４２で、基本要素データを抽出する。
【００８８】
次に、ステップＳ４３で、基本要素データの親セル情報に基づき上位のセルデータを検索する。
【００８９】
さらに、ステップＳ４４で、セルデータの親セル情報に基づきさらに上位のセルデータを検索する。検索したセルデータの親セルデータが存在すればステップＳ４４の処理は再帰的に実行される。
【００９０】
その後、ステップＳ４５で、親セル情報を辿って最終的に最上位のセルデータを検索する。なお、逆階層構造レイアウトデータＲＤＨの構造によっては、ステップＳ４２，Ｓ４３，実行後に直ちにステップＳ４５が実行されることもある。
【００９１】
最上位のセルデータが検索されると、最上位のセルデータによって規定される実空間領域が決定し、この実空間領域に少なくとも一つの基本要素データで規定される図形が用いられることになるため、図形検証の一つである占有率計算の対象となる。
【００９２】
続いて、占有率計算部４２による逆階層構造解析情報Ｄ４１に基づく占有率計算処理に移る。なお、本実施の形態では、実空間領域は複数のメッシュ領域から構成されるとしてメッシュ領域単位に処理を実行する。
【００９３】
まず、ステップＳ４６で、基本要素データで規定される図形の絶対座標を計算する。基本要素データから最上位セルデータに至る全てのセルデータの領域情報に基づき、実空間領域上における基本要素データで規定される図形の座標位置が決定する。
【００９４】
例えば、図５の例では、基本要素データＦ２で規定される図形が存在する絶対座標は、メモリセル７、メモリセルアレイ６、メモリ２及び半導体チップ１からなる階層構造が明確になった時点ではじめて確定し、半導体チップ１に形成されるメモリ２のメモリセルアレイ６における所定のメモリセル７の所定位置が基本要素データＦ２の形成位置となる。
【００９５】
ステップＳ４７において、選択されたメッシュ領域とステップＳ４６で絶対座標が確定した図形とが重複する領域を、メッシュ領域上における図形の占有領域として抽出する。
【００９６】
ステップＳ４７Ｃにおいて、全ての基本要素データの抽出の有無（Yes/No）がチェックされ、抽出されていない場合はステップＳ４２に戻る。以降、全ての基本要素データについてステップＳ４２〜Ｓ４７の処理が繰り返された後、ステップＳ４７ＣでYesとなり、ステップＳ４８に移行する。
【００９７】
ステップＳ４８において、２つの図形が同一領域上に重なって配置されていた場合、一方の図形の占有領域から重複部分を除去する占有領域変形処理が施される。
【００９８】
そして、ステップＳ４９において、ステップＳ４７，Ｓ４８を経て得られた占有領域の総面積に基づき、選択されたメッシュ領域における占有率を計算する。この際、ステップＳ４８で、占有領域変形処理が施されているため、２以上の図形が同一領域を占有した場合でも、各図形の占有領域を単純加算することによって占有領域の総面積を正確に求めることができる。
【００９９】
その後、ステップＳ４９Ｃで全てのメッシュ領域の占有率の計算終了の有無がチェックされ、また、計算が終了していないメッシュ領域があると判断されると、ステップＳ４９Ｍで新たなメッシュ領域を選択した後、ステップＳ４２に戻る。
【０１００】
そして、ステップＳ４９Ｃで全てのメッシュ領域の占有率の計算終了が判断されると、ステップＳ５０で全てのメッシュ領域それぞれの占有率に基づき全体占有率の計算を行い処理を終了する。
【０１０１】
既存の階層構造レイアウトデータＤＨに基づき、占有率計算を行う場合、上位のセルデータから順に階層を降りていき、基本要素データを検索した後、今度は階層を最上位まで辿って、ステップＳ４２〜Ｓ５０と同様な計算を行う必要がある。
【０１０２】
この際、一旦、階層構造を展開してフラットデータにする必要が生じるため、展開に要する処理時間や中間ファイル（作業領域）が膨大になり、処理不能になることもある。
【０１０３】
一方、本実施の形態では、逆階層構造レイアウトデータＲＤＨの基本要素データを用いるため、基本要素データから処理を開始して、簡単に上位のセルデータに辿っていくことにより、セルデータの検索処理が簡単になり、占有率計算を高速に行うことができる。
【０１０４】
また、実施の形態４では、階層構造レイアウトデータＤＨから逆階層構造レイアウトデータＲＤＨに変換する正逆階層データ変換部２０を有しているため、階層構造レイアウトデータＤＨが与えられた場合も同様に高速な占有率計算が可能となる。
【０１０５】
＜実施の形態５＞
図１２はこの発明の実施の形態５である占有率解析装置の構成を示すブロック図である。同図に示すように、逆階層構造解析部４１は逆階層構造レイアウトデータＲＤＨを受け、逆階層構造レイアウトデータＲＤＨに基づき逆階層構造解析情報Ｄ４１を出力する。占有率計算部５２は逆階層構造解析情報Ｄ４１に基づき占有率計算結果Ｄ５２を出力する。
【０１０６】
なお、占有率解析装置は逆階層構造レイアウトデータＲＤＨを直接用いる構成でも、図１２に示すように、既存の階層構造レイアウトデータＤＨを正逆階層データ変換部２０によって変換された逆階層構造レイアウトデータＲＤＨを用いる構成のいずれでも良い。なお、正逆階層データ変換部２０としては実施の形態２のレイアウトデータ変換装置が該当する。
【０１０７】
図１３は実施の形態５の占有率解析装置の占有率計算動作を示すフローチャートである。なお、図１３では既存の階層構造レイアウトデータＤＨを利用する図１２の構成に対応させている。以下、図１３を参照してその占有率計算動作を説明する。
【０１０８】
まず、ステップＳ５１で、正逆階層データ変換部２０によって階層構造レイアウトデータＤＨを逆階層構造レイアウトデータＲＤＨに変換する。
【０１０９】
続いて、逆階層構造解析部４１による逆階層構造レイアウトデータＲＤＨに基づき、実施の形態４と同様の逆階層構造解析処理が行われる。すなわち、図１３のステップＳ５２〜Ｓ５５の処理内容は、図１１のステップＳ４２〜Ｓ４５の処理内容と同様である。
【０１１０】
ステップＳ５５で最上位のセルデータが検索されると、最上位のセルデータによって規定される実空間領域が決定し、この実空間領域に少なくとも一つの基本要素データで規定される図形が用いられることになるため、占有率計算対象となる。
【０１１１】
続いて、占有率計算部５２による逆階層構造解析情報Ｄ４１に基づく占有率計算処理に移る。
【０１１２】
まず、ステップＳ５６で、基本要素データの絶対座標を計算する。基本要素データから最上位セルデータに至る全てのセルデータの領域情報に基づき、実空間領域上における基本要素データで規定される図形の絶対座標位置が決定する。
【０１１３】
ステップＳ５７において、選択されたメッシュ領域とステップＳ５６で絶対座標が確定した図形とが重複する領域を、メッシュ領域上における図形の占有領域として抽出する。
【０１１４】
ステップＳ５７Ｃにおいて、全ての基本要素データの抽出の有無（Yes/No）がチェックされ、抽出されていない場合はステップＳ５２に戻る。以降、全ての基本要素データについてステップＳ５２〜Ｓ５７の処理が繰り返された後、ステップＳ５７ＣでYesとなり、ステップＳ５８に移行する。
【０１１５】
ステップＳ５８において、２つの図形が同一領域上で重複した場合に、その重複部分を減算用図形として発生させる。
【０１１６】
そして、ステップＳ５９において、ステップＳ５７で抽出された占有領域を単純加算して得られる単純重複面積から、ステップＳ５８で得た減算用図形の面積を差し引くことにより、選択されたメッシュ領域における占有面積を簡単かつ正確に計算することができる。この際、個々の占有領域自体は変形を受けることはないため、個々の占有領域の形状が複雑化することはない。
【０１１７】
その後、ステップＳ５９Ｃで全てのメッシュ領域の占有率の計算終了の有無がチェックされ、また、計算が終了していないメッシュ領域があると判断されると、ステップＳ５９Ｍで新たなメッシュ領域を選択した後、ステップＳ５２に戻る。
【０１１８】
そして、ステップＳ５９Ｃで全てのメッシュ領域の占有率の計算終了が判断されると、ステップＳ６０で全てのメッシュ領域それぞれの占有率に基づき全体占有率の計算を行い処理を終了する。
【０１１９】
既存の階層構造レイアウトデータＤＨで、同様に占有率計算を行う場合は、階層構造を展開してフラットデータにする必要が生じるため、展開に要する処理時間や中間ファイル（作業領域）が膨大になり、処理不能になることもあった。
【０１２０】
一方、本実施の形態では、逆階層構造レイアウトデータＲＤＨの基本要素データから処理を開始することができるため、セルデータの検索処理が簡単になり、占有率計算を高速に行うことができる。
【０１２１】
また、実施の形態５では、階層構造レイアウトデータＤＨから逆階層構造レイアウトデータＲＤＨに変換する正逆階層データ変換部２０を有しているため、階層構造レイアウトデータＤＨが与えられた場合も同様に高速な占有率計算が可能となる。
【０１２２】
＜実施の形態６＞
図１４はこの発明の実施の形態６であるフーリエ解析装置の構成を示すブロック図である。同図に示すように、逆階層構造解析部４１は逆階層構造レイアウトデータＲＤＨを受け、逆階層構造レイアウトデータＲＤＨに基づき逆階層構造解析情報Ｄ４１を出力する。図形検証部であるフーリエ解析部６２は逆階層構造解析情報Ｄ４１に基づき解析結果Ｄ６２を出力する。
【０１２３】
なお、フーリエ解析装置は逆階層構造レイアウトデータＲＤＨを直接用いる構成でも、図１４に示すように、既存の階層構造レイアウトデータＤＨを正逆階層データ変換部２０によって変換された逆階層構造レイアウトデータＲＤＨを用いる構成のいずれでも良い。なお、正逆階層データ変換部２０としては実施の形態２のレイアウトデータ変換装置が該当する。
【０１２４】
図１５は実施の形態６のフーリエ解析装置のフーリエ解析動作を示すフローチャートである。なお、図１５では既存の階層構造レイアウトデータＤＨを利用する図１４の構成に対応させている。以下、図１５を参照してそのフーリエ解析動作を説明する。
【０１２５】
まず、ステップＳ６１で、正逆階層データ変換部２０によって階層構造レイアウトデータＤＨを逆階層構造レイアウトデータＲＤＨに変換する。
【０１２６】
続いて、逆階層構造解析部４１による逆階層構造レイアウトデータＲＤＨに基づき、実施の形態４と同様の逆階層構造解析処理が行われる。すなわち、図１５のステップＳ６２〜Ｓ６５の処理内容は、図１１のステップＳ４２〜Ｓ４５の処理内容と同様である。
【０１２７】
ステップＳ６５で最上位のセルデータが検索されると、最上位のセルデータによって規定される実空間領域が決定し、この実空間領域に少なくとも一つの基本要素データで規定される図形が用いられることになり、図形検証の一つであるフーリエ解析処理の対象となる。
【０１２８】
続いて、フーリエ解析部６２による逆階層構造解析情報Ｄ４１に基づくフーリエ解析処理に移る。
【０１２９】
まず、ステップＳ６６で、基本要素データの絶対座標を計算する。基本要素データから最上位セルデータに至る全てのセルデータの領域情報に基づき、実空間領域上における基本要素データの座標位置が決定する。
【０１３０】
ステップＳ６７において、実空間領域における選択されたメッシュ領域とステップＳ６６で座標位置が決定した図形との重複領域を占有領域として抽出する。
【０１３１】
ステップＳ６７Ｃにおいて、全ての基本要素データの抽出の有無（Yes/No）がチェックされ、抽出されていない場合はステップＳ６２に戻る。以降、全ての基本要素データについてステップＳ６２〜Ｓ６７の処理が繰り返された後、ステップＳ６７ＣでYesとなり、ステップＳ６８に移行する。
【０１３２】
ステップＳ６８において、２つの図形が同一領域上で重なって配置されていた場合、一方の図形の占有領域から重複部分を除去する占有領域変形処理が施される。
【０１３３】
そして、ステップＳ６９において、ステップＳ６７，Ｓ６８を経て得られた占有領域に基づき、選択されたメッシュ領域におけるフーリエ像を計算する。この際、ステップＳ６８で、占有領域変形処理が施されているため、２以上の図形が同一領域を占有した場合でも、各図形の占有領域を単純加算することによって占有領域が正確に決定する。
【０１３４】
その後、ステップＳ７０にフーリエ像を逆フーリエ変換する。このように、ステップＳ６９，Ｓ７０によるメッシュ領域単位でフーリエ解析処理の結果が解析結果Ｄ６２となる。
【０１３５】
その後、ステップＳ７０Ｃで全てのメッシュ領域におけるフーリエ解析処理終了の有無がチェックされ、また、計算が終了していないメッシュ領域があると判断されると、ステップＳ７０Ｍで新たなメッシュ領域を選択した後、ステップＳ６２に戻る。
【０１３６】
そして、ステップＳ７０Ｃで全てのメッシュ領域の解析終了が判断されると、処理を終了する。
【０１３７】
既存の階層構造レイアウトデータＤＨで、同様にフーリエ解析処理を行う場合は、階層構造を展開してフラットデータにする必要が生じるため、展開に要する処理時間や中間ファイル（作業領域）が膨大になり、処理不能になることもあった。
【０１３８】
一方、本実施の形態では、逆階層構造レイアウトデータＲＤＨの基本要素データを用いるため、セルデータの検索処理が簡単になり、フーリエ解析を高速に行うことができる。加えて、フーリエ解析を行うことにより、比較的長い距離間における物理現象に対しても解析することができる。
【０１３９】
また、実施の形態６では、階層構造レイアウトデータＤＨから逆階層構造レイアウトデータＲＤＨに変換する正逆階層データ変換部２０を有しているため、階層構造レイアウトデータＤＨが与えられた場合も同様に高速なフーリエ解析処理が可能となる。
【０１４０】
＜実施の形態７＞
図１６はこの発明の実施の形態７であるフーリエ解析装置の構成を示すブロック図である。同図に示すように、逆階層構造解析部４１は逆階層構造レイアウトデータＲＤＨを受け、逆階層構造レイアウトデータＲＤＨに基づき逆階層構造解析情報Ｄ４１を出力する。フーリエ解析部７２は逆階層構造解析情報Ｄ４１に基づき解析結果Ｄ７２を出力する。
【０１４１】
なお、フーリエ解析装置は逆階層構造レイアウトデータＲＤＨを直接用いる構成でも、図１６に示すように、既存の階層構造レイアウトデータＤＨを正逆階層データ変換部２０によって変換された逆階層構造レイアウトデータＲＤＨを用いる構成のいずれでも良い。なお、正逆階層データ変換部２０としては実施の形態２のレイアウトデータ変換装置が該当する。
【０１４２】
図１７は実施の形態７のフーリエ解析装置の占有率計算動作を示すフローチャートである。なお、図１７では既存の階層構造レイアウトデータＤＨを利用する図１６の構成に対応させている。以下、図１７を参照してそのフーリエ解析動作を説明する。
【０１４３】
まず、ステップＳ７１で、正逆階層データ変換部２０によって階層構造レイアウトデータＤＨを逆階層構造レイアウトデータＲＤＨに変換する。
【０１４４】
続いて、逆階層構造解析部４１による逆階層構造レイアウトデータＲＤＨに基づき、実施の形態４と同様の逆階層構造解析処理が行われる。すなわち、図１７のステップＳ７２〜Ｓ７５の処理内容は、図１１のステップＳ４２〜Ｓ４５の処理内容と同様である。
【０１４５】
ステップＳ７５で最上位のセルデータが検索されると、最上位のセルデータによって規定される実空間領域が決定し、この実空間領域に少なくとも一つの基本要素データで規定される図形が用いられることになるため、フーリエ解析の対象となる。
【０１４６】
続いて、フーリエ解析部７２による逆階層構造解析情報Ｄ４１に基づくフーリエ解析処理に移る。
【０１４７】
まず、ステップＳ７６で、基本要素データの絶対座標を計算する。基本要素データから最上位セルデータに至る全てのセルデータの領域情報に基づき、実空間領域上における基本要素データの座標位置が決定する。
【０１４８】
ステップＳ７７において、実空間領域における選択されたメッシュ領域とステップＳ７６で絶対位置が決定した図形との重複領域を占有領域として抽出する。
【０１４９】
ステップＳ７７Ｃにおいて、全ての基本要素データの抽出の有無（Yes/No）がチェックされ、抽出されていない場合はステップＳ７２に戻る。以降、全ての基本要素データについてステップＳ７２〜Ｓ７７の処理が繰り返された後、ステップＳ７７ＣでYesとなり、ステップＳ７８に移行する。
【０１５０】
ステップＳ７８において、２つの図形が同一領域上で重複した場合に、その重複部分を減算用図形として発生させる。
【０１５１】
そして、ステップＳ７９において、ステップＳ７７で抽出された占有領域を単純加算して得られる単純重複面積から、ステップＳ７８で得た減算用図形の面積を差し引くことにより、選択されたメッシュ領域における総占有領域を簡単かつ正確に得、当該総占有領域のフーリエ像を計算する。この際、個々の占有領域自体は変形を受けることはないため、個々の占有領域の形状が複雑化することはない。
【０１５２】
その後、ステップＳ８０でフーリエ像を逆フーリエ変換する。これらステップＳ７８，Ｓ７９の処理によって得られる結果が解析結果Ｄ７２となる。
【０１５３】
続いて、ステップＳ８０Ｃで全てのフーリエメッシュ領域の占有率の計算終了の有無がチェックされ、また、フーリエ解析が終了していないメッシュ領域があると判断されると、ステップＳ８０Ｍで新たなメッシュ領域を選択した後、ステップＳ７２に戻る。
【０１５４】
そして、ステップＳ８０Ｃで全てのメッシュ領域の解析終了が判断されると、処理を終了する。
【０１５５】
既存の階層構造レイアウトデータＤＨで、同様にフーリエ解析を行う場合は、階層構造を展開してフラットデータにする必要が生じるため、展開に要する処理時間や中間ファイル（作業領域）が膨大になり、処理不能になることもあった。
【０１５６】
一方、本実施の形態では、逆階層構造レイアウトデータＲＤＨの基本要素データを用いるため、セルデータの検索処理が簡単になり、フーリエ解析処理を高速に行うことができる。
【０１５７】
また、実施の形態７では、階層構造レイアウトデータＤＨから逆階層構造レイアウトデータＲＤＨに変換する正逆階層データ変換部２０を有しているため、階層構造レイアウトデータＤＨが与えられた場合も同様に高速なフーリエ解析処理が可能となる。
【図面の簡単な説明】
【０１５８】
【図１】この発明の実施の形態１であるレイアウトデータの保存方式を示す説明図である。
【図２】逆階層構造のレイアウトデータ生成方法を示すフローチャートである。
【図３】実施の形態１であるレイアウトデータの保存状態を示す説明図である。
【図４】実施の形態１であるレイアウトデータの保存状態をツリー形式で示す説明図である。
【図５】レイアウトデータにおける階層構造を例示する説明図である。
【図６】この発明の実施の形態２であるレイアウトデータ変換装置の構成を示すブロック図である。
【図７】実施の形態２のレイアウトデータ変換装置の動作を示すフローチャートである。
【図８】この発明の実施の形態３であるレイアウトデータ変換装置の構成を示すブロック図である。
【図９】実施の形態３のレイアウトデータ変換装置の動作を示すフローチャートである。
【図１０】この発明の実施の形態４である占有率解析装置の構成を示すブロック図である。
【図１１】実施の形態４の占有率解析装置の占有率計算動作を示すフローチャートである。
【図１２】この発明の実施の形態５である占有率解析装置の構成を示すブロック図である。
【図１３】実施の形態５の占有率解析装置の占有率計算動作を示すフローチャートである。
【図１４】この発明の実施の形態６であるフーリエ解析装置の構成を示すブロック図である。
【図１５】実施の形態６のフーリエ解析装置のフーリエ解析動作を示すフローチャートである。
【図１６】この発明の実施の形態７であるフーリエ解析装置の構成を示すブロック図である。
【図１７】実施の形態７のフーリエ解析装置のフーリエ解析動作を示すフローチャートである。
【図１８】従来のレイアウトデータの保存状態を示す説明図である。
【図１９】従来のレイアウトデータの保存状態をツリー形式で示す説明図である。
【符号の説明】
【０１５９】
１１  基本要素データ記述部、１２，１３  セルデータ記述部、１４  最上位セルデータ記述部、２０  正逆階層データ変換部、２１  階層構造解析部、２２  逆階層構造生成部、３１，４１  逆階層構造解析部、３２  階層構造生成部、４２，５２  占有率計算部、６２，７２  フーリエ解析部。
【図１】
0004298783.tif 000002
【図２】
0004298783.tif 000003
【図３】
0004298783.tif 000004
【図４】
0004298783.tif 000005
【図５】
0004298783.tif 000006
【図６】
0004298783.tif 000007
【図７】
0004298783.tif 000008
【図８】
0004298783.tif 000009
【図９】
0004298783.tif 000010
【図１０】
0004298783.tif 000011
【図１１】
0004298783.tif 000012
【図１２】
0004298783.tif 000013
【図１３】
0004298783.tif 000014
【図１４】
0004298783.tif 000015
【図１５】
0004298783.tif 000016
【図１６】
0004298783.tif 000017
【図１７】
0004298783.tif 000018
【図１８】
0004298783.tif 000019
【図１９】
0004298783.tif 000020