JP2012050008A

JP2012050008A - 誤り検出訂正方法および半導体メモリ装置

Info

Publication number: JP2012050008A
Application number: JP2010192697A
Authority: JP
Inventors: Kenji Sakagami; 健二坂上
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2010-08-30
Filing date: 2010-08-30
Publication date: 2012-03-08
Also published as: US20120054580A1; CN102386931A; US9015548B2

Abstract

【課題】効率のよい誤り検出訂正方法を提供する。
【解決手段】実施形態の誤り検出訂正方法は、低密度パリティ検査符号の検査行列のタナーグラフに対応して設定されたチェックノード２０からチェックノード２０に接続されている複数のビットノードに向け信頼度αを伝搬する処理と、ビットノードからビットノードに接続されている複数のチェックノード２０に向け信頼度βを伝搬する処理と、を繰り返す、サムプロダクトアルゴリズムを用いた復号処理において、チェックノード２０が２ビット以上のパリティを備える。
【選択図】図５

Description

本発明の実施の形態は、ＬＤＰＣ符号による誤り検出訂正方法、および前記誤り検出訂正方法を行う半導体メモリ装置に関する。

半導体メモリ等のストレージ分野での高密度記録等のために、デジタルデータの誤り訂正符号に関する開発が行われている。誤り訂正符号は、代数系の誤り訂正方式と確率にもとづく反復計算による誤り訂正方式とに大別できる。そして、後者に属する低密度パリティ検査符号（Ｌｏw Ｄensity Parity Check coｄes、以下、「ＬＤＰＣ符号」という）はシャノン限界に迫る、優れた性能が報告されている。そして、ＬＤＰＣ符号化データはサムプロダクトアルゴリズムを用いることにより、比較的少ない回路規模で並列処理を行うことができる。

ＬＤＰＣ符号は半導体メモリ装置等への応用が進んでいるが、更に効率の良い誤り検出訂正方法が求められていた。

特開２００８−２１９５２８号公報

本発明の実施形態は、効率のよい誤り検出訂正方法、および前記誤り検出訂正方法を用いた半導体メモリ装置を提供することを目的とする。

上記目的を達成すべく、本発明の実施形態の誤り検出訂正方法は、低密度パリティ検査符号の検査行列のタナーグラフに対応して設定されたチェックノードからチェックノードに接続されている複数のビットノードに向け信頼度αを伝搬する処理と、ビットノードからビットノードに接続されている複数のチェックノードに向け信頼度βを伝搬する処理と、を繰り返す、サムプロダクトアルゴリズムを用いた復号処理において、チェックノードが２ビット以上のパリティを備える。

また本発明の別の実施形態の半導体メモリ装置は、低密度パリティ検査符号の検査行列のタナーグラフに対応して設定されたチェックノードからチェックノードに接続されている複数のビットノードに向け信頼度αを伝搬する処理と、ビットノードからビットノードに接続されている複数のチェックノードに向け信頼度βを伝搬する処理と、を繰り返す、サムプロダクトアルゴリズムを用いた復号処理において、チェックノードが２ビット以上のパリティを備えた誤り検出訂正方法を行う。

検査行列Ｈ１を説明するための説明図である。タナーグラフＧ１を説明するための説明図である。タナーグラフＧ２の場合の行処理および列処理を説明するための説明図である。第１実施形態の半導体メモリシステムの構成図である。第１実施形態の誤り検出訂正方法における補助チェックノードを説明するための説明図である。第１実施形態の変形例の誤り検出訂正方法における補助チェックノードを説明するための説明図である。第１実施形態の誤り検出訂正方法における復号処理の流れを示すフローチャートである。第２実施形態の誤り検出訂正方法におけるブロック分割による補助パリティを説明するための説明図である。第３実施形態の誤り検出訂正方法における通常チェックノードのパリティビットを説明するための説明図であり、図９（Ａ）は送信データを、図９（Ｂ）は受信データを示している。第３実施形態の誤り検出訂正方法における補助チェックノードの補助パリティビットを説明するための説明図であり、図１０（Ａ）は送信データを、図１０（Ｂ）は受信データを示している。第３実施形態の変形例の誤り検出訂正方法における補助チェックノードの補助パリティビットを説明するための説明図である。

＜ＬＤＰＣ符号＞
最初にＬＤＰＣ符号について説明する。ＬＤＰＣ符号は、非常に疎な検査行列、すなわち、行列内の非零要素数が少ない検査行列により定義される線形符号であり、タナーグラフで示すことができる。そして、誤り訂正処理は、タナーグラフ上で接続された符号語の各ビットに対応したビットノード（ビットノード）と各パリティ検査式に対応したチェックノードとの間で局所的に推論した結果を、やりとりしながら更新していくことに相当する。

図１に、（６、２）ＬＤＰＣ符号における、行重みｗｒ＝３、列重みｗｃ＝２の検査行列Ｈ１を示す。なお、（６、２）ＬＤＰＣ符号とは、符号長が６ビット、情報長が２ビットのＬＤＰＣ符号のことである。

そして、図２に示すように、検査行列Ｈ１をタナーグラフＧ１で示すと、ビットノードは検査行列Ｈの列に対応し、チェックノードは検査行列Ｈの行に対応している。そして検査行列Ｈ１の要素の中で、「１」であるノード間をエッジで結ぶことによりタナーグラフＧ１が構成されている。例えば、検査行列Ｈ１の第２行第５列の、丸で囲った「１」は、タナーグラフＧ１の太線で示すエッジに対応している。そして、検査行列Ｈ１の行重みｗｒ＝３は、ひとつのチェックノードと接続されているビットノードの数、すなわちエッジ数３に対応し、検査行列Ｈの列重みｗｃ＝２は、ひとつのビットノードと接続されているチェックノードの数、すなわちエッジ数２に対応している。

