JP5112468B2 - 誤り検出訂正回路、メモリコントローラ、および半導体メモリ装置 - Google Patents

Description

本発明は、ＬＤＰＣ符号化されたデータを復号処理する誤り検出訂正回路、前記誤り検出訂正回路を有するメモリコントローラ、および前記誤り検出訂正回路を有する半導体メモリ装置に関し、特に部分並列処理を行う誤り検出訂正回路、前記誤り検出訂正回路を有するメモリコントローラ、および前記誤り検出訂正回路を有する半導体メモリ装置に関する。

半導体メモリ等のストレージ分野での高密度記録等のために、デジタルデータの誤り訂正符号に関する開発が行われている。誤り訂正符号は、代数系の誤り訂正方式と確率にもとづく反復計算による誤り訂正方式とに大別できる。そして、後者に属する低密度パリティ検査符号（Ｌｏw Density Parity Check codes、以下、「ＬＤＰＣ符号」という）はシャノン限界に迫る、優れた性能が報告されている。

ＬＤＰＣ符号化データはサムプロダクト（Sum-Product）アルゴリズムを用いることにより、比較的少ない回路規模で並列処理を行うことができる。しかし、符号長の長いＬＤＰＣ符号化データでは、全ての処理を並列で行う完全並列処理は、多数の演算回路を全て実装する必要があるため現実的ではない。

このため、例えば、特開２００６−２７９３９６号公報には、正方行列を並べた構成の検査行列を用いて部分並列処理を行う復号装置が開示されている。

しかし、特開２００６−２７９３９６号公報に開示された部分並列処理であっても、正方行列のサイズが大きくなると、演算回路を実装することは容易ではなく、かつ消費電力も大きくなる。

このため、処理速度、実装効率および消費電力のバランスのとれた処理効率のよい誤り検出訂正回路、前記誤り検出訂正回路を有するメモリコントローラ、および前記誤り検出訂正回路を有する半導体メモリ装置が求められていた。

特開２００６−２７９３９６号公報

本発明は処理効率のよい誤り検出訂正回路、前記誤り検出訂正回路を有するメモリコントローラ、および前記誤り検出訂正回路を有する半導体メモリ装置を提供することを目的とする。

上記目的を達成すべく、本発明の一態様の、低密度パリティ検査符号により符号化された受信データをサムプロダクト・アルゴリズムを用いて復号処理する誤り検出訂正回路であって、サイズｐ（ｐは８以上の整数）の単位行列からなるブロックと、単位行列の各行が「１」から「ｐ−１」のシフト値に対応してシフトしている複数のブロックと、からなる検査行列をもとに、受信データを、ｐ個のデータからなるグループに分割し出力する第１のセレクタと、それぞれのグループを、さらにＹ個（Ｙは２以上の整数）のサブグループに分割し出力する第２のセレクタと、確率βを算出処理するための複数の第１の変数を、第１のアドレスと関連付けて格納する第１のメモリと、外部値αを算出処理するための複数の第２の変数を、第２のアドレスと関連付けて格納する第２のメモリと、第２のメモリに格納された複数の第２の変数に対して、シフト値とサブグループとに応じたローテイト値のローテイト処理を行い、演算ユニットに送信するローテイターと、シフト値に連動してサブグループ単位で、第１の変数と第２の変数とを用いた並列演算処理を行う（ｐ／Ｙ）個の演算回路からなる演算ユニットと、シフト値およびローテイト値に応じて、第１のセレクタ、第２のセレクタ、およびローテイターを制御する制御部と、を具備する。

本発明によれば、処理効率のよい誤り検出訂正回路、前記誤り検出訂正回路を有するメモリコントローラ、および前記誤り検出訂正回路を有する半導体メモリ装置を提供することができる。

検査行列Ｈ１を説明するための説明図である。 タナーグラフＧ１を説明するための説明図である。 タナーグラフＧ２の場合の（Ａ）行処理および（Ｂ）列処理を説明するための説明図である。 （Ａ）は部分並列処理に用いる検査行列Ｈ２であり、（Ｂ）はブロック毎のシフト値を示している。 検査行列Ｈ３のブロックのシフトを説明するための図であり、（Ａ）はシフト値＝０、（Ｂ）はシフト値＝１のブロックを示している。 公知の誤り検出訂正回路の処理を説明するための説明図である。 公知の誤り検出訂正回路のシフト処理を説明するための説明図である。 第１の実施の形態のメモリカードの構成を示す構成図である。 第１の実施の形態の誤り検出部の構成を示す構成図である。 第１の形態の誤り検出訂正回路の処理の流れを説明するためのフローチャートである。 第１の形態の誤り検出訂正回路の処理を説明するための説明図である。 第１の形態の誤り検出訂正回路の処理を説明するための説明図である。 第１の形態の誤り検出訂正回路の処理を説明するための説明図である。 第１の形態の誤り検出訂正回路のシフト処理を説明するための説明図である。 第２の形態の誤り検出訂正回路の処理を説明するための説明図である。 第２の形態の誤り検出訂正回路の処理を説明するための説明図である。 第２の形態の誤り検出訂正回路の処理を説明するための説明図である。 第２の形態の誤り検出訂正回路のシフト処理を説明するための説明図である。 第３の形態の誤り検出訂正回路の処理を説明するための説明図である。 第３の形態の誤り検出訂正回路の処理を説明するための説明図である。 第３の形態の誤り検出訂正回路の処理を説明するための説明図である。 第３の形態の誤り検出訂正回路のシフト処理を説明するための説明図である。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

