(57)【要約】【課題】誤り訂正をより高精度に実行する。【解決手段】メモリシステムは、不揮発性メモリと、メモリコントローラと、を備える。不揮発性メモリは、誤り訂正符号を記憶する。メモリコントローラは、不揮発性メモリから読出し情報を取得する処理を行い、少なくとも読出し情報に基づいて計算される軟判定入力値と、軟判定入力値により復号された復号語と、に基づいて、復号語の信頼度と相関を持つ情報である信頼性メトリックを計算し、複数の信頼性メトリックの履歴または履歴から求められる統計情報である参照情報を記憶し、信頼性メトリックから信頼度を計算するための対応情報を用いて、信頼性メトリックから信頼度を計算し、復号語および信頼度に基づいて、復号情報を計算し、参照情報に基づいて、対応情報を更新する。【選択図】図６
2020046871.tif 000002
【特許請求の範囲】
【請求項１】
誤り訂正符号を記憶する不揮発性メモリと、
前記不揮発性メモリから読出し情報を取得する処理を行い、
少なくとも前記読出し情報に基づいて計算される軟判定入力値と、前記軟判定入力値により復号された復号語と、に基づいて、前記復号語の信頼度と相関を持つ情報である信頼性メトリックを計算し、
複数の前記信頼性メトリックの履歴または前記履歴から求められる統計情報である参照情報を記憶し、
前記信頼性メトリックから前記信頼度を計算するための対応情報を用いて、前記信頼性メトリックから前記信頼度を計算し、
前記復号語および前記信頼度に基づいて、復号情報を計算し、
前記参照情報に基づいて、前記対応情報を更新する、
メモリコントローラと、
を備えるメモリシステム。
【請求項２】
前記不揮発性メモリは、符号を構成するシンボルのうち少なくとも１つのシンボルが少なくとも第１の成分符号と前記第１の成分符号とは異なる第２の成分符号とによって保護されている多次元の誤り訂正符号を記憶し、
前記メモリコントローラは、少なくとも前記第１の成分符号の復号情報と、前記読出し情報に基づいて、前記第２の成分符号の前記軟判定入力値を計算する、
請求項１に記載のメモリシステム。
【請求項３】
前記復号情報は、前記第１の成分符号の外部値、および、前記第２の成分符号の外部値である、
請求項２に記載のメモリシステム。
【請求項４】
前記復号情報は、前記復号語、および、前記復号語の信頼度である
請求項２に記載のメモリシステム。
【請求項５】
前記メモリコントローラは、
前記第１の成分符号に対して、前記信頼性メトリックから前記信頼度を計算するための第１の対応情報を使用し、前記第２の成分符号に対して、前記信頼性メトリックから前記信頼度を計算するための第２の対応情報を使用する、
請求項２に記載のメモリシステム。
【請求項６】
前記信頼性メトリックは、前記軟判定入力値と前記復号語との間の距離である、
請求項１に記載のメモリシステム。
【請求項７】
前記対応情報は、前記復号語が正しい復号語であるという条件下での前記信頼性メトリックの出現確率である第１確率、および、前記復号語が正しい復号語でないという条件下での前記信頼性メトリックの出現確率である第２確率を含み、
前記メモリコントローラは、
前記参照情報を用いて、複数の前記信頼性メトリックを、正しい復号語から計算された前記信頼性メトリックを含む第１集合と、正しくない復号語から計算された前記信頼性メトリックを含む第２集合と、に分類し、
前記第１集合内での前記信頼性メトリックの出現確率から前記第１確率を計算し、
前記第２集合内での前記信頼性メトリックの出現確率から前記第２確率を計算し、
計算した前記第１確率および計算した前記第２確率を用いて、前記対応情報を更新する、
請求項１に記載のメモリシステム。
【請求項８】
前記対応情報は、前記復号語が正しい復号語である事前確率を示す第３確率、および、前記復号語が正しい復号語でない事前確率を示す第４確率を含み、
前記メモリコントローラは、
複数の前記信頼性メトリックを前記第１集合と前記第２集合とに分類するときに、前記第３確率と前記第４確率を計算し、
計算した前記第３確率および計算した前記第４確率を用いて、前記対応情報を更新する、
請求項７に記載のメモリシステム。
【請求項９】
前記対応情報は、前記復号語が正しい復号語である事前確率を示す第３確率、および、前記復号語が正しい復号語でない事前確率を示す第４確率を含み、
前記メモリコントローラは、
復号処理の反復回数に基づいて前記第３確率および前記第４確率を推定する、
請求項１に記載のメモリシステム。
【請求項１０】
前記対応情報は、前記復号語が正しい復号語である事前確率を示す第３確率、および、前記復号語が正しい復号語でない事前確率を示す第４確率を含み、
前記メモリコントローラは、
前記読出し情報および前記復号情報に基づいて硬判定値を計算し、前記硬判定値に対して計算したシンドロームに基づいて前記第３確率および前記第４確率を推定する、
請求項１に記載のメモリシステム。
【請求項１１】
前記メモリコントローラは、
前記信頼性メトリックの計算、および、前記信頼度の計算の少なくとも一方と並行して、前記対応情報を更新する処理を実行する、
請求項１に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下の実施形態は、メモリシステムに関する。
【背景技術】
【０００２】
メモリシステムでは、一般に、記憶するデータを保護するために、誤り訂正符号化されたデータが記憶される。このため、メモリシステムに記憶されたデータを読み出す際には、誤り訂正符号化されたデータに対する復号が行われる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特表２０１２−５０４８４２号公報
【特許文献２】特表２０１４−５２０４８９号公報
【特許文献３】米国特許出願公開第２０１１／０２６８１６８号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、誤り訂正をより高精度に実行可能なメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
実施形態によれば、メモリシステムは、不揮発性メモリと、メモリコントローラと、を備える。不揮発性メモリは、誤り訂正符号を記憶する。メモリコントローラは、不揮発性メモリから読出し情報を取得する処理を行い、少なくとも読出し情報に基づいて計算される軟判定入力値と、軟判定入力値により復号された復号語と、に基づいて、復号語の信頼度と相関を持つ情報である信頼性メトリックを計算し、複数の信頼性メトリックの履歴または履歴から求められる統計情報である参照情報を記憶し、信頼性メトリックから信頼度を計算するための対応情報を用いて、信頼性メトリックから信頼度を計算し、復号語および信頼度に基づいて、復号情報を計算し、参照情報に基づいて、対応情報を更新する。
【図面の簡単な説明】
【０００６】
【図１】図１は、データを誤り訂正符号で保護する動作の一般的な流れを説明するための図である。
【図２】図２は、積符号の一例を示す図である。
【図３】図３は、二次元の誤り訂正符号に対してターボ復号を実行する機能ブロックの一例を示すブロック図である。
【図４】図４は、図３に示す機能ブロックによる処理フローの一例を示すフローチャートである。
【図５】図５は、信頼度を用いた外部値の計算処理の一例を示すフローチャートである。
【図６】図６は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。
【図７】図７は、第１の実施形態に係る復号器の概略構成例を示すブロック図である。
【図８】図８は、本実施形態に係るＳＩＳＯ復号部が実現するターボ復号器の概略構成例を示すブロック図である。
【図９】図９は、図８に示すターボ復号器による復号処理の一例を示すフローチャートである。
【図１０】図１０は、信頼性メトリック、ヒストグラムおよび経験分布の例を示す図である。
【図１１】図１１は、条件付き確率を求める処理の一例を示す図である。
【図１２】図１２は、第１の実施形態に係るＳＩＳＯ復号部が実現する近似的ターボ復号器の概略構成例を示すブロック図である。
【図１３】図１３は、図１２に示す近似的ターボ復号器の処理フローの一例を示すフローチャートである。
【図１４】図１４は、第２の実施形態に係る次元１軟判定入力値計算部の動作フローの一例を示すフローチャートである。
【図１５】図１５は、第３の実施形態に係る次元１軟判定入力値計算部の動作フローの一例を示すフローチャートである。
【図１６】図１６は、次元ごとに異なる信頼性メトリックのヒストグラムを記憶する例を示す図である。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態に係るメモリシステムを詳細に説明する。なお、以下の実施形態により本発明が限定されるものではない。
【０００８】
近年、ＮＡＮＤ型フラッシュメモリなどの不揮発性メモリを利用したメモリシステムは、その高速性という特長を生かし、様々な場所で用いられている。しかしながら、不揮発性メモリから読出したデータには、不揮発性メモリに記憶されてからの時間経過や読出し・書込みの際に生じるノイズ等に起因するエラーが含まれる可能性がある。そのため、一般には、不揮発性メモリに記憶するデータに対して誤り訂正符号を用いた符号化処理が実行され、読出し時にはその誤り訂正符号を用いた復号処理が実行されることで、読出したデータに含まれているエラーが除去される。
【０００９】
図１は、データを誤り訂正符号で保護する動作の一般的な流れを説明するための図である。なお、本説明におけるユーザとは、例えばパーソナルコンピュータ、サーバ装置、ポータブルな情報機器、デジタルスチルカメラ等の情報処理装置であってよい。
【００１０】
ユーザ９３１は、書込み対象のデータ（以下、書込みデータという）をメモリシステム９００に対して送信する。メモリシステム９００は、ユーザ９３１から受け取った書込みデータを符号化器９４１を用いて符号化し、これにより生成された符号化データ（符号語）を不揮発性メモリ９２０に書込む。従って、不揮発性メモリ９２０に書込まれる符号化データには、基本的にはエラーが含まれていない。
【００１１】
不揮発性メモリ９２０に記憶されている符号化データは、例えばユーザ９３２からの読出し要求に応じて読出される。ここで、読出された符号化データにはエラーが含まれている可能性がある。そこで、読出された符号化データに含まれるエラーを復号器９４２を用いて除去しつつ復号を実行することで、オリジナルの符号語が復元される。その後、オリジナルの符号語または復元された符号化前の書込みデータがユーザ９３２へ送信される。なお、読出し要求を発行したユーザ９３２は、書込み要求を発行したユーザ９３１と同一のユーザであってもよいし、別のユーザであってもよい。
【００１２】
ここで、符号化器９４１が書込みデータを‘０’または‘１’で表現された二値情報（ビット）から構成される符号語に符号化し、その符号語が二値情報として不揮発性メモリ９２０に記憶された場合を想定する。以下、不揮発性メモリ９２０からのデータ読出しの際、記憶されたデータを‘０’であるか‘１’であるかを示す二値情報として読出して復号器９４２に入力する場合、その入力情報を硬判定入力（Hard-Input）と称する。それに対し、記憶されたデータを‘０’であった確率または‘１’であった確率の情報として読出して復号器９４２に入力する場合、その確率情報を軟判定入力（Soft-Input）と称する。
【００１３】
また、復号器９４２が出力する復号結果が、オリジナルの書込みデータが‘０’であったか‘１’であったかの二値情報である場合、その出力情報を硬判定出力（Hard-Output）と称する。それに対し、復号器９４２が出力する復号結果にオリジナルの書込みデータが‘０’であったか‘１’であったかの確率情報が含まれる場合、その出力情報を軟判定出力（Soft-Output）と称する。
【００１４】
復号器９４２への入力として軟判定入力を用いた場合、硬判定入力を用いた場合と比較してより多くの情報を用いた復号が可能となる。そのため、読出しデータにエラーが多く含まれる場合には、復号器９４２への入力として軟判定入力を用いた方が、正しいデータを復号できる確率を高めることができる。
【００１５】
軟判定入力値および軟判定出力値として、例えば情報を‘０’か‘１’かのビットで表現する二元符号（Binary  Code）に対しては、しばしばビットが‘０’である確率と‘１’である確率との比の自然対数であるＬＬＲ（Log-Likelihood-Ratio）表現が用いられる。二元符号の符号語はビット値のベクトルとして表現できるので、二元符号の軟判定入力値および軟判定出力値は、ＬＬＲ（実数値）のベクトルとして表現することができる。以降の実施形態では、説明の簡略化のため、軟判定入力値および軟判定出力値の確率情報がＬＬＲのベクトルとして表現されている場合を例示するが、このような場合に限定されず、種々変形することが可能である。
【００１６】
軟判定入力に対して軟判定出力を行う復号器（以下、ＳＩＳＯ（Soft-Input  Soft-Output）復号器という）は、例えば、多次元の誤り訂正符号の成分符号復号器として用いることができる。
【００１７】
ここで、多次元の誤り訂正符号とは、誤り訂正符号の少なくとも一つ以上の構成単位であるシンボルが、複数のより小規模な成分符号によって多重に保護されているものを指す。また、１シンボルは、例えば１ビット（二元体（binary  field）の元（element））、または、二元体以外の有限体（finite  field）などのアルファベットの元で構成される。
【００１８】
多次元の誤り訂正符号の例として、図２に積符号を示す。図２に示す積符号５００は、構成単位である各情報ビット（シンボルであってもよい）ｄ０〜ｄ３が、行方向（図面中横方向）と列方向（図面中縦方向）とのそれぞれで、情報長２ビットで且つパリティ長２ビットのハミング符号５１１〜５１５および５２１〜５２５で保護された構造を備える。このような積符号５００では、全ての情報ビットｄ０〜ｄ３およびパリティビットｐ０〜ｐ２０が行方向のハミング符号と列方向のハミング符号とで２重に保護されている。図２に示す積符号では、全てのシンボルが行方向（次元１と称される）および列方向（次元２と称される）の成分符号によって二重に保護されている。なお、多次元の誤り訂正符号としてはこれに限らず、例えば一般化ＬＤＰＣ符号（Generalized  Low  Density  Parity  Check  Code）などであってもよい。一般化ＬＤＰＣ符号を含む一般の多次元の誤り訂正符号では、シンボルごとに保護の多重度が異なっていてもよく、また、成分符号を次元１と次元２のようにグループ分けすることができないが、このような符号構成に対しても本技術は適用することが可能である。
【００１９】
このような多次元の誤り訂正符号に対しては、軟判定反復復号を行うことができる。以下では、軟判定反復復号としてターボ復号を用いる例を説明するが、ターボ復号以外のどのような軟判定反復復号を用いてもよい。図３は、二次元の誤り訂正符号に対してターボ復号を実行する機能ブロックの一例を示す図である。また、図４は、図３に示す機能ブロックによる処理フローの一例を示すフローチャートである。
【００２０】
図３に示すように、二次元の誤り訂正符号に対してターボ復号を実行する機能ブロックには、読出し情報メモリ９０１と、次元１加算器９１１と、次元１ＳＩＳＯ復号器９１２と、次元１外部値メモリ９１３と、次元２加算器９２１と、次元２ＳＩＳＯ復号器９２２と、次元２外部値メモリ９２３とが含まれる。
【００２１】
このような機能ブロックによるターボ復号動作では、図４に示すように、まず、不揮発性メモリ９２０から誤り訂正符号が軟判定値で読出される（ステップＳ９０１）。読み出された軟判定値の誤り訂正符号は、読出し情報として読出し情報メモリ９０１へ転送されて記憶される（ステップＳ９０２）。
【００２２】
つぎに、読出し情報メモリ９０１内の読出し情報と、次元２外部値メモリ９２３内の次元２外部値とが次元１加算器９１１により加算され、これにより、次元１軟判定入力値（＝読出し情報＋次元２外部値）が計算される（ステップＳ９０３）。なお、次元１外部値メモリ９１３および次元２外部値メモリ９２３はともに、本動作の起動時にリセット（ゼロクリア）されているものとする。
【００２３】
つづいて、次元１加算器９１１で計算された次元１軟判定入力値が、成分符号ごとに次元１ＳＩＳＯ復号器９１２に入力される。次元１ＳＩＳＯ復号器９１２は、入力された次元１軟判定入力値に対して次元１の軟判定復号を実行することで、次元１外部値を計算する（ステップＳ９０４）。計算された次元１外部値は、次元１外部値メモリ９１３へ転送されて記憶される（ステップＳ９０５）。
【００２４】
つぎに、読出し情報メモリ９０１内の読出し情報と、次元１外部値メモリ９１３内の次元１外部値とが次元２加算器９２１により加算され、これにより、次元２軟判定入力値（＝読出し情報＋次元１外部値）が計算される（ステップＳ９０６）。
【００２５】
つづいて、次元２加算器９２１で計算された次元２軟判定入力値が、成分符号ごとに次元２ＳＩＳＯ復号器９２２に入力される。次元２ＳＩＳＯ復号器９２２は、入力された次元２軟判定入力値に対して次元２の軟判定復号を実行することで、次元２外部値を計算する（ステップＳ９０７）。計算された次元２外部値は、次元２外部値メモリ９２３へ転送されて記憶される（ステップＳ９０８）。
【００２６】
つぎに、復号に成功したか否かが判定される（ステップＳ９０９）。復号に成功したとは、例えば正しいと判断できる復号語が発見されたことなどであってよい。復号に成功した場合（ステップＳ９０９のＹＥＳ）、外部の制御部等に復号の成功とともに発見された復号語が通知され（ステップＳ９１０）、本動作が終了する。一方、復号に成功していない場合（ステップＳ９０９のＮＯ）、本動作の反復回数が予め設定しておいた規定値に達しているか否かが判定され（ステップＳ９１１）、規定値に達していない場合（ステップＳ９１１のＮＯ）、ステップＳ９０３へリターンして、以降の動作を実行する。また、規定値に達していた場合（ステップＳ９１１のＹＥＳ）、外部の制御部等に復号の失敗が通知され（ステップＳ９１２）、本動作が終了する。なお、反復回数とは、例えば図４のステップＳ９０３〜Ｓ９０８の動作を繰り返した回数等であってよい。
【００２７】
次に、次元１ＳＩＳＯ復号器９１２および次元２ＳＩＳＯ復号器９２２に適用可能な、外部値を計算する復号アルゴリズムの例を説明する。外部値は、例えば、信頼性メトリックから信頼度を計算し、計算した信頼度を用いて計算することができる。信頼度は、復号語が真の復号語（正しい復号語）である軟判定入力値を与えられた下でのベイズ確率、または、その近似値である。信頼性メトリックは、信頼度と相関を持つ情報である。信頼度は、例えば、信頼性メトリックから信頼度を計算するための対応情報を用いて計算される。対応情報は、例えば、信頼性メトリックから信頼度を計算する信頼度計算関数である。信頼度計算関数は、信頼性メトリックと信頼度とを対応づけたテーブルの形式で表されてもよい。
【００２８】
図５は、信頼度を用いた外部値の計算処理の一例を示すフローチャートである。図５では、次元１ＳＩＳＯ復号器９１２が次元１外部値を計算する場合（ステップＳ９０４）を例に説明するが、次元２ＳＩＳＯ復号器９２２が次元２外部値を計算する場合（ステップＳ９０７）にも同様の手順を適用できる。
【００２９】
次元１ＳＩＳＯ復号器９１２は、軟判定入力値ｒを入力し、軟判定入力値ｒに基づき、復号語ｃを計算する（ステップＳ１０１）。軟判定入力値ｒは、例えば、次元１軟判定入力値に相当する。
【００３０】
次元１ＳＩＳＯ復号器９１２は、軟判定入力値ｒと復号語ｃとから、信頼性メトリックｍ＝ｆ（ｒ，ｃ）を計算する（ステップＳ１０２）。信頼性メトリックｍは、例えば、軟判定入力値ｒと復号語ｃとの間の距離である。すなわち、信頼性メトリックｍを計算する関数ｆ（ｒ，ｃ）は、例えば軟判定入力値ｒと復号語ｃの間の距離関数ｆ（ｒ，ｃ）＝｜ｒ−（１−２ｃ）｜２を用いることができる。信頼性メトリックｍは、これに限られず、例えば軟判定入力値ｒのノルム｜ｒ｜２などを用いてもよい。この例では信頼性メトリックｍは一次元の値であるが、それに限らず、例えば距離とノルムとを含む、多次元のベクトルであっても構わない。
【００３１】
次元１ＳＩＳＯ復号器９１２は、信頼度、すなわち復号語ｃが真の復号語ｘである確率φ＝Ｐ（ｃ＝ｘ｜ｒ）を、信頼度計算関数ｇ（ｍ）を用いて、φ≒ｇ（ｍ）として計算する（ステップＳ１０３）。
【００３２】
次元１ＳＩＳＯ復号器９１２は、軟判定入力値ｒ、復号語ｃ、および、確率φから、外部値ベクトルｖを計算し、外部値ベクトルｖを出力する（ステップＳ１０４）。例えば、ｉ番目のビットの軟判定入力値ｒｉを、復号語のｉ番目のビットの値をｃｉとして、ｉ番目のビットの外部値ｖｉを以下の式（１）で計算する。
【数１】
2020046871.tif 000003
【００３３】
なお式（１）は一例であり、これに限られるものではない。軟判定入力値ｒｉ、復号語ｃｉ、および、確率φから、外部値ベクトルｖの各要素である外部値ｖｉを計算する方法であればどのような計算方法を用いてもよい。
【００３４】
各次元の外部値は、復号処理で用いられる復号情報に相当する。例えば、次元２外部値から計算される次元１軟判定入力値が次元１ＳＩＳＯ復号器９１２に入力され、次元１ＳＩＳＯ復号器９１２による次元１の軟判定復号で用いられる。また、次元１外部値から計算される次元２軟判定入力値が次元２ＳＩＳＯ復号器９２２に入力され、次元２ＳＩＳＯ復号器９２２による次元２の軟判定復号で用いられる。
【００３５】
上述のように、信頼度計算関数ｇ（ｍ）は、信頼性メトリックｍを用いて、信頼度、すなわち復号語ｃが真の復号語ｘである確率φを近似的に求めるために用いられる関数である。信頼度計算関数ｇ（ｍ）がより正確に確率φを近似しているほど、結果的に高い訂正能力を達成することができる。
【００３６】
（第１の実施形態）
図６は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。図６に示すように、メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とを備える。メモリシステム１は、ホスト３０と接続可能であり、図６ではホスト３０と接続された状態が示されている。ホスト３０は、例えば、パーソナルコンピュータ、携帯端末などの電子機器であってよい。
【００３７】
不揮発性メモリ２０は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤ型フラッシュメモリ（以下、単にＮＡＮＤメモリという）である。以下の説明では、不揮発性メモリ２０としてＮＡＮＤメモリが用いられた場合を例示するが、不揮発性メモリ２０として３次元構造フラッシュメモリ、ＲｅＲＡＭ（Resistance  Random  Access  Memory）、ＦｅＲＡＭ（Ferroelectric  Random  Access  Memory）等のＮＡＮＤメモリ以外の記憶装置を用いることも可能である。また、不揮発性メモリ２０が半導体メモリであることは必須ではなく、半導体メモリ以外の種々の記憶媒体に対して本実施形態を適用することも可能である。
【００３８】
メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とが１つのパッケージとして構成されるメモリカード等であってもよいし、ＳＳＤ（Solid  State  Drive）等であってもよい。
【００３９】
メモリコントローラ１０は、ホスト３０からの書込み要求に従って不揮発性メモリ２０への書込みを制御する。また、ホスト３０からの読出し要求に従って不揮発性メモリ２０からの読出しを制御する。メモリコントローラ１０は、ホストＩ／Ｆ（ホストインタフェース）１５、メモリＩ／Ｆ（メモリインタフェース）１３、制御部１１、符号化／復号部（コーデック）１４およびデータバッファ１２を備える。ホストＩ／Ｆ１５、メモリＩ／Ｆ１３、制御部１１、符号化／復号部１４およびデータバッファ１２は、内部バス１６で相互に接続されている。
【００４０】
ホストＩ／Ｆ１５は、ホスト３０との間のインタフェース規格に従った処理を実施し、ホスト３０から受信した命令、書込み対象のユーザデータなどを内部バス１６に出力する。また、ホストＩ／Ｆ１５は、不揮発性メモリ２０から読出されて復元されたユーザデータ、制御部１１からの応答などをホスト３０へ送信する。
【００４１】
メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０への書込み処理を行う。また、メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０からの読出し処理を行う。
【００４２】
データバッファ１２は、メモリコントローラ１０がホスト３０から受信したユーザデータを不揮発性メモリ２０へ記憶するまでに一時記憶する。また、データバッファ１２は、不揮発性メモリ２０から読出したユーザデータをホスト３０へ送信するまでに一時記憶する。データバッファ１２には、例えば、ＳＲＡＭ（Static  Random  Access  Memory）やＤＲＡＭ（Dynamic  Random  Access  Memory）などの汎用メモリを用いることができる。
【００４３】
制御部１１は、メモリシステム１の各構成要素を統括的に制御する。制御部１１は、ホスト３０からホストＩ／Ｆ１５経由で命令を受けた場合に、その命令に従った制御を行う。例えば、制御部１１は、ホスト３０からの命令に従って、不揮発性メモリ２０へのユーザデータおよびパリティの書込みをメモリＩ／Ｆ１３へ指示する。また、制御部１１は、ホスト３０からの命令に従って、不揮発性メモリ２０からのユーザデータおよびパリティの読出しをメモリＩ／Ｆ１３へ指示する。
【００４４】
また、制御部１１は、ホスト３０からユーザデータの書込み要求を受信した場合、データバッファ１２に蓄積されるユーザデータに対して、不揮発性メモリ２０上の記憶領域（メモリ領域）を決定する。すなわち、制御部１１は、ユーザデータの書込み先を管理する。ホスト３０から受信したユーザデータの論理アドレスと該ユーザデータが記憶された不揮発性メモリ２０上の記憶領域を示す物理アドレスとの対応はアドレス変換テーブルとして記憶される。
【００４５】
また、制御部１１は、ホスト３０から読出し要求を受信した場合、読出し要求により指定された論理アドレスを上述のアドレス変換テーブルを用いて物理アドレスに変換し、該物理アドレスからの読出しをメモリＩ／Ｆ１３へ指示する。
【００４６】
ＮＡＮＤメモリでは、一般に、ページと呼ばれるデータ単位で、書込みおよび読出しが行われ、ブロックと呼ばれるデータ単位で消去が行われる。本実施形態では、この同一のワード線に接続される複数のメモリセルをメモリセルグループと呼ぶ。メモリセルがシングルレベルセル（ＳＬＣ）である場合は、１つのメモリセルグループが１ページに対応する。メモリセルがマルチレベルセル（ＭＬＣ）である場合は、１つのメモリセルグループが複数ページに対応する。また、各メモリセルはワード線に接続するとともにビット線にも接続される。従って、各メモリセルは、ワード線を識別するアドレスとビット線を識別するアドレスとで識別することが可能である。
【００４７】
ホスト３０から送信されるユーザデータは、内部バス１６に転送されてデータバッファ１２に一旦記憶される。符号化／復号部１４は、不揮発性メモリ２０に記憶されるユーザデータを符号化して符号語を生成する。また、符号化／復号部１４は、不揮発性メモリ２０から読出された受信語を復号してユーザデータを復元する。そこで符号化／復号部１４は、符号化器（Encoder）１７と復号器（Decoder）１８を備える。なお、符号化／復号部１４により符号化されるデータには、ユーザデータ以外にも、メモリコントローラ１０内部で用いる制御データ等が含まれてもよい。
【００４８】
次に、本実施形態の書込み処理について説明する。制御部１１は、不揮発性メモリ２０へのユーザデータの書込み時に、ユーザデータの符号化を符号化器１７に指示する。その際、制御部１１は、不揮発性メモリ２０における符号語の記憶場所（記憶アドレス）を決定し、決定した記憶場所もメモリＩ／Ｆ１３へ指示する。
【００４９】
符号化器１７は、制御部１１からの指示に基づいて、データバッファ１２上のユーザデータを符号化して符号語を生成する。符号化方式としては、例えば、ＢＣＨ（Bose-Chandhuri-Hocquenghem）符号やＲＳ（リード・ソロモン）符号を用いた符号化方式を採用することができる。符号化器１７により生成される符号語は、上述において図２を用いて例示した積符号５００などの多次元の誤り訂正符号である。図２に例示した積符号５００は、上述したように、構成単位である各情報ビット（シンボルであってもよい）ｄ０〜ｄ３が、行方向（図面中横方向）と列方向（図面中縦方向）とのそれぞれで、情報長２ビットで且つパリティ長２ビットのハミング符号である成分符号５１１〜５１５および５２１〜５２５で保護された構造を備える。このような積符号５００では、全ての情報ビットｄ０〜ｄ３およびパリティビットｐ０〜ｐ２０が行方向の成分符号（ハミング符号）５１１〜５１５と列方向の成分符号（ハミング符号）５２１〜５２５とで２重に保護されている。メモリＩ／Ｆ１３は、制御部１１から指示された不揮発性メモリ２０上の記憶場所へ符号語を記憶する制御を行う。
【００５０】
次に、本実施形態の不揮発性メモリ２０からの読出し時の処理について説明する。制御部１１は、不揮発性メモリ２０からの読出し時に、不揮発性メモリ２０上のアドレスを指定してメモリＩ／Ｆ１３へ読出しを指示する。また、制御部１１は、復号器１８へ復号の開始を指示する。メモリＩ／Ｆ１３は、制御部１１の指示に従って、不揮発性メモリ２０の指定されたアドレスから受信語を読出し、読出した受信語を復号器１８に入力する。復号器１８は、この不揮発性メモリ２０から読出された受信語を復号する。
【００５１】
復号器１８は、不揮発性メモリ２０から読出された受信語を復号する。図７は、復号器１８の概略構成例を示すブロック図である。復号器１８は、硬判定値を入力として復号を実行し、その結果として硬判定値を出力するＨＩＨＯ（hard-input  hard-output）復号部１８１と、軟判定値を入力として復号を実行し、その結果として軟判定値を出力するＳＩＳＯ（soft-input  soft-output）復号部１８２とを備える。
【００５２】
一般に、ＳＩＳＯ復号は、ＨＩＨＯ復号より誤り訂正能力は高いが処理時間が長いという特徴を持つ。そこで本実施形態では、まず、ＨＩＨＯ復号部１８１が、不揮発性メモリ２０から硬判定値として読出された受信語をＨＩＨＯ復号し、硬判定復号により復号できなかった受信語を軟判定値として読出すように構成する。そして、ＳＩＳＯ復号部１８２が、軟判定値として読出された受信語をＳＩＳＯ復号するように構成する。ただし、このような構成に限られず、ＨＩＨＯ復号を省略して全ての受信語にＳＩＳＯ復号を実行する構成など、種々変形することが可能である。
【００５３】
つづいて、図７に示すＳＩＳＯ復号部１８２のより詳細な構成を、図面を参照して詳細に説明する。図８は、本実施形態に係るＳＩＳＯ復号部が実現するターボ復号器１００の概略構成例を示すブロック図である。
【００５４】
図８に示すように、ターボ復号器１００は、読出し情報メモリ９０１と、次元１加算器９１１と、次元１ＳＩＳＯ復号器９６２と、次元１外部値メモリ９１３と、次元２加算器９２１と、次元２ＳＩＳＯ復号器９７２と、次元２外部値メモリ９２３と、参照情報メモリ９５１と、更新部９５２と、を備える。
【００５５】
ターボ復号器１００は、参照情報メモリ９５１および更新部９５２を追加したこと、並びに、次元１ＳＩＳＯ復号器９６２および次元２ＳＩＳＯ復号器９７２の機能が、図３と異なっている。他の機能は、図３と同様の機能を備えるため同一の記号を付し説明を省略する。
【００５６】
参照情報メモリ９５１は、信頼性メトリックの履歴、または、信頼性メトリックの履歴から求められる統計情報である参照情報を記憶する記憶部である。更新部９５２は、参照情報を参照して信頼度計算関数（対応情報）を更新する。信頼度計算関数の更新処理の詳細は後述する。
【００５７】
次元１ＳＩＳＯ復号器９６２は、計算した信頼性メトリックに基づく参照情報を参照情報メモリ９５１に記憶する点、および、更新部９５２から通知された信頼度計算関数ｇ（ｍ）を用いて信頼度を計算し、計算した信頼度を用いて外部値を計算する点が、図３の次元１ＳＩＳＯ復号器９１２と異なっている。
【００５８】
次元２ＳＩＳＯ復号器９７２は、計算した信頼性メトリックに基づく参照情報を参照情報メモリ９５１に記憶する点、および、更新部９５２から通知された信頼度計算関数ｇ（ｍ）を用いて信頼度を計算し、計算した信頼度を用いて外部値を計算する点が、図３の次元２ＳＩＳＯ復号器９２２と異なっている。
【００５９】
図９は、図８に示すターボ復号器１００による復号処理の一例を示すフローチャートである。なお、更新部９５２は、例えば本動作の起動時に、信頼度計算関数ｇ（ｍ）を予め定められた初期値に初期化する。
【００６０】
ステップＳ２０１からステップＳ２０５は、図４のステップＳ９０１からステップＳ９０５までと同様の処理なので、その説明を省略する。
【００６１】
なおステップＳ２０４では、次元１ＳＩＳＯ復号器９６２は、図５に示す手順に従い次元１外部値を計算する。このときに用いる信頼度計算関数ｇ（ｍ）は、更新部９５２から通知される。
【００６２】
次元１ＳＩＳＯ復号器９６２は、信頼性メトリックｍを計算するごとに、参照情報メモリ９５１の参照情報を更新する（ステップＳ２０６）。参照情報は、例えば、信頼性メトリックｍの値のヒストグラム（信頼性メトリックの履歴から求められる統計情報）である。次元１ＳＩＳＯ復号器９６２は、信頼性メトリックｍの履歴から求められる経験分布Ｐ＾（ｍ）をさらに参照情報として記憶してもよい。
【００６３】
図１０は、信頼性メトリック、ヒストグラムおよび経験分布の例を示す図である。図１０の上部は、図２に示すような５行、５列の積符号の各行（行１〜５）および各列（列１〜５）の信頼性メトリックｍの値のリスト（信頼性メトリックの履歴）を示す。図１０の下部は、このリストから計算した信頼性メトリックｍのヒストグラムおよび経験分布Ｐ＾（ｍ）を示す。
【００６４】
例えば行４と列２でｍ＝７の値が観測されていることから、ｍ＝７のヒストグラムのカウント値は２となる。また、行数＋列数が１０であることから、経験分布の値Ｐ＾（ｍ＝７）＝２／１０＝０．２となる。
【００６５】
図１０では、信頼性メトリックｍが０〜９までの整数を取り得る例が示されている。信頼性メトリックｍは、離散値である必要はなく、連続値であってもよい。信頼性メトリックｍが連続値の場合、参照情報メモリ９５１は、例えば連続値を所定の範囲で区切ったビンごとにヒストグラムを記憶すればよい。
【００６６】
図９に戻り、次元２ＳＩＳＯ復号器９７２による処理（ステップＳ２０７〜ステップＳ２１０）も、次元１ＳＩＳＯ復号器９６２と同様に実行される。
【００６７】
ステップＳ２０７からステップＳ２０９は、図４のステップＳ９０６からステップＳ９０８までと同様の処理なので、その説明を省略する。
【００６８】
なおステップＳ２０８では、次元２ＳＩＳＯ復号器９７２は、図５に示す手順に従い次元２外部値を計算する。このときに用いる信頼度計算関数ｇ（ｍ）は、更新部９５２から通知される。
【００６９】
次元２ＳＩＳＯ復号器９７２は、信頼性メトリックｍを計算するごとに、参照情報メモリ９５１の参照情報を更新する（ステップＳ２１０）。
【００７０】
ステップＳ２１１からステップＳ２１４は、図４のステップＳ９０９からステップＳ９１２までと同様の処理なので、その説明を省略する。
【００７１】
反復回数が規定値に規定値に達していない場合（ステップＳ２１３のＮＯ）、更新部９５２は、信頼度計算関数ｇ（ｍ）を更新し（ステップＳ２１５）、ステップＳ２０３へリターンして、以降の動作を実行する。信頼度計算関数ｇ（ｍ）の更新処理の詳細は後述する。
【００７２】
このように、第１の実施形態の更新部９５２は、次元１ＳＩＳＯ復号器９６２および次元２ＳＩＳＯ復号器９７２で用いる信頼度計算関数ｇ（ｍ）を動的に更新する。これにより、復号対象となる誤り訂正符号の構成やフラッシュメモリの状態によらず、高い訂正能力を達成することができる。
【００７３】
なお、次元１ＳＩＳＯ復号器９６２および次元２ＳＩＳＯ復号器９７２は、信頼性メトリックｍを計算するごとに信頼性メトリックのヒストグラムを求めて参照情報メモリ９５１のヒストグラムを更新する代わりに、信頼性メトリックの値自体を参照情報メモリ９５１に記憶してもよい。言い換えると次元１ＳＩＳＯ復号器９６２および次元２ＳＩＳＯ復号器９７２は、信頼性メトリックｍを計算するごとに、参照情報メモリ９５１に記憶された信頼性メトリックの履歴を更新してもよい。この場合、例えば更新部９５２は、信頼性メトリックｍの履歴からヒストグラムを計算し、信頼度計算関数ｇ（ｍ）の更新に用いればよい。
【００７４】
次に、信頼度計算関数ｇ（ｍ）の更新処理の詳細について説明する。更新部９５２は、信頼度計算関数ｇ（ｍ）を、例えば以下の式（２）に従って更新する。
【数２】
2020046871.tif 000004
【００７５】
Ｐ（ｍ｜ｃ＝ｘ）は復号語ｃが真の復号語ｘであるという条件下での信頼性メトリックｍの出現確率（第１確率）である。Ｐ（ｍ｜ｃ≠ｘ）は復号語ｃが真の復号語ｘでないという条件下での信頼性メトリックｍの出現確率（第２確率）である。Ｐ（ｃ＝ｘ）は、復号語ｃが真の復号語ｘである事前確率（第３確率）を示す。Ｐ（ｃ≠ｘ）は、復号語ｃが真の復号語ｘでないケースの事前確率（第４確率）を示す。
【００７６】
なお、事前確率Ｐ（ｃ＝ｘ）およびＰ（ｃ≠ｘ）の間には、Ｐ（ｃ＝ｘ）＋Ｐ（ｃ≠ｘ）＝１という関係が成立している。従って、事前確率Ｐ（ｃ＝ｘ）または事前確率Ｐ（ｃ≠ｘ）のうち一方が求まれば、他方も求めることができる。２つの事前確率の比Ｐ（ｃ＝ｘ）／Ｐ（ｃ≠ｘ）などが既知である場合も、事前確率Ｐ（ｃ＝ｘ）およびＰ（ｃ≠ｘ）は計算可能である。そこで以降では、Ｐ（ｃ＝ｘ）およびＰ（ｃ≠ｘ）を区別せずいずれも事前確率と呼ぶこととする。事前確率としては、例えば事前確率Ｐ（ｃ＝ｘ）＝Ｐ（ｃ≠ｘ）＝０．５のような固定値を用いることができる。
【００７７】
更新部９５２は、経験分布Ｐ＾（ｍ）に基づきクラスタリングアルゴリズムを適用することで、条件付き確率Ｐ（ｍ｜ｃ＝ｘ）およびＰ（ｍ｜ｃ≠ｘ）を求めることができる。更新部９５２は、例えば、経験分布Ｐ＾（ｍ）に対してｋ−ｍｅａｎｓアルゴリズムに基づくクラスタリング（ただしクラスタ数ｋ＝２）を適用することで、複数の信頼性メトリックを、クラスタＡおよびクラスタＢの２つのクラスタ（集合）のいずれかに分類するとともに、クラスタＡに属する条件下での信頼性メトリックｍの出現確率Ｐ（ｍ｜Ａ）と、クラスタＢに属する条件下での信頼性メトリックｍの出現確率Ｐ（ｍ｜Ｂ）とを推定することができる。
【００７８】
クラスタＡおよびクラスタＢのうち、一方が真の復号語ｘである復号語ｃから計算された信頼性メトリックが分類されたクラスタに対応し、他方が真の復号語ｘでない復号語ｃから計算された信頼性メトリックが分類されたクラスタに対応する。更新部９５２は、クラスタＡおよびクラスタＢのうち、いずれが真の復号語ｘである復号語ｃから計算された信頼性メトリックが分類されたクラスタであるかを、「信頼性メトリックｍが小さい方が確率φが大きい」という関係を利用して決定できる。また、更新部９５２は、各クラスタ内での各信頼性メトリックの出現確率を、Ｐ（ｍ｜ｃ＝ｘ）およびＰ（ｍ｜ｃ≠ｘ）のいずれかとして計算することができる。
【００７９】
例えば、更新部９５２は、各クラスタの信頼性メトリックｍの期待値、すなわち、ｍＡ＝Ｅ［ｍ｜Ａ］およびｍＢ＝Ｅ［ｍ｜Ｂ］を求める。更新部９５２は、「信頼性メトリックｍが小さい方が確率φが大きい」という関係を利用することで、以下の式（３）および式（４）のように条件付き確率Ｐ（ｍ｜ｃ＝ｘ）およびＰ（ｍ｜ｃ≠ｘ）を求めることができる。
【数３】
2020046871.tif 000005
【数４】
2020046871.tif 000006
【００８０】
信頼性メトリックと信頼度とを対応づけたテーブルの形式で信頼度計算関数を表す場合、更新部９５２は、式（２）を満たすような信頼性メトリックと信頼度とを対応づけたテーブルとなるようにテーブルを更新すればよい。
【００８１】
図１１は、更新部９５２がクラスタリングアルゴリズムによって条件付き確率Ｐ（ｍ｜ｃ＝ｘ）およびＰ（ｍ｜ｃ≠ｘ）を求める処理の一例を示す図である。
【００８２】
図１１の上部に示す経験分布Ｐ＾（ｍ）が与えられたとき、ｋ−ｍｅａｎｓアルゴリズムを適用することで、更新部９５２は、図１１の下部に示すような、クラスタＡに属する条件下での信頼性メトリックｍの出現確率Ｐ（ｍ｜Ａ）、および、クラスタＢに属する条件下での信頼性メトリックｍの出現確率Ｐ（ｍ｜Ｂ）を計算することができる。
【００８３】
ここで、クラスタＡの信頼性メトリックｍの期待値は０．６７であり、クラスタＢの信頼性メトリックｍの期待値は７．００である。従って、クラスタＡが、信頼性メトリックｍが小さい、すなわち復号語ｃが真の復号語ｘと等しい場合に対応するクラスタであることが分かる。従って、更新部９５２は、条件付き確率Ｐ（ｍ｜ｃ＝ｘ）は、出現確率Ｐ（ｍ｜Ａ）であり、条件付き確率Ｐ（ｍ｜ｃ≠ｘ）は、出現確率Ｐ（ｍ｜Ｂ）であると決定できる。
【００８４】
なお適用可能なクラスタリングアルゴリズムはｋ−ｍｅａｎｓアルゴリズムに限られず、どのようなクラスタリングアルゴリズムを適用してもよい。例えば、ＥＭ（Expectation  Maximization）アルゴリズムに基づく混合分布のパラメータ推定手法などのアルゴリズムを適用することが可能である。
【００８５】
なお、上述のように、事前確率Ｐ（ｃ＝ｘ）、Ｐ（ｃ≠ｘ）としては固定値を用いてもよいが、より正しい事前確率の値を用いることで、信頼度計算関数ｇ（ｍ）による信頼度の近似精度を上げることができる。
【００８６】
更新部９５２は、例えば、Ｐ（ｍ｜ｃ＝ｘ）とＰ（ｍ｜ｃ≠ｘ）と同様に、クラスタリングアルゴリズムによって事前確率を推定することができる。例えばＥＭアルゴリズムに基づく混合分布のパラメータ推定手法では、推定の過程で事前確率が求められる。従って更新部９５２は、推定の過程で求められる事前確率を、信頼度計算関数ｇ（ｍ）の更新処理で用いてもよい。
【００８７】
また、一般に復号語ｃが真の復号語ｘと等しい（＝訂正に成功している）確率は、反復復号処理の後半になるにつれ増加する。すなわち、反復復号の反復回数と事前確率とは相関を持っている。また、一般に読出し情報、次元１外部値、および、次元２外部値から計算した硬判定値にエラーが少ないとき、硬判定値に対して計算したシンドロームが０である確率が高くなり、また復号語ｃが真の復号語ｘと等しい（＝訂正に成功している）確率も高くなるという関係が成立している。すなわち、「硬判定値に対して計算したシンドロームが０である数」と事前確率とは相関を持っている。更新部９５２は、このような事前確率と相関を持つ値から、事前確率を推定することも可能である。
【００８８】
更新部９５２は、例えば反復回数が大きくなるに従い、復号語ｃが真の復号語ｘである事前確率Ｐ（ｃ＝ｘ）を増加させてもよい。また更新部９５２は、例えばシンドロームが０である数が大きいほど、復号語ｃが真の復号語ｘである事前確率Ｐ（ｃ＝ｘ）を増加させてもよい。
【００８９】
信頼性メトリックと信頼度の対応関係は、用いる符号やメモリシステムにかかるストレス条件などの条件に依存して変化する。そのため、予め特定の条件に対してのみ最適化された固定の信頼度計算関数ｇ（ｍ）を用いる構成では、メモリシステムにかかるストレス条件等が変化した場合に、信頼度の計算精度が低下し、その結果誤り訂正能力が低下するおそれがある。これに対して、第１の実施形態では、多次元の誤り訂正符号の軟判定復号時に用いられる信頼度計算関数を、復号処理中に動的に更新する。これにより、より高い精度で信頼度を計算することができ、この結果、ストレス条件等によらず高い訂正能力を実現することが可能となる。また、信頼度計算関数を予め最適化する必要がなくなる。
【００９０】
（第２の実施形態）
ＳＩＳＯ復号器を用いたターボ復号器は、確率情報である外部値を外部値メモリに記憶しておかなければならないため、復号に必要なメモリ量が増大してしまう可能性がある。そこで、復号に必要なメモリ量を削減することが可能なメモリシステムの提供が望まれる。
【００９１】
第２の実施形態では、復号に必要なメモリ量を削減することが可能なメモリシステムの例を説明する。第２の実施形態のメモリシステムの概略構成は、第１の実施形態のメモリシステムの概略構成を示す図６と同様であるため説明を省略する。第２の実施形態では、ＳＩＳＯ復号部１８２が実現するターボ復号器の機能が第１の実施形態と異なる。
【００９２】
図１２は、本実施形態に係るＳＩＳＯ復号部が実現する近似的ターボ復号器１００−２の概略構成例を示すブロック図である。また、図１３は、図１２に示す近似的ターボ復号器１００−２の処理フローの一例を示すフローチャートである。
【００９３】
図１２に示すように、ＳＩＳＯ復号部１８２が実現する近似的ターボ復号器１００−２は、読出し情報メモリ１０１と、中間値メモリ１０２と、次元１軟判定入力値計算部１１１と、次元１成分符号ＳＩＳＯ復号器１１２と、次元２軟判定入力値計算部１２１と、次元２成分符号ＳＩＳＯ復号器１２２と、参照情報メモリ１５１と、更新部１５２と、を備える。
【００９４】
次元１軟判定入力値計算部１１１および次元２軟判定入力値計算部１２１は、読出し情報メモリ１０１に記憶された軟判定値の読出し情報と、中間値メモリ１０２に記憶された次元１の中間値（次元１中間値）および次元２の中間値（次元２中間値）とから、各次元の軟判定入力値を成分符号ごとに計算する。
【００９５】
なお、中間値とは、復号の途中で計算される各成分符号の中間の硬判定値と、この中間の硬判定値の信頼度とからなる情報であり、次元１の外部値（次元１外部値）および次元２の外部値（次元２外部値）の近似計算に必要な情報である。本実施形態では、中間の硬判定値の信頼度が、信頼度計算関数によって計算される。中間の硬判定値の信頼度の計算方法の詳細は後述する。
【００９６】
次元１成分符号ＳＩＳＯ復号器１１２および次元２成分符号ＳＩＳＯ復号器１２２は、入力された各次元の軟判定入力値に対して成分符号ごとにＳＩＳＯ復号を実行することで、各次元の中間値を計算する。
【００９７】
本実施形態では、各次元の中間値、すなわち、各成分符号の中間の硬判定値、すなわち復号語と、中間の硬判定値の信頼度、すなわち復号語の信頼度とが、復号処理で用いられる復号情報に相当する。次元１成分符号ＳＩＳＯ復号器１１２および次元２成分符号ＳＩＳＯ復号器１２２は、更新部１５２から通知された信頼度計算関数ｇ（ｍ）を用いて、中間の硬判定値の信頼度を計算する。また、次元１成分符号ＳＩＳＯ復号器１１２は、信頼性メトリックに基づく参照情報を参照情報メモリ１５１に記憶する。
【００９８】
参照情報メモリ１５１は、信頼性メトリックの履歴、または、信頼性メトリックの履歴から求められる統計情報である参照情報を記憶する記憶部である。更新部１５２は、参照情報を参照して信頼度計算関数（対応情報）を更新する。
【００９９】
図１２に示す近似的ターボ復号器１００−２によるターボ復号動作では、図１３に示すように、まず、不揮発性メモリ２０から多次元の誤り訂正符号が軟判定値で読出される（ステップＳ３０１）。読出された軟判定値の多次元の誤り訂正符号は、読出し情報として読出し情報メモリ１０１へ転送されて記憶される（ステップＳ３０２）。
【０１００】
つぎに、読出し情報メモリ１０１内の読出し情報と中間値メモリ１０２内の次元１中間値および次元２中間値とを次元１軟判定入力値計算部１１１に入力して、次元１軟判定入力値を計算する（ステップＳ３０３）。なお、本動作の起動時に、中間値メモリ１０２がリセット（ゼロクリア）されているものとする。従って、最初の次元１軟判定入力値の計算処理では、次元１中間値および次元２中間値として例えば０ビットが連続するデータが次元１軟判定入力値計算部１１１に入力される。
【０１０１】
つぎに、次元１軟判定入力値計算部１１１で計算された次元１軟判定入力値を次元１の成分符号ごとに次元１成分符号ＳＩＳＯ復号器１１２に入力して、次元１中間値、すなわち復号語と復号語の信頼度とを計算する（ステップＳ３０４）。次元１成分符号ＳＩＳＯ復号器１１２は、第１の実施形態と同様の処理により、復号語の信頼度を計算する。計算された次元１中間値は、中間値メモリ１０２に転送されて記憶される（ステップＳ３０５）。
【０１０２】
次元１成分符号ＳＩＳＯ復号器１１２は、次元１中間値の計算時に、信頼性メトリックを計算する。次元１成分符号ＳＩＳＯ復号器１１２は、信頼性メトリックｍを計算するごとに、参照情報メモリ１５１の参照情報を更新する（ステップＳ３０６）。参照情報は、例えば、信頼性メトリックｍの値のヒストグラムである。
【０１０３】
つぎに、読出し情報メモリ１０１内の読出し情報と中間値メモリ１０２内の次元１中間値および次元２中間値とを次元２軟判定入力値計算部１２１に入力して、次元２軟判定入力値を計算する（ステップＳ３０７）。なお、最初の次元２軟判定入力値の計算処理時には、中間値メモリ１０２に次元２中間値が記憶されていないため、最初の次元２軟判定入力値の計算処理では、次元１中間値と例えば０ビットが連続するデータと次元２軟判定入力値計算部１２１に入力される。
【０１０４】
つぎに、次元２軟判定入力値計算部１２１で計算された次元２軟判定入力値を次元２の成分符号ごとに次元２成分符号ＳＩＳＯ復号器１２２に入力して、次元２中間値、すなわち復号語と復号語の信頼度とを計算する（ステップＳ３０８）。次元２成分符号ＳＩＳＯ復号器１２２は、第１の実施形態と同様の処理により、復号語の信頼度を計算する。計算された次元２中間値は、中間値メモリ１０２に転送されて記憶される（ステップＳ３０９）。
【０１０５】
次元２成分符号ＳＩＳＯ復号器１２２は、次元２中間値の計算時に、信頼性メトリックを計算する。次元２成分符号ＳＩＳＯ復号器１２２は、信頼性メトリックｍを計算するごとに、参照情報メモリ１５１の参照情報を更新する（ステップＳ３１０）。
【０１０６】
つぎに、復号に成功したか否かが判定される（ステップＳ３１１）。復号に成功したとは、例えば正しいと判断できる復号語が発見されたことであってよい。また、発見された復号語が正しいか否かの判断は、例えば符号化／復号部１４内の不図示の制御部が実行してもよい。復号に成功した場合（ステップＳ３１１のＹＥＳ）、外部の制御部１１等に復号の成功とともに発見された復号語が通知され（ステップＳ３１２）、本動作が終了する。一方、復号に成功していない場合（ステップＳ３１１のＮＯ）、本動作の反復回数が予め設定しておいた規定値に達しているか否かが判定される（ステップＳ３１３）。
【０１０７】
反復回数が規定値に規定値に達していない場合（ステップＳ３１３のＮＯ）、更新部１５２は、信頼度計算関数ｇ（ｍ）を更新し（ステップＳ３１５）、ステップＳ３０３へリターンして、以降の動作を実行する。更新部１５２は、第１の実施形態の更新部９５２と同様の手順で信頼度計算関数ｇ（ｍ）を更新することができる。
【０１０８】
また、規定値に達していた場合（ステップＳ３１３のＹＥＳ）、外部の制御部１１等に復号の失敗が通知され（ステップＳ３１４）、本動作が終了する。なお、反復回数とは、例えば図１３のステップＳ３０３〜Ｓ３１０の動作を繰り返した回数等であってよい。
【０１０９】
つづいて、図１３のステップＳ３０３およびＳ３０６において、図１２における次元１軟判定入力値計算部１１１および次元２軟判定入力値計算部１２１が次元１軟判定入力値および次元２軟判定入力値を計算する際の動作フローを、図面を参照して詳細に説明する。図１４は、本実施形態に係る次元１軟判定入力値計算部の動作フローの一例を示すフローチャートである。なお、図１４には、次元１軟判定入力値計算部１１１の動作を示すが、同様の動作を次元２軟判定入力値計算部１２１に適用することが可能である。
【０１１０】
図１４に示すように、次元１軟判定入力値計算部１１１は、次元１軟判定入力値を計算するにあたり、まず、読出し情報メモリ１０１から読出し情報を入力するとともに、中間値メモリ１０２から次元１中間値および次元２中間値を入力する（ステップＳ３２１）。
【０１１１】
つぎに、次元１軟判定入力値計算部１１１は、入力した読出し情報と次元１中間値および次元２中間値とから次元２外部値の近似値を計算する。具体的には、次元１軟判定入力値計算部１１１は、次元２中間値における次元２の復号語、次元２の復号語の信頼度から、式（１）に従って次元２外部値を計算する。
【０１１２】
ただし式（１）を計算するためには次元２軟判定入力値ｒの値が必要であるが、本実施形態では、現時点で次元２軟判定入力値が未知である。そこで本実施形態では、読出し情報を次元２軟判定入力値ｒの近似値として代用して次元２外部値を近似的に計算する（ステップＳ３２２）。
【０１１３】
つぎに、ステップＳ３２２で計算された次元２外部値の近似値と読出し情報とを加算することで、次元１軟判定入力値を計算する（ステップＳ３２３）。その後、計算された次元１軟判定入力値を次元１の成分符号ごとに次元１成分符号ＳＩＳＯ復号器１１２へ出力し（ステップＳ３２４）、図１３に示す動作へリターンする。
【０１１４】
以上のように、読出し情報を軟判定入力値の近似値として代用した場合でも、最終的に計算される軟判定入力値は、本来のターボ復号において計算されるべき軟判定入力値に対して、よい近似となっている。これは、本実施形態によれば、例えば図３に例示した構成における各次元の外部値メモリ（次元１外部値メモリ９１３および次元２外部値メモリ９２３）を、より容量の小さい中間値メモリ１０２で代用することができることを示唆している。
【０１１５】
具体的には、第１の実施形態では、外部値を次元ごとに記憶しておくメモリが必要であったが、本実施形態では、外部値として硬判定値（復号語に相当）および復号語の信頼度を記憶しておけばよく、また、全ての次元に対して１つのメモリを共有することが可能となる。その結果、本実施形態によれば、復号に必要なメモリ量を削減することが可能である。
【０１１６】
以上のように、第２の実施形態も第１の実施形態と同様に、軟判定復号時に用いられる信頼度計算関数を、復号処理中に動的に更新することができる。また、第２の実施形態では、復号に必要なメモリ量を削減することが可能となる。
【０１１７】
（第３の実施形態）
つぎに、第３の実施形態に係るメモリシステムについて、図面を参照して詳細に説明する。本実施形態における符号化／復号部を含むメモリシステムの構成は、第２の実施形態において図５、図６、および、図１２を用いて例示したメモリシステムと同様であってよいため、ここでは重複する説明を省略する。また、本実施形態に係る近似的ターボ復号器の処理フローも第２の実施形態において図１３を用いて説明した処理フローと同様であってよいため、ここでは重複する説明を省略する。ただし、本実施形態では、次元１軟判定入力値計算部１１１および次元２軟判定入力値計算部１２１の動作フローが、第２の実施形態において図１４を用いて例示した動作フローとは異なる。
【０１１８】
図１５は、本実施形態に係る次元１軟判定入力値計算部の動作フローの一例を示すフローチャートである。なお、図１５には、次元１軟判定入力値計算部１１１の動作を示すが、同様の動作を次元２軟判定入力値計算部１２１に適用することが可能である。また、図１５に示す動作において、図１４に示す動作と同様の動作については、同一の符号を付し、詳細な説明を省略する。
【０１１９】
図１５に示すように、次元１軟判定入力値計算部１１１は、まず、図１４におけるステップＳ３２１と同様にして、読出し情報と次元１中間値および次元２中間値とを入力し、入力した読出し情報と次元１中間値および次元２中間値とから次元２外部値の近似値を計算する。本実施形態では、次元１軟判定入力値計算部１１１は、次元１中間値における次元１の復号語、次元１の復号語の信頼度から、式（１）に基づいて次元１の外部値の近似値を計算する。ただし式（１）を計算するためには軟判定入力値ｒの値が必要であるが、本実施形態では、現時点で次元１軟判定入力値が未知である。そこで本実施形態では、読出し情報を次元１軟判定入力値の近似値として代用して次元１外部値の近似値を計算する。（ステップＳ５２１）
【０１２０】
つづいて、次元１軟判定入力値計算部１１１は、次元１中間値における次元２の復号語、次元２の復号語の信頼度から、式（１）に基づいて次元２の外部値の近似値を計算する。ただし式（１）を計算するためには次元２軟判定入力値ｒの値が必要であるが、本実施形態では、現時点で次元２軟判定入力値が未知である。そこで本実施形態では、読出し情報と次元１外部値の加算結果を次元２軟判定入力値の近似値として代用して次元２外部値の近似値を計算する。（ステップＳ５２２）
【０１２１】
その後、次元１軟判定入力値計算部１１１は、図１４のステップＳ３２４〜Ｓ３２５で説明した動作と同様の動作を実行することで、次元２外部値の近似値と読出し情報とを加算して次元１軟判定入力値を計算し（ステップＳ５２３）、計算された次元１軟判定入力値を次元１の成分符号ごとに次元１成分符号ＳＩＳＯ復号器１１２へ出力して（ステップＳ５２４）、図１３に示す動作へリターンする。
【０１２２】
以上のように、一方の次元の対数事後確率比を他方の次元の軟判定入力値の近似値として代用した場合でも、最終的に計算される軟判定入力値は、本来のターボ復号において計算されるべき軟判定入力値に対して、よい近似となっている。これにより、第２の実施形態と同様に、例えば図３に例示した構成における各次元の外部値メモリ（次元１外部値メモリ９１３および次元２外部値メモリ９２３）を、より容量の小さい中間値メモリ１０２で代用することが可能となり、復号に必要なメモリ量を削減することが可能である。
【０１２３】
その他の構成、動作および効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【０１２４】
（第４の実施形態）
つぎに、第４の実施形態に係るメモリシステムについて説明する。第２の実施形態において図１４を用いて例示した次元１軟判定入力値計算部１１１および次元２軟判定入力値計算部１２１の動作フローと、第３の実施形態において図１５を用いて例示した次元１軟判定入力値計算部１１１および次元２軟判定入力値計算部１２１の動作フローとは、特定の条件で選択的に切り替えて使い分けることが可能である。例えば、次元１または次元２の復号語の信頼度が予め定めておいた閾値より高い場合には、図１５に示した動作フローを用いて次元１軟判定入力値または次元２軟判定入力値を求め、それ以外の場合には、図１４に示した動作フローを用いて次元１軟判定入力値または次元２軟判定入力値を求めるというように、復号語の信頼度に基づいて実行する動作フローを切り替えるように構成することも可能である。
【０１２５】
そのような構成においても、上述した実施形態と同様に、例えば図３に例示した構成における各次元の外部値メモリ９１３および９２３を、より容量の小さい中間値メモリ１０２で代用することが可能となり、復号に必要なメモリ量を削減することが可能である。
【０１２６】
その他の構成、動作および効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【０１２７】
（変形例１）
上記各実施形態では、例えば各次元について共通の信頼度計算関数ｇ（ｍ）を用いていた。信頼度計算関数ｇ（ｍ）は、予め定められた規則に従い変更されてもよい。
【０１２８】
信頼度計算関数ｇ（ｍ）を変更する規則としては、例えば以下の（Ｒ１）〜（Ｒ３）に示すような規則を用いることができる。
（Ｒ１）次元１の成分符号を復号する場合と、次元２の成分符号を復号する場合とで、それぞれ異なる信頼度計算関数ｇ（ｍ）を用いる。
（Ｒ２）復号語ｃを得るために複数種類の復号器（例えばBounded  Distance  Decoder、Chase  decoder、Ordered  Statistics  Decoderなど）が使用されている場合、いずれの復号器から得られた復号語であるかによって、それぞれ異なる信頼度計算関数ｇ（ｍ）を用いる。
（Ｒ３）復号語ｃを得るために複数種類の復号器が使用されている場合、複数種類の復号器の出力した復号語ｃが一致しているか否かによって、それぞれ異なる信頼度計算関数ｇ（ｍ）を用いる。
【０１２９】
（Ｒ３）の場合、各復号器は、例えば以下のようにして、使用する信頼度計算関数ｇ（ｍ）を決定する。
（Ｒ３−１）復号語ｃが一致している復号器については、共通の信頼度計算関数ｇ（ｍ）を使用し、不一致の復号器については、各復号器に対して定められた個別の信頼度計算関数ｇ（ｍ）を使用する。
（Ｒ３−２）復号語ｃが一致している復号器については、復号語ｃが一致している場合の関数として定められた第１の共通の信頼度計算関数ｇ（ｍ）を使用し、不一致の復号器については、復号語ｃが一致していない場合の関数として定められた第２の共通の信頼度計算関数ｇ（ｍ）を使用する。
（Ｒ３−３）すべての復号器の復号語ｃが一致している場合は、共通の信頼度計算関数ｇ（ｍ）を使用する。復号語ｃが一致しない復号器が存在する場合は、正しいと推定される復号器のみを用いて、当該復号器に対して定められた信頼度計算関数ｇ（ｍ）を使用する。
【０１３０】
異なる信頼度計算関数ｇ（ｍ）を用いる場合、更新部（更新部９５２、更新部１５２）は、使用する信頼度計算関数ｇ（ｍ）ごとにそれぞれ異なる初期値を初期化に用いる。また、参照情報メモリ（参照情報メモリ９５１、参照情報メモリ１５１）は、信頼度計算関数ｇ（ｍ）ごとにそれぞれ異なる信頼性メトリックｍのヒストグラムを記憶する。また、更新部（更新部９５２、更新部１５２）は、信頼度計算関数ｇ（ｍ）ごとに更新値を計算する。
【０１３１】
図１６は、次元ごとに異なる信頼性メトリックｍのヒストグラムを記憶する例を示す図である。図１６では、行１〜５に対応する次元１の信頼性メトリックｍのヒストグラムおよび経験分布、並びに、列１〜５に対応する次元２の信頼性メトリックｍのヒストグラムおよび経験分布の例が示されている。
【０１３２】
このように、規則に従い異なる信頼度計算関数ｇ（ｍ）を用いることで、信頼度計算関数ｇ（ｍ）がより精度よく信頼度φ＝Ｐ（ｃ＝ｘ｜ｒ）を近似できるようになり、より高い訂正能力を得ることができると期待される。
【０１３３】
（変形例２）
更新部（更新部９５２、更新部１５２）は、信頼度計算関数ｇ（ｍ）の更新処理を、他の処理の少なくとも一部と並行して実行してもよい。変形例１の（Ｒ１）のように次元ごとに異なる信頼度計算関数ｇ（ｍ）を用いる場合であれば、更新部は、複数の次元のうち、いずれかの復号処理を実行中に、他の次元で使用する信頼度計算関数ｇ（ｍ）の更新処理を実行してもよい。
【０１３４】
（変形例３）
これまでは主に二次元の誤り訂正符号を例に説明したが、三次元以上の誤り訂正符号に対しても同様に上記実施形態を適用できる。また、BCH符号、RS符号などを含む多次元でない誤り訂正符号に対しても上記実施形態を適用しうる。例えば、多次元でない誤り訂正符号に対して複数回の復号処理を実行して最終的な復号結果を出力する構成であって、各復号処理で上記のように信頼性メトリックおよび信頼度を計算する構成に対しても適用しうる。
【０１３５】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１３６】
１  メモリシステム
１０  メモリコントローラ
１１  制御部
１２  データバッファ
１３  メモリＩ／Ｆ
１４  符号化／復号部
１５  ホストＩ／Ｆ
１６  内部バス
１７  符号化器
１８  復号器
２０  不揮発性メモリ
３０  ホスト
１００  ターボ復号器
１００−２  近似的ターボ復号器
１０１  読出し情報メモリ
１０２  中間値メモリ
１１１  次元１軟判定入力値計算部
１１２  次元１成分符号ＳＩＳＯ復号器
１２１  次元２軟判定入力値計算部
１２２  次元２成分符号ＳＩＳＯ復号器
１５１  参照情報メモリ
１５２  更新部
１８１  ＨＩＨＯ復号部
１８２  ＳＩＳＯ復号部
９１１  次元１加算器
９１２  次元１ＳＩＳＯ復号器
９１３  次元１外部値メモリ
９２０  不揮発性メモリ
９２１  次元２加算器
９２２  次元２ＳＩＳＯ復号器
９２３  次元２外部値メモリ
９４１  符号化器
９４２  復号器
９５１  参照情報メモリ
９５２  更新部
９６２  次元１ＳＩＳＯ復号器
９７２  次元２ＳＩＳＯ復号器
【図１】
2020046871.tif 000007
【図２】
2020046871.tif 000008
【図３】
2020046871.tif 000009
【図４】
2020046871.tif 000010
【図５】
2020046871.tif 000011
【図６】
2020046871.tif 000012
【図７】
2020046871.tif 000013
【図８】
2020046871.tif 000014
【図９】
2020046871.tif 000015
【図１０】
2020046871.tif 000016
【図１１】
2020046871.tif 000017
【図１２】
2020046871.tif 000018
【図１３】
2020046871.tif 000019
【図１４】
2020046871.tif 000020
【図１５】
2020046871.tif 000021
【図１６】
2020046871.tif 000022