(57)【特許請求の範囲】
【請求項１】
階層設計されたマスクパターンデータを構成する複数のストラクチャからパターンに重なりのない露光データを作成するための階層データを作成するデータ作成方法であって、
前記マスクパターンデータから検出した重なり合うパターンの階層間の重なり情報を作成する第１ステップと、
前記重なり情報に基づいて、前記重なり合うパターンのうち低い優先度が設定されているパターンを持ち上げて候補パターンデータ及び削除パターンデータを作成する第２ステップと、
前記候補パターンデータから削除パターンデータを削除して重なりのないパターンデータを作成する第３ステップと
を有し、
前記第１ステップは、
前記重なり合うパターンの所属するストラクチャ同士が異なる場合には、該ストラクチャ内に配置されている、前記重なり合うパターンと同じパターンがより多数存在するパターンに対してより高い優先度を設定するステップと、
前記優先度に応じて前記重なり情報を作成するステップと
を含むことを特徴とするデータ作成方法。
【請求項２】
請求項１に記載のデータ作成方法において、
前記重なり合うパターンの配置個数が同じ場合には、該重なり合うパターンのうち頂点の多いパターンに対して高い優先度を設定することを特徴とするデータ作成方法。
【請求項３】
請求項１に記載のデータ作成方法において、
前記第２ステップは、
前記重なり情報に基づいて、前記候補パターンデータ及び削除パターンデータを各階層単位に作成するステップを有することを特徴とするデータ作成方法。
【請求項４】
請求項１に記載のデータ作成方法において、
前記第３ステップでは、
サイジングしない場合は、各階層毎に候補パターンデータから削除パターンデータを削除して階層データを作成し、
サイジングする場合は、各階層毎に候補パターンデータと削除パターンデータをそれぞれサイジング後、各階層毎に候補パターンから削除パターンを削除して階層データを作成することを特徴とするデータ作成方法。
【請求項５】
請求項１に記載のデータ作成方法において、
前記第１ステップでは、前記重なり合うパターンを含まない非侵入領域を設定し、
前記第２ステップでは、前記非侵入領域に含まれる削除パターンを持ち上げないことを特徴とするデータ作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は階層設計された半導体集積回路装置のマスクパターンデータからパターンの重なり合いを除去した露光データ、それを作成するための階層データを作成するデータ作成方法に関するものである。
【０００２】
半導体集積回路用露光データ（以後、単に露光データと呼ぶ）をマスクウエハに露光する過程において、露光データにパターンの重なり（オーバーラップ）があると多重露光になる。このことから、パターンのオーバーラップをなくした露光データが必要になる。このため、階層化設計された半導体集積回路用マスクパターンデータ（以後、単にマスクパターンデータと呼ぶ）に対してオーバーラップ除去処理を実施した後、そのデータをフォーマット変換処理して露光データを作成する方法が採られている。
【０００３】
近年の半導体集積回路（ＬＳＩ）においては、大規模化及び高集積化が進められ、そのＬＳＩを作成するために必要なマスクパターンデータ、露光データのデータ量も増大している。そのため、マスクパターンデータ及び露光データを階層化し、繰り返し性のあるパターンに対してマトリックス状のパターンデータを作成することで、データ量を削減している。しかし、マトリックス状のパターンデータの一部に重なりがあると、上記のオーバーラップ除去処理において繰り返し性が保存されない、即ちマトリックス状のパターンデータを展開して重なりを除去しなければならないため、処理後にデータ量の増加と露光データへの変換時間が長くなる。このため、繰り返し性を保持した露光データ作成用のデータを作成することが求められている。
【０００４】
【従来の技術】
従来、露光データを作成する第１の方法として、階層化設計されたマスクパターンデータの全てを展開し、予めパターンの重なりをなくした露光データ作成用データを作成する。その後、重なりのない露光データ作成用データを露光データにフォーマット変換し、それを露光装置に入力する方法が用いられてきた。
【０００５】
階層化設計されたマスクパターンデータは、次の特徴を持ち、このような構造を階層構造と呼ぶ。
（ａ）階層構造はストラクチャの単位で表現される。
（ｂ）ストラクチャの内容は、パターンと他のストラクチャの配置情報から成る。
（ｃ）同じ名前を持つストラクチャは必ず同じパターンとストラクチャの配置情報から構成される。
【０００６】
マスクパターンデータは、図３６（ａ）に示す構造木で表される階層構造を持ち、図３６（ｂ）に示すように各ストラクチャ及びパターンが配置される。このような階層構造におけるストラクチャの関係は親子関係等、家系図と同じ呼び方で表現される。
【０００７】
図３６（ａ），（ｂ）のマスクパターンデータを用いて説明すると、マスクパターンデータは、ストラクチャＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，ＧとパターンＰ，Ｑ，Ｒから構成されている。尚、図３６（ａ）では、ストラクチャを丸で囲み、パターンを四角で囲んで区別している。尚、この表記は、以下の説明において共通に用いられる。
【０００８】
ストラクチャの関係を説明すると、例えばストラクチャＢはストラクチャＡの子ストラクチャ、ストラクチャＤはストラクチャＢの子ストラクチャである。逆に、ストラクチャＡはストラクチャＢの親ストラクチャ、ストラクチャＢはストラクチャＤの親ストラクチャである。更に、ストラクチャＡ，ＢはストラクチャＣの先祖ストラクチャであり、ストラクチャＤ，ＥはストラクチャＡの子孫ストラクチャである。ストラクチャＤは、ストラクチャＡの直系関係にあり、ストラクチャＣの傍系関係にある。特に、最上階のストラクチャＡはトップストラクチャと呼ばれることがある。
【０００９】
このような階層化設計は、半導体集積回路の大規模化にともない設計の容易化やデータ量の削減などを目的として行われる。
しかし、半導体集積回路の大規模化に伴い、マスクパターンデータを全展開して重なりを無くした露光データ作成用データを作成する方法では、作成処理時に必要な作業領域、作成された露光データ作成用データのデータ量が膨大になるうえ、作成処理に時間がかかってしまう。
【００１０】
また、露光データ作成用データを露光データに変換する課程でも、作成時間の短縮、データ量の削減のため階層構造を利用した処理が行われることが多い。従って、露光データ作成用データが階層構造を持つことは非常に重要である。
【００１１】
そこで、マスクパターンデータの階層構造を利用し、全展開処理を行わずに重なりのない露光データ作成用階層データ（以下、単に階層データと呼ぶ）を作成する第２の方法が考えられる。
【００１２】
この第２の方法は、マスクパターンデータの重なりパターンを同じストラクチャのパターンとして階層を構成し直し、重なりのない階層データを作成する方法である。例えば、図３７に示すようにレイアウトされるマスクパターンデータは、図３８に示す階層構造を持つ。マスクパターンデータはストラクチャＡ〜Ｅから構成され、ストラクチャＣ，Ｄ，ＥはそれぞれパターンＲ，Ｓ，Ｔ、パターンＰ，Ｑ、パターンＵ，Ｖを持つ（図３９参照）。
【００１３】
このマスクパターンデータにおいて、左端列上段及び下段のストラクチャＣが持つパターンＳとストラクチャＤが持つパターンＱが重なり合い、右端列上段及び下段のストラクチャＣが持つパターンＳとストラクチャＥが持つパターンＵが重なり合っている（図において破線の丸にて重なり部分を示す）。従って、第２の方法では、重なり合うパターンＱ及びＳ、パターンＳ及びＵを共通の先祖ストラクチャＡに展開する。以降、先祖のストラクチャにパターンを展開することを、パターンを先祖のストラクチャに持ち上げると呼ぶことにする。
【００１４】
ところで、マスクパターンデータは、マトリックス状に配置された１２個のストラクチャＣを持つ。従って、一部のストラクチャＣからパターンＳを先祖ストラクチャＡに持ち上げると、パターンＳを持つストラクチャＣとそれを持たないストラクチャＣが共存することになり、矛盾が生じてしまう。これを避けるために、パターンＱまたはＵと直接重なっていないパターンＳもストラクチャＢ（又はストラクチャＡ）に持ち上げる。その結果、図４０〜図４２の階層データとなる。図４０は階層データのレイアウト図、図４１は階層データの階層木図、図４２は各ストラクチャが持つパターンのレイアウト図である。
【００１５】
尚、図４０〜図４２では、構成を変更したストラクチャと元のストラクチャの階層関係を解りやすくするために同じ符号を付している。そして、持ち上げられたパターン又はＯＲ処理したパターンは、元のパターンが解りやすいように符号を付している。即ち、図４１のパターンＱＳ１，ＱＳ２はパターンＱとパターンＳを、パターンＳＵ１，ＳＵ２はパターンＳとパターンＵをそれぞれＯＲ処理（論理和演算）したものである。また、パターンＳ１〜Ｓ８は、元のパターンＳ（但し重なり合いのないもの）をストラクチャＢに持ち上げて展開したパターンである。尚、パターンＳをストラクチャＢに持ち上げるのは、一般にデータ量がストラクチャＡに持ち上げる場合に比べて少なくなるからである。
【００１６】
このように階層構造を変更し、各ストラクチャ単位（各階層単位）でＯＲ処理を行い重なりのない階層データを作成する。
この方法により作成された階層データのパターンデータ量は、全展開した場合と比較して大幅な削減になっている。
【００１７】
一般に、パターンは頂点（又は線分）により表現されているので、パターンデータ量は各パターンの頂点の合計数に比例する。図４０に示す第２の方法で作成されたデータと、図４３に示す第１の方法により展開して作成されたデータでパターン頂点数を比較する。第２の方法でデータを作成した場合、パターンＱＳ１，ＱＳ２，ＳＶ１，ＳＶ２でそれぞれ頂点数８、パターンＳ１〜Ｓ８，Ｐ，Ｒ，Ｔ，Ｖがそれぞれ頂点数４であるため、頂点数の合計は８０個になる。一方、第１の方法でデータを作成した場合のパターンの頂点数は、頂点数４のパターンが４０個、頂点数８のパターン（凹形状パターン）が４個で合計１９２個になる。このように、第２の方法は第１の方法に比べて大幅なデータ量削減になっている。
【００１８】
【発明が解決しようとする課題】
しかし、第２の方法においても、データによってはパターンデータ量の削減が充分でなく、階層データのデータ量が増大する。上記では、繰り返し性のあるパターンＲ，Ｓ，Ｔを持つストラクチャＣからパターンＳをストラクチャＢに持ち上げているため、パターンＳについて繰り返し性を保持することができない。このため、例えばストラクチャＣが１２（＝３×４）個でなくもっと多い数、例えば３０６（３×１０２）個の場合、ストラクチャＢに３０２個のパターンＳが展開されるため、このパターンの頂点数だけでも１０２８個（＝４×３０２）となるので、パターンの頂点数の合計は１２５６個になる。このように、第２の方法においても、データ量が増大するという問題がある。
【００１９】
また、繰り返し性を保持したデータを作成することができないため、階層データから露光データに変換する処理の処理効率の低下を招く。露光データとして例えばブロック露光用データを作成する場合、階層データから露光データへ変換する処理で、繰り返しパターンを抽出する処理がある。この抽出処理において、持ち上げたパターン（図４２におけるパターンＳ１〜Ｓ８）から繰り返しパターン（図４２のパターンＳ２〜Ｓ７）を抽出する。これらのパターンは、元々繰り返し性を持っていたパターンであるため２度手間（展開と抽出）なり、変換に要する処理時間、ひいてはマスクパターンデータから露光データを作成するまでの全体の処理時間が長くなるという問題がある。
【００２０】
本発明は上記問題点を解決するためになされたものであって、その目的は階層化設計されたマスクパターンデータにおける繰り返し性を保持して露光データを作成するための階層データを作成するとともに、その階層データのデータ量削減を図ることのできるデータ作成方法を提供することにある。
【００２１】
【課題を解決するための手段】
上記目的を達成するため、請求項１に記載の発明は、階層設計されたマスクパターンデータを構成する複数のストラクチャからパターンに重なりのない露光データを作成するための階層データを作成するデータ作成方法であって、前記マスクパターンデータから検出した重なり合うパターンの階層間の重なり情報を作成する第１ステップと、前記重なり情報に基づいて、前記重なり合うパターンのうち低い優先度が設定されているパターンを持ち上げて候補パターンデータ及び削除パターンデータを作成する第２ステップと、前記候補パターンデータから削除パターンデータを削除して重なりのないパターンデータを作成する第３ステップとを有し、前記第１ステップは、前記重なり合うパターンの所属するストラクチャ同士が異なる場合には、該ストラクチャ内に配置されている、前記重なり合うパターンと同じパターンがより多数存在するパターンに対してより高い優先度を設定するステップと、前記優先度に応じて前記重なり情報を作成するステップとを含む。このように、重なり情報に基づいて作成した候補パターンデータと削除パターンデータとから重なりのないパターンデータを作成することで、マスクパターンデータの階層構造をほぼ保持したまま階層データを作成することができる。
【００２２】
また、請求項２に記載の発明のように、前記重なり合うパターンの配置個数が同じ場合には、該重なり合うパターンのうち頂点の多いパターンに対して高い優先度を設定する。
【００２３】
前記第２ステップは、請求項３に記載の発明のように、前記重なり情報に基づいて、前記候補パターンデータ及び削除パターンデータを各階層単位に作成するステップを有する。
【００２４】
前記第３ステップでは、請求項４に記載の発明のように、サイジングしない場合は、各階層毎に候補パターンデータから削除パターンデータを削除して階層データを作成し、サイジングする場合は、各階層毎に候補パターンデータと削除パターンデータをそれぞれサイジング後、各階層毎に候補パターンから削除パターンを削除して階層データを作成する。これにより、正しくサイジングした階層データを作成することができる。
【００２５】
請求項５に記載の発明のように、前記第１ステップでは、前記重なり合うパターンを含まない非侵入領域を設定し、前記第２ステップでは、前記非侵入領域に含まれる削除パターンを持ち上げない。これにより、繰り返し性のある削除パターンのうち、非侵入領域に含まれる削除パターンを持ち上げないことで、ストラクチャに展開する削除パターンのデータ量が少なくなる。
【００２６】
【発明の実施の形態】
以下、本発明を具体化した一実施の形態を図１〜図３５に従って説明する。
図２は、本実施形態の露光データ作成装置のハードウエア構成を概略的に示すブロック図である。
【００２７】
露光データ作成装置１は、中央処理装置（以下、ＣＰＵという）２と、それに接続された端末装置３，ディスク装置４，メモリ装置５を含む。
端末装置３は、ユーザからの要求や指示，パラメータの入力等に用いるキーボード，マウス装置（図示せず）等の入力装置と、パターン画像，処理結果，等の表示に用いるＶＤＴ，モニタ，プリンタ等の表示装置を含む。
【００２８】
ディスク装置４は、通常、磁気ディスク装置、光ディスク装置、光ディスク装置等の記憶装置であり、これには図１に示す露光データ作成処理のためのプログラムデータ及び第１〜第８ファイル１１〜１８が格納され、ＣＰＵ２は、端末装置３の操作に応答して起動し、図１のステップに従って露光データ作成処理を実行する。尚、図１の各ファイル１１〜１８は、異なる記憶装置またはメモリ装置５に作成されても良く、また、各ファイル１１〜１８が複数の記憶装置にまたがって作成される構成としても良い。
【００２９】
メモリ装置５は記憶装置であり、ディスク装置４に比べ高速なアクセスを提供するが、容量が小さい。従って、ＣＰＵ２は、処理過程のサイズの小さいデータを高速アクセスする目的でメモリ装置５を用いる。尚、図１の内部データを格納するファイル１２を、このメモリ装置５に作成しても良い。
【００３０】
露光データ作成処理のためのプログラムデータは、記録媒体６を用いて提供される。記録媒体６は、フレキシブルディスク、ＣＤ−ＲＯＭ、ハードディスク、メモリカード、ＲＯM、パンチカード、テープ等のコンピュータ読み取り可能な媒体である。
【００３１】
尚、記録媒体６には、通信媒体を介して提供されるプログラムデータを格納した他の計算機の主記憶装置（メモリ装置等）、補助記憶装置（ディスク装置）やその計算機にて読み取られる可搬型媒体を含む。更に、コンピュータによって直接実行可能なプログラムを記録した記録媒体だけでなく、いったん他の記録媒体（ハードディスク等）にインストールすることによって実行可能となるようなプログラムを記録した記録媒体や、暗号化されたり、圧縮されたりしたプログラムを記録した記録媒体も含む。
【００３２】
提供されたプログラムデータは、記録媒体６から一旦ディスク装置４にコピーまたはインストール後にメモリ装置５にロードされ、または記録媒体６から直接メモリ装置５にロードされ実行する。また、通信媒体を介して接続される他の計算機に格納されて提供された場合も、他の装置から通信媒体を介して受信後にディスク装置４にコピーまたはインストールされ、メモリ装置５にロードされ実行するものである。
【００３３】
次に、露光データ作成処理の概要を図１のフロー図に従って第１〜第８ファイル１１〜１８に予め格納されるデータ、または露光データ作成処理において格納されるデータと共に説明する。
【００３４】
第１ファイル１１には、露光データ作成処理の入力データとしてマスクパターンデータが格納されている。マスクパターンデータは、予め論理回路データに基づいてトランジスタ等の素子，各種セル，それらを接続する信号配線等のパターンデータにより構成され、それらパターンデータは階層構造を持つ。
【００３５】
ステップ２１において、図２のＣＰＵ２は、階層化設計されたマスクパターンデータを読み込み、各ストラクチャ（各階層）毎にＯＲ処理を行い、同じストラクチャ内（同じ階層内）で重なりを無くしたパターンデータと配置データを作成し、それらを第２及び第３ファイル１２，１３にそれぞれ格納する。また、このステップ２１において、ＣＰＵ２は、マスクパターンデータの階層解析を行い、各ストラクチャが保有するパターン数、各ストラクチャの配置個数、各ストラクチャをトップとして考えて展開した場合のパターン数などの情報を求める。これらの情報はマスクパターンデータの階層木を探索することにより、実際に全展開することなく求める。
【００３６】
ステップ２２において、図２のＣＰＵ２は、パターンの重なり情報を収集し、単独持ち上げ情報、連結持ち上げ情報、代表情報、非侵入領域を作成する。単独持ち上げ情報、連結持ち上げ情報は、
（１）重なりパターンの所属するストラクチャのストラクチャ名が同じ場合、
（２−Ａ）重なりパターンの所属するストラクチャのストラクチャ名が違う場合で直系関係にある場合、
（２−Ｂ）重なりパターンの所属するストラクチャのストラクチャ名が違う場合で傍系関係にある場合、
の３つの場合に応じて作成する。
【００３７】
ステップ２３において、図２のＣＰＵ２は、ステップ２２にて作成した情報をもとに、重なりパターンの単独持ち上げ、連結持ち上げを行い作成した候補パターンデータ、削除パターンデータを第４，第５ファイル１４，１５に格納する。候補パターンデータ及び削除パターンデータは、重なりを解消するために図形論理減算処理（ＳＵＢ処理）を実施する対象のパターンデータである。
【００３８】
候補パターンデータは、パターンの重なりを解消するために先祖ストラクチャに持ち上げたデータであり、削除パターンデータは候補パターンデータから重なり合う部分を除くためにその候補パターンデータと同じストラクチャに複写したデータである。従って、削除パターンデータに指定された元のパターンデータには構造の変更が加えられないので、そのパターンを含むストラクチャの繰り返し性が保持されることになる。
【００３９】
ステップ２４において、図２のＣＰＵ２は、第４及び第５ファイル１４，１５の候補パターンデータ、削除パターンデータに対してＯＲ処理、サイジング処理、ＳＵＢ処理を実施して作成したパターンデータを第６ファイル１６に格納する。このＳＵＢ処理によって、候補パターンデータから削除パターンデータと重なり合う部分が除かれて重なりのないパターンデータが作成される。
【００４０】
ステップ２５において、図２のＣＰＵ２は、ステップ２４において作成した重なりのないパターンデータと第３ファイル１３の配置データを使い、パターンの重なりを除いた階層データを作成する。そして、ＣＰＵ２は、作成した階層データを第７ファイル１７に格納する。
【００４１】
ステップ２６において、図２のＣＰＵ２は、ステップ２５において作成した階層データをフォーマット変換して露光データを作成し、その露光データを第８ファイル１８に格納する。
【００４２】
上記ステップ２１〜２５の処理を図３７のマスクパターンデータに対して実施した場合について説明する。
図３は、処理後即ち重なりを無くした階層データのレイアウト図、図４はその階層木図、図５は処理後の階層データを構成するストラクチャＡ，Ｃ，Ｄ，Ｅが持つパターンのレイアウト図である。尚、図３〜図５に示すストラクチャＡ〜Ｅは、上記処理により構成が変更されたものがあるが、これ以降の説明において作成前後の対応を解りやすくするために同じ符号を用いることにする。
【００４３】
先ず、ステップ２２，２３において、図２のＣＰＵ２は、重なり合うパターンＱ及びＳ、パターンＳ及びＵを検出し、それぞれに対応する情報を作成する。そして、ＣＰＵ２は、作成した情報を基に候補パターンデータ及び削除パターンデータを作成する。図３７のマスクパターンデータでは、パターンＱとパターンＳの配置個数、パターンＵとパターンＳの配置個数を比較し、配置個数の少ないパターンＱ，Ｕを候補パターンとしてパターンＱ及びＳ、パターンＵ及びＳの共通の先祖であるストラクチャＡに展開した候補パターンデータ１４を作成する。そして、ＣＰＵ２は、候補パターンデータ１４に重なるパターンＳを削除パターンとしてそのデータ１５を作成する。配置個数の少ないパターンを候補パターンデータとすることで、ストラクチャに展開するパターンのデータ量が少なくなる。
【００４４】
次に、ステップ２４において、ＣＰＵ２は、候補パターンデータ１４と削除パターンデータ１５の重なり部分を候補パターンデータから切り取ったパターンＱＳ１，ＱＳ２，ＳＵ１，ＳＵ２（図２参照）のデータを作成する。これにより、作成された階層データの各ストラクチャは、図４及び図５に示すように、ストラクチャＡはパターンＱＳ１，ＱＳ２，ＳＵ１，ＳＵ２を、ストラクチャＤはパターンＰを、ストラクチャＥはパターンＶを持つ。そして、ストラクチャＢ及びＣは構成が変更されていない。即ち、ストラクチャＣ（パターンＲ，Ｓ，Ｔ）の繰り返し性は保持されている。
【００４５】
従って、上記の処理後の階層データが持つパターンの頂点数の合計は、パターンＱＳ１，ＱＳ２，ＳＵ１，ＳＵ２がそれぞれ頂点数８、パターンＰ，Ｒ，Ｓ，Ｔ，Ｖがそれぞれ頂点数４であるため、５２個である。上記したように、第１の従来方法では頂点数の合計が１５２６個、第２の従来方法ではそれが８０個であった。
【００４６】
このように、本実施形態によれば、従来の方法に比べて階層データのデータ量を大幅に削減できる。また、ストラクチャＣ（パターンＲ，Ｓ，Ｔ）の繰り返し性が保持されているので、階層データから露光データに変換する処理に要する時間が短い、即ち処理効率を上げることができる。
【００４７】
次に、上記各処理を順に詳述する。尚、図１に示すファイル１１〜１８及び各処理を説明する上で必要なファイルに格納するデータに、それを格納するファイルの符号を付して説明する。
【００４８】
先ず、ステップ２２の処理を詳述する。
図６は、ステップ２２において、重なり状況により単純持ち上げ情報、連結持ち上げ情報、代表情報を作成する情報作成処理（情報作成手段）のフロー図である。即ち、図６のステップ３１〜３４は、ステップ２２のサブステップの一部である。尚、この情報作成処理を説明するにあたって、図７〜図１０を用いる。
【００４９】
ＣＰＵ２は、処理する入力パターンデータ１２を構成するストラクチャをボトムアップ（階層木のボトム（最下層）のストラクチャから順番に上に向かって）で順次選出し、その選出したストラクチャが持つパターンに対して他のストラクチャに含まれるパターンの重なりがあるか否かを判断する。そして、パターンの重なりがある場合に、選出したストラクチャのパターンに対して作成した情報を追加する。そして、ＣＰＵ２は、ストラクチャの種類全て、即ちストラクチャの種類分処理をループして重なりを判定すると、この情報作成処理を終了して元に戻る。
【００５０】
詳述すると、ステップ３１は終了判定処理であり、ＣＰＵ２は、全てのストラクチャ種類について処理を終了したか否かを判断し、終了していない場合はストラクチャの全ての種類でループするべくステップ３２に進み、全ての種類について処理を終了したときには処理を終了して呼び出し元へ戻る。
【００５１】
ステップ３２において、ＣＰＵ２は、選出したストラクチャをトップストラクチャと見なし、スイープ法を使い重なりを調査する。重なりの調査は、子ストラクチャの存在領域の枠、パターンの存在領域の枠を置き、重なり判定をする。重なりありの場合、子ストラクチャの存在領域の枠を孫ストラクチャ存在領域の枠、パターン存在領域の枠で置き換える。ＣＰＵ２は、この操作を行い、最終的にパターン存在領域の枠をパターンデータに置き換え、パターンの重なりを検出する。
【００５２】
ここで、ストラクチャの存在領域とは、そのストラクチャを全展開した場合のパターンの存在する領域を示す枠のことである。以後、単に枠と呼ぶことにする。また、枠の重なり判定は、幾何学的に重なりがあるかどうかに加え、枠がどのようなグループに所属するかの識別番号でも判断する。
【００５３】
この識別番号を使うことにより、多重に重なりを調査することを防ぐことができ、共通の先祖で最も近縁のストラクチャが選出されたストラクチャとなるパターンの重なりだけを見つけることができる。
【００５４】
この識別番号は次のように与えられる。選出されたストラクチャとその子ストラクチャの枠には、全て異なる識別番号を与える。選出されたストラクチャとその子ストラクチャ以外のストラクチャ（孫、曾孫ストラクチャなど）の枠には、親ストラクチャと同じ識別番号を与える。また、パターンの枠には、所属ストラクチャと同じ識別番号を与える。
【００５５】
例えば、図７，８に示すパターンデータにおいて重なりを見つける手順を説明する。
このパターンデータの構造を説明すると、図８に示すように、ストラクチャＡは２個の子ストラクチャＢを持ち、ストラクチャＢは２個の子ストラクチャＣを持ち、ストラクチャＣはパターンＰ，Ｑを持つ。
【００５６】
図７右下に示すように、ストラクチャＢが持つ２つのストラクチャＣに重なりがあり、２つのストラクチャＣが持つパターンＰがストラクチャＢにおいて重なっている。更に、図７左上に示すように、ストラクチャＡが持つ２つのストラクチャＢに重なりがある。
【００５７】
ＣＰＵ２は、ボトムアップでストラクチャＣ，Ｂ，Ａの順にストラクチャを選出する。
先ず、最初に選出したストラクチャＣはボトムストラクチャであるので、ＣＰＵ２は重なりを調べない。
【００５８】
次に、ＣＰＵ２は、選出したストラクチャＢの重なりを調べる。図９（ａ）〜（ｃ）はストラクチャＢの重なりを調べる場合の説明図である。
図９（ａ）において、ＣＰＵ２は、ストラクチャＢに子ストラクチャＣの枠を置き、子ストラクチャの枠に異なる識別番号１，２を与える。与えた識別番号に括弧付して図中に示す。ストラクチャＣの枠は幾何学的な重なりと異なる識別番号を持つので重なりありとなる。
【００５９】
図９（ｂ）において、ＣＰＵ２は、ストラクチャＢに子ストラクチャＣが持つパターンＰ，Ｑの枠を置き、パターンＰ，Ｑの枠にそれぞれ所属ストラクチャＣと同じ識別番号１，２を与える。パターンＰの枠は幾何学的な重なりと異なる識別番号を持つので、ＣＰＵ２は「重なりあり」と判定する。一方、パターンＱの枠は幾何学的な重なりがないので、ＣＰＵ２は「重なりなし」と判定する。
【００６０】
図９（ｃ）において、ＣＰＵ２は、「重なりあり」と判定したパターンＰの枠により最後にパターンＰのパターンデータ（線分データなど）を比較し、その比較結果に基づいてパターンＰに「重なりあり」と判定し、重なりを確定する。
【００６１】
次に、ストラクチャＡにおける重なりを調べる場合について説明する。図１０（ａ）〜（ｄ）はストラクチャＡの重なりを調べる場合の説明図である。
図１０（ａ）において、ＣＰＵ２は、ストラクチャＡに子ストラクチャＢの枠を置き、子ストラクチャの枠には異なる識別番号１，２を与える。ストラクチャＢの枠は幾何学的な重なりと異なる識別番号を持つので、ＣＰＵ２は「重なりあり」と判定する。
【００６２】
図１０（ｂ）において、ＣＰＵ２は、ストラクチャＡに子ストラクチャＣ（ストラクチャＡの孫ストラクチャ）の枠を置き、ストラクチャＣの枠には親ストラクチャＢと同じ識別番号１，２をそれぞれ与える。ストラクチャＣの枠は全て幾何学的に重なるが、識別番号が異なるのは真ん中の重なりを作るストラクチャＣの枠だけである。従って、ＣＰＵ２は、真ん中にある２つのストラクチャＣの枠を「重なりあり」と判定する。
【００６３】
図１０（ｃ）において、ＣＰＵ２は、真ん中の重なりを作るストラクチャＣが持つパターンの枠をストラクチャＡに置き、パターンの枠に所属ストラクチャＣと同じ識別番号１，２をそれぞれ与える。パターンＰの枠は幾何学的な重なりと異なる識別番号を持つので、ＣＰＵ２は「重なりあり」と判定する。一方、パターンＱの枠は幾何学的な重なりがないので、ＣＰＵ２は「重なりなし」と判定する。
【００６４】
図１０（ｄ）において、ＣＰＵ２は、「重なりあり」と判定したパターンＰの枠により最後にパターンＰのパターンデータ（線分データなど）を比較し、その比較結果に基づいてパターンＰに「重なりあり」と判定し、重なりを確定する。
【００６５】
この方法によれば、共通の先祖で最も近縁のストラクチャが選出されたストラクチャとなる重なりパターンＰ，Ｑを展開することなく効率よく見つけることができる。
【００６６】
このようにパターンＰ，Ｑに重なりがあると判定すると、ＣＰＵ２は、図６のステップ３３からステップ３４に進み、そのステップ３４において重なり合うパターンに対して情報を追加する。この情報の追加は、重なり調査でパターンに重なりが見つかるたびに呼び出される。従って、図７，８のデータの場合、ステップ３４における情報追加はストラクチャＢで一回、ストラクチャＡで一回呼び出される。
【００６７】
次に、単独持ち上げ情報、連結持ち上げ情報、代表情報、非侵入領域の作成手順を、図１１〜図１９に従って説明する。
図１１は、重なりがある２つのパターンに対する単独持ち上げ情報、連結持ち上げ情報、代表情報、非侵入領域の作成手順を示すフロー図である。尚、ここでは、重なりがある２つのパターンをパターンＰ，Ｑとして図示及び説明する。
【００６８】
ステップ４１は優先度決定処理であり、図２のＣＰＵ２は、パターンＰ，Ｑの重なり状況に応じてそれぞれの優先度を決定する。ステップ４２は情報追加処理であり、ＣＰＵ２は、ステップ４１において決定した優先度に基づいてパターンＰ，Ｑの情報を単独持ち上げ情報、連結持ち上げ情報、として追加する。ステップ４２は、ステップ４３の判定処理と、その判定結果に基づくステップ４４ａ〜４４ｃ，４５ａ〜４５ｄ，４６ａ〜４６ｃの追加処理から構成される。詳述すると、ＣＰＵ２は、ステップ４１において決定した２つのパターンＰ，Ｑの優先番号に基づいて、パターンＱの優先番号が大きい場合にはステップ４４ａ〜４４ｃを、優先番号が同じ場合にはステップ４５ａ〜４５ｄを、パターンＰの優先番号が大きい場合にはステップ４６ａ〜４６ｃを実行する。
【００６９】
これらの処理を終了すると、ＣＰＵ２は、ステップ４７の領域設定処理を実行する。ステップ４７において、ＣＰＵ２は、パターンＰ，Ｑの存在領域とサイジング幅を用いて非侵入領域を設定する。非侵入領域は、不必要な削除パターンを持ち上げないために設定する。
【００７０】
次に、上記の各処理を詳述する。
先ず、ステップ４１の優先度決定処理を説明する。
ＣＰＵ２は、パターンの重なり状況、詳しくはパターンが所属するストラクチャに応じて優先度を決定する。その重なり状況と優先度の関係は、以下のとおりである。
（１）重なりパターンの所属するストラクチャのストラクチャ名が同じ場合。両パターンを同じ優先度とする。
（２）重なりパターンの所属するストラクチャのストラクチャ名が違う場合。
（２−Ａ）直系関係にある場合、子孫に当たるストラクチャに所属するパターンを高い優先度とする。
（２−Ｂ）傍系関係にある場合、展開した場合の配置個数の多いストラクチャに所属するパターンを高い優先度とする。展開した場合の配置個数が同じ場合は、パタンの頂点数の多いパターンを高い優先度とする。頂点数も同じ場合は、優先度を同じとする。
【００７１】
優先度と連結持ち上げ情報，単独持ち上げ情報の関係は、以下のとおりである。
（１）優先度が同じ場合。それぞれのパターンの連結展開番号を連結持ち上げ情報として、それぞれのパターンの単独展開番号を単独持ち上げ情報として追加する。
（２）優先度が異なる場合。それぞれのパターンの連結展開番号を連結持ち上げ情報として、優先度の小さいパターンの単独展開番号を、単独持ち上げ情報として追加する。
【００７２】
ここで、単独展開番号、連結展開番号を説明する。
図１２（ａ），（ｂ）、図１３は、展開番号を説明する図である。展開番号は、あるストラクチャを固定したとき、展開イメージでパターンを一意的に識別する識別番号である。具体的には、次の手順で決めることができる。
【００７３】
（１）各ストラクチャの保有パターン数（直接持つパターンの数）と展開パターン数（展開イメージでのパターン数）を求める（図１２（ａ））。この数は、図１のステップ２１における前処理において階層木をたどることで求める。
【００７４】
（２）入力パターンデータの親子関係に対し、図１２（ｂ）のように番号を割り当てる。割当の一般規則は、ストラクチャＸが子ストラクチャＹ，Ｚを有し、ストラクチャＸの保有パターンがＮｘ個、ストラクチャＹの展開パターンをＮｙ個、ストラクチャＺの展開パターンをＮｚ個としたとき、ストラクチャＸの保有パターンに０〜Ｎx-1 、ストラクチャＹの保有パターンにＮx 〜Ｎx ＋Ｎy-1 、ストラクチャＺの保有パターンにＮx ＋Ｎy 〜Ｎx ＋Ｎy ＋Ｎz-1 の数字を割り当てる。
【００７５】
（３）割り当てられた番号の最小値を加算することで展開番号を求める。図１３には、各ストラクチャ及びパターンに割り当てた数字をそれぞれの近傍に表示している。ストラクチャＡを基準にした場合、左から３番目にあるパターンＳ（矢印で示したパターン）の展開番号は、（左から２番目にあるストラクチャＢに割り当てた番号５）＋（ストラクチャＤに割り当てた番号１）＋（パターンＳに割り当てた番号１）＝７となる。また、ストラクチャＢを基準にした場合の左から３番目にあるパターンＳの展開番号は、（ストラクチャＤに割り当てた番号１）＋（パターンＳに割り当てた番号１）＝２となる。
【００７６】
連結展開番号とは、展開番号に連結情報を反映させた物である。計算規則は、連結したパターンの展開番号から一つ代表となる展開番号を選び、先祖ストラクチャでは代表として選ばれた展開番号で置き換えることにより計算する。そして、連結情報を反映させない展開番号そのものが単独展開番号となる。
【００７７】
図１４，１５は、単独展開番号と連結展開の違いを説明する図である。パターンＰ，Ｑに重なりがあり、ストラクチャＹに１０００、ストラクチャＺに２００、ストラクチャＡに１００，ストラクチャＢに２０、ストラクチャＣに１０、ストラクチャＤに３５、ストラクチャＥに４０の番号が割り当てられている。この場合、ストラクチャＸからストラクチャＥのそれぞれを基準にした単独展開番号、連結展開番号は、図１５のようになる。
【００７８】
違いは、ストラクチャＸ，Ｙ，Ｚを基準にしたパターンＱの単独展開番号と連結展開番号にある。この違いは、パターンＰ及びＱがストラクチャＡで連結していてストラクチャＡの先祖ストラクチャでは代表としてＰの連結展開番号に置き換えられたことにある。
【００７９】
次に、単独持ち上げ情報に対する単独展開番号の追加と、展開持ち上げ情報に対する連結展開の追加の方法を説明する。
図）１６は、各情報のデータ構造を説明する図である。
【００８０】
単独持ち上げ情報は、ストラクチャ単位で単独展開番号、代表情報ポインタの情報を持つ。
連結持ち上げ情報は、ストラクチャ単位で連結展開番号、連結ポインタ、代表情報ポインタの情報を持つ。連結ポインタはパターンの連結に応じて作成される。
【００８１】
代表情報は、連結したパターンに共通する情報である。代表展開番号は、連結したパターンの中から任意に選ばれた展開番号である。持ち上げフラグは、同じ連結展開を持つパターンをさらに先祖のストラクチャに持ち上げるかどうかのフラグである。
【００８２】
次に、図１１のステップ４２における情報追加処理を説明する。
図１７、図１８（ａ），（ｂ）は、各ストラクチャの情報追加を説明する図である。
【００８３】
図１７に示す構造を持つパターンデータにおいて、パターンＰとパターンＱを重なりパターンとすると、パターンＰの所属ストラクチャはストラクチャＤ、パターンＱの所属ストラクチャはストラクチャＦ、共通の先祖で最近縁のストラクチャは選出されたストラクチャＡである。
【００８４】
パターンＰの情報を単独持ち上げ情報として、図１８（ａ）に示すように、パターンＰとストラクチャＡの間にあるストラクチャＢ，Ｃ，Ｄに対応する場所にボトムアップ（ストラクチャＤ，Ｃ，Ｂの順）で追加する。
【００８５】
パターンＱの情報を単独持ち上げ情報として、図１８（ａ）に示すように、パターンＱとストラクチャＡの間にあるストラクチャＥ，Ｆに対応する場所にボトムアップ（ストラクチャＦ，Ｅ，Ａの順）で追加する。
【００８６】
情報をボトムアップで追加する理由は、各ストラクチャにおける単独展開番号、連結展開番号を計算するためである。
さらに、ストラクチャＡに追加する場合は、代表情報の持ち上げフラグをオフにし、それ以外はオンにし、連結ポインタを使ってパターンＰとパターンＱの情報をつないでおく。
【００８７】
次に、図１１のステップ４７における領域設定処理を説明する。
図１９は、非侵入領域を説明するための図である。非侵入領域の初期値をストラクチャ存在領域に設定し、重なりパターンの存在領域と交わらないように領域辺を後退させて設定する。図１９において、実線で示す領域がパターンＰを含むストラクチャの存在領域であり、それに対して重なりパターンＰ，Ｑの存在領域（右側の太い破線で示す領域）と交わらないように領域右辺を一点鎖線で示す位置まで後退させて設定する。
【００８８】
サイジング指定がある場合は、サイジング幅×２だけ更に内側に後退させる。図１９において、サイジング指定がある場合は、一点鎖線で示す位置から左方向にサイジング幅の２倍だけ後退させた領域（左側の太い破線で示す領域）を設定する。
【００８９】
尚、図１９には、パターンＰを含むストラクチャに対して非侵入領域を設定する場合を示しており、パターンＱを含むストラクチャに対しても同様に非侵入領域が設定される。
【００９０】
後退する方向は、上、下、右、左の４方向で、設定後の領域面積が最大になる方向を選ぶ。非侵入領域の設定は、選出されたストラクチャＡとパターンＰ及びＱの間にあるストラクチャに対して行う。例えば、図１７の構造を持つパターンデータでは、ストラクチャＢ，Ｃ，Ｄ，Ｅ，ＦがストラクチャＡとパターンＰ及びＱの間にあるストラクチャであるため、これらに対して設定する。
【００９１】
次に、図１のステップ２３の処理を詳述する。
図２０は、ステップ２３において、候補パターン、削除パターンファイルの作成手順を示すフロー図である。即ち、図２０のステップ５１〜５５は、ステップ２３のサブステップである。
【００９２】
先ず、図２のＣＰＵ２は、ステップ５１，５２をストラクチャ種類でループする、即ちステップ５１の判断処理によってステップ５２の単独持ち上げ処理をボトムアップにてパターンデータを構成するストラクチャの全種類について実施する。ステップ５２において、ＣＰＵ２は、入力パターンデータ１２から単独持ち上げ情報を使ってパターンの単独持ち上げを行い、仮候補パターンデータ１４ａを作成する。
【００９３】
次に、ＣＰＵ２は、ステップ５３，５４をストラクチャ種類でループする、即ちステップ５３の判断処理によってステップ５４の連結持ち上げ処理をボトムアップにてパターンデータを構成するストラクチャの全種類について実施する。ステップ５４において、ＣＰＵ２は、仮候補パターンデータ１４ａから転結持ち上げ情報を使ってパターンの連結持ち上げを行い、削除パターンデータ１５を作成する。
【００９４】
そして、ＣＰＵ２は、ステップ５５において、サイジングありの場合には仮候補パターンデータ１４ａと削除パターンデータ１５を合成して候補パターンデータ１４を作成し、サイジングなしの場合は仮候補パターンデータ１４ａを候補パターン１４とする。
【００９５】
図２１及び図２２は、図２０のステップ５２における単独持ち上げの手順を示すフロー図である。
尚、ステップ５１で入力パターンデータ１２から選出したストラクチャを、ストラクチャＡとして説明する。
【００９６】
先ず、図２のＣＰＵ２は、ステップ６１の判断処理においてストラクチャＡが保有しているパターンのうち未処理パターンがあるか否かを判断することによって、ステップ６１〜６３ａ，６３ｂをストラクチャＡが直接保有しているパターン分ループする。
【００９７】
ステップ６２において、ＣＰＵ２は、選出されたパターンとストラクチャＡに対応する単独持ち上げ情報に一致する単独展開番号があるか調べる。一致するものがある場合は持ち上げると判定し、一致するものがない場合は持ち上げないと判定する。また、一致するものがある場合は、対応する代表情報の候補作成フラグをオンにする。
【００９８】
ステップ６２においてパターンを持ち上げると判定した場合、ＣＰＵ２は、ステップ６３ａにおいてこのパターンをストラクチャＡに対応する単独持ち上げパターンデータ１４ｂとしてファイルに保存する。このデータは、ストラクチャＡを子ストラクチャとして配置するストラクチャで再度単独持ち上げ判定の対象となる。
【００９９】
一方、ステップ６２においてパターンを持ち上げないと判定された場合ＣＰＵ２は、ステップ６３ｂにおいてこのパターンをストラクチャＡに対応する仮候補パターンデータ１４ａとし、このパターンの単独持ち上げ処理は終了する。
【０１００】
単独パターンデータのデータ構造は、図２３（左）に示すように、ストラクチャ単位で作成される。パターンデータポインタは、入力パターンデータの保存アドレスである。配置情報は、パターンを配置する位置に関する情報で、ＸＹ座標、回転、倍率から構成されている。
【０１０１】
次に、ＣＰＵ２は、図２２のステップ６４の判断処理によって、ステップ６４〜６８ａ，６８ｂをストラクチャＡが配置している子ストラクチャの分ループする。更に、ＣＰＵ２は、ステップ６５の判断処理によって、単独持ち上げパターンデータ１４ｂに基づいて、ステップ６５〜６８ａ，６８ｂをストラクチャＡに配置する子ストラクチャＢの単独持ち上げパターンの数分ループする。尚、ストラクチャＢの単独持ち上げパターンは、ボトムアップ処理であるから、ストラクチャＡより先にストラクチャＢが選択されたときに既に作成されている。
【０１０２】
ステップ６６において、ＣＰＵ２は、単独持ち上げパターンの持つ配置情報に、ストラクチャＢの配置情報を合成する。この手順でストラクチャＢからの相対配置情報が、ストラクチャＡからの相対配置情報に変換される。
【０１０３】
ステップ６７において、ＣＰＵ２は、図２１のステップ６２と同様にして持ち上げ判定を行う。このステップ６７における判定結果に基づいて、ＣＰＵ２は、図２１のステップ６３ａ，６３ｂと同様に、ステップ６８ａにおいて仮候補パターンデータ１４ａを、ステップ６８ｂにおいて単独持ち上げパターンデータ１４ｂを作成する。
【０１０４】
図２４及び図２５は、図２０のステップ５４における連結持ち上げの手順を示すフロー図である。
尚、ステップ５３で仮候補パターンデータ１４ａから選出したストラクチャを、ストラクチャＡとして説明する。
【０１０５】
先ず、図２のＣＰＵ２は、ステップ７１の判断処理において仮候補パターンデータ１４ａにストラクチャＡに仮候補パターンがあるか否かを判断することによって、ステップ７１〜７３をストラクチャＡの仮候補パターン分ループする。
【０１０６】
ステップ７２において、ＣＰＵ２は、ストラクチャＡの非侵入領域にパターンの存在領域が包含されるかどうかを判定する。包含されている場合は、持ち上げないと判定する。少しでもはみ出ていれば連結展開番号による判定を行う。
【０１０７】
連結展開番号による判定は、パターンとストラクチャＡに対応する連結持ち上げ情報に一致する連結展開があるかどうか調べる。一致するものがない場合は持ち上げないと判定する。一致するものがある場合は、代表情報の持ち上げフラグを参照し、オンなら持ち上げを行うと判定し、オフなら持ち上げを行わないと判定する。
【０１０８】
ステップ７３において、ＣＰＵ２はステップ７２で持ち上げると判定した場合、このパターンをストラクチャＡに対応する連結持ち上げパターンとし、連結持ち上げパターンデータ１４ｃを作成する。このデータ１４ｃは、ストラクチャＡを子ストラクチャとして配置するストラクチャで再度連結持ち上げ判定の対象となる。この操作の意味は、連結持ち上げパターンのコピーを削除パターンとして持ち上げて仮候補パターンと重なるパターンを切り取るためである。一方、ＣＰＵ２は、ステップ７２において持ち上げないと判定した場合、ステップ７３ではない処理を行わずにステップ７１に戻る。
【０１０９】
次に、ＣＰＵ２は、図２５のステップ７４の判断処理によって、ステップ７４〜８０をストラクチャＡが配置している子ストラクチャ分ループする。更に、ＣＰＵ２は、ステップ７５における判断処理によって、連結持ち上げパターンデータ１４ｃに基づいて、ステップ７５〜８０をストラクチャＡの配置する子ストラクチャＢの連結持ち上げパターンでループする。尚、ストラクチャＢの連結持ち上げパターンは、ボトムアップ処理であるから、ストラクチャＡより先にストラクチャＢが選択されたときに既に作成されている。
【０１１０】
ステップ７６で連結持ち上げパターンの持つ配置情報に子ストラクチャＢの配置情報を合成する。この手順で子ストラクチャＢからの相対配置情報が、ストラクチャＡからの相対配置情報に変換される。
【０１１１】
ステップ７７において、ＣＰＵ２は、ステップ７２と同様にして持ち上げ判定を行う。このステップ７７における判定結果に基づいて、ＣＰＵ２は、図２４のステップ７３と同様に、ステップ７８において連結持ち上げパターデータ１４ｃを作成する。
【０１１２】
ステップ７９において、ＣＰＵ２は、候補作成フラグにより削除パターンを作成するかどうかの判定を行う。このフラグがオンになっている場合は、このパターンと連結するパターンでストラクチャＡの仮候補パターンが作成されている。従って、ＣＰＵ２は、この仮候補パターンを切り取るためにステップ８０でストラクチャＡの削除パターンデータ１５を作成する。
【０１１３】
以上の様にして削除パターンデータ１５を作成すると、ＣＰＵ２は、連結持ち上げ処理を終了して戻る。即ち、ＣＰＵ２は、図２０のステップ５３に移る。そのステップ５３においてストラクチャの全種類に対する連結持ち上げ処理を終了したと判定すると、ＣＰＵ２はステップ５５に移る。
【０１１４】
ステップ５５において、ＣＰＵ２は、作成した仮候補パターンデータ１４ａと削除パターンデータ１５とから、候補パターンデータ１４を作成する。サイジングなしの場合、ＣＰＵ２は、仮候補パターンデータ１４ａをそのまま候補パターンデータ１４にする。一方、サイジングありの場合、ＣＰＵ２は、仮候補パターンデータ１４ａと削除パターンデータ１５をストラクチャ単位で合成（図形論理和演算）して候補パターンデータ１４とする。
【０１１５】
このステップ５５において、仮候補パターンデータ１４ａと削除パターンデータ１５をストラクチャ単位で合成することにより、サイジング処理におけるマイナスサイジングの時にパターンが離間してスリットが発生するのを防ぐことができる。
【０１１６】
図２６は、候補パターンデータ１４、削除パターンデータ１５のデータ構造を説明する図である。各パターンデータ１４，１５はストラクチャ単位でパターン頂点データを持つ。
【０１１７】
次に、図１のステップ２４の処理を詳述する。
図２７は、ステップ２４において、候補パターンデータ、削除パターンデータからパターンデータを作成する手順を示すフロー図である。即ち、図２７のステップ８１〜８３は、ステップ２４のサブステップである。
【０１１８】
先ず、図２のＣＰＵ２は、ステップ８１において候補パターンデータ１４に対してＯＲ処理、サイジング処理を行う。次に、ＣＰＵ２は、ステップ８２において、削除パターンデータ１５に対してＯＲ処理、サイジング処理を行う。
【０１１９】
次に、ＣＰＵ２は、ステップ８３において、ＯＲ処理，サイジング処理を行った候補パターンから削除パターンをＳＵＢ処理してパターンデータ１６を作成する。
【０１２０】
図２８は、図１のステップ２４、詳しくは図２７のステップ８１，８２におけるＯＲ処理、サイジング処理の手順を示すフロー図である。即ち、図２８のステップ９１〜９５は、ステップ２４（ステップ８１及びステップ８２）のサブステップである。
【０１２１】
図２のＣＰＵ２は、ステップ９１においてストラクチャ種類でループ判定し、ステップ９２において選出したストラクチャに対応する候補パターンデータ１４（または削除パターンデータ１５）に対してＯＲ処理を行う。尚、このループはボトムアップでなくても良い。
【０１２２】
次に、ＣＰＵ２は、ステップ９３においてサイジング有無の判定を行い、サイジングの指定があればステップ９４，９５をループする。ＣＰＵ２は、ステップ９４においてストラクチャ種類でループ判定し、ステップ９５において選出したストラクチャに対応するＯＲ処理後のデータ（ＯＲ処理後の候補パターンデータ１４又は削除パターンデータ１５）に対してサイジング処理を行う。
【０１２３】
図２９は、図１のステップ２４、詳しくは図２７のステップ８３におけるＳＵＢ処理の手順を示すフロー図である。即ち、図２９のステップ１０１，１０２は、ステップ２４（ステップ８３）のサブステップである。
【０１２４】
図２のＣＰＵ２は、ステップ１０１においてストラクチャ種類でループ判定し、ステップ１０２において選出したストラクチャに対応する候補パターンから削除パターンをＳＵＢ処理する。この処理により候補パターンから重なりパターンが切り取られる。尚、このループはボトムアップでなくても良い。
【０１２５】
次に、上記のように構成された露光データ作成装置の作用を図１のステップに従って説明する。
以下、図３７のデータにステップ２２〜２４の各処理を適用した場合の例を説明する。
【０１２６】
［ステップ２２］
ボトムアップ（ストラクチャＥ，Ｄ，Ｃ，Ｂ，Ａの順）でパターンの重なりをスイープ法を用いて調査する。ストラクチャＡにおける重なり調査で使い、４箇所に重なりを見つける。これらの重なりを、左上，左下，右上，右下の順に［１］，［２］，［３］，［４］として説明する。
【０１２７】
［１］の場所では、パターンＱとパターンＳが重なっており、所属するストラクチャＤ，Ｃの関係は異なるストラクチャ名で傍系関係にあるので、ストラクチャＤ，Ｃの展開した場合の配置個数を比較する。ストラクチャＤの配置個数は３個、ストラクチャＣの配置個数は６個なのでパターンＳが優先度の高いパターンとなる。従って、次の情報追加をテーブルに行う。
【０１２８】
（１）パターンＱの単独展開番号を、階層木においてパターンＱとストラクチャＡの間にあるストラクチャＤに対応する単独持ち上げテーブルに追加する。
（２）パターンＱの連結展開番号を、ストラクチャＡと階層木に於いてパターンＱとストラクチャＡの間にあるストラクチャＤに対応する連結持ち上げテーブルに追加する。
【０１２９】
（３）パターンＲの連結展開番号を、ストラクチャＡと階層木においてパターンＲとストラクチャＡの間にあるストラクチャＢ，Ｃに対応する連結持ち上げテーブルに追加する。
【０１３０】
パターンＱの（１），（２）のテーブル追加の例を以下説明する。
図３０（ａ）〜（ｅ）は、各ストラクチャＡ〜Ｅを基準とした場合の単独展開番号である。説明のために全ての単独展開番号を記述した。実際には、マスクパターンデータを、展開することなく重なりパターンのみの単独展開番号を計算する。
【０１３１】
（１），（２）の追加情報は、各ストラクチャ毎に同時に行われる。
「ストラクチャＤに対応する情報の作成」
パターンＱのストラクチャＤでの単独展開番号１（図３０（ｄ）参照）をストラクチャＤに対応する単独持ち上げ情報テーブルに追加する。
【０１３２】
パターンＱのストラクチャＤでの連結展開番号１をストラクチャＤに対応する連結持ち上げ情報テーブルに追加する。ストラクチャＤはボトムストラクチャであり、パターンＱの連結展開番号は、単独展開番号と等しい。ストラクチャＤでパターンＱは重なりがない。よって、連結ポインタはなしとする。
【０１３３】
代表情報の持ち上げフラグは、ストラクチャＡに対応していないのでオンとする。代表情報の代表展開番号は、パターンＱの連結展開番号とパターンＱがストラクチャＤで連結しているパターンの連結展開番号から選ばれる。パターンＱのみであるので代表展開番号は１が選ばれる。
【０１３４】
単独持ち上げ情報、連結持ち上げ情報のポインタを、作成した代表情報につなぐ。
図３１は、単独持ち上げテーブル、連結持ち上げ情報テーブル、代表情報テーブルを説明する図である。各テーブルは、（単独展開番号、代表情報ポインタ）、（連結展開番号、連結ポインタ、代表情報ポインタ）、（代表展開番号、持ち上げフラグ）のように各情報は組にして表現されている。各情報の組には、情報識別のための名前をつけて区別してある。
【０１３５】
図３１において、［１］の箇所におけるパターンＱのストラクチャＤに対応する追加情報は、単独持ち上げ情報がＴ１（１，Ｄ９）、連結持ち上げ情報がＲ１３（１，なし，Ｄ９）、代表情報がＤ９（１，ＯＮ）である。
【０１３６】
「ストラクチャＡに対応する情報の作成」
パターンＱは単独持ち上げ情報テーブルへの追加なし。
パターンＱのストラクチャＡでの連結展開番号１をストラクチャＡに対応する連結持ち上げ情報テーブルに追加する。パターンＱの連結展開番号は、ストラクチャＤの代表情報を元に計算される。ストラクチャＡでパターンＱはパターンＰと重なるのでパターンＰの情報へのポインタを設定する。
【０１３７】
代表情報の持ち上げフラグは、ストラクチャＡに対応しているのでＯＦＦとする。代表情報の代表情報番号は、パターンＱの連結展開番号とパターンＱがストラクチャＡで連結しているパターンの連結展開番号から選ばれる。パターンＱ及びＰから選ばれる。例えば、パターンＱの連結展開番号を代表番号とする。
【０１３８】
連結持ち上げ情報のポインタを作成した代表情報につなぐ。
図３１において［１］のパターンＱのストラクチャＡに対する追加情報は、連結持ち上げ情報がＲ１（１，Ｒ１，Ｄ１）、代表情報がＤ１（１，ＯＦＦ）である。
【０１３９】
上記の［１］にある重なりに対する操作を［２］〜［４］の箇所にある重なりに対しても同様に行い、単独持ち上げ情報テーブル、連結情報持ち上げ情報テーブル、代表情報テーブルをそれぞれ作成する。
【０１４０】
［ステップ２３］
作成した単独持ち上げ情報テーブル、連結情報持ち上げ情報テーブル、代表情報テーブルをもとに候補パターンデータ、削除パターンデータを作成する。
【０１４１】
各パターンデータは、ボトムアップで単独持ち上げ情報テーブル、連結情報持ち上げ情報テーブルの単独展開番号、連結展開番号とパターンデータの単独展開番号、連結展開番号の比較により作成される。
【０１４２】
図３２（ａ）はサイジングありの場合の候補パターン、図３２（ｂ）は削除パターンの説明図である。図３２（ａ）に示すように、ストラクチャＡには候補パターンとしてストラクチャＤ，Ｅが持っていたパターンＱ，Ｕが持ち上げられている。図３２（ｂ）に示すように、ストラクチャＡには削除パターンとしてパターンＱ，Ｕと重なり合うパターンＳ（ストラクチャＣ）のコピーが持ち上げられている。
【０１４３】
図３３（ａ）はサイジングなしの場合の候補パターン、図３３（ｂ）は削除パターンの説明図である。図３３（ａ）に示すように、ストラクチャＡには候補パターンとしてストラクチャＤ，Ｅが持っていたパターンＱ，Ｕと、それに重なるパターンＳ（ストラクチャＣ）のコピーが持ち上げられている。図３３（ｂ）に示すように、ストラクチャＡには削除パターンとしてパターンＱ，Ｕと重なり合うパターンＳ（ストラクチャＣ）のコピーが持ち上げられている。
【０１４４】
［ステップ２４］
サイジング指定なしの場合、各ストラクチャに対応する候補パターン（図３２（ａ））、削除パターン（図３２（ｂ））を、それぞれＯＲ処理し、その後それぞれをＳＵＢ処理する。
【０１４５】
図３４（ａ）〜（ｃ）はストラクチャＡに対するＯＲ処理、ＳＵＢ処理の説明図である。図３４（ａ）に示すストラクチャＡの候補パターン（パターンＱ，Ｕ）から図３４（ｂ）に示すストラクチャＡの削除パターン（パターンＳのコピー）をそれぞれＯＲ処理し、ＳＵＢ処理して図３４（ｃ）に示すパターンＱＳ１，ＱＳ２，ＳＵ１，ＳＵ２を得る。
【０１４６】
サイジング指定ありの場合、各ストラクチャに対応する候補パターン（図３３（ａ））、削除パターン（図３３（ｂ））を、それぞれＯＲ処理、サイジングし、その後それぞれをＳＵＢ処理する。
【０１４７】
図３５（ａ）〜（ｃ）はストラクチャＡに対するＯＲ処理、サイジングとしてマイナスサイジング、ＳＵＢ処理の説明図である。図３５（ａ）に示すストラクチャＡの候補パターン（パターンＱ＋Ｓ，Ｓ＋Ｕ）と図３５（ｂ）に示すストラクチャＡの削除パターン（パターンＳのコピー）をそれぞれサイジング処理して実線で示すパターンを得、それらをＳＵＢ処理して図３５（ｃ）に示すパターンＱＳ１，ＱＳ２，ＳＵ１，ＳＵ２を得る。
【０１４８】
以上記述したように、本実施の形態によれば、以下の効果を奏する。
（１）ステップ２２では、階層設計されたマスクパターンデータ１１（入力パターンデータ１２）から検出した重なり合うパターンの階層間の重なり情報を作成し、ステップ２３では、重なり情報に基づいて、重なり合うパターンを持ち上げて候補パターンデータ１４及び削除パターンデータ１５を作成する。そしてステップ２４では、候補パターンデータ１４から削除パターンデータ１５を削除して重なりのないパターンデータ１６を作成するようにした。その結果、重なりのないパターンデータ１６を作成することで、マスクパターンデータ１１の階層構造をほぼ保持したまま階層データ１７を作成することができる。
【０１４９】
（２）ステップ２２では、重なり合うパターンのそれぞれが所属するストラクチャのストラクチャ名と互いのパターンの関係に基づく状況に応じて、重なり情報として単独持ち上げ情報と連結持ち上げ情報と代表情報を作成するようにした。その結果、重なり状況に応じて作成する情報を変更することにより、展開するパターン数が少なくなり、作成される階層データのデータ量増加を抑制することができる。
【０１５０】
（３）サイジング指定がある場合には仮候補パターンデータ１４ａと削除パターンデータ１５を合成した候補パターンデータ１４を作成するようにした。その結果、この合成後の候補パターンにサイジング処理を施すことで、パターンが離間してスリットが発生するのを防ぐことができる。
【０１５１】
（４）ステップ２４では、サイジングしない場合は、各階層毎に候補パターンデータ１４から削除パターンデータ１５を削除してパターンデータ１６を作成し、サイジングする場合は、各階層毎に候補パターンデータ１４と削除パターンデータ１５をそれぞれサイジング後、各階層毎に候補パターンデータ１４から削除パターンデータ１５を削除してパターンデータ１６を作成するようにした。その結果、サイジング後の図形を損なうことなくパターンデータ１６ひいては階層データ１７を作成することができる。
【０１５２】
（５）ステップ２２では、重なり合うパターンを含まない非侵入領域を設定し、ステップ２３では、非侵入領域に含まれる削除パターンを持ち上げないようにした。その結果、繰り返し性のある削除パターンのうち、非侵入領域に含まれる削除パターンを持ち上げないことで、ストラクチャに展開する削除パターンのデータ量を少なくすることができる。
【０１５３】
（６）階層構造を保持した階層データ１７を作成することができるため、その階層データからデータ量が少ない露光データ１８を作成することができると共に、その露光データ１９の変換に要する処理時間を短縮することができる。
【０１５４】
尚、前記実施形態は、以下の態様に変更してもよい。
○上記実施形態では、階層解析を図１のステップ２１において実施したが、ステップ２２又はステップ２３において実施する構成としても良い。
【０１５５】
○上記実施形態は、繰り返し性の多いパターンを必要とするメモリ品種のみならず、階層構造を使用したデータであれば適用できるため、ロジック品種、システムＬＳＩ等の階層化設計された半導体集積回路用マスクパターンデータに幅広く適用できる。
【０１５６】
以上の実施形態をまとめ、本発明の構成に関する以下の事項を開示する。
（Ａ）  請求項１に記載のデータ作成方法において、前記第１ステップでは、前記重なり合うパターンのそれぞれが所属するストラクチャのストラクチャ名と互いのパターンの関係に基づく状況に応じて、前記重なり情報として単独持ち上げ情報と連結持ち上げ情報と代表情報を作成することを特徴とするデータ作成方法。このように、重なり状況に応じて作成する情報を変更することにより、展開するパターン数が少なくなり、作成される階層データのデータ量増加を抑制することができる。
【０１５７】
（Ｂ）  上記（Ａ）に記載のデータ作成方法において、前記第１ステップでは、（１）重なり合うパターンのそれぞれが所属するストラクチャのストラクチャ名が同じ場合、（２）重なり合うパターンのそれぞれが所属するストラクチャのストラクチャ名が違う場合で互いに直系関係にある場合、（３）重なり合うパターンのそれぞれが所属するストラクチャのストラクチャ名が違う場合で互いに傍系関係にある場合、の３つの場合の状況に基づいて、前記重なり情報として単独持ち上げ情報、連結持ち上げ情報、代表情報を作成することを特徴とするデータ作成方法。
【０１５８】
（Ｃ）  請求項１に記載のデータ作成方法において、前記第２ステップでは、前記重なり合うパターンに共通のストラクチャに、前記候補パターンを持ち上げた前記候補パターンデータを作成し、前記削除パターンのコピーを持ち上げた前記削除パターンデータを作成することを特徴とするデータ作成方法。
【０１５９】
（Ｄ）  請求項１に記載のデータ作成方法において、前記第２ステップは、前記重なり情報に基づいて前記候補パターンデータを作成する単独持ち上げステップと、前記重なり情報に基づいて前記削除パターンデータを作成する連結持ち上げステップと、を含むことを特徴とするデータ作成方法。
【０１６０】
（Ｅ）  上記（Ｄ）に記載のデータ作成方法において、前記第２ステップは、更に、サイジング指定がある場合には前記候補パターンと前記削除パターンを合成した候補パターンデータを作成するステップを含むことを特徴とするデータ作成方法。この合成後の候補パターンにサイジング処理を施すことで、パターンが離間してスリットが発生するのを防ぐ。
【０１６１】
（Ｆ）  階層設計されたマスクパターンデータからパターンに重なりのない露光データを作成するための階層データを作成するデータ作成装置であって、前記マスクパターンデータの階層間の重なり情報を収集する情報収集手段と、前記重なり情報に基づいて、重なり合うパターンを持ち上げて候補パターンデータ及び削除パターンデータを作成する第１のデータ作成手段と、前記候補パターンデータから削除パターンデータを削除して重なりのないパターンデータを作成する第２のデータ作成手段と、を有することを特徴とするデータ作成装置。
【０１６２】
（Ｇ）  階層設計されたマスクパターンデータからパターンに重なりのない露光データを作成するための階層データを作成するプログラムデータを記録したコンピュータ読み取り可能な記録媒体であって、前記プログラムは、前記マスクパターンデータの階層間の重なり情報を収集するステップと、前記重なり情報に基づいて、重なり合うパターンを持ち上げて候補パターンデータ及び削除パターンデータを作成するステップと、前記候補パターンデータから削除パターンデータを削除して重なりのないパターンデータを作成するステップと、を有する方法を実行する、記録媒体。
【０１６３】
【発明の効果】
以上詳述したように、本発明によれば、重なりパターンの状況に応じて重なり情報を作成し、その情報に基づいて作成した候補パターンデータ及び削除パターンデータから階層データを作成することで、展開するパターンの数が少なくなり、作成する階層データのデータ量増加を抑制することができる。
【０１６４】
作成した重なり情報に基づいて重なり合うパターンを持ち上げて候補パターンデータと削除パターンデータを作成するようにしたため、マスクパターンデータの階層構造をほぼ保持して階層データを作成することができるので、その階層データから露光データに変換する処理時間を短縮することができる。
【図面の簡単な説明】
【図１】  一実施形態の露光データ作成処理のフロー図である。
【図２】  一実施形態のデータ作成装置の概略構成図である。
【図３】  露光データ作成用階層データのレイアウト図である。
【図４】  露光データ作成用階層データの階層木図である。
【図５】  露光データ作成用階層データのパターン図である。
【図６】  情報テーブル作成処理のフロー図である。
【図７】  重なり調査を説明するためのレイアウト図である。
【図８】  重なり調査を説明するデータの階層木図である。
【図９】  (a)〜(c)は重なり調査の手順を示すレイアウト図である。
【図１０】  (a)〜(d)は重なり調査の手順を示すレイアウト図である。
【図１１】  情報追加処理のフロー図である。
【図１２】  (a)，(b)は展開番号の説明図である。
【図１３】  展開番号を説明するデータの階層木図である。
【図１４】  単独及び連結展開番号を説明するデータの階層木図である。
【図１５】  単独及び連結展開番号の説明図である。
【図１６】  単独及び連結持ち上げ情報、代表情報の構造説明図である。
【図１７】  重なり情報の追加を説明するデータの階層木図である。
【図１８】  (a)，(b)は重なり情報を追加するテーブルの説明図である。
【図１９】  非侵入領域の説明図である。
【図２０】  候補及び削除パターンデータ作成処理のフロー図である。
【図２１】  単独持ち上げ処理のフロー図である。
【図２２】  単独持ち上げ処理のフロー図である。
【図２３】  単独及び連結持ち上げパターンデータの構造説明図である。
【図２４】  連結持ち上げ処理のフロー図である。
【図２５】  連結持ち上げ処理のフロー図である。
【図２６】  候補及び削除パターンデータの構造説明図である。
【図２７】  パターンデータ作成処理のフロー図である。
【図２８】  ＳＵＢ処理のフロー図である。
【図２９】  ＯＲ処理、サイジング処理のフロー図である。
【図３０】  (a)〜(e)は単独展開番号の説明図である。
【図３１】  単独及び連結持ち上げ情報、代表情報の関係図である。
【図３２】  (a)は候補パターン、(b)は削除パターンの説明図である。
【図３３】  (a)は候補パターン、(b)は削除パターンの説明図である。
【図３４】  (a)〜(c)は図形論理処理後のパターン図である。
【図３５】  (a)〜(c)は図形論理処理後のパターン図である。
【図３６】  (a)，(b)は階層化設計データの説明図である。
【図３７】  マスクパターンデータのレイアウト図である。
【図３８】  マスクパターンデータの階層説明図である。
【図３９】  階層化設計データのパターン図である。
【図４０】  従来方法による階層データのレイアウト図である。
【図４１】  従来方法による階層データの階層説明図である。
【図４２】  従来方法による階層データのパターン図である。
【図４３】  展開して作成した階層データのパターン図である。
【符号の説明】
１１  マスクパターンデータ
１４  候補パターンデータ
１５  削除パターンデータ
１６  パターンデータ
１７  階層データ
１８  露光データ
２２  第１ステップ
２３  第２ステップ
２４  第３ステップ
【図１】
0003759357.tif 000002
【図２】
0003759357.tif 000003
【図３】
0003759357.tif 000004
【図４】
0003759357.tif 000005
【図５】
0003759357.tif 000006
【図６】
0003759357.tif 000007
【図７】
0003759357.tif 000008
【図８】
0003759357.tif 000009
【図９】
0003759357.tif 000010
【図１０】
0003759357.tif 000011
【図１１】
0003759357.tif 000012
【図１２】
0003759357.tif 000013
【図１３】
0003759357.tif 000014
【図１４】
0003759357.tif 000015
【図１５】
0003759357.tif 000016
【図１６】
0003759357.tif 000017
【図１７】
0003759357.tif 000018
【図１８】
0003759357.tif 000019
【図１９】
0003759357.tif 000020
【図２０】
0003759357.tif 000021
【図２１】
0003759357.tif 000022
【図２２】
0003759357.tif 000023
【図２３】
0003759357.tif 000024
【図２４】
0003759357.tif 000025
【図２５】
0003759357.tif 000026
【図２６】
0003759357.tif 000027
【図２７】
0003759357.tif 000028
【図２８】
0003759357.tif 000029
【図２９】
0003759357.tif 000030
【図３０】
0003759357.tif 000031
【図３１】
0003759357.tif 000032
【図３２】
0003759357.tif 000033
【図３３】
0003759357.tif 000034
【図３４】
0003759357.tif 000035
【図３５】
0003759357.tif 000036
【図３６】
0003759357.tif 000037
【図３７】
0003759357.tif 000038
【図３８】
0003759357.tif 000039
【図３９】
0003759357.tif 000040
【図４０】
0003759357.tif 000041
【図４１】
0003759357.tif 000042
【図４２】
0003759357.tif 000043
【図４３】
0003759357.tif 000044