α（ｊ、ｉ）＝ｓｉｇｎ（Πβ（ｍ、ｊ））×ｍｉｎ（｜β（ｍ、ｊ）｜） ・・・（式６）
ただし、ｍはチェックノードｊに接続したビットノードの中で、ｍ＝ｉ、以外とする。

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

Ｐｂ（ｉ）＝λ（ｉ）＋Σα（ｋ、ｉ） ・・・（式７）
ここで、i＝１〜Ｎであり、Ｎは符号長である。そして、Σはビットノードｉに接続された全ての和である。

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

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

そして、部分並列処理には、特開２００６−２７９３９６号公報に開示された方法以外にも、いくつかの方法がある。例えば、複数の単位行列（以下「ブロック」ともいう。）を組み合わせて構成した検査行列を用い、ブロックサイズのビットノード分の演算回路により並列処理を行う方法がある。

図４（Ａ）に複数の単位行列を組み合わせて構成した検査行列Ｈ３を示す。検査行列Ｈ３は、１区画が５×５個の要素からなるブロックを横に６個、縦に３個並べて、縦１５行、横３０列となっている。

そして、図４（Ｂ）に示すように、検査行列Ｈ３の各ブロックＢは、対角成分には１が並び、他は全て０となる単位行列を数値分だけシフト処理した正方行列（以下、シフト行列）である。なお、図４（Ａ）に示した検査行列Ｈ３は、ユーザーデータ用のブロックである符号化対象（メッセージ）ブロック部Ｈ３Ａと、ユーザーデータから生成したパリティ用のパリティ用ブロック部Ｈ３Ｂとから構成されている。そして、図３（Ｂ）に示すように、シフト値「０」は単位行列を示し、シフト値「−１」は０行列を示している。なお、０行列は実際の演算処理が不要なため、以下では除いて説明する。

シフト処理によってあふれたビットはブロック内の最左列に挿入されている。検査行列Ｈ３を用いた復号処理ではシフト値を指定することにより必要なブロックの情報、すなわち、処理すべきノードの情報を得ることができる。なお、５×５のブロックからなる検査行列Ｈ３においては、シフト値は、復号処理に直接は関係のない、０行列を除くと、０、１、２、３、４の、５種類のいずれかである。

図４（Ａ）に示したブロックサイズ５Ｘ５（以下、「ブロックサイズ５」という）の正方行列を組み合わせた検査行列Ｈ３を用いた場合には、演算ユニットを５個設けることで、５個のチェックノードに対して部分並列処理を実行することができる。なお、部分並列処理を実行するためには、ビットノード単位での事前／事後確率βを求めるための変数（以下、「ＬＭＥＭ変数」ともいう）を格納するビットノード記憶部（ＬＭＥＭ）と、チェックノード単位で外部値αを求めるための変数（以下、「ＴＭＥＭ変数」ともいう）を格納するチェックノード記憶部（ＴＭＥＭ）が必要である。ビットノードは列方向のアドレス（列アドレス）で管理するのでＬＭＥＭは列アドレスで管理し、チェックノードは行方向のアドレス（行アドレス）で管理するのでＴＭＥＭは行アドレスで管理する。外部値α、確率βを計算する場合は、ＬＭＥＭからリードしたＬＭＥＭ変数とＴＭＥＭからリードしたＴＭＥＭ変数が、演算回路にそれぞれ入力されて演算処理が実行される。

以下、ＴＭＥＭからリードした複数のＴＭＥＭ変数をシフト値に応じてローテイトする方法について説明する。すなわち、図５および図６に示すように、ブロックサイズ８の検査行列Ｈ４を用いた、ＴＭＥＭ１３２からリードした８個のＴＭＥＭ変数の処理の場合には、誤り検出訂正回路１０１では、ＬＭＥＭ１２６と、ＴＭＥＭ１２６と、演算ユニット１３０と、ローテイター１３２と、が使用される。演算ユニット１３０は８個の演算回路ＡＬＵ０〜ＡＬＵ８からなり、８個の処理を並列処理することができる。なお、ブロックサイズ８の検査行列Ｈ３を用いた場合のシフト値は、０〜７の８種類である。

図５（Ａ）および図６（Ａ）に示すように、シフト値が「０」のブロックＢ（０）場合は、ローテイター１３２によりローテイト値０のローテイト処理が行われ、同一アドレスの変数同士で演算が実行される。ただし、ローテイト値０のローテイト処理とはローテイトされないことである。

