(57)【要約】【課題】誤訂正による誤り訂正能力の低下を抑制すること。【解決手段】実施形態によれば、符号化／復号部は、２つ以上の成分符号を有する多次元の誤り訂正符号を復号する復号装置であって、多次元の誤り訂正符号を格納する内部メモリと、少なくとも２つ以上の成分符号それぞれのシンドロームまたはシンドロームが０であるか０以外の値であるかを示す信頼性フラグを管理する付加情報記憶部と、内部メモリに格納された多次元の誤り訂正符号に対して成分符号単位で復号処理を実行することで各成分符号のエラーベクタを検出する復号器と、付加情報記憶部に格納されているシンドロームまたは信頼性フラグに基づいて、復号器によるエラーベクタの検出が誤検出であるか否かを判定する検出部とを備える。【選択図】図２
2018164174.tif 000002
【特許請求の範囲】
【請求項１】
２つ以上の成分符号を有する多次元の誤り訂正符号を復号する復号装置であって、
前記多次元の誤り訂正符号を格納する記憶部と、
少なくとも前記２つ以上の成分符号それぞれのシンドロームまたは前記シンドロームが０であるか０以外の値であるかを示す信頼性フラグを管理する付加情報記憶部と、
前記記憶部に格納された前記多次元の誤り訂正符号に対して成分符号単位で第１復号処理を実行することで各成分符号のエラーベクタを検出する復号器と、
前記付加情報記憶部に格納されている前記シンドロームまたは前記信頼性フラグに基づいて、前記復号器による前記エラーベクタの検出が誤検出であるか否かを判定する検出部と、
を備える復号装置。
【請求項２】
前記復号器は、
前記検出部により前記エラーベクタの検出が誤検出ではないと判定された場合、前記記憶部内の前記多次元の誤り訂正符号における前記エラーベクタに対応するシンボルを書き換える第１の書換え処理を実行するとともに、前記第１の書換え処理後の前記多次元の誤り訂正符号に基づいて前記付加情報記憶部内の前記シンドロームまたは前記信頼性フラグを更新し、
前記検出部により前記エラーベクタの検出が誤検出であると判定された場合、前記第１の書換え処理を実行しない
請求項１に記載の復号装置。
【請求項３】
前記検出部は、第１の次元の第１の成分符号に関してエラーベクタが検出された場合、
前記第１の次元とは異なる第２の次元の成分符号であって前記エラーベクタが示すエラーを含む第２の成分符号に関して前記付加情報記憶部に管理されている前記シンドロームまたは前記信頼性フラグが、前記シンドロームが０であることを示していれば、前記エラーベクタの検出が誤検出であると判定し、
前記第２の成分符号に関して前記付加情報記憶部に管理されている前記シンドロームまたは前記信頼性フラグが、前記シンドロームが０以外の値であることを示していれば、前記エラーベクタの検出が誤検出ではないと判定する
請求項１に記載の復号装置。
【請求項４】
前記検出部は、第１の次元の第１の成分符号に関して検出された複数のエラーを含むエラーベクタに基づいて前記第１の書換え処理が実行された場合であって前記第１の成分符号に関して前記付加情報記憶部で管理されている第１のシンドロームまたは第１の信頼性フラグが前記第１のシンドロームが０であることを示している場合、
前記第１の次元とは異なる第２の次元の成分符号に対する復号によって前記第１の書換え処理の前の値に書き戻されるシンボルの数が２以上であれば、前記第１の書換え処理は誤訂正であると判定し、
前記第１の書換え処理の前の値に書き戻されるシンボルの数が２未満であれば、前記第１の書換え処理は誤訂正ではないと判定し、
前記復号器は、
前記検出部により前記第１の書換え処理が誤訂正であると判定された場合、前記記憶部内の前記多次元の誤り訂正符号における前記エラーベクタに対応するシンボルを書き換える第２の書換え処理を実行するとともに、前記第２の書換え処理後の前記多次元の誤り訂正符号に基づいて前記付加情報記憶部内の前記シンドロームまたは前記信頼性フラグを更新し、
前記検出部により前記第１の書換え処理が誤訂正ではないと判定された場合、前記第２の書換え処理を実行しない
請求項２に記載の復号装置。
【請求項５】
前記付加情報記憶部は、前記記憶部に格納された前記多次元の誤り訂正符号を構成する前記複数の成分符号に関して誤り訂正がなされたシンボルの数を示す訂正シンボル数を管理し、
前記検出部は、前記付加情報記憶部に格納されている前記訂正シンボル数に基づいて、前記第１復号処理により検出された前記エラーベクタに対応する前記記憶部内の前記シンボルに対して前記復号器が以前に実行した第１の書換え処理が誤訂正であるか否かを判定し、
前記復号器は、
前記検出部により前記エラーベクタに対応する前記記憶部内の前記シンボルに対して前記以前に実行した第１の書換え処理が誤訂正であると判定された場合、前記記憶部内の前記多次元の誤り訂正符号における前記エラーベクタに対応するシンボルを書き換える第２の書換え処理を実行するとともに、前記第２の書換え処理後の前記多次元の誤り訂正符号に基づいて前記付加情報記憶部内の前記シンドロームまたは前記信頼性フラグを更新し、
前記検出部により前記エラーベクタに対応する前記記憶部内の前記シンボルに対して前記以前に実行した第１の書換え処理が誤訂正ではないと判定された場合、前記第２の書換え処理を実行しない
請求項２に記載の復号装置。
【請求項６】
前記付加情報記憶部は、前記記憶部に格納された前記多次元の誤り訂正符号を構成する前記複数の成分符号に関して過去に誤訂正がなされたか否かを示す誤訂正フラグを管理し、
前記復号器は、前記付加情報記憶部内の前記誤訂正フラグが過去に誤訂正がなされたことを示している成分符号に対する前記第１復号処理をスキップする
請求項２に記載の復号装置。
【請求項７】
前記復号器は、
復号対象とする成分符号における１つ以上のシンボルを誤りシンボルと仮定するテストパターンを生成し、
前記復号対象とする成分符号を構成するシンボルのうち前記生成されたテストパターンにおいて誤りシンボルと仮定されたシンボルの値を反転することでビットフリップされた成分符号を生成し、
前記ビットフリップされた成分符号に対して第２復号処理を実行する
請求項１に記載の復号装置。
【請求項８】
前記復号器は、
それぞれ異なる組み合わせ位置のシンボルを誤りシンボルと仮定する複数パターンの前記テストパターンを生成し、
前記生成した複数パターンのテストパターンのうち前記第２復号処理に使用するテストパターンを前記付加情報記憶部に管理されている前記付加情報に基づいて絞り込み、
前記絞り込まれたテストパターンを用いて前記復号対象とする成分符号における前記誤りシンボルと仮定されたシンボルの前記値を反転することで前記ビットフリップされた成分符号を生成する
請求項７に記載の復号装置。
【請求項９】
前記復号器は、
それぞれ異なる組み合わせ位置のシンボルを誤りシンボルと仮定する複数パターンの前記テストパターンを生成し、
前記複数パターンのテストパターンをそれぞれ用いて生成された複数の前記ビットフリップされた成分符号に対して前記第２復号処理をそれぞれ実行し、
前記複数のビットフリップされた成分符号に対する前記第２復号処理の結果に基づいて、前記複数パターンのテストパターンの中から尤もらしい復号語を得られるテストパターンを特定し、
前記特定されたテストパターンと前記復号対象とする成分符号との排他的論理和をとることで尤もらしい復号語を生成し、
前記生成された尤もらしい復号語に対して前記第１復号処理を実行し、
前記第１復号処理の結果に基づいて、前記生成された尤もらしい復号語のうち最も尤もらしい復号語を決定する
請求項７に記載の復号装置。
【請求項１０】
前記検出部は、前記テストパターンを用いてビットフリップされた第１の次元の第１の成分符号に対する前記第２復号処理によりエラーベクタが検出された場合、
前記第１の次元とは異なる第２の次元の成分符号であって前記エラーベクタが示すエラーを含む第２の成分符号に関して前記付加情報記憶部に管理されているシンドロームまたは信頼性フラグに前記シンドロームが０であることを示すものが含まれていれば、前記エラーベクタの検出が誤検出であって前記テストパターンの仮説は間違っていると判定し、
前記信頼性フラグまたは前記シンドロームに前記シンドロームが０であることを示すものが含まれていなければ、前記エラーベクタの検出は誤検出ではなく前記第１のテストパターンの仮説は正しい可能性が高いと判定し、
前記復号器は、
前記複数パターンのテストパターンそれぞれを用いて生成された前記第１の次元の複数のビットフリップされた第１の成分符号に対する前記第２復号処理により複数のエラーベクタが検出された場合、前記検出部により前記エラーベクタの検出は誤検出ではなく前記テストパターンの仮説は正しい可能性が高いと判定されたエラーベクタのうちの一つを尤らしいエラーベクタと特定し、
前記記憶部内の前記多次元の誤り訂正符号における前記尤もらしいエラーベクタと前記テストパターンに対応するシンボルを書き換える第１の書換え処理を実行するとともに、前記第１の書換え処理後の前記多次元の誤り訂正符号に基づいて前記付加情報記憶部内の前記シンドロームまたは前記信頼性フラグを更新する
請求項７に記載の復号装置。
【請求項１１】
前記付加情報記憶部は、前記記憶部に格納された前記多次元の誤り訂正符号を構成する前記複数の成分符号に関して誤り訂正がなされたシンボルの数を示す訂正シンボル数を管理し、
前記検出部は、前記付加情報記憶部に格納されている前記訂正シンボル数に、前記テストパターンにおいて仮定されている誤りシンボルの数を加えた数に基づいて、前記復号処理により検出された前記エラーベクタに対応する前記記憶部内の前記シンボルに対して前記復号器が以前に実行した第１の書換え処理が誤訂正であるか否かを判定し、
前記復号器は、
前記検出部により前記エラーベクタに対応する前記記憶部内の前記シンボルに対して前記以前に実行した第１の書換え処理が誤訂正であると判定された場合、前記記憶部内の前記多次元の誤り訂正符号における前記エラーベクタに対応するシンボルを書き換える第２の書換え処理を実行するとともに、前記第２の書換え処理後の前記多次元の誤り訂正符号に基づいて前記付加情報記憶部内の前記シンドロームまたは前記信頼性フラグを更新し、
前記検出部により前記エラーベクタに対応する前記記憶部内の前記シンボルに対して前記以前に実行した第１の書換え処理が誤訂正ではないと判定された場合、前記第２の書換え処理を実行しない
請求項７に記載の復号装置。
【請求項１２】
前記復号器は、前記記憶部に格納された前記多次元の誤り訂正符号を構成する各成分符号から計算されるシンドロームに基づいて前記付加情報記憶部内の各シンドロームまたは各信頼性フラグを設定または更新する請求項１に記載の復号装置。
【請求項１３】
前記復号処理は、反復復号である請求項１に記載の復号装置。
【請求項１４】
前記多次元の誤り訂正符号を構成する前記成分符号のうちの少なくとも１つは、ＢＣＨ符号およびＲＳ（Reed-Solomon）符号のうちのいずれかである請求項１に記載の復号装置。
【請求項１５】
前記信頼性フラグは、前記シンドロームが０であるか０以外の値であるかを１または０の値で保持する請求項１に記載の復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
以下の実施形態は、一般的に、復号装置に関する。
【背景技術】
【０００２】
記憶装置では、一般に、記憶するデータを保護するために、符号化されたデータが記憶される。このため、記憶装置に記憶されたデータを読み出す際には、誤り訂正符号化されたデータに対する復号が行われる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許出願公開第２０１５／０３３３７７４号明細書
【特許文献２】国際特許出願公開第２００６／１３２３３１号
【特許文献３】特開２００９−２２５３２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、誤訂正による誤り訂正能力の低下を抑制することが可能な復号装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
実施形態によれば、２つ以上の成分符号を有する多次元の誤り訂正符号を復号する復号装置は、前記多次元の誤り訂正符号を格納する記憶部と、すくなくとも前記２つ以上の成分符号それぞれのシンドロームまたは前記シンドロームが０であるか０以外の値であるかを示す信頼性フラグを管理する付加情報記憶部と、前記記憶部に格納された前記多次元の誤り訂正符号に対して成分符号単位で復号処理を実行することで各成分符号のエラーベクタを検出する復号器と、前記付加情報記憶部に格納されている前記シンドロームまたは前記信頼性フラグに基づいて、前記復号器による前記エラーベクタの検出が誤検出であるか否かを判定する検出部とを備える。
【図面の簡単な説明】
【０００６】
【図１】図１は、第１の実施形態にかかるメモリシステム（半導体記憶装置）の概略構成例を示すブロック図である。
【図２】図２は、図１に示す符号化／復号部のより詳細なブロック構成例を示すブロック図である。
【図３】図３は、第１の実施形態において例示的に用いる多次元の誤り訂正符号（積符号）の概略構成例を示す図である。
【図４】図４は、第１の実施形態にかかる行方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図５】図５は、第１の実施形態にかかる列方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図６】図６は、第１の実施形態にかかる復号処理の概略動作例を示すフローチャートである。
【図７】図７は、第２の実施形態にかかるＣ２方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図８】図８は、第２の実施形態にかかるＣ１方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図９】図９は、第２の実施形態にかかる復号処理の概略動作例を示すフローチャートである。
【図１０】図１０は、第３の実施形態にかかるＣ２方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図１１】図１１は、第３の実施形態にかかるＣ１方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図１２】図１２は、第４の実施形態にかかるＣ２方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図１３】図１３は、第４の実施形態にかかるＣ１方向の成分符号に対する復号処理の流れの一例を示す模式図である。
【図１４】図１４は、第４の実施形態にかかる復号動作の一例を示すフローチャートである。
【図１５】図１５は、第５の実施形態にかかるリスト復号を採用した復号処理の概略動作例を示すフローチャートである。
【図１６】図１６は、図１５のステップＳ５０４およびＳ５１２で実行されるテストパターンを用いた復号処理の動作例を示すフローチャートである。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態にかかる復号装置、ならびに、この復号装置を備えたメモリコントローラ、メモリシステムおよびメモリコントローラの制御方法を詳細に説明する。なお、以下の実施形態により本発明が限定されるものではない。
【０００８】
記憶媒体から読み出されたデータにはビットエラーまたはシンボルエラー（以下、単にエラーという）が含まれることがある。そのため、このようなエラーを検出・訂正するために、読み出されたデータに対して誤り訂正が実行されるが、誤り訂正の際にエラーを誤って検出する誤検出が発生し、その誤検出に基づいてデータが訂正されてしまうと、データには読み出した際のエラーに加えて誤検出に基づくエラーが含まれることとなる。本説明では、誤検出に基づく誤り訂正によって内部メモリを書き変えることを、誤訂正と称する。このような誤訂正が発生すると、記憶媒体から読み出されたデータを誤り訂正することが不可能となる可能性がある。その場合、記憶媒体から正しいデータを取得できなくなる。
【０００９】
そこで、以下で例示する実施形態では、ユーザデータが複数の誤り訂正符号（以下、成分符号という）により二重以上に保護されている誤り訂正符号（以下、多次元の誤り訂正符号という）に対して復号を繰り返し実施する反復復号において、誤検出や誤訂正を適切に検出して対処することで、誤り訂正能力の低下を抑制することを可能にする。
【００１０】
（第１の実施形態）
図１は、第１の実施形態にかかるメモリシステム（記憶装置）の概略構成例を示すブロック図である。図１に示すように、メモリシステム１は、メモリコントローラ２と不揮発性メモリ３とを備える。メモリシステム１は、ホスト４と接続可能であり、図１ではホスト４と接続された状態が示されている。ホスト４は、例えば、パーソナルコンピュータ、携帯端末などの電子機器であってよい。
【００１１】
不揮発性メモリ３は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤ型フラッシュメモリ（以下、単にＮＡＮＤメモリという）である。以下の説明では、不揮発性メモリ３としてＮＡＮＤメモリが用いられた場合を例示するが、不揮発性メモリ３として３次元構造フラッシュメモリ、ＲｅＲＡＭ（Resistance Random Access Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）等のＮＡＮＤメモリ以外の半導体メモリを用いることも可能である。また、不揮発性メモリ３が半導体メモリであることは必須ではなく、半導体メモリ以外の種々の記憶媒体に対して本実施形態を適用することも可能である。
【００１２】
メモリシステム１は、メモリコントローラ２と不揮発性メモリ３とが１つのパッケージとして構成されるメモリカード等であってもよいし、ＳＳＤ（Solid State Drive）等であってもよい。
【００１３】
メモリコントローラ２は、ホスト４からの書込みコマンド（要求）に従って不揮発性メモリ３への書込みを制御する。また、ホスト４からの読み出しコマンドに従って不揮発性メモリ３からの読み出しを制御する。メモリコントローラ２は、ホストＩ／Ｆ（ホストインタフェース）２１、メモリＩ／Ｆ（メモリインタフェース）２２、制御部２３およびデータバッファ２５を備える。ホストＩ／Ｆ２１、メモリＩ／Ｆ２２、制御部２３およびデータバッファ２５は、内部バス２０で相互に接続されている。
【００１４】
ホストＩ／Ｆ２１は、ホスト４との間のインタフェース規格に従った処理を実施し、ホスト４から受信した命令、ユーザデータなどを内部バス２０に出力する。また、ホストＩ／Ｆ２１は、不揮発性メモリ３から読み出されたユーザデータ、制御部２３からの応答などをホスト４へ送信する。
【００１５】
メモリＩ／Ｆ２２は、制御部２３の指示に基づいて、不揮発性メモリ３への書込み処理を行う。また、メモリＩ／Ｆ２２は、制御部２３の指示に基づいて、不揮発性メモリ３からの読み出し処理を行う。
【００１６】
制御部２３は、メモリシステム１の各構成要素を統括的に制御する。制御部２３は、ホスト４からホストＩ／Ｆ２１経由で命令を受けた場合に、その命令に従った制御を行う。例えば、制御部２３は、ホスト４からの命令に従って、不揮発性メモリ３へのデータの書き込みをメモリＩ／Ｆ２２へ指示する。また、制御部２３は、ホスト４からの命令に従って、不揮発性メモリ３からのデータの読み出しをメモリＩ／Ｆ２２へ指示する。
【００１７】
また、制御部２３は、ホスト４から書込み要求を受信した場合、データバッファ２５に蓄積されるユーザデータに対して、不揮発性メモリ３上の格納領域（メモリ領域）を決定する。すなわち、制御部２３は、不揮発性メモリ３におけるユーザデータの書込み先を管理する。ホスト４から受信したユーザデータの論理アドレスと該ユーザデータが格納された不揮発性メモリ３上の格納領域を示す物理アドレスとの対応はアドレス変換テーブルとして格納される。
【００１８】
また、制御部２３は、ホスト４から読み出し要求を受信した場合、読み出し要求により指定された論理アドレスを上述のアドレス変換テーブルを用いて物理アドレスに変換し、該物理アドレスからの読み出しをメモリＩ／Ｆ２２へ指示する。
【００１９】
ＮＡＮＤメモリなどの不揮発性メモリ３では、一般に、ページと呼ばれるデータ単位で、書込みおよび読み出しが行われ、ブロックと呼ばれるデータ単位で消去が行われる。本実施形態では、この同一のワード線に接続される複数のメモリセルをメモリセルグループと呼ぶ。メモリセルがシングルレベルセル（ＳＬＣ）である場合は、１つのメモリセルグループが１ページに対応する。メモリセルがマルチレベルセル（ＭＬＣ）である場合は、１つのメモリセルグループが複数ページに対応する。また、各メモリセルはワード線に接続するとともにビット線にも接続される。したがって、各メモリセルは、ワード線を識別するアドレスとビット線を識別するアドレスとで識別することが可能である。
【００２０】
データバッファ２５は、メモリコントローラ２がホスト４から受信したユーザデータを不揮発性メモリ３へ記憶するまでに一時格納する。また、データバッファ２５は、不揮発性メモリ３から読み出したユーザデータをホスト４へ送信するまでに一時格納する。データバッファ２５には、例えば、ＳＲＡＭ（Static Random Access Memory）やＤＲＡＭ（Dynamic Random Access Memory）などの汎用メモリを用いることができる。
【００２１】
また、メモリＩ／Ｆ２２内には、符号化／復号部（復号装置）２４が設けられる。符号化／復号部２４は、不揮発性メモリ３への書込み対象であるユーザデータを符号化して符号語を生成する。また、符号化／復号部２４は、不揮発性メモリ３から読み出された受信語を復号してユーザデータを復元する。なお、符号化／復号部２４により符号化されるデータには、ユーザデータ以外にも、メモリコントローラ２内部で用いる制御データ等が含まれてもよい。以下の説明では、これらをまとめてユーザデータという。また、符号化／復号部２４は、メモリＩ／Ｆ２２内に限られず、その一部または全部がメモリＩ／Ｆ２２の外に設けられて内部バス２０に接続されてもよい。
【００２２】
図２に、図１に示す符号化／復号部２４のより詳細なブロック構成例を示す。図２に示すように、符号化／復号部２４は、符号化器２４１と、復号器２４２と、付加情報記憶部２４３と、検出部２４４と、内部メモリ２４５とを備える。
【００２３】
内部メモリ２４５は、たとえばＳＲＡＭなどで構成されたメモリ領域である。この内部メモリ２４５は、制御部２３から不揮発性メモリ３への書込みを指示されたユーザデータを符号化する際のワーキングメモリとして機能する。また、内部メモリ２４５は、不揮発性メモリ３から読み出された受信語を復号してユーザデータを復元する際のワーキングメモリとしても機能する。
【００２４】
不揮発性メモリ３へデータを書き込む際には、データバッファ２５に蓄積されているユーザデータの符号化が、制御部２３からメモリＩ／Ｆ２２へ指示される。その際、制御部２３は、不揮発性メモリ３内での符号語の格納場所（格納アドレス）を決定し、決定した格納場所への符号語の書込みもメモリＩ／Ｆ２２へ指示する。符号化器２４１は、メモリＩ／Ｆ２２へ入力された制御部２３からの指示に基づいて、データバッファ２５から内部メモリ２４５上に転送されたユーザデータを符号化して符号語を生成し、生成した符号語を指示された格納領域へ格納する。
【００２５】
ここで、符号化器２４１に採用される符号化方式としては、例えば、ＢＣＨ（Bose-Chandhuri-Hocquenghem）符号やＲＳ（リード・ソロモン）符号を用いた符号化方式を例示することができる。本実施形態では、符号化器２４１は、ユーザデータから多次元の誤り訂正符号（multi-dimensional error correction code）を符号語として生成する。多次元の誤り訂正符号とは、たとえば列方向の成分符号と行方向の成分符号との２次元の成分符号でユーザデータを二重に保護する積符号に代表されるような、２次元以上の成分符号でユーザデータの少なくとも一部を二重以上に保護する誤り訂正符号である。このような多次元の誤り訂正符号には、上述した積符号の他に、積符号を一般化した概念であるグラフ符号（Graph Codes）や、グラフ符号を更に一般化した概念である一般化ＬＤＰＣ符号（Generalized Low-Density Parity Check Codes）などが存在する。なお、本説明では、たとえば積符号における行方向や列方向など、各成分符号を構成するシンボルの配列方向をそれぞれ１つの“次元”と称している。また、以下の説明では、簡略化のため、多次元の誤り訂正符号として積符号を例示している。
【００２６】
図３は、本実施形態において例示的に用いる多次元の誤り訂正符号の概略構成例を示す図である。図３には、多次元の誤り訂正符号の一例として、符号長を１６シンボルとし、情報長（ユーザデータのデータ長）を４シンボルとしたＲＳ符号による２次元の誤り訂正符号である積符号３０が例示されている。この積符号３０は、たとえば、データシンボルｄ０〜ｄ８と、パリティシンボルｐ０〜ｐ６とから構成される。なお、本実施形態では、多次元の誤り訂正符号として２次元の誤り訂正符号である積符号３０を例示しているが、これに限定されるものではない。すなわち、上述したように、２次元以上の成分符号でユーザデータの少なくとも一部を二重以上に保護する２次元以上（多次元）の誤り訂正符号であれば、種々の誤り訂正符号を用いることが可能である。
【００２７】
図３に示すような符号構造を備える積符号３０では、データシンボルｄ０〜ｄ８およびパリティシンボルｐ０〜ｐ６が、８つの成分符号３０１〜３０４および３１１〜３１４によってそれぞれ二重に保護されている。たとえば、成分符号３０１は、データシンボルｄ０〜ｄ２を、パリティシンボルｐ０で符号化している。そこでデータシンボルｄ０に着目すると、このデータシンボルｄ０は、成分符号３０１と成分符号３１１とによって同時に二重に保護されている。同様に、データシンボルｄ０以外の各シンボルｄ１〜ｄ８についても行方向の成分符号３０１〜３０３と列方向の成分符号３１１〜３１３とによって二重保護されている。なお、図３では、パリティシンボルｐ０〜ｐ６もそれぞれ２重保護される構成をとっているが、符号構成によっては一重保護を含んでもかまわない。
【００２８】
ここで、本説明におけるシンボル（データシンボルおよびパリティシンボル）とは、情報の単位のことである。例えば二元ＢＣＨ符号のシンボルはビット（“０”か“１”かの二値情報）であり、ＲＳ符号のシンボルは一般の有限体（finite field）の元（element）である。また、誤り訂正符号の符号語は一般に、シンボルを並べたベクタである。したがって、多次元の誤り訂正符号をＢＣＨ符号とした場合、その成分符号の符号語（以下、成分符号語という）は、“０”および“１”の２値のビット情報が所定シンボル数分並べられた符号構造を有する。一方、多次元の誤り訂正符号をＲＳ符号とした場合、その成分符号語は、ガロア拡大体の元が所定シンボル数分並べられた符号構造を有する。
【００２９】
不揮発性メモリ３からデータを読み出す際には、制御部２３からメモリＩ／Ｆ２２へ、目的の符号語が格納されている格納場所からの読出し指示が、当該格納場所を指定するアドレスとともに入力される。メモリＩ／Ｆ２２は、制御部２３の指示に従って、不揮発性メモリ３の指定されたアドレスからの符号語の読み出しを開始するとともに、メモリＩ／Ｆ２２内の復号器２４２に対して、読み出された符号語（受信語）に対する復号処理の開始を指示する。その後、不揮発性メモリ３から復号対象の符号語が読み出されて内部メモリ２４５に蓄積されると、この内部メモリ２４５内のデータが成分符号語単位で復号器２４２に入力されて復号される。
【００３０】
復号器２４２による復号処理では、復号対象の成分符号語に含まれる誤りシンボルの位置および値が検出される。本説明では、復号処理によって検出された誤りシンボルの位置に“１”を格納し、その他の要素を０で表現した、要素数が成分符号長と同じベクタをエラーベクタとも称する。エラーベクタが検出された場合、復号器２４２は、エラーベクタが検出された成分符号に関し、この成分符号が復号に成功したこと、言い換えれば、シンドロームが０であることを、付加情報記憶部２４３に登録する。なお、付加情報の詳細については、後述において触れる。
【００３１】
検出部２４４は、復号器２４２による復号処理によってエラーベクタが見つかった場合、付加情報記憶部２４３に登録されている付加情報に基づいて、検出されたエラーベクタが誤検出であるか否かを判定する（第１の誤検出防止手段）。復号器２４２は、エラーベクタの検出が検出部２４４によって誤検出でないと判定された場合、内部メモリ２４５内の該当するシンボルの値を正しいと推定される値に書き換える書換え処理を実行する。一方、検出部２４４によって誤検出であると判定された場合、復号器２４２は、内部メモリ２４５の書換え処理を実行しない。
【００３２】
なお、復号器２４２が実行する復号処理には、硬判定復号と、軟判定復号とが含まれ得る。硬判定復号とは、硬判定値を入力として復号を実行し、その結果として硬判定値を出力する復号処理である。一方、軟判定復号とは、軟判定値を入力として復号を実行し、その結果として軟判定値を出力する復号処理である。
【００３３】
一般に、軟判定復号は、硬判定復号より誤り訂正能力は高いが処理時間が長いという特徴を持つ。そこで、たとえば復号器２４２は、まず、不揮発性メモリ３から硬判定値として読み出されて内部メモリ２４５に格納された受信語に対して硬判定復号を実行し、この硬判定復号により復号できなかった受信語を軟判定値として読み出して内部メモリ２４５に格納し、この内部メモリ２４５に格納された軟判定値の受信語に対して軟判定復号を実行するように構成されてもよい。ただし、このような構成に限られず、たとえば硬判定復号を省略して全ての受信語に軟判定復号を実行する構成など、種々変形することが可能である。
【００３４】
つぎに、本実施形態にかかる復号処理の流れについて、図面を用いて詳細に説明する。図４および図５は、本実施形態にかかる復号処理の流れを説明するための模式図であり、図４は、行方向の成分符号に対する復号処理の流れの一例を示し、図５は、図４に示す復号処理の後に実行される列方向の成分符号に対する復号処理の流れの一例を示している。なお、本説明では、復号対象の多次元の誤り訂正符号を図３に示す積符号３０をとする。ただし、以下の説明では、図３に示す積符号３０を、ユーザデータを含むブロックをｄ０〜ｄ８とし、パリティビットを含むブロックをｐ０〜ｐ６とし、各ブロックに複数のシンボルが含まれる符号構造を備えた２次元ＢＣＨブロック積符号に拡張した場合を例示する。また、図３では、積符号３０における行方向をＣ１方向（または次元）とし、列方向をＣ２方向（または次元）とする。さらに、以下の説明では、復号器２４２の最大訂正可能数ｔを２シンボルとした場合を例示する。
【００３５】
図４および図５に示すように、本実施形態では、積符号３０を構成する各成分符号に付与する付加情報として、信頼性フラグ４０１〜４０４および４１１〜４１４が設定されている。具体例を挙げると、Ｃ１方向の成分符号３０１に対しては、信頼性フラグ４０１が設定されている。また、Ｃ２方向の成分符号３１１に対しては、信頼性フラグ４１１が設定されている。これらのような信頼性フラグ４０１〜４０４および４１１〜４１４には、成分符号のシンドロームが０であることを“１”で示し、シンドロームが０以外であること、すなわち成分符号がエラーを含んでいることを“０”で示す２値フラグを用いることができる。ただし、このような、成分符号にエラーが含まれない可能性（以下、信頼性ともいう）を２段階で示す２値フラグに限定されず、３段階以上で示す情報を付加情報として用いることも可能である。または、信頼性フラグに代えて、シンドロームを付加情報として用いることも可能である。その場合、後述する説明において、信頼性フラグの代わりに、シンドロームが用いられることとなる。
【００３６】
本実施形態にかかる復号処理では、まず、不揮発性メモリ３から読み出されて内部メモリ２４５に蓄積された積符号３０の各成分符号３０１〜３０４および３１１〜３１４に対してシンドロームチェックを実施し、このシンドロームチェックの結果に基づいて、各成分符号３０１〜３０４および３１１〜３１４に対して付与されている信頼性フラグ４０１〜４０４および４１１〜４１４を更新する。
【００３７】
ただし、信頼性フラグ４０１〜４０４および４１１〜４１４を最初に更新するため動作は、各成分符号のシンドロームチェックに限られず、訂正数を１（＝ｔ−１）シンボルと制限した復号を実施し、その結果に基づいて信頼性フラグ４０１〜４０４および４１１〜４１４を更新する構成とすることも可能である。または、訂正数を（ｔ−１）とした反復復号（limited iterative decoding）を実施し、その結果に基づいて信頼性フラグ４０１〜４０４および４１１〜４１４を更新する構成とすることも可能である。
【００３８】
なお、最初に信頼性フラグを更新するための動作をシンドロームチェックではなく復号とした場合、その復号には、上述の訂正数が制限（ｔ−１）された反復復号のような、誤訂正の発生確率が比較的低い復号手法であれば、種々の復号手法を適用することが可能である。
【００３９】
ここで、反復復号とは、得られた受信語から通信路の信頼度を符号化の情報を利用して計算し、復号時にその信頼度の更新を繰り返すことによってその信頼性を高め、最終的に得られた信頼度に基づいて正しい符号語が得られたか否かの判定を行う復号手法であり、誤り特性の大幅な改善を図ることが可能な復号手法の１つである。ただし、本実施形態では、このような反復復号に限定されず、誤訂正の発生確率が比較的低い反復復号手法であれば、たとえば限界距離復号など、種々の復号手法を適用することが可能である。
【００４０】
最初に信頼性フラグを更新した後は、内部メモリ２４５に蓄積された積符号３０の復号において、復号器２４２は、各成分符号３０１〜３０４および３１１〜３１４に対し、たとえば最大訂正数を最大訂正可能数ｔ（＝２）シンボルとした反復復号を実行する。
【００４１】
最初に信頼性フラグを更新した後に積符号３０に対して実行される復号の過程をより具体的に説明すると、本実施形態では、まず、Ｃ１方向の成分符号３０１〜３０４が順次復号される。復号順序としては、たとえば先頭行である成分符号３０１から順にＣ２方向に沿って復号対象の成分符号を選択する方法など、種々の順序を適用することが可能である。
【００４２】
Ｃ１方向の成分符号３０１〜３０３に対する復号の結果、積符号３０にエラーベクタが検出されなければ、つづいてＣ２方向の成分符号３１１〜３１４に対する復号が実行される。一方、成分符号３０１〜３０４に対する復号により積符号３０にエラーベクタが検出された場合には、Ｃ２方向の成分符号３１１〜３１４のうちエラーベクタが示す誤りシンボルを含む成分符号の信頼性フラグが確認される。この確認したＣ２方向の成分符号に関する信頼性フラグが全て“０”を示していた場合、すなわち、確認した成分符号のシンドロームが全て“０以外“である場合、内部メモリ２４５内の積符号３０におけるエラーベクタに対応するシンボルの値が正しいと推定される値に書き換えられるとともに（書換え処理）、上記エラーベクタが示す誤りシンボルを含むＣ１方向の成分符号の信頼性フラグが書換え後の成分符号から計算されるシンドロームに基づいて更新される。その際、上記エラーベクタが示す誤りシンボルを含むＣ２方向の成分符号の信頼性フラグが、書換え後の成分符号から計算されるシンドロームに基づいて更新されてもよい。一方、上記において確認したＣ２方向の成分符号に関する信頼性フラグに“１”のものが含まれていた場合、すなわち、確認した成分符号のシンドロームに“０”のものが含まれていた場合、Ｃ１方向の成分符号３０１〜３０４に対する復号によるエラーベクタの検出は誤検出である可能性が高いと判定し、内部メモリ２４５に対する書換え処理を実行しない。
【００４３】
つづいて、Ｃ２方向の成分符号３１１〜３１４に対する復号では、Ｃ１方向の成分符号３０１〜３０４に対する復号と同様に、所定の復号順序に従って成分符号３１１〜３１４が順次復号される。ここで、成分符号３１１〜３１４に対する復号により積符号３０にエラーベクタが検出された場合には、Ｃ１方向の成分符号３０１〜３０４に対する復号の流れと同様に、Ｃ２方向の成分符号３１１〜３１４のうちエラーベクタが示す誤りシンボルを含む成分符号の信頼性フラグが確認され、信頼性フラグが全て“０”を示していた場合には、内部メモリ２４５に対する書換え処理が実行されるとともに、上記エラーベクタが示す誤りシンボルを含むＣ２方向の成分符号の信頼性フラグが更新される。その際、上記エラーベクタが示す誤りシンボルを含むＣ１方向の成分符号の信頼性フラグが、書換え後の成分符号から計算されるシンドロームに基づいて更新されてもよい。また、確認したＣ１方向の成分符号に関する信頼性フラグに“１”のものが含まれていた場合にも、Ｃ１方向の成分符号３０１〜３０４に対する復号の流れと同様に、この復号によるエラーベクタの検出は誤検出である可能性が高いと判定して、内部メモリ２４５に対する書換え処理を実行しない。なお、Ｃ２方向の成分符号３１１〜３１４に対する上記復号を実行した後は、反復復号処理の終了条件（打ち切り条件ともいう）を満たしているか否かが判定され、この条件を満たしている場合、復号処理を終了し、満たしていない場合、再度、Ｃ１方向の成分符号３０１〜３０４に対する復号が実行されてもよい。
【００４４】
このように本実施形態では、エラーベクタの検出が誤検出であるか否かを判定するために、「ある次元の成分符号を復号した結果、エラーベクタが検出された場合、当該エラーベクタが示すエラーを含む他の次元の成分符号の信頼性フラグに“１”のものが含まれていれば、前記エラーベクタの検出は誤検出であると判定し、前記エラーベクタを含む他の次元の成分符号の信頼性フラグが全て“０”を示していれば、前記エラーベクタの検出は誤検出ではないと判定する」というアルゴリズム（以下、第１のアルゴリズムという）を採用している。
【００４５】
上記復号の流れを図４および図５に示す具体例を用いて説明すると、図４に示す例では、Ｃ１方向の成分符号３０１〜３０４に対する復号の結果、成分符号３０４におけるパリティシンボルｐ１およびｐ６（図３参照）がそれぞれエラーｅ８およびｅ１６であると検出されている。なお、図４および図５では、それぞれのブロックに含まれるエラーが“ｅ”で示されている。
【００４６】
そこで、第１のアルゴリズムに従い、Ｃ２方向の成分符号３１１〜３１４のうち、エラーｅ８およびｅ１６に相当するパリティシンボルｐ１およびｐ６を含む成分符号３１４の信頼性フラグ４１４が確認される。信頼性フラグ４１４の値は“０”である。そのため、通常では、内部メモリ２４５内の積符号３０におけるエラーベクタに対応するシンボル（パリティシンボルｐ１およびｐ６）の値を正しいと推定される値に書き換える書換え処理が実行されるとともに、エラーｅ８およびｅ１６を含むＣ１方向の成分符号３０２および３０４の信頼性フラグ４０２および４０４が書換え後の成分符号３０２および３０４からそれぞれ計算されるシンドロームに基づいて更新される。その際、上記エラーｅ８およびｅ１６を含むＣ２方向の成分符号３１４の信頼性フラグ４１４が、書換え後の成分符号３１４から計算されるシンドロームに基づいて更新されてもよい。
【００４７】
ただし、本説明では、エラーベクタが、訂正不可能な、言い換えれば最大訂正可能数である２シンボルを超えたエラーを含むエラーベクタである。そのため、本例では、内部メモリ２４５内の積符号３０におけるエラーベクタｅ１６に対応するシンボル（パリティシンボルｐ６）に対する書換え処理が実行されない。
【００４８】
つづいて、Ｃ２方向の成分符号３１１〜３１４に対する復号では、Ｃ１方向の成分符号３０１〜３０４に対する復号と同様に、先頭列である成分符号３１１から順にＣ１方向に沿って成分符号単位の復号が実行される。その結果、図５に示す例では、たとえば成分符号３１４におけるパリティシンボルｐ１（図３参照）がエラーｅ８であるとして新たに検出される。したがって、Ｃ２方向の成分符号３１１〜３１４に対する復号によって検出されたエラーベクタには、エラーｅ８とエラーｅ１６とが含まれることとなる。
【００４９】
そこで、第１のアルゴリズムに従い、Ｃ１方向の成分符号３０１〜３０４のうち、エラーｅ８に相当するパリティシンボルｐ１を含む成分符号３０２の信頼性フラグ４０２と、エラーｅ１６に相当するパリティシンボルｐ６を含む成分符号３０４の信頼性フラグ４０４とが確認される。信頼性フラグ４０４は“０”であるが、上述したように、エラーｅ９が訂正不可能なエラーであるため、このエラーｅ１６に対応するパリティシンボルｐ６に対する書換え処理は実行されない。
【００５０】
一方、成分符号３０２に対する信頼性フラグ４０２の値は“１”である。これは、Ｃ２方向の成分符号３１１〜３１４に対する復号の結果、信頼性フラグ４０２によってエラーが存在しないと示されている領域にエラーｅ８が検出されたことを意味している。
【００５１】
そこで本実施形態では、第１のアルゴリズムに従い、エラーｅ８を含むエラーベクタの検出は誤検出であるとして、内部メモリ２４５に対する書換え処理を実行せずに、Ｃ２方向の成分符号３１１〜３１４に対する今回の復号を終了する。その後、反復復号処理の終了条件（打ち切り条件ともいう）を満たしているか否かが判定され、条件を満たしている場合、復号処理を終了し、満たしていない場合、再度、Ｃ１方向の成分符号３０１〜３０４に対する復号が実行される。
【００５２】
なお、エラーベクタの検出が誤検出であるか否かを判定するためのアルゴリズムとしては、上述した第１のアルゴリズムに限定されず、種々変形することが可能である。たとえば、「検出されたエラーベクタに含まれるエラーの数が最大訂正可能数ｔである場合には、当該エラーベクタの検出は誤検出である」と判定するアルゴリズムや、「１つの成分符号に関し、この成分符号の次元とは異なる次元の２つ以上の成分符号の信頼性フラグの値を“１”から“０”に更新する必要がある場合には、当該エラーベクタの検出は誤検出である」と判定するアルゴリズムなど、種々のアルゴリズムを第１のアルゴリズムとして採用することが可能である。
【００５３】
つづいて、本実施形態にかかる復号処理の全体的な動作フローについて、図面を用いて詳細に説明する。図６は、本実施形態にかかる復号処理の概略動作例を示すフローチャートである。なお、本説明では、復号器２４２の動作に着目する。また、本説明では、明確化のため、復号対象の多次元の誤り訂正符号を図３に示す積符号３０とした場合を例示する。さらに、図６に示す動作を実行するにあたって、内部メモリ２４５内には、不揮発性メモリ３から読み出された積符号３０が蓄積されているものとする。
【００５４】
図６に示すように、復号器２４２は、まず、内部メモリ２４５内に蓄積された積符号３０の各成分符号３０１〜３０４および３１１〜３１４に対してシンドロームチェックを行い（ステップＳ１０１）、このシンドロームチェックの結果に基づいて、付加情報記憶部２４３に格納されている各成分符号の信頼性フラグ（付加情報）をセット（更新）する（ステップＳ１０２）。
【００５５】
つぎに復号器２４２は、積符号３０を構成する２つの次元（Ｃ１方向およびＣ２方向）のうち第１の次元（これをＣ１方向とする）の成分符号３０１〜３０４に対し、成分符号単位で復号処理を実行する（ステップＳ１０３）。具体的には、復号器２４２は、上述したように、成分符号３０１〜３０４の中から復号対象とする成分符号を１つずつ順次選択し、選択した成分符号に対して最大訂正数を最大訂正可能数ｔ（たとえば２）とした反復復号を実行する。
【００５６】
つぎに復号器２４２は、ステップＳ１０３の復号処理においてエラーベクタが検出されたか否かを判定し（ステップＳ１０４）、エラーベクタが検出されていない場合（ステップＳ１０４；ＮＯ）、ステップＳ１０７へ進む。一方、エラーベクタが検出されていた場合（ステップＳ１０４；ＹＥＳ）、復号器２４２は、検出されたエラーベクタを検出部２４４に入力して、エラーベクタの検出が誤検出であるか否かを判定する（ステップＳ１０５）。
【００５７】
エラーベクタが入力された検出部２４４は、上述した第１のアルゴリズムに従い、復号器２４２によるエラーベクタの検出が誤検出であるか否かを判定する。具体的には、検出部２４４は、付加情報記憶部２４３を参照することで、第１の次元（Ｃ１方向）とは異なる次元である第２の次元（Ｃ２方向）の成分符号３１１〜３１４のうち、検出されたエラーベクタによって示されるエラーを含む成分符号に関する信頼性フラグの値を特定し、特定した信頼性フラグの値に基づいて、このエラーベクタの検出が誤検出であるか否かを判定する。また、検出部２４４は、この判定結果を復号器２４２へ返す。復号器２４２は、検出部２４４から入力された判定結果が誤検出であることを示していた場合（ステップＳ１０５；ＹＥＳ）、ステップＳ１０７へ進む。一方、判定結果が誤検出でないことを示していた場合（ステップＳ１０５；ＮＯ）、復号器２４２は、内部メモリ２４５内の積符号３０における検出されたエラーベクタに対応するシンボル、すなわち誤りと判定されたシンボルの値を正しいと推定される値に書き換える書換え処理を実行し（ステップＳ１０６）、ステップＳ１０７へ進む。
【００５８】
ステップＳ１０７では、ステップＳ１０３の復号処理後またはステップＳ１０６の書換え処理後の積符号３０から各成分符号３０１〜３０４のシンドロームを計算し、計算されたシンドロームに基づいて、付加情報記憶部２４３に登録されている第１の次元の成分符号３０１〜３０４についての信頼性フラグ４０１〜４０４を更新する（ステップＳ１０８）。この際、上述したように、復号器２４２は、書換え処理後の積符号３０から第２の次元の各成分符号３１１〜３１４のシンドロームを計算し、この計算されたシンドロームに基づいて、第２の次元の成分符号３１１〜３１４に関する信頼性フラグ４１１〜４１４を更新してもよい。
【００５９】
つぎに復号器２４２は、積符号３０を構成する２つの次元のうち他の第２の次元（これをＣ２方向とする）の成分符号３１１〜３１４に対して、上述においてステップＳ１０３〜Ｓ１０７で説明した動作と同様の動作を実行する。具体的には、まず、復号器２４２は、第２の次元の成分符号３１１〜３１４に対し、ステップＳ１０３で説明した動作と同様にして、成分符号単位で復号処理を実行する（ステップＳ１０８）。つづいて、復号器２４２は、ステップＳ１０８の復号処理においてエラーベクタが検出されたか否かを判定し（ステップＳ１０９）、エラーベクタが検出されていない場合（ステップＳ１０９；ＮＯ）はステップＳ１１２へ進み、エラーベクタが検出されていた場合（ステップＳ１０９；ＹＥＳ）は検出されたエラーベクタを検出部２４４に入力して、エラーベクタの検出が誤検出であるか否かを判定する（ステップＳ１１０）。つづいて復号器２４２は、検出部２４４から入力された判定結果が誤検出であることを示していた場合（ステップＳ１１０；ＹＥＳ）はステップＳ１１２へ進み、一方、判定結果が誤検出でないことを示していた場合（ステップＳ１１０；ＮＯ）は、内部メモリ２４５内の検出されたエラーベクタに対応するシンボルの値を正しいと推定される値に書き換える書換え処理を実行して（ステップＳ１１１）、ステップＳ１１２へ進む。ステップＳ１１２では、ステップＳ１０８の復号処理後またはステップＳ１１１の書換え処理後の積符号３０に基づいて、付加情報記憶部２４３に登録されている第２の次元の成分符号３１１〜３１４についての信頼性フラグ４１１〜４１４を更新する（ステップＳ１１２）。
【００６０】
その後、復号器２４２は、積符号３０における全ての誤りシンボルの訂正に成功したか否かを判定し（ステップＳ１１３）、訂正に成功している場合（ステップＳ１１３；ＹＥＳ）、制御部２３へ訂正成功を返す（ステップＳ１１６）とともに、復号処理により復元された内部メモリ２４５内のユーザデータをたとえばデータバッファ２５に格納する。なお、全ての誤りシンボルの訂正に成功したか否かは、たとえば積符号３０を構成する全ての成分符号３０１〜３０４および３１１〜３１４に対する信頼性フラグが“１”であるか否かや、全ての成分符号３０１〜３０４および３１１〜３１４のシンドロームが”“０”になったか否かなどに基づいて判定することができる。
【００６１】
一方、全ての誤りシンボルの訂正に成功していない場合（ステップＳ１１３；ＮＯ）、復号器２４２は、内部メモリ２４５にロードされた積符号３０に対する反復復号処理の終了条件を満たしているか否かを判定し（ステップＳ１１４）、満たしている場合（ステップＳ１１４；ＹＥＳ）、制御部２３へ復号失敗を返した後（ステップＳ１１５）、本動作を終了する。一方、終了条件が満たされていない場合（ステップＳ１１４；ＮＯ）、復号器２４２は、ステップＳ１０３へリターンし、再度、第１および第２の次元の成分符号３０１〜３０４および３１１〜３１４に対して以降の動作を実行する。なお、終了条件（打ち切り条件）とは、たとえば十分に尤もらしい復号語が得られたことや反復復号の繰返し回数が予め定めておいた所定回数に達したことなどとすることができる。
【００６２】
以上で説明したように、本実施形態では、多次元の誤り訂正符号を構成する成分符号に対し、この成分符号の信頼性（すなわち、エラーが存在しない可能性）が高いか低いかを示す付加情報として、信頼性フラグが付与される。多次元の誤り訂正符号に対して反復復号を実施する際には、各成分符号に対する復号において誤検出が発生したか否かを信頼性フラグを用いて検出し、誤検出が発生したと判定した場合には、この誤検出に基づく誤り訂正を回避する。それにより、誤訂正の発生を抑制することが可能となるため、誤り訂正能力の低下を抑制することが可能となる。
【００６３】
（第２の実施形態）
第１の実施形態では、復号により発生した誤検出を検出して誤訂正の発生を防止する場合を例示したが、以下に例示する第２の実施形態では、誤りであると検出されなかった誤検出によって誤訂正が発生した場合でも、誤訂正の発生を検出して適切に対処することで、誤り訂正能力の低下を抑制する。なお、以下の説明において、上述した実施形態と同様の構成については、同一の符号を付し、その重複する説明を省略する。
【００６４】
本実施形態にかかるメモリシステムの構成は、第１の実施形態において図１および図２を用いて説明した構成と同様であってよい。また、本実施形態において例示的に用いる多次元の誤り訂正符号としては、第１の実施形態と同様に、図３に示す積符号３０を用いるものとする。
【００６５】
つづいて本実施形態にかかる復号処理の流れについて、図面を用いて詳細に説明する。図７および図８は、本実施形態にかかる復号処理の流れを説明するための模式図であり、図７は、Ｃ２方向の成分符号に対する復号処理の流れの一例を示し、図８は、図７に示す復号処理の後に実行されるＣ１方向の成分符号に対する復号処理の流れの一例を示している。なお、第１の実施形態と同様に、復号器２４２の最大訂正可能数ｔを２シンボルとする。また、以下では、先に実行されたＣ１方向の成分符号３０１〜３０４に対する復号の説明を省略して、Ｃ２方向の成分符号３１１〜３１４に対する復号から説明する。
【００６６】
図７および図８に示すように、積符号３０を構成する各成分符号３０１〜３０４および３１１〜３１４には、付加情報として、信頼性フラグ４０１〜４０４および４１１〜４１４が設定されている。
【００６７】
図７に示す例では、Ｃ２方向の成分符号３１１〜３１４に対する復号の結果、成分符号３１４のパリティシンボルｐ０、ｐ１３およびｐ６にエラーＥ４、Ｅ８およびｅ１６が検出されている。これらのうち、エラーＥ４およびＥ８は誤検出であるが、誤検出と検出されずに誤り訂正が実行されてしまったものと仮定する。また、誤検出のエラーＥ４およびＥ８を誤訂正した結果、訂正後の成分符号３１４から計算されたシンドロームが“０”となり、それにより、成分符号３１４の信頼性フラグ４１４が“１”に更新されている。
【００６８】
つづいて、反復復号処理の終了条件（打ち切り条件）が満たされておらず、Ｃ１方向の成分符号３０１〜３０４に対する復号が再度実行されたものとする。その結果、図８に例示するように、図７に示すＣ２方向の復号によって誤訂正されたパリティシンボルｐ０およびｐ１にエラーｅ４およびｅ８が検出される。
【００６９】
このような例の場合、第１の実施形態のように、Ｃ１方向とは異なる次元であるＣ２方向の信頼性フラグを確認して誤検出であるか否かを判定する方法では、Ｃ２方向の成分符号３１４の信頼性フラグ４１４の値が“１”を示していることから、エラーｅ４およびｅ８を示すエラーベクタの検出は誤検出であると判定される。その結果、エラーｅ４およびｅ８に対する誤り訂正が実行されないこととなる。これは、内部メモリ２４５内の積符号３０に既に含まれてしまった誤訂正を検出して再訂正することができないことを示唆している。
【００７０】
そこで本実施形態では、たとえば第１の実施形態で採用した、エラーベクタの検出が誤検出であるか否かを判定するための第１のアルゴリズムに加え、内部メモリ２４５内の積符号３０に既に含まれてしまった誤訂正を検出するためのアルゴリズム（以下、第２のアルゴリズムという）を採用する。
【００７１】
第２のアルゴリズムとしては、「一つの成分符号に対して検出されたエラーベクタが別次元の複数個の成分符号に対して検出されたエラーベクタによって“否定”されたとき、前記一つの成分符号に対して検出されたエラーベクタに基づく誤り訂正は“誤訂正”であると判定する」というアルゴリズムを採用することができる。ここで、「ある次元のエラーベクタが他の次元のエラーベクタによって“否定”される」とは、前記ある次元のエラーベクタの検出を誤検出であったと判断することを意味している。したがって、第２のアルゴリズムは、「ある次元の成分符号に関して検出された複数のエラーを含むエラーベクタに基づいて書換え処理が実行されていた場合であって前記ある次元の成分符号の信頼性フラグが“１”である場合、前記ある次元とは異なる次元の成分符号に対する復号によって前記書換え処理の前の値に書き戻されるシンボルの数が所定数（たとえば２以上の整数）以上であれば、前記書換え処理は誤訂正であると判定し、前記書換え処理の前の値に書き戻されるシンボルの数が所定数未満であれば、前記書換え処理は誤訂正であると判定する」と言い換えることも可能である。
【００７２】
より具体的には、第２のアルゴリズムとして、「ある次元の成分符号に関してエラーベクタが検出された場合であって当該成分符号の信頼性フラグが“１”を示している場合、前記エラーベクタに含まれるエラーをそれぞれ含む１つ以上の他の次元の成分符号の信頼性フラグのうち“０”を示しているものの数が第１の所定数以上である場合には、前記エラーベクタの検出は誤検出ではないと判定し、前記第１の所定数未満であれば、前記エラーベクタの検出は誤検出であると判定する」というアルゴリズムなどを採用することができる。
【００７３】
または、「ある次元の成分符号に関してエラーベクタが検出された場合であって当該成分符号の信頼性フラグが“１”を示している場合、前記エラーベクタに含まれるエラーをそれぞれ含む１つ以上の他の次元の成分符号の信頼性フラグのうち、“１”を示しているものの数に（前記ある次元の成分符号の信頼性フラグの分である）１を加えた数と、“０”を示しているものの数とで大小関係を特定し（多数決）、“１”を示している信頼性フラグの数が過半数であれば、前記エラーベクタの検出は誤検出であると判定し、“１”を示している信頼性フラグの数と“０”を示している信頼性フラグの数とが同数、もしくは、“０”を示している信頼性フラグが過半数であれば、前記エラーベクタの検出は誤検出ではないと判定する」というアルゴリズムを第２のアルゴリズムとして採用することもできる。
【００７４】
ただし、上述の具体例における前者の第２のアルゴリズムでは、第１の所定数を１とすると、「前記エラーベクタに含まれるエラーをそれぞれ含む１つ以上の他の次元の成分符号の信頼性フラグのうち“０”を示しているものの数」が１である場合も「前記１つ以上エラーベクタの検出は誤検出ではない」と判定される。そこで、前者の第２のアルゴリズムでは、第１の所定数を２以上に制限してもよい。また、前者の第２のアルゴリズムに第１の所定数を１とする場合も含める場合には、前者の第２のアルゴリズムに加え、「ある次元の成分符号に関してエラーベクタが検出された場合であって当該成分符号の信頼性フラグが“１”を示している場合、前記エラーベクタに含まれるエラーをそれぞれ含む１つ以上の他の次元の成分符号の信頼性フラグのうち“０”を示しているものの数が１であって前記検出されたエラーベクタに含まれるエラーの数が最大訂正可能数であれば、前記エラーベクタの検出は誤検出ではないと判定し、前記エラーベクタに含まれるエラーをそれぞれ含む１つ以上の他の次元の成分符号の信頼性フラグのうち“０”を示しているものの数が０であるか、もしくは、前記最大訂正可能数未満であれば、前記エラーベクタの検出は誤検出であると判定する」というアルゴリズムとすることも可能である。
【００７５】
以上のような第２のアルゴリズムを採用することで、現在実行している復号（今回の復号ともいう）によって発見されたエラーベクタが、誤検出されたエラーベクタであるか、以前の復号において誤訂正されることによって発生したエラーベクタである（すなわち、今回の復号では誤検出ではない）かを的確に判定して対処することが可能となるため、誤り訂正能力の低下をより抑制することが可能となる。なお、第２のアルゴリズムによれば、「エラーベクタの検出は誤検出である」は「復号対象の成分符号に対して以前の復号においてした書換え処理は誤訂正ではない」と同義であり、「エラーベクタの検出は誤検出ではない」は「復号対象の成分符号に対して以前の復号においてした書換え処理は誤訂正である」と同義である。
【００７６】
上述した第２のアルゴリズムを図８に示す例に適用する。その結果、Ｃ１方向またはＣ２方向に対する反復復号のある段階でＣ２方向の成分符号３１４に対する復号によってエラーｅ４およびｅ８を含むエラーベクタが誤って検出されたとする。ここで、エラーｅ４およびｅ８を含むＣ１方向の成分符号３０１および３０２の信頼性フラグ４０１および４０２が“０”である。そのため、第１のアルゴリズムでは、これらのエラーｅ４およびｅ８を含むエラーベクタを誤訂正とは検出できず、その結果、内部メモリ２４５内の積符号３０がこのエラーベクタに基づいて書き換えられる。
【００７７】
その後、Ｃ２方向の成分符号の復号が終了すると、Ｃ１方向の成分符号の復号が再び実行される。このとき、成分符号３０１の復号によってエラーｅ４を含むエラーベクタが検出され、また、成分符号３０２の復号によってエラーｅ８を含むエラーベクタが検出されたとする。ここで、エラーｅ４およびｅ８を含むＣ２方向の成分符号３１４の信頼性フラグ４１４は“１”であるため、第１のアルゴリズムでは、これらのエラーベクタは“誤検出”と判断される。そこで本実施形態では、上述した第２のアルゴリズムに基づくことで、成分符号３１４に対する復号によって見つかったエラーベクタを、成分符号３０１および３０２の２つのエラーベクタが“否定”しているとし、成分符号３１４に対する復号で見つかったエラーベクタは“誤訂正”であったと判断する。
【００７８】
このように、図７および図８に示す例では、第２のアルゴリズムに基づくことで、先のＣ１方向に対する復号において成分符号３０１および３０２に対して見つかったエラーベクタに基づく誤り訂正は誤訂正であると判断されるため、今回のＣ２方向に対する復号において成分符号３１４に対して見つかったエラーベクタに基づいて内部メモリ２４５内の積符号３０が書き換えられるとともに、書き換え後の成分符号３０１および３０２から計算されるシンドロームに基づいて、信頼性フラグ４０１および４０２が“１”に更新される。また、誤訂正と判断されたシンボルを含む成分符号３１４については、その信頼性フラグ４１４が“０”に更新される。その際、この成分符号３１４に対する付加情報として、過去に誤訂正をされたか否かを示す誤訂正フラグを別途設け、この誤訂正フラグを、成分符号３１４が過去に誤訂正されたことを示す値に更新しておいてもよい。なお、誤訂正フラグに関する詳細については、後述する第4の実施形態において触れる。
【００７９】
なお、誤訂正による書換え前のパリティシンボルｐ０およびｐ１の値の情報、または、以前の復号においてパリティシンボルｐ０およびｐ１がどのように書き換えられたかを示す情報が存在する場合には、その情報に基づいて、パリティシンボルｐ０およびｐ１の値を書き換える書換え処理（ロールバック処理、差戻し処理または再書換え処理ともいう）が実行されてもよい。
【００８０】
また、内部メモリ２４５内の積符号３０に既に含まれてしまった誤訂正を検出するためのアルゴリズムとしては、上述した第２のアルゴリズムに限定されず、種々変形することが可能である。たとえば、各成分符号に関して誤り訂正したシンボルの数をカウントしておき、このカウント値に基づいて、「誤り訂正したシンボルの数が第２の所定数以上である成分符号については、当該成分符号についてされた誤り訂正は誤訂正であると判定し、前記第２の所定数未満である成分符号については、当該成分符号についてされた誤り訂正は誤訂正ではないと判定する」というアルゴリズムなど、種々のアルゴリズムを第２のアルゴリズムとして採用することが可能である。
【００８１】
つづいて、本実施形態にかかる復号処理の全体的な動作フローについて、図面を用いて詳細に説明する。なお、以下の説明では、第１の実施形態において図６を用いて説明した動作と同様の動作については、それを引用することで、その詳細な説明を省略する。
【００８２】
図９は、本実施形態にかかる復号処理の概略動作例を示すフローチャートである。なお、本説明では、復号器２４２の動作に着目する。また、本説明では、明確化のため、復号対象の多次元の誤り訂正符号を図３に示す積符号３０とした場合を例示する。さらに、図９に示す動作を実行するにあたって、内部メモリ２４５内には、不揮発性メモリ３から読み出された積符号３０が蓄積されているものとする。
【００８３】
図９に示す動作例と図６に示す動作例とを比較すると明らかなように、本実施形態にかかる復号処理の主要な流れは、第１の実施形態にかかる復号処理の流れと同様であってよい。ただし、本実施形態では、図９のステップＳ１０５（図６のステップＳ１０５に相当）において、検出部２４４から入力された判定結果が誤検出であることを示していた場合（ステップＳ１０５；ＹＥＳ）、復号器２４２は、内部メモリ２４５内に格納されている符号語（積符号３０）に誤訂正されたシンボルが含まれているか否かを判定する（ステップＳ２０１）。具体的には、ステップＳ１０５においてエラーベクタが入力された検出部２４４が、上述において例示した第２のアルゴリズムに従い、検出されたエラーベクタが内部メモリ２４５内の積符号３０に既に含まれてしまった誤訂正によるものであるか否かを判定し、その判定結果を復号器２４２へ返す。
【００８４】
復号器２４２は、検出部２４４から入力された判定結果が誤訂正によるものであることを示していた場合（ステップＳ２０１；ＹＥＳ）、ステップＳ１０６へ進み、内部メモリ２４５内の積符号３０における検出されたエラーベクタに対応するシンボル、すなわち誤りと判定されたシンボルの値を正しいと推定される値、すなわち誤り訂正（誤訂正）前の値に書き換える書換え処理を実行し（ステップＳ１０６）、ステップＳ１０７へ進む。一方、検出部２４４から入力された判定結果が誤訂正によるものではない、すなわち今回のエラーベクタの検出が誤検出であることを示していた場合（ステップＳ２０１；ＮＯ）、復号器２４２は、そのままステップＳ１０７へ進む。
【００８５】
また、本実施形態では、図９のステップＳ１１０（図６のステップＳ１１０に相当）において、検出部２４４から入力された判定結果が誤検出であることを示していた場合（ステップＳ１１０；ＹＥＳ）も同様に、検出部２４４において第２のアルゴリズムに従って判定された誤訂正によるものであるか否かの判定結果が復号器２４２に入力され、復号器２４２がこの判定結果に基づいて内部メモリ２４５内に格納されている符号語（積符号３０）に誤訂正されたシンボルが含まれているか否かを判定する（ステップＳ２０２）。この判定の結果、検出部２４４から入力された判定結果が誤訂正によるものであることを示していた場合（ステップＳ２０２；ＹＥＳ）には、復号器２４２は、ステップＳ１１１へ進んで書換え処理を実行し（ステップＳ１１１）、その後、ステップＳ１１２へ進む。一方、検出部２４４から入力された判定結果が誤訂正によるものではない、すなわち今回のエラーベクタの検出が誤検出であることを示していた場合（ステップＳ２０２；ＮＯ）には、復号器２４２は、そのままステップＳ１１２へ進み、以降、第１の実施形態において図６のステップＳ１１２〜Ｓ１１６を用いて説明した動作と同様の動作を実行する。
【００８６】
以上で説明したように、本実施形態では、付加情報として用いた信頼性フラグを利用して、内部メモリ２４５内の多次元の誤り訂正符号（積符号３０）に既に組み込まれた誤訂正を検出し、誤訂正が検出されたと判定した場合には、この誤訂正を解消する書換え処理を実行する。それにより、誤訂正が発生した場合でもこれを解消することが可能となるため、誤り訂正能力の低下をより抑制することが可能となる。なお、その他の構成、動作および効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【００８７】
（第３の実施形態）
第２の実施形態では、内部メモリ２４５内の多次元の誤り訂正符号（積符号３０）に既に組み込まれた誤訂正を検出するための情報として信頼性フラグを用いる場合を例示した。一方、第３の実施形態では、内部メモリ２４５内の多次元の誤り訂正符号（積符号３０）に既に組み込まれた誤訂正をより正確に検出する方法について、具体例を挙げて説明する。なお、以下の説明において、上述した実施形態と同様の構成については、同一の符号を付し、その重複する説明を省略する。
【００８８】
本実施形態にかかるメモリシステム（半導体記憶装置）の構成は、上述の実施形態と同様に、第１の実施形態において図１および図２を用いて説明した構成と同様であってよい。また、本実施形態において例示的に用いる多次元の誤り訂正符号としては、上述の実施形態と同様に、第１の実施形態において図３に示す積符号３０を用いるものとする。
【００８９】
つづいて本実施形態にかかる復号処理の流れについて、図面を用いて詳細に説明する。図１０および図１１は、本実施形態にかかる復号処理の流れを説明するための模式図であり、図１０は、Ｃ２方向の成分符号に対する復号処理の流れの一例を示し、図１１は、図１０に示す復号処理の後に実行されるＣ１方向の成分符号に対する復号処理の流れの一例を示している。なお、第１の実施形態と同様に、復号器２４２の最大訂正可能数ｔを２シンボルとする。また、以下では、先に実行されたＣ１方向の成分符号３０１〜３０４に対する復号を省略して、Ｃ２方向の成分符号３１１〜３１４に対する復号から説明する。
【００９０】
図１０および図１１に示すように、積符号３０を構成する各成分符号３０１〜３０４および３１１〜３１４には、付加情報として、信頼性フラグ４０１〜４０４および４１１〜４１４の他に、訂正シンボル数５０１〜５０４および５１１〜５１４が設定されている。
【００９１】
訂正シンボル数とは、それぞれに対応付けられた成分符号に対して実行された書換え処理（誤り訂正処理）により書き換えられたシンボルの累積数である。なお、この訂正シンボル数には、誤訂正と判定された結果、不揮発性メモリ３から読み出された際の値に書き戻されたシンボルの数が含まれていてもよいし、含まれていなくてもよい。
【００９２】
このような訂正シンボル数を内部メモリ２４５内の多次元の誤り訂正符号（積符号３０）に既に組み込まれた誤訂正を検出するための情報として用いる場合、既に組み込まれた誤訂正を検出するためのアルゴリズムには、第２の実施形態における第２のアルゴリズムに加えて、以下のような第３のアルゴリズムを採用することができる。すなわち、「第２のアルゴリズムによって後に誤検出と判定されたエラーベクタに基づいて書き換えられた成分符号について、前記エラーベクタに含まれるエラーの数が第３の所定数以上であった場合、前記エラーベクタの検出は誤検出であると判定し、第３の所定数未満である場合には、前記エラーベクタの検出は誤検出ではないと判定する」というアルゴリズムを第３のアルゴリズムとして採用することが可能である。
【００９３】
この第３のアルゴリズムにおける第３の所定数には、たとえば復号器２４２による復号の最大訂正可能数ｔ（＝２）を用いることができる。これは、最大訂正可能数ｔ以上のエラーベクタが検出された場合、このエラーベクタの検出が誤検出である可能性が高いためである。このように、各成分符号の訂正シンボル数と誤訂正の発生とには、相関関係が存在する。そこで、第３の所定数を最大訂正可能数ｔとして、最大訂正可能数ｔ以上のエラーベクタの検出に基づいて実行された誤り訂正（書換え処理）によって書き換えられたシンボルに再度エラーベクタが検出された場合には先の誤り訂正が誤訂正であると判定されるように第３のアルゴリズムを構成することで、より正確な誤訂正の検出が可能となる。ただし、第３の所定数は最大訂正可能数ｔに限定されず、多次元の誤り訂正符号の符号構造に応じて適宜設定することが可能である。
【００９４】
このような第３のアルゴリズムは、第２のアルゴリズムと同様に、たとえば図９のステップＳ２０１およびＳ２０２において、エラーベクタが入力された検出部２４４が、この検出されたエラーベクタが内部メモリ２４５内の積符号３０に既に含まれてしまった誤訂正によるものであるか否かを判定する際に使用される。本実施形態にかかる復号処理の他の動作は、たとえば第２の実施形態において図９を用いて説明した動作と同様であってよい。
【００９５】
以上で説明したように、本実施形態では、内部メモリ２４５内の積符号３０に既に含まれてしまった誤訂正を検出するための判定材料となる付加情報として、各成分符号に対して実行された書換え処理（誤り訂正処理）により書き換えられたシンボルの数を示す訂正シンボル数を用いている。上述したように、各成分符号の訂正シンボル数と誤訂正とには相関関係が存在することから、この訂正シンボル数を誤訂正を検出するための判定材料として用いることで、より正確な誤訂正の検出が可能となる。その結果、誤り訂正能力の低下をより抑制することが可能となる。なお、その他の構成、動作および効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【００９６】
（第４の実施形態）
つぎに、第４の実施形態について、図面を用いて詳細に説明する。第４の実施形態では、たとえば上述した第２または第３の実施形態において誤訂正が検出された成分符号が存在する場合、以降の反復復号処理においてはこの成分符号に対する復号処理をスキップすることで、同じ誤訂正が繰り返し発生することを防止（再発防止）する。なお、以下の説明において、上述した実施形態と同様の構成については、同一の符号を付し、その重複する説明を省略する。
【００９７】
本実施形態にかかるメモリシステム（半導体記憶装置）の構成は、上述の実施形態と同様に、第１の実施形態において図１および図２を用いて説明した構成と同様であってよい。また、本実施形態において例示的に用いる多次元の誤り訂正符号としては、上述の実施形態と同様に、図３に示す積符号３０を用いるものとする。
【００９８】
つづいて本実施形態にかかる復号処理の流れについて、図面を用いて詳細に説明する。図１２および図１３は、本実施形態にかかる復号処理の流れを説明するための模式図であり、図１２は、Ｃ２方向の成分符号に対する復号処理の流れの一例を示し、図１３は、図１２に示す復号処理の後に実行されるＣ１方向の成分符号に対する復号処理の流れの一例を示している。なお、第２の実施形態と同様に、復号器２４２の最大訂正可能数ｔを２シンボルとする。また、以下では、先に実行されたＣ１方向の成分符号３０１〜３０４に対する復号を省略して、Ｃ２方向の成分符号３１１〜３１４に対する復号から説明する。
【００９９】
図１２および図１３に示すように、積符号３０を構成する各成分符号３０１〜３０４および３１１〜３１４には、付加情報として、信頼性フラグ４０１〜４０４および４１１〜４１４の他に、誤訂正フラグ６０１〜６０４および６１１〜６１４が設定されている。
【０１００】
誤訂正フラグとは、それぞれに対応付けられた成分符号に対して過去に誤訂正をされたか否か、言い換えれば、それぞれに対応付けられた成分符号に対する以前の復号処理において誤訂正が発生したと判定されたか否かを示す付加情報である。この誤訂正フラグは、たとえば以前の復号処理において誤訂正が発生したことを“１”で示し、誤訂正が発生していないことを“０”で示す２値フラグを用いることができる。
【０１０１】
このような誤訂正フラグを用いて誤訂正の再発を防止するアルゴリズムとしては、たとえば、「誤訂正フラグが“１”である成分符号に関しては、復号処理をスキップする」アルゴリズム（これを第４のアルゴリズムとする）を採用することが可能である。
【０１０２】
つづいて、本実施形態にかかる復号処理の全体的な動作フローについて、図面を用いて詳細に説明する。なお、以下の説明では、第２の実施形態において図９を用いて説明した動作と同様の動作については、それを引用することで、その詳細な説明を省略する。
【０１０３】
本実施形態にかかる復号処理の全体的な動作フローは、たとえば上述の実施形態において図６または図９を用いて説明した動作フローと同様であってよい。ただし、本実施形態では、図６または図９のステップＳ１０３およびＳ１０８に示す復号動作が、図１４に例示される動作となる。
【０１０４】
図１４に示すように、本実施形態では、第１の次元（Ｃ１方向）または第２の次元（Ｃ２方向）の成分符号に対して成分符号単位で復号処理を実行するに際し、未選択の成分符号を順次選択する（ステップＳ４０１）。なお、復号順序としては、上述したように、たとえば先頭行である成分符号３０１／３１１から順にＣ２／Ｃ１方向に沿って復号対象の成分符号を選択する方法など、種々の順序を適用することが可能である。
【０１０５】
つぎに、復号器２４２は、選択した成分符号に関して過去に誤訂正がされたか否かを、検出部２４４を用いて判定する（ステップＳ４０２）。具体的には、復号器２４２は、検出部２４４へ選択中の成分符号を特定する情報を入力する。これに対し、検出部２４４は、選択中の成分符号に付与されている誤訂正フラグを参照することで、当該成分符号に対して過去に誤訂正がされたか否かを判定し、この判定結果を復号器２４２へ返す。
【０１０６】
選択した成分符号に関して過去に誤訂正がされていた場合（ステップＳ４０２；ＹＥＳ）、復号器２４２は、選択中の成分符号に対する復号処理をスキップし、ステップＳ４０６へ進む。一方、選択した成分符号に関して過去に誤訂正がされていない場合（ステップＳ４０２；ＮＯ）、復号器２４２は、選択した成分符号に対して反復復号を実行する（ステップＳ４０３）。つづいて、復号器２４２は、この復号に成功した場合（ステップＳ４０４；ＹＥＳ）、復号結果を所定のメモリ（たとえば内部メモリ２４５の一部）に蓄積し（ステップＳ４０５）、ステップＳ４０６へ進む。一方、復号に成功しなかった場合（ステップＳ４０４；ＮＯ）、復号器２４２は、復号結果を保存せずにステップＳ４０６へ進む。
【０１０７】
ステップＳ４０６では、復号器２４２は、対象の次元（第１の次元（Ｃ１方向）または第２の次元（Ｃ２方向））において未選択の成分符号が存在するか否かを判定し、未選択の成分符号が存在する場合（ステップＳ４０６；ＹＥＳ）、ステップＳ４０１へリターンして次の成分符号を選択し、以降の動作を実行する。一方、全ての成分符号を選択済みである場合（ステップＳ４０６；ＮＯ）、復号器２４２は、図６または図９の動作へリターンする。
【０１０８】
なお、本実施形態にかかる誤訂正フラグは、反復復号の過程でリセットされてもよい。すなわち、図６または図９および図１４に示す動作を実行する過程で復号処理の反復回数が所定回数に達した場合、誤訂正フラグをリセットした上で、その後の復号処理を継続するように構成することも可能である。なお、誤訂正フラグのリセット可否を判定するための所定回数は、たとえば同じ誤訂正が行われる可能性がある程度低くなったことを期待できる反復回数など、任意の回数に設定されてよい。
【０１０９】
以上で説明したように、本実施形態では、一度誤訂正が発生した成分符号に関しては、以降の反復復号処理においてこの成分符号に対する復号処理がスキップされる。これにより、本実施形態では、同じ誤訂正が繰り返し発生することが防止（再発防止）できるため、誤り訂正能力の低下をより抑制することが可能となる。なお、その他の構成、動作および効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【０１１０】
（第５の実施形態）
つぎに、第５の実施形態について、図面を用いて詳細に説明する。第５の実施形態では、たとえば上述した実施形態において復号に成功しなかった成分符号に対し、リスト復号と呼ばれる手法を用いて再度復号を実行することで、誤り訂正能力の向上を図る。なお、以下の説明において、上述した実施形態と同様の構成については、同一の符号を付し、その重複する説明を省略する。
【０１１１】
本実施形態にかかるメモリシステム（半導体記憶装置）の構成は、上述の実施形態と同様に、第１の実施形態において図１および図２を用いて説明した構成と同様であってよい。また、本実施形態において例示的に用いる多次元の誤り訂正符号としては、上述の実施形態と同様に、図３に示す積符号３０を用いるものとする。
【０１１２】
ここでリスト復号とは、ある受信語から１つ以上のシンボルの値を反転（フリップ）させた符号語を複数パターン生成し、生成した複数パターンの符号語それぞれに対して復号処理を実行し、その結果、復号に成功するものがあった場合には、成功した復号により得られた復号語の中から最も尤もらしいと推定される復号語を発見する復号手法である。そこで本実施形態では、リスト復号を使った硬判定復号において、この尤もらしいと推定する方法の一つとして、上述した第１の実施形態または第２の実施形態を用いる。
【０１１３】
受信語中のいずれのシンボルの値を反転させるかは、たとえばテストパターンと呼ばれる仮説によって管理される。このテストパターンとは、受信語中のエラー位置に関する仮説であり、受信語における反転対象とする１つ以上のシンボルの位置を特定するための情報である。たとえば受信語における先頭シンボルが誤りシンボルであると仮定するテストパターンには、この先頭シンボルを特定するための情報が含まれている。同様に、たとえば受信語における先頭シンボルと２番目のシンボルとが誤りシンボルであると仮定するテストパターンには、これら先頭シンボルと２番目のシンボルとを特定するための情報が含まれている。
【０１１４】
そこでリスト復号では、仮定する誤りシンボルの位置のパターン数と同数のテストパターンが用いられる。ただし、仮定する誤りシンボルの数が大きすぎると、使用するテストパターンの数が膨大な数となってしまう。そのため、仮定する誤りシンボルの数は、たとえば受信語の符号構造やエラー傾向に応じて適宜設定されることが好ましい。
【０１１５】
本実施形態にかかるリスト復号を採用した復号処理は、たとえば上述した実施形態において図６または図９を用いて説明した復号処理の動作におけるステップＳ１１５の代わりに実行される。そこで本説明では、図９に示す復号処理をベースとし、その動作におけるステップＳ１１５の代わりに実行されるリスト復号を採用した復号処理について、例を挙げて説明する。
【０１１６】
図１５は、本実施形態にかかるリスト復号を採用した復号処理の概略動作例を示すフローチャートである。図１５に示すように、たとえば図９のステップＳ１１３において積符号３０における全ての誤りシンボルの訂正に成功していないと判定され（ステップＳ１１３；ＮＯ）、さらに、内部メモリ２４５にロードされた積符号３０に対する反復復号処理の終了条件を満たしていると判定された場合（ステップＳ１１４；ＹＥＳ）、復号器２４２は、まず、たとえば内部メモリ２４５にロードされた積符号３０における第１の次元（Ｃ１方向）の成分符号３０１〜３０４のうちから、信頼性フラグが“１”でない、すなわち未訂正の誤りシンボルを含む成分符号を全て抽出する（ステップＳ５０２）。つづいて、復号器２４２は、ステップＳ５０２において未訂正の誤りシンボルを含む成分符号が抽出されたか否かを判定し（ステップＳ５０３）、抽出されなかった場合（ステップＳ５０３；ＹＥＳ）、ステップＳ５１０へ進む。一方、未訂正の誤りシンボルを含む成分符号が抽出された場合（ステップＳ５０３；ＮＯ）、復号器２４２は、抽出された成分符号に対して、テストパターンを用いたリスト復号を実行する（ステップＳ５０４）。テストパターンを用いたリスト復号の動作例については、後述において図１６を用いて説明する。
【０１１７】
つぎに復号器２４２は、ステップＳ５０４のリスト復号に成功したか否かを判定し（ステップＳ５０５）、成功しなかった場合（ステップＳ５０５；ＮＯ）、ステップＳ５０９へ進む。一方、リスト復号に成功した場合（ステップＳ５０５；ＹＥＳ）、復号器２４２は、内部メモリ２４５内の積符号３０において、検出されたエラーベクタによってエラーと示されているシンボルの値と、ステップＳ５０４のリスト復号において尤もらしい復号語を生成する際に使用したテストパターンにおいて仮定された誤りシンボルに対応するシンボルの値とを、正しいと推定される値に書き換える書換え処理を実行し（ステップＳ５０８）、ステップＳ５０９へ進む。
【０１１８】
ステップＳ５０９では、ステップＳ５０４のリスト復号後またはステップＳ５０８の書換え処理後の積符号３０から各成分符号３０１〜３０４のシンドロームを計算し、計算されたシンドロームに基づいて、付加情報記憶部２４３に登録されている第１の次元の成分符号３０１〜３０４についての信頼性フラグ４０１〜４０４を更新する。この際、上述したように、復号器２４２は、書換え処理後の積符号３０から第２の次元の各成分符号３１１〜３１４のシンドロームを計算し、この計算されたシンドロームに基づいて、第２の次元の成分符号３１１〜３１４に関する信頼性フラグ４１１〜４１４を更新してもよい。
【０１１９】
つぎに復号器２４２は、第２の次元（Ｃ２方向）の成分符号３１１〜３１４に対して、上述においてステップＳ５０２〜Ｓ５０９で説明した動作と同様の動作（図１５のステップＳ５１０〜Ｓ５１７）を実行することで、内部メモリ２４５内の積符号３０を必要に応じて書き換えるとともに、書き換え後の積符号３０から計算される各成分符号のシンドロームに基づいて、第２の次元の成分符号３１１〜３１４に関する信頼性フラグ４１１〜４１４を更新する。
【０１２０】
その後、復号器２４２は、図９のステップＳ１１３〜Ｓ１１４を用いて説明した動作と同様の動作（図１５のステップＳ５１８〜Ｓ５１９）を実行することで、積符号３０における全ての誤りシンボルの訂正に成功したか否かを判定し（ステップＳ５１８）、訂正に成功している場合（ステップＳ５１８；ＹＥＳ）、制御部２３へ訂正成功を返す（ステップＳ５２０）とともに、復号処理により復元された内部メモリ２４５内のユーザデータをたとえばデータバッファ２５に格納する。一方、全ての誤りシンボルの訂正に成功していない場合（ステップＳ５１８；ＮＯ）、復号器２４２は、反復復号処理の終了条件を満たしているか否かを判定し（ステップＳ５１９）、満たしている場合（ステップＳ５１９；ＹＥＳ）、制御部２３へ復号失敗を返した後（ステップＳ５２１）、本動作を終了する。一方、終了条件が満たされていない場合（ステップＳ５１９；ＮＯ）、復号器２４２は、ステップＳ５０２へリターンし、再度、第１および第２の次元の成分符号３０１〜３０４および３１１〜３１４に対して以降の動作を実行する。
【０１２１】
つづいて、図１５のステップＳ５０４およびＳ５１２におけるテストパターンを用いたリスト復号の動作例について、図１６を用いて詳細に説明する。図１６は、本実施形態におけるテストパターンを用いたリスト復号の概略動作例を示すフローチャートである。
【０１２２】
図１６に示すように、本動作例では、復号器２４２は、まず、図１５のステップＳ５０２／Ｓ５１０で抽出した第１の次元／第２の次元における未訂正の誤りシンボルを含む成分符号のうち未選択の成分符号を１つ選択する（ステップＳ５４１）。つづいて復号器２４２は、選択した成分符号に対して、複数パターンのテストパターンを生成する（ステップＳ５４２）。なお、複数パターンのテストパターンとは、仮説する誤りシンボルの位置パターンが互いに異なるテストパターンである。
【０１２３】
つづいて復号器２４２は、生成したテストパターンから適切なテストパターンを抽出する絞り込みを実行する（ステップＳ５４３）。なお、適切なテストパターンは、誤りであり得ないシンボルを誤りシンボルと仮定していないテストパターンや、必要以上の数のシンボルを誤りシンボルと仮定していないテストパターンなどであってよい。生成されたテストパターンから適切なテストパターンへの絞り込みでは、たとえば付加情報記憶部２４３に記憶されている信頼性フラグなどの付加情報を用いることが可能である。具体的には、たとえばあるテストパターンに関し、このテストパターンおいて誤りシンボルと仮定しているシンボルを含む他の次元の成分符号に対する信頼性フラグが“１”である場合には、このテストパターンは適切なテストパターンではないと判断するなどの手法をとることが可能である。
【０１２４】
つぎに復号器２４２は、ステップＳ５４３で絞り込んだテストパターンのうち未選択のテストパターンを１つ選択する（ステップＳ５４４）。つづいて復号器２４２は、ステップＳ５４１で選択した成分符号におけるシンボルのうち、ステップＳ５４３で選択したテストパターンにおいて誤りと仮定されているシンボルの位置に対応するシンボルの値を反転することで、ビットフリップされた成分符号を生成する（ステップＳ５４５）。
【０１２５】
つぎに復号器２４２は、ビットフリップされた成分符号に対し、図６のステップＳ１０３と同様に、反復復号を実行する（ステップＳ５４６）。つづいて復号器２４２は、ステップＳ５４６の復号処理においてエラーベクタが検出されたか否かを判定し（ステップＳ５４７）、エラーベクタが検出されていない場合（ステップＳ５４７；ＮＯ）、ステップＳ５５１へ進む。一方、エラーベクタが検出されていた場合（ステップＳ５４７；ＹＥＳ）、復号器２４２は、たとえば図６のステップＳ１０５を用いて説明した動作と同様の動作により、検出されたエラーベクタを検出部２４４に入力して、エラーベクタの検出が誤検出であるか否かを判定する（ステップＳ５４８）。
【０１２６】
ステップＳ５４８の判定の結果、検出部２４４から入力された判定結果が誤検出でないことを示していた場合（ステップＳ５４８；ＮＯ）、検出されたエラーベクタと、このエラーベクタを検出した際に使用されていたテストパターンとを内部メモリ２４５等に一旦記録しておき（ステップＳ５５０）、ステップＳ５５１へ進む。
【０１２７】
一方、ステップＳ５４８の判定の結果、検出部２４４から入力された判定結果が誤検出であることを示していた場合（ステップＳ５４８；ＹＥＳ）、復号器２４２は、たとえば図９のステップＳ２０１を用いて説明した動作と同様の動作により、内部メモリ２４５内に格納されている符号語（積符号３０）に誤訂正されたシンボルが含まれているか否かを判定する（ステップＳ５４９）。ただし、本実施形態では、復号対象の成分符号における１つ以上のシンボルがテストパターンによる仮説によって仮想的に誤り訂正されている。そのため、復号対象の成分符号に関する訂正シンボル数は、テストパターンを考慮していない元々の数に各テストパターンが仮定する誤りシンボルの数を加算した値となっている。たとえば元々の訂正シンボル数が“１”であって、テストパターンが仮定する誤りシンボルの数が“１”である場合、ステップＳ５４７において検出部２４４が参照する訂正シンボル数は、それらの合計である“２”となる。
【０１２８】
つづいて復号器２４２は、検出部２４４から入力された判定結果が誤訂正によるものであることを示していた場合（ステップＳ５４９；ＹＥＳ）、ステップＳ５５１へ進む。一方、検出部２４４から入力された判定結果が誤訂正によるものでないことを示していた場合（ステップＳ５４９；ＮＯ）、復号器２４２は、ステップＳ５５０へ進み、検出されたエラーベクタと、このエラーベクタを検出した際に使用されていたテストパターンとを内部メモリ２４５等に一旦記録しておき、ステップＳ５５１へ進む。
【０１２９】
ステップＳ５５１では、復号器２４２は、ステップＳ５４３で絞り込まれたテストパターンのうち未選択のテストパターンが存在するか否か、すなわち、全ての適切なテストパターンと組み合わせて復号処理を実行したか否かを判定する。全てのテストパターンを選択済みである場合（ステップＳ５５１；ＹＥＳ）、復号器２４２は、ステップＳ５５６へ進む。一方、未選択のテストパターンが存在する場合（ステップＳ５５１；ＮＯ）、復号器２４２は、復号処理を終了する条件（打ち切り条件ともいう）を満たしているか否かを判定し（ステップＳ５５２）、満たしている場合（ステップＳ５５２；ＹＥＳ）、ステップＳ５５３へ進む。一方、打ち切り条件を満たしていない場合（ステップＳ５５２；ＮＯ）、復号器２４２は、ステップＳ５４４へリターンし、次の未選択のテストパターンを選択して、以降の動作を実行する。なお、復号処理を終了する条件（打ち切り条件）とは、たとえば復号の繰り返し回数が所定の反復回数に達したことや、十分に尤もらしい復号語が得られたことなどとすることができる。
【０１３０】
ステップＳ５５３では、復号器２４２は、ステップＳ５５０において１組以上のエラーベクタおよびテストパターンが記録されているか否かを判定する。１組以上のエラーベクタおよびテストパターンが記録されている場合（ステップＳ５５３；ＹＥＳ）、復号器２４２は、組み合わせて記録されているエラーベクタとテストパターンとの排他的論理和（ＸＯＲ）をとることで、尤もらしい復号語を生成する（ステップＳ５５４）。つづいて復号器２４２は、生成した尤もらしい復号語の中から最も尤もらしい復号語を決定し（ステップＳ５５５）、ステップＳ５５６へ進む。一方、エラーベクタとテストパターンとが記録されていない場合（ステップＳ５５３；ＮＯ）、復号器２４２は、そのままステップＳ５５６へ進む。
【０１３１】
なお、ステップＳ５５５における最も尤もらしい復号語の決定では、上述した第１の実施形態において図６を用いて説明した動作が実行されてもよい。すなわち、ステップＳ５５４で生成された尤もらしい復号語を内部メモリ２４５内に組み込み、これにより得られた積符号３０に対して図６に示す動作を実行し、それにより得られる復号成功／失敗の結果や信頼性フラグまたはシンドロームの値に基づいて、何れの復号語が最も尤もらしい復号語であるかが特定されてもよい。さらに、ステップＳ５５５における最も尤もらしい復号語の決定の際に、上述した第２の実施形態において図９を用いて説明した動作が実行されるように構成することも可能である。
【０１３２】
ステップＳ５５６では、復号器２４２は、図１５のステップＳ５０２／Ｓ５１０で抽出した成分符号を全て選択したか否か、すなわちステップＳ５０２／Ｓ５１０で抽出した成分符号に対してステップＳ５４３で絞り込まれた全てのテストパターンを用いて復号処理を実行したか否かを判定する。未選択の成分符号が存在する場合（ステップＳ５５６；ＮＯ）、復号器２４２は、ステップＳ５４１へリターンして次の未選択の成分符号を選択し、以降の動作を実行する。一方、抽出した全ての成分符号が選択済みである場合（ステップＳ５５６；ＹＥＳ）、復号器２４２は、図１５に示す動作へリターンする。
【０１３３】
以上のように、本実施形態によれば、たとえば上述した実施形態における復号にリスト復号を組み合わせることで、誤り訂正能力をより向上させることが可能となる。なお、その他の構成、動作および効果は、上述した実施形態と同様であるため、ここでは詳細な説明を省略する。
【０１３４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１３５】
１…メモリシステム、２…メモリコントローラ、３…不揮発性メモリ、４…ホスト、２０…内部バス、２１…ホストＩ／Ｆ、２２…メモリＩ／Ｆ、２３…制御部、２４…符号化／復号部、２５…データバッファ、３０…積符号、２４１…符号化器、２４２…復号器、２４３…付加情報・レジスタ記憶部、２４４…検出部、２４５…内部メモリ、３０１〜３０３，３１１〜３１４…成分符号、４０１〜４０４，４１１〜４１４…信頼性フラグ、５０１〜５０４，５１１〜５１４…訂正シンボル数、６０１〜６０４，６１１〜６１４…誤訂正フラグ
【図１】
2018164174.tif 000003
【図２】
2018164174.tif 000004
【図３】
2018164174.tif 000005
【図４】
2018164174.tif 000006
【図５】
2018164174.tif 000007
【図６】
2018164174.tif 000008
【図７】
2018164174.tif 000009
【図８】
2018164174.tif 000010
【図９】
2018164174.tif 000011
【図１０】
2018164174.tif 000012
【図１１】
2018164174.tif 000013
【図１２】
2018164174.tif 000014
【図１３】
2018164174.tif 000015
【図１４】
2018164174.tif 000016
【図１５】
2018164174.tif 000017
【図１６】
2018164174.tif 000018