(57)【要約】信号（ｎ次元パターンを表示、ここで、ｎは2より大きいか、等しい）を分離スプラインカーネルによって近似し得るスムースカーネルで畳み込みに適用される高速畳み込み方法と、ソフトウェアまたは信号処理回路を用いて前記方法を実行するよう構成されたシステム。長さNの信号に対してNlogNのオーダーの算術演算を必要とするフーリエに基づく畳み込み法と違って、本発明の方法は同じことをするのにN回オーダーの算術演算を行うだけでよい。ウェーブレットに基づく畳み込み近似（典型的には、本発明に従って同じ信号を畳み込むのに必要とされる以上の算術演算を必要とする）と違って、本発明の方法はスプラインカーネルである畳み込みカーネルに対して正確である。【特許請求の範囲】
【請求項１】
少なくとも分離スプラインカーネルにほぼ等しいスムースカーネルｄを用いてｎ次元のパターンp（x1, …, xn）の畳み込みを行い、畳み込みの結果r＝Dｐ＝d×p、ここで、Dはｄの循環であり、ｎは１より大きい、を表示するデータを生成する方法であって、
（ａ）該分離スプラインカーネルをk(x1,…xn) ＝ k1(x1)…kn(xn)（ここで kj は循環Kj を持ち、ｋ（x1, …, xn）は演算子A＝A1A2...Anであることを容認し、Aj は消滅演算子か平滑化演算子であり、この消滅演算子か平滑化演算子は、AjKjがまばらである(Aj が消滅演算子であるとき)か又はAjKj がほとんど至るところで局所的に一定マトリクスである（平滑化演算子であるとき）ような方式でカーネルkjの循環Kj上で演算する）と指定するステップと、
（ｂ）パターンp の各列に対するq1＝A1k1×pを表示する追加のデータを生成するようにパターンp を表示するパターンデータと、カーネルk1を表示するカーネルデータを処理するステップと、
（ｃ）r1の少数の要素が直接計算される準備的な始動ステップを実行し、次に演算子Ａ1によって決定される自然の再生関係を用いて、ｒ1要素の全ての、他のものを決定することによって、前記パターンに対するr1＝k1×pを表示するデータを決定するためパターンの前記各列に対してA1r1＝q1を後方計算するように追加のデータを処理するステップと、
（ｄ）r1T＝(k1×p)Tがr1の置換を示す(k1×p)Tの各列に対してq2＝A2k2×(k1×p)Tを表示するデータを生成するようにr1＝k1×p を表示するデータを処理するステップと、
（ｅ）(k1×p)Tの前記各列に対してA2r2T＝q2を後方計算するようにq2＝A2k2×r1Tを表示するデータを処理し、それによって前記パターンｐ に対するr2T ＝(k2×k1×p)Tを表示するデータを決定するステップと、
とを含む、前記方法。
【請求項２】
ｎ＝２であり、ステップ（e）が、r が畳み込み D p に近似している前記パターンのr＝(k2×k1×p)を表示するデータを生成するようにr2T＝(k2×k1×p)Tを表示するデータ上に置換するステップを含む、請求項１記載の方法。
【請求項３】
（ｆ）前記パターンに対しr＝(k2×k1×p)を表示するデータによって少なくとも部分的に決定される、畳み込まれた画像データに応じてパターン信号を生成するステップと、
（ｇ）該パターン信号を一連の光学部品上に投射させ、該光学部品からのパターン画像を該パターン信号に応じてリソグラフィターゲット上に投影するステップと
も含んでいる、請求項２記載の方法。
【請求項４】
該パターン信号が光学信号である、請求項３記載の方法。
【請求項５】
該パターン信号が電子ビーム信号である、請求項３記載の方法。
【請求項６】
ステップ（ｆ）で用いられる、畳み込まれた画像データが前記パターンに対してr＝ (k2×k1×p)を表示する前記データである、請求項３記載の方法。
【請求項７】
ｎが２より大きく、
（ｆ）前記パターンに対してr2T＝(k2×k1×p)Tを表示する該データを決定した後、iが正の整数でj＝(ｎ−２)であるステップ（d）と（e）のｉ番目の繰り返し計算を行っている間、qi+2＝Ai+2ki+2×qi+1を表示し、ri+2T＝(ki+2×ki+1×…×k1×p)Tを表示するデータが生成されるステップ(d)と(e)をj回繰り返すステップ、
をも含む、請求項１記載の方法。
【請求項８】
該パターンデータがステップ（ｂ）の前に記憶装置の記憶位置に格納され、ステップ（ｄ）が
(ｉ)（k1×p）の各行を表示するデータがp の列を表示する該パターンデータによって前もって占有される該記憶位置の列を占有するよう該記憶装置内にr1＝k1×p を表示するデータを格納するステップと、
（ｉｉ）(k1×p)Tの前記各列に対してq2＝A2k2×(k1×p)Tを表示する該データの生成中に該記憶位置の一つの前記列から(k1×p)の一つの前記行を表示するデータを読み出すステップと、
を含む、請求項１記載の方法。
【請求項９】
少なくとも分離スプラインカーネルにほぼ等しいスムースカーネルｄを用いて２次元のパターンp（ｘ、ｙ）の畳み込みを行い、畳み込みの結果r＝Dｐ＝d×p（ここで、Dはｄ の循環である）を表示するデータを生成する方法であって、
（ａ）該分離スプラインカーネルをk(x,y)＝k1(x)k1(y)、ここで
|x|≦R に対してk1(x)＝(R2−x2)  
|x|>R に対してk1(x)＝cd−|x|
該カーネルk1(x)が
k1(x)＝kc(x)＋k+(x)＋k-(x)
であり、ここで、kc(x)がカーネル
|x|≦R に対して、kｃ(x)＝(R2 − x2)  
|x|>R に対して、kｃ(x)＝0
k+(x)が片側のラプラス カーネルで
|x|>R に対して、k+(x)＝cd−|x|
|x|≦R に対して、k+(x)＝0
であり、
k-(x)が片側のラプラス カーネルで
|x|<−Rに対して、k-(x)＝cdx
|x|≧Rに対して、k-(x)＝0
である、と指定するステップと、
（ｂ）パターンpの各列に対しキャップ畳み込みkc×p(x)を表示する追加データと、前記各列に対する第二の畳み込みk＋×p(x)と、前記各列に対する第三の畳み込みk-×p(x)を生成するようにパターンpを表示するパターンデータとカーネルkc、カーネルk＋、カーネルk-を表示するカーネルデータを処理し、
q1＝k1×p(x,y)＝(kc×p(x,y))＋(k+×p(x,y))＋k_×p(x,y)
を表示するデータを生成するように前記各列に対する該キャップ畳み込み、該第二の畳み込み、該第三の畳み込みを表示する該追加データを一緒に加えるステップであって、該キャップ畳み込みを表示する該データはAcが
Ackc(x)＝kc(x＋３)−３kc(x＋２)＋３kc(x＋１)−kc(x)
で定義される消滅演算子である前記各列に対するAckc × p(x)を計算することによって生成され、
kc(x＋３)＝Ackc(x)＋kc(x)＋３kc(x＋２)−3kc(x＋１)
の繰り返し関係を用いてAc-1(Ackc×p)(x)＝kc×p(x)を計算することによって生成され、該第二の畳み込みを表示する該データはA＋が
A＋k＋(x)＝k＋(x＋１)−d−1k+(x)
で定義される消滅演算子である前記各列に対するA+k+ × p(x)を計算することによって生成され、
(k+×p)(x＋１, y)＝( A+k+×p)(x, y)＋ d-1(k+×p)(x, y)
の繰り返し関係を用いてA+−1(A+k+×p) (x)＝k+×p(x)を計算することによって生成され、第三の畳み込みを表示するデータはA_ が
A_k_ (x)＝k_ (x−1)−d-1k_(x)
で定義される消滅演算子である前記各列に対するA_k_×p(x)を計算することによって生成され、
(k_×p)(x−1,y)＝(A_k_×p)(x, y)＋d-1(k_×p)(x,y)
の繰り返し関係を用いて終わりから始めまで繰り返すことによりA_−1(A_k_×p) (x) ＝ k_ x p(x)を計算するステップと、
（ｃ）(k1×p(x,y))Tを表示するデータを生成するように(k1×p(x,y))を表示するデータを置換するステップと、
（ｄ）今回は該カーネルデータを用いて該パターンデータではなく(k1×p(x,y))Tを表示する該データを処理することによってステップ（ｂ)を繰り返し、それによってq1T ＝ (k1(x)×k1(y)×p(x,y)) Tを表示するデータを生成するステップと、
を含む、前記方法。
【請求項１０】
該パターンデータがステップ（ｂ）の前に記憶装置の記憶位置に格納され、ステップ（ｃ）が、（k1×p）の各行を表示するデータがp(x,y)の列を表示するパターンによって以前に占有された記憶位置の列を占有するように記憶装置内の（k1 x p）を表示する該データを格納することによって達成される、請求項９記載の方法。
【請求項１１】
（ｅ）ｒ＝k×pを表示するデータを作るためにq1T ＝ (k1×k1×p) Tを表示する該データを置換するステップ
をも含む、請求項９記載の方法。
【請求項１２】
（ｆ）ｒ＝k×pを表示する該データによって少なくとも部分的に決定される、畳み込まれた画像データに応じてパターン信号を生成するステップと、
（ｇ）該パターン信号を一連の光学部品上に投射させ、該光学部品からのパターン画像を該パターン信号に応じてリソグラフィターゲット上に投影するステップと、
をも含む、請求項１１記載の方法。
【請求項１３】
該パターン信号が光学信号である、請求項１２記載の方法。
【請求項１４】
該パターン信号が電子ビーム信号である、請求項１２記載の方法。
【請求項１５】
畳み込みの結果r(x、y)＝Dp＝d×p（ここで、Dはｄ の循環である）を表示するデータを生成するために、少なくとも分離カーネルにほぼ等しいスムースカーネルｄ を用いて、２次元のパターンp(x、y)の畳み込みを行う方法であって、
（ａ）該カーネルd を近似するk(x,y)を用いて分離カーネルをk(x,y)＝ k２(x)k２(y)と指定するステップであって、ここで
|x|≦Rに対してk２(x)＝２ cos2(πx /２R )
|x|>Rに対してk２(x)＝０
であるステップと、
（ｂ）該パターンpの各列を表示するデータと該カーネルk２を表示するカーネルデータを処理して
（ｉ）−R−3 ≦ x ≦n−1に対して前記各列にAk2×ｐ（ここでAk2(x)×p(x)＝B(p(x＋ R)＋p(x＋R＋１)−p (x−R)−p (x−R＋１))）を表示するデータを生成し、
（ｉｉ）r（ｘ＋２）＝A r（ｘ）＋B( r（ｘ＋１）−r（ｘ）)＋r（ｘ−1）の繰り返し関係を用い、また前記繰り返し演算を始動させるようにr（−R−4）＝ r（−R−3）＝ r（−R−2）＝０の関係を用いて繰り返し演算を実施して前記各列に対するr（ｘ）＝A−1 ( Ak2(x)×p (x))を見つけ、それによってステップ（ｉｉ）の最終繰り返しの終わりでk2×ｐを表示するデータを作るステップと、
（ｃ）k2×ｐを表示する該データを置換して(k2×ｐ)Tを表示するデータを作るステップと、
（ｄ）今回は該パターンデータの列上ではなく(k２×p)Tを表示するデータの列上でステップ（ｂ）を繰り返し、それによってk２を用いてk２×pのすべての行の畳み込みを表示するデータを生成するステップと、
を含む、前記方法。
【請求項１６】
ステップ（ｂ）、（ｃ）、（ｄ）がプログラムされた処理装置で実行され、該処理装置がステップ（ｂ）の開始時に初期状態であり、ステップ(d)の後に該処理装置が更に
（ｅ）k３を用いてk２×pのすべての行の畳み込みを表示する該データを置換して該畳み込みの結果r(x、y)を表示するデータを作るステップと、
（ｆ）ステップ（ｅ）の後、初期の処理装置の状態に戻すステップと、
を行う、請求項１５記載の方法。
【請求項１７】
（ｇ）該畳み込みの結果ｒ(x,y)を表示する該データによって少なくとも部分的に決定される、畳み込まれた画像データに応じてパターン信号を生成するステップと、
（ｈ）該パターン信号を一連の光学部品上に投射させ、該光学部品からのパターン画像を該パターン信号に応じてリソグラフィターゲット上に投影するステップと、
をも含む、請求項１６記載の方法。
【請求項１８】
該パターン信号が光学信号である、請求項１７記載の方法。
【請求項１９】
該パターン信号が電子ビーム信号である、請求項１７記載の方法。
【請求項２０】
該パターンデータがステップ（ｂ）の前に記憶装置の記憶位置に格納され、ステップ（ｃ）が、（k2 × p）の各行を表示するデータがp(x,y)の列を表示する該パターンデータによって以前に占有された該記憶位置の列を占有するように該記憶装置内の（k2×p）を表示する該データを格納することによって達成される、請求項１５記載の方法。
【請求項２１】
B ＝２sin2(π/２L)である、請求項１５記載の方法。
【請求項２２】
B＝１である、請求項１５記載の方法
【請求項２３】
少なくとも分離スプラインカーネルにほぼ等しいスムースカーネルｄ を用いて、ｎ次元のパターンp（x1, …, xn）を表示する第一データを畳み込み、kj が循環Kj を持つ、dを近似し、該カーネルk(x1,…,xn )がパターンp の各列に対してq1＝A1k1×p を表示する第三のデータを生成するように前記第一データを用いて、Aj が、AjKjがまばらである(Aj が消滅演算子であるとき)か、AjKj がほとんど至るところで局所的に一定マトリクスである（Aj が平滑化演算子あるとき）ようにカーネルkjの循環Kj上で演算する消滅演算子か平滑化演算子である演算子A＝A1A2...Anであることを容認する分離スプラインカーネルk(x1,…xn)＝k1(x1)…kn(xn)を表示する第二データを処理することによって、かつ、前記パターンに対するr1＝k1 × p を表示する第四データを決定するために該パターンの前記各列に対してA1r1＝q1を後方計算するように第三データを処理することによって、かつ、r1T＝(k1×p)Tがr1の置換を示す(k1×p)Tの各列に対してq2＝A2k2×(k1×p)Tを表示する第五データを生成するように第四データを処理することによって、かつ、(k1×p)Tの前記各列に対してA2rT＝q2を後方計算するように第五データを処理し、それによって前記パターンに対するr2T＝(k2×k1×p)Tを表示する第六データを決定することによって、畳み込みの結果r ＝Dｐ＝d×p（ここで、Dはｄの循環であり、ｎは１より大きい）を表示するデータを生成するソフトウェアでプログラムされた処理装置と、
該処理装置に結合され、アクセス可能な、少なくとも該第一データ、該第二データ、該第五データを格納するよう構成された少なくとも一つの記憶装置と、
該処理装置が該入力装置からの少なくとも一つの制御信号に応じて該ソフトウェアを実行する、該処理装置に結合された入力装置と、
を含む、計算機システム。
【請求項２４】
ｎ＝２であり、該ソフトウェアが該第六データ上に置換を行わせて該処理装置に前記パターンに対してr＝(k2×k1×p)を表示する第七データを生成し、ここで該第七データが畳み込みの結果r＝Dp＝d×ｐを表示する前記データである、請求項２３記載のシステム。
【請求項２５】
n次元のパターンp(x1, …, xn)を表示する第一データと、kj が循環Kj を持ち、カーネルk(x1,…,xn )が、演算子A ＝ A1A2...Anを容認し（ここで、Ajは消滅演算子か平滑化演算子であり、この消滅演算子か平滑化演算子は、AjKjがまばらである（Aj が消滅演算子であるとき）か、AjKj がほとんど至るところで局所的に一定マトリクスである（Aj が平滑化演算子あるとき）ような方式でカーネルkjの循環Kj上で演算する）、前記カーネルkはnが１より大きいとき循環Dを持つスムースカーネルに少なくともほぼ等しい分離スプラインカーネルk(x1,…xn)＝k1(x1)…kn(xn)を表示する第二データを含むデータ上で算術演算を行うように構成されたデジタル信号処理回路と、
デジタル信号処理回路に結合され、該第一データ上で畳み込みをデジタル信号処理回路に行わせるデジタル信号回路に命令に応じて制御ビットを生成させるように、かつパターンp の各列に対するq1＝A1k1×p を表示する第三データを生成するように該第一データと該第二データを処理することによって、また前記パターンに対するr1＝k1×pを表示する第四データを決定するために該パターンｐの前記各列に対してA1r1＝q1を後方計算するように該第三のデータを処理することによって、またr1T＝(k1×p)Tがr1の置換を示す(k1×p)Tの各列に対してq2＝A2k2×(k1×p)Tを表示する第五データを生成するように該第四データを処理することによって、また(k1×p)Tの前記各列に対してA2r2T＝q2を後方計算するように第五データを処理し、それによって前記パターンに対するr2T＝(k2×k1×p)Tを表示する第六データを決定することによって、デジタル信号処理回路に制御ビットを送ることを保証するように構成されたプログラム制御ユニットと、
を含むデジタル信号処理装置。
【請求項２６】
n＝２であり、該制御ビットが該デジタル処理回路に前記パターンに対してr＝(k2×k1 ×p)を表示する第七データを表示するように該第六データ上に置換を行わせる、請求項２５記載のシステム。
【請求項２７】
デジタル信号処理回路と、該デジタル信号回路に結合されたプログラム制御ユニットを含み、該デジタル信号処理回路は、n次元のパターンp(x1, …, xn)を表示する第一データと、分離スプラインカーネルk(x1,…xn)＝k1(x1)…kn(xn)を表示する第二データとを含むデータ上で算術演算を行うように構成され（ここで、kj は循環Kj を持ち、カーネルk(x1,…,xn )は、演算子A＝A1A2...Anを容認するが、Ajは消滅演算子か平滑化演算子であり、この消滅演算子か平滑化演算子は、AjKjがまばらである（Ajが消滅演算子であるとき）か、AjKjがほとんど至るところで局所的に一定マトリクスである（Ajが平滑化演算子あるとき）ような方式でカーネルkjの循環Kj上で演算し、前記カーネルｋは、ｎが１より大きいとき循環Dを持つスムースカーネルに少なくともほぼ等しい）、プログラム制御ユニットからの制御ビットに応じてパターンp の各列に対するq1＝A1k1×pを表示する第三データを生成するように該第一データと該第二データを処理することによって、かつ、前記パターンに対するr1＝k1×pを表示する第四データを決定するために該パターンの前記各列に対してA1r1＝q1を後方計算するように該第三データを処理することによって、かつr1T＝(k1×p)Tがr1の置換を示す(k1×p)Tの各列に対してq2＝A2k2×(k1×p)Tを表示する第五データを生成するように該第四データを処理することによって、かつ、(k1×p)Tの前記各列に対してA2r2T＝qを後方計算するように第五データを処理し、それによって前記パターンに対するr2T＝(k2×k1×p)Tを表示する第六データを決定することによって、かつ、前記パターンに対するr2＝（k2×k1×p）を表示する第七データを生成するよう第六データ上で置換を実行することによって、該第一データ上で畳み込みを行うよう構成されたデジタル信号処理装置と、
前記第七データによって少なくとも部分的に決定され、畳み込まれた画像データに応じてパターン信号を生成するよう構成されるパターン信号発生器と、
該パターン信号がその上に投射するよう配置され、光学部品が該パターン信号に応じてリソグラフィターゲット上にパターン画像を投射する一連の光学部品と、
を含む、リソグラフィ・システム。
【請求項２８】
該デジタル信号処理装置が該パターン信号発生器に前記第七データを導入することを保証し、該パターン信号発生器が前記第七データに応じてパターン信号を生成するように構成されている、請求項２７記載のリソグラフィ・システム。
【請求項２９】
該パターン信号が光学信号である、請求項２７記載のリソグラフィ・システム。
【請求項３０】
該光学信号が光学ビームであり、該一連の光学部品が該光学ビームを焦点の合ったビームに生成するように焦点をあわせるように構成され、該リソグラフィターゲットに対して該焦点の合ったビームを走査するように構成されている、請求項２９記載のリソグラフィ・システム。
【請求項３１】
該パターン信号が電子ビーム信号である、請求項２７記載のリソグラフィ・システム。
【請求項３２】
該一連の光学部品が該電子ビームを焦点の合った電子ビームに生成するように焦点をあわせるように構成され、該リソグラフィターゲットに対して該焦点の合った電子ビームを走査するように構成された、請求項３１記載のリソグラフィ・システム。
【請求項３３】
ｎ次元のパターンp(x1, …, xn)を表示する第一データを、スムースカーネルｄを近似する分離スプラインカーネルk(x1,…xn)＝k1(x1)…kn(xn)を表示する第二データで畳み込みを行うよう構成され（ここで、kj は循環Kj を持ち、カーネルk(x1,…,xn )は、演算子A ＝A1A2...Anを容認するが、Aj は消滅演算子か平滑化演算子であり、この消滅演算子か平滑化演算子は、AjKjがまばらである(Aj が消滅演算子であるとき)か、AjKj がほとんど至るところで局所的に一定マトリクスである（Aj が平滑化演算子あるとき）ような方式でカーネルkjの循環Kj上で演算する）、該第一信号と該第二信号から該パターンp の各列に対するq1＝A1k1×pを表示する第三信号を生成することによって、かつ、前記パターンに対するr1＝k1×p を表示する第四信号を生成するように該パターンの前記各列に対してA1r1＝q1を後方計算するように該第三信号を処理することによって、かつ、該第四信号から、r1T＝(k1×p)Tがr1の置換を示す(k1×p)Tの各列に対してq2＝A2k2×(k1×p)Tを表示する第五信号を生成することによって、かつ、(k1×p)Tの前記各列に対してA2r2T＝q2を後方計算するように第五信号を処理し、それによって前記パターンｐ に対するr2T＝(k2×k1×p)Tを表示する第六信号を生成する（ここで、前記第六信号が畳み込みの結果r＝Dｐを少なくとも近似的に表示するものである）ことによって畳み込みの結果r＝Dｐ＝d×pを表示する信号（ここで、Dがｄ の循環であり、ｎが１より大きい）を生成するように構成された装置。
【請求項３４】
装置が電子回路からなる、請求項３３記載の装置。
【請求項３５】
該装置がプログラム可能なゲートアレイを基本とした計算機システムである、請求項３３記載の装置。
【請求項３６】
命令を格納する計算機読み出し可能な記憶媒体であって、該命令が計算機によって実行可能であり、該命令が、該計算機がｎ次元のパターンp(x1, …, xn)を表示する第一データをkj が循環Kj を持ち、スムースカーネルｄを近似し、カーネルk(x1,…,xn )がAj はAjKjがまばらである(Aj が消滅演算子であるとき)か、AjKj がほとんど至るところで局所的に一定マトリクスである（Aj が平滑化演算子あるとき）ようにカーネルkjの循環Kj上で演算する消滅演算子か平滑化演算子である演算子A＝A1A2...Anであることを容認する分離スプラインカーネルk(x1,…xn)＝k1(x1)…kn(xn)に少なくともほぼ等しい スムースカーネルｄで畳み込み、Dがｄの循環であり、nが１より大きいとき、前記命令を実行するのに応じて、畳み込みの結果r ＝Dｐ＝d×pを表示するデータを生成する方法のようなものであり、前記方法が
該パターンp の各列に対するq1＝A1k1×pを表示する第三データを生成するように前記第一データで分離スプラインカーネルk(x1,…xn)＝k1(x1)…kn(xn)を表示する第二データを処理するステップと、
前記パターンに対するr1＝k1×pを表示する第四データを決定するために該パターンの前記各列に対するA1r1＝q1を後方計算するように該第三データを処理するステップと、
r1T＝(k1×p)Tがr1の置換を示す(k1×p)Tの各列に対するq2＝A2k2×(k1×p)Tを表示する第五データを生成するように該第四データを処理するステップと、
(k1×p)Tの前記各列に対するA2r2T＝q2を後方計算するように該第五データを処理し、それによって前記パターンに対するr2T＝(k2×k1×p)Tを表示する第六データを決定するステップと、
前記パターンに対するr＝(k2×k1×p)を表示する第七データを生成するように該第六データ上で置換を行い、それによって前記第七データが少なくとも該畳み込みの結果r ＝Dｐを近似的に表示するステップと、
を含む、前記媒体。
【発明の詳細な説明】
【発明の内容】
【０００１】
関連出願の相互参照
本出願は、Richard E. CrandallによりEtec Systems, Inc.に譲渡された２０００年１月１１日出願の係属中の米国特許出願第０９/４８０,９０８号の一部継続出願である。米国特許出願第０９/４８０,９０８号の全文は、本明細書に援用されている。
発明の分野
本発明は、パターン（例えば、ピクセルアレイを表示するイメージデータ）を表示するデータ上で畳み込みを行うための信号処理方法および装置に関する。発明によれば、畳み込みカーネルは（または近似する）分離スプライン機能である。
発明の背景
畳み込みは、音、静止画像、ビデオ、リソグラフィ、無線（レーダ）信号処理の分野を含む多くの状況で、信号上で一般に行われる。典型的には、畳み込まれるべき信号はパターン信号である。“パターン”や“パターン信号”という表現の各々は、データワード（ピクセルであり得るが必要としない）の一次元シーケンス又は二次元（あるいはより高い次元の）アレイを示すために広い意味で本明細書に用いられる。典型的には、データワードは２進法のビットを含み、その畳み込みは、ソフトウェア、デジタル信号処理回路、カスタムハードウェア、またはＦＰＧＡシステム（計算システムに基づいたフィールドプログラム可能なゲートアレイ）を用いた２進法のビット上で個別のやり方で行われる。
【０００２】
本明細書の“データ”という用語は、データを表示する１つ以上の信号を意味し、本明細書の“データワード”という表現は、データワードを表示する１つ以上の信号を意味する。
【０００３】
非常に大きなパターンを表示するデータを処理する時でさえ、畳み込みを高速に実行する動機は無数に存在する。本発明は、リソグラフィの分野での近接補正の要求により動機づけられた。そのような問題においては、大きなパターン“ｐ”（パターンがピクセルアレイであるとき）と拡散カーネル“ｄ”を表示するデータ間の二次元畳み込みが試みられる。しばしば、カーネル“ｄ”は、ガウスまたはガウスの重ね合せか、あるいはスムースカーネルである。更に詳しくは、本発明は、畳み込みが正確または正確に極めて近いガウスカーネル（または他のスムースカーネル）を用いてＮＮ’ピクセル（ＮとＮ’の各々が非常に大きい）を含む二次元パターンを畳み込むのに適切な“Ｏ(ＮＮ’）”アルゴリズム（せいぜいＮＮ’乗算や加算しか必要としないアルゴリズム）を確立するという試みから生じた。
【０００４】
近接補正を行うための目的（リソグラフィ分野で）は、光学部品の出力にマスクまたはウエハ上に所望のパターンを作らせるために、一連の反射光または屈折光（または電子ビーム光）に入力することができる“生”光信号（または“生”電子ビーム信号）を生成することである。マスクまたはウエハ上の所望のパターンを作るために必要な生光信号（または生電子ビーム信号）の特性を決定するために、脱畳み込み演算子は、典型的には、よく知られた近接問題を修正するためにピクセル（パターン“ｐ”を決定する）の非常に大きなアレイ上で行われる。電子ビームリソグラフィの場合、近接問題は、書かれている基板（マスクまたはウエハ）での電子散乱に起因する。基板上の広げられた領域を電子（即ち、ピクセル自体に加えて書かれている各ピクセルを囲む領域）にさらし、散乱はビームが基板上に入射するビーム直径を超えて電子ビームを効果的に広げる。
【０００５】
ほぼ全ての近接補正スキームにおいて、そのような脱畳み込み演算子は少なくとも一回の畳み込みステップを含んでいる。従って、典型的な近接補正を行う際、ピクセルの非常に大きなアレイ（パターン“ｐ”を決定する）は、拡散カーネルで畳み込まれなければならない。そのような畳み込みは、典型的には、２進法のピクセルの非常に大きなアレイを含むパターン上で行われるが、この制限は次の議論において重要ではなく、発明の実行にとって不可欠なことではない。実際に、本発明は、下に記述される特性を有するスムース畳み込みカーネルで任意のパターン“ｐ”を表示するデータ上で畳み込みを実行することができる。
【０００６】
パターン“ｐ”と畳み込みカーネル“ｄ”を表示するデータの場合、循環畳み込みとみなす。
【０００７】
【数１】
2005517999.tif 000002
ここで、×Ｃは、畳み込み演算子が循環特性と、インディシアル束縛と範囲においてのみ異なる非循環畳み込みを有することを示す。
【０００８】
【数２】
2005517999.tif 000003
ここで“×Ａ”は畳み込み演算子が非循環特性を持つことを示す。
【０００９】
単純には、我々は多くの議論を一次元に限定する（ここで、パターンｐは順序付けられた一連のＮデータ値であり、カーネルは順序付けられた一連のＭ値である）。それにもかかわらず、発明の典型的な実施形態においては、パターンは二次元（データ値の二次元アレイＰjkはパターンを決定する）であり、畳み込みを定義する和（前段落に示した和のいずれか１つの和に相当する和）は、Ｐjkアレイの指数ｋと指数ｊと同様にインデックスｋより多いことは理解すべきである。データ値のＮ×Ｎ’アレイによって決定された二次元パターンｐの場合には、指数ｎ、ｉ、ｊ、および前の段落パラグラフの中で述べた式中のドメインの長さＮは、２ベクトルである。
【００１０】
一次元の場合には、循環畳み込みの結果は長さがＮ（Ｎデータ値を含む）であり、非循環畳み込みの結果の長さはＭ＋Ｎ−１である。
【００１１】
等価な行列ベクトル積のように循環畳み込みｄ×cｐを計算することができることが基準となる。
ｄ×cｐ＝Ｄｐ
ここで、Ｄはｄの循環行列であり（以後、ｄの“循環”）、その一次元形式は次のように（Ｎが３より大きいと仮定して）定義される。
【００１２】
【数３】
2005517999.tif 000004
それ故、循環畳み込みのための従来方式は行列代数の用語で計算することができる。非循環畳み込みは同様の行列操作で得ることができる。
【００１３】
簡単にするために、我々は非循環あるいは循環特性のどちらかを有する畳み込みを表示するために記号ｘを用いる。たいていの議論では、記号は非循環特性を有する畳み込みを意味する。当業者は、指定された非循環畳み込みと考えれば、対応する循環畳み込みが非循環畳み込みを決定するパラメータ（例えば、境界条件やカーネルの循環の定義）のわずかな修正によって実行され得るを認識する。
【００１４】
上記で引用した米国特許出願第０９/４８０,９０８号は、その中心の考え（一次元の実施形態では）が、多項式スプラインカーネルf（fはＬ区分fI(x)を備えた次数δの区分的な多項式スプライン関数f(x)である場合）によってスムースカーネルｄに近似し、次に、ｆとｐの畳み込みを高速に計算するために一定の次数（説明された方法における）の各多項式を消滅する(または平滑化する)適切な演算子を用いる高速畳み込みを開示している。いくつかの実施形態には、スムースカーネルｄは、多項式スプラインカーネルではないが、そのドメインの隣接したセグメント上に定義されたＬ区分からなるスプラインカーネルｆによって近似される（典型的な二次元の場合、その後のスプラインカーネルは、そのドメインが半径方向のパラメータの、一連の連続または不連続の値である半径方向に対称な関数である）。米国特許出願第０９/４８０,９０８号に記述されている “スプライン”畳み込みは従来のウェーブレットスキームを思い出させる特徴を持ち、Ｏ(Ｎ)アルゴリズム（ウェーブレットスキームであるような）であるが、“スプライン”畳み込みの利点は、ｃＮ算術演算（乗算と加算）を用いて（Ｎデータ値から成るパターンｐを示すデータ上で）それを実行することができることであり、一方で因数“ｂ”が典型的には（即ち、典型的に誤差分析で）因数“ｃ”より著しく大きい場合、同じデータ上の従来のウェーブレット畳み込みはｂＮ算術演算を必要とする。言い換えれば、スプライン畳み込みに関して示された大きな０定数は従来のウェーブレット畳み込みのそのような典型的な定数より著しく小さい。
【００１５】
米国特許出願第０９/４８０,９０８号に記載されているスプライン畳み込みは、Ｄがｄの循環である場合に、畳み込みの結果ｒ＝Ｄｐを表示するデータを生成するために、スムース拡散カーネルｄを用いてパターン“ｐ”（即ち、パターン“ｐ”を表示するデータ）の循環または非循環畳み込みを行う方法である。それが、データ値（例えば、ピクセル）の連続的な（または不連続的な）一次元のドメインによって決定されるという意味において、パターン“ｐ”は一次元であることができ、データ値（または不連続のデータ値の二次元アレイ）の連続的な二次元のドメインによって決定されるという意味において、それは二次元であることができ、またはｐは二次元を超える次元を持つことができる。典型的な不連続の実行において、ｉが０からＮ−１（Ｎは信号の長さである）に変わる場合、一連の不連続に順序付けられたデータ値（例えば、ピクセル）ｐｉである不連続なものによって決定されるという意味においてパターンｐは一次元であり、ｉが０からＮ−１でｊが０からＮ’−１に変わる場合、データ値ｄijのアレイによって決定されるという意味においてそれは二次元であり、または二次元以上の次元を持つ（それはデータ値の一連の三次元によって決定される）。典型的には、ｉが０からＮ−１そしてｊが０からＮ’−１に変わる場合、データ値ｄijのアレイによってカーネルｄは決定される（しかし、カーネルｄは一連の不連続なデータ値ｄ0からｄN-１によっても選択的に決定されうる）。
【００１６】
米国特許出願第０９/４８０,９０８号に記載されたいくつかの実施態様には、畳み込みＤｐは次のステップ
（ａ）多項式スプラインカーネルｆによってカーネルｄを近似する（もしカーネルｄ自体が多項式スプラインカーネルでなければ、ｄ＝ｆという条件においてステップ（ａ）は省略される）ステップと、
（ｂ）Ｆがカーネルｆの循環、Δδ＋1が、Δδ＋１Ｆ＝Ｂがまばらである方法において循環Ｆに関して作用する、消滅演算子（その形式はfの多項式セグメントの次数δに一般に依存する）である場合、ｑ＝Ｂｐ＝Δδ＋１Ｆｐを計算するステップと、
（ｃ）ｒ＝Ｆｐを決定するためにΔδ＋１ｒ＝ｑを逆演算するステップと、
を行うことにより達成される。
【００１７】
カーネルｄ自体が多項式スプラインカーネルである場合（その結果ｄ＝ｆ、またｆ＝ｄ）、その方法は正確な結果（ｒ＝Ｄｐ）を与える。そうでなければ、×が畳み込みを表示する場合、その方法における固有の誤差は（ｆ−ｄ）×ｐであり、したがって誤差は容易に制限される。
【００１８】
一次元の場合（畳み込まれるべきパターンは長さＮの一次元パターンである）では、Δδ＋１は、Ｎ×Ｎ循環行列の形式を以下のように定義する；
【００１９】
【数４】
2005517999.tif 000005
ここでは各入力が二項係数であり、δがｆのスプラインカーネルｆのスプラインセグメントの最大次数である。例えば、スプラインカーネルｆが二次元のセグメントを含むとき、δ＝２である。二次元又はより高い次元の場合、消滅演算子は下記の通り定義することができる。
【００２０】
【数５】
2005517999.tif 000006
ここで、
【００２１】
【数６】
2005517999.tif 000007
はｄ座標のｈ番目に関してのｎ次偏導関数である。例えば、ラプラス
【００２２】
【数７】
2005517999.tif 000008
は、ｄ次元の引数ｆ＝ｆ（ｘ1，ｘ2，・・・ｘｄ）の区分的な平面の関数を消滅させる。
【００２３】
一次元の場合には、スプラインカーネルｆの各セグメント（“ピボットポイント”）の終点が、カーネルｄの連続要素ｄｉおよびｄｉ＋１であってもよく、ステップ（ａ）は、カーネルｄの対応するセグメントと十分に一致する一つとしてスプラインカーネルの各セグメントを選択するためにカーブフィッティングを行うことにより実行することができる。いくつかの実施形態には、適切な境界条件が、導関数をマッチングするかピボットポイントで他のある平滑基準を満たすような、各ピボットポイントで満たされる。
【００２４】
出願第０９/４８０,９０８号に記載されたある実施例には、ステップ（ｃ）が、Ｆの少数の行によるｐの正確な乗算演算によってｒ＝Ｆｐの少数の最小コンポーネントが計算される予備的“点火”ステップを含み、次にスプラインカーネルによって決定された自然繰り返し関係を用いてｒのコンポーネントと演算子Δδ＋１の残りを決定するステップを含んでいる。例えば、一次元の条件において、“δ”がスプラインカーネルｆ（例えば、スプラインカーネルが二次のセグメントを含む場合のｒ0、ｒ1、ｒ）のスプラインセグメントの最大次数である場合、ｒの最小コンポーネントはｒ0、ｒ1、…ｒδであり、これらの（δ＋１）コンポーネントはＦの（δ＋１）行によるｐの正確な乗算演算によって決定される。（δ＋１）コンポーネントは選択的に他の方法を決定させることができる。その後、コンポーネントの残り“ｒδ”は演算子Δδ＋１によって決定された自然繰り返し関係を用いて決定される。コンポーネントｒ0、ｒ1、…、ｒδを生成する“点火”演算はＯ(Ｎ)計算で達成されうる。繰り返し関係計算もＯ(Ｎ)計算で達成されうる。
【００２５】
他の実施形態には、畳み込みｒ＝Ｄｐを行う米国出願第０９/４８０,９０８号に開示された方法は、
（ａ）多項式スプラインカーネルｆによってカーネルｄを近似する（もしカーネルｄ自体が多項式スプラインカーネルでないならば、ｄ＝ｆという条件においてステップ（ａ）は省略される）ステップと、
（ｂ）Ｆがカーネルｆの循環であり、Δδが平滑化演算子（その形式はFの多項式セグメントの次数δに一般に依存し、そして循環Ｆ上でＢ＝ΔδＦが、ほぼどこでも局所定数行列であるようなものを演算する）である場合、ｑ＝Ｂｐ＝ΔδＦｐを計算するステップと、
（ｃ）ｒ＝Ｆｐを決定するためにΔδｒ＝ｑを後方計算するステップと、
を含んでいる。一次元の場合（ｐの長さはＮである）には、Δδは、Ｎ×Ｎ循環行列の形式をもっている。
【００２６】
【数８】
2005517999.tif 000009
ここで、各入力は二項係数であり、δはスプラインカーネルｆのスプラインセグメントの最大の次数である。より高い次元の場合には、平滑化演算子Δδが同様に定義される。
【００２７】
米国特許出願第０９/４８０,９０８号に開示された他の実施形態では、畳み込みＤｐ（Ｄは平滑カーネルｄの循環である）は、
（ａ）多項式スプラインカーネルでないスプラインカーネルｆによってカーネルｄに近似するステップ（もしカーネルｄ自体が多項式スプラインカーネルとは異なった、スプラインカーネルのようなものでなければ、ｄ＝ｆという条件においてステップ（ａ）は省略される）と、
（ｂ）ｑ＝Ｂｐ＝ＡＦｐを計算するステップであって、Ｆがカーネルｆの循環であり、Ａは消滅または平滑化演算子であり、Ａが消滅演算子であるとき、ＡＦ＝Ｂがまばらであるという方法で循環Ｆに関してＡが演算し、Ａが平滑化演算子であるとき、ＡＦ＝Ｂがほぼどこでも局所定数行列である方法で循環Ｆに関してＡが演算する、前記ステップと、
（ｃ）ｒ＝Ｆｐを決定するためにＡｒ＝ｑを後方計算するステップと、
を含んでいる。
【００２８】
従来の畳み込み方法に対して本発明の利点をより良く評価するために、我々は次に２つのタイプの従来の畳み込み方法：フーリエに基づいた畳み込みとウェーブレットに基づいた畳み込みについて説明する。
【００２９】
よく知られているように、Ｆがフーリエ行列である場合、フーリエに基づいた畳み込みは簡潔な事実に依存する。例えば、
Ｆjk＝ｅ−２πｊｋ/Ｎ
次に循環の変形ＦＤＦ-1は対角であり、我々は下記式を計算する。
Ｄｐ＝Ｆ-1（ＦＤＦ-1）Ｆｐ
かなり適切な演算子Ｆｐが通常のフーリエ変換であり、かっこの部分による演算子は（対角状態による）二進法の積であり、最終演算子Ｆ-1は逆フーリエ変換である。対角行列ＦＤＦ-1の生成は一回の変換を必要とするので、任意のＤにおける変換には三回のフーリエ変換を実際には必要とする。しかしながらＤが固定され、一回で変換がされる場合には、次の畳み込みＤｐは、よく知られているように、各々二回の変形だけが必要となる。フーリエに基づいた循環畳み込みのときの複雑性は、要求される二つまたは三つのＦＥＴ（高速フーリエ変換）のために、長さＮ（Ｎデータ値によって決定されたパターン）のパターンｐを畳み込むためのこのようなＯ（ＮｌｏｇＮ）演算子（即ち、ＮｌｏｇＮの命令における乗算と加法）である。フーリエの方法は（ＦＥＴ精度に依存する、まるめ誤差に至るまで）正確な方法であることを留意すべきである。
【００３０】
従来の畳み込み方法の別のクラスは、それらの性質によって一般に不正確であるウェーブレット畳み込み方法から成り立つ。そのような方法の基礎となる考えは簡潔で、行列代数のパラダイムの中で以下のように使える。Ｎごとの循環Ｄを与えられると仮定すると、下記特性を持っている行列Ｗ（典型的にコンパクトなウェーブレット変換である）を見つけることが可能である、
（１）Ｗは単一である（即ち、Ｗ-1はＷの随伴行列である）、
（２）Ｗはまばらである、
（３）ＷＤＷ-1はまばらである、
ここで、この関係において“まばら”は、Ｏ(Ｎ2)というのではなく、任意のｘにおけるどんな行列ベクトル積Ｗｘも、縮小された複雑性Ｏ(Ｎ)を含んでいることを単に示している。
【００３１】
想定する特性を用いて、我々は次のように計算することができる。：
Ｄｐ＝Ｗ-1（ＷＤＷ-1）Ｗｐ
３つのまばらマトリクスベクトル積によって、ユニタリティはＷ-1のまばらを意味するということが留意される。したがって、ウェーブレットに基づいた畳み込み複雑性は、一定の循環Ｄとして両方のまばら特性を厳密に与える行列Ｗを見つけることが一般に不可能である以外、Ｎデータ値によって決定されたパターンｐを畳み込むためのＯ(Ｎ)である。典型的には、畳み込みカーネルｄが十分に平滑である場合には、ウェーブレット演算子Ｗ（まばらである）は、ある許容しうる近似誤差内では、上記の特性（3）が適用できるものと分かる。上記の特性（１）と（２）は、少なくともコンパクトウェーブレット（それは通常近似である、特性（３）である）の群にとって共通である。
【００３２】
従来のウェーブレット畳み込みに対する（米国出願第０９/４８０,９０８号の教示によれば）“スプライン”畳み込みの利点は、ｃＮ算術演算を用いて（Ｎデータ値を含むパターンｐを示すデータ上で）行うことができるということであるが、（典型的な誤差が組まれていると想定している）因数“ｂ”が因数“ｃ”より著しく大きい場合、同じデータ上の従来のウェーブレット畳み込みは、ｂＮ算術演算を必要とする。出願第０９/４８０,９０８号の“スプライン”畳み込み方法の他の重要な利点の中には（従来の畳み込み方法に対して）、次のとおりである。スプライン畳み込みはスプラインカーネルｆに関しては正確であるが、ウェーブレット畳み込みスキームは設計により近似する（また、ウェーブレット畳み込みのための誤差分析は実行するのが難しい）；スプライン畳み込みによって畳み込まれた信号に対する信号長は無制限である（即ち、いくつかの従来方式のように２の累乗である必要がなく、実際には特別な形式を持つ必要はない）；また、スプライン畳み込みは０でパッディングせずに、非循環畳み込みを可能にする。
【００３３】
本発明の分離スプライン畳み込み（米国出願第０９/４８０,９０８号のスプライン畳み込みのような）は、Ｎデータ値によって決定されたパターンｐを畳み込むためのＯ(Ｎ)方法である。本発明の分離スプライン畳み込みは、本発明の分離スプライン畳み込みがｄＮ算術演算（乗法と加法）を用いて（Ｎデータ値からなる二次元又はより高い次元のパターンｐを示すデータ上で）行うことができるという点で、米国出願第０９/４８０,９０８号のスプライン畳み込みより有利であるが、同じデータ上の米国出願第０９/４８０,９０８号のスプライン畳み込みは、ｃＮ算術演算を必要とし、ここで、因数“ｃ”はより大きく、因数“ｄ”より典型的には著しく大きい。言いかえれば、本発明の分離スプライン畳み込みに示された大きなO定数は、米国特許出願第０９/４８０,９０８号に記載されるスプライン畳み込みのための典型的に示された大きなO定数より著しく小さい。
発明の概要
実施形態の１種においては、本発明は、平滑拡散カーネルｄを用いて、畳み込みの結果ｒ＝Ｄｐ＝ｄ×ｐ
ここで、Ｄはｄの循環行列（本明細書ではしばしば“循環”と呼ばれる）であり、“×”は畳み込みを示す、を表示するデータを生成するために、ｎ次元のパターン“ｐ”（即ち、ｎ次元のパターン“ｐ”を示すデータ）、ｎ≧２、の二次元の循環または非循環畳み込みを実行する方法である。二次元のパターンｐは、データ値の連続的な二次元範囲又は不連続データ値の二次元アレイによって決定される。典型的な不連続実施形態においては、パターンｐは不連続の順序づけられた一連のデータ値（例えばピクセル）Ｐij、ここで、ｉは０からＮ−１に変化し、ｊは０からＮ’−1に変化する、によって決定されるという意味で二次元である。パターンｐの次元が２次元以上である場合、３またはより高い次元の一連のデータ値によって決定される。典型的には、カーネルｄはデータ値ｄij、ここで、ｉは０からＮ−1に変わり、ｊは０からＮ’−1に変わる、のアレイによって決定される。
【００３４】
好適実施形態において、畳み込みｒ＝Ｄｐ＝ｄ×ｐ、ここで、ｄは分離スプラインカーネルによって十分に示された近似する（または等しい）を行う本発明の方法は、
（ａ）該分離スプラインカーネルをk(x1,…xn)＝k1(x1)…kn(xn)、ここでｋは演算子A ＝ A1A2...Anであることを容認し、ｎはパターンｐの次元であり、Aj がAjKjがまばらである(Aj が消滅演算子であるとき)か、AjKj がほとんど至るところで局所的に一定マトリクスである（Aj が平滑化演算子であるとき）ようにカーネルkjの循環Kj上で演算する消滅演算子か平滑化演算子である、と指定するステップと、
（ｂ）パターンｐ上の各々の行のq1＝A1k1×ｐを計算するステップと、
（ｃ）r1の少数のコンポーネントが直接計算され、次に演算子A1によって決定された自然な繰り返しを用いて、r1のコンポーネントの残りを決定する、予備的点火ステップを行うことにより、パターンに対するr1＝k1×ｐを決定するためにパターンの前記各行に対してA1r1＝ｑ1を後方計算するステップと、
（ｄ）パターンについてのｒ1T＝（ｋ1×ｐ）を生成するためにステップ（ｃ）の中で生成されたｒ1＝ｋ1×ｐを置換し、(ｋ1×ｐ)Tの各列に対するｑ2＝A2k2×r1T＝A2k2×(ｋ1×ｐ)Tの計算をするステップと、
（ｅ）パターンに対するｒT＝(ｋ2×ｋ1×ｐ)Tを決定するために(ｋ1×ｐ)Tの上述の各列に対するA2rT＝q2を後方計算するステップと、
を含んでいる。
【００３５】
パターンｐが二次元である（ｎ＝２）場合において、ステップ（ｅ）の結果はｒ＝（ｋ2×ｋ1×ｐ）、ここで、結果ｒは（希望畳み込みｒ＝Ｄｐに近い近似である）ｋ×ｐと厳密に等しい、を表示するデータを生成するために典型的には転換される。
【００３６】
ｎ＞２であるｐがｎ次元パターンである場合、各々の付加された次元に対してそれらが各々のために繰り返されるという意味で、ステップ（ｄ）と（ｅ）は繰り返され（ｑｉ＝Aiki×ｑｉ-1はｉ回の繰り返し中にｉ回目の次元で計算されている）、ステップ（ｅ）の最終繰り返しの結果の置き換えは、ｋ×ｐと正確に等しく、所望の畳み込みｒ＝Ｄｐに密接な近似である。ｎ次元のアレイＭ（軸ｉ1,i2,…inを有する)について、多次元の置換は(Ｍi1,i2...in)T＝Ｍi2,i3...ini1として定義される。
【００３７】
ステップ（ｃ）のある実施形態においては、ｒ1の少数の最小コンポーネントは、予備的点火ステップの間で直接計算され、ｒ1のコンポーネントの残りは自然繰り返し関係を用いて決定される。ステップ（ｃ）の好適実施形態においては、ｒ1の少数の大きな負のコンポーネントは、予備的点火ステップの間に直接計算され、ｒ1のコンポーネントの残りは自然繰り返し関係を用いて決定される。
【００３８】
カーネルｄ自体が分離スプラインカーネルである場合（その結果ｄ＝ｋ、及びＫ＝Ｄ）、該方法は正確な結果（ｒ＝Ｄｐ）を与える。さもなければ、該方法における固有の誤差は（k−d）×ｐであるので、誤差は容易に束縛される。
【００３９】
パターンｐが二次元である好適実施形態の１種において、２次元カーネルはk(x,y)＝k1(x)k1(y)として定義される。
|x|≦Rに対して、k1(x)＝(R2−x2)  
|x|>Rに対して、k1(x)＝cd−|x|
一次元カーネルk1(x)は３つの部分を有する。
k1(x)＝k c(x)＋k+(x)＋k_(x)
であり、ここで、k c(x)はカーネル
|x|≦Rに対してkｃ(x)＝(R2−x2)  
|x|>Rに対してkｃ(x)＝０
であり、k +(x)が片側のラプラス カーネルで
|x|>Rに対してk+(x)＝cd−|x|
|x|≦Rに対してk+(x)＝０
であり、k−(x)が片側のラプラスカーネルで
|x|<−Rに対して、k−(x)＝cdx
|x|≧Rに対して、k−(x)＝０
である。
各々の一次元畳み込みは三つ部分で行われる。キャップ（|x|）および２減衰範囲（x>R、x<−R）は、各々異なる畳み込みによって各々出され、最終結果を得るためにその結果はともに加えられる。
【００４０】
より詳しくは、実施形態の言及した方法においては、本発明は畳み込みｒ＝ｄ×ｐ、ここで、ｐは二次元パターンであり、ｄは分離スプラインカーネルによって十分に近似されている（または等しい）カーネルである、を
（ａ）分離スプラインカーネルをk(x,y)＝ｋ1(ｘ)ｋ1(ｙ)、ｋ1(ｘ)が前段落で定義されているとして指定するステップと
（ｂ）パターンｐの各列に対するキャップ畳み込みｋc×ｐ(ｘ）、上述の各々の列に対する第二畳み込みｋ+×p(ｘ)、前記各列に対する第三の畳み込みｋ_×ｐ(ｘ)を計算し、次を表示するデータを生成するために前記各列に対するキャップ畳み込み、第二畳み込み、第三畳み込みをともに加算し、
ｑ1＝ｋ1×ｐ＝（ｋc×ｐ）＋（ｋ＋×ｐ）＋（ｋ_×ｐ）、
ここで、キャップ畳み込みは前記各列に対するＡcＫc×ｐを計算し、Ａcは
Ａcｋc（ｘ）＝ｋc（ｘ＋３）−３ｋc（ｘ＋２）＋３ｋc（ｘ＋１）-ｋc（ｘ）として定義される消滅演算子である、繰り返し関係
kc(x＋3)＝Acｋc(x)＋ｋc(x)＋3kc(x＋2)−3kc(x＋1)を用いてAc-1(Acｋc×p)(x)＝ｋc×p(x)を計算することによって達成され、第二畳み込みは前記各列に対するA＋k＋×p(x)を計算し、ここで、A＋は
A＋k＋(x)＝k＋(x＋1)−d-1k＋(x)として定義された消滅演算子であり、繰り返し関係：
(k＋×p)(x＋1,y)＝(A＋k＋×p)(x,y)＋d−1(k＋×p)(x,y)を用いてA＋-1(A＋k＋×p)(x)＝k＋×p(x)を計算することによって達成され、
第三畳み込みは前記各列に対するA_k_×p(x)を計算し、ここでA-は
A_k_(x)＝k_(x−1)−d-1k_(x)として定義される消滅演算子であり、下記繰り返し関係(k_×p)(x-1,y)＝(A_k_×p)(x,y)＋ｄ-1（k×p）(x,y)を用いて最初から最後まで繰り返すことによりA_-1(A_k_×p)(x)＝k_×p(x)を計算することにより達成されるステップと、
（ｃ）(ｋ1×ｐ)Tを生成するために(ｋ1×ｐ)を置換するステップと、
（ｄ）ステップ（ｂ）を、このときpの列の上ではなく(ｋ1×ｐ)Tの列の上で繰り返し、それによってそのためｋ1をもったｋ1×ｐの列をすべて畳み込むステップと、
（ｅ）ｒ＝ｋ×ｐを示すデータを生成するためにステップ（ｄ）の結果を置換するステップと、
を行うことにより達成する。
【００４１】
典型的には、パターンp(x,y)はステップ（ｂ）より前の記憶装置に格納され、ステップ（ｂ）の各々の繰り返しは記憶装置から読みこまれたパターンp(x,y)の異なる列上で行われ、ステップ（ｃ）はメモリに以前、p(x,y)の対応する列によって占められたメモリ位置を(ｋ1×ｐ)Tの各列が占めるように(ｋ1×ｐ)T格納するステップを含んでいる。
任意に、最終ステップ（ステップ（ｅ））は省略される。
【００４２】
パターンｐが二次元である個的実施形態の他の種類においては、二次元カーネルは下記のように定義される
k(x,y)＝k2(x)k2(y)
|x|≦Rに対して、k２(x)＝２cos2（πｘ/(2R)）
|x|>Rに対して、k２(x)＝０
一次元カーネルk2(x)は二つの部分を有する。
ｋ2(x)＝kc(x)＋ki(x)，
ここで、kc(x)はカーネルであり、
|x|≦Rに対して、kc(x)＝２cos(πx/R)
|x|>Rに対して、kc(x)＝０
ki(x)は
|x|≦Rのとき、ki(x)＝１
|x|>Rに対して、ki(x)＝０である。
【００４３】
更に詳しくは、前段落で定義されたk2(x)を用いたk(x,y)＝k2(x)k2(y)における実施形態においては、畳み込みｒ＝ｄ×ｐ、ここで、ｄは分離コサインカーネルによって十分に近似する（または等しい）、を行う本発明の方法は、
（ａ）分離コサインカーネルをk(x,y)＝k2(x)k2(y)として指定するステップと、
（ｂ）パターンp(x,y)の各列に対して、次の二つのステップ
（ｉ）−Ｒ−３  ｘ  ｎ−１の場合、前記各列に対する値Ak2×pを次のようにAｋ2(x)×ｐ(ｘ)＝２sin2(π/２Ｌ)(ｐ(ｘ＋Ｒ)＋ｐ(ｘ＋Ｒ＋１)−ｐ(ｘ−Ｒ)−ｐ(ｘ−Ｒ＋１))計算するステップと、
（ｉｉ）前記各列に対するr(x)＝A-1(Ak2×p)を見つけるために、繰り返し関係ｒ(ｘ＋２)＝Aｒ(ｘ)＋２sin2(π/２Ｌ)(ｒ(ｘ＋１)−ｒ(ｘ))＋ｒ(ｘ−１)を用い、前記繰り返し演算を点火するために関係ｒ(−Ｒ−４)＝ｒ(−Ｒ−３)＝ｒ(−Ｒ−２)＝０を用いて回帰演算を行い、それによってステップ（ｉｉ）の最終繰り返しの終わりにｋ2×ｐを得るステップと
を行い、
（ｃ）(ｋ2×ｐ)Tを得るためにｋ2×ｐを置換するステップと、
（ｄ）ｐの列ではなく(ｋ2×ｐ)Tの列上でこのとき、ステップ（ｂ）を繰り返し、それによってｋ2を用いたｋ2×ｐのすべての列を畳み込むステップと
を含んでいる。
【００４４】
好ましくは、ステップ（ａ）〜（ｄ）は適切にプログラムされた処理装置によって行われ、処理装置は、更に、（ｅ）ステップ（ｄ）の後、r(x,y)を得るためにステップ（ｄ）の結果を置換するステップと、初期のプロセッサー状態に戻すステップを行う。この種類での実施形態の変法においては、因数２sin2(π/２Ｌ)は因数１に置き換えられる。
【００４５】
他の実施形態においては、本発明は、発明の方法の、任意の実施形態に従って分離カーネルを用いて、ｎ次元パターン（ｎは２以上である）を表示するデータ上に、畳み込みを行うソフトウェアでプログラムされたコンピュータである。発明の他の実施形態は、本発明の方法の任意の実施形態に従った分離カーネル、本発明の方法の、任意の具体形態に従ったそのようなデータ上の畳み込みを実行するために構成された装置（カスタムまたは特定の電子回路、またはシステム（“ＦＰＧＡシステム”）、そのようなデジタル信号処理回路、そのようなカスタムまたは特定の電子回路、またはそのようなＦＰＧＡシステムを含んでいるリソグラフィ・システムを用いた、ｎ次元パターン（ｎは２以上である）を表示するデータについて畳み込みを行うために構成されたデジタル信号処理回路を含むデジタル信号プロセッサーを含んでいる。
【００４６】
また、コンピュータ実行可能な命令を格納するコンピュータ読み取り可能な記憶媒体も発明の範囲内であり、ここで、命令は命令の実行に応じて本発明の実施形態をコンピュータが行うようなものである。
好適実施形態の詳細な説明
特許請求の範囲に含まれる開示内容全体の用語“データ”はデータワードを表示する１つ以上の信号を意味する。したがって、パターン“ｐ”を表示するデータが、パターンｐを表示する一つ以上の信号を意味するスムースカーネル“ｄ”を表示するデータを用いて畳み込まれる（本発明）という表現は、畳み込み結果を表現するデータ（即ち、１つ以上の信号）を生成するために、カーネルｄを表現する、1つ以上の他の、一連の信号で処理されることを意味する。
【００４７】
本発明の好適実施形態は、“消滅”演算子や“平滑”演算子として記載される。
【００４８】
我々は、最初に分離に関する理論について発見的な動機を提供する。スプライン畳み込みに関する理論は、我々がその範囲の各々は演算子Ａによって消滅される部分的なカーネルから開始する前提に基づいている。次に、我々は、Ａｋによるパターンの畳み込みを行う。Ａがカーネルの各領域を消滅させるので、畳み込みは実際にはカーネルの領域の境界をもつ。したがって、次元ｄの畳み込みについて、Ａｋはある意味（ｄ−１）次元のカーネルである。例えば、カーネルを考えると：
ｘ2＋ｙ2≦ｒ02に対して、k(x,y)＝α(ｒ04−２ｒ02(ｘ2＋ｙ2)＋(ｘ2＋ｙ2)2)
ｘ2＋ｙ2>ｒ02に対して、k(x,y)＝０
このカーネルが消滅するとき、その境界はｋの不連続によって生成された、ｒ0でのリングである。Ａｋの０でないエリアはｒ０において線形あり、また、これはそれが“次元”ｄ−１であると私たちが言うとき、意味されるものである。
【００４９】
発明の畳み込みが分離カーネルを用いるということはこの理由である。基礎前提は、発明の二次元の畳み込みを行うために、分離カーネルを“因数分解”し、二つの一次元畳み込みを行うということである。これらの畳み込みは範囲に依存せず、実際にこの技術は、畳み込み演算の回数を劇的に減少させる。
【００５０】
我々が二次元カーネル、k(x,y)を有すると仮定すると、次のように表現することができる。
ｋ(x,y)＝kx(x)ky(y)
これがそうである場合には、パターンｐが示され、我々は次のような畳み込みの結果を表現することができる：
【００５１】
【数９】
2005517999.tif 000010
しかし、
【００５２】
【数１０】
2005517999.tif 000011
はｋjによるpの行ごとの畳み込みであることに注目のこと。発明の生じる畳み込みを得るために、我々はpy(y,j)を決定し、その後、列に沿ってｋxによりこれを畳み込む。次の例が示すように、この畳み込みはピクセル当たりわずかな演算によって特徴づけられる。
【００５３】
次の実施例は、発明に従って実行された分離スプライン畳み込みの二つの実施例である。これらの実施例は多項式、ラプラス、三角法のスプライン技術を例示するために選択されたものである。
実施例１：ラプラス減衰分離カーネルを用いた二次式
この算法における一次元スプラインカーネルは次のように定義される。
|x|≦Rに対して、ｋ1(ｘ)＝ａ(ｂ2-ｘ2)
|x|> Rに対して、ｋ1(ｘ)＝cd-|x|
連続性を達成するためにそのα(b2-R2)＝cd-Rを主張することができる。
【００５４】
２次元カーネルは下記のように定義される：
k(x,y)＝k1(x)k1(y)                              （１）
各々の一次元の畳み込みは三つの部分で行われる。キャップ（|x|）と２つの減衰範囲（x>R、ｘ<-R）は、各々異なる畳み込みによって作られ、最終結果を得るためにその結果はともに加えられる。
【００５５】
一次元キャップ畳み込みは、カーネル
|x|≦Rに対して、kc(x)＝ａ(b2-x2)
|x|> Rに対して、kc(x)＝０
を用いて次のように達成される。我々は、形式
Ackc(x)＝ekc(x+i)＋fkc(x+j)＋gkc(x+m)＋hkc(x+n)
ここで、e、f、g、h、I、j、m、nは整数である、消滅演算子Ａcを選択する。
【００５６】
e、f、g、h、I、j、m、nの適切に選択された値においては、Ackc(x)は、パラメータｘの少数の特定の値の場合以外は０である。したがって、各ｘ値に対する（Ackc×p）を計算するために、少数の加算（および畳み込みが行われる間隔の境界の近くの少数の加算さえ）を単に計算する必要がある。各ｘ値のために(Ackc×p)(x)を計算した後、繰り返し関係はAc-1(Ackc×p)(x)＝r(x)を計算するために用いられる。典型的な実行においては、繰り返し関係計算を“点火する”ために、Ａc-1(Ａcｋc×ｐ)(ｘ）の少数の初期値が直接計算によって見つけられる。
【００５７】
kc(x)におけるパラメータ“ａ”と“ｂ”がａ＝１とｂ＝Ｒを満たす場合を考える。この場合、我々は
Ａcｋc(ｘ)＝kc(x+3)−3kc(x+2)＋3kc(x+1)−kc(x)となるための消滅演算子Ａcを選択する。
【００５８】
この演算子Ａcにおいて、Ackc(x)は、次のｘの、４つの値；ｘ＝−２Ｒ＋１、ｘ＝２Ｒ＋１、ｘ＝２Ｒ−１、ｘ＝−２Ｒ−１以外は０である。したがって、ｘの各値に対して(Ａcｋc×ｐ)(ｘ)を計算するために、７つの加算（および畳み込みが行われる間隔の、境界近くの少数の加算さえ）を単に計算することが必要である。Ａc-1(Ackc×p)(x)＝r(x)を計算するために用いられる繰り返し関係は、形式
kc(x+3)＝Ackc(x)＋kc(x)＋3kc(x+2)−3kc(x+1)におけるＡcを定義した方程式を書き直し、ｘに対して繰り返し計算することにより決定される。最後の問題は、これをするために我々がｋcの3つの初期値を必要とするということである。畳み込みを“点火する”というこの問題に対し二つの解決策がある。最初に、我々は、３(２Ｒ−２)乗算を３(２Ｒ−３)加算をする、値{r(0),r(1),r(2)}を直接計算で解くことができる。そうでなければ、我々は、これらのポイントがパターンから離れ、カーネル範囲を越えて位置するので、r(x)は−Ｒ未満のｘに対して０でなければならないことに留意することができる。したがって、我々はｒ(−Ｒ−２），ｒ(−Ｒ−１）、ｒ(−Ｒ）がすべて０であることがわかる。次に、我々は{r(0),r(1),r(2)}を見つけるため繰り返すことができるので、畳み込みを無視する。後者の手順は、３(Ｒ＋２)を加算し（Ｒ＋２）を乗算することを必要とするので、その場合、第二の方法ははるかに経済的である。第二の方法が第一の方法ほど経済的でなくなる他の場合がある。
【００５９】
正の減衰領域に対する一次元畳み込みは片側ラプラス減衰カーネルを用いて行われる。
|x|> Rに対して          ｋ＋(ｘ)＝ｃｄ-|ｘ|
|x|≦Rのとき            ｋ＋(ｘ）＝０
それは単純な消滅演算子Ａ＋によって消滅される：
A＋k＋(x)＝k＋(x+1)-d-1k＋(x)
A＋k＋(R)＝cd-R、一方A＋k＋(R)＝0に注目のこと。これはパターン変換と規模であり、繰り返しは下記と同様に単純である。
ｒ(x+1)＝(A＋k＋×p)(x)+d-1r(x)
この減衰カーネルについて興味深い点は、結果の領域に点火し得ることである。即ち、我々は、ｒがＲ未満のすべてのｘに対して０であることがわかる。我々は第一のＲ値を０で満たすので、その時にスプラインが実際に始まる。
【００６０】
負の減衰領域のための一次元畳み込みは、繰り返しが対向する向きに取られるべきもの以外は、正の減衰領域に対する一次元の畳み込みとまったく同じである。kcとk＋の畳み込みがポインタの単一通過上で計算することができるので、これは算法を遅くするが、ｋ_畳み込みは、第二の逆通過を必要とする。
【００６１】
次のものは、発明の分離スプライン畳み込みとして前述の二次元畳み込みを実行するための一つの算法である。算法表現の場合、我々は次の定義を必要とする。ｋ_カーネルは
|x|<-Rに対して、ｋ-(ｘ)＝ｃｄｘ
|x|≧Ｒのとき、ｋ-(ｘ)＝０
であり、その消滅Ａ_は：
A_k_(x)＝k_(x-1)-d-1k_(x)
である。
【００６２】
算法は、入力として (x,y)∈Ｄに対するパターンｐ(x,y)を用い、Dは一定のサイズの矩形ドメインである。Ｄにおける全ての点でｒ(ｘ,ｙ)＝(ｋ×ｐ)(ｘ,ｙ)に戻り、ｋ(x,y)は上記の方程式（１）に定義されている。この場合、我々は、単にラプラス減衰の種類に基づき、ｋを記載する最適“定数”がＤの幅と高さに依存することから、Ｄのサイズが固定されることを要求する。下記ｋ(ｘ,ｙ)を処理することにより、算法が畳み込みを計算することを留意すること。
ｋ(ｘ,ｙ)＝(ｋｃ＋ｋ＋＋ｋ_)(ｘ)(ｋｃ＋ｋ＋＋ｋ_)(ｙ)＝ｋ1(ｘ)ｋ1 (ｙ)
算法は、より容易に理解することができるような最適化されていない方法で存在する。浮動小数点演算により、おそらく多項式畳み込みについてカタストロフィックで無秩序な振る舞いであると考えることは重要であるので、これは固定小数点数で行われなければならない。
【００６３】
“ラプラス減衰分離スプライン畳み込みによる二次のアルゴリズム”と呼ばれる算法は次のとおりである。
【００６４】
（ａ）列の上にループする。各列について、キャップ畳み込み（ステップｉ）、正の減衰畳み込み（ステップｉｉ）、列について負の減衰畳み込み（ステップiii）を計算し、前記列に対してステップ（ｉ）、（ｉｉ）、（ｉｉｉ）において得られた三つの畳み込みを共に加算する（ステップｉｖ）ことによってｋ1(ｘ)を用いて列の畳み込みを計算する。ステップ（ｉ）、（ｉｉ）、（ｉｉｉ）、（ｉｖ）ステップの一回の反復は、パターンの各列に対するように行われる。
【００６５】
（ｉ）ｋc畳み込みを以下のように計算するステップ、
上述のパターンの行を用いて畳み込まれる消滅カーネル、(Ａcｋc×ｐ)(ｘ）、ここで、Ａcが上記で定義される、を計算するステップと、
ｋｃ(ｘ)におけるパラメータ“a”と“ｂ”がa＝１とｂ＝Ｒを満たす場合には、ｋc(ｘ＋３)＝Ackc(x)＋kc(x)＋３kc(x+2)−３kc(x+1)である上記繰り返し関係を用いてＡc-1(Ａcｋc×ｐ)(ｘ,ｙ))を計算するステップ；
（ｉｉ）ｋ＋畳み込みを以下のように計算するステップ：
Ａ＋が上で定義したとおりである場合、消滅カーネルが上述のパターンの前記列を用いて畳み込まれた(A＋k＋×p)(x)を計算し、(Ａ＋ｋ＋×ｐ)(ｘ)＝ｃｄRp(x-R,y)であるので、これは重要でない計算であると考える、
下記繰り返し関係を用いて
(ｋ＋×ｐ)(ｘ＋1,y)＝(Ａ＋ｋ＋×ｐ)(x,y)＋d-1(ｋ＋×ｐ)(x,y)；
A＋-１(A−k−×p)(x,y))を計算する；
（ｉｉｉ）ｋ_畳み込みを計算する：
Ａ_が上記で定義される場合、消滅カーネルが上述のパターンの行を用いて畳み込まれる、(Ａ_ｋ_×ｐ)(ｘ)を計算するステップ。(A_k_×p)(x)＝ｃｄ−Ｒp(ｘ＋Ｒ,ｙ）であるので、これが重要でない計算であることに注目する；
下記の繰り返し関係を用いて、初めから最後まで繰り返すことによってＡ_-1(A_k_×p)(x,y))を計算する；
(ｋ_×ｐ)(x−１,y)＝(A_k_×p)(x,y)＋ｄ-1(ｋ_×ｐ)(x,y)；
（iv）上述のパターンの行に対してステップ（i）、（ii）、（iii）の結果を加算し、それによってｋ1×ｐ＝(kc×p)＋(k＋×p)＋(k_×p)を表示するデータをステップ（iv）の最後の繰り返しの終わりに得るステップ；
（ｂ）(k1×p)Tを得るためにｋ1×ｐを変換させる、
（ｃ）ｐの列以外である(k1×p)Tの列についてこのとき、ステップ（ａ）を繰り返し、それによってｋ1をもつk1×pの全ての行を畳み込む、
（ｄ）r(x,y)を得るためにステップ（ｃ）の結果を変換させ、繰り返す。
【００６６】
典型的には、パターンp(x,y)はステップ（ａ）の前に記憶装置に格納され、ステップ（i）の各繰り返しは記憶装置から読みこまれたパターンp(x,y)の異なる行上で実行され、ステップ（ｂ）は、(ｋ1×ｐ)Tの各列が、以前p(x,y)の対応する列によって占められた記憶装置位置を占めるそのようにメモリで格納する(k1×p)Tのステップを含む。
【００６７】
算法のいくつかの変法は、その速度を増加させるために行うことができる。例えば、全ての場合において、算法は好ましくは各々の消滅された畳み込みを計算し、同時にそれを膨張させるようにプログラムされた処理装置によって行われることが好ましい。このように、それが平滑化する前に、消滅された畳み込みを格納する必要はない。また、ｋ＋とｋcの双方が、処理装置の同じ通過について計算されることが好ましい。また、行を渡る技術がキャップと正の減衰領域畳み込みと、行の戻り、負の畳み込みを計算するために用いられ、加算がすべて同じループ部分であるべきである場合に、二つの完全な置換が典型的には必要ない。また、算法を行うためにいくつかの種類のプロセッサーを用いるとき、適した演算が最も速いと思われる。
【００６８】
ラプラス減衰がｅ-xであり、ガウスがｅ-x2であるので、ガウスへの近似として、本発明の畳み込みの上記実施形態がパターンのサイズに左右されることに留意すること。したがって、エラーはドメインのサイズに左右される。
実施例２：平方コサイン分離カーネル
我々は、次に他の分離スプラインのカーネル（“平方コサイン”分離カーネル）と、平方コサインを用いる本発明の畳み込み方法の具体形態を示す。平方コサイン分離カーネルを用いる畳み込みは、パターンの次元に依存しないので、上記 “ラプラス減衰を用いた二次式”カーネルを用いた畳み込みより、より速く、よりクリーンである。平方コサインカーネルは、また一つの通過において一連の列の畳み込みについて主に適した方法と、渡る技術を可能にさせ、計算は転移で行われる。平方コサインカーネルはより不変であるので、浮動小数点演算を用い得る。多項式であることから、誤差が多項式のように無秩序になるということは言えることであり、平方コサインカーネルについては、小さな誤差が小さな振動雑音になる。パターンがある意味で“規則正しい”場合、雑音が精度のいくつか（非常に小さな）のレベルに対して重要でないと考えられる。我々は一次元の平方コサインカーネルを次のように定義する：
|x|≦Rに対して、k2(x)＝２cos2(πx/2R)
|x|>Rに対して、k2(x)＝０
二次元のカーネルは次のように定義される：
k(x,y)＝k2(x)k2(y)                                            （２）
以前のように、二つのカーネルの合計としてカーネルk2(x)が書かれる。これらの最初は次のとおり：
|x|≦Rに対して、kc(x)＝2cos(πx/R)
|x|>Rに対して、kc(x)＝０
である。
【００６９】
その他のカーネルは、
|x|≦Rに対して、ｋi(ｘ)＝１
|x|>Rに対して、ｋi(ｘ)＝０
である。
【００７０】
これらの二つのカーネルについて、k2(x)＝kc(x)+ki(x)であると言える。カーネルｋｉは、我々が概念の連続に対してAiと呼ぶ不連続の導関数によって容易に消滅する。この消滅演算子の陽関数表示の定義は、
Aif(x)＝f(x＋1)-f(x)
である。
【００７１】
コサインを消滅すると、ｋcは簡単ではなくなるが、
cos(π(x＋1)/L)＋cos(π(x−１)/L＝２(cosπｘ/L)(cosπ/L)
に注目するならば、我々が
Acf(x)＝f(x＋１)＋f(x−１)−2(cosπ/L)f(x)
次によって演算子Acを定義する場合には、ｋcがAcによって消滅されることは明らかである。我々が用いる消滅演算子Aはこれら二つの演算子の“積”である。
Af(x)＝Ac○Aif(x)＝f(x＋２)−(１＋２cosπ/L)(f(x＋１)−f(x））−f(x−１)
Aiだけが消滅したものに作用するAk2＝Ai×Ack2であるので、Aは、ｋ2を消滅するように見え、同じことがAkiに対しても言える。計算は、次のようにAkのゼロでない値が
Ak2(-R−１)＝２sin2(π/２L)
Ak2(-R)＝２sin2(π/２L)
Ak2(R−１)＝−２sin2(π/２L)
Ak2(R)＝−２sin2(π/２L)
我々は、発明に従ってr(x,y)を計算するために、パターンp(x,y)を用いて上記の平方コサインカーネル
k2(x)k2(y)＝(kc(x)＋ki(x)(kc(y)＋ki(y)）
によって決定されたk(x,y)の畳み込みについての算法を次に示す。上で定義された“ラプラス減衰を用いた二次”カーネルを用いる畳み込みについて上記算法にこれは非常に似ている。“平方コサイン分離スプライン畳み込みについての算法”と呼ばれる算法は次のとおりである。
【００７２】
（ａ）列の上にループする。パターンp(x,y)の各列について、k2(x)を用いて前述の列の畳み込みを計算する。これは、
（i）-R−３  ≦  x   ≦  ｎ−１の場合、前記列に対するAk2(x)×p(x)＝２sin2(π/2L)の値を次のように：Ak2(x)×p(x)＝２sin2(π/２L)(p(x)+R)＋p(x＋R＋１)-(p(x−R)−p(x−R＋１))計算するステップと、
（ii）繰り返し関係r(x＋２)＝Ar(x)＋(１＋２cosπ/L)(r(x＋１)−r(x))＋r(x−1)によって、列に対するr(x)を見つけるために繰り返し演算を点火するr(-R−４)＝r(-R−３)＝r(-R−２)＝０を用い、それによってｋ2×pを表示するデータであるステップ（ii）の最後の繰り返しの終わり得るステップと、
を含む一次元スプライン畳み込みによって行われる。
【００７３】
（ｂ）(ｋ2×ｐ)Ｔをつくるためにｋ2×ｐを置換する。
【００７４】
（ｃ）ステップ（ａ）をこのときｐ(ｘ,ｙ)の列についてではなく(ｋ2×ｐ)Ｔの列について繰り返し、それによってｋ2を用いてｋ2×ｐの全ての行を畳み込む。
【００７５】
好ましくは、ステップ（ｃ）の結果を置換する最終ステップはｒ(ｘ,ｙ)を得るために行われ、処理装置はそれから初期状態に戻る。
【００７６】
典型的には、パターンｐ(ｘ,ｙ)はステップ（ａ）の前に記憶装置に格納され、ステップ（ｉ）の各々の繰り返しは記憶装置から読まれたパターンｐ(ｘ,ｙ)の異なる列について行われ、ステップ（ｂ）は、(ｋ2×ｐ)Ｔの各列が以前にｐ(ｘ,ｙ)の対応する列によって占められた記憶装置の位置を占めるように記憶装置に(ｋ2×ｐ)Ｔを格納するステップを含む。
【００７７】
記載された算法の単純な計算総数は以下のとおりである：ｈが高さである場合、ステップ（ａ）のｈ反復があり；Akの計算には一回の乗算と三回の加算が含まれ、ｗ＋Ｒ＋３回（ｗは幅である）行われ；繰り返しは一回の乗算と四回の加算を必要とし、ｗ＋Ｒ＋３回（ｗは幅である）行われる。したがって、平方
【００７８】
【数１１】
2005517999.tif 000012
×
【００７９】
【数１２】
2005517999.tif 000013
アレイに関する全アルゴリズムは次を必要とする。
【００８０】
【数１３】
2005517999.tif 000014
が掛けられ、
【００８１】
【数１４】
2005517999.tif 000015
を加える。これは２、３の方法で最適化することができる。まず、最終段階において標準化することができ、Ak×pをp(x＋R)＋p(x＋R＋1)−(p(x-R)-p(x-R＋1))として計算させることができる。これは
【００８２】
【数１５】
2005517999.tif 000016
が乗ずることを保存し、著しく計算上のコストを縮小する。第２に、乗算の全てが同様の２つの定数によるものであり、その結果、最適にハードコード化することができる。第３は最も重要なことに、この方法は列に関して独立して作業するので、とても容易に並行にさせることができ、またベクトル化させることができることである。加算の数も縮小させることができるが、これは一般にほとんど計算時間に影響しない。
【００８３】
好適実施形態においては、より一般に、分離スプラインカーネルによってｄが十分に近似される（または等しい）場合、畳み込みｒ＝Ｄｐ＝ｄ×ｐ（×は畳み込みを意味する）を行う本発明の方法は、
（ａ）分離スプラインカーネルをk(x1,…,xn)＝k1(x1)k2(x2)…kn(xn)、ここで、ｋは演算子A＝A1A2…Anであることを容認し、ＡjＫj＝Ｂjがまばら（Ａjが消滅演算子である時）であり、またはAjKj＝Bjがほぼどこでも局所定数行列（Ａjが平滑化演算子である時）であり、ｎがパターンｐの次元であるような方法でカーネルｋjの循環Kjに関してAjが消滅演算しまたは平滑化演算子である、として指定するステップと、
（ｂ）パターンｐの各列に対するｑ1＝Ｂ1ｐ＝Ａ1ｋ1×ｐを計算するステップと
（ｃ）ｒ1のコンポーネントの少数を直接計算し、次に演算子A1によって決定される自然繰り返し関係を用いてr1のコンポーネントの残りを決定する予備的点火ステップを行うことにより、前記パターンに対するｒ1＝ｋ1×ｐを決定するために前記パターンの各列に対するA1ｒ１＝ｑ1を後方計算するステップと、
（ｄ）パターンに対するｒ1T＝(ｋ1×ｐ)Tを生成するために、ステップ（ｃ）で生成されるｒ1＝ｋ1×ｐを置換し、(ｋ1×ｐ)Tの各列に対するｑ2＝Ｂ2ｒ1T＝Ａ2ｋ2×(ｋ1×ｐ)Tを計算するステップと、
（ｅ）パターンに対するｒ2T＝（ｋ2×ｋ1×ｐ）Tを決定するために(ｋ1×ｐ)Tの上記各列に対するＡ2ｒT＝ｑ2を後方計算するステップと、
を含んでいる。
【００８４】
パターンｐが二次元（ｎ＝２）である場合には、ステップ（ｅ）の結果はｒ＝（ｋ2×ｋ1×ｐ）を示すデータを生成するために一般的には変換され、結果ｒは所望の畳み込みＤｐに近い近似値になる。ｎ>２である場合、ステップ（ｄ）と（ｅ）は（上記要約において定義されたような置換演算により）パターンｐの個々の追加の次元で繰り返され、ステップ（ｅ）の最終繰り返しの結果の置換が、所望の畳み込みＤｐにかなり近い近似値となる（またはまさに等しい）。
【００８５】
ステップ（ｃ）のいくつかの実施形態においては、ｒ1の少数の最小コンポーネントは、予備的点火ステップの間に直接計算され、次にｒ1のコンポーネントの残りは自然繰り返し関係を用いて決定される。ステップ（ｃ）の好適実施形態においては、ｒ1の少数の大きい負のコンポーネントは、予備的点火ステップの間に直接計算され、次にｒ1のコンポーネントの残りは自然繰り返し関係を用いて決定される。
【００８６】
カーネルｄそれ自体が分離スプラインカーネル（その結果ｄ＝ｋ、Ｋ＝Ｄである）の場合、該方法は正確な結果（ｒ＝Ｄｐ）を与える。そうでなければ、該方法に固有の誤差は（ｋ−ｄ）×ｐであるので、その誤差は容易に制限される。
【００８７】
次のものは、本発明の畳み込みに分離スプライン法を行う機能のワーキングソースコード（Ｃ言語における）の実施例である。実施例において指定されたカーネルは、上記平方コサインカーネルである。この関数は、入力パターン（*Pattern）、出力アレイ（*Result）、一次元のワーキングバッファ（*r）にポインタを送ることによって呼び出される。グローバル変数はアレイサイズであり、ＮＸ×ＮＹ、Ｎ＝最大（ＮＸ,ＮＹ）である。このコードは、いくつかの論理的な条項を有する最小の記憶装置で使うために最適化されている。これに対する下降は、算法の容易さが最初に容易に見えないということである。ほとんどのコードはラインのある変化であることに留意すること。
ｒ[x+1]＝c2*r[x]−r[x＋１]＋ｓ；
ｓ＋＝s2*(q[ｘ＋Ｌ］＋q[x＋Ｌ＋１]-q[ｘ−Ｌ]-q[ｘ−Ｌ＋１］）；
その結果、実際の算法は概念的に非常にコンパクトである。
実施例：平方コサイン分散スプライン畳み込みの実施形態に関するＣソースコード
ボイド
クロスライン畳み込み（フロート*パターン，フロート*リザルト，フロート*r）｛
Int  x,y；
フロート*q  ，*Resultptr, s；
フロートc＝(フロート)cos(PI/L)，c2＝2*c，s2＝1，max, norm；
但し、(y＝0；y<NY；y++)｛/*Xディレクションコンンボリューション*/
r[-L-5]＝r[-L-4]＝０；
ｓ＝０；
ｑ＝&パターン[N*y]；
Resultptr＝&リザルト[N*y]；
ｘ＝−L-4；
r[x+1]＝c2*r[x]−r[x-1]+s；
s+＝0；
x＝-L-3；
r[x+1]＝c2*r[x]-r[x-1]+s；
s+＝0；
x＝-L-2；
r[x+1]＝c2*r[x]−r[x-1]+s；
s+＝0；
x＝-L-1；
r[x+1]＝c2*r[x]−r[x-1]+s；
s+＝s2*q[x+L+1]；
(x＝-L；x<0；++x){
r[x+1]＝c2*r[x]−r[x-1]+s；
ｓ＋＝ｓ２＊（ｑ［ｘ＋Ｌ］＋ｑ［Ｘ＋Ｌ＋１］）；
｝
但し、（x＝0；x＜L−1；＋＋ｘ）｛
r[ｘ＋１]＝c2*r[x]−r[ｘ−１]＋ｓ；
ｓ＋＝s2*(q[ｘ＋Ｌ］＋q[Ｘ＋Ｌ＋１］）；
｝
ｘ＝Ｌ−１；
r[ｘ＋１]＝c2*r[ｘ］−r[ｘ−１]＋ｓ；
ｓ＋＝s2*(q[ｘ＋Ｌ]＋q[ｘ＋Ｌ＋１]−ｑ[ｘ−Ｌ＋１］）；
但し、(x＝Ｌ；ｘ＜ＮＸ−Ｌ−１；ｘ＋＋）｛
r[ｘ＋１]＝c2*r[ｘ]−r[ｘ−１]＋ｓ；
ｓ＋＝s2*(q[ｘ＋Ｌ]＋q[ｘ＋Ｌ＋１]−q[ｘ−Ｌ]−q[ｘ−Ｌ＋１］）；
｝
ｘ＝ＮＸ−Ｌ−１；
r[ｘ＋１]＝c2*r[ｘ]−r[ｘ−１]＋ｓ；
ｓ＋＝s2*(q[ｘ＋Ｌ]−q[ｘ−Ｌ]−q[ｘ−Ｌ＋１］）；
但し、（ｘ＝ＮＸ−Ｌ；ｘ＜ＮＸ−１；Ｘ＋＋）｛
r[ｘ＋１]＝c2*r[ｘ]−r[ｘ−１]＋ｓ；
ｓ−＝s2*(q[ｘ−Ｌ]＋ｑ[ｘ−Ｌ＋１］）；//ノート−＝
｝
但し、(x＝0；ｘ＜ＮＸ；ｘ＋＋）
Resultptr[ｘ］＝ｒ［ｘ］；
｝
但し、(x＝０；ｘ＜ＮＸ；ｘ＋＋）｛／＊Ｙディレクションコンボリューション*/
r[−Ｌ−５]＝r{−Ｌ−４}＝０；
ｓ＝０；
ｑ＝＆リザルト[ｘ］；
Resultptr＝＆リザルト[ｘ］；
ｙ＝−Ｌ−４；
r[ｙ＋１]＝c2*r[ｙ]−[ｙ−１]＋ｓ；
ｓ＋＝０；
ｙ＝−Ｌ−３；
r[ｘ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝０；
ｙ＝−Ｌ−２；
r[ｙ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝０；
ｙ＝−Ｌ−１；
r[ｙ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝q[N*(ｙ＋Ｌ＋１）］；
但し、(ｙ＝−Ｌ；ｙ＜０；＋＋ｙ）｛
r[ｙ＋１］＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝(q[N*(ｙ＋Ｌ)]＋q[N*(ｙ＋Ｌ＋１）］；
｝
但し、(ｙ＝０；ｙ＜Ｌ−１；＋＋ｙ）｛
r[ｙ＋１］＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝(ｑ[N*(Ｙ＋１)]＋q[N*(ｙ＋Ｌ＋１）］；
｝
ｙ＝Ｌ−１；
r[ｙ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝(q[N*(ｙ＋Ｌ)]＋q[N*ｙ＋Ｌ＋１)])−q[N*(ｙ−Ｌ＋１）］；
但し、（ｙ＝Ｌ；ｙ＜ＮＹ−Ｌ−１；ｙ＋＋）｛
r[ｙ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝(q[N*(ｙ＋１)]＋q[N*(ｙ＋Ｌ＋１)]−q[N*(ｙ−Ｌ)]−q[N*(ｙ−Ｌ＋１）］；
｝
ｙ＝ＮＹ−Ｌ−１；
r[ｙ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
ｓ＋＝(q[N*(ｙ＋Ｌ)]−q[N*(ｙ−Ｌ)]−q[N*(ｙ−Ｌ＋１）］；
但し、(ｙ＝ＮＹ−Ｌ；ｙ＜ＮＹ−１；ｙ＋＋){
r[ｙ＋１]＝c2*r[ｙ]−r[ｙ−１]＋ｓ；
Ｓ−＝(q[N*(ｙ−Ｌ)]＋q[N*(ｙ−Ｌ＋１）］）；//ノート＝
｝
但し(ｙ＝０；ｙ＜ＮＹ；ｙ＋＋）
Resultptr[N*y]＝r[ｙ]；
｝
発明の方法の、いくつかの二次元の実行においては、不連続畳み込みが、行列形式を用いて行われ、それにより辞書編集インデキシングを用いて、二次元のピクセル長方形は一次元の列ベクトルに変換される。この場合、循環行列ＦはＮＮ’ごとの異常になるが、消滅演算子Ａが適用される時、演算子ＡＦはまばらになる。本発明の実施形態のこの種類は、消滅しない循環的な領域を決定論的に指数化された行列要素に変換するという利点がある。
【００８８】
図１は発明を具体化するコンピュータシステムのブロックダイヤグラムである。システムは（発明の畳み込み方法の全ての実施形態を実行するソフトウェアでプログラムされる）処理装置２、ディスプレイデバイス４、入力デバイス６、処理装置２と接続された記憶装置８（任意に出力デバイス５も）を含む。処理装置２が２進法のデータを処理するために形成された典型的な処理装置である場合、それは発明の方法の“不連続”実行を行うためにソフトウェアでプログラムされる。一般的に、メモリ８は、畳み込みカーネルｄの循環Ｄを示すデータ、スプラインカーネルｋ(ｘ1，ｘ2，...ｘn）＝ｋ1(ｘ1)ｋ1(ｘ2））...ｋn(ｘn）の因数カーネルｋ１の循環Ｋ1、畳み込まれるためのパターンｐ、方法の実行中生成される中間量、畳み込みから起因する畳み込まれた信号ｒ＝Ｋｐを示すデータを格納する。いくつかの実施形態において、処理装置２が、スプラインカーネルに畳み込みカーネルｄ（ユーザ指定束縛を受ける）に近似させる、スプラインカーネルｋの特定のパラメータを決定するように（問題のユーザ指定畳み込みカーネルｄから）プログラムされる。いくつかの実施形態においては、処理装置２は一つ以上のルックアップテーブルを生成し、記憶装置８（または処理装置２に関連したキャッシュメモリ）にそれらを格納し、発明の実行中に格納されたルックアップテーブルにアクセスする。ユーザは入力デバイス６を使用して、処理装置２（処理パラメータまたは束縛を指定することにより含む）を制御する。処理装置２（畳み込まれる二次元パターンｐと発明に従って生成される畳み込み結果Ｋｐの表現のような）によって生成されたテキストとイメージは、ディスプレイデバイス４に表示される。出力デバイス５（ディスプレイデバイス４の代わりにまたはそのディスプレイデバイス４に加えて使用することができる）は、好ましくは音声再生ユニット、Ｉ／Ｏポート（入力／出力）または信号処理（または記憶装置）デバイス(またはシステム)のようなパターン対応のデバイスである。
【００８９】
図２は、メモリユニット１４に格納されたイメージデータ上で畳み込み（本発明）を実行するために形成されるデジタル信号処理装置（“ＤＳＰ”）１０を含むリソグラフィ・システムのブロック図である。メモリユニット１４に格納されたイメージデータは、畳み込ませるためパターンｐを決定する。ＤＳＰ１０は、畳み込み結果ｒ＝Ｋｐを示す出力データを生成するためにイメージデータを処理する。出力データはメモリ１４（場合によっては更に処理を受ける）に格納されおよび／または“パターン信号”生成デバイス１６に出力される。装置１６は、ＤＳＰ１０から受け取るデータに応じてパターン信号（例えば、時間によって変化する振幅を持つ光学または他の電磁放射ビームまたは時間によって変化する振幅を持つ電子ビーム）を生成する。
【００９０】
実施形態の種別において、デバイス１６は、光学１８をリソグラフィターゲット２０上に出力ビームを投影させるために光学部品１８に投射する光学放射ビームを出す。制御ユニット１２からのスキャン制御信号に応じて、リソグラフィターゲット２０を横切る出力ビームをスキャンする。デバイス１６から出されたビームの振幅は、走査された出力ビーム（光学１８の出力）がピクセルのパターンにおけるターゲット２０を露光する方法において、時間（ユニット１２からのスキャン制御信号によって決定された走査パターンと仮定する、ＤＳＰ１０からの出力データに応じて）の関数として変化する。
【００９１】
他の実施形態においては、デバイス１６は、リソグラフィターゲット２０上に光学１８に出力電子ビームを投影させるために光学１８に投射する電子ビームを放射する。光学１８は、制御ユニット１２からのスキャン制御信号に応じて、ターゲットを横切る出力電子ビームをスキャンする。デバイス１６から放射された電子ビームの振幅は、光学１８からの走査された出力ビームがピクセルのパターンにおけるターゲット２０を露光する方法において、時間（ユニット１２からのスキャン制御信号によって決定された走査パターンと仮定する、ＤＳＰ１０からの出力データに応じて）の関数として変化する。
【００９２】
または、デバイス１６はターゲット２０に、パターンを決定する上述のイメージであるピクセルを含むイメージを投影するために光学部品１８によって焦点を合わせる（走査されないで）放射線を出すことができる。例えば、デバイス１６の一実施形態は、ターゲット２０を横切ってどんなビームも走査するために光学部品１８を必要とせずにターゲット２０上のパターンとして光学１８から投影するように光学部品１８によって焦点を合わせる光放射線を出す。
【００９３】
我々は、そのようなパターン信号の例が光学部品１８によって走査される光学ビームまたは他の放射線ビーム、光学１８によって走査される電子ビーム、焦点を合わせるが光学部品１８によって走査されない放射線を含むことを認識して、デバイス１６の出力を“パターン信号”と呼ぶ。光学部品１８は、一連の反射および／または屈折光学（ターゲット２０を横切ってビームを走査するために光学の１つ以上の要素を移動させるための手段を含む走査能力をもつ又はもたない）であってもよく、一連の電子ビーム光学部品（ターゲット２０を横切って電子ビームを走査するためにその1つ以上の要素を移動させるための手段を含む走査能力をもつ）であってもよい。光学１８の出力はリソグラフィターゲット２０上のパターンとして（例えば、走査されていることを含む）投影される。
【００９４】
典型的には、ターゲット２０は（パターンの投影は集積回路製造において有用なマスクをその上に作るので）ガラスプレートあるいは半導体ウエハである。非常に小さなパターンがターゲット２０に投影されるように、光学部品１８は典型的にはパターン信号を集中させる。
【００９５】
デバイス１６から出力される“列”パターン信号はパターンを決定するが、光学部品１８（またはイメージングビームとターゲット２０間の相互作用に固有の）によって導入された回析人工物（あるいは他の人工物）は、ターゲット上で実際に作ったパターンがこのパターンと異なってもよい。例えば、デバイス１６からの“生の”パターン信号出力は、シーケンスの個々の単一ピクセル上に焦点を合わせた電子ビームに依存する振幅によって決定されたパターン投影をするために、電子ビーム光学部品１８によって焦点を合わせるとともにターゲット上のピクセルのシーケンス上に走査する電子ビームである場合と考える。この場合、周知の“近接問題”（上で述べた）は、焦点を合わせた電子ビームが入射する（電子を各々のピクセルからターゲットの周囲の領域に分散することによる）各ピクセルを囲む領域をさらすことを引き起こす。その結果、焦点を合わせた電子ビームがシーケンスのピクセルの１つに入射する各々の時間多重ピクセル領域がさらされる場合、ターゲット２０上に実際に得られたパターンは、シーケンスの各ピクセルに焦点を合わせた電子ビームを送ることの結果の重ね合せによって決定される。
【００９６】
したがって、ＤＳＰ１０はターゲット２０上の所望のパターンを作るために必要とされる特性をもつ“生の”パターン信号をデバイス１６に出力させる、出力データを生成するために形成される。これを達成するために、ＤＳＰ１０は光学部品１８によって導入されると予想される任意の人工物、および／または光学部品１８からターゲット２０上に入射する電子ビームの任意の予想された散乱（ターゲット２０による）を補償するために、ピクセル（記憶装置１４に格納されたイメージデータ）の大きなアレイ上で脱畳み込み演算を行う。イメージデータがパターン“ｐ”を決定するピクセルの非常に大きな配列を決定する場合、ＤＳＰ１０によって行われる脱畳み込み演算は、記憶装置１４から検索する格納されたイメージデータについての畳み込み演算（発明に従って実行された）を含んでいる。したがって畳み込み結果ｒ＝Ｋｐを示すデータを生成するために、ＤＳＰ１０は本発明に従ってイメージデータを処理する。次に、後者のデータはデバイス１６に主張されるか、またはデバイス１６に主張する前に更に処理される。
【００９７】
図２のシステムのコントローラ１２はユニット１０、１４、１６、１８に適切な制御信号を供給し、（例えば）指定されたパラメータを用いて畳み込み演算を実行させるＤＳＰ１０への命令をダウンロードすることができる。
【００９８】
図３は図２のＤＳＰ１０として使用することができ、かつイメージデータについて発明に従って畳み込みを行うために構成されたデジタル信号処理装置（ＤＳＰ）のブロック図である。図３のＤＳＰは、（畳み込みを実行ために必要とされる行列乗算と繰り返し関係演算のための）加算と乗算回路を含む演算計算ユニット（ＡＣＵ）３４、（畳み込み演算を実行するためにＤＳＰによって実行される命令を格納する）プログラムメモリ３０、プログラム制御ユニット（ＰＣＵ）３２、メモリ管理ユニット３６、またデータメモリ３８を含み、図に示されているように接続されている。ユーザからのコマンドに応じて、図２のコントローラ１２はメモリ３０に適切な命令をロードし、パターンｐ（図３において“ＩＮＰＵＴ”と標識されたデータ）を示すデータは、記憶装置３８にロードされる。
【００９９】
ＰＣＵ３２は、回路を解読する命令である、プログラム記憶装置３０から命令のシーケンスを取り出すために命令フェッチ回路を含み、ユニット３６および／またはユニット３４への適切な時に表明用回路を解読することによって生成されたコントロールビットを格納することを記録する。
【０１００】
メモリ管理ユニット３６は、ＰＣＵ３２からのコントロールビットに応じてアドレス信号（データを書くために、またはデータを読むために記憶装置３８におけるメモリ位置を各々確認する）を生成し、かつ記憶装置３８へのアドレスバス上のそのようなアドレス信号を表明するように構成される。したがって、ＰＣＵ３２（プログラム記憶装置３０からの命令の解読によりＰＣＵ３２の中で生成された）からのコントロールビットに応じて、ユニット３６は、データ記憶装置３８へのアドレス信号を表明する。
【０１０１】
メモリ管理ユニット３６によるアドレスに応じて、データ記憶装置３８はＡＣＵ３４（データバス上）にデータを示す信号を送る。部分的に処理されたデータ、またはｒ＝ｋ×ｐという最終畳み込み結果を表示するＡＣＵ３４から生じる出力信号は、記憶装置３８へのユニット３６によって主張されたアドレスによって決定された記憶装置３８の位置に格納する記憶装置３８へのデータバス上に伝達することができる。いくつかの実施形態においては、記憶装置３８はＤＳＰのためのＩ／Ｏバッファーとしての機能があり、最終畳み込み結果を表示するデータは、記憶装置３８（出力データ“ＯＵＴＰＵＴ１”として）からパターン信号発生器１６に出力される。他の実施形態においては、最終畳み込み結果を表示するデータは、ＡＣＵ３４（出力データ“ＯＵＴＰＵＴ２”として）からパターン信号発生器１６に直接（またはバッファを通って）流れる。
【０１０２】
図４は図２のシステムについての変更であり、ここで、要素１６、１８、２０は、図２の同一番号が付けられた要素と同じである。図４の実施形態においては、要素４６はメモリユニット４４から受け取るイメージデータ（畳み込まれるべきパターンｐを決定する)について畳み込み（発明の任意の実施形態にしたがって）を実行するために形成される。要素４６（発明の方法の任意の実施形態に従ってデータについて畳み込みを行うために構成されたデジタル信号処理回路、または発明の方法の任意の実施形態に従ってデータについて畳み込みを行うために構成された特定の電子回路、または本発明の方法の任意の実施形態に従ってデータについて畳み込みを行うために構成されたプログラム可能なゲートアレイに基づいた計算システムを含むデジタル信号処理装置であり得る）は、畳み込み結果ｒ＝Ｋｐを表示する出力データを生成するためにイメージデータを処理する。出力データは、ＤＳＰからパターン信号生成デバイス１６まで直接流れ、デバイス１６は要素４６からの出力データに応じてパターン信号を生成する。図４システムの制御器４２は、要素４４、４６、１６、１８に適切な制御信号を供給し、（例えば）指定されたパラメータを用いて畳み込み演算を要素４６に実行させるために要素４６への命令をダウンロードすることができる。
【０１０３】
図３のＤＳＰは、本発明の方法のいずれの実施形態を実行し得ることが考慮される。畳み込み演算の終わりに、畳み込み結果ｒ＝Ｋｐを表示する処理されたデータは生成されている。このデータは、デバイス１６に直接流すことができ、更に（例えば、ユニット３４において）処理され、その後デバイス１６あるいは記憶装置１４に表明されることができる。
【０１０４】
畳み込みカーネル（“ｄ”）が、次の意味で、分離スプラインカーネル（“ｋ”）によって十分に近似されるように十分に平滑であるならば、本発明の方法はいずれの畳み込み（ｒ＝ｄ×ｐ）も実行することができる。本方法（（ｋ−ｄ）×ｐである）に固有の誤差が、許容範囲内である場合、分離スプラインカーネル“ｋ”によってカーネル“ｄ”は十分に近似される。一般的には、電子ビームリソグラフィ近接誤差訂正の分野で用いられる畳み込みカーネル“ｄ”は、分離スプラインカーネル“ｋ”が十分近似されるように十分に平滑である。クリプトグラフィに直面されるもののように、雑音（ランダム）である畳み込みカーネルは分離スプラインカーネル“ｋ”によって十分に近似されるように典型的には十分に平滑ではない。
【０１０５】
図５は、コンピュータ実行可能な命令（ソフトウェア）を格納するコンピュータ読み取り可能な記憶媒体５０(ＣＤ−ＲＯＭである)の簡易正面図である。その命令は命令の実行に応じて、コンピュータが本発明の方法の実施形態を行うようなものである。
【０１０６】
発明は特定の好適実施形態とともに記載してきたが、特許請求した本発明がそのような特定の実施形態に過度に制限されるべきでないことは理解されるべきである。例えば、いくつかの実施形態においては、本発明は、ソフトウェア中もしくはデジタル信号プロセッサ（“ＤＳＰ”）を含むシステムによってではなく、ハードワイヤード回路（例えば、カスタムまたは特定の電子回路）またはＦＰＧＡシステム（システム計算に基づいたフィールドプログラム可能なゲートアレイ）によって実行されることが考慮されている。
【図面の簡単な説明】
【０１０７】
【図１】発明の方法を実行するためのソフトウェアでプログラムされたコンピュータシステムのブロック図である。
【図２】イメージデータについて畳み込み（本発明）を行うように構成されたデジタル信号処理装置、畳み込まれたイメージデータの結果からパターン信号（例えば、時間を変わる振幅が時間で変動する光学ビームの電子ビーム）を生成するデバイスを含むリソグラフィ・システムのブロック図である。パターン信号は、一連の光学（例えば、反射または屈折光学、または電子ビーム光学）に供給され、光学の出力はパターンとしてグラスプレート上に投影され、従って、集積回路製造において有用なマスクを生産する。
【図３】イメージデータについて畳み込み（本発明）を行うように構成されたデジタル信号処理装置（図２のデジタル信号処理装置として使用しうる）のブロック図である。
【図４】図２のシステム上の変化があるリソグラフィ・システムのブロック図である。
【図５】コンピュータ実行可能な命令を格納するコンピュータ読み取り可能な記憶媒体（ＣＤ−ＲＯＭ）の簡易立面図であり、ここで、命令は命令の実行に応じて、コンピュータが発明の方法の実施形態を実行するようなものである。
【符号の説明】
【０１０８】
５０…コンピュータ読み取り可能な記憶媒体
【図１】
2005517999.tif 000017
【図２】
2005517999.tif 000018
【図３】
2005517999.tif 000019
【図４】
2005517999.tif 000020
【図５】
2005517999.tif 000021