列アドレス０のＬＭＥＭ変数、行アドレス０のＴＭＥＭ変数（図５（Ａ）破線表示）
列アドレス１のＬＭＥＭ変数、行アドレス１のＴＭＥＭ変数
列アドレス２のＬＭＥＭ変数、行アドレス２のＴＭＥＭ変数
・
・
列アドレス７のＬＭＥＭ変数、行アドレス７のＴＭＥＭ変数（図５（Ａ）破線表示）

これに対して、図５（Ｂ）および図６（Ｂ）に示すように、シフト値が「１」のブロックＢ（１）の場合は、ローテイター１３２によりローテイト値１のローテイト処理が行われ、以下のような変数同士で演算が実行される。すなわち、ローテイト値１のローテイト処理とは、それぞれの変数をひとつ下段に移動し、あふれた最下段の変数を最上段に挿入するシフト処理である。

列アドレス０のＬＭＥＭ変数、行アドレス７のＴＭＥＭ変数（図５（Ｂ）破線表示）
列アドレス１のＬＭＥＭ変数、行アドレス０のＴＭＥＭ変数（図５（Ｂ）破線表示）
列アドレス２のＬＭＥＭ変数、行アドレス１のＴＭＥＭ変数
・
・
列アドレス７のＬＭＥＭ変数、行アドレス６のＴＭＥＭ変数

そして、図６（Ｃ）に示すように、シフト値が「７」のブロックＢ（７）の場合は、ローテイター１３２によりローテイト値７のローテイト処理が行われ、以下のような変数同士で演算が実行される。すなわち、ローテイト値７のローテイト処理とは、ローテイト値１のローテイト処理を７回行う処理である。

列アドレス０のＬＭＥＭ変数、行アドレス１のＴＭＥＭ変数
列アドレス１のＬＭＥＭ変数、行アドレス２のＴＭＥＭ変数
列アドレス２のＬＭＥＭ変数、行アドレス３のＴＭＥＭ変数
・
・
列アドレス７のＬＭＥＭ変数、行アドレス０のＴＭＥＭ変数

図７に、ブロックシフト値（０〜７）毎の演算回路入力変数の組み合わせを示す。

以上のように、ローテイター１３２は、ＬＭＥＭ１２６あるいはＴＭＥＭ１３２からリードした変数を演算ユニット１３０に入力する前にブロックのシフト値に応じたローテイト値にローテイトする。ブロックサイズ８の検査行列Ｈ３を用いた誤り検出訂正回路１０１の場合には、ローテイター１３２の最大ローテイト値は「ブロックサイズ−１」の「７」になる。信頼度の量子化ビット数を「ｕ」とすると、それぞれの変数のビット数は「ｕ」になるので、ローテイター１３２の入出力データ幅は「８×ｕ」ビットになる。

＜第１の実施の形態＞
以下、本発明の第１の実施の形態の誤り検出訂正回路、メモリコントローラ、および半導体メモリ装置（以下、「誤り検出訂正回路等」ともいう」について説明する。

以上の説明では、説明を簡単にするために、ブロックサイズ等が極端に小さい例（ｐ＝８等）について説明したが、例えば、半導体メモリ装置のメモリコントローラの誤り検出訂正回路では、ブロックサイズｐは、１２８〜２５６規模の値になり、非常に大きい。このため、第１の実施の形態の誤り検出訂正回路では、ブロックサイズのｐ個、設置する必要のある演算回路ＡＬＵを、１／Ｙ（Ｙは２以上の整数）に削減して並列度を意図的に下げている。なお、以下の説明では、やはり説明を簡単にするために、ブロックサイズ等が小さく（ｐ＝８）、Ｙ＝２の場合を例に説明する。

最初に、図９を用いて本発明の第１の実施の形態の誤り検出訂正回路１、誤り検出訂正回路１を有するメモリコントローラ２および誤り検出訂正回路１を有する半導体メモリ装置であるメモリカード３の構成を説明する。

図９に示すように、メモリカード３はパソコンまたはデジタルカメラ等のホスト４から受信したデータを記憶し、記憶したデータをホスト４に送信する記憶媒体である。メモリカード３は、半導体メモリ部（以下、単に「メモリ部」ともいう。）１３と、誤り検出訂正回路１を具備したメモリコントローラ２とを有する。メモリ部１３は、ＮＡＮＤ型フラッシュメモリから構成されており、単位セルである多数のメモリセル１３Ｄが、ビット線１３Ｅ等で接続された構造を有する。

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

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

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

