JP2019054448A - メモリシステム - Google Patents

Abstract

【課題】誤り訂正能力を低下させずにレイテンシを高める。【解決手段】実施形態に係るメモリシステムは、複数のテストパタンから中間復号語を検出するテストパタン復号部と、前記テストパタン復号部で検出された中間復号語と前記受信語とのユークリッド距離を計算するユークリッド距離計算部と、最尤復号語候補を保持する最尤復号語選択部とを備え、前記最尤復号語選択部は、前記テストパタン復号部で検出された中間復号語である第１の中間復号語のユークリッド距離が、前記保持している最尤復号語候補のユークリッド距離よりも短い場合、前記第１の中間復号語で前記保持している最尤復号語候補を更新し、前記テストパタン復号部は、中間復号語のユークリッド距離が前記最尤復号語選択部に保持されている前記最尤復号語候補の前記ユークリッド距離よりも短くなる可能性のないテストパタンに対する復号を実行しない。【選択図】図２

Description

以下の実施形態は、一般的に、メモリシステムに関する。

メモリシステムでは、一般に、記憶するデータを保護するために、符号化されたデータが記憶される。このため、メモリシステムに記憶されたデータを読み出す際には、誤り訂正符号化されたデータに対する復号が行われる。

米国特許第８３４１５０２号明細書 米国特許第８４６８４３１号明細書

Antoine Valembois and Marc Fossorier, Senior Member, IEEE, "Box and Match Techniques Applied to Soft-Decision Decoding" IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50, NO. 5, MAY 2004.

本発明の一つの実施形態は、誤り訂正能力を低下させずにレイテンシを高めることが可能なメモリシステムを提供することを目的とする。

実施形態に係るメモリシステムは、不揮発性メモリと、前記不揮発性メモリから読み出された受信語を軟判定値の符号語に変換する軟判定値変換部と、前記軟判定値の符号語に対する複数のテストパタンのリストを生成するリスト生成部と、前記リストに含まれるテストパタンから中間復号語を検出するテストパタン復号部と、前記テストパタン復号部で検出された中間復号語と前記受信語とのユークリッド距離を計算するユークリッド距離計算部と、最尤復号語候補を保持する最尤復号語選択部とを備え、前記最尤復号語選択部は、前記テストパタン復号部で検出された中間復号語である第１の中間復号語のユークリッド距離が、前記保持している最尤復号語候補のユークリッド距離よりも短い場合、前記第１の中間復号語で前記保持している最尤復号語候補を更新し、最終的に保持している前記最尤復号語候補を軟判定出力値として出力し、前記テストパタン復号部は、中間復号語のユークリッド距離が前記最尤復号語選択部に保持されている前記最尤復号語候補の前記ユークリッド距離よりも短くなる可能性のないテストパタンに対する復号を実行しない。

図１は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。 図２は、第１の実施形態に係るメモリＩ／Ｆのより詳細な構成例を示すブロック図である。 図３は、第１の実施形態における受信語のＬＬＲ列のソートを説明するための図である。 図４は、第１の実施形態に係るソート後のＬＬＲ列に対するフリップ対象範囲を示す図である。 図５は、第１の実施形態に係る最尤復号語選択部が選択する最尤復号語候補を説明するための図である。 図６は、第１の実施形態に係る復号動作の一例を示すフローチャートである。 図７は、第２の実施形態に係るソート後のＬＬＲ列に対するシンドロームサイズ及びフリップ対象範囲を示す図である。

以下に添付図面を参照して、実施形態に係るメモリシステムを詳細に説明する。なお、以下の実施形態により本発明が限定されるものではない。

最尤復号法を使った軟判定復号では、メモリセルに記憶されている各ビットの（０，１）の値を“０である確率”で示したものを入力（受信語）とし、採用する復号アルゴリズムを使用して受信語から復号語の候補となる符号語のリストを生成する。なお、復号対象の符号語は、たとえば列方向の成分符号と行方向の成分符号との２次元の成分符号でユーザデータを二重に保護する積符号に代表されるような、２次元以上の成分符号でユーザデータの少なくとも一部を二重以上に保護する多次元の誤り訂正符号であってよい。その場合、説明文中の符号語は、多次元の誤り訂正符号における成分符号に相当する。このような多次元の誤り訂正符号には、上述した積符号の他に、積符号を一般化した概念であるグラフ符号（Graph Codes）や、グラフ符号を更に一般化した概念である一般化ＬＤＰＣ符号（Generalized Low-Density Parity Check Codes）などが存在する。

つづいて、受信語と復号語候補の符号語とがどの程度かけ離れているかを表すユークリッド距離といわれるメトリック（正しい符号語であることの尤もらしさを表す指標）を計算し、ユークリッド距離が最も小さい復号語候補の符号語を最尤復号語の候補（以下、最尤復号語候補という）として選択する。その後、最尤復号語候補として選択した符号語の軟判定出力値を計算して出力する。最尤復号語候補となる符号語のリストを生成する復号アルゴリズムとしては、Ｃｈａｓｅ復号、ＯＳＤ（Ordered Statistics Decoding）などが存在する。

このような最尤復号法を使った軟判定復号において最も高い訂正能力を得るには、復号語の候補となるリストに全符号語を含め、それぞれに対してユークリッド距離を計算して最尤符号語を決定する必要がある。しかしながら、全ての符号語に対してのユークリッド距離を計算するには膨大な計算量が発生するため、データ読出し時のレイテンシが非常に大きくなってしまうという課題がある。

そこで、一般的にメモリシステムに実装される軟判定復号では、「テストパタン」と呼ばれるエラービットの位置及び個数の組合せを仮定するパタンのリストを生成し、これらのテストパタンを用いつつ復号アルゴリズムに従って候補となる符号語を検出することで、ユークリッド距離の算出対象とする符号語を絞り込むことが行なわれる。

テストパタン生成方法の例としては、軟判定入力値の対数尤度比の絶対値の和の小さいものから順に候補とするテストパタンを選択する方法が存在する。また、ＯＳＤでは、Box and Match Algorithmなどの方法が存在する。しかしながら、これらの方法では、リストアップするテストパタンの数を削減するほど誤り訂正能力が低下してしまうという課題が存在する。そこで以下の実施形態では、誤り訂正能力を低下させずにレイテンシを小さくすることが可能なメモリシステムについて、例を挙げて詳細に説明する。

（第１の実施形態）
図１は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。図１に示すように、メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とを備える。メモリコントローラ１０及び不揮発性メモリ２０は、例えばそれらの組み合わせにより一つのメモリシステムを構成している。このようなメモリシステム１の例としては、ＳＤ（登録商標）カードのようなメモリカード、ＳＳＤ（Solid State Drive）等が挙げられる。

