(57)【特許請求の範囲】
【請求項１】
データの読み書きを制御する記憶制御装置において、
複数のデータブロックの中から、データパターンが同じデータブロックの数を示す計数値を複数のデータパターンのそれぞれについて計数し、前記複数のデータパターンのそれぞれについて計数値順に付与された順位を示す順位情報と、前記複数のデータブロックとを記憶装置に書き込む書き込み部と、
前記複数のデータブロックのうち一のデータブロックを前記記憶装置から読み出したとき、前記一のデータブロックのエラーを検出した場合に、前記複数のデータパターンの中から前記順位情報に基づいて選択したデータパターンを用いて前記一のデータブロックを置き換える読み出し部と、
を有する記憶制御装置。
【請求項２】
前記書き込み部は、前記複数のデータブロックのそれぞれにエラー検出符号を付加して前記記憶装置に書き込み、
前記読み出し部は、前記一のデータブロックに付加された前記エラー検出符号を用いて、前記一のデータブロックのエラーを検出する、
請求項１記載の記憶制御装置。
【請求項３】
前記エラー検出符号は、パリティビットである、
請求項２記載の記憶制御装置。
【請求項４】
前記書き込み部は、前記複数のデータパターンのそれぞれに対して、算出されるパリティビットを対応付けた対応情報を前記記憶装置に書き込み、
前記読み出し部は、前記一のデータブロックのエラーを検出した場合、前記複数のデータパターンのうち、前記一のデータブロックに付加されたパリティビットと同じパリティビットが前記対応情報に対応付けられ、かつ、前記順位情報が示す順位が最も高いデータパターンを用いて、前記一のデータブロックを置き換える、
請求項３記載の記憶制御装置。
【請求項５】
前記読み出し部は、前記一のデータブロックのエラーを検出した場合、前記複数のデータブロックのうち、前記一のデータブロックと１ビットのみビット値が異なり、かつ、データパターンを基に算出される算出エラー検出符号が前記一のデータブロックに付加された前記エラー検出符号と同じであり、かつ、前記順位情報が示す順位が最も高いデータパターンを用いて、前記一のデータブロックを置き換える、
請求項２または３記載の記憶制御装置。
【請求項６】
データの読み書きを制御するストレージ装置において、
記憶装置と、
複数のデータブロックの中から、データパターンが同じデータブロックの数を示す計数値を複数のデータパターンのそれぞれについて計数し、前記複数のデータパターンのそれぞれについて計数値順に付与された順位を示す順位情報と、前記複数のデータブロックとを前記記憶装置に書き込む書き込み部、および、
前記複数のデータブロックのうち一のデータブロックを前記記憶装置から読み出したとき、前記一のデータブロックのエラーを検出した場合に、前記複数のデータパターンの中から前記順位情報に基づいて選択したデータパターンを用いて前記一のデータブロックを置き換える読み出し部、
を備える記憶制御装置と、
を有するストレージ装置。
【請求項７】
データの読み書きを制御する記憶制御方法において、
コンピュータが、
複数のデータブロックの中から、データパターンが同じデータブロックの数を示す計数値を複数のデータパターンのそれぞれについて計数し、前記複数のデータパターンのそれぞれについて計数値順に付与された順位を示す順位情報と、前記複数のデータブロックとを記憶装置に書き込み、
前記複数のデータブロックのうち一のデータブロックを前記記憶装置から読み出したとき、前記一のデータブロックのエラーを検出した場合に、前記複数のデータパターンの中から前記順位情報に基づいて選択したデータパターンを用いて前記一のデータブロックを置き換える、
記憶制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は記憶制御装置、ストレージ装置および記憶制御方法に関する。
【背景技術】
【０００２】
転送されるデータのエラーを検出する技術が一般的に知られている。例えば、パリティビットやＣＲＣ（Cyclic Redundancy Check）などのチェック符号を用いることで、データにエラーがあるか否かを検出できる。そして、データにエラーがあるときには、訂正処理が実行される。
【０００３】
また、訂正処理に関する次のような技術が提案されている。例えば、誤り訂正装置は、復調データの確からしさを示す信頼度情報ビットが所定レベルである復調データを操作して復調データパターンが取り得る可能性のある全ての組合せの復調データパターンを生成する。誤り訂正装置は、復調データパターンに対して誤り訂正を実行する。
【０００４】
また、誤り訂正用の生成多項式による剰余と複数の訂正パターンの表形式のデータを予め作成し、複数の訂正パターンを基に修正した訂正済み候補に対して誤り検知処理を行い、剰余が０となって訂正されたと判定されるまで処理を繰り返す技術が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−３３０９７９号公報
【特許文献２】特開２０００−２６１３２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
近年、記憶装置の容量増加に伴って、書き込んだデータにエラーが発生することが多くなっている。エラーの数が多い場合には、読み出し時にチェック符号を用いて複数ビットエラーを訂正する技術が有効であるが、この技術は複雑で訂正処理時間が長く、読み出し処理の完了までに長い時間がかかるという問題がある。
【０００７】
１つの側面では、本発明は、複数ビットエラーを訂正し得る高速な訂正処理を実現できる記憶制御装置、ストレージ装置および記憶制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの態様では、記憶制御装置が提供される。この記憶制御装置は書き込み部と読み出し部とを有する。書き込み部は、複数のデータブロックの中から、データパターンが同じデータブロックの数を示す計数値を複数のデータパターンのそれぞれについて計数し、複数のデータパターンのそれぞれについて計数値順に付与された順位を示す順位情報を、複数のデータブロックとともに記憶装置に書き込む。読み出し部は、複数のデータブロックのうち一のデータブロックを記憶装置から読み出したとき、一のデータブロックのエラーを検出した場合に、複数のデータパターンの中から順位情報に基づいて選択したデータパターンを用いて一のデータブロックを置き換える。
【０００９】
また、１つの態様では、ストレージ装置が提供される。このストレージ装置は、記憶装置と、記憶制御装置とを備える。また、記憶制御装置は、書き込み部と読み出し部とを有する。書き込み部は、複数のデータブロックの中から、データパターンが同じデータブロックの数を示す計数値を複数のデータパターンのそれぞれについて計数し、複数のデータパターンのそれぞれについて計数値順に付与された順位を示す順位情報を、複数のデータブロックとともに記憶装置に書き込む。読み出し部は、複数のデータブロックのうち一のデータブロックを記憶装置から読み出したとき、一のデータブロックのエラーを検出した場合に、複数のデータパターンの中から順位情報に基づいて選択したデータパターンを用いて一のデータブロックを置き換える。
【００１０】
また、１つの態様では、記憶制御方法が提供される。この記憶制御方法は、コンピュータが複数のデータブロックの中から、データパターンが同じデータブロックの数を示す計数値を複数のデータパターンのそれぞれについて計数し、複数のデータパターンのそれぞれについて計数値順に付与された順位を示す順位情報を、複数のデータブロックとともに記憶装置に書き込み、複数のデータブロックのうち一のデータブロックを記憶装置から読み出したとき、一のデータブロックのエラーを検出した場合に、複数のデータパターンの中から順位情報に基づいて選択したデータパターンを用いて一のデータブロックを置き換える。
【発明の効果】
【００１１】
１つの側面では、複数ビットエラーを訂正し得る高速な訂正処理を実現できる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の記憶制御装置を示す図である。
【図２】第２の実施の形態のストレージシステムを示す図である。
【図３】ＣＭのハードウェア例を示す図である。
【図４】ＮＡＮＤコントローラの機能例を示す図である。
【図５】カウントテーブルの例を示す図である。
【図６】ＮＡＮＤ型フラッシュメモリの記憶領域の構造の例を示す図である。
【図７】書き込み処理の例を示すフローチャートである。
【図８】読み出し処理の例（その１）を示すフローチャートである。
【図９】読み出し処理の例（その２）を示すフローチャートである。
【図１０】第３の実施の形態の読み出し処理の例を示すフローチャートである。
【図１１】第４の実施の形態のカウントテーブルの例を示す図である。
【図１２】第４の実施の形態の書き込み処理の例を示すフローチャートである。
【図１３】第４の実施の形態の読み出し処理の例を示すフローチャートである。
【図１４】第５の実施の形態の読み出し処理の例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の記憶制御装置を示す図である。記憶制御装置１は、記憶装置２に対するデータの読み書きを制御する装置である。記憶装置２は、例えば、ＲＡＭ（Random Access Memory）、フラッシュメモリなどである。なお、記憶制御装置１は、例えば、記憶装置２と一体化されていてもよい。
【００１４】
記憶制御装置１は、書き込み部１ａと読み出し部１ｂを有する。書き込み部１ａおよび読み出し部１ｂは、例えば、それぞれ個別の電子回路として実装される。あるいは、書き込み部１ａと読み出し部１ｂの処理は、プロセッサが所定のプログラムを実行することで実現されてもよい。
【００１５】
書き込み部１ａは、複数のデータブロック３ａ，３ｂ，３ｃ，・・・を有するデータブロック群３を記憶装置２に書き込む際に、次のような処理を実行する。書き込み部１ａは、複数のデータブロック３ａ，３ｂ，３ｃ，・・・の中から、データパターンが同じデータブロックの数を、複数のデータパターンのそれぞれについて計数する。複数のデータパターンとは、データブロック群３に含まれるデータブロックがとり得るデータパターンである。以下、データパターン毎の計数値を「出現数」と記載する。なお、図１の例では、データブロック３ａ，３ｂ，３ｃのデータパターンはそれぞれ「０１０１」、「１１００」、「１０１１」であるとする。
【００１６】
書き込み部１ａは、複数のデータパターンのそれぞれについて出現数順に付与された順位を示す順位情報４を、複数のデータブロック３ａ，３ｂ，３ｃ，・・・とともに記憶装置２に書き込む。図１の例では、順位情報４には、複数のデータパターンが出現数が大きい順にソートされて登録されている。また、図１の例では、「１１００」、「１０１１」、「０１０１」の順に出現順が大きかったものとする。
【００１７】
なお、複数のデータブロック３ａ，３ｂ，３ｃ，・・・は、読み出し時にデータブロック単位でエラーの有無を検出可能な状態で記憶装置２に記憶される。エラーの検出方法は簡単な方法でよく、本実施の形態では、例としてパリティビットを用いた方法が用いられるものとする。例えば、データブロック３ａ，３ｂ，３ｃのそれぞれに対してパリティビット５ａ，５ｂ，５ｃが付加されて記憶装置２に記憶される。
【００１８】
読み出し部１ｂは、記憶装置２に書き込まれた複数のデータブロック３ａ，３ｂ，３ｃ，・・・を読み出す際に、次のような処理を実行する。読み出し部１ｂは、複数のデータブロック３ａ，３ｂ，３ｃ，・・・を読み出す際に、エラーの有無をチェックする。本実施の形態では、データブロック毎に付加されたパリティビットを用いてエラーの有無がチェックされる。ここで、データブロック３ｂからエラーが検出されたとする。
【００１９】
読み出し部１ｂは、複数のデータパターンの中から、順位情報４に基づいて選択したデータパターンを用いて、データブロック３ｂを置き換える。例えば、読み出し部１ｂは、複数のデータパターンの中から、データパターンを基に算出されるパリティビットの値がデータブロック３ｂに付加されたパリティビット５ｂと同じであるデータパターンを特定する。読み出し部１ｂは、特定したデータパターンのうち順位が最も高いデータパターンを用いて、データブロック３ｂを置き換える。図１の例では、「１１００」を用いてデータブロック３ｂが置き換えられる。
【００２０】
ここで、出現数が大きいデータパターンほど、エラーが検出されたデータブロック３ｂの正しいビット列である可能性が高い。そのため、読み出し部１ｂは、順位情報４に基づき、複数のデータパターンの中からできるだけ順位が高いデータパターンを選択し、選択したデータパターンを用いてデータブロック３ｂを置き換える。これにより、高い確率でエラーを訂正できる。しかも、データブロック３ｂにおける１ビットエラーだけでなく、複数ビットエラーも訂正できる可能性がある。
【００２１】
このように、第１の実施の形態によれば、順位情報４に基づいてデータパターンが選択され、選択されたデータパターンを用いてデータブロックが置き換えられる、という単純な処理手順を用いて、データ訂正処理が行われる。したがって、複数ビットエラーを訂正し得る高速な訂正処理を実現できる。
【００２２】
［第２の実施の形態］
図２は、第２の実施の形態のストレージシステムを示す図である。図２に示すストレージシステムは、ストレージ装置１００およびホスト装置４００を含む。ストレージ装置１００とホスト装置４００とは、例えば、ファイバチャネル（ＦＣ：Fibre Channel）やｉＳＣＳＩ（Internet Small Computer System Interface）などを用いたＳＡＮ（Storage Area Network）を介して接続される。
【００２３】
ストレージ装置１００は、ＣＥ（Controller Enclosure）２００およびＤＥ（Device Enclosure）３００を有する。
ＣＥ２００は、ＣＭ（Controller Module）２１０を有する。ＤＥ３００は、複数の記憶装置を搭載する。ＤＥ３００は、記憶装置としてＨＤＤ（Hard Disk Drive）を備えたディスクアレイ装置である。なお、ＤＥ３００に搭載される記憶装置は、ＳＳＤ（Solid State Drive）などの他の種類の記憶装置であってもよい。ＣＭ２１０は、ホスト装置４００からの要求に応じて、ＤＥ３００に搭載されたＨＤＤに対するアクセスを制御する。
【００２４】
次に、ＣＭのハードウェアについて、説明する。
図３は、ＣＭのハードウェア例を示す図である。ＣＭ２１０は、ＣＰＵ（Central Processing Unit）２１１、ＲＡＭ２１２、メモリコントローラ２１３、ＮＡＮＤ型フラッシュメモリ２１４、ＰＣＩｅ（Peripheral Components Interconnect Express）スイッチ２１５、ＣＡ（Channel Adapter）２１６、ＤＩ（Device Interface）２１７、電源供給ユニット２１８、停電時給電ユニット２１９およびＮＡＮＤコントローラ２２０を有する。
【００２５】
ＣＰＵ２１１は、ＣＭ２１０の情報処理を制御する。ＣＰＵ２１１は、複数のプロセッシング要素を含むマルチプロセッサであってもよい。
ＲＡＭ２１２は、ＣＭ２１０の主記憶装置である。ＲＡＭ２１２は、ＣＰＵ２１１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ２１２は、ＣＰＵ２１１による処理に用いる各種データを記憶する。
【００２６】
メモリコントローラ２１３は、ＣＰＵ２１１またはＮＡＮＤコントローラ２２０の指示によりＲＡＭ２１２に格納されている各種データの読み出し、または、ＲＡＭ２１２に対する各種データの書き込みを行う。
【００２７】
ＮＡＮＤ型フラッシュメモリ２１４は、ストレージ装置１００が停電により停止したときに、ＲＡＭ２１２に格納されているデータをバックアップする。
ＰＣＩｅスイッチ２１５は、ＣＰＵ２１１とＣＡ２１６およびＤＩ２１７との間で、データを送受信する。ＣＡ２１６は、ホスト装置４００と通信するためのインタフェースである。ＤＩ２１７は、ＤＥ３００と通信するためのインタフェースである。
【００２８】
電源供給ユニット２１８は、外部から電源電力の供給を受けて、ストレージ装置１００内の各部に対して電力を供給する。停電時給電ユニット２１９は、図示しないバッテリを備える。停電時給電ユニット２１９は、停電などによって電源供給ユニット２１８からの電力供給が停止した場合に、ＲＡＭ２１２、メモリコントローラ２１３、ＮＡＮＤ型フラッシュメモリ２１４およびＮＡＮＤコントローラ２２０にバッテリから電力を供給する。
【００２９】
ＮＡＮＤコントローラ２２０は、ＤＭＡＣ（Direct Memory Access Controller）２２０ａおよびＲＡＭ２２０ｂを有する。ＤＭＡＣ２２０ａは、ＲＡＭ２１２に格納されたデータをＮＡＮＤ型フラッシュメモリ２１４に書き込む書き込み動作や、ＮＡＮＤ型フラッシュメモリ２１４に格納されたデータを読み出してＲＡＭ２１２に書き戻す読み出し動作を実行する。ＤＭＡＣ２２０ａは、例えば、電源供給ユニット２１８からの電力供給が停止したことが停電時給電ユニット２１９から通知されたとき、上記の書き込み動作を実行する。また、ＤＭＡＣ２２０ａは、例えば、電源供給ユニット２１８からの電力供給が再開したことが停電時給電ユニット２１９から通知されたとき、上記の読み出し動作を実行する。なお、ＤＭＡＣ２２０ａは、ＣＰＵ２１１からの指示に応じてＮＡＮＤ型フラッシュメモリ２１４の読み書きを実行してもよい。ＲＡＭ２２０ｂは、ＮＡＮＤ型フラッシュメモリ２１４に格納されるデータを一時的に記憶する。
【００３０】
次に、ＮＡＮＤコントローラが有する機能について説明する。
図４は、ＮＡＮＤコントローラの機能例を示す図である。ＮＡＮＤコントローラ２２０は、記憶部２２１、書き込み部２２２および読み出し部２２３を有する。なお、図４では、ＣＭ２１０が有するＣＰＵ２１１などを省略している。
【００３１】
記憶部２２１は、例えば、ＲＡＭ２２０ｂに確保した記憶領域として実装される。記憶部２２１は、ＲＡＭ２１２から取得されるデータを一時的に記憶する。ここで、ＮＡＮＤ型フラッシュメモリ２１４には、ページ単位でデータの書き込み処理が行われる。例えば、ページのサイズは、１６キロバイトである。記憶部２２１は、ＲＡＭ２１２から取得されるデータが少なくともページ単位のサイズになるまでデータを蓄積する。そして、蓄積されたデータが、ＮＡＮＤ型フラッシュメモリ２１４に格納される。なお、ＮＡＮＤ型フラッシュメモリ２１４からデータを読み出す場合、ページ単位でデータの読み出し処理が行われる。
【００３２】
また、記憶部２２１は、カウントテーブルを記憶する。カウントテーブルには、ＮＡＮＤ型フラッシュメモリ２１４に書き込まれる１ページ分のデータの中に同じデータパターンが出現した出現数を、データパターン毎に保持する情報が登録される。データパターンは、ユニット単位のサイズでカウントされる。例えば、ユニットのサイズは、８ビットである。
【００３３】
書き込み部２２２および読み出し部２２３は、例えば、ＤＭＡＣ２２０ａの一部として実現される。
書き込み部２２２は、電源供給ユニット２１８からの電力供給が停止したとき、ＲＡＭ２１２に格納されているデータをメモリコントローラ２１３を介して読み出し、ＮＡＮＤ型フラッシュメモリ２１４に書き込む。この書き込みは、次のような手順で実行される。
【００３４】
書き込み部２２２は、ＲＡＭ２１２から読み出したデータを、記憶部２２１に一時的に格納する。書き込み部２２２は、記憶部２２１に１ページ分のデータが蓄積されると、それらのデータをＮＡＮＤ型フラッシュメモリ２１４の空きページに書き込む。このとき、書き込み部２２２は、１ページ分のデータについてユニット単位でデータパターンを検出して、同じデータパターンの出現数をユニットがとり得るデータパターン毎に計数し、計数結果をカウントテーブルに登録する。また、書き込み部２２２は、１ページ分のデータに基づいて、ＣＲＣを算出する。また、書き込み部２２２は、ユニット毎にパリティビットを算出する。書き込み部２２２は、算出したパリティビットをユニットに付加してＮＡＮＤ型フラッシュメモリ２１４に書き込む。また、書き込み部２２２は、ＣＲＣとカウントテーブルとを、データの書き込み先のページに対応付けて、ＮＡＮＤ型フラッシュメモリ２１４に書き込む。
【００３５】
読み出し部２２３は、電源供給ユニット２１８からの電力供給が再開されたとき、ＮＡＮＤ型フラッシュメモリ２１４に格納されたデータを読み出し、メモリコントローラ２１３を介してＲＡＭ２１２に書き戻す。ＮＡＮＤ型フラッシュメモリ２１４からのページ毎のデータ読み出し時には、次のようなエラー訂正処理が実行される。
【００３６】
読み出し部２２３は、ＮＡＮＤ型フラッシュメモリ２１４の１つのページからのデータ読み出しの前に、このページに対応付けられているＣＲＣとカウントテーブルとをＮＡＮＤ型フラッシュメモリ２１４から読み出し、記憶部２２１に格納する。次に、読み出し部２２３は、ページからユニットおよびパリティビットを読み出し、記憶部２２１に格納する。読み出し部２２３は、読み出した１ページ分のデータ、すなわちユニットの集合のエラーチェックを、ＣＲＣを用いて実行する。エラーが含まれている場合、読み出し部２２３は、パリティビットを用いてエラーのあるユニットを特定し、カウントテーブルに登録されているデータパターンを出現数の高い順に選択し、選択したデータパターンを用いてエラーを訂正できるかを試みる。読み出し部２２３は、選択したデータパターンを基に算出されるパリティビットと、エラーのあるユニットに付加されているパリティビットとが一致するか否かで訂正できるかを判定する。読み出し部２２３は、訂正できると判定した場合、エラーのあるユニットをデータパターンに置き換えて、エラーを訂正する。
【００３７】
次に、カウントテーブルについて詳細に説明する。
図５は、カウントテーブルの例を示す図である。カウントテーブル２２１ａは、記憶部２２１においてページ毎に生成され、ＮＡＮＤ型フラッシュメモリ２１４に格納される。カウントテーブル２２１ａは、項番、データパターン、出現数の項目を含む。
【００３８】
項番の項目には、レコードを識別する情報が登録される。データパターンの項目には、データパターンが登録される。出現数の項目には、ページにおいてデータパターンが出現した回数が登録される。また、カウントテーブル２２１ａには、ユニットがとり得る全てのデータパターンに対応するレコードが登録される。また、カウントテーブル２２１ａがＮＡＮＤ型フラッシュメモリ２１４に格納される段階では、レコードは出現数が多い順にソートされている。この段階では、項番は出現数の順位を示す。例えば、カウントテーブル２２１ａには、項番が“１”、データパターンが“０ｘＦＦ”、出現数が“０ｘ８０”という情報が登録される。このカウントテーブル２２１ａがレコードのソート後の状態であるとすると、これは、出現回数が最も高いデータパターンが“０ｘＦＦ”であり、当該データパターンが出現した回数が“０ｘ８０”であることを示す。このようなカウントテーブル２２１ａが格納されることで、各データパターンに対して出現数に応じて付与された順位を示す情報が、ページに対応づけて保存される。
【００３９】
なお、本実施の形態では、ユニットは８ビットであるとする。図５では、データパターンを１６進数で表記しているが、実際のデータパターンは８ビットのビット列である。
図６は、ＮＡＮＤ型フラッシュメモリの記憶領域の構造の例を示す図である。ＮＡＮＤ型フラッシュメモリ２１４には、ＤＡＴＡエリアとＳＰＡＲＥエリアとがページ毎に割り当てられている。ＤＡＴＡエリアは、通常の書き込みデータが書き込まれる領域であり、本実施の形態では、パリティビットが付加されたユニットが格納される。ＳＰＡＲＥエリアは、エラー訂正情報や制御情報の格納のために割り当てられた領域であり、本実施の形態では、ＣＲＣとカウントテーブル２２１ａが格納される。
【００４０】
次に、ＲＡＭ２１２に格納されている書き込みデータをＮＡＮＤ型フラッシュメモリ２１４に格納するまでの処理について、詳細に説明する。
図７は、書き込み処理の例を示すフローチャートである。図示しないが、書き込み部２２２は、ＲＡＭ２１２からデータを順次読み出し、記憶部２２１に格納する。書き込み部２２２は、この格納処理と並行して、記憶部２２１に格納されたデータ量を監視しながら図７の処理を実行する。なお、記憶部２２１へのデータの格納は、例えば、ＣＰＵ２１１からの指示に応じて行われてもよい。以下、図７に示す処理をステップ番号に沿って説明する。
【００４１】
（Ｓ１１）書き込み部２２２は、ｍに０を代入する。ｍは、ユニットの番号を示す変数であり、「ユニット（ｍ）」は、ｍ番目のユニットを示す。ここで、１ページ分のユニットは、０〜Ｎ番目まで存在するものとする。
【００４２】
（Ｓ１２）書き込み部２２２は、記憶部２２１に１ユニット分のデータが蓄積されると、記憶部２２１からユニット（ｍ）を読み出す。また、このユニット（ｍ）に対応するカウントテーブル２２１ａを生成して、記憶部２２１に格納する。生成されたカウントテーブル２２１ａには、項番とデータパターンのみ登録されている。
【００４３】
（Ｓ１３）書き込み部２２２は、カウントテーブル２２１ａを参照し、ユニット（ｍ）と同じデータパターンを特定する。
（Ｓ１４）書き込み部２２２は、カウントテーブル２２１ａのレコードのうち、ステップＳ１３で特定したデータパターンに対応するレコードの出現数に１を加算する。例えば、ユニット（ｍ）のデータのデータパターンが“０ｘＦＦ”である場合、書き込み部２２２は、カウントテーブル２２１ａのデータパターンの項目“０ｘＦＦ”に対応する出現数に１を加算する。
【００４４】
（Ｓ１５）書き込み部２２２は、ｍがＮであるか否かを判定する。ｍがＮの場合、処理をステップＳ１７に進める。ｍがＮでない場合、処理をステップＳ１６に進める。
（Ｓ１６）書き込み部２２２は、ｍに１を加算する。そして、処理をステップＳ１２に進める。
【００４５】
（Ｓ１７）書き込み部２２２は、カウントテーブル２２１ａのレコードを、出現数が多い順にソートする。また、書き込み部２２２は、ソートした後、カウントテーブル２２１ａの項番の項目を出現数の高い順に番号をつけ直す。
【００４６】
（Ｓ１８）書き込み部２２２は、１ページ分のユニットに基づいて、ＣＲＣを算出する。例えば、ＣＲＣは、１ページ分のユニットのビット列を所定の定数で割った余りである。
【００４７】
（Ｓ１９）書き込み部２２２は、ユニット毎にパリティビットを算出する。書き込み部２２２は、算出したパリティビットをユニット毎に付加する。そして、書き込み部２２２は、パリティビットが付加されたユニットを含む書き込みデータをＮＡＮＤ型フラッシュメモリ２１４のＤＡＴＡエリアに書き込む。
【００４８】
（Ｓ２０）書き込み部２２２は、ステップＳ１８で算出したＣＲＣとカウントテーブル２２１ａとを、ＮＡＮＤ型フラッシュメモリ２１４の領域のうち、ステップＳ１９での書き込み先のＤＡＴＡエリアに対応するＳＰＡＲＥエリアに書き込む。そして、処理を終了する。
【００４９】
以上の図７の処理により、パリティビットが付加された１ページ分のユニットが、そのページに対応するカウントテーブル２２１ａおよびＣＲＣとともにＮＡＮＤ型フラッシュメモリ２１４に書き込まれる。なお、図７の処理では、記憶部２２１にデータが１ユニット分蓄積される毎にステップＳ１２〜Ｓ１４の処理が実行される。これにより、データパターンの出現数の計数処理がデータ書き込みの処理時間全体に与える影響を小さくすることができる。
【００５０】
次に、ＮＡＮＤ型フラッシュメモリ２１４に格納されたデータを読み出すときの処理について説明する。
図８は、読み出し処理の例（その１）を示すフローチャートである。読み出し部２２３は、ＮＡＮＤ型フラッシュメモリ２１４に格納されたデータをページ単位で読み出す。図８は、ページ単位の処理を示す。なお、ＮＡＮＤ型フラッシュメモリ２１４からのデータ読み出しは、例えば、ＣＰＵ２１１からの指示に応じて行われてもよい。以下、図８に示す処理をステップ番号に沿って説明する。
【００５１】
（Ｓ２１）読み出し部２２３は、ＮＡＮＤ型フラッシュメモリ２１４の対象ページに対応するＤＡＴＡエリアから、１ページ分のユニットをパリティビットとともに記憶部２２１に読み出す。また、読み出し部２２３は、このＤＡＴＡエリアに対応するＳＰＡＲＥエリアから、ＣＲＣとカウントテーブル２２１ａとを記憶部２２１に読み出す。
【００５２】
（Ｓ２２）読み出し部２２３は、ｍに０を代入する。また、読み出し部２２３は、ｎに１を代入する。ｎは、カウントテーブル２２１ａの項番を示す変数であり、「データパターン（ｎ）」は、項番ｎのレコードに登録されたデータパターンを示す。
【００５３】
（Ｓ２３）読み出し部２２３は、ステップＳ２１で読み出したＣＲＣを用いて、ステップＳ２１で読み出した１ページ分のユニットにエラーが含まれているか否かを判定する。エラーを検出した場合、処理をステップＳ２４に進める。エラーを検出しなかった場合、処理をステップＳ３５に進める。
【００５４】
（Ｓ２４）読み出し部２２３は、記憶部２２１からユニット（ｍ）を読み出す。
（Ｓ２５）読み出し部２２３は、ユニット（ｍ）に付加されているパリティビットを用いて、ユニット（ｍ）にエラーが含まれているか否かを判定する。エラーを検出した場合、処理をステップＳ２６に進める。エラーを検出しなかった場合、処理をステップＳ３１に進める。
【００５５】
（Ｓ２６）読み出し部２２３は、ステップＳ２１で読み出したカウントテーブル２２１ａからデータパターン（ｎ）を取得する。
（Ｓ２７）読み出し部２２３は、データパターン（ｎ）を基にパリティビットを算出する。読み出し部２２３は、算出したパリティビットと、ユニット（ｍ）に付加されているパリティビットとが同じであるか否かを判定する。同じ場合、処理をステップＳ２９に進める。異なる場合、処理をステップＳ２８に進める。
【００５６】
（Ｓ２８）読み出し部２２３は、ｎに１を加算する。そして、処理をステップＳ２６に進める。
（Ｓ２９）読み出し部２２３は、記憶部２２１に記憶されたユニット（ｍ）のビット列をデータパターン（ｎ）に置き換えて、エラーを訂正する。
【００５７】
（Ｓ３０）読み出し部２２３は、ｎに１を代入する。そして、処理をステップＳ３１に進める。
図９は、読み出し処理の例（その２）を示すフローチャートである。以下、図９に示す処理をステップ番号に沿って説明する。
【００５８】
（Ｓ３１）読み出し部２２３は、ｍがＮであるか否かを判定する。ｍがＮの場合、処理をステップＳ３３に進める。ｍがＮでない場合、処理をステップＳ３２に進める。
（Ｓ３２）読み出し部２２３は、ｍに１を加算する。そして、処理をステップＳ２４に進める。
【００５９】
（Ｓ３３）読み出し部２２３は、ステップＳ２１で読み出したＣＲＣを用いて、記憶部２２１に記憶されている、訂正後の１ページ分のユニットにエラーが含まれているか否かを判定する。エラーを検出した場合、処理をステップＳ３４に進める。エラーを検出しなかった場合、読み出し部２２３は、各ユニットに付加されているパリティビットを削除し、読み出し要求元に書き込みデータを送信する。そして、処理をステップＳ３５に進める。
【００６０】
（Ｓ３４）読み出し部２２３は、読み出し要求元にエラー通知を送信する。そして、処理を終了する。
（Ｓ３５）読み出し部２２３は、記憶部２２１に記憶されている１ページ分のユニットを、メモリコントローラ２１３を介してＲＡＭ２１２に書き込む。また、読み出し部２２３は、記憶部２２１に格納したユニット、パリティビット、ＣＲＣおよびカウントテーブル２２１ａを消去する。
【００６１】
以上の図８〜９の処理によれば、読み出し部２２３は、ＮＡＮＤ型フラッシュメモリ２１４から読み出したユニットのエラーを検出した場合、該当ページにおける出現数の高いデータパターンから順に選択する。そして、読み出し部２２３は、パリティビットが、ＮＡＮＤ型フラッシュメモリ２１４から読み出したパリティビットと一致するデータパターンを用いて、ユニットのビット列を置き換えることで、ユニットのエラーを訂正する。
【００６２】
この訂正処理では、出現数の高いデータパターンほど、エラーが検出されたユニットの正しい値である可能性が高いという考え方が用いられている。この考え方に基づく上記訂正処理により、出現数に基づいて選択したデータパターンを用いてユニットのビット列を置き換えるという単純な処理手順で、エラーが訂正され得る。また、このエラー訂正処理によれば、訂正し得るビット数に制限はなく、２ビット以上のエラーを訂正することもできる。
【００６３】
図８のステップＳ２７でパリティビットが同じと判定される確率は、１／２である。このため、ページ全体での平均で見ると、ユニット毎の処理ではステップＳ２５で１回とステップＳ２７で２回の合計３回程度、パリティビットの計算が行われる。すなわち、ユニット当たり３回のパリティビット計算とパターン置き換え処理とによって、エラーが訂正され得る。
【００６４】
したがって、少なくとも、ＥＣＣを用いて２ビット以上のエラーを訂正可能なエラー訂正処理と比較して、エラー訂正処理の負荷を軽減できる。その結果、エラー訂正処理の速度を向上させ、その処理時間を短縮できる。すなわち、エラー訂正精度よりエラー訂正速度を重視した多ビットエラーの訂正処理を実現できる。また、ＥＣＣを用いて１ビットエラーを訂正可能なほとんどのエラー訂正処理と比較した場合、ユニットのビット数が大きいほどエラー訂正処理の負荷を軽減できる。
【００６５】
さらに、パリティビットはデータパターンから一意に決まるので、カウントテーブル２２１ａの各レコードにデータパターンに基づくパリティビットをあらかじめ登録しておいてもよい。この場合、ステップＳ２７ではパリティビットが計算されずに、カウントテーブル２２１ａから読み出したパリティビットとＮＡＮＤ型フラッシュメモリ２１４から読み出したパリティビットとの比較だけが行われればよい。このような処理によれば、ＥＣＣを用いて１ビットエラーを訂正可能なエラー訂正処理よりも、エラー訂正処理の負荷を確実に軽減できる。
【００６６】
［第３の実施の形態］
次に、第３の実施の形態を説明する。前述の第２の実施の形態との相違する事項を主に説明し、共通する事項の説明を省略する。
【００６７】
第３の実施の形態では、ＮＡＮＤ型フラッシュメモリ２１４から読み出したユニットにエラーがある場合、当該ユニットと１ビットの違いのあるデータパターンをカウントテーブル２２１ａから特定して、エラーを訂正する機能を提供する。
【００６８】
第３の実施の形態のストレージ装置および機能は、第２の実施の形態の装置および機能と同様である。そこで、第３の実施の形態では、第２の実施の形態と同じ符号、名称を用いる。
【００６９】
図１０は、第３の実施の形態の読み出し処理の例を示すフローチャートである。第３の実施の形態では、図８の処理が図１０のように変形される。図８と異なる処理ステップについてのみ説明し、他のステップの説明を省略する。また、図１０では、ステップＳ２６の次にステップＳ２６ａが追加される。
【００７０】
（Ｓ２６ａ）読み出し部２２３は、ステップＳ２６で取得したデータパターン（ｎ）とユニット（ｍ）を比較する。読み出し部２２３は、比較した結果、１ビットだけビット値が異なるか否かを判定する。例えば、取得したデータパターン（ｎ）とユニット（ｍ）とのハミング距離を算出し、得られたビット列における１の数が１つである場合に、１ビットだけビット値が異なると判定される。１ビットだけビット値が異なる場合、処理をステップＳ２７に進める。２ビット以上ビット値が異なる場合、処理をステップＳ２８に進める。
【００７１】
ＮＡＮＤ型フラッシュメモリ２１４から読み出されたユニットのエラーが検出された場合、１ビットエラーである確率が最も高い。また、上記処理によれば、訂正に用いるデータパターンの選択条件として、読み出されたユニットと１ビットだけビット値が異なるという条件が追加される。これにより、第２の実施の形態と比較して１ビットエラーを高精度に訂正でき、ページ全体でのエラー訂正精度も向上させることができる。
【００７２】
［第４の実施の形態］
次に、第４の実施の形態を説明する。前述の第２の実施の形態との相違する事項を主に説明し、共通する事項の説明を省略する。
【００７３】
第４の実施の形態では、カウントテーブル２２１ａにパリティビットの項目が追加されたカウントテーブルが用いられる。そして、ＮＡＮＤ型フラッシュメモリ２１４から読み出したユニットにエラーがある場合、当該ユニットに付加されているパリティビットと同じパリティビットに対応するデータパターンが当該カウントテーブルから特定され、エラーが訂正される。第４の実施の形態は、このような機能を提供する。
【００７４】
第４の実施の形態のストレージ装置および機能は、第２の実施の形態の装置および機能と同様である。そこで、第４の実施の形態では、第２の実施の形態と同じ符号、名称を用いる。また、第４の実施の形態では、上述したように、カウントテーブル２２１ａにパリティビットの項目が追加されたカウントテーブルが作成される。当該カウントテーブルについて、図１１で説明する。
【００７５】
図１１は、第４の実施の形態のカウントテーブルの例を示す図である。カウントテーブル２２１ｂは、記憶部２２１に格納される。カウントテーブル２２１ｂは、項番、データパターン、パリティビット、出現数の項目を含む。カウントテーブル２２１ｂは、カウントテーブル２２１ａの項目にパリティビットの項目が追加されたものである。パリティビットの項目には、対応するデータパターンを基に算出されたパリティビットが登録される。パリティビットはデータパターンから一意に決まるため、初期状態ではカウントテーブル２２１ｂには項番、データパターン、パリティビットの各項目に情報があらかじめ登録されている。
【００７６】
書き込み部２２２は、１ページ分のユニットに基づいてカウントテーブル２２１ｂを生成すると、カウントテーブル２２１ｂをカウントテーブル２２１ｃのように変形する。カウントテーブル２２１ｃは、カウントテーブル２２１ｂのパリティビットが“１”のレコードの中で出現数が最も高いレコードと、パリティビットが“０”のレコードの中で出現数が最も高いレコードとを抽出したものである。
【００７７】
図１２は、第４の実施の形態の書き込み処理の例を示すフローチャートである。第４の実施の形態では、図７の処理が図１２のように変形される。図７と異なる処理ステップについてのみ説明し、他のステップの説明を省略する。図１２では、ステップＳ１７がステップＳ１７ａに変更される。なお、ステップＳ１３，Ｓ１４では、カウントテーブル２２１ａの代わりにカウントテーブル２２１ｂが用いられる。
【００７８】
（Ｓ１７ａ）書き込み部２２２は、カウントテーブル２２１ｂにおけるパリティビットが０のレコードの中から、出現数が最大のレコードを特定する。また、書き込み部２２２は、カウントテーブル２２１ｂにおけるパリティビットが１のレコードの中から、出現数が最大のレコードを特定する。書き込み部２２２は、カウントテーブル２２１ｂから、特定した２つのレコードのみ残し、それ以外のレコードを削除して、カウントテーブル２２１ｃを生成する。
【００７９】
なお、ステップＳ２０では、ステップＳ１７ａで生成されたカウントテーブル２２１ｃがＳＰＡＲＥエリアに書き込まれる。
図１３は、第４の実施の形態の読み出し処理の例を示すフローチャートである。第４の実施の形態では、図８の処理が図１３のように変形される。図８と異なる処理ステップについてのみ説明し、他のステップの説明を省略する。また、図１３では、図８のステップＳ２２がステップＳ２２ａ、ステップＳ２５がステップＳ２５ａ、ステップＳ２６がステップＳ２６ｂ、ステップＳ２９がステップＳ２９ａに変わり、ステップＳ２７，Ｓ２８，Ｓ３０は実行されない。
【００８０】
（Ｓ２２ａ）読み出し部２２３は、ｍに０を代入する。そして、処理をステップＳ２３に進める。
（Ｓ２５ａ）読み出し部２２３は、ユニット（ｍ）に付加されているパリティビットを用いて、ユニット（ｍ）にエラーが含まれているか否かを判定する。エラーを検出した場合、処理をステップＳ２６ｂに進める。エラーを検出しなかった場合、処理をステップＳ３１に進める。
【００８１】
（Ｓ２６ｂ）読み出し部２２３は、カウントテーブル２２１ｃを参照し、ユニット（ｍ）に付加されたパリティビットと同じパリティビットのデータパターンを取得する。そして、処理をステップＳ２９ａに進める。
【００８２】
（Ｓ２９ａ）読み出し部２２３は、ユニット（ｍ）をステップＳ２６ｂで取得したデータパターンに置き換えて、エラーを訂正する。そして、処理をステップＳ３１に進める。
以上の第４の実施の形態によれば、読み出し部２２３は、カウントテーブル２２１ｃに登録された２つのデータパターンから、パリティビットに基づいて訂正に用いるデータパターンを選択する。第２の実施の形態の図８の処理と比較した場合、ステップＳ２６の代わりにステップＳ２６ｂが実行されることで、パリティビットの計算数が減少する。このため、第２の実施の形態と比較して、訂正に用いるデータパターンを選択するための処理負荷が軽減され、その処理時間が短縮される。これにより、ＥＣＣを用いてエラーを検出・訂正する従来の処理と比較して、処理負荷を軽減し、処理時間を短縮できる。
【００８３】
また、第２の実施の形態と比較して、ＮＡＮＤ型フラッシュメモリ２１４にページ毎に保存されるカウントテーブル２２１ｃの容量が小さくなる。このため、ＮＡＮＤ型フラッシュメモリ２１４の記憶領域の利用効率を向上させることができる。
【００８４】
［第５の実施の形態］
次に、第５の実施の形態を説明する。前述の第２，４の実施の形態との相違する事項を主に説明し、共通する事項の説明を省略する。
【００８５】
第５の実施の形態では、ビットパターンにパリティビットが対応づけられた、図１１のカウントテーブル２２１ｂが用いられる。ＮＡＮＤ型フラッシュメモリ２１４への１ページ分のユニットの書き込み処理では、レコードが出現数の多い順にソートされた状態のカウントテーブル２２１ｂが、ＮＡＮＤ型フラッシュメモリ２１４のＳＰＡＲＥエリアに保存される。また、ＮＡＮＤ型フラッシュメモリ２１４から読み出したユニットにエラーがある場合、当該ユニットに付加されているパリティビットと同じパリティビットが登録されたレコードが、保存されたカウントテーブル２２１ｂの中から特定される。そして、特定されたレコードのデータパターンの中から当該ユニットと１ビットだけビット値が異なるデータパターンが特定され、エラーが訂正される。第５の実施の形態は、このような機能を提供する。
【００８６】
第５の実施の形態のストレージ装置および機能は、第２，４の実施の形態の装置および機能と同様である。そこで、第５の実施の形態では、第２，４の実施の形態と同じ符号、名称を用いる。また、第５の実施の形態では、上述したように、カウントテーブル２２１ｂが作成される。
【００８７】
まず、ＮＡＮＤ型フラッシュメモリ２１４への１ページ分のユニットの書き込み処理手順は、基本的に図７と同様であるので、ここでは図示を省略する。ただし、本実施の形態では、カウントテーブル２２１ａの代わりにカウントテーブル２２１ｂが用いられ、ステップＳ１７ではパリティビットを含めてカウントテーブル２２１ｂのレコードがソートされ、ステップＳ１９ではソートされたカウントテーブル２２１ｂが書き込まれる点が、図７と相違する。
【００８８】
図１４は、第５の実施の形態の読み出し処理の例を示すフローチャートである。第５の実施の形態では、図８の処理が図１４のように変形される。図８と異なる処理ステップについてのみ説明し、他のステップの説明を省略する。また、第５の実施の形態では、図８のステップＳ２２がステップＳ２２ｂ、ステップＳ２５がステップＳ２５ｂ、ステップＳ２８がステップＳ２８ａ、ステップＳ２９がステップＳ２９ｂ、ステップＳ３０がステップＳ３０ａに変更され、ステップＳ２７は実行されない。さらに、第５の実施の形態では、図８のステップＳ２６の代わりにステップＳ２６ｃ，２６ｄが実行される。
【００８９】
（Ｓ２２ｂ）読み出し部２２３は、ｍに０を代入する。また、読み出し部２２３は、ｌに１を代入する。ｌは、後述するように、カウントテーブル２２１ｂのレコードのうち、エラーが検出されたユニットに付加されているパリティビットと同じパリティビットを含むレコードについて、テーブル先頭からの順位を示す変数である。そして、処理をステップＳ２３に進める。
【００９０】
（Ｓ２５ｂ）読み出し部２２３は、ユニット（ｍ）に付加されているパリティビットを用いて、ユニット（ｍ）にエラーが含まれているか否かを判定する。エラーを検出した場合、読み出し部２２３は、カウントテーブル２２１ｂのレコードのうち、ユニット（ｍ）に付加されているパリティビットと同じパリティビットを含むレコードだけを処理対象として、ステップＳ２６ｃ以後の処理を実行する。エラーを検出しなかった場合、処理をステップＳ３１に進める。
【００９１】
（Ｓ２６ｃ）読み出し部２２３は、カウントテーブル２２１ｂを参照し、データパターン（ｌ）を取得する。データパターン（ｌ）は、処理対象のレコードのうち先頭からｌ番目（すなわち、ｌ番目に出現数が大きい）レコードに登録されたデータパターンである。そして、処理をステップＳ２６ｄに進める。
【００９２】
（Ｓ２６ｄ）読み出し部２２３は、ステップＳ２６ｃで取得したデータパターン（ｌ）とユニット（ｍ）を比較する。読み出し部２２３は、比較した結果、１ビットだけビット値が異なるか否かを判定する。１ビットだけビット値が異なる場合、処理をステップＳ２９ｂに進める。２ビット以上ビット値が異なる場合、処理をステップＳ２８ａに進める。
【００９３】
（Ｓ２８ａ）読み出し部２２３は、ｌに１を加算する。そして、処理をステップＳ２６ｃに進める。
（Ｓ２９ｂ）読み出し部２２３は、ユニット（ｍ）をステップＳ２６ｃで取得したデータパターンに置き換えて、エラーを訂正する。そして、処理をステップＳ３０ａに進める。
【００９４】
（Ｓ３０ａ）読み出し部２２３は、ｌに１を代入する。そして、処理をステップＳ３１に進める。
第５の実施の形態では、書き込みデータのユニットにエラーがある場合、当該ユニットに付加されているパリティビットと同じパリティビットがカウントテーブル２２１ｂの中から特定される。これにより、エラー訂正に用いるデータパターンの候補を絞り込むことができる。そして、データパターンの候補が絞り込まれた後、特定されたパリティビットの中で当該ユニットと１ビットだけビット値が異なるデータパターンが特定され、エラーが訂正される。これにより、訂正処理の時間を短縮しつつ、１ビットエラーの訂正精度を高めることができる。
【符号の説明】
【００９５】
１  記憶制御装置
１ａ  書き込み部
１ｂ  読み出し部
２  記憶装置
３  データブロック群
３ａ，３ｂ，３ｃ  データブロック
４  順位情報
５ａ，５ｂ，５ｃ  パリティビット
【図１】
0006646213.tif 000002
【図２】
0006646213.tif 000003
【図３】
0006646213.tif 000004
【図４】
0006646213.tif 000005
【図５】
0006646213.tif 000006
【図６】
0006646213.tif 000007
【図７】
0006646213.tif 000008
【図８】
0006646213.tif 000009
【図９】
0006646213.tif 000010
【図１０】
0006646213.tif 000011
【図１１】
0006646213.tif 000012
【図１２】
0006646213.tif 000013
【図１３】
0006646213.tif 000014
【図１４】
0006646213.tif 000015