(57)【要約】【課題】硬判定読出し時に高い訂正能力を持つ復号を行う。【解決手段】実施形態によれば、メモリシステムは、連接符号を記録する不揮発性メモリと、前記不揮発性メモリから読み出された前記連接符号の受信語を復号し、当該復号により得られた復号語を出力する復号器と、を備え、前記復号器は、前記読み出された連接符号のうち外符号の符号語制約が課せられているビット系列である外符号部に対して限界距離復号を実行し、当該限界距離復号により得られた第１復号結果を出力する第１外符号復号器と、前記第１外符号復号器から出力された前記第１復号結果のビット系列に対して内符号の規則に基づきエラービットの推定を実行し、当該推定により得られた前記エラービットの集合を出力する内符号エラービット推定部と、前記第１外符号復号器から出力された前記第１復号結果に対し、前記内符号エラービット推定部から出力された前記エラービットの集合を用いた復号を実行する第２外符号復号器とを備える。【選択図】図４
2019057752.tif 000002
【特許請求の範囲】
【請求項１】
連接符号を記録する不揮発性メモリと、
前記不揮発性メモリから読み出された前記連接符号の受信語を復号し、当該復号により得られた復号語を出力する復号器と、
を備え、
前記復号器は、
前記読み出された連接符号のうち外符号の符号語制約が課せられているビット系列である外符号部に対して限界距離復号を実行し、当該限界距離復号により得られた第１復号結果を出力する第１外符号復号器と、
前記第１外符号復号器から出力された前記第１復号結果のビット系列に対して内符号の規則に基づきエラービットの推定を実行し、当該推定により得られた前記エラービットの集合を出力する内符号エラービット推定部と、
前記第１外符号復号器から出力された前記第１復号結果に対し、前記内符号エラービット推定部から出力された前記エラービットの集合を用いた復号を実行する第２外符号復号器と、
を備えるメモリシステム。
【請求項２】
前記連接符号は、代数的符号を外符号とし、疎グラフに基づく符号を内符号とする請求項１に記載のメモリシステム。
【請求項３】
前記第２外符号復号器から出力された第２復号結果に対して前記内符号の規則に基づき復号を実行する内符号復号器をさらに備える請求項１に記載のメモリシステム。
【請求項４】
前記内符号復号器から出力された第３復号結果における前記外符号部及び前記内符号の符号語制約が課せられているビット系列である内符号部それぞれのパリティ検査を実行する第１パリティ検査部をさらに備えるメモリシステム。
【請求項５】
前記内符号エラービット推定部は、
前記受信語又は前記受信語に対して前記第１外符号復号器が実行した前記限界距離復号により得られた前記第１復号結果の前記ビット系列を入力として受け付けるデータ入力部と、
前記推定されたエラービットそれぞれについてエラーである可能性の度合いを示すエラー度を計算し、計算された前記エラー度の系列を記録する第１エラー度計算部と、
前記データ入力部が受け付けた前記第１復号結果の前記ビット系列から前記内符号の規則を用いて前記エラービットを推定し、前記推定されたエラービットのビット系列を保持するエラービット推定部と、
を備える請求項１に記載のメモリシステム。
【請求項６】
前記内符号エラービット推定部は、
前記データ入力部が受け付けた前記第１復号結果の前記ビット系列に対して前記内符号のパリティ検査を行う１又は複数の第２パリティ検査部と、
前記第２パリティ検査部による各パリティ検査の結果として得られる１又は複数のシンドローム値を保存するシンドロームレジスタと、
前記第１復号結果の前記ビット系列における各ビットについて前記シンドロームレジスタに保存されたシンドローム値の和を計算するシンドロームカウンタと、
をさらに備え、
前記エラービット推定部は、前記シンドロームカウンタによって計算された前記シンドローム値の和が所定の閾値を超えたビットを基前記エラービットであると推定し、
前記第１エラー度計算部は、前記推定されたエラービットそれぞれに対し、当該エラービットが関わる前記パリティ検査により得られた前記シンドローム値の和を前記エラー度として記録する
請求項５に記載のメモリシステム。
【請求項７】
前記エラービット推定部に保持されている前記推定されたエラービットのビット系列及び前記第１エラー度計算部に記録されている前記エラー度の系列を入力するデータ入力部と、
入力された前記推定されたエラービットのビット系列及び前記エラー度の系列に基づいて前記受信語を基準としたビット系列における１以上のビットを反転させることで１以上のテストパタンを生成するテストパタン生成部と、
前記１以上のテストパタンに対し、前記外符号の規則を用いて訂正可能数を超えた復号を実行することで、１又は複数の復号語候補を生成する復号部と、
前記受信語と前記１又は複数の復号語候補それぞれとを比較し、前記受信語と前記１又は複数の復号語候補それぞれとの間でビット反転が生じた位置を特定し、特定した前記位置のエラー度の和を計算する第２エラー度計算部と、
前記１又は複数の復号語候補の前記エラー度の和の中から最大のエラー度の和の復号語候補を最尤復号語として選択する最尤復号語選択部と、
を備える請求項５に記載のメモリシステム。
【請求項８】
前記復号器は、前記１以上のテストパタンに対して前記外符号の限界距離復号を実行し、
前記第２エラー度計算部は、前記限界距離復号が成功した１又は複数の復号語候補に対し、前記受信語を基準として前記ビット反転が生じた位置の前記エラー度の和を計算する
請求項７に記載のメモリシステム。
【請求項９】
前記１以上のテストパタンに対して前記外符号のパリティ検査を実行する第３パリティ検査部をさらに備え、
前記第２エラー度計算部は、前記第３パリティ検査部によるパリティ検査の結果、シンドローム値が０となった１又は複数の復号語候補に対し、前記受信語を基準として前記ビット反転が生じた位置の前記エラー度の和を計算する
請求項７に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下の実施形態は、一般的に、メモリシステムに関する。
【背景技術】
【０００２】
フラッシュメモリ等の記憶装置に記録されたデータは、硬判定読出し（ハードビットリードともいう）又は軟判定読出し（ソフトビットリードともいう）のいずれかにより読み出すことができる。硬判定読出しでは、記録されているデータが、‘０’又は‘１’のビットとして読み出される。一方、軟判定読出しでは、記録されているデータが、‘０’であるか‘１’であるかの確率に関する情報として読み出される。
【０００３】
従来の代数的符号では、軟判定読出しを行った場合には符号の訂正可能数を超えた復号を行うことができるが、硬判定読出しを行った場合には、一般に符号の訂正可能数を超えた復号を行うことができない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−６５９６９号公報
【特許文献２】米国特許出願公開第２００７／０１９５８９４号明細書
【特許文献３】特開２００４−２８８２８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の一つの実施形態は、硬判定読出し時に高い訂正能力を持つ復号を行うことが可能なメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
実施形態によれば、メモリシステムは、連接符号を記録する不揮発性メモリと、前記不揮発性メモリから読み出された前記連接符号の受信語を復号し、当該復号により得られた復号語を出力する復号器と、を備え、前記復号器は、前記読み出された連接符号のうち外符号の符号語制約が課せられているビット系列である外符号部に対して限界距離復号を実行し、当該限界距離復号により得られた第１復号結果を出力する第１外符号復号器と、前記第１外符号復号器から出力された前記第１復号結果のビット系列に対して内符号の規則に基づきエラービットの推定を実行し、当該推定により得られた前記エラービットの集合を出力する内符号エラービット推定部と、前記第１外符号復号器から出力された前記第１復号結果に対し、前記内符号エラービット推定部から出力された前記エラービットの集合を用いた復号を実行する第２外符号復号器とを備える。
【図面の簡単な説明】
【０００７】
【図１】図１は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。
【図２】図２は、第１の実施形態に係る復号器の概略構成例を示すブロック図である。
【図３Ａ】図３Ａは、第１の実施形態において生成される連接符号語の例を示す図である。
【図３Ｂ】図３Ｂは、第１の実施形態において生成される連接符号語の他の例を示す図である。
【図４】図４は、第１の実施形態に係る復号器のより詳細な構成例を示すブロック図である。
【図５】図５は、第１の実施形態に係る内符号エラービット推定部のより具体的な構成例を示すブロック図である。
【図６】図６は、第１の実施形態に係る第２外符号復号部のより具体的な構成例を示すブロック図である。
【図７】図７は、第１の実施形態に係る復号動作の一例を示すフローチャートである。
【図８】図８は、第１の実施形態に係るパリティ検査行列の一例を示す図である。
【図９】図９は、第１の実施形態に係る受信語の一例を示す図である。
【図１０】図１０は、図７のステップＳ１０２の復号の結果として最終的に得られるビット系列の一例を示す図である。
【図１１】図１１は、図７のステップＳ１０３に示す手順により得られるシンボル系列の一例を示す図である。
【図１２】図１２は、図７のステップＳ１０６に示すパリティ検査の結果として得られるシンドローム値が０となるフリップ位置のペア及びその結果得られる復号語候補のスコアの一例を示す図である。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態に係るメモリシステムを詳細に説明する。なお、以下の実施形態により本発明が限定されるものではない。
【０００９】
誤り訂正符号（Error Correcting Codes：ＥＣＣ）は、記憶装置から読み出したデータに含まれる誤りを訂正することができる。例えば代数的符号では、記憶装置に記録したデータを硬判定読出しした場合、符号の最小距離から定まる訂正可能数までの誤りビットを限界距離復号法により訂正することができる。そこで以下の実施形態では、外符号に代数的符号、内符号に疎グラフに基づく符号を用いた連接符号を２値のデータ（硬判定値）として読み出して得られた受信語を復号する際に、内符号の情報を用いて外符号の復号を実行することで、外符号の訂正可能数を超えた復号を可能にする。それにより、読出し遅延の比較的小さい硬判定読出し時に高い訂正能力を持つ復号を行うことが可能なメモリシステムが実現される。
【００１０】
（第１の実施形態）
まず、第１の実施形態に係るメモリシステムについて、図面を参照して詳細に説明する。図１は、第１の実施形態に係るメモリシステムの概略構成例を示すブロック図である。図１に示すように、メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とを備える。メモリシステム１は、ホスト３０と接続可能であり、図１ではホスト３０と接続された状態が示されている。ホスト３０は、例えば、パーソナルコンピュータ、携帯端末などの電子機器であってよい。
【００１１】
不揮発性メモリ２０は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤ型フラッシュメモリ（以下、単にＮＡＮＤメモリという）である。以下の説明では、不揮発性メモリ２０としてＮＡＮＤメモリが用いられた場合を例示するが、不揮発性メモリ２０として３次元構造フラッシュメモリ、ＲｅＲＡＭ（Resistance Random Access Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）等のＮＡＮＤメモリ以外の記憶装置を用いることも可能である。また、不揮発性メモリ２０が半導体メモリであることは必須ではなく、半導体メモリ以外の種々の記憶媒体に対して本実施形態を適用することも可能である。
【００１２】
メモリシステム１は、いわゆるＳＳＤ（Solid State Drive）や、メモリコントローラ１０と不揮発性メモリ２０とが１つのパッケージとして構成されるメモリカード等、不揮発性メモリ２０を備える種々のメモリシステムであってよい。
【００１３】
メモリコントローラ１０は、ホスト３０からの書込み要求に従って不揮発性メモリ２０への書込みを制御する。また、ホスト３０からの読出し要求に従って不揮発性メモリ２０からの読み出しを制御する。メモリコントローラ１０は、ホストＩ／Ｆ（ホストインタフェース）１５、メモリＩ／Ｆ（メモリインタフェース）１３、制御部１１、符号化／復号部（コーデック）１４及びデータバッファ１２を備える。ホストＩ／Ｆ１５、メモリＩ／Ｆ１３、制御部１１、符号化／復号部１４及びデータバッファ１２は、内部バス１６で相互に接続されている。
【００１４】
ホストＩ／Ｆ１５は、ホスト３０との間のインタフェース規格に従った処理を実施し、ホスト３０から受信した命令、書込み対象のユーザデータなどを内部バス１６に出力する。また、ホストＩ／Ｆ１５は、不揮発性メモリ２０から読み出されて復元されたユーザデータ、制御部１１からの応答などをホスト３０へ送信する。
【００１５】
メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０への書込み処理を行う。また、メモリＩ／Ｆ１３は、制御部１１の指示に基づいて、不揮発性メモリ２０からの読み出し処理を行う。
【００１６】
制御部１１は、メモリシステム１の各構成要素を統括的に制御する。制御部１１は、ホスト３０からホストＩ／Ｆ１５経由で命令を受けた場合に、その命令に従った制御を行う。例えば、制御部１１は、ホスト３０からの命令に従って、不揮発性メモリ２０へのユーザデータ及びパリティの書き込みをメモリＩ／Ｆ１３へ指示する。また、制御部１１は、ホスト３０からの命令に従って、不揮発性メモリ２０からのユーザデータ及びパリティの読み出しをメモリＩ／Ｆ１３へ指示する。
【００１７】
また、制御部１１は、ホスト３０から書込み要求を受信した場合、データバッファ１２に蓄積されるユーザデータに対して、不揮発性メモリ２０上の格納領域（メモリ領域）を決定する。すなわち、制御部１１は、ユーザデータの書込み先を管理する。ホスト３０から受信したユーザデータの論理アドレスと該ユーザデータが格納された不揮発性メモリ２０上の格納領域を示す物理アドレスとの対応はアドレス変換テーブルとして格納される。
【００１８】
また、制御部１１は、ホスト３０から読出し要求を受信した場合、読出し要求により指定された論理アドレスを上述のアドレス変換テーブルを用いて物理アドレスに変換し、該物理アドレスからの読み出しをメモリＩ／Ｆ１３へ指示する。
【００１９】
ＮＡＮＤメモリでは、一般に、ページと呼ばれるデータ単位で、書き込み及び読み出しが行われ、ブロックと呼ばれるデータ単位で消去が行われる。本実施形態では、この同一のワード線に接続される複数のメモリセルをメモリセルグループと呼ぶ。メモリセルがシングルレベルセル（ＳＬＣ）である場合は、１つのメモリセルグループが１ページに対応する。メモリセルがマルチレベルセル（ＭＬＣ）である場合は、１つのメモリセルグループが複数ページに対応する。また、各メモリセルはワード線に接続するとともにビット線にも接続される。したがって、各メモリセルは、ワード線を識別するアドレスとビット線を識別するアドレスとで識別することが可能である。
【００２０】
データバッファ１２は、メモリコントローラ１０がホスト３０から受信したユーザデータを不揮発性メモリ２０へ記憶するまでに一時格納する。また、データバッファ１２は、不揮発性メモリ２０から読み出したユーザデータをホスト３０へ送信するまでに一時格納する。データバッファ１２には、例えば、ＳＲＡＭ（Static Random Access Memory）やＤＲＡＭ（Dynamic Random Access Memory）などの汎用メモリを用いることができる。
【００２１】
ホスト３０から送信されるユーザデータは、内部バス１６に転送されてデータバッファ１２に一旦格納される。符号化／復号部１４は、不揮発性メモリ２０に格納されるユーザデータを符号化して符号語を生成する。また、符号化／復号部１４は、不揮発性メモリ２０から読み出された受信語を復号してユーザデータを復元する。そこで符号化／復号部１４は、符号化器（Encoder）１７と復号器（Decoder）１８を備える。なお、符号化／復号部１４により符号化されるデータには、ユーザデータ以外にも、メモリコントローラ１０内部で用いる制御データ等が含まれてもよい。
【００２２】
次に、本実施形態の書込み処理について説明する。制御部１１は、不揮発性メモリ２０への書込み時に、ユーザデータの符号化を符号化器１７に指示する。その際、制御部１１は、不揮発性メモリ２０における符号語の格納場所（格納アドレス）を決定し、決定した格納場所もメモリＩ／Ｆ１３へ指示する。
【００２３】
符号化器１７は、制御部１１からの指示に基づいて、データバッファ１２上のユーザデータを符号化して符号語を生成する。符号化方式としては、後述するように、例えば、ＢＣＨ（Bose-Chandhuri-Hocquenghem）符号やＲＳ（リード・ソロモン）符号のような代数的符号を用いた符号化方式や、ＬＤＰＣ（Low-Density Parity-Check）符号のような疎グラフに基づく符号を用いた符号化方式とを採用することができる。メモリＩ／Ｆ１３は、制御部１１から指示された不揮発性メモリ２０上の格納場所へ符号語を格納する制御を行う。
【００２４】
次に、本実施形態の不揮発性メモリ２０からの読出し時の処理について説明する。制御部１１は、不揮発性メモリ２０からの読出し時に、不揮発性メモリ２０上のアドレスを指定してメモリＩ／Ｆ１３へ読み出しを指示する。また、制御部１１は、復号器１８へ復号の開始を指示する。メモリＩ／Ｆ１３は、制御部１１の指示に従って、不揮発性メモリ２０の指定されたアドレスから受信語を読み出し、読み出した受信語を復号器１８に入力する。復号器１８は、この不揮発性メモリ２０から読み出された受信語を復号する。
【００２５】
復号器１８は、不揮発性メモリ２０から読み出された受信語を復号する。図２は、復号器１８の概略構成例を示すブロック図である。図２に示すように、復号器１８は、硬判定値を入力として復号を実行し、その結果として硬判定値を出力するＨＩＨＯ（hard-input hard-output）復号部１８１と、軟判定値を入力として復号を実行し、その結果として軟判定値を出力するＳＩＳＯ（soft-input soft-output）復号部１８２とを備える。
【００２６】
一般に、ＳＩＳＯ復号は、ＨＩＨＯ復号より誤り訂正能力は高いが処理時間が長いという特徴を持つ。そこで本実施形態では、まず、ＨＩＨＯ復号部１８１が、不揮発性メモリ２０から硬判定値として読み出された受信語をＨＩＨＯ復号し、硬判定復号により復号できなかった受信語を軟判定値として読み出すように構成する。そして、ＳＩＳＯ復号部１８２が、軟判定値として読み出された受信語をＳＩＳＯ復号するように構成する。ただし、本実施形態では、ＨＩＨＯ復号で十分な誤り訂正能力を実現することが可能であるため、ＳＩＳＯ復号が省略されてもよい。
【００２７】
また、本実施形態において、符号化器１７は、ＢＣＨ符号やＲＳ符号のような代数的符号を外符号とし、ＬＤＰＣ符号のような疎グラフに基づく符号を内符号とする連接符号を生成する。外符号は、符号長ｎ、情報長ｋ及び最小距離ｄの（ｎ，ｋ，ｄ）−符号とする。その場合、不揮発性メモリ２０に記録されているデータを‘０’又は‘１’の硬判定値のデータとして読み出したとすると、外符号では限界距離復号法によりｔ（＝［（ｄ−１）／２］）ビットまでの誤りを訂正することができる。ここで、［ｘ］は、ｘ以下の最大の整数を表す。また、上式により定まるｔを、符号の訂正可能数と呼ぶ。
【００２８】
つづいて、符号化器１７による連接符号の符号化方法について説明する。符号化器１７にある長さの情報語（ユーザデータ）が与えられたとすると、その情報語は、まず外符号の符号器（以下、外符号器という）を用いて符号化される。それにより、外符号の符号語（以下、外符号語という）が生成される。なお、情報語、外符号器及び外符号語は、それぞれ複数であってもよい。その場合、それら外符号の符号長、情報長及び最小距離は、異なっていてもよい。また、情報語は外符号の符号器により符号化される前に、ＣＲＣ、ＢＣＨ符号、ＲＳ符号などの符号により符号化されていてもよい。
【００２９】
次に、１つ又は複数の外符号語が内符号の符号器（以下、内符号器という）への入力とされ、それにより、内符号の符号語（以下、内符号語という）が生成される。その結果、連接符号の符号語（以下、連接符号語という）が生成される。なお、内符号器及び内符号語は、複数であってもよい。その場合、それら内符号の符号長、情報長及び最小距離は、異なっていてもよい。
【００３０】
以上の手順により符号化器１７によって生成された連接符号語の構成の例を図３Ａ及び図３Ｂに示す。まず、図３Ａに示す連接符号語Ｃ１では、局所的なビット系列ｃ１１，ｃ１２，…，ｃ１ｎ，…それぞれに対して、外符号の符号語制約が課せられている。また、連接符号語Ｃ１では、別の局所的なビット系列ｃ１００に対して、内符号の符号語制約が課せられている。一方、図３Ｂに示す連接符号語Ｃ２でも同様に、局所的なビット系列ｃ２１，ｃ２２，…，ｃ２ｎ，…それぞれに対して、外符号の符号語制約が課せられ、また、別の局所的なビット系列ｃ２０１〜ｃ２０３に対して、内符号の符号語制約が課せられている。これらの連接符号語Ｃ１及びＣ２は、ビット毎又は多値変調された形で不揮発性メモリ２０にデータとして記録される。なお、本説明において、符号語制約が課せられているとは、符号化されていることを意味している。
【００３１】
つづいて、復号器１８による連接符号の復号方法について説明する。そこで、図３Ａに例示した連接符号語Ｃ１が不揮発性メモリ２０に記録され、その連接符号語Ｃ１を‘０’又は‘１’の硬判定値のデータとして読み出すことで、受信語を得た場合を仮定する。そのような場合、読み出された受信語では、図３Ａに例示した符号語を基準として、そのうちの１つ以上のビットが‘０’から‘１’へ又は‘１’から‘０’へと反転している場合がある。本説明では、そのようなビットの反転をエラーと称する。また、読み出された受信語（連接符号語Ｃ１に相当）のうち、外符号の符号語制約が課せられている局所的なビット系列（ビット系列ｃ１１，ｃ１２，…，ｃ１ｎ，…に相当）を外符号部と称する。さらに、読み出された受信語のうち、内符号の符号語制約が課せられている局所的なビット系列（ビット系列ｃ１００に相当）を内符号部と称する。
【００３２】
つづいて、図４に、本実施形態に係る復号器のより詳細な構成例を示す。図４に示すように、復号器１８は、１以上の第１外符号復号器よりなる第１外符号復号器群１０２と、１以上の内符号エラービット推定部よりなる内符号エラービット推定部群１０３と、１以上の第２外符号復号器よりなる第２外符号復号器群１０４と、１以上の内符号復号器よりなる内符号復号器群１０５と、１以上の内符号／外符号パリティ検査部よりなる内符号／外符号パリティ検査部群１０６とを備える。
【００３３】
第１外符号復号器群１０２は、不揮発性メモリ２０から読み出された受信語１０１又は内符号／外符号パリティ検査部群１０６からの出力を入力とし、入力された受信語１０１又は内符号／外符号パリティ検査部群１０６からの出力における外符号部に対して限界距離復号を行う。なお、内符号／外符号パリティ検査部群１０６からの出力に対しては限界距離復号を行わなくてもよい。
【００３４】
内符号エラービット推定部群１０３は、第１外符号復号器群１０２の出力を入力とし、この入力に対して内符号の規則に基づきエラービットの推定を行う。個々の内符号エラービット推定部１０３Ａのより具体的な構成例を、図５に示す。図５に示すように、個々の内符号エラービット推定部１０３Ａは、データ入力部１３１と、１つ以上のパリティ検査部１３２と、シンドロームレジスタ１３３と、シンドロームカウンタ１３４と、エラービット推定部１３５と、エラー度計算部１３６とを備える。
【００３５】
データ入力部１３１は、受信語１０１又は受信語１０１に対して第１外符号復号器群１０２が限界距離復号を実行することで得られた復号結果であるビット系列又は内符号／外符号パリティ検査部群１０６からの出力を入力として受け付ける。個々のパリティ検査部１３２は、入力されたビット系列に対して内符号のパリティ検査を行う。シンドロームレジスタ１３３は、各パリティ検査の結果得られる１又は複数のシンドローム値を保存する。シンドロームカウンタ１３４は、各ビットが関わるパリティ検査のシンドローム値の和を計算する。
【００３６】
エラービット推定部１３５は、入力されたビット系列から内符号の規則を用いてエラーであるビット（以下、推定エラービットという）を推定し、推定エラービットのビット系列を保存し出力する。より具体的には、エラービット推定部１３５は、シンドロームカウンタ１３４に保存されているシンドローム値の和に対し、ある閾値を基準としてこの閾値を超えたビットを推定エラービットであると推定し、推定エラービットのビット系列を記録し出力する。なお、以下の説明では、推定エラービットのビット系列を推定エラービット系列といい、推定エラービットの集まりを推定エラービットの集合という。
【００３７】
エラー度計算部１３６は、推定エラービットそれぞれに対してそのビットがエラーである可能性の度合いを示すエラー度を計算し、計算されたエラー度の系列（以下、エラー度系列という）を記録する。より具体的には、エラー度計算部１３６は、推定エラービットに対し、そのビットが関わるパリティ検査のシンドローム値の和をエラー度とし記録し出力する。
【００３８】
なお、エラー度は、非負の実数又は整数であり、エラー度が大きいものほどエラーである確率が高いと推定されたことを示している。このようなエラー度には、上述のように、例えばビット毎に計算されたシンドローム値の和を用いることができる。また、ここでは、どのビットを推定エラービットの集合に含めるかを定めるエラー度閾値Ｔが予め与えられ、内符号エラービット推定部群１０３は、エラー度がエラー度閾値Ｔ以上であるビットを推定エラービットの集合に含めるものとする。
【００３９】
図４に戻り説明する。第２外符号復号器群１０４は、第１外符号復号器群１０２の出力及び内符号エラービット推定部群１０３の出力を入力とし、この入力における外符号部に対して外符号の訂正可能数を超えた復号を行う。個々の第２外符号復号器１０４Ａのより具体的な構成例を、図６に示す。図６に示すように、個々の第２外符号復号器１０４Ａは、データ入力部１４１と、テストパタン生成部１４２と、限界距離復号部１４３と、パリティ検査部１４４と、エラー度計算部１４５と、最尤復号語選択部１４６とを備える。
【００４０】
データ入力部１４１は、例えば内符号エラービット推定部１０３Ａのエラービット推定部１３５に記録されている推定エラービット系列及びエラー度計算部１３６に記録されているエラー度系列を入力として受け付ける。
【００４１】
テストパタン生成部１４２は、データ入力部１４１により受け付けられた推定エラービット系列及びエラー度系列に基づいて受信語１０１を基準としていくつかのビットを反転させたビット系列、すなわちテストパタンを１又は複数作成する。
【００４２】
限界距離復号部１４３は、テストパタン生成部１４２が生成した１又は複数のテストパタンに対し、外符号の規則を用いて訂正可能数を超えた復号、例えば外符号の限界距離復号を行い、その結果検出された復号語候補の中から１又は複数の復号語候補を選択する。なお、復号語候補の選択は、例えばシンドローム値等から求まる尤度（正しい復号語であることを示す度合い）の高い順等であってもよい。
【００４３】
パリティ検査部１４４は、限界距離復号部１４３で選択された１又は複数の復号語候補に対して外符号のパリティ検査を行なう。
【００４４】
エラー度計算部１４５は、受信語１０１と復号語候補それぞれとを比較してビット反転が生じた位置のエラー度の和を計算する。又は、エラー度計算部１４５は、限界距離復号が成功した１又は複数の復号語候補に対し、受信語１０１を基準としてビット反転が生じた位置のエラー度の和を計算する。若しくは、エラー度計算部１４５は、パリティ検査部１４４によるパリティ検査の結果シンドローム値が０となった１又は複数の復号語候補に対し、受信語１０１を基準としてビット反転が生じた位置のエラー度の和を計算する。
【００４５】
最尤復号語選択部１４６は、前記エラー度計算部１４５で計算されたエラー度の和の中から最大のエラー度の和に対応する復号語候補を最も尤もらしい復号語（最尤復号語ともいう）として選択して記録し出力する。
【００４６】
図４に戻り説明する。内符号復号器群１０５は、第２外符号復号器群１０４の出力を入力とし、この入力に対して内符号の規則に基づき復号を行う。なお、内符号復号器群１０５による復号を実行するか否かは、例えばユーザによるホスト３０を介した設定や各種条件に基づいて適宜判断されてもよい。
【００４７】
内符号／外符号パリティ検査部群１０６は、内符号復号器群１０５の出力を入力とし、この入力における内符号部及び外符号部それぞれのパリティ検査を行う。内符号／外符号パリティ検査部群１０６は、内符号部及び外符号部それぞれのパリティ検査においてエラーがないと判定された場合、内符号復号器群１０５の出力を復号語１０７として出力する。一方、内符号部又は外符号部のパリティ検査においてエラーがあると判定された場合、内符号／外符号パリティ検査部群１０６は、内符号復号器群１０５の出力を第１外符号復号器群１０２への入力とする。なお，ユーザデータにエラーがないことを保証すれば十分な場合には、必ずしも外符号のパリティ検査においてエラーがないと判定される必要はない。また、ユーザデータが外符号の符号器により符号化される前にＣＲＣ、ＢＣＨ符号、ＲＳ符号などの符号により符号化されている場合は、それらのパリティ検査が行われ、パリティ検査でエラーがないと判定された場合に、内符号復号器群１０５の出力を復号語１０７として出力する。
【００４８】
つづいて、本実施形態に係る復号器１８における復号動作について、図面を参照して詳細に説明する。図７は、本実施形態に係る復号動作の一例を示すフローチャートである。
【００４９】
図７に示すように、本実施形態に係る復号動作では、まず、メモリＩ／Ｆ１３によって不揮発性メモリ２０から読み出された連接符号の受信語１０１が復号器１８に入力されるのを待機し（ステップＳ１０１のＮＯ）、受信語１０１が入力されると（ステップＳ１０１のＹＥＳ）、第１外符号復号器群１０２が、入力された受信語１０１における外符号部に対して、限界距離復号を実行する（ステップＳ１０２）。この限界距離復号により検出された外符号部におけるエラー数が訂正可能数以下である場合、第１外符号復号器群１０２は、受信語１０１を正しい復号語に訂正することができる。一方で、外符号部におけるエラー数が訂正可能数より大きい場合には、次の２つのパターンがあり得る。１つ目のパターンでは、復号に失敗し、限界距離復号前の外符号部のビット系列がそのまま復号結果として返される。２つ目のパターンでは、誤訂正が発生し、本来記録した外符号部のビット系列とは異なるビット系列が返される。このように、２つのパターンのいずれでも限界距離復号を行った結果として正しい復号語を得ることができないが、本動作では、１つ目のパターンを復号失敗とし、２つ目のパターンは復号に失敗していないとする。
【００５０】
ステップＳ１０２の限界距離復号の結果は、内符号エラービット推定部群１０３に入力される。内符号エラービット推定部群１０３は、連接符号の受信語１０１に対してステップＳ１０２の動作を行った結果得られたビット系列に対し、内符号部におけるエラービットの位置を推定する（ステップＳ１０３）。エラービットを推定する過程において、全てのビットには、そのビットがエラーである可能性を示すエラー度が付与される。内符号エラービット推定部群１０３は、予め設定されているエラー度閾値Ｔに基づいて、エラー度がエラー度閾値Ｔ以上であるビットを推定エラービットの集合に含め、これにより得られた推定エラービットの集合を出力する。
【００５１】
内符号エラービット推定部群１０３で得られた推定エラービットの集合は、第２外符号復号器群１０４に入力される。第２外符号復号器群１０４は、ステップＳ１０２で復号に失敗した外符号部に対し、ステップＳ１０３で得られた推定エラービットの情報を用いることにより、外符号の訂正可能数を超えた復号を実行する（ステップＳ１０４）。この復号では、第２外符号復号器群１０４は、外符号部の受信語１０１を基準として、推定エラービットの集合に含まれるＦ個のビットをフリップしたビット系列（以降、テストパタンと呼ぶ）を用意する。ある外符号部の受信語１０１に対しステップＳ１０３で得られた推定エラービットの個数をＥ個とすると、第２外符号復号器群１０４は、ＥＣＦ個のテストパタンを用意する。ただし、フリップするビット数Ｆは複数種類存在してもよい。第２外符号復号器群１０４は、これらのテストパタンに対し、次の２通りのいずれかの方法により復号を行う。
【００５２】
・（第１の方法）パリティ検査による復号
第１の方法では、第２外符号復号器群１０４は、テストパタン全てに対し、外符号のパリティ検査を実行し、このパリティ検査の結果、シンドロームが０になったテストパタンを復号語候補とする。この方法では、比較的誤訂正率を下げつつ訂正可能数を超えた復号を行うことができる。
【００５３】
・（第２の方法）限界距離復号による復号
第２の方法では、第２外符号復号器群１０４は、テストパタン全てに対し、外符号の限界距離復号を実行し、この復号に成功したテストパタンを復号語候補とする。この方法では、比較的推定エラービットの数が少ない場合でも訂正可能数を超えた復号を行うことができる。
【００５４】
つづいて、第２外符号復号器群１０４は、ステップＳ１０４の動作において、上記の２通りの方法のいずれかで得られた各復号語候補に対し、以下のようにしてスコアを計算する。まず第１に、外符号部の受信語１０１からある復号語候補が得られた場合、フリップされたビットの位置集合をＩ＝｛ｉ１，ｉ２，…，ｉｆ｝とする。ここで、ｆはフリップされたビットの総数である。第２に、Ｉのビット位置に対応し、以下の式（１）により得られるエラー度の和Ｓをスコアとして計算する。
【数１】
2019057752.tif 000003
【００５５】
以上の手順により各復号語候補に対するスコアを計算すると、第２外符号復号器群１０４は、ステップＳ１０４の動作において、スコアが最も大きい復号語候補を最終的な外符号復号語として選択する。
【００５６】
ステップＳ１０４において最終的に選択された外符号復号語は、内符号復号器群１０５に入力される。内符号復号器群１０５は、ステップＳ１０４において最終的に選択された外符号復号語のビット系列における内符号部に対し、次の２通りのいずれかの方法により復号を実行する（ステップＳ１０５）。
【００５７】
・（第１の方法）通常の復号
第１の方法では、内符号復号器群１０５は、内符号部の全てのビットを復号対象として復号を行う。この方法では、比較的多くのエラービットを訂正することができる。
【００５８】
・（第２の方法）外符号の結果を利用した復号
第２の方法では、内符号復号器群１０５は、ステップＳ１０２又はステップＳ１０４において復号に成功した外符号部を除いた内符号部に対して、内符号の復号を行う。この方法では、比較的誤訂正率を下げつつ復号を行うことができる。
【００５９】
ステップＳ１０５における内符号に対する復号の結果は、内符号／外符号パリティ検査部群１０６に入力される。内符号／外符号パリティ検査部群１０６は、ステップＳ１０５の復号の結果として得られるビット系列に対し、内符号部及び外符号部のパリティ検査を行う（ステップＳ１０６）。内符号部及び外符号部のパリティ検査においてエラーがないと判定された場合（ステップＳ１０７のＮＯ）、内符号／外符号パリティ検査部群１０６の出力が復号語１０７として復号器１８から出力され（ステップＳ１０８）、本動作が終了する。一方、内符号部又は外符号部のパリティ検査においてエラーがあると判定された場合（ステップＳ１０７のＹＥＳ）、ステップＳ１０２〜Ｓ１０６までの動作の繰返し回数が予め設定しておいた所定回数未満であるか否かが判定され（ステップＳ１０９）、繰返し回数が所定回数未満である場合（ステップＳ１０９のＹＥＳ）、本動作がステップＳ１０２へリターンして、内符号／外符号パリティ検査部群１０６の出力が第１外符号復号器群１０２へ入力される。一方、繰返し回数が所定回数に達していた場合（ステップＳ１０９のＮＯ）、復号失敗と判断されて（ステップＳ１１０）、本動作が終了する。
【００６０】
なお、図７に示す動作において、ステップＳ１０４までの過程において正しいと判断できる復号語１０７が発見されている場合には、ステップＳ１０５〜Ｓ１０７の動作における少なくとも１つをスキップすることも可能である。
【００６１】
つづいて、本実施形態に係る復号動作について、具体例を用いて詳細に説明する。本説明では、符号長８、情報長４及び最小距離４の拡大ハミング符号を外符号とし、符号長３０及び情報長１７のＬＤＰＣ符号を内符号とする連接符号を考える。ここで、外符号の拡大ハミング符号の数は２つであるとする。また、内符号であるＬＤＰＣ符号のパリティ検査行列は図８に示すパリティ検査行列Ｈで与えられるとする。ただし、図８における空欄部分は‘０’を表し、局所的なビット系列６０１及び６０２はそれぞれ外符号の制約を満たすビット系列であるとする。また、連接符号の符号語ｃ＝（ｃ１，ｃ２，…，ｃ３０）において、ｃ’＝（ｃ１，…，ｃ８）及びｃ”＝（ｃ９，…，ｃ１６）の局所的なビット系列は、外符号である拡大ハミング符号の符号語制約を満たすものとする。
【００６２】
ここで、図８に示す内符号のパリティ検査行列Ｈについて説明する。なお、図８の説明にあたり、全ての要素が０であるビット系列が連接符号の符号語として不揮発性メモリ２０に記録されており、この記録されているデータを読み出したときに、１、９及び１５番目のビットにエラーが発生した場合を仮定する。このような仮定の下では、受信語ｒは、図９に示すように、ｒｊ＝０（ｊ≠１，９，１５）で且つｒ１＝ｒ９＝ｒ１５＝１であるビット配列となる。ただし、図９における空欄部分は０を表し、局所的なビット系列７０１及び７０２はそれぞれ外符号の制約を満たすビット系列であるとする。なお、図９〜図１１における枠外に付された１〜３０までの数字は、各受信ビットのアドレスを示している。
【００６３】
図９に示すようなビット系列の受信語ｒを受信（図７のステップＳ１０１）した場合の復号器１８の復号動作（図７に相当）は、以下のようになる。
【００６４】
・ステップＳ１０２
図７のステップＳ１０２では、第１外符号復号器群１０２が、受信語ｒの外符号部ｒ’＝（ｒ１，ｒ２，…，ｒ８）及びｒ”＝（ｒ９，ｒ１０，…，ｒ１６）に対し、拡大ハミング符号で限界距離復号を行う。拡大ハミング符号の限界距離復号では、１ビットエラーを訂正することができ、また、２ビットエラーを検出することができる。言い換えると、１ビットエラーの場合は復号に成功し、２ビットエラーの場合は復号に失敗する。したがって、エラー数が１つである外符号部の受信語ｒ’は正しく訂正され、エラー数が２つである外符号部の受信語ｒ”’は復号に失敗することとなる。ステップＳ１０２の復号の結果として最終的に得られるビット系列ｄ’を図１０に示す。図１０における空欄部分は０を表し、局所的なビット系列８０１及び８０２はそれぞれ外符号の制約を満たすビット系列であるとする。
【００６５】
・ステップＳ１０３
図７のステップＳ１０３では、内符号エラービット推定部群１０３は、連接符号の受信語ｒに対してステップＳ１０２の動作を行った結果得られるビット系列ｄ’に対し、内符号部に対するエラー位置の推定を行う。具体的には、図８のパリティ検査行列Ｈで定められる内符号に対してビット系列ｄ’のパリティ検査を行い、各ビットに対してパリティ検査の結果シンドロームが０にならなかった場合の数をカウントする。この手順は以下のように表すことができる。
【００６６】
まず、シンドロームｓ＝ｄ’ＨＴを計算する。ただし、この演算は２元体上で行う。また、ＨＴはパリティ検査行列Ｈの転置を表す。つぎに、各ビットに対してパリティ検査が通らなかった場合の数ｕ＝ｓＨを計算する。ただし、この演算は整数体上で行う。その結果、ｕの各要素が与えられたエラー度閾値Ｔ以上であるビットを推定エラービットとする。
【００６７】
このような手順により得られるシンボル系列ｕの一例を図１１に示す。ただし、図１１において、空欄部分は０を表し、局所的なビット系列９０１及び９０２はそれぞれ外符号の制約を満たすビット系列であるとする。ここで、エラー度閾値Ｔを２とすると、ステップＳ１０３の結果として得られる推定エラービットの集合は、｛７，９，１２，１３，１４，１５，１６，１８，１９，２３｝となる。
【００６８】
・ステップＳ１０４
図７のステップＳ１０４では、第２外符号復号器群１０４は、ステップＳ１０２で復号に失敗した外符号部の受信語ｒ”＝（ｒ９，ｒ１０，…，ｒ１６）部分に対し、ステップＳ１０３で得られた情報を用いて外符号の訂正可能数を超えた復号を行う。ここでは、第１の方法として例示したテストパタンに対するパリティ検査を用いた復号を行うものとする。ステップＳ１０３で得られた該当箇所の推定エラービット集合は｛９（３），１２（２），１３（２），１４（２），１５（３），１６（２）｝である。ここで、括弧（）内の数字は各推定エラービットのエラー度を表す。実際にフリップするビット数Ｆを２とすると、全テストパタンのうち、パリティ検査の結果、シンドローム値が０となるフリップ位置のペア、及び、その結果得られる復号語候補のスコアは、図１２に示すようになる。よって、最大スコアを持つフリップ組｛９，１５｝が訂正ビット位置と判定され、その結果、外符号部の受信語ｒ”がステップＳ１０４において正しく訂正される。
【００６９】
・ステップＳ１０５
図７のステップＳ１０５では、内符号復号器群１０５は、ステップＳ１０４の動作を行った結果得られるビット系列における内符号部に対して復号を行う。ただし、本具体例では、上述したステップＳ１０４までの動作により受信語ｒ中の全てのエラーが訂正されているため、ステップＳ１０５では訂正は行われない。
【００７０】
・ステップＳ１０６〜Ｓ１０８
図７のステップＳ１０６では、内符号／外符号パリティ検査部群１０６は、ステップＳ１０５の動作を行った結果得られるビット系列に対し、内符号部及び外符号部のパリティ検査を行う。本具体例では、ステップＳ１０４までの動作により受信語ｒ中の全てのエラーが訂正されているため、内符号部及び外符号部のパリティ検査においてエラーがないと判定される（ステップＳ１０７のＮＯ）。その結果、図７のステップＳ１０８では、ステップＳ１０５の動作を行った結果得られるビット系列が復号語として出力される。
【００７１】
以上のように、本実施形態によれば、外符号に代数的符号、内符号に疎グラフに基づく符号を用いた連接符号を硬判定読出しして得られた受信語を復号する際に、内符号の情報を用いて外符号の復号を実行することで、外符号の訂正可能数を超えた復号を可能にする。それにより、読出し遅延の比較的小さい硬判定読出し時に高い訂正能力を持つ復号を行うことが可能なメモリシステムが実現される。
【００７２】
（第２の実施形態）
上述した第１の実施形態では、外符号をＢＣＨ符号やＲＳ符号のような代数的符号とし、内符号をＬＤＰＣ符号のような疎グラフに基づく符号としたが、このような組合せに限定されるものではない。例えば、外符号をハミング符号又はＢＣＨ符号とし、内符号をＱＣ（Quasi-Cyclic）−ＬＤＰＣ符号とする連接符号に対して、第１の実施形態に係る復号器１８による復号動作を実行することも可能である。ただし、この場合、外符号の符号長を、内符号であるＱＣ−ＬＤＰＣ符号のブロックサイズの整数倍とする必要がある。
【００７３】
以上のような構成とすることで、第２の実施形態では、外符号及び内符号ともにブロック単位で処理を行うことが可能となるため、効率的な復号処理を実現することが可能となる。
【００７４】
なお、本実施形態における復号器を含むメモリシステムの構成並びにその他の動作及び効果は、上述した第１の実施形態と同様であるため、ここでは重複する説明を省略する。
【００７５】
（第３の実施形態）
上述した第１の実施形態では、内符号エラービット推定部群１０３を用い、内符号の規則に基づきエラービットの推定を行ったが、これに限定されるものではない。例えば、図４に示す構成において、内符号エラービット推定部群１０３の代わりに、内符号信頼度計算装置群を用いることができる。
【００７６】
内符号信頼度計算装置群は、例えば、受信語１０１、シンドローム値、及び、内符号／外符号パリティ検査部群からの出力を入力として、各ビットの信頼度を計算する。対象ビットの受信語をｒ、予め設定されている受信語の重みをＷ、復号時点における対象ビットの復号語をｖ、対象ビットに関わるシンドローム値をｓとすると、内符号信頼度計算装置群は、以下の式（２）により各ビットの信頼度Ｌを計算することができる。なお、以下の式（２）において、ｒ、ｖ及びｓには、｛０，１｝の２値の代わりに｛＋１，−１｝の２値が用いられるものとする。
【数２】
2019057752.tif 000004
【００７７】
上記式（２）により算出される信頼度Ｌは、ビットがどの程度０でありそうか又は１でありそうかを定量化したものであり、正の大きな値であるほど０である可能性が高く、負の大きな値であるほど１である可能性が高いことを示している。
【００７８】
このように、内符号エラービット推定部群１０３の代わりに、内符号信頼度計算装置群を用いることで、第３の実施形態では、第２外符号復号装置群１０４において信頼度Ｌを用いた復号を行うことができる。その場合、信頼度硬判定値に対して限界距離復号および限界距離を超えた復号が実行される。なお、第１外符号復号器群１でエラーがないと判定された外符号部に対しては、反復復号の所定の繰り返し回数の間は復号が実行されなくてもよい。
【００７９】
限界距離を超えた復号においては、第１の実施形態におけるエラー度の代わりに信頼度Ｌを用いることでテストパタンが生成される。例えば、内符号信頼度計算装置群は、予め設定されている信頼度閾値Ｔに基づいて、信頼度Ｌが信頼度閾値Ｔ以下であるビットを推定エラービットの集合に含め、これにより得られた推定エラービット系列を記録し出力するとともに、推定エラービットそれぞれに対する信頼度Ｌを推定エラービット系列に沿って並べた系列（以下、信頼度系列という）を記録し出力する。これに対し、テストパタン生成部１４２は、入力された推定エラービット系列及び信頼度系列に基づいて、受信語１０１または信頼度硬判定値を基準としていくつかのビットを反転させたビット系列、すなわちテストパタンを１又は複数作成する。
【００８０】
テストパタンを用いた限界距離を超えた復号については第１の実施形態と同様であるため、ここでは重複する説明を省略する。
【００８１】
ただし、テストパタンを用いた限界距離を超えた復号により得られた復号語候補に対しては、第１の実施形態におけるエラー度の代わりに、信頼度Ｌを用いて得られる信頼度の和が各復号語候補に対して計算される。
【００８２】
以上の手順により得られた各復号語候補に対する信頼度の和を計算すると、第２外符号復号装置群１０４は、信頼度の和が最も小さい復号語候補を最終的な外符号復号語として選択する。
【００８３】
なお、本実施形態における復号器を含むメモリシステムの構成並びにその他の動作及び効果は、上述した第１の実施形態と同様であるため、ここでは重複する説明を省略する。
【００８４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００８５】
１…メモリシステム、１０…メモリコントローラ、１１…制御部、１２…データバッファ、１３…メモリＩ／Ｆ、１４…符号化／復号部、１５…ホストＩ／Ｆ、１６…内部バス、１７…符号化器、１８…復号器、１８１…ＨＩＨＯ復号部、１８２…ＳＩＳＯ復号部、２０…不揮発性メモリ、３０…ホスト、１０１…受信語、１０２…第１外符号復号器群、１０３…内符号エラービット推定部群、１０３Ａ…内符号エラービット推定部、１０４…第２外符号復号器群、１０４Ａ…第２外符号復号器、１０５…内符号復号器群、１０６…内符号／外符号パリティ検査部群、１０７…復号語、１３１…データ入力部、１３２…パリティ検査部、１３３…シンドロームレジスタ、１３４…シンドロームカウンタ、１３５…エラービット推定部、１３６…エラー度計算部、１４１…データ入力部、１４２…テストパタン生成部、１４３…限界距離復号部、１４４…パリティ検査部、１４５…エラー度計算部、１４６…最尤復号語選択部。
【図１】
2019057752.tif 000005
【図２】
2019057752.tif 000006
【図３Ａ】
2019057752.tif 000007
【図３Ｂ】
2019057752.tif 000008
【図４】
2019057752.tif 000009
【図５】
2019057752.tif 000010
【図６】
2019057752.tif 000011
【図７】
2019057752.tif 000012
【図８】
2019057752.tif 000013
【図９】
2019057752.tif 000014
【図１０】
2019057752.tif 000015
【図１１】
2019057752.tif 000016
【図１２】
2019057752.tif 000017