そして、図１０に示すように、誤り検出訂正回路１は、制御部２０と、受信部２１と、初期ＬＬＲ算出部２２と、硬判定部２４と、パリティ検査部２５と、第１のメモリであるビットノード記憶部（ＬＭＥＭ）２６と、ローテイター３２と、第２のメモリであるチェックノード記憶部（ＴＭＥＭ）３１と、演算ユニット３０と、第１のセレクタであるセレクタ２３と、第２のセレクタであるセレクタ３６と、を有する。制御部２０は誤り検出訂正回路１全体の制御を行うが、ＣＰＵコア１１の一部であってもよい。受信部２１は、バス１７を介してメモリ部１３に記憶されていた符号化データを受信する。ここで、符号化データは、例えば、ＮＡＮＤ型フラッシュメモリの読み出し電圧として誤り検出訂正回路１に入力される。初期ＬＬＲ算出部２２は入力された符号化データをもとに図示しない対数尤度比テーブル等を用いて初期ＬＬＲを算出する。硬判定部２４は、事後確率（ＬＬＲ）をもとに、ビットデータが「０」または「１」のいずれか硬判定する。

パリティ検査部２５は、硬判定されたデータのパリティ検査を行う。セレクタ２３は、制御部２０の制御によりデータを、検査行列のブロックサイズｐにあわせたｐ（８）個のグループ単位にデータを分割する。セレクタ３５、３６は、制御部２０の制御によりそれぞれのグループから、１／Ｙ（１／２）のサイズのｐ／Ｙ（４）個のサブグループを選択し分割する。すなわち、それぞれの分割処理はセレクタ２３、３５、３６が所定のデータのみを選択することにより行われる。ビットノード記憶部（ＬＭＥＭ）２６はビットノード単位での事前／事後確率βを求めるための第１の変数であるＬＭＥＭ変数を格納する。チェックノード記憶部（ＴＭＥＭ）はチェックノード単位で外部値αを求めるための第２の変数であるＴＭＥＭ変数を格納する。ローテイター３２は制御部２０の制御により、ＴＭＥＭ変数を所定のローテイト値にローテイト処理する。演算ユニット３０は、チェックノード演算部２９と、ビットノード演算部２８とを有する。

次に、図１０〜図１４を用いて、本実施の形態の誤り検出訂正回路１の動作の流れについて説明する。

＜ステップＳ１０＞ データ受信
受信部２１は、メモリ部１３に記憶されていた符号化データを受信する。

＜ステップＳ１１＞ 初期ＬＬＲ値受信
初期ＬＬＲ算出部２２が、尤度比テーブル（不図示）等をもとに符号化データから初期ＬＬＲ（事前確率β）を算出する。

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

＜ステップＳ１３＞ パリティチェック
パリティ検査部２５は、一時推定語を用いてパリティチェックを行う。

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

＜ステップＳ１６＞ 初期化／分割
パリティ検査部２５は、パリティチェックの結果、誤りがあった場合（Ｓ１４：Ｎｏ）には、イタレーション処理を開始するために、ブロックのシフト値を初期化する。また、制御部２０は、セレクタ２３により、事前確率βとなる初期ＬＬＲのデータをｐ（８）個単位のグループに分割し、グループ単位で以下の処理を行う。

＜ステップＳ１７＞ 事前確率β格納
所定のグループの事前確率β（ＬＭＥＭ変数）が、ＬＭＥＭ２６に送信され、第１のアドレスであるＬＭＥＭアドレスと関連付けて格納される。

＜ステップＳ１８＞サブグループ分割
ＬＭＥＭ２６に格納されたＬＭＥＭ変数は、セレクタ３６によりＹ（２）個のサブグループに分割され、順にＳ１９からの処理が行われる。ここで、サブグループは、ＬＭＥＭアドレスにもとづいて、例えば、アドレス中央値を基準に、上位アドレスサブグループと下位アドレスサブグループとに分割される。後に説明するようにＴＭＥＭ変数も、セレクタ３５によりＹ（２）個のサブグループに分割され処理される。例えば、ＬＭＥＭ変数、ＴＭＥＭ変数は、アドレスが（０、１、２、３）のサブグループＬＡ、ＴＡと、アドレスが（４、５、６、７）のサブグループＬＢ、ＴＢと、に分割される。

＜ステップＳ１９＞チェックノード処理（行処理）／ビットノード処理（列処理）
ビットノードから接続されているチェックノードに事前確率βが送信され、チェックノード演算部２９は、受信した確率の積を算出し接続されているビットノードに外部情報αとして送信する。外部情報αはＴＭＥＭ３１に第２のアドレスであるＴＭＥＭアドレスと関連付けて格納される。

チェックノードでは、接続されているビットノードに外部情報αが送信され、ビットノード演算部２８は受信した確率の積を算出し接続されているチェックノードに、事後確率βとして送信する。事後確率βはＬＭＥＭ２６に、第１のアドレスであるＬＭＥＭアドレスと関連付けて格納される。なおＴＭＥＭ３１、ＬＭＥＭ２６に、既に格納されている変数がある場合には、新しい変数が上書きされる。

