(57)【要約】【課題】ＬＤＰＣ符号の復号処理をより小規模な構成により実現可能とする。【解決手段】実施形態の復号装置は、符号に応じて定められる変数ノードに対して変数ノード処理を行い第１のメッセージを出力し、符号に応じて定められるチェックノードに対して第１のメッセージに基づきチェックノード処理を行い第２のメッセージを出力し、第２のメッセージのうち一部のメッセージを記憶する。第１のメッセージに含まれるメッセージであって、チェックノードのうち既に記憶される一部のメッセージに対応するチェックノードに転送されるべきメッセージを除外したメッセージをチェックノードに転送し、第２のメッセージを変数ノードに転送すると共に、第２のメッセージのうち一部のメッセージを記憶部に転送する。【選択図】図７
2016144052.tif 000002
【特許請求の範囲】
【請求項１】
符号に応じて定められる変数ノードに対して変数ノード処理を行い第１のメッセージを出力する変数ノード処理部と、
前記符号に応じて定められるチェックノードに対して前記第１のメッセージに基づきチェックノード処理を行い第２のメッセージを出力するチェックノード処理部と、
前記第２のメッセージのうち一部のメッセージを記憶する記憶部と、
前記第１のメッセージに含まれるメッセージであって、前記チェックノードのうち既に前記記憶部に記憶された前記一部のメッセージに対応するチェックノードに転送されるべきメッセージを除外したメッセージを前記チェックノードに転送する第１転送部と、
前記第２のメッセージを前記変数ノードに転送すると共に、前記第２のメッセージのうち一部のメッセージを前記記憶部に転送する第２転送部と
を備える
復号装置。
【請求項２】
前記チェックノード処理部は、
前記符号に応じて予め定められるチェックノード数未満の数の前記チェックノードに対して前記チェックノード処理を行う
請求項１に記載の復号装置。
【請求項３】
前記チェックノード処理部は、
前記チェックノード処理を行うチェックノード演算部を複数含み、
前記チェックノード処理部が含む前記チェックノード演算部の数は、
前記チェックノードの総数をＣ（Ｃは１以上の整数）とし、前記変数ノード処理部および前記チェックノード処理部による処理の繰り返し単位における前記チェックノード演算部によるチェックノード処理を行う平均回数をＬ（Ｌ＜２×Ｃ）とするとき、Ｃ／Ｌよりも少ない
請求項１または請求項２に記載の復号装置。
【請求項４】
１つの前記変数ノードに接続する前記チェックノードの平均数をＮ（Ｎ＞２）とするとき、前記一部のメッセージに対応するチェックノード数の全チェックノード数に対する割合は、（Ｎ−２）／Ｎ以下である
請求項１乃至請求項３の何れか１項に記載の復号装置。
【請求項５】
前記第２転送部は、
前記変数ノード処理部および前記チェックノード処理部による処理の繰り返し単位毎に異なる前記チェックノードの集合に基づく前記一部のメッセージを前記記憶部に転送する
請求項１乃至請求項４の何れか１項に記載の復号装置。
【請求項６】
前記第２転送部は、
連続する前記繰り返し単位では互いに共通部分を持たない前記チェックノードの集合に基づく前記一部のメッセージを前記記憶部に転送する
請求項５に記載の復号装置。
【請求項７】
前記第２転送部は、
前記繰り返し単位による繰り返し回数が大きくなる極限で前記一部のメッセージそれぞれの前記記憶部に転送される回数が等しくなるように前記チェックノードの集合を異ならせて、前記チェックノードの集合に基づく前記一部のメッセージを前記記憶部に転送する
請求項５または請求項６に記載の復号装置。
【請求項８】
符号に応じて定められる変数ノードに対して変数ノード処理を行い第１のメッセージを出力し、
前記符号に応じて定められるチェックノードに対して前記第１のメッセージに基づきチェックノード処理を行い第２のメッセージを出力し、
前記第２のメッセージのうち一部のメッセージを記憶部に記憶し、
前記第１のメッセージに含まれるメッセージであって、前記チェックノードのうち既に前記記憶部に記憶された前記一部のメッセージに対応するチェックノードに転送されるべきメッセージを除外したメッセージを前記チェックノードに転送し、
前記第２のメッセージを前記変数ノードに転送すると共に、前記第２のメッセージのうち一部のメッセージを前記記憶部に転送する
復号方法。
【請求項９】
処理の繰り返し単位毎に一部のチェックノードの更新値を記憶し、
次の前記繰り返し単位における前記一部のチェックノードの更新値は前記記憶している更新値で代替し、
チェックノード処理を行う毎に全ての変数ノードの更新を行う
復号方法。
【請求項１０】
前記変数ノードに接続する前記チェックノードの数の平均値をＮ（Ｎは２を超える整数）とし、前記更新値を前記記憶している更新値で代替する前記一部のチェックノード数の全チェックノード数に対する割合は（Ｎ−２）／Ｎ以下である
請求項９に記載の復号方法。
【請求項１１】
前記更新値を前記記憶している更新値で代替する前記一部のチェックノードの集合は、前記繰り返し単位毎に異なる
請求項９または請求項１０に記載の復号方法。
【請求項１２】
連続する前記繰り返し単位では、前記更新値を前記記憶している更新値で代替する前記一部のチェックノードの集合は、互いに共通部分を含まない
請求項１１に記載の復号方法。
【請求項１３】
前記繰り返し単位毎の繰り返し数が大きくなる極限で、前記チェックノードそれぞれの前記更新値が前記記憶している更新値で代替される確率が等しくなる
請求項９乃至請求項１２の何れか１項に記載の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、復号装置および復号方法に関する。
【背景技術】
【０００２】
通信システムや記憶装置などに用いられる、強力な誤り訂正符号能力を持った符号方式としてＬＤＰＣ(Low-Density  Parity-Check)符号が知られている。このＬＤＰＣ符号は、パリティ検査行列を用いて行処理演算および列処理演算と呼ばれるメッセージ値の計算を繰り返し行い、受信語データの事後確率を求めることで復号を行う。ＬＤＰＣ符号は、既存のエラー訂正符号の中で最も理論限界に近いエラー訂正能力を有することから、通信システムや記憶装置において広く用いられている。
【０００３】
一方、近年の不揮発性の半導体記憶装置として主流となっているフラッシュメモリは、メモリセルの微細化や多値化に伴い、読み出し時に発生するエラーが深刻化している。そのため、従来から用いられているＢＣＨ符号ではエラー訂正能力不足となってきており、近年では、より高いエラー訂正能力を持つＬＤＰＣ符号が注目されている。それと共に、エラー訂正方式における世代間の互換性を保つため、ＬＤＰＣ符号の復号回路のオンチップ化技術が求められている。このオンチップ化により、ＬＤＰＣ符号の復号処理を半導体記憶装置が形成されるチップ上の回路で行うことで、半導体記憶装置の見かけ上のエラー発生率を一定以下に抑制することが可能となる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ming  Gu,  and  Shantanu  Chakrabartty,  IEEE  Journal  of  Solid-State  Circuits,  val.  46,  no.  6,  pp.  1433-1442  (2011).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、ＬＤＰＣ符号は、確率に基づきエラー訂正を行うため、複雑な実数演算を必要とする。特に、ＬＤＰＣ符号の復号計算におけるチェックノード処理は、確率値の和積計算が必要となり、大きな計算リソースが要求される。したがって、ＬＤＰＣ符号の復号処理をハードウェア化するためには、大規模なディジタル半導体回路が必要となり、オンチップ化が難しい。
【０００６】
そこで、ＬＤＰＣ符号の復号を行う半導体回路の規模を縮小するため、実数を電流で表現してアナログ回路により実数計算処理を行う方法も提案されている。しかしながら、電流によってデータ値を表現する場合、データ処理中は常に電流を流し続ける必要があり、膨大な電力を消費することになってしまうという問題点があった。
【０００７】
このように、従来の技術を用いてＬＤＰＣ符号にて十分なエラー訂正能力を得るためには、実数計算による復号処理を用いる必要があり、半導体集積回路などを用いた誤り訂正装置の実装が大規模化してしまうという問題点があった。
【０００８】
本発明が解決しようとする課題は、ＬＤＰＣ符号の復号処理をより小規模な構成により実現可能とする復号装置および復号方法を提供することにある。
【課題を解決するための手段】
【０００９】
実施形態の復号装置は、符号に応じて定められる変数ノードに対して変数ノード処理を行い第１のメッセージを出力し、符号に応じて定められるチェックノードに対して第１のメッセージに基づきチェックノード処理を行い第２のメッセージを出力し、第２のメッセージのうち一部のメッセージを記憶する。第１のメッセージに含まれるメッセージであって、チェックノードのうち既に記憶される一部のメッセージに対応するチェックノードに転送されるべきメッセージを除外したメッセージをチェックノードに転送し、第２のメッセージを変数ノードに転送すると共に、第２のメッセージのうち一部のメッセージを記憶する。
【図面の簡単な説明】
【００１０】
【図１】図１は、各実施形態に係る復号装置を含むメモリシステムの一例の構成を概略的に示す図である。
【図２】図２は、検査行列を表現するタナーグラフの例を示す図である。
【図３】図３は、実施形態に適用可能なチェックノード処理を説明するための図である。
【図４】図４は、確率伝播法によるＬＤＰＣ符号の復号処理の流れを概略的に示す図である。
【図５】図５は、各実施形態に係る、確率伝播法によるＬＤＰＣ符号の復号処理の流れを概略的に示す図である。
【図６】図６は、各実施形態に係る、一部のチェックノードの更新を休止させた場合の効果について説明するための図である。
【図７】図７は、第１の実施形態に係る復号装置の一例の構成を示すブロック図である。
【図８】図８は、第１の実施形態に係る、転送を除外するチェックノードの部分集合を各イタレーション間で異ならせる場合を示す図である。
【図９】図９は、転送を除外するチェックノードの部分集合を各イタレーション間で異ならせない場合を示す図である。
【図１０】図１０は、第２の実施形態に係る復号装置の一例の構成を示すブロック図である場合。
【図１１】図１１は、既存技術による復号装置の構成の一例を示すブロック図である。
【図１２】図１２は、第３の実施形態に適用可能な通信システムの一例の構成を示す図である。
【発明を実施するための形態】
【００１１】
（各実施形態に共通の構成）
以下、各実施形態に係る復号装置について説明する。各実施形態に係る復号装置は、低密度パリティ検査符号（ＬＤＰＣ  code：Low-Density  Parity-Check  code）の復号を行う。図１は、各実施形態に係る復号装置を含むメモリシステムの一例の構成を概略的に示す。
【００１２】
図１において、メモリシステム１は、メモリ部２と、符号化部３と、復号部４とを含む。入力データ５は、符号化部３に入力されてＬＤＰＣ符号に符号化され、メモリ部２に供給される。メモリ部２は、例えばコントローラと記憶媒体とを備え、メモリ部２に供給されたＬＤＰＣ符号は、コントローラにより記憶媒体に書き込まれる。第１の実施形態では、記憶媒体としてフラッシュメモリを用いるものとする。
【００１３】
これらメモリ部２、符号化部３および復号部４は、１つの半導体チップ内に組み込んで構成することができる。これに限らず、メモリ部２、符号化部３および復号部４を、それぞれ個別のハードウェアとして構成することもできる。さらに、符号化部３および復号部４を、ＣＰＵ(Central  Processing  Unit)上で動作するプログラムにより構成してもよい。
【００１４】
また、メモリ部２は、例えば外部から読み出し要求を受け取ると、コントローラにより記憶媒体からＬＤＰＣ符号を読み出す。読み出されたＬＤＰＣ符号は、復号部４に供給される。復号部４は、供給されたＬＤＰＣ符号を復号し、元の入力データ５を復元して出力データ６としてメモリシステム１から出力する。
【００１５】
なお、記憶媒体としてフラッシュメモリを用いた場合、情報の読み出しは、閾値電圧がハイかローかによって行われる。
【００１６】
先ず、ＬＤＰＣ符号について説明する。ＬＤＰＣ符号は、検査行列と呼ばれる、成分の大多数が０であり、少数の成分のみが１である疎(Low-Density)な行列によって特徴付けられる符号である。符号長に応じて大きな検査行列が必要となるが、以下では、説明のため検査行列Ｈを８×４行列であるとして説明する。次式（１）に、検査行列Ｈの例を示す。
【数１】
2016144052.tif 000003
【００１７】
検査行列Ｈの各行および各列に含まれる１の数を重みと呼び、全ての行および列の重みが０より大きくなるように検査行列を作成する。行重みおよび列重みがそれぞれ一定値である場合、この検査行列を正則と呼ぶ。式（１）に例示した検査行列Ｈは、行重みが全て４であり、列重みが全て２である正則行列である。
【００１８】
ＬＤＰＣ方式においては、通信路に送る、メモリに格納するなどの処理の対象のデータ列ｘを、ＨｃT＝０となるようなデータ列ｃに変換する。このデータ列ｃを符号と呼ぶ。つまり、ＬＤＰＣ方式において情報処理に用いられるデータは、元のデータ列ｘではなく、変換された符号ｃである。上述した符号化部３は、入力データ５によるデータ列に対して、この変換処理を施す。メモリ部２は、入力データ５が変換された符号ｃをフラッシュメモリに書き込む。
【００１９】
一般に、符号ｃは、データ列ｘよりデータ長の長いデータ列であり、データ列ｘに含まれる情報に加えて、エラー訂正に必要な情報が含まれる。一方、符号化自体は、１対１対応の写像であり、データ列ｘが与えられれば符号ｃが一意に決まり、逆に、符号ｃが与えられれば元のデータ列ｘは一意に決まる。また、（データ列ｘの長さ）／（符号ｃの長さ）を符号化率と呼び、符号化率が高い程、効率の良いエラー訂正方法であるといえる。
【００２０】
検査行列Ｈは、図２に示すタナーグラフで表現できる。タナーグラフは、ノード｛ｃ0，ｃ1，…，ｃ7｝とノード｛ｆ0，ｆ1，ｆ2，ｆ3｝とを上下に並べ、検査行列Ｈの成分ｈijについて、成分ｈij＝１の場合にのみ、直線で結んだグラフである。タナーグラフにおいて、ノード｛ｃi｝を変数ノード、ノード｛ｆj｝をチェックノードと呼ぶ。変数ノードｃiの各ノードは、検査行列Ｈの各列に対応しており、値が１である行の行番号と、結ばれているチェックノードｆjの番号とが一致している。一方、チェックノードｆjの各ノードは、検査行列Ｈの各行に対応しており、値が１である列の列番号と、結ばれている変数ノードｃiの番号とが一致している。
【００２１】
式（２）は、上述した式（１）の検査行列Ｈの場合の各変数ノード｛ｃi｝および各チェックノード｛ｆj｝の例を示す。
【数２】
2016144052.tif 000004
【００２２】
次に、ＬＤＰＣ符号における基本的な復号処理について説明する。以下の復号処理は、例えば上述した復号部４にて実行されるものとする。この場合、復号部４は、メモリ部２に格納された符号を読み出して復号し、元のデータを復元する。ＬＤＰＣ符号におけるエラー訂正方法として、確率伝播法(Belief  Propagation：ＢＰ法)を用いた方法が一般的に知られている。以下、確率伝播法について説明する。
【００２３】
先ず、各変数ノードｃiは、ある物理量の列ｙ=｛ｙi｝について、それぞれの値ｙiに対応するディジタル値が０である確率Ｑ0iを受信する。変数ノードｃiは、自身が接続するチェックノード｛ｆj，ｆh，…｝にこの確率Ｑ0iをメッセージ｛ｑij，ｑih，…｝として送信する（図３（ａ）参照）。
【００２４】
なお、物理量の列ｙは、例えばメモリ部２から読み出されたビット列である。メモリ部２は、記憶媒体としてフラッシュメモリを用いている場合、記憶媒体からのビット列の読み出しの際のしきい値電圧を取得し、取得したしきい値電圧に基づき、読み出したビット列について、確からしさを示す確率をビット毎に求め、しきい値電圧を確率値に変換する。各変数ノードｃiは、この各ビットの確率値を確率Ｑ0iとして受信することになる。
【００２５】
チェックノードｆjは、接続する変数ノード｛ｃi，ｃk，…｝から送信されたメッセージｑ＝｛ｑij，ｑkj，…｝を元に、パリティ条件を考慮の上、各変数ノード｛ｃi，ｃk，…｝がディジタルデータ値の１を持つ確率｛ｒji，ｒjk，…｝を計算し、メッセージｒijとして各変数ノード｛ｃi，ｃk，…｝に返信する（図３（ｂ）参照）。
【００２６】
ここで、チェックノードｆjは、変数ノードｃiに返送するメッセージｒjiを計算する際に、変数ノードｃi自身からのメッセージｑijを含めない。すなわち、変数ノードｃiは、メッセージｒjiによって、自身以外の変数ノードのメッセージを受け取ることになる。より具体的には、チェックノードｆjは、次式（３）に従いチェックノード処理を行い、メッセージｒjiの計算を行う。なお、式（３）において、値Ａ(ｊ)は、チェックノードｆjに接続する変数ノードの添字｛ｉ，ｋ，…｝の集合である。
【数３】
2016144052.tif 000005
【００２７】
変数ノードｃiは、接続する各々のチェックノード｛ｆj，ｆk，…｝から受け取ったメッセージ（確率）｛ｒji，ｒki，…｝に基づき変数ノード処理を行う。
【００２８】
すなわち、変数ノードｃiは、メッセージ｛ｒji，ｒki，…｝と、自身の持つ確率Ｑ0iとを用いて、受信したデータが元々０であった確率Ｑ’iを計算する。変数ノードｃiは、計算の結果、確率Ｑ’iが１／２以上であれば、受信データの値が１であると仮定し、確率Ｑ’iが１／２未満であれは、受信データの値が０であると仮定する。
【００２９】
ＬＤＰＣ方式によるエラー訂正では、この仮定値を用いてパリティチェックを行う。より具体的には、仮定値の列ｃtemp＝｛ｃ0temp，ｃ1temp，…｝に対して、ＨｃtempT＝０となるか否かを判定する。若し、ＨｃtempT＝０であれば、仮定値ｃtempが格納されていたディジタルデータ列であると推定し、計算を終了する。一方、ＨｃtempT＝０でなければ、変数ノードｃiは、メッセージｑ＝｛ｑij，ｑkj，…｝を再計算し、計算結果をチェックノード｛ｆj，ｆk，…｝に送信する（図３（ｂ）参照）。
【００３０】
変数ノードｃiにおける計算は、具体的には、下記の式（４）のようになる。
【数４】
2016144052.tif 000006
【００３１】
ここで、式（４）中の値Ｂ(ｉ)は、変数ノードｃiに接続するチェックノードｆの添字｛ｊ，ｋ，…｝の集合である。また、値Ｋは、下記の式（５）を満たすように決定される規格化定数である。
【数５】
2016144052.tif 000007
【００３２】
ここで、変数ノードｃiからチェックノードｆjに送信されるメッセージｑijは、確率Ｑ01と確率｛ｒki，ｒli，…｝を元に計算した、「変数ノードｃiのディジタルデータ値が１である確率」であり、チェックノードｆjからのメッセージｒjiは含まれない。すなわち、チェックノードｆjは、メッセージｑijにより自身以外のチェックノードのメッセージを受け取ることになる。
【００３３】
メッセージｑを受け取ったチェックノードは、受け取ったメッセージｑを元にメッセージ（確率）ｒを計算して、変数ノードに返送する。以上のアルゴリズムを、パリティ条件が満たされるまで繰り返し実行する。すなわち、計算したメッセージｒを用いて仮定値の列ｃtempを更新し、更新した仮定値の列ｃtempに対して、ＨｃtempT＝が０になるまで、アルゴリズムを繰り返す。
【００３４】
各実施形態においては、変数ノードがメッセージｑを計算してチェックノードに送信し、チェックノードからメッセージｒを受信するまでをエラー訂正処理の単位とし、その単位を「イタレーション」と呼ぶことにする。
【００３５】
図４は、上述した、確率伝播法によるＬＤＰＣ符号の復号処理の流れを概略的に示す。なお、図４は、検査行列Ｈとして式（１）に例示した４行８列の行列を用いた例である。すなわち、図４では、８個の変数ノード｛ｃ1，ｃ2，ｃ3，ｃ4，ｃ5，ｃ6，ｃ7｝を含む変数ノードｃiと、４個のチェックノード｛ｆ0，ｆ1，ｆ2，ｆ3｝を含むチェックノードｆjとが示されている。
【００３６】
図４において、ステップＳ１で、変数ノードｃiは、例えばメモリ部２から読み出された８ビットの読み出しビットそれぞれに対応する確率Ｑ0iをそれぞれ受信する。変数ノードｃiは、受信した各確率Ｑ0iに基づき仮定値の列ｃtempを更新すると共に、各確率Ｑ0iをメッセージｑijとして、検査行列Ｈに従いチェックノードｆjに振り分ける（ステップＳ２）。
【００３７】
チェックノードｆjは、受信した各メッセージｑijに基づき式（３）に従いチェックノード処理を行い（ステップＳ３）、結果をメッセージｒjiとして、検査行列Ｈに従い変数ノードｃiに返送する（ステップＳ４）。各メッセージｒjiは、変数ノードｃiに受信される（ステップＳ５）。
【００３８】
変数ノードｃiは、受信した各メッセージｒjiに基づき変数ノード処理を行う。変数ノードｃiは、変数ノード処理の結果、仮定値の列ｃtempに対してＨｃT＝０とならないと判定した場合、メッセージｑijを再計算する。
【００３９】
変数ノードｃiは、再計算したメッセージｑijをチェックノードｆjに送信し（ステップＳ６）、チェックノードｆjは、受信したメッセージｑijに基づきチェックノード処理を行い（ステップＳ７）、結果のメッセージｒjiを変数ノードｃiに送信する（ステップＳ８）。このメッセージｒjiは、変数ノードｃiに受信される（ステップＳ９）。変数ノードｃiは、受信したメッセージｒjiに基づき仮定値の列ｃtempを更新する。
【００４０】
以降、ステップＳ５での変数ノードｃiにおけるメッセージｑijの計算から、ステップＳ９でのチェックノードｆjにおけるメッセージｒjiの受信までの処理を繰り返し単位として、パリティ条件が満たされるまで処理が繰り返される。この繰り返し単位が、上述したイタレーションに相当する。
【００４１】
なお、受信した各確率Ｑ0iに基づく仮定値の列ｃtempの更新および各確率Ｑ0iのチェックノードｆjへの送信の処理から、ステップＳ５でのメッセージｒjiの受信までの処理も、上述の繰り返し単位の処理と同等の処理であると見做す。
【００４２】
（各実施形態によるエラー訂正処理の詳細）
確率伝播法によるエラー訂正処理では、上述した通り、変数ノードとチェックノードとの間で確率値のやり取りを行うことによって、変数ノードにおける元データを推定するための確率Ｑ’を計算している。一連の処理において最終的に必要な情報は、確率Ｑ’が１／２より大きいか否かという情報であり、具体的な値の詳細については、重要性が低い。そのため、変数ノード処理およびチェックノード処理における確率の計算は、厳密である必要性が低いといえる。特に、変数ノード処理における確率計算は、各チェックノードから送信されたメッセージを相乗して行われるため、１つのチェックノードからのメッセージが最終的な結果に与える影響はそれほど大きくないと考えられる。
【００４３】
したがって、変数ノードに送信されるチェックノードからのメッセージは、イタレーション毎に更新される一方で、チェックノードの一部でこの更新がなされなかったとしても、最終的な結果に大きな影響は及ぼさないと考えられる。
【００４４】
各実施形態では、この点を考慮して、イタレーションにおいて、各チェックノード｛ｆ0，ｆ1，…｝のうち一部のチェックノードの更新を休止させ、チェックノード処理を休止させる。更新を休止させるチェックノードは、連続するイタレーション間で異ならせるようにする。休止させるチェックノードから変数ノードに送信されるべきメッセージは、前回のイタレーションの際に当該チェックノードにおいて計算されたメッセージをメモリなどに記憶させておき、このメモリに記憶されたメッセージで代替する。
【００４５】
このように、イタレーションにおいて各チェックノード｛ｆ0，ｆ1，…｝のうち一部のチェックノードの更新を休止させることで、チェックノード処理を行うための構成を削減することができる。また、チェックノード処理を行うための構成によっては、チェックノード処理をより高速に実行することが可能となる。
【００４６】
図５は、各実施形態に係る、確率伝播法によるＬＤＰＣ符号の復号処理の流れを概略的に示す。なお、図５において、上述した図４と同様に、検査行列Ｈとして式（１）に例示した４行８列の行列を用い、８個の変数ノード｛ｃ1，ｃ2，ｃ3，ｃ4，ｃ5，ｃ6，ｃ7｝を含む変数ノードｃiと、４個のチェックノード｛ｆ0，ｆ1，ｆ2，ｆ3｝を含むチェックノードｆjとが示されている。また、図５において、更新を休止させるチェックノードｆjは、斜線および「休」の文字を付して示している。
【００４７】
なお、変数ノードおよびチェックノードは、実際には、メモリやレジスタといった記憶媒体を用いて構成される。
【００４８】
第ｋイタレーションでは、チェックノードｆ0の更新を休止させる。すなわち、第ｋイタレーションでは、チェックノードｆ0は、変数ノードｃiからのメッセージｑijを受け取らず、値すなわち確率ｒ0i）の更新は行わない。チェックノードｆ0から変数ノードｃiへ返送するメッセージｒ0iは、第ｋ−１イタレーションにおいて得られた、別途記憶しているメッセージｒ0iで代替する。
【００４９】
第ｋイタレーションにおいて、その他のチェックノードｆ1〜ｆ3は、通常通り値の更新を行い、メッセージを変数ノードｃiに返送する。また、次の第ｋ＋１イタレーションにおいて値の更新を行わないチェックノードｆ1のメッセージｒ1iは、別途メモリに記憶する。
【００５０】
同様に、第ｋ＋１、第ｋ＋２および第ｋ＋３イタレーションでは、それぞれチェックノードｆ1、ｆ2およびｆ3の更新が休止される。したがって、第ｋ＋１、第ｋ＋２および第ｋ＋３イタレーションでは、各チェックノードｆ1、ｆ2およびｆ3は、変数ノードｃiからのメッセージｑijは受け取らず、値の更新も行わない。これらのチェックノードｆ1、ｆ2およびｆ3から変数ノードｃiへ返送すべきメッセージは、直前のイタレーションにおいて記憶していた値で代替し、且つ、次のイタレーションで更新を行わないチェックノードのメッセージは別途メモリに記憶する。
【００５１】
このように、各イタレーションにおいて各チェックノードｆ0〜ｆ3のうち一部のチェックノードの更新を休止させることで、チェックノード処理を、検査行列Ｈにより規定されるチェックノード数よりも少ないチェックノード数で実行することができる。これにより、チェックノード処理による計算量（並列度）を削減し、回路規模を縮小することが可能となる。
【００５２】
なお、図５の例では、第ｋ−１イタレーションは、イタレーションを繰り返す繰り返し処理の最初のイタレーションである。この最初のイタレーションにおける処理は、図４のステップＳ１〜ステップＳ５における処理と略同様である。すなわち、第ｋ−１イタレーションでは、変数ノードｃiは、例えばメモリ部２から読み出しビットそれぞれに対応する確率Ｑ0iを受信し、仮定値の列ｃtempの更新およびメッセージｑijの各チェックノードｆ0〜ｆ3への送信を行う。
【００５３】
このとき、全てのチェックノードｆ0〜ｆ3にメッセージｑijを送信し各チェックノードｆ0〜ｆ3でチェックノード処理を行うと、チェックノード処理の削減の効果が十分に得られないことになる。
【００５４】
そこで、この最初のイタレーションにおいては、次のイタレーション（図５の例では第ｋイタレーション）で更新を休止させないチェックノード（例えばチェックノードｆ3）に対してメッセージｑijを送信せず、当該チェックノードの更新を休止させる。そして、当該チェックノードから変数ノードｃiに送信すべきメッセージｒjiは、例えばメモリに予め記憶されている固定値を用いる。固定値としては、例えば１／２を用いることが考えられる。固定値は、１／２に限定されず、確率の値として利用可能な値であればよい。
【００５５】
次に、図６を用いて、各実施形態に係る、チェックノードのうち一部のチェックノードの更新を休止させた場合の効果について説明する。図６は、ＬＤＰＣ符号によるエラー訂正処理において、最初のイタレーションを除く各イタレーションにおいてチェックノード更新の休止率を異ならせた場合のエラービット数の例を示す。なお、図６は、符号長１ｋ（キロ）ビットのＬＤＰＣ符号によりエラー訂正を行った例である。更新を休止したチェックノードは、直前のイタレーションにおいて記憶された値で代替している。
【００５６】
図６において、「○（丸印）」は休止率が０、「＊（星印）」、「×（バツ印）」、「△（三角印）」、「□（四角印）」および「◇（菱型印）」は、それぞれ休止率が１／１０、２／１０、３／１０、４／１０および５／１０を示す。また、図６において、縦軸はエラー訂正処理を行った結果の平均エラービット数、横軸はイタレーションの回数をそれぞれ示す。
【００５７】
チェックノード更新の休止率が３／１０以下の場合、イタレーションを繰り返すことで平均エラービット数が減少してゆくことが分かる。一方、チェックノード更新の休止率が４／１０以上では、イタレーションを繰り返しても平均エラービット数が減少せず、エラーフロアの現象が生じる。
【００５８】
なお、更新を休止するチェックノードは、イタレーション毎に異ならせることが望ましく、各チェックノードの更新の休止率は、全てのチェックノードで同程度であることが望ましい。チェックノード更新の休止率にチェックノード間で偏りがあると、一部の変数ノードでエラーが訂正されにくくなるおそれがあるからである。
【００５９】
図６に示すエラー訂正処理においては、各変数ノードに３つのチェックノードが接続されている検査行列を用いた。図３および式（３）を用いて説明したように、変数ノードからチェックノードへ送るメッセージは、そのチェックノードを除く、残りのチェックノードから返送されたメッセージを利用している。したがって、図６の例の場合、１つのチェックノードに送られるメッセージは、別の２個のチェックノードの情報を元にしている。
【００６０】
更新を休止するチェックノード数が全体のチェックノード数の１／３である場合は、この２個のチェックノードのうち１個が更新を休止している。一方、更新を休止するチェックノード数が全体のチェックノード数の１／３を超える場合は、２個のチェックノードの両方が休止している状態が生じる。この場合、変数ノードからチェックノードへ返送するメッセージの更新も行われないため、エラー訂正が適切に行われなくなる。図６において、休止率が４／１０および５／１０においてエラーフロアが現れるのは、このためである。
【００６１】
ここで、各イタレーションにおいて、全体のチェックノードのうち一部のチェックノードで更新を休止する場合の、チェックノードの休止率について考える。なお、各変数ノードに接続されているチェックノード数の平均値をＮ個（Ｎ＞２）とする。上述のように、各変数ノードにおいて更新を休止するチェックノード数の、チェックノード数の総数に対する割合が（Ｎ−２）／Ｎを越える場合、変数ノードからチェックノードへ返信するメッセージの更新が行われない状態が生じ、適切なエラー訂正ができなくなるおそれがある。したがって、各変数ノードにおいて更新を休止するチェックノード数の全チェックノード数に対する割合は、（Ｎ−２）／Ｎ以下であることが望ましい。
【００６２】
（第１の実施形態）
図７は、第１の実施形態に係る復号装置の一例の構成を示す。図７において、復号部４は、変数ノード処理部４０と、第１転送部４１と、チェックノード処理部４２と、第２転送部４３と、振り分け制御部４４と、メッセージ記憶部４５とを含む。また、メモリ部２は、メモリ２０と、閾値読み出し部２１と、閾値・確率変換部２２と、初期確率記憶部２３とを含む。
【００６３】
復号部４をハードウェアで構成する場合、復号部４に含まれる各部は、例えば１つの半導体チップ上に構成される。これに限らず、復号部４に含まれる各部の一部または全部を個別のハードウェアによって構成してもよい。また、メッセージ記憶部４５は、例えば、書き換え可能な不揮発性メモリと、当該不揮発性メモリに対するデータの読み書きを行うための構成とを含む。メモリ部２についても同様に、メモリ部２に含まれる各部は、例えば１つの半導体チップ上に構成される。また、メモリ部２に含まれる各部の一部または全部を個別のハードウェアによって構成することもできる。
【００６４】
なお、復号部４およびメモリ部２は、例えば、これら復号部４およびメモリ部２が含まれるメモリシステム１の上位の構成からの制御に従い動作する。これに限らず、メモリシステム１にコントローラを設け、復号部４およびメモリ部２は、このコントローラにより動作が制御されるようにしてもよい。また、以下では、説明のため、検査行列Ｈにより定められるチェックノード数が６個であるものとする。
【００６５】
メモリ部２において、メモリ２０は、記憶媒体であり、例えばフラッシュメモリである。閾値読み出し部２１は、メモリ２０からの読み出しの際のしきい値電圧を取得する。閾値・確率変換部２２は、閾値読み出し部２１に取得された閾値電圧に基づき、読み出したビット列について、確からしさを示す確率をビット毎に求め、閾値電圧を確率に変換する。閾値・確率変換器２２で求められた各ビットの確率値は、初期確率記憶部２３に記憶される。
【００６６】
復号部４において、変数ノード処理部４０は、初期確率記憶部２３に記憶された確率値または後述する第２転送部４３から送信されるメッセージ（確率値）ｒjiに基づき変数ノード処理を行い、確率Ｑ0iを算出する。変数ノード処理部４０は、算出した各確率Ｑ0iをメッセージｑijとして、それぞれ第１転送部４１に送信する。
【００６７】
第１転送部４１は、変数ノード処理部４０からメッセージｑijを受信すると、その旨を振り分け制御部４４に通知する。また、第１転送部４１は、振り分け制御部４４の制御に従い、メッセージｑijのうちチェックノード処理部４２においてチェックノード処理を行うべきメッセージを選択してチェックノード処理部４２に転送する。
【００６８】
チェックノード処理部４２は、検査行列Ｈに応じて予め定められたチェックノード数未満の数のチェックノードに対するチェックノード処理を行い、確率ｒijを算出する。例えば、チェックノード処理部４２は、検査行列Ｈに応じて予め定められた６個のチェックノード数に対し、４個のチェックノードに対するチェックノード処理を行う。チェックノード処理部４２は、チェックノード処理により算出された確率ｒjiによりチェックノードを更新し、当該確率ｒjiをメッセージｒjiとして第２転送部４３に送信する。
【００６９】
第２転送部４３は、振り分け制御部４４の制御に従い、チェックノード処理部４２から送信されたメッセージｒjiのうち指定された一部のメッセージをメッセージ記憶部４５に記憶する。この例では、検査行列Ｈに応じて予め定められた６個のチェックノードに対し、４個のチェックノードに対するチェックノード処理を行うため、少なくともその差分の２個のチェックノードに対応するメッセージをメッセージ記憶部４５に記憶する。
【００７０】
また、第２転送部４３は、振り分け制御部４４の制御に従い、チェックノード処理部４２から送信されたメッセージｒjiと、メッセージ記憶部４５に前回のイタレーションにおいて記憶されたメッセージとを、それぞれ適切な変数ノードに供給されるように、変数ノード処理部４０に送信する。変数ノード処理部４０は、変数ノード毎に確率Ｑ0i’を算出して仮定値の列ｃtempを求める。
【００７１】
判定部４６は、変数ノード処理部４０で求められた仮定値の列ｃtempに対してＨｃtemp＝０が成り立つか否かを判定する。判定部４６は、成り立つと判定した場合、変数ノード毎に算出された確率Ｑ0iをそれぞれビット値に変換して、例えばこのメモリシステム１の上位の構成に対して出力する。成り立たないと判定した場合は、その旨を上位構成に対して通知する。
【００７２】
次に、振り分け制御部４４における第ｋイタレーションの処理について、より詳細に説明する。振り分け制御部４４は、第１転送部４１から、メッセージｑijを受け取った旨の通知を受けると、受け取った各メッセージｑijの転送先を判定し、チェックノード処理部４２における判定した転送先に各メッセージｑijを転送する。
【００７３】
このとき、振り分け制御部４４は、全てのチェックノードｆjのうち一部のチェックノードを含む部分集合Ａに属するチェックノードｆAに送るべきメッセージｑiAをチェックノード処理部４２に転送しないように、第１転送部４１を制御する。換言すれば、振り分け制御部４４は、全てのチェックノードｆjに送るべきメッセージｑijから部分集合Ａに含まれるチェックノードｆAに送るべきメッセージｑiAを除外したメッセージ（メッセージｑi(j-A)とする）をチェックノード処理部４２に転送する。これにより、チェックノードｆAに対するチェックノード処理が休止され、チェックノードｆAの更新が行われないようになる。
【００７４】
第１転送部４１は、この制御に従い、メッセージｑi(j-A)をチェックノード処理部４２に転送する。
【００７５】
チェックノード処理部４２は、それぞれのチェックノードに対応するチェックノード処理を行う。ここで、部分集合Ａに属するチェックノードｆAに送るべきメッセージｑiAは、チェックノード処理部４２に転送されていないため、チェックノード処理部４２は、部分集合Ａに属するチェックノードｆAに対応する処理を行わない。チェックノード処理部４２は、チェックノード処理によって生成したメッセージｒ(j-A)iを第２転送部４３に送信する。このメッセージｒ(j-A)iは、全てのチェックノードｆjのうちチェックノードｆAを除外したチェックノードに対するチェックノード処理により生成されたメッセージである。
【００７６】
振り分け制御部４４は、メッセージ記憶部４５から、前回のイタレーション（この場合は第ｋ−１イタレーション）において記憶した部分集合ＡによるメッセージｒAi’を読み出すように第２転送部４３を制御する。この、メッセージ記憶部４５から読み出したメッセージｒAi’は、第ｋイタレーションでチェックノード処理部４２において除外され転送されなかったメッセージｒAiの代替のメッセージとなる。
【００７７】
なお、１回目のイタレーション（第１イタレーション）による処理の実行にあたり、メッセージ記憶部４５に対して、初期値となるメッセージを予め記憶させておく。この初期値となるメッセージは、確率値として利用可能な値であれば、特に限定されない。例えば、１／２を初期値としてメッセージ記憶部４５に記憶させておくことが考えられる。
【００７８】
振り分け制御部４４は、メッセージ記憶部４５から読み出したメッセージｒAi’と、チェックノード処理部４２から転送されたメッセージｒ(j-A)iとを、変数ノード処理部４０に転送するように、第２転送部４３を制御する。このとき、振り分け制御部４４は、これらメッセージｒAi’およびメッセージｒ(j-A)iの転送先を判定し、変数ノード処理部４０における判定した転送先に各メッセージを転送するように、第２転送部４３を制御する。
【００７９】
また、振り分け制御部４４は、全てのチェックノードｆjのうち、次の第ｋ＋１イタレーションの際にチェックノード処理を休止する、部分集合Ｂに属するチェックノードｆBから送られたメッセージ（メッセージｒBiとする）をメッセージ記憶部４５に記憶させるように、第２転送部４３を制御する。
【００８０】
一例として、振り分け制御部４４は、上述した図５に示されるように、第ｋイタレーション、第ｋ＋１イタレーション、…において、チェックノードｆ0、チェックノードｆ1、…のように、各チェックノードｆ0〜ｆ3から、チェックノード処理を休止させるチェックノードを順次に選択することができる。これに限らず、振り分け制御部４４は、乱数などを用い、チェックノード処理を休止させるチェックノードを、各チェックノードｆ0〜ｆ3からランダムに選択してもよい。さらに、振り分け制御部４４は、予め作成されたテーブルに従い、チェックノード処理を休止させるチェックノードを選択してもよい。
【００８１】
第２転送部４３は、これらの制御に従い、メッセージｒAi’およびメッセージｒ(j-A)iを変数ノード処理部４０の判定した転送先に転送すると共に、メッセージｒBiをメッセージ記憶部４５に記憶させる。
【００８２】
変数ノード処理部４０は、第２転送部４３から受信したメッセージｒAi’およびメッセージｒ(j-A)iを用いて、各変数ノードにおいてビットが０（または１）である確率Ｑ0i’の値をそれぞれ計算する。変数ノード処理部４０は、算出した各確率Ｑ0i’の値を、判定部４６に送信する。変数ノード処理部４０が各確率Ｑ0i’の値を判定部４６に送信する処理までが、第ｋイタレーションの処理である。
【００８３】
判定部４６は、各確率Ｑ0i’の値に基づき、計算が収束したか否かを判定する。すなわち、判定部４６は、各確率Ｑ0i’の値に基づき、仮定値の列ｃtempに対してＨｃtempTの値が収束したか否かを判定する。収束したと判定した場合、各確率Ｑ0i’の値をそのまま、またはビット値に変換して上位構成に対して出力する。
【００８４】
一方、収束していないと判定した場合、その旨を示す通知を例えば上位構成に送信する。この場合、上位構成からの制御により、次の第ｋ＋１イタレーションの処理が開始される。
【００８５】
第ｋ＋１イタレーションでは、振り分け制御部４４は、変数ノード処理部４０からのメッセージｑijが第１転送部４１に受信されると、受信したメッセージｑijの転送先を判定する。そして、振り分け制御部４４は、全てのチェックノードｆjのうち一部のチェックノードを含み、且つ、上述の部分集合Ａと異なる部分集合Ｂに属するチェックノードｆBに送るべきメッセージｑiBを除外したメッセージ（メッセージｑi(j-B)とする）をチェックノード処理部４２の適切なチェックノードに転送するように、第１転送部４１を制御する。
【００８６】
以上のように、第１の実施形態に係る復号部４は、変数ノード処理部４０からチェックノード処理部４２に送るメッセージｑijのうち、一部のチェックノードへ送るべきメッセージを除外してチェックノード処理部４２に送る。そして、復号部４は、メッセージ記憶部４５に記憶している過去のメッセージを、除外したメッセージに対して代替して変数ノード処理部４０で利用するようにしている。これにより、第１の実施形態に係る復号部４では、チェックノード処理の計算量を低減することができ、既存の構成と比較して、チェックノード処理部４２の回路規模を小さくすることができる。
【００８７】
ところで、上述した構成において、第１転送部４１が転送を除外するチェックノードの部分集合は、各イタレーション間で異ならせるようにすると好ましい。さらに、連続するイタレーション間では、第１転送部４１が転送を除外するチェックノードの部分集合が互いに重複部分を持たないようにすると、より好ましい。
【００８８】
以下、このことについて、図８および図９を用いてより具体的に説明する。なお、図８および図９において、チェックノードは、互いに重複部分を持たない４個の部分集合２０２10、２０２11、２０２12および２０２13に分割されている。なお、図８および図９において、チェックノード処理が休止される部分集合は、斜線を付して示している。
【００８９】
図８は、第１の実施形態に係る復号処理を概略的に示す。第１の実施形態では、上述したように、イタレーション間で、チェックノード処理を休止させるチェックノードを異ならせている。
【００９０】
図８の例では、第ｋイタレーションのチェックノード処理２０２1において、部分集合２０２13に対するチェックノード処理が休止され、部分集合２０２13に含まれるチェックノードの更新が行われない。一方、他の部分集合２０２10〜２０２12については、チェックノード処理が実行されチェックノードが更新される。このチェックノードが更新された部分集合２０２10〜２０２12に対するチェックノード処理により生成された各メッセージが、次の第ｋ＋１イタレーションにおける変数ノード処理２００2に送られる。
【００９１】
また、変数ノード処理２００2に対して、第ｋイタレーションで更新が行われなかった部分集合２０２13に対する、前回の第ｋ−１イタレーションでのチェックノード処理により生成され記憶されたメッセージ２０１1が、第ｋイタレーションにおける部分集合２０２13に対応するメッセージの代替メッセージとして変数ノード処理２００2に送られる。
【００９２】
さらに、第ｋイタレーションにおいて、次の第ｋ＋１イタレーションで更新を行わない部分集合２０２13に対するチェックノード処理により生成されたメッセージ２０１2が記憶される。
【００９３】
第ｋ＋１イタレーションにおいて、チェックノード処理２０２1で生成された部分集合２０２10〜２０２12によるメッセージと、記憶されたメッセージ２０１1とを用いて変数ノード処理２００2が実行される。変数ノード処理２００2で生成された各メッセージは、チェックノード処理２０２2に送られる。
【００９４】
チェックノード処理２０２2では、第ｋイタレーションにおいてチェックノート処理が休止された部分集合２０２13と異なる部分集合２０２12に対するチェックノード処理が休止され、部分集合２０２12に含まれるチェックノードの更新が行われない。一方、他の部分集合２０２10、２０２11および２０２13については、チェックノード処理が実行されチェックノードが更新される。このチェックノードが更新された部分集合２０２10、２０２11および２０２13に対するチェックノード処理により生成された各メッセージが、次の第ｋ＋２イタレーションにおける変数ノード処理２００3に送られる。
【００９５】
また、変数ノード処理２００3に対して、第ｋ＋１イタレーションで更新が行われなかった部分集合２０２12に対する、前回の第ｋイタレーションでのチェックノード処理により生成され記憶されたメッセージ２０１2が、第ｋイタレーションにおける部分集合２０２12に対応するメッセージの代替メッセージとして変数ノード処理２００3に送られる。さらに、第ｋ＋１イタレーションにおいて、次の第ｋ＋２イタレーションで更新を行わない部分集合２０２11に対するチェックノード処理により生成されたメッセージ２０１3が記憶される。
【００９６】
このように、第１の実施形態に係る復号処理では、変数ノード処理２００x（添字ｘは、１、２、…）からチェックノード処理２０２xにメッセージを転送する際に、一部のチェックノードへ送られるべきメッセージを転送しない。したがって、当該一部のチェックノードの更新は行われず、前回のイタレーションにおいて記憶されたメッセージが代替メッセージとして変数ノード処理２００xに転送される。
【００９７】
図９は、イタレーション間で同一のチェックノードのチェックノード処理を休止させる例を示す。なお、図９において、上述した図８と共通する部分には同一の符号を付して、詳細な説明を省略する。
【００９８】
図９の例では、各イタレーションの各チェックノード処理２０２1、２０２2および２０２3において、同一の部分集合２０２13に対するチェックノード処理を休止させている。この場合、例えば第ｋ＋１イタレーションにおける代替用に記憶させるためのメッセージ２０１2（図８参照）を第ｋイタレーションで生成することができない。そのため、第ｋ＋１イタレーションにおける変数ノード処理２００2では、第ｋイタレーションと同じメッセージ２０１1を使うことになる。この場合、計算が収束しにくくなり、エラーフロアが生じるおそれがある。
【００９９】
したがって、第ｋイタレーションにおいて更新されないチェックノードの集合ＣKと、第ｋ＋１イタレーションにおいて更新されないチェックノードの集合Ｃk+1は、異ならせることが望ましい。また、チェックノードの集合Ｃkと集合Ｃk+1との間で共通部分が存在する場合、共通部分に属するチェックノードの更新頻度が低下するため、計算が収束しにくくなるおそれがある。したがって、集合Ｃkと集合Ｃk+1との間で共通部分を持たないことが望ましい。
【０１００】
さらに、更新されないチェックノードに偏りが発生しないように、各チェックノードのメッセージが過去のイタレーションにおいて記憶されたメッセージによって代替される頻度は、全てのチェックノード間で一定であることが望ましい。例えば、当該代替される頻度が、イタレーション回数が大きくなる極限において全てのチェックノードにおいて等しくなるように、チェックノード処理を休止させるチェックノードを各イタレーション間で振り分ける。チェックノード処理を休止させるチェックノードは、各イタレーション間で順次に選択してもよいし、乱数などを用いてランダムに選択してもよい。また、予め作成したテーブルに従い、チェックノード処理を休止させるチェックノードを選択してもよい。
【０１０１】
（第２の実施形態）
次に、第２の実施形態について説明する。第２の実施形態は、図７を用いて説明した第１の実施形態に係るチェックノード処理部４２において、それぞれ式（３）に示したチェックノードの演算を実行する複数のチェックノード演算部を並列に設けた例である。
【０１０２】
図１０は、第２の実施形態に係る復号装置の一例の構成を示す。なお、図１０において、上述した図７と共通する部分には同一の符号を付して、詳細な説明を省略する。また、以下では、説明のため、検査行列Ｈにより定められるチェックノード数が６個であるものとする。
【０１０３】
図１０の例では、チェックノード処理部４２’は、検査行列Ｈにより定められるチェックノード数より少ない、４個のチェックノード演算部４２０1、４２０2、４２０3および４２０4を含む。したがって、各イタレーションにおけるチェックノードの更新の休止率は、１／３となる。各チェックノード演算部４２０1、４２０2、４２０3および４２０4は、イタレーション毎に１回または複数回のチェックノード演算を行う。
【０１０４】
振り分け制御部４４は、第１転送部４１から、メッセージｑijを受け取った旨の通知を受けると、受け取った各メッセージｑijの転送先を判定する。そして、振り分け制御部４４は、転送先の判定結果に従い、各メッセージｑijを各チェックノード演算部４２０1、４２０2、４２０3および４２０4に転送するように第１転送部４１を制御する。このとき、振り分け制御部４４は、各メッセージｑijのうち２個のチェックノードに送るべきメッセージｑi2をチェックノード処理部４２’に転送しないように、第１転送部４１を制御する。
【０１０５】
第１転送部４１は、この制御に従い、メッセージｑijからメッセージｑi2を除外したメッセージｑi(j-2)をチェックノード処理部４２’に転送する。各メッセージｑi(j-2)は、各チェックノード演算部４２０1、４２０2、４２０3および４２０4にそれぞれ転送される。
【０１０６】
チェックノード処理部４２’において、各チェックノード演算部４２０1、４２０2、４２０3および４２０4は、転送された各メッセージｑi(j-2)に基づきそれぞれチェックノード処理を行う。チェックノード処理部４２’は、各チェックノード演算部４２０1、４２０2、４２０3および４２０4により算出されたメッセージｒ(j-2)iを第２転送部４３に転送する。
【０１０７】
振り分け制御部４４は、メッセージ記憶部４５から、前回のイタレーションにおいて記憶した、２個のチェックノードによるメッセージｒｊi’を読み出すように第２転送部４３を制御する。この、メッセージ記憶部４５から読み出したメッセージｒji’は、今回のイタレーションでチェックノード処理部４２において除外され転送されなかったメッセージの代替のメッセージとなる。
【０１０８】
振り分け制御部４４は、メッセージ記憶部４５から読み出したメッセージｒji’と、チェックノード処理部４２から転送されたメッセージｒ(j-2)iとを変数ノード処理部４０に転送するように、第２転送部４３を制御する。このとき、振り分け制御部４４は、これらメッセージｒAi’およびメッセージｒ(j-A)iの転送先を判定し、変数ノード処理部４０における判定した転送先に各メッセージを転送するように、第２転送部４３を制御する。
【０１０９】
また、振り分け制御部４４は、全てのチェックノードｆjのうち、次のイタレーションの際にチェックノード処理を休止する２個のチェックノードから送られたメッセージをメッセージ記憶部４５に記憶させるように、第２転送部４３を制御する。
【０１１０】
第２転送部４３は、これらの制御に従い、メッセージｒji’およびメッセージｒ(j-2)iを変数ノード処理部４０の判定した転送先に転送すると共に、次のイタレーションにおいてチェックノード処理を休止させる２個のチェックノードから送られたメッセージをメッセージ記憶部４５に記憶させる。
【０１１１】
図１１は、既存技術による復号装置の構成の一例を示す。なお、図１１において、図７および図１０と共通する部分には同一の符号を付して、詳細な説明を省略する。図１１に例示されるように、既存技術による復号部４”では、チェックノード処理部１０１は、検査行列Ｈにより予め定められるチェックノード数に応じた数（この例では６個）のチェックノード演算部１０１1、１０１2、…、１０１6を備える必要があった。
【０１１２】
図１０に示すチェックノード演算部４２０1〜４２０4、および、図１１に示すチェックノード演算部１０１1〜１０１6は、それぞれ上述した式（３）の演算を行う。この式（３）は、（変数ノード数−１）回の乗算を行う総乗演算であり、変数ノード数によっては大きな回路規模が必要となる可能性がある。
【０１１３】
第２の実施形態では、検査行列Ｈにより予め定められるチェックノード数よりも少ない数のチェックノード演算部でチェックノード処理が可能であるため、既存技術による構成に対して、チェックノード処理部の回路規模を小さくすることができる。より具体的には、各イタレーションにおいて、全チェックノード数をＣ個とし、チェックノード演算部が式（３）によるチェックノードの計算を行う平均回数をＬ回（但し、Ｌ＜２×Ｃ）とすれば、第２の実施形態に係る構成では、チェックノード演算部の数をＣ／Ｌ（個）よりも少なくすることができる。したがって、第２の実施形態に係る構成では、チェックノード処理部の回路規模を、既存の構成と比べて小さくすることができる。
【０１１４】
（第３の実施形態）
次に、第３の実施形態について説明する。上述では、各実施形態が図１のメモリシステム１の復号部４に適用されるように説明したが、これはこの例に限定されない。すなわち、上述の各実施形態は、有線または無線の通信路上でデータの送受信を行う通信システムに適用することも可能である。
【０１１５】
図１２は、第３の実施形態に適用可能な通信システムの一例の構成を示す。図１２において、入力データ５’が符号化部３’に入力され、ＬＤＰＣ符号に符号化される。符号化されたＬＤＰＣ符号は、変調部７において通信路８に適した方式で変調され、変調信号として通信路８に送信される。復調部９は、通信路８を介して送信された変調信号を受信して復調し、ディジタルデータとして復号部４’に供給する。このとき、復調部９は、受信信号に関する情報を復号部４’に渡す。復号部４’は、復調部９から渡された受信信号に関する情報に基づき、復調部９から供給されたディジタルデータのビット毎の確率値を求める。そして、復号部４’は、求めた確率値に基づき各実施形態で説明したようにしてＬＤＰＣ符号を復号し、入力データ５’を復元する。復号部４’は、復元したデータを出力データ６’として出力する。
【０１１６】
このように、通信路８を介して情報の送受信を行う通信システムにおいても、ＬＤＰＣ復号においてチェックノード処理を行うチェックノード処理部の回路規模を、既存の構成と比べて小さくすることができる。
【０１１７】
なお、本発明は上述した各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、各実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【０１１８】
１  メモリシステム
２  メモリ部
３,３’  符号化部
４,４’，４”  復号部
８  通信路
２０  メモリ
２１  閾値読み出し部
２２  閾値・確率変換部
２３  初期確率記憶部
４０  変数ノード処理部
４１  第１転送部
４２，４２’  チェックノード処理部
４３  第２転送部
４４  振り分け制御部
４５  メッセージ記憶部
４６  判定部
２００1，２００2，２００3  変数ノード処理
２０１1，２０１2，２０１3  メッセージ
２０２1，２０２2，２０２3  チェックノード処理
２０２10，２０２11，２０２12，２０２13  部分集合
４２０1，４２０2，４２０3，４２０4  チェックノード演算部
【図１】
2016144052.tif 000008
【図２】
2016144052.tif 000009
【図３】
2016144052.tif 000010
【図４】
2016144052.tif 000011
【図５】
2016144052.tif 000012
【図６】
2016144052.tif 000013
【図７】
2016144052.tif 000014
【図８】
2016144052.tif 000015
【図９】
2016144052.tif 000016
【図１０】
2016144052.tif 000017
【図１１】
2016144052.tif 000018
【図１２】
2016144052.tif 000019