(57)【要約】【課題】セル階層化を十分に行うことができ、データ圧縮効率の高いパターンデータ圧縮処理技術を提供する。【解決手段】図形パターンに含まれる１以上のアレイについての繰り返しピッチのうちの最頻出のピッチである代表アレイピッチを取得し、代表アレイピッチにピッチを固定してアレイ化を行う。これによって生成された１以上のピッチ固定アレイの中から、繰り返し個数が最小であるアレイを基準アレイとして特定する。図形パターンにおいて、基準アレイを構成する図形の重心を中心とし、代表アレイピッチで囲まれた矩形領域内に位置する、１以上のピッチ固定アレイのそれぞれを構成する図形を、種セルの構成図形として特定する。該構成図形を含む外接矩形を種セルとして設定し、該種セルに基づいて図形パターンについてのセル階層化処理を行う。【選択図】図２
2008250759.tif 000002
【特許請求の範囲】
【請求項１】
複数の図形が空間的に配置されることで形成される図形パターンがフラット化状態で記述されてなるパターンデータに基づいて、前記図形パターンをセル階層化した形式にて記述する階層化データを生成するデータ処理装置であって、
前記図形パターンに含まれる１以上のアレイについての繰り返しピッチのうちの最頻出のピッチである代表アレイピッチを取得する代表アレイピッチ取得手段と、
前記パターンデータを対象に、前記代表アレイピッチにピッチを固定してアレイ化を行うピッチ固定アレイ化手段と、
前記ピッチ固定アレイ化手段によって生成された１以上のピッチ固定アレイの中から、繰り返し個数が最小であるアレイを基準アレイとして特定する基準アレイ特定手段と、
前記図形パターンにおいて、前記基準アレイを構成する図形の重心を中心とし、前記代表アレイピッチで囲まれた矩形領域内に位置する、前記１以上のピッチ固定アレイのそれぞれを構成する図形を、前記セル階層化における繰り返し単位である種セルの構成図形として特定し、前記構成図形を含む外接矩形を前記種セルとして設定する種セル設定手段と、
前記種セルに基づいて前記図形パターンについてのセル階層化処理を行い、前記種セルを特定する情報と、前記種セルのピッチ情報と繰り返し個数情報とを含む前記階層化データを生成する階層化処理手段と、
を備えることを特徴とするデータ処理装置。
【請求項２】
請求項１に記載のデータ処理装置であって、
前記代表アレイピッチ取得手段が、
前記図形パターンのなかで、同一形状を有し同一ピッチで繰り返し配置されている図形群をアレイ化するアレイ生成手段と、
前記アレイ生成手段によって生成された１以上のアレイの繰り返しピッチの中から、最小のピッチを代表アレイピッチとして検出する代表アレイピッチ検出手段と、
を備えることを特徴とするデータ処理装置。
【請求項３】
請求項１または請求項２に記載のデータ処理装置であって、
前記代表アレイピッチよりも大きなサイズの図形を前記代表アレイピッチごとに切断する切断処理手段、
をさらに備え、
前記切断処理によって得られた切断図形を前記パターンデータを構成する図形に含めて前記ピッチ固定アレイ化を行う、
ことを特徴とするデータ処理装置。
【請求項４】
請求項１ないし請求項３のいずれかに記載のデータ処理装置であって、
前記図形パターンを構成する図形の少なくとも一部が、単一の図形と同等に取り扱われている複数の図形からなる図形の組である、
ことを特徴とするデータ処理装置。
【請求項５】
コンピュータが備えるＣＰＵとメモリとを使用することにより、前記コンピュータを、請求項１ないし請求項４のいずれかに記載のデータ処理装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＳＩパターンなどのパターンデータについての圧縮データを生成する技術に関する。
【背景技術】
【０００２】
近年、大規模な半導体集積回路の高集積化、微細化に伴い、取り扱うＬＳＩパターンのデータ量は膨大なものとなってきた。ＬＳＩパターンを取り扱うソフトウェアプログラムや半導体描画装置では、データ量が膨大であるため、処理に長時間を要することや、データ格納のために大容量の記憶装置が必要となることが問題となっている。
【０００３】
ＬＳＩパターンは、ストリームフォーマットと呼ばれるセル階層を有する形式にてデータを記述可能なデータフォーマットで表現される。しかし、元々の設計段階では階層を有するように記述されていたＬＳＩパターンデータに対し、様々な演算や補正を施すと、ＬＳＩパターンデータは階層を保持できず、部分的に、セル階層のない状態になってしまうことがある。この現象は、フラット化と称される。
【０００４】
フラット化状態にあるＬＳＩパターンデータにおいては、全ての図形についての形状情報と配置情報とが書き下される態様でデータ記述がなされているので、そのデータ量は膨大である。従って、上述のように処理時間が増大したり、あるいは処理中に使用メモリがオーバーフローするというような事態につながることもあり、好ましくない。
【０００５】
このような事態を避けるため、ＬＳＩパターンデータを圧縮するというアプローチは有効である。ＬＳＩパターンの中に、同じ図形の繰り返しや、異なる図形同士が同じ相対的位置関係で繰り返されている部分があれば、それらを１つのセルとするセル階層化を行うことで、ＬＳＩパターンを圧縮し、データ量を小さくすることができる。データ量が小さくなれば、上述のような問題は解決できるので、セルを階層化してデータを圧縮する技術は昨今注目されている。
【０００６】
特に、半導体のメモリセルや液晶回路の画素セルの場合、数百個×数百個程度から大きいものでは数千個×数千個程度のアレイ状にセルが配置され、アレイ領域がＬＳＩパターンの大部分を占めることも多くある。このような配置がなされたセルがフラット化されると、セル階層化されている状態に比してデータ量が著しく増大する。そのため、フラット化されたアレイ領域を階層化することはとりわけ重要である。
【０００７】
係る問題を解決すべく、等間隔で繰り返し出現する図形の二次元アレイを単独図形単位で生成し、単独図形のピッチと配置個数が同じアレイをグループ化して複数図形のブロックアレイし、これに基づいてセル階層化を行い、データ圧縮を実現する技術がすでに公知である（例えば、特許文献１参照）。
【０００８】
【特許文献１】特開２００１−２３０６７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ＬＳＩパターンは通常、何らかの電気回路であるため、レイヤの特性にもよるが、隣接するセル同士が重なっていることが多い。換言すれば、アレイピッチが１つの種セル（アレイ配置の基準となるセル）の外接矩形サイズよりもアレイピッチの方が小さい状態で配置されていることが多い。また、こうした場合、配置位置に重なりのある図形と重なりのない図形とでは、ピッチや繰り返し個数が異なることもよくある。
【００１０】
図４（ａ）は、この状態にあるＬＳＩパターンを例示する図であり、図４（ｂ）はその種セルを示す図である。図４（ａ）のＬＳＩパターンは、種セルが４種類の図形ａ、ｂ、ｃ、ｄによって構成されており、縦方向に隣接する種セルの図形ａ同士、および横方向に隣接する種セルの図形ｂ同士が重なるように、アレイ配置がなされている。なお、種セルのｘ軸、ｙ軸方向のサイズがそれぞれＳ１、Ｓ２であり、種セルのｘ軸、ｙ軸方向のピッチがそれぞれｐ１、ｐ２であるとする。
【００１１】
図４（ａ）のアレイ配置にあるＬＳＩパターンがフラット化されている場合、特許文献１に開示された技術を適用してデータ圧縮を試みると、まず、個々の図形ごとに（つまりは図形ａ、ｂ、ｃ、ｄのそれぞれについて）、２次元アレイが生成される。図１４は、この２次元アレイを示す図である。ところが、これら４つの図形についての２次元アレイのうち、等ピッチかつ等個数の関係にあるのは図形ｃと図形ｄとだけであるので、階層化できるのはこの２つの図形のみであり、図形ａと図形ｂとは、それぞれ別個に階層化されるに過ぎない。図１５は、この場合のセル階層化の結果を示す図である。すなわち、特許文献１に開示の方法では、図形ｃと図形ｄのみについて１つのセルとして取り扱うことが出来るように記述されたＬＳＩパターンデータが得られるに過ぎない。
【００１２】
すなわち、特許文献１に開示された方法では、ピッチや繰り返し個数が異なる図形を含む場合に、不充分なセル階層化しか実現することは出来ない。
【００１３】
本発明は、上記課題に鑑みてなされたものであり、セル階層化を十分に行うことができ、データ圧縮効率の高いパターンデータ圧縮処理技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、請求項１の発明は、複数の図形が空間的に配置されることで形成される図形パターンがフラット化状態で記述されてなるパターンデータに基づいて、前記図形パターンをセル階層化した形式にて記述する階層化データを生成するデータ処理装置であって、前記図形パターンに含まれる１以上のアレイについての繰り返しピッチのうちの最頻出のピッチである代表アレイピッチを取得する代表アレイピッチ取得手段と、
前記パターンデータを対象に、前記代表アレイピッチにピッチを固定してアレイ化を行うピッチ固定アレイ化手段と、前記ピッチ固定アレイ化手段によって生成された１以上のピッチ固定アレイの中から、繰り返し個数が最小であるアレイを基準アレイとして特定する基準アレイ特定手段と、前記図形パターンにおいて、前記基準アレイを構成する図形の重心を中心とし、前記代表アレイピッチで囲まれた矩形領域内に位置する、前記１以上のピッチ固定アレイのそれぞれを構成する図形を、前記セル階層化における繰り返し単位である種セルの構成図形として特定し、前記構成図形を含む外接矩形を前記種セルとして設定する種セル設定手段と、前記種セルに基づいて前記図形パターンについてのセル階層化処理を行い、前記種セルを特定する情報と、前記種セルのピッチ情報と繰り返し個数情報とを含む前記階層化データを生成する階層化処理手段と、を備えることを特徴とする。
【００１５】
請求項２の発明は、請求項１に記載のデータ処理装置であって、前記代表アレイピッチ取得手段が、前記図形パターンのなかで、同一形状を有し同一ピッチで繰り返し配置されている図形群をアレイ化するアレイ生成手段と、前記アレイ生成手段によって生成された１以上のアレイの繰り返しピッチの中から、最小のピッチを代表アレイピッチとして検出する代表アレイピッチ検出手段と、を備えることを特徴とする。
【００１６】
請求項３の発明は、請求項１または請求項２に記載のデータ処理装置であって、前記代表アレイピッチよりも大きなサイズの図形を前記代表アレイピッチごとに切断する切断処理手段、をさらに備え、前記切断処理によって得られた切断図形を前記パターンデータを構成する図形に含めて前記ピッチ固定アレイ化を行う、ことを特徴とする。
【００１７】
請求項４の発明は、請求項１ないし請求項３のいずれかに記載のデータ処理装置であって、前記図形パターンを構成する図形の少なくとも一部が、単一の図形と同等に取り扱われている複数の図形からなる図形の組である、ことを特徴とする。
【００１８】
請求項５の発明は、プログラムであって、コンピュータが備えるＣＰＵとメモリとを使用することにより、前記コンピュータを、請求項１ないし請求項４のいずれかに記載のデータ処理装置として機能させることを特徴とする。
【発明の効果】
【００１９】
請求項１ないし請求項５の発明によれば、繰り返しピッチおよび繰り返し個数が基準アレイを構成する図形と部分的にでも共通する図形を、基準アレイを構成する図形と１つの種セルで表現することが出来るので、フラット化状態にある図形パターンが繰り返しピッチや繰り返し個数が異なる図形を含む場合であっても、できるだけ多くの図形を種セルに含むようにして良好にセル階層化することが出来る。
【００２０】
特に、請求項３の発明によれば、そのままではセル階層化の対象とならない、大きなサイズの図形を含む図形パターンであっても、セル階層化することが出来るので、パターンデータが当該図形パターンを含む場合であっても、良好に圧縮できる。
【発明を実施するための最良の形態】
【００２１】
＜装置構成＞
図１は、本実施の形態に係るデータ処理装置１の構成を概略的に示す図である。データ処理装置１は、少なくとも部分的にフラット化状態にある（フラット化している、などともいう）ＬＳＩパターンデータから、階層化がなされた（階層化状態にある、などともいう）ＬＳＩパターンデータを生成する処理を行う装置である。
【００２２】
なお、本実施の形態において、ＬＳＩパターンデータがフラット化状態にあるとは、ＬＳＩパターンを構成する１つ１つの図形についての形状情報と位置情報とを全て書き下す態様にて、ＬＳＩパターンデータが記述されてなる状態をいう。具体的には、例えば、全ての図形（あるいは図形の外接矩形）について、頂点位置の座標を列挙することによって記述される。
【００２３】
なお、本実施の形態において、図形とは、単一の図形のみならず、単一の図形と同等に取り扱われている複数の図形からなる図形の組も含むものとする。係る場合、この複数の図形は、部分的に階層化されているともいう。
【００２４】
一方、ＬＳＩパターンデータが階層化状態にあるとは、ＬＳＩパターンの繰り返し単位である種セルを特定する情報（種セルを構成する図形についての形状情報と種セル内での位置情報）と、該種セルの配置のための情報（基準位置情報、ピッチ情報、繰り返し個数情報）とで、ＬＳＩパターンデータが記述されてなる状態をいう。ここで、基準位置情報とは、繰り返し配置の基準となる位置（始点位置）を特定する座標値である。
【００２５】
加えて、同一形状を有し同一ピッチで繰り返し配置されている図形群を、それぞれの図形の形状情報と、基準位置情報と、ピッチ情報と、繰り返し個数情報とで記述することを、アレイ化という。なお、アレイ化の対象となった図形群をアレイと称することとする。
【００２６】
データ処理装置１は、コンピュータによって実現されるのがその好適な一態様である。すなわち、データ処理装置１は、マウスやキーボードなどからなる操作部１１、ディスプレイからなる表示部１２、ハードディスクなどからなる記憶部１３、外部の装置との間で種々のデータの送受信を担う、例えばＬＡＮやＵＳＢ接続などが可能なインターフェース部１４、さらには、ＤＶＤ−ＲＡＭやＲＶＤ−ＲＷ、あるいはマイクロドライブなどといった可搬性の記録媒体との間でデータのリード／ライトを行うリード／ライト部１５、ＣＰＵ１６ａ、ＲＯＭ１６ｂ、ＲＡＭ１６ｃなどからなる制御部１６などを主として備える。
【００２７】
図２は、データ処理装置１において実現される機能的構成について示す図である。図２においては、データ処理装置１における種々のデータの流れを併せて示している。データ処理装置１においては、記憶部１３に記憶されているプログラム１３ｐがＣＰＵ１６ａにより実行されることにより、制御部１６およびその他の各部の作用によって、機能的構成要素として、第１アレイ化処理部２と、代表アレイピッチ検出部３と、第２アレイ化処理部４と、基準アレイ特定部５と、種セル生成部６と、階層化処理部７と、切断処理部８とが、主として実現される。データ処理装置１における種々の操作は、ＧＵＩを介して行われる。すなわち、操作部１１を介して種々の処理用のメニューが表示部１２に呼び出され、その表示内容に基づいて処理条件の設定や処理の実行指示が行えるようになっている。係るデータ処理装置１は、インターフェース部１４やリード／ライト部１５を介して、他の装置との間で直接又は間接に、階層化処理前後のＬＳＩパターンデータその他のデータの授受が可能に構成されてなる。
【００２８】
第１アレイ化処理部２は、ＬＳＩパターンの少なくとも一部分についてフラット化状態にあるＬＳＩパターンデータである処理対象データＤ０について、アレイ化する処理を担う。具体的には、例えば、各図形ごとに該図形を構成する複数の頂点位置をその中の１つを基準とする相対位置座標に変換し、基準とした頂点位置同士の差分を算出して、この差分値が同じである図形同士を、同一アレイに属する図形であると特定することで、アレイ化が行えたことになる。その場合、算出した頂点位置の差分値が、該アレイのピッチ（アレイピッチ）となる。
【００２９】
第１アレイ化処理部２は、係るアレイ化の結果を第１アレイ化データＤＡ１として出力する。第１アレイ化データＤＡ１は、それぞれのアレイを構成する図形の形状情報と、基準位置情報と、ピッチ情報（ｘ、ｙ軸方向それぞれのピッチ）とを少なくとも含むが、さらに、繰り返し個数情報（ｘ、ｙ軸方向それぞれの繰り返し個数）を含んでいてもよい。なお、本実施の形態においては、ピッチ情報を（ｓ，ｔ）、繰り返し個数情報を（ｕ，ｖ）などと記述することとする。
【００３０】
代表アレイピッチ検出部３は、第１アレイ化データＤＡ１の記述内容を参照し、処理対象データＤ０についての代表アレイピッチを検出する処理を担う。ここで、代表アレイピッチとは、第１アレイ化データＤＡ１にピッチ情報として記述されている各アレイのピッチ情報のうち、最頻出のものをいう。代表アレイピッチ検出部３は、該当するピッチ情報を代表アレイピッチデータＤＰとして出力する。
【００３１】
なお、処理対象データＤ０とされているＬＳＩパターンデータがもともと階層化状態にあったデータである場合など、セルのピッチ情報が既知アレイピッチ情報ＩＰとして操作部１１を通じて与えられた場合には、代表アレイピッチ検出部３が既知アレイピッチ情報ＩＰの内容に基づいて代表アレイピッチを特定し、その結果を出力するようになっていてもよい。
【００３２】
第２アレイ化処理部４は、処理対象データＤ０について、代表アレイピッチデータＤＰに記述されている代表アレイピッチのみが各アレイのピッチとなるようにアレイ化を行う。この第２アレイ化処理部４によるアレイ化のことを特に、ピッチ固定アレイ化とも称する。また、生成されたアレイをピッチ固定アレイとも称する。具体的には、例えば、各図形ごとに該図形を構成する複数の頂点位置をその中の１つを基準とする相対位置座標に変換し、得られた相対位置座標が同じである図形を同一のアレイを構成しうる図形として特定し、基準とした頂点位置同士の差分を算出して、得られた差分値が代表アレイピッチと同じである図形を、グルーピングすることによって行える。
【００３３】
第２アレイ化処理部４は、生成されたピッチ固定アレイを特定する情報を第２アレイ化データＤＡ２として出力する。すなわち、第２アレイ化データＤＡ２は、各ピッチ固定アレイを構成する図形の形状情報と、基準位置情報と、代表アレイピッチと、繰り返し個数情報とを含む。
【００３４】
この場合、第１アレイ化処理部２におけるアレイ化処理によって生成されたアレイのうち、ピッチが代表アレイピッチと一致するアレイについては（第１アレイ化データに記述されているピッチ情報が、代表アレイピッチと合致するアレイについては）、第１アレイ化データＤＡ１の記述内容をそのままピッチ固定アレイ化処理の結果として利用する態様であってもよい。
【００３５】
一方で、第１アレイ化処理部２におけるアレイ化において代表アレイピッチとは異なるピッチを有するように生成されたアレイに属する図形群については、ピッチ固定アレイ化を行っても、全ての図形が１つのアレイとなることはない。この場合は、一部の図形のみがピッチ固定アレイ化がされ、残りは対象とならないか、基準位置や繰り返し個数が相異なる複数のアレイに分けてピッチ固定アレイ化がなされるか、全くピッチ固定アレイ化の対象とならないか、のいずれかとなる。
【００３６】
基準アレイ特定部５は、第２アレイ化データＤＡ２の記述内容に記述されてなる、各ピッチ固定アレイについての繰り返し個数情報に基づいて、基準アレイを特定する処理を担う。ここで、基準アレイとは、各ピッチ固定アレイのうち、繰り返し個数が最頻出のものであって、かつ、原則として、ｘ軸方向、ｙ軸方向の繰り返し個数がいずれも最小のものをいう。また、基準アレイについての繰り返し個数のことを、代表配置個数と称する。
【００３７】
例えば、繰り返し個数が、（ｍ，ｎ）、（ｍ＋α，ｎ）、（ｍ，ｎ＋β）、（ｍ＋γ，ｎ＋δ）なるアレイ（ｍ、ｎ、α、β、γ、δは自然数）の頻度が同じであれば、（ｍ，ｎ）なる繰り返し個数のアレイが基準アレイとして特定され、（ｍ，ｎ）が代表配置個数となる。
【００３８】
なお、このような基準アレイを特定するのは、後述する階層化処理の際に、出来るだけ多くの図形を１つの種セルによって階層化できるようにするためである。すなわち、（ｍ，ｎ）なる繰り返し個数のアレイを基準アレイとした場合、繰り返し個数が（ｍ＋α，ｎ）、（ｍ，ｎ＋β）、（ｍ＋γ，ｎ＋δ）なるアレイについても、少なくとも、基準アレイと同じく、ｘ軸方向についてはｍ個、ｙ軸方向についてはｎ個の図形を含んでいることから、その部分については基準アレイを構成する図形とともに１つの種セルによって階層化することが出来る。仮に、繰り返し個数が（ｍ＋α，ｎ）のアレイを基準アレイと定めてしまうと、（ｍ、ｎ）や（ｍ，ｎ＋β）なる繰り返し個数を有するアレイに属する図形ついては、ｘ軸方向の数がα個足りないために、基準アレイとしたアレイに属する図形とは同一の種セルによって階層化されることはないことになる。
【００３９】
ただし、繰り返し個数が（ｍ，ｎ）、（ｍ−α，ｎ＋β）、（ｍ＋γ，ｎ−δ）なるアレイ（ｍ、ｎ、α、β、γ、δ、ｍ−α、ｎ−δは自然数）の少なくとも２つについての頻度が同じであった場合には、ｘ軸方向、ｙ軸方向の繰り返し個数がいずれも最小という条件のアレイは存在しない。この場合は、いずれか１つのアレイを任意に基準アレイとして特定することになる。この場合には、基準アレイに以外のアレイに属する図形については、基準アレイに属する図形とは同じ種セルによって階層化することは出来なくなるため、別の種セルを新たに設定して階層化することが必要となる。
【００４０】
つまりは、第２アレイ化処理部４によるピッチ固定アレイ化と、これに続く、基準アレイ特定部５における基準アレイの特定という２つの処理は、ＬＳＩパターンに配置されている図形のうち、繰り返しのピッチが共通し、同じ繰り返し個数で繰り返されているものを、できるだけ１つの種セルで階層化できるようにするための処理であるといえる。
【００４１】
基準アレイ特定部５は、基準アレイと代表配置個数を特定する情報を含む基準アレイデータＤＡＣを出力する。
【００４２】
種セル生成部６は、セル階層化後の繰り返し単位となる種セルを設定し、その内容を記述した種セルデータＤＣを出力する。種セルは、基準アレイを構成する図形の重心位置を中心として、代表アレイピッチによって区分された矩形領域に含まれる、各ピッチ固定アレイの図形の外接矩形として設定される。種セル生成部６は、種セル構成する図形についての形状情報と種セル内での位置情報を含む種セルデータＤＣが生成される。
【００４３】
階層化処理部７は、種セルデータＤＣに基づいて、処理対象データＤ０を階層化し、階層化データＤＬを生成する処理を担う。具体的には、処理対象データＤ０で特定されるＬＳＩパターンのうち、種セル生成部６によって設定された種セルが代表配置個数を繰り返し個数として繰り返されてなる部分を、つまりは種セルを繰り返し単位とするアレイを特定し、該アレイにおける種セルのピッチを、種セルピッチ情報として取得する。例えば、種セルと同じ配置関係にある図形をグルーピングし、それらの図形の全てを含む外接矩形の座標位置を特定するという処理を、該当する全ての図形に対して行うことで、全ての種セルの配置位置が特定される。また、それらの外接矩形のピッチが、種セルのピッチとなる。
【００４４】
階層化処理部７は、取得された種セルピッチ情報と、代表配置個数と、種セルデータＤＣの記述内容（種セルの構成を特定する内容である）とを組み合わせて、階層化データＤＬを生成する。
【００４５】
なお、ＬＳＩパターンを構成する全ての図形が種セルデータＤＣに基づいて階層化されるとは限らず、階層化の対象とならなかった図形が存在する場合がある。係る場合、階層化データＤＬは処理対象データＤ０の全てに基づいて生成されたデータではない。係る場合の階層化データＤＬを特に部分階層化データＤＬと称することがある。
【００４６】
このような場合、階層化処理部７は、処理対象データＤ０から階層化データＤＬの生成対象となった図形部分を除いた未完了差分データＤＳを生成する。この未完了差分データＤＳは、新たな処理対象データＤ０として取り扱われることになり、新たに種セルが設定され、これに基づいて部分階層化データＤＬが別途生成されることになる。このようにして得られた全ての部分階層化データＤＬを合成することで、最終的な階層化データが生成されることになる。
【００４７】
切断処理部８は、代表アレイピッチの範囲に収まらないほど大きな図形が存在する場合に、これを代表アレイピッチの大きさに切断する処理を担う。切断処理部８は、係る切断処理の結果を、切断化済データＤ０αとして出力する。該切断化済データＤ０αが生成された場合には、上述した第２アレイ化処理部４におけるピッチ固定アレイ化、種セル生成部６における種セルの生成、階層化処理部７における階層化処理は、切断化済データＤ０αを対象に行われることになる。
【００４８】
なお、階層化データＤＬの生成に至るまでに各部において出力される、第１アレイ化データＤＡ１、代表アレイピッチデータＤＰ、第２アレイ化データＤＡ２、基準アレイデータＤＡＣ、種セルデータＤＣのデータフォーマットについては、後段の処理で参照可能な形式で記述されていれば特段の制限はない。
【００４９】
また、階層化データＤＬは、これを用いた処理を行う図示しない所定の処理装置（例えば半導体製造装置など）で認識可能な形式で記述されていればよい。
【００５０】
＜階層化処理の流れ＞
次に、データ処理装置１において行われるＬＳＩパターンのセル階層化の流れを具体例に基づいて詳細に説明する。図３は、係るセル階層化の流れを概略的に示す図である。ここでは、図４（ａ）のＬＳＩパターンが処理対象データＤ０に記述されている場合を例として説明する。
【００５１】
まず、第１アレイ化処理部２によってアレイ化が行われる（ステップＳ１）。図４（ａ）に示すＬＳＩパターンの場合であれば、４種類の図形ａ、ｂ、ｃ、ｄが存在するので、これらについてのアレイ化が行われ、４つのアレイが生成されることになる。図５が、該ＬＳＩパターンについてアレイ化した状態を示す図である。例えば、図形ａについてのアレイＡａにおけるｘ軸方向のピッチをＰａ１、ｙ軸方向のピッチをＰａ２などと表すようにすると、図形ａ、図形ｂ、図形ｃ、図形ｄについてのアレイＡａ、Ａｂ、Ａｃ、Ａｄの各方向のピッチはそれぞれ、
アレイＡａ：（Ｐａ１，Ｐａ２）＝（ｐ１／２，ｐ２）；
アレイＡｂ：（Ｐｂ１，Ｐｂ２）＝（ｐ１，ｐ２）；
アレイＡｃ：（Ｐｃ１，Ｐｃ２）＝（ｐ１，ｐ２）；
アレイＡｄ：（Ｐｄ１，Ｐｄ２）＝（ｐ１，ｐ２）；
となる。また、例えば、アレイＡａのｘ軸方向の繰り返し個数をＮａ１、ｙ軸方向の繰り返し個数をＮａ２などと表すようにすると、アレイＡａ、Ａｂ、Ａｃ、Ａｄの各方向の繰り返し個数はそれぞれ、
アレイＡａ：（Ｎａ１，Ｎａ２）＝（６，４）；
アレイＡｂ：（Ｎｂ１，Ｎｂ２）＝（４，３）；
アレイＡｃ：（Ｎｃ１，Ｎｃ２）＝（３，３）；
アレイＡｄ：（Ｎｄ１，Ｎｄ２）＝（３，３）；
となる。
【００５２】
次に、代表アレイピッチ検出部３によって代表アレイピッチが検出される（ステップＳ２）。図４のＬＳＩパターンの場合であれば、アレイＡｂ、Ａｃ、Ａｄのピッチがいずれも（ｐ１，ｐ２）であるので、これが処理対象データＤ０についての代表アレイピッチに該当する。
【００５３】
次に、第２アレイ化処理部４によって、ピッチ固定アレイ化が行われる（ステップＳ３）。図６は、図４（ａ）に示すＬＳＩパターンについて、ピッチ固定アレイ化を行った状態を示す図である。
【００５４】
上述のように、代表アレイピッチは、第１アレイ化処理部２でアレイ化されたアレイＡｂ、Ａｃ、Ａｄのそれぞれのピッチに基づいて決定されている。よって、これらのアレイについては、そのままピッチ固定アレイとなる。従って、第１アレイ化データＤＡ１に記述されていたそのままの内容を第２アレイ化データＤＡ２においても記述する。
【００５５】
一方、代表アレイピッチとは異なる（ｐ１／２，ｐ２）なるアレイピッチを有してなるアレイＡａを構成する図形ａについては、ｘ軸方向のピッチが代表アレイピッチの１／２である。よって、図形ａについては、ｘ軸方向についてアレイＡａの２倍のピッチを有するようにピッチ固定アレイ化がなされることになる。すなわち、図６に示すように、２つのアレイＡａ１とアレイＡａ２とが得られることになる。
【００５６】
結局のところ、図４（ａ）に示すＬＳＩパターンについては、ピッチ固定アレイ化によって５つのピッチ固定アレイＡａ１、Ａａ２、Ａｂ、Ａｃ、Ａｄが得られることになる。そして、ピッチ固定アレイＡａ１、Ａａ２、Ａｂ、Ａｃ、Ａｄの各方向の繰り返し個数はそれぞれ、
アレイＡａ１：（Ｎａ１１，Ｎａ１２）＝（３，４）；
アレイＡａ２：（Ｎａ２１，Ｎａ２２）＝（３，４）；
アレイＡｂ：（Ｎｂ１，Ｎｂ２）＝（４，３）；
アレイＡｃ：（Ｎｃ１，Ｎｃ２）＝（３，３）；
アレイＡｄ：（Ｎｄ１，Ｎｄ２）＝（３，３）；
となる。
【００５７】
ピッチ固定アレイ化がなされると、基準アレイが特定される（ステップＳ４）。上述した各ピッチ固定アレイにおいては、アレイＡｃとアレイＡｄがいずれも（３，３）という繰り返し個数を有している。この場合、いずれか１つが基準アレイとして選択されればよい。その選択は任意になされてよい。例えば、オペレータが選択可能とされていてもよいし、第２アレイ化データＤＡ２においてアレイの情報が記述されている順の早い方が選択されるようになっていてもよい。ここでは、アレイＡｃが検出元とされる場合について説明する。いずれにせよ、代表配置個数は（３，３）となる。
【００５８】
代表配置個数が（３，３）であるアレイが基準アレイとして特定されることで、繰り返し個数が（３，４）や（４，３）であるアレイを構成する図形についても、その一部分については、基準アレイを構成する図形と同じ種セルで階層化を行えることになる。
【００５９】
基準アレイが特定されると、種セルの設定が行われる（ステップＳ５）。
【００６０】
上述したように、種セルは、基準アレイを構成する図形を中心とする矩形領域内に含まれる、各ピッチ固定アレイを構成する図形によって定められる。なお、矩形領域の少なくとも一部に含まれている図形であれば種セルを構成する図形として取り扱える。また、該矩形領域内に同一のピッチ固定アレイについての図形が複数存在する場合は、そのうちのいずれか１つのみが、任意に選択されればよい。
【００６１】
図７は、種セル生成部６による具体的な種セルの設定の仕方を説明するための図である。種セル生成部６においては、まず、基準アレイの四方端部のいずれかにある図形を特定する。図７においては基準アレイＡｃの左下端部の図形を特定した場合を図示している。そして、この特定した図形の重心位置を中心として、代表アレイピッチで区分される矩形領域内を特定する。図７においては矩形領域Ｒ１がこれに該当する。そして、この矩形領域Ｒ１内に含まれる各ピッチ固定アレイの図形を特定する。図７においては、斜線を付した図形が特定されたものとする。なお、図形ａ１、ａ２、ｂのように矩形領域Ｒ１内に候補が２つある場合には、いずれか一方が選択されればよい。例えば、原点に近い方が選択されるように定められていてもよい。
【００６２】
矩形領域Ｒ１内に属する各ピッチ固定アレイの図形が選択されると、今度は、基準アレイであるアレイＡｃにおいて矩形領域Ｒ１と対角位置にある図形（図７においては、右上端部）を中心とする矩形領域Ｒ２を特定し、その中に、矩形領域Ｒ１において選択された図形が存在するか否かを確認する。矩形領域Ｒ１および矩形領域Ｒ２の両方に存在する図形を含む最小の外接矩形を、種セルとして設定する。なお、矩形領域Ｒ２は、矩形領域Ｒ１がアレイの四方端部のどの位置に定められたとしても、対角位置の関係にあるように設定される。
【００６３】
図８は、図７の結果に基づいて設定された種セルＣ１を示す図である。すなわち、種セルＣ１は、図形ａ１、ａ２、ｂ、ｃ、ｄを１つずつ、図８に示すような相対的位置関係で有する外接矩形領域である。種セル生成部６は、この種セルＣ１について、これを構成する図形についての形状情報と種セル内での位置情報を含む種セルデータＤＣを生成する。すなわち、種セルＣ１についての種セルデータＤＣは、図形ａ１、ａ２、ｂ、ｃ、ｄの形状情報と、それぞれの図形の種セル内における相対位置を示す情報とから構成される。
【００６４】
種セルデータＤＣが生成されると、階層化処理部７は、種セルデータＤＣの記述内容に基づいて、該種セルＣ１を繰り返し単位とする階層化処理を行う（ステップＳ６）。すなわち、処理対象データＤ０で特定されるＬＳＩパターンのうち、種セルＣ１を繰り返し単位とするアレイを特定し、該アレイにおける種セルＣ１のピッチを、種セルピッチ情報として取得する。図９は、種セルＣ１についての種セルデータＤＣに基づいて階層化処理を行った結果を例示する図である。階層化処理の結果、種セルＣ１についての３×３のアレイが生成されている。すなわち、図９においては太線で示す矩形が１つ１つの種セルに相当し、この矩形内に存在する図形は全て階層化処理の対象とされたことを意味する。
【００６５】
係る階層化処理が終わると、階層化処理部７はＬＳＩパターンを構成する全ての図形が階層化の対象とされたか否かを判定する（ステップＳ７）。全ての図形が階層化されていれば（ステップＳ７でＹＥＳ）、処理は終了する。
【００６６】
図９に示した結果では、図形ａ（ａ１、ａ２）、ｂの一部が階層化の対象とされずに残っている（ステップＳ７でＮＯ）。この場合は、階層化処理部７が、処理対象データＤ０から階層化処理の対象となった図形（図９において太線矩形領域内に属する図形）のデータを消去することで、階層化の対象とされなかった図形ａ、ｂの一部のみの情報を記述してなる未完了差分データＤＳを生成する。
【００６７】
そして、生成された未完了差分データＤＳを新たな処理対象データＤ０として、ステップＳ１からの処理が再び行われることになる。図９に示した結果に基づき未完了差分データＤＳが生成される場合について言えば、残っている図形ａもしくは図形ｂのいずれかについて次の階層化が行われ、さらに再度の処理で、残りの図形についての階層化が行われることになる。
【００６８】
図１０は、全ての図形について階層化がなされた状態を示す図である。すなわち、処理対象データＤ０において全ての図形についての情報を書き下すことによって表現されていたＬＳＩパターンは、２個の図形ａ（ａ１、ａ２）と図形ｂと図形ｃとを含む種セルＣ１による３×３のアレイ（繰り返し個数が（３，３）のアレイの意）と、図形ａからなる種セルＣ２による６×１のアレイと、図形ｂからなる種セルＣ３による１×３のアレイとで表現されることになる。なお、それぞれの種セルについての繰り返し個数は、代表配置個数に一致している。最終的に階層化処理が終了した時点での階層化データＤＬは、３つの種セルＣ１、Ｃ２、Ｃ３の内容（含まれる図形の形状と相対位置）を特定する情報と、各種セルのピッチ情報と繰り返し個数情報とが記述されたものとして出力される。
【００６９】
なお、種セルの設定の際に、代表アレイピッチで区分される矩形領域内に属する図形を選択する態様は、上述の場合には限られない。従って、設定される種セルの内容は、上述の場合と異なることがある。係る場合、これに基づく階層化処理結果（階層化データＤＬの記述内容）も、上述の場合とは異なることになる。図１１は、種セルＣ１を生成する場合とは異なる図形選択を行って設定される種セルＣ１’を示す図である。また、図１２は、種セルＣ１’の設定後、全ての図形について階層化を行った後の結果を例示する図である。図１２に示すように、係る場合、階層化処理を行うと、処理対象データＤ０のＬＳＩパターンは、図形ａ（ａ１、ａ２）と図形ｂと図形ｃとを含む種セルＣ１’による３×３のアレイと、図形ａからなる種セルＣ２’による６×１のアレイと、図形ｂからなる３種セルＣ３’による１×３のアレイとで表現されることになる。
【００７０】
この結果において、それぞれの種セルＣ１’、Ｃ２’、Ｃ３’に含まれる図形の種類と個数、各種セルを繰り返し単位とするアレイのピッチと繰り返し個数は、図１０に示す、種セルＣ１、Ｃ２、Ｃ３を設定して階層化した場合と同じである。両者が異なるのは、異なるのは種セル内の各図形の相対位置と、種セルの配置位置（基準位置）のみである。これらが異なったとしても、階層化データのデータサイズには違いは生じないので、元の処理対象データＤ０は、種セルの設定の仕方（種セルを構成する図形の選択の仕方）によらず、同程度に圧縮されることになる。
【００７１】
＜大きな図形の切断＞
ＬＳＩパターンの内容によっては、代表アレイピッチの範囲に収まらないほど大きな図形が存在することがある。図１３（ａ）は、そうした図形の一例を示す図である。図１３（ａ）においては、略矩形の枠体が連続してなる図形が存在する場合を例示している。なお、図１３においては厳密な図示を省略しているが、係る図形は、実際には一筆書きで記述された図形である。このような図形は、もともとは重なりのあった複数の図形として記述されていたものの、データ処理の過程で重なり情報が除去されることなどによって生じることが多い。こうした図形が存在する場合、上述のような態様では、この図形はそれ自体で１つの種セルとして取り扱わざるを得ないことになるが、その場合、該種セルの情報として、該図形の全ての形状情報（全ての頂点位置の情報）を書き下す必要があるため、結局のところ、ＬＳＩパターンデータのデータサイズを十分に圧縮することが出来ないことになる。
【００７２】
こうした事態を避けるべく、本実施の形態に係るデータ処理装置１においては、そうした代表ピッチよりも大きな図形を、それぞれが代表アレイピッチの範囲内の大きさを有する複数図形に切断して、種セルの構成要素として取り扱えるようにすることが出来る。
【００７３】
具体的には、ステップＳ２において代表アレイピッチが検出されると、ステップＳ３におけるピッチ固定アレイ化の前に、切断処理部８の作用によって、係る切断処理を行うことが可能とされてなる。
【００７４】
なお、切断位置は、図１３（ｂ）に例示するように、対象図形の端点を原点とし、代表アレイピッチを単位とする格子上の領域に１つの切断図形が含まれるように定めればよい。あるいは、別の位置を基準とすることも可能である。
【００７５】
係る切断処理が行われると、切断処理部８は、元々の処理対象データＤ０における切断対称図形の記述を、個々の切断図形についての情報に書き換え、これを切断化済データＤ０αとして出力する。該切断化済データＤ０αが生成された場合には、ステップＳ３以降の処理は、処理対象データＤ０に代えて切断化済データＤ０αを対象に行われることになる。
【００７６】
以上、説明したように、本実施の形態によれば、ＬＳＩパターンデータを構成する図形について、通常のアレイ化処理（第１アレイ化処理）で定まる最頻出のピッチである代表アレイピッチに各図形についてのピッチを固定したアレイ化処理（第２アレイ化処理）を行い、その結果から特定される基準アレイに基づいて繰り返し個数が共通する部分を１つの種セルとして階層化するようにすることで、フラット化状態にあるＬＳＩパターンが繰り返しピッチや繰り返し個数が異なる図形を含む場合であっても、できるだけ多くの図形を種セルに含むようにして良好にセル階層化することが出来る。すなわち、高い圧縮効率でのセル階層化が実現される。また、１つの種セルにより多くの図形が含まれることは、本来ひとかたまりで取り扱うべき図形が別々のセルに属するようになることが抑制されることでもあるので、後工程におけるセルのハンドリングのしやすさの観点からも好ましいといえる。
【図面の簡単な説明】
【００７７】
【図１】データ処理装置１の構成を概略的に示す図である。
【図２】データ処理装置１において実現される機能的構成について示す図である。
【図３】セル階層化の流れを概略的に示す図である。
【図４】ＬＳＩパターンを例示する図である。
【図５】アレイ化した状態を示す図である。
【図６】ピッチ固定アレイ化を行った状態を示す図である。
【図７】種セルの設定の仕方を説明するための図である。
【図８】種セルＣ１を示す図である。
【図９】種セルデータＤＣに基づいて階層化処理を行った結果を示す図である。
【図１０】全ての図形について階層化がなされた状態を示す図である。
【図１１】種セルＣ１’を示す図である。
【図１２】種セルＣ１’を設定した後、全ての図形について階層化処理を行った結果を示す図である。
【図１３】図形の切断を行う場合について説明するための図である。
【図１４】従来の手法で得られる２次元アレイを示す図である。
【図１５】従来の手法で得られる階層化結果を示す図である。
【符号の説明】
【００７８】
１  データ処理装置
１１  操作部
１２  表示部
１３  記憶部
１３ｐ  プログラム
１４  インターフェース部
１５  リード／ライト部
１６  制御部
２  第１アレイ化処理部
３  代表アレイピッチ検出部
４  第２アレイ化処理部
５  基準アレイ特定部
６  種セル生成部
７  階層化処理部
８  切断処理部
Ａａ、Ａａ１、Ａａ２、Ａｂ、Ａｃ、Ａｄ  アレイ
Ｃ１、Ｃ２、Ｃ３、Ｃ１’、Ｃ２’、Ｃ３’  種セル
【図１】
2008250759.tif 000003
【図２】
2008250759.tif 000004
【図３】
2008250759.tif 000005
【図４】
2008250759.tif 000006
【図５】
2008250759.tif 000007
【図６】
2008250759.tif 000008
【図７】
2008250759.tif 000009
【図８】
2008250759.tif 000010
【図９】
2008250759.tif 000011
【図１０】
2008250759.tif 000012
【図１１】
2008250759.tif 000013
【図１２】
2008250759.tif 000014
【図１３】
2008250759.tif 000015
【図１４】
2008250759.tif 000016
【図１５】
2008250759.tif 000017