このとき、図１１〜図１４に示すように、シフト値が偶数の場合、ステップ１にてサブグループＬＡ（変数アドレス０〜３）、サブグループＴＡ（変数アドレス０〜３）をアクセスし、ステップ２にてサブグループＬＢ（変数アドレス４〜７）、サブグループＴＢ（変数アドレス４〜７）をアクセスし、シフト値が奇数の場合、ステップ１にてサブグループＬＡ（変数アドレス０〜３）、サブグループＴＢ（変数アドレス４〜７）をアクセスし、ステップ２にてサブグループＬＢ（変数アドレス４〜７）、サブグループＴＡ（変数アドレス０〜３）をアクセスする。ここで、サブグループにアクセスするとは、演算ユニット３０がアクセスされた２つの変数を用いて演算処理を行うことを意味する。
すなわち、並列処理毎に、ＴＭＥＭ３１に格納されていたＴＭＥＭ変数は、シフト値とローテイト値とに応じたローテイト処理がローテイター３２により行われ、セレクタ３５、３６により演算に必要なサブグループの変数が選択される。

なお、図１４等において、ローテイト値４（０）とは、ローテイト処理により、並び順が１周して再び「０」になったという意味である。

＜ステップＳ２０〜Ｓ２３＞
全てのサブグループ（ステップ：ローテイト値）／グループ（シフト値）の処理が完了するまで、行処理／列処理が行われる。すなわち、ｐ＝８、Ｙ＝２の場合には、ステップＳ１８〜Ｓ２３の処理が８回行われ、さらに、それぞれの繰り返し処理の中でステップＳ１９〜Ｓ２１の処理が２回行われる。

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

以上で説明した誤り検出訂正回路１は、演算ユニット３０の演算回路ＡＬＵの数をｐ（８）個から１／Ｙ（１／２）の、ｐ／Ｙ（４）個に低減できる。すなわち、回路規模が小さく、消費電力が低減した処理効率のよい誤り検出訂正回路である。また、誤り検出訂正回路１を有するメモリコントローラ２、および誤り検出訂正回路１を有する半導体メモリ装置であるメモリカード３は処理効率がよい。

なお、ブロックサイズｐが６４以上のときに、上記実施の形態の誤り検出訂正回路１の効果が明瞭となり、２５６以上のとき、さらに顕著となる。ｐの上限は実装の制限から決定されるが、例えば１ｋ程度である。

以上の説明のように、本実施の形態の誤り検出訂正回路１は、低密度パリティ検査符号の検査行列のタナーグラフに対応して設定された複数の検査ノードおよび複数のビットノードの間で外部値α、確率βを反復伝搬させ、その過程において確率βから算出される事後値（事後確率：ＬＬＲ）の硬判定値を検査行列でパリティ検査することにより収束判定し受信データの推定値を決定するサムプロダクト・アルゴリズムを用いて、受信データからの符号検出を行い、サイズｐ（ｐは８以上の整数）の単位行列からなるブロックと、前記単位行列の各行が「１」から「ｐ−１」のシフト値に対応してシフトしている複数のブロックと、からなる前記検査行列をもとに、前記受信データを、ｐ個のグループに分割する第１のセレクタと、それぞれの前記グループを、さらにＹ個（Ｙは２以上の整数）のサブグループに分割する第２のセレクタと、確率βを算出処理するための複数の第１の変数を、第１のアドレスと関連付けて格納する第１のメモリと、外部値αを算出処理するための複数の第２の変数を、第２のアドレスと関連付けて格納する第２のメモリと、前記第２のメモリに格納された複数の前記第２の変数に対して、前記シフト値と前記サブグループとに応じたローテイト値のローテイト処理を行い、演算ユニットに送信するローテイターと、前記シフト値に連動して前記サブグループ単位で、前記第１の変数と前記第２の変数とを用いて並列演算処理を行う（ｐ／Ｙ）個の演算回路からなる前記演算ユニットと、前記シフト値およびローテイト値に応じて、前記第１のセレクタ、前記第２のセレクタ、前記演算ユニット、および前記ローテイターを制御する制御部と、を具備する。

＜第２の実施の形態＞
以下、図面を参照して本発明の第２の実施の形態の誤り検出訂正回路１Ａ等について説明する。第２の実施の形態の誤り検出訂正回路１Ａ等は、第１の実施の形態の誤り検出訂正回路１と類似しているので、同じ説明は省略する。

第１の実施の形態の誤り検出訂正回路１は、演算ユニット３０の演算回路ＡＬＵの数を１／Ｙに低減した。しかし、ブロックのシフト値制御の都合で、ローテイターの最大ローテイト値は「ブロックサイズ−１」を維持する必要がある。

すなわち、ここで、１回目のラウンドでＴＭＥＭ変数Ｔ１〜Ｔ４をローテイターに入力し、２回目のラウンドでＴ５〜Ｔ８を入力するように制御する場合を考えてみる。ブロックのシフト値が「７」だった場合、例えばＴＭＥＭ変数Ｔ１を、最大シフト値の７ローテイトする必要があるが（図６（Ｂ）参照）、ローテイターは最大で４しかローテイトできないため、要求機能を満足することができない。すなわち、演算回路数は４に半減できるが、これにあわせてローテイターのローテイト機能（回路規模）を半減することはできなかった。また、ローテイター３２に入力するＴＭＥＭ変数の数も、ブロックサイズ分の８個必要になるので、ＴＭＥＭ３１のリードデータ幅は「８×ｕ」ビットのままである。さらに、演算ユニット３０に必要な４個のＴＭＥＭ変数を入力するためには、「８ｕビット to ４ｕビット」のセレクタ３６が必要になる。

