以下、発明の実施形態を通じて本発明を� ��明するが、以下の実施形態は請求の範囲に� ��る発明を限定するものではなく、また実施� ��態の中で説明されている特徴の組み合わせ� ��全てが発明の解決手段に必須であるとは限� ��ない。

 図1は、半導体メモリ等のメモリ40を試験� ��るメモリ試験装置10、およびメモリ40のフェ イルビットを救済するメモリ救済装置20の一� ��を示す図である。メモリ試験装置10は、試� �対象のメモリ40の各記憶セルが、正常に動作 するか否かを試験する。メモリ試験装置10は� ��メモリ40の各記憶セルがフェイルビットで� �るか否かを示すフェイルデータを、ライン� �済装置20に入力してよい。メモリ40は、例え� ��2次元のマトリクス状に記憶セルが配置され た半導体メモリであってよい。また、メモリ 40には、記憶セルのマトリクスにおける行方� ��または列方向のアドレスラインに対して、� ��れぞれ所定の数の予備ラインが予め設けら� ��る。

 メモリ救済装置20は、予備ライン割当装� �100および設定部30を備える。予備ライン割当 装置100は、メモリ試験装置10からメモリ40の� �ェイルデータを受け取る。また、予備ライ� �割当装置100は、当該フェイルデータに基づ� �て、メモリ40においてフェイルビットを有す る行方向のアドレスライン(行方向のフェイ� �ライン)及び列方向のアドレスライン(列方向 のフェイルライン)のうち、いずれのフェイ� �ラインに予備ラインを割り当てるかを決定� �る。ここで、フェイルラインとは、行方向� �よび列方向のアドレスラインのうち、フェ� �ルビットを有するアドレスラインを指して� �い。設定部30は、予備ライン割当装置100が決 定した予備ラインの割当てを、メモリ40に設� ��する。例えば設定部30は、当該予備ライン� �割当てに応じて、メモリ40内の配線をレーザ 等により溶断することで、当該割当てをメモ リ40に設定してよい。このような処理により� ��フェイルビットを救済したメモリ40を製造� �ることができる。

 図2は、予備ライン割当装置100の構成の一 例を示す図である。予備ライン割当装置100は 、ビット計数部110、重み算出部120、および割 当部130を有する。ビット計数部110は、メモリ 試験装置10からメモリ40のフェイルデータを� �け取る。

 図3は、メモリ40のフェイルデータの一例� ��示す図である。ビット計数部110は、図3に示 すような、フェイルデータのビットマップを 受け取ってよい。ビット計数部110は、当該ビ ットマップを格納するビットマップメモリを 有してよい。なお図3においては、行方向お� �び列方向に、10ラインずつのアドレスライン を有するメモリ40を一例として説明する。ま� ��図3において、行方向および列方向のアドレ スラインが交差する点が、それぞれ1ビット� �記憶セルに対応する。また、本例のメモリ40 におけるフェイルビットをX印で示す。本例� �は、(行アドレス、列アドレス)=(1、1)、(1、3) 、(1、5)、(1、9)、(2、1)、(3、2)、(3、4)、(3、7) 、(5、3)、(6、4)、(8、4)の各ビットが、フェイ ルビットである。

 ビット計数部110は、それぞれのフェイル� ��イン(行方向のアドレスライン1、2、3、5、6� ��8、および列方向のアドレスライン1、2、3、 4、5、7、9)に含まれるそれぞれのフェイルビ� ��トについて、当該フェイルビットを含み、� ��つ当該フェイルラインとは異なる方向のフ� ��イルラインが有するフェイルビットの個数� ��、直交フェイルビット数として計数する。� ��えば、フェイルビット(n,m)の行アドレスラ� �ンnにおける直交フェイルビット数は、フェ� ��ルビット(n,m)を含み、且つ行アドレスライ� �nと直交する列アドレスラインmが有するフェ イルビット数である(ただし、n,mは整数)。ま� ��、フェイルビット(n,m)の列アドレスラインm� ��おける直交フェイルビット数は、フェイル� ��ット(n,m)を含み、且つ列アドレスラインmと� ��交する行アドレスラインnが有するフェイル ビット数である。

 より具体的には、例えばフェイルビット( 1,1)の行アドレスライン1における直交フェイ� ��ビット数は、列アドレスライン1が有するフ ェイルビット数であるので、本例では"2"とな る。また、フェイルビット(1,1)の列アドレス� ��イン1における直交フェイルビット数は、行 アドレスライン1が有するフェイルビット数� �あるので、本例では"4"となる。

 ビット計数部110は、それぞれのフェイル� ��ット(n,m)について、行アドレスラインnにお� ��る直交フェイルビット数と、列アドレスラ� ��ンmにおける直交フェイルビット数とを計数 して、それぞれのフェイルビットごとに格納 する。ビット計数部110は、メモリ40の各ビッ� ��に対して、行アドレスラインにおける直交� ��ェイルビット数を格納する行ビット数レジ� ��タと、列アドレスラインにおける直交フェ� ��ルビット数を格納する列ビット数レジスタ� ��を、それぞれ有してよい。

 重み算出部120は、それぞれのフェイルラ� ��ンに含まれるフェイルビットの、当該フェ� ��ルラインにおける直交フェイルビット数に� ��づいて、それぞれのフェイルラインの重み� ��数を算出する。例えば重み算出部120は、当� ��フェイルラインにおける直交フェイルビッ� ��数がより大きいフェイルビットに対して、� ��り小さい係数を算出してよい。そして、そ� ��ぞれのフェイルラインが有するフェイルビ� ��トの係数の総和を、当該フェイルラインの� ��み係数として算出してよい。

 基本的には、含まれるフェイルビット数� ��より多いフェイルラインに対して、順次予� ��ラインを割り当てることにより、より多く� ��フェイルビットを救済することができる。� ��かし、メモリ40の各記憶セルは、メモリ40の 所定の面内に形成されるので、行アドレスラ インおよび列アドレスラインの双方に属する ように、2次元マトリクス状に形成すること� �好ましい。このため、各フェイルビットは� �行アドレスラインおよび列アドレスライン� �双方で救済することができる。このとき、� �つのフェイルビットが、行アドレスライン� �予備ライン、および列アドレスラインの予� �ラインの双方で救済されるように予備ライ� �を割り当てた場合、救済できるフェイルビ� �トの総数が減少してしまう。

 これに対し、予備ライン割当装置100は、� ��フェイルビットについて、行アドレスライ� ��および列アドレスラインにおける直交フェ� ��ルビット数を求めることにより、それぞれ� ��フェイルビットを行アドレスラインまたは� ��アドレスラインのいずれで救済すべきかを� ��す係数を取得することができる。そして、� ��フェイルラインが有するフェイルビットの� ��数の総和を求めることにより、予備ライン� ��割り当てるべきかを示す重み係数を、各フ� ��イルラインについて取得することができる� ��

 より具体的には、重み算出部120は、それ� ��れのフェイルラインが有するフェイルビッ� ��の、当該フェイルラインにおける直交フェ� ��ルビット数の逆数の総和に基づいて、当該� ��ェイルラインの重み係数を算出してよい。� ��えば、行アドレスライン1が有するフェイル ビット(1,1)、(1,3)、(1,5)、(1,9)の、行アドレス� ��イン1における直交フェイルビット数は、2� �2、1、1となる。重み算出部120は、行アドレ� �ライン1の重み係数として、これらの直交フ� ��イルビット数の逆数の総和、すなわち1/2+1/2 +1/1+1/1=3を算出してよい。重み係数算出部120� �、フェイルラインごとに重み係数を算出し� �格納してよい。重み係数算出部120は、アド� �スラインごとに設けられ、対応するアドレ� �ラインの重み係数を格納する重みレジスタ� �有してよい。

 割当部130は、重み算出部120が算出した重� ��係数の大小関係に基づいて、いずれのフェ� ��ルラインに予備ラインを割り当てるかを決� ��する。例えば割当部130は、重み係数がより� ��きいフェイルラインに予備ラインを割り当� ��てよい。例えば図3に示した例では、行アド レスライン1の重み係数が最も大きいので、� �当部130は、行アドレスライン1に、行方向の� ��備ラインを割り当ててよい。

 また、割当部130には、メモリ40に設けら� �た行方向および列方向の予備ラインのそれ� �れの本数が予め通知されてよい。例えば割� �部130には、使用者等により、予備ラインの� �数が予め通知される。割当部130は、通知さ� �た行方向および列方向の予備ラインの本数� �それぞれ格納する初期予備ライン数レジス� �を有してよい。また、割当部130は、いずれ� �のフェイルラインに予備ラインを割り当て� �場合に、該当する方向の予備ラインの本数� �減じることにより算出した、各方向の残存� �備ライン数を格納する残存予備ライン数レ� �スタを更に有してよい。割当部130は、残存� �備ライン数がゼロでないことを条件として� �当該方向の予備ラインを、フェイルライン� �割り当ててよい。

 図4は、予備ライン割当装置100における処 理の一例を説明する図である。図3において� �明したように、割当部130は、重み係数が最� �大きいフェイルライン(図3では、行アドレス ライン1)に、対応する方向の予備ラインを割� ��当てる。このとき、割当部130は、当該フェ� ��ルラインに予備ラインを割り当てた旨を、� ��ット計数部110に通知してよい。

 ビット計数部110は、予備ラインが割り当� ��られたフェイルラインに含まれるフェイル� ��ットを除外した場合の、それぞれのフェイ� ��ビットの行方向および列方向における直交� ��ェイルビット数を算出する。ビット計数部1 10は、予備ラインが割り当てられたフェイル� ��インに含まれるフェイルビットを除外した� ��合のフェイルデータのビットマップを格納� ��る更新ビットマップメモリを更に有してよ� ��。

 本例のビット計数部110は、図4に示すよう に、行アドレスライン1が有するフェイルビ� �トが救済されたものとして、それぞれのフ� �イルビットの直交フェイルビット数を再計� �する。ビット計数部110は、再計算した行方� �および列方向の直交フェイルビット数をそ� �ぞれのフェイルビットについて新たに格納� �る、行方向および列方向の再計算ビット数� �ジスタを更に有してよい。

 重み算出部120は、ビット計数部110が再計� ��して新たに格納した直交フェイルビット数� ��基づいて、予備ラインが割り当てられたフ� ��イルラインに含まれるフェイルビットを除� ��した場合の、それぞれのフェイルラインの� ��み係数を算出する。例えば、本例の行アド� ��スライン2の重み係数は、行アドレスライン 1のフェイルビットが救済されたことにより� �1/2から1に再計算される。重み算出部120は、� ��ェイルラインごとに重み係数を再計算して� ��納する。重み算出部120は、アドレスライン� ��とに設けられ、対応するアドレスラインに� ��して再計算された重み係数を格納する、更� ��重みレジスタを更に有してよい。

 割当部130は、重み算出部120が新たに格納� ��た重み係数に基づいて、次に予備ラインを� ��り当てるべきフェイルラインを選択する。� ��えば割当部130は、更新された重み係数が最� ��大きいフェイルラインに、次の予備ライン� ��割り当ててよい。また、例えば図4の行アド レスライン3と列アドレスライン4のように、� ��み係数が同一の値となる場合も考えられる� ��この場合、割当部130は、使用者等により予� ��指定される方向のフェイルラインを優先し� ��、予備ラインを割り当ててよい。また、割� ��部130は、残存予備ライン数がより大きい方� ��のフェイルラインを優先して、予備ライン� ��割り当ててもよい。また、割当部130は、重� ��係数が同一である複数のフェイルラインに� ��して、同時に予備ラインを割り当ててもよ� ��。

 このような処理を繰り返すことにより、� ��済できるフェイルビット数が最大化される� ��うに、予備ラインを割り当てることができ� ��。このため、全てのフェイルビットが救済� ��れるような予備ラインの割り当ての解を、� ��率よく検出することができる。

 図5は、予備ライン割当装置100の他の構成 例を示す図である。本例における予備ライン 割当装置100は、図1から図4に関連して説明し� ��予備ライン割当装置100の構成に対して、救� ��可否判定部140を更に備える。本例の予備ラ� ��ン割当装置100における他の構成要素は、図1 から図4に関連して説明した予備ライン割当� �置100と同一であってよい。

 救済可否判定部140は、図1から図4におい� �説明したように予備ラインを順次割り当て� �場合に、全てのフェイルビットを救済でき� �か否かを判定する。例えば救済可否判定部14 0は、割当部130が、いずれかのフェイルライ� �に予備ラインを割り当てる毎に、全てのフ� �イルビットを救済できる可能性が残ってい� �か否かを判定してよい。

 一例として、救済可否判定部140は、残存� ��備ライン数がゼロとなった場合に、救済さ� ��ていないフェイルビットが残っている場合� ��、全てのフェイルビットを救済できる可能� ��が無くなったと判定してよい。また、残存� ��備ライン数がゼロでない場合においても、� ��済可否判定部140は、例えば図10から図12にお いて後述するような方法で、全てのフェイル ビットを救済できる可能性が残っているか否 かを判定してよい。

 割当部130は、いずれのフェイルラインに� ��備ラインを割り当てたかを、救済可否判定� ��140に通知してよい。救済可否判定部140は、� ��該通知の内容と、ビット計数部110、重み算� ��部120、および割当部130における各レジスタ� ��各メモリの情報とに基づいて、全てのフェ� ��ルビットを救済できる可能性が残っている� ��否かを判定してよい。

 例えば救済可否判定部140は、当該フェイ� ��ラインに予備ラインを割り当てた結果、割� ��部130の残存予備ライン数レジスタが格納し� ��ライン数がゼロとなり、且つビット計数部1 10の更新ビットマップメモリが格納したビッ� ��マップにフェイルデータが残存する場合に� ��全てのフェイルビットを救済できる可能性� ��無いと判定してよい。また、救済可否判定� ��140は、当該フェイルラインに予備ラインを� ��り当てた結果、一の方向の残存予備ライン� ��がゼロとなり、且つ他の方向の残存予備ラ� ��ン数が当該他の方向のフェイルライン数よ� ��少なくなった場合に、全てのフェイルビッ� ��を救済できる可能性が無いと判定してもよ� ��。

 図6は、図5に示した予備ライン割当装置10 0の処理の一例を説明する図である。本例で� �、残存するフェイルビットが(行アドレス、� ��アドレス)=(1、1)、(1、2)、(2、3)、(2、4)、(2� �5)、(2、6)、(3、4)、(3、5)、(3、6)の各ビット� �あり、行方向の残存予備ライン数が1であり� ��列方向の残存予備ライン数が4である第1の� �態の場合を説明する。図6に示す第1の状態は 、メモリ40の初期状態であってよく、また図1 から図5において説明した処理において、い� �つかの予備ラインが割り当てられた後の状� �であってもよい。

 図1から図4において説明したように、重� �算出部120は、それぞれのアドレスラインに� �して重み係数を算出する。そして、割当部13 0は、重み係数が最も大きいフェイルライン� �、予備ラインを割り当てる。本例では、行� �ドレスライン2の重み係数が最も大きいので� ��行アドレスライン2に、行方向の予備ライン を割り当てる。この結果、行方向の残存予備 ライン数はゼロとなる。また、列方向のフェ イルライン数は"5"となり、列方向の残存予備 ライン数"4"より大きい。このような場合、救 済可否判定部140は、いずれかのフェイルビッ トを救済できないと判定して、その旨を割当 部130に通知する。

 割当部130は、当該通知を受けた場合に、� ��備ラインが既に割り当てられているフェイ� ��ラインのいずれかを第1のフェイルラインと して、第1のフェイルラインに対する予備ラ� �ンの割り当てを解除する。本例の割当部130� �、直前に予備ラインを割り当てた行アドレ� �ライン2を第1のフェイルラインとして、予備 ラインの割り当てを解除する。このとき、ビ ット計数部110、重み算出部120、および割当部 130における各レジスタおよび各メモリの内容 は、第1のフェイルラインに予備ラインを割� �当てる前の状態に戻される。

 例えば重み算出部120は、救済可否判定部1 40が、いずれかのフェイルビットを救済でき� ��いと判定した場合に、第1のフェイルライン に予備ラインを割当てる前の重み係数を再計 算してよい。また、ビット計数部110、重み算 出部120、および割当部130は、各レジスタおよ び各メモリについて、フェイルラインに予備 ラインを割り当てる毎のそれぞれの状態を格 納するキャッシュメモリを有してよい。

 また、割当部130は、救済可否判定部140か� ��、いずれかのフェイルビットを救済できな� ��旨の通知を受けた場合に、第1のフェイルラ インが有するフェイルビットを含み、且つ第 1のフェイルラインとは異なる方向の、それ� �れの第2のフェイルラインを選択して、予備� ��インを割り当てる。本例の割当部130は、行� ��ドレスライン2が有するフェイルビット(2,3)� ��(2,4)、(2,5)、(2,6)を含み、且つ行アドレスラ� ��ン2と直交する4本の列アドレスライン3、4、 5、6に、列方向の予備ラインを割り当てる。

 本例では、第2フェイルラインとして選択 されたアドレスラインの本数が、当該方向に 残存する予備ライン数以下であるので、救済 可否判定部140は、全てのフェイルビットを救 済できる可能性がある旨を、割当部130に通知 する。ビット計数部110および重み算出部120は 、それぞれの第2フェイルラインに予備ライ� �を割り当てた状態の、フェイルデータのビ� �トマップ、直交フェイルビット数、重み係� �等を再計算する。

 そして、割当部130は、再計算された重み� ��数に基づいて、次に予備ラインを割り当て� ��べきフェイルラインを選択する。本例の割� ��部130は、行アドレスライン1の重み係数が最 も大きいので、行アドレスライン1に、行方� �の予備ラインを割り当てる。このとき、救� �可否判定部140は、行方向の残存予備ライン� �がゼロでなく、且つ当該予備ラインを割り� �てた場合に残存するフェイルビットがゼロ� �なるので、当該割当により、全てのフェイ� �ビットが救済できた旨を割当部130に通知し� �よい。割当部130は、当該通知を受けた場合� �、予備ラインの割当の態様を確定して、設� �部30に通知してよい。

 以上のように、第1のフェイルラインに予 備ラインを設定すると全てのフェイルビット を救済できる可能性が無いと判定された場合 、予備ライン割当装置100は、第1のフェイル� �インに対する割り当てを解除することによ� �、第1のフェイルラインを割り当てた状態で� ��予備ラインの割り当て解を探索するそれ以� ��の処理を省略することができる。このため� ��処理時間を短縮することができる。また、� ��1のフェイルラインに予備ラインを設定しな い場合、第1のフェイルラインに含まれるフ� �イルビットは、直交する第2のフェイルライ� ��に予備ラインを割り当てなければ救済でき� ��い。本例のように、第1のフェイルラインに 対する割り当てを解除した場合に、直交する 第2のフェイルラインに強制的に予備ライン� �割り当てることにより、予備ラインの割り� �て解を探索する処理の効率を向上させるこ� �ができる。

 また、第2フェイルラインとして選択され たアドレスラインの本数が、当該方向に残存 する予備ライン数より多い場合、救済可否判 定部140は、全てのフェイルビットを救済でき る可能性が無い旨を、割当部130に通知する。 この場合、第1の状態における残存フェイル� �ットと、残存予備ラインとの組み合わせで� �、全てのフェイルビットを救済できる予備� �インの割り当て解が存在しない。

 このため割当部130は、第1の状態となる直 前に、フェイルラインに割り当てた予備ライ ンを更に解除する。つまり割当部130は、当該 フェイルラインに予備ラインを割り当てた結 果、残存フェイルビットおよび残存予備ライ ンが第1の状態となった、フェイルラインに� �する予備ラインの割り当てを更に解除する� �そして割当部130は、予備ラインの割り当て� �解除したフェイルラインのフェイルビット� �含み、且つ当該フェイルラインに直交する� �ェイルラインに予備ラインを強制的に割り� �てる。

 このように、予備ライン割当装置100は、� ��てのフェイルビットを救済できる可能性が� ��い場合に、予備ラインの割り当てを順に解� ��して、直交するフェイルラインに予備ライ� ��を強制的に割り当てる。そして、予備ライ� ��の割り当て解を探索することにより、効率� ��く割り当て解を検出することができる。

 図7は、図1から図6において説明した予備� ��イン割当装置100の動作の一例を示すフロー� ��ャートである。上述したように、まずビッ� ��計数部110は、各フェイルビットについて、� ��方向および列方向の直交フェイルビット数� ��計数する(S400)。

 次に、重み算出部120は、各フェイルライ� ��に含まれるフェイルビットの直交フェイル� ��ット数に基づいて、それぞれのフェイルラ� ��ンの重み係数を算出する(S402)。そして、予� ��ライン割当装置100は、図1から図6において� �明したように、フェイルラインの重み係数� �基づいて、予備ラインの割当処理を行う(S404 )。

 そして予備ライン割当装置100は、S404の処 理により全てのフェイルビットが救済できる か否かを判定する(S406)。全てのフェイルビッ トが救済できる場合、設定部30はメモリ40に� �して救済処理を行う(S408)。また、いずれか� �フェイルビットが救済できない場合、予備� �イン割当装置100は、例えばその旨を使用者� �に通知することにより、救済不可の処理を� �う(S410)。

 図8は、図7において説明した予備ライン� �割当処理S404の、処理の一例を示すフローチ� ��ートである。上述したように、割当部130は� ��重み係数が最大のフェイルラインに予備ラ� ��ンを割り当てる(S500)。次に、救済可否判定� ��140は、割当部130が一つの予備ラインをフェ� ��ルラインに割り当てた場合に、予め定めら� ��た判定基準に基づいて、全てのフェイルビ� ��トを救済できる可能性が残っているか否か� ��判定する(S502)。例えば救済可否判定部140は� ��上述したように、残存フェイルビットと、� ��存予備ライン数とに基づいて、全てのフェ� ��ルビットを救済できるか否かを判定してよ� ��。

 S502において全てのフェイルビットを救済 できる可能性が残っていると判定された場合 、ビット計数部110および重み算出部120の各レ ジスタおよび各メモリのデータを更新する。 例えば重み算出部120は、重み係数を更新する (S504)。また、救済可否判定部140は、救済され ていないフェイルビットが存在するか否かを 判定する(S506)。S506において、救済されてい� �いフェイルビットが存在すると判定された� �合、S500からの処理を繰り返して、予備ライ� ��を順次割り当てる。また、S506において、救 済されていないフェイルビットが存在しない と判定された場合、予備ラインの当該割り当 ての態様で、全てのフェイルビットが救済可 能であると判定する(S508)。この場合、図7に� �いて説明したように設定部30により、救済処 理S508を行う。

 また、S502において、全てのフェイルビッ トを救済できる可能性が無いと判定された場 合、割当部130は、直前に設定した予備ライン の割り当てを解除する(S510)。そして、ビット 計数部110および重み算出部120の各レジスタお よび各メモリのデータを、当該予備ラインを 割り当てる前の状態に戻す。例えば重み算出 部120は、当該予備ラインを割り当てる前の状 態の重み係数を再計算してよい(S512)。

 次に、割当部130は、予備ラインの割り当� ��を解除した第1のフェイルラインのフェイル ビットを含み、第1のフェイルラインと直交� �る第2のフェイルラインを選択して、予備ラ� ��ンを割り当てる(S514)。次に、救済可否判定� ��140は、全てのフェイルビットを救済できる� ��能性があるか否かを判定する(S516)。

 S516において、全てのフェイルビットを救 済できる可能性があると判定された場合、当 該予備ラインの割り当てに基づいて、S504以� �の処理を行う。また、S516においていずれか� ��フェイルビットを救済できないと判定され� ��場合、割当部130は、更に予備ラインの割り� ��てを解除できるか否かを判定してよい(S518)� ��例えば、既にメモリ40の初期状態にまで遡� �て予備ラインの割り当てを解除している場� �、これ以上の予備ラインの割り当てを解除� �きないと判定してよい。

 S518において、更に予備ラインの割り当て を解除できると判定した場合、割当部130は、 S510の処理に戻り、直前に割り当てた予備ラ� �ンを解除する。また、S518において、更に予� ��ラインの割り当てを解除できないと判定し� ��場合、メモリ40に対しての全てのフェイル� �ットを救済できる予備ラインの割り当て解� �存在しないとして、処理を終了する。この� �合、図7において説明した救済不可処理S410を 実行する。以上のような処理により、予備ラ インの割り当て解を効率よく検出することが できる。

 また、以上の例においては、予備ライン� ��割り当てる毎に、各フェイルラインの重み� ��数を更新する例を説明した。他の例では、� ��備ライン割当装置100は、各フェイルライン� ��重み係数を更新せずともよい。この場合、� ��備ライン割当装置100は、図8において説明し た、重み係数更新処理S504および重み係数再� �算処理S512を省略してよい。このような処理� ��よっても、予備ラインの割り当て解を効率� ��く検出することができる。

 また、図8の処理例では、S502において、� �てのフェイルビットを救済できないと判定� �れた場合に、直前に割り当てた予備ライン� �解除する(S512)。他の例におけるS512の処理で� ��、S500において最初に割り当てた予備ライン を解除してもよい。この場合、S512の処理で� �、ビット計数部110および重み算出部120の各� �ジスタおよび各メモリは、初期状態に戻さ� �る。また、S500の処理の前に、割当部130は、� ��め定められた数のフェイルビットがあるフ� ��イルラインに、予備ラインを予め割り当て� ��よい。

 図9は、メモリ40における他のフェイルデ� ��タの例を示す図である。また、本例のメモ� ��40の記憶領域は、列方向および行方向の少� �くとも一方において、複数の記憶ブロック� �分割される。図9の例では、メモリ40の記憶� �域は、行方向に3つのブロックに分割され、� ��方向に2つのブロックに分割される。メモリ 40は、それぞれの記憶ブロックごとに、行方� ��および列方向の予備ラインを有してよい。

 係るメモリ40に対して、図8において説明� ��たS502の処理において、救済可否判定部140が いずれかのフェイルビットを救済できないと 判定した場合、直前の第1のフェイルライン� �り当てた予備ラインを解除する(S510)。そし� �、S514の処理において割当部130は、第1のフェ イルラインと同一の方向のフェイルであり、 且つ記憶ブロック毎のフェイルビット数が、 第1のフェイルラインと同一となる第3のフェ� ��ルラインを選択して、予備ラインを強制的� ��割り当ててよい。このとき、割当部130は、� ��述した第2のフェイルライン、および第3の� �ェイルラインの双方に対して、予備ライン� �割り当ててよい。

 例えば、図8において説明したS500の処理� �おいて、図9に示した行アドレスライン1に予 備ラインを割り当てた場合を説明する。この 場合において、いずれかのフェイルビットを 救済できないと判定された場合(S502)、S514の� �理においては、まず第2のフェイルラインと� ��て、列アドレスライン1、2、7、8、9が選択� �れる。更に、行アドレスライン2が有するフ� ��イルビットの記憶ブロック毎の個数は、行� ��ドレスライン1が有するフェイルビットの記 憶ブロック毎の個数と同一となるので、割当 部130は、行アドレスライン2のフェイルビッ� �を含み、且つ行アドレスライン2と直交する� ��アドレスライン2、3、6、7、9を第3のフェイ� ��ラインとして選択する。

 そして割当部130は、選択した第2のフェイ ルラインおよび第3のフェイルラインに、強� �的に予備ラインを割り当てる(S514)。このよ� �に、記憶ブロック毎に予備ラインが設けら� �ている場合において、あるフェイルライン� �予備ラインを割り当てると全てのフェイル� �ットを救済できない場合、当該フェイルラ� �ンに対して、記憶ブロック毎のフェイルビ� �ト数が同一であるフェイルラインも、予備� �インを割り当てた場合には全てのフェイル� �ットを救済できない可能性が高い。係るフ� �イルラインについても、直交する第3のフェ� ��ルラインに強制的に予備ラインを割り当て� ��ことにより、予備ラインの割り当て解を更� ��効率よく探索することができる。

 図10は、予備ライン割当装置100の他の構� �例を示す図である。本例の予備ライン割当� �置100は、図5に関連して説明した予備ライン� ��当装置100の構成に加え、孤立フェイル検出� ��150を更に備える。他の構成要素は、図5に関 連して説明した予備ライン割当装置100と同一 であってよい。

 孤立フェイル検出部150は、当該フェイル� ��ットを含む列方向および行方向のフェイル� ��インに、他のフェイルビットが無い場合に� ��当該フェイルビットを孤立フェイルビット� ��して検出する。つまり、孤立フェイル検出� ��150は、列方向のあるフェイルラインに含ま� ��るフェイルビットが一つだけであり、且つ� ��該フェイルビットを含み当該フェイルライ� ��と直交する行方向のフェイルラインに、他� ��フェイルビットが含まれない場合に、当該� ��ェイルビットを孤立フェイルビットとして� ��出する。孤立フェイル検出部150は、ビット� ��数部110が順次更新して格納しているフェイ� ��データのビットマップに基づいて、それぞ� ��の状態における孤立フェイルビットを順次� ��出してよい。

 図11は、孤立フェイル検出部150に与えら� �るフェイルデータのビットマップの一例を� �す図である。上述したように、孤立フェイ� �検出部150は、当該ビットマップに基づいて� �孤立フェイルビットを検出してよい。本例� �は、孤立フェイル検出部150は、フェイルビ� �ト(1,1)、(2,2)、(3,3)、(4,4)、(5,5)の5つのフェイ ルビットを、孤立フェイルビットとして検出 する。

 また、救済可否判定部140は、図8に示した S502およびS516の処理において、孤立フェイル� ��ット数および残存予備ライン数に基づいて� ��全てのフェイルビットを救済できる可能性� ��残っているか否かを判定してよい。例えば� ��済可否判定部140は、行方向および列方向の� ��存予備ライン数の和が、孤立フェイル数よ� ��少ない場合に、全てのフェイルビットを救� ��できる可能性が無いと判定してよい。

 また、割当部130は、図8において説明した S500の処理において、孤立フェイル数および� �存予備ライン数に基づいて、強制的に予備� �インを割り当てるべきフェイルラインを選� �してよい。例えば割当部130は、孤立フェイ� �ビット数から、列方向の残存予備ラインの� �数を減じた減算結果に応じた本数の行方向� �予備ラインを、孤立フェイルビットを含む� �意の行方向のフェイルラインに割り当てて� �い。

 例えば、孤立フェイルビット数が"5"であ� ��、列方向の残存予備ラインの本数が"2"であ� ��場合、割当部130は、3本の行方向の予備ライ ンを、孤立フェイルビットを含むいずれか3� �の行方向のフェイルラインに割り当てる。� �様に、孤立フェイルビット数が"5"であり、� �方向の残存予備ラインの本数が"4"である場� �、割当部130は、1本の列方向の予備ラインを� ��孤立フェイルビットを含むいずれか1本の列 方向のフェイルラインに割り当てる。

 各方向の予備ラインで救済できる孤立フ� ��イルビット数の最大値は、当該方向の残存� ��備ライン数となる。このため、行方向また� ��列方向の少なくともいずれかの残存予備ラ� ��ン数aが孤立フェイルビット数bより少ない� �合、他の方向の予備ラインでは、少なくと� �b-a個の孤立フェイルビット数を救済しなけ� �ばならない。

 このため、上述したように、孤立フェイ� ��数および残存予備ライン数に基づいて、強� ��的に予備ラインを割り当てることにより、� ��に効率よく予備ラインの割り当て解を探索� ��ることができる。また、孤立フェイル検出� ��150は、重み係数に基づいて割当部130が予備� ��インをフェイルラインに割当てる毎に、当� ��フェイルラインに含まれるフェイルビット� ��除外した状態における、孤立フェイルビッ� ��を検出してよい。孤立フェイル検出部150は� ��各状態における孤立フェイルビット数を格� ��するレジスタを有してよい。

 また、まだ予備ラインが割り当てられて� ��らず、未救済のフェイルビットの全てが孤� ��フェイルビットとなった場合であって、孤� ��フェイルビット数が残存予備ライン数より� ��ない場合、救済可能であることが確定する� ��この場合、割当部130は、残存している全て� ��フェイルラインに予備ラインを割り当てて� ��割当処理を終了してよい。例えば割当部130� ��、使用者等により予め指定された方向の予� ��ラインを優先して、残存しているフェイル� ��インに割り当ててよい。

 また、図10および図11に関連して説明した 、孤立フェイルビットに係る処理は、図9に� �連して説明した記憶ブロック毎に行ってよ� �。例えば、救済可否判定部140は、いずれか� �記憶ブロックにおいて、行方向および列方� �の残存予備ライン数の和が、孤立フェイル� �より少ない場合に、全てのフェイルビット� �救済できる可能性が無いと判定してよい。

 図12は、救済可否判定部140の一部の構成� �を示す図である。本例の救済可否判定部140� �、図1から図11に関連して説明した機能を実� �する構成に加え、第1の乗算部142、第2の乗算 部144、および比較部146を有する。

 第1の乗算部142は、列方向のフェイルライ ンに含まれるフェイルビットの個数の最大値 と、列方向の残存予備ラインの本数とを乗算 した第1の乗算値を算出する。つまり、第1の� ��算値は、列方向の残存予備ラインにより救� ��可能なフェイルビットの最大値を示す。ま� ��、第2の乗算部144は行方向のフェイルライン に含まれるフェイルビットの個数の最大値と 、行方向の残存予備ラインの本数とを乗算し た第2の乗算値を算出する。つまり、第2の乗� ��値は、行方向の残存予備ラインにより救済� ��能なフェイルビットの最大値を示す。

 比較部146は、第1の乗算値および第2の乗� �値の和が、残存フェイルビットの総数より� �さいか否かを判定する。第1の乗算値および� ��2の乗算値の和が、残存フェイルビットの総 数より小さい場合、残存予備ラインでは全て のフェイルビットを救済できない。この場合 、比較部146は、その旨を割当部130に通知する 。

 図13は、フェイルビットのビットマップ� �一例を示す図である。本例のフェイルビッ� �の総数は13であり、行方向および列方向の残 存予備ラインの本数はそれぞれ"3"である。

 第1の乗算部142は、行方向のフェイルライ ンに含まれるフェイルビットの個数の最大値 を検出する。図13に示すように、本例におけ� ��当該最大値は"2"である。第1の乗算部142は、 残存予備ラインの本数"3"と、最大値"2"とを乗 算して、第1の乗算値"6"を算出する。

 同様に、第2の乗算部144は、列方向のフェ イルラインに含まれるフェイルビットの個数 の最大値を検出する。図13に示すように、本� ��における当該最大値は"2"である。第2の乗算 部144は、残存予備ラインの本数"3"と、最大値 "2"とを乗算して、第2の乗算値"6"を算出する� �

 本例では、第1の乗算値および第2の乗算� �の和"12"が、残存フェイルビット数"13"より小 さい。このため比較部146は、全てのフェイル ビットを救済できない旨を、割当部130に通知 する。このような処理により、全てのフェイ ルビットを救済できる可能性が無くなったこ とを、より早期に検出することができるので 、予備ラインの割り当て解を効率よく探索す ることができる。

 また、救済可否判定部140は、図12および� �13に関連して説明した第1の乗算値および第2� ��乗算値を用いた処理を、図9に関連して説明 した記憶ブロック毎に行ってよい。例えば、 救済可否判定部140は、いずれかの記憶ブロッ クにおける、第1の乗算値および第2の乗算値� ��和が、残存フェイルビット数より小さい場� ��に、全てのフェイルビットを救済できる可� ��性が無いと判定してよい。

 図14は、本発明の一つの実施形態に係る� �モリ製造方法の一例を示すフローチャート� �ある。当該メモリ製造方法は、図1から図13� �おいて説明した予備ライン割当方法および� �モリ救済方法を用いて、半導体メモリ等の� �モリ40を製造する。

 まず、メモリ形成段階において、複数の� ��備ラインが設けられたメモリ40を形成する(S 600)。次に、メモリ40を試験して、メモリ40の� ��ェイルデータを生成する(S602)。

 次に、予備ライン割当段階において、メ� ��リ40においてフェイルビットを有する行方� �のフェイルライン及び列方向のフェイルラ� �ンのうち、いずれのフェイルラインに予備� �インを割り当てるかを決定する(S604)。S604は� ��図1から図13において説明した予備ライン割� ��装置100を用いて行ってよい。

 そして、決定した予備ラインの割り当て� ��、メモリ40に設定してメモリ40を救済するこ とにより、良品のメモリ40を製造する(S606)。S 606は、図1から図13において説明した設定部30� ��用いて行ってよい。このような処理により� ��良品のメモリ40を効率よく製造することが� �きる。

 図15は、本発明の一つの実施形態に係る� �ンピュータ1900のハードウェア構成の一例を� ��す。コンピュータ1900は、与えられるプログ ラムに基づいて、図1から図14において説明し た予備ライン割当装置100として機能してよい 。

 コンピュータ1900が予備ライン割当装置100 として機能する場合、プログラムは、コンピ ュータ1900を、図1から図14において説明した� �ット計数部110、重み算出部120、割当部130、� �済可否判定部140、および孤立フェイル検出� �150のすくなくともいずれかとして機能させ� �よい。例えばプログラムは、CPU2000を、ビッ� ��計数部110、重み算出部120、割当部130、救済� ��否判定部140、および孤立フェイル検出部150� ��して機能させてよく、またハードディスク� ��ライブ2040またはRAM2020を、ビット計数部110� �重み算出部120、および割当部130に設けられ� �各レジスタおよび各メモリとして機能させ� �よい。

 コンピュータ1900は、CPU周辺部、入出力部 、及びレガシー入出力部を備える。CPU周辺部 は、ホストコントローラ2082により相互に接� �されるCPU2000、RAM2020、グラフィックコントロ ーラ2075、及び表示装置2080を有する。入出力� ��は、入出力コントローラ2084によりホストコ ントローラ2082に接続される通信インターフ� �ース2030、ハードディスクドライブ2040、及び CD-ROMドライブ2060を有する。レガシー入出力� �は、入出力コントローラ2084に接続されるROM2 010、フレキシブルディスク・ドライブ2050、� �び入出力チップ2070を有する。

 ホストコントローラ2082は、RAM2020と、高� �転送レートでRAM2020をアクセスするCPU2000及び グラフィックコントローラ2075とを接続する� �CPU2000は、ROM2010及びRAM2020に格納されたプロ� �ラムに基づいて動作して、各部の制御を行� �。グラフィックコントローラ2075は、CPU2000等 がRAM2020内に設けたフレーム・バッファ上に� �成する画像データを取得して、表示装置2080� ��に表示させる。これに代えて、グラフィッ� ��コントローラ2075は、CPU2000等が生成する画� �データを格納するフレーム・バッファを、� �部に含んでもよい。

 入出力コントローラ2084は、ホストコント ローラ2082と、比較的高速な入出力装置であ� �通信インターフェース2030、ハードディスク� ��ライブ2040、CD-ROMドライブ2060を接続する。� �信インターフェース2030は、ネットワークを� ��して他の装置と通信する。例えば通信イン� ��ーフェイス2030は、メモリ試験装置10および� ��定部30と通信してよい。ハードディスクド� �イブ2040は、コンピュータ1900内のCPU2000が使� �するプログラム及びデータを格納する。CD-RO Mドライブ2060は、CD-ROM2095からプログラム又は データを読み取り、RAM2020を介してハードデ� �スクドライブ2040に提供する。

 また、入出力コントローラ2084には、ROM201 0と、フレキシブルディスク・ドライブ2050、� ��び入出力チップ2070の比較的低速な入出力装 置とが接続される。ROM2010は、コンピュータ19 00が起動時に実行するブート・プログラム、� ��ンピュータ1900のハードウェアに依存するプ ログラム等を格納する。フレキシブルディス ク・ドライブ2050は、フレキシブルディスク20 90からプログラム又はデータを読み取り、RAM2 020を介してハードディスクドライブ2040に提� �する。入出力チップ2070は、フレキシブルデ� ��スク・ドライブ2050、パラレル・ポート、シ リアル・ポート、キーボード・ポート、マウ ス・ポート等を介して各種の入出力装置を接 続する。

 RAM2020を介してハードディスクドライブ204 0に提供されるプログラムは、フレキシブル� �ィスク2090、CD-ROM2095、又はICカード等の記録� ��体に格納されて利用者によって提供される� ��プログラムは、記録媒体から読み出され、R AM2020を介してコンピュータ1900内のハードデ� �スクドライブ2040にインストールされ、CPU2000 において実行される。

 当該プログラムは、コンピュータ1900にイ ンストールされる。当該プログラムは、CPU200 0等に働きかけて、コンピュータ1900を、前述� ��た予備ライン割当装置100の各構成要素とし� ��機能させる。

 以上に示したプログラムは、外部の記録� ��体に格納されてもよい。記録媒体としては� ��フレキシブルディスク2090、CD-ROM2095の他に� �DVDおよびCD等の光学記録媒体、MO等の光磁気� ��録媒体、テープ媒体、ICカード等の半導体� �モリ等を用いることができる。また、専用� �信ネットワークまたはインターネットに接� �されたサーバシステムに設けたハードディ� �ク又はRAM等の記憶装置を記録媒体として使� �して、ネットワークを介してプログラムを� �ンピュータ1900に提供してもよい。

 以上、実施形態を用いて本発明を説明し� ��が、本発明の技術的範囲は上記実施形態に� ��載の範囲には限定されない。上記実施形態� ��、多様な変更又は改良を加えることができ� ��。そのような変更又は改良を加えた形態も� ��発明の技術的範囲に含まれ得ることが、請� ��の範囲の記載から明らかである。

 以上説明したように、本例における予備� ��イン割当装置100によれば、予備ラインの割� ��当て解を効率よく探索することができる。� ��た、メモリ救済装置20によれば、メモリを� �率よく救済することができる。