(57)【要約】  不揮発性メインメモリ（１０）が、記憶場所の複数の物理ブロックを備えている。ポインティング情報（１１２ａ〜ｃ，１１４ａ〜ｃ）をメインメモリ（１０）に記憶し、このポインティング情報は、特定機能用に使用した使用済みブロックへのポインタ（１１２ａ〜ｃ）、およびこれらの特定機能用に将来使用するために空いている空きブロックへのポインタ（１１４ａ〜ｃ）から成る。空きブロックは、使用済みブロックのうち選択したものと置き換える。このことが発生した後、少なくとも２つの空きブロックを置き換えに使用して初めて、ポインティング情報の更新バージョンをメインメモリに書き込むことができる。起動時に、空きブロックへのポインタ（１１４ａ〜ｃ）の少なくとも１つを用いて、空きブロックの少なくとも１つにアクセスして、アクセスした空きブロックが使用済みブロックの特定のものの置き換えとして使用されたか否かを判定する。使用された場合は、この空きブロックを、上記使用済みブロックの特定のものの代わりに使用する。
2009521049.tif 000002
【特許請求の範囲】
【請求項１】
記憶場所の複数の物理ブロックから成り、一度に少なくとも１つの物理ブロックを消去することをサポートする不揮発性メインメモリと、
前記メインメモリに記憶されたポインティング情報を維持するように構成されたマッピング制御回路とを備え、
前記記憶されたポインティング情報は、特定機能用に使用した使用済みブロックへのポインタと、前記特定機能用に将来使用するために空いている空きブロックへのポインタから成り、前記マッピング制御回路は、前記使用済みブロックのうち選択した１ブロックの少なくとも一部分の代替として、代替ブロックを、前記空きブロックへのポインタが指示する前記空きブロックから提供し、少なくとも、前記空きブロックの少なくとも２つの組合せを１つ使用した後に、前記空きブロックの少なくとも２つを前記代替ブロックとして使用して初めて、前記ポインティング情報の更新バージョンを前記メインメモリに書き込むように構成され、前記マッピング制御回路はさらに、少なくとも起動時に、前記記憶されたポインティング情報からの前記空きブロックへのポインタの少なくとも１つを使用して、前記空きブロックの少なくとも１つにアクセスして、前記アクセスした空きブロックが、前記使用済みブロックのうち特定の１ブロックの代替ブロックとして使用されたか否かを判定し、前記アクセスした空きブロックが前記代替ブロックとして使用された場合は、起動後に、前記アクセスした空きブロックを、前記特定の１ブロックの代替ブロックとして使用するように構成されていることを特徴とする装置。
【請求項２】
請求項１に記載の装置において、前記メインメモリがフラッシュメモリであることを特徴とする装置。
【請求項３】
請求項１に記載の装置において、さらに、前記メインメモリとは別の作業メモリを備え、前記マッピング制御回路は、起動時に、訂正情報を前記作業メモリに記憶するように構成され、前記訂正情報は前記ポインティング情報に対する訂正を表し、前記訂正の各々が、当該空きブロックが代替ブロックとして使用されていることを前記マッピング制御回路が判定した前記空きブロックのそれぞれを示すことを特徴とする装置。
【請求項４】
請求項３に記載の装置において、前記マッピング制御回路は、論理アドレスを物理ブロックにマッピングするマッピングテーブルの変更部分をキャッシュ記憶するように構成され、前記訂正情報は前記変更部分と並列して記憶されることを特徴とする装置。
【請求項５】
請求項３に記載の装置において、前記マッピング制御回路は、前記メインメモリからロードした前記ポインティング情報の一部分をキャッシュ記憶し、前記ロードした前記ポインティング情報の一部分に、前記作業メモリからの前記記憶されている訂正情報に従って訂正を加えるように構成されることを特徴とする装置。
【請求項６】
請求項３に記載の装置において、前記マッピング制御回路は、論理読出しブロックアドレスが前記記憶されている訂正情報によってカバーされるか否かを検査することによって、前記論理読出しブロックアドレスで読出しコマンドに応答し、前記論理読出しブロックアドレスが前記訂正情報によってカバーされる際に、前記訂正情報を用いて物理ブロックを選択し、前記論理読出しブロックアドレスが前記訂正情報によってカバーされない際に、前記論理読出しブロックアドレス用に前記使用済みブロック内に定義された物理ブロックのアドレスを使用するように構成されていることを特徴とする装置。
【請求項７】
請求項１に記載の装置において、前記ポインティング情報は、論理ブロックアドレスのそれぞれのセグメントについて、論理ブロックアドレスを物理ブロックアドレスにマッピングするためのマッピングテーブルを備え、前記論理ブロックアドレスのそれぞれのセグメントに対する前記マッピングテーブルのセグメントは、それぞれ異なるブロック内に記憶され、前記マッピング制御回路は、異なるセグメントを記憶するためのそれぞれ異なるブロックの代替ブロックを選択するために前記空きブロックへのポインタを使用する使用法を共用するように構成されていることを特徴とする装置。
【請求項８】
請求項１に記載の装置において、前記マッピング制御回路は、論理ブロック内の少なくとも１つのアドレス範囲用の書込みコマンドを受信するように構成され、前記マッピング制御回路は、前記論理ブロック用の第１および第２物理ブロックを前記メインメモリ内に維持するように構成され、前記第２物理ブロックは、前記ポインティング情報によって指示される前記空きブロックから選択され、前記第１物理ブロックは、前記論理ブロックの基本バージョンを含み、前記マッピング制御回路は、前記第２物理ブロック内の、前記少なくとも１つのアドレス範囲を含むアドレス部分のみに書き込むことによって、前記書込みコマンドに応答するように構成され、前記マッピング制御回路は、前記読出しコマンドが前記アドレス部分中の前記論理ブロックをアドレス指定しているか否かに応じて、前記第２物理ブロックからのデータまたは前記第１物理ブロックからのデータを戻すことによって、前記論理ブロックに対する前記出しコマンドに応答するように構成されていることを特徴とする装置。
【請求項９】
請求項８に記載の装置において、前記マッピング制御回路は、前記第１物理ブロックの始点から前記アドレス範囲の始点までのアドレスに対するデータを、前記第１物理ブロックから前記第２物理ブロックにコピーすることによって前記書込みコマンドに応答し、前記書込みコマンドに従って、前記アドレス範囲に対するデータを前記第２物理ブロックに書き込むように構成され、前記第２物理ブロックの残りのデータは、前記書込みコマンドに応答して書き込まれていないまま残されていることを特徴とする装置。
【請求項１０】
請求項８に記載の装置において、前記マッピング制御回路は、前記空きブロックの１つへのポインタの少なくとも１つを使用して、少なくとも起動時に選択的に、前記第２物理ブロックにアクセスし、前記第２物理ブロックが前記アドレス部分におけるデータを記憶するために使用されたか否かを判定し、使用された場合は、前記第２物理ブロックを使用して、その後に前記アドレス部分をアドレス指定する読出しコマンドに応答して、前記第２物理ブロックからデータを供給するように構成されていることを特徴とする装置。
【請求項１１】
請求項１０に記載の装置において、さらに、作業メモリを備え、前記マッピング制御回路は、起動時に、訂正情報を前記作業メモリに記憶するように構成され、前記訂正情報は前記ポインティング情報に対する訂正を表し、前記訂正の各々は、前記空きブロックうち、当該空きブロックが前記第２物理ブロックとして使用されていることを判定した空きブロック、及び当該第２物理ブロック内の前記アドレス部分を示すことを特徴とする装置。
【請求項１２】
請求項８に記載の装置において、前記マッピング制御回路は、第２のアドレス範囲に対する第２の書込みコマンドを受信し、前記第２のアドレス範囲が前記アドレス部分に重複するか否かを検査することによって、前記第２の書込みコマンドに応答し、重複しない場合、前記コマンドによって識別されるデータを前記第２物理ブロック内に書き込み、重複する場合、前記コマンドによって識別されるデータを、前記空きブロックから選択した第３物理ブロックに書き込むように構成されていることを特徴とする装置。
【請求項１３】
請求項１２に記載の装置において、前記マッピング制御回路は、残りのデータを、前記第１物理ブロックから、前記第２物理ブロックおよび前記第３物理ブロックの一方にコピーし、その後に、前記第１物理ブロックの代わりに、前記第２物理ブロックおよび前記第３物理ブロックの一方を使用し、前記コピーの後に、前記第１物理ブロックを消去するように構成されていることを特徴とする装置。
【請求項１４】
請求項１に記載の装置において、前記マッピング制御回路は、前記ポインティング情報によって識別される全ての空きブロックを使用した時点を検出し、この検出時に、前記ポインティング情報の更新バージョンを前記メインメモリに書き込み、前記更新バージョン内では、前記空きブロックへの元のポインタが、前記使用済みブロックへのポインタに追加され、前記空きブロックに置き換えたブロックへの元のポインタが、前記使用済みブロックへのポインタから除去され、前記空きブロックへのポインタに追加されていることを特徴とする装置。
【請求項１５】
請求項１４に記載の装置において、前記マッピング制御回路は、前記ポインティング情報の前記更新バージョンを前記メインメモリに書き込む前に、前記空きブロックに置き換えたブロックを消去するように構成されていることを特徴とする装置。
【請求項１６】
請求項１４に記載の装置において、前記マッピング制御回路は、更なる使用を永久に中止した前記メインメモリの不良ブロックを識別する情報を前記メインメモリに書き込み、少なくとも起動時に、前記不良ブロックを識別する情報を検索するように構成されていることを特徴とする装置。
【請求項１７】
請求項１４に記載の装置において、前記マッピング制御回路は、論理ブロック内のアドレス範囲に対する書込みコマンドを受信し、前記論理ブロック用の第１および第２物理ブロックを維持するように構成され、前記第２物理ブロックは、前記ポインティング情報によって指示される前記空きブロックから選択され、前記第１物理ブロックは前記論理ブロックの基本バージョンを含み、前記マッピング制御回路はさらに、前記第２物理ブロック内の、前記アドレス範囲を含む前記アドレス部分のみに書き込むことによって前記書込みコマンドに応答し、読出しコマンドが前記アドレス部分の中の論理ブロックをアドレス指定しているか否かに応じて、前記第２物理ブロックからのデータまたは前記第１物理ブロックからのデータを戻すことによって、前記論理ブロックに対する前記読出しコマンドに応答するように構成され、前記マッピング制御回路はさらに、残りのデータを前記第１物理ブロックから前記第２物理ブロックにコピーし、かつ前記第２物理ブロックへのポインタを前記ポインティング情報の前記更新バージョン中に使用済みブロックとして含めることによって、前記ポインティング情報によって識別される全ての空きブロックを使用したことの検出に応答するように構成されていることを特徴とする装置。
【請求項１８】
記憶場所の複数の物理ブロックから成り、一度に少なくとも１つの物理ブロックを消去することをサポートする不揮発性メインメモリを、マッピング制御回路を用いて動作させる方法において、
ポインティング情報を前記メインメモリに記憶するステップであって、前記ポインティング情報は、特定機能用に使用した使用済みブロックへのポインタと、前記特定機能用に将来使用するために空いている空きブロックへのポインタから成るステップと；
前記空きブロックを用いて、前記使用済みブロックから選択した１ブロックを置き換えるステップと；
少なくとも、前記空きブロックの少なくとも２つの組合せを１つ使用した後に、前記空きブロックの少なくとも２つを代替ブロックとして使用して初めて、前記ポインティング情報の更新バージョンを前記メインメモリに書き込むステップと；
少なくとも前記マッピング制御回路の起動時に選択的に、前記空きブロックへのポインタの少なくとも１つを使用して、前記空きブロックの少なくとも１つにアクセスするステップと；
少なくとも前記マッピング制御回路の起動時に選択的に、前記アクセスした空きブロックが、前記使用済みブロックのうち特定の１ブロックの代替ブロックとして使用されたか否かを判定するステップと；
前記アクセスした空きブロックが前記代替ブロックとして使用された場合に、前記アクセスした空きブロックを、前記特定の１ブロックの代わりに使用するステップと
を具えていることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリデバイス、およびこうしたデバイスを動作させる方法に関するものである。
【背景技術】
【０００２】
【特許文献１】米国特許第６７１１６６３号明細書
【０００３】
米国特許第６７１１６６３号明細書は、フラッシュメモリデバイスを開示している。あらゆる半導体メモリデバイスからとだいたい同様に、フラッシュメモリ素子からデータを読み込むことができる。データの書込みはより複雑である。一般的に書込みは、メモリセルの１つのブロックを消去して、その後に消去したブロックにデータのページをプログラムすることを含む。一般的に、消去は、ブロック全体に対して集合的に実行することのみが可能であり、したがって、この場合はブロック全体が消去の単位を形成する。プログラミングは通常、ページと呼ばれる定義によってより小さい単位で行うことができる。
【０００４】
フラッシュメモリ素子は、損耗するという問題がある。データブロックは、損耗しきる前に、限られた回数だけ消去およびプログラムすることができ、それ以降は、もはや信頼性を以って使用することはできない。フラッシュメモリデバイスの特定のアドレスのブロックを、他のブロックより頻繁に消去およびプログラムする場合、これらのブロックの有効寿命が、このフラッシュメモリデバイスの有効寿命を制限する。
【０００５】
時間変化する論理アドレス−物理アドレスマッピングを用いることによって、この問題に応えてきた。マッピングを用いて、フラッシュメモリにアクセスするために使用する論理アドレスが、異なる時刻にフラッシュメモリの異なる物理ブロック内の記憶場所を参照することを可能にすることができる。したがって、頻繁に消去およびプログラムを必要とする論理アドレスを、時間と共に異なる物理ブロックに再マッピングして、この論理ブロックを消去およびプログラムする毎に、同一の物理ブロックを消去およびプログラムしなければならないことを回避することができる（本明細書において、「論理ブロック」は、物理ブロック内のマッピング可能な完結した一組のアドレスの完全セットにマッピングされる一組のアドレスを称し、随意的に大まかに、これらの記憶場所に記憶されているデータをも称する）。
【０００６】
効率的な論理アドレス−物理アドレスのマッピングは、論理アドレスに応じて記憶した物理アドレスを含むマッピングテーブルを必要とし、これらの論理アドレスが当該物理アドレスに対応する。原則として、こうしたマッピングテーブルは、物理アドレス−論理アドレスマッピングの変更がなされる毎に更新しなければならない。従来は、フラッシュメモリ用のこうしたマッピングテーブルはＲＡＭメモリ（ランダムアクセスメモリ）に記憶している。起動時に、マッピングテーブルをフラッシュメモリに記憶した「タグ」から再構成し、これらのタグは、異なる物理メモリ領域（例えばブロック）に対する現在の論理アドレスを示す。
【０００７】
米国特許第６７１１６６３号明細書は、フラッシュメモリ自体に記憶したマッピングテーブルの使用法について記載している。米国特許第６７１１６６３号明細書は、セグメント構成のマッピングを使用している。このメモリは、複数の、ブロックのセグメントとして構成されている。それぞれのマッピングテーブルをセグメント毎に設けて、このテーブルが、セグメントに対する論理アドレスを当該セグメントにおける物理アドレスに変換する。セグメントのサイズは、各マッピングテーブルのサイズがメモリページ、つまりフラッシュメモリのプログラミングの単位に相当するように選択する。
【０００８】
米国特許第６７１１６６３号明細書は、セグメントのマッピングテーブルの連続したバージョンを記憶するために、各セグメント内に「メモリ更新ブロック」を設けている。メモリ更新ブロックの最後にプログラムしたページをマッピングテーブルとして使用する。セグメントのマッピングテーブルを変更する毎に、更新したマッピングテーブルをメモリ更新ブロックの次のページにプログラムする。各変更後に、新たなページを用いて、メモリ更新ブロックの全てのページがプログラムされるまで、マッピングテーブルを記憶する。全てのページをプログラムしたあとに、メモリテーブルの次の更新が発生すると、メモリ更新ブロックを消去して、新たなメモリテーブルを、消去したブロックの最初のページに書き込む。
【０００９】
この方法は、起動時に、タグからマッピングテーブルを再構成する時間を必要としない利点を有する。その代わりに、マッピングテーブルをフラッシュメモリから直接読み出すことができる。
【００１０】
しかし、マッピングテーブルを記憶したブロックは、頻繁な更新により、損耗が増加する問題があり得る。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的はとりわけ、必要とするマッピングテーブルの更新頻度がより少なく、起動時に長い検索時間を必要としない、マッピングテーブルを記憶したメモリ素子を提供することにある。
【課題を解決するための手段】
【００１２】
本発明によれば、請求項１に記載の装置が提供される。本明細書では、マッピング制御回路は、メインメモリ、例えばフラッシュメモリに記憶されたポインティング情報を維持する。ポインティング情報は、特定機能用に使用するブロックへのポインタ（例えば、論理アドレスのデータ、または、データの検索において使用するデータブロックへのポインタを記憶するため）を含む。これに加えて、ポインティング情報は空きブロックへのポインタを含む。（例えば１つのブロックの過度の損耗を回避するために）特定機能に使用するブロックを置き換える際に、マッピング制御回路は、常にメインメモリのポインティング情報を更新せずに、記憶している空きブロックへのポインタに従って代わりのブロックを選択する。起動時に、マッピング制御回路は、記憶している空きブロックへのポインタの１つ以上を使用して、当該空きブロックが特定機能用のブロックの代替に使用されたか否かを判定し、使用された場合は、この使用済みブロックに代わる空きブロックを使用する。したがって、ポインティング情報が必ずしもメインメモリ内で置き換えられない場合でも、ポインタが空きブロックとして識別したブロックに検索を集中することができるので、起動が高速になる。
【００１３】
一好適例では、メインメモリに記憶している空きブロックへのポインタを使い果たす毎に、ポインティング情報の新たなバージョンを書き込む。この時に、多くの使用済みブロックが空きになっており、これらのブロックを消去した後に、これらのブロックへのポインタを新たなバージョンに記憶することができる。
【００１４】
一好適例では、マッピング制御回路が訂正情報を記憶し、この情報は、作業メモリ（例えばＲＡＭのような揮発性メモリ）内で、空きブロックが使用済みブロックを置き換えるために使用されたか否かを示す。通常動作中に、この訂正情報を使用して、使用済みブロックを置き換える空きブロックの選択を加速することができる。他の好適例では、マッピングテーブルの変更部分（例えば論理アドレス空間のそれぞれのセグメントに対応する物理ブロックのアドレスを含む部分）をキャッシュ記憶する。この他の好適例では、訂正情報を変更部分と並列的に記憶する。したがって、例えば、訂正情報をメインメモリからロードする毎に、訂正情報に応じて、キャッシュ記憶しているマッピングテーブルの対応部分を訂正することができる。代案として、訂正情報をメインメモリからロードする毎に、訂正情報に応じて個々のポインタを訂正することができ、あるいは、論理アドレスの訂正が利用可能である場合には、メインメモリからのポインタのロードをバイパスすることができる。
【００１５】
一好適例では、部分的な書込み動作をブロックに適用する。この場合、少なくとも２つのブロックが同一機能についての情報を記憶し、第１ブロックは、完結した（しかし、部分的に古い）データを有し、第２ブロックは、完結していないが最新のデータを有する。このように、第２ブロックにすでに書き込んだデータと重複しないデータを後に書き込む動作を、他の空きブロックを使用せずに第２ブロックに適用することができる。この好適例では、空きブロックを用いて使用済みブロックを置き換える際に、使用済みブロックはすぐに空きにはならない。読出し動作は古いブロックから行うことができ、あるいは読出し動作が更新されたデータをアドレス指定する際には、新たなブロックから行うことができる。起動時に、マッピング制御回路は、記憶している空きブロックへのポインタを使用して、これらのブロックが特定機能用の部分的データを有するか否かどうかを検査し、有する場合には、これらのブロックを元のブロックと組み合わせて、ポインティング情報によって識別される機能用に使用する。
【００１６】
他の好適例では、２つ以上の書込みコマンドを処理した際に、３つ以上のブロックを同一機能、即ち前に記憶しているデータと重複するデータに関係するコマンド用に使用することができる。代案の好適例では、所定数より多いブロックが同一の機能に必要である際に、不完全に書き込まれたブロックを完結させ、同じ機能用の他のブロックを空き状態にする。他の好適例では、以前に空きであったブロック、並びに更新データ用に使用したブロックの一部を示す訂正情報を、作業メモリに維持する。
【００１７】
本発明のこれらおよび他の目的および有利な態様は、図面に例示する好適な実施例の説明より明らかになる。
【発明を実施するための最良の形態】
【００１８】
図１に、メモリを有する装置を示す。この装置は、フラッシュメモリ１０と、マッピングテーブルメモリ１２と、マッピング制御回路１４と、プロセッサ１６と、マルチプレクサ１８ａ，ｂとを備えている。例えば、マッピング制御回路１４は、マッピング制御の機能を実行するコンピュータプログラムによりプログラムされたプログラマブル回路として実現される。プロセッサ１６は、マッピング制御回路１４への制御接続部を有する。プロセッサ１６およびマッピング制御回路１４のデータ入出力は、フラッシュメモリ１０のデータ入出力に結合されている。マッピング制御回路１４およびプロセッサ１６は、（随意的にページアドレス部も含む）ブロックアドレス部分および残りのアドレス部分用のアドレス出力を有する。プロセッサ１６およびマッピング制御回路１４からの、ブロックアドレス部分の出力および残りのアドレス部分の出力は、それぞれマルチプレクサ１８ａ，ｂを経由してフラッシュメモリ１０のブロックアドレス入力および残りのアドレス入力に結合されている。プロセッサ１６からのアドレス出力は、マッピングテーブルメモリ１２を経由してマルチプレクサ１８ｂに結合されている。マッピング制御回路１４は、マッピングテーブルメモリ１２およびマルチプレクサ１８ａ，ｂに結合された制御出力を有する。
【００１９】
フラッシュメモリ１０は、一度に少なくとも１ブロックの記憶場所の消去動作を可能にする種類のものである。したがって、消去の単位をブロックと称する。記憶場所は一度に１ページだけプログラムすることができる。一般的に、各ブロックは複数のページを含む。
【００２０】
通常の読出し動作では、プロセッサ１６は読出しアドレスを出力して記憶場所にアクセスする。アドレスは、ブロックアドレス部分および残りのアドレス部分を含む。読出しアドレスのブロックアドレス部分を、マッピングテーブルメモリ１２によって物理ブロックアドレスに変換して、フラッシュメモリ１０に供給する。変換は一般的に、論理ブロックアドレスを、マッピングテーブルメモリ１２用のアドレスとして使用して、対応する物理アドレスを読み出すことを含む。残りのアドレス部分は、変換せずにフラッシュメモリ１０に供給する。より進歩的な実施例では、読出しアドレスの変換は、アドレスのページアドレス部分とブロックアドレス部分との組合せの変換を含むことができる。
【００２１】
図２に、書込み動作のフローチャートを示す。第１ステップ２１では、プロセッサ１６は、書込み動作の要求を、この書込み動作に適用すべき論理ブロックアドレスと共に、マッピング制御回路１４に信号通知する。第２ステップ２２では、マッピング制御回路１４は、書込みに使用する物理ブロックを選択する。より進歩的な実施例では、マッピング制御回路１４は、書込みに使用する物理ブロックおよび物理ページを共に選択する。選択したブロックおよびページは、他の論理ブロックアドレス用に使用されていない消去済みブロック、または、進歩的な実施例では、使用中でない消去済みページであるべきである。随意的に、マッピング制御回路１４は、使用していないブロックがまだ消去されていない場合、フラッシュメモリ１０に当該ブロックを消去させる。いずれにせよ、使用していないブロックのいずれも消去されていない場合、これを実行する。
【００２２】
マッピング制御回路１４は、選択した物理ブロック（またはページ）を、プロセッサ１６が書込みを要求する論理ブロック（またはページ）に割り当てる。第３ステップ２３では、マッピング制御回路１４は、論理アドレスを物理アドレスにマッピングするための、新たに割り当てたブロック（またはページ）を占める新たなマッピングテーブルを構成する。一実施例では、マッピング制御回路１４は、マッピングテーブルメモリ１２内のマッピングテーブルを更新して、フラッシュメモリに、上記論理ブロック（またはページ）用の新たなデータを物理ブロック（またはページ）の記憶場所にプログラムさせる。
【００２３】
第４ステップ２４では、マッピング制御回路１４は、少なくとも１つのプログラムされたページを含むマッピングテーブルの記憶用に割り当てられた一組のブロックうち最初のブロックを識別する。
【００２４】
その後、マッピング制御回路１４は連続的に、上記割り当てられたブロックの最初のブロック内の順序的に最初の未使用のページまたは一組のページを検索する。第５ステップ２５では、マッピング制御回路１４は、こうしたページまたは一組のページを発見したか否かを検査する。発見した場合、マッピング制御回路１４は第６ステップ２６を実行し、発見した１つ又は複数のページに新たなマッピングテーブルをプログラムする。マッピング制御回路１４が、上記最初のブロック内に未使用のページを発見しない場合、マッピング制御回路１４は第７ステップ２７に分岐し、ここでマッピング制御回路１４は、マッピングテーブルの記憶に割り当てた一組のブロックのうち次のブロックを選択する。第８ステップ２８では、マッピング制御回路１４は、上記次のブロック内の、順序的に最初の未使用のページまたは一組のページに、新たなマッピングテーブルをプログラムする。第９ステップ２９では、マッピング制御回路１４は、フラッシュメモリ１０を制御して、上記最初のブロックを消去する。
【００２５】
図３に、装置が起動するフローチャートを示す。第１ステップ３１では、マッピング制御回路１４は、少なくとも１つのプログラムされたページを含むマッピングテーブルの記憶用に割り当てられた一組のブロックの最初のブロックを識別する。その後、マッピング制御回路１４は、上記最初のブロック内の、順序的に最後に使用したページまたは一組のページを検索する。第２ステップ３２では、マッピング制御回路１４は、最後に使用したページからマッピングテーブルメモリ１２にマッピングテーブルをコピーする。第３ステップ３３では、マッピング制御回路１４はシステムの通常動作を開始する。
【００２６】
なお、マッピング制御回路１４は、第９ステップ２９において上記最初のブロックを消去する前に、第８ステップ２８において新たなマッピングテーブルをフラッシュメモリ１０にプログラムする。この処理が何らかの理由で、例えばシステム（の一部）への電力供給を解除することによって中断された場合、第８ステップ２８は実行されるが、第９ステップ２９は実行されない恐れがある。マッピング制御回路１４は起動時に、マッピングテーブルの記憶用に割り当てられたブロックのうち１つは満杯であり、これらの割り当てられたブロックの他の少なくとも１つは空きでないことを検出することによって、このことを検出するように構成されている。このことを検出した場合は、マッピング制御回路１４は、起動時に、完全に満杯ではない上記割り当てられたブロックのうち１つのブロック内の、順序的に最後に使用したページまたは一組のページを使用し、フラッシュメモリ１０に、満杯である上記割り当てられたブロックを消去させることが好ましい。代案として、マッピング制御回路１４は、満杯である上記割り当てられたブロックの、順序的に最後に使用したページまたは一組のページを使用することができる。この場合、新たにプログラムしたデータを入手し損なうかもしれないが、このことは、図２の処理が早期に中断された場合であり得る。
【００２７】
図４ａ〜ｃは、マッピングテーブルの記憶用に割り当てられた一組のブロック内のページを利用する３つの段階を示す。各図には、同じ２つのブロック４０，４２の組を示す。マッピングテーブルをプログラムしたページを斜線で示す。消去した（空きの）ブロックを、斜線がないことによって示す。一実施例では、各ページにフラグビットをプログラムして、当該ページが空きであるかプログラムされているかを示す。代案として、ブロック内の全てのデータが消去された状態（例えば論理ビット値１）であるか否かを検査することによって、および、随意的にＥＣＣの場合（エラー訂正コードをブロック内で使用している場合）は、ＥＣＣがエラーを示しているか否かを検査することによって、空きのブロックを検出することができる。あるいはまた、タグをデータとともに書き込む場合、有効なタグの存在を検査することによって検出することができる。
【００２８】
例えば、ページはアドレスの増加と共に図のより下方に示し、図の最上部に示すページが最小アドレスを有する。
【００２９】
第１段階（図４ａ）では、第１ブロック４０のページの一部分にマッピングテーブルがプログラムされている。ブロック４０，４２がこの状態にある際に、マッピング制御回路１４は起動時に、空きでないブロック４０内の最下部に示すプログラムされたページを使用する。プロセッサ１６が書込みを要求すると、マッピング制御回路１４は、空きでないブロック４０内の最上部に示す空きのページを、新たなマッピングテーブルをプログラムするために選択する。
【００３０】
第２段階（図４ｂ）では、第１ブロック４０の全てのページにマッピングテーブルをプログラムし、第２ブロック４２は空きである。この場合、マッピング制御回路１４は、図４ａの場合のように起動を進める。プロセッサ１６が書込みを要求すると、マッピング制御回路１４は、第２ブロック４２内の最初の空きのページを、新たなマッピングテーブルをプログラムするために選択する。新たなマッピングテーブルをプログラムした後、マッピング制御回路１４は、満杯のブロックを消去し、これにより、図４ｃに示す第３段階に至る。
【００３１】
第３段階（図４ｃ）では、第１ブロック４０は空きであり、第２ブロック４２の一部分はプログラムされている。ブロック４０，４２がこの状態にある際に、これらのブロックの役割は図４ａと逆になる。
【００３２】
図４ｄに、第２の段階（図４ｂ）後に、電源の早期の遮断により生じる状態を示す。一方のブロック４０は満杯であり、他方のブロック４２は空きではない。マッピング制御回路１４が起動時にこの状態に直面した場合、マッピング制御回路１４は、満杯のブロックを消去して、満杯でないブロック４２からのマッピングテーブルを使用する。
【００３３】
代案の実施例では、マッピング制御回路１４は、マッピングテーブルに付随するバージョン番号を書き込み、このバージョン番号は、テーブルを書き込む毎に増加する（さもなければ、所定順序に従い変化する）。この実施例では、最新バージョン番号を有するマッピングテーブルを選択することによって、マッピングテーブルの有効なバージョンを識別することができる。別の実施例では、マッピング制御回路１４は、更新をバージョン番号とともに、いずれかの中間ブロックに書き込むことができ、例えば他のブロックが満杯である場合は、書込み後にこれらの他のブロックを消去する。
【００３４】
他の実施例では、新たなブロックへの書込み前に満杯のブロック内に「ダーティ」フラグを設定し、起動時に適正なブロックの選択を補助するように、マッピング制御回路を構成することができる。この場合、マッピング制御回路１４はまず、ダーティとしてマークされていないブロックから最後のマッピングテーブルを使用しようとする。このブロックが（エラーにより）空きである場合、マッピング制御回路１４はダーティのブロックに頼る。
【００３５】
バージョン番号は周期的に変更することができる。バージョン番号は、適正なブロックを見つける目的で満杯のブロックおよび空きのブロックを検査する代わりに、ブロック内の、マッピングテーブルを有するページの位置と組み合わせて利用することができる。この場合、短い周期、例えば４つの異なるバージョン番号で十分である。整数個のマッピングテーブルをブロック内に適合させる実施例を示してきたが、このことが必要でないことは明らかである。マッピングテーブルのサイズが、ブロックを整数個のマッピングテーブルで満たすことができないようなサイズである際に、マッピング制御回路１４は最後のマッピングテーブルを、一方のブロックから他方のブロックにオーバーフローさせる（溢れ出させる）ことによって書き込むことができる。この場合、オーバーフローしているマッピングテーブルの後に別のマッピングテーブルを記憶していない場合に、マッピング制御回路１４は起動時に、このオーバーフローしているマッピングテーブルを使用し、マッピング制御回路１４は、次のブロック内に完全なマッピングテーブルを書き込むまで、最初のブロックを消去しない。
【００３６】
この時点までは、完結したフラッシュメモリ用のマッピングテーブルを記憶していることを仮定している。他の実施例では、複数のマッピングテーブルを、それぞれの論理アドレスのセグメント（範囲）に設ける。
【００３７】
この他の実施例では、マッピング制御回路１４は、マッピングテーブルの記憶用に割り当てられた一組のブロック内の独立して選択可能なそれぞれのページから、それぞれの範囲用のマッピングテーブルをプログラムおよびロードする。別の実施例では、マッピング制御回路１４は、マッピングテーブルに当たるセグメントの識別子を、当該マッピングテーブルが記憶されているフラッシュメモリ１０のページにプログラムするように構成されている。起動時に、マッピング制御回路１４は、割り当てられたブロックを検索して、各セグメントの識別子を含む順序的に最後のページを見つける。マッピング制御回路１４はこれらのページをマッピングテーブルメモリ１２にコピーして、アドレスの変換中に使用することが好ましい。
【００３８】
プロセッサ１６が新たなページの書込みを要求すると、マッピング制御回路１４は前述のように新たなマッピングテーブルを生成するが、プロセッサ１６が書込みを要求する論理アドレスを含むセグメントの論理アドレスのみについて生成する。しがたって、マッピング制御回路１４は、当該セグメント用の新たなマッピングテーブルを、マッピングテーブルの記憶用に割り当てられた一組のブロック内のマッピングテーブルに追加するに過ぎない。例えば、異なるセグメント用のマッピングテーブルを、異なる形式の斜線で図４ａ，ｂに示す。
【００３９】
図５に、割り当てられたブロックが満杯である際に、書込み中に起こることを示す。この場合、マッピング制御回路１４は、更新したセグメント用の新たなマッピングテーブルを、マッピングテーブルの記憶用に割り当てられた一組のブロックのうち空きのブロックの１つ４２に書き込む。これに加えて、いくつかの実施例では、マッピング制御回路１４は、他のセグメント用の現在のマッピングテーブルを、空きのブロックの１つ４２にコピーする。このことを図の矢印により図式的に示すが、もちろん、これらのマッピングテーブルの内容は、フラッシュメモリ１０の代わりにマッピングテーブルメモリ１２からコピーすることもできる。その後、マッピング制御回路１４は、フラッシュメモリ１０に満杯のブロック４０を消去させる。これにより、マッピング制御回路１４が起動時に、どのブロックが有効なマッピングテーブルを含むかを識別することを可能にする。
【００４０】
古いブロック４０を誤って消去していない場合、マッピング制御回路１４は、満杯のブロック４０が空きでないブロック４２と組み合わされていることを検出して、起動時に満杯のブロックを消去する。マッピング制御回路１４はまず、全てのセグメント用のマッピングテーブルが満杯でないブロック４２内に記憶されていることを検証することが好ましい。記憶されていない場合には、マッピング制御回路１４はまず、満杯のブロック４０内のコピーされていないセグメント用の順序的に最後のマッピングテーブルを検索して、満杯のブロック４０を消去する前に、これらのマッピングテーブルを満杯でないブロック４２にコピーする。
【００４１】
代案として、まず新たなマッピングテーブルを空きのブロック４２に書き込む際に、他のセグメント用のマッピングテーブルをコピーせず、満杯のブロック４０を消去しない。この場合、マッピング制御回路１４は、誤った遮断の場合と同様に、起動時にブロックを読み出すことがまだ可能である。他のブロック４２が満杯になるまで、満杯のブロック４０の消去を延期することができる、というのは、起動時にマッピング制御回路１４は、どのブロックが満杯でないかを検出することによって、どのブロックが最後に書き込まれかを、まだ検出することができるからである。この代案では、マッピング制御回路１４は、満杯でないブロックが満杯になりそうな際のみに、満杯のブロック４０を消去する必要がある。この場合、マッピング制御回路１４はまず、あるセグメント用のマッピングテーブルが満杯でないブロック４２内にまだ記憶されていなければ、これらのセグメント用のマッピングテーブルをコピーすることが好ましい。すなわち、満杯でないブロック４２内にまだプログラムされていないマッピングテーブルを追加した後に、満杯でないブロック４２が１つの空きページを残すのにちょうど十分な空間を有するまで、消去を延期することができる。
【００４２】
他の実施例では、マッピングテーブルの記憶用に割り当てられた一組のブロックが３つ以上のブロックを含む。このことは例えば、これらのブロックに記憶したデータ（例えばマッピングテーブル）が、１つのブロックから他のブロックにオーバーフローし得るほど大きい場合に有利であり得る。この場合、例えば割り当てられたブロックは、所定のシーケンスで使用することができる。その場合は、上記一組のうち少なくとも最も長らく更新していないブロックを消去して、マッピングテーブルを記憶するために再使用することが好ましい。起動中に、マッピング制御回路１４は空きのブロックを位置検出し、これを利用してシーケンスの開始／終了を決定し、このシーケンスから、マッピング制御回路は、記憶しているデータの最新バージョンを検出する。
【００４３】
図６に、異なるブロックを異なるセグメント用に使用する実施例を示す。この場合、４つのブロック６０を同数のセグメント用に設け、ブロック６０の１つが満杯である場合用に予備ブロック６２を設ける。動作中に、マッピング制御回路１４が書込み要求を処理する際に、マッピング制御回路１４は、書込み要求によって変更されたセグメント用の新たなマッピングテーブルを、当該セグメント用の前のマッピングテーブルを含むブロック内にプログラムする。当該セグメント用のブロック６０が満杯である場合、マッピング制御回路１４は新たなマッピングテーブルを予備ブロック６２内にプログラムする。そして、この予備ブロックは、当該セグメント用のブロックになり、その後にマッピング制御回路１４は、当該セグメント用の古いブロックを消去する。一実施例では、ページに書き込む際に、セグメントの識別子を新たなブロックにプログラムするか、あるいは、こうした識別子をブロックの各ページ中にプログラムすることができる。
【００４４】
起動時に、マッピング制御回路１４は、割り当てられたブロック６０，６２の各々を検査して、これらのブロックをどのセグメント用に使用するかを決定する。ブロックからの順序的に最後のマッピングテーブルを、セグメント用のマッピングテーブルとして使用する。電源遮断により、１つのセグメント用のデータを含む割り当てられたブロック６０，６２が２つ存在する場合、マッピング制御回路１４は、これらのブロックから満杯でないブロックを選択し、その他のブロックを消去して、満杯でないブロックからの順序的に最後のマッピングテーブルを使用する。
【００４５】
一実施例では、マッピングテーブルメモリ１２は、全てのセグメント用のテーブルを並列的に含み、メモリマッピングテーブルはいかなる論理アドレスも即座に変換することができる。この実施例では、マッピング制御回路１４は、全てのセグメント用のマッピングテーブルをマッピングテーブルメモリ１２にロードする。他の実施例では、マッピングテーブルメモリ１２は、セグメントの限定された部分集合用のマッピングテーブルのみ、例えば１つのセグメント用のマッピングテーブルのみを、一度に記憶する。この実施例では、マッピング制御回路１４は、当該セグメント用のマッピングテーブルがマッピングテーブルメモリ１２内に存在しないセグメント内の論理アドレスを受信した際に、割り当てられたブロック、６０，６２または４０，４２からのマッピングテーブルを用いて、１つのセグメント用のマッピングテーブルを他のセグメント用のものに置き換える。
【００４６】
セグメント用の整数個のマッピングテーブルがブロックに適合する実施例を示してきたが、このことは必要でないことは明らかである。セグメント用のマッピングテーブルのサイズが、セグメント用の整数個のマッピングテーブルでブロックを満たすことができないサイズである際に、マッピング制御回路１４は、最終セグメント用のマッピングテーブルを、図５の場合には一方のブロックから他方のブロックにオーバーフローさせて書き込むことができる。この場合、オーバーフローしているマッピングテーブルの後に他のマッピングテーブルを記憶ない場合に、マッピング制御回路１４は起動時に、オーバーフローしているマッピングテーブルを使用して、完全なマッピングテーブルを次のブロック内に書き込むまで最初のブロックを消去しない。図６の場合、セグメント用の完全なマッピングテーブルを、新たに割り当てたブロックに書き込み、そしてすぐに、前に割り当てたブロックを空きにすることが好ましい。
【００４７】
一実施例では、所定組のブロックを、マッピングテーブルの記憶用に割り当てる。この実施例では、この所定組のブロックは所定のアドレスに位置し、このためマッピング制御回路１４は、これらの所定のアドレスにあるブロックを参照するように設計することができる。しかし、このことは、割り当てられたブロックがより早く損耗する欠点を有し得る。代案として、変化する１つまたは複数のブロックをマッピングテーブルを記憶するために割り当てることができ、メモリでバックアップされたＲＡＭを設けて、割り当てられた１つまたは複数のブロックへのポインタを記憶することができる。
【００４８】
代案の実施例では、連結リスト構造を用いて、マッピングテーブルを記憶するために割り当てられた一組のブロックを規定する。これを図７ａに示す。ここではフラッシュメモリ７１全体をブロックに分割して概略的に示す。フラッシュメモリ内の所定の物理アドレス（例えばアドレスゼロ）にあるベース（基本）ブロック７０を用いて、１つ以上のベースポインタを記憶する。このベースブロックを拡大したもの７０ａを、ベースポインタ位置７２とともに示す。この位置からのベースポインタは、他のポインタを記憶している他のブロック７４を指示（ポイント）する。この他のブロックを拡大したもの７４ａを、マッピングテーブルを記憶するために割り当てられたブロック７６を指示するポインタを有するベースポインタ位置７５とともに示す。
【００４９】
起動中に、マッピング制御回路１４はまず、ポインタ７２をベースブロック７０からロードし、このポインタを使用して他のブロック７４をアドレス指定し、このブロックから、マッピング制御回路１４は、マッピングテーブルの記憶用に割り当てたブロック７６へのポインタをロードする。マッピング制御回路１４は、その後の使用のためにこのポインタを保存し、このポインタを使用して、マッピングテーブルの記憶用に割り当てられたブロック７６から現在のマッピングテーブルをマッピングテーブルメモリ１２にロードする。このことは例えば、前に記載したいずれかの方法を用いて行うことができる。
【００５０】
なお、ブロック７０，７４の各々は、１つの有効なポインタのみを含む。したがって、これらのブロックは、マッピングテーブルを有するブロック７６を、ベースブロック７０または中間ブロック７４内の１つのダイレクトポインタによって全く同様に発見することができたという意味で冗長である。これらの冗長なブロックを足し合わせて、ベースブロックを更新する必要のある頻度を低減する。
【００５１】
さらに、この構造は、マッピングテーブルを記憶するためのブロック７６として異なる物理ブロックを割り当てて、同一ブロックを他よりずっと頻繁に消去することを回避することができる利点がある。割り当てられたブロック７６を変更する毎に、割り当てられたブロック７６を指示するブロック７４内に新たなポインタ７５を書き込む。少なくとも置き換え可能なブロック（割り当てられたブロック７６および中間ブロック７４）の各々が、消去された回数を示すカウンタ値を記憶し、マッピング制御回路１４は、このカウンタ値が閾値を超えると、関連するブロックを異なるブロックに置き換えるように構成可能であることが好ましい。例えばブロックを消去する毎にカウンタ値を書き込む際に、このカウンタ値を１だけ増加することができる。
【００５２】
同様に、時間と共に、異なる物理ブロックを中間ブロック７４用に用いて、新たなポインタ値を記憶する前に同一ブロックを過度に頻繁に消去することを回避することができる。中間ブロック７４を変更する毎に、中間ブロック７４を指示するベースブロック７０内に新たなポインタ７２を書き込む。なお、中間ブロック７４の変更の頻度は、割り当てられたブロック７６の変更の頻度より低い。一例では、割り当てられたブロック７６をＮ１回（例えばＮ１＝８）消去する毎に、割り当てられたブロック７６用に異なる物理ブロックを選択する。したがって、中間ブロック７４は、割り当てられたブロックをＮ２回（例えばＮ２＝１０００００、又はより一般的にいえば、ブロックを消去してまだデータを記憶するために利用することができる最大回数より小さい任意の整数）消去する毎に、１回だけ更新する必要がある。中間ブロック７４に対応する物理ブロックをＮ２回消去すると、この物理ブロックも置き換えられる。したがって、こうした置き換えは、割り当てられたブロック７６の消去をＮ１×Ｎ２回した後に発生する。こうして、より遅い損耗が中間ブロック７４に生じ、ベースブロック７０にはさらに少ない損耗が生じる。
【００５３】
代案として、中間ブロック７４を全く利用せずに、割り当てられたブロック７６を直接指示するベースブロック７０内のポインタ７２を利用することができる。このことは、フラッシュメモリのより効率的な使用、およびマッピングテーブルのより高速の検索を提供する。しかし、ベースブロックの損耗は増加する。少し時間をおいて、ポインタ値を有するブロックを消去しなければならず、このことは不可避の損耗の増加をもたらす。こうした損耗を低減するために、中間ブロック７４内の中間ポインタを、ベースブロック７０と割り当てられたブロック７６との間に使用する。
【００５４】
他の代案として、中間ブロックのチェーン（連鎖）を用いることができ、つまり、割り当てられたブロック７６を指示するチェーン内の最後のブロックを除いて、ベースブロック７０内のポインタ７２がチェーン内の最初のブロックを指示し、チェーン内の次のブロックの各々が、チェーン内のその次のブロックを指示する。このようにして、ベースブロックの損耗を低減することができる。中間ブロックが割り当てられたブロックからより遠いほど、これらのブロックを更新する必要性はより低い。したがって、所定の物理アドレスを有するベースブロック７０を、これが損耗するほど頻繁な更新から保護することができる。
【００５５】
固定の所定長のチェーンを使用することができる。代案として、動的に適応可能な長さを用いることができる。この場合、チェーン内の最終の中間ブロックが、当該ブロックのポインタが上記割り当てられたブロックを指示することの指標を記憶する（あるいは、チェーンの終点から所定距離にあるブロックが、チェーンに沿って所定距離にあるブロックがこうしたポインタを記憶していることを示す）ことが好ましい。一実施例では、マッピング制御回路１４が閾値を上回る更新頻度を検出すると（例えばベースブロック７０が消去された回数が閾値Ｔを上回ると）、マッピング制御回路１４はチェーンの長さを増加させる。したがって、チェーンの長さを使用の種類に適応させて、ベースブロック７０の過度の損耗を回避することができる。一実施例では、チェーンの長さの延長を用いて、閾値回数より多いベースブロック７０の更新を回避する。このことは例えば、ベースブロック７０が例えば閾値（Ｔ＝１０００００）回更新されると、追加的な中間ブロックをチェーン内に追加し、ベースブロック７０の最終回の消去後に、新たなブロックへのポインタをベースブロック７０内に書き込み、そして、次の中間ブロックへのポインタを新たな中間ブロックに書き込むことによって実現することができる。新たな中間ブロックを閾値Ｔ回消去した場合等に、ベースブロックの役割を果たす新たな中間ブロックを用いてこのことを繰り返すことができる。
【００５６】
他の実施例では、チェーンはツリー（木）構造の一部である。すなわち、チェーンからのポインタを記憶するいくつかのブロックは、他のブロックへの他の有効なポインタも記憶し、これらの他のブロックも、１つ以上の他のポインタ、または論理アドレス−物理アドレスのマッピングテーブル（の一部）を記憶する。起動時に、マッピング制御回路１４は、ツリー構造の全てのブランチ（枝、分枝）のポインタを追跡して、マッピングテーブル（の一部）を見つける。
【００５７】
複数の有効なポインタを記憶するブロックは同時に、ツリー構造内の分岐（分岐点）を有するノードに対応する。ツリー構造内の最終ノード（リーフ（葉）ノード）はマッピングテーブルの一部分を指示する。任意の深さのツリー構造を用いることができる。ツリー内のいくつかのノードは、分岐しないノードであり、ツリー構造内の次の１つのノードのみを指示するノードであることが好ましい。これらのノードは単に、ツリー構造の深さ（ルート（根）ノードとリーフノードとの間のノード数）を増加させる働きをし、リーフノードの数は増加させない。したがって、ルートノード用の１つ又は複数のポインタを記憶するブロックの更新頻度を低減することができる。
【００５８】
こうした分岐しない複数のノードは直列に使用することが好ましい。また、ノードの層全体（所定の深さ、即ちルートノードから等距離にある全てのノード）を非分岐にすることが好ましく、連続した複数の層のノードを非分岐にすることがより好ましい。これらの層は、単にツリー構造の深さ（ルートノードとリーフノードとの間のノード数）を増加させる働きをし、リーフノードの数を増加させる働きはしない。したがって、ルートノードに対する１つ又は複数のポインタを記憶するブロックの更新頻度を低減することができる。所望すれば、ツリー構造の深さを動的に増加させて更新頻度をさらに低減することができる。
【００５９】
他の実施例では、複数のブロックを、マッピングテーブル又はその一部分を記憶するために割り当てる。このことは例えば、古い割り当てられたブロック内の古いマッピングテーブルを消去する前に、新たに割り当てられたブロック内に新たなマッピングテーブルを記憶する実施例に適用することができる。代案として、このことは例えば、論理ブロックアドレスのそれぞれのセグメント用のマッピングテーブルをそれぞれのブロック内に記憶する実施例に適用することができる。
【００６０】
図７ｂは、この実施例を示す。この実施例では、ベースブロック７０は、それぞれ中間ブロック７４，７８への第１および第２ポインタ７２，７２ａを含み、これらの中間ブロックの各々は、それぞれ割り当てられたブロック７６，７９へのポインタ７５，７５ａを含む。この実施例では、起動中に、マッピング制御回路１４は、まずポインタ７２，７２ａをベースブロック７０からロードし、これらのポインタを使用して他のブロック７４，７８をアドレス指定し、マッピングテーブルの記憶用に割り当てられたブロック７６，７９へのポインタをロードする。マッピング制御回路１４は、その後の使用のためにこれらのポインタを保存し、これらのポインタを用いて、現在のマッピングテーブルまたはそのセグメントを、マッピングテーブルの記憶用に割り当てられたブロック７６から、マッピングテーブルメモリ１２にロードする。このことは例えば、前に記載した方法のいずれかを用いて行うことができる。
【００６１】
割り当てられたブロック７６，７９の一方の代わりに他のブロックを、マッピングテーブルの記憶用に使用し始める際に、マッピング制御回路１４は、中間ブロック７４，７８内のポインタのうち、置き換えられた方の割り当てられたブロック７６，７９を指示していた方のポインタを変更する。マッピング制御回路１４は、ポインタを変更する前に、新しいマッピングテーブル（またはマッピングテーブルのセグメント）を、新たに割り当てられたブロック内に記憶することが好ましい。
【００６２】
２つのポインタ７２，７２ａをベースブロックに記憶する構造を示してきたが、代案が可能であることは明らかである。例えば、２つのポインタの代わりに、単一の中間ブロックへの単一のポインタを記憶することができ、この中間ブロックが、割り当てられたブロック７６，７９への２つのポインタを記憶する。このことは、必要なブロックがより少数であるという利点があるが、より多くの消去動作を必要とするので、より損耗をもたらす。他の例として、３つ以上の割り当てられたブロック７６，７９を用いる際に、３つ以上のポインタを（ベースブロック７０または中間ブロック７４，７８内に）記憶することができる。代案として、互いに所定の物理的関係にある（例えば連続した物理アドレスを有する）ブロックを、中間ブロック７４，７８または割り当てられたブロック７６，７９用に用いる際に、中間ブロック７４，７８の一方または割り当てられたブロック７６，７９の一方への単一のポインタを使用することができる。
【００６３】
前の例では、有効なポインタだけを各ブロック内に記憶することを示したが、このことは、マッピング制御回路１４が、ベースブロック７０および中間ブロック７４，７８内のポインタ値を変更する毎にこれらのブロックを消去して再書込みする（あるいは中間ブロック７４，７８を置き換える）ことを意味する。代案として、マッピング制御回路１４は、前に記憶したポインタを消去することなしに、ポインタを有するベースブロック７０または中間ブロック７４，７８内の新しいページに、新たなポインタ値の各々を書き込むように構成することができる。
【００６４】
図７ｃに、連続したポインタ７２，７５用の連続したページの使用法を示す。ポインタ値を含むページを斜線で示す。各場合において、斜線を付けた最下部のページ（ポインタ値を含み、かつ最高アドレスを有するページ）が有効なポインタ値を含む。より上部の（より低いアドレスを有する）ページは、より古い（無効な）ポインタ値を含む。代案の実施例では、マッピング制御回路１４は、ポインタに付随するバージョン番号を書き込み、このバージョン番号は、テーブルを書き込む（さもなければ、所定シーケンスに従って変化する）毎に増加する。この実施例では、最新のバージョン番号を有するマッピングテーブルを選択することによって、マッピングテーブルの有効なバージョンを識別することができる。
【００６５】
起動中に、マッピング制御回路１４は、例えば、所定のページ列内のポインタを有するページであって、空きページが後続するページを検索することによって、有効な（最新に記憶した）ポインタ値を無効なポインタ値と区別する。この所定のページ列は例えば、物理アドレスの列とすることができる。検索は、例えば二分探索（バイナリサーチ）法（まずブロック内の中ほどのあるページが空きであるか否かを検査し、そして、最初に検査したページが空きである場合または空きでない場合にそれぞれ、前半または後半内の中ほどのあるページを検査し、等を、検査したページの両側に隣接するページがすでに検査したページになるまで行う方法）とすることができる。この実施例は、起動中のより長い探索時間を代償にして、必要な消去動作の頻度がより少ないという利点がある。
【００６６】
代案の実施例では、マッピング制御回路１４はポインタに付随するバージョン番号を書き込み、このバージョン番号は、新たなポインタを書き込む（さもなければ、所定シーケンスに従って変更する）毎に増加する。この実施例では、最新のバージョン番号を有するポインタを選択することによって、ポインタの有効バージョンを識別することができる。さらに他の実施例では、マッピング制御回路１４は、更新をバージョン番号とともに、いずれかの中間ブロックに書き込むことができ、例えば他のブロックが満杯である場合は、書込み後に他のブロックを消去する。
【００６７】
バージョン番号は周期的に変化させることができる。バージョン番号は、適正なブロックを見つける目的で満杯のブロックおよび空きのブロックを検査する代わりに、ブロック内のポインタを有するページの位置と組み合わせて用いることができる。この場合、例えば４つの異なるバージョン番号の短い周期で十分である。
【００６８】
他の実施例では、マッピング制御回路は、新たな中間ブロックへの書込み前に満杯の中間ブロックに「ダーティ」フラグを設定し、起動時に適正なブロックの選択を補助するように構成することができる。この場合、マッピング制御回路１４はまず、ダーティとしてマークされていない中間ブロックを使用しようとする。このブロックが（エラーにより）空きである場合、マッピング制御回路１４はダーティのブロックに頼る。
【００６９】
（図７ｂの場合のように）複数の有効なポインタ値を並列的に使用する実施例では、複数の並列的なポインタ値を、これらのポインタ値のランクの識別子を伴って記憶することができる。この場合、起動中に、マッピング制御回路１４は、ランク毎の有効な（最新に記憶した）ポインタ値を検索し、これらのポインタ値は、ほとんどが、所定シーケンス内で、同じランクの他のあらゆるポインタ値より進んだ位置にあったものである。
【００７０】
マッピング制御回路１４がポインタ値の記憶用に全てのページを使用し尽くし、新たなポインタ値を書き込まなければならない際に、マッピング制御回路１４はブロックを消去して、再び最上部から開始する。図８ａ〜ｃは、複数ブロックをポインタ値用に使用する代案実施例を示す。ベースブロック７０内のポインタ７２、８２は、第１中間ブロック７４および第２中間ブロック８４を参照する。最初に、図８ａに示すように、ポインタ値を変更する毎に、変更したポインタ値７５を第１中間ブロック７４内の新たなページに書き込み、第２中間ブロック８４は空きのままである。第１中間ブロック７４が満杯である際に、マッピング制御回路１４は、図８ｂに示すように、次に変更したポインタ値７５を第２中間ブロック８４の第１ページに書き込み、その後に図８ｃに示すように、古いポインタ値のブロックを消去する。
【００７１】
このようにして、更新の中断によるエラーを容易に回復することができる。起動中に、マッピング制御回路１４は、第１中間ブロック７４が満杯であるか否かを検査し、満杯である場合、１つ以上のポインタを第２中間ブロック８４から入手可能であるか否かを検査する。入手可能である場合、マッピング制御回路１４は第２中間ブロック８４からの最終ポインタを使用し、入手可能でない場合、マッピング制御回路１４は第１中間ブロック７４からの最終ポインタ値を使用する。第１中間ブロック７４が空きである場合、マッピング制御回路１４は第２中間ブロック８４からの最終ポインタ値を使用する。
【００７２】
なお、第２中間ブロック８４へのポインタ値の追加、および、古い第２中間ブロックの消去は、長い時間にわたって行う（例えば複数ポインタ値を第２中間ブロック８４に書き込むまで消去を遅らせる）ことができる、というのは、マッピング制御回路１４は起動時に、中間ブロックが満杯であるか否かを検査することによって、どの中間ブロックが有効なポインタ値を有するかを特定し、当該中間ブロックが空きでない場合は他の中間ブロックからの最終ポインタ値を使用し、それ以外の場合は、先行する中間ブロックからの最終ポインタ値を使用するように構成することができるからである。
【００７３】
この技術はベースブロック７０にも適用することができる。例えばベースブロック７０の全てのページを使用している際に、マッピング制御回路１４は、所定の予備ベースブロック（例えばブロックアドレス１を有するブロック）内の最初のページに次のポインタ値を書き込み、その後にベースブロック７０を消去する。例えば第２中間ブロック８４を変更する場合、マッピング制御回路１４は、古い中間ブロックへのポインタ値８２の後に（必要であれば）第２中間ブロック８４にポインタ値を追加し、第２中間ブロック８４内の最初のページにポインタ値を書き込む。
【００７４】
図９ａに、例えば図７ｂの場合のように、２つ以上の有効なポインタ値を並列的に使用する例を示す。並列的なポインタ値は、それぞれのランクに対応する（例えば連続した論理アドレス範囲用のマッピングテーブルの連続したセグメントのランクに対応し、並列的なポインタを第１および第２ポインタと称する）。それぞれの中間ブロックをそれぞれのランクに対するポインタ値の記憶用に割り当て、割り当てたランクを識別する情報（例えばランクに対応する数）を、ポインタ値を含むそれぞれの中間ブロックに記憶する。
【００７５】
有効な並列的なポインタの各々を、それぞれの中間ブロック７４，７８内の最後に占有された位置に記憶する。追加的なポインタ９２をベースブロック７０内に記憶し、このポインタは追加的な中間ブロック９４を指示する。他の中間ブロック７４，７８のいずれも満杯でない間は、この追加的な中間ブロック９４は空きのままである。この場合、マッピング制御回路１４は、新たなポインタ値を中間ブロック７４，７８内の連続したページに書き込む。中間ブロック７４，７８の一方が満杯であり、新たなポインタ値を追加しなければならない際に、マッピング制御回路１４はこの新たなポインタ値を追加的な中間ブロック９４に書き込む。これに加えて、マッピング制御回路１４は、このポインタのランクの識別子を追加的ブロック９４に書き込む。図９ｂに示すように、その後、マッピング制御回路１４は満杯の中間ブロックを消去する。この消去したブロックは今度は、追加的な中間ブロックの一部を想定し、つまり、ポインタ値を追加しなければならない時にある中間ブロックが再び満杯である際に、マッピング制御回路１４はこのポインタ値を、現在空きである追加的ブロックに書き込み、満杯のブロックを消去する。
【００７６】
起動時に、マッピング制御回路１４は、ポインタをベースブロック７０からロードして、どのポインタがランク毎の中間ブロックを指示するかを特定する。こうした中間ブロックの２つが同一ランクに対応する場合、マッピング制御回路１４は、これらの中間部ロックのうち満杯でない、または空きである方を選択して、上記割り当てられたブロックへのポインタをロードし、他方の中間ブロックが満杯である場合、このブロックを消去する。ランクに対する一方のブロックが満杯であり、他方が空きである場合、マッピング制御回路１４は、満杯のブロックからの最後に書き込んだポインタ値を使用する。
【００７７】
図１０ａ，ｂに、異なるランクのポインタ値１０５ａ，１０５ｂを共に同じブロック内に記憶し、各ポインタ値がそのランクの識別子を伴う実施例を示す。この実施例では、マッピング制御回路１４は、全てのランクに対する新たなポインタ値を同一の中間ブロック７４に、当該ブロックが満杯になるまで追加する。次に、あるランクに対する新たなポインタ値を書き込まなければならない際に、マッピング制御回路１４は、このランクに対する新たなポインタ値を追加的ブロック９４に書き込み、その他の１つまたは複数のランクに対する、１つまたは複数の有効なポインタ値を追加的ブロック９４にコピーする。その後に、マッピング制御回路１４は満杯のブロックを消去する。起動時に、マッピング制御回路１４は、ベースブロック７０内のポインタ値を使用して中間ブロックを特定し、空きでもなく満杯でもない中間ブロックを検索して、このブロックからの最後に書き込んだポインタ値を使用し、このブロックが全てのランクに対するポインタ値を生じさせなければ、マッピング制御回路１４は、他のブロックが満杯でなければ、残りの全てのランク対する、最後に書き込んだポインタ値を他のブロックからロードする。
【００７８】
なお、有効なポインタ値を２つ以上の可能なブロックから選択しなければならない実施例のいずれにおいても、マッピング制御回路１４は、例えば、空きでない他のブロックが利用可能な場合の満杯ブロックの消去、バージョン番号の使用、ダーティフラグの使用のような何らかのメカニズムを使用して、使用するブロックを決定するように構成することができる。また、矛盾が生じた場合、マッピング制御回路１４は、信頼性のある最終バージョンを識別することができる。例えば、マッピング制御回路が、ポインタが無効なマッピングテーブル（例えば、空のマッピングテーブル、または、異なる論理アドレスを同一の物理アドレスにマッピングするテーブル）を参照していることを判定した場合、マッピング制御回路はポインタの前のバージョンを用いることができる。このことは、マッピング制御回路１４が情報の置き換えを完了する前に情報を消去しないことが保証されている際に、最良のエラー訂正をもたらす。
【００７９】
他の実施例では、更新の回数を低減する。このことは、マッピングテーブルを更新する際に、マッピングテーブルに関連して、マッピングテーブルに記入すべきブロックを指定する「空き」ブロックのリストを記憶することによって行う。したがって、論理アドレスが第１ブロックの物理アドレスにマッピングされ、その後の第１ブロック内のデータの更新中に、マッピング制御回路１４が（例えば第１ブロックのそれ以上の損耗を回避するために）第１ブロックを第２ブロックに置き換えることを選択した場合、マッピング制御回路１４は、第２ブロックを空きリストから選択して、論理アドレスの識別子（例えば「タグ」）を第２ブロック内に記憶する。この場合、マッピング制御回路１４は新たなマッピングテーブルを書込まない。その代わりに、その後の起動時に、マッピング制御回路１４は、古いマッピングテーブルに関連して記憶した空きリストを使用して、空きリスト上のブロックのいずれかが更新に使用されたか否かを判定する。使用されている場合、マッピング制御回路１４は、マッピングテーブルの訂正を、これらのブロック内の論理アドレスの識別子から推測する。空きブロックのリスト上の全てのブロックを使用した場合のみに、マッピングテーブルの新たなバージョンを記憶する必要がある。
【００８０】
図１１に、この実施例において使用する、マッピングテーブルの情報を有するメモリからのブロック１１０を示す。このブロックは、マッピングテーブルの連続したバージョン１１２ａ〜ｃを含み、各バージョンは空きブロックのアドレスを有する「空きリスト」１１４ａ〜ｃを伴う。マッピングテーブル１１２ｃの最終バージョン、及びこれに関連する空きリスト１１４ｃを現在バージョンと称する。動作中には、マッピングテーブル１１２ｃの現在バージョン中にアドレスが出現する物理ブロックを代替ブロックを用いて更新しなければならない際に、マッピング制御回路１４は、関連する空きリスト１１４ｃからの最初に利用可能なアドレスを使用して、この最初に利用可能なアドレスによってアドレス指定したブロックに更新を書き込む。これに加えて、マッピング制御回路１４はタグをこの新たなブロックに書き込み、このタグは更新を適用する論理ブロックアドレスを識別する。マッピング制御回路１４は、新たなブロックにおける更新が完了した後に、現在のマッピングテーブル１１２ｃにまだ見られる古いブロックを消去する。
【００８１】
したがって、マッピング制御回路１４は、マッピングテーブルメモリ１２中のマッピングテーブルを更新することが好ましい。マッピング制御回路１４が、現在の空きリスト１１４ｃ中の全てのブロックを更新に使用したことを検出すると、マッピング制御回路１４は、マッピングテーブル及び消去した古いブロックのリストの新たなバージョンを、ブロック１１０内の古い空きリスト１１４ｃの後に（あるいはマッピングテーブルデータ用に使用した他のブロック内に）書き込む。各空きリストは複数のブロックのアドレスを含むことが好ましい。この場合、一旦、古い空きリスト１１４ｃを使い切ったときにのみ、マッピングテーブルおよび空きリストの新たなバージョンを書き込むことが好ましい。
【００８２】
起動時に、マッピング制御回路１４は、例えばブロック１１０内の空でない最後のページを検索することによって、空きリスト１１４ｃの現在バージョンを読み出す。そして、マッピング制御回路１４は、この空きリスト１１４ｃ上のアドレスによってアドレス指定されるページを参照して、データがこれらのページに書き込まれているか否かを判定する。書き込まれている場合は、マッピング制御回路１４はタグから、どの訂正をマッピングテーブルの現在バージョンに適用しなければならないかを決定する。したがって、各々が、論理ブロックのアドレスおよび物理ブロックのアドレスを当該論理ブロックについての更新データによって識別する１つ以上の訂正を決定する。一実施例では、マッピング制御回路１４は、マッピングテーブル１１２ｃの現在バージョンをブロック１１０からマッピングテーブルメモリ１２にコピーして、これらの訂正をマッピングテーブルメモリ１２中のマッピングテーブルに適用する。他の実施例では、マッピング制御回路１４は、訂正のリストをマッピングテーブルメモリ１２に記憶し、マッピングテーブルのエントリをブロック１１０からロードする際に、これらの訂正をマッピングテーブルのエントリに適用する。
【００８３】
マッピング制御回路１４は、空きリスト１１４ｃからのブロックを、これらのブロックのアドレスが空きリスト１１４ｃ中に出現する順序で、更新に使用することが好ましい。この場合、起動時に、マッピング制御回路１４は、空きリスト１１４ｃ上のブロックを、これらのブロックのアドレスが空きリスト中に出現する順序で、更新について検査し、一旦、あるブロックが更新されていないことを判定すると検査を中止することが好ましい。このことは起動を加速するが、ブロックの一部分のみが空きリスト１１４ｃに出現する際に、こうしたシーケンスを使用しないでも起動は非常に速い。
【００８４】
一旦、ブロックの更新バージョンが完全に書き込まれると、現在のマッピングテーブル１１２ｃ中に出現する古いブロックの各々を消去することが好ましい。したがって、データは失われない。しかし、マッピングテーブルおよび（好ましくは消去された全てのブロックが出現する）空きリストの新たなバージョンが書き込まれる直前まで、消去を遅延させることができる。また、マッピングテーブル１１２ａ〜ｃおよび空きリスト１１４ａ〜ｃを次々に記憶する実施例を示したが、マッピングテーブルと空きリストとの関連付けは他の方法で、例えば両方のバージョン番号を含めることによって実現することができることは明らかであり、ここではマッピングテーブルおよび空きリストを任意に記憶することができる。また、マッピングテーブルおよびこれに関連する空きリストを、異なるブロックに、例えば同じ順序で記憶して、関連性を提供することができる。
【００８５】
この技術は、上記の全ての実施例と組み合わせて、あるいはそれだけで利用することができることは明らかである。例えば、複数のブロックを用いて、空きリストおよびこれに関連するマッピングテーブルの複数バージョンを記憶することができ、新たなバージョンを新たなブロックに書き込んだ後にのみ、満杯のブロックを消去して、起動時に検索によって最新バージョンを見出すことができる。
【００８６】
他の実施例として、セグメント化したマッピングテーブルを使用することができ、この場合、更新したセグメントについての新たなバージョンを記憶する必要がある。この場合、それぞれの空きリストをそれぞれのセグメント用に用いることができ、あるセグメント用のブロックの更新は当該セグメントに用の空きリストを用いて実行される。しかし、全てのセグメント用の共通の空きリストを使用して、あらゆるセグメント用のブロックの更新を、全てのセグメント用の同一の共用空きリストを用いて実行することが好ましい。このことは、記憶する必要のあるマッピングテーブルの更新回数を低減する。なお、この場合、それぞれのセグメント内で参照するブロックのアドレスに制約を課さないことが好ましく、このことは、すべてのブロックが特定アドレスビットについて同じアドレス値を有する物理ブロックの各組に各セグメントをマッピングする際よりも少し長いアドレスが、セグメント用のマッピングテーブル内に必要であることを意味し得る。
【００８７】
さらに、複数セグメントを使用する場合、一実施例では、一部のセグメントのみ（例えば１セグメントのみ）のためのマッピングテーブル部分をマッピングテーブルメモリ１２にキャッシュ記憶する。このことは、小型のマッピングテーブルメモリ１２を使用することを可能にする。この場合、全てのセグメントについての訂正を、キャッシュ記憶するマッピングテーブルとともにマッピングテーブルメモリ１２に記憶することが好ましい。この場合、マッピング制御回路１４は、必要時に、新たなセグメント用のマッピングテーブルをフラッシュメモリのブロックからマッピングテーブルメモリにロードして、マッピングテーブルメモリ１２に記憶されている訂正を適用する。他の実施例では、マッピング制御回路１４は、セグメント用のマッピングテーブルをフラッシュメモリ１０からロードする前に、訂正を用いて論理アドレスをマッピングしようとするように構成することができる。このことはアクセス速度を増加させる。
【００８８】
他の実施例として、ポインタのチェーンを用いて、マッピングテーブルおよび空きリストを記憶しているブロック１１０（または一組のブロック）を識別することができる。このようにして、ブロック１１０（またはマッピングテーブルおよび空きリストを一緒にまたは別個に記憶している一組のブロック）を、損耗の問題なしに置き換えることができる。
【００８９】
空きリストの使用法は、ポインタのチェーンにも適用することができる。一実施例では、チェーン内にある中間ブロックへのポインタは、新たな中間ブロック用に使用するブロックを指示するポインタの空きリストに関連する。新たな中間ブロックを作成する際に、空きリスト上で識別されるブロックを使用し、新たなポインタ値をこのブロックに書き込む。これに加えて、（例えばバージョン番号を含めることによって）有効ブロックとしてのこのブロック内に情報を記憶し、ベースブロック内にあるこの中間ブロックへのポインタは更新しない。空きリストを使い切った場合のみに、ベースブロックを、新たな中間ブロックおよび空きリストへのポインタ値で更新する。
【００９０】
整数個のマッピングテーブルと空きリストをブロック内に適合させる実施例を示してきたが、このことが必要でないことは明らかである。マッピングテーブルと空きリストの合計サイズが、整数個のマッピングテーブルと空きリストで１ブロックを満たすことができないサイズである際に、マッピング制御回路１４は、最後のマッピングテーブルと空きリストを、一方のブロックから他方のブロックにオーバーフローさせて書き込むことができる。この場合、他のマッピングテーブルと空きリストを、オーバーフローしているマッピングテーブルの後に全く記憶しない場合に、マッピング制御回路１４は、起動時にオーバーフローしているマッピングテーブルと空きリストを使用して、完全なマッピングテーブルと空きリストを次のブロックに書き込んだ後まで、最初のブロックを消去しない。
【００９１】
図１２ａに、ブロックを直ちに完全に更新しない実施例を示す。ある論理ブロックに対する元の完結したデータ組を記憶する第１ブロック１２０を示す。この論理ブロックに対する更新データ１２３を記憶する第２ブロック１２２を示す。
【００９２】
一実施例では、マッピング制御回路１４は、例えば空きリスト１１４ｃから空きブロックを選択することによって、第１ブロック１２０にマッピングされる論理ブロックの一部を更新するコマンドに応答するように構成されている。この空きブロックが第２ブロック１２２になる。マッピング制御回路１４は、ブロックのデータの更新部分１２３のみを第２ブロック１２２に書き込む。マッピング制御回路１４が、その後にこの種のコマンドを受けると、同じ論理ブロック内、前に更新した記憶場所と重複しない記憶場所について、マッピング制御回路１４は新たに更新されたデータを第２ブロック１２２に書き込む。マッピング制御回路１４は、その後の他のコマンドに対してこのことを繰り返す。
【００９３】
その後のコマンドにおける更新が重複する場合、マッピング制御回路１４は第１ブロック１２０の残りの（まだ更新していない）記憶場所を第２ブロック１２２にコピーする。マッピング制御回路１４はまた、第２のブロック１２２が完結したことを示す情報を第２ブロック１２２に書き込む。その後に、第２ブロックは第１ブロック１２０の役割を引き継ぎ、マッピング制御回路１４は、更新を記憶する第２ブロックとして作用する新たなブロックを（例えば空きリスト１１４ｃから）選択する。その後に元の第１ブロック１２０を消去する。
【００９４】
いつでも、たとえばそれ以上の空きブロックが利用可能でない際に、マッピング制御回路１４は、第１ブロック１２０の残りの（まだ更新されていない）記憶場所を第２ブロック１２２にコピーすることができる。そして、マッピング制御回路１４はまた、第２ブロック１２２が完結したことを示す情報を第２ブロック１２２に書き込む。その後に、マッピング制御回路は第２ブロック１２２を第１ブロック１２０の役割に使用し、その後に元の第１のブロック１２０を消去する。一実施例では、マッピング制御回路１４は、装置を停止する際にもこの動作を実行する。
【００９５】
読出し中に、マッピング制御回路１４が論理ブロック用の読出しコマンドを受信した場合、マッピング制御回路１４は、第１および第２ブロック１２０，１２２がこの論理ブロック用に利用可能であるか否かを判定し、利用可能である場合は、読出し動作が、更新される記憶場所用の、第２ブロック１２２からの更新データ１２３に関係するか、更新しない値用の、第１ブロック１２０からの元のデータに関係するかを判定する。前者の場合は、マッピング制御回路１４は読出し動作を第２ブロック１２２に指向させ、後者の場合は、マッピング制御回路は読出し動作を第１ブロックに指向させる。
【００９６】
マッピング制御回路１４は、更新されたブロックの部分を示す別な訂正をマッピングテーブルメモリ１２に記憶して、読出し動作中に、更新されたデータ１２３を識別するために用いることが好ましい。例えば更新を書き込む際に、これらの別な訂正をマッピングテーブルメモリ１２に記憶する。
【００９７】
一実施例では、マッピング制御回路１４は、起動時に、空きリスト１１４ｃ用いて更新を回復する。この実施例では、マッピング制御回路１４は、空きリスト１１４ｃ上に挙げられた１つ以上のブロックについて、これらのブロックがデータ、及びどの論理ブロック用であるかを示すタグを含むか否かを検査をする。含む場合は、マッピング制御回路１４は、これらのブロックが、当該ブロックが完結していることを示す情報を含むか否かの検査を実行する。含む場合は、マッピング制御回路１４は、マッピングテーブル１１２ｃ内の上記論理ブロック用に識別されたブロックの代わりに、当該ブロックを使用する。マッピング制御回路１４が、データは含むが完結していないブロックを発見した場合、マッピング制御回路１４は、このブロックを第２ブロック１２２として使用し、マッピングテーブル１２２ｃ内に同じ論理ブロック用に挙げられたブロックを第１ブロック１２０として使用する。一実施例では、マッピング制御回路１４は、この場合に別な訂正を生成し、この別な訂正をマッピングテーブルメモリに記憶する。
【００９８】
図１２ｂに、更新されたデータ１２３に加えて、更新されたデータ１２３より前のアドレスについてコピーしたデータも記憶する実施例を示す。このことは、読出し用の別な訂正を単純化し、つまり、更新されたデータ１２３の終点までのデータを、第２ブロック１２２から読み出すことができ、更新されたデータ１２３の後のデータは、第１ブロック１２０から読み出す必要がある。このことは、ブロックに順に書き込むことしかできないフラッシュメモリ１０にとって特に有用である。この場合、書込み動作中に、マッピング制御回路１４はまず、更新されたデータまでのデータを、第１ブロック１２０から第２ブロック１２２にコピーし、そして更新されたデータ１２３を第２ブロック１２２に書き込む。
【００９９】
他の実施例では、マッピング制御回路１４は、別な書込みコマンドを検査して、この書込みコマンドが、第１ブロック１２０および第２ブロック１２２が当該論理アドレス用に使用中である論理アドレスに対するものであるか否かを判定する。そうである場合、マッピング制御回路１４は、この書込みコマンドが、ブロック内の更新されたデータの後の記憶場所に指向されているか否かを検査する。指向されている場合、マッピング制御回路１４は、更新されたデータ１２３の終点から別な書込みコマンドのアドレスの始点までのデータを、第１ブロック１２０から第２ブロック１２２にコピーし、その後に、この別な書込みコマンドのデータを第２ブロック１２２に書き込む。新たな書込みコマンド用の記憶場所が、第２ブロック内の既に書き込まれた部分より前にあるか重複する場合、マッピング制御回路１４は、第２ブロック１２２からのデータのコピーの後に、空きブロックを第３ブロック１２４として選択し、新たな書込みコマンド用のデータをこの第３のブロック１２４に書き込む。
【０１００】
一実施例では、マッピング制御回路１４は、第１、第２および第３ブロック１２０，１２２，１２４を使用中のままに維持する。更なる書込み動作が同じ論理ブロックに対して発生すると、さらに多くのブロックを使用することができる。この実施例では、マッピング制御回路１４は、読出しアドレスに応じて、これらのブロック１２０，１２２，１２４の１つからの読出し動作を実行する。したがって、マッピング制御回路１４は、これらブロック１２０，１２２，１２４の各々を識別し、かつブロックの位置を最新のデータが記憶されている所まで識別する別な訂正を記憶することができる。また、いつでも（例えば、それ以上の空きブロックが利用可能でない際に）メモリのマッピング制御回路１４は、全ての訂正を一掃して、最小に満たされているブロック１２４（前に最新であったブロック１２２等の役割を次に引き継ぐ）を完全に満たすことができ、この第３のブロック１２４に、このブロックが完結したことを示す情報を記憶することができる。マッピング制御回路１４は、その後に他のブロック１２０，１２２を消去し、更新されたメモリマッピングテーブルおよび空きリストをフラッシュメモリ１０に書き込むことができる。
【０１０１】
起動時に、マッピング制御回路１４は、空きリスト１２３ｃに挙げられたブロックを検索し、これらのブロックがデータを有するか否かを判定する。ある論理ブロック用のブロックが、当該ブロックが完結していることの指標を含む場合、マッピング制御回路１４は、マッピングテーブル中に上記論理ブロック用に挙げられたブロックの代わりに、このブロックを使用する。空きリスト中の１つ以上のブロックが同じ論理ブロック用のデータを含むが、これらブロックのいずれも、当該ブロックが完結していることを示していないことを、マッピング制御回路１４が発見した場合、マッピング制御回路１４は、発見したブロック１２２，１２４を参照する別な訂正情報を構成する。
【０１０２】
原則として、複数の追加的なブロック１２２，１２４がある論理ブロック用に使用中である際にマッピング制御回路１４が書込みコマンドを受信して、追加的な各ブロック１２２，１２４内の最後に更新した記憶場所の後の記憶場所にデータを書込み更新する際に、マッピング制御回路１４はこの更新を書き込む場所の選択肢を有する。最も古い（最も満たされている）追加的ブロックに書き込むことは、より新しいブロック内により大きな更新用の空間が残されているという利点を有し、このことは、追加的ブロックの必要性を低減する。しかし、最も新しい追加的ブロックに書き込むことも利用することができ、このことは、最も新しいブロック内の更新されたデータを、より古いブロック内のデータよりも拡張することができるという効果を有する。この場合、マッピング制御回路１４は、より古いブロックを消去することが好ましい。また、マッピング制御回路１４はこの場合、更新の順序を示す情報をブロック内に書き込んで、起動中に別な訂正を形成するために使用する琴が好ましい。
【０１０３】
本明細書では、チェーン内のポインタ及びマッピングテーブル内の物理ブロックのアドレスを共に、並びに空きリスト内のブロックアドレスを、ポインティング情報と称し、それぞれの機能に割り当てられたそれぞれの物理ブロックを識別するために使用する。これらの機能の代表的な例は、論理ブロックアドレス用のブロックとして機能するブロック、ポインタを提供するブロック、および空きリストを提供するブロックである。
【０１０４】
マッピング制御回路１４は、例えば、本明細書に記載したようにブロックを使用するための命令のプログラムをプログラムされたプログラマブル処理回路として実現することができる。代案として、マッピング制御回路１４の一部または全部を、本明細書に記載した機能を実行することに特化した回路として実現することができる。
【０１０５】
個別ブロックを指示するポインティング情報を使用し、個別ブロックを用いてポインティング情報（消去する単位であるブロック）を記憶する実施例を示してきたが、その代わりに、こうした消去の単位のグループを指示するポインティング情報を使用することができ、及び／または、単位のグループを用いて連続的な有効ポインタ値を記憶することができることは明らかである。
【０１０６】
（別な）訂正リストを、マッピングテーブルメモリ１２、好適には例えばＳＲＡＭやＤＲＡＭなどのＲＡＭメモリに記憶する実施例を示してきたが、代案として、追加的なＲＡＭメモリ（図示せず）を更新制御回路１４に結合して設け、訂正のリストを記憶することができることは明らかである。同様に、他の情報、例えばポインタのチェーンに従って得られた最終ポインタ、後の更新の書込みに使用する空でないブロックの識別子を、マッピングテーブルメモリ１２またはこうした追加的なＲＡＭメモリに記憶することができ、これにより、フラッシュメモリ１０中でこの情報を検索することは、起動時のみ、そして随意的に、その後の例外的時点、例えばリセット信号またはエラー信号の受信後のみにのみに実行する必要がある。
【０１０７】
明らかなように、いくつかの物理ブロックは、時間の経過と共に使用不能になることがあり、このことは例えば、こうしたブロックを特定回数以上消去した後の損耗、またはブロック内に生じる他のエラーによって生じる。このことが発生すると、マッピング制御回路１４はこれらのブロックの使用を回避する。一旦、ブロックの使用を放棄すると、当該ブロックをマッピングテーブルおよび空きリストから除去する。推移的に、マッピング制御回路１４は、マッピング制御回路１４がもはやフラッシュメモリ１０内で使用すべきでない物理ブロックアドレスの「不良リスト」を表現する情報を維持する。ブロックを放棄すると、このブロックは「不良リスト」に追加されるが、フラッシュメモリ１０内の空きリストまたはマッピングテーブルの即時の更新は必要ない。後者の更新は、空きリストを使い切るまで延期することができる。起動時に、マッピング制御回路１４は、空きリストまたはマッピングテーブル内で参照するブロックが不良リストにも存在するか否かについて不良リストを検査し、存在する場合、マッピング制御回路１４は、当該ブロックがこれらのリスト（空きリストまたはマッピングテーブル）のいずれにもないものとして動作する。
【図面の簡単な説明】
【０１０８】
【図１】メモリを有する装置を示す図である。
【図２】書込み動作を実行するフローチャートである。
【図３】起動するフローチャートを示す。
【図４】図４ａ〜４ｄは、ポインタの連続バージョンを有するメモリのブロックを示す図である。
【図５】異なるマッピングテーブルのセグメントポインタを有するメモリのブロックを示す図である。
【図６】異なるマッピングテーブルのセグメントポインタを有するメモリのブロックを示す図である。
【図７】図７ａ〜７ｃは、ポインタのチェーンを有するメモリのブロックを示す図である。
【図８−１】図８ａ、８ｂはポインタのツリーを有するメモリのブロックを示す図である。
【図８−２】図８ｃはポインタのツリーを有するメモリのブロックを示す図である。
【図９】図９ａ、９ｂはポインタのチェーンを有するメモリのブロックを示す図である。
【図１０】図１０ａ、１０ｂはポインタのチェーンを有する、メモリのブロックを示す図である。
【図１１】空きリストの使用法を示す図である。
【図１２】図１２ａ、１２ｂは空きリストの使用法を示す図である。
【図１】
2009521049.tif 000003
【図２】
2009521049.tif 000004
【図３】
2009521049.tif 000005
【図４ａ】
2009521049.tif 000006
【図４ｂ】
2009521049.tif 000007
【図４ｃ】
2009521049.tif 000008
【図４ｄ】
2009521049.tif 000009
【図５】
2009521049.tif 000010
【図６】
2009521049.tif 000011
【図７ａ】
2009521049.tif 000012
【図７ｂ】
2009521049.tif 000013
【図７ｃ】
2009521049.tif 000014
【図８ａ】
2009521049.tif 000015
【図８ｂ】
2009521049.tif 000016
【図８ｃ】
2009521049.tif 000017
【図９ａ】
2009521049.tif 000018
【図９ｂ】
2009521049.tif 000019
【図１０ａ】
2009521049.tif 000020
【図１０ｂ】
2009521049.tif 000021
【図１１】
2009521049.tif 000022
【図１２ａ】
2009521049.tif 000023
【図１２ｂ】
2009521049.tif 000024
【国際調査報告】
2009521049.tif 000025
2009521049.tif 000026