このため、ブロックサイズが２５６規模あり、ｕ＝６ビットの誤り検出訂正回路では、ローテイター単体で例えば５０Ｋゲート規模に達し、データバス幅も２５６×６ビット＝１５３６ビットと膨大になる。このため、ＴＭＥＭリードデータ幅、ローテイター規模、セレクタ規模、および前記回路を接続するデータバス幅等を、演算ユニット削減数に比例させて削減することはできなかった。

これに対して、本実施の形態の誤り検出訂正回路１Ａでは、ＬＭＥＭ変数およびＴＭＥＭ変数をアドレスの大小による分割ではなく、アドレスの下位ビットにもとづき分割する。例えば、例えば、アドレスの最下位１ビットにもとづいて、アドレスが偶数のサブグループ（０、２、４、６)Ｔｅと、アドレスが奇数のサブグループ（１、３、５、７）Ｔｏと、の、２グループに分割する。

すなわち、アドレスが偶数とは、アドレスの最下位１ビットが「０」であることを意味し、アドレスが奇数とは、アドレスの最下位１ビットが「１」であるであることを意味している。

そして、誤り検出訂正回路１Ａのイタレーション処理においては、シフト値が偶数の場合、ステップ１にてサブグループＬｅ、サブグループＴｅをアクセスし、ステップ２にてサブグループＬｏ、サブグループＴｏをアクセスし、シフト値が奇数の場合、ステップ１にてサブグループＬｅ、サブグループＴｏをアクセスし、ステップ２にてＬｏ、Ｔｅをアクセスする。

すなわち、ブロック演算処理のステップ１でサブグループＬｅの処理を実行し、ステップ２でサブグループＬｏの処理を実行すると、ブロックシフト値が偶数の場合、ステップ１にてサブグループＬｅはサブグループＴｅと演算を実行し、ステップ２にてサブグループＬｏはサブグループＴｏと演算を実行する。そしてブロックシフト値が奇数の場合、ステップ１にてサブグループＬｅはサブグループＴｏと演算を実行し、ステップ２にてサブグループＬｏはサブグループＴｅと演算を実行する。よって、ブロックシフト値が偶数の場合、ステップ１にてサブグループＬｅ、サブグループＴｅをアクセスし、ステップ２にてサブグループＬｏ、サブグループＴｏをアクセスする。そしてブロックシフト値が奇数の場合、ステップ１にてサブグループＬｅ、サブグループＴｏをアクセスし、ステップ２にてサブグループＬｏ、サブグループＴｅをアクセスする。

すなわち、誤り検出訂正回路１Ａでは、ＴＭＥＭ変数は下位ビットにもとづいてサブグループ分けされているために、ローテイター３２Ａには演算処理に必要なサブグループだけが入力する。

図１５〜図１７に、誤り検出訂正回路１Ａの各シフト値／各ステップにおけるＴＭＥＭ変数ローテイト値の関係を示す。また図１７にシフト値、ステップ、ローテイト値のまとめを示す。

誤り検出訂正回路１Ａでは、演算ユニット３０Ａの演算回路数を、１／Ｙ＝１／２、に削減できるだけでなく、ＴＭＥＭ３１Ａへのアクセス単位（１ワード）のデータ幅を８ｕビットから４ｕビットと１／２、に削減できる。さらに、ローテイター３２Ａの最大ローテイト値および入出力データ幅、ＴＭＥＭ３１Ａとローテイター３２Ａと演算ユニット３０Ａとを接続するデータバス幅、も１／２に削減できる。また、「８ｕビット to ４ｕビット」のセレクタ３６は不要となる。

すなわち、誤り検出訂正回路１Ａは、第１の実施の形態の誤り訂正部１が有する効果に加えてローテイターを含む周辺メモリ、回路、およびデータバスの幅を、演算回路数に合わせて削減できる。すなわち、誤り検出訂正回路１Ａは、柔軟に処理速度と回路規模／消費電力の調整が可能なスケーラビリティを備える。

以上の説明のように、本実施の形態の誤り検出訂正回路１Ａでは、制御部２０が、第１のアドレスおよび第２のアドレスの最下位アドレス１ビットをもとに、各グループを２個のサブグループに分割するように制御する。