不揮発性メモリ２０は、例えばＮＡＮＤ型フラッシュメモリなどの不揮発性メモリであってよい。また、１つのメモリコントローラ１０に接続される不揮発性メモリ２０は１つに限られず、複数の不揮発性メモリ２０を接続することが可能である。

メモリコントローラ１０は、ホストバスを介して接続されたホスト３０から受信した命令に応答して、不揮発性メモリ２０にアクセスする。ホスト３０は、コンピュータの構成を備えている。コンピュータとは、例えば、パーソナルコンピュータ、サーバ装置、ポータブルな情報機器、デジタルスチルカメラ等であってよい。ホストバスの準拠する規格としては、任意の規格が採用可能である。

メモリコントローラ１０は、ＣＰＵ（Central Processing Unit）１１、ＲＡＭ（Random Access Memory）１２、バッファメモリ１４、メモリインタフェース（Ｉ／Ｆ）１５及びホストインタフェース（Ｉ／Ｆ）１７を備え、これらが内部バス１８を介して相互に接続されている。

ホストＩ／Ｆ１７は、ホスト３０から受信した命令及びデータを、それぞれＣＰＵ１１及びバッファメモリ１４に転送する。また、ホストＩ／Ｆ１７は、ＣＰＵ１１からの命令に応答して、バッファメモリ１４内のデータをホスト３０へ転送する。

ＣＰＵ１１は、メモリコントローラ１０全体の動作を制御する。例えば、ＣＰＵ１１は、ホスト３０から書込み命令を受信した際には、それに応答して、メモリＩ／Ｆ１５に対して書込み命令を発行する。読出し及び消去の際も同様に、ホスト３０からの命令に応答して、メモリＩ／Ｆ１５に対して読出し命令又は消去命令を発行する。またＣＰＵ１１は、ウエアレベリングやガベージコレクション等、不揮発性メモリ２０を管理するための様々な処理を実行する。

ＲＡＭ１２は、例えばＤＲＡＭ（Dynamic RAM）等の半導体メモリであり、ＣＰＵ１１等の作業領域として使用される。ＲＡＭ１２には、不揮発性メモリ２０を管理するためのファームウェア、及び、各種の管理テーブル等がロードされ得る。

バッファメモリ１４は、書込みデータ又は読出しデータを一時的に保持するメモリ領域として機能する。バッファメモリ１４は、ＤＲＡＭ、ＳＲＡＭ（Static RAM）等によって構成され得る。

メモリＩ／Ｆ１５は、チャネルを介して１つ以上の不揮発性メモリ２０と接続され、不揮発性メモリ２０との通信を制御する。メモリＩ／Ｆ１５は、ＣＰＵ１１から受信した命令に基づき、信号ALE、信号CLE、信号WEn、及び信号REnを不揮発性メモリ２０へ出力する。例えば書込み時には、メモリＩ／Ｆ１５は、ＣＰＵ１１が発行した書込み命令及びバッファメモリ１４内の書込みデータを入出力信号I/Oとして不揮発性メモリ２０へ転送する。また、読出し時には、メモリＩ／Ｆ１５は、ＣＰＵ１１が発行した読出し命令を入出力信号I/Oとして不揮発性メモリ２０へ転送する。そして、メモリＩ／Ｆ１５は、不揮発性メモリ２０から読み出されたデータを入出力信号I/Oとして受信し、これをバッファメモリ１４へ転送する。

ここで、信号CEnは、不揮発性メモリ２０をイネーブルにするための信号である。信号CLEは、入力信号I/Oが命令であることを不揮発性メモリ２０に通知する信号である。信号ALEは、入力信号I/Oがアドレスであることを不揮発性メモリ２０に通知する信号である。信号WEnは、入力信号I/Oを不揮発性メモリ２０に取り込ませるための信号である。信号REnは、不揮発性メモリ２０から出力信号I/Oを読み出すための信号である。レディ・ビジー信号RBnは、不揮発性メモリ２０がレディ状態（メモリコントローラ１０からの命令を受信できる状態）であるか、それともビジー状態（メモリコントローラ１０からの命令を受信できない状態）であるかを示す信号である。入出力信号I/Oは、例えば８ビットの信号である。入出力信号I/Oは、不揮発性メモリ２０とメモリコントローラ１０との間で送受信されるデータの実体であり、命令、アドレス、書込みデータ、読出しデータ等である。

図２は、図１に示すメモリＩ／Ｆ１５のより詳細な構成例を示すブロック図である。図２に示すように、メモリＩ／Ｆ１５は、不揮発性メモリ２０に書き込むデータを符号化するとともに、不揮発性メモリ２０から読み出されたデータを復号するＥＣＣ（Error Correction Code）部１００を備える。ＥＣＣ部１００は、軟判定値変換部１４０と、内部メモリ１３０と、リスト生成部１２０と、軟判定復号部１１０と、硬判定値変換部１５０とを備える。

軟判定値変換部１４０は、不揮発性メモリ２０から読み出されたデータを軟判定値（後述するＬＬＲ）に変換する。

内部メモリ１３０は、不揮発性メモリ２０から読み出された受信語、軟判定値変換部１４０により軟判定値（ＬＬＲ）に変換された符号語、この符号語に対するテストパタンを軟判定復号部１１０が復号する過程で生成された軟判定値の復号語（以下、中間復号語という）等を格納する。

軟判定復号部１１０は、内部メモリ１３０内の軟判定値の符号語又は中間復号語に対して軟判定復号（ソフトビット復号：ＳＢ復号）を実行する。

硬判定値変換部１５０は、内部メモリ１３０内に格納された軟判定値の符号語（例えば復号完了後の復号語）を（０，１）の２値で表された硬判定値の符号語に変換する。なお、硬判定値変換部１５０により硬判定値に変換された符号語は、不揮発性メモリ２０内に再度書き込まれてもよいし（例えばガベージコレクション時）、バッファメモリ１４等を介してホスト３０へ出力されてもよい。

リスト生成部１２０は、ＳＢ復号の入力となるテストパタンのリストを生成する。例えばリスト生成部１２０は、既出の復号語候補がある場合（例えば後述する最尤復号語選択部１１４において最尤復号語候補が保持されている場合）、その復号語候補のユークリッド距離を元に、当該ユークリッド距離よりも短いユークリッド距離となる可能性のあるテストパタンのリストを生成する。

