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