また、誤り検出訂正回路１Ａは、ＬＤＰＣ符号による誤り検出／訂正処理機能を備え、１ラウンドの処理（ラウンド処理）で、選択したビットノードに関して、ＬＤＰＣ符号のパリティ検査行列のタナーグラフに対応して設定された複数のチェックノードから当該チェックノードに接続されている複数のビットノードに向け外部情報（α）を伝搬する行処理、および、当該複数のビットノードから該複数のチェックノードに向け事後確率（β）を伝搬する列処理を連続実行する。そして、ラウンド処理繰り返しの過程において、βから算出される事後値を用いて収束判定し符号データの推定し、入力値からの符号検出を行う。そして、サイズｐ×ｐ（ｐは８以上の整数）の正方行列を複数個組み合わせて検査行列を構成するもので、ビットノード単位での事前／事後確率βを求めるための変数を格納／管理するメモリ（ＬＭＥＭ）と、チェックノード単位で外部値αを求めるための変数を格納／管理するメモリ（ＴＭＥＭ）を備え、ブロックのシフト値に連動してｐ個のビットノードと、ｐ個のチェックノード単位で演算処理する機能を備えるもので、ｐ個のビットノードとチェックノードをｐ／Ｙ個（Ｙは２以上の整数）のサブグループに分け、サブグループに対応する変数グループ単位で、ＬＭＥＭ／ＴＭＥＭアクセスとアクセスした変数のローテーション処理を実行するもので、ＬＭＥＭ／ＴＭＥＭの下位アドレスでサブグループ分けをする。

さらに、誤り検出訂正回路１Ａは、演算処理を実行するとき、ＬＭＥＭ、ＴＭＥＭいずれかのワードアクセス順とローテイターのローテイト値を、ブロックシフト値に応じて、決定する機能を備えることが好ましく、特に好ましくは演算処理を実行するとき、ＴＭＥＭのワードアクセス順とローテイターのローテイト値を、ブロックシフト値に応じて、決定する機能を備える。

＜第３の実施の形態＞
以下、図面を参照して本発明の第３の実施の形態の誤り検出訂正回路１Ｂ等について説明する。第３の実施の形態の誤り検出訂正回路１Ｂ等は、第２の実施の形態の誤り検出訂正回路１Ａと類似しているので、同じ説明は省略する。

本実施の形態の誤り検出訂正回路１Ｂは、サブグループ分割数Ｙ＝４の場合であり、演算ユニット３０Ｂは、２（８／４）個の演算回路ＡＬＵを有している。すなわち、ＬＭＥＭ２６Ｂ、ＴＭＥＭ３１Ｂに格納された変数のアドレス最下位２ビットが「００」、「０１」、「１０」、「１１」のいずれであるかに、もとづいて、ＬＭＥＭ変数およびＴＭＥＭ変数を、それぞれ４つのサブグループに分割して、処理する。

誤り検出訂正回路１Ｂでは、第２の実施の形態の誤り検出訂正回路１Ａ（Ｙ＝２）と同様に、制御部２０がシフト値毎に、ＬＭＥＭ２６Ｂ、ＴＭＥＭ３１Ｂからアクセスする変数グループを、ローテイト値に応じてローテイター３２Ｂがローテイト処理する。すなわち、制御部２０が、ステップに応じてＴＭＥＭ変数のローテイト値を制御する。図２２に誤り検出訂正回路１Ｂにおけるシフト値、ステップ毎、ローテイト値のまとめを示す。

誤り検出訂正回路１Ｂは、誤り検出訂正回路１Ａが有する効果に加えて、より回路規模／消費電力を低減できる。なお、サブグループ分割数Ｙの上限は、処理速度と回路規模／消費電力とのトレードオフの関係から適宜、決定されるが、ブロックサイズｐ以下であり例えば８である。

以上の説明のように、本実施の形態の誤り検出訂正回路１Ｂでは、制御部２０が、第１のアドレスおよび第２のアドレスの下位アドレス２ビットをもとに、各グループを４個のサブグループに分割するように制御する。

なお以上は、ホスト４と接続されるメモリカード３からなるメモリシステムを例に説明したが、メモリシステムとしては、ホスト４の内部に収納され、ホスト４の起動データ等を記憶する、いわゆるエンベデッドタイプのＮＡＮＤ型フラッシュメモリ装置等でもメモリカード３等と同じ効果を得ることができる。さらには、符号化データの復号を確率にもとづく反復計算により行う誤り検出訂正回路であれば、デジタルテレビ放送受信機等の誤り検出訂正回路でも半導体メモリシステムと同じ効果を得ることができる。また、誤り検出訂正回路としては専用の回路ではなく汎用ＣＰＵに読み込まれ動作するものであってもよい。