また、リスト生成部１２０は、テストパタン削減部１２１を備える。このテストパタン削減部１２１は、リスト生成部１２０により生成されたリストが既に存在する場合であって、既出の復号語候補がある場合には、その復号語候補のユークリッド距離を元に、当該ユークリッド距離よりも短いユークリッド距離となる可能性のないテストパタンを上記リストから削除する。

軟判定復号部１１０は、テストパタン復号部１１１と、ユークリッド距離計算部１１３と、最尤復号語選択部１１４と、テストパタン実行判定部１１２とを備える。

テストパタン復号部１１１は、規定のアルゴリズムに従ってリスト生成部１２０から入力されたリスト内のテストパタンを順次復号する。

ユークリッド距離計算部１１３は、テストパタン復号部１１１で検出された符号語（中間復号語）と受信語とのユークリッド距離を計算する。

最尤復号語選択部１１４は、ユークリッド距離計算部１１３で新たに計算されたユークリッド距離と既出の最尤復号語候補のユークリッド距離との大きさを比較し、ユークリッド距離が小さい方の中間復号語で最尤復号語候補を更新して保持する。

テストパタン実行判定部１１２は、最尤復号語選択部１１４に保持されている最尤復号語候補のユークリッド距離に基づいて、リスト生成部１２０から入力されたリストにおけるテストパタンに対してＳＢ復号を実行するか否かを判定し、ＳＢ復号を実行すると判定したテストパタンをテストパタン復号部１１１に入力する。

このように本実施形態では、最尤復号語となり得ないテストパタンをリストに含めない機能（リスト生成部１２０及びテストパタン削減部１２１）を備えることで、復号時の計算量を削減し、レイテンシを小さくしている。また、本実施形態では、最尤復号語となり得ないテストパタンに対するＳＢ復号をスキップする機能（テストパタン実行判定部１１２）を備えることでも、復号時の計算量を削減して、レイテンシを小さくしている。

なお、ＥＣＣ部１００は、メモリＩ／Ｆ１５とは独立してメモリコントローラ１０内に設けられてもよい。その場合、例えばＣＰＵ１１は、不揮発性メモリ２０から読み出されたデータをメモリＩ／Ｆ１５を経由してＥＣＣ部１００へ入力するような制御を実行する。

つづいて、本実施形態における復号処理の流れについて、図面を用いて詳細に説明する。

復号処理では、まず、不揮発性メモリ２０からの対象データ（符号語）の読出しが実行される。不揮発性メモリ２０に対するデータの読出しでは、硬判定読出し（ハードビット（ＨＢ）リードともいう）と、軟判定読出し（ソフトビット（ＳＢ）リードともいう）とが実行される。

硬判定読出し（ハードビット（ＨＢ）リード）では、読み出したビット値が（０，１）で切り替わる読出し電圧（以下、ＨＢリードレベルという）を各メモリセルに印加することで、２値のデータである硬判定値のデータ（ハードビット（ＨＢ）データともいう）が読み出される。軟判定読出し（ソフトビット（ＳＢ）リード）では、ＨＢリードレベルから電圧値をそれぞれ±δ，±２δ，…シフトした複数のリードレベル（以下、ＳＢリードレベルという）を各メモリセルに印加することで、LOWERページ、MIDDLEページ、UPPERページ等よりなる複数ページのデータ（ソフトビット（ＳＢ）データともいう）が読み出される。

ＳＢリードにより各メモリセルから読み出されたＳＢデータは、各メモリセルの閾値電圧が想定される（０，１）の状態（閾値電圧分布）からどの程度ずれているかを示している。このＳＢデータは、各メモリセルから読み出したビット値の信頼性（値の正しさ）を表現する対数尤度比（Log Likelihood Ratio：LLR）に変換することができる。

ここで、不揮発性メモリ２０から受信語ｙが読み出されたとすると、その受信語ｙにおけるｉ番目のビットｂ_ｉのＬＬＲは、以下に式（１）で表すことができる。なお、式（１）において、Ｐ（ｂ_ｉ＝０｜ｙ）は、ｉ番目のビットｂ_ｉの値が“０”である確率を示し、Ｐ（ｂ_ｉ＝１｜ｙ）は、ｉ番目のビットｂ_ｉの値が“１”である確率を示している。

式（１）から求まるＬＬＲがプラスであれば、このＬＬＲはｉ番目のビットｂ_ｉの値が“０”であることを示唆しており、マイナスであれば、ｉ番目のビットｂ_ｉの値が“１”であることを示唆している。また、ＬＬＲの絶対値は、式（１）から求まるＬＬＲの正負によって示唆される値の信頼度を示しており、絶対値が大きいほど信頼度が高く、小さいほど信頼度が低い。

軟判定値変換部１４０は、各メモリセルから読み出された複数ページのＳＢデータをＬＬＲに変換し、内部メモリ１３０に格納する。図３の上段に、不揮発性メモリ２０から読み出したＳＢデータの受信語を変換することで生成されたＬＬＲ列の一例を示す。理論的には、ＬＬＲは実数で表されるものであるが、本説明では、図３に示すように、ＬＬＲが整数に丸め込まれて、離散化された値を持つものとする。したがって、内部メモリ１３０内の符号語は、離散化された値を持つＬＬＲで表現された符号語となる。

リスト生成部１２０は、図３に示すように、ＳＢ復号対象の符号語の各ビットを軟判定入力値（ＬＬＲ）の絶対値の小さい順にソートする（Ｓ１１）。その際、リスト生成部１２０は、ＳＢ復号対象の符号語における全ビットをソートしてもよいし、符号語の一部のビット（例えばＬＬＲの絶対値の小さいものから順に所定数のビット）をソートしてもよい。

また、リスト生成部１２０は、テストパタン復号部１１１がＣｈａｓｅ復号アルゴリズムに従って復号を実行するように設計されていた場合には、Ｃｈａｓｅ復号用のテストパタンのリストを生成し、ＯＳＤアルゴリズムに従って復号を実行するように設計されていた場合には、ＯＳＤ用のテストパタンのリストを生成する。本実施形態では、Ｃｈａｓｅ復号アルゴリズムが採用されている場合を例に挙げ、ＯＳＤアルゴリズムを採用した場合については、後述する第２の実施形態において説明する。

Ｃｈａｓｅ復号用テストパタンのリストを生成する場合、リスト生成部１２０は、フリップ数を１としたテストパタンのリスト、フリップ数を２としたテストパタンのリスト、フリップ数を３としたテストパタンのリスト、…、フリップ数をｆ（ｆは１以上の整数）としたテストパタンのリストを順次生成する。