ＬＤＰＣ符号を用いた復号処理においては、（以下、単に「ＬＤＰＣにおいては」ともいう）、はタナーグラフのエッジに割り当てられた信頼度（確率）情報をノードにおいて反復的に更新することで実行される。信頼度情報には、チェックノードからビットノードへの確率情報（以下、「外部値」または「外部情報」ともいい、記号「α」で表示する）と、ビットノードからチェックノードへの確率情報（以下、「事前確率」、「事後確率」、単に「確率」、または「対数尤度比（ＬＬＲ）」ともいい、記号「β」または「λ」で表示する）の２種類がある。信頼度更新処理は、行処理と列処理とからなり、行処理と列処理とを１回ずつ実行した単位のことを１イタレーション（ラウンド）処理と呼び、復号処理はイタレーション処理を繰り返す反復処理により行われる。

以上の説明のように、外部値αとは、ＬＤＰＣ復号処理のときの、チェックノードからビットノードへの確率情報であり、確率βとはビットノードからチェックノードへの確率情報であり、当業者にとり周知の用語である。

以下、図３（Ａ）〜図３（Ｄ）に示すタナーグラフＧ２の一部を用いて、行処理および列処理について説明する。最初に、図３（Ａ）および図３（Ｂ）を用いて、ビットノード処理（列処理）について説明する。あるビットノード、例えばビットノード３、に対応する入力された符号語ビットの初期信頼度であるＬＬＲ、をλ（３）とし、このビットノード３へのチェックノードからの確率を、α（ｊ、３）とする。ここで、ｊはビットノード３に接続しているチェックノード番号を示す。

そして、ビットノード３は、α（１、３）に対応するエッジのチェックノードすなわち、チェックノード１に対して、以下の（式１）で表される計算を行う。

β（３、１）＝ λ（３）＋α（２、３）・・・（式１）

同様に、ノード番号ｊのチェックノードに対して、以下の（式２）で表される計算を行う。

β（３、ｊ）＝ λ（３）＋Σα（ｋ、３）・・・（式２）

ここで、Σはビットノード３に接続しているチェックノードの中で、ｋ＝ｊ以外の総和を意味する。

以上の計算を全てのビットノードに対して行い、以下の（式３）で表されるβ（ｉ、ｊ）を計算する。なお、ここで、符号長をＮ、ノード番号を、ｉとすると、ｉ＝１〜Ｎである。また、Σはビットノードｉに接続しているチェックノードの中で、ｋ＝ｊ以外の総和を意味する。

β（ｉ、ｊ）＝ λ（ｉ）＋Σα（ｋ、ｉ）・・・（式３）

次に、図３（Ｃ）および図３（Ｄ）を用いて、チェックノード処理（行処理）について説明する。あるチェックノード、例えばチェックノード１、へのメッセージである外部情報を、β（ｋ、１）としたとき、このチェックノードはβ（１、１）に対応するエッジのビットノードであるビットノード１に対して以下の（式４）で表されるα（１、１）を計算する。

α（１、１）＝ｓｉｇｎ（Πβ（ｍ、１））×ｍｉｎ（｜β（ｍ、１）｜）・・・（式４）

ただし、ｋはこのチェックノード１に接続されているビットノード番号である。そして、ｍは「２」から「３」の中から選択される。ここで、ｓｉｇｎ（Πβ（ｍ、１））は、β（ｍ、１）を、ｍ＝２から３、まで乗算した結果の符合（「＋１」あるいは「−１」）を意味する。また、｜β（ｍ、１）｜は、β（ｍ、１）の絶対値であり、ｍｉｎは複数の｜β（ｍ、１）｜の中から最小値を選択する関数である。

同様にして、α（１、ｉ）についても、以下の（式５）を使って算出する。

α（１、ｉ）＝ｓｉｇｎ（Πβ（ｍ、１））×ｍｉｎ｛｜β（ｍ、１）｜｝・・・（式５）

ただし、ｉはチェックノード１に接続しているビットノード番号であり、図１（Ｂ）のタナーグラフの例では、「１」、「２」、「３」である。また、ｍはチェックノード１に接続したビットノードの中で、ｍ＝ｉ、以外とする。

以上の計算を全てのチェックノードに対して行い、α（ｊ、ｉ）を以下の（式６）を使って計算する。

α（ｊ、ｉ）＝ｓｉｇｎ（Πβ（ｍ、ｊ））×ｍｉｎ（｜β（ｍ、ｊ）｜）・・・（式６）

ただし、ｍはチェックノードｊに接続したビットノードの中で、ｍ＝ｉ、以外とする。

そして、反復復号では、以上に示したビットノード処理とチェックノード処理とを１回ずつ実行した１イタレーション処理（１ラウンド）毎に、以下の（式７）によって、事後確率Ｐｂ（ｉ）を求める。

Ｐｂ（ｉ）＝λ（ｉ）＋Σα（ｋ、ｉ）・・・（式７）

ここで、i＝１〜Ｎであり、Ｎは符号長である。そして、Σはビットノードｉに接続された全ての和である。

この事後確率値（一時推定語）Ｐｂを基にビット判定、すなわち、当該ビットが、「０」または「１」のいずれであるかが硬判定される。そして、この硬判定結果を使用して、ＬＤＰＣ符号の最終パリティチェックを行い、誤りないことが確認された時点で反復処理を終了する。以上が、ＬＤＰＣ符号の反復復号方法である。