本発明の、さらに別の実施の形態によるＬＤＰＣ符号による誤り検出訂正方法は、受信信号からＬＬＲを算出するＬＬＲ算出工程と、前記ＬＬＲまたは確率βをもとに硬判定を行う硬判定工程と、硬判定結果をもとにパリティ検査を行うパリティ検査工程と、前記受信信号をｐ個のグループに分割するグループ分割工程と、それぞれの前記グループをＹ個のサブグループに分割するサブグループ分割工程と、前記確率βを算出処理するための前記サブグループの複数の第１の変数を、第１のアドレスと関連付けて第１のメモリに格納するとともに、外部値αを算出処理するための前記サブグループの複数の第２の変数を、第２のアドレスと関連付けて第２のメモリに格納する変数格納工程と、前記第１のメモリに格納された前記複数の第１の変数に対して選択処理する選択工程と、前記第２のメモリに格納された前記複数の第２の変数に対してローテイト処理するローテイト工程と、選択処理されたｐ／Ｙ個の前記第１の変数とローテイト処理されたｐ／Ｙ個の前記第２の変数とをｐ／Ｙ個の演算回路により並列処理する並列処理工程と、を具備する。ただし前記ＬＤＰＣ符号はサイズｐ（ｐは８以上の整数）の単位行列からなるブロックと、前記単位行列の各行が「１」から「ｐ−１」のシフト値に対応してシフトしている複数のブロックと、からなる検査行列をもとにし、前記グループは前記シフト値に対応しており、前記ローテイト処理および前記選択処理は、前記シフト値および前記サブグループに応じたローテイト値にもとづき実行される。

さらに、上記誤り検出訂正方法において、サブグループ分割工程は、前記第１のアドレスおよび前記第２のアドレスの下位アドレスをもとに行われることが好ましく、より好ましくは前記第１のアドレスおよび前記第２のアドレスの最下位アドレス１ビットをもとに行われる。

上記のように、本発明は、上述した実施の形態に限定されるものではなく、本発明の要旨を変えない範囲において、種々の変更、改変等が可能である。

１、１Ａ、１Ｂ…誤り検出訂正回路、２…メモリコントローラ、３…メモリカード、４…ホスト、１０…ＲＯＭ、１１…ＣＰＵコア、１２…符号化器、１３…メモリ部、１３Ｄ…メモリセル、１３Ｅ…ビット線、１４…Ｈｏｓｔ Ｉ／Ｆ、１６…ＮＡＮＤ Ｉ／Ｆ、１７…バス、１８…ＲＡＭ、２０…制御部、２１…受信部、２２…算出部、２３…セレクタ、２４…硬判定部、２５…パリティ検査部、２６、２６Ａ、２６Ｂ…ビットノード記憶部（ＬＭＥＭ）、２８…ビットノード演算部、２９…チェックノード演算部、３０、３０Ａ、３０Ｂ…演算ユニット、３１、３１Ａ、３１Ｂ…チェックノード記憶部（ＴＭＥＭ）、３２、３２Ａ、３２Ｂ…ローテイター、３５、３６…セレクタ、１０１…誤り検出訂正回路、１３０…演算ユニット、１３２…ローテイター、ＡＬＵ…演算回路

Claims (5)

1. 低密度パリティ検査符号により符号化された受信データをサムプロダクト・アルゴリズムを用いて復号処理する誤り検出訂正回路であって、
   サイズｐ（ｐは８以上の整数）の単位行列からなるブロックと、前記単位行列の各行が「１」から「ｐ−１」のシフト値に対応してシフトしている複数のブロックと、からなる検査行列をもとに、前記受信データを、ｐ個のデータからなるグループに分割し出力する第１のセレクタと、
   それぞれの前記グループを、さらにＹ個（Ｙは２以上の整数）のサブグループに分割し出力する第２のセレクタと、
   確率βを算出処理するための複数の第１の変数を、第１のアドレスと関連付けて格納する第１のメモリと、
   外部値αを算出処理するための複数の第２の変数を、第２のアドレスと関連付けて格納する第２のメモリと、
   前記第２のメモリに格納された前記複数の第２の変数に対して、前記シフト値と前記サブグループとに応じたローテイト値のローテイト処理を行い、演算ユニットに送信するローテイターと、
   前記シフト値に連動して前記サブグループ単位で、前記第１の変数と前記第２の変数とを用いた並列演算処理を行う（ｐ／Ｙ）個の演算回路からなる前記演算ユニットと、
   前記シフト値およびローテイト値に応じて、前記第１のセレクタ、前記第２のセレクタ、および前記ローテイターを制御する制御部と、を具備する。
2. 前記制御部が、前記サブグループへの分割を、前記第１のアドレスおよび前記第２のアドレスの下位アドレスをもとに制御することを特徴とする請求項１に記載の誤り検出訂正回路。
3. 前記制御部が、前記第１のアドレスおよび前記第２のアドレスの最下位アドレス１ビットをもとに、それぞれの前記グループを、２個の前記サブグループに分割するように制御することを特徴とする請求項１に記載の誤り検出訂正回路。
4. 請求項１に記載の誤り検出訂正回路を有することを特徴とするメモリコントローラ。
5. 請求項４に記載のメモリコントローラと、前記メモリコントローラによってデータの読出し・書き込みが行われるＮＡＮＤ型フラッシュメモリ部とを有し、前記ＮＡＮＤ型フラッシュメモリ部からのデータの読出し時に前記誤り検出訂正回路により訂正されたデータを読み出すことを特徴とする半導体メモリ装置。

Images