生成されるリストの大きさ（テストパタンの数）は、フリップするビットの数（以下、フリップ数という）の最大値から定められてもよいし、予めテストパタンの数の上限値として定められてもよい。ただし、リストの大きさ（テストパタンの数）は、許容されるレイテンシを満足し得る程度の大きさに設定される（ＬＲＢ：LeastReliableBasis）。

また、フリップ対象とするビットの範囲（フリップ対象範囲）Ｆは、図４に示すように、例えばソート後のＬＬＲ列に対し、ＬＬＲの絶対値の小さいものから順に所定の個数（以下、閾値数という）（ｎ）までの範囲となるように制限されてもよい。なお、図４では、閾値数（ｎ）を４とした場合が示されている。

以上のような方法において、フリップ数の最大値をｋとし、閾値数（ｎ）を４とした場合、生成されるリストの大きさは、フリップ数を１としたテストパタンの組合せ数ｎＣ１と、フリップ数を２としたテストパタンの組合せ数ｎＣ２と、フリップ数を３としたテストパタンの組合せ数ｎＣ３と、…、フリップ数をｋとしたテストパタンの組合せ数ｎＣｋとの合計値（ｎＣ１＋ｎＣ２＋ｎＣ３＋…＋ｎＣｋ）となる。

なお、リスト内におけるテストパタンの優先順位は、例えばＬＬＲの絶対値の小さいビットをフリップするテストパタンほど高い優先度となるような優先順位であってよい。言い換えれば、テストパタン復号部１１１における復号順序は、例えばＬＬＲの絶対値の小さいビットをフリップするテストパタンほど高い優先度となるような優先順位であってよい。

また、本実施形態では、後述するように、Ｃｈａｓｅ復号アルゴリズムを使って訂正可能数ｔの符号語に対してフリップ数ｆのテストパタンを生成する際、既に１つの候補となる復号語が見つかっており（言い換えれば、既に最尤復号語候補が最尤復号語選択部１１４に保持されており）、且つ、そのユークリッド距離が（ｆ＋ｔ）ａ＋ｔ＋１（なお、ａは任意の自然数）より大きい場合には、リスト生成時のフリップ対象とするビットの条件に、ＬＬＲの絶対値がａ以下のものという条件を追加する。このような条件を追加することで、フリップ対象範囲Ｆ（図４参照）内のビットからさらにフリップ対象とするビットが絞り込まれ、それにより、フリップするビットの組合せ数が減少し、生成されるテストパタンの数が減少する。その結果、復号時の計算量が削減し、レイテンシを小さくすることが可能となる。

軟判定復号部１１０は、入力された軟判定入力値（ＬＬＲ）を用いてＳＢ復号を実行する。Ｃｈａｓｅ復号アルゴリズムが採用されている本実施形態では、軟判定復号部１１０は、フリップ数を０とした復号（復号実行回数が１回）、フリップ数を１とした復号、フリップ数を２とした復号、フリップ数を３とした復号、…、フリップ数をｋとした復号を順次実行する。

ユークリッド距離計算部１１３は、テストパタン復号部１１１で検出された符号語（中間復号語）と受信語とのユークリッド距離を計算する。このユークリッド距離は、例えばエラービットに対応する軟判定入力値（ＬＬＲ）の絶対値の総和であってよい。

例えば図５に示すように、テストパタン復号部１１１が中間復号語＃１の１番目のビットと３番目のビットがエラービットであると検出した場合、ユークリッド距離計算部１１３は、中間復号語＃１のユークリッド距離を１番目のビットのＬＬＲの絶対値‘１’と、３番目のビットのＬＬＲの絶対値‘５’との総和である‘６’を、中間復号語＃１のユークリッド距離として算出する。また、中間復号語＃２についても同様に、ユークリッド距離計算部１１３は、テストパタン復号部１１１がエラービットとして検出した１番目と９番目とのビットのＬＬＲの絶対値の総和をユークリッド距離（‘４’）として算出する。同様に、中間復号語＃３についても、ユークリッド距離計算部１１３は、テストパタン復号部１１１がエラービットとして検出した１番目と５番目と７番目と９番目とのビットのＬＬＲの絶対値の総和をユークリッド距離（‘６’）として算出する。

最尤復号語選択部１１４は、最初に検出された中間復号語とユークリッド距離とを最尤復号語候補として保存する。また、最尤復号語選択部１１４は、２つ目以降に見つかった中間復号語については、その中間復号語のユークリッド距離を計算し、計算されたユークリッド距離と保存されている最尤復号語候補のユークリッド距離とを比較し、ユークリッド距離が小さい方の復号語を最尤復号語候補として保存し直す。したがって、新たに検出された中間復号語のユークリッド距離の方が小さければ、新たに検出された中間復号語で保存されている最尤復号語候補が更新される。

つづいて、Ｃｈａｓｅ復号アルゴリズムを使ったＳＢ復号の流れについて、具体例を挙げて説明する。

Ｃｈａｓｅ復号アルゴリズムにおいて、訂正可能数ｔを１とし、フリップ数が１のテストパタンを用いて復号した場合、得られるエラー数はフリップ数１に訂正可能数ｔ＝１を加えた合計２ビットとなる。このとき、得られるユークリッド距離が検出されたエラービットのＬＬＲの絶対値の総和であることから、得られるユークリッド距離とエラービットのＬＬＲの絶対値との組み合わせは、以下の表１のように列挙することができる。

表１から分かるように、訂正可能数ｔを１、フリップ数を１とした場合に、ユークリッド距離が３以下の最尤復号語候補を得るには、フリップ対象の１ビットはＬＬＲの絶対値が１であるビットに限定される。また、ユークリッド距離が５以下の最尤復号語候補を得るには、フリップ対象の１ビットはＬＬＲの絶対値が１又は２であるビットに限定される。これを一般化すると、ユークリッド距離が２ａ＋１以下（ａは０以上の整数）の最尤復号語候補を得るには、フリップ対象の１ビットはＬＬＲの絶対値がａ以下のビットに限定されることが得られる。

また、訂正可能数ｔを１とし、フリップ数を２とした場合には、Ｃｈａｓｅ復号の結果として得られるエラービットの数は３ビットとなる。したがって、得られるユークリッド距離とエラービットのＬＬＲの絶対値との組み合わせは、以下の表２のように列挙することができる。

表２から分かるように、ユークリッド距離が３ａ＋１以下の最尤復号語候補を得るには、フリップ対象とする２ビットは、それぞれＬＬＲの絶対値がａ以下のビットに限定される。