そして既に説明したように、メッセージ伝達アルゴリズムとして、サムプロダクトアルゴリズムを用いた、ビットノードおよびチェックノードにおける信頼度更新アルゴリズムでは、並列処理による復号処理を行うことができる。

ＬＤＰＣでは、チェックノードに接続するビットノードのパリティチェックがパスしたら、そのビットノードの信頼度αを上げ、パスしなければ信頼度αを下げる処理を行う。ここで、従来のＬＤＰＣ符号による誤り検出訂正方法においては、チェックノードにおける誤り検出には、パリティビットが用いられていた。パリティビットは最も単純な誤り検出符号であり、巡回冗長検査（ＣＲＣ）の特殊ケースである１ビットＣＲＣ（ＣＲＣ１）であり、多項式（ｘ＋１）から生成される。

パリティビットは奇数個のビットが変化した場合には、誤りが発生したことを検出できる。しかし、パリティビットによる誤り検出検査は１以上の奇数誤り検出能力しか備えていない。よって、同一チェックノードに接続された複数ビットノードで２以上の偶数誤りが発生すると、パリティ検査が誤ってパスするため、ビットノードに対して正しい信頼度の更新ができないという構造的問題があった。以後、この現象を「誤行処理」と呼ぶ。

誤行処理のため、ＬＤＰＣでは、複数ビット誤りの分布パターンによっては、復号処理時間が長くなったり、最悪の場合、復号処理が収束しなかったりする。検査行列の行数を増やしてチェックノードを増やすことにより、チェックノードにおける誤り検出精度を上げること、すなわち誤行処理の発生を抑制することは可能である。しかし検査行列の行数を増やすと、それに比例して復号時間が増大するとともに、チェックノード用の変数格納メモリ容量が増大してしまう。

＜第１実施形態＞
以下、本発明の第１実施形態の誤り検出訂正方法および半導体メモリ装置について説明する。最初に、図４を用いて本発明の第１実施形態の半導体メモリ装置であるメモリカード３の構成を説明する。

図４に示すように、メモリカード３はパソコンまたはデジタルカメラ等のホスト４から受信したデータを記憶し、記憶したデータをホスト４に送信する記憶媒体である。メモリカード３は、半導体メモリ部（以下、単に「メモリ部」ともいう。）１３と、誤り検出訂正部１５を具備したメモリコントローラ２とを有する。メモリ部１３は、ＮＡＮＤ型フラッシュメモリから構成されており、単位セルである多数のメモリセル１３Ｄが、ビット線１３Ｅ等で接続された構造を有する。なお、本実施の形態としての半導体記憶装置はホストの内部に収納されホストの起動データ等を記憶する、いわゆるエンベデッドタイプの記憶装置であってもよく、または半導体ディスク：ＳＳＤ(Solid State Ｄrive)等の形態であってもよい。あるいは半導体メモリ装置とホスト４とが、例えば携帯音楽プレーヤであるＭＰ３プレーヤ等のメモリシステム１を構成していてもよい

そして、メモリコントローラ２は、バス１７を介して接続された、ＲＯＭ１０と、ＣＰＵコア１１と、ＲＡＭ１８と、ホストＩ／Ｆ（インターフェイス）１４と、誤り訂正（ＥＣＣ：Errｏｒ Correcting Coｄe）部１５と、ＮＡＮＤＩ／Ｆ（インターフェイス）１６と、を有する。

メモリコントローラ２は、ＣＰＵコア１１を用いて、ホストＩ／Ｆ１４を介してホスト４とのデータ送受信を、ＮＡＮＤＩ／Ｆ１６を介してメモリ部１３とのデータ送受信を行う。またメモリコントローラ２は、書き換え回数の制限を含めたメモリ部１３のアドレス管理をＣＰＵコア１１で実行されるＦＷ（Firm Ware）で実現している。また、ホスト４からのコマンド入力に応じたメモリカード３全体の制御もＦＷで実行される。ＲＯＭ１０には、メモリカード３の制御プログラム等が記憶されており、ＲＡＭ１８には、アドレス管理で必要となるアドレス変換デーブル等が記憶される。

ＥＣＣ部１５は、データ記憶時に誤り訂正符号を生成し付与する符号化器１２と、データ読み出し時に、読み出された符号化データを復号する誤り検出訂正部１８とを有する。本実施の形態のＥＣＣ部１５は、確率にもとづく反復計算により復号処理される誤り訂正符号である低密度パリティ検査符号を用いる。

すなわち、ＥＣＣ部１５は、ＬＤＰＣ符号の検査行列のタナーグラフに対応して設定されたチェックノードからチェックノードに接続されている複数のビットノードに向け信頼度αを伝搬する処理と、ビットノードからビットノードに接続されている複数のチェックノードに向け信頼度βを伝搬する処理と、を繰り返す、サムプロダクトアルゴリズムを用いた復号処理を行う。

そして、ＥＣＣ部１５は、チェックノードの誤り検出能力が、従来の誤り検出訂正方法におけるパリティビットによる誤り検出能力よりも高い。例えば、図５に示すように、ＥＣＣ部１５のチェックノード２０は、パリティビットによるチェックを行う通常チェックノード２１と、パリティビットとは異なる第２のパリティによるチェックを行う補助チェックノード２２と、を有する。

すなわち、それぞれのチェックノード２０が、本来のＬＤＰＣのパリティ（第１のパリティ／パリティビット／１ビットＣＲＣ／ＣＲＣ１）による誤り検出機能を有する通常チェックノード２１に加えて、通常チェックノード２１とは独立した誤り検出機能を有する補助チェックノード２２をＥＣＣ部１５は有する。以下、補助チェックノード２２で用いるために、符号化し生成するパリティを補助パリティ（第２のパリティ）と呼ぶ。

