(57)【特許請求の範囲】
【請求項１】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、
（ａ）チャネルから前記符号ワードの前記表現をインポートすること、
（ｂ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ｃ）（ｉ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（ii）前記符号ワードビットの推定値が、前記グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすることを含む方法。
【請求項２】
（ｄ）前記グラフの少なくとも一部を複数の部分グラフに分割することを更に含み、
前記メッセージの交換の少なくとも一部が各部分グラフ内で別個に実行され、
前記グラフにトラッピング集合が含まれる兆候を示す前記基準が、前記部分グラフのうち１個だけで復号化の収束が失敗することを含む、請求項１に記載の方法。
【請求項３】
前記グラフにトラッピング集合が含まれている兆候を示す前記基準が、前記推定値のシンドロームの要素の１パーセント以下が非ゼロであり、２個の連続的な反復において一定であることを含む、請求項１に記載の方法。
【請求項４】
前記リセットが、前記チェックノードから送られるメッセージの少なくとも一部をゼロに設定することを含む、請求項１に記載の方法。
【請求項５】
前記リセットが、前記チェックノードから送られる全てのメッセージをゼロに設定することを含む、請求項４に記載の方法。
【請求項６】
前記リセットが、前記ビットノードから送られるメッセージの少なくとも一部を切り捨てることを含む、請求項１に記載の方法。
【請求項７】
前記リセットが、前記ビットノードから送られる全てのメッセージを切り捨てることを含む、請求項６に記載の方法。
【請求項８】
前記メッセージが対数尤度比であり、前記切り捨てが１０〜１６の間の値である、請求項６に記載の方法。
【請求項９】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、
（ａ）チャネルから前記符号ワードの前記表現をインポートすること、
（ｂ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ｃ）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記ビットノードから送られた前記メッセージの少なくとも一部を切り捨てることを含む方法。
【請求項１０】
前記所定の失敗基準が、前記推定値のシンドロームの要素の少なくとも所定個数が非ゼロである、請求項９に記載の方法。
【請求項１１】
前記所定個数が１である、請求項１０に記載の方法。
【請求項１２】
前記所定の失敗基準が、前記反復の所定回数実行後に、前記シンドロームの要素の少なくとも所定個数が非ゼロである、請求項１０に記載の方法。
【請求項１３】
前記所定の失敗基準が、所定時間経過後に、前記シンドロームの要素の少なくとも所定個数が非ゼロである、請求項１０に記載の方法。
【請求項１４】
前記所定の失敗基準が、前記メッセージの所定回数の交換後に、前記シンドロームの要素の少なくとも所定個数が非ゼロである、請求項１０に記載の方法。
【請求項１５】
前記所定の失敗基準が、連続的な２回の反復において、前記シンドロームの要素の高々所定個数が非ゼロのままである、請求項９に記載の方法。
【請求項１６】
前記所定の失敗基準が、連続的な２回の反復実行後に、非ゼロである前記シンドロームの要素の個数の差が所定の限度を下回る、請求項９に記載の方法。
【請求項１７】
前記所定の失敗基準が、所定回数の連続的な反復実行の前後で、前記推定値間で所定の限度を下回るハミング距離を含む、請求項９に記載の方法。
【請求項１８】
連続的な反復の前記所定回数が１である、請求項１７に記載の方法。
【請求項１９】
前記ビットノードから送られた全てのメッセージが切り捨てられる、請求項９に記載の方法。
【請求項２０】
前記メッセージが対数尤度比であり、前記切り捨てが１０〜１６の間の値である、請求項９に記載の方法。
【請求項２１】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、
（ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ｂ）（ｉ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（ii）前記符号ワードビットの推定値が、前記グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダ。
【請求項２２】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、
（ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、
（ｂ）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記ビットノードから送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダ。
【請求項２３】
（ａ）Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダと、
（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ii）（Ａ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（Ｂ）前記符号ワードビットの推定値が、前記グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含むメモリコントローラ。
【請求項２４】
（ｃ）前記符号ワードの少なくとも一部を主メモリに保存し、且つ前記符号ワードの前記少なくとも一部の表現を前記主メモリから取得する回路を更に含む、請求項２３に記載のメモリコントローラ。
【請求項２５】
（ａ）請求項２４に記載の前記メモリコントローラと、
（ｂ）前記主メモリとを含むメモリ装置。
【請求項２６】
（ａ）Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダと、
（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ii）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記ビットノードから送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含んでいるメモリコントローラ。
【請求項２７】
（ｃ）前記符号ワードの少なくとも一部を主メモリに保存し、且つ前記符号ワードの前記少なくとも一部の表現を前記主メモリから取得する回路を更に含む、請求項２６に記載のメモリコントローラ。
【請求項２８】
（ａ）請求項２７に記載の前記メモリコントローラと、
（ｂ）前記主メモリとを含むメモリ装置。
【請求項２９】
（ａ）通信チャネルから受信したメッセージを復調することによりＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、
（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ii）（Ａ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（Ｂ）前記符号ワードビットの推定値が、前記グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含む受信器。
【請求項３０】
（ａ）通信チャネルから受信したメッセージを復調することによりＫ個の情報ビットを
Ｎ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、
（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ii）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記ビットノードから送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含む受信器。
【請求項３１】
メッセージを送受信する通信システムであって、
（ａ）（ｉ）前記メッセージのＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダ、および
（ii）通信チャネルを介して前記符号ワードを変調信号として送信する変調器を含む送信器と、
（ｂ）（ｉ）前記通信チャネルから前記変調信号を受信して前記変調信号を復調することより、前記符号ワードの表現を生成する復調器、および
（ii）（Ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（Ｂ）（Ｉ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（II）前記符号ワードビットの推定値が、前記グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダを含む受信器とを含む通信システム。
【請求項３２】
メッセージを送受信する通信システムであって、
（ａ）（ｉ）前記メッセージのＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダ、および
（ii）通信チャネルを介して前記符号ワードを変調信号として送信する変調器を含む送信器と、
（ｂ）（ｉ）前記通信チャネルから前記変調信号を受信して前記変調信号を復調することにより、前記符号ワードの表現を生成する復調器、および
（ii）（Ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおける前記ビットノードと前記チェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（Ｂ）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記ビットノードから送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの表現を復号化するプロセッサを含むデコーダを含む受信器とを含む通信システム。
【請求項３３】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、
（ａ）チャネルから前記符号ワードの表現をインポートすること、
（ｂ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ｃ）前記行列の前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ｄ）（ｉ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（ii）前記符号ワードビットの推定値が、前記パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすることを含む方法。
【請求項３４】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、
（ａ）チャネルから前記符号ワードの表現をインポートすること、
（ｂ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ｃ）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新することおよび、
（ｄ）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記列から送られた前記メッセージの少なくとも一部を切り捨てることを含む方法。
【請求項３５】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、
（ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ｂ）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（ｃ）（ｉ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（ii）前記符号ワードビットの推定値が、前記パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダ。
【請求項３６】
Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、
（ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ｂ）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（ｃ）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記列から送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダ。
【請求項３７】
（ａ）Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダと、
（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ii）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（iii）（Ａ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（Ｂ）前記符号ワードビットの推定値が、前記パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含むメモリコントローラ。
【請求項３８】
（ｃ）前記符号ワードの少なくとも一部を主メモリに保存し、且つ前記符号ワードの前記少なくとも一部の表現を前記主メモリから取得する回路を更に含む、請求項３７に記載のメモリコントローラ。
【請求項３９】
（ａ）請求項３８に記載の前記メモリコントローラと、
（ｂ）前記主メモリとを含むメモリ装置。
【請求項４０】
（ａ）Ｋ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダと、
（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ii）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（iii）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記列から送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含むメモリコントローラ。
【請求項４１】
（ｃ）前記符号ワードの少なくとも一部を主メモリに保存し、且つ前記符号ワードの前記少なくとも一部の表現を前記主メモリから取得する回路を更に含む、請求項４０に記載のメモリコントローラ。
【請求項４２】
（ａ）請求項４１に記載の前記メモリコントローラと、
（ｂ）前記主メモリとを含むメモリ装置。
【請求項４３】
（ａ）通信チャネルから受信したメッセージを復調することによりＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、
（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ii）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（iii）（Ａ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（Ｂ）前記符号ワードビットの推定値が、前記パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含む受信器。
【請求項４４】
（ａ）通信チャネルから受信したメッセージを復調することよりＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、
（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（ii）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（iii）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復
を続ける前に前記列から送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダとを含む受信器。
【請求項４５】
メッセージを送受信する通信システムであって、
（ａ）（ｉ）前記メッセージのＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダ、および
（ii）通信チャネルを介して前記符号ワードを変調信号として送信する変調器を含む送信器と、
（ｂ）（ｉ）前記通信チャネルから前記変調信号を受信して前記変調信号を復調するこ
とにより、前記符号ワードの表現を生成する復調器、および
（ii）（Ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（Ｂ）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（Ｃ）（Ｉ）所定の失敗基準に照らして前記復号化が収束に失敗し、且つ
（II）前記符号ワードビットの推定値が、前記パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、前記反復を続ける前に前記メッセージの少なくとも一部をリセットすること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダを含む受信器とを含む通信システム。
【請求項４６】
メッセージを送受信する通信システムであって、
（ａ）（ｉ）前記メッセージのＫ個の情報ビットをＮ（＞Ｋ）個の符号ワードビットの符号ワードとして符号化するエンコーダ、および
（ii）通信チャネルを介して前記符号ワードを変調信号として送信する変調器を含む送信器と、
（ｂ）（ｉ）前記通信チャネルから前記変調信号を受信して前記変調信号を復調することにより、前記符号ワードの表現を生成する復調器、および
（ii）（Ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、
（Ｂ）前記行と前記列との間でのメッセージ交換を含むステップにより複数回の復号化反復で前記符号ワードビットの推定値を更新すること、
（Ｃ）所定の失敗基準に照らして前記復号化が収束に失敗した場合、前記反復を続ける前に前記列から送られた前記メッセージの少なくとも一部を切り捨てること、を含むステップにより、前記符号ワードの推定値を更新するアルゴリズムを実行することにより前記符号ワードの前記表現を復号化するプロセッサを含むデコーダを含む受信器とを含む通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本特許出願は、２００８年６月２３日出願の米国仮特許出願第６１／０７４，７０１号を優先権主張するものである。
【０００２】
本明細書に、トラッピング集合に起因する非収束を克服する低密度パリティチェック（ＬＤＰＣ）復号化の方法および関連装置を開示する。
【背景技術】
【０００３】
誤り訂正符号（ＥＣＣ）は、通信システムおよび記憶装置において共通的に用いられる。通信チャネルおよび記憶装置の両方において生じる各種の物理現象の結果として通信または保存された情報を損なうノイズ効果が生じる。誤り訂正符号化スキームを用いて、通信または保存された情報を結果的に生じた誤りから保護することができる。これは、通信チャネルを介した伝送またはメモリ装置への保存の前に情報を符号化することにより行われる。符号化処理は、情報に冗長性を加えることにより情報ビットシーケンスを符号ワードに変換する。次いでこの冗長性を用いて、復号処理を介して損なわれた可能性のある符号ワードから情報を復元することができる。
【０００４】
通信システムおよび記憶システムの両方において、情報ビットシーケンスｉは、通信チャネルにまたはメモリ装置に適合された一連のシンボルｘに変調または写像された符号化ビットシーケンスｖに符号化される。通信チャネルまたはメモリ装置の出力端で一連のシンボルｙが得られる。当該システムのＥＣＣデコーダはシーケンスｙを復号化して、ビットシーケンス
0005593312.tif 000002
を復元するものであり、元の情報ビットシーケンスｉを高い確度で再構築しなければならない。
【０００５】
一般的なＥＣＣファミリーは、線形２値ブロック符号のファミリーである。長さがＮであるＫ次元の線形２値符号は、長さＫの情報ビットシーケンスを長さＮの符号ワードに線形写像したものであって、Ｎ＞Ｋである。符号レートはＲ＝Ｋ／Ｎで定義される。１×Ｎ次元の符号ワードｖの符号化処理が通常、次式に従い１×Ｋ次元の情報ビットシーケンスｉにＫ×Ｎ次元の生成行列Ｇを乗ずることで行われる。
【０００６】
【数１】
0005593312.tif 000003
【０００７】
また、Ｍ×Ｎ次元のパリティチェック行列Ｈを定義することも慣習的であり、Ｍ＝Ｎ−Ｋ である。パリティチェック行列は、次式を介して生成行列に関連付けられる。
【０００８】
【数２】
0005593312.tif 000004
【０００９】
パリティチェック行列を用いて、長さがＮである２値ベクトルが有効な符号ワードであるか否かを調べることができる。１×Ｎの２値ベクトルｖは、次式が成立する場合に限っ
て符号に属する。
【００１０】
【数３】
0005593312.tif 000005
（式（３）において、ｖ’のプライム記号はｖ’が列ベクトルであることを意味する。）
【００１１】
近年、反復的符号化スキームが広く普及している。これらのスキームにおいて、符号はいくつかの簡単な組成符号の連接として構成され、簡単な符号の組成デコーダの間で情報を交換することにより、反復的な復号化アルゴリズムを用いて復号化される。通常、符号は組成符号間の相互接続を記述する二部グラフを用いて定義することができる。この場合、復号化はグラフの辺を介してやり取りされる反復的メッセージと見なすことができる。
【００１２】
反復符号の伝播しているクラスは、低密度パリティチェック（ＬＤＰＣ）符号である。ＬＤＰＣ符号は、疎なパリティチェック行列Ｈにより定義される線形２値ブロック符号である。図１に示すように、当該符号を同等に、Ｎ個のビットノード（図１ではＮ＝１３）の集合Ｖ、Ｍ個のチェックノード（図１ではＭ＝１０）の集合Ｃ、およびビットノードをチェックノードに接続する辺の集合Ｅ（図１ではＥ＝３８）を有する疎な二部グラフＧ＝（Ｖ，Ｃ，Ｅ）により定義できる。ビットノードは符号ワードビットに対応し、チェックノードはビットに対するパリティチェック制約に対応する。ビットノードは、辺により当該ビットノードが関与するチェックノードに接続される。図１の左側の符号の行列表現において、ビットノードｉをチェックノードｊに接続している辺を行ｊと列ｉの交差箇所における非ゼロの行列成分で表す。
【００１３】
図１の最初および最後のチェックノードの次に、式（３）に等価な行を示す。記号
0005593312.tif 000006
は「ＸＯＲ」を意味する。
【００１４】
ＬＤＰＣ符号は、反復的メッセージ受け渡し復号化アルゴリズムを用いて復号化することができる。これらのアルゴリズムは、ビットノード間でメッセージを交換することにより動作し、符号を表す基礎となる二部グラフの辺に沿ってノードをチェックする。デコーダには、符号ワードビットの初期推定値が与えられる（通信チャネル出力または読み出されたメモリ内容に基づいて）。これらの初期推定値は、有効な符号ワードとしてビットが満たすべきパリティチェック制約（式（３）による）を課すことにより洗練および改良される。これは、グラフの辺に沿って受け渡されるメッセージを用いて、符号ワードビットを表すビットノードと符号ワードビットに対するパリティチェック制約を表すチェックノードの間で情報を交換することにより行われる。
【００１５】
反復復号化アルゴリズムにおいて、ビット推定値およびビット推定値の信頼度の両方を伝達する「弱い」ビット推定値の利用が一般的である。
【００１６】
グラフの辺に沿って受け渡されるメッセージにより伝達されるビット推定値はさまざまな形式で表すことができる。「弱い」ビット推定値を表す一般的な尺度は、対数尤度比（ＬＬＲ）であり、
0005593312.tif 000007
（current constraints and observations：現在の制約および観測値）
ここに、「現在の制約および観測値」が手元のメッセージを計算する際に考慮される各種のパリティチェック制約であり、観測値ｙはこれらのパリティチェックに関与するビットに対応する。一般性を失うことなく、簡潔のため以下において常にＬＬＲメッセージを用いるものと仮定する。ＬＬＲの符号はビットの推定値を与える（すなわち、正のＬＬＲはｖ＝０に対応し、負のＬＬＲはｖ＝１に対応する）。ＬＬＲの大きさは、推定値の信頼度を与える（すなわち、｜ＬＬＲ｜＝０は推定値が全く信頼できないことを意味し、｜ＬＬＲ｜＝±∞は推定値が完全に信頼でき且つビット値が既知であることを意味する）。
【００１７】
通常、ビットノードとチェックノードの間のグラフ辺に沿った復号化を行う間に受け渡されるメッセージは外因的である。辺ｅ上のノードｎから受け渡された外因的メッセージｍは、辺ｅ以外でｎに接続している辺上で受取られた全ての値を考慮に入れる（当該メッセージは新しい情報だけに基づいているため、外因的と呼ばれる）。
【００１８】
メッセージ受け渡し復号化アルゴリズムの一例として、確率伝播（ＢＰ）アルゴリズムがあり、メッセージ受け渡しアルゴリズムファミリの中で最良のアルゴリズムと考えられる。
【００１９】
Ｐv＝ｌｏｇ（Ｐｒ（ｖ＝０｜ｙ）／Ｐｒ（ｖ＝１｜ｙ））が、受信されたかまたは読
み出された記号ｙだけに基づいてビットｖの初期デコーダ推定値を表すとする。ビットのいくつかは通信チャネルを介して送信されていないかまたはメモリ装置に保存されていないためにこれらのビットのｙ観測値が無い可能性もある点に注意されたい。この場合、二つの可能性がある。１）短縮ビット、すなわちビットは先験的に知られていてＰv＝±∞
（ビットが０か１に応じて）である。２）パンクチャードビット、すなわちビットは先見的には知られておらずＰv＝ｌｏｇ（Ｐｒ（ｖ＝０）／Ｐｒ（ｖ＝１））であり、Ｐｒ（
ｖ＝０）およびＰｒ（ｖ＝１）はビットｖが各々０または１である先験的確率である。情報ビットが０または１である先験的確率が等しく、且つ符号が線形であると仮定すれば、Ｐv＝ｌｏｇ（（１／２）／（１／２））＝０である。
【００２０】
Ｑv＝ｌｏｇ（Ｐｒ（ｖ＝０｜ｙ，Ｈ・ｖ＝０）／Ｐｒ（ｖ＝１｜ｙ，Ｈ・ｖ＝０））
が、受取ったかまたは読み出された全体のシーケンスｙに基づき、且つビットｖが符号ワードの一部であると仮定（すなわち、Ｈ・ｖ＝０と仮定）して、ビットｖの最終デコーダ推定値を表すとする。
【００２１】
Ｑvcがビットノードｖからチェックノードｃへのメッセージを表すとする。Ｒcvをチェックノードｃからビットノードｖへのメッセージを表すとする。
【００２２】
ＢＰアルゴリズムは以下の更新規則を利用してメッセージを計算する。
【００２３】
ビットノードからチェックノードへの計算規則は次式である。
【００２４】
【数４】
0005593312.tif 000008
【００２５】
ここに、Ｎ（ｎ，Ｇ）はグラフＧにおけるノードｎの隣接ノードの集合を表し、ｃ’∈Ｎ（ｖ，Ｇ）＼ｃは、ノード「ｃ」を除く隣接ノードを指す（和はｃ以外の全ての隣接ノードについて求める）。
【００２６】
チェックノードからビットノードへの計算規則は次式である。
【００２７】
【数５】
0005593312.tif 000009
【００２８】
ここに、φ（ｘ）＝｛ｓｉｇｎ（ｘ），−ｌｏｇ  ｔａｎｈ（｜ｘ｜／２）｝であって、φ領域内の演算は群｛０，１｝×Ｒ+にわたり行われる（これは基本的に、ここでの和
は大きさの合計と符号同士のＸＯＲとして定義されていることを意味する）。式（４）の表記と同様に、Ｎ（ｃ，Ｇ）はグラフＧ内のチェックノードｃの隣接するビットノードの集合を表し、ｖ’∈Ｎ（ｃ，Ｇ）＼ｖはノード「ｖ」を除く隣接ノードを指す（和はｖ以外の全ての隣接ノードについて求める）。
【００２９】
ビットｖに対する最終デコーダ推定値は以下の通りである。
【００３０】
【数６】
0005593312.tif 000010
【００３１】
メッセージ受け渡し復号化を行う間におけるメッセージ受け渡しの順序を復号化スケジュールと呼ぶ。ＢＰ復号化は特定のスケジュールを用いることは示唆せず、計算規則（式（４）、（５）および（６））を定義するだけである。復号化スケジュールは、符号の期待される誤り訂正能力に影響を及ぼさない。しかし、復号化スケジュールは、デコーダの収束速度およびデコーダの複雑度に大いに影響し得る。
【００３２】
ＬＤＰＣ符号を復号化する標準メッセージ受け渡しスケジュールは、各反復において全ての可変ノード、および後続する全てのチェックノードが隣接ノードに新規メッセージを受け渡すフラッディングスケジュールである（Ｒ．Ｇ．Gallager，Low-Density  Parity-Check  Codes，Camridge，ＭＡ：ＭＩＴ  Ｐｒｅｓｓ  1963）。フラッディングスケジュールに基づく標準ＢＰアルゴリズムを図２に与える。
【００３３】
フラッディングスケジュールに基づくＢＰアルゴリズムの標準的な実装は必要なメモリの観点から高価である。（Ｐv，Ｑv，Ｑvc、およびＲcv個のメッセージを保存するために）総計で２｜Ｖ｜＋２｜Ｅ｜個のメッセージを保存する必要がある。更に、フラッディングスケジュールは収束速度が遅いため、必要とされる誤り訂正能力を所与の復号化スループットで提供するためにより高度な復号化論理（例：ＡＳＩＣ上により多くのプロセッサ）を必要とする。
【００３４】
より効率的な、連続メッセージ受け渡し復号化スケジュールが知られている。連続メッセージ受け渡し復号化スケジュールでは、ビットまたはチェックノードを連続的に辿り、各ノードについて、当該ノードとの間で対応するメッセージがやり取りされる。例えば、連続スケジュールは、グラフ内のチェックノードを何らかの順序で連続的に辿ることにより実装でき、各チェックノードｃ∈Ｃについて以下のメッセージは送られる。
【００３５】
１．各ｖ∈Ｎ（ｃ）に対してＱvc（すなわち、ノードｃへの全てのＱvcメッセージ）
２．各ｖ∈Ｎ（ｃ）に対してＲcv（すなわち、ノードｃからの全てのＲcvメッセージ）
【００３６】
フラッディングスケジュールとは対照的に、連続スケジュールはグラフ上で情報の即時且つより高速な伝播を可能にする結果、収束がより速く（ほぼ２倍速く）なる。更に、連続スケジュールは、必要なメモリを大幅に減らしつつ効率的に実装できる。これは、Ｑvc
メッセージをオンザフライ計算するためにＱv個のメッセージおよびＲcv個のメッセージ
を用いることにより実現でき、従ってＱvc個のメッセージを保存するための追加メモリを使用する必要がなくなる。これは式（４）、（６）に基づいてＱvcを（Ｑv−Ｒcv）で表
すことにより行われる。更に、先験的なメッセージＰvにより初期化されたものと同一メ
モリを用いて、反復的に更新されたＱv個の後験的メッセージを保存する。フラッディン
グスケジュールの標準的な実装では符号のグラフ構造を保存するために２倍のメモリを必要とする両方のデータ構造Ｎ（ｃ）∀ｃ∈ＣおよびＮ（ｖ）∀ｖ∈Ｖを使用するのに対し、連続スケジュールではＮ（ｃ）∀ｃ∈Ｃに関する知識だけを使用すればよいため、必要なメモリを更に減らすことができる。連続にスケジューリングされた復号化アルゴリズムを図３に示す。
【００３７】
要約すれば、連続復号化スケジュールは、フラッディングスケジュールに対して以下の利点がある。
【００３８】
１）連続復号化スケジュールは、標準フラッディングスケジュールと比較して収束速度を２倍に上げる。これは、フラッディングスケジュールに基づくデコーダと比較して、所与のスループットで所与の誤り訂正能力を提供するために半分の復号化論理だけで済むことを意味する。
【００３９】
２）連続復号化スケジュールは、デコーダの実装におけるメモリ効率を高める。｜Ｖ｜＋｜Ｅ｜個のメッセージだけを保存するＲＡＭが必要である（標準フラッディングスケジュールのように２｜Ｖ｜＋２｜Ｅ｜個のメッセージを保存するのではなく）。標準フラッディングスケジュールと比較して符号のグラフ構造を保存するのに半分のＲＯＭサイズで済む。
【００４０】
３）反復実行の間、「オンザフライ」収束テストを計算の一環として実施できるため、反復実行中に収束が検出でき、且つ任意の時点で復号化を終了できる。これにより復号に要する時間とエネルギー消費を節約できる。
【００４１】
[定義]
本明細書に記述する方法は、少なくとも二つの異なる条件下でデータ誤りの訂正に適用できる。一つの条件、記憶媒体からどのデータを取得するかである。他の条件は、伝送媒体からどのデータを受信するかである。記憶媒体および伝送媒体は、データに誤りを入れる「チャネル」の特別な場合である。データの「取得」および「受信」という概念を本明細書ではてデータを「インポート」するという概念に一般化している。データの「取得」およびデータの「受信」は、データをチャネルから「インポートする」特別な場合である。
【００４２】
本明細書に示す方法により復号化されるデータは符号ワードの表現である。これらの方法の一つが復号化に適用される前にチャネル内で符号ワードがノイズにより損なわれている恐れがあるため、データは符号ワードの「表現」に過ぎず、符号ワード自体ではない。
【発明の概要】
【発明が解決しようとする課題】
【００４３】
反復符号化システムでは図４で示すように、エラーフロアと呼ばれる好ましくない現象が生じ、通信チャネルまたはメモリ装置内で特定の「ノイズ」レベル以下では、ビット誤りの原因である「ノイズ」がたとえ減少するにせよ、デコーダの出力におけるブロック誤り率（ＢＥＲ）ははるかに遅く減少し始める。この現象は特に、必要なデコーダ出力ブロック誤り率が極めて低い（〜１０-10）ことが求められる記憶システム内で問題となる。
図４では右へ行くほどノイズが増加する点に注意されたい。
【００４４】
反復符号化システムの誤り訂正能力およびエラーフロアは、符号長が増加するにつれて向上する（これはどのＥＣＣシステムでも言えるが、特に短い符号長で誤り訂正能力が劣る反復符号化システムで顕著である）ことが良く知られている。
【００４５】
しかし、反復符号化システムの従来方式の実装では、復号化ハードウェアのメモリの複雑度は符号長と比例するため、たとえ知られている最も効率的な実装（例：連続的にスケジューリングされたデコーダ）であっても長い符号を使用すれば複雑度が高まる。
【００４６】
従って、本明細書では、複雑度の低い復号化ハードウェアを用いて極めて低いエラーフロアおよびほぼ最適な誤り訂正能力を提供する極めて長いＬＤＰＣ符号を実装する方法を開示する。
【００４７】
適切に設計されたＬＤＰＣ符号は極めて強力であって、符号ワード内の多くの誤りを訂正できるが、たとえ不正確なビットの数が非常に少なくてグラフ内の特定の領域に限定できるにせよ、「トラッピング集合」として知られる現象に起因してデコーダが失敗し、符号のエラーフロアが増加する恐れがある。トラッピング集合は一般的なＬＤＰＣ符号に対して明確に定義されていないものの、「これらは、誘導された部分グラフがごく少数の奇数次数チェックノードしか存在しないように、比較的少ない数の可変ノードを有する集合である。」として記述されている。
【００４８】
トラッピング集合は、ＬＤＰＣグラフのトポロジおよび使用する特定の復号化アルゴリズムに関連していて、回避および解析するのが困難である。
【００４９】
トラッピング集合は、歴史的に記憶装置が要求する信頼度が、例えば保存された１０14個のビット当たり１個のビット誤りというように比較的高いため、記憶装置分野で問題であった。その結果、フラッシュメモリ装置等のメモリ装置で用いられる符号はエラーフロアが低くなければならないが、トラッピング集合はエラーフロアを増やしてしまう。
【課題を解決するための手段】
【００５０】
従って、本明細書に示す一実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、本方法は（ａ）チャネルから符号ワードの表現をインポートすること、（ｂ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ｃ）（ｉ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（ii）符号ワードビットの推定値が、当該グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすることを含んでいる。
【００５１】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、本方法は（ａ）チャネルから符号ワードの表現をインポートすること、（ｂ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ｃ）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該ビットノードから送られたメッセージの少なくとも一部を切り捨てることを含んでいる。
【００５２】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとし
て符号化する符号ワードの表現を復号化するデコーダであって、（ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ｂ）（ｉ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（ii）符号ワードビットの推定値が、当該グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含んでいる。
【００５３】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、（ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ｂ）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該ビットノードから送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含んでいる。
【００５４】
本明細書に示す別の実施形態はメモリコントローラであって、（ａ）Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダと、（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ii）（Ａ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（Ｂ）符号ワードビットの推定値が、当該グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００５５】
本明細書に示す別の実施形態はメモリコントローラであって、（ａ）Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダと、（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ii）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該ビットノードから送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００５６】
本明細書に示す別の実施形態は受信器であって、（ａ）通信チャネルから受信したメッセージを復調することよりＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ii）（Ａ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（Ｂ）符号ワードビットの推定値が、当該グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００５７】
本明細書に示す別の実施形態は受信器であって、（ａ）通信チャネルから受信したメッセージを復調することよりＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、（ｂ）（ｉ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ii）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該ビットノードから送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００５８】
本明細書に示す別の実施形態はメッセージを送受信する通信システムであって、（ａ）（ｉ）当該メッセージのＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダ、および（ii）通信チャネルを介して符号ワードを変調信号として送信する変調器を含む送信器と、（ｂ）（ｉ）通信チャネルから変調信号を受信して当該変調信号を復調することより、符号ワードの表現を生成する復調器、および（ii）（Ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（Ｂ）（Ｉ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（ＩＩ）符号ワードビットの推定値が、当該グラフにトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダを含む受信器とを含んでいる。
【００５９】
本明細書に示す別の実施形態はメッセージを送受信する通信システムであって、（ａ）（ｉ）当該メッセージのＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダ、および（ii）通信チャネルを介して符号ワードを変調信号として送信する変調器を含む送信器と、（ｂ）（ｉ）通信チャネルから変調信号を受信して当該変調信号を復調することにより、符号ワードの表現を生成する復調器、および（ii）（Ａ）Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフにおけるビットノードとチェックノードとの間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（Ｂ）（Ｉ）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該ビットノードから送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダを含む受信器とを含んでいる。
【００６０】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、本方法は（ａ）チャネルから符号ワードの表現をインポートすること、（ｂ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ｃ）当該行列の行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ｄ）（ｉ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（ii）符号ワードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすることを含んでいる。
【００６１】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化する方法であって、本方法は（ａ）チャネルから
符号ワードの表現をインポートすること、（ｂ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ｃ）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新することおよび、（ｄ）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該列から送られたメッセージの少なくとも一部を切り捨てることを含んでいる。
【００６２】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、（ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ｂ）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（ｃ）（ｉ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（ii）符号ワードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含んでいる。
【００６３】
本明細書に示す別の実施形態は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化するデコーダであって、（ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ｂ）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（ｃ）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該列から送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含んでいる。
【００６４】
本明細書に示す別の実施形態はメモリコントローラであって、（ａ）Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダと、（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ii）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（iii）（Ａ）所定の失敗基準に照らして復号化が収束に失敗し、
且つ（Ｂ）符号ワードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００６５】
本明細書に示す別の実施形態はメモリコントローラであって、（ａ）Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダと、（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ii）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（iii）所定の失敗基準に照らして復号化が収束に失敗した場合、
反復を続ける前に当該列から送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００６６】
本明細書に示す別の実施形態は受信器であって、（ａ）通信チャネルから受信したメッセージを復調することよりＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ii）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（iii）（
Ａ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（Ｂ）符号ワードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００６７】
本明細書に示す別の実施形態は受信器であって、（ａ）通信チャネルから受信したメッセージを復調することよりＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を生成する復調器と、（ｂ）（ｉ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（ii）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（iii）所
定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該列から送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダとを含んでいる。
【００６８】
本明細書に示す別の実施形態はメッセージを送受信する通信システムであって、（ａ）（ｉ）当該メッセージのＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダ、および（ii）通信チャネルを介して符号ワードを変調信号として送信する変調器を含む送信器と、（ｂ）（ｉ）通信チャネルから変調信号を受信して当該変調信号を復調することにより、符号ワードの表現を生成する復調器、および（ii）（Ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（Ｂ）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（Ｃ）（Ｉ）所定の失敗基準に照らして復号化が収束に失敗し、且つ（ＩＩ）符号ワードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部をリセットすること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダを含む受信器とを含んでいる。
【００６９】
本明細書に示す別の実施形態はメッセージを送受信する通信システムであって、（ａ）（ｉ）当該メッセージのＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダ、および（ii）通信チャネルを介して符号ワードを変調信号として送信する変調器を含む送信器と、（ｂ）（ｉ）通信チャネルから変調信号を受信して当該変調信号を復調することにより、符号ワードの表現を生成する復調器、および（ii）（Ａ）Ｎ−Ｋ行およびＮ列を有するパリティチェック行列を提供すること、（Ｂ）行と列との間でのメッセージ交換を含むステップにより複数回の復号化反復で符号ワードビットの推定値を更新すること、（Ｃ）所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該列から送られたメッセージの少なくとも一部を切り捨てること、を含むステップにより、符号ワードの推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化するプロセッサを含むデコーダを含む受信器とを含んでいる。
【００７０】
本明細書において、チャネルからインポートされたＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を復号化する４種の一般的な方法を示す。
【００７１】
最初の２種の一般的な方法によれば、Ｎ個のビットノードおよびＮ−Ｋ個のチェックノードを含むグラフのビットノードとチェックノードとの間でメッセージを交換することにより、複数回の復号化反復で符号ワードビットの推定値を更新する。
【００７２】
第１の一般的な方法によれば、所定の失敗基準に照らして復号化が失敗し、且つ符号ワードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たしている場合、反復を続ける前にメッセージの少なくとも一部がリセットされる。
【００７３】
第１の一般的な方法のいくつかの実施形態において、グラフの少なくとも一部が複数の部分グラフに分割される。メッセージ交換の少なくとも一部が各部分グラフ内で別個に実行される。当該グラフにトラッピング集合が含まれるとする関連基準は、当該部分グラフのうち１個だけで復号化の収束が失敗することを含んでいる。
【００７４】
当該グラフにトラッピング集合が含まれる別の基準は、符号ワードビットの推定値のシンドロームの要素の高々約１パーセントが非ゼロ且つ２個の連続的な反復において一定であることである。
【００７５】
メッセージの少なくとも一部をリセットすることは、好適にはチェックノードから送られるメッセージの少なくとも一部の設定、および／またはビットノードから送られるメッセージの少なくとも一部の切り捨てを含んでいる。最も好適には、リセットは、チェックノードから送られた全てのメッセージをゼロに設定する、および／またはビットノードから送られる全てのメッセージを切り捨てることを含んでいる。好適には、ビットノードから送られるメッセージは対数尤度比であり、そのうち切り捨てられるメッセージは、約１０〜約１６桁である。
【００７６】
第２の一般的な方法によれば、所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前にビットノードから送られたメッセージの少なくとも一部が切り捨てられる。
【００７７】
一つの好適な失敗の基準は、例えば所定回数の反復の後、または所定時間の後、あるいはビットノードとチェックノード間での所定回数のメッセージ交換の後で、符号ワードビット推定値の非ゼロであるシンドロームの要素が少なくとも所定個数であることを含んでいる。別の好適な失敗基準は、２つの連続的な反復において符号ワードビット推定値の非ゼロであるシンドロームの要素が多くとも所定個数であることを含んでいる。好適な他の失敗基準は、連続的な２回の反復の後で、符号ワードビット推定値の非ゼロであるシンドロームの要素の数が所定の限度を下回ることを含んでいる。別の好適な失敗基準は、連続的な所定回数の反復の前後（例：１回の反復の前後）で、符号ワードビット推定値間のハミング距離が所定の限度を下回ることを含んでいる。
【００７８】
好適には、ビットノードから送られた全てのメッセージが切り捨てられる。
【００７９】
好適には、メッセージは対数尤度比であり、そのうち切り捨てられるメッセージは、高々約１０〜約１６桁が切り捨てられる。
【００８０】
上述のように、ＬＤＰＣ復号化のグラフ図は図１に示すように行列表現と等価である。従って、第３および第４の一般的な方法によれば、符号ワードビットの推定値は、Ｎビットのベクトル要素を有するビットベクトルとＮ−Ｋ個のチェックベクトル要素を有するチェックのベクトルを接続するパリティチェック行列を用いて更新される。複数回の復号化反復において、符号ワードビットの推定値は、そのように接続されたビットベクトル要素とチェックベクトル要素との間でメッセージを交換することにより更新される。
【００８１】
第３の一般的な方法によれば、所定の失敗基準に照らして復号化が失敗し、且つ符号ワ
ードビットの推定値が、当該パリティチェック行列にトラッピング集合が含まれている兆候を示す基準を満たす場合、反復を続ける前にメッセージの少なくとも一部がリセットされる。
【００８２】
第４の一般的な方法によれば、所定の失敗基準に照らして復号化が収束に失敗した場合、反復を続ける前に当該列から送られたメッセージの少なくとも一部が切り捨てられる。
【００８３】
４種の一般的な方法の一つに対応するデコーダは、対応する一般的な方法により符号ワードビット推定値を更新するアルゴリズムを実行することにより符号ワードの表現を復号化する１個以上のプロセッサを含んでいる。
【００８４】
４種の一般的な方法の一つに対応するメモリコントローラは、Ｋ個の情報ビットをＮ＞Ｋビットの符号ワードとして符号化するエンコーダと、一般的な方法に対応するデコーダとを含んでいる。通常、このようなメモリコントローラは、符号ワードの少なくとも一部をメインメモリに保存すると共に、当該メインメモリから当該符号ワードの（おそらくノイズが多い）少なくとも一部の表現を取得する回路を含んでいる。４種の一般的な方法の一つに対応するメモリ装置は、このようなメモリコントローラを含むと共に、メインメモリをも含んでいる。
【００８５】
４種の一般的な方法の一つに対応する受信器は、通信チャネルから受信したメッセージを復調する復調器を含んでいる。復調器は、Ｋ個の情報ビットをＮ＞Ｋ個の符号ワードビットとして符号化する符号ワードの表現を提供する。そのような受信器はまた、一般的な方法に対応するデコーダを含んでいる。
【００８６】
４種の一般的な方法の一つに対応する通信システムは、送信器および受信器を含んでいる。送信器は、メッセージのＫ個の情報ビットをＮ＞Ｋ個の符号ワードビットの符号ワードとして符号化するエンコーダと、通信チャネルを介して当該符号ワードを変調信号として送信する変調器を含んでいる。受信器は、一般的な方法に対応する受信器である。
【００８７】
添付の図面を参照しながら、各種の実施形態についてあくまでも例示目的で記述する。
【図面の簡単な説明】
【００８８】
【図１】ＬＤＰＣ符号が疎なパリティチェック行列または疎な二部グラフとしてどのように表現できるかを示す。
【図２】フラッディングスケジュール確率伝播アルゴリズムを示す。
【図３】従来の連続スケジュール確率伝播アルゴリズムを示す。
【図４】エラーフロアを示す。
【図５】部分グラフ内および部分グラフと外部チェックノードの集合との間でどのようにメッセージが交換されるかを示す。
【図６】部分グラフ内および部分グラフと外部チェックノードの集合との間でメッセージが交換される確率伝播アルゴリズムを示す。
【図７Ａ】図６のアルゴリズムを実装するデコーダの高水準模式ブロック図である。
【図７Ｂ】図６のアルゴリズムを実装するデコーダの高水準模式ブロック図である。
【図８】図１の疎な二部グラフを部分グラフに分割する２通りの方法を示す。
【図９】図１の疎な二部グラフを部分グラフに分割する２通りの方法を示す。
【図１０】コントローラが図７Ａのデコーダを含むフラッシュメモリ装置の高水準模式ブロック図である。
【図１１】図１０の詳細図である。
【図１２】受信器が図７Ａのデコーダを含む通信システムの高水準模式ブロック図である。
【発明を実施するための形態】
【００８９】
複雑度が低いＬＰＤＣ復号化およびトラッピング集合に起因する非収束を克服するＬＰＤＣ復号化の原理および動作は、図面および付随する記述を参照することでよりよく理解されよう。
【００９０】
ＬＤＰＣ符号用の従来型デコーダにおいて、デコーダが必要とするメモリは符号長Ｎ（符号の基礎となるグラフ｜Ｖ｜の可変ノードの数に等しい）および符号の基礎となるグラフ｜Ｅ｜の辺の数に比例する。効率的な実装において（例えば、連続的にスケジュールされたデコーダに基づいて）、必要とされるメモリは（｜Ｖ｜＋｜Ｅ｜）*ｂｐｍビットと
同程度に小さくてよく、ここに｜Ｖ｜はビット推定値の数、｜Ｅ｜は辺メッセージの数、ｂｐｍはデコーダのメモリに保存されている１メッセージ当たりのビット数である（ここでは簡便のため、ビット推定値および辺メッセージの保存に同じビット数が必要とされると仮定しているが必ずしもそうでなくてもよい点に注意されたい）。充分な復号化時間が利用できると仮定すれば、本明細書に開示するデコーダは従来型デコーダと比較して、｜Ｖ｜個のビット推定値および｜Ｅ｜個の辺メッセージの一部だけを同時に保存することで、デコーダの誤り訂正能力を全く低下させることなく、復号化の実装に用いるメモリがはるかに小さくて済む。これは、適切な復号化スケジュールを採用し、且つ本明細書に記述する復号化ハードウェアを用いることにより実現される。
【００９１】
本明細書に記述する方法およびデコーダは、符号を表す基礎となるグラフをいくつかの区間に分割することにより動作し、グラフの異なる区間を一度に１個以上順次処理することによりメッセージ受け渡し復号化アルゴリズムを実行する。復号化実行中の各段階で、現在処理されているグラフ区間（群）に対応するビット推定値および辺メッセージだけが保存される。このようにして、極めて長いＬＤＰＣ符号は採用するため、複雑度が低い復号化ハードウェアを利用しながら、ほぼ最適な誤り訂正能力および極めて低いエラーフロアが得られる。
【００９２】
本明細書に開示するデコーダは、主に以下の三つの理由により、メモリ装置での使用に極めて適している。
【００９３】
１．低いＥＣＣエラーフロアは、厳しいデコーダ出力ＢＥＲ要件（＜１０-15）がある
メモリ装置において特に重要である。短い符号を用いる場合、このような低いエラーフロアを実現することは極めて難しく、通常は符号の誤り訂正能力を犠牲にすることを必要とするが、これは符号の長さが短いために既に下げられている。従って、等価な長い符号を用いて符号の誤り訂正能力が向上し、従って保存されたデータを損なう所与のメモリ「ノイズ」から情報を保護するためにより低いＥＣＣ冗長性が必要とされる。より大量の情報を所与の数のメモリセル（または所与のメモリシリコンサイズを用いて）に保存することができるため、これは結果的にメモリの費用対効果を向上させる。従って、メモリ装置の長ＥＣＣを使用することで大きい利点が得られるものと期待される。
【００９４】
２．本明細書に開示するＬＤＰＣ方法は、一度にグラフ全体ではなく、各処理フェーズで符号の基礎となるグラフの区間を処理することを可能にする。このことは、各フェーズで「弱い」ビット推定値の全てではなく、「弱い」ビット推定値の一部だけを保存することができることを意味する。ここで、「弱い」ビット推定値という用語は、ストレージ（恐らくはフラッシュ装置）からの読み出しから推論される各々の保存されたビットの推定値「ｙ」の信頼度を記述する一群のビットを指す。
【００９５】
現在必要とされるビット観測値（ｙ）だけを記憶装置から読み出すことができ、従ってＥＣＣ復号化を実装するためにメモリコントローラ内に大きいバッファを必要としないた
め、この特徴をメモリ装置で容易に利用することができる。あるいは、全てのビット観測値（ベクトルｖで表す）を一度にメモリから読み出す場合でも、これらの保存に必要なバッファは通常、デコーダが必要とするビット観測値（Ｐv個のメッセージ）の保存に必要
なメモリよりもはるかに小さい。このように、現在デコーダにより処理中であるグラフ区間に対応する弱いビット推定値の一部だけが毎回生成される結果、必要とされるデコーダのメモリが小さくて済む。
【００９６】
例えば、各セルが単一のビットｖを保存し、各セルから読み出された状態ｙが０または１のいずれかであるＳＬＣフラッシュメモリ装置を考える（１セル当たり１ビットを保存するフラッシュメモリ装置である。「ＳＬＣ」は「単一レベルセル」を意味するが、実際には各セルが２レベルをサポートするため誤った名称である。「ＳＬＣ」の「Ｓ」はプログラミングされたレベルが一つしかないことを示す）。すると、読み出されたセル状態のベクトルｖの保存に必要とされるメモリはＮビットである。一方、全ての弱いビット推定値（Ｐv個のメッセージ）の保存により大きいメモリが必要となり得る（例えば、各ＬＬ
Ｒ推定値が６ビットに保存される場合は６Ｎビット）。従って、各デコーダ起動において必要とされる弱いビット推定値だけを生成する方がより効率的である。あるビットｖに対するＬＬＲビット推定値Ｐv＝ｌｏｇ（Ｐｒ（ｖ＝０｜ｙ）／Ｐｒ（ｖ＝１｜ｙ））を、
メモリ「ノイズ」に関する先験的な知識に基づいてフラッシュメモリ装置から読み出された対応するビット観測値ｖから生成することができる。換言すれば、メモリ「ノイズ」統計値を知ることにより、「ｙ」がセルから読まれる前提で、特定のメモリセルに保存されたビットｖが０／１である確率を推論することができる。
【００９７】
例えば、特定のＳＬＣフラッシュメモリ装置において、プログラムされたものとは異なるセルの状態を読み出す確率をｐ＝１０-2とすれば、ｙ＝０ならばＰv＝ｌｏｇ（（１−
ｐ）／ｐ）＝４．６、およびｙ＝１ならはＰv＝ｌｏｇ（ｐ／（１−ｐ））＝−４．６で
ある。更に、セルが単一ビット（１個の「強いビット」）を保存し、当該装置は２個の「弱いビット」に等価な８個の閾値電圧レベルを読み出すように構成されているためにフラッシュ装置の各セル（「ｖ」で表す）から読み出すことができる状態の数が８である場合、コントローラ内で３ビットのストレージを必要とする各要素「ｖ」が、３ビットより多い、例えば６ビット（ＢＰＭ＝１メッセージ当たりのビット数＝６）として表現することができるＬＬＲ値Ｐvに変換される。これら６ビットは、フラッシュセルから読み出され
た２個の弱いビットとは逆に弱いビット推定値であって、この６ビットのＬＬＲ値に対応している。
【００９８】
３．本明細書に示す種類の復号化スケジュールは、（従来の復号化スケジュールと比較して）必要なメモリがより小さくて済む。しかし、本明細書に開示する復号化スケジュールでは、デコーダ収束速度が遅くなり、特にデコーダの最大誤り訂正能力付近で動作しているときに復号化時間が増大する恐れがある。このようなデコーダは、可変ＥＣＣ復号化待ち時間を許容できるメモリ装置には極めて適している。例えば、損傷ビットの数が多いために、保存された正しい符号ワードにＥＣＣが収束するために必要とされる復号化時間が長い場合、メモリコントローラは以前に読まれた符号ワードの復号化が終了するまでメモリからの読み出しを止めることができる。フラッシュメモリ装置の寿命の大半では、メモリ「ノイズ」が小さく、且つ損傷ビットの数が少ない点に注意されたい。従って、デコーダは効率的且つ迅速に動作するため、パイプライン化された効率的なメモリ読み出しが可能になる。稀に、メモリから読み出された損傷ビットの数が多く、復号化時間が長引いた結果、読み出パイプラインがストールすることがある。従って、これらの可変的な復号化時間特徴にも拘わらず、平均的にはスループットは影響を受けないままである。
【００９９】
実施形態の一つのクラスによれば、符号を表す二部グラフＧ＝（Ｖ，Ｃ，Ｅ）が以下のようにいくつかの区間に分割される。すなわち、１）ビットノードの集合Ｖをｔ個の互い
に素な部分集合Ｖ1，Ｖ2，．．．，Ｖt（但しＶ＝Ｖ1∪Ｖ2∪．．．∪Ｖt）に分割する。２）ビットノードの各部分集合Ｖiについて、Ｖi内のビットノードだけに接続しているチェックノードの全てを含むチェックノードの部分集合Ｃiを形成する。３）これまでに形
成されたチェックノードの部分集合のいずれにも存在しないチェックノードの全てを含む外部チェックノードの部分集合ＣJすなわちＣJ＝Ｃ＼（Ｃ1∪Ｃ2∪．．．∪Ｃt）を形成
する。４）グラフＧをＧi＝（Ｖi，Ｃi，Ｅi）のようにｔ個の部分グラフＧ1，Ｇ2，．．．，Ｇtに分割する。ここにＥiはＶi内のビットノードとＣi内のチェックノードとの間で接続している辺の集合である。集合ＣJに接続している辺をＥJで表す（ＥJ＝Ｅ＼（Ｅ1∪Ｅ2∪．．．∪Ｅtに注意）。
【０１００】
これらの実施形態において、復号化フェーズを反復的に実行することによりグラフＧは特別なメッセージ受け渡しスケジュールに従い処理され、各復号化フェーズは以下の順序でグラフの辺に沿ってメッセージを交換する。
【０１０１】
ｉ＝１からｔまで
１．図５にＲCJViメッセージと表記されたＲcv個のメッセージをＥJ内の辺に沿ってチ
ェックノードｃ∈ＣJからビットノードｖ∈Ｖiへ送る。図５にＲCiViメッセージと表記された、チェックノードｃ∈Ｃiからビットノードｖ∈ＶiへのＲcv個のメッセージをゼロに設定する。全てのビットｖ∈Ｖiについて、初期ビット推定値を図５にＰViメッセージと
表記されたＰvに設定する。メッセージＲCJViが当該ステップより前に他のｔ−１個の部
分グラフＧk（ｋ≠ｉ）のためにデコーダを起動した結果である点に注意されたい。他の
部分グラフが未だ処理されていない場合、図５に示すそれらの対応メッセージＱvicJはＰviすなわちメモリから読み出されたかまたは通信チャネルから受信された推定値に設定される。これらがパンクチャードビットである場合、そのＰviはゼロである。
【０１０２】
２．何らかのスケジュールに従い（例：Ｃi内のチェックノードを連続的に辿って各チ
ェックノードについて当該チェックノードとの間でメッセージをやり取りすることにより実行される図３に記述する連続スケジュールに従い）、Ｅi内の辺に沿ってＶi内のビットノードからＣi内のチェックノードへＱvc個のメッセージを、およびＣi内のチェックノードからＶi内のビットノードへＲcv個のメッセージを送ることにより１回以上の反復を実
行する。これを図５にＱViciおよびＲCiViメッセージと表記する。
【０１０３】
３．図５にＱViCJメッセージと表記されたＱvc個のメッセージをＥJ内の辺に沿ってＶi内のビットノードからＣJ内のチェックノードへ送る。
【０１０４】
復号化は、デコーダが全てのパリティチェック制約を満たす有効な符号ワードに収束するまで、または許された復号化フェーズの最大数に達するまで続けられる。各部分グラフｉ内でのメッセージの受け渡しの停止基準も同様である。当該部分グラフ内のパリティチェック制約が全て満たされるか、または許された最大反復回数に達するまで繰り返す。一般に、許された最大反復回数は、部分グラフ毎に、またはデコーダの起動毎に変化する場合がある。
【０１０５】
ＥJの辺に沿って送られたメッセージ（図５のＲCJViメッセージおよびＱVjCJメッセー
ジ）を用いてグラフの異なる区間同士で情報を交換する。復号化を実行する間に各ステージで送られたメッセージを、メッセージ受け渡し復号化アルゴリズムの標準的な計算規則により計算することができる。例えば、ＢＰ復号化が実装されている場合、メッセージは式（４）および（５）に従い計算される。Ｍｉｎ  Ｓｕｍアルゴリズム、Ｇａｌｌａｇｈｅｒ  Ａアルゴリズム、およびＧａｌｌａｇｈｅｒ  Ｂアルゴリズム等、他のメッセージ受け渡し復号化アルゴリズムは自身の計算規則を有している。
【０１０６】
このような復号化アルゴリズムを、ＢＰ復号化を実装している各部分グラフ内で連続的にスケジュールされたメッセージ受け渡し復号化を仮定して図６に要約する。このアルゴリズムでは、ビットノードｖ∈Ｖiに対応するＱv個のメッセージだけを復号化する間の各段階において、Ｅiの辺に対応するＲcv個のメッセージおよびＥjの辺に対応するメッセージが保存される。従って、このクラスの実施形態のデコーダは、効率的な従来型デコーダにおける（｜Ｖ｜＋｜Ｅ｜）個のメッセージに対して、（ｍａｘ｛｜Ｖ1｜，｜Ｖ2｜，．．．，｜Ｖi｜｝＋ｍａｘ｛｜Ｅ1｜，｜Ｅ2｜，．．．，｜Ｅi｜｝＋｜ＥJ｜）個のメッ
セージだけを同時に保存すればよい。従って、必要なメモリは、従来型デコーダが必要とするメモリの〜１／ｔ分数である。長いＬＤＰＣ符号を実装する場合、これはデコーダの複雑度に対して大きい利点をもたらす。
【０１０７】
このクラスの実施形態による例示的なデコーダ３０の高水準模式ブロック図を図７Ａに示す。デコーダ３０は、以下のものを含んでいる。
【０１０８】
１．メモリから読み出されたかまたは通信チャネルから受信した対応ビット観測値ｙt
＝［ｙv：ｖ∈Ｖi］（ｙvはビットｖに対応する観測値）に基づいて、現在処理中である
部分グラフＧi＝（Ｖi，Ｃi，Ｅi）内のビットｖ∈Ｖiについて初期ビット推定値Ｐt＝［Ｐv：ｖ∈Ｖi］を計算する初期ＬＬＲ計算ブロック３２。
【０１０９】
２．現在処理中である部分グラフ（Ｐvメッセージとして初期化されたＱvメッセージ）内のビットノードｖ∈Ｖiに対するビット推定値を保存するメモリ領域３６を含む読み出
し／書込みメモリ３４。
【０１１０】
３．以下を含む読み出し／書込みメモリ３５
３ａ．現在処理中である部分グラフの辺集合Ｅiに対応するＲcv個のメッセージを保存
するメモリ領域３８。
【０１１１】
３ｂ．ＥJの辺に沿ってメッセージを保存するメモリ領域４０。メモリ領域４０は、ｉ
）ビットノードｖ∈Ｖi，∀ｉ’∈｛１，．．．，ｎ｝＼ｉからチェックノードｃ∈ＣJへのＱvc個のメッセージ（ｉは現在処理中である部分グラフの添え字）を保存すると共に、ii）ビットノードｖ∈Ｖiについてメモリ領域４０は最初にチェックノードｃ∈ＣJからのＲcv個のメッセージを保存し、その後で当該部分グラフを処理しているメモリ領域４０はのＱvcをチェックノードｃ∈ＣJに保存する。
【０１１２】
４．（図６に示す）メッセージの更新に関わる計算を実行する処理ユニット４２。
【０１１３】
５．  メモリ３４と処理ユニット４２との間でメッセージをルーティングするルーティング層４４。例えば、このクラスの実施形態のいくつかのサブクラスにおいて、図６の部分グラフＧ1〜Ｇtにわたるループ内で、ルーティング層４４は各プロセッサ４２に現在の部分グラフＧiの当該プロセッサ自身のチェックノードを割り当て、チェックノードの処
理はＧiの全てのチェックノードについて（または、プロセッサ４２の数と同数の、Ｇiのチェックノードについて）並列に実行される。
【０１１４】
６．符号のグラフ構造を保存する読み出し専用メモリ（ＲＯＭ）４６。メモリのアドレス指定およびルーティング層４４によるスイッチングはＲＯＭ４６のエントリに基づく。
【０１１５】
デコーダ３０は複数の処理ユニット４２を含んでいるため、メッセージの更新に関わる計算を並列に実行することができる。単一の処理ユニット４２しか備えていない別の実施形態はルーティング層４４を含んでいない。
【０１１６】
上述のように、連続的な受け渡しスケジュールは、チェックノードまたはビットノードのいずれか連続的に辿る。図７Ａのデコーダ３０はチェックノードを連続的に辿る。図７Ｂは、ビットノードを連続的に辿る同様のデコーダ３１の高水準模式ブロック図である。
【０１１７】
このクラスの実施形態によるグラフ分割の一例を図８に示す。全てのビットノードが２個のチェックノードに接続され、全てのチェックノードが４個のビットノードに接続されるように、１８個のビットノードおよび９個のチェックノードを有する規則的な二部グラフにより記述されるＬＤＰＣ符号を本例に用いる。これは長さが１８、レートが１／２のＬＤＰＣ符号である。元のグラフを図８の左側に示す。これは図１のグラフでもある。自身のビットノード、チェックノード、および辺を部分集合に分割した後のグラフを図８の右側に示す。これが同じグラフを明快さのために再構成したものに過ぎない点に注意されたい。この符号の場合、従来技術の効率的なデコーダは１８＋３６＝５４個のメッセージを保存する必要がある一方、対応するデコーダ３０は６＋８＋１２＝２６個のメッセージだけを保存すればよいため、同じ誤り訂正能力を維持しながらデコーダのメモリ複雑度が５２％減少される。
【０１１８】
図８の例のように、全ての部分グラフがトポロジー的に同一であることが好適である。この文脈において、「トポロジー的同一性」は、全ての部分グラフが同数のビットノードおよび同数のチェックノードを有し、各々のビットノードが内部チェックノードへの接続性に関して他の全ての部分グラフに対応するビットノードを有し、各部分グラフのチェックノードは、ビットノードへの接続性に関して他の全ての部分グラフに対応するチェックノードを有することを意味する。例えば図８において以下が成り立つ。
【０１１９】
ビットノード１および５が部分グラフ１の両方のチェックノードに接続し、ビットノード１１および１６が部分グラフ２の両方のチェックノードに接続し、ビットノード１３および１７が部分グラフ３の両方のチェックノードに接続していて、且つこれらのビットノードのいずれも外部チェックノード（集合ＣJのチェックノード）に接続していないため
、ビットノード１、５、１１、１３、１６および１７は対応している。
【０１２０】
残りのビットノードは、これらのビットノードの各々が同一部分グラフの１個のチェックノードに接続しているため、対応している。
【０１２１】
部分グラフの全てのチェックノードは、これらのチェックノードの各々が部分グラフのチェックノードだけに接続している自身の部分グラフの２個ビットノード、および外部チェックノードにも接続している自身の部分グラフの他の２個のビットに接続しているため、対応している。
【０１２２】
部分グラフが「トポロジー的に同一」であるために外部チェックノードに対して同一の接続性を有する必要が無い点に注意されたい。例えば、同一の外部チェックノード７に接続している部分グラフ３の２個のビットノード１５、１８はまた、部分グラフ３の同一チェックノード９にも接続しているが、同一外部チェックノード２に接続している部分グラフ１の２個のビットノード４、１２は部分グラフ１の異なるチェックノード３、８に接続している。
【０１２３】
しかし、必要ならばグリーディアルゴリズムにより任意のＬＤＰＣグラフＧを部分グラフに分割することができる。第１の部分グラフは、ビットノードの任意の集合を選択することにより構築される。第１の部分グラフのチェックノードは、それらのビットノードだけに接続するチェックノードである。第２の部分グラフは、残りのビットノードの中から任意のビットノードの集合を選択することにより構築される。無論、第２の部分グラフ内のビットノードの数が第１の部分グラフのビットノードの数に等しいことが好適である。
ここでも、第２の部分グラフのチェックノードは、第２の部分グラフのビットノードだけに接続するチェックノードである。ビットノードの任意選択は必要な回数だけ繰り返される。最後の部分グラフは選択されなかったビットノードおよびそれらのビットノードだけに接続するチェックノードを含んでいる。残りのチェックノードがＣJを構成する。
【０１２４】
上述の実施形態のクラスにおいて、ＬＤＰＣグラフＧは、各々が自身のビットノードおよびチェックノードを有するｔ個の部分グラフに加え、チェックノードだけからなる別個の部分集合ＣJに分割される。別のクラスの実施形態において、図９に示すように、Ｇは
各々が自身のビットノードおよびチェックノードを有するちょうどｔ個の部分グラフに分割される。例えば上述のグリーディアルゴリズムを用いて、最後の部分グラフ（Ｇt）は
選択されなかったビットノード、これらのビットノードだけに接続するチェックノード、および残り全てのチェックノードを含んでいる。これは、部分グラフのビットノードから分離されたビットノードの自身の部分集合に接続している第１のクラスの実施形態の集合ＣJと同等である。このクラスの実施形態において、図６のアルゴリズムは、部分グラフ
ループ内の部分グラフＧ1〜Ｇt-1だけを含め、且つ専らＧt内だけに切り離されたメッセ
ージ交換により部分グラフループを辿ることにより各復号化フェーズを終了することにより変更されている。図９にｔ＝４の場合を示す。これらの実施形態の１個の下位クラスにおいて、いくつかのビットはパンクチャードビットであり、Ｇtはこれらのビット専用で
ある。Ｇtの全てのビットはパンクチャードビットであり、全てのパンクチャードビット
はＧtのビットである。
【０１２５】
図１０は、フラッシュメモリ装置の高水準模式ブロック図である。行列に配置された複数のメモリセルＭを含むメモリセルアレイ１は、列制御回路２、行制御回路３、ｃ−ソース制御回路４、およびｃ−ｐウェル制御回路５により制御される。列制御回路２はメモリセルアレイ１のビット線（ＢＬ）に接続されていて、メモリセル（Ｍ）に保存されたデータを読み、書込み動作中のメモリセル（Ｍ）の状態を判定し、ビット線（ＢＬ）の電位レベルを制御して書込みを実行するかまたは書込みを禁止する。行制御回路３はワード線（ＷＬ）に接続されていて、ワード線（ＷＬ）の一つを選択し、読み出し電圧を印加し、列制御回路２により制御されたビット線の電位レベルと組み合わされた書込み電圧を印加し、メモリセル（Ｍ）が形成されているｐ型領域の電圧に結合された消去電圧を印加する。ｃ−ソース制御回路４は、メモリセル（Ｍ）に接続している共通ソース線を制御する。ｃ−ｐウェル制御回路５は、ｃ−ｐウェル電圧を制御する。
【０１２６】
メモリセル（Ｍ）に保存されたデータは、列制御回路２により読み出されて、入出力線およびデータ入力／出力バッファ６を介して外部入出力線へ出力される。メモリセルに保存されるプログラムデータは、外部入出力線を介してデータ入出力バッファ６に入力され、列制御回路２へ転送される。外部入出力線は、コントローラ２０に接続している。
【０１２７】
フラッシュメモリ装置を制御する命令データが、コントローラ２０に接続している外部制御線に接続している命令インタフェースに入力される。命令データは、要求されている動作をフラッシュメモリに知らせる。入力命令は、列制御回路２、列制御回路３、ｃ−ソース制御回路４、ｃ−ｐウェル制御回路５、およびデータ入力／出力バッファ６を制御する状態機械８へ転送される。状態機械８は、ＲＥＡＤＹ／ＢＵＳＹまたはＰＡＳＳ／ＦＡＩＬ等、フラッシュメモリの状態データを出力することができる。
【０１２８】
コントローラ２０は、パーソナルコンピュータ、デジタルカメラ、形態情報端末等のホストシステムに接続しているかまたは接続可能である。メモリアレイ１にデータを保存または読み出す等の命令を発行し、且つそのようなデータを提供または受け取るのはホスト側である。コントローラ２０はそのような命令を、命令回路７により解釈および実行可能な命令信号に変換する。コントローラ２０はまた、通常はメモリアレイに書き込まれるか
または読み出されているユーザーデータ用のバッファメモリを含んでいる。典型的なメモリ装置は、コントローラ２０、各々がメモリアレイおよび付随する制御、入出力および状態機械回路を含む１個以上の集積回路チップ２２を含む１個の集積回路チップ２１を含んでいる。このトレンドは無論、そのような装置のメモリアレイとコントローラ回路を１個以上の集積回路チップ上に集積することである。メモリ装置は、ホストシステムの一部として埋め込まれていても、またはホストシステムの嵌め込みソケットに着脱自在に挿入可能なメモリカードに含まれていてもよい。そのようなカードはメモリ装置全体を含んでいても、またはコントローラとメモリアレイが付随する周辺回路と共に別個のカードで提供されてもよい。
【０１２９】
図１１は図１０の一部の拡大図であり、コントローラ２０が、ホストから１個以上の符号ワードとして受信したユーザーデータを符号化するエンコーダ５２、符号ワードを（または符号ワードのいずれかのビットがパンクチャードビットである場合その非パンクチャードビットだけを）をメモリセル配列１に保存するよう命令回路７に指示すると共に、保存された符号ワード（またはパンクチャードビットの場合はその保存された部分）をメモリセルアレイ１から取り出すよう命令回路７に指示する回路５４、および回路５４により取得された符号ワードの表現を復号化するデコーダ３０を含んでいることを示す。あるいは、コントローラ２０はデコーダ３０の代わりにデコーダ３１を含んでいてもよい。
【０１３０】
本明細書に開示する方法およびデコーダは主としてデータ記憶システムで用いることを意図しているが、これらの方法およびデコーダはまた通信システム、特に高周波を大幅に減衰させる媒体を介した波伝播に依存する通信システムにも適用できる。そのような通信は本質的に遅く且つノイズが多い。そのような通信の一例として、沿岸局と水面下の潜水艦との間の無線通信がある。
【０１３１】
図１２は、送信器１１０、チャネル１０３、および受信器１１２を含む通信システム１００の高水準模式ブロック図である。送信器１１０はエンコーダ１０１および変調器１０２を含んでいる。受信器１１２は復調器１０４およびデコーダ３０を含んでいる。エンコーダ１０１はメッセージを受信して対応する符号ワードを生成する。変調器１０２は、生成された符号ワードにＢＰＳＫ、ＱＰＳＫまたは多値ＱＡＭ等のデジタル変調を施し、その結果得られた変調信号をチャネル１０３経由で受信器１２に送信する。受信器１１２において、復調器１０４はチャネル１０３から変調信号を受信し、受信した変調信号に対しＢＰＳＫ、ＱＰＳＫまたは多値ＱＡＭ等のデジタル復調を施す。デコーダ３０は、その結果得られた上述のような元の符号ワードの表現を復号化する。あるい、受信器１１２はデコーダ３０の代わりにデコーダ３１を含んでいてもよい。
【０１３２】
ここでトラッピング集合の問題に注目すれば、ＬＤＰＣ復号化におけるトラッピング集合を克服する２種類の従来方法がある。
【０１３３】
１．トラッピング集合無しでＬＤＰＣ符号を設計することによりトラッピング集合を回避する。
【０１３４】
２．復号化を行う間、アルゴリズム手段によりトラッピング集合を克服する。
【０１３５】
第１の種類の従来方法には以下の短所がある。
【０１３６】
トラッピング集合が明確に定義されておらず、且つ長いＬＤＰＣ符号が極めて複雑であるため、エラーフロアが低いグラフを設計して、エラーフロアが低いことを証明するのは、広範囲なシミュレーション要する困難なタスクになる恐れがある。更に、そのようなアプローチにより、符号化／復号化スキームにおける実装の複雑度、復号化の速度および柔
軟性等、他の態様に関して良好な特性を示すある種のＬＤＰＣ符号の利用が除外される恐れがある。
【０１３７】
復号化を行う間にトラッピング集合を克服するアルゴリズム的方法を用いる第２の種類の従来方法に関しては以下が言える。
【０１３８】
文献においていくつかの方法が提案されている。
１．平均化。
２．通知された動的スケジューリング
３．トラッピング集合を識別して、それを回避すべくカスタマイズされた積和アルゴリズムを設計する。
【０１３９】
１．平均化方法は、ビット値に対する更新アルゴリズムを用いる。更新は、先行する反復の結果だけでなく、いくつかの反復の結果の平均にも基づいている。算術平均、幾何平均、および重み付き算術幾何平均を含むいくつかの平均化方法が提案されている。
【０１４０】
２．通知された動的スケジューリング。この方法では、毎回の反復で全てのチェックノードが更新される訳ではなく、グラフ内のメッセージの現在状態に基づいて更新される次のチェックノードを選択する。チェックノードは、当該チェックノードの更新が復号処理にとってどの程度有用であるかを測定する尺度に基づいて選択される。
【０１４１】
両方法共にエラーフロアの向上を実現することができるが、平均化のために先行メッセージの履歴を保存する必要があり、通知された動的スケジューリングは高い計算量をもたらすため、アルゴリズムに付随する複雑度が高い。
【０１４２】
第３の種類の方法は、トラッピング集合の識別および各グラフ用に特化されたアルゴリズムを必要とするため、特に同一アプリケーションで複数のＬＤＰＣ符号が考慮する場合に、特定のシナリオにこれらを使用するのは限界がある。
【０１４３】
現在述べている革新的な方法によれば、符号ワードの復号化は２段階のフェーズで実行される。第一フェーズを行う間、従来の復号化はＬＤＰＣ符号により定義されるグラフに沿って実行される。
【０１４４】
トラッピング集合の存在が疑われ、復号処理が妥当な符号ワード（すなわち全てのパリティチェック式を満たす符号ワード）に収束することが阻害される場合、復号化の第２フェーズに移行する。このフェーズでは、当該符号のグラフのノードに関連付けられた値のいくつかが変更される。
【０１４５】
トラッピング集合が存在することは少数のビットが正しく収束することに失敗していることを示唆するため、トラッピング集合の存在を識別することができるのは、連続的に復号化を反復する間に少数を除く全てのビットが安定しているか、または他の全てのパリティチェック式が満たされる一方で少数のパリティチェック式が失敗する場合である。例えば、上述のように分割されたグラフの部分グラフのうち１個だけのパリティチェック式が失敗したならば、当該部分グラフはトラッピング集合であるかまたは含んでいることが疑われる。トラッピング集合の存在を示唆する別の兆候は、１パーセント以下のパリティチェック式だけが一貫して失敗していることである。例えば、シンドロームＨ・ｖ’（ｖ’は推定されたビットの列ベクトル）のいくつかの要素が非ゼロであって、連続的な２回の反復において同一であることは、トラッピング集合の存在を示唆する。
【０１４６】
このような変更の二つの例は以下の通りである。
【０１４７】
１．チェックノードの値Ｒcvをゼロにリセットする。
【０１４８】
２．ビット確率の弱い値Ｑvを切り捨てる、すなわちビット確率に対応する弱い値Ｑvの大きさを所定の値、典型的には１０〜１６の間の値に制限する。
【０１４９】
この方法論の背景にある動機は、反復処理を行う間に誤ったビットが高い確率を実現し、且つ誤った結果（パリティチェック式に対応するノードで含まれる）の信頼度もまた高い場合に小さいトラッピング集合に起因して収束の失敗が生じることである。このような状況では、更に反復しても、誤ったビットに対してなされた強い決定（好適には、弱い値の符号として実装される）は変わらない。
【０１５０】
しかし、デコーダが、小さいトラッピング集合に含まれない全てのビットが既にそれらの正しい値に設定されている初期状態で動作を開始していた場合、符号ワードを正しく復号化する確率は極めて高い。
【０１５１】
メッセージＲcvの値をゼロにリセットすることにより、トラッピング集合に含まれない全てのビットが正しい状態に戻る。
【０１５２】
この状況において、正しく復号化されているビット（大部分のビットはこの段階にある）に関連するメッセージＱvcおよびＲcvは急速に高い信頼度値まで上昇する一方、トラッピング集合内のビットに関するメッセージは遅く上昇するため、正しいメッセージからのトラッピング集合内のビットに対応する値に対してより大きな影響がある。そのような手順は、トラッピング集合内のビットの値を訂正する際に有用である。
【０１５３】
この手順は、従来のＬＤＰＣ復号化アルゴリズムに最小限の複雑度が加わるに過ぎない。
【０１５４】
一実施形態において、本アルゴリズムは限られた回数の反復について復号化を実行する。収束に失敗した場合、本アルゴリズムは、Ｒcvメッセージのいくつかまたは全て等、特定の変数をゼロに設定するステップを追加し、ついで従来の復号化を続ける。
【０１５５】
別の実施形態では、限られた回数の反復を実行した後で、Ｑv値のいくつかまたは全て
等、いくつかの変数に対して切捨て動作を追加し、次いで本アルゴリズムは従来の復号化を続ける。
【０１５６】
両方のアルゴリズムは極めて簡単であって、低い複雑度で実装でき、更に、従来の高い複雑度且つ特化された方法とは対照的に一般的なＬＤＰＣグラフに適用できる。
【０１５７】
弱い値Ｑvの切り捨ては、以下のように、各種の非収束基準および遅い収束基準に対し
て有用である。
【０１５８】
１．所定回数の反復実行後、または所定時間経過後、または所定回数のメッセージ交換後に、所定のシンドロームの要素が非ゼロである場合。要素の所定個数の典型的な値は１である。
【０１５９】
２．連続的な２回の反復においてシンドロームの要素の高々所定の個数が非ゼロのままである場合。
【０１６０】
３．連続的な２回の反復においてシンドロームの非ゼロ要素の数の差違が所定の限度を下回り、遅い収束を示唆する場合。
【０１６１】
４．所定回数の反復（通常は１回の反復）の前後でビット推定値間のハミング距離が所定の限度を下回り、遅い収束を示唆する場合。
【０１６２】
上述のように非収束および遅い収束を考慮すべく図７Ａ、７Ｂのデコーダ３０、３１は容易に変更される。具体的には、上述の基準に従い非収束または遅い収束を検出すべくルーティング層４４を変更し、ルーティング層４４により判定された非収束または遅い収束に応答して、Ｒcv値のいくつかまた全てをゼロにする、および／またはＱv値のいくつか
または全てを切り捨てるべくプロセッサ４２を修正する。
【０１６３】
以上は、符号ワードの表現を復号化する方法、これらの方法を使用するデコーダ、自身のコントローラがこのようなデコーダを含むメモリ、および自身の受信器がこのようなデコーダを含む通信システムの限定された数の実施形態を記述したものである。本方法、デコーダ、メモリ、およびシステムの多くの変型、変更、およびその他の応用が行えることが理解されよう。
【図１】
0005593312.tif 000011
【図２】
0005593312.tif 000012
【図３】
0005593312.tif 000013
【図４】
0005593312.tif 000014
【図５】
0005593312.tif 000015
【図６】
0005593312.tif 000016
【図７Ａ】
0005593312.tif 000017
【図７Ｂ】
0005593312.tif 000018
【図８】
0005593312.tif 000019
【図９】
0005593312.tif 000020
【図１０】
0005593312.tif 000021
【図１１】
0005593312.tif 000022
【図１２】
0005593312.tif 000023