以上のことから、訂正可能数ｔを１とした符号において、フリップ数ｆでユークリッド距離が（ｆ＋１）ａ＋１以下の最尤復号語候補を検出するためには、フリップ対象のｆビットそれぞれを、ＬＬＲの絶対値がａ以下のビットに限定すればよいことが分かる。

次に、訂正可能数ｔを２とした場合について説明する。訂正可能数ｔを２とし、フリップ数を１とした場合には、Ｃｈａｓｅ復号の結果として得られるエラービットの数は３ビットとなる。したがって、得られるユークリッド距離とエラービットのＬＬＲの絶対値との組み合わせは、以下の表３のように列挙することができる。

表３から分かるように、訂正可能数ｔを２とした符号において、フリップ数ｆでユークリッド距離が３ａ＋２以下の最尤復号語候補を検出するためには、フリップ対象のｆビットそれぞれを、ＬＬＲの絶対値がａ以下のビットに限定すればよいことが分かる。

また、訂正可能数ｔを２とし、フリップ数を２とした場合には、検出されるエラービットの数が４ビットとなるため、得られるユークリッド距離とエラービットのＬＬＲの絶対値との組み合わせは、以下の表４のように列挙することができる。

表４から分かるように、訂正可能数ｔを２とし、フリップ数を２とした場合において、ユークリッド距離が４ａ＋２以下の最尤復号語候補を検出するためには、フリップ対象の２ビットそれぞれを、ＬＬＲの絶対値がａ以下のビットに限定すればよい。

以上のように、Ｃｈａｓｅ復号アルゴリズムを使って訂正可能数ｔの符号語をフリップ数ｆのビットフリップしたテストパタンを用いて復号する場合において、ユークリッド距離が（ｆ＋ｔ）ａ＋ｔ以下となる最尤復号語候補を検出するためには、フリップ対象のｆビットそれぞれを、ＬＬＲの絶対値がａ以下のビットに限定すればよいことが分かる。

たとえば訂正可能数が２の符号語に関し、フリップ数０で１つの最尤復号語候補が検出され、そのユークリッド距離が９であった場合、最尤復号語候補を更新するためには、新たに検出された中間復号語のユークリッド距離は８以下である必要がある。そこで、リスト生成部１２０は、フリップ数を１としたテストパタンのリストを生成する際に、フリップ対象のビットをＬＬＲの絶対値が１又は２のビットに制限する。または、既にフリップ数を１としたテストパタンのリストが生成されている場合には、リスト生成部１２０内のテストパタン削減部１２１が、フリップ対象のビットをＬＬＲの絶対値が１又は２のビットでないテストパタンをリストから削除する。これにより、最尤復号語となり得ないテストパタンをリストから除外することが可能となるため、復号時の計算量が削減されて、レイテンシが小さくなるという効果が得られる。

また、フリップ数を１としたテストパタンのリストを用いてＣｈａｓｅ復号を実行した結果又は実行中にユークリッド距離が例えば６の最尤復号語候補が検出された場合、リストの残りのテストパタンのうちＬＬＲの絶対値が２のビットがフリップされたテストパタンを用いてＣｈａｓｅ復号を実行したとしても、最尤復号語選択部１１４に保持された最尤復号語候補が更新されることはない。そこで、このような場合には、軟判定復号部１１０内のテストパタン実行判定部１１２は、ＬＬＲの絶対値が２のビットがフリップされたテストパタンに対し、テストパタン復号部１１１がＣｈａｓｅ復号が実行を実行しないように制限する。例えばテストパタン実行判定部１１２は、ＬＬＲの絶対値が２のビットがフリップされたテストパタンのテストパタン復号部１１１への入力をスキップする。これにより、最尤復号語となり得ないテストパタンに対するＳＢ復号がスキップされるため、復号時の計算量が削減されて、レイテンシを小さくなるという効果が得られる。

次に、本実施形態に係る復号動作について、図面を参照して詳細に説明する。図６は、本実施形態に係る復号動作の一例を示すフローチャートである。図６に示すように、本実施形態では、まず、リスト生成部１２０がフリップ数をｆとしたテストパタン（以下、ｆビットフリップのテストパタンという）のリストを生成する（ステップＳ１０１）。なお、ｆの初期値は１であるとする。また、既にｆビットフリップのテストパタンのリストが存在する場合には、ステップＳ１０１がスキップされてもよい。

次に、リスト生成部１２０のテストパタン削減部１２１が、リストアップされたｆビットフリップのテストパタンのうち、最尤復号語候補となる可能性のないテストパタンを削除することで、復号対象のテストパタンを絞り込む（ステップＳ１０２）。具体的には、テストパタン削減部１２１は、まず、リストアップされたテストパタンそれぞれについて、エラービットと仮定されているビットのＬＬＲの総和からユークリッド距離を算出する。つづいて、テストパタン削減部１２１は、最尤復号語選択部１１４に格納されている最尤復号語候補のユークリッド距離を取得する。その後、テストパタン削減部１２１は、リストアップされたテストパタンのうち、ユークリッド距離が最尤復号語候補のユークリッド距離以上のものをリストから削除する。これにより、復号対象とするテストパタンが絞り込まれるため、復号時の計算量が削減されて、レイテンシを小さくすることができる。なお、ステップＳ１０１においてリスト生成部１２０が最尤復号語候補となる可能性のないテストパタンを生成しないように動作する場合には、ステップＳ１０２を省略することも可能である。また、絞り込み後のリストは、軟判定復号部１１０のテストパタン実行判定部１１２に入力される。

次に、テストパタン実行判定部１１２が、入力されたリストの中から未選択のテストパタンを１つ選択する（ステップＳ１０３）。なお、選択時の優先順位としては、上述したように、例えばＬＬＲの絶対値の小さいビットをフリップするテストパタンほど高い優先度となるような優先順位であってよい。このような選択順序とすることで、エラーベクタが検出される可能性の高いテストパタンに対する復号を優先的に実行することが可能になるとともに、復号処理の流れにおける比較的早期に、最尤復号語選択部１１４に格納される最尤復号語候補のユークリッド距離を短くすることが可能となる。その結果、リスト生成部１２０がリストに含めないこととするテストパタンの数、テストパタン削減部１２１がリストから削除するテストパタンの数、及び、テストパタン実行判定部１１２がスキップ対象とするテストパタンの数が増加するため、復号時の計算量がより削減されて、レイテンシをより小さくすることが可能となる。