なお、ｎ個（ｎは２以上の整数）通常チェックノード２１を１つの単位として第２のパリティを作成した補助チェックノード２２を有することが好ましい。例えば図６に示す変形例のように、２個の通常チェックノード２１を１つの単位として第２のパリティを作成した補助チェックノード２２を有することが好ましい。

なお、補助パリティはＬＤＰＣの符号化範囲に含めても良いし、含めなくともよく、システムの構成要件に応じて柔軟に決定すればよい。以下の説明ではＬＤＰＣパリティには含めることとする。補助パリティをＬＤＰＣパリティに含めることで補助パリティ自身が誤った場合でも、ＬＤＰＣの本来の復号機能で、補助パリティビットの誤りを訂正できる。

既に説明したように、従来のＬＤＰＣのチェックノード（通常チェックノード）におけるパリティチェックはパリティビットを用いているために、１ビット以上の奇数ビット誤りしか検出できない。これに対して本実施形態の誤り検出訂正方式では、通常のＬＤＰＣパリティ（パリティビット）を補完するための補助符号化（第２のパリティ）を有し、２ビット以上の偶数誤りが検出可能な場合がある。

更に第２のパリティとして、誤り検出だけでなく、誤り訂正可能な符号を用いてもよい。第２のパリティは、例えば、誤り検出ビット数ｔ＝２以上のＣＲＣ符号（ＣＲＣ２、３、４、５、６、７、・・・３２、・・・）、誤り訂正シンボル数ｔ＝２以上のハミング符号、ＢＣＨ符号、またはＲＳ符号等の通常符号化方式から選択することができる。

後述するように、第２のパリティが誤り訂正能力を有する場合には、補助チェックノード２２のチェック結果に応じて、チェックノードにおいて誤り訂正処理を行うことができる。

次に、図７を用いて、本実施形態の誤り検出訂正方法を用いるＥＣＣ部１５の動作の流れについて説明する。

＜ステップＳ１０＞データ受信
メモリ部１３に記憶されていた符号化データが、ＮＡＮＤＩ／Ｆ１６を介してＥＣＣ部１８の誤り検出訂正部１５が受信される。

＜ステップＳ１１＞初期ＬＬＲ値受信
誤り検出訂正部１５の初期ＬＬＲ算出部（不図示）が、ＲＯＭ１０等に記憶されていた尤度比テーブル等をもとに符号化データから初期ＬＬＲ（事前確率β）を算出する。

＜ステップＳ１２＞硬判定
ＬＬＲをもとに、硬判定が行われ、一時推定語が生成される。

＜ステップＳ１３＞最終パリティチェック
誤り検出訂正部１５は、一時推定語を用いて最終パリティチェックを行う。

＜ステップＳ１４＞最終パリティチェックＯＫ？
誤り検出訂正部１５は、最終パリティチェックの結果、誤りがないことが確認された場合（Ｙｅｓ）には、ステップＳ１５において、復号データをホストＩ／Ｆ１４を介してホスト４に出力し、処理は終了する。

＜ステップＳ１６＞初期化
誤り検出訂正部１５は、最終パリティチェックの結果、誤りがあった場合（Ｓ１４：Ｎｏ）には、初期ＬＬＲをもとに、イタレーション処理を開始する。

＜ステップＳ１７＞チェックノード処理（行処理）／ビットノード処理（列処理）
ビットノードから接続されているチェックノードに事前確率βが送信され、チェックノードは、受信した確率の積を算出し接続されているビットノードに外部情報（信頼度）αとして送信する。

チェックノードでは、接続されているビットノードに外部情報αが送信され、ビットノードは受信した確率の積を算出し接続されているチェックノードに、事後確率βとして送信する。

１ラウンドの処理が完了すると、ステップＳ１２において硬判定処理が行われ、更にステップＳ１３において最終パリティチェックが行われ、ＯＫの場合には処理は完了する。ＮＧの場合には、ステップＳ１８の処理が繰り返し行われる。

ここでは、補助チェックノードにおける補助符号化方式にＣＲＣを採用した場合のチェックノード処理について説明する。なお、ＣＲＣｔとは、ｔビットＣＲＣを意味する。事前/事後確率をβ、外部情報をαとすると、ＬＤＰＣパリティ（第１のパリティ）と補助パリティ（第２のパリティ）との両方の結果にもとづいて、αに加減算する値Mを変更する。

すなわち、通常チェックノードおよび補助チェックノードのチェック結果に応じて、接続されている複数のビットノードへ伝搬する信頼度αを増減する。

なお、すでに説明したように、従来のＬＤＣＰでは、αに加減算する値Mは、β最小値（βｍ）の絶対値｜βｍ｜に固定されていた。これに対して本実施形態（変形例）のＬＤＰＣでは、Mは下記のように決定される。

実施の形態の場合（ｎ＝１）では、補助パリティ判定結果をそのまま利用してαを更新する。
変形例の場合（ｎ＞１）では、ｎ＝１の場合に比べると、補助パリティ判定結果の信頼度が低下しているので、その信頼度に応じてαを更新する。

以下、行処理でＬＤＰＣパリティチェックと補助パリティチェック（ＣＲＣチェック）を同時実行した場合のＭ値の決定例を示す。

＜ＣＲＣ、ｎ＝１（実施形態）＞
（ケース１）ＬＤＰＣパリティ（第１のパリティ）ＯＫ、補助パリティ（第２のパリティ）ＯＫ
⇒｜α｜にM＝Ｈ×｜βｍ｜を加える。Ｈは補正係数であり、補助パリティの精度に応じて値を変える。例えば、ＣＲＣ３の場合Ｈ＝２．０とし、ＣＲＣ４の場合Ｈ＝３．０とする。すなわち、信頼度αを増加する。

