(57)【要約】  本発明は、フラッシュメモリなどの不揮発性メモリ（「ＮＶＭ」）の不規則なパリティ分布、及びメタデータタグを介した不規則なパリティの検出に関することができる。例えば、ＮＶＭの各コードワードが、ＮＶＭ内にランダムに分布できる１又はそれ以上のパリティページを含むことができる。ページをパリティページとして識別するために、このページのメタデータにパリティページマーカーを含めることができる。ＮＶＭの起動中、ページの論理−物理アドレスマッピングを含むアドレステーブルを作成することができる。しかしながら、パリティページマーカーを含むページについては、このアドレステーブルの作成中にスキップすることができる。また、コードワードに関連する２又はそれ以上のパリティページを有することにより、このコードワード内のエラーを修復するための追加の保護層を提供することもできる。【選択図】      なし【特許請求の範囲】
【請求項１】
複数のページを含む不揮発性メモリ（「ＮＶＭ」）にデータを記憶する方法であって、
前記複数のページの１つよりも大きなサイズの前記データに対して使用する符号化技術を選択するステップと、
前記符号化技術を前記データに適用して、パリティメタデータに値する少なくとも１つのページを生成するステップと、
前記データを前記複数のページの第１の部分にプログラムするステップと、
前記パリティメタデータを前記複数のページの第２の部分に記憶するステップと、
を含み、前記記憶するステップが、前記第２の部分の各ページのメタデータフィールドに、前記第２の部分が前記パリティメタデータを記憶していることを示すマークを付けるステップを含む、
ことを特徴とする方法。
【請求項２】
前記第２の部分が、少なくとも２つのページを含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記第２の部分が前記パリティメタデータを記憶していることを示す前記メタデータフィールドを、前記ＮＶＭの第２のメモリ位置に冗長的に記憶するステップをさらに含む、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記第２の部分が、前記ＮＶＭにわたる不規則な分布を含む、
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記第１の部分が、少なくとも１つの訂正不能ページを含んでいると判断するステップと、
前記パリティメタデータを使用して、前記少なくとも１つの訂正不能ページを修復するステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記不揮発性メモリが、フラッシュメモリを含む、
ことを特徴とする請求項１に記載の方法。
【請求項７】
各々が一意の物理アドレスに関連する複数のページを含む不揮発性メモリ（「ＮＶＭ」）の論理−物理マッピングアドレステーブルを構築する方法であって、
前記複数のページの第１のページを、
前記第１のページがパリティページであるか否かを示す、前記第１のページの第１のメタデータタグを読み取り、
前記第１のメタデータタグが、前記第１のページがパリティページでないことを示していると判断することに応答して、
前記第１のページの第１の論理アドレスを決定し、
前記第１の論理アドレスを前記第１のページの一意の物理アドレスとともに前記論理−物理間のマッピングのアドレステーブルに記憶し、
前記第１のメタデータタグが、前記第１のページがパリティページであることを示していると判断することに応答して、
前記第１の論理アドレスが前記アドレステーブルに記憶されないように前記第１のページをスキップする、
ことによって処理するステップを含む、
ことを特徴とする方法。
【請求項８】
前記ＮＶＭの電源がオンになったと判断するステップをさらに含み、前記第１のメタデータタグの前記読み取りが、前記ＮＶＭの電源がオンになったと判断することに応答して行われる、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記複数のページの各ページを、前記複数のページの次のページに進むことによって連続的に処理し、前記複数のページの最終ページが処理されるまで前記次のページに対して前記処理を行うステップをさらに含む、
ことを特徴とする請求項７に記載の方法。
【請求項１０】
前記第１の論理アドレスの決定が、前記第１のページのメタデータから前記第１の論理アドレスを読み取ることを含む、
ことを特徴とする請求項７に記載の方法。
【請求項１１】
複数のページを含む不揮発性メモリ（「ＮＶＭ」）を備え、
前記複数のページのサブセットがパリティページであり、
前記複数のページが複数のコードワードにグループ化され、該複数のコードワードの各コードワードが、前記複数のページのうちの少なくとも２つの連続ページと、少なくとも１つのパリティページとを含み、前記複数のコードワードの少なくとも第１のサブセットが、少なくとも２つのパリティページを含み、
前記ＮＶＭの前記ページへのアクセスを制御するためのプロセッサをさらに備え、
前記プロセッサが、各パリティページのメタデータフィールドに、前記ページがパリティページであることを示すためのマークを付けるように構成される、
ことを特徴とする電子装置。
【請求項１２】
前記複数のコードワードのうちの特定のコードワードのユーザデータに符号化技術を適用して、前記特定のコードワードに関連するパリティメタデータを生成するように構成されたエラー訂正符号モジュールをさらに備え、前記プロセッサが、前記特定のコードワードの少なくとも１つのパリティページに前記パリティメタデータを記憶するようにさらに構成される、
ことを特徴とする請求項１１に記載の電子装置。
【請求項１３】
前記プロセッサが、
特定のコードワードの各ページを検索し、
前記検索中に、前記特定のコードワードの訂正不能ページを識別し、
前記遭遇に応答して、前記特定のコードワード内の各ページのデータを、前記訂正不能ページまで左向きに走査してバッファし、
前記遭遇に応答して、右向きに走査して前記特定のコードワードの最後を判別し、
前記訂正不能ページよりも後の各ページを検索する時に、前記訂正不能ページのデータ、及び前記コードワード内の前記訂正不能ページよりも後の各ページのデータをバッファするようにさらに構成される、
ことを特徴とする請求項１１に記載の電子装置。
【請求項１４】
前記プロセッサが、パリティページマーカーに遭遇するまで左向きに走査することにより、前記特定のコードワードの先頭を判別するようにさらに構成される、
ことを特徴とする請求項１３に記載の電子装置。
【請求項１５】
前記プロセッサが、第１のページのメタデータタグに遭遇するまで左向きに走査することにより、前記特定のコードワードの先頭を判別するようにさらに構成される、
ことを特徴とする請求項１３に記載の電子装置。
【請求項１６】
前記プロセッサが、パリティページマーカーの次の非パリティページマーカーに遭遇するまで右向きに走査することにより、前記特定のコードワードの最後を判別するようにさらに構成される、
ことを特徴とする請求項１３に記載の電子装置。
【請求項１７】
前記プロセッサが、第１のページのメタデータタグに遭遇するまで右向きに走査することにより、前記特定のコードワードの最後を判別するようにさらに構成される、
ことを特徴とする請求項１３に記載の電子装置。
【請求項１８】
前記プロセッサが、前記バッファしたデータ、及び前記特定のコードワードに含まれる少なくとも１つのパリティページに基づいて、前記訂正不能ページを修復するようにさらに構成される、
ことを特徴とする請求項１３に記載の電子装置。
【請求項１９】
前記プロセッサが、
特定のコードワードが第１の数の推定されるパリティページを含むという事前推定に基づいて少なくとも２つのパリティ方程式を生成し、
前記特定のコードワードを検索し、
各ページを検索する時に、前記特定のコードワードの各ページのデータを使用して前記少なくとも２つのパリティ方程式の計算を更新する、
ようにさらに構成されることを特徴とする請求項１１に記載の電子装置。
【請求項２０】
前記プロセッサが、
各実際のパリティページのメタデータタグを読み取ることにより、前記特定のコードワードの最後を検索した時点で前記特定のコードワードに関連する第２の数の実際のパリティページを特定し、
前記第２の数が前記第１の数よりも少ないと判断し、
前記少なくとも２つのパリティ方程式の第２の数の前記更新された計算を除いて全て廃棄する、
ようにさらに構成されることを特徴とする請求項１９に記載の電子装置。
【請求項２１】
前記プロセッサが、
各実際のパリティページのメタデータタグを読み取ることにより、前記特定のコードワードの最後を検索した時点で前記特定のコードワードに関連する第２の数の実際のパリティページを特定し、
前記第２の数が前記第１の数に等しいと判断し、
前記少なくとも２つのパリティの方程式の前記更新された計算を使用して、前記特定のコードワードの少なくとも１つの訂正不能ページを修復する、
ようにさらに構成されることを特徴とする請求項１９に記載の電子装置。
【請求項２２】
前記ＮＶＭ及び前記プロセッサを含む集積回路パッケージをさらに備える、
ことを特徴とする請求項１１に記載の電子装置。
【請求項２３】
前記ＮＶＭを含む集積回路パッケージをさらに備え、前記プロセッサが、前記集積回路パッケージの外部のシステムオンチップに実装される、
ことを特徴とする請求項１１に記載の電子装置。
【請求項２４】
前記不揮発性メモリが、フラッシュメモリを含む、
ことを特徴とする請求項１１に記載の電子装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フラッシュメモリなどの不揮発性メモリの不規則なパリティ分布、及びこの不規則なパリティをメタデータタグを介して検出することに関することができる。
【背景技術】
【０００２】
一般に、大容量記憶には、ＮＡＮＤフラッシュメモリ及びその他の種類の不揮発性メモリ（「ＮＶＭ」）が使用される。例えば、ポータブルメディアプレーヤ又は携帯電話機などの消費者向け電子機器は、音楽、ビデオ、及びその他の媒体を記憶するために未処理のフラッシュメモリ又はフラッシュカードを有していることが多い。
【０００３】
ＮＡＮＤフラッシュメモリなどの不揮発性メモリには、メモリ位置に初期不良が含まれるものもあり、又は使用を通じて不良が出現することもある。また、使用可能なメモリ位置に記憶されているデータに、読み込み妨害又は電荷保持の問題などのその他のエラー誘発現象が発生することもある。従って、これらのメモリ位置に記憶されたデータを正確に検索できることを保証するために、「パリティデータ」を算出してデータとともに記憶することができる。例えば、これらのデータにエラー訂正符号を適用して、このようなパリティデータを生成することができる。
【０００４】
さらに、今日の消費者向け電子機器は、装置の動作を制御して（読み取り、書き込み、又は消去コマンドなどの）ＮＶＭへのアクセス要求を実行する埋め込みシステムを含むことが多い。電子装置に最初に電力が印加されると、この電子装置は、ＮＶＭを走査してＮＶＭの（例えば、ＮＶＭの各ページの）コンテンツを特定することができる。例えば、この走査中、電子装置は、各ページに関連する論理アドレスを識別することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願第１２／５６２，８６０号明細書
【特許文献２】米国特許出願第＿＿＿＿＿＿＿＿＿＿号明細書
【特許文献３】米国特許出願第１２／５０９，０７１号明細書
【発明の概要】
【課題を解決するための手段】
【０００６】
（ＮＡＮＤフラッシュメモリのような）フラッシュメモリなどの不揮発性メモリ（「ＮＶＭ」）内の不規則なパリティ分布のためのシステム及び方法を開示する。さらに、本明細書では、メタデータタグを介してこのような不規則なパリティ分布を検出するためのシステム及び方法を開示する。
【０００７】
いくつかの実施形態では、システムオンチップ及びＮＶＭを含むことができる電子装置を提供することができる。ＮＶＭは、ＮＡＮＤフラッシュメモリなどのフラッシュメモリ、又は他のいずれかの好適な種類の不揮発性メモリを含むことができる。システムオンチップは、ＮＶＭにアクセスするためのＮＶＭインターフェイスを含むことができる。いくつかの実施形態では、ＮＶＭインターフェイスが、ＮＶＭにユーザデータを記憶するためのファイルシステムからの書き込み要求、ＮＶＭに記憶されたデータを検索する（例えば、読み取る、又は別様にアクセスする）ための検索要求、或いはこれらの両方を受け取ることができる。
【０００８】
いくつかの実施形態では、全体として「コードワード」を構成するＮＶＭの（物理アドレスなどの）２又はそれ以上の連続するページにデータを記憶することができる。コードワードの各ページは、そのページのエラーを訂正するための（「内部ＥＣＣ」などの）ＥＣＣデータを含むことができる。さらに、コードワードには、１又はそれ以上の「パリティページ」を含めることができ、各パリティページは、全体としてのコードワードに関連する（「外部ＥＣＣ」などの）ＥＣＣデータを提供することができる。各パリティページは、コードワードのエラーを訂正するための追加の保護層を提供することができる。例えば、コードワードが「ｍ」個のパリティページを含む場合には、たとえコードワードが最大「ｍ」個の訂正不能ページを含む場合でも、このコードワード内のエラーを好適に訂正することができる（例えば、この場合、「訂正不能ページ」は、このページのエラーを訂正するのに不十分な可能性のある内部ＥＣＣデータを含むページを意味することができる）。
【０００９】
いくつかの実施形態では、パリティページが、ＮＶＭにわたって不規則に分布することができる。一例として、パリティページの「規則的な分布」は、常にＮＶＭのスーパーブロックの同じチップ番号に位置するパリティページを含むことができる。対象的に、パリティページの分布が不規則なＮＶＭは、必ずしも同じチップ番号に位置するとは限らず、むしろＮＶＭのあらゆる好適な位置に存在できるパリティページを含むことができる。同様に、コードワードは、（スーパーブロックの同じチップ番号などの）同じ位置で開始及び終了することに限定されず、開始位置及び終了位置が不規則に分布すること、及び長さが不規則に分布することを含むことができる。
【００１０】
このように、パリティページの不規則な分布は、あるデータをより強力に保護する役に立つことができる。一例として、重要度の高い情報を保護するためにより多くのパリティページを使用することができ、重要度の低い情報を保護するためにより少ないパリティページを使用することができる。別の例として、いくつかの実施形態では、エラーを起こしやすいページを保護するためにより多くのパリティページを使用することができ、エラーを起こしにくいページを保護するためにより少ないパリティページを使用することができる。
【００１１】
ＮＶＭメモリのパリティページは、不規則に分布することができるので、ＮＶＭのどのページ（例えば、物理アドレス）がパリティページであるかを直ちに認識できないこともある。どのページがパリティページであるかを判断するために、例えば、各ページのメタデータ情報に「パリティページマーカー」を含めることができる。ＮＶＭインターフェイス、又は電子装置の他の好適な構成要素がこのメタデータタグを読み取って、特定のページがパリティページであるか否かを判定することができる。
【００１２】
いくつかの実施形態では、電子装置の起動中に、ＮＶＭのページの論理−物理アドレスをマッピングするテーブルを生成することができる。このテーブルは、例えば、起動時にページ全体を走査してこれらの論理アドレスを読み取り、次にこれらの論理アドレス及び読み取ったページの関連する物理アドレスを論理−物理アドレステーブルに記憶することによって生成することができる。しかしながら、このようなテーブルに外部ＥＣＣデータを含めることが必要な場合もあるので、この走査中に各ページのパリティページマーカーを読み取ることができる。このパリティページマーカーが、ページがパリティページであることを示す場合には、このページをスキップして、このページの情報を論理−物理アドレステーブルに含めないようにすることができる。
【００１３】
いくつかの実施形態では、パリティページの不規則な分布が、ＮＶＭからのデータの検索に影響することがある。例えば、ＮＶＭからコードワードを検索している間に、訂正不能ページに遭遇することがある。しかしながら、パリティページの不規則な分布により、そのコードワードにどれほどのパリティページが関連しているかを直ちに認識できず、従って訂正不能ページを修復できるかどうかを直ちに認識できないことがある。従って、いくつかの実施形態では、コードワードが検索されている間に、このコードワードのデータをバッファすることができる。コードワードの最後に到達すると、ＮＶＭインターフェイス（又はその他の好適な構成要素など）は、そのコードワードにどれほどのパリティページが含まれているか、従って（もしあれば）このコードワードの訂正不能ページを修復できるか否かを判断することができる。訂正不能ページを修復できる場合、バッファしたデータ及びパリティページを使用して、この訂正不能ページを修復することができる。
【００１４】
いくつかの実施形態では、ＮＶＭインターフェイスが、コードワード内の最初の訂正不能ページに遭遇した時にのみ、コードワードのバッファを開始する。このシナリオでは、訂正不能ページに遭遇した場合、ＮＶＭインターフェイスが、コードワードを「左向きに走査」して、コードワードの全ての前のページ及び現在のページをバッファすることができる。次に、ＮＶＭインターフェイスは、コードワードの残り部分を検索する時に、コードワードの検索及びコードワードの残りのバッファを継続することができる。コードワードの最後に到達した時点でパリティページの数を特定することができ、好適な数のパリティページが存在する場合には、訂正不能ページを修復することができる。
【００１５】
いくつかの実施形態では、データをバッファするのではなく、訂正不能なコードワードの修復に必要な計算を「オンザフライ」で行うことができる。例えば、ＮＶＭインターフェイスは、検索中のコードワードに関連するパリティページが２つ（又は他のいずれかの好適な数）存在すると「推定」することができる。ＮＶＭインターフェイスは、コードワードの検索中に、検索したページのデータを使用して２つの計算を更新し、各計算を、推定されるパリティページの異なる方に関連付けることができる。コードワードの最後に到達した時点で、実際のパリティページの数及び訂正不能ページの数を特定することができる。（訂正不能ページがたった１つ又はそれ以下の場合、又は実際のパリティページが１つのみの場合などの）第２の計算が必要でない場合、第２の計算を廃棄することができる。（実際のパリティページが２つ存在する場合、訂正不能ページが２つ存在する場合などの）両方の計算が必要な場合、２つの計算を使用して訂正不能ページを修復することができる。
【００１６】
全体を通じて同じ参照記号が同じ部分を示す添付図面とともに以下の詳細な説明を検討すれば、本発明の上記の及びその他の態様及び利点がより明らかになるであろう。
【図面の簡単な説明】
【００１７】
【図１】本発明のいくつかの実施形態により構成される電子装置の概略図である。
【図２】本発明のいくつかの実施形態により構成される電子装置の概略図である。
【図３】本発明のいくつかの実施形態による不揮発性メモリの機能図である。
【図４】本発明のいくつかの実施形態による不揮発性メモリの機能図である。
【図５】本発明のいくつかの実施形態による、パリティの不規則な分布を示すスーパーブロックの機能図である。
【図６】本発明のいくつかの実施形態による、起動時に不揮発性メモリのアドレステーブルを構築する処理を示す図である。
【図７Ａ】本発明のいくつかの実施形態による、不揮発性メモリからデータを検索する処理を示す図である。
【図７Ｂ】本発明のいくつかの実施形態による、不揮発性メモリからデータを検索する処理を示す図である。
【図８】本発明のいくつかの実施形態による、不揮発性メモリからデータを検索する処理を示す図である。
【発明を実施するための形態】
【００１８】
図１は、電子装置１００の概略図である。いくつかの実施形態では、電子装置１００が、（カリフォルニア州クパチーノのＡｐｐｌｅ社から市販されているｉＰｏｄ（商標）などの）ポータブルメディアプレーヤ、（Ａｐｐｌｅ社から市販されているｉＰｈｏｎｅ（商標)などの）携帯電話機、ポケットサイズ・パーソナルコンピュータ、携帯情報端末（ＰＤＡ）、デスクトップコンピュータ、ラップトップコンピュータ、携帯ゲーム機、遠隔制御装置、及びその他のいずれの好適な種類の電子装置であってもよく、又はこれらの電子装置を含んでいてもよい。
【００１９】
電子装置１００は、システムオンチップ（「ＳｏＣ」）１１０及び不揮発性メモリ（「ＮＶＭ」）１２０を含むことができる。ＳｏＣ１１０は、制御回路１１２、メモリ１１４、エラー訂正符号（「ＥＣＣ」）モジュール１１６、及びＮＶＭインターフェイス１１８を含むことができる。ＮＶＭインターフェイス１１８、ＥＣＣモジュール１１６、及び制御回路１１２を、システムオンチップに含まれる別個のモジュールとして示しているが、これは本発明の実施形態の説明を単純化するためにすぎない。例えば、いくつかの実施形態では、これらのモジュールを全て別個の物理エンティティとすることができ、及び／又は独自の超小型電子チップとして形成することもできる。別の例として、いくつかの実施形態では、これらのモジュールを全て単一の超小型電子チップに形成することができ、またこれらのモジュールが同じ基板及び／又はハードウェアを共有することもできる。さらに別の例として、いくつかの実施形態では、これらのモジュールが、ハードウェア構成要素、ソフトウェア構成要素、又はこれらの両方のいくつかの部分を共有することもできる。従って、制御回路１１２及びＮＶＭインターフェイス１１８を統合した部分を、総称して「制御回路」と呼ぶこともある。
【００２０】
不揮発性メモリ１２０を使用して情報を記憶し、電子装置１００の電力が切断された時にこれを保持することができる。本明細書で使用する場合、及び状況に応じて、「不揮発性メモリ」は、データを記憶できるＮＶＭ集積回路、又はこのような（ＮＶＭ１２０などの）ＮＶＭ集積回路を含むＮＶＭパッケージを意味することができる。
【００２１】
不揮発性メモリ１２０は、フローティングゲート又は電荷トラップ技術に基づくＮＡＮＤフラッシュメモリ、ＮＯＲフラッシュメモリ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、強誘電ＲＡＭ（「ＦＲＡＭ（登録商標）」）、磁気抵抗ＲＡＭ（「ＭＲＡＭ」）、他のあらゆる既知の又は将来の不揮発性メモリ技術、或いはこれらのあらゆる組み合わせを含むことができる。いくつかの実施形態では、ＮＶＭ１２０が、外部電子装置１００である取り外し可能記憶装置を含むことができる。この場合、ＮＶＭ１２０は、例えば、ユニバーサルシリアルバス（「ＵＳＢ」）メモリドライブ、（フラッシュカードなどの）メモリカード、又は他のあらゆる好適な取り外し可能記憶装置を含むことができる。いくつかの実施形態では、電子装置１００にＮＶＭ１２０を組み込むことができる。この場合、ＮＶＭパッケージ１２０を、例えば電子装置の統合メモリとすることができる。
【００２２】
ＮＶＭ１２０は、複数のチップ（すなわち、集積回路）を含むことができ、この場合、各チップを１又はそれ以上の「ブロック」に編成すること、及び各ブロックを一度に消去することができる。各ブロックは、さらに「ページ」に編成することができ、この場合、各ページを一度にプログラムすること、及び読み取ることができる。例えば、各ページは、ＮＶＭの特定の「物理アドレス」に対応することができ、この物理アドレスにデータを書き込み、及び／又はこの物理アドレスからデータを読み取ることができる。（各チップからの、チップ内の位置又は「ブロック番号」が同じ１つのブロックなどの）ＮＶＭ１２０の対応するチップからのブロックは、「スーパーブロック」と呼ばれる論理記憶ユニットを形成することができる。さらに、ＮＶＭ１２０のチップは、あらゆる好適な数のブロック及びページを含むことができる。ページに加え、（物理ブロックアドレスなどの）物理アドレスを使用してＮＶＭ１２０の（ブロック等の）各メモリ位置を処理することもできる。
【００２３】
図１及びそれ以降の図、並びに様々な開示する実施形態を、フラッシュ技術を使用する観点から説明することがある。しかしながら、これは限定を意図するものではなく、他のあらゆる種類の不揮発性メモリを代わりに実装することができる。さらに、電子装置１００は、電力供給装置又はいずれかのユーザ入力又は出力構成要素などの他のあらゆる好適な構成要素を含むこともでき、これらについては、図が複雑になり過ぎないように図１には示してない。
【００２４】
上述したように、システムオンチップ１１０は、制御回路１１２、メモリ１１４、エラー訂正符号（「ＥＣＣ」）モジュール１１６、並びにＮＶＭインターフェイス１５０を含むことができる。制御回路１１２は、ＳｏＣ１１０、並びにＳｏＣ１１２及び／又は電子装置１００のその他の構成要素の一般的動作及び機能を制御することができる。例えば、制御回路１１２は、ユーザ入力及び／又はアプリケーションの命令に応答して、ＮＶＭ１２０からデータを取得し又はＮＶＭ１２０にデータを記憶するための読み取り又は書き込みコマンドをＮＶＭインターフェイス１１８に発行することができる。説明を明確にするために、制御回路１１２が記憶又は検索を要求するデータについては、たとえこのデータがユーザ又はユーザアプリケーションに直接関連しない場合でも「ユーザデータ」と呼ぶことができる。むしろ、ユーザデータは、（アプリケーションなどを介して）制御回路１１２により生成又は取得されたあらゆる好適な一連のデジタル情報を含むことができる。
【００２５】
制御回路１１２は、ハードウェア、ソフトウェア、及びファームウェアのいずれかの組み合わせ、並びに電子装置１００の機能を引き起こすいずれかの構成要素、回路又は論理回路を含むことができる。例えば、制御回路１１２は、ＮＶＭ１２０及び／又はメモリ１１４に記憶されたソフトウェア／ファームウェアの制御下で動作する１又はそれ以上のプロセッサを含むことができる。
【００２６】
メモリ１１４は、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）、同期ダイナミック・ランダム・アクセス・メモリ（ＳＤＲＡＭ）、ダブルデータレート（ＤＤＲ）ＲＡＭ、キャッシュメモリ、リード・オンリ・メモリ（ＲＯＭ）、他のいずれかの好適なメモリ、又はこれらのいずれかの組み合わせなどの、あらゆる好適な種類の揮発性又は不揮発性メモリを含むことができる。メモリ１４０は、不揮発性メモリにプログラムするための、又は不揮発性メモリ１２０から読み取るためのユーザデータを一時的に記憶することができるデータソースを含むことができる。いくつかの実施形態では、メモリ１４０が、制御回路１１２の一部として実現されるあらゆるプロセッサのためのメインメモリとして機能することができる。
【００２７】
ＥＣＣモジュール１１６は、リードソロモン（「ＲＳ」）符号、Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ（「ＢＣＨ」）符号、周期的冗長検査（「ＣＲＣ」）符号、或いはＥＣＣデータを生成するためのその他のあらゆる好適なエラー訂正又は検出符号などの１又はそれ以上のエラー訂正符号又はエラー検出符号を採用することができる。本明細書で使用する「ＥＣＣデータ」という用語は、エラー訂正及び／又は検出符号をユーザデータに適用することにより生成されるあらゆる好適なデータを意味することができ、このＥＣＣデータを使用して、ユーザデータの検証、ユーザデータの訂正、又はこれらの両方を行うことができる。
【００２８】
いくつかの実施形態では、ＥＣＣモジュールが、単一ページのユーザデータにエラー訂正符号を適用して「内部ＥＣＣデータ」を生成することができる。その後、この内部ＥＣＣデータを使用して、この単一ページのユーザデータを訂正及び／又は検証することができる。さらに、以下でより詳細に説明するように、いくつかの実施形態では、ＥＣＣモジュールが、（２又はそれ以上の連続ページなどの）コードワード全体のユーザデータにエラー訂正符号を適用することもできる。この場合、ＥＣＣモジュールは、コードワードのユーザデータを全体として訂正するために使用できる「外部ＥＣＣデータ」を生成することができる。この外部ＥＣＣデータを１又はそれ以上の「パリティページ」に記憶することができ、このパリティページを、この外部ＥＣＣデータの記憶専用のページとすることができる。パリティページ及び外部ＥＣＣデータについては、以下でより詳細に説明する。
【００２９】
ＥＣＣモジュール１１６は、ある「強度」を有することができ、このＥＣＣの「強度」は、ＥＣＣモジュール１１６により生成された内部ＥＣＣによって訂正できる（フリップ化ビットなどの）最大エラー数を示すことができる。例えば、ＥＣＣモジュール１１６は、エラー訂正符号を使用して、あるページ内の最大「ｔ」個のエラーを訂正することができ、あるページ内の最大「ｎ」個のエラーを検出することができる（ｎは、ｔよりも大きなエラー数とすることができる）。本明細書で使用する「ｔ個のエラー」という用語は、ＥＣＣコードがページ内で訂正できる最大エラー数を意味し、「ｎ個のエラー」は、ＥＣＣコードがページ内で検出できる最大エラー数を意味する。例えば、あるページがｔ個よりも多くのエラーを含む場合、このページは、内部ＥＣＣデータによって「訂正不能」とすることができる。同様に、あるページがｎ個よりも多くのエラーを含む場合、内部ＥＣＣデータは、このページ内にどれほどのエラーが存在するかを適切に判断することができない。
【００３０】
ＥＣＣモジュール１１６は、例えば、１又はそれ以上の線形フィードバックシフトレジスタ（ＬＦＳＲ）などのハードウェアの形で実現してもよく、或いはプロセッサにより実行されるソフトウェアの形で実現してもよい。ソフトウェアによる実現では、対応するプログラムコードを、例えばＮＶＭ１２０又はメモリ１１４に記憶することができる。
【００３１】
ＮＶＭインターフェイス１１８は、制御回路１１２とＮＶＭ１２０の間のインターフェイス又はドライバとして機能するように構成されたハードウェアとソフトウェアのあらゆる好適な組み合わせを含むことができる。ＮＶＭインターフェイス１１８に含まれるあらゆるソフトウェアモジュールに関して、対応するプログラムコードをＮＶＭ１２０又はメモリ１１４に記憶することができる。
【００３２】
ＮＶＭインターフェイス１１８は、制御回路１１２がＮＶＭ１２０にアクセスして、ＮＶＭ１２０の（ページ、ブロック、スーパーブロック、チップなどの）メモリ位置及びそこに記憶された（ユーザデータなどの）データを管理できるようにする様々な機能を実行することができる。例えば、ＮＶＭインターフェイス１１８は、制御回路１１２からの読み取り又は書き込みコマンドを解釈し、ＥＣＣモジュール１１６に、ＮＶＭ１２０に記憶するユーザデータを符号化するように指示し、ＥＣＣモジュール１１６に、ＮＶＭ１２０から読み取ったユーザデータを復号するように指示し、ガーベージコレクションを実行し、ウェアレベリングを実行し、ＮＶＭ１２０のバスプロトコルと互換性のある読み取り及びプログラム命令を生成することなどができる。
【００３３】
図２は、電子装置２００の概略図であり、この図には、様々な実施形態による電子装置１００（図１）のソフトウェア及びハードウェア構成要素のいくつかを詳細に示すことができる。従って、電子装置２００は、図１に関連して上述した特徴及び機能のいずれかを有することができ、逆もまた同様である。電子装置２００は、ファイルシステム２１０、ＮＶＭインターフェイス２１８、及びＮＶＭ２２０を含むことができる。ＮＶＭインターフェイス２１８は、例えば、図１のＮＶＭインターフェイス１１８に対応することができ、ＮＶＭドライバ２３２及びＮＶＭバスコントローラ２３４を含むことができる。ファイルシステム２１０及びＮＶＭドライバ２３２は、ソフトウェアモジュールとすることができ、ＮＶＭバスコントローラ２３４及びＮＶＭ２２０は、ハードウェアモジュールとすることができる。従って、ＮＶＭドライバ２３２は、ＮＶＭインターフェイス２１８のソフトウェア面を表すことができ、ＮＶＭバスコントローラ２３４は、ＮＶＭインターフェイス２１８のハードウェア面を表すことができる。
【００３４】
ファイルシステム２１０は、ファイルアロケーションテーブル（「ＦＡＴ」）ファイルシステムなどのあらゆる好適な種類のファイルシステムを含むことができ、電子装置２００のオペレーティングシステムの一部（図１のＳｏＣ制御回路１１２の一部など）であることができる。いくつかの実施形態では、ファイルシステム２１０が、Ｙｅｔ  Ａｎｏｔｈｅｒ  Ｆｌａｓｈ  Ｆｉｌｅ  Ｓｙｓｔｅｍ（「ＹＡＦＦＳ」）などのフラッシュファイルシステムを含むことができる。これらの実施形態では、ファイルシステム２１０が、以下で説明するＮＶＭドライバ２３２の機能の一部又は全部を実行することができ、従ってファイルシステム２１０とＮＶＭドライバ２３２は別個のモジュールであることも、又はそうでないこともある。
【００３５】
ファイルシステム２１０は、アプリケーション及びオペレーティングシステムのファイル及びフォルダ構造を管理することができる。ファイルシステム２１０は、電子装置２００上で実行されるアプリケーション又はオペレーティングシステムの制御下で動作することができ、このアプリケーション又はオペレーティングシステムによってＮＶＭ２２０から情報を読み取ること又はＮＶＭ２２０に情報を記憶することが要求された時に、ＮＶＭドライバ２３２に読み取り及び書き込みコマンドをそれぞれ与えることができる。ファイルシステム２１０は、各読み取り又は書き込みコマンドとともに、論理ページアドレス、又はページオフセットを含む論理ブロックアドレスなどの、ユーザデータをどこから読み取り又はどこに書き込むべきかを示す論理アドレスを提供することができる。
【００３６】
ファイルシステム２１０は、ＮＶＭ２２０と直接的な互換性のないＮＶＭドライバ２３２に読み取り及び書き込み要求を提供することができる。例えば、論理アドレスは、ハードドライブベースのシステム固有の規約又は協約を使用することができる。ハードドライブベースのシステムは、フラッシュメモリとは異なり、最初にブロックの削除を行わずにメモリ位置に上書きすることができる。さらに、ハードドライブは、装置の寿命を延ばすためにウェアレベリングを必要としない。従って、ＮＶＭインターフェイス２１８は、ファイルシステム要求を処理するための、及び他の管理機能を実施するためのメモリ固有の、ベンダ固有の、又はこれらの両方のいずれかの機能を、ＮＶＭ２２０に適した形で実行することができる。
【００３７】
ＮＶＭドライバ２３２は、トランスレーションレイヤ２３６を含むことができる。いくつかの実施形態では、トランスレーションレイヤ２３６を、フラッシュトランスレーションレイヤ（「ＦＴＬ」）とすることができる。書き込み動作時には、トランスレーションレイヤ２３６が、ＮＶＭ２２０上の未使用の消去済みの物理アドレスに論理アドレスをマッピングすることができる。読み取り動作時には、トランスレーションレイヤ２３６が、この論理アドレスを使用して、要求されたデータが記憶されている物理アドレスを特定することができる。各ＮＶＭは、ＮＶＭのサイズ又はベンダに応じて異なるレイアウトを有することができるので、このマッピング動作は、メモリ及び／又はベンダに特化したものとなり得る。トランスレーションレイヤ２３６は、論理−物理アドレスマッピングに加え、他にもあらゆる好適な機能を実行することができる。例えば、トランスレーションレイヤ２３６は、ガーベージコレクション及びウェアレベリングなどの、フラッシュトランスレーションレイヤに特有のその他の機能のいずれかを実行することができる。
【００３８】
ＮＶＭドライバ２３２は、ＮＶＭバスコントローラ２３４と相互作用して、（書き込み要求、読み取り要求、削除要求などの）ＮＶＭアクセス要求を完了することができる。例えば、ＮＶＭドライバ２３２は、ＮＶＭバスコントローラ２３４に、データを記憶又は検索するための、及び書き込み要求の場合には、対応する書き込むべきデータベクトルを記憶又は検索するための物理アドレスを提供することができる。ＮＶＭバスコントローラ２１６は、ＮＶＭ２２０へのハードウェアインターフェイスとして機能することができ、またバスプロトコル、データ速度、及びＮＶＭ２２０のその他の仕様を使用してＮＶＭ２２０と通信することができる。
【００３９】
ＮＶＭインターフェイス２１８は、本明細書では「メタデータ」と呼ぶこともあるメモリ管理データに基づいてＮＶＭ２２０を管理することができる。メタデータは、ＮＶＭドライバ２３２によって生成することもでき、又はＮＶＭドライバ２３２の制御下で動作するモジュールによって生成することもできる。メタデータは、例えば、（ファイルシステム２１０により提供される「論理アドレス」などの）論理アドレスと物理アドレスの間のマッピング、不良ブロック管理情報、ウェアレベリング情報、ガーベージコレクション情報、エラー訂正符号（「ＥＣＣ」）データ、又はこれらのいずれかの組み合わせを管理するために使用されるあらゆる情報を含むことができる。従って、一般に、本明細書で使用する「メタデータ」という用語は、一般に不揮発性メモリの動作及びメモリ位置を管理するために使用できるユーザデータについての又はこれに関連するあらゆる情報（及びユーザデータではない情報など）を意味することができる。
【００４０】
ＮＶＭインターフェイス２１８は、ＮＶＭ２２０にメタデータを記憶するように構成することができる。いくつかの実施形態では、ＮＶＭインターフェイス２１８が、ユーザデータに関連するメタデータを、ユーザデータを記憶した（ページなどの）位置と同じメモリ位置に記憶することができる。例えば、ＮＶＭインターフェイス２１８は、ユーザデータ、関連する論理アドレス、ユーザデータのＥＣＣデータ、及びその他のあらゆる好適なメタデータを、ＮＶＭ２２０の１つのメモリ位置に記憶することができる。別の例として、ＮＶＭ２２０のあらゆる好適なメモリ位置にメタデータを記憶することもできる。
【００４１】
上述したように、（図１のＮＶＭ１２０などの）不揮発性メモリは、チップ、ブロック、ページ、スーパーブロックなどに編成することができる。例えば、図３及び図４に、ＮＶＭ３２０の概略的なレイアウトを示す。図３及び図４は、ＮＶＭ３２０の組織的レイアウトを例示するためのものにすぎず、不揮発性メモリの実際の物理レイアウトを示すものではない。例えば、図３及び図４には、チップ０がチップ１に隣接するように示しているが、これは、これらのチップの機能関係を例示するためのものにすぎず、ＮＶＭ３２０の実際の物理レイアウトでは、これらのチップが互いに近くに位置することも、又はしないこともある。さらに、図３及び図４には、一定数のチップ、ブロック、及びページを示しているが、これは例示目的にすぎず、当業者であれば、ＮＶＭ３２０があらゆる好適な数のチップ、ブロック、及びページを含むことができると理解するであろう。一例として、ＮＶＭ３２０の各チップは、４０９６個のブロックを含むことができ、各ブロックは、そのブロックがＳＬＣブロックであるか、２−ｂｉｔＭＬＣブロックであるか、又は３−ｂｉｔＭＬＣブロックであるかどうかに基づいて、６４個、１２８個、又は１９２個のページを含むことができ、各ページは５１２バイトを含むことができる。
【００４２】
図３に示すように、ＮＶＭ３２０は、チップ０、チップ１、チップ２及びチップ３などの１又はそれ以上のチップ（すなわち、集積回路）を含むことができる。次に、各チップを１又はそれ以上の「ブロック」に編成することができる。例えば、チップ０を、ブロック０〜３に編成された形で示している。ＮＶＭ３２０の消去コマンド中には、メモリのブロック全体を一度に消去することができる。次に、チップの各ブロックを１又はそれ以上のページに編成することができる。例えば、チップ２の（ブロック３０２などの）ブロック０を、ページ０〜３に編成された形で示している。ＮＶＭ３２０の読み取り又は書き込みコマンド中には、全ページの読み込み又は書き込みをそれぞれ一度に行うことができる。ＮＶＭ３２０は、各チップからのチップ内の同じ位置又は「ブロック番号」を有する１ブロックを含む１又はそれ以上のスーパーブロックを含むこともできる。例えば、ＮＶＭ３２０のスーパーブロック０は、チップ０〜３の各々のブロック０を含むことができる。同様に、ＮＶＭ３２０のスーパーブロック１は、チップ０〜３の各々のブロック１を含むことができ、ＮＶＭ３２０のスーパーブロック２は、チップ０〜３の各々のブロック２を含むことができ、以下同様である。
【００４３】
ＮＶＭ３２０の各スーパーブロックは、スーパーブロックの各チップからの１ページを含むことにより形成される１又はそれ以上の「ストライプ」を含むことができ、各ページは、そのチップ内の同じページ番号を有する。例えば、図４に、ＮＶＭ３２０のストライプ３１０を示している。ストライプ３１０は、スーパーブロック０のチップ１〜３の各々の同じページ番号を含むことができる。ＮＶＭ３２０の動作中には、このストライプ及び／又はスーパーブロックのページを順に処理することができる。例えば、ストライプ３１０の読み取り又は書き込み動作中には、ページ３２０を処理し、その後ページ３３０を処理し、ページ３４０を処理し、そしてページ３５０を処理することができる。このように、ストライプ３１２に含まれるデータを、情報の「コードワード」と見なすことができる。具体的には、本明細書で使用する「コードワード」という用語は、不揮発性メモリの１又はそれ以上の連続するページに含まれる、全体として１つの情報を形成するデータを意味することができる。以下でより詳細に説明するように、コードワードは、単一のストライプに限定されるわけではなく、１又はそれ以上のストライプの連続するページからのデータを含むことができる。
【００４４】
ＮＶＭ３２０の各ページは、あらゆる好適な情報を含むことができる。例えば、これらのページは、ユーザデータ、メタデータ、又はこれらの両方を含むことができる。いくつかの実施形態では、ＥＣＣデータなどのメタデータをページに含めて、ＮＶＭ３２０に記憶された情報のエラー検出及び／又は訂正のために提供することができる。例えば、（図１のＥＣＣモジュール１１６などの）ＥＣＣモジュールは、単一ページのユーザデータにエラー訂正符号を適用して「内部ＥＣＣデータ」を生成することができる。次に、この内部ＥＣＣデータを使用して、この単一ページのユーザデータを訂正及び／又は検証することができる。一例として、図４に、ページ３２２、３３２、３４２及び３５２を含むことができるストライプ３１２を示す。ページ３２２、３３２、３４２及び３５２内のデータは、全体としてコードワード３９０を形成することができる。例えば、ページ３２２は、ユーザデータ３２４から成る第１の部分と、内部ＥＣＣデータ３２６から成る第２の部分とを含むことができる。説明を単純にするために図示してはいないが、ページ３２２は、ＮＶＭ３２０の管理又は動作のための他のあらゆる好適なデータ又は（位置データ、生成データなどの）メタデータを含むこともできる。上述したように、ＥＣＣデータ３２６は、好適なＥＣＣモジュールに、ページ３２２のユーザデータに対してエラー訂正符号を実行させて、このＥＣＣデータを生成することにより生成することができる。
【００４５】
（記憶されたデータを読み取ること、又はこのデータに別様にアクセスすることなどの）ページ３２２の検索中には、ページ３２２の内部ＥＣＣデータを使用して、ページ３２２のユーザデータの完全性を維持することができる。例えば、ページ３２２のユーザデータ内に「ｔ個」以下のエラーしか存在しない場合、このページの内部ＥＣＣデータを使用してこれらのエラー訂正することができる。同様に、ページ３２２のユーザデータ内にｎ個以下のエラーしか存在しない場合、このページの内部ＥＣＣデータは、ページ３２２内にどれほどのエラーが存在するかを識別することができる（例えば、この場合ｎの方がｔよりも大きいものとすることができる）。同様に、ページ３３２及びページ３４２などのページは、ユーザデータ及びこれらの関連する内部ＥＣＣデータを含むことができる。
【００４６】
いくつかの実施形態では、ＥＣＣデータを１又はそれ以上のページのユーザデータにさらに提供することができる。例えば、（図１のＥＣＣモジュール１１６などの）ＥＣＣモジュールは、コードワード全体のユーザデータにエラー訂正符号を適用して、「外部ＥＣＣデータ」を生成することができる。この外部ＥＣＣデータを使用して、コードワードのユーザデータを全体として訂正することができる。一例として、図４に、ページ３２２、３３２及び３４２のユーザデータに関連できる外部ＥＣＣデータ３５６を含むことができるストライプ３１２のページ３５２を示している。換言すれば、ページ３５２の外部ＥＣＣデータ３５６を使用して、コードワード３９０全体のエラーを訂正及び／又は検出することができる。外部ＥＣＣデータ３５６を生成するためには、上述したようにコードワード３９０全体に対して好適なエラー訂正を実行したはずである。
【００４７】
ページ３５２は、（例えば、単一ページのみのための内部ＥＣＣデータではなく）コードワード３９０全体のための外部ＥＣＣデータを含むことができるので、ページ３５２を「パリティページ」３５２と呼ぶことができる。本明細書で使用する「パリティページ」という用語は、２又はそれ以上のデータページのユーザデータ内のエラーを訂正及び／又は検出するための外部ＥＣＣデータを含むことができるＮＶＭのページを意味する。いくつかの実施形態では、パリティページを外部ＥＣＣデータ専用にすることができ、パリティページが独自のユーザデータを含まなくてもよい。さらに、図４には外部ＥＣＣデータ３５６を示し、これが（例えば、パリティページ３５２内の情報の全てのバイトを使用しているので）パリティページ３５２全体を満たしているが、これとは別に、外部ＥＣＣデータ３５６がページ３５２の一部しか満たさない場合もある。具体的には、外部ＥＣＣデータは、この外部ＥＣＣデータを保持するのに必要なだけのパリティページの空間しか使用しなくてよい。例えば、コードワード３９０のための外部ＥＣＣデータが４００バイトの情報を含み、パリティページ３５２が５１２バイトを記憶できる場合、この外部ＥＣＣデータは、パリティページ３５２の５１２バイトのうちの４００バイトしか占めなくてよい。
【００４８】
このようにすることで、これらのコードワード３９０の各ページ内のデータを２回保護することができる。最初に、各ページは、そのページの内部ＥＣＣデータによって保護される（例えば、内部ＥＣＣデータ３２６によってユーザデータ３２４を保護することができる）。一例として、ユーザデータ３２４がｔ個以下のエラーしか有していない場合、内部ＥＣＣデータ３２６を使用してこれらのエラーを訂正することができる。次に、パリティページ３５２の外部ＥＣＣデータ３５６を通じて、ユーザデータ３２２に第２の保護層を提供することができる。例えば、ユーザデータ３２２が、ｔ個よりも多くのエラーを有する場合、ページ３２２の内部ＥＣＣデータ３２６だけでは、ユーザデータ３２２を訂正するのに不十分な恐れがある。この場合、パリティページ３５２の外部ＥＣＣデータ３５６を使用して、ユーザデータ３２２を訂正することができる。例えば、コードワードのページのユーザデータ、及びパリティページの外部ＥＣＣデータに関わる方程式を生成することができる。説明を簡単にするために、一例として単純な加算方程式を以下に示す。
Ｘ＝Ａ＋Ｂ＋Ｃ  （１）
式中、Ｘは、パリティページ３５２の外部ＥＣＣデータに関連し、Ａは、ページ３２２のユーザデータに関連し、Ｂは、ページ３３２のユーザデータに関連し、Ｃは、ページ３４２のユーザデータに関連することができる。説明を単純にするために、方程式（１）を加算方程式として示しているが、これとは別に、Ｘ、Ａ、Ｂ、及びＣを含む他のあらゆる好適な方程式を使用することもできる。Ｂ及びＣが両方ともｔ個よりも少ないエラーしか含まないと仮定すれば、Ｂ及びＣのユーザデータを正しく認識することができる。Ａがｔ個よりも多くのエラーを有する場合、Ａは、Ａを訂正するのに内部ＥＣＣデータでは不十分な「訂正不能」ページとなり得る。この場合、方程式（１）をＡについて解くことにより、Ａの正しいユーザデータを求めることができる。
Ａ＝Ｘ−Ｂ−Ｅ  （２）
このように、パリティページ３５２の外部ＥＣＣデータ３５６を使用して、ページの正しいユーザデータを求めることができ、ＮＶＭ３２０のユーザデータに第２のレベルの保護を提供することができる。さらに、これにより、あるページがｔ個よりも多くのエラーを含んでいる場合（例えば、ページが「訂正不能」である場合）でも、このページのユーザデータを訂正することができる。
【００４９】
いくつかの実施形態では、ＮＶＭ３２０が、例えば、不揮発性メモリ内の他のデータよりも重要な又はエラーを起こしやすいユーザデータを含むことがある。このような場合、このようなデータに追加の保護を行うことが望ましい場合がある。例えば、コードワードに１つのパリティページが提供されている場合、ｔ個よりも多くのエラーを有するページが１つ以下の場合には、依然としてこのページ内のユーザデータを訂正することができる。しかしながら、コードワードが、ｔ個よりも多くのエラーを有するページを２つ又はそれ以上含む場合、（例えば、方程式（１）などの１つの方程式から２つの未知数を求めることはできないので）単一の外部ＥＣＣデータだけでは、これらの両方のページを訂正できない場合がある。従って、いくつかの実施形態では、（２又はそれ以上のパリティページなどの）２又はそれ以上のＥＣＣデータの組をコードワードに提供して、このコードワードのユーザデータに追加の保護を行うことができる。例えば、ＥＣＣモジュールは、コードワード全体のユーザデータに対して２つのエラー訂正符号を実行することができ、各エラー訂正符号により１組のＥＣＣデータを生成することができる。その後、この２組のＥＣＣデータをコードワードの２つのパリティページに記憶することができる。
【００５０】
いくつかの実施形態では、コードワードが、単一のストライプに限定されるのではなく、スーパーブロックの２又はそれ以上のストライプにわたることができる。例えば、図５に、不揮発性メモリのスーパーブロック５００を示す。例えば、スーパーブロック５００は、図３のＮＶＭ３２０のスーパーブロック０〜３のいずれかに対応することができる。図５には、スーパーブロック５００が、４つのチップ（すなわち、チップ０〜３）の各々からのブロックを含むものとして示し、これらのブロックの各々が４つのページ（すなわち、ページ０〜４）を有するものとして示しているが、これは例示目的にすぎない。これとは別に、スーパーブロック５００は、あらゆる好適な数のチップ及び／又はページを含むことができる。
【００５１】
図５に示すように、ページＡ１、Ｂ１及びＹ１は、単一のコードワード（「コードワード１」）を形成することができ、Ｙ１をコードワード１のパリティページとすることができる。同様に、Ａ１、Ｂ２、Ｃ２、Ｘ１及びＸ２は、単一のコードワード（「コードワード２」）を形成することができ、Ｘ１及びＸ２を、それぞれコードワード２のパリティページとすることができる。コードワード１及びコードワード２を、それぞれ３つ及び４つのページを有するものとして示しているが、これは例示目的であり、これとは別に、コードワード１及びコードワード２は、あらゆる好適な数のページを含むことができる。従って、図５には、コードワードがスーパーブロック５００のあらゆる好適な位置において開始又は終了することができ、特定の位置において開始及び終了することに限定されない（例えば、ストライプの最初から開始し、又はストライプの最後で終了することなどに限定されない）ことを示している。このように、不揮発性メモリのパリティページは、スーパーブロック内で不規則に分布することができる。
【００５２】
図５には、コードワードのユーザデータを保護するために、この単一のコードワードが２又はそれ以上のパリティページを含むことができることも示している。いくつかの実施形態では、重要度の高い情報を保護するためにより多くのパリティページを使用することができ、重要度の低い情報を保護するためにより少ないパリティページを使用することができる。別の例として、いくつかの実施形態では、エラーを起こしやすいページを保護するためにより多くのパリティページを使用することができ、エラーを起こしにくいページを保護するためにより少ないパリティページを使用することができる。
【００５３】
従って、コードワードは、これに関連する複数のパリティページを有することができるので、複数のページがｔ個よりも多くのエラーを有する場合（例えば、複数のページが「訂正不能」である場合）にもコードワードを訂正することができる。一例として、図５のコードワード２は、Ｘ１及びＸ２という２つのパリティページを有する。このように、２つのパリティページを利用できるので、コードワードのページのユーザデータ、及びパリティページのＥＣＣデータに関わる２つの好適な方程式を生成することができる。例えば、以下に２つの例示的な方程式を示す。
Ｘ１＝Ａ２＋Ｂ２＋Ｃ２  （３）
Ｘ２＝Ａ２＊Ｂ２＊Ｃ２  （４）
方程式（３）及び（４）は、例示を目的とするものにすぎず、２つの訂正不能ページの復元を十分にサポートする他のいずれの２つの方程式を使用してもよい。例えば、いくつかの実施形態では、第１の方程式を（ＧＦ（２）加算方程式などの）単純なＸＯＲ方程式とすることができ、第２の方程式をＧＦ（２ｘ）に基づくリードソロモン方程式とすることができ、この場合、ｘは、８又はその他のいずれかの好適な数に相当することができる。
【００５４】
従って、コードワード２の最大２ページがｔ個よりも多くのエラーを有する（例えば、「訂正不能」である）場合、（例えば、２つの方程式からは２つの未知数を求めることができるので）方程式（３）及び（４）を同時に解いて、これらのページの正しいユーザデータを求めることができる。このように、コードワードのための追加の外部ＥＣＣデータの組を生成することにより、追加の保護層を提供して、コードワードをデータエラーから保護することができる。同様に、コードワードを保護するために、あらゆる好適な数のパリティページ及び外部ＥＣＣデータの組を含めることができる。例えば、（例えば、ｔ個以上のエラーを有する）「訂正不能」なページがｎ個以下の場合、コードワードのために「ｎ」組の外部ＥＣＣデータを生成して、このコードワードを訂正することができる。
【００５５】
本明細書で使用する「訂正不能」又は「訂正不能ページ」という用語は、ｔ個よりも多くのエラーを有し、そのページ内の内部ＥＣＣデータによって訂正できないページを意味することができる。しかしながら、訂正不能ページを含むコードワードが（例えば、適切な数の外部ＥＣＣデータの組を有する）好適な数のパリティページを有する場合には、依然としてこの訂正不能ページを修復することができる。従って、本明細書で使用する「訂正不能ページ」という用語は、１又はそれ以上のパリティページの使用を通じてこのようなページを修復することができるので、このページを絶対に訂正できないことを意味するものではない。
【００５６】
図５のパリティページは不規則に分布しているので、（例えば、コードワードはあらゆる位置において開始及び終了できるので）スーパーブロックのパリティページがどこに位置するかを直ちに認識できないこともある。従って、いくつかの実施形態では、ページのメタデータに、どのページがパリティページであるかを示すためのマーカーを含めることができる。例えば、各ページのメタデータタグとして「パリティページマーカー」を含めることができる。一般に、このメタデータタグとして単一ビットを使用することができる。例えば、ページがパリティページである場合には、ビットを「１」とすることができ、ページがパリティページでない場合には、「０」とすることができ、又は逆であってもよい。或いは、パリティページマーカーのために他のあらゆる好適な数のビットを使用することもできる。
【００５７】
各ページのメタデータタグにパリティページマーカーを記憶することにより、システムのメモリ内の空間を節約することができる。例えば、パリティページマーカーを含んでいなければ、不揮発性メモリの各ページ、及びそのページがパリティページであるか否かを記録する（例えば、図１のＮＶＭ１２０又はメモリ１１４に記憶される）別個のテーブルを記憶することが必要となり得る。しかしながら、各ページが、別個のテーブルを維持する代わりにパリティページマーカーを含んでいる場合、あるページを（読み取り、又はそのデータに別様にアクセスすることなどの）処理のために検索する際に、システムは、そのページがパリティページであるかどうかを判断することができる。
【００５８】
ページがパリティページ又は非パリティページとして正しく識別されることを支援するために、このパリティページマーカーを含むメタデータタグを冗長的に記憶することができる。例えば、（図１のＮＶＭインターフェイス１１８などの）ＮＶＭインターフェイスは、書き込み要求に応答して、データ及びその関連するパリティページマーカーを（ページなどの）第１のメモリ位置に記憶し、このパリティページマーカーの冗長コピーを第２のメモリ位置に記憶することができる。こうすれば、たとえ第１のメモリ位置がアクセス不能になったとしても、メモリインターフェイスは、なおも第２のメモリ位置に記憶されたバックアップコピーからパリティページマーカーを回収することができる。従って、システムは、ページがパリティページであるか否かを依然として正確に判断することができる。２００９年９月１８日に出願された「不揮発性メモリのためのメタデータ冗長方式（ＭＥＴＡＤＡＴＡ  ＲＥＤＵＮＤＡＮＣＹ  ＳＣＨＥＭＥＳ  ＦＯＲ  ＮＯＮ−ＶＯＬＡＴＩＬＥ  ＭＥＭＯＲＩＥＳ）」という名称の、同一出願人による同時係属中の米国特許出願第１２／５６２，８６０号に記載されるように、パリティページマーカーに加えて、他のあらゆる好適なメタデータを冗長的に記憶することもでき、この特許出願はその全体が本明細書に組み入れられる。
【００５９】
ＮＶＭの各ページは、パリティページマーカーを含むことができるので、あらゆるコードワード内からそのコードワードのサイズを特定することができる。例えば、再び図５を参照して、ＮＶＭインターフェイス（又は電子装置の他のあらゆる好適な構成要素など）が、スーパーブロック５００のデータを走査（例えば、読み取り）しているものとする。一例として、ＮＶＭインターフェイスが、現在コードワード２のページＡ２を走査しているものとする。ＮＶＭインターフェイスは、コードワード２のサイズを特定するために、パリティページに遭遇するまで「左向きに走査」することができる。
【００６０】
本明細書で使用する「左向きに走査」という用語は、ＮＶＭのページを現在の処理方向とは逆の方向に走査することを意味する。例えば、図５では、「左向きに走査」するために、スーパーブロック５００のページをＡ２、Ｙ１、Ｂ１、Ａ１、・・・のような順序で走査することができる。ここでも、図５はＮＶＭの機能を示すものにすぎず、ＮＶＭの物理レイアウトを示すことは意図していないので、「左向きに走査」という用語は、ページの物理レイアウトを示すものではなく、ページを処理する順序を示すためのものにすぎない。さらに、左向きに走査する場合、この走査は、ページをラップアラウンドして、１つのストリップから別のストリップへ進むことができる。例えば、左向きに走査する場合、Ｃ１、Ｂ２、Ａ２、・・・のような順序でページを処理することができる。同様に、本明細書で使用する「右向きに走査」という用語は、ＮＶＭのページを現在の処理方向に走査することを意味する。例えば、図５では、「右向きに走査」するために、スーパーブロック５００のページをＹ１、Ａ２、Ｂ２、Ｃ１、Ｘ１、・・・のような順序で走査することができる。
【００６１】
従って、ＮＶＭインターフェイス（又は電子装置の他の好適な構成要素など）は、図示のようなコードワードのサイズを特定するために、ページＡ２から左向きに走査することができる。ＮＶＭインターフェイスは、パリティページ（すなわち、ページＹ１）に遭遇するまで左向きに走査し続けることができる。例えば、ＮＶＭインターフェイスは、ページのパリティページマーカーを読み取ることにより、そのページがパリティページであると判断することができる。ページＹ１は、前のコードワードの最後を示すことができるので、ＮＶＭインターフェイスは、コードワード２がページＹ１の右側のページ（すなわち、ページＡ２）から開始すると判断することができる。ＮＶＭインターフェイスは、コードワード２の最後を特定するために、パリティページ（すなわち、ページＸ１）に遭遇するまで右向きに走査することができる。その後、ＮＶＭインターフェイスは、非パリティページ（すなわち、ページＡ３）に遭遇し、従って新たなコードワードの指示が開始されるまで、右向きに走査し続けることができる。この結果、ＮＶＭインターフェイスは、これらの２つの走査から、（例えば、右向きの走査において２つのパリティページに遭遇したという理由で）コードワード２が２つのパリティページを有し、コードワードのサイズが（ページＡ２、Ｂ２、Ｃ２、Ｘ１及びＸ２などの）５ページの長さにわたると判断することができる。
【００６２】
いくつかの実施形態では、パリティページマーカーに加えて、又はパリティページマーカーの代わりに、ページは、「最初のページ」マーカーを含むことができる。例えば、あるページのメタデータに、このページがコードワードの最初のページであることを示すメタデータタグを含めることができる（例えば、ページＡ２が、最初のページのメタデータタグを含むことができる）。従って、この場合、コードワードの先頭を特定するために、ＮＶＭインターフェイスは、最初のページのメタデータタグに遭遇するまで左向きに走査することができる。
【００６３】
いくつかの実施形態では、不規則な分布のパリティページを含めると、電子装置の様々な動作に影響することがある。一例として、不規則な分布のパリティページは、装置の起動シーケンスに影響を及ぼすことがある。上述したように、ＮＶＭインターフェイスは、ＮＶＭのユーザデータの論理−物理アドレスマッピングを記憶することができる。具体的には、この論理−物理アドレスマッピングを維持するために別個のテーブル（すなわち「アドレステーブル」）を作成することができる。しかしながら、このアドレステーブルは、隣接位置、障害、読み取り動作の失敗による阻害作用、又は他の何らかのエラー誘発現象に起因して、無効になること（例えば、テーブルが更新されずにユーザデータが移動すること）、或いはエラーを生じること又は読み取り不能になることがある。従って、アドレステーブルの完全性を保持する助けとするために、ＮＶＭの起動時にこのテーブルを再構築することができる。例えば、起動時に、ＮＶＭの各ページを走査して、（ページのメタデータから）各ページの論理アドレスを読み取ることができる。その後、この論理アドレスをページの物理アドレスに関連付けて、アドレステーブルに記憶することができる。
【００６４】
しかしながら、パリティページは、ユーザデータを含まないこともあるので、一般的には、パリティページの論理アドレスをアドレステーブルに記憶する必要はないと考えられる。従って、電子装置の起動中にアドレステーブルを作成する際に、これらのページを「スキップ」することができる。しかしながら、パリティページの不規則な分布に起因して、システムがパリティページの位置を容易に認識できないこともある。従って、起動中に、各ページのパリティページマーカーを読み取ることができる。このパリティマーカーが、ページが非パリティページであることを示す場合、このページの論理アドレス及び関連する物理アドレスをアドレステーブルに記憶することができる。一方、パリティページマーカーが、ページがパリティページであることを示す場合には、このページをスキップし、このページの論理アドレスがアドレステーブルに記憶されないようにすることができる。
【００６５】
ここで図６を参照すると、本発明のいくつかの実施形態による処理６００の例示的なフローチャートを示している。（図１の電子装置１００などの）電子装置の起動時に、処理６００を実行してアドレステーブルを構築することができる。具体的には、処理６００を実行して、パリティページが不規則な分布した不揮発性メモリに関連するアドレステーブルを構築することができる。処理６００は、図１及び図２のＮＶＭインターフェイス１１８又は２１８などのあらゆる好適なメモリインターフェイスによってそれぞれ実行することができ、処理６００をそのように説明していることもある。しかしながら、メモリシステム又は電子装置内の他のあらゆる好適な（単複の）構成要素を、これらのステップを実行するように構成することもできると理解されたい。
【００６６】
処理６００は、ステップ６０２から開始することができる。例えば、ステップ６０２は、電子装置の起動時に行うことができる。ステップ６０４において、処理６００は、現在のページのパリティページマーカーを読み取ることによってＮＶＭのページを走査することができる。ステップ６０６において、パリティページマーカーを解析して、このページがパリティページであるか否かを判定することができる。例えば、「１」のパリティページマーカーは、ページがパリティページであることを示すことができ、「０」のパリティページマーカーは、ページがパリティページでないことを示すことができる。これとは別に、他のあらゆる好適なマーカー又はビットシーケンスを使用して、ページがパリティページであるか否かを示すことができる。
【００６７】
ページがパリティページでないと判定されたことに応答して、処理６００はステップ６０８へ進み、このページをアドレステーブルに追加することができる。具体的には、ステップ６０８において、ページの論理アドレスを読み取ることができる。ステップ６０８において、この読み取った論理アドレスをページの物理アドレスに関連付けて、アドレステーブルに記憶することができる。
【００６８】
ステップ６１２において、処理６００は、ＮＶＭ内に未だ走査されていないページ（例えば、物理的位置）がさらに存在するかどうかを判断することができる。さらなるページが存在することに応答して、処理６００は、ステップ６１６においてＮＶＭの次のページへ進むことができる。その後、ＮＶＭ全体が走査されてアドレステーブルが完成するまで、必要に応じてステップ６０４、６０６、６０８、６１０、６１２及び６１６をループ及び反復することができる。ＮＶＭ内に走査すべきページがこれ以上存在しないことに応答して、処理６００は、ステップ６１２からステップ６１４へ進んで処理を終えることができる。
【００６９】
ステップ６０６に戻ると、パリティページマーカーが、現在のページがパリティページであることを示すことに応答して、処理６００は、直接ステップ６１２へ進むことができる。このように、ステップ６０８及びステップ６１０を迂回することにより、パリティページの論理アドレスをスキップし、これがアドレステーブルに記憶されないようにすることができる。従って、処理６００を実行することにより、ＮＶＭインターフェイスは、ユーザデータを含むページ（例えば、非パリティページ）の論理−物理アドレスを含むアドレステーブルを構築する一方で、外部ＥＣＣデータしか含まない全てのページ（例えば、パリティページ）を迂回する。具体的には、ページがパリティページであると判断した時点で、処理３００は、このパリティページを無視し（例えば、このパリティページのメタデータの論理アドレス領域を無視し）、代わりに非パリティページが見つかるまでＮＶＭのページを走査し続けることができる。
【００７０】
パリティページの不規則な分布によって影響されることがあるシステム動作の別の例に、ＮＶＭからのデータの検索がある。例えば、データの検索は、いつパリティページが読み取られ、処理され、又はその記憶データに別様にアクセスさせるかを含むことができる。データを検索する際には、（ｔ個よりも多くのエラーを有するページなどの）１又はそれ以上の訂正不能ページに遭遇することがある。単一のパリティページ及び／又は規則的に分布するパリティページしか含まないシステムでは、システムが、コードワード内のどれほどの訂正不能ページを修復できるかを自動的に認識することができる。しかしながら、不規則な分布のパリティページを含むシステムでは、このシステムは、コードワードを修復できるかどうかを判断する前に、まずこのコードワードに関連するパリティページの数を特定することを必要とすることができる。例えば、コードワードの検索中に、２つの訂正不能ページに遭遇した場合、システムは、このコードワードが２(又はそれ以上の）組の外部ＥＣＣデータを有しているかどうかの判断を必要とすることができる。このコードワードが、２又はそれ以上の組の外部ＥＣＣデータを伴っている場合、この２つの訂正不能ページをエラーのないページに置き換えて、コードワードの信憑性を復元することができる。
【００７１】
上述したように、システムは、（例えば、コードワードが１組の外部ＥＣＣデータを有する場合には）方程式（１）、又は（例えば、コードワードが２組の外部ＥＣＣデータを有する場合には）方程式（３）及び方程式（４）などの方程式、又は他のあらゆる好適な方程式を適用して、ｔ個よりも多くのエラーを含むコードワード内の訂正不能ページを修復することができる。従って、いくつかの実施形態では、あるコードワードを検索する時に、このコードワードのデータをバッファすることができる。その後、コードワード全体の検索が完了した時に、システムは、どれほどの訂正不能ページが存在し、そのコードワードにどれほどのパリティページが利用可能であるかを判断することができる。この情報から、システムは、訂正不能ページを修復できるかどうかを判断することができ、できる場合には、バッファしているデータを適用して適当な方程式を解き、これにより訂正不能ページの正しい値を求めることができる。
【００７２】
いくつかの実施形態では、コードワードを検索する最初からコードワードをバッファするのではなく、訂正不能ページを検出した後にバッファを開始することができる。訂正不能ページを有していないコードワードはバッファしなくてもよいので、例えば、これによりシステム内のメモリを節約することができる。
【００７３】
一例として、システムが、図５のコードワード２を検索し、ページＢ２が訂正不能であると判断したとする。システムは、訂正不能ページに遭遇すると、（ページＡ２などの）そのコードワードの先頭に遭遇するまで左向きに走査することができる。次に、システムは、ページＢ２の左側にある１又は複数のページをバッファするとともに、ページＢ２自体もバッファすることができる。次に、システムは、ページＢ２の後のコードワードのページの検索及びバッファに進むことができる。さらなる訂正不能ページに遭遇したことに応答して、システムは、これらの訂正不能ページを修復するための好適な数のパリティページが存在する可能性があるので、コードワードのページの検索及びバッファを継続することができる。換言すれば、これらの訂正不能ページを修復するための好適な数の外部ＥＣＣデータの組がコードワードの最後に存在する可能性もあるので、システムは、訂正不能ページに遭遇した時点でコードワードが修復不能であると自動的に見なすことができない。システムは、コードワードの最後に行き着くと、（例えば、ページのパリティページマーカーを読み取ることによって）どれほどのパリティページが利用可能であるかを判断し、好適な数のパリティページが存在する場合には、（例えば、方程式（１）、（３）、（４）、又はいずれかの好適な数の外部ＥＣＣデータの組に関連する他のあらゆる好適な方程式を適用することによって）訂正不能ページを修復することができる。
【００７４】
いくつかの実施形態では、コードワードをバッファするのではなく、コードワードを検索している時に、ページを訂正するための１又はそれ以上の好適な方程式を「オンザフライで」計算することができる。一例として、システムは、コードワードを検索する時に、このコードワードが２つのパリティページ（又は他のいずれかの好適な数のパリティページなど）を伴っているかのようにページを処理することができる。従って、ページを検索する時に、このページのデータを使用して、方程式（３）及び方程式（４）（又はその他のあらゆる好適な方程式）などの方程式の計算をオンザフライで更新することができる。システムは、コードワードの最後に到達し、実際にどれほどのパリティページが存在するかを判断した時点で、例えば、両方の方程式を適用し、方程式の一方のみを適用し、方程式を適用せず、又はコードワードを廃棄することができる。例えば、２つの訂正不能ページ及び２つのパリティページが存在するとの判断時には、両方の方程式を適用してこれらのページを修復することができる。別の例として、１つの訂正不能ページ及び１つのパリティページが存在するとの判断時には、計算した方程式の一方を使用してこのページを訂正することができる（例えば、同時に他方の計算した方程式を廃棄することができる）。さらに別の例として、訂正不能ページが存在しないとの判断時には、修復の必要がないので、いずれの計算した方程式も使用しなくてよい。さらに別の例として、訂正不能ページを修復するのに十分なパリティページが存在しないとの判断時には、このコードワードを不正確なデータを有しているものとして廃棄することができる。同様に、コードワードを検索した時に、３又はそれ以上の方程式を計算する「オンザフライ」法を使用することもできる。
【００７５】
図７Ａ、図７Ｂ、及び図８には、不揮発性メモリのコードワードからデータを検索するための処理７００、７５０、及び８００をそれぞれ示す。処理７００、７５０、及び８００は、図１及び図２のＮＶＭインターフェイス１１８又は２１８などのあらゆる好適なメモリインターフェイスによってそれぞれ実行することができ、これらの処理をそのように説明していることもある。しかしながら、メモリシステム又は電子装置内の他のあらゆる好適な（単複の）構成要素を、これらのステップを実行するように構成することもできると理解されたい。
【００７６】
例えば、処理７００及び７５０では、コードワードのページのデータが検索された時に、このデータをバッファすることができる。その後、このバッファされたデータを使用して、コードワードの訂正不能ページを修復することができる。
【００７７】
処理７００は、ステップ７０２から開始することができる。７０４において、ＮＶＭから特定のデータの組を検索する要求を受け取ることができる。例えば、データを読み取る要求、データを処理する要求、又は別様にデータにアクセスする要求を受け取ることができる。ステップ７０６において、この要求を、関連する物理アドレスの組に変換することができる。例えば、特定のデータの組を記憶するページの物理アドレスを決定することができる。
【００７８】
ステップ７０８において、ステップ７０６の物理アドレスに記憶されたデータを検索することができる。データの検索中、処理７００は、ステップ７１０において、訂正不能ページに遭遇したかどうかを判断することができる。訂正不能ページに遭遇してないことに応答して、物理アドレスのデータの検索を「正常に」続行することができる。換言すれば、外部ＥＣＣデータに関連する、又は訂正不能ページを修復することに関連する追加ステップを実行することなくデータを検索することができる。
【００７９】
一方、処理７００は、訂正不能ページに遭遇したことに応答してステップ７１６へ進むことができる。ステップ７１６において、検索を要求されたデータをバッファすることができる。例えば、ＮＶＭは、訂正不能ページから開始して左向きに、その後右向きに走査して、ステップ７０６において決定された物理アドレスに記憶されているデータをバッファすることができる。その後、このバッファされたデータを使用して、訂正不能ページを修復することができる。例えば、このバッファされたデータを、このデータに関連する１又はそれ以上の外部ＥＣＣコードとともに使用して、訂正不能ページ修復することができる。その後、処理７００は、ステップ７１４において終了することができる。
【００８０】
図７Ｂに進むと、処理７５０は、例えば、コードワードのページのデータを検索する時に、このデータをバッファすることができる。処理７５０のステップのいくつかは、図７Ａの処理７００のステップの１又はそれ以上に対応することができる。例えば、処理７５０のステップは、処理７００のステップ７０８、７１０、７１２、及び７１４をより詳細に示すことができる。
【００８１】
処理７５０は、ステップ７５２から開始することができる。ステップ７５４において、コードワードの最初のページ（例えば、物理アドレス）を検索することができる。例えば、この「コードワード」は、処理７００のステップ７０６において決定された物理アドレスの組に対応することができる。ページのデータを検索するために、このページを読み取り、処理し、又はその記憶データにアクセスさせることができる。ステップ７５６において、処理７５０は、ステップ７５４において検索されたページが訂正不能であるかどうかを判断することができる。例えば、このページがｔ個よりも多くのエラーを有している場合、このページを訂正不能、従ってページの内部ＥＣＣデータではこのページのエラーを訂正できないものとすることができる。ページが訂正不能でないことに応答して、処理７５０は、ステップ７５８において、コードワードの最後に到達したかどうかを判定することができる。コードワードの最後に到達していない場合、処理７５０は、ステップ７５４へ戻って次のページ（例えば、物理アドレス）を検索することができる。或いは、コードワードの最後に到達した場合、処理７５０は、ステップ７６０において終了することができる。このように、コードワードのページがいずれも訂正不能でない場合、コードワード全体を検索することができ（すなわち、ステップ７５４、７５６、及び７５６をループすることにより）、処理７５０は、いずれのページもバッファさせることなく終了することができる。
【００８２】
ステップ７５６に戻ると、コードワードのページが訂正不能であることに応答して、ＮＶＭインターフェイスは、ステップ７６２において、そのコードワードの先頭まで「左向きに走査」することができる。例えば、ＮＶＭインターフェイスは、ページがパリティページであることを示す（メタデータタグなどの）パリティページマーカーを有するページに到達するまで左向きに走査することにより、コードワードの先頭を識別することができる。この場合、パリティページに直接続くページを、コードワードの先頭として特定することができる。別の例として、ＮＶＭインターフェイスは、最初にメタデータタグに遭遇し、従ってそのページがコードワードの最初のページであることが示されるまで左向きに走査することができる。ＮＶＭインターフェイスは、ステップ７５４において検索したページの左側にあるページ、及びステップ７５４において検索したページ自体をバッファすることができる。その後、処理７５０は、ステップ７６４及びステップ７６６において、コードワードの残りのページの検索及びバッファを継続することができる。
【００８３】
コードワードの最後に到達したこと、及びコードワード全体がバッファされたことに応答して、ステップ７６８において、パリティページ及び訂正不能ページの数を特定することができる。例えば、ＮＶＭインターフェイスは、訂正不能ページが検索された時に、これらのページの数の集計を保持しておくことができる。パリティページの数を特定するために、ＮＶＭインターフェイスは、これらのパリティページを、ページがパリティページでないことを示す（従って、コードワードの全てのパリティページを走査し終えたことなどを示す）パリティページマーカーを有するページに到達するまで「右向きに走査」することができる。
【００８４】
１又はそれ以上のパリティページの使用を通じてページを修復できない可能性がある例も存在し得る。これらの例では、ＮＶＭコントローラが、複数の訂正不能エラー処理ポリシのいずれか１つを呼び出すことができる。例えば、ユーザデータページが訂正不能である場合、ＮＶＭコントローラは、揮発性メモリのデータ構造にアクセスすることによってこのページを回復し、このページのメタデータを取得することができる。訂正不能エラーからの回復により、システムが動作を継続し、データの一貫性を保持できるようになる。訂正不能エラーから回復させるためのさらなる詳細は、例えば、Ｐｏｓｔ他による、＿＿年＿＿月＿＿日に（本願と同時に）出願された「不揮発性メモリのための訂正不能エラー処理方式（Ｕｎｃｏｒｒｅｃｔａｂｌｅ  Ｅｒｒｏｒ  Ｈａｎｄｌｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｎｏｎ−Ｖｏｌａｔｉｌｅ  Ｍｅｍｏｒｉｅｓ）」という名称の米国特許出願第＿＿＿＿＿＿＿号（代理人整理番号Ｐ８９０５ＵＳ１）に見出だすことができ、この開示はその全体が引用により組み入れられる。別の例として、インデックスページ（すなわち、論理セクタから物理アドレスへのマッピングを記憶するＮＶＭ内のページ）が訂正不能である場合、ＮＶＭは、復元動作を呼び出す前に、揮発性メモリのデータ構造にアクセスすることによってこのページを再構成しようと試みることができる。訂正不能エラーを有するインデックスページを処理するためのさらなる詳細は、例えば、Ｗａｋｒａｔ他による、２００９年７月２４日に出願された米国特許出願第１２／５０９，０７１号、及びＰＯＳＴらによる、＿＿年＿＿月＿＿日に（本願と同時に）出願された、「インデックスブロックのためのガーベージコレクション方式（Ｇａｒｂａｇｅ  Ｃｏｌｌｅｃｔｉｏｎ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｉｎｄｅｘ  Ｂｌｏｃｋ）」という名称の米国特許出願第＿＿＿＿＿＿＿号（代理人整理番号Ｐ８９０７ＵＳ１）において見出すことができ、これらの両開示はその全体が引用により組み入れられる。
【００８５】
ステップ７７０において、処理７５０は、コードワードが修復可能であるかどうかを判定することができる。例えば、パリティページの数が訂正不能ページの数以上である場合、このコードワードは修復できる可能性がある。別の例として、パリティページの数が訂正不能ページの数未満である場合、このコードワードは修復できない可能性がある。コードワードが修復可能であることに応答して、ステップ７７２において、このコードワードを修復することができる。例えば、（例えば、コードワードが１組の外部ＥＣＣデータを有している場合には）方程式（１）、又は（例えば、コードワードが２組の外部ＥＣＣデータを有している場合には）方程式（３）及び方程式（４）などの方程式、又はその他のあらゆる好適な方程式を計算して、訂正不能ページを修復することができる。その後、処理７５０は、ステップ７６０において終了することができる。一方、コードワードが修復可能でない場合、ステップ７７４において、このコードワードを、例えば不正確なデータを有するものとして廃棄することができる。
【００８６】
いくつかの実施形態では、これとは別に、処理７５０がステップ７６４から開始し、それよりも前のステップを省くことができる。例えば、そうすることで、最初に少なくとも１つの訂正不能ページが存在するかどうかを判断せずに、常にコードワードのデータをバッファするシステムを実現することができる。
【００８７】
図８に、不揮発性メモリのコードワードからデータを検索するための処理８００を示す。例えば、処理８００は、データを検索する時に、方程式を「オンザフライ」で計算して、コードワードの訂正不能ページを修復することができる。換言すれば、処理８００は、訂正不能ページのデータをバッファする必要なくこれらのページを修復することができる。説明を単純にするために図示してはいないが、処理８００は、処理７００のステップ７０４及びステップ７０６などの、コードワードの検索要求を受け取り、この検索要求を物理アドレスの組に変換する事前のステップをさらに含むことができる。
【００８８】
処理８００は、ステップ８０２から開始することができる。ステップ８０４において、この処理は、コードワードが「ｍ」個のパリティページ（例えば、「ｍ」組の外部ＥＣＣデータ）を有し、これらのパリティページに関連する方程式が「ｍ」個存在すると推定することができる（例えば、「ｍ」は１、２、３、４、又はその他のあらゆる好適な数であってよい）。例えば、ｍが１に等しい場合、処理８００は、方程式（１）を推定することができる。別の例として、ｍが２に等しい場合、処理８００は、方程式（３）及び方程式（４）を推定することができる。
【００８９】
ステップ８０６において、コードワード内の最初のページを検索することができる。例えば、このページを読み取り、処理し、又はその記憶データに別様にアクセスさせることができる。ステップ８０８において、ステップ８０４で特定した１又は複数の方程式の計算を、検索したページのデータを使用して更新することができる。ステップ８１０において、処理８００は、コードワードの最後に到達したかどうかを判定することができる。最後に到達していないことに応答して、処理８００はステップ８０６へ戻り、ステップ８０８及びステップ８１０を繰り返すことができる。このように、コードワードの最後に到達するまでステップ８０６、８０８及び８１０をループすることにより、コードワードを継続的に進行してページを検索し、この検索したページのデータを使用して計算を更新することによってステップ８０４の方程式を「オンザフライ」で計算することができる。
【００９０】
コードワードの最後に到達したことに応答して、処理８００は、ステップ８１２において、そのコードワードに関連する実際のパリティページの数を特定することができる。例えば、ＮＶＭインターフェイスは、コードワードのパリティページに到達すると、ページがパリティページでないことを示す（従って、このコードワードの全てのパリティページが走査されたことを示す）パリティページマーカーを有するページに到達するまでパリティページを「右向きに走査」することにより、パリティページの数を特定することができる。ステップ８１２で特定された実際のパリティページの数は、ステップ８０４で推定したパリティページの数「ｍ」と等しい場合も、又は等しくない場合もある。ステップ８１２において、ＮＶＭインターフェイスは、コードワード内の訂正不能ページの数を特定することもできる。例えば、ＮＶＭインターフェイスは、コードワードを検索する時に、ｔ個よりも多くのエラーを含むページの数の集計を保持しておくことができる。
【００９１】
ステップ８１４において、「ｍ」個の方程式から（もしあれば）「誤った」方程式を廃棄することができる。誤った方程式は、処理８００で計算した、存在すると推定はしたものの、方程式を作成するための好適な外部ＥＣＣデータが存在しないあらゆる方程式を含むことができる。一例として、ステップ８０４において、ＮＶＭインターフェイスが、２つのパリティページが存在すると推定し、従ってコードワードが検索された時に方程式（３）及び方程式（４）をオンザフライで計算したと考える。しかしながら、ステップ８１２において、ＮＶＭインターフェイスが、コードワードに関連する実際のパリティページが１つしか存在しないと判断したと考える。この結果、ステップ８１４において、方程式（４）を誤った方程式として廃棄することができる。
【００９２】
ステップ８１６において、処理８００は、コードワードが修復可能であるかどうかを判断することができる。例えば、ステップ８１４で廃棄されなかった方程式の数（又はステップ８１２において特定された実際のパリティページの数など）が訂正不能ページの数以上である場合、コードワードを修復することができる。コードワードが修復可能であることに応答して、ステップ８１８においてこのコードワードを修復し、処理はステップ８２０において終了することができる。例えば、ステップ８１４で廃棄されなかった１又はそれ以上の「ｍ」個の方程式を使用して、訂正不能ページの正しい値を解くことができる。一方、コードワードが修復可能でない場合、ステップ８８２において、このコードワードを、例えば不正確なデータを有するものとして廃棄することができる。
【００９３】
上述した処理は例示にすぎないと理解されたい。本発明の範囲から逸脱することなく、ステップのいずれかを除去し、修正し、又は組み合わせることができ、あらゆる追加のステップを加えることができる。
【００９４】
説明した本発明の実施形態は、限定ではなく例示目的で示したものである。
【図１】
2013522792.tif 000002
【図２】
2013522792.tif 000003
【図３】
2013522792.tif 000004
【図４】
2013522792.tif 000005
【図５】
2013522792.tif 000006
【図６】
2013522792.tif 000007
【図７Ａ】
2013522792.tif 000008
【図７Ｂ】
2013522792.tif 000009
【図８】
2013522792.tif 000010
【国際調査報告】
2013522792.tif 000011
2013522792.tif 000012
2013522792.tif 000013
2013522792.tif 000014
2013522792.tif 000015