次に、テストパタン実行判定部１１２は、選択したテストパタンを用いたＳＢ復号を実行するか否かを判定する（ステップＳ１０４）。具体的には、テストパタン実行判定部１１２は、選択したテストパタンのユークリッド距離を特定する。このユークリッド距離は、リスト生成部１２０からリストとともに入力されてもよいし、テストパタン実行判定部１１２が選択したテストパタンにおいてエラービットと仮定されているビットのＬＬＲの総和から算出してもよい。つづいて、テストパタン実行判定部１１２は、最尤復号語選択部１１４に格納されている最尤復号語候補のユークリッド距離を取得する。その後、テストパタン実行判定部１１２は、選択したテストパタンのユークリッド距離が最尤復号語候補のユークリッド距離未満であれば、当該テストパタンに対するＳＢ復号を実行すると判定し（ステップＳ１０４のＹＥＳ）、ステップＳ１０５へ進む。一方、選択したテストパタンのユークリッド距離が最尤復号語候補のユークリッド距離以上であれば、テストパタン実行判定部１１２は、当該テストパタンに対するＳＢ復号を実行しないと判定し（ステップＳ１０４のＮＯ）、ステップＳ１１２へ進む。これにより、最尤復号語候補が検出され得ないテストパタンに対するＳＢ復号がスキップされるため、復号時の計算量が削減されて、レイテンシを小さくすることができる。

ステップＳ１０５では、テストパタン実行判定部１１２からテストパタン復号部１１１にＳＢ復号を実行すると判定されたテストパタンが入力され、テストパタン復号部１１１が入力されたテストパタンを用いたＳＢ復号を実行する。つづいて、テストパタン復号部１１１は、エラーベクタが検出されたか否かを判定する（ステップＳ１０６）。エラーベクタが検出されなかった場合（ステップＳ１０６のＮＯ）、ステップＳ１１０へ進む。一方、エラーベクタが検出された場合（ステップＳ１０６のＹＥＳ）、ユークリッド距離計算部１１３が、テストパタンによりフリップされたビットのＬＬＲと、検出されたエラーベクタが示すエラービットのＬＬＲとからユークリッド距離を計算する（ステップＳ１０７）。つづいて、最尤復号語選択部１１４が、ユークリッド距離計算部１１３により新たに計算されたユークリッド距離と、保存している最尤復号語候補のユークリッド距離とを比較し（ステップＳ１０８）、新たに計算されたユークリッド距離が最尤復号語候補のユークリッド距離未満であれば（ステップＳ１０８のＹＥＳ）、保存している最尤復号語候補及びそのユークリッド距離を、テストパタン復号部１１１によるＳＢ復号により新たに検出された中間復号語及びその中間復号語についてユークリッド距離計算部１１３が新たに計算したユークリッド距離で更新し（ステップＳ１０９）、ステップＳ１１０へ進む。一方、新たに計算されたユークリッド距離の方が最尤復号語候補のユークリッド距離以上である場合（ステップＳ１０８のＮＯ）、最尤復号語選択部１１４が保持する最尤復号語候補及びそのユークリッド距離を更新せずに、ステップＳ１１０へ進む。

ステップＳ１１０では、ステップＳ１０２による絞り込み後のリストにおけるテストパタンの全てに対してＳＢ復号が完了したか否かが判定される。未だＳＢ復号が実行されていないテストパタンが存在する場合（ステップＳ１１０のＮＯ）は、ステップＳ１０３へリターンし、新たに選択されたテストパタンに対して以降の動作が実行される。一方、リストにある全てのテストパタンに対してＳＢ復号が完了している場合（ステップＳ１１０のＹＥＳ）、フリップ数ｆを１インクリメント（ステップＳ１１１）した後、ステップＳ１１２へ進む。

ステップＳ１１２では、フリップ数ｆがフリップ数の最大値ｋよりも大きいか否か、すなわち、フリップ数の最大値ｋまでの全てのテストパタンについての処理が完了したか否かが判定される。フリップ数ｆが最大値ｋ以下である場合（ステップＳ１１２のＮＯ）、ステップＳ１０１へリターンして、新たなフリップ数ｆについてｆビットフリップのテストパタンのリストが生成された後、以降の動作が実行される。一方、フリップ数ｆが最大値ｋより大きい場合（ステップＳ１１２のＹＥＳ）、本動作が終了される。

以上のように、本実施形態によれば、既出の最尤復号語候補よりもユークリッド距離が小さくなる可能性がないテストパタンをリストから排除して復号対象に含めないことで、最尤復号法での計算量を削減してレイテンシを小さくすることが可能となる。また、復号の途中で新たな最尤復号語候補が検出された場合には、この新たな最尤復号語候補よりもユークリッド距離が小さくなる可能性がないテストパタンに対するＳＢ復号をスキップすることで、最尤復号法での計算量を削減してレイテンシを小さくすることが可能となる。

（第２の実施形態）
上述した第１の実施形態では、Ｃｈａｓｅ復号アルゴリズムが採用されている場合を例に挙げた。これに対し、第２の実施形態では、ＯＳＤアルゴリズムが採用された場合について、例を挙げて詳細に説明する。

本実施形態において、メモリＩ／Ｆを含むメモリシステムの概略構成は、上述した第１の実施形態に係るメモリシステム１（図１及び図２参照）と同様であってよいため、ここでは詳細な説明を省略する。また、復号動作についても同様に、上述した第１の実施形態において図６等を用いて説明した概略動作例と同様であってよいため、ここでは詳細な説明を省略する。

つづいて、ＯＳＤアルゴリズムを使ったＳＢ復号の流れについて、具体例を挙げて説明する。本説明では、保護対象の情報語が訂正可能数がｔの符号語で保護されているものとする。また、入力された符号語に対して、ＯＳＤ復号の前に実行された限界距離復号の結果、ユークリッド距離がｂの中間復号語が最尤復号語候補として検出されているものとする。この場合、ＯＳＤ復号の結果として得られるエラーベクタには、少なくとも（ｔ＋１）個のエラービットが含まれることになる。

ＯＳＤ用テストパタンを生成する場合においては、符号語に対してフリップ対象とするビットの範囲（フリップ対象範囲）Ｆを設定する場合、リスト生成部１２０は、図７に示すように、例えば図３を用いて説明したソート（Ｓ１１）後のＬＬＲ列に対し、ＬＬＲの絶対値の小さいものから順に、シンドロームサイズ（パリティサイズ）ｐに所定の閾値数（ｎ）を加えた数（ｐ＋ｎ）をエラーが存在する可能性のある範囲（以下、エラー仮定範囲という）とし、所定の閾値数（ｎ）に相当する範囲をフリップ対象範囲Ｆに設定する。その際、閾値数（ｎ）は、フリップ数ごとに異なる値としてもよい。なお、図７では、シンドロームサイズを４とし、閾値数（ｎ）を４とした場合が示されている。