（ケース２）ＬＤＰＣパリティＯＫ、補助パリティＮＧ
⇒｜α｜にM＝｜βｍ｜を加える。補助パリティＮＧの原因が検査対象ビットでない可能性があるので、従来のＬＤＰＣと同じ処理を施す。

（ケース３）ＬＤＰＣパリティＮＧ
⇒｜α｜からM＝｜βｍ｜を引く。すなわち、信頼度αを減少する。

なお、オプション（変形例）として、補助パリティの検出精度を高くした場合、例えば補助パリティ４ビット以上の場合には、パスしたチェックノードに接続されたビットノードの信頼度｜α｜を一律に最大値に設定してもよい。

＜ＣＲＣ、ｎ＞１（変形例）＞
（ケース１）ＬＤＰＣパリティＯＫ、補助パリティＯＫ
⇒｜α｜にM＝Ｈ×｜βｍ｜を加える。すなわち、信頼度αを増加する。Ｈは補正係数で、補助パリティの精度とｎに応じて決定する。例えば、ｎ＝２、ＣＲＣ３の場合Ｈ＝１．６、ｎ＝２、ＣＲＣ４の場合Ｈ＝１．８、ｎ＝３、ＣＲＣ３の場合Ｈ＝１．２、ｎ＝３、ＣＲＣ４の場合Ｈ＝１．４とする。

（ケース２）ＬＤＰＣパリティＯＫ、補助パリティＮＧ
⇒｜α｜にM＝｜βｍ｜を加える。すなわち、補助パリティＮＧの原因が検査対象ビットでない可能性があるので、従来と同じ処理を施す。

ＣＲＣの誤り検出可能ビット数ｔを大きくし、かつｎ＝１（行列毎に補助パリティを付加）とすると、誤行処理の発生確率が下がるので、従来のＬＤＰＣの欠点を大幅に改善できる。その代わり、補助パリティのビット数が増え実効的な符号化率が低下する。例えば、NANＤフラッシュメモリのページにおけるデータに対するパリティの占める割合が増える。このため、ｎとtとは、訂正能力強化と実効的符号化率とのトレードオフの関係で決定される。

ここで誤り訂正機能を備える符号（ハミング符号、ＢＣＨ符号、ＲＳ符号等）により、補助符号化した場合は、誤り検出機能だけでなく、誤り訂正機能を使ってもよい。誤り検出機能のみを使う場合は、ＣＲＣパリティと同様に処理すればよい。例えばＢＣＨ符号で補助符号化を実施した場合、ＬＤＰＣの復号処理と連動させてＢＣＨの誤り訂正処理を実行し、ＬＤＰＣの誤り訂正処理を補助してもよい。例えば、ＢＣＨの誤り訂正処理とＬＤＰＣと誤り訂正とを並列処理させる実装状態では、ＢＣＨの誤り訂正が成功したら、ＬＤＰＣ処理に不整合の起きないタイミング（例えばＬＤＰＣの１回の行処理/列処理が終了する１ラウンド処理終了時）に、ＬＤＰＣ復号対象データをＢＣＨで訂正したデータに更新すればよい。

以上の説明のように、チェックノードが、パリティビットより誤り検出能力が高い、２ビット以上のパリティを有する実施形態のＬＤＰＣ誤り検出訂正方法は、誤行処理の発生が小さいため、効率がよい。すなわち、通常チェックノードに加えて補助チェックノードを有し、チェックノード処理が２ビット以上のパリティを有する本実施形態の誤り検出訂正方法は、誤行列処理発生確率を下げることができる。

また、補助チェックノードが２ビット以上のパリティ有する場合、例えば４ビット以上の強力な補助パリティを有する場合は、補助パリティ検査をパスした補助チェックノードに接続するビットノードの信頼度を一律に最大値にすることで、復号時間を更に短縮し効率を上げることもできる。なおチェックノードのビット数は、増加すると符号化率が低下するので、例えば１０２４ビット以下が好ましい。

以上の説明のように、本実施形態のＬＤＰＣ符号によるＥＣＣ部は、ｎ個（ｎは１以上の整数で好ましくは２以上）のチェックノード毎に補助チェックノード２２を設けるもので、補助チェックノード２２において、ｎ個のチェックノードに接続するビットノードのｔシンボル（ｔ＝２以上の整数）誤り検出機能を備え、補助チェックノード２２のパリティチェック結果に応じて、ＬＤＰＣの演算処理内容を変更する。すなわち、チェックノード２０に２ビット以上のパリティを持たせることで、チェックノード処理において２ビット以上の偶数誤り検出ができないために誤行列処理を行ってしまう確率を下げることができる。

本実施形態の誤り検出訂正方法を用いた半導体メモリ装置は、復号時間が短く回路規模がコンパクトである。そして、本実施形態の誤り検出訂正方法は、誤行処理発生確率の低い、優れた訂正能力を備える。

＜第２実施形態＞
次に本発明の第２実施形態の誤り検出訂正方法および半導体メモリ装置であるメモリカード３Ａについて説明する。本実施の形態は第１実施形態と類似しているため同じ構成要素には同じ符号を付し説明は省略する。

