(57)【要約】      （修正有）【課題】データの書き込みおよび読み出しを後入れ先出し方式で行う不揮発性メモリの制御に有用なメモリシステムを提供する。【解決手段】メモリシステム１は、不揮発性メモリ３とコントローラ２とを具備する。不揮発性メモリは、複数の磁気記憶細線をそれぞれ含む複数の第１ブロックを備え、複数の磁気記憶細線に含まれる複数のレイヤは、論理アドレスに関連付けられているデータが格納された第１属性のレイヤ、および論理アドレスに関連付けられていないデータが格納された第２属性のレイヤ、の少なくともいずれかを含む。第２属性のレイヤの第１の方向に隣接する位置には、第１レイヤが存在する。コントローラは、複数の第１ブロックの各々における複数のレイヤに対する第２属性のレイヤの割合に基づいて、複数の第１ブロックからコンパクション処理のソースブロックを選択するように構成される。【選択図】図１
2020149223.tif 000002
【特許請求の範囲】
【請求項１】
複数の磁気記憶細線をそれぞれ含む複数の第１ブロックを備え、前記複数の磁気記憶細線に含まれる複数のレイヤにそれぞれ格納されているデータを最上位のレイヤから最下位のレイヤに向かう第１の方向または前記第１の方向とは逆の第２の方向にレイヤ単位でシフトさせることによって、各ブロックに対するデータの書き込みおよび読み出しを後入れ先出し方式で行うように構成された不揮発性メモリと、
前記不揮発性メモリを制御するコントローラとを具備し、
前記複数のレイヤは、論理アドレスに関連付けられているデータが格納された第１属性のレイヤ、および論理アドレスに関連付けられていないデータが格納された第２属性のレイヤ、の少なくともいずれかを含み、
前記第２属性のレイヤの前記第１の方向に隣接する位置には、前記第１属性のレイヤが存在し、
前記コントローラは、前記複数の第１ブロックの各々における前記複数のレイヤに対する前記第２属性のレイヤの割合に基づいて、前記複数の第１ブロックからコンパクション処理のソースブロックを選択するように構成されたメモリシステム。
【請求項２】
前記コントローラは、前記割合が高いブロックほど優先して前記ソースブロックとして選択する請求項１記載のメモリシステム。
【請求項３】
前記コントローラは、前記複数の第１ブロックから前記割合が高い複数の第２ブロックを選択し、前記複数の第２ブロックから、前記最下位のレイヤにより近い前記第１属性のレイヤを含むブロックを、前記ソースブロックとして選択する請求項１記載のメモリシステム。
【請求項４】
前記複数のレイヤは、前記第１属性のレイヤおよび前記第２属性のレイヤとは異なる第３属性のレイヤをさらに含み、
前記第３属性のレイヤの前記第１の方向には、前記第１属性のレイヤおよび前記第２属性のレイヤは位置せず、
前記コントローラは、前記複数の第１ブロックから、前記第３属性のレイヤを含まず、且つ前記複数のレイヤに対する前記第２属性のレイヤの割合が、前記不揮発性メモリの物理容量に対する余裕容量の割合を示す余裕率以上であるブロック、または前記複数のレイヤに対する前記第２属性のレイヤおよび前記第３属性のレイヤの割合が前記余裕率以上であるブロックを、前記ソースブロックとして選択するように構成された請求項１記載のメモリシステム。
【請求項５】
前記コントローラは、さらに、前記複数の第１ブロックから、データが書き込まれてから経過した時間に基づいて前記ソースブロックを選択する請求項１記載のメモリシステム。
【請求項６】
前記複数のレイヤは、前記第１属性のレイヤおよび前記第２属性のレイヤとは異なる第３属性のレイヤをさらに含み、
前記第３属性のレイヤの前記第１の方向には、前記第１属性のレイヤおよび前記第２属性のレイヤは位置せず、
前記コントローラは、前記複数の第１ブロックから、前記複数のレイヤがすべて前記第３属性のレイヤであるブロックを前記コンパクション処理のデスティネーションブロックとして選択する請求項１乃至請求項５のいずれか一項に記載のメモリシステム。
【請求項７】
前記複数のレイヤは、前記第１の方向に前記第１属性のレイヤが存在しない第３属性のレイヤをさらに含み、
前記コントローラは、前記ソースブロックに含まれる前記第１属性のレイヤの数以上の前記第３属性のレイヤを含むブロックを、前記コンパクション処理のデスティネーションブロックとして選択する請求項１乃至請求項５のいずれか一項に記載のメモリシステム。
【請求項８】
前記コントローラは、前記コンパクション処理において、前記ソースブロック内の１つ以上の前記第１属性のレイヤにそれぞれ格納されているデータを、前記デスティネーションブロックに書き込むように構成された請求項６または請求項７記載のメモリシステム。
【請求項９】
前記コントローラによって制御されるランダムアクセスメモリをさらに具備し、
前記コントローラはさらに、前記ソースブロック内の１つ以上の前記第１属性のレイヤにそれぞれ格納されているデータを前記ランダムアクセスメモリに格納し、前記ランダムアクセスメモリに格納されたデータを前記ソースブロックに書き込む請求項１乃至請求項５のいずれか一項に記載のメモリシステム。
【請求項１０】
前記コントローラは、さらに、前記複数の第１ブロックから最上位のレイヤから連続する１つ以上のレイヤがそれぞれ前記第２属性のレイヤである第３ブロックを選択し、前記第３ブロックに対して前記１つ以上のレイヤからデータを読み出すためのリード動作を行うように構成された請求項１記載のメモリシステム。
【請求項１１】
前記複数の第１ブロックの各々は、隣接するレイヤの集合をそれぞれ含むように論理的に区分された複数のフレームを含み、
前記コントローラは、さらに、
前記複数の第１ブロックの内の第４ブロックに含まれる複数のフレームの内、第１データ部および第１誤り訂正符号を含む第１フレームと、第２データ部および第２誤り訂正符号を含む第２フレームとを読み出し、
前記第１誤り訂正符号を用いて前記第１データ部に対して誤り訂正処理を行い、
前記誤り訂正処理において訂正された誤りが、前記複数の磁気記憶細線の内の第１磁気記憶細線で発生していた場合、前記第１磁気記憶細線内の第１レイヤに格納されたデータを、前記第１磁気記憶細線内の第２レイヤに格納されたデータで置き換えることによって、前記第２データ部を訂正するように構成された請求項１乃至請求項５のいずれか一項に記載のメモリシステム。
【請求項１２】
前記コントローラによって制御されるランダムアクセスメモリをさらに具備し、
前記複数の第１ブロックの各々は、隣接するレイヤの集合をそれぞれ含むように論理的に区分された複数のフレームを含み、
前記コントローラは、さらに、
前記複数の第１ブロックの内の第４ブロックに含まれる複数のフレームを読み出し、
前記読み出された複数のフレームを前記ランダムアクセスメモリに格納し、
前記読み出された複数のフレームの内の第１フレームに含まれる第１誤り訂正符号を用いて、前記第１フレームに含まれる第１データ部に対して誤り訂正処理を行い、
前記誤り訂正処理において訂正された誤りが、前記複数の磁気記憶細線の内の第１磁気記憶細線で発生していた場合、前記第１磁気記憶細線内の第１レイヤに格納されたデータを、前記第１磁気記憶細線内の第２レイヤに格納されたデータで置き換えることによって、前記読み出された複数のフレームの内の第２フレームに含まれる第２データ部を訂正するように構成された請求項１乃至請求項５のいずれか一項に記載のメモリシステム。
【請求項１３】
前記第４ブロックは、前記ソースブロックである請求項１１または請求項１２記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性メモリを制御する技術に関する。
【背景技術】
【０００２】
近年、不揮発性メモリを備えるメモリシステムが広く普及している。このようなメモリシステムの１つとして、ＮＡＮＤ型フラッシュメモリを備えるソリッドステートドライブ（ＳＳＤ）が知られている。
【０００３】
最近では、次世代の不揮発性メモリとして、データの書き込みおよび読み出しを後入れ先出し方式で行う種類の不揮発性メモリが開発され始めている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１６−１４３４３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、データの書き込みおよび読み出しを後入れ先出し方式で行う不揮発性メモリの制御に有用なメモリシステムを提供することである。
【課題を解決するための手段】
【０００６】
実施形態によれば、メモリシステムは、不揮発性メモリとコントローラとを具備する。前記不揮発性メモリは、複数の磁気記憶細線をそれぞれ含む複数の第１ブロックを備え、前記複数の磁気記憶細線に含まれる複数のレイヤにそれぞれ格納されているデータを最上位のレイヤから最下位のレイヤに向かう第１の方向または前記第１の方向とは逆の第２の方向にレイヤ単位でシフトさせることによって、各ブロックに対するデータの書き込みおよび読み出しを後入れ先出し方式で行うように構成される。前記コントローラは、前記不揮発性メモリを制御する。前記複数のレイヤは、論理アドレスに関連付けられているデータが格納された第１属性のレイヤ、および論理アドレスに関連付けられていないデータが格納された第２属性のレイヤ、の少なくともいずれかを含む。前記第２属性のレイヤの前記第１の方向に隣接する位置には、前記第１レイヤが存在する。前記コントローラは、前記複数の第１ブロックの各々における前記複数のレイヤに対する前記第２属性のレイヤの割合に基づいて、前記複数の第１ブロックからコンパクション処理のソースブロックを選択するように構成される。
【図面の簡単な説明】
【０００７】
【図１】第１実施形態に係るメモリシステムの構成例を示すブロック図。
【図２】第１実施形態のメモリシステムに含まれる不揮発性メモリ内のセルアレイの構成例を示す図。
【図３】セルアレイ内の各ブロックに含まれる複数の磁気記憶細線（Ｍａｇｎｅｔｉｃ  Ｍｅｍｏｒｙ  Ｌｉｎｅ：ＭＭＬ）の内の１つのＭＭＬに対応する例示的な回路構成を示す図。
【図４】ＭＭＬにおける記憶状態の移動（磁壁の移動）を示す図。
【図５】ブロックに書き込まれるデータ部それぞれに対する誤り訂正符号の符号量配分の例を示す図。
【図６】データ部が書き込まれるべきブロック内のページの位置に応じて誤り訂正符号の符号量配分を変更する例を示す図。
【図７】同じレイヤ内のＭＭＬの境界で誤り訂正符号の符号量配分を変更する例を示す図。
【図８】ブロックサイズに対応する複数のデータ部をそれぞれエンコードし、エンコードされたデータ部それぞれをブロックに書き込む処理の手順を示すフローチャート。
【図９】ブロックサイズに対応する複数のデータ部をそれぞれエンコードし、エンコードされたデータ部それぞれをブロックに書き込む処理の別の手順を示すフローチャート。
【図１０】ルックアップテーブル（ＬＵＴ）内のマッピング情報の例を示す図。
【図１１】セルアレイの外観の例を示す斜視図。
【図１２】ＭＭＬへの書き込み動作の第１の例を示す図。
【図１３】ＭＭＬへの書き込み動作の第２の例を示す図。
【図１４】ＭＭＬからの読み出し動作の例を示す図。
【図１５】比較例に係るメモリシステムにおけるコンパクションを説明するための図。
【図１６】比較例に係るメモリシステムにおけるブロックの枯渇を説明するための図。
【図１７】比較例に係るメモリシステムによって実行されるコンパクション処理の手順の例を示すフローチャート。
【図１８】ＭＭＬに関するパラメータを説明するための図。
【図１９】ＭＭＬの利用状態を説明するための図。
【図２０】第１実施形態のメモリシステムにおいて、有効レイヤ率に基づくコンパクションが行われたと仮定した場合の例を示す図。
【図２１】ＮＡＮＤ・ＮＯＲ型フラッシュメモリと図２の不揮発性メモリとのコンパクションの差異を示す図。
【図２２】１ページのデータが書き込まれた場合の、ＭＭＬの書き込み余地を管理するためのＶｏｉｄＣｎｔと無効レイヤ率を管理するためのＩｎＶａｌｉｄＣｎｔとの例を示す図。
【図２３】書き込み処理の手順の例を示すフローチャート。
【図２４】ブロックに書き込まれている１ページのデータが削除された場合に、当該ページがＩｎｖａｌｉｄ領域となる例を示す図。
【図２５】ブロックに書き込まれている１ページのデータが削除された場合に、当該ページがＶｏｉｄ領域となる例を示す図。
【図２６】１ページのデータが削除された場合のＶｏｉｄＣｎｔとＩｎｖａｌｉｄＣｎｔとの例を示す図。
【図２７】１ページのデータが削除された場合のＶｏｉｄＣｎｔとＩｎｖａｌｉｄＣｎｔとの別の例を示す図。
【図２８】カウント更新処理の手順の例を示すフローチャート。
【図２９】コンパクション対象のソースブロックとして選択されるブロックの例を説明するための図。
【図３０】図２の不揮発性メモリが特定の余裕率を持つ場合に、各ブロックが余裕率以上の空き容量を有することを示す図。
【図３１】リード動作のみによるセルフコンパクションの例を示す図。
【図３２】リード動作のみによるセルフコンパクションが行われた場合のＶｏｉｄＣｎｔとＩｎｖａｌｉｄＣｎｔとの例を示す図。
【図３３】リード動作のみによるセルフコンパクションが行われた場合のＶｏｉｄＣｎｔとＩｎｖａｌｉｄＣｎｔとの別の例を示す図。
【図３４】リード動作のみによるセルフコンパクション処理の手順の例を示すフローチャート。
【図３５】ソースブロックとデスティネーションブロックを同一にしたセルフコンパクションの例を示す図。
【図３６】第２実施形態に係るメモリシステムの構成例を示すブロック図。
【図３７】第２実施形態に係るメモリシステムにおいて、経年変化によるエラーがそれぞれ発生したソースブロックとデスティネーションブロックを用いてコンパクションが行われる例を示す図。
【図３８】デスティネーションブロックとしてフリーブロックが用いられる場合のコンパクションの効果の例を示す図。
【図３９】デスティネーションブロックとしてフリーブロックが用いられる場合のコンパクションの効果の別の例を示す図。
【図４０】ＭＭＬ内で意図されたシフトが発生しない例を示す図。
【図４１】ブロックに書き込まれた、データ部および誤り訂正符号（パリティ）を含むフレームで、シフトエラーおよびランダムエラーが発生した例を示す図。
【図４２】より上層にあるフレームで発生したエラーの影響を受けて、下層のフレームのエラー訂正が失敗する例を示す図。
【図４３】第１フレームにおいてシフト量が学習される例を示す図。
【図４４】第１フレームを、学習されたシフト量に適応させる例を示す図。
【図４５】第２フレームにおいてシフト量が学習される例を示す図。
【図４６】第２フレームを、学習されたシフト量に適応させる例を示す図。
【図４７】第３フレームにおいてシフト量が学習される例を示す図。
【図４８】第３フレームを、学習されたシフト量に適応させる例を示す図。
【図４９】第４フレームにおいてシフト量が学習される例を示す図。
【図５０】第４フレームおよび第５フレームを、学習されたシフト量に適応させることにより、第４フレームおよび第５フレームのエラー訂正が成功する例を示す図。
【図５１】シフトエラーの開始位置に応じた学習および適応の例を示す図。
【図５２】シフトエラー学習・適応処理の手順の例を示すフローチャート。
【図５３】シフトエラー学習・適応処理の手順の別の例を示すフローチャート。
【図５４】シフトエラーテーブルの一構成例を示す図。
【図５５】ランダムエラーの例を示す図。
【図５６】シフトエラーの例を示す図。
【図５７】期待値とシフトエラーが発生した場合の読み出し結果との第１の例を示す図。
【図５８】図５７の読み出し結果と、エラー訂正結果との例を示す図。
【図５９】図５７の期待値と読み出し結果との関係を示す編集グラフの例を示す図。
【図６０】図５９の編集グラフに基づいてシフト量が決定される例を示す図。
【図６１】図６０のシフト量でシフトされた読み出し結果と、エラー訂正結果との例を示す図。
【図６２】期待値とシフトエラーが発生した場合の読み出し結果との第２の例を示す図。
【図６３】図６２の読み出し結果と、エラー訂正結果との例を示す図。
【図６４】図６２の期待値と読み出し結果との関係を示す編集グラフの例を示す図。
【図６５】図６４の編集グラフに基づいてシフト量が算出される例を示す図。
【図６６】図６５のシフト量でシフトされた読み出し結果と、エラー訂正結果との例を示す図。
【図６７】編集グラフを用いて判別されるエラーの例を示す図。
【図６８】期待値と、シフトエラーが発生した場合の読み出し結果と、さらにランダムエラーが発生した場合の読み出し結果との例を示す図。
【図６９】編集グラフを用いて、シフトエラーの発生と、シフトエラーおよびランダムエラーの発生とが判別される例を示す図。
【発明を実施するための形態】
【０００８】
以下、図面を参照して、実施形態を説明する。  
（第１実施形態）
図１は第１実施形態に係るメモリシステム１の構成例を示す。メモリシステム１はコントローラ（メモリコントローラ）２と不揮発性メモリ３とを含む。メモリシステム１はホスト４と接続可能であり、図１ではメモリシステム１がホスト４に接続されている状態を示している。ホスト４は、パーソナルコンピュータ、サーバ、携帯端末、等の電子機器である。
【０００９】
不揮発性メモリ３はデータを不揮発に記憶するメモリである。不揮発性メモリ３は、ブロックと呼ばれるある容量単位において、当該ブロックに含まれるページ単位でデータの書き込みおよび読み出しを後入れ先出し方式（先入れ後出し方式とも称される）で行うように構成されている。不揮発性メモリ３は、複数のブロックを含む。各ブロックは、シフトレジスタの複数のステージとして機能する複数のレイヤを含む。換言すれば、１つのレイヤはシフトレジスタ内のステージの１つとして機能する。不揮発性メモリ３は、個々のレイヤに格納されているデータを最初のステージに対応するレイヤから最後のステージに対応するレイヤに向かう第１の方向または第１の方向とは逆の第２の方向にレイヤ単位でシフトさせることによって、あるブロックにおいてページ単位でデータの書き込みおよび読み出しを後入れ先出し方式で行う。
【００１０】
データの書き込みおよび読み出しを後入れ先出し方式で行うタイプの不揮発性メモリ３の一例としては、磁壁メモリが挙げられる。磁壁メモリとは、情報（“１”または“０”）を格納するための複数の磁区を含む磁気シフトレジスタに電流を流すことによって各磁区をシフト（移動）させながら、データの書き込みおよび読み出しを行うタイプの磁気メモリである。
【００１１】
メモリシステム１は、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）として実現されてもよいし、メモリコントローラ２と不揮発性メモリ３が１つのパッケージとして構成されるメモリカードとして実現されてもよい。
【００１２】
メモリコントローラ２は、ホスト４から受信されるライト要求（ライトコマンド）に従って不揮発性メモリ３へのデータの書き込みを制御する。また、メモリコントローラ２は、ホスト４から受信されるリード要求（リードコマンド）に従って不揮発性メモリ３からのデータの読み出しを制御する。
【００１３】
メモリコントローラ２は、ＳｏＣのような回路によって実現されていてもよい。メモリコントローラ２は、ホストインタフェース２１、メモリインタフェース２２、制御部２３、符号化／復号部（Ｅｎｃｏｄｅｒ／Ｄｅｃｏｄｅｒ）２４、データバッファ２５、スタティックランダムアクセスメモリ（ＳＲＡＭ）２８等を備える。ホストインタフェース２１、メモリインタフェース２２、制御部２３、符号化／復号部（Ｅｎｃｏｄｅｒ／Ｄｅｃｏｄｅｒ）２４、データバッファ２５、およびＳＲＡＭ２８は、内部バス２０に接続されている。
【００１４】
ホストインタフェース２１は、ホストとデバイスとの間のインタフェース規格に従った処理を実施し、ホスト４から受信した要求、ユーザデータなどを内部バス２０に出力する。また、ホストインタフェース２１は、不揮発性メモリ３から読み出されたユーザデータ、制御部２３から受信した応答などをホスト４へ送信する。なお、本実施形態では、ホスト４からのライト要求により不揮発性メモリ３へ書き込むデータをユーザデータと呼ぶ。
【００１５】
メモリインタフェース２２は、制御部２３からの指示に基づいて、不揮発性メモリ３へデータを書き込む書き込み動作を行う。また、メモリインタフェース２２は、制御部２３からの指示に基づいて、不揮発性メモリ３からデータを読み出す読み出し動作を行う。
【００１６】
制御部２３は、メモリシステム１の各構成要素を統括的に制御する。制御部２３は、ＣＰＵ（プロセッサ）によって実現されてもよい。
【００１７】
制御部２３は、ホスト４からホストインタフェース２１経由で要求を受けた場合に、その要求に従った制御を行う。例えば、制御部２３は、ホスト４から受信したライト要求に従って、不揮発性メモリ３へのユーザデータおよびパリティの書き込みをメモリインタフェース２２へ指示する。また、制御部２３は、ホスト４から受信したリード要求に従って、不揮発性メモリ３からのユーザデータおよびパリティの読み出しをメモリインタフェース２２へ指示する。ここで、パリティとは、ユーザデータを符号化することによって得られる誤り訂正符号（ＥＣＣ）を意味する。ライト要求は、論理アドレスと、書き込むべきライトデータの長さ、等を指定する。ライト要求によって指定される論理アドレスはライトデータが書き込まれるべき論理アドレスを示す。リード要求は、論理アドレスと、読み出されるべきデータの長さ、等を指定する。リード要求によって指定される論理アドレスは、読み出されるべきデータに対応する論理アドレスを示す。
【００１８】
また、制御部２３は、ホスト４からライト要求を受信した場合、データバッファ２５に蓄積されるユーザデータが書き込まれるべき不揮発性メモリ３上の記憶領域（メモリ領域）を決定する。すなわち、制御部２３は、ユーザデータの書き込み先を管理する。制御部２３は、ホスト４から受信したライト要求により指定された論理アドレスとこの論理アドレスに対応するユーザデータが格納された不揮発性メモリ３上の記憶領域を示す物理アドレスとの間のマッピングを、アドレス変換テーブルとして機能するルックアップテーブル（ＬＵＴ）２３１を使用して管理する。ＬＵＴ２３１はメモリシステム１内のＲＡＭ（ダイナミックＲＡＭ（ＤＲＡＭ）またはＳＲＡＭ２８）に格納されていてもよいし、不揮発性メモリ３に不揮発に格納されていてもよい。後者においては、メモリシステム１がパワーオンされた時にＬＵＴ２３１が不揮発性メモリ３からメモリシステム１内のＲＡＭにロードされてもよい。
【００１９】
また、制御部２３は、ホスト４からリード要求を受信した場合、ＬＵＴ２３１を用いて、リード要求により指定された論理アドレスを物理アドレスに変換し、該物理アドレスからのデータの読み出しをメモリインタフェース２２へ指示する。
【００２０】
制御部２３はさらに、物理アドレスを論理アドレスに変換するための逆引きＬＵＴ２３２、不揮発性メモリ３の書き込み余地を管理するためのＶｏｉｄＣｎｔ２３３、不揮発性メモリ３の無効レイヤ率を管理するためのＩｎＶａｌｉｄＣｎｔ２３４等の、不揮発性メモリ３を制御するための様々なデータを管理し得る。これら逆引きＬＵＴ２３２、ＶｏｉｄＣｎｔ２３３、およびＩｎＶａｌｉｄＣｎｔ２３４は、例えばブロック単位で管理される。また、このようなデータはＳＲＡＭ２８等のＲＡＭに格納され得る。
【００２１】
不揮発性メモリ３に含まれるブロックの各々は、上述したように複数のレイヤを含む。これらレイヤは、複数のページに論理的に区分されている。各ページは、隣接する幾つかのレイヤの集合を含む。１つのページのサイズは、ユーザデータとＥＣＣとを含むＥＣＣフレーム（以下、フレームとも称する）のサイズによって予め規定される。このため、不揮発性メモリ３においては、一般に、ページと呼ばれるデータ単位（ＥＣＣフレーム単位）で、書き込みおよび読み出しが行われる。
【００２２】
データバッファ２５は、ホスト４から受信されたユーザデータを一時的に格納する。また、データバッファ２５は、不揮発性メモリ３から読み出されたユーザデータを一時的に格納する。また、データバッファ２５は、ユーザデータが符号化されて生成された符号語（ユーザデータ＋ＥＣＣ）を一時格納する。データバッファ２５は、例えば、上述のＲＡＭ（ＳＲＡＭま２８たはＤＲＡＭ）で構成される。
【００２３】
ホスト４から送信されるユーザデータは内部バス２０に転送されてデータバッファ２５に格納される。符号化／復号部２４は、不揮発性メモリ３に書き込むべきデータを符号化して符号語を生成する。符号化としてはどのような符号化を用いてもよいが、例えばＲＳ（Ｒｅｅｄ  Ｓｏｌｏｍｏｎ）符号化、ＢＣＨ（Ｂｏｓｅ  Ｃｈａｕｄｈｕｒｉ  Ｈｏｃｑｕｅｎｇｈｅｍ）符号化、ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号化を用いることができる。符号化／復号部２４は、符号化部（Ｅｎｃｏｄｉｎｇ  Ｕｎｉｔ）２６と復号部（Ｄｅｃｏｄｉｎｇ  Ｕｎｉｔ）２７を備える。本実施形態の符号化および復号の詳細については後述する。
【００２４】
説明を簡単にするために、本実施形態では、不揮発性メモリ３が１つの不揮発性メモリチップを含む場合を想定するが、本実施形態は、不揮発性メモリ３が複数の不揮発性メモリチップを含む構成にも適用可能である。
【００２５】
図２は、不揮発性メモリ３に含まれるセルアレイの構成例を示す。以下では、理解しやすくするために特定の数値を使用してセルアレイの構成例を説明するが、これら数値はあくまで例示であり、本実施形態はこれら特定の数値に限定されず、任意の数値が本実施形態のセルアレイの構成に適用可能である。
【００２６】
セルアレイは、複数のブロックを含む。複数のブロックの各々は、後入り先出し方式でデータの書き込みおよび読み出しを行う単位である。
【００２７】
ここでは、各ブロックが、レイヤＬ０〜Ｌ２８７の計２８８個のレイヤを含む場合を想定する。これら２８８個のレイヤが上述のシフトレジスタの複数のステージとしてそれぞれ機能する。レイヤＬ２８７はシフトレジスタの最初のステージに対応し、レイヤＬ０はシフトレジスタの最後のステージに対応する。
【００２８】
各ブロックのレイヤＬ０〜Ｌ２８７は、各ブロックに含まれる複数の磁気記憶細線（ＭＭＬ）によって実現することができる。複数のＭＭＬの各々は、後入り先出し方式で１ビット幅のデータを書き込みおよび読み出しを行う単位である。ＭＭＬは、磁気記憶細線、磁性体柱、磁性線、磁性細線、ストリング等と称される磁性体である。
【００２９】
ここでは、各ブロックが１Ｋ＋α本のＭＭＬを含む場合を想定する。磁壁メモリにおいては、このＭＭＬは磁気シフトレジスタであり、例えば、一方向に延びた磁性体によって実現される。磁壁メモリの各ＭＭＬは磁性細線と称されることもある。各ＭＭＬは最初のステージから最後のステージまでの複数のステージにそれぞれ対応する複数の磁区を含むことができる。各磁区の磁化方向が、“１”または“０”を示す情報として利用される。
【００３０】
各ＭＭＬは、先に書き込まれたデータは次にデータが書き込まれると奥側にその記憶位置が移動し、奥のデータは、後にプログラムしたデータを読み出してからでないと読み出すことができない、という後入れ先出し方式でアクセスされる。
【００３１】
本実施形態では、１ＭＭＬは２５６＋βビットを格納可能であると想定する。これは、磁壁メモリの１ＭＭＬが２５６＋β個の磁区を含む構成に対応する。
【００３２】
この場合、１ブロックのサイズは、（１Ｋ＋α）×（２５６＋β）ｂｉｔ＝３２ＫＢ＋α’となる。ここで、α、β、α’（α’＝α×（２５６＋β）＋β×（１Ｋ＋α）−α×β）は、パリティを格納するための領域として使われる他、データに付属して保存したい情報を格納するための領域として使われることが考えられる。以下では簡単のため、α、β、α’はパリティとして使われるものとする。パリティはデータに付加される誤り訂正符号（ＥＣＣ）である。なお、上記のα、β、α’の数値は一例として示したものであり、本実施形態では、他の様々な数値を適用することができる。
【００３３】
以下では、α＝０、β＝３２のケースを例示して説明する。  
図２において、縦方向に連なる複数の楕円の集合が１つのＭＭＬを示している。１Ｋ＋α本のＭＭＬの組み合わせが１つのブロックを構成する。ブロックは２重四角で表されている。ブロックの中に含まれる１Ｋ＋α本のＭＭＬは、２８８（２５６＋３２）個のレイヤＬ０〜Ｌ２８７を構成する。レイヤＬ０〜Ｌ２８７の各々は、角丸四角で表されている。
【００３４】
各ブロックに含まれる１Ｋ＋α本のＭＭＬそれぞれの一端は、１Ｋ＋α個の入出力部にそれぞれ接続されている。図２においては、これら１Ｋ＋α個の入出力部の集合は、入出力部群３１として表されている。このブロックに対するデータの書き込みおよび読み出しは入出力部群３１を介して行われる。
【００３５】
入出力部群３１に最も近いレイヤＬ２８７はシフトレジスタの最初のステージとして使用され、入出力部群３１から最も離れているレイヤＬ０はシフトレジスタの最後のステージとして使用される。
【００３６】
書き込み動作においては、個々のレイヤに格納されているデータは最初のステージに対応するレイヤＬ２９７から最後のステージに対応するレイヤＬ０に向かう第１の方向（図２において上から下に向かう方向）にレイヤ単位でシフトされる。
【００３７】
読み出し動作においては、個々のレイヤに格納されているデータは第１の方向とは逆の第２の方向（図２において下から上に向かう方向）にレイヤ単位でシフトされる。
【００３８】
レイヤＬ０〜Ｌ２８７は、隣接する３６（＝２８８／８）個のレイヤを各々が含む８個のレイヤグループに分けられる。これらレイヤグループはページと称される。換言すれば、レイヤＬ０〜Ｌ２８７は８個のページｐ０〜ｐ７に論理的に区分されている。１つのページは、隣接する３６（＝２８８／８）個のレイヤを含む。ページｐ０〜ｐ７の各々は四角で表されている。１つのブロックは８個のページｐ０〜ｐ７から構成される。
【００３９】
ページｐ０〜ｐ７それぞれの容量は、予め決められたサイズを有するデータ部を格納できるように予め規定されている。例えば、１つのページは、所定サイズを有するデータ部とこのデータ部に対応する誤り訂正符号（ＥＣＣ）とを含むＥＣＣフレームを格納可能な容量を有するように規定されてもよい。１つのＥＣＣフレームに含まれるデータ部のサイズは、例えば、４ＫＢであってもよい。この場合、１つのＥＣＣフレームは、４ＫＢのユーザデータと、ＥＣＣとを含む。１つのブロックは８個のページｐ０〜ｐ７にそれぞれ対応する８個のデータ部（８個のＥＣＣフレーム）を格納することができる。
【００４０】
以下では、入出力部群３１に最も近いページｐ７は「最初のページ」としても参照され、また入出力部群３１から最も遠いページｐ０は「最後のページ」としても参照される。
【００４１】
入出力部群３１はシフト制御部３２および読み書き制御部３３にそれぞれ接続される。シフト制御部３２は、ブロック内の各レイヤのデータを、レイヤＬ２９７からレイヤＬ０に向かう方向に、またはレイヤＬ０からレイヤＬ２９７に向かう方向にレイヤ単位でシフトさせる。
【００４２】
磁壁メモリにおいては、シフト制御部３２は、ブロック内の各ＭＭＬに電流パルスを供給することによって各ＭＭＬ内の磁壁それぞれをシフト（移動）させる。各ＭＭＬにおいては、磁壁の移動によって、各磁区がレイヤ単位（つまりビット単位）でシフト（移動）される。
【００４３】
読み書き制御部３３は、入出力部群３１を介してこのブロックに対するデータの書き込みおよび読み出しを制御する。
【００４４】
図３は、各ブロックに含まれる複数のＭＭＬのうちの１つのＭＭＬ１０に対応する例示的な回路構成を示している。ここでは、不揮発性メモリ３が磁壁メモリである場合が想定されている。
【００４５】
ＭＭＬ１０は磁気記憶細線、磁性体柱、磁性線、磁性細線、ストリング等と称される磁性体であり、磁気シフトレジスタとして機能する。ＭＭＬ１０は一方向に延びており、その長手方向に沿って配置される複数の磁区１５を有する。互いに磁化方向が異なる隣接する磁区１５間には磁壁１６が存在する。
【００４６】
ＭＭＬ１０は、一端部１０ａｅと、他端部１０ａｆとを有する。一端部１０ａｅは入出力部３１−１に接続されるとともに、シフト制御部３２の第１トランジスタＴｒ１にも接続される。他端部１０ａｆは磁性線ドライバＭＭＬ−Ｄ−１に接続される。
【００４７】
入出力部３１−１はＭＭＬ１０用の入出力部である。ＭＭＬ１０に対するデータの書き込みおよび読み出しは入出力部３１−１を介して実行される。書き込み動作においては、入出力部３１−１は、読み書き制御部３３からの信号に基づき、入出力部３１−１に接続されたＭＭＬ１０内の一部分に、特定の磁化方向を有する磁化を形成する。読み出し書き込み動作においては、入出力部３１−１は、入出力部３１−１に接続されたＭＭＬ１０内の一部分の磁化方向を検出することによってＭＭＬ１０からデータを読み出す。入出力部３１−１は、例えば、磁性層１１ａと中間層１２ａとを含む。中間層１２ａは磁性層１１ａとＭＭＬ１０との間に配置されている。磁性層１１ａは読み書き制御部３３のトランジスタＴｒ２に接続されている。
【００４８】
読み書き制御部３３は、トランジスタＴｒ２に加え、入出力部３１−１を介してＭＭＬ１０を駆動する読み書きドライバＲＷ−Ｄ−１と、ＭＭＬ１０を選択するための読み書きセレクタＲＷＣＳ−１とを含む。
【００４９】
シフト制御部３２は、ＭＭＬ１０内の各磁区の磁化をビット単位でシフトさせるために、磁性線ドライバＭＭＬ−Ｄ−１と共同してＭＭＬ１０に電流を流す。シフト制御部３２は、トランジスタＴｒ１に加え、ＭＭＬ１０に電流を流すためのシフトドライバ（ｄｏｍａｉｎ  ｗａｌｌ  ｓｈｉｆｔ  ｄｒｉｖｅｒ）ＤＷＳ−Ｄ−１と、ＭＭＬ１０を選択するためのシフトセレクタ（ｄｏｍａｉｎ  ｗａｌｌ  ｓｈｉｆｔ  ｓｅｌｅｃｔｏｒ）ＤＷＳ−ＣＳ−１とを含む。
【００５０】
ＭＭＬ１０は、第１方向Ｄ１に延在している。ＭＭＬ１０に含まれる各磁区１５の磁化は、１つの状態（第１状態）において、第１磁化方向１５ｍａ（ここでは磁化方向Ｎ）である。第１磁化方向１５ｍａは、第１方向Ｄ１と交差する。各磁区１５の磁化方向は、別の状態（第２状態）において、第２磁化方向１５ｍｂ（ここでは磁化方向Ｓ）である。第２磁化方向１５ｍｂは、第１方向Ｄ１と交差し且つ第１磁化方向１５ｍａとは逆である。
【００５１】
ＭＭＬ１０の複数の磁区１５の磁化は、読み書き制御部３３から入出力部３１−１に供給される信号により制御される。これにより、上記の第１磁化方向１５ｍａおよび第２磁化方向１５ｍｂが形成される。ＭＭＬ１０中の複数の磁区１５の磁化の方向（第１磁化方向１５ｍａおよび第２磁化方向１５ｍｂ）が、記憶する情報（１および０）に対応する。
【００５２】
ＭＭＬ１０に流れる電流により、ＭＭＬ１０内の磁壁１６それぞれがシフト（移動）し、この結果、複数の磁区１５の磁化がそれぞれシフト（移動）する。例えば、ＭＭＬ１０において一端部１０ａｅから他端部１０ａｆに向かって電流が流れたときに、複数の磁区１５の磁化が、一端部１０ａｅから他端部１０ａｆに向かって移動する。ＭＭＬ１０において他端部１０ａｆから一端部１０ａｅに向かって電流が流れたときに、複数の磁区１５の磁化が、他端部１０ａｆから一端部１０ａｅに向かって移動する。電流の向きと、磁化のシフトの向きが逆でもよい。
【００５３】
ＭＭＬ１０に情報を記憶する（書き込む）場合には、一端部１０ａｅから他端部１０ａｆに向かう電流のパルスをＭＭＬ１０に供給し、且つ入出力部３１−１によって、入出力部３１−１に接続されているＭＭＬ１０内の部分に、第１磁化方向１５ｍａまたは第２磁化方向１５ｍｂの磁化を形成する。これによって、複数の磁区１５の磁化が一端部１０ａｅから他端部１０ａｆに向かって移動すると同時に、入出力部３１−１に接続されているＭＭＬ１０内の部分に情報が書き込まれる。
【００５４】
ＭＭＬ１０に記憶された情報を再生する（読み出す）場合には、他端部１０ａｆから一端部１０ａｅに向かう電流のパルスをＭＭＬ１０に供給し、且つ入出力部３１−１により、入出力部３１−１に接続されているＭＭＬ１０内の部分の磁化の方向（第１磁化方向または第２磁化方向）が検出される。これによって入出力部３１−１に接続されているＭＭＬ１０内の部分から情報が読み出されると同時に、複数の磁区１５の磁化が他端部１０ａｆから一端部１０ａｅに向かって移動する。
【００５５】
入出力部３１−１では、例えば、磁気抵抗効果などにより、入出力部３１−１に接続されているＭＭＬ１０内の部分の磁化の方向が検出される。
【００５６】
このように、ＭＭＬ１０に対する情報の書き込みと読み出しは、後入れ先出し方式で行われる。ＭＭＬ１０からの情報の読み出しは破壊読み出しである。
【００５７】
ここでは、１つのＭＭＬ１０に対する情報の書き込みと読み出しについて説明したが、実際には、同じブロックに含まれる全てのＭＭＬに対する情報の書き込みおよび読み出しが並列に実行される。
【００５８】
図４は、ＭＭＬ１０における記憶状態の移動（磁壁１６の移動）を示している。  
図４においては、初期記憶状態ＭＳｔにおいて、所定の情報「００１１０１１００１」がＭＭＬ１０に記憶されている場合が想定されている。図４においては、１ビットシフト分の電流パルスを与えてこの情報をシフトさせた後の３つの状態（ＣＡＳＥ１、ＣＡＳＥ２、ＣＡＳＥ３）を例示している。
【００５９】
ＣＡＳＥ１は、「正しいシフト動作」に対応する。この場合、すべての磁壁１６が同じ速度で移動する。この場合は、シフト動作後においても初期記憶状態ＭＳｔの情報が維持されている。
【００６０】
一方、ＣＡＳＥ２は、誤動作の例である。ＣＡＳＥ２では、２番目の磁壁１６が他の磁壁よりも早い速度で移動している。２番目の磁壁１６が３番目の磁壁１６に追いついて、情報の一部が失われている。すなわち、初期記憶状態ＭＳｔの情報が維持されず、情報が変化している。
【００６１】
ＣＡＳＥ３も、誤動作の例である。ＣＡＳＥ３では、２番目の磁壁１６の移動速度が遅い。この例では、２番目の磁壁１６が移動していないように描かれている。この場合も、初期の記憶状態ＭＳｔの情報が維持されず、情報が変化している。
【００６２】
このように、磁壁１６の移動速度にばらつきがあると、磁気記憶において誤動作が生じる。この誤動作は、情報がシフトされる回数が多くなると顕著となる。すなわち、シフト動作の回数が多くなると、情報が劣化する。
【００６３】
以下、メモリシステム１の詳細について説明する。まず、メモリシステム１が有する幾つかの特徴の概要について説明する。尚、以下では、理解しやすいように特定の数値を例示して説明するが、本実施形態は、これら数値に限定されるものではない。
【００６４】
＜データ扱い単位＞  
基本的には、ブロックへのデータの書き込みおよび読み出しは、ブロックサイズに対応するデータの単位で実行される。
【００６５】
＜ＥＣＣフレーム＞  
ＥＣＣフレームのサイズは４ＫＢ＋α’／８である。
【００６６】
＜エンコードおよびデコード＞  
メモリコントローラ２は、不揮発性メモリ３のあるブロックに書き込むべきデータ部をエンコードしてＥＣＣ（パリティ）が付加されたデータ部を生成し、ＥＣＣ（パリティ）が付加されたデータ部を不揮発性メモリ３のこのブロックに書き込む。メモリコントローラ２は、不揮発性メモリ３のあるブロックから読み出されたデータ部に付加されているＥＣＣを使用してこのデータ部をデコードし、この読み出されたデータ部の誤りを訂正する。
【００６７】
＜データ読み出し＞  
メモリコントローラ２は、たとえホスト４によって指定された読み出し対象データがあるブロックに格納された複数のデータ部の一部のみであった場合でも、このブロック内の全てのデータ部を不揮発性メモリ３から読み出す。メモリコントローラ２は、読み出された全てのデータ部を再エンコードし、再エンコードされたデータ部それぞれ、つまりＥＣＣ（パリティ）が付加されたデータ部それぞれを、同じブロックか、違うブロックに書き戻す。
【００６８】
＜書き戻し先＞  
データバッファ２５が十分な容量を有しているケースにおいては、メモリコントローラ２は、不揮発性メモリ３内のあるブロックから読み出したデータ部それぞれを、同じブロックに書き戻してもよいし、別のブロックに書き戻してもよい。ここで、書き戻しは、不揮発性メモリ３から読み出されたデータ部のリカバリのために行われる。不揮発性メモリ３内の各ブロックからデータが読み出されると、そのデータが不揮発性メモリ３から消失されてしまうからである。
【００６９】
データバッファ２５の容量が少ない場合には、メモリコントローラ２は、不揮発性メモリ３内のあるブロックから１つずつ読み出されるデータ部を、別のブロックに１つずつ書き戻すことができる。この場合、この別のブロックにおけるデータ部の配置は、データ部が読み出された元のブロックにおけるデータ部の配置とは逆順となる。
【００７０】
＜ブロックシフトカウンタ＞  
メモリコントローラ２は、不揮発性メモリ３内の複数のブロックの各々について、データをシフトさせる動作が行われた回数の累積値を示すカウンタ値を管理する。このカウンタ値はブロックそれぞれの疲弊度を評価するために使用される。このカウンタはブロックシフトカウンタと称される。
【００７１】
＜誤り訂正符号の符号量配分＞  
メモリコントローラ２は、データ部が書き込まれるべきブロック内のページの位置に応じて、このデータ部に付加される誤り訂正符号の符号量を変更することができる。
【００７２】
以下、メモリシステム１の動作の例を説明する。  
ここでは、ホスト４から４ＫＢ単位（＝ページサイズ）でデータのライト／リードが要求され、メモリコントローラ２が、不揮発性メモリ３に対するデータの書き込みおよび読み出しをブロックサイズ単位で行う場合を想定する。
【００７３】
まず、書き込み処理について説明する。ホスト４から受信される４ＫＢデータは、データバッファ２５に格納される。符号化／復号部（Ｅｎｃｏｄｅｒ／Ｄｅｃｏｄｅｒ）２４内の符号化部２６は、この４ＫＢデータをエンコードしてこの４ＫＢデータに対応する誤り訂正符号を生成する。生成された誤り訂正符号が付加されたこの４ＫＢデータはデータバッファ２５に再び格納される。
【００７４】
データバッファ２５に８ページ分のデータ（誤り訂正符号が付加された８個の４ＫＢデータ）が蓄積されると、メモリコントローラ２は、８ページ分のデータを不揮発性メモリ内のあるブロックに書き込む。
【００７５】
書き込み処理の手順を図８および図９に示す。エンコード処理にかかる遅延がデータバッファ２５から不揮発性メモリ３までの転送スピードに対して十分少ない場合には、図８のフローチャートに示すように、不揮発性メモリ３にデータを書く時にエンコード処理を行うという方法を利用することができる。一方、エンコード処理を前もって行う場合には、図９のフローチャートに示される手順で書き込み処理が実行される。
【００７６】
まず、図８のフローチャートに示される書き込み処理について説明する。  
メモリコントローラ２がホスト４からライト要求を受信した時、メモリコントローラ２は、図８のフローチャートに示される書き込み処理を開始する。
【００７７】
メモリコントローラ２は、このライト要求に関連付けられた４ＫＢデータをホスト４から受信し、この４ＫＢデータをデータバッファ２５に格納する（ステップＳ１）。メモリコントローラ２は、データバッファ２５に蓄積されたデータ部の数をカウントし、データバッファ２５に蓄積されたデータ部の数が８に達したか否かを判定する（ステップＳ２）。データバッファ２５に蓄積されたデータ部の数が８個に達していないならば（ステップＳ２のＮＯ）、メモリコントローラ２は、処理を終了する。
【００７８】
データバッファ２５に蓄積されたデータ部の数が８個に達したならば（ステップＳ２のＹＥＳ）、メモリコントローラ２は、符号化部２６を使用してこれら８個のデータ部をそれぞれエンコードして誤り訂正符号をそれぞれ生成し、これら誤り訂正符号がそれぞれに付加された８個のデータ部を不揮発性メモリ３内のあるブロックに書き込む（ステップＳ４）。ステップＳ４では、メモリコントローラ２は、データバッファ２５に蓄積されたデータ部の数をゼロにリセットする処理も実行する。
【００７９】
次に、図９のフローチャートに示される書き込み処理について説明する。  
メモリコントローラ２がホスト４からライト要求を受信した時、メモリコントローラ２は、図９のフローチャートに示される書き込み処理を開始する。
【００８０】
メモリコントローラ２は、このライト要求に関連付けられた４ＫＢデータをホスト４から受信し、この４ＫＢデータをデータバッファ２５に格納する（ステップＳ１１）。メモリコントローラ２は、符号化部２６を使用してこの４ＫＢデータをエンコードして誤り訂正符号を生成し（ステップＳ１２）、誤り訂正符号が付加された４ＫＢデータをデータバッファ２５に格納する。
【００８１】
メモリコントローラ２は、データバッファ２５に蓄積されたデータ部の数、つまり誤り訂正符号が付加された４ＫＢデータの数をカウントし、データバッファ２５に蓄積されたデータ部の数が８に達したか否かを判定する（ステップＳ１３）。データバッファ２５に蓄積されたデータ部の数が８個に達していないならば（ステップＳ１３のＮＯ）、メモリコントローラ２は、処理を終了する。
【００８２】
データバッファ２５に蓄積されたデータ部の数が８個に達したならば（ステップＳ１３のＹＥＳ）、メモリコントローラ２は、誤り訂正符号がそれぞれに付加された８個のデータ部を不揮発性メモリ３内のあるブロックに書き込む（ステップＳ１４）。ステップＳ４では、メモリコントローラ２は、データバッファ２５に蓄積されたデータ部の数をゼロにリセットする処理も実行する。
【００８３】
＜付与される誤り訂正符号の符号量＞  
このように、本実施形態では、１ページ分の４ＫＢデータに誤り訂正符号（パリティ）が追加される。誤り訂正符号（パリティ）のサイズは、例えば、α’／８である。この結果、誤り訂正符号が付加された８ページ分のデータの総サイズは、３２ＫＢ＋α’となる。
【００８４】
＜書き込み動作について＞  
図８のステップＳ４および図９のステップＳ１４の各々で行われる書き込み動作につい説明する。
【００８５】
メモリコントローラ２は、書き込み指示（Ｐｒｏｇｒａｍコマンド）とともに３２ＫＢ＋α’のデータのうちの最初の１レイヤ分のデータを不揮発性メモリ３に送出し、この１レイヤ分のデータを、選択されたブロックのレイヤＬ２８７に書き込む。この１レイヤ分のデータのサイズは、１Ｋビット＋αである。
【００８６】
この１レイヤ分のデータが選択されたブロックのレイヤＬ２８７に書き込まれるのと同時に、選択されたブロックの各レイヤ（ｎ）のデータはレイヤ（ｎ−１）にシフトされる。
【００８７】
これを繰り返し、３６レイヤ目のデータが選択されたブロックに書き込まれると、レイヤＬ２８７〜レイヤＬ２５２の部分、つまり、ページｐ７に、４ＫＢ＋α’／８のサイズを有するデータ部（ページデータ）が書かれた状態になる。
【００８８】
そして、残りの７ページ分のデータ部それぞれをこの選択されたブロックに書き込む処理が完了すると、図５に示すように、最初に入力されたページデータＤ０はページｐ０に、最後に、つまり８番目に入力されたページデータＤ７はページｐ７に書き込まれた（プログラムされた）状態になる。
【００８９】
上述の説明では、全ての４ＫＢデータに等しいサイズ（α’／８）のパリティを誤り訂正符号として追加するようにエンコード処理を実行した。したがって、全てのページは３６レイヤずつの境界で分けられる。例えば、ページｐ０はレイヤＬ０〜レイヤＬ３５から成り、ページｐ７はレイヤＬ２５２〜レイヤＬ２８７から成る。
【００９０】
データ部が書き込まれるべきブロック中の位置によって異なる強度のＥＣＣをデータ部に付加する場合が考えられる。一例では、最終的にページｐ０にプログラムされるデータ部、つまり最初にブロックに入力されるページデータに多くパリティを割り当て、逆に最終的にページｐ７にプログラムされるデータ部、つまり最後にブロックに入力されるページデータに少ないパリティを割り当てる。その場合、図６に示すように、最初に入力されるデータ部Ｄ０のパリティ（ＥＣＣ）を含むサイズは４ＫＢ＋α’／８＋γ、最後にプログラムされるデータ部Ｄ７のパリティ（ＥＣＣ）を含むサイズは４ＫＢ＋α’／８−γ、それ以外のデータ部Ｄ２〜Ｄ６の各々については、パリティ（ＥＣＣ）を含むサイズは、４ＫＢ＋α’／８になる。
【００９１】
例えば、γが３つのレイヤに対応するサイズを有するケースでは、図６のように、ページｐ０はレイヤＬ０〜レイヤＬ３８の３９レイヤから成り、ページｐ７はレイヤＬ２５５〜レイヤＬ２８７の３３レイヤから成る。
【００９２】
１ブロック中に記録されるデータ全体に含まれるパリティの合計サイズはα’に維持される。最終的にページｐ７にプログラムされるデータＤ７に含まれるパリティのサイズは３レイヤ分少なく、最終的にページｐ０にプログラムされるデータＤ０に含まれるパリティのサイズは３レイヤ分多い。このパリティの配分は一例に過ぎない。例えば、ページｐ１とページｐ６との間でもパリティサイズを調整する場合が考えられる。この場合、最終的にページｐ６にプログラムされるデータに含まれるパリティのサイズを２レイヤ分減らし、最終的にページｐ１にプログラムされるデータに含まれるパリティのサイズを２レイヤ分増やしてもよい。
【００９３】
このように、本実施形態では、書き込み先ブロックの容量に対応する複数のデータ部（ここでは、８個のページデータ）をこの書き込み先ブロックに書き込む場合、メモリコントローラ２は、書き込むべきページデータが書き込み先ブロックへ入力される順序に応じて、この書き込むべきページデータに付加される誤り訂正符号の符号量を変更する。
【００９４】
書き込み動作においては、最初に書き込み先ブロックに入力されたページデータ、つまり最終的にページｐ０にプログラムされるデータＤ０は、何度もシフトされる。一方、最後に書き込み先ブロックに入力されたページデータ、つまり最終的にページｐ７にプログラムされるデータＤ７がシフトされる回数は非常に少ない。読み出し動作においても、データＤ０がシフトされる回数はデータＤ７がシフトされる回数よりも非常に多い。したがって、最終的にページｐ０にプログラムされるデータＤ０には誤りが蓄積されやすい。
【００９５】
本実施形態では、書き込むべきページデータが書き込み先ブロックへ入力される順序に応じて、このページデータに付加される誤り訂正符号の符号量が変更される。したがって、最終的にページｐ０にプログラムされるデータＤ０に対して誤り訂正符号の符号量をより多く配分することが可能となる。
【００９６】
なお、上述の誤り訂正符号の符号量配分では、ページｐ０〜ｐ７が互い異なるレイヤを含むようにページｐ０〜ｐ７への誤り訂正符号の符号量の配分が決定される例を説明したが、図７に示すように、隣接する２つのページが同じレイヤ内のＭＭＬ間の境界で互いに分離されるようにページｐ０〜ｐ７への誤り訂正符号の符号量の配分が決定されてもよい。
【００９７】
この場合、レイヤ単位で読み出されたデータの一部を次のページ用に扱うことが必要になるため、処理が複雑になる。しかし、ページｐ０〜ページｐ７への誤り訂正符号の配分量は予め定められている。したがって、個々のページについて、先頭レイヤ、先頭レイヤ内の先頭ＭＭＬ、最終レイヤ、最終レイヤ内の最終ＭＭＬも予め定められる。よって、アクセス対象のページのｉｄ（例えばページ番号）に単純な演算を施すだけで、このアクセス対象のページに対応する先頭レイヤ、先頭レイヤ内の先頭ＭＭＬ、最終レイヤ、最終レイヤ内の最終ＭＭＬを容易に算出することができる。
【００９８】
本実施形態における、各データ部への誤り訂正符号の符号量配分は図１の制御部２３によって行われる。
【００９９】
書き込み先ブロックへの８つのデータ部（８つのページデータ）の書き込みが完了した場合、メモリコントローラ２は、これら８つのページデータそれぞれに対応する論理アドレスにこれら８つのページデータが格納された不揮発性メモリ３内の記憶位置を示す物理アドレスがマッピングされるように、ＬＵＴ２３１を更新する。
【０１００】
ＬＵＴ２３１は、図１０に示すように、論理アドレスそれぞれとこれら論理アドレスに対応するデータ部が書き込まれている不揮発性メモリ３の物理アドレス（ブロック番号、ページ番号）それぞれとの間のマッピングを管理してもよい。論理クラスタアドレスは論理ブロックアドレス（ＬＢＡ）または論理クラスタアドレス（ＬＣＡ）のいずれであってもよいが、以下では、論理アドレスとして、４ＫＢ単位でアドレス指定するＬＣＡが使用される場合を想定する。ブロック番号はある特定のブロックを指定するブロック識別子（ブロックｉｄ）であり、ページ番号はページｐ０〜ｐ７のいずれかを指定するページ識別子である。
【０１０１】
図１０では、ＬＣＡ０に対応するページデータＬＣＡ０−ｄがブロックｂ０のページｐ６、ＬＣＡ１に対応するページデータＬＣＡ１−ｄがブロックｂ５のページｐ２、ＬＣＡ２に対応するページデータＬＣＡ２−ｄがブロックｂ０のページｐ７、…、ＬＣＡ８に対応するページデータＬＣＡ８−ｄがブロックｂ０のページｐ５に書き込まれている場合が想定されている。
【０１０２】
この場合、ＬＵＴ２３１においては、ＬＣＡ０に対応するエントリにブロック番号ｂ０およびページ番号ｐ６が格納され、ＬＣＡ１に対応するエントリにブロック番号ｂ５およびページ番号ｐ２が格納され、ＬＣＡ２に対応するエントリにブロック番号ｂ０およびページ番号ｐ７が格納され、同様に、ＬＣＡ８に対応するエントリにブロック番号ｂ０およびページ番号ｐ５が格納されている。
【０１０３】
ホスト４から受信されるリード要求によって例えばＬＣＡ２が指定された場合には、メモリコントローラ２は、ＬＵＴ２３１を参照することによって、ＬＣＡ２に対応するページデータＬＣＡ２−ｄが格納されている不揮発性メモリ３内の記憶位置としてブロック番号ｂ０、ページ番号ｐ７を取得することができる。
【０１０４】
ホスト４からリード要求を受信した場合、メモリコントローラ２は、以下の処理を実行する。
【０１０５】
メモリコントローラ２は、ＬＵＴ２３１を使って、ホスト４からのリード要求によって指定されたＬＣＡｉに対応するページデータが保存されているブロック番号およびページ番号を得る。次に、メモリコントローラ２は、そのブロックの全ページのページデータをページｐ７から１ページずつ順番に読み出す。
【０１０６】
図１０のブロックｂ０を例にすると、まず、ブロックｂ０のページｐ７にあるページデータＬＣＡ２−ｄが読み出されると、ページデータＬＣＡ２−ｄはブロックｂ０の外に出され、ブロックｂ０のページｐ６にあったページデータＬＣＡ０−ｄはブロックｂ０のページｐ７に移動（シフト）し、ブロックｂ０のページｐ５にあったページデータＬＣＡ８−ｄはブロックｂ０のページｐ６に移動（シフト）し、…、ブロックｂ０のページｐ０にあったページデータＬＣＡ４−ｄはブロックｂ０のページｐ１に移動（シフト）する。
【０１０７】
ブロックｂ０のページｐ７に移動されているページデータＬＣＡ０−ｄが読み出されると、ページデータＬＣＡ０−ｄはブロックｂ０の外に出され、ブロックｂ０のページｐ７に移動されているページデータＬＣＡ８−ｄはブロックｂ０のページｐ７に移動し、ブロックｂ０のページｐ５に移動されているページデータＬＣＡｘｘｘ−ｄはブロックｂ０のページｐ６に移動し、…、ブロックｂ０のページｐ１に移動されているページデータＬＣＡ４−ｄはブロックｂ０のページｐ２に移動する。
【０１０８】
このようにして、メモリコントローラ２は、図１０のブロックｂ０に格納されていた８個のページデータを不揮発性メモリ３から順次読み出す。なお、実際には、上記のようなデータの移動（シフト）動作はレイヤ単位で実行される。１つのページが３６個のレイヤを含む場合、各ページのデータは３６回のシフト動作によって１ページ分シフトされる。
【０１０９】
そして、メモリコントローラ２は、読み出したページデータそれぞれの誤りを訂正するためにこれら読み出したページデータそれぞれを符号化／復号部２４の復号部２７によってデコードする。復号部２７によってデコードされたページデータがホスト４から要求されたデータであるならば、メモリコントローラ２は、ホストインタフェース２１を介して、このデコードされたページデータをホスト４に返す。さらに、復号部２７によってデコードされたページデータがホスト４から要求されたデータであるならば、メモリコントローラ２は、このデコードされたページデータをデータバッファ２５にも入れる。一方、復号部２７によってデコードされたページデータがホスト４から要求されたデータでないならば、メモリコントローラ２は、このデコードされたページデータを、ホスト４には返さず、データバッファ２５に入れる。
【０１１０】
データバッファ２５に入れられた各ページデータは符号化／復号部２４の符号化部２６によって再度エンコードされ、そして不揮発性メモリ３にプログラムされる。
【０１１１】
上述したページデータの読み出しおよびプログラムが行われる際に、データバッファ２５が十分な容量を有しており、データバッファ２５内にリード用の３２ＫＢの領域を確保可能な場合には、メモリコントローラ２は、１ブロック分の全てのページデータをデータバッファ２５に入れる。その後、メモリコントローラ２は、データバッファ２５のページデータを順次再エンコードし、不揮発性メモリ３にプログラムする（書き戻す）。その方法は、図８および図９で説明した書き込み処理と同様である。これらページデータが書き戻されるブロックは、これらページデータが読み出されたブロックと同じブロックでもよいし、別のブロックでもよい。同じブロックまたは別のブロックのいずれに書き戻すかは、これらブロックのブロックシフトカウンタの値に基づいて決定される。これらページデータを同じブロックにページ位置も同じになるように書き戻す場合には、これらページデータの記憶位置は変更されないので、ＬＵＴ２３１の更新は不要である。これらページデータを別のブロックに書き戻す場合には、これら各ページデータに対応するブロック番号がこの別のブロックのブロック番号に変更されるようにＬＵＴ２３１上のブロック番号を更新する。
【０１１２】
図１１の斜視図は、メモリセルアレイの構成の一例を示す。図１１において、互いに直交する２方向をＸ方向およびＹ方向とし、これらＸ方向およびＹ方向（ＸＹ平面）に対して直交し、ＭＭＬ１０が延伸した方向をＺ方向とする。
【０１１３】
Ｙ方向に延伸したソース線ＳＬは、Ｘ方向に複数配列される。ソース線ＳＬ上には、ＭＭＬ１０、磁気抵抗効果素子１１、および選択素子１２がＺ方向に配列されている。磁気抵抗効果素子１１は、例えばＭＴＪ素子で構成される。ＭＴＪ素子は、磁性層１１Ｒ、非磁性層１１Ｎ、および磁性層１１Ｓを含む。ＭＴＪ素子の詳細については後述する。
【０１１４】
メモリセルアレイの構成を詳述すると、ソース線ＳＬ上にはＭＭＬ１０が設けられる。ＭＭＬ上には磁性層１１Ｓが設けられる。磁性層１１ＳはＹ方向にある距離だけ延伸しており、延伸した磁性層１１Ｓ上には非磁性層１１Ｎおよび磁性層１１Ｒが順に設けられる。磁性層１１Ｒ上には、選択素子１２を介してビット線ＢＬが設けられる。
【０１１５】
Ｚ方向に設けられたＭＭＬ、磁気抵抗効果素子１１、および選択素子１２は、ＸおよびＹ方向に行列状に配列される。Ｘ方向に配列された選択素子１２上にはビット線ＢＬが設けられる。さらに、磁性層１１Ｓ上には、フィールド線（書き込み線）ＦＬが設けられる。フィールド線ＦＬは、Ｘ方向およびＹ方向に隣接する磁気抵抗効果素子１１の間を縫うように、Ｘ方向にジグザグ状に配置される。
【０１１６】
以下に、ＭＴＪ素子について詳述する。ＭＴＪ素子は、磁性層１１Ｒ、非磁性層１１Ｎ、および磁性層１１Ｓを含む。磁性層１１Ｒと磁性層１１Ｓ間には非磁性層１１Ｎが配置される。磁性層１１Ｒは参照層として機能し、磁性層１１Ｓは記憶層として機能する。非磁性層１１Ｎはトンネルバリアとして機能する。なお、ＭＴＪ素子は、さらなる層を含んでいてもよい。
【０１１７】
磁性層（記憶層）１１Ｓは、ある軸に沿う方向に磁化されている。例えば、磁性層１１Ｓの磁化は、層１１Ｓ、１１Ｒ、および１１Ｎの境界面に対して垂直な方向に沿って安定している。磁性層１１Ｓの磁化方向は、ＭＭＬが有する磁区の磁化方向により、反転されることが可能である。
【０１１８】
磁性層（参照層）１１Ｒは、方向が固定または不変の磁化を有し、例えば、磁性層（記憶層）１１Ｓの保磁力より大きい保磁力を有する。磁性層１１Ｒの磁化方向が「固定されている」または「不変である」とは、磁性層（記憶層）１１Ｓの磁化を反転させる、ＭＭＬの磁区の磁化方向によって、磁性層１１Ｒの磁化方向が反転しないことを意味する。
【０１１９】
磁性層１１Ｒ、非磁性層１１Ｎ、および磁性層１１Ｓの組は、磁気抵抗効果を示す。具体的には、磁性層１１Ｓの磁化方向と磁性層１１Ｒの磁化方向が平行である場合、ＭＴＪ素子は最小の抵抗値を示す。一方、磁性層１１Ｓの磁化方向と磁性層１１Ｒの磁化方向が平行でない場合、ＭＴＪ素子は最大の抵抗値を示す。ＭＴＪ素子である磁気抵抗効果素子１１は、磁性層（記憶層）１１Ｓと磁性層（参照層）１１Ｒの磁化方向の相対関係が平行であるとき低抵抗状態にあり、平行でないとき高抵抗状態にある。
【０１２０】
図１２および図１３は、不揮発性メモリ３内のあるＭＭＬ１０に対する書き込みシーケンスの例を示す。
【０１２１】
まず図１２（Ａ）に示すように、データの書き込みを開始するために、ＦＬに電流が流されたことにより発生する誘導磁場により、特定の磁化方向を有する磁区（ここでは磁区Ｎ）が形成される（Ｐｒｅ  Ｗｒｉｔｅ）。形成された磁区Ｎは、図１２（Ｂ）に示すように、ＭＭＬ１０の上層の磁区から下層の磁区に向かう方向への磁区単位のシフト（Ｆｏｒｗａｒｄ  Ｓｈｉｆｔ）により、ＭＭＬ１０の最上層の磁区として設定される。このシフトは、ＭＭＬ１０に電流が流されたことに応じて発生する。
【０１２２】
次いで図１２（Ｃ）に示すように、データ“１”を書き込むために磁区Ｓが形成される（“Ｓ／１”  Ｗｒｉｔｅ）。形成された磁区Ｓは、図１２（Ｄ）に示すように、Ｆｏｒｗａｒｄ  Ｓｈｉｆｔにより、ＭＭＬ１０の最上層の磁区として設定される。また、このＦｏｒｗａｒｄ  Ｓｈｉｆｔにより、それまで最上層に設定されていた磁区Ｎが１つ下の層に移動する。ＭＭＬ１０内に形成された、最上層の磁区Ｓと１つ下の層の磁区Ｎは、データ“１”の格納に相当する。
【０１２３】
さらに図１３（Ｅ）に示すように、データ“０”を書き込むために磁区Ｓが形成される（“Ｓ／０”  Ｗｒｉｔｅ）。形成された磁区Ｓは、図１３（Ｆ）に示すように、Ｆｏｒｗａｒｄ  Ｓｈｉｆｔにより、ＭＭＬ１０の最上層の磁区として設定される。また、このＦｏｒｗａｒｄ  Ｓｈｉｆｔにより、それまで最上層に設定されていた磁区Ｓが１つ下の層に移動すると共に、その１つ下の層に設定されていた磁区Ｎがさらに１つ下の層に移動する。ＭＭＬ１０内に形成された、最上層の磁区Ｓとその１つ下の層の磁区Ｓは、データ“０”の格納に相当する。
【０１２４】
図１４は、不揮発性メモリ３内のあるＭＭＬ１０に対する読み出しシーケンスの例を示す。ここでは図１４（Ａ）に示すように、読み出しが開始される前の初期状態において、ＭＭＬ１０の最上層から順に、磁区Ｓ、磁区Ｓ、磁区Ｎが設定されている場合について例示する。
【０１２５】
まず図１４（Ｂ）に示すように、ＭＭＬ１０の下層の磁区から上層の磁区に向かう方向への磁区単位のシフト（Ｒｅｖｅｒｓｅ  Ｓｈｉｆｔ）により、ＭＭＬ１０内の複数の磁区がそれぞれ１つ上の層に移動した後、最上層から移動した磁区Ｓによる磁気誘導によって生じる、磁気抵抗効果素子１１の特定の抵抗状態（ここでは低抵抗状態）が検知される（“Ｓ／Ｘ”  Ｒｅａｄ）。
【０１２６】
次いで図１４（Ｃ）に示すように、Ｒｅｖｅｒｓｅ  Ｓｈｉｆｔにより、ＭＭＬ１０内の複数の磁区がそれぞれ１つ上の層に移動した後、最上層から移動した磁区Ｓによる磁気誘導によって生じる、磁気抵抗効果素子１１の低抵抗状態が検知され、１つ前に検知された低抵抗状態から変化がないことに基づいて、データ“０”が出力される（“Ｓ／０  Ｒｅａｄ”）。つまり、初期状態において最上層に設定されていた磁区Ｓと、その１つ下の層に設定されていた磁区Ｓとによって格納されていたデータ“０”が読み出される。
【０１２７】
さらに図１４（Ｄ）に示すように、Ｒｅｖｅｒｓｅ  Ｓｈｉｆｔにより、ＭＭＬ１０内の複数の磁区がそれぞれ１つ上の層に移動した後、最上層から移動した磁区Ｎによる磁気誘導によって生じる、磁気抵抗効果素子１１の高抵抗状態が検知され、１つ前に検知された低抵抗状態から変化したことに基づいて、データ“１”が出力される（“Ｎ／１  Ｒｅａｄ”）。つまり、初期状態において最上層の１つ下の層に設定されていた磁区Ｓと、そのさらに１つ下の層に設定されていた磁区Ｎとによって格納されていたデータ“１”が読み出される。
【０１２８】
以上のように、不揮発性メモリ３は、後入れ先出し方式でデータの書き込みおよび読み出しが行われる特性と、読み出しによってデータが破壊される破壊読み出しの特性とを有する。以下では、このような特性を有する不揮発性メモリ３におけるコンパクション動作について説明する。
【０１２９】
＜比較例  ＮＡＮＤ型フラッシュメモリにおけるコンパクション＞  
本実施形態の不揮発性メモリ３を備えるメモリシステム１におけるコンパクション動作が理解されやすいように、比較例として、ＮＡＮＤ型フラッシュメモリを備えるメモリシステムにおけるコンパクション動作について説明する。また以下では、不揮発性メモリ３が磁壁メモリである場合を例示する。
【０１３０】
ＮＡＮＤ型フラッシュメモリは複数のブロックを含む。各ブロックは複数のページを含む。ブロックは最小の消去単位として機能する。ページは、データ書き込み動作およびデータ読み出し動作の単位である。
【０１３１】
ブロックは、有効データを格納しているアクティブブロック（書き込み済みブロック）と、有効データを格納しておらず、イレーズ処理を経ることで新たなデータの書き込みに利用可能なフリーブロック（未使用ブロックとも称する）とに大別される。有効データは、論理アドレス（例えば論理ブロックアドレス（ＬＢＡ））に関連付けられているデータであって、後にホスト４によってリードされる可能性があるデータである。
【０１３２】
アクティブブロックには無効データも含まれ得る。無効データは、どの論理アドレスにも関連付けられていないデータであって、もはやホスト４からリードされる可能性がないデータである。
【０１３３】
各ブロックに対して許容できる最大プログラム／イレーズ（Ｐ／Ｅ）サイクル数には限界がある。あるブロックの１回のＰ／Ｅサイクルは、このブロック内のすべてのメモリセルを消去状態にするための消去動作と、このブロックのページそれぞれにデータを書き込む書き込み動作（より詳しくはプログラム動作）とを含む。
【０１３４】
図１５は、データ書き込みが行われることによるフリーブロック群４１とアクティブブロック群４２との変遷を時系列順に示している。ここでは、ＮＡＮＤ型フラッシュメモリに、３つのフリーブロック４１１，４１２，４１３を含むフリーブロック群４１と、それぞれ全ページにデータが書き込まれた４つのアクティブブロック（書き込み済みブロック）４２１，４２２，４２３，４２４を含むアクティブブロック群４２とが含まれる時点からの変遷を例示する。
【０１３５】
図１５では、ブロック内の、有効データが格納されているページ（Ｖａｌｉｄ）、無効データが格納されているページ（Ｉｎｖａｌｉｄ）、およびデータがまだ書き込まれていないページ（Ｅｒａｓｅ）が、それぞれ識別できるように表記されている。管理が容易になるように、例えばデータが全ページに書き込まれたブロックがアクティブブロックとして管理される。
【０１３６】
１つのページへのデータ書き込みは、１回のＰ／Ｅサイクル当たり１回のみ可能である。このため、あるＬＢＡに対応する更新データは、このＬＢＡに対応する以前のデータが格納されている物理記憶位置ではなく、別の物理記憶位置に書き込まれる。そして、このＬＢＡをこの別の物理記憶位置に関連付けるようにＬＵＴが更新されることにより、以前のデータが無効化され、無効データになる。
【０１３７】
図１５に示すように、例えば、フリーブロック群４１から新たな書き込み先として選択されたブロック４１１に、あるＬＢＡに対応する更新データが書き込まれたことにより、このＬＢＡに対応するアクティブブロック４２１〜４２４内の以前のデータが無効データになる。そして、全ページにデータが書き込まれたブロック４１１は、新たなアクティブブロックとして管理される。同様にして、フリーブロック群４１から新たな書き込み先として選択され、全ページにデータが書き込まれたブロック４１２も、新たなアクティブブロックとして管理される。
【０１３８】
このメモリシステムに設けられるメモリコントローラは、フリーブロックの数を管理している。フリーブロック群４１から選択されたブロックが新たな書き込み先ブロックとして使用されることに伴って、フリーブロックの数が閾値を下回った場合、ホスト４からのコマンドを処理する合間にコンパクション処理が開始される。
【０１３９】
図１６に示すように、コンパクション処理により、アクティブブロック（ソースブロック）４２１，４２２，４２３，４２４，４１１内の有効データが、コンパクションのための書き込み先ブロック（デスティネーションブロック）４３１，４３２，４３３に書き込まれる。そして、有効データが存在しなくなったブロック４２１，４２２，４２３，４２４，４１１は、イレーズ処理を経ることで新たなデータの書き込みに利用可能なフリーブロックとして再利用される。また、全ページにデータが書き込まれたデスティネーションブロック４３１，４３２，４３３は、アクティブブロックとして新たに管理される。
【０１４０】
図１７のフローチャートは、メモリコントローラによって実行されるコンパクション処理の手順の例を示す。
【０１４１】
まず、メモリコントローラはフリーブロック数が閾値未満であるか否かを判定する（ステップＳ２１）。フリーブロック数が閾値以上である場合（ステップＳ２１のＮＯ）、処理を終了する。
【０１４２】
フリーブロック数が閾値未満である場合（ステップＳ２１のＹＥＳ）、メモリコントローラはソースブロックを決定する（ステップＳ２２）。ソースブロックには、例えば有効データ率が小さいブロックが選択される。そして、メモリコントローラはデスティネーションブロックを決定する（ステップＳ２３）。デスティネーションブロックにはフリーブロックが選択される。
【０１４３】
次いで、メモリコントローラは、ソースブロック内の有効データをデスティネーションブロックに書き込む（ステップＳ２４）。ソースブロック内の全ての有効データがデスティネーションブロックに書き込まれた後、メモリコントローラはソースブロック内のデータを消去する（ステップＳ２５）。
【０１４４】
以上により、ＮＡＮＤ型フラッシュメモリを備えるメモリシステムでは、ソースブロックをフリーブロックとして再利用できる。ソースブロックとして有効データ率が小さいブロックが選択されることにより、無効データ率が大きいブロックから優先して無効データの領域をなくすことができるので、効率的にフリーブロックを増やすことができる。
【０１４５】
＜コンパクション＞  
本実施形態のメモリシステム１におけるコンパクション動作を説明するために、磁壁メモリ３内のブロックに関するパラメータを定義する。図１８は、あるブロックを構成する複数のＭＭＬ１０の内の１つを図示したものであり、説明を分かりやすくするために、ブロック内の複数のＭＭＬ１０において各レイヤの書き込み状態が全て同じであると仮定する。したがって、図１８に示す１つのＭＭＬ１０の状態は、ブロック内の全てのＭＭＬ１０の状態を表している。
【０１４６】
ＭＭＬ１０に含まれる複数のレイヤ間の上位／下位は、ＭＭＬ１０の深さ方向の位置に基づき、より浅い位置にあるレイヤを上位（上位レイヤ）と称し、より深い位置にあるレイヤを下位（下位レイヤ）と称する。複数のレイヤにそれぞれ格納されているデータを最上位のレイヤから最下位のレイヤに向かう第１の方向、またはこの第１の方向とは逆の第２の方向にレイヤ単位でシフトさせることによって、各ブロックに対するデータの書き込みおよび読み出しが後入れ先出し方式で行われる。
【０１４７】
ＭＭＬ１０内の各レイヤは、Ｖａｌｉｄ−ｄａｔａ、Ｉｎｖａｌｉｄ−ｄａｔａ、およびＶｏｉｄの３つの属性の内のいずれかを有する。
【０１４８】
Ｖａｌｉｄ−ｄａｔａ属性のレイヤ（Ｖａｌｉｄレイヤとも称する）には、論理アドレス（ここではＬＣＡ）に関連付けられている最新のデータであって、後にホスト４によって参照される可能性があるデータ（すなわち有効データ）が格納されている。ＭＭＬ１０内で最も深いＶａｌｉｄレイヤの深さを、有効レイヤ深さと定義する。つまり、有効レイヤ深さは、ＭＭＬ１０内の複数のブロックにおける、最上位レイヤから最も遠いＶａｌｉｄレイヤの位置、換言すると最下位レイヤに最も近いＶａｌｉｄレイヤの位置を示す。
【０１４９】
Ｉｎｖａｌｉｄ−ｄａｔａ属性のレイヤ（Ｉｎｖａｌｉｄレイヤとも称する）は、対応するエントリがＬＵＴ２３１に存在しないデータが格納され、且つそのレイヤよりも下にＶａｌｉｄレイヤが存在するレイヤである。換言すると、Ｉｎｖａｌｉｄレイヤは、どの論理アドレスにも関連付けられていないデータが格納され、且つＶａｌｉｄレイヤよりも上に存在する（つまり第１の方向にＶａｌｉｄレイヤが存在する）レイヤである。
【０１５０】
Ｖｏｉｄ属性のレイヤ（Ｖｏｉｄレイヤとも称する）は、ＭＭＬ１０にデータをさらに書き込み可能であることを示す。Ｖｏｉｄレイヤ（あるいはＶｏｉｄレイヤ群）はＭＭＬ１０内の最下部に含まれ得る。つまり、Ｖｏｉｄレイヤよりも下に、ＶａｌｉｄレイヤおよびＩｎｖａｌｉｄレイヤは存在しない。
【０１５１】
Ｖｏｉｄレイヤの数に相当する書き込み余地は、書き込み可能な領域の大きさを示し、ＭＭＬ１０に含まれるレイヤの総数であるＴｏｔａｌレイヤ深さから、有効レイヤ深さを減算することにより得られる。なお、どの論理アドレスにも関連付けられていないデータが格納されているレイヤであって、そのレイヤよりも下にＶａｌｉｄレイヤが存在しないレイヤは、Ｖｏｉｄレイヤである。
【０１５２】
各々の書き込み余地が１００％である複数のＭＭＬ１０で構成されるブロックは、フリーブロックである。つまり、複数のＭＭＬ１０内の全てのレイヤがＶｏｉｄレイヤであるブロックは、フリーブロックである。また、各々の書き込み余地が０％である複数のＭＭＬ１０で構成されるブロックは、データをさらに書き込むことができないブロックである。
【０１５３】
１つのＭＭＬ１０に含まれる全てのレイヤに対するＶａｌｉｄレイヤの割合（すなわちＭＭＬ１０のＴｏｔａｌレイヤ深さに対するＶａｌｉｄレイヤの数の割合）を有効レイヤ率と定義する。また、１つのＭＭＬ１０に含まれる全てのレイヤに対するＩｎｖａｌｉｄレイヤの割合（すなわちＭＭＬ１０のＴｏｔａｌレイヤ深さに対するＩｎｖａｌｉｄレイヤの数の割合）を無効レイヤ率と定義する。
【０１５４】
上述したようにブロック内の複数のＭＭＬ１０において各レイヤの書き込み状態が全て同じであると仮定するならば、１つのブロックに含まれる全てのレイヤに対するＶａｌｉｄレイヤの割合（すなわち１つのブロックの全レイヤ数に対するＶａｌｉｄレイヤの数の割合）を有効レイヤ率と定義し得る。また、１つのブロックに含まれる全てのレイヤに対するＩｎｖａｌｉｄレイヤの割合（すなわち１つのブロックの全レイヤ数に対するＩｎｖａｌｉｄレイヤの数の割合）を無効レイヤ率と定義し得る。
【０１５５】
図１９を参照して、利用されているブロックの好ましい状態と好ましくない状態とについて説明する。
【０１５６】
まず、全てのレイヤがＶａｌｉｄレイヤであるブロック６２は、全てのレイヤがＶａｌｉｄ−ｄａｔａの格納に利用されているので、好ましい状態のブロックと云える。
【０１５７】
Ｖａｌｉｄレイヤ６３１とＶｏｉｄレイヤ６３２とで構成されるブロック６３には、Ｖｏｉｄレイヤ６３２に相当する書き込み余地がある。したがって、ブロック６３は、レイヤ全てがＶａｌｉｄ−ｄａｔａの格納に用いられていないものの、書き込み余地の分、新たなデータの格納に利用可能であるので、全てのレイヤがＶａｌｉｄレイヤであるブロック６２に次いで好ましい状態であると云える。
【０１５８】
Ｉｎｖａｌｉｄレイヤ６４１およびＶａｌｉｄレイヤ６４２で構成されるブロック６４と、Ｖａｌｉｄレイヤ６５１，６５３およびＩｎｖａｌｉｄレイヤ６５２で構成されるブロック６５とは、データの格納に利用できないＩｎｖａｌｉｄレイヤ６４１，６５２をそれぞれ含んでいるので、好ましくない状態であると云える。このようなブロック６４，６５では、データを読み出すリード動作により、Ｉｎｖａｌｉｄレイヤ６４１，６５２のデータを読み出して、Ｉｎｖａｌｉｄレイヤ６４１，６５２をなくすことができる。なお、ブロック６５では、Ｉｎｖａｌｉｄレイヤ６５２に対する読み出しの前に、Ｖａｌｉｄレイヤ６５１に対するリード動作が必要になるので、負荷が大きくなる。そのため、ブロック６５は、ブロック６４よりも好ましくない状態であると云える。
【０１５９】
上述したように、磁壁メモリ３に対するデータの書き込みおよび読み出しは後入れ先出し方式で行われる。また、磁壁メモリ３は、読み出されたデータが当該不揮発性メモリ３から消える破壊読み出しの特性を有する。
【０１６０】
したがって、ＮＡＮＤ型フラッシュメモリではブロック単位でのイレーズが行われるのに対して、磁壁メモリ３では読み出しによりデータを削除できる。この特徴により、ＮＡＮＤ型フラッシュメモリでは、１つのブロック内の全ての領域にそれぞれデータが書き込まれたブロックが書き込み済みブロックとして分類されるのに対して、磁壁メモリ３では１つのブロック内の全ての領域（レイヤ）にデータが書き込まれる必要はない。つまり磁壁メモリ３では、少なくとも１つのレイヤにデータが書き込まれたブロックが、書き込み済みブロックとして分類される。
【０１６１】
また、ＮＡＮＤ型フラッシュメモリではフリーブロックを新たに作成するためにコンパクションが実施されたのに対して、磁壁メモリ３では書き込み余地を増やすためにコンパクションが実施される。
【０１６２】
図２０は、磁壁メモリ３内のブロックを用いたコンパクション動作の例を示す。  
図２０（Ａ）に示すシナリオ１の例では有効レイヤ率が３０％であるソースブロック４５が選択されているのに対して、図２０（Ｂ）に示すシナリオ２の例では有効レイヤ率が４０％であるソースブロック４７が選択されている。ここでは、いずれの例でも、フリーブロックがデスティネーションブロック４６，４８として選択されるものとする。フリーブロックであるデスティネーションブロック４６，４８は、全てのレイヤがＶｏｉｄレイヤであるので、有効レイヤ率および無効レイヤ率が０％であり、書き込み余地が１００％である。
【０１６３】
図２０（Ａ）に示すように、ソースブロック４５は、Ｖａｌｉｄ−ｄａｔａ  ｓ０を格納しているＶａｌｉｄレイヤとＶｏｉｄレイヤとで構成されている。また、ソースブロック４５の無効レイヤ率は０％であり、書き込み余地は７０％である。
【０１６４】
ソースブロック４５とデスティネーションブロック４６とを用いてコンパクション動作が行われた場合、ソースブロック４５からＶａｌｉｄ−ｄａｔａ  ｓ０が読み出され、読み出されたＶａｌｉｄ−ｄａｔａ  ｓ０がデスティネーションブロック４６に書き込まれる。その結果、ソースブロック４５の書き込み余地は１００％になり、デスティネーションブロック４６の書き込み余地は７０％になる。
【０１６５】
したがって、コンパクション動作の前後で、ソースブロック４５の書き込み余地とデスティネーションブロックの書き込み余地とが入れ替わっただけであり、ソースブロック４５とデスティネーションブロック４６とを合わせた全体の書き込み余地は変化していない。
【０１６６】
一方、図２０（Ｂ）に示すように、ソースブロック４７は、Ｖａｌｉｄ−ｄａｔａ  ｓ１を格納しているＶａｌｉｄレイヤと、Ｉｎｖａｌｉｄ−ｄａｔａを格納しているＩｎｖａｌｉｄ−ｄａｔａレイヤと、Ｖａｌｉｄ−ｄａｔａ  Ｓ２を格納しているＶａｌｉｄレイヤとで構成されている。また、ソースブロック４７の無効レイヤ率は６０％であり、書き込み余地は０％である。
【０１６７】
ソースブロック４７とデスティネーションブロック４８とを用いてコンパクション動作が行われた場合、ソースブロック４７からＶａｌｉｄ−ｄａｔａ  ｓ１が読み出され、Ｉｎｖａｌｉｄ−ｄａｔａが読み出され、Ｖａｌｉｄ−ｄａｔａ  ｓ２が読み出される。読み出されたＶａｌｉｄ−ｄａｔａ  ｓ１とＶａｌｉｄ−ｄａｔａ  ｓ２は、デスティネーションブロック４８に書き込まれる。その結果、ソースブロック４７の書き込み余地は１００％になり、デスティネーションブロック４８の書き込み余地は６０％になる。また、ソースブロック４７の無効レイヤ率は０％になる。
【０１６８】
したがって、ソースブロック４５とデスティネーションブロック４６とを合わせた全体の書き込み余地は、コンパクション動作の前後で、デスティネーションブロック４８の６０％の書き込み余地の分、増加している。つまり、コンパクション動作前のソースブロック４７における０％の書き込み余地と、コンパクション動作後のデスティネーションブロック４８における６０％の書き込み余地との差分だけ、書き込み余地が改善している。
【０１６９】
上述したＮＡＮＤ型フラッシュメモリに対するコンパクション動作では、ソースブロックとして有効データ率が小さいブロックが選択される。仮に、磁壁メモリ３に対するコンパクション動作でも同様にして有効レイヤ率が小さいブロックが選択された場合、シナリオ２の有効レイヤ率が４０％であるブロック４７ではなく、シナリオ１の有効レイヤ率が３０％のブロック４５がソースブロックとして選択される。その場合、コンパクション動作の前後で書き込み余地は変化しない。したがって、有効レイヤ率が小さいブロックをソースブロックとして選択したならば、コンパクション動作を行っても書き込み余地を改善できない可能性がある。
【０１７０】
そのため本実施形態では、データの書き込みおよび読み出しが後入れ先出し方式で行われる不揮発性メモリ３（例えば磁壁メモリ）に対するコンパクション動作において、無効レイヤ率が大きいブロックほど優先してソースブロックとして選択する。また、同一の無効レイヤ率を有するブロック間では、有効レイヤ深さが深いほど優先してソースブロックとして選択する。つまり、同一の高い無効レイヤ率を有する複数のブロックが選択された場合には、より深い有効レイヤ深さを有するブロックが、すなわち最下位レイヤにより近い有効レイヤを有するブロックが、ソースブロックとして選択される。
【０１７１】
図２１は、コンパクション動作に関するＮＡＮＤ型フラッシュメモリ（あるいはＮＯＲ型フラッシュメモリ）と磁壁メモリ３との相違点を示す。ＮＡＮＤ型フラッシュメモリと磁壁メモリ３のいずれでも、コンパクション動作はフリーブロック率（あるいはフリーブロック数）が閾値を下回ったことに応じて発動される。ＮＡＮＤ型フラッシュメモリに対するコンパクション動作において、ソースブロックは有効データ率が小さいブロックであり、デスティネーションブロックはフリーブロックである。
【０１７２】
これに対して、本実施形態における磁壁メモリ３に対するコンパクション動作では、磁壁メモリ３内の複数のブロックから、無効レイヤ率に基づいてソースブロックが選択される。例えば、無効レイヤ率が大きいブロックほど優先してソースブロックとして選択される。大きな無効レイヤ率（例えば最大の無効レイヤ率）を有する複数のブロックが存在する場合には、それら複数のブロックから、より深い有効レイヤ深さを有するブロックがソースブロックとして選択される。
【０１７３】
また、デスティネーションブロックは、無効レイヤ率が０であるフリーブロック、あるいはソースブロックに含まれるＶａｌｉｄ−ｄａｔａのサイズ以上のＶｏｉｄ領域を含むブロックである。つまり、デスティネーションブロックには、全てのレイヤがＶｏｉｄレイヤであるフリーブロック、またはソースブロックに含まれるＶａｌｉｄレイヤの数以上のＶｏｉｄレイヤを含むブロックが選択される。
【０１７４】
図１に示したように、メモリコントローラ２は、ＬＵＴ２３１、逆引きＬＵＴ２３２、ＶｏｉｄＣｎｔ２３３、およびＩｎＶａｌｉｄＣｎｔ２３４を管理する。ＬＵＴ２３１は、論理アドレスを物理アドレスに変換するために用いられる。例えば磁壁メモリ３に含まれる全てのブロックに対して、１つのＬＵＴ２３２が設けられる。
【０１７５】
逆引きＬＵＴ２３２は、物理アドレスを論理アドレスに変換するために用いられる。例えばブロック毎に、１つの逆引きＬＵＴ２３２が設けられる。
【０１７６】
ＶｏｉｄＣｎｔ２３３は、ブロック毎の書き込み余地を管理するために用いられる。ＩｎＶａｌｉｄＣｎｔ２３４は、ブロック毎の無効レイヤ率を管理するために用いられる。
【０１７７】
上述したように、各ブロックは複数のレイヤを含み、１つのブロック内の各ページは隣接する幾つかのレイヤの集合を含む。そして、磁壁メモリ３では、例えばページ単位で、データの書き込み、読み出し、および削除が行われる。
【０１７８】
したがって、あるページを構成するレイヤ群は、Ｖａｌｉｄレイヤ群、Ｉｎｖａｌｉｄレイヤ群、およびＶｏｉｄレイヤ群の少なくともいずれかであると云える。そのため、ブロック内のＶｏｉｄレイヤ群で構成されるページ（Ｖｏｉｄページ）をカウントしたＶｏｉｄＣｎｔ２３３を用いて、ブロックの書き込み余地を管理できる。同様に、ブロック内のＩｎｖａｌｉｄレイヤ群で構成されるページ（Ｉｎｖａｌｉｄページ）の数をカウントしたＩｎＶａｌｉｄＣｎｔ２３４を用いて、ブロックの無効レイヤ率を管理できる。つまり、書き込み余地および無効レイヤ率の代わりに、ページ単位のＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４をそれぞれ利用できる。
【０１７９】
＜書き込み余地および無効レイヤ率の管理方法＞  
（データ書き込み）  
図２２および図２３を参照して、データ書き込みに応じて管理される書き込み余地について説明する。以下では、説明を分かりやすくするために、磁壁メモリ３内の各ブロックが４つのページを含む場合について例示する。また、１つのブロックを構成する複数のＭＭＬ１０は全て同じ状態であると仮定する。
【０１８０】
図２２（Ａ）には、状態ＸにおけるブロックＢ０を構成するＭＭＬ１０と、状態ＸにおけるＬＵＴ２３１および逆引きＬＵＴ２３２との例が示されている。状態ＸにおけるブロックＢ０はフリーブロックである。フリーブロック内のレイヤは全てＶｏｉｄレイヤである。換言すると、フリーブロック内のページは全てＶｏｉｄ属性のページ（Ｖｏｉｄページ）である。そのため、ＶｏｉｄＣｎｔ２３３には、ブロックＢ０に書き込み可能なページ数が初期値として設定される。つまり、ＶｏｉｄＣｎｔ２３３には４が設定される。ＶｏｉｄＣｎｔ２３３は、ブロックＢ０へのページ単位の書き込みが行われる毎に、１だけ減算される。
【０１８１】
また、フリーブロックにはＩｎｖａｌｉｄレイヤ（あるいはＩｎｖａｌｉｄ−ｄａｔａのページ（Ｉｎｖａｌｉｄページ））が存在しないので、ＩｎＶａｌｉｄＣｎｔ２３４には０が設定される。このように、ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４には、ページ単位の数が設定され得る。
【０１８２】
図２２（Ｂ）は、このブロックＢ０のページＰ０に論理アドレスＬＣＡａのページデータＬＣＡａ＿ｄが書き込まれた場合の例を示す。この場合、ページＰ０はＶａｌｉｄ−ｄａｔａが格納されているページ（Ｖａｌｉｄページ）になり、ＬＵＴ２３２には、この論理アドレスＬＣＡａと、ページデータＬＣＡａ＿ｄが書き込まれた物理アドレスを表すブロック番号Ｂ０およびページ番号Ｐ０とを含むエントリが追加される。また、逆引きＬＵＴ２３２では、ブロックＢ０のページＰ０に対応する物理アドレス０に対して関連付けられるように、論理アドレスＬＣＡａが記録される。さらに、ページデータＬＣＡａ＿ｄが書き込まれたページＰ０の分だけ、ＶｏｉｄＣｎｔ２３３が減算される。つまり、ＶｏｉｄＣｎｔ２３３は４から１を引いた３になる。
【０１８３】
図２３のフローチャートは、メモリコントローラ２によって実行される書き込み処理の手順の例を示す。
【０１８４】
まず、メモリコントローラ２は、磁壁メモリ３内の書き込み先ブロックに１ページ分のページデータを書き込む（ステップＳ３１）。メモリコントローラ２は、書き込まれたページデータに対応する論理アドレスに、このページデータが格納された磁壁メモリ３内の記憶位置を示す物理アドレスがマッピングされるように、ＬＵＴ２３１を更新する（ステップＳ３２）。また、メモリコントローラ２は、書き込まれたページデータが格納された磁壁メモリ３内の記憶位置を示す物理アドレスに、このページデータに対応する論理アドレスがマッピングされるように、逆引きＬＵＴ２３２を更新する（ステップＳ３３）。そしてメモリコントローラ２は、１ページ分のページデータが書き込まれたことに基づき、ＶｏｉｄＣｎｔ２３３から１を減算する（ステップＳ３４）。
【０１８５】
以上により、磁壁メモリ３に対するデータ書き込みに応じて、ＬＵＴ２３１、逆引きＬＵＴ２３２、およびＶｏｉｄＣｎｔ２３３が更新される。
【０１８６】
なお以下では、説明を分かりやすくするために、あるブロックに対してページ単位のデータが書き込まれる毎に、ページ番号は１ずつ増加するものとする。例えば、ブロックＢ０内のページ番号Ｐ０のページ（すなわちページＰ０）に第０ページデータが書き込まれた後に、このブロックＢ０に第１ページデータがさらに書き込まれるならば、第１ページデータはページ番号Ｐ１のページ（すなわちページＰ１）に書き込まれる。
【０１８７】
また、あるブロックに含まれる複数のページ間の上位／下位は、ＭＭＬ１０に含まれる複数のレイヤ間の上位／下位と同様に、ブロック内の深さ方向の位置に基づき、より浅い位置にあるページを上位（上位ページ）と称し、より深い位置にあるページを下位（下位ページ）と称する。
【０１８８】
（データ削除）  
図２４から図２８を参照して、データ削除に応じて管理される書き込み余地および無効レイヤ率について説明する。磁壁メモリ３では、例えばページ単位でデータが削除される。磁壁メモリ３内のあるページのデータを削除するとは、そのデータに対応する論理アドレスを含むエントリ（アドレス情報とも称する）をＬＵＴ２３１から消去することに相当する。
【０１８９】
メモリコントローラ２は、ある論理アドレスのデータを磁壁メモリ３から削除することが要求された場合、この論理アドレスを含むエントリをＬＵＴ２３１から消去する。削除されたデータが格納されていた領域（すなわちページ）の属性は、Ｖａｌｉｄ−ｄａｔａから、（１）Ｉｎｖａｌｉｄ−ｄａｔａ、または（２）Ｖｏｉｄに変わる。
【０１９０】
図２４は、削除されたデータが格納されていたページＰ１の属性が、Ｖａｌｉｄ−ｄａｔａからＩｎｖａｌｉｄ−ｄａｔａに変わる例を示す。削除対象のページＰ１よりも下位にＶａｌｉｄページがあるならば、そのページＰ１の属性はＩｎｖａｌｉｄ−ｄａｔａになる。
【０１９１】
これに対して、図２５は、削除されたデータが格納されていたページＰ０の属性が、Ｖａｌｉｄ−ｄａｔａからＶｏｉｄに変わる例を示す。削除対象のページＰ０よりも下にＶａｌｉｄページがなければ、そのページＰ０の属性はＶｏｉｄになる。
【０１９２】
図２６は、削除されたデータが格納されていたページの属性がＩｎｖａｌｉｄ−ｄａｔａになった場合に、ＩｎＶａｌｉｄＣｎｔ２３４が更新される例を示す。図２６（Ａ）に示す状態Ａでは、複数のＭＭＬ１０で構成されるブロックＢ０において、ページＰ０、ページＰ１、およびページＰ２に、論理アドレスＬＣＡｃのデータＬＣＡｃ＿ｄ、論理アドレスＬＣＡｂのデータＬＣＡｂ＿ｄ、および論理アドレスＬＣＡａのデータＬＣＡａ＿ｄがそれぞれ格納されている。また、ブロックＢ０内の最も下のページはＶｏｉｄページである。ＬＵＴ２３１および逆引きＬＵＴ２３２には、この状態ＡのブロックＢ０に対応する論理アドレスと物理アドレスとのマッピング情報が含まれている。
【０１９３】
この状態ＡのブロックＢ０から論理アドレスＬＣＡｂのデータＬＣＡｂ＿ｄが削除される場合、図２６（Ｂ）に示すように、メモリコントローラ２は論理アドレスＬＣＡｂを含むエントリをＬＵＴ２３１から消去する。そして、メモリコントローラ２は、ブロックＢ０（すなわちブロックＢ０を構成するＭＭＬ１０）において、ページＰ１よりも下にＶａｌｉｄページがあるならば、ページＰ１の属性をＩｎｖａｌｉｄ−ｄａｔａに決定する。一方、メモリコントローラ２は、ページＰ１よりも下にＶａｌｉｄページがないならば、ページＰ１の属性をＶｏｉｄに決定する。
【０１９４】
より具体的には、メモリコントローラ２は、ＬＵＴ２３１に、ページ番号Ｐ１より小さな、ブロックＢ０内のページ番号を含むエントリがあるか否かを判定する。つまり、ＬＵＴ２３１に、削除されたデータＬＣＡｂ＿ｄよりも先にブロックＢ０に書き込まれたデータに対応するエントリがあるか否かが判定される。メモリコントローラ２は、ＬＵＴ２３１に、ページ番号Ｐ１より小さな、ブロックＢ０内のページ番号を含むエントリがあるならば、ページＰ１の属性をＩｎｖａｌｉｄ−ｄａｔａに決定する。一方、メモリコントローラ２は、ＬＵＴ２３１に、ページ番号Ｐ１より小さな、ブロックＢ０内のページ番号を含むエントリがないならば、ページＰ１の属性をＶｏｉｄに決定する。
【０１９５】
図２６（Ｂ）に示す例では、ページ番号Ｐ１より小さなページ番号である、ブロックＢ０内のページ番号Ｐ０を含むエントリが、ＬＵＴ２３１に含まれている。そのため、メモリコントローラ２は、ページＰ１の属性をＩｎｖａｌｉｄ−ｄａｔａに決定すると共に、ＩｎＶａｌｉｄＣｎｔ２３４に１を加算することにより、ＩｎＶａｌｉｄＣｎｔ２３４を０から１に更新する。なお、データが削除される場合には、メモリコントローラ２は、あるページの属性が、Ｉｎｖａｌｉｄ−ｄａｔａに変わるならば、逆引きＬＵＴ２３２を更新せず、Ｖｏｉｄに変わるならば、逆引きＬＵＴ２３２を更新する。図２６（Ｂ）に示す例では、削除されたページＰ１の属性がＩｎｖａｌｉｄ−ｄａｔａに変わるので、逆引きＬＵＴ２３２は更新されない。
【０１９６】
図２７は、削除されたデータが格納されていたページの属性がＶｏｉｄになった場合に、ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４が更新される例を示す。
【０１９７】
図２７（Ａ）に示す状態Ｂでは、複数のＭＭＬ１０で構成されるブロックＢ０において、ページＰ１に論理アドレスＬＣＡｂのデータＬＣＡｂ＿ｄが格納されている。ページＰ０はＶｏｉｄページであり、ページＰ２はＩｎｖａｌｉｄページである。また、ブロックＢ０内の最も下のページはＶｏｉｄページである。したがって、状態ＢのブロックＢ０に対応するＶｏｉｄＣｎｔ２３３として２が設定され、ＩｎＶａｌｉｄＣｎｔ２３４として１が設定されている。
【０１９８】
ＬＵＴ２３１および逆引きＬＵＴ２３２には、この状態ＢのブロックＢ０に対応する論理アドレスと物理アドレスとのマッピング情報が含まれている。
【０１９９】
この状態ＢのブロックＢ０から論理アドレスＬＣＡｂのデータＬＣＡｂ＿ｄが削除される場合、図２７（Ｂ）に示すように、メモリコントローラ２は論理アドレスＬＣＡｂを含むエントリをＬＵＴ２３２から消去する。そして、メモリコントローラ２は、データＬＣＡｂ＿ｄが格納されていたページＰ１の属性を、Ｉｎｖａｌｉｄ−ｄａｔａとＶｏｉｄのいずれかに決定する。メモリコントローラ２は、ページ番号Ｐ１より小さなページ番号である、ブロックＢ０内のページ番号を含むエントリが、ＬＵＴ２３１に含まれていないので、ページＰ１の属性をＶｏｉｄに決定すると共に、ＶｏｉｄＣｎｔ２３３に１を加算することにより、ＶｏｉｄＣｎｔ２３３を２から３に更新する。上述した通り、メモリコントローラ２は、あるページの属性が、Ｉｎｖａｌｉｄ−ｄａｔａに変わるならば、逆引きＬＵＴ２３２を更新せず、Ｖｏｉｄに変わるならば、逆引きＬＵＴ２３２を更新する。図２７（Ｂ）に示す例では、ページＰ１の属性がＶｏｉｄに変わるので、メモリコントローラ２は逆引きＬＵＴ２３２を更新する。より具体的には、メモリコントローラ２は、逆引きＬＵＴ２３２において、ページＰ１に関連付けられている論理アドレスＬＣＡｂを消去する。
【０２００】
あるページの属性がＶｏｉｄに変わった場合、メモリコントローラ２は、当該ページから連続する１つ以上の上位ページ（すなわち当該ページに隣接する１つ以上の上位ページ）がＶｏｉｄページに変わるか否かを判定する。より詳しくは、１つ以上の上位ページがＩｎｖａｌｉｄページである場合、メモリコントローラ２は、それら１つ以上の上位ページの属性がＩｎｖａｌｉｄ−ｄａｔａからＶｏｉｄに変わると判断する。一方、１つ以上の上位ページがＩｎｖａｌｉｄページでない場合、すなわち１つ以上の上位ページがＶａｌｉｄページである場合、メモリコントローラ２は、それら１つ以上の上位ページの属性が変わらないと判断する。
【０２０１】
図２７（Ｂ）に示す例では、ページＰ１の属性がＶｏｉｄに変わった場合、メモリコントローラ２は、ページＰ１から連続する上位のページＰ２がＶｏｉｄページに変わるか否かを判定する。より具体的には、メモリコントローラ２は、ブロックＢ０内の、ページ番号Ｐ１より１つ大きいページ番号Ｐ２を含むエントリがＬＵＴ２３１に存在するか否かを判定する。ブロックＢ０内の、ページ番号Ｐ１より１つ大きいページ番号Ｐ２を含むエントリがＬＵＴ２３１に存在しない場合、ページＰ２はＩｎｖａｌｉｄページであるので、メモリコントローラ２は、ページＰ２の属性がＩｎｖａｌｉｄ−ｄａｔａからＶｏｉｄに変わると判断する。一方、ブロックＢ０内の、ページ番号Ｐ１より１つ大きいページ番号Ｐ２を含むエントリがＬＵＴ２３１に存在する場合、ページＰ２はＶａｌｉｄページであるので、メモリコントローラ２は、ページＰ２の属性が変わらないと判断する。
【０２０２】
図２７（Ｂ）に示すように、ＬＵＴ２３１には、ブロックＢ０内の、ページ番号Ｐ１より１つ大きいページ番号Ｐ２を含むエントリが存在しないので、メモリコントローラ２は、ページＰ２の属性をＶｏｉｄに決定すると共に、ＶｏｉｄＣｎｔ２３３に１を加算することによって３から４に更新し、またＩｎＶａｌｉｄＣｎｔ２３４から１を減算することによって１から０に更新する。また、ページＰ２の属性がＶｏｉｄに変わるので、メモリコントローラ２は、逆引きＬＵＴ２３２において、ページＰ２に関連付けられている論理アドレスＬＣＡａを消去する。
【０２０３】
ページＰ２の属性がＶｏｉｄに変わった場合に、もしページＰ２から連続した上位のページがあるならば、上述したページＰ２に対する方法と同様にして、その上位のページがＶｏｉｄページに変わるか否かが判定される。この判定は、属性がＶｏｉｄに変わったページよりも上のページがブロックＢ０に存在しないか、あるいは属性がＶｏｉｄに変わったページの１つ上のページがＶａｌｉｄページであると判断されるまで、繰り返し行われる。メモリコントローラ２は、この判定により、あるページがＶｏｉｄページに変わると判断した場合、逆引きＬＵＴ２３２において、当該ページに関連付けられている論理アドレスを消去する。
【０２０４】
図２８のフローチャートを参照して、ブロック内の１つのページが削除された場合に実行される、ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４の更新処理の手順の例を説明する。ここでは、説明を分かりやすくするために、ページが削除されたブロックがブロックＢ０である場合を例示する。
【０２０５】
まず、メモリコントローラ２は、対象ページ番号Ｐに、削除されたページのページ番号を設定する（ステップＳ４０１）。そして、メモリコントローラ２は、ページが削除されたブロックＢ０に対応する逆引きＬＵＴ２３２に、対象ページ番号Ｐよりも小さいページ番号を含むエントリがあるか否かを判定する（ステップＳ４０２）。つまり、メモリコントローラ２は、削除されたページよりも下位にＶａｌｉｄページがあるか否かを判定するための候補の有無を判定する。
【０２０６】
逆引きＬＵＴ２３２に、対象ページ番号Ｐよりも小さいページ番号を含むエントリ（以下、エントリＡと称する）がある場合（ステップＳ４０２のＹＥＳ）、メモリコントローラ２は、逆引きＬＵＴ２３２から得られたエントリＡとＬＵＴ２３１とに整合性があるか否かを判定する（ステップＳ４０３）。つまり、その対象ページ番号Ｐよりも小さいページ番号のページがＶａｌｉｄページであるか否かが判定される。上述した通り、データが削除される場合、当該データの論理アドレスを含むエントリがＬＵＴ２３１から消去される。また、そのページの属性がＩｎｖａｌｉｄ−ｄａｔａに変わった場合には逆引きＬＵＴ２３２は更新されないが、Ｖｏｉｄに変わった場合には当該ページに関連付けられた論理アドレスを削除するように、逆引きＬＵＴ２３２が更新される。
【０２０７】
メモリコントローラ２は、このようなＬＵＴ２３１と逆引きＬＵＴ２３２とを用いて、逆引きＬＵＴ２３２のエントリＡによって示される情報が、ＬＵＴ２３１に示される最新の情報との整合性を有しているかを確認する。逆引きＬＵＴ２３２のエントリＡによって示される情報と、ＬＵＴ２３１に示される最新の情報とが一致している場合、エントリＡとＬＵＴ２３１とに整合性があると云える。一方、逆引きＬＵＴ２３２のエントリＡによって示される情報と、ＬＵＴ２３１に示される最新の情報とが一致していない場合、エントリＡとＬＵＴ２３１とに整合性がないと云える。
【０２０８】
より具体的には、メモリコントローラ２は、エントリＡ（すなわち、逆引きＬＵＴ２３２において、対象ページ番号Ｐよりも小さいページ番号を含むエントリ）に含まれる論理アドレスを用いて、ＬＵＴ２３１から、この論理アドレスを含むエントリ（以下、エントリＢと称する）を取得する。そして、メモリコントローラ２は、エントリＡによって示されるブロックおよびページが、エントリＢによって示されるブロックおよびページと一致するか否かを判定する。逆引きＬＵＴ２３２から得られたエントリＡは、ブロックＢ０内の１つのページのページ番号を示す。また、ＬＵＴ２３１から得られたエントリＢは、ブロック番号とページ番号とを示す。
【０２０９】
メモリコントローラ２は、例えば、エントリＢに示されるブロック番号がＢ０であり、且つエントリＡによって示されるページ番号とエントリＢによって示されるページ番号とが一致する場合に、エントリＡによって示されるブロックおよびページが、エントリＢによって示されるブロックおよびページと一致すると判断する。この場合、メモリコントローラ２は、逆引きＬＵＴ２３２のエントリＡとＬＵＴ２３１とに整合性があると判断する。
【０２１０】
一方、エントリＢに示されるブロック番号がＢ０でない場合、あるいはエントリＢに示されるブロック番号がＢ０であっても、エントリＡによって示されるページ番号がエントリＢによって示されるページ番号とは異なる場合、メモリコントローラ２は、エントリＡによって示されるブロックおよびページが、エントリＢによって示されるブロックおよびページと一致しないと判断する。この場合、メモリコントローラ２は、逆引きＬＵＴ２３２のエントリＡとＬＵＴ２３１とに整合性がないと判断する。
【０２１１】
逆引きＬＵＴ２３２のエントリＡとＬＵＴ２３１とに整合性があるならば（ステップＳ４０３のＹＥＳ）、削除されたページがＶａｌｉｄページからＩｎｖａｌｉｄページに変わるので、メモリコントローラ２はＩｎＶａｌｉｄＣｎｔ２３４に１を加算し（ステップＳ４０４）、処理を終了する。
【０２１２】
一方、逆引きＬＵＴ２３２に、対象ページ番号Ｐよりも小さいページ番号を含むエントリがない場合（ステップＳ４０２のＮＯ）、あるいは、逆引きＬＵＴ２３２に、対象ページ番号Ｐよりも小さいページ番号を含むエントリＡがあるものの（ステップＳ４０２のＹＥＳ）、エントリＡとＬＵＴ２３１とに整合性がない場合（ステップＳ４０３のＮＯ）、削除されたページがＶａｌｉｄページからＶｏｉｄページに変わるので、メモリコントローラ２はＶｏｉｄＣｎｔ２３３に１を加算する（ステップＳ４０５）。また、逆引きＬＵＴ２３２において、削除されたページに関連付けられた論理アドレスは消去される。
【０２１３】
次いで、メモリコントローラ２は対象ページ番号Ｐに１を加算する（ステップＳ４０６）。そして、メモリコントローラ２は、逆引きＬＵＴ２３２に対象ページ番号Ｐを含むエントリが存在するか否かを判定する（ステップＳ４０７）。つまり、属性がＶｏｉｄに変わったページ（Ｐ−１）の上位ページが存在するか否かが判定される。例えば、対象ページ番号Ｐが、逆引きＬＵＴ２３２において論理アドレスに関連付けられている最大のページ番号以下である場合に、あるいは対象ページ番号Ｐがブロックに含まれるページ数以下である場合に、対象ページ番号Ｐのページは存在する可能性がある。逆引きＬＵＴ２３２に対象ページ番号Ｐを含むエントリが存在しない場合（ステップＳ４０７のＮＯ）、処理を終了する。
【０２１４】
逆引きＬＵＴ２３２に対象ページ番号Ｐを含むエントリ（以下、エントリＣと称する）が存在する場合（ステップＳ４０７のＹＥＳ）、メモリコントローラ２は、逆引きＬＵＴ２３２から得られたエントリＣとＬＵＴ２３１に整合性があるか否かを判定する（ステップＳ４０８）。つまり、対象ページ番号ＰのページがＶａｌｉｄページであるか否かが判定される。
【０２１５】
より具体的には、ステップＳ４０３と同様に、メモリコントローラ２は、エントリＣに含まれる論理アドレスを用いて、ＬＵＴ２３１から、この論理アドレスを含むエントリ（以下、エントリＤと称する）を取得する。そして、メモリコントローラ２は、エントリＣによって示されるブロックおよびページが、エントリＤによって示されるブロックおよびページと一致するか否かを判定する。逆引きＬＵＴ２３２から得られたエントリＣは、ブロックＢ０内の１つのページのページ番号を示す。また、ＬＵＴ２３１から得られたエントリＤは、ブロック番号とページ番号とを示す。
【０２１６】
メモリコントローラ２は、例えば、エントリＤに示されるブロック番号がＢ０であり、且つエントリＣによって示されるページ番号とエントリＤによって示されるページ番号とが一致する場合に、エントリＣによって示されるブロックおよびページが、エントリＤによって示されるブロックおよびページと一致すると判断する。この場合、メモリコントローラ２は、逆引きＬＵＴ２３２のエントリＣとＬＵＴ２３１とに整合性があると判断する。
【０２１７】
一方、エントリＤに示されるブロック番号がＢ０でない場合、あるいはエントリＤに示されるブロック番号がＢ０であっても、エントリＣによって示されるページ番号がエントリＤによって示されるページ番号とは異なる場合、メモリコントローラ２は、エントリＣによって示されるブロックおよびページが、エントリＤによって示されるブロックおよびページと一致しないと判断する。この場合、メモリコントローラ２は、逆引きＬＵＴ２３２のエントリＣとＬＵＴ２３１とに整合性がないと判断する。
【０２１８】
逆引きＬＵＴ２３２のエントリＣ（すなわち逆引きＬＵＴ２３２において対象ページ番号Ｐを含むエントリ）とＬＵＴ２３１とに整合性がある場合（ステップＳ４０８のＹＥＳ）、処理を終了する。
【０２１９】
一方、逆引きＬＵＴ２３２に対象ページ番号Ｐを含むエントリＣが存在するものの（ステップＳ４０７のＹＥＳ）、このエントリＣとＬＵＴ２３１とに整合性がない場合（ステップＳ４０８のＮＯ）、対象ページ番号ＰのページがＩｎｖａｌｉｄページであって、Ｖｏｉｄ属性に変わるので、メモリコントローラ２は、ＩｎＶａｌｉｄＣｎｔ２３４から１を減算し（ステップＳ４０９）、ＶｏｉｄＣｎｔ２３３に１を加算し（ステップＳ４１０）、ステップＳ４０６に戻る。ステップＳ４０６に戻ることにより、ブロック内にさらに上位のページ（ページ（Ｐ＋１））が存在し、Ｖｏｉｄ属性に変わるか否かが判定される。なお、逆引きＬＵＴ２３２において、Ｖｏｉｄ属性に変わったページ（すなわち対象ページ番号Ｐのページ）に関連付けられた論理アドレスは消去される。
【０２２０】
以上により、ブロック内の１つのページが削除された場合に、ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４が更新される。
【０２２１】
上述した例では、あるブロックに対してページ単位のデータが書き込まれる毎に、ページ番号を１ずつ増加させる規則が用いられる場合について説明した。この規則が用いられる場合には、逆引きＬＵＴ２３２及びＬＵＴ２３１に記録されているエントリ内のページ番号に基づいて、あるブロック内のあるページの上下に、Ｖａｌｉｄ−ｄａｔａの属性を有するページ（Ｖａｌｉｄページ）が存在するか否かが容易に判断できる。例えば、削除されたページがＩｎｖａｌｉｄ−ｄａｔａとＶｏｉｄのいずれの属性に変わるかを、逆引きＬＵＴ２３２及びＬＵＴ２３１を用いて、そのページの下にＶａｌｉｄページがあるか否かを確認するのみで判断できる。しかしながら、上述したような判断が可能であるならば、この規則に限らず、ブロック、ページ、レイヤ等を管理するためのいずれの規則が用いられてもよい。
【０２２２】
以上のような管理方法により、データの書き込みおよび削除に応じて、ブロック毎にＶｏｉｄＣｎｔ２３３、ＩｎＶａｌｉｄＣｎｔ２３４、有効レイヤ深さ等のパラメータが更新できる。なお、ブロック毎の書き込み余地および無効レイヤ率は、ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４とそれぞれ比例関係にある。そのため、書き込み余地および無効レイヤ率として、ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４をそれぞれ代用できる。さらに、有効レイヤ深さの代わりに、最深のＶａｌｉｄページの深さを示す有効ページ深さが用いられてもよいし、Ｔｏｔａｌレイヤ深さの代わりに、ブロックのページ数が用いられてもよい。
【０２２３】
（コンパクション）  
メモリコントローラ２は、コンパクション動作によって磁壁メモリ３の書き込み余地を効率的に増やすことができるように、コンパクションのソースブロックとデスティネーションブロックとを選択する。
【０２２４】
（ソースブロックの選択）  
メモリコントローラ２は、磁壁メモリ３内の複数のブロックから、例えば無効レイヤ率が大きいブロックを優先して、ソースブロックとして選択する。また、メモリコントローラ２は、無効レイヤ率が等しいブロック間では、有効レイヤ深さが深いブロックを優先して、ソースブロックとして選択する。
【０２２５】
図２９を参照して、コンパクションのソースブロックが選択される例を説明する。ここでは、磁壁メモリ３内の５つのブロックＢ１〜Ｂ５から１つのソースブロックが選択される場合を例示する。各ブロックのページ数は８である。ＶｏｉｄＣｎｔ２３３およびＩｎＶａｌｉｄＣｎｔ２３４の算出方法は、上述した通りである。
【０２２６】
無効レイヤ率は、ＩｎＶａｌｉｄＣｎｔ２３４をブロックのページ数である８で除算することにより得られる。無効レイヤ率として、ＩｎＶａｌｉｄＣｎｔ２３４がそのまま用いられてもよい。また、有効レイヤ深さとして、ブロックのページ数である８から、ＶｏｉｄＣｎｔ２３３を減算することにより得られる有効ページ深さが用いられる。
【０２２７】
ブロックＢ１〜Ｂ５の内、無効レイヤ率が最大であるブロックは、無効レイヤ率が５０％であるブロックＢ４である。そのため、メモリコントローラ２はブロックＢ４をソースブロックとして選択する。ブロックＢ４をソースブロックとしてコンパクションが行われる場合、ブロックＢ４内のＶａｌｉｄページに相当する領域のデータのみがデスティネーションブロックにコピーされる。コンパクションにより、ブロックＢ４内のＩｎｖａｌｉｄページに相当する領域が再び利用できるようになるので、ソースブロックとして選択されるブロックの無効レイヤ率（すなわちブロック内のＩｎｖａｌｉｄ−ｄａｔａの領域）が大きいほど、一度のコンパクションで増加する書き込み可能領域（書き込み余地）をより大きくできる。
【０２２８】
もしブロックＢ４を除いたブロックＢ１，Ｂ２，Ｂ３，Ｂ５の中からソースブロックが選択されるならば、無効レイヤ率が最大であるブロックは、無効レイヤ率が２５％であるブロックＢ２およびブロックＢ３である。この場合、メモリコントローラ２はソースブロックの候補として、ブロックＢ２とブロックＢ３とを選択する。
【０２２９】
最大の無効レイヤ率を有する複数のブロックが存在する場合には、メモリコントローラ２は、例えば、有効レイヤ深さがより深いブロックを優先してソースブロックとして選択する。メモリコントローラ２は、ブロックＢ２の有効レイヤ深さが６であり、ブロックＢ３の有効レイヤ深さが８であるので、より深い有効レイヤ深さを有するブロックＢ３をソースブロックとして選択する。
【０２３０】
有効レイヤ深さがより深いブロックを優先してソースブロックとして選択することにより、書き込み余地がより小さいブロックを優先的にソースブロックとして選択できる。つまり、有効レイヤ深さがより深いブロックを選択することは、書き込み余地（あるいはＶｏｉｄＣｎｔ２３３）がより小さいブロックを選択することに相当する。
【０２３１】
（デスティネーションブロックの選択）  
メモリコントローラ２は、下記の２つのブロックのいずれかをデスティネーションブロックとして選択する。  
（１）Ｉｎｖａｌｉｄ−ｄａｔａの領域を含まず、且つソースブロック内のＶａｌｉｄ−ｄａｔａの領域のサイズ以上のＶｏｉｄ領域（すなわちソースブロック内のＶａｌｉｄレイヤの数以上のＶｏｉｄレイヤ）を含むブロック
（２）フリーブロック
メモリコントローラ２は、ソースブロック内の１つ以上のＶａｌｉｄレイヤにそれぞれ格納されているデータを、デスティネーションブロックに書き込むコンパクション動作を行う。（１）および（２）のいずれがデスティネーションブロックとして選択された場合にも、デスティネーションブロックはＩｎｖａｌｉｄ−ｄａｔａの領域を含んでいないので、コンパクション動作後に磁壁メモリ３内の書き込み可能領域（書き込み余地）が増加する。さらに、（２）のフリーブロックが選択される場合には、ソースブロック内のデータがフリーブロックに書き直されることによって、メモリセルに書き込まれてから時間が経過したことによるデータ記憶劣化を防止するリフレッシュ効果がある。
【０２３２】
なお、ある１つのソースブロック内のデータは、複数のデスティネーションブロックにコピーされてもよい。その場合、例えば、２つのブロック内のＶｏｉｄ領域のサイズ（あるいはＶｏｉｄレイヤの数）の合計が、ソースブロック内のＶａｌｉｄ−ｄａｔａの領域のサイズ（あるいはＶａｌｉｄレイヤの数）以上であれば、それら２つのブロックがデスティネーションブロックとして選択され得る。
【０２３３】
メモリコントローラ２は、上記のように選択されたソースブロックとデスティネーションブロックとを用いてコンパクション動作を行う。その際、デスティネーションブロックのＬＵＴ２３１、逆引きＬＵＴ２３２、ＶｏｉｄＣｎｔ２３３、およびＩｎＶａｌｉｄＣｎｔ２３４は、ソースブロック内のＶａｌｉｄ−ｄａｔａがデスティネーションブロックに書き込まれたことに応じてそれぞれ更新される。ソースブロック内の全てのＶａｌｉｄ−ｄａｔａがデスティネーションブロックにコピーされた（書き込まれた）ならば、ソースブロックはフリーブロックになる。
【０２３４】
なお、ソースブロックから読み出されたＶａｌｉｄ−ｄａｔａにエラーが発生しているならば、誤り訂正処理によりそのエラーが訂正されたＶａｌｉｄ−ｄａｔａがデスティネーションブロックに書き込まれる。つまり、コンパクション処理と並行して誤り訂正処理が行われてもよい。
【０２３５】
＜余裕率を考慮したソースブロックの選択＞  
余裕率（オーバープロビジョニング）をＸ％持つ記憶装置とは、表示される記憶容量（表示容量）に加えて、Ｘ％の記憶容量（余裕容量）を持つ記憶装置を意味する。つまり、表記容量と物理容量（実装容量）との差を余裕容量、表記容量に対する余裕容量の比率を余裕率と呼ぶ。
【０２３６】
記憶装置にデータを書き込む際にワーストとなる利用状態は、図３０に示すように、記憶装置に含まれるブロック全てがＸ％の余裕率に相当する無効レイヤ率を有する状態である。上述した磁壁メモリ３に対するコンパクションのソースブロックを選択する方法では、使用されている記憶容量が増加するにつれて多数のブロック候補からソースブロック（あるいはソースブロック候補）を選択する必要がある。ブロック候補は、例えば、磁壁メモリ３に含まれる複数のブロックの内、フリーブロックを除いたブロックである。ブロック候補間の無効レイヤ率や有効レイヤ深さを比較するための処理の処理量は、使用されている記憶容量（使用容量）が増加するほど増大する可能性があり、ソースブロックを選択するために要する時間が長くなる。
【０２３７】
このような場合、ソースブロックを選択するために要する時間を短縮するために（すなわちソースブロックの選択速度を上げるために）、メモリコントローラ２は余裕率と使用容量とを考慮してソースブロックを選択してもよい。例えば、使用容量が特定の閾値を超えた場合、あるいは、表記容量または物理容量に対する使用容量の割合が特定の閾値を超えた場合、メモリコントローラ２は、無効レイヤ率が余裕率以上であるブロック（より詳しくは無効レイヤ率が余裕率以上であるＭＭＬ１０を含むブロック）をソースブロックとして選択する。あるいは、ＭＭＬ１０に含まれる全レイヤに対するＩｎｖａｌｉｄレイヤおよびＶｏｉｄレイヤの割合が余裕率以上であるＭＭＬ１０を含むブロック（より詳しくは全レイヤに対するＩｎｖａｌｉｄレイヤおよびＶｏｉｄレイヤの割合が余裕率以上であるＭＭＬ１０を含むブロック）が、ソースブロックとして選択されてもよい。
【０２３８】
＜リード動作によるセルフコンパクション＞  
ＭＭＬ１０の最上位レイヤがＩｎｖａｌｉｄレイヤである場合、そのＩｎｖａｌｉｄレイヤからデータを読み出すリード動作のみによるコンパクションで、ＭＭＬ１０の書き込み余地を増やすことができる。
【０２３９】
図３１は、最上位レイヤがＩｎｖａｌｉｄレイヤであるＭＭＬ１０に対して、リード動作のみによるコンパクションが行われる例を示す。メモリコントローラ２は、最上位レイヤから連続する１つ以上のＩｎｖａｌｉｄレイヤ６６１を含むＭＭＬ１０に対して、その１つ以上のＩｎｖａｌｉｄレイヤ６６１の分、リード動作を行う。このリード動作によって、ＭＭＬ１０内のＶａｌｉｄレイヤ群６６２は最上位レイヤを先頭とする領域に位置するようにシフトする。Ｖａｌｉｄレイヤ群６６２は最上位レイヤを先頭とする領域に位置するようにシフトすることを、Ｖａｌｉｄレイヤ群６６２を頭出しするとも称する。
【０２４０】
また、シフトしたＶａｌｉｄレイヤ群６６２の下位にあるレイヤ群は、Ｖｏｉｄレイヤ群６６３である。したがって、リード動作のみによるコンパクションで、このＶｏｉｄレイヤ群６６３に相当する書き込み余地が増加する。なお、このリード動作によって読み出されたデータ（Ｉｎｖａｌｉｄ−ｄａｔａ）は、データバスに送出されず、破棄される。そのため、データバスを利用することなく、書き込み余地を増やすことができる。データをデータバスに送出しない読み出しは、自己リードとも称される。
【０２４１】
より具体的な例として、図３２および図３３を参照して、ブロック内の最上位ページがＩｎｖａｌｉｄページであるソースブロックに対して、コンパクションが行われる場合について説明する。メモリコントローラ２は、磁壁メモリ３内の複数のブロックから、最上位のレイヤから連続する１つ以上のレイヤがそれぞれＩｎｖａｌｉｄレイヤであるＭＭＬ１０で構成されるブロックを、すなわち最上位ページから連続する１つ以上のページがそれぞれＩｎｖａｌｉｄページであるブロックを選択し、このブロックに対して、それら１つ以上のレイヤ（ページ）を読み出すためのリード動作を行う。
【０２４２】
図３２（Ａ）に示す例では、ソースブロックは、論理アドレスＬＣＡｄのデータＬＣＡｄ＿ｄ、論理アドレスＬＣＡｃのデータＬＣＡｃ＿ｄ、論理アドレスＬＣＡｂのデータＬＣＡｂ＿ｄ、および論理アドレスＬＣＡａのデータＬＣＡａ＿ｄがそれぞれ格納されたＶａｌｉｄページＰ０，Ｐ１，Ｐ２，Ｐ３で構成されている。このソースブロックにおいて、ＩｎＶａｌｉｄＣｎｔ２３４は０であり、ＶｏｉｄＣｎｔ２３３は０であり、有効レイヤ深さは４であり、書き込み余地は０（＝０％）である。
【０２４３】
このソースブロックの最上位ページＰ３に格納されたデータＬＣＡａ＿ｄの削除が要求された場合、図３２（Ｂ）に示すように、データＬＣＡａ＿ｄの論理アドレスＬＣＡａを含むエントリがＬＵＴ２３１から消去される。これに応じて、最上位ページＰ３がＶａｌｉｄページからＩｎｖａｌｉｄページに変わり、ＩｎＶａｌｉｄＣｎｔ２３４は１が加算されることにより０から１に増加する。
【０２４４】
メモリコントローラ２は、ＩｎＶａｌｉｄＣｎｔ２３４が増加した場合、その増加した分に対応する回数だけ、ソースブロックに対するページ単位のリード動作を行う。ここでは、メモリコントローラ２はソースブロックに対して１回のリード動作（すなわち１ページ分のリード動作）を行う。つまり、メモリコントローラ２は最上位のＩｎｖａｌｉｄページを読み出すためのリード動作を行う。
【０２４５】
これにより、図３２（Ｃ）に示すように、最上位のＩｎｖａｌｉｄページがソースブロックからなくなると共に、３つのＶａｌｉｄページがそれぞれ１つだけ上位の位置にシフトされる。したがって、ソースブロックにおいてＶａｌｉｄページが頭出しされる。
【０２４６】
シフトしたＶａｌｉｄページの下位にあるページは、Ｖｏｉｄページになる。したがって、リード動作のみによるコンパクションで、１ページのＶｏｉｄページが新たに作成され、このＶｏｉｄページに相当する書き込み余地が増加する。また、ＩｎＶａｌｉｄＣｎｔ２３４は１が減算されることにより１から０に減少し、ＶｏｉｄＣｎｔ２３３は１が加算されることにより０から１に増加する。また、４であった有効レイヤ深さは１減少して３になり、０（＝０％）であった書き込み余地は１増加して１（＝２５％）になる。
【０２４７】
このように、ＩｎＶａｌｉｄＣｎｔ２３４の増分に対応する回数だけリード動作が行われることにより、ソースブロックからＩｎｖａｌｉｄページである最上位ページをなくし、書き込み余地を増やすことができる。
【０２４８】
また図３３（Ａ）に示す例では、ソースブロックは、論理アドレスＬＣＡｃのデータＬＣＡｃ＿ｄおよび論理アドレスＬＣＡａのデータＬＣＡａ＿ｄがそれぞれ格納されたＶａｌｉｄページＰ０，Ｐ２と、データＬＣＡｂ＿ｄが格納されたＩｎｖａｌｉｄページＰ１と、最下位のＶｏｉｄページとで構成されている。このソースブロックにおいて、ＩｎＶａｌｉｄＣｎｔ２３４は１であり、ＶｏｉｄＣｎｔ２３３は１であり、有効レイヤ深さは３であり、書き込み余地は１（＝２５％）である。
【０２４９】
このソースブロックの最上位ページＰ２に格納されたデータＬＣＡａ＿ｄの削除が要求された場合、図３３（Ｂ）に示すように、データＬＣＡａ＿ｄの論理アドレスＬＣＡａを含むエントリがＬＵＴ２３１から消去される。これに応じて、最上位ページＰ２がＶａｌｉｄページからＩｎｖａｌｉｄページに変わり、ＩｎＶａｌｉｄＣｎｔ２３４は１が加算されることにより１から２に増加する。
【０２５０】
メモリコントローラ２は、ＩｎＶａｌｉｄＣｎｔ２３４が増加した場合、その増加した分に対応する回数だけ、ソースブロックに対するページ単位のリード動作を行う。ここでは、メモリコントローラ２はソースブロックに対して１回のリード動作を行う。つまり、メモリコントローラ２は最上位のＩｎｖａｌｉｄページＰ２を読み出すためのリード動作を行う。これにより、図３３（Ｃ）に示すように、データＬＣＡｂ＿ｄが格納されているＩｎｖａｌｉｄページＰ１とデータＬＣＡｃ＿ｄが格納されているＶａｌｉｄページＰ０とが、図３３（Ｂ）に示した位置からそれぞれ１つだけ上位の位置にシフトされる。またメモリコントローラ２は、逆引きＬＵＴ２３２において、リードされたＩｎｖａｌｉｄページＰ２に関連付けられている論理アドレスＬＣＡａを消去する。
【０２５１】
シフトしたＶａｌｉｄページＰ０よりも下位にあるページは、Ｖｏｉｄページになる。したがって、リード動作のみによるコンパクションで、１ページのＶｏｉｄページが新たに作成され、このＶｏｉｄページに相当する書き込み余地が増加する。ＩｎＶａｌｉｄＣｎｔ２３４は１が減算されることにより２から１に減少し、ＶｏｉｄＣｎｔ２３３は１が加算されることにより１から２に増加する。また、３であった有効レイヤ深さは１減少して２になり、１（＝２５％）であった書き込み余地は１増加して２（＝５０％）になる。
【０２５２】
次いで、メモリコントローラ２は、逆引きＬＵＴ２３２とＬＵＴ２３１とを参照して、最上位ページがＩｎｖａｌｉｄページであるか否かを判定する。より具体的には、メモリコントローラ２は、逆引きＬＵＴ２３２において論理アドレスが関連付けられているページの内の最上位ページを特定し、その特定されたページに関連付けられた論理アドレスを取得する。そして、メモリコントローラ２は、ＬＵＴ２３１に、取得された論理アドレスを含むエントリがあるか否かを判定する。取得された論理アドレスを含むエントリがＬＵＴ２３１に存在しないならば、メモリコントローラ２はソースブロックに対して１回のリード動作を行う。取得された論理アドレスを含むエントリがＬＵＴ２３１に存在するならば、リード動作は行われない。
【０２５３】
図３３（Ｃ）に示す逆引きＬＵＴ２３２では、論理アドレスＬＣＡｂが関連付けられたページＰ１が特定され、論理アドレスＬＣＡｂが取得される。そして、論理アドレスＬＣＡｂを含むエントリがＬＵＴ２３１に存在しないので、ソースブロックに対する１回のリード動作が行われる。つまり、最上位のＩｎｖａｌｉｄページＰ１を読み出すためのリード動作が行われる。
【０２５４】
その結果、図３３（Ｄ）に示すように、最上位のＩｎｖａｌｉｄページＰ１がソースブロックからなくなると共に、ＶａｌｉｄページＰ０が１つだけ上位の位置にシフトされる。したがって、ソースブロックにおいてＶａｌｉｄページが頭出しされる。またメモリコントローラ２は、逆引きＬＵＴ２３２において、リードされたＩｎｖａｌｉｄページＰ１に関連付けられている論理アドレスＬＣＡｂを消去する。
【０２５５】
シフトしたＶａｌｉｄページＰ０の下位にあるページは、Ｖｏｉｄページになる。したがって、リード動作のみによるコンパクションで、１ページのＶｏｉｄページが新たに作成され、このＶｏｉｄページに相当する書き込み余地が増加する。ＩｎＶａｌｉｄＣｎｔ２３４は１が減算されることにより１から０に減少し、ＶｏｉｄＣｎｔ２３３は１が加算されることにより２から３に増加する。また、２であった有効レイヤ深さは１減少して１になり、２（＝５０％）であった書き込み余地は１増加して３（＝７５％）になる。
【０２５６】
このように、ＩｎＶａｌｉｄＣｎｔ２３４の増分に対応する回数だけリード動作が行われた後、このリード動作に応じてＩｎｖａｌｉｄページが最上位ページとなったならば、さらにリード動作が行われ。これにより、ソースブロックからＩｎｖａｌｉｄページである最上位ページをなくし、書き込み余地を増やすことができる。
【０２５７】
図３４のフローチャートは、リード動作のみによるセルフコンパクション処理の手順の例を示す。ここでは、１つの対象ブロック（ソースブロック）に対してセルフコンパクション処理が行われることを想定する。セルフコンパクション処理では、ソースブロックを管理するための逆引きＬＵＴ２３２と、磁壁メモリ３内の全てのブロックを管理するためのＬＵＴ２３１とが用いられ得る。
【０２５８】
まず、メモリコントローラ２は、ソースブロックに対応する逆引きＬＵＴ２３２において、論理アドレスが関連付けられているページ内の最上位ページを特定し、特定されたページに関連付けられた論理アドレスを取得する（ステップＳ５１）。そして、メモリコントローラ２は、ＬＵＴ２３１に、取得された論理アドレスを含むエントリが存在するか否かを判定する（ステップＳ５２）。ＬＵＴ２３１に、取得された論理アドレスを含むエントリが存在する場合（ステップＳ５２のＹＥＳ）、処理を終了する。
【０２５９】
ＬＵＴ２３１に、取得された論理アドレスを含むエントリが存在しない場合（ステップＳ５２のＮＯ）、メモリコントローラ２はソースブロックに対する１ページ分のリード動作を行う（ステップＳ５３）。このリード動作によって読み出されたデータに応じて、メモリコントローラ２は、ＬＵＴ２３１を更新し（ステップＳ５４）、逆引きＬＵＴ２３２を更新する（ステップＳ５５）。また、メモリコントローラ２は、ＶｏｉｄＣｎｔ２３３に１を加算し（ステップＳ５６）、ＩｎＶａｌｉｄＣｎｔ２３４から１を減算する（ステップＳ５７）。
【０２６０】
以上により、ソースブロックからＩｎｖａｌｉｄページである最上位ページをなくし、書き込み余地を増やすことができる。各ブロックには先入れ後出し方式でデータが格納されるので、あるソースブロックに対するリード動作を行うことにより、その際に読み出されたデータを別のブロックにコピーする動作を行うことなく、ソースブロックの最上位ページから連続した１つ以上のＩｎｖａｌｉｄページを無くすことができる。
【０２６１】
＜ソースブロックとデスティネーションブロックが同一であるコンパクション＞  
メモリコントローラ２は、選択されたソースブロックをデスティネーションブロックとしても選択し得る。この場合、メモリコントローラ２は、ソースブロックおよびデスティネーションブロックとして選択されたブロック内のＶａｌｉｄ−ｄａｔａのみをデータバッファ２５等に蓄積し、蓄積されたＶａｌｉｄ−ｄａｔａをそのブロックに書き込む（書き戻す）。
【０２６２】
図３５は、ソースブロックおよびデスティネーションブロックとして選択されたブロックに対するコンパクション動作の例を示す。初期状態において、このブロックは、３つのＶａｌｉｄページと、４つのＩｎｖａｌｉｄページと、１つのＶｏｉｄページとで構成されている。このブロックに対して１回目のリード動作が行われた場合、Ｖａｌｉｄページである最上位ページのデータが読み出されると共に、全ページがそれぞれ１つ上位にシフトし、最下位ページがＶｏｉｄページになる。読み出されたデータはＶａｌｉｄ−ｄａｔａ  ｄ０であるので、Ｖａｌｉｄ−ｄａｔａ  ｄ０はデータバッファ２５に蓄積される。
【０２６３】
その後、２回目から５回目のリード動作が行われた場合、Ｉｎｖａｌｉｄページである最上位ページのデータがそれぞれ読み出されると共に、全ページがそれぞれ１つ上位にシフトし、最下位ページがＶｏｉｄページになる。したがって５回目のリード動作後には、図３５に示すように、最上位ページにＶａｌｉｄ−ｄａｔａ  ｄ５が格納された状態となる。
【０２６４】
次いで、６回目のリード動作が行われた場合、この最上位ページのＶａｌｉｄ−ｄａｔａ  ｄ５が読み出されると共に、全ページがそれぞれ１つ上位にシフトし、最下位ページがＶｏｉｄページになる。読み出されたＶａｌｉｄ−ｄａｔａ  ｄ５はデータバッファ２５に蓄積される。
【０２６５】
ブロック内の最後のＶａｌｉｄ−ｄａｔａ  ｄ６は読み出されず、ブロック内に格納されたままにする。そして、データバッファ２５に蓄積されたＶａｌｉｄ−ｄａｔａ  ｄ０とＶａｌｉｄ−ｄａｔａ  ｄ５とがブロックに書き戻される。
【０２６６】
以上により、ソースブロックとは別のデスティネーションブロックを選択することなく、すなわちデスティネーションブロックとして選択される別のブロックを確保することなく、コンパクションを行うことができる。したがって、ソースブロックおよびデスティネーションブロックとして選択されたブロックにおいて、Ｉｎｖａｌｉｄ領域を無くすことができる。さらに、Ｖａｌｉｄ−ｄａｔａが書き戻されるので、経年劣化によるデータ劣化を防ぐリフレッシュ効果が見込まれる。
【０２６７】
なお、上述した例では、最下位のＶａｌｉｄ−ｄａｔａ（図３５ではＶａｌｉｄ−ｄａｔａ  ｄ６）をブロックから読み出さずに残す例を示したが、ブロック内の最下位のＶａｌｉｄ−ｄａｔａを含む全てのＶａｌｉｄ−ｄａｔａを読み出して、データバッファ２５に蓄積し、それら全てのＶａｌｉｄ−ｄａｔａをブロックに書き戻してもよい。これにより、全てのＶａｌｉｄ−ｄａｔａについてリフレッシュ効果が得られる。
【０２６８】
以上説明したように、第１実施形態は、データの書き込みおよび読み出しを後入れ先出し方式で行う不揮発性メモリの制御に有用である。不揮発性メモリ３は、１つ以上のＭＭＬ１０をそれぞれ含む複数の第１ブロックを備え、１つ以上のＭＭＬ１０に含まれる複数のレイヤにそれぞれ格納されているデータを最上位のレイヤから最下位のレイヤに向かう第１の方向または第１の方向とは逆の第２の方向にレイヤ単位でシフトさせることによって、各ブロックに対するデータの書き込みおよび読み出しを後入れ先出し方式で行う。複数のレイヤは、論理アドレスに関連付けられているデータが格納されたＶａｌｉｄレイヤ、および論理アドレスに関連付けられていないデータが格納されたＩｎｖａｌｉｄレイヤの少なくともいずれかを含む。Ｉｎｖａｌｉｄレイヤの第１の方向に隣接する位置には、Ｖａｌｉｄレイヤが存在する。メモリコントローラ２は、複数の第１ブロックの各々における複数のレイヤに対するＩｎｖａｌｉｄレイヤの割合（すなわち無効レイヤ率）に基づいて、それら複数の第１ブロックからコンパクション処理のソースブロックを選択する。
【０２６９】
この割合に基づいてソースブロックを選択することにより、コンパクション処理によって増加する不揮発性メモリ３内の書き込み余地を、より効果的に増やすことができる。
【０２７０】
（第２実施形態）  
次に、メモリシステム１内の不揮発性メモリ３から読み出されたデータのエラー訂正について、第２実施形態として説明する。このエラー訂正は、第１実施形態で説明したコンパクション動作中にデータ（Ｖａｌｉｄ−ｄａｔａ）が読み出された場合や、ホスト４からのリード要求に応じてデータが読み出された場合等に行われ得る。
【０２７１】
第２実施形態に係るメモリシステム１の構成は、第１実施形態に係るメモリシステム１の構成と同様である。以下では、主に、第１実施形態と異なる部分を説明する。
【０２７２】
図３７は第２実施形態に係るメモリシステム１の構成を示す。このメモリシステム１には、第１実施形態のメモリシステム１に対して、制御部２３によって用いられるシフトエラーテーブル２３５が加えられている。シフトエラーテーブル２３５はシフトエラーを訂正するための情報を含む。また、シフトエラーテーブル２３５はブロック単位で管理される。シフトエラーテーブル２３５の詳細については、図５４等を参照して後述する。
【０２７３】
メモリシステム１内の不揮発性メモリ３（例えば磁壁メモリ）において発生するエラーには、（Ｉ）ランダムエラーと（ＩＩ）シフトエラーの２種類がある。ランダムエラーは、（Ｉ−Ａ）ある磁性に設定された後に時間が経過したことによる磁性の反転と、（Ｉ−Ｂ）記憶時に誤った磁性に磁化されたことによる磁化ミスのいずれかによって発生する。
【０２７４】
＜ランダムエラー＞  
図３７は、ある磁性に設定された後に時間が経過したことによる磁性の反転によってランダムエラー（Ｉ−Ａ）が生じたブロックに対して、コンパクション動作が行われる場合の例を示す。
【０２７５】
図３７に示すように、時刻ｔ０では、ソースブロックおよびデスティネーションブロックにエラーは全く発生していない。そして、時刻ｔ０から時間が経過した時刻ｔ１では、ソースブロックおよびデスティネーションブロックの双方に、磁性の反転によるランダムエラーが発生している。この磁性の反転によるランダムエラーによって、各ブロック内のデータにはビット反転エラーが発生している。
【０２７６】
時刻ｔ１において、ソースブロックとデスティネーションブロックとを用いたコンパクション動作が行われる場合、まず、ソースブロックからＶａｌｉｄ−ｄａｔａ  ｓ１とＶａｌｉｄ−ｄａｔａ  ｓ２とが読み出される。読み出されたＶａｌｉｄ−ｄａｔａ  ｓ１およびＶａｌｉｄ−ｄａｔａ  ｓ２に対しては、各データに含まれるＥＣＣを用いた誤り訂正処理が行われる。これにより、読み出されたＶａｌｉｄ−ｄａｔａ  ｓ１およびＶａｌｉｄ−ｄａｔａ  ｓ２に発生しているビット反転エラーが訂正される。
【０２７７】
そして、エラー訂正されたＶａｌｉｄ−ｄａｔａ  ｓ１およびＶａｌｉｄ−ｄａｔａ  ｓ２は、デスティネーションブロックに書き込まれる。これにより、ソースブロックをフリーブロックとして再利用できるので、ソースブロックに含まれていたＩｎｖａｌｉｄ領域の分、書き込み余地を増やすことができる。
【０２７８】
一方で、コンパクション動作が行われる前にデスティネーションブロックに格納されていたＶａｌｉｄ−ｄａｔａ  ｄ０は、コンパクション動作によってソースブロック内のＶａｌｉｄ−ｄａｔａ  ｓ１およびＶａｌｉｄ−ｄａｔａ  ｓ２がデスティネーションブロックにさらに書き込まれることによって、デスティネーションブロック内のより下位のレイヤに押し込まれる（すなわちシフトされる）。デスティネーションブロックに格納されていたＶａｌｉｄ−ｄａｔａ  ｄ０がコンパクション動作中に読み出されることはないので、Ｖａｌｉｄ−ｄａｔａ  ｄ０に対して誤り訂正処理は行われない。したがって、デスティネーションブロックに格納されていたＶａｌｉｄ−ｄａｔａ  ｄ０は、ビット反転エラーが訂正されることなく、デスティネーションブロック内の下位レイヤに押し込まれてしまう。
【０２７９】
Ｖａｌｉｄ−ｄａｔａ  ｄ０のような領域では、さらなる時間経過によってエラー量が増大し、ＥＣＣを用いた誤り訂正処理によって対処できなくなる可能性がある、すなわちＥＣＣを用いた誤り訂正処理が失敗する可能性がある。
【０２８０】
本実施形態では、この磁性反転によるランダムエラー（Ｉ−Ａ）をコンパクションにより解消する。具体的には、メモリコントローラ２は、データが書き込まれてから長い時間が経過したブロック（古いブロックとも称する）をソースブロックとして選択し、フリーブロックをデスティネーションブロックとして選択して、コンパクション動作を行う。メモリコントローラ２は、データが書き込まれてから閾値以上の時間が経過したブロックをソースブロックとして選択してもよいし、データが書き込まれてから経過した時間がより長いブロックを優先してソースブロックとして選択してもよい。
【０２８１】
不揮発性メモリ３に含まれる複数のブロックから古いブロックを特定する方法としては、（ａ）逆引きＬＵＴ２３２内の各エントリに書き込み時刻を示す情報をさらに含め、書き込み時刻に基づいて古いブロックを特定する方法、（ｂ）不揮発性メモリ３に含まれる複数のブロックの書き込み順序を予め決定しておき、最も新しく書き込まれたブロックの、書き込み順序内での順番に基づいて、その１つ後の順番のブロックを古いブロックとして特定する方法、等がある。（ｂ）の方法では、不揮発性メモリ３が３つのブロックで構成され、ブロック番号１、２、３の順である書き込み順序が決定されている場合、ブロック番号３のブロックにデータが書き終えた後の時点において、メモリコントローラ２はブロック番号１のブロックを古いブロックとして特定する。
【０２８２】
古いブロックをソースブロックとして選択することにより、磁性反転によるランダムエラー（すなわち経年劣化によるビット反転エラー）が発生している可能性がより高いブロックを、ソースブロックとして選択できる。
【０２８３】
図３８に示す例では、古いブロックが選択されたソースブロック内のＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１には経年劣化によるビット反転エラーが発生している。メモリコントローラ２は、ソースブロックからＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１を読み出し、読み出されたＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１に対して誤り訂正処理を行う。そして、メモリコントローラ２は、エラー訂正されたＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１をフリーブロックであるデスティネーションブロックに書き込む。
【０２８４】
以上のコンパクション動作により、エラー訂正されたＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１が新規にデスティネーションブロックに書き込まれることによるリフレッシュ効果が得られる。
【０２８５】
図３９はさらに、ソースブロックである古いブロックがＩｎｖａｌｉｄ−ｄａｔａの領域を含む例を示す。ソースブロック内のＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１の各領域には経年劣化によるビット反転エラーが発生している。メモリコントローラ２は、ソースブロックからＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１を読み出し、読み出されたＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１に対して誤り訂正処理を行う。そして、メモリコントローラ２は、エラー訂正されたＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１をフリーブロックであるデスティネーションブロックに書き込む。
【０２８６】
以上のコンパクション動作により、エラー訂正されたＶａｌｉｄ−ｄａｔａ  ｓ０，ｓ１が新規にデスティネーションブロックに書き込まれることによるリフレッシュ効果が得られると共に、ソースブロックからＩｎｖａｌｉｄ領域がなくなり、フリーブロックとして再利用されることによって、書き込み余地が増加する。
【０２８７】
なお、記憶時に誤った磁性に磁化されたことによる磁化ミス（Ｉ−Ｂ）は、記憶のために発生させた磁力が意図された通りに作用しなかったために、ＭＭＬ１０を意図された状態に磁化できなかった場合に発生する。この磁化ミスによるエラーは、データ書き込み直後でも発生し得るエラーであるが、上述した誤り訂正処理によって同様に訂正できる。
【０２８８】
＜シフトエラー＞  
シフトエラー（ＩＩ）は、図４０に示すように、ＭＭＬ１０でデータがシフトされる際に、印加電界の強度が不十分な状態になり、意図されたシフトが起こらないことによって発生するエラーである。図４０に示す例では、ある磁化方向（例えば磁化方向Ｎ）に磁化されているＭＭＬ１０内の領域と、別の磁化方向（例えば磁化方向Ｓ）に磁化されているＭＭＬ１０内の領域とを、それぞれ異なる斜線のハッチングで図示している。シフトエラーは、読み出しに伴うシフト動作と書き込みに伴うシフト動作のいずれでも発生し得る。より具体的には、シフトエラーは、図４を参照して上述した例のように、例えばＭＭＬ１０内の複数の磁壁１６（あるいは磁区）の移動速度にばらつきが発生した場合の誤ったシフト動作によって発生する。
【０２８９】
シフトエラーが発生したＭＭＬ１０内のデータが読み出された場合、読み出されたデータは、本来読み出されるべきデータと比較して、シフトエラーが発生した箇所を起点に、データ全体がシフトしている。ＭＭＬ１０では、後入れ先出し方式でデータの書き込みおよび読み出しが行われるので、ＭＭＬ１０内のより下位のレイヤに格納されたデータほど、つまりシフトされた回数が多いデータほど、シフトエラーが発生する確率が上昇し、また上位のレイヤで発生したシフトエラーの影響が下位のレイヤに伝播する。
【０２９０】
図４１を参照して、あるブロックに含まれるフレーム内で発生したシフトエラーとランダムエラーの例を説明する。上述した通り、ブロックに対する書き込みおよび読み出しはページ単位で行われる。１つのページのサイズは、ユーザデータとＥＣＣとを含むフレームのサイズによって予め規定される。このため、不揮発性メモリ３においては、一般に、ページと呼ばれるデータ単位（フレーム単位）で、書き込みおよび読み出しが行われる。ここでは、説明を容易にするために、フレームの単位とページの単位とが同一であるものとして扱う。つまり、ブロック内の複数のページが、当該ブロック内の複数のフレームにそれぞれ対応する。ブロック内の複数のレイヤは、複数のフレームに論理的に区分されている。各フレームは、隣接する幾つかのレイヤの集合を含んでいる。
【０２９１】
また、ブロックは物理的に複数のＭＭＬ１０（ここではＭ０からＭ１０００＋α）で構成されている。各ＭＭＬ１０では、レイヤ毎に１ビットのデータが格納され得る。
【０２９２】
図４１（Ａ）に示すように、ブロック内の各フレーム（ここではフレームβ）は、１ページ分（例えば４ＫＢ）のデータ部とＥＣＣ（パリティ）とを含んでいる。ここで、フレームβが、上位レイヤから下位レイヤへの順に、レイヤＬ３８からレイヤＬ０までの３９個のレイヤを含む場合を例示する。フレームβには、ＥＣＣを用いた誤り訂正処理により、エラーが発生していることが検出されている。この誤り訂正処理では、エラーがシフトエラーとランダムエラーのいずれであるかを判別できないが、説明を分かりやすくするために、フレームβ内のレイヤでは、シフトエラーの発生箇所とランダムエラーの発生箇所とが識別できるように図示されている。このフレームβでは、Ｌ３６からＬ０までのレイヤ群でシフトエラーが発生し、またレイヤＬ２およびレイヤＬ１でランダムエラーが発生している。
【０２９３】
図４１（Ｂ）は、フレームβにおいて発生している各エラーを、ブロックを構成するＭＭＬ１０内の対応するレイヤ上にマッピングしたものである。これにより、ブロック内のＭＭＬ  Ｍ１においてレイヤＬ３６＋α（フレームβ内のレイヤＬ３６に相当）以降のレイヤ群でシフトエラーが発生し、またＭＭＬ  Ｍ１０００＋（α―１）においてレイヤＬ２＋α（フレームβ内のレイヤＬ２に相当）およびレイヤＬ１＋α（フレームβ内のレイヤＬ１に相当）でランダムエラーが発生していることが分かる。図４１（Ｂ）において、シフトエラーが発生しているレイヤはドットで図示し、ランダムエラーが発生しているレイヤは斜線で図示している。
【０２９４】
ＭＭＬ  Ｍ１では、レイヤＬ３６＋αで発生したシフトエラーが、このレイヤＬ３６＋αよりも下位にあるレイヤ群に伝播したことにより、レイヤＬ３６＋α以降のレイヤ群でシフトエラーが発生している。つまり、シフトエラーが発生したレイヤ群には、実際に過剰シフトまたはシフト不足が発生した１つのレイヤ（ここではレイヤＬ３６＋α）と、その影響を受けた同一のＭＭＬ内にある下位のレイヤ群とが含まれ得る。
【０２９５】
さらに図４２に示すように、複数のフレームで構成されるブロックでは、上位のフレームで発生したシフトエラーの影響が下位のフレームに伝播する。ここでは、ブロックが、上位から順に、第１フレームから第５フレームで構成されている場合を例示している。
【０２９６】
図４２において、垂直方向に延びる各列は１つのＭＭＬ１０を示し、水平方向に延びる各行は１つのレイヤを示す。つまり、図４２に示す例では、水平方向に並べられた複数の列で表される複数のＭＭＬ１０と、垂直方向に並べられた複数の行で表される複数のレイヤとで、ブロックが表現されている。１つの列に対応する各ＭＭＬ１０において、空白で図示されたレイヤではエラーが発生しておらず、一方、斜線で図示されたレイヤはシフトエラーが発生している。
【０２９７】
いずれのフレームも、シフトエラーが発生した１つ以上のＭＭＬ１０を含んでいる。また、上位のフレームで発生したシフトエラーの影響を受けることにより、下位のフレームほど、シフトエラーが発生しているＭＭＬ１０の数が増加する、すなわちエラー量が増大する。
【０２９８】
例えば、上位の第１フレーム、第２フレーム、および第３フレームが読み出された場合、各フレームに含まれるＥＣＣを用いたエラー訂正が成功し、発生したシフトエラーを訂正できる。これに対して、下位の第４フレームおよび第５フレームが読み出された場合、エラー量が大きいために、各フレームに含まれるＥＣＣを用いたエラー訂正が失敗し、発生したシフトエラーを訂正できない場合がある。
【０２９９】
本実施形態では、上位フレームで発生したシフトエラーを学習し、その学習結果に下位フレームを適応させる。これにより、上位フレームで発生したシフトエラーの影響を受けて発生している、下位フレーム内のシフトエラーを訂正できる。そのため、学習結果に適応した下位フレームに対してＥＣＣを用いた誤り訂正処理を行うことにより、ＥＣＣによるエラー訂正が成功する可能性を高めることができる。なお、「学習」は、発生したシフトエラーを訂正するための情報を取得することを表す。また、「適応」は、取得された情報を用いてシフトエラーを訂正することを表す。
【０３００】
ところで、シフトエラーを解決するための方法として、例えば、図６を参照して上述したように、最終的により下位に格納されるデータ部ほど、より強い強度のＥＣＣ（パリティ）を付加する方法がある。一例では、最終的に最下位に位置するページに格納されるデータ部（すなわち最初にブロックに入力されるページデータ）のＥＣＣを含むサイズは、最終的に最上位に位置するページに格納されるデータ部（すなわち最後にブロックに入力されるページデータ）のＥＣＣを含むサイズよりも大きい。なお、データ部のサイズはＥＣＣのサイズよりも大きい。
【０３０１】
しかし、この方法では、レイヤ（あるいはページ）毎のデータ部に、データ部が最終的に格納されるＭＭＬ１０内の位置に応じて異なるエラー訂正能力を有するＥＣＣを付加し、管理する必要がある。ここで、コンパクションが行われ、ソースブロックから読み出されたデータがデスティネーションブロックに書き込まれるケースを考える。このケースでは、データが格納されていたソースブロック内の位置（例えば上層）と、当該データが格納されるべきデスティネーションブロック内の位置（例えば下層）とが異なるならば、データとＥＣＣとからなるフレームのデータ長が、ソースブロックに格納されていた時点とデスティネーションブロックに格納される時点とで変化する。そのため、レイヤ（あるいはページ）毎のデータ部に異なるエラー訂正能力を有するＥＣＣを付加する方法では、管理が困難である。
【０３０２】
そのため本実施形態では、最終的にＭＭＬ１０内の下位に格納されるデータ部ほど、より強い強度のＥＣＣを付加する方法ではなく、上位フレームで発生したシフトエラーを学習し、その学習結果を下位のフレームに適応する方法が用いられる。これにより、データの管理が容易になると共に、読み出されたデータに発生しているエラーに対する訂正精度を高めることができる。
【０３０３】
図４３から図５０を参照して、上位フレームで発生したシフトエラーを学習し、その学習結果に下位のフレームを適応させる方法について具体的に説明する。
【０３０４】
まず図４３に示すように、メモリコントローラ２はブロック内の第１フレームを読み出し、第１フレーム内のＥＣＣを用いた誤り訂正処理を行う。この誤り訂正処理が成功し、１つ以上のデータ（ビット）のエラーが訂正されていた場合、メモリコントローラ２はエラーが発生していたＭＭＬ１０を特定する。そして、メモリコントローラ２は、当該エラーがシフトエラーであるならば、そのシフトエラーを訂正するための情報を学習し、その学習結果を辞書（例えばシフトエラーテーブル２３５）に登録する。辞書には、例えば、シフトエラーが発生していたＭＭＬ１０を特定可能な情報と、シフトエラーを訂正するためにデータをシフトすべき量（例えばシフトすべき方向およびビット数）とが登録される。なお、発生していたエラーがシフトエラーであるか否かを判定する方法については、図５５から図６９を参照して後述する。
【０３０５】
図４４に示すように、この辞書に登録されたシフトエラーを訂正するための情報に、読み出された第１フレームを適応させることにより、第１フレームに発生しているシフトエラーを訂正できる。１つの列に対応する各ＭＭＬ１０において、ドットで図示されたレイヤは、発生していたシフトエラーが訂正されたレイヤを示している。また、第２フレーム以降のフレーム群の各々では、第１フレームにおいてシフトエラーが発生していた１つ以上のＭＭＬ１０において、同様にシフトエラーが発生する。そのため、この辞書に登録されたシフトエラーを訂正するための情報に第２フレーム以降の各フレームを適応させることにより、第１フレームで発生したシフトエラーの影響により発生している、第２フレーム以降の各フレーム内のシフトエラーを訂正できる。
【０３０６】
より具体的には、第１フレームに対する学習と第２フレームに対する適応とにおいて、メモリコントローラ２は、まず、第１フレーム内のＥＣＣを用いて、第１フレーム内の第１データ部に対して誤り訂正処理を行う。そして、この誤り訂正処理において訂正されたシフトエラーが、あるＭＭＬ１０で発生していた場合、メモリコントローラ２は、このＭＭＬ１０内のあるレイヤに格納されたデータを、当該ＭＭＬ１０内の別のレイヤに格納されたデータに置き換えることによって、第２フレーム内のデータ部を訂正する。これにより、第１フレームで発生したシフトエラーの影響により発生している、第２フレーム内のシフトエラーを訂正できる。
【０３０７】
次いで図４５に示すように、メモリコントローラ２はブロック内の第２フレームを読み出し、第２フレーム内のＥＣＣを用いた誤り訂正処理を行う。この誤り訂正処理が成功し、少なくとも１つのエラーが訂正されていた場合、メモリコントローラ２はエラーが発生していたＭＭＬ１０を特定する。そして、メモリコントローラ２は、当該エラーがシフトエラーであるならば、そのシフトエラーを訂正するための情報を学習し、その学習結果を辞書に登録する。この登録では、例えば、第１フレームで学習されたシフトエラーとの差分が登録される。
【０３０８】
図４６に示すように、この辞書に登録されたシフトエラーを訂正するための情報に、読み出された第２フレームを適応させることにより、第２フレームに発生しているシフトエラーを訂正できる。また、第３フレーム以降のフレーム群の各々では、第１フレームと第２フレームの少なくとも一方においてシフトエラーが発生していた１つ以上のＭＭＬ１０において、シフトエラーが発生する。そのため、この辞書に登録されたシフトエラーを訂正するための情報に第３フレーム以降の各フレームを適応させることにより、第１フレームおよび第２フレームで発生したシフトエラーの影響により発生している、第３フレーム以降の各フレーム内のシフトエラーを訂正できる。
【０３０９】
そして図４７に示すように、メモリコントローラ２はブロック内の第３フレームを読み出し、第３フレーム内のＥＣＣを用いた誤り訂正処理を行う。この誤り訂正処理が成功し、１つ以上のデータのエラーが訂正されていた場合、メモリコントローラ２はエラーが発生していたＭＭＬ１０を特定する。そして、メモリコントローラ２は、当該エラーがシフトエラーであるならば、そのシフトエラーを訂正するための情報を学習し、その学習結果を辞書に登録する。この登録では、例えば、第１フレームおよび第２フレームで学習されたシフトエラーとの差分が登録される。
【０３１０】
図４８に示すように、この辞書に登録されたシフトエラーを訂正するための情報に、読み出された第３フレームを適応させることにより、第３フレームに発生しているシフトエラーを訂正できる。また、第４フレーム以降のフレーム群の各々では、第１フレームと第２フレームと第３フレームの少なくとも１つにおいてシフトエラーが発生していた１つ以上のＭＭＬ１０において、シフトエラーが発生する。そのため、この辞書に登録されたシフトエラーを訂正するための情報に第４フレーム以降の各フレームを適応させることにより、第１フレーム、第２フレーム、および第３フレームで発生したシフトエラーの影響により発生している、第４フレーム以降の各フレーム内のシフトエラーを訂正できる。
【０３１１】
さらに図４９に示すように、メモリコントローラ２はブロック内の第４フレームを読み出し、第４フレーム内のＥＣＣを用いた誤り訂正処理が失敗するので、第１フレーム、第２フレーム、および第３フレームに対するシフトエラーの学習結果を示す辞書に、読み出された第４フレームを適応させ、適応した第４フレーム内のＥＣＣを用いた誤り訂正処理を行う。
【０３１２】
図４２を参照して上述したように、読み出された状態のままの第４フレームに対してＥＣＣを用いた誤り訂正処理が行われた場合、エラー量が大きいために、エラー訂正が失敗する。しかし、シフトエラーの学習結果を示す辞書に適応した第４フレームでは、第１フレーム、第２フレーム、および第３フレームで発生したシフトエラーの影響により発生している、第４フレーム内のシフトエラーが訂正され、エラー量が低減しているので、第４フレームに対する誤り訂正処理が成功する可能性を高めることができる。
【０３１３】
この誤り訂正処理が成功し、１つ以上のデータのエラーが訂正されていた場合、メモリコントローラ２はエラーが発生していたＭＭＬ１０を特定する。そして、メモリコントローラ２は、当該エラーがシフトエラーであるならば、そのシフトエラーを訂正するための情報を学習し、その学習結果を辞書に登録する。この登録では、例えば、第１フレーム、第２フレーム、および第３フレームで学習されたシフトエラーとの差分が登録される。
【０３１４】
図５０に示すように、この辞書に登録されたシフトエラーを訂正するための情報に、読み出された第４フレームを適応させることにより、第４フレームに発生しているシフトエラーを訂正できる。また、第５フレームでは、第１フレームと第２フレームと第３フレームと第４フレームの少なくとも１つにおいてシフトエラーが発生していた１つ以上のＭＭＬ１０において、シフトエラーが発生する。そのため、この辞書に登録されたシフトエラーを訂正するための情報に第５フレームを適応させることにより、第１フレーム、第２フレーム、第３フレーム、および第４フレームで発生したシフトエラーの影響により発生している、第５フレーム内のシフトエラーを訂正できる。
【０３１５】
図４２を参照して上述したように、読み出された状態のままの第５フレームに対してＥＣＣを用いた誤り訂正処理が行われた場合、エラー量が大きいために、エラー訂正が失敗する。しかし、シフトエラーの学習結果を示す辞書に適応した第５フレームでは、第１フレーム、第２フレーム、第３フレーム、および第４フレームで発生したシフトエラーの影響により発生している、第５フレーム内のシフトエラーが訂正され、エラー量が低減しているので、第５フレームに対する誤り訂正処理が成功する可能性を高めることができる。
【０３１６】
また図５１は、不揮発性メモリ３内のあるブロックがフレームβ、フレームβ−１、およびフレームβ−２の３つのフレームを含む例を示す。図５１（Ａ）に示すように、ＭＭＬ  Ｍ１では、フレームβ内のレイヤＬＡ１を開始位置とする第１シフトエラーと、フレームβ−２内のレイヤＬＡ２を開始位置とする第２シフトエラーとが発生している。また、ＭＭＬ  Ｍ０では、β−２内のレイヤＬＢ１を開始位置とする第３シフトエラーが発生している。さらに、各フレームβ，β−１，β−２では幾つかのランダムエラーが発生している。
【０３１７】
図５１（Ｂ）に示すように、まず、読み出されたフレームβに対する誤り訂正処理が成功した場合、ＭＭＬ  Ｍ１内のレイヤＬＡ１を開始位置とする第１シフトエラーが学習され、学習結果が辞書に登録される。次に、読み出されたフレームβ−１を、第１シフトエラーの学習結果が登録された辞書に適応させることにより、フレームβ−１で発生している第１シフトエラーを、つまりフレームβ−１に影響している第１シフトエラーを、訂正できる。
【０３１８】
さらに、読み出されたフレームβ−２を、第１シフトエラーの学習結果が登録された辞書に適応させることにより、フレームβ−２で発生している第１シフトエラーを、つまりフレームβ−２に影響している第１シフトエラーを、訂正できる。そして、第１シフトエラーが訂正されたフレームβ−２（あるいは読み出されたフレームβ−２）に対する誤り訂正処理が成功した場合、ＭＭＬ  Ｍ１内のレイヤＬＡ２を開始位置とする第２シフトエラーとＭＭＬ  Ｍ０内のレイヤＬＢ１を開始位置とする第３シフトエラーとが学習され、学習結果が辞書にさらに登録される。
【０３１９】
このように、ブロックに含まれる複数のフレームが読み出された場合、各フレームを用いてシフトエラーの学習が行われ得ると共に、各フレームに対してシフトエラーを訂正するための適応が行われ得る。
【０３２０】
図５２は、メモリコントローラ２によって実行されるシフトエラー学習・適応処理の手順の例を示す。ここでは、説明を分かりやすくするために、１つのブロック内の全データがまとめて読み出された後に、シフトエラーの学習および適応が行われる例を示すが、１つのブロックからフレーム単位のデータが読み出される毎に、シフトエラーの学習および適応が行われてもよい。
【０３２１】
まず、メモリコントローラ２は、不揮発性メモリ３内の１つのブロックに格納された全データを読み出し、データバッファ２５等に蓄積する（ステップＳ６０１）。つまり、ブロックを構成する複数のフレームが読み出され、データバッファ２５等に蓄積される。そして、メモリコントローラ２は、対象フレーム番号ｉに１を設定する（ステップＳ６０２）。
【０３２２】
対象フレーム番号ｉがブロック内のフレーム数以下である場合、メモリコントローラ２は第ｉフレームに対する誤り訂正処理を行う（ステップＳ６０３）。メモリコントローラ２は、第ｉフレームに含まれるＥＣＣ（パリティ）を用いて誤り訂正処理を行う。ＥＣＣは、エラー位置を特定可能な符号であり、例えばＢＣＨ符号である。そして、メモリコントローラ２はこの誤り訂正処理が成功したか否かを判定する（ステップＳ６０４）。誤り訂正処理が成功した場合（ステップＳ６０４のＹＥＳ）、メモリコントローラ２は誤り訂正処理において訂正されたエラーがあったどうかを判定する（ステップＳ６０５）。エラーは、第ｉフレーム内の１つ以上のビットのデータに発生した誤りであり、誤り訂正処理において検出された後、訂正される。
【０３２３】
誤り訂正処理において訂正されたエラーがあった場合（ステップＳ６０５のＹＥＳ）、メモリコントローラ２はブロックを構成する複数のＭＭＬ１０の内、エラーを含んでいたＭＭＬ１０を検出する（ステップＳ６０６）。また、メモリコントローラ２は、そのＭＭＬ１０内で発生していたエラーのエラーモードを検出する（ステップＳ６０７）。検出されるエラーモードは、ランダムエラーとシフトエラーの少なくともいずれかである。エラーモードを検出するための方法については、図５５から図６９を参照して後述する。
【０３２４】
エラーモードがシフトエラーであるならば（ステップＳ６０８のＹＥＳ）、メモリコントローラ２は、シフトエラーを訂正するための情報を含むシフトエラーテーブル２３５を更新する（ステップＳ６０９）。シフトエラーテーブル２３５は、例えば、シフトエラーが発生したＭＭＬ１０を特定するための情報と訂正のためにデータがシフトされるべきシフト量とをそれぞれ含む１つ以上のエントリを含み得る。メモリコントローラ２は、あるシフトエラーを訂正するための情報を含むエントリをシフトエラーテーブル２３５に追加してもよいし、あるシフトエラーが発生したＭＭＬ１０に対応するエントリがシフトエラーテーブル２３５に既に含まれているならば、そのエントリ内のシフト量を更新してもよい。
【０３２５】
訂正されたエラーがシフトエラーでないならば（ステップＳ６０８のＮＯ）、すなわちランダムエラーであるならば、ステップＳ６０９の手順はスキップされる。
【０３２６】
ステップＳ６０６からステップＳ６０９までの手順は、第ｉフレームにエラーが発生していて、そのエラーが訂正された場合に、シフトエラーに関する情報をＭＭＬ１０毎に学習するための学習フェーズであり、したがって、エラーを含む複数のＭＭＬ１０が存在する場合にはＭＭＬ１０毎に行われ得る。
【０３２７】
次いで、メモリコントローラ２は対象フレーム番号ｉに１を加算し（ステップＳ６１０）、その対象フレーム番号ｉがブロック内のフレーム数以下であるならば、ステップＳ６０３に戻り、次のフレームに対する処理が行われる。対象フレーム番号ｉがブロック内のフレーム数を超えたならば、処理を終了する。
【０３２８】
また、第ｉフレームに対する誤り訂正処理が失敗した場合（ステップＳ６０４のＮＯ）、メモリコントローラ２は、シフトエラーテーブル２３５にシフトエラー訂正のための情報が含まれているか否かを判定する（ステップＳ６１１）。シフトエラーテーブル２３５にシフトエラー訂正のための情報が含まれている場合（ステップＳ６１１のＹＥＳ）、メモリコントローラ２は第ｉフレームをシフトエラー訂正のための情報に適応させる（ステップＳ６１２）。メモリコントローラ２は、適応した第ｉフレームに対して誤り訂正処理を行う（ステップＳ６１３）。メモリコントローラ２は、適応した第ｉフレームに含まれるＥＣＣ（パリティ）を用いて誤り訂正処理を行う。そして、メモリコントローラ２は誤り訂正処理が成功したか否かを判定する（ステップＳ６１４）。誤り訂正処理が成功した場合（ステップＳ６１４のＹＥＳ）、ステップＳ６０５に進み、ステップＳ６１４で訂正されたエラーがあれば、そのエラーに関する学習フェーズ（ステップＳ６０６からステップＳ６０９）に遷移する。
【０３２９】
一方、誤り訂正処理が失敗した場合（ステップＳ６１４のＮＯ）、あるいはシフトエラーテーブル２３５にシフトエラー訂正のための情報が含まれていない場合（ステップＳ６１１のＮＯ）、メモリコントローラ２は、シフトエラーテーブル２３５を用いる方法とは別のエラー訂正方法を用いてエラーを訂正し（ステップＳ６１５）、処理を終了する。この別のエラー訂正方法は、例えばＲｅｄｕｎｄａｎｔ  Ａｒｒａｙｓ  ｏｆ  Ｉｎｅｘｐｅｎｓｉｖｅ  Ｄｉｓｋｓ（ＲＡＩＤ）による方法である。
【０３３０】
ステップＳ６１１からステップＳ６１４までの手順は、読み出された第ｉフレームに対する誤り訂正処理が失敗した場合に、シフトエラーテーブル２３５に示されるシフトエラー訂正のための情報に第ｉフレームを適応させるための適応フェーズである。ステップＳ６１４では、シフトエラー訂正のための情報に適応した第ｉフレームに対して、すなわちシフトエラーテーブル２３５を用いてシフトエラーが訂正され、エラー量が低減された第ｉフレームに対して、誤り訂正処理が行われる。そのため、シフトエラー訂正のための情報に適応した第ｉフレームに対して行われる誤り訂正処理（ステップＳ６１４）は、不揮発性メモリ３から読み出された状態のままの第ｉフレームに対して行われる誤り訂正処理（ステップＳ６０４）よりも、成功する確率が上昇する。ステップＳ６１４の誤り訂正処理が成功した場合、ステップＳ６０４の単なる誤り訂正処理だけでは訂正できなかった第ｉフレーム内のエラーを、シフトエラーテーブル２３５を用いて訂正できたと云える。さらに、ステップＳ６１４の誤り訂正処理で訂正されたエラーを学習フェーズで学習でき、その学習結果（すなわちシフトエラーテーブル２３５の更新）が以降のフレームに対するエラー訂正に反映され得る。
【０３３１】
以上により、各フレームに発生しているシフトエラーを学習し、学習結果に以降のフレームを適応させながら、各フレームに対するＥＣＣを用いた誤り訂正処理が行われる。これにより、読み出されたデータに誤りが発生していたとしても、正しいデータが得られる可能性が高まる。
【０３３２】
なお、上述した例では、誤り訂正処理が失敗した場合に、ステップＳ６１１からステップＳ６１４までの適応フェーズに移行する例を示したが、誤り訂正処理が成功するか失敗するかに関わらず、適応フェーズに移行するようにしてもよい。したがって、メモリコントローラ２は、例えば誤り訂正処理を行う前に適応フェーズに移行してもよい。
【０３３３】
図５３のフローチャートは、誤り訂正処理を行う前に、適応フェーズに移行する場合のシフトエラー学習・適応処理の手順の例を示す。ステップＳ７０１およびステップＳ７０２の手順は、図５２のフローチャートを参照して上述したステップＳ６０１およびステップＳ６０２の手順と同様である。そして、メモリコントローラ２は第ｉフレームに対する誤り訂正処理を行うことなく、適応フェーズに移行する。
【０３３４】
より具体的には、メモリコントローラ２は、シフトエラーシフトエラーテーブル２３５にシフトエラー訂正のための情報が含まれているか否かを判定する（ステップＳ７０３）。シフトエラーテーブル２３５にシフトエラー訂正のための情報が含まれている場合（ステップＳ７０３のＹＥＳ）、メモリコントローラ２は第ｉフレームをシフトエラー訂正のための情報に適応させる（ステップＳ７０４）。メモリコントローラ２は、適応した第ｉフレームに対して誤り訂正処理を行う（ステップＳ７０５）。
【０３３５】
一方、シフトエラーテーブル２３５にシフトエラー訂正のための情報が含まれていない場合（ステップＳ７０３のＮＯ）、メモリコントローラ２は、第ｉフレーム（すなわちシフトエラー訂正のための情報に適応していない第ｉフレーム）に対して誤り訂正処理を行う（ステップＳ７０６）。
【０３３６】
次いで、メモリコントローラ２は、ステップＳ７０５またはステップＳ７０６の誤り訂正処理が成功したか否かを判定する（ステップＳ７０７）。誤り訂正処理が成功した場合（ステップＳ７０７のＹＥＳ）、ステップＳ７０８に進み、ステップＳ７０５またはステップＳ７０６の誤り訂正処理で訂正されたエラーがあれば、そのエラーに関する学習フェーズ（ステップＳ７０８からステップＳ７１１）に遷移する。この学習フェーズの具体的な手順は、図５２のフローチャートを参照して上述したステップＳ６０６からステップＳ６０９の学習フェーズと同様である。
【０３３７】
そして、メモリコントローラ２は対象フレーム番号ｉに１を加算し（ステップＳ７１２）、その対象フレーム番号ｉがブロック内のフレーム数以下であるならば、ステップＳ７０３に戻り、次のフレームに対する処理が行われる。対象フレーム番号ｉがブロック内のフレーム数を超えたならば、処理を終了する。
【０３３８】
また、ステップＳ７０５またはステップＳ７０６の誤り訂正処理が失敗した場合（ステップＳ７０７のＮＯ）、メモリコントローラ２は、シフトエラーテーブル２３５を用いる方法とは別のエラー訂正方法を用いてエラーを訂正し（ステップＳ７１３）、処理を終了する。この別のエラー訂正方法は、例えばＲＡＩＤによる方法である。
【０３３９】
以上のように、メモリコントローラ２は、誤り訂正処理を行う前に適応フェーズに移行する。この場合、メモリコントローラ２は、シフトエラー訂正のための情報があれば、その情報に適応したフレームに対して誤り訂正処理を行うことができる。
【０３４０】
図５４はシフトエラーテーブル２３５の一構成例を示す。シフトエラーテーブル２３５は、例えばブロック単位に管理される。また、シフトエラーテーブル２３５は、不揮発性メモリ３内のシフトエラーが発生した複数のＭＭＬ１０に対応する複数のエントリを含む。各エントリは、例えば、ＭＭＬ位置とシフト量とを含む。
【０３４１】
シフトエラーが発生したあるＭＭＬ１０に対応するエントリにおいて、「ＭＭＬ位置」はそのＭＭＬ１０を特定するための情報を示す。「ＭＭＬ位置」には、数値や識別情報のような、不揮発性メモリ３内の複数のＭＭＬ１０の内の１つのＭＭＬ１０を特定できる情報が設定され得る。
【０３４２】
また、「シフト量」は、そのＭＭＬ１０で発生したシフトエラーを訂正するためのシフト量を示す。「シフト量」には、ＭＭＬ１０から読み出された複数ビットのデータをシフトすべき方向とそのビット数とが特定できる情報であれば、どのような情報が設定されてもよい。例えば“＋１”や“−２”のようなベクトルが用いられる場合、正負（＋または−）でシフト方向が特定され、数値でビット数が特定される。
【０３４３】
メモリコントローラ２は、後続する、あるフレーム内のデータ部をシフトエラーテーブル２３５に適応させる場合、例えば、「シフト量」に示されるシフト方向に、「シフト量」で示されるビット数（例えばＮビット分）だけ、そのデータ部に含まれるビット群をシフト（移動）する。これにより、データ部内のある範囲のビット群が、そのデータ部内の別のビット群に置き換えられる。
【０３４４】
なお、ブロックに含まれる複数のフレームがフレーム単位で読み出される場合、メモリコントローラ２は、シフトエラーテーブル２３５で、シフト量だけでなく、そのシフト量に基づいてシフトしたことにより、別のフレーム内に配置されるデータビット群も保持するように、管理し得る。隣り合う２つのフレームでは、シフト量に基づくシフトにより、それらフレーム間の境界を超えてビット群がシフトし得る。つまり、一方のフレーム内の境界に隣接するビット群が、他方のフレーム内の当該境界に隣接するビット群で置き換えられ得る。そのため、メモリコントローラ２は、あるフレーム内のデータ部をシフト量に基づきシフトする際に利用できるように、そのシフトで必要になる別のフレーム内のビット群をシフトエラーテーブル２３５で管理し得る。
【０３４５】
１つのＭＭＬ１０に複数のシフトエラーが発生している場合、シフトエラーテーブル２３５には、それら複数のシフトエラーにそれぞれ対応する複数のエントリが含まれ得る。あるいは、ある１つのＭＭＬ１０に関して、複数のシフトエラーを訂正するためのシフト量が統合された１つのエントリが含まれてもよい。
【０３４６】
図５５は、ランダムエラーが発生している場合のデータ読み出し結果の例を示す。ここでは、ＭＭＬ１０が１３個の磁区を含み、これら１３個の磁区を用いて１２ビットのデータが格納されている場合を例示する。ＭＭＬ１０内の各磁区の磁化方向ＮまたはＳは、各磁区の記憶値として用いられる。例えば、ＭＭＬ１０上の連続する２つの磁区の各々の磁化方向が一致することはデータ“０”が格納されていることに相当し、磁化方向が異なることはデータ“１”が格納されていることに相当する。なお、ＭＭＬ１０内の１３個の磁区において、最も浅い位置にある磁区は磁区０であり、最も深い位置にある磁区は磁区１２である。ＭＭＬ１０内の磁区の記憶値が読み出される場合は、最初に最も浅い磁区０の記憶値が読み出され、後続する磁区１から磁区１１までの各磁区の記憶値が順に読み出された後、最後に磁区１３の記憶値が読み出される。
【０３４７】
図５５に示す期待値は、ＭＭＬ１０に記憶されているべき理想的な記憶値と、それに対応するデータとを示す。以下では、（Ａ）ランダムエラーが１箇所発生した場合の読み出し結果の例、（Ｂ）ランダムエラーが２箇所発生した場合の読み出し結果の第１の例、および（Ｃ）ランダムエラーが２箇所発生した場合の読み出し結果の第２の例についてそれぞれ説明する。
【０３４８】
（Ａ）ＭＭＬ１０内の磁区６に記憶されていた磁化方向Ｎが磁化方向Ｓに反転したことによって、１つの記憶値にランダムエラーが発生した場合、読み出された順序に並んだ第１ビットから第１２ビットまでの１２ビットのデータ内の連続する２つのデータ（ここでは第６ビットのデータおよび第７ビットのデータ）にエラーが発生する。つまり、ＭＭＬ１０内の１つの磁区に誤った磁化方向が記憶されたならば、連続する２ビットのデータが誤ることになる。
【０３４９】
また、（Ｂ）ＭＭＬ１０内の磁区５および磁区６にそれぞれ記憶されていた磁化方向Ｎが磁化方向Ｓに反転したことによって、２つの記憶値にランダムエラーが発生した場合、読み出された順序に並んだ第１ビットから第１２ビットまでの１２ビットのデータ内の、第５ビットのデータおよび第７ビットのデータにエラーが発生する。なお、データが０および１の２値のいずれかになるので、第６ビットのデータは、２つの磁区５および磁区６で発生した２つのランダムエラーの影響を受けたことによって、つまり誤りが２回発生したことによって、正常な値として得られている。つまり、ＭＭＬ１０内の連続した２つの磁区にそれぞれ誤った磁化方向が記憶されたならば、２ビットのデータが誤ることになる。
【０３５０】
さらに、（Ｃ）ＭＭＬ１０内の磁区４および磁区６にそれぞれ記憶されていた磁化方向Ｎが磁化方向Ｓに反転したことによって、２つの記憶値にランダムエラーが発生した場合、読み出された順序に並んだ第１ビットから第１２ビットまでの１２ビットのデータ内の、第４ビットのデータ、第５ビットのデータ、第６ビットのデータ、および第７ビットのデータにエラーが発生する。つまり、ＭＭＬ１０内の離れた２つの磁区（すなわち連続していない２つの磁区）に誤った磁化方向が記憶されたならば、４ビットのデータが誤ることになる。
【０３５１】
また図５６は、シフトエラーが発生している場合のデータ読み出し結果の例を示す。ＭＭＬ１０内の磁区や、各磁区の記憶値に基づいて得られるデータの値については、図５５を参照して上述した通りである。期待値は、ＭＭＬ１０に記憶されているべき理想的な記憶値と、それに対応するデータとを示す。
【０３５２】
図５６に示すように、シフトエラーが発生した場合、読み出された順序に並んだ第１ビットから第１２ビットまでの１２ビットのデータには不規則なエラーが発生する。この例では、リード動作時に下層レイヤから上層レイヤへの方向のシフトが不足したことに起因するシフトエラーが発生している。より具体的には、リード動作において、下層レイヤから上層レイヤへの方向の磁区２のシフトが不足したことにより、磁区２と同様の磁化方向Ｓを有する磁区３が追加され、本来、期待値に示すように、磁区３以降に位置すべき複数の磁区が、磁区４以降に位置したようになっている。これにより、読み出し結果の１２ビットのデータでは、不規則なエラーが発生している。
【０３５３】
なお、この他にも、リード動作時に下層レイヤから上層レイヤへの方向のシフトが過剰であったことに起因するシフトエラー、ライト動作時に上層レイヤから下層レイヤへの方向のシフトが過剰であったことに起因するシフトエラー、ライト動作時に上層レイヤから下層レイヤへの方向のシフトが不足したことに起因するシフトエラーが発生し得る。
【０３５４】
図５７から図６１を参照して、あるＭＭＬ１０から読み出された複数ビットのデータに１つのシフトエラーが発生していると判別される第１の例について説明する。このシフトエラーは、リード動作時のシフト不足に起因して発生するシフトエラーか、あるいはライド動作時の過剰シフトに起因して発生するシフトエラーである。図５５および図５６を参照して上述した例と同様に、ＭＭＬ１０が１３個の磁区を含み、これら１３個の磁区を用いて１２ビットのデータが格納されていることを想定する。
【０３５５】
図５７は、期待値とシフトエラーが発生している場合の読み出し結果とを示す。期待値には、ＭＭＬ１０に記憶されているべき理想的な記憶値と、それに対応するデータとが示されている。シフトエラーが発生している場合の読み出し結果には、ＭＭＬ１０から実際に読み出された記憶値と、それに対応するデータと、各データのエラー判定結果とが示されている。
【０３５６】
読み出されたＭＭＬ１０上の記憶値では、磁区３に磁化方向Ｓが追加されたことにより、本来、磁区３から磁区１１に設定されるべき磁化方向が、それぞれ磁区４から磁区１２に設定されている。また、本来、磁区１２に設定されるべき磁化方向Ｎが失われている。
【０３５７】
磁区３への磁化方向Ｓの追加は、例えば、磁区２の磁化方向を読み出すための読み出し動作に含まれるシフト動作（すなわち下位レイヤから上位レイヤへの方向のシフト動作）が不足したこと、あるいは磁区２の磁化方向を書き込むための書き込み動作に含まれるシフト動作（すなわち上位レイヤから下位レイヤへの方向のシフト動作）が過剰であったことによって発生し得る。
【０３５８】
また読み出されたＭＭＬ１０上の記憶値に基づく１２ビットのデータを、対応する記憶値が読み出された順に、第１ビットから第１２ビットまでのデータとすると、第３ビット、第６ビット、第８ビット、第９ビット、および第１０ビットのデータに誤りが発生している。つまり、図５８に示すように、読み出された１２ビットのデータには、１つの記憶値にランダムエラーが発生したことに応じて連続する２ビットのデータに誤りが発生するというランダムエラーに対応する規則的なエラーではなく、不規則なエラーが発生している。
【０３５９】
図５９は、読み出し結果のデータと期待値のデータとに基づく編集グラフ（ｅｄｉｔ  ｇｒａｐｈ）から取得された最短経路８１の例を示す。編集グラフは、読み出し結果のデータを期待値のデータと一致させるための経路を示す。編集グラフは、例えば、以下の（１）から（４）までの手順により得られる。
【０３６０】
（１）Ｍビットの読み出し結果のデータが垂直方向に順に配置され、Ｎビットの期待値のデータが水平方向に順に配置された平面上に、読み出し結果のデータの第ｉビットと期待値のデータの第ｊビットとでそれぞれ特定される複数の点（ｉ，ｊ）を設定する。なお、ｉ∈［０，Ｍ］であり、ｊ∈［０，Ｎ］である。読み出し結果のデータの第０ビットと期待値のデータの第０ビットとしては、同一の値が設定されているものと仮定する。またここでは、ｉ，ｊの各々の値が小さいビットほど上位ビットと称し、大きいビットほど下位ビットと称する。  
（２）ｉ∈［１，Ｍ］であり、ｊ∈［０，Ｎ］である点（ｉ，ｊ）に関して、点（ｉ−１，ｊ）から点（ｉ，ｊ）までの垂直方向の辺（すなわち線分）を、平面上に描画する。  
（３）ｉ∈［０，Ｍ］であり、ｊ∈［１，Ｎ］である点（ｉ，ｊ）に関して、点（ｉ，ｊ−１）から点（ｉ，ｊ）までの水平方向の辺を、平面上に描画する。  
（４）読み出し結果のデータの第ｉビットと期待値のデータの第ｊビットが等しいならば、点（ｉ−１，ｊ−１）から点（ｉ，ｊ）までの斜め方向の辺を、平面上に描画する。
【０３６１】
メモリコントローラ２は、上記の編集グラフを得るための手順（１）〜（４）により描画された多数の辺（線分）から、点（０，０）から点（Ｍ，Ｎ）までを結ぶ最短経路８１を構成する辺を特定する。点（０，０）から点（Ｍ，Ｎ）までを結ぶ多数の経路から、最短の距離を有する経路を検索するために、メモリコントローラ２には様々なアルゴリズムを適用でき、例えばＷｕアルゴリズムが適用される。そして、最短の距離を有する複数の最短経路の候補が得られた場合、メモリコントローラ２は、それら複数の候補から、斜め方向の辺をより多く含む経路を最短経路８１として選択する。
【０３６２】
点（０，０）から点（Ｍ，Ｎ）までを結ぶ経路を構成する各辺は、読み出し結果のデータを期待値のデータと一致させるための変更内容を表す。
【０３６３】
編集グラフを構成する複数の辺の内、点（ｉ，ｊ）を終点とする１つの辺は、  
（ａ）斜め方向の辺であるならば、読み出し結果のデータの第ｉビットと期待値のデータの第ｊビットとが一致することを示し、  
（ｂ）水平方向の辺であるならば、読み出し結果のデータの第ｉビットの後に期待値のデータの第ｊビットを挿入することを示し、  
（ｃ）垂直方向の辺であるならば、読み出し結果のデータの第ｉビットを削除すること示す。
【０３６４】
図５９に示す最短経路８１では、点（２，１）を終点とする垂直方向の辺８１１によって、読み出し結果のデータの第２ビットを削除することが示され、点（１２，１２）を終点とする水平方向の辺８１２によって、読み出し結果のデータの第１２ビットの後に期待値のデータの第１２ビットを挿入することが示されている。
【０３６５】
したがって図６０に示すように、読み出し結果のデータの第２ビットを削除し、読み出し結果のデータの第１２ビットの後に期待値のデータの第１２ビットを挿入することにより、読み出し結果のデータを期待値のデータと一致させることができる。読み出し結果のデータの第２ビットを削除することは、読み出し結果のデータの第３ビット以降のビット群を、下位ビットから上位ビットへの方向（図６０では左方向）に１ビット分シフトすることに相当し得る。
【０３６６】
さらに、図５９に示す最短経路８１を構成する辺から、支配的な（主要な）斜め方向の辺８１３が特定される。この辺８１３は、始点（２，１）から終点（１２，１１）までの辺である。点（０，０）から点（Ｍ，Ｎ）までの対角線８２に対する、この支配的な斜め方向の辺８１３のずれは、シフトエラーを訂正するためのシフト量を表す。つまり、最短経路８１に含まれる辺８１３は、対角線８２との比較により、読み出し結果のデータの第２ビットを起点として、下方向（上位ビットから下位ビットへの方向）に１ビット分のシフトエラーが発生していることを表している。
【０３６７】
したがって図６１に示すように、読み出し結果のデータの第３ビット以降のビット群を、下位ビットから上位ビットへの方向（図６１では左方向）に１ビット分シフトしたならば、このビット群に発生しているエラーを１箇所に削減できる。
【０３６８】
また図６２から図６６を参照して、あるＭＭＬ１０から読み出された複数ビットのデータに１つのシフトエラーが発生していると判別される第２の例について説明する。このシフトエラーは、リード動作時の過剰シフトに起因して発生するシフトエラーか、あるいはライド動作時のシフト不足に起因して発生するシフトエラーである。図５５および図５６を参照して上述した例と同様に、ＭＭＬ１０が１３個の磁区を含み、これら１３個の磁区を用いて１２ビットのデータが格納されていることを想定する。
【０３６９】
図６２は、期待値とシフトエラーが発生している場合の読み出し結果とを示す。期待値には、ＭＭＬ１０に記憶されているべき理想的な記憶値と、それに対応するデータとが示されている。シフトエラーが発生している場合の読み出し結果には、ＭＭＬ１０から実際に読み出された記憶値と、それに対応するデータと、各データのエラー判定結果とが示されている。
【０３７０】
読み出されたＭＭＬ１０上の記憶値では、磁区３の磁化方向Ｎが削除されたことにより、本来、磁区４から磁区１２に設定されるべき磁化方向が、それぞれ磁区３から磁区１１に設定されている。また、磁区１２に磁化方向Ｓが設定されている。
【０３７１】
磁区３の磁化方向Ｎの削除は、例えば、磁区３の磁化方向を読み出すための読み出し動作に含まれるシフト動作（すなわち下位レイヤから上位レイヤへの方向のシフト動作）が過剰であったこと、磁区３の磁化方向を書き込むための書き込み動作に含まれるシフト動作（すなわち上位レイヤから下位レイヤへの方向のシフト動作）が不足したことによって発生し得る。
【０３７２】
また読み出されたＭＭＬ１０上の記憶値に基づく１２ビットのデータ（読み出し結果のデータ）を、対応する記憶値が読み出された順に、第１ビットから第１２ビットまでのデータとすると、第３ビット、第５ビット、第７ビット、第８ビット、および第９ビットのデータに誤りが発生している。つまり、図６３に示すように、読み出された１２ビットのデータには、１つの記憶値にランダムエラーが発生したことに応じて連続する２ビットのデータに誤りが発生するというランダムエラーに対応する規則的なエラーではなく、不規則なエラーが発生している。
【０３７３】
図６４は、読み出し結果のデータと期待値のデータとに基づく編集グラフから取得された最短経路８５の例を示す。メモリコントローラ２は、上記の編集グラフを得るための手順（１）〜（４）により描画された多数の辺（線分）から、点（０，０）から点（Ｍ，Ｎ）までを結ぶ最短経路８５を構成する辺を特定する。最短経路８５を得る方法については図５９を参照して上述した通りである。
【０３７４】
図６４に示す最短経路８５では、  
点（３，２）を終点とする垂直方向の辺８５２によって、読み出し結果のデータの第３ビットを削除することと、  
点（３，３）を終点とする水平方向の辺８５１によって、読み出し結果のデータの第３ビットの後に期待値のデータの第３ビットを挿入することと、  
点（３，４）を終点とする水平方向の辺８５３によって、読み出し結果のデータの第３ビットの後に期待値のデータの第４ビットを挿入することと、  
点（１２，１２）を終点とする垂直方向の辺８５４によって、読み出し結果のデータの第１２ビットを削除することとが示されている。
【０３７５】
したがって図６５に示すように、読み出し結果のデータの第３ビットを削除し、（削除した）読み出し結果のデータの第３ビットの後に期待値のデータの第３ビットを挿入し、読み出し結果のデータの第３ビットの後に期待値のデータの第４ビットを挿入することにより、読み出し結果のデータを期待値のデータと一致させることができる。これらの１ビットの削除および２ビットの挿入は、読み出し結果のデータの第４ビット以降のビット群を、上位ビットから下位ビットへの方向（図６５では右方向）に１ビット分シフトすることに相当し得る。
【０３７６】
さらに、図６４に示す最短経路８５を構成する辺から、支配的な斜め方向の辺８５５が特定される。この辺８５５は、始点（３，４）から終点（１１，１２）までの辺である。点（０，０）から点（Ｍ，Ｎ）までの対角線８６に対する、この支配的な斜め方向の辺８５５のずれは、シフトエラーを訂正するためのシフト量を表す。つまり、最短経路８５に含まれる辺８５５は、対角線８６との比較により、読み出し結果のデータの第３ビットを起点として、上方向（下位ビットから上位ビットへの方向）に１ビット分のシフトエラーが発生していることを表している。
【０３７７】
したがって図６６に示すように、読み出し結果のデータの第４ビット以降のビット群を、上位ビットから下位ビットへの方向（図６６では右方向）に１ビット分シフトしたならば、このビット群に発生しているエラーを１箇所に削減できる。
【０３７８】
また図６７は、読み出し結果のデータと期待値のデータとに基づく編集グラフから取得された最短経路に基づいて、シフトエラーおよびランダムエラーが判別される例を示す。
【０３７９】
図６７に示すように、最短経路７１に含まれる斜め方向の辺７１Ａは、読み出し結果のデータと期待値のデータとが一致しているので、ランダムエラーとシフトエラーのいずれも発生していないと判別される。最短経路７１の水平方向の辺７１Ｂは、ランダムエラーか、あるいは読み出し結果のデータを右（上位ビットから下位ビットへの方向）に１ビット分シフトすれば期待値のデータと一致するシフトエラーの先頭であると判別される。最短経路７１の垂直方向の辺７１Ｃは、ランダムエラーか、あるいは読み出し結果のデータを左（下位ビットから上位ビットへの方向）に１ビット分シフトすれば期待値のデータと一致するシフトエラーの先頭と判別される。
【０３８０】
最短経路７２は、読み出し結果のデータを右（上位ビットから下位ビットへの方向）に１ビット分シフトすれば期待値のデータと一致するシフトエラーと判別される。また、最短経路７３は、読み出し結果のデータを左（下位ビットから上位ビットへの方向）に１ビット分シフトすれば期待値のデータと一致するシフトエラーと判別される。
【０３８１】
図６８は、１箇所のシフトエラーに加えて、１箇所のランダムエラーがさらに発生している読み出し結果の例を示す。図６８に示す例では、図５６を参照して上述した例と同様に、磁区３に磁化方向Ｓが追加されたことにより、本来、磁区３から磁区１１に設定されるべき磁化方向が、それぞれ磁区４から磁区１２に設定されると共に、本来、磁区１２に設定されるべき磁化方向Ｎが失われるシフトエラーが発生している。その後、磁区７に設定されていた磁化方向Ｎが磁化方向Ｓに反転するランダムエラーが発生している。
【０３８２】
図６９は、読み出し結果のデータと期待値のデータとに基づく編集グラフから取得された最短経路に基づいて、シフトエラーおよびランダムエラーが判別される例を示す。
【０３８３】
図６９（Ａ）は、シフトエラーのみが発生した時点の読み出し結果のデータと期待値のデータとに基づく編集グラフから取得された最短経路７５を示す。メモリコントローラ２は、対角線７７に対する、この最短経路７５に含まれる支配的な斜め方向の辺７５１のずれに基づいて、読み出し結果のデータを左（下位ビットから上位ビットへの方向）に１ビット分シフトすれば期待値のデータと一致するシフトエラーが発生していると判別できる。
【０３８４】
次いで、図６９（Ｂ）は、シフトエラーに加えてランダムエラーが発生した時点の読み出し結果のデータと期待値のデータとに基づく編集グラフから取得された最短経路７６を示す。この最短経路７６には、対角線７７に対して同一のずれを有する２つの斜め方向の辺７６１，７６２が含まれ、これら２つの辺７６１，７６２を切断するように、垂直方向の辺と水平方向の辺とが含まれている。メモリコントローラ２は、２つの斜め方向の辺７６１，７６２の少なくとも一方を、最短経路７６に含まれる支配的な斜め方向の辺として選択する。そして、メモリコントローラ２は、対角線７７に対する支配的な斜め方向の辺７６１，７６２のずれに基づいて、読み出し結果のデータを左（下位ビットから上位ビットへの方向）に１ビット分シフトすれば期待値のデータと一致するシフトエラーが発生していると判別できる。つまり、シフトエラーに加えてランダムエラーが発生している場合にも、最短経路７６から、できるだけ長い斜め方向の辺７６１，７６２が特定されるようにすることにより、読み出し結果のデータに発生したシフトエラーを推定できる。
【０３８５】
本例では、２つの支配的な斜め方向の辺７６１，７６２がいずれも、読み出し結果のデータを左に１ビット分シフトすれば期待値のデータと一致するシフトエラーが発生していると判別される場合について示した。もし、これら２つの支配的な斜め方向の辺７６１，７６２がシフトしている方向やその量がそれぞれ異なるならば、メモリコントローラ２は、辺７６１に対応する第１ビット群と辺７６２に第２ビット群とに対してそれぞれ異なるシフトを行う。つまり、メモリコントローラ２は、対角線７７に対する辺７６１のずれに基づく、ある方向および量で第１ビット群をシフトし、対角線７７に対する辺７６２のずれに基づく、別の方向および量で第２ビット群をシフトする。
【０３８６】
以上により、あるＭＭＬ１０から読み出された読み出し結果のデータのビット群にシフトエラーが発生していることを判別できると共に、そのシフトエラーを訂正するためのシフト量（すなわちシフトされる方向およびビット数）を決定できる。メモリコントローラ２は、このシフトエラーについて、シフトエラーが発生しているＭＭＬ１０を特定するための情報と、シフトエラーを訂正するためのシフト量（例えば下位ビットから上位ビットへの方向に１ビット分シフトすること）を示す情報とを用いて、シフトエラーテーブル２３５を更新する。メモリコントローラ２は、例えば、これら情報を含むエントリをシフトエラーテーブル２３５に追加してもよいし、これら情報を用いて既にあるエントリを更新してもよい。
【０３８７】
そして、シフトエラーテーブル２３５に示される情報に、より下位のフレームの読み出し結果のデータを適応させることにより、下位のフレームのデータに伝播したシフトエラーの影響を解消できる。これにより、例えばデータ部が最終的に格納されるＭＭＬ１０内の位置に応じて異なるエラー訂正能力を有するＥＣＣを付加する方法を用いることなく、エラーを訂正できる可能性を高めることができる。
【０３８８】
また、コンパクションのソースブロックから読み出されたデータを、シフトエラーテーブル２３５に示される情報に適応させれば、書き込み余地を増やしながら、データを訂正できる。つまり、シフトエラーテーブル２３５を用いたシフトエラーの訂正と、ＥＣＣを用いた誤り訂正とを併用して訂正されたデータを、デスティネーションブロックに書き込むことができる。なお、シフトエラーテーブル２３５に示される情報は、コンパクション時に読み出されたデータに限らず、ホスト４によるリード要求に応じて読み出されたデータにも適応できる。なおコンパクションは、フリーブロック率（またはフリーブロック数）が閾値未満になった場合や、逆引きＬＵＴ２３２に含まれる書き込み時刻を定期的に確認し、書き込み時刻が閾値よりも古い時刻になった場合に、開始され得る。
【０３８９】
以上説明したように、第２実施形態は、データの書き込みおよび読み出しを後入れ先出し方式で行う不揮発性メモリの制御に有用である。不揮発性メモリ３は、１つ以上のＭＭＬ１０をそれぞれ含む複数のブロックを備え、１つ以上のＭＭＬ１０に含まれる複数のレイヤにそれぞれ格納されているデータを最上位のレイヤから最下位のレイヤに向かう第１の方向または第１の方向とは逆の第２の方向にレイヤ単位でシフトさせることによって、各ブロックに対するデータの書き込みおよび読み出しを後入れ先出し方式で行う。複数のブロックの各々は、隣接するレイヤの集合をそれぞれ含むように論理的に区分された複数のフレームを含む。メモリコントローラ２は、複数のブロックの内の１つのブロックに含まれる複数のフレームの内、第１データ部および第１ＥＣＣを含む第１フレームと、第２データ部および第２ＥＣＣを含む第２フレームとを読み出す。メモリコントローラ２は、第１ＥＣＣを用いて第１データ部に対して誤り訂正処理を行い、この誤り訂正処理において訂正された誤りが、複数のＭＭＬ１０の内の第１ＭＭＬ１０で発生していた場合、第１ＭＭＬ１０内の第１レイヤに格納されたデータを、第１ＭＭＬ１０内の第２レイヤに格納されたデータで置き換えることによって、第２データ部を訂正する。
【０３９０】
このように、第１ＥＣＣを用いて第１データ部に対して行われた誤り訂正処理の結果に基づき、第１データ部で発生していた誤りが学習され、この学習結果に第２データ部を適応させる。これにより、第２ＥＣＣを用いた誤り訂正処理とは別の手段で、第２データ部に発生している誤りを低減できる。
【０３９１】
また、第１および第２実施形態に記載された様々な機能の各々は、回路（処理回路）によって実現されてもよい。処理回路の例には、中央処理装置（ＣＰＵ）のような、プログラムされたプロセッサが含まれる。このプロセッサは、メモリに格納されたコンピュータプログラム（命令群）を実行することによって、記載された機能それぞれを実行する。このプロセッサは、電気回路を含むマイクロプロセッサであってもよい。処理回路の例には、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、マイクロコントローラ、コントローラ、他の電気回路部品も含まれる。これら実施形態に記載されたＣＰＵ以外の他のコンポーネントの各々もまた処理回路によって実現されてもよい。
【０３９２】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０３９３】
１…メモリシステム、２…メモリコントローラ、３…不揮発性メモリ、２１…ホストインタフェース、２２…メモリインタフェース、２３…制御部、２４…符号化／復号部（Ｅｎｃｏｄｅｒ／Ｄｅｃｏｄｅｒ）、２５…データバッファ、２８…ＳＲＡＭ。
【図１】
2020149223.tif 000003
【図２】
2020149223.tif 000004
【図３】
2020149223.tif 000005
【図４】
2020149223.tif 000006
【図５】
2020149223.tif 000007
【図６】
2020149223.tif 000008
【図７】
2020149223.tif 000009
【図８】
2020149223.tif 000010
【図９】
2020149223.tif 000011
【図１０】
2020149223.tif 000012
【図１１】
2020149223.tif 000013
【図１２】
2020149223.tif 000014
【図１３】
2020149223.tif 000015
【図１４】
2020149223.tif 000016
【図１５】
2020149223.tif 000017
【図１６】
2020149223.tif 000018
【図１７】
2020149223.tif 000019
【図１８】
2020149223.tif 000020
【図１９】
2020149223.tif 000021
【図２０】
2020149223.tif 000022
【図２１】
2020149223.tif 000023
【図２２】
2020149223.tif 000024
【図２３】
2020149223.tif 000025
【図２４】
2020149223.tif 000026
【図２５】
2020149223.tif 000027
【図２６】
2020149223.tif 000028
【図２７】
2020149223.tif 000029
【図２８】
2020149223.tif 000030
【図２９】
2020149223.tif 000031
【図３０】
2020149223.tif 000032
【図３１】
2020149223.tif 000033
【図３２】
2020149223.tif 000034
【図３３】
2020149223.tif 000035
【図３４】
2020149223.tif 000036
【図３５】
2020149223.tif 000037
【図３６】
2020149223.tif 000038
【図３７】
2020149223.tif 000039
【図３８】
2020149223.tif 000040
【図３９】
2020149223.tif 000041
【図４０】
2020149223.tif 000042
【図４１】
2020149223.tif 000043
【図４２】
2020149223.tif 000044
【図４３】
2020149223.tif 000045
【図４４】
2020149223.tif 000046
【図４５】
2020149223.tif 000047
【図４６】
2020149223.tif 000048
【図４７】
2020149223.tif 000049
【図４８】
2020149223.tif 000050
【図４９】
2020149223.tif 000051
【図５０】
2020149223.tif 000052
【図５１】
2020149223.tif 000053
【図５２】
2020149223.tif 000054
【図５３】
2020149223.tif 000055
【図５４】
2020149223.tif 000056
【図５５】
2020149223.tif 000057
【図５６】
2020149223.tif 000058
【図５７】
2020149223.tif 000059
【図５８】
2020149223.tif 000060
【図５９】
2020149223.tif 000061
【図６０】
2020149223.tif 000062
【図６１】
2020149223.tif 000063
【図６２】
2020149223.tif 000064
【図６３】
2020149223.tif 000065
【図６４】
2020149223.tif 000066
【図６５】
2020149223.tif 000067
【図６６】
2020149223.tif 000068
【図６７】
2020149223.tif 000069
【図６８】
2020149223.tif 000070
【図６９】
2020149223.tif 000071