ＯＳＤアルゴリズムにおけるフェーズ（以下、ＯＳＤフェーズという）０では、軟判定復号部１１０は、ソートされたビットのうち、ＬＬＲの絶対値の最も小さいものから順にシンドロームサイズ分のビットを使用してＯＳＤフェーズ０の復号を実行する。ただし、ＬＬＲの絶対値の最も小さいビットから数えて（ｔ＋１）番目のビットのＬＬＲが最尤復号語候補のユークリッド距離ｂ以上である場合、ＯＳＤフェーズ０の復号を実行したとしても最尤復号語選択部１１４内の最尤復号語候補が更新されることはない。そのため、この場合には、リスト生成部１２０はリストを生成せずに、「パタン無し」であることを軟判定復号部１１０に通知する。この場合、ＥＣＣ部１００は、以降のＯＳＤを実行せず、既に得られている最尤復号語候補を最終的な復号語である軟判定出力値として出力する。

ＯＳＤフェーズ０以降、ＯＳＤフェーズ１からＯＳＤフェーズｋ（ｋはフリップ数の最大値に相当）までが順次実行される。具体的には、ＯＳＤフェーズｊ（ｊは１以上ｋ以下）では、リスト生成部１２０が、ソートされたビットのうちＯＳＤフェーズ０で使用したシンドロームサイズｐのビットを除いたフリップ対象範囲Ｆ内のビットをｊ個フリップするテストパタンのリストを生成し、軟判定復号部１１０が生成されたテストパタンのリストに従いＯＳＤフェーズｊの復号を実行する。

その際、ＯＳＤフェーズ（ｊ−１）（ｊは１以上ｋ以下）までの過程でユークリッド距離がｃの符号語が検出されている場合、ＯＳＤフェーズｊ以降では、エラーと仮定するｊ個のビットのＬＬＲの絶対値の和がｃより大きくなるテストパタンを復号したとしても、当該復号により検出された中間復号語が最尤復号語候補となることはない。そこで、このような場合、ＯＳＤフェーズｊ以降では、リスト生成部１２０は、フリップ対象としたｊ個のビットのＬＬＲの絶対値の和がｃより大きくなるテストパタンを含まないリストを生成する。若しくは、既にリストが存在する場合には、テストパタン削減部１２１がリストから該当のテストパタンを削除するか、テストパタン実行判定部１１２が当該テストパタンをテストパタン復号部１１１による復号対象から除外する。

さらに、１＜ｊ＜ｔ（ｔは符号語の訂正可能数）の場合、ＬＲＢに基づいて（ｔ＋１−ｊ）個のＬＬＲの絶対値の和をｍとおくとき、エラーと仮定するｊ個のビットのＬＬＲの和がｃ−ｍより大きくなるテストパタンを復号したとしても、当該復号により検出された中間復号語が最尤復号語候補となることはない。そこで、このような場合、ＯＳＤフェーズｊ以降では、リスト生成部１２０は、フリップ対象とするｊ個のビットのＬＬＲの絶対値の和がｃ−ｍ以上となるテストパタンを含まないリストを生成する。若しくは、既にリストが存在する場合には、テストパタン削減部１２１がリストから該当のテストパタンを削除するか、テストパタン実行判定部１１２が当該テストパタンをテストパタン復号部１１１による復号対象から除外する。

以上のような構成及び動作とすることで、本実施形態によれば、ＯＳＤアルゴリズムを採用した場合も、第１の実施形態と同様に、既出の最尤復号語候補よりもユークリッド距離が小さくなる可能性がないテストパタンをリストから排除して復号対象に含めないことで、最尤復号法での計算量を削減してレイテンシを小さくすることが可能となる。また、復号の途中で新たな最尤復号語候補が検出された場合には、この新たな最尤復号語候補よりもユークリッド距離が小さくなる可能性がないテストパタンに対するＳＢ復号をスキップすることで、最尤復号法での計算量を削減してレイテンシを小さくすることが可能となる。

その他の構成、動作及び効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１…メモリシステム、１０…メモリコントローラ、１１…ＣＰＵ、１２…ＲＡＭ、１４…バッファメモリ、１５…メモリＩ／Ｆ、１７…ホストＩ／Ｆ、１８…内部バス、２０…不揮発性メモリ、３０…ホスト、１００…ＥＣＣ部、１１０…軟判定復号部、１１１…テストパタン復号部、１１２…テストパタン実行判定部、１１３…ユークリッド距離計算部、１１４…最尤復号語選択部、１２０…リスト生成部、１２１…テストパタン削減部、１３０…内部メモリ、１４０…軟判定値変換部、１５０…硬判定値変換部。

Claims (17)

1. 不揮発性メモリと、
   前記不揮発性メモリから読み出された受信語を軟判定値の符号語に変換する軟判定値変換部と、
   前記軟判定値の符号語に対する複数のテストパタンのリストを生成するリスト生成部と、
   前記リストに含まれるテストパタンから中間復号語を検出するテストパタン復号部と、
   前記テストパタン復号部で検出された中間復号語と前記受信語とのユークリッド距離を計算するユークリッド距離計算部と、
   最尤復号語候補を保持する最尤復号語選択部と、
   を備え、
   前記最尤復号語選択部は、前記テストパタン復号部で検出された中間復号語である第１の中間復号語のユークリッド距離が、前記保持している最尤復号語候補のユークリッド距離よりも短い場合、前記第１の中間復号語で前記保持している最尤復号語候補を更新し、最終的に保持している前記最尤復号語候補を軟判定出力値として出力し、
   前記テストパタン復号部は、中間復号語のユークリッド距離が前記最尤復号語選択部に保持されている前記最尤復号語候補の前記ユークリッド距離よりも短くなる可能性のないテストパタンに対する復号を実行しない
   メモリシステム。