第１実施形態の補助符号化方式では、補助パリティを付加する単位であるチェックノード数ｎを大きくすることで補助パリティサイズ増加を抑えられる。しかし補助パリティの誤り検出信頼度は、ｎに比例して下がる。本実施の形態の特殊補助符号化方式では第１実施形態の補助パリティを改善した。すなわち、改良補助符号を用いる本実施の形態の特殊補助符号化方式では、例えば、チェックノード１個当たり補助パリティとして特殊補助符号の１ビットパリティを付加するだけであるが、所定の確率で２ビット以上の偶数誤りが検出可能になり、符号化率を大きく低下させることなく、誤行処理の発生を抑制できる。

図８に示すように、本実施の形態の誤り検出訂正方式では、あるチェックノードに接続するｋビットのデータセット（データ列）をｍブロックに分割する。ブロックの分割方法は任意でよい。例えば、ｍ＝２、データセット３２ビットの場合、上位１６ビットと下位１６ビットとに分割したり、偶数１６ビットと奇数１６ビットとのように分割したりする。

そして、ｍ個のオペランド間で演算/データ処理（例えば、加算、減算、乗算、除算、べき乗算、スクランブル、圧縮/伸張、暗号化、ガロア体演算、あるいはこれらの組み合わせ等）を実行し、処理結果の例えば１ビットの奇数パリティを計算し、これを補助パリティ（特殊補助符号）とする。

そして、ＬＤＰＣ行処理時に、補助パリティを再計算し、受信した補助パリティと値が一致するか確認し、一致すれば補助パリティＯＫと判定する。以上の機構により、１ビットの補助パリティだけで２ビット以上の偶数誤りを後述するように、所定の確率で検出することができる。

例えば、加算処理ではキャリーが発生するため、あるビット誤りによる変化が、他の複数の上位ビットに影響を与える場合がある。すなわち、誤りのない状況での演算結果の「１」の個数と、２ビット以上の偶数誤りを伴う演算結果での「１」の個数が異なってくる現象が発生することがある。このため２ビット以上の誤りを１ビットのパリティにより検出可能となる。

ただし、必ずしも２ビット以上の偶数誤りで補助パリティ結果が変化するとは限らないので、この機構は、あくまでもチェックノードでの２ビット以上偶数誤りを誤判定する確率を下げる機能しか備えてはいない。

以下、具体的に説明を行う。ここでは、ｋ＝８ビットとし、あるチェックノードに接続するデータ列をＤとする。データ列をｍ＝２分割して２個の数値データとして扱い、２オペランドの加算処理を実行する。このとき、最上位ビットのキャリーアウトは奇数パリティ計算に含めてもよいが、以下の説明では含めないこととする。

Ｄ＝“００００＿０１０１”
Ｄ２＝“００００”、Ｄ１＝“０１０１”、
Ｄ１＋Ｄ２＝“００００”＋“０１０１”＝“０１０１”、

ここで、補助パリティ＝奇数パリティ＝“０”（ビット「１」の個数が奇数個なら奇数パリティ＝「１」）。Ｄの受信データＲに２ビット誤りが発生し、Ｒ＝“０１００＿０１１１”、ｒ１＝“０１１１“、ｒ２＝“０１００”になったとする。すると、ｒ１＋ｒ２＝“０１１１”＋“０１００”＝“１０１１”となる。「１」の個数が奇数なので補助パリティを再計算すると「１」になり、受信した補助パリティ＝「０」と異なることから、２ビット誤りが検出できる。

すなわち、パリティビット（１ビットＣＲＣ）による従来のＬＤＰＣパリティチェック（通常チェックノード）は２ビット以上の偶数誤りが発生すると誤判定する。これに対して、本実施形態の補助パリティ（特殊補助符号）は２ビット以上の偶数誤りを１００％は検出できないが、誤ったビット位置によっては検出できる。このため、特殊補助符号化を実施することで、ＬＤＰＣパリティの誤判定確率、すなわち誤行処理の発生確率を下げることができる。

データセットの分割数ｍに応じて、ビット誤り現象に対する補助パリティビットへの影響度が変わる場合があるので、ｍは影響度の大きくなる適切な値に設定する。例えば上記のように加算処理により補助パリティを生成する場合、ｍを大きくすると「１」どうしの加算発生確率が増え、キャリー伝播が起きやすくなるので、ｍを大きくするのが望ましい。

ここで、例えば、１個のチェックノードに接続するビットノード数が４０ビット程度の場合には、ｍ＝４にして４個の１０ビットデータを生成し、４個のオペランドによる加算結果をもとに補助パリティを計算する。更に、補助パリティ計算にキャリーアウトを含めた方が偶数ビットエラーを検出しやすい場合には、含めてもよい。

演算内容も、データの性質に応じて選択される。また、複数種類の演算、またはデータ加工を組み合わせてもよい。例えば、データに「０」または「１」の連続パターンが多い場合は、通信技術でよく使われるスクランブルをかけてトグルパターン“１０１０・・・”を多く含むデータパターンに変換してから加算あるいは減算を実行し、キャリー/ボローが発生しやすい状況を意図的に作り出すことが好ましい。

既に説明した第１実施形態においては、通常補助符号化でｎ＝１で補助パリティサイズが最小になるＣＲＣ２を採用した場合でも２ビットの補助パリティ（第２のパリティ）が必要になる。しかし、本実施形態の誤り検出訂正方式では、特殊符号化方式により補助パリティ（第２のパリティ）は１ビットなので、通常補助符号化に比べて実質的符号化率低下を最小限に抑えることができる。

なお、チェックノードにおけるパリティ判定結果に応じたαの更新は例えば、以下のように行う。

＜ｎ＝１の場合＞
（ケース１）ＬＤＰＣパリティ（第１のパリティ）ＯＫ、補助パリティ（第２のパリティ）ＯＫ
⇒｜α｜にM＝Ｈ×｜βｍ｜を加える。Ｈは補正係数で、例えば、Ｈ＝１．５である。すなわち、信頼度αを増加する。

