(57)【要約】メモリ装置は、多数のメモリ位置の物理ブロックを有するメインメモリ（１０）を備える。メインメモリ、例えばフラッシュメモリは、一度に少なくとも１個の物理ブロックの消去を行う。最終的に、物理アドレスマッピングテーブルにいたる論理アドレスのようなポインティング情報を指し示す、ポインタ（７２,７５）のチェーンをメインメモリ（１０）内に保存し、各ポインタ（７２,７５）を各ブロック（７０,７４）に各個に保存し、チェーンにおける最終ではない各ポインタ（７２）はチェーンにおける次のポインタを有する対応ブロック（７４）を指すものとする。メインメモリ（１０）の起動時、メインメモリからのポインタを使用して、チェーンをたどってポインティング情報を見つける。通常動作においては、ＲＡＭメモリに保存した直接ポインタを優先的に使用する。
2009521044.tif 000002
【特許請求の範囲】
【請求項１】
多数のメモリ位置の物理ブロックを有し、一度に少なくとも１個の物理ブロックを消去することができる不揮発性メインメモリと、
対応するブロックにそれぞれ各個に格納したポインタのチェーンを保持するよう構成し、チェーン中の最終ではない各ポインタはチェーン中の次のポインタを有する各ブロックを指し示すものとした、マッピング制御回路であって、さらに少なくとも一個の他のブロック中に格納したポインティング情報を保持するよう構成し、チェーン中の最終ポインタは前記ポインティング情報を有するブロックを指すものとし、さらにまた、少なくとも装置を起動するとき、前記メインメモリからの前記ポインタを使用して前記チェーンをたどることによって前記ポインティング情報を見つけ出すよう構成した該マッピング制御回路と、
を有することを特徴とする装置。
【請求項２】
請求項１記載の装置において、前記マッピング制御回路は、ポインタを修正せずに前記他のブロックを多数回消去しまた更新ポインティング情報を前記他のブロックに書き込み、この後、前記他のブロックの代わりに置換ブロックを使用して前記ポインティング情報を格納し、最終ポインタが前記置換ブロックを指し示すよう修正するように構成した、装置。
【請求項３】
請求項２に記載の装置において、前記マッピング制御回路は、前記最終ポインタを格納している対応のブロックを他の置換ブロックに置換し、前記最終ポインタを格納しているブロックを指し示す最終ではないポインタを、前記他の置換ブロックを指し示すよう修正し、前記最終ではないポインタは前記最終ポインタより低頻度で修正するように構成した装置。
【請求項４】
請求項２に記載の装置において、前記マッピング制御回路は、前記ポインティング情報を更新する回数に基づいて、動的に前記チェーンの長さを調節するよう構成した装置。
【請求項５】
請求項１に記載の装置において、前記マッピング制御回路は、順次バージョンの特定ポインタを、これら特定ポインタのための少なくとも１個の特定ブロック中におけるそれぞれ相互に異なる各メモリ位置に、書き込むよう構成し、さらにマッピング制御回路は、前記少なくとも１個の特定ブロックをサーチして最新バージョンの前記特定ポインタを少なくとも装置の起動時に見つけ出すことによって、前記最新バージョンの特定ポインタを読み出すよう構成した装置。
【請求項６】
請求項５に記載の装置において、前記マッピング制御回路は、スペアブロックを確保し、前記特定ポインタのための前記少なくとも１個の特定ブロックが満杯の時、新バージョンの特定ポインタを前記スペアブロックへ書き込み、続いて前記特定ポインタのための前記少なくとも１個の特定ブロックを消去するよう構成し、
さらに前記マッピング制御回路１４は、前記特定ポインタのための前記少なくとも１個の特定ブロックが満杯または空であることを検出するとき、起動時に前記スペアブロックをサーチして最新バージョンの前記特定ポインタを見つけ出すよう構成した装置。
【請求項７】
請求項６に記載の装置において、前記マッピング制御回路は、前記特定ポインタのための前記少なくとも１個の特定ブロックおよび前記スペアブロックを指し示すポインタを、それぞれに対応する各ブロックに各個に格納するよう構成した装置。
【請求項８】
請求項６に記載の装置において、前記マッピング制御回路は、前記スペアブロックを、多数の同時有効ポインタのためのそれぞれ対応するブロックのスペアに共通のスペアブロックとして使用するよう構成した装置。
【請求項９】
請求項１に記載の装置において、前記マッピング制御回路は、ポインタツリーを保持する構成とし、ツリー中の最終ポインタは前記ポインティング情報を有する各ブロックを指し示すものとし、前記チェーンは前記ツリーの一部とし、前記ツリー中の最終ではないポインタは共有ブロックを指し示すものとし、前記ツリー中における単一ノードからの異なる分岐ポインタを前記共有ブロック中に一緒に格納するよう構成した装置。
【請求項１０】
請求項９に記載の装置において、前記マッピング制御回路は、順次バージョンの特定ポインタをメインメモリ中の前記共有ブロックに書き込む構成とし、この場合、前記特定ポインタを更新するシーケンスに基づいて動的に選択した順番で、前記特定分岐ポインタを前記共有ブロック中のそれぞれ相互に異なるメモリ位置に書き込むよう構成し、さらに前記マッピング制御回路は、前記共有ブロックをサーチして最新バージョンの前記特定ポインタを少なくとも起動時に見つけ出すことによって、最新バージョンの各分岐の前記特定ポインタを読み出すよう構成した装置。
【請求項１１】
請求項１０に記載の装置において、前記マッピング制御回路は、スペアブロックを確保し、前記対応するブロックが満杯のときに新バージョンの１個の特定ポインタを前記スペアブロックに書き込み、他分岐の最新バージョンのポインタを前記スペアブロックにコピーし、続いて前記共有ブロックを消去するよう構成し、また前記マッピング制御回路は、マッピング制御回路が、満杯である前記共有ブロックを検出するとき、少なくとも起動時に、前記スペアブロックをサーチして前記分岐ポインタを見つけ出すよう構成した装置。
【請求項１２】
請求項１１に記載の装置において、前記マッピング制御回路は、少なくとも起動時、および前記特定ポインタを格納しているブロックのどれか一個でも満杯であるとき、前記スペアブロック中に情報を格納しているかどうか検査し、格納している場合、満杯ブロックからの情報の代わりに前記スペアブロックのからの情報を使用するよう構成した装置。
【請求項１３】
請求項１に記載の装置において、前記メインメモリをフラッシュメモリとした装置。
【請求項１４】
請求項１に記載の装置において、この装置がＲＡＭメモリを有し、前記マッピング制御回路は、前記ポインティング情報を有するブロックを直接指し示す直接ポインタを前記ＲＡＭメモリに格納し、起動後の操作中直接ポインタを使用して前記ポインティング情報を見つけ出すよう構成した装置。
【請求項１５】
多数のメモリ位置の物理ブロックを有するメインメモリの操作の方法であって、前記メインメモリは一度に少なくとも１個の物理ブロックを消去するよう構成した該メインメモリの操作方法において、
ポインタチェーンを格納し、各ポインタをそれぞれに対応するブロックに各個に格納し、チェーン中の最終ではない各ポインタは、チェーン中の次のポインタを有するそれぞれに対応するブロックを指し示すものとし、
ポインティング情報を少なくとも一個の他のブロック中に格納し、チェーン中の最終ポインタは前記他のブロックを指し示すものとし、
起動時にメ前記インメモリを使用し、前記チェーンをたどることによって前記ポンティング情報を見出す、
ことを特徴とするメインメモリ操作の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリデバイスおよびこのようなメモリデバイスを操作する方法に関するものである。
【背景技術】
【０００２】
特許文献１（米国特許第６,７１１,６６３号）は、フラッシュメモリデバイスを開示している。データは、フラッシュメモリデバイスから、半導体メモリデバイスほぼ同様に読み出すことができる。書き込みデータはより複雑である。通常、書き込みは、メモリセルのブロックを消去し、続いて消去したブロックにデータページをプログラムする（組み込む）ことを伴う。通常、消去はブロック全体に対し一括にのみ実行でき、したがって、この場合、このブロック全体は消去構成単位を形成する。プログラミング（プログラム組み込み）は、通常より小さい構成単位（いわゆるページと定義される）で実行される。
【０００３】
フラッシュメモリデバイスには消耗の問題がある。データブロックは消耗しきる前の限定回数でしか消去およびプログラム組み込みを行えず、消耗後はもはや信頼を持って用いることはできない。もし特定アドレスのためのフラッシュメモリデバイスにおけるブロックを、他のブロックよりも一層頻繁に消去およびプログラム組み込みしたら、これらブロックの有効寿命がフラッシュメモリデバイスの有効寿命を限定することになる。
【０００４】
この問題は、時間変動型論理‐物理アドレスマッピングを使用して対処された。マッピングを用いることにより、フラッシュメモリにアクセスするために使用する論理アドレスが、異なる時間にフラッシュメモリの異なる物理ブロックの位置を参照できる。このようにして、消去およびプログラミングを頻繁に要する論理アドレスは、時々、異なる物理ブロックに再マッピングし、これにより、論理ブロックが消去およびプログラム組み込みされる度毎に、同一の物理ブロックが消去およびプログラミングされるのを防ぐことができる。（本明細書で用いる用語「論理ブロック」は、物理ブロックにおけるマッピング可能なアドレスのセット全体にマッピングするアドレスセットを表現するものであり、随意的にこれら位置に格納したデータをもおおまかに言及する。）
【０００５】
効率的な論理‐物理マッピングはマッピングテーブルを要し、このマッピングテーブルは、論理アドレスに基づいて格納した物理アドレスを有し、この論理アドレスに対して物理アドレスが対応する。原則的に、このようなマッピングテーブルは、物理‐論理アドレスマッピングの変更が行われる度毎に更新しなければならない。通常、このようなフラッシュメモリのマッピングテーブルはＲＡＭメモリに保存する。起動中、マッピングテーブルは、フラッシュメモリ中に格納される「タグ」から再構築し、異なる物理メモリ領域（例えばブロック）に対してその現論理アドレスは何であるかを示す。
【０００６】
特許文献１（米国特許第６７１１６６３号）は、フラッシュメモリ自体に格納するマッピングテーブルの利用を説明している。特許文献１は、セグメントで編成したマッピングを使用する。メモリは多数のブロックセグメントとして編成される。各セグメントに対してそれぞれに対応するマッピングテーブルを設け、この各セグメントのための論理アドレスをこのセグメントにおける物理アドレスに変換する。セグメントのサイズは、各マッピングテーブルのサイズがメモリページ、つまりフラッシュメモリのプログラム組み込みの構成単位に対応するよう選択する。
【０００７】
特許文献１（米国特許第６７１１６６３号）は、各セグメントに「メモリ更新ブロック」を設け、このセグメントにおける順次バージョンのマッピングテーブルを格納する。メモリ更新ブロックにおける最後のプログラム組み込みページをマッピングテーブルとして用いる。セグメントのマッピングテーブルが変更される度毎に、更新マッピングテーブルをメモリ更新ブロックにおける次のページに組み込む。各変更の後、新しいページを用いて、メモリ更新ブロックのすべてのページがプログラム組み込みされるまでマッピングテーブルを格納する。すべてのページがプログラム組み込みされた後、メモリテーブルの次の更新が起きる時、メモリ更新ブロックを消去し、新しいメモリテーブルを消去したブロックの最初にページへ書き込まれる。
【０００８】
このアプローチは起動中にタグからマッピングテーブルを再構築するのに時間を要さないという利点がある。一方、マッピングテーブルはフラッシュメモリから直接読み出すことができる。
【０００９】
しかし、マッピングテーブルを格納するブロックは、頻繁な更新によって消耗が激しくなる。
【特許文献１】米国特許第６，７１１，６６３号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
とくに、本発明の目的は、マッピングテーブルを格納するメモリを有し、マッピングテーブルの更新による際限のない消耗を回避する装置を得るにある。
【課題を解決するための手段】
【００１１】
請求項１に従って装置を提供する。請求項１においては、マッピング制御回路は、ポインタのチェーンをメインメモリ（例えばフラッシュメモリ）のそれぞれに対応するブロックに各個に格納する。チェーンにおける最終ではない各ポインタは、チェーンにおける次のポインタを有する対応のブロックを指し示す。またマッピング制御回路は、メインメモリ内にポインティング情報を格納する。チェーンにおける最終ポインタはポインティング情報を有するブロックを指し示す。初期ポインタは、好適には、所定ブロックに格納する。このようにして、マッピング制御回路は、ポインティング情報をこのチェーンをたどることによって動的に選択したブロック中に見つけ出すことができる。
【００１２】
ある実施形態においては、マッピング制御回路は、ブロック内でポインティング情報を多数回更新した後、ポインティング情報を有するブロックを置換する。つぎに、最終ポインタは、置換ブロックを指し示すよう更新する。このようにして、ポインティング情報を有するブロックが置換されるまでは、新バージョンのポインティング情報を書き込むとき、最終ポインタは更新を必要とせず、これにより、消耗が少なくなる。ある実施形態においては、より長いチェーンを用い、チェーンに沿ったポインタを有するブロックを、多数回更新の後、置換することができる。この場合、置換の頻度をチェーンに沿ってより上流になる程より低く抑えることができ、チェーンの根元における過剰な消耗を回避することができる。さらに別の実施形態においては、チェーンの長さを動的に変化させ、例えば閾回数以上の更新が生じる場合チェーンを延長することによって、チェーンの根元における更新回数を必要範囲内に留めるようにする。
【００１３】
別の実施形態においては、ポインタツリーを用い、チェーンはツリーの一部とする。このようにして、ツリー中のノードは、多数のポインタによる多数の後継サクセサに分岐することができる。
【００１４】
別の実施形態においては、順次バージョンのポインタをそれぞれ、ポインタのためのブロックにおける相互に異なる対応位置に書き込む。この実施形態においては、マッピング制御回路は、最新バージョンのブロックをサーチすることによって、特定ポインタの最新バージョンを読み出す。このようにして、ポインタを変更する度毎にブロックを消去する必要がなく、消耗を減少させ、同時に、起動時にそのブロックまたは２，３個の代替ブロック内での限定サーチで済ますことができる。さらにある実施形態においては、スペアブロックを確保し、ポインタの初期ブロックが満杯になったときポインタの新バージョンを書き込むようにする。続いてポインタの初期ブロックを消去する。これにより、中断によるポインタの損失を防ぐ。起動時、マッピング制御回路は、少なくとも特定ポインタのためのブロックが満杯であるのを検出するとき、ポインタのサーチをスペアブロックまで拡張する。さらにある実施形態においては、初期ブロックおよびスペアブロックを指し示す他のポインタをメインメモリのブロック内に一緒に保存する。
【００１５】
さらにある実施形態においては、スペアブロックを異なるポインタのための多数の異なるブロックと共有することができる。この場合、ポインタをスペアブロックに書き込む度毎に、その後ポインタのための初期ブロックを全てのポインタのためのスペアブロックとして用いることができる。
【００１６】
さらにある実施形態においては、チェーンはポインタツリーの一部とする。この場合、ツリー内の同一ノードからの異なる分岐の他のポインタは、初期ブロックおよびスペアブロックを指し示すことができ、これらのブロックを速やかに識別することができる。ノードからの他のポインタは異なるポインタのブロックおよびそれらが共有するスペアブロックを指し示すこともできる。さらにある実施形態においては、同一ノードからのこれら他のポインタを同一ブロック内に一緒に格納することができる。
【００１７】
別の実施形態においては、チェーンはツリーおよびポインティング情報を有するそれぞれのブロックを指し示すツリーにおける異なる最終ポインタの一部とする。このようにして、複数のブロックに分布しているポインティング情報を簡単に見つけることができる。
【００１８】
別の実施形態においては、同一ノードからの異なる分岐を指し示す準備バージョンのポインタは,新バージョンが届くとき、ポインタを更新するシーケンスに従って動的に選択した順番で、格納する。起動時、マッピング制御回路は、ブロックをサーチすることによって、最新バージョンの各分岐ポインタを読み出す。この方法においては、ポインタの格納を要するブロック数を少なく抑えることができる。さらにある実施形態においては、これまで使用していたブロックが満杯であるとき、ノードからの分岐へのポインタの新バージョンを書き込むよう、スペアブロックを設けることができる。この場合、そのノードからの他の分岐ポインタのバージョンを、スペアブロックおよびこれまで使用していたブロックへコピーする。起動時、マッピング制御回路は各ブロックが満杯であることを検出するとき、マッピング制御回路はスペアブロックをサーチして分岐ポインタを見つけ出す。
【００１９】
次の図面に図示した典型的な実施例の説明から、これらおよび他の実施例ならびに発明の効果が明らかになるであろう。
【発明を実施するための最良の形態】
【００２０】
図１は、メモリを備える装置の図である。この装置はフラッシュメモリ１０、マッピングテーブルメモリ１２、マッピング制御回路１４、プロセッサ１６およびマルチプレクサ１８ａ,ｂを備える。例えば、マッピング制御回路１４は、マッピング制御の機能を実行するコンピュータプログラムを組み込んだプログラム可能回路として実装する。プロセッサ１６はマッピング制御回路１４への制御接続部を有する。プロセッサ１６およびマッピング制御回路１４のデータ入出力部をフラッシュメモリ１０のデータ入出力部に接続する。マッピング制御回路１４およびプロセッサ１６は、ブロックアドレス部分（随意にページアドレス部分も含む）および残りのアドレス部分のアドレス出力部を有する。プロセッサ１６およびマッピング制御回路１４からのブロックアドレス部分出力部および残りのアドレス部分出力部は、マルチプレクサ１８ａ，ｂそれぞれを介して、フラッシュメモリ１０のブロックアドレス入力部および残りのアドレス入力部に接続する。プロセッサ１６からのアドレス出力部は、マッピングテーブルメモリ１２を介してマルチプレクサ１８ｂに接続する。マッピング制御回路１４は、マッピングテーブルメモリ１２およびマルチプレクサ１８ａ，ｂに接続する制御出力を有する。
【００２１】
フラッシュメモリ１０は、一度に少なくとも１個のメモリ位置ブロックの消去操作を可能とするタイプとする。それゆえ、消去の単位をブロックと称する。メモリ位置は一度に１個のページを組み込むことができる。通常、各ブロックは多数のページを有する。
【００２２】
通常の読み出し操作においては、プロセッサ１６はメモリ位置にアクセスするため読み出しアドレスを出力する。この読み出しアドレスはブロックアドレス部分および残りのアドレス部分を有する。読み出しアドレスのブロックアドレス部分をマッピングテーブルメモリ１２によって物理ブロックアドレスに変換し、フラッシュメモリ１０に供給する。通常、変換には、この論理ブロックアドレスを対応する物理アドレスを読み出すマッピングテーブルメモリ１２のためのアドレスとして用いる。残りのアドレス部分は変換せずにフラッシュメモリ１０へ供給する。より進歩した実施例においては、読み出しアドレスの変換は、そのアドレスのページアドレス部分およびブロックアドレス部分の組み合わせの変換を含む。
【００２３】
図２は書き込み操作のフローチャートである。第１ステップ２１において、プロセッサ１６は、マッピング制御回路１４に対して、書き込み操作を要求する信号を、書き込み操作に適用する論理ブロックアドレスとともに、送る。第２ステップ２２において、マッピング制御回路１４は書き込みに用いる物理ブロックを選択する。より進歩した実施例においては、マッピング制御回路１４は書き込みに用いる物理ブロックおよび物理ページの双方を選択する。選択したブロックおよびページは、別の論理ブロックアドレスには用いない消去ブロックとする、または進歩した実施例においては使用しない消去ページとする。随意に、マッピング制御回路１４は、フラッシュメモリ１０に対して、そのブロックがまだ消去されていない場合、未使用のブロックを消去させる。未使用のブロックのいずれも消去されていない場合は必ずこれを実行する。
【００２４】
マッピング制御回路１４は、選択した物理ブロック（またはページ）を、プロセッサ１６が書き込みを要求する論理ブロック（またはページ）に割り当てる。第３ステップ２３において、マッピング制御回路１４は、新たに割り当てたブロック（またはページ）を考慮して、論理アドレスを物理アドレスにマッピングするための新マッピングテーブルを構築する。ある実施例においては、マッピング制御回路１４によって、マッピングテーブルメモリ１２中のマッピングテーブルを更新し、フラッシュメモリに対して論理ブロック（またはページ）の新しいデータを物理ブロック（またはページ）のメモリ位置に組み込ませる。
【００２５】
第４ステップ２４において、マッピング制御回路１４は、少なくとも１個の組み込んだページを含むマッピングテーブルの格納に割り当てた１組のブロックセットにおける最初のブロックを識別する。
【００２６】
続いて、マッピング制御回路１４は、割り当てたブロックセットにおける最初のブロック中の、順次の最初の未使用ページまたは未使用ページセットをサーチする。第５ステップ２５において、マッピング制御回路１４は、このようなページまたはページセットが見つかったどうかを検証する。見つかった場合、マッピング制御回路１４は第６ステップ２６を実行し、見つかったページまたはページセットに新しいマッピングテーブルを組み込む。マッピング制御回路１４が、上記のブロックセットの最初のブロック中に未使用ページを見つけられない場合、マッピング制御回路１４は第７ステップ２７に分岐し、マッピング制御回路１４は、マッピングテーブルの格納に割り当てたブロックセットのうち次のブロックを選択する。第８ステップ２８において、マッピング制御回路１４は、上記の割り当てたブロックセットのうち次のブロック中において、順次の最初の未使用ページまたはページセットに、新しいマッピングテーブルを組み込む。第９ステップ２９において、マッピング制御回路１４はフラッシュメモリ１０を制御して、割り当てたブロックセットのうち最初のブロックを消去するものとする。
【００２７】
図３は装置の起動のフローチャートである。第１ステップ３１において、マッピング制御回路１４は、少なくとも１個のプログラミングした（組み込んだ）ページを有するマッピングテーブルの格納に割り当てた、ブロックセットの最初のブロックを識別する。続いて、マッピング制御回路１４は、上記の割り当てたブロックセットの最初のブロック中において、順次の最終使用済みページまたはページセットをサーチする。第２ステプ３２において、マッピング制御回路１４は、最終使用済みページからマッピングテーブルをマッピングテーブルメモリ１２にコピーする。第３ステップ３３において、マッピング制御回路１４はシステムの通常動作を開始する。
【００２８】
マッピング制御回路１４は、第９ステップ２９において最初のブロックを消去する前に、第８ステプ２８において新しいマッピングテーブルをフラッシュメモリ１０に組み入れることに留意されたい。もしこのプロセスが何らかの理由で、例えば（一部の）システムへの電力供給が止まることによって、中断される場合、第９ステップが行われることなく、第８ステップ２８のみが実行される危険性がある。マッピングテーブル格納に割り当てブロックのうち一個のブロックが満杯で、これら割り当てたブロックのうち少なくとも他の１個が空でないことを検出することによって、マッピング制御回路１４を起動中にこれを検出するよう構成する。検出した場合、マッピング制御回路１４はなるべく、起動時に完全に満杯ではない割り当てブロックのうち１個のブロックにおける順次の最終使用済みページまたはページセットを使用し、フラッシュメモリ１０に満杯の割り当てブロックを消去させる。代替案として、マッピング制御回路１４は、満杯の割り当てブロックにおける順次の最終使用済みページまたはページセットを用いることができる。この場合、新たに組み込んだデータは失われるが、これは、いずれにせよ図２のプロセスが早期に中断した場合である。
【００２９】
図４（ａ）〜（ｃ）はマッピングテーブル格納に割り当てたブロックセット中におけるページを使用する３段階を示す。各図中に２つのブロック４０,４２の同一セットを示す。マッピングテーブルを組み込んだページをハッチングによって示す。消去した（空の）ブロックはハッチングなしで示す。ある実施例においては、各ページにフラッグビットを組み込み、ページが空かプログラムされているかを表示するようにする。代案として、ブロック中の全てのデータが消去された状態か（例えば論理ビット値１）どうかを検査することによって、空ブロックを検出することができる。また随意に、ＥＣＣ(error correcting code：ブロック中で使用するエラー訂正コード）の場合は、ＥＣＣがエラーを表示するかどうかを検査することによって検出する。代案として、データとともにタグが書き込まれている場合は、有効タグの存在を検査することによって検出する。
【００３０】
例えば、ページをアドレスが増えるにつれより下部に示し、最上部のページは最も低いアドレスを有するようにした。
【００３１】
第１段階（図４ａ参照）において、第１ブロック４０のページの一部にマッピングテーブルを組み込んだ。ブロック４０，４２がこの状態にあるとき、マッピング制御回路１４は、起動中空でないブロック４０中の最下部に示される組み込んだページを用いる。プロセッサ１６が書き込み要求した時は、マッピング制御回路１４は、新しいマッピングテーブルを組み込むため、空でないブロック４０における空ページの最上部に示したものを選択する。
【００３２】
第２段階（図４ｂ参照）において、第１ブロック４０の全てのページにマッピングテーブルが組み込まれ、第２ブロック４２を空にする。この場合、マッピング制御回路１４は、図４ａの場合と同様に起動を行う。プロセッサ１６が書き込み要求したときは、マッピング制御回路１４は、新しいマッピングテーブルを組み込むため、第２ブロック４２中の最初の空ページを選択する。新しいマッピングテーブルを組み込んだ後、マッピング制御回路１４は満杯ブロックを消去し、図４ｃに示す第３段階へ進む。
【００３３】
第３段階（図４ｃ参照）において、第１ブロック４０は空であり第２ブロック４２の一部はプログラムされている。ブロック４０，４２がこの状態のとぎ、ブロックの役割は図４ａと逆転している。
【００３４】
図４ｄは、第２段階（図４ｂ参照）の後に、電力供給が早期に断絶したために生じる状態を示す。一方のブロック４０は満杯であり、他方のブロック４２は空ではない。マッピング制御回路１４が起動中この状態に遭遇した場合、マッピング制御回路１４は満杯ブロックを消去し、満杯ではないブロック４２からマッピングテーブルを用いる。
【００３５】
ある代替的実施例において、マッピング制御回路１４は、マッピングテーブルに付随するバージョン番号を書き込み、このバージョン番号はテーブルを書き込む度毎に増大させする（または所定シーケンスに従って変更する）。この実施例においては、マッピングテーブルの有効バージョンは、最も増進したバージョン番号を有するマッピングテーブルを選択することによって、識別することができる。他の実施例においては、マッピング制御回路１４は、バージョン番号を有する更新（アップデート）を任意の中間ブロックに書き込み、例えば他のブロックが満杯の場合、書き込み後その他のブロックを消去する。
【００３６】
別の実施例においては、マッピング制御回路１４は、起動時に正しいブロックの選択を助けるよう、新しいブロックに書き込む前に満杯ブロックに「ダーティ」フラッグをセットするように構成する。この場合、マッピング制御回路１４は、最初に、ダーティのマークが付いていないブロックから最終マッピングテーブルを用いようとする。このブロックが（エラーによって）空の場合、マッピンング制御回路１４はこのダーティブロックに頼る。
【００３７】
バージョン番号は周期的に変化させることができる。正しいブロックを見つけ出すため満杯および空ブロックを検査する代わりに、バージョン番号をブロック中のマッピングテーブルを有するページの位置と組み合わせて用いることができる。この場合、短い周期、例えば４個の異なるバージョン番号で十分である。上述の実施例においては、整数個のマッピングテーブルをブロックに当てはめてきたが、当然これは必ずしも必要ではない。マッピングテーブルのサイズが、ブロックを整数個のマッピングテーブルで満たすことができないとき、マッピング制御回路１４は、一つのブロックから他のブロックにオーバーフローする最終マッピングテーブルを書き込む。この場合、もし追加のマッピングテーブルがオーバーフローしているマッピングテーブルの後に格納されていない場合、マッピング制御回路１４は、起動時にオーバーフローしているマッピングテーブルを使用し、またマッピング制御回路１４は、次のブロックが満杯になるまでマッピングテーブルを書き込まれるまでは、第１ブロックを消去しない。
【００３８】
上述したところは、１個のフラッシュメモリに対してマッピングテーブルを格納すると仮定して説明した。他の実施例においては、多数のマッピングテーブルを論理アドレスの対応セグメント（範囲）に対して供給する。
【００３９】
この他の実施例においては、マッピング制御回路１４は、マッピングテーブル格納に割り当てるブロックセットにおけるそれぞれ独立して選択可能なページから、それぞれに対応する範囲に対してマッピングテーブルをプログラムし、ロードする。さらに他の実施例においては、マッピング制御回路１４は、マッピングテーブルをフラッシュメモリ１０のページに適用して格納するセグメントの識別をプログラミングするよう構成する。起動中、マッピング制御回路１４は、割り当てたブロックをサーチして、対応するセグメントのための識別を有する順次の最終ページを見つけ出す。好適には、マッピング制御回路１４は、アドレス変換中に使用するため、これらのページをマッピングテーブルメモリ１２にコピーする。
【００４０】
プロセッサ１６が新しいページの書き込みを要求するとき、マッピング制御回路１４は新しいマッピングテーブルを上述のように生成するが、プロセッサ１６が書き込みを要求する論理アドレスを有する、セグメント中の論理アドレスのみのために生成する。したがって、マッピング制御回路１４は、そのセグメントに対する新マッピングテーブルを、マッピングテーブル格納に割り当てたブロックセット中のマッピングテーブルに追加するだけである。例えば、異なるセグメントのマッピングテーブルを、図４ａ，ｂにおいて異なる形式のハッチングで示した。
【００４１】
図５は、割り当てブロックが満杯のとき書き込み中にどのようなことが起こるかを示す。この場合、マッピング制御回路１４は、更新したセグメントに対する新マッピングテーブルを、マッピングテーブル格納に割り当てたブロックセットのうち空のブロック４２に書き込む。さらに、幾つかの実施例においては、マッピング制御回路１４は、他のセグメントに対する現マッピングテーブルを、空ブロック４２にコピーする。これを図中に矢印で図式的に示したが、もちろん、これらマッピングテーブルの内容を、フラッシュメモリ１０からコピーする代わりに、マッピングテーブルメモリ１２からコピーすることができる。これに続いて、マッピング制御回路１４はフラッシュメモリ１０に満杯ブロック４０を消去させる。これによって、マッピング制御回路１４は、起動中どのブロックが有効なマッピングテーブルを有しているか識別することができる。
【００４２】
古いブロック４０が誤って消去されなかった場合、マッピング制御回路１４は、起動の際に、満杯ブロック４０が空でないブロック４２と組み合わさっていることを検出し、満杯ブロックを消去する。好適には、マッピング制御回路１４は、まず全てのセグメントに対してマッピングテーブルが満杯でないブロック４２中に格納されていることを検証する。もしそうでなければ、マッピング制御回路１４は、まず満杯ブロック４０におけるコピーされていないセグメントの逐次的な最終マッピングテーブルをサーチし、これらコピーしていないマッピングテーブルを満杯でないブロック４２にコピーしてから満杯ブロック４０を消去する。
【００４３】
代案として、まず新マッピングテーブルを空ブロック４２に書き込むとき、他のセグメントに対するマッピングテーブルをコピーせず、また満杯ブロック４０を消去しない。この場合、誤って断線した場合でも、マッピング制御回路１４は起動中に依然としてブロックを読み出すことができる。満杯ブロック４０の消去は、他方のブロック４２が満杯になるまで延期することができ、これはすなわち、起動中マッピング制御回路１４が依然として、どのブロックが満杯でないかを検出することによって、どのブロックが最後に書き込まれたブロックかを検出することができるからである。この代替案においては、マッピング制御回路１４は、満杯ではないブロックがまさに満杯になろうとするときのみ、満杯ブロック４０を消去する必要がある。好適には、この場合、マッピング制御回路１４は、まず、満杯ではないブロック４２にマッピングテーブルがまだ一つも格納されていないセグメントがあるとしたら、このセグメントに対してマッピングテーブルをコピーする。すなわち、満杯ではないブロック４２にまだプログラムされていなかったマッピングテーブルを追加した後に、満杯ではないブロック４２が一つのフリーページ用に十分なスペース残量となるまで、消去を延期することができる。
【００４４】
別の実施例においては、マッピングテーブル格納に割り当てたブロックセットは２個より多くのブロックを有するものとする。このことは、例えばブロックに格納したデータ（例えばマッピングテーブル）が大き過ぎて一つのブロックから他のブロックにデータがオーバーフローする場合に有利である。この場合、例えば割り当てブロックを所定の順序で用いることができる。この場合、好適には、ブロックセットのうち少なくとも直近の最終更新ブロックを最初に消去し、マッピングテーブル格納に再利用する。起動時、マッピング制御回路１４は、空ブロックを見つけ出し、それを用いてシーケンスの始点／終点を決定し、そこからマッピング制御回路１４は最新バージョンの格納データを見つけ出す。
【００４５】
図６は、異なるブロックを異なるセグメントに用いる実施例を示す。この場合、４個のブロック６０を同数のセグメント用に用意し、スペアブロック６２をブロック６０のうち１個が満杯になる場合のために用意する。動作にあたり、マッピング制御回路１４が書き込み要求を処理するとき、マッピング制御回路１４は、書き込み要求によって変化したセグメントのための新マッピングテーブルを、このセグメントの先行マッピングテーブルを有するブロックに組み込む。そのセグメントのブロック６０が満杯の場合、マッピング制御回路１４は新マッピングテーブルをスペアブロック６２へ組み込む。このとき、スペアブロックはこのセグメント用のブロックとなり、続いてマッピング制御回路１４はセグメントの古いブロックを消去する。ある一つの実施例においては、セグメントの識別を新ブロックへ組み込み、また代案として、このような識別を、ページを書き込むときにブロックの各ページに組み込むことができる。
【００４６】
起動中、マッピング制御回路１４は、各割り当てブロック６０,６２を検査してどのセグメントにブロックを用いているか決定する。ブロックから逐次的な最終マッピングテーブルをセグメントのためのマッピングテーブルとして使用する。電力遮断のために、セグメント用のデータを有する２個の割り当てブロック６０，６２がある場合、マッピング制御回路１４は、満杯ではないブロックから選択し、他方のブロックを消去し、満杯ではないブロックから逐次的な最終マッピングテーブルを用いる。
【００４７】
ある一つの実施例においては、マッピングテーブルメモリ１２を、全てのセグメント用のテーブルを並列的に有し、メモリマッピングテーブルはいかなる論理アドレスも直ちに変換できるものとする。この実施例においては、マッピング制御回路１４は、全てのセグメントのためのマッピングテーブルをマッピングテーブルメモリ１２にロードする。ある代替実施例においては、マッピングテーブルメモリ１２は、セグメントの限られたサブセットのみに対する、例えば一度に１セグメントのみに対するマッピングテーブルを格納する。この実施例においては、マッピング制御回路１４は、マッピングテーブルメモリ１２に存在しないマッピングテーブルのセグメントに論理アドレスを収容するとき、割り当てブロック６０，６２または４０，４２からのマッピングテーブルを用いて、あるセグメント用のマッピングテーブルを他のセグメント用のマッピングテーブルと置換する。
【００４８】
これまで、整数個のセグメント用マッピングテーブルをブロックに当てはめる実施例を示してきたが、当然これは必ずしも必要ではない。セグメント用のマッピングテーブルのサイズが、ブロックを整数個のセグメント用マッピングテーブルで満杯にできないとき、マッピング制御回路１４は、図５の場合においては、一方のブロックから他方のブロックにオーバーフローさせて最終セグメント用のマッピングテーブルを書き込むことができる。この場合、もし追加のマッピングテーブルをオーバーフローしているマッピングテーブルの後に格納されていない場合、マッピング制御回路１４は、起動時にオーバーフローしているマッピングテーブルを使用し、またマッピング制御回路１４は、次のブロックが満杯になるまでマッピングテーブルを書き込まれるまでは、第１ブロックを消去しない。図６の場合、セグメント用の満杯マッピングテーブルはなるべく新たに割り当てたブロックに書き込み、こうして割り当て先行の割り当てブロックを直ちに空にする。
【００４９】
ある実施例においては、所定ブロックセットをマッピングテーブル格納に割り当てるものとする。この実施例においては、所定ブロックセットは所定アドレスに配置し、マッピンング制御回路１４はこれら所定アドレスにおけるブロックを調べるよう構成することができる。しかし、このことは割り当てブロックがより早く消耗するという弱点がある。代替案として、変更したブロックまたは複数のブロックをマッピンテーブル格納に割り当てることができ、ＲＡＭでバックアップするメモリを設け、割り当てブロックまたは複数のブロックを示すポインタを格納する。
【００５０】
ある代替実施例においては、リンク付けしたリスト構造を用いてマッピングテーブル格納に割り当てたブロックセットを画定する。このことを図７ａに示す。この場合、フラッシュメモリ７１の全体をブロックに分割して図式的に示す。フラッシュメモリ中の所定物理アドレス（例えばアドレス０）におけるベースブロック７０を、１個またはそれ以上のベースポインタを格納するために用いる。このベースブロックの拡大部分７０ａをベースポインタメモリ位置７２とともに示す。このメモリ位置からのベースポインタは、他のポインタを格納する他のブロック７４を指し示す。この他のブロックの拡大部分７４ａをベースポインタのメモリ位置７５とともに示し、このメモリ位置７５は、マッピングテーブル格納に割り当てたブロック７６を指すポインタを有する。
【００５１】
起動中、マッピング制御回路１４は、まず、ベースブロック７０からポインタ７２をロードし、このアドレスを用いて、他のブロック７４のアドレスを指定し、ブロック７４からマッピング制御回路１４はマッピングテーブル格納に割り当てたブロック７６を指すポインタをロードする。マッピング制御回路１４は、順次の使用のためにこのポインタを保存し、ポインタを用いて、マッピングテーブル格納に割り当てたブロック７６からの現マッピングテーブルを、マッピングテーブルメモリ１２にロードする。このことは、例えば上述した方法のうち任意な方法を用いて実行することができる。
【００５２】
この構造は、異なる物理ブロックを、マッピングテーブル格納ブロック７６として割り当てることができ、同一ブロックを他のブロックよりずっと頻繁に消去することを防ぐようにすることができるという利点を有する。割り当てブロック７６を変更する度毎に、新しいポインタを、割り当てブロック７６を指すブロック７４に書き込む。好適には、少なくとも置換可能なブロック（割り当てブロック７６および中間ブロック７４）はそれぞれ消去された回数を示すカウンタ値を格納し、マッピング制御回路１４は、カウンタ値が閾値を超える時、関連するブロックを異なるブロックに置換するよう構成することができる。カウンタ値は、例えばブロック消去後に書き込む度毎に、１ずつ増やすことができる。
【００５３】
同様に、時間の経過につれ、異なる物理ブロックを中間ブロック７４に用いることができ、新しいポインタ値を格納する前に同一ブロックを頻繁に消去しすぎるのを防ぐ。中間ブロック７４を変更する度毎に、新ポインタ７２を、中間ブロック７４を指すベースブロック７０に書き込む。中間ブロック７４の変更は、割り当てブロック７６の変更より頻繁に行わないことに留意されたい。ある一つの実施例においては、割り当てブロック７６をＮ１回（例えばＮ１＝８）消去する度に、異なる物理ブロックを割り当てブロック７６用に選択する。このとき、中間ブロック７４は、割り当てブロックをＮ２回（例えばＮ２＝１０００００、より一般的には、ブロックを消去でき依然データ格納に使用できる最大回数以下の任意の整数）消去する毎に一回だけ更新を必要とする。中間ブロック７４に対応する物理ブロックをＮ２回消去したとき、この物理ブロックを置換する。この場合、このような置換は、割り当てブロック７６をＮ１×Ｎ２回消去した後に生ずる。このようにして、中間ブロック７４の消耗がより遅くなり、またベースブロック７０の消耗もより一層少なくなる。
【００５４】
代替案として、中間ブロック７４を用いず、ベースブロック７０におけるポインタ７２が割り当てブロック７６を直接指し示すようにすることができる。これにより、フラッシュメモリのより効率的な使用およびより迅速なマッピングテーブルの読み出しが得られる。しかし、ベースブロックの消耗は増大する。一定時間後、ポインタ値を有するブロックは消去しなければならず、このことは消耗の増大を不可避的にもたらすことに留意されたい。そのような消耗を軽減するために、中間ブロック７４における中間ポインタをベースブロック７０と割り当てブロックとの間で使用する。
【００５５】
別の代替案として、中間ブロックのチェーン（連鎖）を使用することができ、ベースブロック７０におけるポインタ７２はチェーンの最初のブロックを指し、割り当てブロック７６を指し示す最終ブロックを除き、各後続ブロックはチェーンにおけるそれに続くブロックを指し示すものとする。この方法においては、ベースブロックの消耗を軽減することができる。割り当てブロックからの中間ブロックの数を増やすにつれ、これら中間ブロックを更新する必要がより少なくなる。このようにして、所定物理アドレスを有するベースブロック７０を、消耗を引き起こすこのような頻繁な更新から防護することができる。
【００５６】
固定した所定長さのチェーンを用いることができる。代替案として、動的に調節可能な長さのチェーンを用いることができる。この場合、チェーンにおける最終中間ブロックは、そのポインタが割り当てブロックを指し示す表示を格納する（または、チェーンの終端から所定距離にあるブロックは、チェーンに沿って所定距離にあるブロックがそのようなポインタを格納していることを示すようにする。）ある実施例においては、閾値を超えた更新頻度を検出したとき（例えば、ベースブロック７０を消去した回数が閾値Ｔを超えるとき）、マッピング制御回路１４はチェーンの長さを増加させる。このようにして、チェーンの長さを使用タイプに適応させ、ベースブロック７０の過度の消耗を防ぐことができる。ある実施例においては、チェーン長の延長を用いて、ベースブロック７０を閾値回数より多く更新するのを防ぐ。これは、例えば、ベースブロック７０を、例えば閾値回数（Ｔ＝１０００００）更新したときチェーンにおける付加的な中間ブロックを追加し、最後にベースブロック７０を消去した後、ベースブロック７０に新ブロックを示すポインタを書き込み、新中間ブロックに次の中間ブロックを示すポインタを書き込むことによって、実現することができる。新中間ブロックを例えば閾値回数であるＴ回消去した場合、新中間ブロックにベースブロック７０の役割を果たさせながら、これを繰り返すことができる。
【００５７】
さらに他の実施例においては、多数のブロックを、マッピングテーブルまたはマッピングテーブルの一部を格納するために割り当てる。このことは、例えば、古い割り当てブロックにおける古いマッピングテーブルを消去する前に、新マッピングテーブルを新割り当てブロックに格納する実施例に適用する。代替案として、このことを、例えば、論理ブロックアドレスの対応するセグメント用のマッピングテーブルを対応するブロックに格納する実施例に適用する。
【００５８】
図７ｂはこの実施例を示す。この実施例においては、ベースブロック７０は、各対応する中間ブロック７４，７８を示す第１および第２のポインタ７２ａ，７２ｂを有し、同様に各中間ブロックは各割り当てブロック７６，７９を示すポインタ７５，７５ａを有するものとする。この実施例においては、起動中、マッピング制御回路１４はまずベースブロック７０からポインタ７２，７２ａをロードし、これらのポインタを用いて他のブロック７４，７８のアドレス指定をし、マッピングテーブル格納用に割り当てたブロック７６,７９を指し示すポインタをロードする。マッピング制御回路１４は、これらポインタをその後使用するため保存し、これらポインタを用い現マッピングテーブルまたはそのセグメントを、マッピングテーブルメモリ１２にマッピングテーブルを格納するために割り当てたブロック７６から、ロードする。このことは、例えば上述した方法のうち任意の方法を用いて実行することができる。
【００５９】
割り当てブロック７６,７９のうち一方の代わりに他のブロックを使用してマッピングテーブルを格納しようとし始めるとき、マッピング制御回路１４は、中間ブロック７４，７８におけるポインタを変更し、このポインタが置換した割り当てブロック７６，７９を指し示すようにする。好適には、マッピング制御回路１４は、ポインタを変更する前に新しいマッピングテーブル（またはマッピングテーブルのセグメント）を新たに割り当てたブロックに格納する。
【００６０】
２個のポインタ７２，７２ａをベースブロック中に格納する構造を示したが、当然のことながら代替案も可能である。例えば、単独のポインタを単独の中間ブロックに格納して２個のポインタを使用する代わりに、単独の中間ブロックに割り当てブロック７６,７９を指し示す２個のポインタを格納することができる。これには必要なブロックが少なくなるという利点があるが、消去操作がより多く必要なためより多くの消耗が発生する。別の実施例においては、２個の割り当てブロック７６,７９より多くのブロックを用いるとき、２個より多くのポインタを格納してもよい（ベースブロック７０または中間ブロック７４，７８中に）。代替案として、互いに所定の物理的関係を有するブロック（例えば連続する物理アドレス）を中間ブロック７４，７８または割り当てブロック７６，７９に用いるとき、１個のポインタを中間ブロック７４，７８の各個にまたは１個の割り当てブロック７６，７９の各個に用いることができる。
【００６１】
上述の実施例においては、有効なポインタのみを各ブロックに格納することを示したが、このことは、マッピング制御回路１４がベースブロック７０および中間ブロック７４，７８を、これらのブロックにおけるポインタ値を変更する度毎に、消去および上書きする（または中間ブロック７４，７８を置換する）ことを意味する。代替案として、先行して格納したポインタを消去せずに、マッピング制御回路１４が各新ポインタ値を、ベースブロック７０内における新ページ、またはポインタを有する中間ブロック７４，７８に、書き込むよう構成することができる。
【００６２】
図７ｃは、順次のポインタ７２，７５のために順次のページを使用することを示す。ポインタ値を有するページをハッチングで示す。各場合において、最下部のハッチング付きページ（このページの最高位アドレスがポインタ値を有する）が有効ポインタ値を有する。より高位のページ（より低位アドレスを持つ）はより古い（無効の）ポインタ値を有する。ある代替実施例においては、マッピング制御回路１４は、ポインタに付随するバージョン数を書き込み、このバージョン数はテーブルを書き込む（さもなければ所定シーケンスに従って変更する）度毎に増やすものとする。この実施例においては、マッピングテーブルの有効バージョンを、最も進んだバージョン数を有するマッピングテーブルを選択することによって、識別することができる。
【００６３】
例えば、ある所定シーケンスのページにおける空ページが続くポインタを有するページをサーチすることによって、起動時にマッピング制御回路１４は、有効（最も新しく格納した）ポインタ値を無効ポインタ値から識別する。この所定シーケンスは、例えば物理アドレスのシーケンスとすることができる。このサーチは、例えば二分探索法（最初にブロックの中間のページが空かどうか検査し、つぎに、この最初に検査したページがそれぞれ空または空でない場合、前半または後半のページの中間ページを検査し、検査するページの両側半分に検査済みページが隣り合うまでこの作業を続ける）とすることができる。この実施例は、起動時により長い探索時間を使うことによって、必要な消去操作をより低頻度にできるという利点がある。
【００６４】
ある代替実施例においては、マッピング制御回路１４は、ポインタに付随するバージョン数を書き込み、このバージョン数は新ポインタを書き込む（または所定シーケンスに従って変更する）度毎に増やすものとする。この実施例においては、ポインタの有効バージョンを、最も進んだバージョン数を有するポインタを選択することによって、識別することができる。さらに別の実施例においては、マッピング制御回路１４はバージョン数を有する更新を任意の中間ブロックへ書き込み、書き込み後他方のブロックを、例えばその他方のブロックが満杯の場合、消去する。
【００６５】
バージョン数を周期的に変更することができる。適切なブロックを見つけるために満杯および空ブロックを検査する代わりに、バージョン数をブロック中のポインタを有するページの位置と組み合わせて用いることができる。この場合、短いサイクル、例えば４個の異なるバージョン数で十分である。
【００６６】
別の実施例においては、マッピング制御回路１４は、新しい中間ブロックへ書き込む前に、満杯中間ブロック中に「ダーティ」フラッグをセットし、起動時に適切なブロック選択を補助するよう構成する。この場合、マッピング制御回路１４は、まずダーティのマークが付いていない中間ブロックを用いようとする。このブロックが（エラーのため）空の場合、マッピング制御回路１４はダーティブロックを用いる。
【００６７】
多数の有効ポインタ値を（図７ｂの場合のように）並列的に用いる実施例においては、ポインタ値は、多数の並列的なポインタ値におけるランクの識別を伴って格納することができる。この場合、起動時に、マッピング制御回路１４は有効（最も新しく格納した）ポインタ値をサーチし、有効ポインタ値の各ランクは、所定シーケンスにおいて同一ランクの他のいかなるポインタより最も進んだ位置にあるものとする。
【００６８】
マッピング制御回路１４がポインタ値格納のために全てのページを使用してしまっており、新たにポインタ値を書き込まなければならないとき、マッピング制御回路１４はそのブロックを消去し、頂部から再度スタートする。図８（ａ）〜（ｃ）は、多数のブロックをポインタ値に使用する代替実施例を示す。ベースブロック７０中のポインタ７２，８２、第１中間ブロック７４および第２中間ブロック８４を参照する。最初、図８ａに示すように、ポインタ値を変更する度毎に、変更したポインタ値７５を第１中間ブロック７４中の新ページに書き込み、第２中間ブロック８４は空のままとする。第１中間ブロック７４が満杯の時、マッピング制御回路１４は、図８ｂに示すように次の変更したポインタ値７５を第２中間ブロック８４の最初のページへ書き込み、続いて図８ｃに示すように前のブロックのポインタ値を消去する。
【００６９】
このようにして、更新の中断によるエラーを簡単に回復することができる。起動時、マッピング制御回路１４は第１中間ブロック７４が満杯かどうか検査し、満杯の場合、第２中間ブロック８４から１個以上のポインタが使用可能か検査する。使用可能である場合、マッピング制御回路１４は第２中間ブロック８４から最後のポインタ値を用い、使用不能の場合、マッピング制御回路１４は第１中間ブロック７４から最後のポインタ値を用いる。第１中間ブロック７４が空の場合、マッピング制御回路１４は第２中間ブロック８４から最後のポインタ値を用いる。
【００７０】
第２中間ブロック８４へのポインタ値追加および使い古しの第２中間ブロック８４の消去は期間を拡張し、例えば多数のポインタ値を第２中間ブロック８４に書き込んでしまうまで遅延させることができることに留意されたい。それは、他方の中間ブロックが空でない場合、この他方の中間ブロックから最後のポインタ値を用い、また他方の中間ブロックがからである場合、先行の中間ブロックから最後のポインタ値を用いて中間ブロックが満杯かを検査することによって、マッピング制御回路１４は起動時にどちらの中間ブロックが有効ポインタ値を有するかを決定するよう構成することができるからである。
【００７１】
この技術はベースブロック７０にも応用することができる。例えばベースブロック７０の全てのページを使用している時、マッピング制御回路１４は次のポインタ値を所定の予備のベースブロック（例えばブロックアドレス１を有するブロック）中の最初のページへ書き込み、続いてベースブロック７０を消去する。例えば第２中間ブロック８４の変更をする場合、マッピング制御回路１４は、（必要ならば）ポインタ値８２を古い中間ブロックへ書き込んだ後、ポインタ値を第２中間ブロック８４へ追加し、第２中間ブロック８４中の最初のページへ書き込む。
【００７２】
図９ａは、例えば図７ｂの場合のように、１個以上の有効ポインタ値を並列的に用いる実施例を示す。並列的なポインタ値は各ランクと対応する（例えば、連続する論理アドレスの範囲におけるマッピングテーブルの連続するセグメントのランクに対応する。つまり、並列的なポインタは第１および第２のポインタでラベル付けする）。対応する各中間ブロックを、対応する各ランクのポインタ値の格納に割り当て、割り当てランクを識別する情報（例えばランクに対応する数）をポインタ値を有する各中間ブロック中に格納する。
【００７３】
有効な並列ポインタは、対応する各中間ブロック７４，７８の最後に占有した位置にそれぞれ格納する。追加ポインタ９２をベースブロック７０中に格納し、ポインタ９２は追加中間ブロック９４を指し示すものとする。この追加中間ブロック９４は、他の中間ブロック７４，７８がいずれも満杯でない間、空のままとする。この場合、マッピング制御回路１４は新ポインタ値を中間ブロック７４７８中の順次のページに書き込む。中間ブロック７４，７８の一方が満杯となり、新ポインタ値を追加しなければならない時、マッピング制御回路１４は新ポインタ値を追加中間ブロック９４に書き込む。加えて、マッピング制御回路１４はポインタのランクの識別を追加ブロック９４へ書き込む。図９ｂに示すように、続いてマッピング制御回路１４は満杯の中間ブロックを消去する。今度はこの消去したブロックは追加中間ブロックの役割を担う、つまり、中間ブロックが再度満杯となり、ポインタ値を追加しなければならない時、マッピング制御回路１４はポインタ値をその時点で空のブロックへ書き込み、満杯ブロックを消去する。
【００７４】
起動時、マッピング制御回路１４はベースブロック７０からポインタを読み込み、どのポインタが各ランクの中間ブロックを指しているか決定する。このような２個の中間ブロックが同一ランクに対応している場合、マッピング制御回路１４はそれらの中間ブロックのうち一方、すなわちポインタを割り当てブロックにロードするために満杯でも空でもない方、を選択し、他方の中間ブロックが満杯の場合この他方の中間ブロックを消去する。そのランクの一方のブロックが満杯であり、他方のブロックが空の場合、マッピング制御回路１４は満杯ブロックから最後の書き込みポインタ値を用いる。
【００７５】
図１０（ａ），（ｂ）は、異なるランクのポインタ値１０５ａ，１０５ｂを同一ブロック中に一緒に格納し、各ポインタはそのランク識別を付随するものとした実施例を示す。この実施例においては、マッピング制御回路１４は、全てのランクの新ポインタ値を同一中間ブロック７４へ満杯になるまで追加する。あるランクの次の新ポインタ値を書き込まなければならないとき、マッピング制御回路１４はそのランクの新ポインタ値を追加ブロック９４に書き込み、他の１個または複数個のランクの１個または複数個の有効ポインタ値を追加ブロック９４にコピーする。続いて、マッピング制御回路１４は満杯ブロックを消去する。起動時、マッピング制御回路１４は、ベースブロック７０中のポインタ値を用いて中間ブロックを確定し、空でも満杯でもない中間ブロックを探索し、これで全てのランクのポインタ値が得られない場合、そのブロックから最後の書き込みポインタ値を用い、これが満杯の場合、マッピング制御回路１４は、他方のブロックから残っているランク全ての最後の書き込みポインタ値をロードする。
【００７６】
当然のことながら、有効ポインタ値を、１個より多くのあり得るブロックから選択しなければならない任意の実施例において、マッピング制御回路１４は、空でない他のブロックが使用可能の場合における満杯ブロックの消去、バージョン数の使用、ダーティフラッグの使用等、任意のメカニズムを用いて、そのブロックが使用可能か確定するよう構成することができる。また、不整合が生じる場合、マッピング制御回路１４は最後の信頼性のあるバージョンを識別することができる。例えば、ポインタが無効なマッピングテーブル（例えば、空のマッピングテーブルまたは異なる論理アドレスを同一の物理アドレスへマッピングするテーブル）を参照していることを、マッピング制御回路１４が判定する場合、マッピング制御回路１４は旧バージョンのポインタを用いることができる。情報の置換を完了する前には、マッピング制御回路１４が情報を消去しないことを確実にしたいとき、このことは取り得る最良のエラー修正が得られる。
【００７７】
他の実施例においては、更新の回数を減らすものとする。これは、マッピングテーブルに関連して、マッピングテーブルを更新するとき、そのマッピングテーブル中に入力すべきブロックを特定する、「フリー」ブロックのリストを格納することによって実行する。このようにして、もし論理アドレスを第１ブロックの物理アドレスにマッピングし、第１ブロック中のデータをつぎに更新する間にマッピング制御回路１４がその第１ブロックを第２ブロックに置換する（例えば第１ブロックのこれ以上の消耗を回避するために）ことを選択する場合、マッピング制御回路１４はフリーリストから第２ブロックを選択し、論理アドレスの識別子（例えば「タグ」）を第２ブロック中に格納する。この場合、マッピング制御回路１４は新マッピングテーブルを書き込むことを省略する。代わりに、次の起動時、マッピング制御回路１４は古いマッピングテーブルに関連して格納したフリーリストを用いて、フリーリストにおける任意のブロックを更新に使用したかどうかを決定する。使用していた場合、マッピング制御回路１４はマッピングテーブルの修正を、これらのブロック中における論理アドレスの識別子から、推測する。マッピングテーブルの新バージョンは、フリーブロックリストの全てのブロックを使用した時のみ、格納する必要がある。
【００７８】
図１１は、この実施例に用いる、マッピングテーブル情報を有するメモリからのブロック１１０を示す。このブロックは、連続バージョン１１２ａ-ｃのマッピングテーブルを有し、各バージョンには、フリーブロックのアドレスを有する「フリーリスト」１１４ａ〜ｃが付随する。最後のバージョンのマッピングテーブル１１２ｃおよびそれに付随するフリーリスト１１４ｃは現バージョンと称する。動作にあたり、アドレスが現バージョンのマッピングテーブル１１２ｃ中に現れる物理ブロックを、置換ブロックを用いて更新しなければならないとき、マッピング制御回路１４は関連するフリーリスト１１４ｃから第１利用可能アドレスを用い、第１使用可能アドレスによってアドレス指定されたブロックに更新を書き込む。さらに、マッピング制御回路１４はこの新ブロックに、更新を適用する論理ブロックアドレスを識別するタグを書き込む。マッピング制御回路１４は、新ブロックにおける更新を完了した後、現マッピングテーブル１１２ｃ中に依然現れる古いブロックを消去する。
【００７９】
好適には、これに応じて、マッピング制御回路１４はマッピングテーブルメモリ１２中のマッピングテーブルを更新する。マッピング制御回路１４が、現フリーリスト１１４ｃにおける全てのブロックを更新に使用したことを検出するとき、マッピング制御回路１４は、新バージョンのマッピングテーブルおよび消去した古いブロックのリストを古いフリーリスト１１４ｃの後のブロック１１０内に（またはマッピングテーブルデータに用いる別のブロック内に）書き込む。好適には、各フリーリストは多数のブロックのアドレスを有するものとする。この場合、新バージョンのマッピングテーブルおよびフリーリストはなるべく、古いフリーリスト１１４ｃを使い果たしてから１回のみ書き込むと好適である。
【００８０】
起動時、マッピング制御回路１４は現バージョンのフリーリスト１１４ｃを、例えばブロック１１０中の最後の空でないページをサーチすることによって、読み出す。つぎに、マッピング制御回路１４はこのフリーリスト１１４ｃにおけるアドレスでアドレス指定されたページを調べ、これらページにデータが書き込まれているかどうか決定する。もしデータが書き込まれていれば、マッピング制御回路１４は、タグから、どの修正を現バージョンのマッピングテーブルへ適用しなければならないかを確定する。このようにして、１個以上の修正を確定し、各修正によって論理ブロックのアドレスおよびその論理ブロックのための更新したデータを有する物理ブロックのアドレスを識別する。ある実施例においては、マッピング制御回路１４は、ブロック１１０から現バージョンのマッピングテーブル１１２ｃを、マッピングテーブルメモリ１２にコピーし、マッピングメモリ１２中のマッピングテーブルに修正を適用する。別の実施例においては、マッピング制御回路１４はマッピングメモリ１２内に修正のリストを格納し、これらの修正を、ブロック１１０からロードするとき、マッピングテーブルの入力に適用する。
【００８１】
好適には、マッピング制御回路１４はフリーリスト１１４ｃからブロックを用い、これらのブロックのアドレスがフリーリスト１１４ｃ中に現れるシーケンス（順番）で更新する。この場合、起動時マッピング制御回路１４は、好適には、ブロックのアドレスがフリーリスト１１４ｃ内で出現する順番で更新するため、フリーリスト１１４ｃにおけるブロックを検査し、ブロックを更新していないことを確定した時点で検査を止めるようにする。これにより起動速度を上げることができるが、ほんの一部のブロックがフリーリスト上に現れるだけで、そのようなシーケンスを用いなくても起動は非常に速い。
【００８２】
好適には、現マッピングテーブル１１２ｃに出現する古い各ブロックを、更新バージョンのブロックを完全に書き込んだ時点で、消去する。このようにしてデータが紛失しないようにする。しかし、新バージョンのマッピングテーブルおよびフリーリスト（このフリーリスト中には全ての消去したブロックが現れるようにすると好適である）を書き込まれる直前まで、消去を遅らせることができる。また、マッピングテーブル１１２ａ〜ｃおよびフリーリスト１１４ａ〜ｃを交互に格納する実施例を説明したが、マッピングテーブルとフリーリストとの間の関連は他の方法、例えばバージョン数を双方に盛り込むことによって実現でき、この場合、マッピングテーブルおよびフリーリストを任意に格納することができる。また、マッピングテーブルおよびこれに関連するフリーリストは、例えばこの関連を生ずるよう同一シーケンスで、異なるブロック中に格納することができる。
【００８３】
この技術は上述の実施例全てを組み合わせて、またはそれ単独で、適用することができると理解されたい。例えば、多数のブロックを使用して、フリーリストおよび関連するマッピングテーブルのバージョンを格納することができ、新ブロックへ新バージョンを書き込んだ後のみ満杯ブロックを消去し、最新バージョンは、起動時にサーチすることによって見つけることができる。
【００８４】
別の実施例として、セグメント化したマッピングテーブルを用いることができ、この場合、更新したセグメントの新バージョンを格納する必要がある。この場合、対応する各フリーリストを対応するセグメントに使用することができ、セグメントのブロックの更新をセグメントのフリーリストを使用して実行する。しかし好適には、全てのセグメントに共通のフリーリストを使用し、任意セグメントのブロックの更新を、全てのセグメントが共有する同一のフリーリストを用いて実行する。これにより、格納する必要のあるマッピングテーブルの更新回数を減らすことができる。この場合なるべく、各セグメント中で参照するブロックのアドレスには何ら制限が課されず、それはセグメントのマッピングテーブル中において、全てが所定アドレスビットの同一アドレス値を有する各物理ブロックセットに各セグメントをマッピングするときよりも、若干長いアドレスを要することを意味することに留意されたい。
【００８５】
さらに、セグメントを用いる時、ある実施例においては、マッピングテーブルメモリ１２は一部のセグメントのみの（例えば一個のセグメントのみの）マッピングテーブルの一部を取得する。これにより、小さいマッピングテーブルメモリ１２を使用することができるようになる。この場合、全てのセグメントの修正は、取得したマッピングテーブルとともに、マッピングテーブルメモリ１２内に格納すると好適である。この場合、マッピング制御回路１４は、必要時、新セグメントのマッピングテーブルを、フラッシュメモリのブロックからマッピングテーブルメモリ内にロードし、マッピングテーブルメモリ１２内に格納した修正を適用する。さらにある実施例においては、マッピング制御回路１４は、フラッシュメモリ１０からセグメントのマッピングテーブルをロードする前に、修正を用いて論理アドレスをマッピングしようとする構成することができる。これによりアクセス速度を向上させることができる。
【００８６】
他の実施例として、ポインタチェーンを使用して、マッピングテーブルおよびフリーリストを格納するブロック１１０（またはブロックセット）を識別する。このようにして、ブロック１１０(または、マッピングテーブルおよびフリーリストを一緒にまたは個別に格納するためのブロックセット）を、消耗の問題なく、交換することができる。
【００８７】
フリーリストの使用もポインタチェーンに適用することができる。ある実施例においては、チェーン中の中間ブロックを指し示すポインタを、新しい中間ブロックに用いるブロックを指し示すポインタのフリーリストに関連付けする。新しい中間ブロックを生成するとき、フリーリストにおいて識別されるブロックを用い、新ポインタ値をこのブロックに書き込む。さらに、何らかの情報をこのブロック中に有効ブロックとして格納し（例えばバージョン数を盛り込むことによって）、中間ブロックを指し示すベースブロック中のポインタを更新しない。フリーリストを使い果たした場合のみ、ベースブロックにおいて、新中間ブロックのポインタ値およびフリーリストを更新する。
【００８８】
ここまで整数個のマッピングテーブルおよびフリーリストをブロックに当てはめる実施例を説明したが、このことは必ずしも必要ではないと理解されたい。マッピングテーブルおよびフリーリストのサイズが、ブロックを整数個のマッピングテーブルおよびフリーリストで満杯にできないとき、マッピング制御回路１４は、一方のブロックから他方のブロックにオーバーフローする最終マッピングテーブルおよびフリーリストを書き込むことができる。この場合、それ以上のマッピングテーブルおよびフリーリストがオーバーフローするマッピングテーブルの後に格納されていない場合、マッピング制御回路１４は起動時にオーバーフローするマッピングテーブルおよびフリーリストを用い、またマッピング制御回路１４は、満杯マッピングテーブルおよびフリーリストを次のブロック中に書き込み終わる後までは、第１ブロックを消去しない。
【００８９】
図１２ａは、直ちにブロックを完全に更新することはない実施例を示す。第１ブロック１２０は、論理ブロックの当初の完全なデータセットを格納していることを示している。第２ブロック１２２は、論理ブロックの更新データ１２３を格納していることを示している。
【００９０】
ある実施例においては、マッピング制御回路１４は、空ブロックを例えばフリーリスト１１４ｃから選択することによって、第１ブロック１２０にマッピングする論理ブロックの一部を更新せよという命令に応答するよう構成することができる。この空ブロックを第２ブロック１２２とする。マッピング制御回路１４は、ブロック１２０の更新した部分のデータ１２３のみを第２ブロック１２２へ書き込む。マッピング制御回路１４が、初期に更新した位置とオーバーラップしていない、同一論理ブロックにおける位置に、このタイプの後続命令を受け取るとき、マッピング制御回路１４は新しい更新データを第２ブロック１２２に書き込む。マッピング制御回路１４は他の後続命令に対してもこのことを繰り返す。
【００９１】
後続命令における更新がオーバーラップしている場合、マッピング制御回路１４は第１ブロック１２０の残りの（まだ更新していない）位置を第２ブロック１２２にコピーする。さらに、マッピング制御回路１４は、第２ブロック１２２に、第２ブロック１２２の準備が完了したことを示す情報を書き込む。第２ブロックが第１ブロック１２０の役割を引き継いだ後、マッピング制御回路１４は、更新を格納する第２ブロックのように機能する新ブロックを（例えばフリーリスト１１４ｃから）選択する。続いて当初の第１ブロックを消去する。
【００９２】
任意の時点、例えばフリーブロックがこれ以上得られないときでも、マッピング制御回路１４は、第１ブロック１２０の残りの（まだ更新していない）位置を第２ブロック１２２へコピーする。このとき、マッピング制御回路１４は、さらに、第２ブロック１２に、第２ブロックの準備が完了したことを示す情報を書き込む。その後、マッピング制御回路１４は第２ブロック１２２を第１ブロック１２０の役割に用い、続いて当初の第１ブロック１２０を消去する。ある実施例においては、マッピング制御回路１４は、装置の電源が遮断されたときも、この操作を行う。
【００９３】
読み出し中、マッピング制御回路１４が論理ブロックの読み出し命令を受け取る場合、マッピング制御回路１４は、第１および第２ブロック１２０，１２２が論理ブロックのために利用可能かどうか確定し、利用可能な場合、その読み出し操作が、更新したメモリ位置のための第２ブロック１２２からの更新データ１２３、または更新していない値のための第１ブロック１２０からの当初データ、のどちらに関するものか確定する。前者の場合、マッピング制御回路１４は読み出し操作を第２ブロック１２２に指示し、後者の場合、マッピング制御回路１４は読み出し操作を第１ブロックに指示する。
【００９４】
マッピング制御回路１４は、好適には、追加の修正をマッピングテーブルメモリ１２中に格納し、ブロックの一部(または複数部分)を更新したことを示し、読み出し操作中に、更新したデータ１２３を識別するようにする。これら追加の修正は、例えば更新を書き込んだとき、マッピングテーブルメモリ１２に格納する。
【００９５】
ある実施例においては、マッピング制御回路１４は、起動時、フリーリスト１１４ｃを用いて更新を修復する。この実施例においては、マッピング制御回路１４は、フリーリスト１１４ｃに載っている１個または複数のブロックの検査を行い、これらブロックが、どの論理ブロックにあるかを示すデータおよびタグ、を有しているかどうかを確定する。有している場合、マッピング制御回路１４は、これらのブロックが、そのブロックの準備が完了していることを示す情報を有しているかどうか検査を行う。有している場合、マッピング制御回路１４は、マッピングテーブル１１２ｃにおける論理ブロックのために識別されるブロックの代わりにそのブロックを用いる。マッピング制御回路１４がデータを有するブロックを検出するがそのブロックの準備が完了していない場合、マッピング制御回路１４は、このブロックを第２ブロック１２２として用い、マッピングテーブル１２２ｃにおける同一論理ブロックにリストされているブロックを第１ブロックとして用いる。ある実施例においては、マッピング制御回路１４は、この場合追加の修正を生成し、この追加の修正をマッピングテーブルメモリに格納する。
【００９６】
図１２ｂは、更新したデータ１２３の他に、コピーしたデータを更新したデータ１２３より前のアドレスへ格納する実施例を示す。この実施例は、読み出しのための、追加の修正を簡略化することができる。この読み出しには、更新データ１２３の終端までのデータを第２ブロック１２２から読み出すことができ、更新データ１２３に連続するデータを第１ブロック１２０から読み出すことを要する。このことは、ブロックをシーケンスに従って（順番通りに）のみ書き込むことができるフラッシュメモリ１０において、とくに有用である。この場合、書き込み操作中、マッピング制御回路１４は、まず、第１ブロック１２０からの更新データまでのデータを第２ブロック１２２にコピーし、この更新データ１２３を第２ブロック１２２に書き込む。
【００９７】
さらにある実施例においては、マッピング制御回路１４は、追加の書き込み命令を検査し、書き込み命令が第１ブロック１２０および第２ブロック１２２を使用している論理アドレスに対するものかどうか決定する。もしそうならば、マッピング制御回路１４は書き込み命令が更新データの後のブロックにおけるメモリ位置に対して指示されたものかどうか検査する。もしそうならば、マッピング制御回路１４は、第１ブロック１２０から第２ブロック１２２に、更新データ１２３の終端から追加書き込み命令のアドレスの始点にいたるデータをコピーし、続けて追加の書き込み命令のデータを第２ブロック１２２に書き込む。新しい書き込み命令のためのメモリ位置が、既に書き込んだ第２ブロックの部分の前にきたりオーバーラップする場合、マッピング制御回路１４は、第３ブロック１２４としてフリーブロックを選択し、新しい書き込み命令のデータをこの第３ブロックに書き込み、これに先立って第２ブロック１２２からのデータのコピーを行う。
【００９８】
ある実施例においては、マッピング制御回路１４は、第１、第２および第３ブロック１２０,１２２,１２４を維持して、使用する。追加書き込み命令を同一論理ブロックに対して行う場合、さらに多くのブロックを使用することもできる。この実施例においては、マッピング制御回路１４は、読み出しアドレスに基づいて、これらブロック１２０，１２２，１２４のうち一個からの読み出し命令を実行する。したがって、マッピング制御回路１４は、これらの各ブロック１２０，１２２，１２４、およびブロック中において最新データを格納している位置にいたるまでの位置を識別する追加の修正を格納することができる。さらに、任意な時点で（例えば利用可能なフリーブロックがこれ以上ないとき）、メモリマッピング制御回路１４はすべての修正を一掃して、最も空きのある（先行する直近ブロック１２２等の次の役割を担う）ブロック１２４を満杯にし、準備が完了したこの第３ブロック１２４に情報を格納することができる。マッピング制御回路１４は続いて、他のブロック１２０，１２２を消去し、更新メモリマッピングテーブルおよびフリーリストをフラッシュメモリ１０へ書き込むことができる。
【００９９】
起動時、マッピング制御回路１４は、フリーリスト１２３ｃに載っているブロックをサーチし、データを有しているかどうか決定する。ある論理ブロックのためのブロックが準備完了していることの表示を有している場合、マッピング制御回路１４は、その論理ブロックのために、マッピングテーブルに載っているブロックの代わりにそのブロックを使用する。マッピング制御回路１４が、フリーリストからの１個または複数個のブロックが同一論理ブロックに対するデータを有することを検出するが、これらのブロックが１個も準備完了していることを示していない場合、マッピング制御回路１４は追加の修正情報を構築し、この追加の修正情報は検出したブロック１２２,１２４を参照する。
【０１００】
原則として、１個より多くの付加的ブロック１２２,１２４を１個の論理ブロックのために使用していて、マッピング制御回路１４が書き込み命令を受け、各付加的ブロック１２２，１２４中の最後に更新したメモリ位置以降のメモリ位置にあるデータを書き込みにより更新するときに、マッピング制御回路１４はどこに更新を書き込むかの選択をすることができる。最も古い（満杯の）付加的ブロックへの書き込みは、より新しいブロックには更新のための余地がより多く残っているという利点があり、このことは付加的ブロックの必要性を少なくする。しかし、最新の付加的ブロックへの書き込みも使用することができ、この場合、最新ブロックにおける更新データをより古いブロックにおける更新データを超える拡張したものとすることができるという効果を有する。この場合、マッピング制御回路１４は、古いブロックを消去すると好適である。さらに好適には、マッピング制御回路１４はこの場合更新のシーケンスを示すブロックに情報を書き込み、起動時に追加修正を形成するのに用いる。
【０１０１】
ここで用いる、チェーンにおけるポインタおよびマッピングテーブル中における物理ブロックのアドレスの双方、ならびにフリーリスト中のブロックアドレスは、それぞれに対応する機能が割り当てられた各物理ブロックをそれぞれ識別するために用いるポインティング情報を意味する。これら機能の典型的な例としては、論理ブロックアドレスとしてのブロック、ポインタをなすブロック、およびフリーリストをなすブロックとして機能するブロックがある。
【０１０２】
マッピング制御回路１４は、例えば、本明細書で説明したようなブロックを使用するための命令のプログラムを組み込んだプログラム可能処理回路として実現することができる。代替案として、マッピング制御回路１４の一部または全てを、上述の機能を果たす専用の回路として実現することができる。
【０１０３】
ここまで、個々のブロックを指し示すポインティング情報を使用し、個々のブロックをポインティング情報の保存に使用する（消去単位はブロック）実施例を示したが、代わりに、そのような消去単位のグループを指し示すポインティング情報を使用し、および/または単位のグループを順次の有効ポインタ値を格納するのに使用することもできると理解されたい。
【０１０４】
ここまで、（追加の）修正のリストを、好適には、ＳＲＡＭまたはＤＲＡＭのようなＲＡＭメモリとするマッピングテーブルメモリ１２に格納する実施例を示したが、代替案として、付加的ＲＡＮメモリ（図示せず）を設け、更新制御回路１４に接続して、修正リストを格納することもできることを理解されたい。同様に、後続のポインタチェーンによって得る最終ポインタ、次の更新の書き込みに使用する空でないブロックの識別などのような他の情報を、マッピングテーブルメモリ１２またこのような付加的ＲＡＭメモリに格納することができ、この情報を見つけるためのフラッシュメモリ１０をサーチすることは、起動時、および随意的に、例えばリセット信号またはエラー信号の受信後のような後の例外的な時点において、のみ実行を要するものとする。
【０１０５】
ここまで、（追加の）修正のリストを、好適には、ＳＲＡＭまたはＤＲＡＭのようなＲＡＭメモリとするマッピングテーブルメモリ１２に格納する実施例を示したが、代替案として、付加的ＲＡＮメモリ（図示せず）を設け、更新制御回路１４に接続して、修正リストを格納することもできることを理解されたい。同様に、後続のポインタチェーンによって得る最終ポインタ、次の更新の書き込みに使用する空でないブロックの識別などのような他の情報を、マッピングテーブルメモリ１２またこのような付加的ＲＡＭメモリに格納することができ、この情報を見つけるためのフラッシュメモリ１０をサーチすることは、起動時、および随意的に、例えばリセット信号またはエラー信号の受信後のような後の例外的な時点において、のみ実行を要するものとする。
【０１０６】
認識されている通り、ある物理ブロックは時間の経過とともに、例えばそのブロックを所定回数以上消去した後の消耗により、またはブロック中に生じる他のエラーにより、使用不能となる。このことが起きるとき、マッピング制御回路１４はこれらのブロックの使用を回避する。一旦使用を断念したブロックはマッピングテーブルおよびフリーリストから除外する。随意的に、マッピング制御回路１４は、フラッシュメモリ１０中でもう使用すべきでない物理ブロックアドレスの「バッドリスト」を示す情報を保持する。ブロックの使用を断念すると「バッドリスト」へ加えるが、フリーリストまたはフラッシュメモリ１０中のマッピングテーブルを直ちに更新する必要はない。後者の更新は、フリーリストを使い果たすまで延期することができる。起動時、マッピング制御回路１４は、バッドリストを検査してフリーリストまたはマッピングテーブル中を参照するブロックがバッドリストにも載っているかどうか決定し、載っている場合マッピング制御回路１４はそのブロックがこれらのどのリスト上にもないものとして動作する。
【図面の簡単な説明】
【０１０７】
【図１】メモリを備える装置のブロック図である。
【図２】書き込み操作の実行のフローチャートである。
【図３】装置の起動のフローチャートである。
【図４ａ】ポインタを有する順次バージョンのメモリブロックの図である。
【図４ｂ】ポインタを有する順次バージョンのメモリブロックの図である。
【図４ｃ】ポインタを有する順次バージョンのメモリブロックの図である。
【図４ｄ】ポインタを有する順次バージョンのメモリブロックの図である。
【図５】異なるマッピングテーブルセグメントポインタを有するメモリブロックの図である。
【図６】異なるマッピングテーブルセグメントポインタを有するメモリブロックの図である。
【図７ａ】ポインタチェーンを有するメモリブロックの図である。
【図７ｂ】ポインタのチェーンを有するメモリブロックの図である。
【図７ｃ】ポインタのチェーンを有するメモリブロックの図である。
【図８ａ】ポインタツリーを有するメモリのブロックの図である。
【図８ｂ】ポインタのツリーを有するメモリブロックの図である。
【図８ｃ】ポインタのツリーを有するメモリブロックの図である。
【図９ａ】ポインタのチェーンを有するメモリブロックの図である。
【図９ｂ】ポインタのチェーンを有するメモリブロックの図である。
【図１０ａ】ポインタのチェーンを有するメモリブロックの図である。
【図１０ｂ】ポインタのチェーンを有するメモリブロックの図である。
【図１１】フリーリストの使用状態を示す図である。
【図１２ａ】フリーリストの使用状態を示す図である。
【図１２ｂ】フリーリストの使用状態を示す図である。
【図１】
2009521044.tif 000003
【図２】
2009521044.tif 000004
【図３】
2009521044.tif 000005
【図４ａ】
2009521044.tif 000006
【図４ｂ】
2009521044.tif 000007
【図４ｃ】
2009521044.tif 000008
【図４ｄ】
2009521044.tif 000009
【図５】
2009521044.tif 000010
【図６】
2009521044.tif 000011
【図７ａ】
2009521044.tif 000012
【図７ｂ】
2009521044.tif 000013
【図７ｃ】
2009521044.tif 000014
【図８ａ】
2009521044.tif 000015
【図８ｂ】
2009521044.tif 000016
【図８ｃ】
2009521044.tif 000017
【図９ａ】
2009521044.tif 000018
【図９ｂ】
2009521044.tif 000019
【図１０ａ】
2009521044.tif 000020
【図１０ｂ】
2009521044.tif 000021
【図１１】
2009521044.tif 000022
【図１２ａ】
2009521044.tif 000023
【図１２ｂ】
2009521044.tif 000024
【国際調査報告】
2009521044.tif 000025
2009521044.tif 000026
2009521044.tif 000027