2. 前記リスト生成部は、前記テストパタンそれぞれがフリップ対象とするビットの軟判定値の絶対値に基づいて、前記テストパタン復号部で検出される符号語のユークリッド距離が前記最尤復号語選択部に保持されている前記最尤復号語候補の前記ユークリッド距離よりも短くなる可能性のない前記テストパタンを含めずに前記リストを生成する請求項１に記載のメモリシステム。
3. 前記テストパタンそれぞれがフリップ対象とするビットの軟判定値の絶対値に基づいて、前記テストパタン復号部で検出される符号語のユークリッド距離が前記最尤復号語選択部に保持されている前記最尤復号語候補の前記ユークリッド距離よりも短くなる可能性のないテストパタンを前記リストから削除するテストパタン削減部をさらに備える請求項１に記載のメモリシステム。
4. 前記テストパタンそれぞれがフリップ対象とするビットの軟判定値の絶対値に基づいて、前記リスト生成部が生成した前記リストに含まれる前記テストパタンのうち、前記テストパタン復号部で検出される符号語のユークリッド距離が前記最尤復号語選択部に保持されている前記最尤復号語候補の前記ユークリッド距離よりも短くなる可能性のないテストパタンに対する前記テストパタン復号部による復号をスキップするテストパタン実行判定部をさらに備える請求項１に記載のメモリシステム。
5. 前記リスト生成部は、フリップするビットの数ごとに異なるテストパタンのリストを生成し、
   前記テストパタン復号部は、前記フリップするビットの数を０とした場合を含む前記フリップするビットの数の小さいリストに含まれるテストパタンから順に復号を実行する
   請求項２に記載のメモリシステム。
6. 前記テストパタン復号部は、前記リストに含まれる前記テストパタンのうち、信頼度の低いビットをフリップ対象とするテストパタンを優先的に復号する請求項１に記載のメモリシステム。
7. 前記ユークリッド距離計算部は、前記リスト生成部でフリップされたビットと前記テストパタン復号部で検出される１つ以上のエラービットに対応する１つ以上の軟判定値の絶対値の総和を前記ユークリッド距離として算出する請求項１に記載のメモリシステム。
8. 前記所定のアルゴリズムは、Ｃｈａｓｅ復号アルゴリズムであり、
   前記リスト生成部は、前記符号語の訂正可能数をｔとし、フリップするビットの数をｆとし、ａを任意の自然数とした場合であって、前記最尤復号語選択部が（ｆ＋ｔ）ａ＋ｔ＋１のユークリッド距離の最尤復号語候補を保持している場合、フリップ対象とするビットの軟判定値の絶対値が前記ａ以下であるテストパタンが含まれない前記リストを生成する
   請求項２に記載のメモリシステム。
9. 前記所定のアルゴリズムは、Ｃｈａｓｅ復号アルゴリズムであり、
   前記テストパタン削減部は、前記符号語の訂正可能数をｔとし、フリップするビットの数をｆとし、ａを任意の自然数とした場合であって、前記最尤復号語選択部が（ｆ＋ｔ）ａ＋ｔ＋１のユークリッド距離の最尤復号語候補を保持している場合、フリップ対象とするビットの軟判定値の絶対値が前記ａ以下であるテストパタンを前記リストから削除する
   請求項３に記載のメモリシステム。
10. 前記所定のアルゴリズムは、Ｃｈａｓｅ復号アルゴリズムであり、
    前記テストパタン実行判定部は、前記符号語の訂正可能数をｔとし、フリップするビットの数をｆとし、ａを任意の自然数とした場合であって、前記最尤復号語選択部が（ｆ＋ｔ）ａ＋ｔ＋１のユークリッド距離の最尤復号語候補を保持している場合、フリップ対象とするビットの軟判定値の絶対値が前記ａ以下であるテストパタンに対する前記テストパタン復号部による復号をスキップする
    請求項４に記載のメモリシステム。
11. 前記所定のアルゴリズムは、ＯＳＤ（Ordered Statistics Decoding）アルゴリズムであり、
    前記リスト生成部は、前記最尤復号語選択部に前記ユークリッド距離がｃの前記最尤復号語候補が保持されている場合、フリップ対象とするビットの軟判定値の絶対値の和が前記ｃより大きいテストパタンが含まれない前記リストを生成する
    請求項２に記載のメモリシステム。
12. 前記所定のアルゴリズムは、ＯＳＤアルゴリズムであり、
    前記テストパタン削減部は、前記最尤復号語選択部に前記ユークリッド距離がｃの前記最尤復号語候補が保持されている場合、フリップ対象とするビットの軟判定値の絶対値の和が前記ｃより大きいテストパタンを前記リストから削除する
    請求項３に記載のメモリシステム。
13. 前記所定のアルゴリズムは、ＯＳＤアルゴリズムであり、
    前記テストパタン実行判定部は、前記最尤復号語選択部に前記ユークリッド距離がｃの前記最尤復号語候補が保持されている場合、フリップ対象とするビットの軟判定値の絶対値の和が前記ｃより大きいテストパタンに対する前記テストパタン復号部による復号をスキップする
    請求項４に記載のメモリシステム。
14. 前記所定のアルゴリズムは、ＯＳＤアルゴリズムであり、
    前記リスト生成部は、前記最尤復号語選択部に前記ユークリッド距離がｃの前記最尤復号語候補が保持されている場合であって、前記符号語の訂正可能数をｔとし、フリップするビットの数をｊとし、前記符号語において前記軟判定値の絶対値の最も小さいビットから順に（ｔ＋１−ｊ）個のビットの軟判定値の絶対値の和をｍとした場合、フリップ対象とするビットの軟判定値の絶対値の和が前記ｃ−ｍより大きいテストパタンが含まれない前記リストを生成する
    請求項２に記載のメモリシステム。
15. 前記所定のアルゴリズムは、ＯＳＤアルゴリズムであり、
    前記テストパタン削減部は、前記最尤復号語選択部に前記ユークリッド距離がｃの前記最尤復号語候補が保持されている場合であって、前記符号語の訂正可能数をｔとし、フリップするビットの数をｊとし、前記符号語において前記軟判定値の絶対値の最も小さいビットから順に（ｔ＋１−ｊ）個のビットの軟判定値の絶対値の和をｍとした場合、フリップ対象とするビットの軟判定値の絶対値の和が前記ｃ−ｍより大きいテストパタンを前記リストから削除する
    請求項３に記載のメモリシステム。
16. 前記所定のアルゴリズムは、ＯＳＤアルゴリズムであり、
    前記テストパタン実行判定部は、前記最尤復号語選択部に前記ユークリッド距離がｃの前記最尤復号語候補が保持されている場合であって、前記符号語の訂正可能数をｔとし、フリップするビットの数をｊとし、前記符号語において前記軟判定値の絶対値の最も小さいビットから順に（ｔ＋１−ｊ）個のビットの軟判定値の絶対値の和をｍとした場合、フリップ対象とするビットの軟判定値の絶対値の和が前記ｃ−ｍより大きいテストパタンに対する前記テストパタン復号部による復号をスキップする
    請求項４に記載のメモリシステム。
17. 前記最尤復号語選択部から出力された前記軟判定出力値を硬判定値の符号語に変換する硬判定値変換部をさらに備える請求項１に記載のメモリシステム。

Images