（ケース２）ＬＤＰＣパリティＯＫ、補助パリティＮＧ
⇒｜α｜にM＝｜βｍ｜を加える。補助パリティＮＧの原因が検査対象ビットでない可能性があるので、従来と同じ処理を施す。

ここで、本実施形態の誤り検出訂正方法の特殊補助符号化においても、ｎ＝２以上にして、実効的符号化率低下を更に低減することもできる。すなわち、チェックノード１のデータをＤ１、チェックノード２のデータをＤ２とした場合、「Ｄ1＋Ｄ2」を演算し、演算結果の奇数パリティを計算し、これを補助パリティビットとする。

なお、ｎ＝２にして２チェックノードに従属するデータセットで補助パリティを演算する場合には、（全チェックノード数×１/２）個の補助パリティの追加となる。ｎは２以上の任意整数値を選択すればよい。ｎは訂正能力と実効的符号化率とのトレードオフで決定する。

＜ｎ＞２の場合＞
（ケース１）ＬＤＰＣパリティＯＫ、補助パリティＯＫ
⇒｜α｜にM＝Ｈ×｜βｍ｜を加える。すなわち、信頼度αを増加する。
Ｈは補正係数で、ｎに応じて決定する。例えば、ｎ＝２の場合Ｈ＝１．４、ｎ＝３の場合Ｈ＝１．２である。

以上の説明のように、本実施の形態の誤り検出訂正方法では、第２のパリティが、データ列を複数の分割データ列に分割し、分割データ列を構成する１ビットデータの間で演算処理を行うことにより作成された特殊補助符号の１ビットパリティである。そして、特に、前記演算処理が、加算処理、減算処理、乗算処理、除算処理、べき乗処理、スクランブル処理、圧縮処理、伸張処理、暗号化処理、またはガロア体演算処理の少なくともいずれかである。

＜第３実施形態＞
次に本発明の第３実施形態の誤り検出訂正方法および半導体メモリ装置であるメモリカード３Ｂについて説明する。本実施の形態は第２実施形態等と類似しているため同じ構成要素には同じ符号を付し説明は省略する。

通常チェックノードが用いる通常のパリティビット、すなわち１ビットＣＲＣは、ｎビットのデータ列Ｄを構成する、１ビットデータＤｎを順に排他的論理和（ＥＯＲ）演算することにより作成される。排他的論理和：ＥＯＲ（ExclusiveｅＯＲ、エクスクルーシブ・オア）は、データが異なる場合に「１」を出力する。

図９に、ｋ＝８ビットとし、あるチェックノードに接続するデータ列をＤ、すなわち１ビットデータ８個からなるデータ列、Ｄ＝００００＿０１０１（ｄ１＝１、ｄ２＝０、ｄ３＝１、ｄ４＝０、ｄ５＝０、ｄ６＝０、ｄ７＝０、ｄ８＝０）を例に通常のパリティビット作成方法を示す。

これに対して、本実施形態の誤り検出訂正方法では、補助ビット（第２のパリティ）は、データ列を構成する１ビットデータに対して順に排他的論理和（ＸORまたはＥOR）演算とＥＯＲ演算以外の論理演算（ブール演算）とを交互に行うことにより作成された１ビットパリティである。

ここで、ＥＯＲ演算以外の論理演算とは、論理積（ANＤ）演算、否論理積（NAND）演算、論理和（ＯＲ）演算、否論理和（NＯＲ）演算である。

例えば、本実施形態の第２のパリティである改良パリティビットは、ｎビットのデータ列Ｄを構成する、１ビットデータｄｎを交互に排他的論理和（ＥＯＲ）演算と論理積（ANＤ）演算とを、することにより作成される。なお、論理積（ANＤ）演算では、データが共に１の場合には「１」を出力する。なお、論理和（ＯＲ）演算では、データの一方でも１なら「１」を出力する。

例えば、図１０に示すように、ｋ＝８ビットとし、あるチェックノードに接続するデータ列をＤとする。これをｍ＝ｋ＝８分割して８個の１ビットの数値データとして扱い、隣接する１ビットどうしのＥＯＲ演算とANＤ演算とを順次実行する。すなわち、演算は計７回実行される。この結果の奇数パリティを計算し、これを補助パリティとする。

Ｄ＝“００００＿０１０１”
ｄ１＝“１”、ｄ２＝“０”、ｄ３＝“１”、ｄ４＝“０”、ｄ５＝“０”、ｄ６＝“０”、ｄ７＝“０”、ｄ８＝“０”、（「＾」はＥＯＲ演算、「＊」はANＤ演算を意味する）

（ｄ１＾ｄ２）＾
（ｄ２＊ｄ３）＾
（ｄ３＾ｄ４）＾
（ｄ４＊ｄ５）＾
（ｄ５＾ｄ６）＾
（ｄ６＊ｄ７）＾

そして、（ｄ７＾ｄ８）＾＝「０」、すなわち、以上の例では、補助パリティ＝奇数パリティ＝「０」となる。

これに対して、Ｄの受信データＲに２ビット誤りが発生し、Ｒ＝“１０００＿０１１１”になったとする。加算結果の「１」の個数が３個の奇数なので補助パリティ（奇数パリティ）を再計算すると「１」になり、受信した補助パリティ＝「０」と異なることから、２ビット誤りを検出することができる。

ここで、表１を用いて更に説明する、表１（Ａ）は送信データの補助パリティを、表１（Ｂ）は誤りが発生した受信データの補助パリティを、表１（Ｃ）は１ビット誤り検出確率を、表１（Ｄ）は２ビット誤り検出確率を示している。表１においては、ｄ２のデータが送受信時で異なる場合を例に示している。

