(57)【要約】【課題】誤り訂正をより高精度に実行可能とする。【解決手段】実施形態のメモリシステムは、不揮発性メモリと、メモリコントローラと、を備える。不揮発性メモリは、Ｎ次元（Ｎは２以上の整数）の誤り訂正符号が記憶される。メモリコントローラは、不揮発性メモリから読み出したＮ次元の誤り訂正符号のｎ次元の成分に対して１回目の復号処理を行い、ｎ次元の成分に対してｍ回目の復号処理により誤り訂正符号の復号に失敗した場合にはｎ次元の成分に対して（ｍ＋１）回目の復号処理を行い、ｍ回目の復号処理が終了した後、ｍ回目の復号処理においてｎ次元以外の次元の成分による復号で訂正されずにｎ次元の成分による復号で訂正されたビットを、ｍ回目の復号処理の入力データのうちの対応するビットに変更し、変更されたデータを使用してｎ次元の成分に対して（ｍ＋１）回目の復号処理を実行する。【選択図】図１
2020046823.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ次元（Ｎは２以上の整数）の誤り訂正符号が記憶された不揮発性メモリと、
前記Ｎ次元の誤り訂正符号を前記不揮発性メモリから読み出し、
前記読み出したＮ次元の誤り訂正符号のｎ次元（ｎは１以上Ｎ以下の整数）の誤り訂正符号に対して１回目の復号処理を行い、
前記ｎ次元の誤り訂正符号に対してｍ回目（ｍは１以上の整数）の復号処理に失敗した場合には前記ｎ次元の誤り訂正符号に対して（ｍ＋１）回目の復号処理を行い、
前記ｍ回目の復号処理が終了した後、前記ｍ回目の復号処理において前記ｎ次元以外の次元の誤り訂正符号による復号で訂正されずに前記ｎ次元の誤り訂正符号による復号で訂正されたビットを、前記ｍ回目の復号処理の入力データのうちの対応するビットに変更し、前記変更されたデータを使用して前記ｎ次元の誤り訂正符号に対して前記（ｍ＋１）回目の復号処理を実行する、
メモリコントローラと、
を備えるメモリシステム。
【請求項２】
前記メモリコントローラは、
前記ｍ回目の復号処理で、前記ｎ次元以外の次元の誤り訂正符号による復号で訂正されたビットを変更しないデータを使用して、前記ｎ次元の誤り訂正符号に対して前記（ｍ＋１）回目の復号処理を実行する、
請求項１に記載のメモリシステム。
【請求項３】
前記ｎ次元の誤り訂正符号の復号処理用に、前記ｍ回目の復号処理の入力データを記憶する記憶領域と、前記ｍ回目の復号処理の復号結果である出力データを記憶する記憶領域と、を含む記憶部をさらに備え、
前記メモリコントローラは、
前記ｎ次元の誤り訂正符号に対応する記憶領域に記憶された前記入力データと、前記出力データとを比較することにより、前記ｎ次元の誤り訂正符号による復号で訂正されたか否かを判定する、
請求項１に記載のメモリシステム。
【請求項４】
前記メモリコントローラは、
前記ｎ次元の誤り訂正符号に対する前記ｍ回目の復号処理の結果を表すエラーベクタに基づいて、前記ｎ次元の誤り訂正符号による前記ｍ回目の復号処理で訂正されたか否かを判定する、
請求項１に記載のメモリシステム。
【請求項５】
前記メモリコントローラは、
ｋ次元（ｋは１以上（Ｎ−１）以下の整数）の誤り訂正符号に対する復号処理の後に（ｋ＋１）次元の誤り訂正符号に対する復号処理を実行する、
請求項１に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下の実施形態は、メモリシステムに関する。
【背景技術】
【０００２】
メモリシステムでは、一般に、記憶するデータを保護するために、誤り訂正符号化されたデータが記憶される。このため、メモリシステムに記憶されたデータを読み出す際には、誤り訂正符号化されたデータに対する復号が行われる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−２１５９３４号公報
【特許文献２】米国特許第５，７５７，８２４号明細書
【特許文献３】米国特許出願公開第２００５／００５５６２２号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、誤り訂正をより高精度に実行可能なメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
実施形態のメモリシステムは、不揮発性メモリと、メモリコントローラと、を備える。不揮発性メモリは、Ｎ次元（Ｎは２以上の整数）の誤り訂正符号が記憶される。メモリコントローラは、不揮発性メモリから読み出したＮ次元の誤り訂正符号のｎ次元の成分に対して１回目の復号処理を行い、ｎ次元の成分に対してｍ回目の復号処理により誤り訂正符号の復号に失敗した場合にはｎ次元の成分に対して（ｍ＋１）回目の復号処理を行い、ｍ回目の復号処理が終了した後、ｍ回目の復号処理においてｎ次元以外の次元の成分による復号で訂正されずにｎ次元の成分による復号で訂正されたビットを、ｍ回目の復号処理の入力データのうちの対応するビットに変更し、変更されたデータを使用してｎ次元の成分に対して（ｍ＋１）回目の復号処理を実行する。
【図面の簡単な説明】
【０００６】
【図１】図１は、本実施形態に係るメモリシステムの概略構成例を示すブロック図である。
【図２】図２は、本実施形態に係る多次元の誤り訂正符号の一例を示す図である。
【図３】図３は、符号化／復号部の機能構成の一例を示すブロック図である。
【図４】図４は、本実施形態による反復復号処理の概要を説明するための図である。
【図５】図５は、共有メモリに記憶されるデータの関係を示す図である。
【図６】図６は、本実施形態における反復復号処理の一例を示すフローチャートである。
【図７】図７は、反復復号処理の入力データおよび出力データの遷移の例を示す図である。
【図８】図８は、２次元の誤り訂正符号により訂正されるビットの遷移の例を示す図である。
【図９】図９は、本実施形態による誤り訂正精度の改善効果の例を示す図である。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態に係るメモリシステムを詳細に説明する。なお、以下の実施形態により本発明が限定されるものではない。
【０００８】
図１は、本実施形態に係るメモリシステムの概略構成例を示すブロック図である。図１に示すように、メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とを備える。メモリシステム１は、ホスト３０と接続可能であり、図１ではホスト３０と接続された状態が示されている。ホスト３０は、例えば、パーソナルコンピュータ、携帯端末などの電子機器であってよい。
【０００９】
不揮発性メモリ２０は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤ型フラッシュメモリ（以下、単にＮＡＮＤメモリという）である。以下の説明では、不揮発性メモリ２０としてＮＡＮＤメモリが用いられた場合を例示するが、不揮発性メモリ２０として３次元構造フラッシュメモリ、ＲｅＲＡＭ（Resistance  Random  Access  Memory）、ＦｅＲＡＭ（Ferroelectric  Random  Access  Memory）等のＮＡＮＤメモリ以外の記憶装置を用いることも可能である。また、不揮発性メモリ２０が半導体メモリであることは必須ではなく、半導体メモリ以外の種々の記憶媒体に対して本実施形態を適用することも可能である。
【００１０】
メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とが１つのパッケージとして構成されるメモリカード等であってもよいし、ＳＳＤ（Solid  State  Drive）等であってもよい。
【００１１】
メモリコントローラ１０は、例えばＳｏＣ（System-On-a-Chip）として構成される半導体集積回路である。以下で説明するメモリコントローラ１０の各構成要素の動作の一部又は全部は、ＣＰＵ（Central  Processing  Unit）がファームウエアを実行することによって実現されてもよいし、ハードウエアで実現されてもよい。
【００１２】
メモリコントローラ１０は、ホスト３０からの書込み要求に従って不揮発性メモリ２０への書込みを制御する。また、ホスト３０からの読出し要求に従って不揮発性メモリ２０からの読み出しを制御する。メモリコントローラ１０は、ホストＩ／Ｆ（ホストインタフェース）１５、メモリＩ／Ｆ（メモリインタフェース）１３、制御部１１、符号化／復号部（コーデック）１４、データバッファ１２および共有メモリ１７を備える。ホストＩ／Ｆ１５、メモリＩ／Ｆ１３、制御部１１、符号化／復号部１４、データバッファ１２および共有メモリ１７は、内部バス１６で相互に接続されている。
【００１３】
ホストＩ／Ｆ１５は、ホスト３０との間のインタフェース規格に従った処理を実施し、ホスト３０から受信した要求、書込み対象のユーザデータなどを内部バス１６に出力する。また、ホストＩ／Ｆ１５は、不揮発性メモリ２０から読み出されて復元されたユーザデータ、制御部１１からの応答などをホスト３０へ送信する。
【００１４】
メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０への書込み処理を行う。また、メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０からの読み出し処理を行う。
【００１５】
データバッファ１２は、メモリコントローラ１０がホスト３０から受信したユーザデータを不揮発性メモリ２０へ記憶するまでに一時記憶する。また、データバッファ１２は、不揮発性メモリ２０から読み出したユーザデータをホスト３０へ送信するまでに一時記憶する。データバッファ１２には、例えば、ＳＲＡＭ（Static  Random  Access  Memory）やＤＲＡＭ（Dynamic  Random  Access  Memory）などの汎用メモリを用いることができる。
【００１６】
制御部１１は、メモリシステム１の各構成要素を統括的に制御する。制御部１１は、ホスト３０からの要求をホストＩ／Ｆ１５経由で受け付けた場合に、その要求に応じた制御を行う。例えば、制御部１１は、ホスト３０からの書込み要求に応じて、不揮発性メモリ２０へのユーザデータおよびパリティの書き込みをメモリＩ／Ｆ１３へ指示する。また、制御部１１は、ホスト３０からの読出し要求に応じて、不揮発性メモリ２０からのユーザデータおよびパリティの読み出しをメモリＩ／Ｆ１３へ指示する。
【００１７】
また、制御部１１は、ホスト３０からユーザデータの書込み要求を受信した場合、データバッファ１２に蓄積されるユーザデータに対して、不揮発性メモリ２０上の記憶領域（メモリ領域）を決定する。すなわち、制御部１１は、ユーザデータの書込み先を管理する。ホスト３０から受信したユーザデータの論理アドレスと該ユーザデータが記憶された不揮発性メモリ２０上の記憶領域を示す物理アドレスとの対応はアドレス変換テーブルとして記憶される。
【００１８】
また、制御部１１は、ホスト３０から読出し要求を受信した場合、読出し要求により指定された論理アドレスを上述のアドレス変換テーブルを用いて物理アドレスに変換し、該物理アドレスからの読み出しをメモリＩ／Ｆ１３へ指示する。
【００１９】
ここで、ＮＡＮＤメモリでは、一般に、ページと呼ばれるデータ単位で、書き込みおよび読み出しが行われ、ブロックと呼ばれるデータ単位で消去が行われる。本実施形態では、同一のワード線に接続される複数のメモリセルをメモリセルグループと呼ぶ。メモリセルがシングルレベルセル（ＳＬＣ）である場合は、１つのメモリセルグループが１ページに対応する。メモリセルがマルチレベルセル（ＭＬＣ）である場合は、１つのメモリセルグループが複数ページに対応する。また、各メモリセルはワード線に接続するとともにビット線にも接続される。したがって、各メモリセルは、ワード線を識別するアドレスとビット線を識別するアドレスとで識別することが可能である。
【００２０】
ホスト３０から送信されるユーザデータは、内部バス１６に転送されてデータバッファ１２に一旦記憶される。符号化／復号部１４は、不揮発性メモリ２０に記憶されるユーザデータを符号化して符号化データ（符号語）を生成する。また、符号化／復号部１４は、不揮発性メモリ２０から読み出された符号化データ（読出し情報又は受信語ともいう）を復号してユーザデータを復元する。なお、符号化／復号部１４により符号化されるデータには、ユーザデータ以外にも、メモリコントローラ１０内部で用いる制御データ等が含まれてもよい。
【００２１】
以上のような構成を備えるメモリシステム１における書込み処理では、制御部１１は、不揮発性メモリ２０への書込み時に、ユーザデータの符号化を符号化／復号部１４に指示する。その際、制御部１１は、不揮発性メモリ２０における符号語の記憶場所（記憶アドレス）を決定し、決定した記憶場所もメモリＩ／Ｆ１３へ指示する。符号化／復号部１４は、制御部１１からの指示に基づいて、データバッファ１２上のユーザデータを符号化して符号語を生成する。符号化方式としては、例えば、ＬＤＰＣ（Low-Density  Parity-Check）符号やＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号やＲＳ（Reed-Solomon）符号を用いた符号化方式を採用することができる。
【００２２】
一方、読出し処理では、制御部１１は、不揮発性メモリ２０からの読出し時に、不揮発性メモリ２０上のアドレスを指定してメモリＩ／Ｆ１３へ読み出しを指示する。また、制御部１１は、符号化／復号部１４へ復号の開始を指示する。メモリＩ／Ｆ１３は、制御部１１の指示に従って、不揮発性メモリ２０の指定されたアドレスに対する読み出しを実行し、この読み出しにより得られた読出し情報を符号化／復号部１４に入力する。そして、符号化／復号部１４は、入力された読出し情報を復号する。
【００２３】
符号化／復号部１４は、例えば、多次元の誤り訂正符号の各成分符号の符号化器／復号器として用いることもできる。多次元の誤り訂正符号とは、誤り訂正符号の少なくとも一つ以上の構成単位であるシンボルが、複数のより小規模な成分符号によって多重に保護されているものを指す。その際、１シンボルは、例えば１ビット（二元体（binary  field）の元（element））、又は、二元体以外の有限体（finite  field）などのアルファベットの元で構成される。
【００２４】
ここで、多次元の誤り訂正符号の例として、図２に積符号を示す。図２に示す積符号５００は、構成単位である各情報ビット（シンボルであってもよい）ｄ０〜ｄ３が、行方向（図面中横方向）と列方向（図面中縦方向）とのそれぞれで、情報長２ビットで且つパリティ長３ビットのハミング符号５１１〜５１５及び５２１〜５２５で保護された構造を備える。このような積符号５００では、全ての情報ビットｄ０〜ｄ３およびパリティビットｐ０〜ｐ２０が行方向（次元１とも称する）のハミング符号と列方向（次元２とも称する）のハミング符号とで二重に保護されている。
【００２５】
なお、多次元の誤り訂正符号としては、図２に例示する積符号５００に限定されず、例えば一般化ＬＤＰＣ符号（Generalized  Low  Density  Parity  Check  Code）などであってもよい。一般化ＬＤＰＣ符号を含む一般の多次元の誤り訂正符号では、シンボルごとに保護の多重度が異なっていてもよい。また、一般の多次元の誤り訂正符号では成分符号を次元１と次元２のようにグループ分けすることができないが、このような符号構造を有する多次元の誤り訂正符号に対しても本技術は適用することが可能である。
【００２６】
図２のような積符号では、例えば、次元１による復号と次元２による復号とを含む復号処理が繰り返し実行される。積符号は、訂正能力が高く計算量の小さい符号化方式を実現するために使用される。積符号で用いられる誤り訂正符号のほとんどは線形符号である。優れた符号構成法および復号法が知られているためである。線形符号では、訂正可能な範囲である符号長内に訂正可能な数以下の誤りがある場合、正しく誤りを検出できる。一方、符号長内に訂正可能な数より多い誤りがある場合、誤りの箇所を特定できない、または、誤りの箇所を誤検出する可能性がある。誤りの箇所を誤検出した場合、その箇所が誤訂正される可能性がある。
【００２７】
また積符号では、特定の領域に集中して誤りがあると訂正が進まなくなる場合がある。例えば積符号で組み合わされる複数の誤り訂正符号による復号結果を上書きして訂正を進めていく場合、いずれかの次元の誤り訂正符号により訂正可能な範囲に、訂正可能な数より多い誤りが含まれていたために誤訂正が行われ、誤訂正の結果が上書きされることがある。この結果、特定の領域に誤りが集中し、訂正が進まなくなる状況が発生しうる。
【００２８】
そこで、本実施形態では、各次元の誤り訂正符号による復号結果を上書きして復号を進めるのではなく、各次元の誤り訂正符号それぞれの復号結果を相互に異なる記憶領域に記憶する。そして、ある次元の誤り訂正符号を復号する際の入力データを、当該誤り訂正符号の前回の訂正結果を反映させず、他の次元の誤り訂正符号の復号結果のみを反映させたデータとする。これにより、誤訂正による誤りの挿入を抑え、訂正能力を向上させることが可能となる。なお、各々の次元の誤り訂正符号は各々の次元の成分符号とも称される。
【００２９】
図３は、符号化／復号部１４の機能構成の一例を示すブロック図である。図３は、図２に示すような２次元の積符号の符号化／復号を行う場合の例を示す。以下では主に２次元の誤り訂正符号を例に説明するが、Ｎ次元（Ｎは２以上の整数）の誤り訂正符号について同様の手法を適用できる。符号化／復号部１４は、例えば、ｋ次元（ｋは１以上（Ｎ−１）以下の整数）の誤り訂正符号に対する復号処理の後に、（ｋ＋１）次元の誤り訂正符号に対する復号処理を実行するように構成できる。
【００３０】
図３に示すように、符号化／復号部１４は、符号化器２０１ａ、２０１ｂと、復号器２０２ａ、２０２ｂとを含む。符号化器２０１ａ、２０１ｂは、それぞれ次元１および次元２の成分符号を符号化する。復号器２０２ａ、２０２ｂは、それぞれ次元１および次元２の成分符号を復号する。
【００３１】
図２の共有メモリ１７は、符号化器２０１ａ、２０１ｂによる符号化、および、復号器２０２ａ、２０２ｂによる復号で参照されるデータを記憶する。共有メモリ１７は、例えば、復号器２０２ａ、２０２ｂのｍ回目（ｍは１以上の整数）の復号処理で、ｎ次元（ｎは１以上Ｎ以下の整数）の誤り訂正符号を復号するときに用いた入力データをそれぞれ記憶する。また、共有メモリ１７は、ｍ回目の復号処理でのｎ次元の誤り訂正符号の復号結果である出力データをそれぞれ記憶する。共有メモリ１７は、符号化／復号部１４の内部に備えられていてもよい。
【００３２】
なお、復号処理には、ハードビット復号（硬判定復号）と、ソフトビット復号（軟判定復号）とが含まれ得る。ハードビット復号では、０または１の１ビット（ハードビット）が入力データとして用いられる。ソフトビット復号では、０または１の確からしさを表す対数尤度比（Log  Likelihood  Ratio：ＬＬＲ）などの尤度情報（ソフトビット）が、さらに入力データとして用いられる。
【００３３】
復号器２０２ａ、２０２ｂは、ハードビットを入力データとして入力し、ハードビットを出力データとして出力する復号器であってもよいし、ハードビットおよびソフトビットを入力データとして入力し、ハードビットを出力データとして出力する復号器であってもよい。
【００３４】
図４は、本実施形態による反復復号処理の概要を説明するための図である。反復復号処理は、符号化器２０１ａ、２０１ｂによる復号処理を繰り返す処理である。メモリＩ／Ｆ１３を介して不揮発性メモリ２０から入力された復号対象のデータは共有メモリ１７に記憶される。復号器２０２ａおよび復号器２０２ｂは、それぞれ共有メモリ１７にアクセスすることができる。復号対象のデータは、例えば共有メモリ１７の記憶領域４０１に記憶される。
【００３５】
以下では、復号器２０２ａによる復号を復号Ｄ１、復号Ｄ１の入力データを復号Ｄ１入力、復号Ｄ１の出力データを復号Ｄ１出力という場合がある。同様に、復号器２０２ｂによる復号を復号Ｄ２、復号Ｄ２の入力データを復号Ｄ２入力、復号Ｄ２の出力データを復号Ｄ２出力という場合がある。
【００３６】
復号処理が開始されると、復号器２０２ａは、共有メモリ１７の記憶領域４０１に記憶された復号対象のデータを入力し、入力されたデータ（復号Ｄ１入力）を復号する。このように、１回目の復号処理内の復号Ｄ１では、復号対象のデータが入力データとなる。復号器２０２ａは、復号結果（復号Ｄ１出力）を共有メモリ１７の記憶領域４０２に記憶する。
【００３７】
復号器２０２ｂは、復号器２０２ａの復号結果等を参照して生成されたデータを入力し、入力されたデータ（復号Ｄ２入力）を復号する。復号Ｄ２入力は、共有メモリ１７に記憶されたデータ（復号Ｄ１出力、復号Ｄ２入力、復号Ｄ２出力）を参照して生成される。生成されたデータは、復号器２０２ｂによる復号時に入力されるとともに、記憶領域４０３に記憶される。復号Ｄ２入力の生成方法の詳細は後述する。１回目の復号Ｄ２では、復号Ｄ１出力がそのまま復号Ｄ２入力に反映される。復号器２０２ｂは、復号結果（復号Ｄ２出力）を共有メモリ１７の記憶領域４０４に記憶する。
【００３８】
２回目以降の復号処理では、復号器２０２ａは、復号器２０２ｂの復号結果等を参照して生成されたデータを入力し、入力されたデータ（復号Ｄ１入力）を復号する。復号Ｄ１入力は、共有メモリ１７に記憶されたデータ（復号Ｄ２出力、復号Ｄ１入力、復号Ｄ１出力）を参照して生成される。生成されたデータは、復号器２０２ａによる復号時に入力されるとともに、記憶領域４０１に記憶される。復号Ｄ１入力の生成方法の詳細は後述する。復号器２０２ａは、復号結果（復号Ｄ１出力）を共有メモリ１７の記憶領域４０２に記憶する。
【００３９】
図５は、共有メモリ１７に記憶されるデータの関係を示す図である。復号器２０２ａは、復号Ｄ１入力を用いて復号Ｄ１を実行し、復号Ｄ１の復号結果である復号Ｄ１出力を共有メモリ１７に記憶する。復号Ｄ２で用いられる復号Ｄ２入力は、共有メモリ１７に記憶された各データを参照して生成される。復号器２０２ｂは、復号Ｄ２入力を用いて復号Ｄ２を実行し、復号Ｄ２の復号結果である復号Ｄ２出力を共有メモリ１７に記憶する。次の復号Ｄ１で用いられる復号Ｄ１入力は、共有メモリ１７に記憶された各データを参照して生成される。
【００４０】
以上のような処理が、例えば繰り返しの上限数（Ｍ回、Ｍは２以上の整数）に達するまで、または、ユーザデータ内の誤りがなくなるまで繰り返し実行される。
【００４１】
なお、復号器２０２ａ、２０２ｂは、復号結果をそのまま共有メモリ１７に記憶してもよいし、復号結果から得られるエラーベクタ、または、エラーベクタに対応するシンドロームを記憶してもよい。エラーベクタは、例えば、誤りがあると特定された位置のみが１に設定されるバイナリベクトルである。エラーベクタおよびシンドロームは、訂正が行われたか否かの判定、および、復号結果の復元に用いることができる。すなわち、エラーベクタおよびシンドロームは、復号結果と等価な情報である。
【００４２】
次に、入力データ（復号Ｄ１入力、復号Ｄ２入力）の生成方法の詳細について説明する。
【００４３】
ｎ次元の成分符号に対する（ｍ＋１）回目の復号処理では、ｍ回目の復号処理で、ｎ次元以外の次元の誤り訂正符号による復号で訂正されずにｎ次元の誤り訂正符号による復号で訂正されたビットの値を、ｍ回目の復号処理で使用した入力データの対応するビットの値（訂正前のビットの値に相当）に変更した入力データが使用される。ｍ回目の復号処理で、ｎ次元以外の次元の誤り訂正符号による復号で訂正されたビットの値は変更されずに、（ｍ＋１）回目の復号処理でそのまま使用される。
【００４４】
より具体的には、（ｍ＋１）回目の復号処理内の復号Ｄ１で用いる入力データ（復号Ｄ１入力）の各ビットは、以下の条件（Ｃ１）、（Ｃ２）、および、（Ｃ３）が順に判断されて生成される。なお各条件はビットごとに判断される。
（Ｃ１）ｍ回目の復号Ｄ２で訂正された場合、すなわち、ｍ回目の復号Ｄ２入力≠復号Ｄ２出力の場合：（ｍ＋１）回目の復号Ｄ１入力＝ｍ回目の復号Ｄ２出力
（Ｃ２）ｍ回目の復号Ｄ１で訂正された場合、すなわち、ｍ回目の復号Ｄ１入力≠復号Ｄ１出力の場合：（ｍ＋１）回目の復号Ｄ１入力＝ｍ回目の復号Ｄ１入力
（Ｃ３）上記以外の場合、すなわち、ｍ回目の復号Ｄ１および復号Ｄ２の両方で訂正されていない場合：（ｍ＋１）回目の復号Ｄ１入力＝ｍ回目の復号Ｄ２出力
【００４５】
（ｍ＋１）回目の復号処理内の復号Ｄ２で用いる入力データ（復号Ｄ２入力）の各ビットは、以下の条件（Ｃ４）、（Ｃ５）、および、（Ｃ６）が順に判断されて生成される。なお各条件はビットごとに判断される。
（Ｃ４）ｍ回目の復号Ｄ１で訂正された場合、すなわち、ｍ回目の復号Ｄ１入力≠復号Ｄ１出力の場合：（ｍ＋１）回目の復号Ｄ２入力＝ｍ回目の復号Ｄ１出力
（Ｃ５）ｍ回目の復号Ｄ２で訂正された場合、すなわち、ｍ回目の復号Ｄ２入力≠復号Ｄ２出力の場合：（ｍ＋１）回目の復号Ｄ２入力＝ｍ回目の復号Ｄ２入力
（Ｃ６）上記以外の場合、すなわち、ｍ回目の復号Ｄ１および復号Ｄ２の両方で訂正されていない場合：（ｍ＋１）回目の復号Ｄ２入力＝ｍ回目の復号Ｄ１出力
【００４６】
なお、共有メモリ１７のデータから、上記条件に従い入力データを生成する機能は、組み合わせ回路などにより実現してもよいし、ＣＰＵなどのプロセッサにプログラムを実行させること、すなわちソフトウェアにより実現してもよい。
【００４７】
次に、このように構成された本実施形態にかかるメモリシステム１による反復復号処理の流れについて説明する。図６は、本実施形態における反復復号処理の一例を示すフローチャートである。
【００４８】
復号器２０２ａは、復号Ｄ１に用いる入力データを生成する（ステップＳ１０１）。上記のように、１回目の復号処理では、復号対象のデータとして共有メモリ１７の記憶領域４０１に記憶されたデータが入力データとなる。２回目以降の復号処理では、復号器２０２ａは、上記条件（Ｃ１）〜（Ｃ３）に従い入力データの各ビットを生成する。
【００４９】
復号器２０２ａは、入力データに対して復号Ｄ１を実行する（ステップＳ１０２）。復号器２０２ａは、復号Ｄ１の結果である復号Ｄ１出力を共有メモリ１７の記憶領域４０２に記憶する（ステップＳ１０３）。
【００５０】
復号器２０２ｂは、復号Ｄ２に用いる入力データを生成する（ステップＳ１０４）。上記のように、１回目の復号処理では、復号Ｄ１の１回目の復号結果である復号Ｄ１出力が入力データとなる。２回目以降の復号処理では、復号器２０２ｂは、上記条件（Ｃ４）〜（Ｃ６）に従い入力データの各ビットを生成する。
【００５１】
復号器２０２ｂは、入力データに対して復号Ｄ２を実行する（ステップＳ１０５）。復号器２０２ｂは、復号Ｄ２の結果である復号Ｄ２出力を共有メモリ１７の記憶領域４０４に記憶する（ステップＳ１０６）。
【００５２】
符号化／復号部１４は、反復復号を終了するか否かを判定する（ステップＳ１０７）。符号化／復号部１４は、例えば、誤り訂正符号の復号に成功した場合、または、誤り訂正符号の復号に失敗したが反復復号の回数が予め設定した上限数（Ｍ回）に達した場合に反復復号を終了すると判定する。符号化／復号部１４は、例えば、誤り訂正符号の復号に失敗し、かつ、反復復号の回数が上限数に達していない場合に反復復号を終了しないと判定する。反復復号を終了しない場合（ステップＳ１０７：Ｎｏ）、ステップＳ１０１に戻り処理が繰り返される。反復復号を終了すると判定した場合（ステップＳ１０７：Ｙｅｓ）、符号化／復号部１４は、反復復号処理を終了する。
【００５３】
次に、本実施形態による反復復号処理の具体例について説明する。図７は、反復復号処理の入力データおよび出力データの遷移の例を示す図である。図７の各列は、例示する７つのビットに対応する。１〜７の数値は、ビットを識別するインデックスを表す。図７の各行は、入力データおよび出力データの時系列の変化を表す。
【００５４】
例えば１行目および２行目は、それぞれ１回目の復号Ｄ１の入力データ（復号Ｄ１入力）および出力データ（復号Ｄ１出力）である。３行目および４行目は、それぞれ１回目の復号Ｄ２の入力データ（復号Ｄ２入力）および出力データ（復号Ｄ２出力）である。５行目および６行目は、それぞれ２回目の復号Ｄ１の入力データ（復号Ｄ１入力）および出力データ（復号Ｄ１出力）である。７行目は、２回目の復号Ｄ２の入力データ（復号Ｄ２入力）である。
【００５５】
インデックス６および７のビットについて、１回目の復号Ｄ１（２行目の復号Ｄ１出力）が誤訂正であったとする。また、１回目の復号Ｄ２（４行目の復号Ｄ２出力）で誤訂正を元に戻すことができなかったとする。このような場合であっても、本実施形態によれば、５行目の復号Ｄ１の入力データ６０２は、１行目の復号Ｄ１入力に戻される。２回目の復号Ｄ１では、インデックス７のビットのように、再び誤訂正を行う可能性もある。一方、１回目の復号Ｄ２の後、復号Ｄ１の保護対象となる領域内のビットの誤りが減っていれば、インデックス６のビットの２回目の復号Ｄ１の復号結果（６行目の復号Ｄ１出力）のように、正しい訂正を行う可能性が高くなる。
【００５６】
また、インデックス６および７のビットについて、１回目の復号Ｄ１（２行目の復号Ｄ１出力）が正しい訂正であったとする。また、１回目の復号Ｄ２（４行目の復号Ｄ２出力）でも同じ値が出力されたとする。このような場合、本実施形態によれば、５行目の復号Ｄ１の入力データ６０２は、訂正前の入力データ（１行目の復号Ｄ１入力）に戻される。しかし、復号Ｄ１の保護対象となる領域に誤訂正が一定量以上入らない限り、インデックス７のビットの６行目の復号Ｄ１出力のように、再度、正しい訂正が行われる。
【００５７】
なお、図７の入力データ６０１は、復号Ｄ２で訂正されたために、復号Ｄ２出力が次の復号Ｄ１入力とされたデータの例を示す（上記（Ｃ１））。入力データ６０２は、復号Ｄ２で訂正されず、復号Ｄ１で訂正されたために、前回の復号Ｄ１入力が復号Ｄ１入力とされたデータの例を示す（上記（Ｃ２））。入力データ６１１は、復号Ｄ１で訂正されたために、復号Ｄ１出力が次の復号Ｄ２入力とされたデータの例を示す（上記（Ｃ４））。入力データ６１２は、復号Ｄ１で訂正されず、復号Ｄ２で訂正されたために、前回の復号Ｄ２入力が復号Ｄ２入力とされたデータの例を示す（上記（Ｃ５））。インデックス１のビットは、復号Ｄ１および復号Ｄ２のいずれでも訂正されないビットに相当する（上記（Ｃ３）および（Ｃ６））。
【００５８】
１回目の復号Ｄ１（２行目の復号Ｄ１出力）が誤訂正であり、かつ、入力データを上書きする構成の場合、次の復号Ｄ２の後でもまだ復号Ｄ１で誤訂正した符号語内のエラーがｔ＋１個以上（ｔは誤り訂正可能なビット数）残留していると、再び復号Ｄ１で誤訂正される。
【００５９】
これに対して本実施形態によれば、各復号器（復号器２０２ａ、２０２ｂ）は、前回の自身による訂正箇所を元に戻して復号を行うことができる。このため、ある次元の誤り訂正符号により誤訂正されたとしても、他の次元の誤り訂正符号により過半数のビットが正しく訂正される限り、正しいデータに収束する可能性が高くなる。
【００６０】
図８は、２次元の誤り訂正符号により訂正されるビットの遷移の例を示す図である。図８は、行方向の９ビットが、次元１の誤り訂正符号により保護され、列方向の９ビットが、次元２の誤り訂正符号により保護される例を示す。図中の「ｅ」は、誤りが生じているビットを表す。図８の例では、次元１の誤り訂正符号により訂正可能なビット数は１であり、次元２の誤り訂正符号により訂正可能なビット数は２であると仮定する。
【００６１】
上部左の図は、例えば１回目の復号Ｄ１の入力データ（復号Ｄ１入力）の例を示す。ビット７０１は、１回目の復号Ｄ１で訂正されるビットを表す。
【００６２】
上部中央の図は、１回目の復号Ｄ１の復号結果（復号Ｄ１出力）を表すとともに、１回目の復号Ｄ２の入力データ（復号Ｄ２入力）を表す。この図に示すように、ビット７０１の誤りが訂正されている。ビット７１２は、復号Ｄ１により誤訂正されたビットを表す。ビット７１１は、１回目の復号Ｄ２で訂正されるビットを表す。
【００６３】
上部右の図は、１回目の復号Ｄ２の復号結果（復号Ｄ２出力）を表す。この図に示すように、ビット７１１の誤りが訂正されている。
【００６４】
本実施形態を適用しない場合、上部右の図の状態になると、次元１および次元２の誤り訂正符号それぞれにより訂正可能なビット数を超えるため、次元１および次元２のいずれの誤り訂正符号を用いても訂正が進まなくなる。このように、本実施形態を適用しない多次元の誤り訂正符号では、特定の領域に集中して誤りがあると訂正が進まなくなる場合がある。これに対して本実施形態によれば、誤訂正により特定の領域に誤りが集中するような場合であっても、入力データを前回の訂正前のデータに戻して復号できる。このため、誤訂正による影響を低減させ、訂正能力を向上させることが可能となる。
【００６５】
例えば下部左の図は、２回目の復号Ｄ１の入力データ（復号Ｄ１入力）の例を示す。ビット７３１は、１回目の復号Ｄ１により訂正されたが、訂正前の値に戻されたビットを表す。
【００６６】
下部中央の図は、２回目の復号Ｄ１の復号結果（復号Ｄ１出力）を表す。１回目の復号Ｄ１入力（上部左の図）とは異なる入力データが入力されるため、１回目の復号Ｄ１出力（上部中央の図）とは異なる出力データであって、誤りが生じているビットが少なくなった出力データが出力される。
【００６７】
下部右の図は、２回目の復号Ｄ２の入力データ（復号Ｄ２入力）を表す。ビット７５１は、１回目の復号Ｄ２により訂正されたが、訂正前の値に戻されたビットを表す。このように値が戻されたとしても、他方の次元の復号である復号Ｄ１によりビットが正しく訂正されているため、次元２の誤り訂正符号により訂正可能な数以下の誤りとなり、２回目の復号Ｄ２による訂正を進めることが可能となる。
【００６８】
図９は、本実施形態による誤り訂正精度の改善効果の例を示す図である。図９は、復号Ｄ１およびＤ２として、それぞれ符号化率０．９８および０．９の誤り訂正符号の復号を行った結果を示す。図９のグラフの横軸は、ビットエラーレート（ＢＥＲ：Bit  Error  Rate）を示す。図９では、ビットエラーレートは、不揮発性メモリ２０から読み出された、復号する前の誤っているビットの確率（誤っているビット数を総ビット数で除算した値）を示す。図９のグラフの縦軸は、フレームエラーレート（ＦＥＲ：Frame  Error  Rate）を示す。
【００６９】
線９０１は、本実施形態を適用せず、複数の誤り訂正符号による復号結果を上書きして訂正を進める方式によるフレームエラーレートとビットエラーレートとの関係を示す。線９０２は、本実施形態によるフレームエラーレートとビットエラーレートとの関係を示す。例えばフレームエラーレート＝１０−２の場合、本実施形態を適用していない方式に比べ、本実施形態によればビットエラーレートが約５％向上している。
【００７０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７１】
１  メモリシステム
１０  メモリコントローラ
１１  制御部
１２  データバッファ
１３  メモリＩ／Ｆ
１４  符号化／復号部
１５  ホストＩ／Ｆ
１６  内部バス
１７  共有メモリ
２０  不揮発性メモリ
３０  ホスト
２０１ａ、２０１ｂ  符号化器
２０２ａ、２０２ｂ  復号器
【図１】
2020046823.tif 000003
【図２】
2020046823.tif 000004
【図３】
2020046823.tif 000005
【図４】
2020046823.tif 000006
【図５】
2020046823.tif 000007
【図６】
2020046823.tif 000008
【図７】
2020046823.tif 000009
【図８】
2020046823.tif 000010
【図９】
2020046823.tif 000011