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