（表１）

表１（Ｃ）に示すように１ビット誤りは５０％の確率で、表１（Ｄ）に示すように２ビット誤りも２ビット誤りが互いに離れたビット位置で発生するという前提下で５０％の確率で、検出可能である。

すなわち、本実施形態の第２のパリティでは、通常のＥＯＲ演算によるパリティビット計算に冗長にANＤ演算を加えることで、ある確率で２ビット誤りの発生を検出できる。すなわち、離れたビット位置で１ビット誤りが２つ発生、すなわち２ビット誤りが発生した場合に、一方のパリティビットでは１ビット誤りが検出できるが、もう一方のパリティビットでは検出できない状況となる。これにより２ビット誤りをある確率で検出可能になる。

なお、ＥＯＲ演算に替えて、排他的否論理和（ＥＮＯＲ）演算を用いることも可能である。すなわち、排他的否論理和（ＥＮＯＲ）とＥＯＲ演算以外の論理演算（ブール演算）とを交互に行うことにより１ビットパリティを作成しても同様の効果を得ることができる。

すなわち、以下の組み合わせである。（１）ＥＯＲとＡＮＤ、（２）ＥＯＲとＮＡＮＤ、（３）ＥＯＲとＯＲ、（４）ＥＯＲとＮＯＲ、（５）ＥＮＯＲとＡＮＤ、（６）ＥＮＯＲとＮＡＮＤ、（７）ＥＮＯＲとＯＲ、（８）ＥＮＯＲとＮＯＲ。

すでに説明したように、公知の１ビットＣＲＣ（ＣＲＣ１）であるパリティビットはデータ列を構成する１ビットデータに対して順にＥOR演算する。これに対して、データ列を構成する１ビットデータに対してＥＯＲ演算またはＥＮＯＲ）演算と、これ以外の論理演算、とを交互に行うことにより作成された改良１ビットパリティは、１ビット長でありながら、誤り検出能力が高い。

すなわち、上記説明ではＬＣＰＣの補助パリティの一例として、改良１ビットパリティを示しているが、改良１ビットパリティは公知の１ビットＣＲＣ（ＣＲＣ１）であるパリティビットが用いられる誤り検出方式に広く適用可能である。

なお、本実施の形態ではビットデータの演算多重度を２にしているが（１ビットデータをＥＯＲとANＤとに入力）、多重度は２以上の整数値であればよく、また、演算を行うビットデータは隣接していなくともよい。

さらに、図１１を用いて補助パリティを２ビットにした本実施形態の変形例について説明する。ここでは、ｍ＝８であり、８個のビットデータ間でＥＯＲ演算およびANＤ演算を実行し、その結果の奇数パリティを補助パリティ１とし、８個のビットデータ間でＥＯＲ演算およびＯＲ演算を実行し、その結果の奇数パリティを補助パリティ２とする。補助パリティ２は補助パリティ１を補完するように設置するもので、補助パリティ１で検出できない２ビット以上の偶数エラーを検出することができる。

表２は、本実施形態の変形例の補助パリティ１、２による誤り検出確率を説明するためであり、表２（Ａ）−１は送信データの補助パリティ１を、表２（Ａ）−２は送信データの補助パリティ２を、表２（Ｂ）−１は受信データの補助パリティ１を、表２（Ｂ）−２は受信データの補助パリティ２を、示している。そして、受信データに誤りが発生、すなわち送受信時でデータが異なる場合を示している。

（表２）

表２に示すように、本変形例の誤り検出訂正方法では、補助パリティ１および補助パリティ２でチェックノード検査をすることで、２ビット以上の偶数誤りを約１００％の確率で検出できる。すなわち、補助パリティ１および補助パリティ２が、それぞれ検出確率５０％であり、それぞれの検出結果が補完関係となるように設計することにより、検出確率が１００％となる。

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

１…メモリシステム
２…メモリコントローラ
３、３Ａ〜３Ｂ…メモリカード
４…ホスト
１１…コア
１２…符号化器
１３…メモリ部
１３Ｄ…メモリセル
１３Ｅ…ビット線
１５…誤り検出訂正部
１７…バス
１８…ＥＣＣ部

Claims

低密度パリティ検査符号の検査行列のタナーグラフに対応して設定されたチェックノードから前記チェックノードに接続されている複数のビットノードに向け信頼度αを伝搬する処理と、ビットノードから前記ビットノードに接続されている複数のチェックノードに向け信頼度βを伝搬する処理と、を繰り返す、サムプロダクトアルゴリズムを用いた復号処理において、
前記チェックノードが２ビット以上のパリティを備えることを特徴とする誤り検出訂正方法。
前記チェックノードとして、前記パリティビットによるチェックを行う通常チェックノードと、前記パリティビットとは異なる第２のパリティによるチェックを行う補助チェックノードと、を有することを特徴とする請求項１に記載の誤り検出訂正方法。
２以上の通常チェックノードを１つの単位として前記第２のパリティを作成した前記補助チェックノードを有することを特徴とする請求項２に記載の誤り検出訂正方法。
前記第２のパリティが、データ列を構成する１ビットデータに対して、排他的論理演算または排他的否論理和演算と、前記排他的論理演算または前記排他的否論理和演算以外の論理演算と、を交互に行うことにより作成された１ビットパリティであることを特徴とする請求項２または請求項３に記載の誤り検出訂正方法。
請求項１から請求項４のいずれか１項に記載の誤り検出訂正方法を行うことを特徴とする半導体メモリ装置。