(57)【要約】      （修正有）【課題】ビット数を削減し、データサイズを低減する描画装置を提供する。【解決手段】描画装置１００は、複数のパターンの図形コードとアレイフラグとアレイ個数とアレイピッチの少なくとも１つを含むパターン情報を取得するパターン分割部４６と、所定の領域毎に、各パターン情報と各パターン情報の使用回数とを関連させた累積テーブル作成部５０と、ハフマンツリーを作成するハフマンツリー作成部５２と、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように暗号化した２進数の可変長コードとを関連させたハフマンテーブルを作成するハフマンテーブル作成部５４と、可変長コードを用いた所定のフォーマットで、描画データに定義される所定の領域内のデータを変換するフォーマット変換部５６と、変換された所定の領域内のデータに基づいて、試料に複数のパターンを描画する描画部１５０と、を備えたことを特徴とする。【選択図】図１
2010067808.tif 000002
【特許請求の範囲】
【請求項１】
描画データを記憶する記憶部と、
前記描画データを基に、定義された複数のパターンの図形コードとアレイフラグとアレイ個数とアレイピッチの少なくとも１つを含むパターン情報を取得する取得部と、
所定の領域毎に、取得された複数のパターン情報を基に、各パターン情報と各パターン情報の使用回数とを関連させた第１のテーブルを作成する第１のテーブル作成部と、
前記第１のテーブルを基に、ハフマンツリーを作成するハフマンツリー作成部と、
前記ハフマンツリーを基に、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードとを関連させた第２のテーブルを作成する第２のテーブル作成部と、
前記第２のテーブルを基に、前記可変長コードを用いた所定のフォーマットで、前記描画データに定義される前記所定の領域内のデータを変換する変換部と、
変換された前記所定の領域内のデータに基づいて、試料に前記複数のパターンを描画する描画部と、
を備えたことを特徴とする描画装置。
【請求項２】
変換された前記所定の領域内のデータは、各パターン情報の可変長コードが連続するデータを含むことを特徴とする請求項１記載の描画装置。
【請求項３】
所定の領域内のデータが、定義された複数のパターンの各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードで作成された描画データを記憶する記憶部と、
前記所定の領域内のデータを復元する復元部と、
復元されたデータを基に、試料に前記複数のパターンを描画する描画部と、
を備えたことを特徴とする描画装置。
【請求項４】
描画データを入力する工程と、
前記描画データを基に、定義された複数のパターンの図形コードとアレイフラグとアレイ個数とアレイピッチの少なくとも１つを含むパターン情報を取得する工程と、
所定の領域毎に、取得された複数のパターン情報を基に、各パターン情報と各パターン情報の使用回数とを関連させた第１のテーブルを作成する工程と、
前記第１のテーブルを基に、ハフマンツリーを作成する工程と、
前記ハフマンツリーを基に、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードとを関連させた第２のテーブルを作成する工程と、
前記第２のテーブルを基に、前記可変長コードを用いた所定のフォーマットで、前記描画データに定義される前記所定の領域内のデータを変換する工程と、
変換された前記所定の領域内のデータを記憶する工程と、
を備えたことを特徴とする描画データの変換方法。
【請求項５】
所定の領域内のデータが、定義された複数のパターンの各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードで作成された描画データを入力する工程と、
前記所定の領域内のデータを復元する工程と、
復元されたデータを基に、試料に前記複数のパターンを描画する工程と、
を備えたことを特徴とする描画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、描画装置、描画データの変換方法及び描画方法に関する。例えば、電子ビームを用いて試料に所定のパターンを描画する描画装置、描画方法、および装置内で処理される描画データの変換方法に関する。
【背景技術】
【０００２】
半導体デバイスの微細化の進展を担うリソグラフィ技術は半導体製造プロセスのなかでも唯一パターンを生成する極めて重要なプロセスである。近年、ＬＳＩの高集積化に伴い、半導体デバイスに要求される回路線幅は年々微細化されてきている。これらの半導体デバイスへ所望の回路パターンを形成するためには、高精度の原画パターン（レチクル或いはマスクともいう。）が必要となる。ここで、電子線（電子ビーム）描画技術は本質的に優れた解像性を有しており、高精度の原画パターンの生産に用いられる。
【０００３】
図１９は、従来の可変成形型電子線描画装置の動作を説明するための概念図である。
可変成形型電子線（ＥＢ：Ｅｌｅｃｔｒｏｎ  ｂｅａｍ）描画装置は、以下のように動作する。第１のアパーチャ４１０には、電子線３３０を成形するための矩形例えば長方形の開口４１１が形成されている。また、第２のアパーチャ４２０には、開口４１１を通過した電子線３３０を所望の矩形形状に成形するための可変成形開口４２１が形成されている。荷電粒子ソース４３０から照射され、開口４１１を通過した電子線３３０は、偏向器により偏向される。そして、可変成形開口４２１の一部を通過して、ステージ上に搭載された試料３４０に照射される。また、ステージは、描画中、所定の一方向（例えば、Ｘ方向とする）に連続的に移動する。すなわち、開口４１１と可変成形開口４２１との両方を通過できる矩形形状が、連続的に移動するステージ上に搭載された試料３４０の描画領域に描画される。開口４１１と可変成形開口４２１との両方を通過させ、任意形状を作成する方式を可変成形方式という。
【０００４】
かかる電子ビーム描画を行なうにあたり、まず、半導体集積回路のレイアウトが設計される。そして、パターンレイアウトが定義されたレイアウトデータ（設計データ）が生成される。そして、レイアウトデータが変換され、電子線描画装置に適応した描画データが生成される。そして、描画データは、描画装置に入力され、複数のデータ処理の後、描画する際のショットデータとして生成される（例えば、特許文献１参照）。そして、このショットデータに従って描画処理が行なわれる。ここで、描画装置内では、描画データが展開されていき、ショットデータが生成される前の中間データが生成されることになる。そして、従来使用されていたパターンのデータフォーマットはあらゆる可能な大きさ、座標、図形種、及び個数に対応することができるように設計されていた。そのため、従来のパターンデータフォーマットでは、これらのいずれにも対応可能な数のビット数が用意されていた。
【０００５】
しかしながら、描画データのレイアウトによっては、従来のパターンデータフォーマットで用意されたビット数の一部しか利用しないといった場合が存在する。例えば、同じ形或いは同じ大きさのパターンの繰り返しが圧倒的に多いレイアウトでは従来のパターンデータフォーマットで確保されたビット数のうち、わずかなビット数しか利用されていないといった状況があった。１つのレイアウトにおいて数個のパターンだけが少ないビット数になるというのであればそれほどの影響を受けるものではないが、近年のパターン微細化やパターン個数の増加に伴い、少ないビット数で済むパターンが増加している。そのため、このような利用されないビット数を累積すると装置のスループットにとって無視できないほどのデータサイズに相当するビット数になってきている。
【特許文献１】特開２００７−１２８９３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述したように、従来使用されていたパターンのデータフォーマットはあらゆる可能な大きさ、座標、図形種、及び個数に対応することができるようなビット数が用意されていた。そのため、使用されないビットも多く、使用されないビット数を累積すると装置のスループットにとって無視できないほどのデータサイズに相当してしまっていた。近年のパターン微細化やパターン個数の増加に伴い、データサイズの低減が求める中、データの使用ビット数の低減化が課題となっていた。さらに、描画装置に入力される描画データ自体も同様にパターンのデータフォーマットはあらゆる可能な大きさ、座標、図形種、及び個数に対応することができるようなビット数が用意されていた。そのため、かかる描画データを描画装置に転送する時間も長くなり、かかる転送時間についても装置のスループットにとって無視できないものとなってきた。
【０００７】
そこで、本発明の一態様は、ビット数を削減し、データサイズを低減する描画装置および描画データの変換方法を提供することを目的とする。また、本発明の他の態様は、入力される描画データのビット数を削減し、転送時間を短縮する描画装置および方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様の描画装置は、
描画データを記憶する記憶部と、
描画データを基に、定義された複数のパターンの図形コードとアレイフラグとアレイ個数とアレイピッチの少なくとも１つを含むパターン情報を取得する取得部と、
所定の領域毎に、取得された複数のパターン情報を基に、各パターン情報と各パターン情報の使用回数とを関連させた第１のテーブルを作成する第１のテーブル作成部と、
第１のテーブルを基に、ハフマンツリーを作成するハフマンツリー作成部と、
ハフマンツリーを基に、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードとを関連させた第２のテーブルを作成する第２のテーブル作成部と、
第２のテーブルを基に、可変長コードを用いた所定のフォーマットで、描画データに定義される所定の領域内のデータを変換する変換部と、
変換された所定の領域内のデータに基づいて、試料に複数のパターンを描画する描画部と、
を備えたことを特徴とする。
【０００９】
かかる構成により、第２のテーブルでは、使用回数の多いパターン情報ほど２進数の可変長コードが小さい値となる。小さい値ほど使用するビット数は少なくて済む。そして、可変長コードを用いた所定のフォーマットで所定の領域内のデータを変換する。そのため、変換された所定の領域内のデータは、各パターン情報を可変長コードで定義されることになる。その際、使用回数の多いパターン情報ほど少ないビット数で定義されているので、変換された所定の領域内のデータに使用するビット数を低減することができる。
【００１０】
また、変換された所定の領域内のデータは、各パターン情報の可変長コードが連続するデータを含むと好適である。
【００１１】
本発明の他の態様の描画装置は、
所定の領域内のデータが、定義された複数のパターンの各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードで作成された描画データを記憶する記憶部と、
所定の領域内のデータを復元する復元部と、
復元されたデータを基に、試料に複数のパターンを描画する描画部と、
を備えたことを特徴とする。
【００１２】
かかる構成により、使用回数の多いパターン情報ほど２進数の可変長コードが小さい値となる。小さい値ほど使用するビット数は少なくて済む。そのため、描画装置に入力される描画データは、所定の領域内のデータに使用するビット数が低減されている。
【００１３】
本発明の一態様の描画データの変換方法は、
描画データを入力する工程と、
描画データを基に、定義された複数のパターンの図形コードとアレイフラグとアレイ個数とアレイピッチの少なくとも１つを含むパターン情報を取得する工程と、
所定の領域毎に、取得された複数のパターン情報を基に、各パターン情報と各パターン情報の使用回数とを関連させた第１のテーブルを作成する工程と、
第１のテーブルを基に、ハフマンツリーを作成する工程と、
ハフマンツリーを基に、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードとを関連させた第２のテーブルを作成する工程と、
第２のテーブルを基に、可変長コードを用いた所定のフォーマットで、描画データに定義される所定の領域内のデータを変換する工程と、
変換された所定の領域内のデータを記憶する工程と、
を備えたことを特徴とする。
【００１４】
本発明の一態様の描画方法は、
所定の領域内のデータが、定義された複数のパターンの各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードで作成された描画データを入力する工程と、
所定の領域内のデータを復元する工程と、
復元されたデータを基に、試料に複数のパターンを描画する工程と、
を備えたことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、使用回数の多いパターン情報ほど少ないビット数で定義されているので、全体の使用ビット数を大幅に低減することができる。よって、データサイズを大幅に小さくすることができる。その結果、描画時間を短縮させ、装置のスループットを向上させることができる。また、全体の使用ビット数が大幅に低減される描画データを入力するので転送時間を大幅に短縮することができる。
【発明を実施するための最良の形態】
【００１６】
以下、実施の形態では、荷電粒子ビームの一例として、電子ビームを用いた構成について説明する。但し、荷電粒子ビームは、電子ビームに限るものではなく、イオンビーム等の荷電粒子を用いたビームでも構わない。また、荷電粒子ビーム装置の一例として、荷電粒子ビーム描画装置、特に、可変成形型の電子ビーム描画装置について説明する。
【００１７】
実施の形態１．
実施の形態１では、アレイ定義された図形データが無い場合について説明する。例えば、各図形が、図形コード、図形サイズ及び図形座標の各パターン情報で定義される場合について説明する。
【００１８】
図１は、実施の形態１における描画装置の構成を示す概念図である。
図１において、描画装置１００は、電子ビーム描画装置の一例である。描画装置１００は、試料１０１に複数の図形から構成されるパターンを描画する。試料１０１には、半導体装置を製造する際にリフォグラフィ工程で用いるためのマスクが含まれる。描画装置１００は、描画部１５０と制御部１６０を備えている。描画部１５０は、描画室１０３と描画室１０３の上部に配置された電子鏡筒１０２を備えている。電子鏡筒１０２内には、電子銃２０１、照明レンズ２０２、第１のアパーチャ２０３、投影レンズ２０４、偏向器２０５、第２のアパーチャ２０６、対物レンズ２０７、及び偏向器２０８が配置されている。そして、描画室１０３内には、ＸＹステージ１０５が配置され、ＸＹステージ１０５上に描画対象となる試料１０１が配置される。制御部１６０は、磁気ディスク装置１１０，１１６，１２２，１２６、データ処理部１１２、メモリ１１４，１２０，１２８、制御計算機１１８、ショットデータ生成部１２４、及び描画制御部１３０を有している。そして、磁気ディスク装置１１０，１１６，１２２，１２６、データ処理部１１２、メモリ１１４，１２０，１２８、制御計算機１１８、ショットデータ生成部１２４、及び描画制御部１３０は、図示していないバスにより互いに接続されている。制御計算機１１８内には、ブロック分割部４０、セル配置部４２、クラスタ分割部４４、パターン分割部４６、パターンデータ記録部４８、累積テーブル作成部５０、ハフマンツリー作成部５２、ハフマンテーブル作成部５４、及びフォーマット変換部５６が配置されている。磁気ディスク装置１１０，１１６，１２２，１２６及びメモリ１１４，１２０，１２８は、記憶部或いは記憶装置の一例となる。また、外部の磁気ディスク装置５００に描画データが格納されている。
【００１９】
ここで、ブロック分割部４０、セル配置部４２、クラスタ分割部４４、パターン分割部４６、パターンデータ記録部４８、累積テーブル作成部５０、ハフマンツリー作成部５２、ハフマンテーブル作成部５４、及びフォーマット変換部５６は、プログラムを実行させるＣＰＵ等の計算機で実行される各処理機能として構成してもよい。或いは、ブロック分割部４０、セル配置部４２、クラスタ分割部４４、パターン分割部４６、パターンデータ記録部４８、累積テーブル作成部５０、ハフマンツリー作成部５２、ハフマンテーブル作成部５４、及びフォーマット変換部５６の各構成を電気的な回路によるハードウェアにより構成してもよい。或いは、電気的な回路によるハードウェアとソフトウェアとの組合せにより実施させても構わない。或いは、かかるハードウェアとファームウェアとの組合せでも構わない。また、ソフトウェアにより、或いはソフトウェアとの組合せにより実施させる場合には、処理を実行する計算機に入力される情報或いは演算処理中及び処理後の各情報はその都度メモリ１２０に記憶される。同様に、データ処理部１１２或いはショットデータ生成部１２４についてもプログラムを実行させるＣＰＵ等の計算機として構成してもよい。或いは、各内部処理構成を電気的な回路によるハードウェアにより構成してもよい。或いは、電気的な回路によるハードウェアとソフトウェアとの組合せにより実施させても構わない。或いは、かかるハードウェアとファームウェアとの組合せでも構わない。また、ソフトウェアにより、或いはソフトウェアとの組合せにより実施させる場合には、処理を実行する計算機に入力される情報或いは演算処理中及び処理後の各情報は、データ処理部１１２についてはその都度メモリ１１４に、ショットデータ生成部１２４についてはその都度メモリ１２８に記憶される。
【００２０】
また、データ処理部１１２、制御計算機１１８、或いはショットデータ生成部１２４は、それぞれ１つの計算機で構成してもよいし、複数の計算機で構成してもよい。それぞれ複数の計算機で構成することで、並列処理を行なうことができる。並列処理を行なえば、処理速度を速くすることができる。
【００２１】
図１では、本実施の形態１を説明する上で必要な構成部分について記載している。描画装置１００にとって、通常、必要なその他の構成が含まれても構わないことは言うまでもない。
【００２２】
図２は、実施の形態１における描画データの階層構造の一例を示す図である。
描画データでは、描画領域が、チップ１０の層、チップ領域を例えばｙ方向に向かって短冊状に仮想分割したストライプ２０の層、ストライプ２０を分割したブロック３０の層、少なくとも１つ以上の図形で構成されるセル３２の層、セル３２を分割したクラスタ３４の層、クラスタ３４内に配置され、セル３２を構成する図形３６（パターン）の層といった一連の複数の内部構成単位ごとに階層化されている。また、１つの試料１０１の描画領域に対して複数のチップがレイアウトされていることが一般的である。そのため、後述するデータ処理部１１２において、チップマージ処理が行なわれ、図２に示すようなマージ後の階層が構成される。尚、ここではストライプ２０についてチップ領域をｙ方向に向かって短冊状に分割した領域としてあるが、これは一例であり、描画面と平行しｙ方向と直交するｘ方向に分割する場合もありうる。或いは描画面と平行するその他の方向であっても構わない。
【００２３】
図３は、実施の形態１における描画方法を示すフローチャート図である。
上述したように、電子ビーム描画を行なうにあたっては、まず、半導体集積回路のレイアウトが設計される。そして、パターンレイアウトが定義されたレイアウトデータ（設計データ）が生成される。そして、レイアウトデータが変換され、描画装置１００に適応した描画データが生成される。そして、描画データは、磁気ディスク装置５００から読み出され、描画装置１００に入力される。描画装置１００内では、磁気ディスク装置１１０に描画データが格納される。そして、後述するように複数のデータ処理の後、描画する際のショットデータとして生成される。
【００２４】
Ｓ（ステップ）１０２において、データ処理工程として、データ処理部１１２は、磁気ディスク装置１１０から複数のチップのそれぞれの描画データを読み出し、入力する。そして、データ処理部１１２は、描画装置１００の描画領域内に再配置して、チップマージ処理を行なう。また、データ処理部１１２は、その他に、ミラーリングやスケーリング処理といったデータ処理を行なっても構わない。そして、これらの処理が実行された後の描画データは、磁気ディスク装置１１６に格納される。
【００２５】
Ｓ１０４において、ブロック分割工程として、ブロック分割部４０は、上段の工程でデータ処理された描画データを展開して、チップ１０或いは各ストライプ２０を図２で示したような複数のブロック３０に仮想分割する。
【００２６】
Ｓ１０６において、セル配置工程として、セル配置部４２は、描画データをさらに展開して、各ブロック３０内にレイアウトされたセル３２を配置する。
【００２７】
Ｓ１０８において、クラスタ分割工程として、クラスタ分割部４４は、描画データをさらに展開して、各セル３２を図２で示したような複数のクラスタ３４に仮想分割する。
【００２８】
Ｓ１１０において、パターン分割工程として、パターン分割部４６は、描画データをさらに展開して、各クラスタ３４を各クラスタ３４内にレイアウトされた図２で示したような複数の図形３６（パターン）に分割する。パターン分割部４６は、パターン分割することで、各クラスタ３４内の図形３６の図形数、図形種類、図形サイズ（Ｌ，Ｍ）、及び配置座標（Ｘ，Ｙ）といったパターンデータ（パターン情報）を取得することができる。よって、パターン分割部４６は、描画データを基に、定義されたパターンの情報を取得することができる。すなわち、パターン分割部４６は、取得部の一例となる。
【００２９】
Ｓ１１２において、パターンデータ記録工程として、パターンデータ記録部４８は、クラスタ３４毎に、得られた図形３６の図形数、図形種類、図形サイズ（Ｌ，Ｍ）、及び配置座標（Ｘ，Ｙ）といったパターンデータをメモリ１２０に記録（格納）する。
【００３０】
Ｓ１１４において、累積テーブル作成工程として、累積テーブル作成部５０は、クラスタ３４毎に、取得された複数のパターン情報を基に、各パターン情報と各パターン情報の使用回数とを関連させた累積テーブル（第１のテーブル）を作成する。累積テーブル作成部５０は、第１のテーブル作成部の一例となる。作成された累積テーブルは、メモリ１２０に格納される。
【００３１】
図４は、実施の形態１における累積テーブルの一例を示す図である。
図４において、累積テーブル６０は、図形コード、図形サイズ（Ｍ，Ｌ）及び図形座標（ｘ，ｙ）の各値とその値の使用回数とを関連させて定義する。ここでは、クラスタ３４に配置されるすべての図形パターンについて、図形コード、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標（ｘ，ｙ）のｘ値、或いは図形座標（ｘ，ｙ）のｙ値が、０ｘ１１となる回数をカウントして定義する。但し、実際には、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標（ｘ，ｙ）のｘ値、或いは図形座標（ｘ，ｙ）のｙ値が、０ｘ１１とはなりえないので、クラスタ３４に配置されるすべての図形パターンのうち、０ｘ１１となる図形コードを有する図形パターンの数だけ累積加算される。ここでは、一例として、累積された使用回数が１１０回の場合を示している。同様に、図形コード、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標（ｘ，ｙ）のｘ値、或いは図形座標（ｘ，ｙ）のｙ値が、０．１となる回数をカウントして定義する。ここでは、累積された使用回数が例えば５０回の場合を示している。同様に、０．２となる回数をカウントして定義する。ここでは、累積された使用回数が例えば１０回の場合を示している。同様に、０．３となる回数をカウントして定義する。ここでは、累積された使用回数が例えば１０回の場合を示している。同様に、０．４となる回数をカウントして定義する。ここでは、累積された使用回数が例えば２０回の場合を示している。同様に、０．５となる回数をカウントして定義する。ここでは、累積された使用回数が例えば２５回の場合を示している。また、後述するように、１つのクラスタ３４内の図形コード、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標（ｘ，ｙ）のｘ値、及び図形座標（ｘ，ｙ）のｙ値のデータは、一連の連続コードで定義される。そのため、一連のデータの終わりを示すＥＯＳ（Ｅｎｄ  Ｏｆ  Ｓｔｒｅａｍ）が特別マークとして示されている。
【００３２】
図５は、実施の形態１における使用回数のカウントの仕方を説明するための一例を示す概念図である。
図５では、クラスタ３４の基準位置から座標（０．５，０．４）の位置に、幅０．５、高さ０．４の図形が配置されている場合を示している。それぞれの単位はＡＵとする。この場合、値０．４が２回、値０．５が２回それぞれ使用されている回数として累積テーブル６０に定義されることになる。累積テーブル６０では、クラスタ３４内に配置される全ての図形について同様に回数をカウントし、その累積値を定義する。
【００３３】
Ｓ１１６において、ハフマンツリー作成工程として、ハフマンツリー作成部５２は、累積テーブル６０をメモリ１２０から読み出し、累積テーブル６０を基に、ハフマンツリーを作成する。作成されたハフマンツリーは、メモリ１２０に格納される。
【００３４】
図６は、図４の累積テーブルに対応するハフマンツリーの一例を示す図である。
図６において、ハフマンツリー７０は、最上位のレベル１の階層にルートノード７２、レベル２の階層に葉ノード７４，７６、レベル３の階層に葉ノード７８，８０、レベル４の階層に葉ノード８２，８４、レベル５の階層に葉ノード８６，８８、レベル６の階層に葉ノード９０，９２、レベル７の階層に葉ノード９５，９６が配置される。レベル１の階層に配置されるルートノード７２がハフマンツリー７０の最初を構成する。このルートノード７２には２つのレベル１の枝が接続される。一方のレベル１の枝の先端には、特別マークのＥＯＳを示す葉ノード７６が配置される。２進数の「１」はこの枝に定義される。他方のレベル１の枝の先端には、レベル２の階層の葉ノード７４が配置される。２進数の「０」はこの枝に定義される。葉ノード７４には２つのレベル２の枝が接続される。一方のレベル２の枝の先端には、レベル３の階層の葉ノード７８が配置される。２進数の「０」はこの枝に定義される。他方のレベル２の枝の先端には、使用回数が最も多いパターン情報値の葉ノード８０が配置される。２進数の「１」はこの枝に定義される。葉ノード７８には２つのレベル３の枝が接続される。一方のレベル３の枝の先端には、レベル４の階層の葉ノード８２が配置される。２進数の「０」はこの枝に定義される。他方のレベル３の枝の先端には、使用回数が２番目に多いパターン情報値の葉ノード８４が配置される。２進数の「１」はこの枝に定義される。葉ノード８２には２つのレベル４の枝が接続される。一方のレベル４の枝の先端には、レベル５の階層の葉ノード８６が配置される。２進数の「０」はこの枝に定義される。他方のレベル４の枝の先端には、使用回数が３番目に多いパターン情報値の葉ノード８８が配置される。２進数の「１」はこの枝に定義される。葉ノード８６には２つのレベル５の枝が接続される。一方のレベル５の枝の先端には、レベル６の階層の葉ノード９０が配置される。２進数の「０」はこの枝に定義される。他方のレベル５の枝の先端には、使用回数が４番目に多いパターン情報値の葉ノード９２が配置される。２進数の「１」はこの枝に定義される。葉ノード９０には２つのレベル６の枝が接続される。一方のレベル６の枝の先端には、使用回数が５番目に多いパターン情報値の葉ノード９５がレベル７の階層として配置される。２進数の「０」はこの枝に定義される。他方のレベル６の枝の先端には、使用回数が同様に５番目に多いパターン情報値の葉ノード９６がレベル７の階層として配置される。２進数の「１」はこの枝に定義される。また、葉ノード７４，７８，８２，８６，９０には、各自より下位の階層に配置された葉ノードのパターン情報値の使用回数の合計値が定義されている。このように、ハフマンツリー７０は、使用回数の少ない下位２つのパターン情報値を最下位の階層レベルの２つの葉ノードとし、使用回数の多いパターン情報値をより上位の階層レベルの葉ノードとしてツリーを構成する。
【００３５】
Ｓ１１８において、ハフマンテーブル作成工程として、ハフマンテーブル作成部５４は、ハフマンツリー７０をメモリ１２０から読み出し、ハフマンツリー７０を基に、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードとを関連させたハフマンテーブル（第２のテーブル）を作成する。ハフマンテーブル作成部５４は、第２のテーブル作成部の一例となる。作成されたハフマンテーブルは、メモリ１２０に格納される。
【００３６】
図７は、図６のハフマンツリーに対応するハフマンテーブルの一例を示す図である。
図７において、ハフマンテーブル９４は、各パターン情報値と２進数の可変長コードとを関連させて定義している。上述したハフマンツリー７０は、次のように可変長コードを決定させる。使用回数が最も多いパターン情報値「０ｘ１１」の葉ノード８０に達するためには、ルートノード７２から２進数の「０」の枝と「１」の枝を１つずつ通らなければならない。よって、値「０ｘ１１」のコードは、２ビットの「０１」となる。使用回数が２番目に多いパターン情報値「０．１」の葉ノード８４に達するためには、ルートノード７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「１」のレベル３の枝とを通らなければならない。よって、値「０．１」のコードは、３ビットの「００１」となる。使用回数が３番目に多いパターン情報値「０．５」の葉ノード８８に達するためには、ルートノード７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「１」のレベル４の枝とを通らなければならない。よって、値「０．５」のコードは、４ビットの「０００１」となる。使用回数が４番目に多いパターン情報値「０．４」の葉ノード９２に達するためには、ルートノード７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「１」のレベル５の枝とを通らなければならない。よって、値「０．４」のコードは、５ビットの「００００１」となる。使用回数が５番目に多いパターン情報値「０．２」の葉ノード９５に達するためには、ルートノード７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「０」のレベル５の枝と２進数の「０」のレベル６の枝とを通らなければならない。よって、値「０．２」のコードは、６ビットの「００００００」となる。また、同様に使用回数が５番目に多いパターン情報値「０．３」の葉ノード９６に達するためには、ルートノード７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「０」のレベル５の枝と２進数の「１」のレベル６の枝とを通らなければならない。よって、値「０．３」のコードは、６ビットの「０００００１」となる。このように、使用回数の多いパターン情報ほど２進数の可変長コードが小さい値となるように暗号化される。すなわち、使用回数の多いパターン情報ほど少ないビット数の値とすることができる。また、特別マークであるＥＯＳのコードは、例外的に使用回数に関わらず１ビットの「１」と定義する。そして、得られた各パターン情報と可変長コードとが関連したハフマンテーブル９４が作成される。
【００３７】
Ｓ１２０において、フォーマット変換工程として、フォーマット変換部５６は、ハフマンテーブル９４を読み出し、ハフマンテーブル９４を基に、可変長コードを用いた所定のフォーマットで、描画データに定義される所定の領域内のデータを変換する。描画データをフォーマット変換することで、ショットデータへと変換される前段階となる中間データを生成することができる。
【００３８】
図８は、実施の形態１における中間データの一例を示す図である。
図８において、生成された中間データ１２では、ストライプヘッダに続き、ストライブ番号、当該ストライプ内に位置するブロックデータについてのブロックヘッダ、ブロック番号が定義される。そして、ブロック番号に続き、当該ブロック内に配置されるセルデータについてのセルヘッダ、セル番号、当該セル内に配置されるクラスタデータについてのクラスタヘッダ、クラスタ番号が定義される。そして、クラスタ番号に続き、クラスタ３４内に配置される第１番目の図形６２について、図形コードと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）が定義される。そして、第１番目の図形のデータに続き、同じクラスタ３４内に配置される第２番目の図形６２について、図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（Ｘ，Ｙ）がデータに区切れなく連続して定義される。このようにして１つのクラスタ３４内の全ての図形について定義した後に、次のクラスタ３４のクラスタヘッダ、クラスタ番号が続いて定義される。以下、同様に、定義される。ここで、図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（Ｘ，Ｙ）は、ハフマンテーブル９４から各コードを読み出し、同じクラスタ３４内に配置されるすべての図形６２についての各コードをつなげて一連の連続コードとして定義する。
【００３９】
従来フォーマットでは、例えば、図形コードを定義するために、例えば、１７ビット、図形サイズ（Ｌ，Ｍ）を定義するために、例えば、Ｌに１７ビット、Ｍに１７ビットが必要であり、座標（Ｘ，Ｙ）を定義するために、例えば、Ｘに１７ビット、Ｙに１７ビットの計６８ビットが必要であった。これに対し、図８の中間データ１２では、図形コード、図形サイズ（Ｌ，Ｍ）のＬとＭ、そして、座標（ｘ，ｙ）のｘとｙはそれぞれ可変長コードのビット値の合計となる。ここで、使用回数の最も多いパターン情報が、例えば、値「０ｘ１１」ならば、「０１」の２ビットで済んでしまうことになる。そのため１５ビットの削減効果が生じる。また、例えば、使用回数の２番目に多いパターン情報として値「０．１」ならば、「００１」の３ビットである場合に、仮に、Ｌ，Ｍ，ｘ，ｙが、すべて値「０．１」ならば、従来６８ビットが必要であったところ１２ビットで済んでしまうことになる。
【００４０】
例えば、１つのクラスタ３４内に３０００個の図形が配置されている場合、図形コード、Ｌ，Ｍ，ｘ，ｙの各値は、合計で１５０００個使用されることになる。ハフマンツリーを用いれば、仮に全て使用回数が１回であったとしても最大長のコードのビット数は、従来の１７ビットより小さくすることができる。実施の形態１では、使用回数の多いパターン情報ほど少ないビット数のコードとなるため、ビット数の低減効果は非常に大きいものとなる。
【００４１】
以上のようにして、変換された結果、ビット数が大幅に低減された各クラスタ内の中間データは、磁気ディスク装置１２２に記憶（格納）される。また、ハフマンテーブル９４も磁気ディスク装置１２２に記憶（格納）される。
【００４２】
Ｓ１２２において、ショットデータ生成工程として、ショットデータ生成部１２４は、磁気ディスク装置１２２から中間データとハフマンテーブル９４を読み出し、ショットデータを生成する。その際、ショットデータ生成部１２４は、読み出した中間データに定義された図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ、ｙ）を定義する連続コードをハフマンテーブル９４を参照して、元の数値に置き換えながら中間データを展開し、各図形をショット図形に分割すればよい。以上のようにして生成されたショットデータは磁気ディスク装置１２６に格納される。
【００４３】
図９は、実施の形態１における同じクラスタ内に配置される複数の図形に対する図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ、ｙ）を定義する連続コードの一例を示す図である。
図９では、例えば、コード「０１００１００１０００００００００００００１・・・１」と中間データの同じクラスタ内に配置される複数の図形に対する図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ，ｙ）の枠に定義されていた場合、ハフマンテーブル９４を読み出して、ハフマンテーブル９４を基に次のように判断される。まず、最初の「０１」によって、図形コードが「０ｘ１１」であることがわかる。次の「００１」によって、図形サイズのＬ値が「０．１」であることがわかる。次の「００１」によって、図形サイズのＭ値が「０．１」であることがわかる。次の「００００００」によって、図形座標のｘ値が「０．２」であることがわかる。次の「００００００」によって、図形座標のｙ値が「０．２」であることがわかる。次の「０１」によって、同じクラスタ内に配置される次の図形の図形コードが「０ｘ１１」であることがわかる。以下、同様にして、同じクラスタ内に配置される全ての図形についての図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ，ｙ）がわかる。そして、最後の「１」によって、同じクラスタ内に配置される全ての図形についての図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ，ｙ）のコードが終了したことがわかる。
【００４４】
そして、描画部１５０は、以上のような複数のフォーマットで変換されたクラスタ内のデータに基づいたショットデータにより制御された電子ビーム２００を用いて以下のように試料１０１にクラスタ内に配置される複数のパターンを描画する。描画部１５０は、描画制御部１３０によって制御される。
【００４５】
電子銃２０１から出た電子ビーム２００は、照明レンズ２０２により矩形、例えば長方形の穴を持つ第１のアパーチャ２０３全体を照明する。ここで、電子ビーム２００をまず矩形、例えば長方形に成形する。そして、第１のアパーチャ２０３を通過した第１のアパーチャ像の電子ビーム２００は、投影レンズ２０４により第２のアパーチャ２０６上に投影される。かかる第２のアパーチャ２０６上での第１のアパーチャ像の位置は、偏向器２０５によって制御され、ビーム形状と寸法を変化させることができる。そして、第２のアパーチャ２０６を通過した第２のアパーチャ像の電子ビーム２００は、対物レンズ２０７により焦点を合わせ、偏向器２０８により偏向されて、移動可能に配置されたＸＹステージ１０５上の試料１０１の所望する位置に照射される。
【００４６】
図１０は、実施の形態１における連続ビットによるビット数の削減効果を説明するための概念図である。
図１０（ａ）には、図形コードは従来のビット数の値で定義し、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ，ｙ）について可変長ビットで定義した場合を示している。かかる場合、１つの図形の図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ，ｙ）を定義する毎に、可変長ビット枠に達しないビット数の余りが生じてしまうことになる。これに対し、実施の形態１では、同じクラスタ内に配置される全ての図形についての図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ，ｙ）を前後の図形について隙間を空けずに連続して一連の可変長コードとして定義することで、図１０（ｂ）に示すように図形間に生じる余りのビットを無くすことができる。
【００４７】
以上のように、実施の形態１によれば、ハフマンツリーで図形コードと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）を可変長コードに暗号化することで、中間データのビット数を大幅に低減することができる。その結果、中間データのデータサイズを小さくすることができ、大幅に描画時間を短縮させることができる。その結果、装置のスループットを大幅に向上させることができる。
【００４８】
実施の形態２．
実施の形態１では、アレイ定義された図形データが無い場合について説明した。実施の形態２では、さらに、アレイ定義された図形データが存在する場合について説明する。例えば、各図形が、図形コード、アレイフラグ、図形サイズ、図形座標、アレイ図形の個数、及びアレイピッチの各パターン情報で定義される場合について説明する。ここで、実施の形態２における描画装置の構成は、図１と同様である。実施の形態２における描画方法は図３と同様である。また、データ処理工程（Ｓ１０２）からパターンデータ記録工程（Ｓ１１２）までの各工程の内容は、実施の形態１と同様である。
【００４９】
Ｓ１１４において、累積テーブル作成工程として、累積テーブル作成部５０は、クラスタ３４毎に、取得された複数のパターン情報を基に、各パターン情報と各パターン情報の使用回数とを関連させた累積テーブル（第１のテーブル）を作成する。作成された累積テーブルは、メモリ１２０に格納される。
【００５０】
図１１は、実施の形態２における累積テーブルの一例を示す図である。
図１１において、累積テーブル６２は、図形コード、アレイフラグ、図形サイズ（Ｍ，Ｌ）、図形座標（ｘ，ｙ）、アレイ図形個数（Ｎｘ，Ｎｙ）及びアレイピッチ（Ｐｘ，Ｐｙ）の各値とその値の使用回数とを関連させて定義する。ここでは、クラスタ３４に配置されるすべての図形パターンについて、図形コード、アレイフラグ、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標（ｘ，ｙ）のｘ値、或いは図形座標（ｘ，ｙ）のｙ値、アレイ図形個数（Ｎｘ，Ｎｙ）のＮｘ値、或いはアレイ図形個数（Ｎｘ，Ｎｙ）のＮｙ値、アレイピッチ（Ｐｘ，Ｐｙ）のＰｘ値、或いはアレイピッチ（Ｐｘ，Ｐｙ）のＰｙ値が、０ｘ１１となる回数をカウントして定義する。但し、実際には、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標（ｘ，ｙ）のｘ値、或いは図形座標（ｘ，ｙ）のｙ値、アレイ図形個数（Ｎｘ，Ｎｙ）のＮｘ値、アレイ図形個数（Ｎｘ，Ｎｙ）のＮｙ値、アレイピッチ（Ｐｘ，Ｐｙ）のＰｘ値、及びアレイピッチ（Ｐｘ，Ｐｙ）のＰｙ値が、０ｘ１１とはなりえないので、クラスタ３４に配置されるすべての図形パターンのうち、０ｘ１１となる図形コード或いはアレイフラグを有する図形パターンの数だけ累積加算される。ここでは、一例として、累積された使用回数が１００回の場合を示している。同様に、図形コード、アレイフラグ、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標のｘ値、図形座標のｙ値、アレイ図形個数のＮｘ値、アレイ図形個数のＮｙ値、アレイピッチのＰｘ値、或いはアレイピッチのＰｙ値が、０．１となる回数をカウントして定義する。ここでは、累積された使用回数が例えば５０回の場合を示している。同様に、０．２となる回数をカウントして定義する。ここでは、累積された使用回数が例えば２０回の場合を示している。同様に、０．３となる回数をカウントして定義する。ここでは、累積された使用回数が例えば１０回の場合を示している。同様に、０．４となる回数をカウントして定義する。ここでは、累積された使用回数が例えば５回の場合を示している。同様に、アレイフラグを示すＦとなる回数をカウントして定義する。ここでは、累積された使用回数が例えば１回の場合を示している。同様に、２となる回数をカウントして定義する。ここでは、累積された使用回数が例えば２回の場合を示している。実施の形態１と同様、１つのクラスタ３４内の図形コード、アレイフラグ、図形サイズの幅値Ｍ、図形サイズの高さ値Ｌ、図形座標のｘ値、図形座標のｙ値、アレイ図形個数のＮｘ値、アレイ図形個数のＮｙ値、アレイピッチのＰｘ値、及びアレイピッチのＰｙ値のデータは、一連の連続コードで定義される。そのため、一連のデータの終わりを示すＥＯＳが特別マークとして示される。
【００５１】
図１２は、実施の形態２におけるアレイ図形の使用回数のカウントの仕方を説明するための一例を示す概念図である。
図１２において、例えば、クラスタ３４の基準位置から座標（０．２，０．２）の位置に、幅０．１、高さ０．１の図形が、ｘ方向にピッチ０．２で２個、ｙ方向にピッチ０．２で２個配置されている場合が示されている。それぞれの単位はＡＵとする。この場合、値０．１が２回、値０．２が４回、値２が２回それぞれ使用されている回数として累積テーブル６２に定義されることになる。累積テーブル６２では、クラスタ３４内に配置される全ての図形について同様に回数をカウントし、その累積値を定義する。
【００５２】
Ｓ１１６において、ハフマンツリー作成工程として、ハフマンツリー作成部５２は、累積テーブル６２をメモリ１２０から読み出し、累積テーブル６２を基に、ハフマンツリーを作成する。作成されたハフマンツリーは、メモリ１２０に格納される。
【００５３】
図１３は、図１１の累積テーブルに対応するハフマンツリーの一例を示す図である。
図１３において、ハフマンツリー１７０は、最上位のレベル１の階層にルートノード１７２、レベル２の階層に葉ノード１７４，１７６、レベル３の階層に葉ノード１７８，１８０、レベル４の階層に葉ノード１８２，１８４、レベル５の階層に葉ノード１８６，１８８、レベル６の階層に葉ノード１９０，１９２、レベル７の階層に葉ノード１９４，１９６、レベル８の階層に葉ノード１９８，１９９が配置される。レベル１の階層に配置されるルートノード１７２がハフマンツリー１７０の最初を構成する。このルートノード１７２には２つのレベル１の枝が接続される。一方のレベル１の枝の先端には、特別マークのＥＯＳを示す葉ノード１７６が配置される。２進数の「１」はこの枝に定義される。他方のレベル１の枝の先端には、レベル２の階層の葉ノード１７４が配置される。２進数の「０」はこの枝に定義される。葉ノード１７４には２つのレベル２の枝が接続される。一方のレベル２の枝の先端には、レベル３の階層の葉ノード１７８が配置される。２進数の「０」はこの枝に定義される。他方のレベル２の枝の先端には、使用回数が最も多いパターン情報値の葉ノード１８０が配置される。２進数の「１」はこの枝に定義される。葉ノード１７８には２つのレベル３の枝が接続される。一方のレベル３の枝の先端には、レベル４の階層の葉ノード１８２が配置される。２進数の「０」はこの枝に定義される。他方のレベル３の枝の先端には、使用回数が２番目に多いパターン情報値の葉ノード１８４が配置される。２進数の「１」はこの枝に定義される。葉ノード１８２には２つのレベル４の枝が接続される。一方のレベル４の枝の先端には、レベル５の階層の葉ノード１８６が配置される。２進数の「０」はこの枝に定義される。他方のレベル４の枝の先端には、使用回数が３番目に多いパターン情報値の葉ノード１８８が配置される。２進数の「１」はこの枝に定義される。葉ノード１８６には２つのレベル５の枝が接続される。一方のレベル５の枝の先端には、レベル６の階層の葉ノード１９０が配置される。２進数の「０」はこの枝に定義される。他方のレベル５の枝の先端には、使用回数が４番目に多いパターン情報値の葉ノード１９２が配置される。２進数の「１」はこの枝に定義される。葉ノード１９０には２つのレベル６の枝が接続される。一方のレベル６の枝の先端には、レベル７の階層の葉ノード１９４が配置される。２進数の「０」はこの枝に定義される。他方のレベル６の枝の先端には、使用回数が５番目に多いパターン情報値の葉ノード１９６が配置される。２進数の「１」はこの枝に定義される。葉ノード１９４には２つのレベル７の枝が接続される。一方のレベル７の枝の先端には、使用回数が６番目に多いパターン情報値の葉ノード１９９がレベル８の階層として配置される。２進数の「１」はこの枝に定義される。他方のレベル７の枝の先端には、使用回数が７番目に多いパターン情報値の葉ノード１９８がレベル８の階層として配置される。２進数の「０」はこの枝に定義される。また、葉ノード１７４，１７８，１８２，１８６，１９０，１９４には、各自より下位の階層に配置された葉ノードのパターン情報値の使用回数の合計値が定義されている。このように、ハフマンツリー１７０は、使用回数の少ない下位２つのパターン情報値を最下位の階層レベルの２つの葉ノードとし、使用回数の多いパターン情報値をより上位の階層レベルの葉ノードとしてツリーを構成する。
【００５４】
Ｓ１１８において、ハフマンテーブル作成工程として、ハフマンテーブル作成部５４は、ハフマンツリー１７０をメモリ１２０から読み出し、ハフマンツリー１７０を基に、各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードとを関連させたハフマンテーブル（第２のテーブル）を作成する。ハフマンテーブル作成部５４は、第２のテーブル作成部の一例となる。作成されたハフマンテーブルは、メモリ１２０に格納される。
【００５５】
図１４は、図１３のハフマンツリーに対応するハフマンテーブルの一例を示す図である。
図１４において、ハフマンテーブル９８は、各パターン情報値と２進数の可変長コードとを関連させて定義している。上述したハフマンツリー１７０は、次のように可変長コードを決定させる。使用回数が最も多いパターン情報値「０ｘ１１」の葉ノード１８０に達するためには、ルートノード１７２から２進数の「０」の枝と「１」の枝を１つずつ通らなければならない。よって、値「０ｘ１１」のコードは、２ビットの「０１」となる。使用回数が２番目に多いパターン情報値「０．１」の葉ノード１８４に達するためには、ルートノード１７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「１」のレベル３の枝とを通らなければならない。よって、値「０．１」のコードは、３ビットの「００１」となる。使用回数が３番目に多いパターン情報値「０．２」の葉ノード１８８に達するためには、ルートノード１７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「１」のレベル４の枝とを通らなければならない。よって、値「０．２」のコードは、４ビットの「０００１」となる。使用回数が４番目に多いパターン情報値「０．３」の葉ノード１９２に達するためには、ルートノード１７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「１」のレベル５の枝とを通らなければならない。よって、値「０．３」のコードは、５ビットの「００００１」となる。使用回数が５番目に多いパターン情報値「０．４」の葉ノード１９６に達するためには、ルートノード１７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「０」のレベル５の枝と２進数の「１」のレベル６の枝とを通らなければならない。よって、値「０．４」のコードは、６ビットの「０００００１」となる。また、使用回数が６番目に多いパターン情報値「２」の葉ノード１９８に達するためには、ルートノード１７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「０」のレベル５の枝と２進数の「０」のレベル６の枝と２進数の「０」のレベル７の枝とを通らなければならない。よって、値「２」のコードは、７ビットの「０００００００」となる。また、使用回数が７番目に多いパターン情報値「Ｆ」の葉ノード１９９に達するためには、ルートノード１７２から２進数の「０」のレベル１の枝と２進数の「０」のレベル２の枝と２進数の「０」のレベル３の枝と２進数の「０」のレベル４の枝と２進数の「０」のレベル５の枝と２進数の「０」のレベル６の枝と２進数の「０」のレベル７の枝とを通らなければならない。よって、値「Ｆ」のコードは、７ビットの「００００００１」となる。このように、使用回数の多いパターン情報ほど２進数の可変長コードが小さい値となるように暗号化される。すなわち、使用回数の多いパターン情報ほど少ないビット数の値とすることができる。また、特別マークであるＥＯＳのコードは、例外的に使用回数に関わらず１ビットの「１」と定義する。そして、得られた各パターン情報と可変長コードとが関連したハフマンテーブル９８が作成される。
【００５６】
Ｓ１２０において、フォーマット変換工程として、フォーマット変換部５６は、ハフマンテーブル９８を読み出し、ハフマンテーブル９８を基に、可変長コードを用いた所定のフォーマットで、描画データに定義される所定の領域内のデータを変換する。描画データをフォーマット変換することで、ショットデータへと変換される前段階となる中間データを生成することができる。
【００５７】
図１５は、実施の形態２における中間データの一例を示す図である。
図１５において、生成された中間データ１２では、ストライプヘッダに続き、ストライブ番号、当該ストライプ内に位置するブロックデータについてのブロックヘッダ、ブロック番号が定義される。そして、ブロック番号に続き、当該ブロック内に配置されるセルデータについてのセルヘッダ、セル番号、当該セル内に配置されるクラスタデータについてのクラスタヘッダ、クラスタ番号が定義される。そして、クラスタ番号に続き、クラスタ３４内に配置される第１番目の図形６２について、図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）が定義される。そして、第１番目の図形のデータに続き、同じクラスタ３４内に配置される第２番目の図形６２について、図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）がデータに区切れなく連続して定義される。このようにして１つのクラスタ３４内の全ての図形について定義した後に、次のクラスタ３４のクラスタヘッダ、クラスタ番号が続いて定義される。以下、同様に、定義される。そして、実施の形態１と同様、図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）は、ハフマンテーブル９８から各コードを読み出し、同じクラスタ３４内に配置されるすべての図形６２についての各コードをつなげて一連の連続コードとして定義する。
【００５８】
従来フォーマットでは、実施の形態１で説明した図形コードと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）の他に、アレイフラグとアレイ図形個数Ｎｘとアレイ図形個数ＮｙとアレイピッチＰｘとアレイピッチＰｙを定義するために、例えば、それぞれ１７ビットが必要であった。これらを使用回数の多いパターン情報ほど少ないビット数の可変長コードとすることで、ビット数の低減効果は非常に大きいものとなる。
【００５９】
以上のようにして、変換された結果、ビット数が大幅に低減された各クラスタ内の中間データは、磁気ディスク装置１２２に記憶（格納）される。また、ハフマンテーブル９８も磁気ディスク装置１２２に記憶（格納）される。
【００６０】
図１６は、実施の形態２における同じクラスタ内に配置される複数の図形に対する図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）を定義する連続コードの一例を示す図である。
図１６では、例えば、コード「０１０００００００００１００１０００１０００１００００００１００００００１０００１０００１・・・１」と中間データの同じクラスタ内に配置される複数の図形に対する図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）の枠に定義されていた場合、ハフマンテーブル９８を読み出して、ハフマンテーブル９８を基に次のように判断される。まず、最初の「０１」によって、図形コードが「０ｘ１１」であることがわかる。次の「０００００００」によって、アレイフラグ有りを示す「Ｆ」であることがわかる。次の「００１」によって、図形サイズのＬ値が「０．１」であることがわかる。次の「００１」によって、図形サイズのＭ値が「０．１」であることがわかる。次の「０００１」によって、図形座標のｘ値が「０．２」であることがわかる。次の「０００１」によって、図形座標のｙ値が「０．２」であることがわかる。次の「００００００１」によって、アレイ図形の個数のＮｘ値が「２」であることがわかる。次の「００００００１」によって、アレイ図形の個数のＮｙ値が「２」であることがわかる。次の「０００１」によって、アレイピッチのＰｘ値が「０．２」であることがわかる。次の「０００１」によって、アレイピッチのＰｙ値が「０．２」であることがわかる。続いて、同様に同じクラスタ内に配置される全ての図形についての図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）がわかる。そして、最後の「１」によって、同じクラスタ内に配置される全ての図形についての図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）のコードが終了したことがわかる。
【００６１】
Ｓ１２２において、ショットデータ生成工程として、ショットデータ生成部１２４は、磁気ディスク装置１２２から中間データとハフマンテーブル９８を読み出し、ショットデータを生成する。その際、ショットデータ生成部１２４は、読み出した中間データに定義された図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）を定義する連続コードをハフマンテーブル９８を参照して、元の数値に置き換えながら中間データを展開し、各図形をショット図形に分割すればよい。以上のようにして生成されたショットデータは磁気ディスク装置１２６に格納される。
【００６２】
そして、描画部１５０は、以上のような複数のフォーマットで変換されたクラスタ内のデータに基づいたショットデータにより制御された電子ビーム２００を用いて以下のように試料１０１にクラスタ内に配置される複数のパターンを描画する。描画部１５０は、描画制御部１３０によって制御される。描画動作は実施の形態１と同様である。
【００６３】
ここで、ある描画データの１つを用いてビット数の低減効果を検証する。９０ｎｍ世代の配線パターンの一例について検証した。その際のクラスタサイズは６．４μｍとした。その結果、従来の方式のままでは、中間データの図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）の枠の合計が１３４６４ビット必要であった。他方、本実施の形態によれば、中間データの図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）の枠の合計が５５１８ビットに削減することができた。これにより５９％に減少させることができた。
【００６４】
以上のように、本実施の形態によれば、ハフマンツリーで図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）を可変長コードに暗号化することで、中間データのビット数を大幅に低減することができる。その結果、中間データのデータサイズを小さくすることができ、大幅に描画時間を短縮させることができる。その結果、装置のスループットを大幅に向上させることができる。
【００６５】
実施の形態３．
実施の形態１，２では、描画装置１００が描画データを入力した後のデータ処理について各図形のパターン情報を可変長コードに暗号化したが、これに限るものではない。実施の形態３では、描画装置１００が入力する前の段階で各図形のパターン情報を可変長コードに暗号化した描画データを描画装置１００が入力する場合について説明する。
【００６６】
図１７は、実施の形態３における描画装置の構成を示す概念図である。
図１７において、データ処理部１１２の代わりに、制御計算機１１３を備え、制御計算機１１３内にデコーダ５８とデータ処理部５９が配置された点以外は、図１と同様である。ここで、デコーダ５８とデータ処理部５９は、プログラムを実行させるＣＰＵ等の計算機で実行される各処理機能として構成してもよい。或いは、デコーダ５８とデータ処理部５９の各構成を電気的な回路によるハードウェアにより構成してもよい。或いは、電気的な回路によるハードウェアとソフトウェアとの組合せにより実施させても構わない。或いは、かかるハードウェアとファームウェアとの組合せでも構わない。また、ソフトウェアにより、或いはソフトウェアとの組合せにより実施させる場合には、処理を実行する計算機に入力される情報或いは演算処理中及び処理後の各情報はその都度メモリ１１４に記憶される。
【００６７】
図１８は、実施の形態３における描画方法を示すフローチャート図である。図１８において、データ処理工程（Ｓ１０２）の前に復元工程（Ｓ１０１）を追加した点以外は、図３と同様である。
【００６８】
実施の形態３では、実施の形態１で説明した図形のデータ構成と同様、ハフマンツリーで図形コードと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）の各パターン情報を可変長コードに暗号化した描画データが磁気ディスク装置５００から読み出され、描画装置１００に入力される。描画装置１００内では、磁気ディスク装置１１０に描画データが格納される。すなわち、クラスタ内のデータが、定義された複数のパターンの各パターン情報と使用回数の多いパターン情報ほど小さい値となるように各パターン情報を暗号化した２進数の可変長コードで作成された描画データが磁気ディスク装置１１０に記憶される。領域はクラスタに限らず、その他の領域毎であっても構わない。ここでは、まだチップマージ処理を行なう前の段階であるので、例えば、各チップのフレーム領域毎に各図形のパターン情報を暗号化した２進数の可変長コードで作成しても好適である。
【００６９】
Ｓ１０１において、デコーダ工程として、デコーダ５８は、磁気ディスク装置１１０から描画データを読み出し、可変長コードで作成された所定の領域内のデータを復元する。デコーダ５８は、復元部の一例である。デコーダ５８は、可変長コードをハフマンテーブルを参照して、元の数値に復元する。入力する描画データ用のハフマンテーブルは、描画データと共に磁気ディスク装置１１０に入力しておけばよい。そして、復元されたデータを基に、以降のデータ処理を行なった後に描画部１５０によって試料１０１に複数のパターンが描画される。データ処理工程（Ｓ１０２）以降の各工程の内容は実施の形態１と同様である。
【００７０】
また、実施の形態２で説明した図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）の各パターン情報を可変長コードに暗号化した描画データを描画装置１００は入力しても好適である。かかる場合には、復元工程（Ｓ１０１）で復元し、以降の各工程の内容は実施の形態２と同様である。
【００７１】
以上のように、描画装置１００の内部で使用する場合の他、装置が入力する前の段階で各パターン情報を可変長コードに暗号化しておくことで、入力する描画データ自体の全体の使用ビット数が大幅に低減される。そして、使用ビット数が大幅に低減された描画データを入力することで描画装置１００への転送時間を大幅に短縮することができる。よって、描画データの転送処理から描画が完了するまでの時間を短縮することができ、スループットを大幅に短縮することができる。
【００７２】
以上、具体例を参照しつつ実施の形態について説明した。しかし、本発明は、これらの具体例に限定されるものではない。例えば、クラスタ毎にフォーマットを選択したが、これに限るものではなく、例えばセル毎にフォーマットを選択しても構わない。
【００７３】
また、装置構成や制御手法等、本発明の説明に直接必要しない部分等については記載を省略したが、必要とされる装置構成や制御手法を適宜選択して用いることができる。例えば、描画装置１００を制御する制御部構成については、記載を省略したが、必要とされる制御部構成を適宜選択して用いることは言うまでもない。
【００７４】
その他、本発明の要素を具備し、当業者が適宜設計変更しうる全ての描画データの作成装置、描画データの作成方法、描画データの変換装置、描画データの変換方法、荷電粒子ビーム描画装置及び描画方法は、本発明の範囲に包含される。
【図面の簡単な説明】
【００７５】
【図１】実施の形態１における描画装置の構成を示す概念図である。
【図２】実施の形態１における描画データの階層構造の一例を示す図である。
【図３】実施の形態１における描画方法を示すフローチャート図である。
【図４】実施の形態１における累積テーブルの一例を示す図である。
【図５】実施の形態１における使用回数のカウントの仕方を説明するための一例を示す概念図である。
【図６】図４の累積テーブルに対応するハフマンツリーの一例を示す図である。
【図７】図６のハフマンツリーに対応するハフマンテーブルの一例を示す図である。
【図８】実施の形態１における中間データの一例を示す図である。
【図９】実施の形態１における同じクラスタ内に配置される複数の図形に対する図形コード、図形サイズ（Ｌ，Ｍ）及び図形座標（ｘ、ｙ）を定義する連続コードの一例を示す図である。
【図１０】実施の形態１における連続ビットによるビット数の削減効果を説明するための概念図である。
【図１１】実施の形態２における累積テーブルの一例を示す図である。
【図１２】実施の形態２におけるアレイ図形の使用回数のカウントの仕方を説明するための一例を示す概念図である。
【図１３】図１１の累積テーブルに対応するハフマンツリーの一例を示す図である。
【図１４】図１３のハフマンツリーに対応するハフマンテーブルの一例を示す図である。
【図１５】実施の形態２における中間データの一例を示す図である。
【図１６】実施の形態２における同じクラスタ内に配置される複数の図形に対する図形コードとアレイフラグと図形サイズ（Ｌ，Ｍ）と図形座標（ｘ、ｙ）とアレイ図形の個数（Ｎｘ，Ｎｙ）とアレイピッチ（Ｐｘ，Ｐｙ）を定義する連続コードの一例を示す図である。
【図１７】実施の形態３における描画装置の構成を示す概念図である。
【図１８】実施の形態３における描画方法を示すフローチャート図である。
【図１９】従来の可変成形型電子線描画装置の動作を説明するための概念図である。
【符号の説明】
【００７６】
１０  チップ
１２  中間データ
２０  ストライプ
３０  ブロック
３２  セル
３４  クラスタ
３６  図形
４０  ブロック分割部
４２  セル配置部
４４  クラスタ分割部
４６  パターン分割部
４８  パターンデータ記録部
５０  累積テーブル作成部
５２  ハフマンツリー作成部
５４  ハフマンテーブル作成部
５６  フォーマット変換部
５８  デコーダ
５９，１１２  データ処理部
６０，６２  累積テーブル
７０，１７０  ハフマンツリー
７２，１７２  ルートノード
７４，７６，７８，８０，８２，８４，８６，８８，９０，９２，９５，９６  葉ノード
１７４，１７６，１７８，１８０，１８２，１８４，１８６，１８８  葉ノード
１９０，１９２，１９４，１９６，１９８，１９９  葉ノード
９４，９８  ハフマンテーブル
１００  描画装置
１０１，３４０  試料
１０２  電子鏡筒
１０３  描画室
１０５  ＸＹステージ
１１０，１１６，１２２，１２６，５００  磁気ディスク装置
１１３，１１８  制御計算機
１１４，１２０，１２８  メモリ
１２４  ショットデータ生成部
１３０描画制御部
１５０  描画部
１６０  制御部
２００  電子ビーム
２０１  電子銃
２０２  照明レンズ
２０３，４１０  第１のアパーチャ
２０６，４２０  第２のアパーチャ
２０４  投影レンズ
２０５，２０８  偏向器
２０７  対物レンズ
３３０  電子線
４１１  開口
４２１  可変成形開口
４３０  荷電粒子ソース
【図１】
2010067808.tif 000003
【図２】
2010067808.tif 000004
【図３】
2010067808.tif 000005
【図４】
2010067808.tif 000006
【図５】
2010067808.tif 000007
【図６】
2010067808.tif 000008
【図７】
2010067808.tif 000009
【図８】
2010067808.tif 000010
【図９】
2010067808.tif 000011
【図１０】
2010067808.tif 000012
【図１１】
2010067808.tif 000013
【図１２】
2010067808.tif 000014
【図１３】
2010067808.tif 000015
【図１４】
2010067808.tif 000016
【図１５】
2010067808.tif 000017
【図１６】
2010067808.tif 000018
【図１７】
2010067808.tif 000019
【図１８】
2010067808.tif 000020
【図１９】
2010067808.tif 000021