(57)【要約】【課題】１回の繰り返し処理において２回以上演算器を使用して符号検出する際に、各ノード間でやりとりするメッセージを保存するメモリ等の回路構成を簡略化する。【解決手段】符号検出装置１は、ビットノードＹｎからチェックノードＸｍへ渡すメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するビットノード処理演算部７と、チェックノードからビットノードへ渡すメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するチェックノード処理演算部５と、Ｑｍ，ｎ（ｍ∈Ｍ（ｎ））を格納するメモリ４と、処理演算部５の演算結果を格納するメモリ６とを有し、チェックノード処理演算器５は、逐次入力されるメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））から一旦、Ａｍ，Ｂｍを求め、再びメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））が逐次入力され、これと、算出されたＡｍ，ＢｍとからメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を逐次算出してビットノード処理演算部７へ出力する。【選択図】図３
2005045735.tif 000002
【特許請求の範囲】
【請求項１】
入力された低密度パリティ検査符号から、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて符号検出する符号検出装置において、
各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算手段と、
上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算手段とを有する
ことを特徴とする符号検出装置。
【請求項２】
上記チェックノード処理演算手段は、入力された上記第１のメッセージからチェックを満たす確率又は当該確率に準じた値を求める第１の演算と、該第１の演算にて得られた該チェックを満たす確率又は当該確率に準じた値に基づき、上記第２のメッセージを求める第２の演算とを実行する
ことを特徴とする請求項１記載の符号検出装置。
【請求項３】
上記変数ノード処理演算手段からの上記第１のメッセージを保存する第１の記憶手段を有し、
上記チェックノード処理演算手段は、上記第１の記憶手段から上記第１のメッセージを読み出す
ことを特徴とする請求項１記載の符号検出装置。
【請求項４】
上記チェックノード処理演算手段における演算結果を記憶する第２の記憶手段を有する
ことを特徴とする請求項１記載の符号検出装置。
【請求項５】
上記チェックノード処理演算手段における演算結果を記憶する第２の記憶手段を有し、
上記第１の演算では、１以上の上記変数ノードからの１以上の上記第１のメッセージが逐次入力され、該１以上の上記第１のメッセージが渡された全てのチェックノードにおけるチェックを満たす確率又は当該確率に準じた値を逐次更新し、
上記第２の演算では、再び上記１以上の上記変数ノードからの１以上の上記第１のメッセージが逐次入力され、上記第１の演算にて更新が終了したチェックを満たす確率又は当該確率に準じた値と、上記１以上の第１のメッセージとから、該１以上の上記第１のメッセージが渡された全てのチェックノードから該１以上の上記変数ノードへ渡す上記第２のメッセージを逐次算出し、
上記第２の記憶手段は、上記逐次更新されるチェックを満たす確率又は当該確率に準じた値、又は更新が終了したチェックを満たす確率又は当該確率に準じた値を記憶する
ことを特徴とする請求項２記載の符号検出装置。
【請求項６】
上記低密度パリティ検査符号は、任意の符号語をｐ回、巡回置換したものもまた符号語になる準巡回符号であることを特徴とする請求項１記載の符号検出装置。
【請求項７】
上記準巡回符号は、ｐ＝１である巡回符号であることを特徴とする請求項６記載の符号検出装置。
【請求項８】
上記第２の記憶手段は、上記チェックノードと同数のメモリと、該メモリのデータを更新する更新手段と、上記メモリを選択してデータを出力する選択手段と、上記更新手段及び選択手段を制御する制御手段とを有する
ことを特徴とする請求項４記載の符号検出装置。
【請求項９】
上記チェックノード処理演算手段における演算結果を記憶する第２の記憶手段を有し、
上記第２の記憶手段は、上記チェックノードと同数のシフトレジスタと、上記チェックノード処理演算手段からの演算結果により上記シフトレジスタのデータを更新する更新手段とを有し、上記シフトレジスタは、更新されたデータを出力する
ことを特徴とする請求項６記載の符号検出装置。
【請求項１０】
上記変数ノード処理演算手段は、上記ｐの倍数個の変数ノードから、該ｐの倍数個の変数ノードに接続される全てのチェックノードに渡す上記第１のメッセージを並列して演算する
ことを特徴とする請求項６記載の符号検出装置。
【請求項１１】
上記低密度パリティ検査符号は、任意の符号語をｐ回、巡回置換したものもまた符号語になる準巡回符号であって、
上記チェックノード処理演算手段における演算結果を記憶する第２の記憶手段を有し、
上記第２の記憶手段は、上記ｐの倍数個の変数ノードにエッジにより接続された全てのチェックノードに対して当該ｐの倍数個の変数ノードから渡される上記第１のメッセージにより更新された当該チェックノードにおけるチェックを満たす確率又は当該確率に準じた値を記憶する
ことを特徴とする請求項２記載の符号検出装置。
【請求項１２】
上記変数ノード処理演算手段は、上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号結果を符号検出結果として出力する
ことを特徴とする請求項１記載の符号検出装置。
【請求項１３】
上記チェックノード処理演算手段が上記チェックを満たす確率又は当該確率に準じた値を算出する第１フェーズにおける演算処理と、上記チェックノード処理演算手段が上記第２のメッセージを算出し上記変数ノード処理演算手段が上記第１のメッセージを算出する第２フェーズにおける演算処理とを繰り返す繰り返し演算処理の繰り返し回数を制御する制御手段を有する
ことを特徴とする請求項２記載の符号検出装置。
【請求項１４】
上記制御手段は、上記繰り返し演算処理を、所定の回数実行するよう制御する
ことを特徴とする請求項１３記載の符号検出装置。
【請求項１５】
上記変数ノード処理演算手段は、上記第２のメッセージから算出した事後確率から硬判定復号結果を算出し、
上記制御手段は、上記繰り返し演算処理を、上記硬判定復号結果が所定の条件を満たすまで実行するよう制御する
ことを特徴とする請求項１３記載の符号検出装置。
【請求項１６】
上記チェックノード処理演算手段を、同一の繰り返し演算処理に２回以上使用する
ことを特徴とする請求項１３記載の符号検出装置。
【請求項１７】
上記チェックノード処理演算手段は、上記第１の演算を実行した後、上記第２の演算を実行する
ことを特徴とする請求項１記載の符号検出装置。
【請求項１８】
上記チェックノード処理演算手段は、上記第１フェーズにおける上記第１の演算を実行する第１フェーズ用処理演算手段と、上記第２フェーズにおける上記第２の演算を行う第２フェーズ用処理演算手段とを有し、
上記第１フェーズ用処理演算手段は、上記第２フェーズ用処理演算手段が上記第２の演算を実行中に、次の繰り返し演算における上記第１の演算を実行する
ことを特徴とする請求項１３記載の符号検出装置。
【請求項１９】
入力された低密度パリティ検査符号から、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて符号検出する符号検出方法において、
各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算工程と、
上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算工程とを有する
ことを特徴とする符号検出方法。
【請求項２０】
上記チェックノード処理演算工程は、入力された上記第１のメッセージからチェックを満たす確率又は当該確率に準じた値を求める第１の演算工程と、該第１の演算にて得られた該チェックを満たす確率又は当該確率に準じた値に基づき、上記第２のメッセージを求める第２の演算工程とを有する
ことを特徴とする請求項１９記載の符号検出方法。
【請求項２１】
上記チェックノード処理演算工程では、上記変数ノード処理演算工程にて得られた上記変数ノード毎の第１のメッセージを保存する第１の記憶手段から上記変数ノード毎の第１のメッセージを読み出す
ことを特徴とする請求項１９記載の符号検出方法。
【請求項２２】
上記チェックノード処理演算工程における演算結果を第２の記憶手段に記憶する記憶工程を有する
ことを特徴とする請求項１９記載の符号検出方法。
【請求項２３】
上記チェックノード処理演算工程における演算結果を第２の記憶手段に記憶する記憶工程を有し、
上記第１の演算工程では、１以上の上記変数ノードからの１以上の上記第１のメッセージが逐次入力され、該１以上の上記第１のメッセージが渡された全てのチェックノードにおけるチェックを満たす確率又は当該確率に準じた値を逐次更新し、
上記第２の演算工程では、再び上記１以上の上記変数ノードからの１以上の上記第１のメッセージが逐次入力され、上記第１の演算にて更新が終了したチェックを満たす確率又は当該確率に準じた値と、上記１以上の第１のメッセージとから、該１以上の上記第１のメッセージが渡された全てのチェックノードから該１以上の上記変数ノードへ渡す上記第２のメッセージを逐次算出し、
上記記憶工程では、上記逐次更新されるチェックを満たす確率又は当該確率に準じた値、又は更新が終了したチェックを満たす確率又は当該確率に準じた値を記憶する
ことを特徴とする請求項２０記載の符号検出方法。
【請求項２４】
上記低密度パリティ検査符号は、任意の符号語をｐ回、巡回置換したものもまた符号語になる準巡回符号であることを特徴とする請求項１９記載の符号検出方法。
【請求項２５】
上記準巡回符号は、ｐ＝１である巡回符号であることを特徴とする請求項２４記載の符号検出方法。
【請求項２６】
チェックノード処理演算工程における演算結果により、チェックノードと同数設けられたメモリに保存されたデータを更新する更新工程と、
チェックノード処理演算工程にて使用されるデータを上記メモリから出力する出力工程とを有する
ことを特徴とする請求項１９記載の符号検出方法。
【請求項２７】
上記低密度パリティ検査符号は、任意の符号語をｐ回、巡回置換したものもまた符号語になる準巡回符号であって、
チェックノード処理演算工程における演算結果により、上記チェックノードと同数のシフトレジスタに保存されたデータを更新する更新工程と、
チェックノード処理演算工程にて使用されるデータを上記シフトレジスタから出力する出力工程とを有する
ことを特徴とする請求項１９記載の符号検出方法。
【請求項２８】
上記変数ノード処理演算工程では、上記ｐの倍数個の変数ノードから、該ｐの倍数個の変数ノードに接続される全てのチェックノードに渡す上記第１のメッセージを並列に演算する
ことを特徴とする請求項２４記載の符号検出方法。
【請求項２９】
上記低密度パリティ検査符号は、任意の符号語をｐ回、巡回置換したものもまた符号語になる準巡回符号であって、
上記ｐの倍数個の変数ノードにエッジにより接続された全てのチェックノードに対して当該ｐの倍数個の変数ノードから渡される上記第１のメッセージにより更新された当該チェックノードにおけるチェックを満たす確率又は当該確率に準じた値を第２の記憶手段に記憶する記憶工程を有する
ことを特徴とする請求項２０記載の符号検出方法。
【請求項３０】
上記チェックノード処理演算工程の上記第１の演算工程にて上記チェックを満たす確率又は当該確率に準じた値を算出する処理を実行する第１フェーズと、上記チェックノード処理演算工程の上記第２の演算工程にて上記第２のメッセージを算出し上記変数ノード処理演算工程にて上記第１のメッセージを算出する第２フェーズとを繰り返す繰り返し演算処理の繰り返し回数を制御する制御工程を有する
ことを特徴とする請求項２０記載の符号検出方法。
【請求項３１】
上記チェックノード処理演算工程は、上記第１フェーズにおける上記第１の演算を実行する第１フェーズ用処理演算工程と、上記第２フェーズにおける上記第２の演算を行う第２フェーズ用処理演算工程とを有し、
上記第２フェーズ用処理演算工程と、次の繰り返し演算における上記第１フェーズ用処理演算工程とを同時に実行する
ことを特徴とする請求項３０記載の符号検出方法。
【請求項３２】
入力された低密度パリティ検査符号から、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて符号検出して復号する復号装置において、
各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算手段と、
上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算手段と、
上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号をする復号手段とを有する
ことを特徴とする復号装置。
【請求項３３】
上記復号手段は、上記硬判定復号結果からパリティ部分を除去することを特徴とする請求項３２記載の復号装置。
【請求項３４】
入力された低密度パリティ検査符号から、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて符号検出して復号する復号方法において、
各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算工程と、
上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算工程と、
上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号をする復号工程とを有する
ことを特徴とする復号方法。
【請求項３５】
メッセージから低密度パリティ検査符号に符号化され記録されたデータを再生する情報処理装置において、
上記記録されたデータを読み出し、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて低密度パリティ検査符号の符号を検出して再生する再生手段を有し、
上記再生手段は、
各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算手段と、
上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算手段と、
上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号をする復号手段と
を有することを特徴とする情報処理装置。
【請求項３６】
上記メッセージを低密度パリティ検査符号に符号化する符号化手段と、
上記符号化されたメッセージを記録する記録手段とを有する
ことを特徴とする請求項３５記載の情報処理装置。
【請求項３７】
メッセージから低密度パリティ検査符号に符号化され記録されたデータを再生する情報処理方法において、
上記記録されたデータを読み出し、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて低密度パリティ検査符号の符号を検出して再生する再生工程を有し、
上記再生工程は、
各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算工程と、
上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算工程と、
上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号をする復号工程と
を有することを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査符号（ＬＤＰＣ：low density parity check code）の軟判定復号を行うための符号検出装置及び方法、及びこれを使用した復号装置及び方法、並びに情報処理装置及び方法に関する。
【背景技術】
【０００２】
低密度パリティ検査符号（以下、ＬＤＰＣ符号という。）は、１９６２年、Robert G. Gallagerによって発表された線形符号の一種であり、そのパリティ検査行列の非零の要素数が全要素数に対して少ない（低密度である）ことが特徴となっている（下記非特許文献１参照）。
【０００３】
また、ＬＤＰＣ符号はパリティ検査行列の２部グラフ（bipartite graph）に、短いサイクルが含まれないことから、繰り返し復号によって良好なビットエラー特性を示すことが知られている。
【０００４】
符号長ＮのＬＤＰＣ符号の任意の符号語ベクトルｃは、Ｍ行Ｎ列のパリティ検査行列をＨとすると、下記式（１）を満たす。
【０００５】
【数１】
2005045735.tif 000003
【０００６】
上式（１）は、Ｍ個のパリティ検査方程式を表している。Ｈの階数（rank）が（Ｎ−Ｋ）（Ｋは次元）で与えられるとき、このＬＤＰＣ符号の符号化率はＫ／Ｎで与えられる。Ｍ＞Ｎ−Ｋの場合、冗長なパリティ検査方程式があることを意味する。
【０００７】
図１は、２元（binary）ＬＤＰＣ符号のパリティ検査行列の例である。この７行２１列の行列の階数は６であり、これによって定まる符号は符号長Ｎ＝２１、次元Ｋ＝１５の線形符号となる。この行列において各行における非零の要素数（“１”の数）（ハミング重み）Ｗｒは全て６、各列における非零の要素数（“１”の数）（ハミング重み）Ｗｃは全て２である。このようにＷｒ、Ｗｃが均一なパリティ検査行列を持つＬＤＰＣ符号はレギュラー（regular）ＬＤＰＣ符号と呼ばれる。
【０００８】
ＬＤＰＣ符号は、線形符号であり、２元に限るものではなく、２元符号以外の場合においても同様の議論ができることは勿論であるが、以下の説明においては、全て２元符号の場合を例に説明する。
【０００９】
先ず、情報語（メッセージ）をＬＤＰＣ符号化し、パリティ検査行列によって符号検出する方法について説明する。ＬＤＰＣ符号を得るためには、始めに、Ｍ行Ｎ列、Ｋ次元のパリティ検査行列Ｈから、Ｋ行Ｎ列の生成行列Ｇ（ＧＨＴ＝０を満たす）を求めておく。そして、Ｋビットの２元メッセージ（ｍ０ｍ１・・・ｍＫ―１）に生成行列Ｇを乗算することによりＮビットの符号語（（ｍ０ｍ１・・・ｍＫ−１）Ｇ＝（ｃ０ｃ１・・・ｃＮ−１））を得る。このようにして得られた符号語は、変調器を介して通信路へ送出され、受信側で受信信号として受信される。この受信信号が復調されたのち、パリティ検査行列により復号され、送信メッセージの推定値（Ｋビット（ｍ０＾ｍ１＾・・・ｍＫ−１＾））として出力される。
【００１０】
次に、受信された受信信号から符号を検出する符号検出方法について詳細に説明する。ＬＤＰＣ符号は、パリティ検査行列或いは２部グラフを元に、メッセージパッシング（message-passing）アルゴリズムによって符号検出できることが知られている。Ｍ行Ｎ列のパリティ検査行列を表現した２部グラフは、チェック（check）に対応するＭ個のノード（node）（チェックノード）、変数（variable）に対応するＮ個のノード（変数ノード）、及びノードを接続するエッジ（edge）により構成される。エッジはパリティ検査行列の非零要素の場所に対応しており、第ｍ行第ｎ列の要素が零でない場合にのみｍ番目のチェックノードとｎ番目の変数ノードとがエッジで接続される。上述したように、ここでは２元符号の場合について説明するため、以降では、変数ノードをビットノードと表現する。
【００１１】
図２は、図１のパリティ検査行列に対応した２部グラフを示しており、丸（〇）で表された７個のチェックノードＸｍ（Ｘ０〜Ｘ６）と、四角（□）で表された２１個のビットノードＹｎ（Ｙ０〜Ｙ２０）とで構成されている。各チェックノードＸｍには６本のエッジが、各ビットノードＹｎには２本のエッジがそれぞれ接続されている。
【００１２】
ＬＤＰＣ符号は、エッジで接続されたチェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させ、ビットノードＸｍからチェックノードＹｎ、チェックノードＹｎからビットノードＸｍへのメッセージ交換を繰り返して行う、メッセージパッシングアルゴリズム（あるいはsum-productアルゴリズム）によるＳＩＳＯ（Soft-In Soft-Out）復号方法により符号検出することができる。このメッセージパッシングアルゴリズムは、次のような手順を繰り返すことで実現される。
【００１３】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、ビットノードＹｎからチェックノードＸｍに伝搬されるメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを事前確率ｐ０ｎ，ｐ１ｎに初期化する。ここでｐｘｎとはビットｎが“x”である事前確率を表すものとする。
【００１４】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、チェックノードＸｍからビットノードＹｎに伝搬されるメッセージr０ｍ，ｎ，r１ｍ，ｎを次式に従って求める。
【００１５】
【数２】
2005045735.tif 000004
【００１６】
［３］手順２−ビットノードにおける処理
必要に応じて各ビットの事後確率ｑ０ｎ、ｑ１ｎを、次式により求める。
【００１７】
【数３】
2005045735.tif 000005
【００１８】
更に繰り返しが必要な場合、次式に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージを計算する。
【００１９】
【数４】
2005045735.tif 000006
【００２０】
メッセージパッシングアルゴリズムによる復号は、終了条件を満たすまで手順１と手順２とを繰り返し、最後に硬判定復号で情報語が推定される。繰り返しの終了条件は、
１）繰り返しが予め定めた回数に達した時点で終了
２）予め定めた繰り返し回数に達していない場合でも硬判定結果がパリティチェックを満たせば終了
等が一般的である。ここで、パリティチェックは、下記（５）のように示される。
【００２１】
【数５】
2005045735.tif 000007
【００２２】
終了条件が上記の１番目としたときの、復号アルゴリズムのフローチャートを図２６に示す。即ち、図２６に示すように、ビットノードＹｎからチェックノードＸｍへのメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを事前確率ｐ０ｎ，ｐ１ｎに初期化する。（ステップＳ２１：手順０）。
【００２３】
次に、各チェックノードＸｍからビットノードＹｎへのメッセージr０ｍ，ｎ，r１ｍ，ｎを計算する（ステップＳ２２：手順１）。
【００２４】
そして、各ビットノードＹｎにおいて、事後確率ｑ０ｎ、ｑ１ｎ及び硬判定結果ｃ＾を計算し、更にチェックノードＸｍへのメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを計算する（ステップＳ２３：手順２）。
【００２５】
その後、規定の繰り返し回数に達しているか否かを判定し（ステップＳ２４）、規定の繰り返し回数を超えない場合は、ステップＳ２１〜ステップＳ２３の処理を繰り返し、規定の繰り返し回数を超えた場合には、硬判定復号し（ステップＳ２５）、処理を終了する。また、上述した如く、予め定めた繰り返し回数に達していない場合であっても、硬判定結果ｃ＾がパリティチェックＨｃ＾＝０を満たしている場合は、処理を終了するようにしてもよい。
【００２６】
なお、上記のアルゴリズムと等価な計算方法として、対数尤度比ＬＬＲ（Log-Likelihood Ratio）を用いて対数領域での計算式に変形すれば、乗算に相当する演算は、全て加算に置き換えられ、ハードウェアやソフトウェアによる処理を簡略化できる。対数領域における演算のアルゴリズムを以下に示す。
【００２７】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、エッジを伝搬するメッセージＱｍ，ｎを各ビットの事前対数尤度比Ｐｎで初期化する。ここで、エッジを伝搬するメッセージＱｍ，ｎ及び各ビットの事前対数尤度比Ｐｎは、夫々下記（６−１）及び（６−２）のように定義される。
【００２８】
【数６】
2005045735.tif 000008
【００２９】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、エッジを伝搬するメッセージＲｍ，ｎを下記式（７−１）により計算する。ここで、Ａｍ、Ｂｍ、及びメッセージＲｍ，ｎは下記（７−２）乃至（７−４）のように定義され、ｆ（β）、αｍ，ｎ、及びβｍ，ｎは下記（７−５）乃至（７−７）で示される。
【００３０】
【数７】
2005045735.tif 000009
【００３１】
［３］手順２−ビットノードにおける処理
各ビットの下記（８）に定義される事後対数尤度比Ｑｎを、下記式（９）により求める。
【００３２】
【数８】
2005045735.tif 000010
【００３３】
【数９】
2005045735.tif 000011
【００３４】
更に繰り返しが必要な場合、下記式（１０）に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージＱｍ，ｎを計算する。
【００３５】
【数１０】
2005045735.tif 000012
【００３６】
ここで、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを求める際に使用される、上記（７−２）及び（７−３）にて定義されるＡｍ、Ｂｍの物理的な意味については次のように解釈できる。Ａｍｆ（Ｂｍ）を計算すると、下記式（１１）となる。
【００３７】
【数１１】
2005045735.tif 000013
【００３８】
ここで、ｒ０ｍ、ｒ１ｍを、以下式（１２−１）及び（１２−２）のように定義した。
【００３９】
【数１２】
2005045735.tif 000014
【００４０】
ビットノードＹｎからチェックノードＸｍへのメッセージｑ０ｍ，ｎ及びｑ１ｍ，ｎを夫々下記（１３−１）及び（１３−２）としたとき、ｒ０ｍは、ｍ番目のチェックを満たす確率に相当する。
【００４１】
【数１３】
2005045735.tif 000015
【００４２】
即ち、Ａｍ、Ｂｍは、各ビットノードＹｎ（ｎ∈Ｎ（ｍ））からチェックノードＸｍへのメッセージＱｍ，ｎ又はｑ０ｍ，ｎ、ｑ１ｍ，ｎに基づいた、ｍ番目のチェックを満たす確率の間接的な表現に相当する。
【００４３】
以上の対数尤度比を用いた場合であって、終了条件が上記の１番目、即ち、手順１と手順２の繰り返しが予め定めた回数に達した時点で終了としたときの、復号アルゴリズムのフローチャートを図２７に示す。即ち、図２７に示すように、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを事前対数尤度比Ｐｎに初期化する。（ステップＳ３１：手順０）。
【００４４】
次に、各チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを計算する（ステップＳ３２：手順１）。
【００４５】
そして、各ビットノードＹｎにおいて、事後対数尤度比Ｑｎ及び硬判定結果ｃ＾を計算し、更にチェックノードＸｍへのメッセージＱｍ，ｎを計算する（ステップＳ３３：手順２）。
【００４６】
その後、規定の繰り返し回数に達しているか否かを判定し（ステップＳ３４）、規定の繰り返し回数を超えない場合は、ステップＳ３１〜ステップＳ３３の処理を繰り返し、規定の繰り返し回数を超えた場合には、硬判定復号し（ステップＳ３５）、処理を終了する。また、上述した如く、予め定めた繰り返し回数に達していない場合であっても、硬判定結果ｃ＾がパリティチェックＨｃ＾＝０を満たしている場合は、処理を終了するようにしてもよい。
【００４７】
なお、以下の説明においては、簡単のため対数尤度比を用いた演算方法にて復号する場合について説明するが、上述の如く事前確率及び事後確率を用いた方法としてもよいことは勿論である。
【００４８】
次に、以上のような手順１及び手順２の演算を繰り返し行ってＬＤＣＰ符号を復号する復号装置について説明する。従来、実施又は提案されているＬＤＰＣ符号の復号装置は、繰り返し毎に同じ演算器を使用するか、否かによって次の２種類に分類することができる。
タイプＡ：繰り返し毎に違う演算器を使用する
タイプＢ：繰り返し毎に同じ演算器を使用する
【００４９】
タイプＡの復号装置では、繰り返し処理をパイプライン化することによって、繰り返し回数に依らず高スループットを得ることができる。しかし繰り返し回数に比例した数の演算器が必要となるため、回路規模が非常に大きくなる。
【００５０】
一方、タイプＢの復号装置の場合、繰り返し回数に応じてスループットが制限されるが、繰り返し回数に依らず回路規模は一定である。また、（ｉ＋１）回目の繰り返し処理はｉ回目の結果を利用するため、同じ回路で演算を行うためには結果を保存する記憶領域が必要となる。
【００５１】
例えば、A. J. Blanksby等による下記非特許文献２に記載の復号装置においては、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎをレジスタに記憶する構成となっている。
【００５２】
また、後述するT. Zhang等による下記非特許文献３の復号装置、及びM. M. Mansour等による下記非特許文献４の復号装置においては、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎの両方をＲＡＭに記憶する構成となっている。
【００５３】
これらタイプＡ及びタイプＢの２つの分類においては、スループットの要求が厳しい場合にはタイプＡ、回路規模の制約が厳しい場合はタイプＢが有利となる。
【００５４】
次に、繰り返し処理１回のあたりの演算に関するパラレル度について考える。メッセージパッシングアルゴリズムを用いたＬＤＰＣ符号の復号装置では、各チェックノードＸｍにおける計算、各ビットノードＹｎにおける計算は他のノードの計算結果に依存しないため、これらの演算をパラレルに実行することができる。一方、列方向の非零要素数Ｗｃが同数の各ビットノードＹｎでは、ビットノードＹｎからチェックノードＸｍへ伝搬されるメッセージＱｍ，ｎの演算器は同じ構造となり、また行方向の非零要素数Ｗｒが同数の各チェックノードＸｍでは、チェックノードＸｍからビットノードＹｎへ伝搬されるメッセージＲｍ，ｎの演算器は同じ構造となる。従って、１つの演算器を時分割で複数のノードの処理に対応させる構造とすれば、少ない演算器の構成で復号装置を実現できる。
【００５５】
従来、実施あるいは提案されているＬＤＰＣ符号の復号装置は、繰り返し処理１回あたりの演算のパラレル度によって次の２種類に分類できる。
【００５６】
タイプ１：Ｍ個の各チェックノードＸｍにおける処理、Ｎ個の各ビットノードＹｎにおける処理を、全てパラレルで独立した演算器により行う
タイプ２：チェックノードＸｍ、ビットノードＹｎの両方、あるいはいずれかを、複数のグループに分けて、各グループ内の処理をパラレルに、別のグループの処理を時分割（シリアル）で行う
【００５７】
ここで、タイプ１の構成では、各チェックノードＸｍの個数Ｍと同数のチェックノード処理演算器を有し、各ビットノードＹｎの個数Ｎと同数のビットノード処理演算器を有する。チェックノード処理演算器、及びビットノード処理演算器は、上述の夫々手順１及び手順２の演算を行う演算器である。このように、ノードに対応した個数の演算器を用意することにより、繰り返し処理１回にかかるクロックサイクル数が少ない、即ち、１回の繰り返し処理は、チェックノードにおける演算とビットノードにおける演算の例えば１クロックとなるため、高いスループットが得られる（例えば下記特許文献１及び非特許文献２参照）。
【００５８】
非特許文献２に記載の復号装置においては、実際にスループット１Ｇｂ／ｓ、符号長１０２４ｂｉｔｓのＬＤＰＣ符号の復号回路をＬＳＩ（large scale integrated circuit）で実現している。しかし、上記タイプ１に示すパラレルの復号装置は、下記の問題点が挙げられる。
【００５９】
（問題点１）符号長の長い符号、パリティチェック数の多い符号の復号回路は回路規模の点で実現が難しい
（問題点２）メッセージ伝搬のための配線は２部グラフのエッジに相当しており、演算器間を接続する配線数が多いため、ＬＳＩやＦＰＧＡ（Field Programmable Gate Array）等ではルーティングが困難となる
【００６０】
また、上記タイプ２は、グループ毎に演算器を時分割で再利用する構成となり、チェックノードＸｍの個数Ｍ、及びビットノードＹｎの個数Ｎよりも、夫々チェックノード処理演算器及びビットノード処理演算器が少なくてすむ。従って、タイプ１の構成と比較すると、グループの数に応じてスループットが低下するが、小さな回路規模で実現できるため、タイプ１の構成の（問題点１）に示した、符号長の大きな符号、パリティチェック数の多い符号への対応が可能となる。しかし、タイプ２の構成では、演算器への入出力を切り替えるために、メッセージを保存するメモリが必要となる。また、着目しているノードのデータを選択する機構、保管場所を制御する機構が必要となる。
【００６１】
特に、全てのノードを異なるグループに分割した場合、即ち、チェックノード処理演算器及びビットノード処理演算器を各１つずつとした場合には、完全なシリアル処理となる。シリアル処理は、高いスループットは得られないが、一般的なコンピュータにおいて復号アルゴリズムをソフトウェアで実現する場合や、回路規模の小さなハードウェアで実現する場合に適している。
【００６２】
タイプ２の構成による復号装置の具体的な実現手段は、非特許文献３乃至５等に記載されている。それぞれの回路構成を図２８乃至図３０に示す。なお、図２８乃至図３０においては、初期化や繰り返し終了条件の判断部は省略している。チェックノード処理演算器は手順１の演算を行うブロックであり、ビットノード処理演算器は手順２の演算を行うブロックである。各演算器の間には、演算器を共有して入出力を切り替えるためのメモリがある。
【００６３】
これら非特許文献３乃至５における復号装置の分類タイプと、復号装置の具体的なパラメータ（ノード数、演算器数）を下記表１に示す。この表１から非特許文献３乃至５の復号装置において、１つの演算器がいくつかのノードによって共有されていることがわかる。
【００６４】
【表１】
2005045735.tif 000016
【００６５】
次に、図２８乃至図３０に示す非特許文献３乃至５に記載の復号装置について詳細に説明する。なお、図２８乃至図３０において、同一の構成要素には、同一の符号を付してその詳細な説明は省略する。
【００６６】
先ず、図２８に示すように、非特許文献３に記載の復号装置１０１は、上述したタイプＢで且つタイプ２に分類されるもの、即ち、繰り返し毎に同じ演算器を使用し、且つ各演算器が時分割で複数のノードの処理を行うタイプの復号装置である。この復号装置１０１は、事前値が入力され、事前値を格納するメモリ１０３と、ビットノードＹｎにおける演算を行うビットノード処理演算器１０４と、チェックノードＸｍにおける演算を行うチェックノード処理演算器１０５と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ及びチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するメモリ１０６と、ビットノード処理演算器１０４の結果に応じて硬判定復号を行い、推定された情報語を出力する硬判定復号器１０７とから構成される。この復号装置１０１は、上記表１に示すように、ビットノード処理演算器１０４及びチェックノード処理演算器１０５共に１つの演算器に２５６個のノードが対応するものとなっている。
【００６７】
また、この図２８に示す復号装置１０１は、メモリがメモリ１０６の１つであるのに対し、図２９に示すように、非特許文献４に記載の復号装置１１０は、同じくタイプＢで且つタイプ２に分類されるものであるが、ビットノード処理演算器１０４において算出されたビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ１０８と、チェックノード処理演算器１０５において算出されたチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するメモリ１０９とで個別に２つのメモリを有している。この復号装置１１０は、上記表１に示すように、ビットノード処理演算器１０４及びチェックノード処理演算器１０５共に１つの演算器に２１１個のノードが対応するものとなっている。
【００６８】
また、非特許文献５に記載の復号装置は、タイプＡで且つタイプ２に分類されるもの、即ち、繰り返し毎に異なる演算器を使用し、且つ各演算器が時分割で複数のノードの処理を行うタイプの復号装置である。この復号装置は、上記表１に示すように、全てのビットノード（Ｎ＝４６０８）が１つのビットノード処理演算器により演算され、また、１つのチェックノード処理演算器により、１２８個のチェックノードの演算が行われるものとなっており、これらの演算器が繰り返し処理回数分用意される。
【００６９】
この復号装置を図３０に示す。なお、図３０においては、簡単のため、ビットノード処理演算器及びチェックノード処理演算器を各１つずつのみ示す。即ち、図３０に示すように、タイプＡ且つタイプ２に分類される復号装置１２０は、事前値を格納するメモリ１１３と、事前値を入力してｋ回の繰り返し演算処理の後に硬判定復号により推定された情報語を出力する硬判定復号器１０７とを有する。即ち、手順１及び手順２の繰り返し演算の回数がｋ回で硬判定復号される復号装置であって、繰り返し演算の回数分のｋ個の演算部１２１０〜１２１ｋ-1を有している。演算部１２１０は、初期化（手順０）を含めた演算を行う部分であり、事前値が入力され、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ１１８０と、チェックノードにおける手順１の演算を行うチェックノード処理演算器１１５０と、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するメモリ１１９０及びメッセージＲｍ，ｎからビットノードＹｎにおける手順２の演算を行うビットノード処理演算器１１４０とを有する。この演算部１２１０よりも後段の演算部１２１１〜１２１ｋ−１においては、手順１及び手順２を演算する演算部となっており、例えば演算部１２１１は、メッセージＱｍ，ｎを格納するメモリ１１８１、チェックノード処理演算器１１５１、メッセージＲｍ，ｎを格納するメモリ１１９１、ビットノード処理演算器とから構成される。そして、最終段のビットノード処理演算器１１４ｋ−１における演算結果が上述の硬判定復号器１０７に入力され処理が完了するものである。
【００７０】
ここで、上述の非特許文献３及び非特許文献４による構成では、演算器の入出力を切り替えるために、メモリにおいて、ＲＡＭを複数のバンクに分割して同時に異なるアドレスのデータにアクセスする方法を用いている。以下、このことについて更に詳細に説明する。
【００７１】
図３１は、上述したアルゴリズムにおいて、手順１及び手順２を行う要部を模式的に示すブロック図である。上述のアルゴリズムに従うと、図３１に示すように、例えば、ビットノードＹｎからチェックノードＸｍへ渡されるメッセージＱｍ，ｎを格納するメモリ（ＲＡＭ）１２８を有する場合、リード時には、チェックノード処理演算器１２５に入力するＷｒ（図１に示すパリティ検査行列の符号語である場合はＷｒ＝６）個のＱｍ，ｎ（ｎ∈Ｎ（ｍ））（データＤ１４）をメモリ１２８から読み出し、ライト時にはビットノード処理演算器１２４から求まるＷｃ（図１に示す行列においては、Ｗｃ＝２）個のＱｍ，ｎ（ｍ∈Ｍ（ｎ））（データＤ１３）をメモリ１２８に書き込む。
【００７２】
同様に、チェックノードＸｍからビットノードＹｎに渡されるメッセージＲｍ，ｎを格納するメモリ（ＲＡＭ）１２９を有する場合、リード時にはビットノードＹｎの演算器１２４に入力するＷｃ個のＲｍ，ｎ（ｍ∈Ｍ（ｎ））（データＤ１２）を読み出し、ライト時にはチェックノードＸｍの演算器１２５から求まるＷｒ個のＲｍ，ｎ（ｎ∈Ｎ（ｍ））（データＤ１１）を書き込む。ここで、Ｎ（ｍ）は、パリティ検査行列第ｍ行における非零要素の列番号、Ｍ（ｎ）は、パリティ検査行列第ｎ列における非零要素の行番号に対応する。
【００７３】
このメッセージＱｍ，ｎ、Ｒｍ，ｎの読み出し及び書き込みについて更に詳細に説明する。ここでは、図３１に示すビットノード処理演算器１２４において算出されたビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ１２８と、チェックノード処理演算器１２５において算出されたチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを格納するメモリ１２９において、各メモリ１２８、１２９が各ノード毎のアドレスにデータを保存する場合を例にとって説明する。
【００７４】
図３２（ａ）及び（ｂ）は、図１に示す行列を使用した復号装置において、夫々メッセージＱｍ，ｎを格納するＲＡＭ及びメッセージＲｍ，ｎを格納するＲＡＭのアドレスを模式的に示す図である。
【００７５】
チェックノードＸｍにおける処理においては、Ｎ個のビットのうち、非零要素（Ｗｒ＝６）分のデータＤ１１（メッセージＲｍ，ｎ（ｎ∈Ｎ（ｍ）））がチェックノード処理演算器１２５によりメモリ１２９に書き込まれる。
【００７６】
ビットノードＹｎにおける処理においては、ビットノード処理演算器１２４により、メモリ１２９からＭ個のチェックのうち、非零要素（Ｗｃ＝２）分のデータＤ１２（メッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））が読み出される。そして、読み出されたデータＤ１２から、ビットノード処理演算器１２４にてメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））が算出され、この算出されたメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））がデータＤ１３としてメモリ１２８に書き込まれる。
【００７７】
そして、チェックノードＸｍにおける処理において、チェックノード処理演算器１２５が、メモリ１２８からデータＤ１４（メッセージＱｍ，ｎ（ｎ∈Ｎ（ｍ）））を読み出し、これよりメッセージＲｍ，ｎ（ｎ∈Ｎ（ｍ））を算出する。
【００７８】
ここで、図３２（ａ）及び（ｂ）に示すように、メモリ１２８及びメモリ１２９において、例えばビットノードＹ０におけるチェックノードＸｍへのメッセージＱｍ，０を算出する場合は、データＤ１２としてメッセージＲ０，０及びＲ６，０が必要になり、チェックノードＸ０におけるビットノードＹｎへのメッセージＲ０，ｎを算出する場合は、データＤ１４として、Ｑ０，０、Ｑ０，１、Ｑ０，３、Ｑ０，１１、Ｑ０，１３、及びＱ０，１７が必要である。これらのデータは、メモリ１２８、１２９にランダムアクセスすることで読み出すことが可能であるものの、メモリにアクセスする回数が多くなるため、スループットが極めて悪くなる。
【００７９】
そこで、行単位又は列単位にアクセスすれば、スループットを向上することができる。しかしながら、上述したように、各演算器１２４、１２５におけるメモリ１２８、１２９の読み出し位置及び書き込み位置（同時にアクセスするデータの格納場所）が列又は行と異なっている。従って、例えばビットノード処理演算器１２４における処理、即ち列単位のアクセスに都合がよいようなメモリ構成とすると、チェックノード処理演算器１２５における処理、即ち行単位のアクセスに不都合が生じてしまう。
【００８０】
そこで、上述の例えば非特許文献３及び非特許文献４のように、メッセージＱｍ，ｎ、Ｒｍ，ｎを格納するメモリを複数バンクに分割してメモリへのアクセスの簡素化を図ったり、非特許文献５のように、ＦＩＦＯ（first in first out）にメッセージを入力し、必要なデータを選択する選択器を備えるような構成にする等の工夫がなされている。
【非特許文献１】Ｒ．Ｇ．ギャラガ（R. G. Gallager）著，「ＬＤＣＰ符号（Low Density Parity Check Codes）」，エムアイティープレス（MIT Press），１９６３年
【非特許文献２】A. J. Blanksby and C. J. Howland著，”A 690-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder”，アイイーイーイー・ジャーナル・オブ・ソリッド・ステイト・サーキット（IEEE Journal of Solid-State Circuits），２００２年３月，第３７巻，第３号，ｐｐ４０４−４１２
【非特許文献３】T. Zhang and K. K. Parhi著,”A 54 MBP （3,6）-REGULAR FPGA LDPC DECODER”，アイイーイーイー・ワークショップ・オン・シグナル・プロセッシング・システムズ（IEEE Workshop on Signal Processing Systems），２００２年，ｐｐ  １２７−１３２
【非特許文献４】M. M. Mansour and N. R. Shanbhag著、「ＬＤＰＣ符号のためのロウパワーＶＬＳＩデコーダの構成（Low-Power VLSI Decoder Architectures for LDPC Codes）」，プロシーデングス・オブ・ザ・２００２・インターナショナル・シンポジウム・オン・ロウ・パワー・エレクトロニクス・アンド・デザイン（Proceedings of the 2002 International Symposium on Low Power Electronics and Design），２００２年，ｐｐ．２８４−２８９
【非特許文献５】E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam著，「マグネティックレコーダチャネルにおける繰り返し復号のためのＶＬＳＩの構成（VLSI Architectures for Iterative Decoders in Magnetic Recording Channels）」、アイイーイーイー・トランザクション・オン・マグネティクス（IEEE Transactions on Magnetics），２００１年３月，第３７巻，第２号，ｐｐ７４８−７５５
【特許文献１】特開２００２−３３６７０号公報
【発明の開示】
【発明が解決しようとする課題】
【００８１】
以上をまとめると、繰り返し毎に異なる演算器を使用するタイプＡ及び繰り返し毎に同一の演算器を使用するタイプＢの２つの分類において、タイプＡの復号装置では、繰り返し処理をパイプライン化することによって、繰り返し回数に依らず高スループットを得ることができるが、繰り返し回数に比例した数の演算器が必要となるため、回路規模が極めて大きくなる。一方、タイプＢの復号装置の場合、回路規模を小さくできるものの繰り返し回数に応じてスループットが制限されてしまう。
【００８２】
また、Ｍ個の各チェックノードＸｍにおける処理、Ｎ個の各ビットノードＹｎにおける処理を、全てパラレルで独立した演算器により行うタイプ１と、チェックノードＸｍ、ビットノードＹｎの両方、あるいはいずれかを、複数のグループに分けて、各グループ内の処理をパラレルに、別のグループの処理を時分割（シリアル）で行うタイプ２の分類においては、いずれの場合においても以下に示す問題点がある。
【００８３】
即ち、タイプ１の復号装置では、ノードに対応した個数の演算器を用意することにより、繰り返し処理１回にかかるクロックサイクル数が少ない、即ち、１回の繰り返し処理は、チェックノードにおける演算とビットノードにおける演算の１クロック等となるため、高いスループットが得られるものの、符号長の長い符号、パリティチェック数の多い符号の復号回路は回路規模の点で実現が難しく、メッセージ伝搬のための配線は２部グラフのエッジに相当しており、演算器間を接続する配線数が多いため、ＬＳＩやＦＰＧＡ等ではルーティングが困難となる。
【００８４】
一方、タイプ２の復号装置は、グループ毎に演算器を時分割で再利用する構成となり、チェックノードＸｍの個数Ｍ、及びビットノードＹｎの個数Ｎよりも、夫々チェックノード処理演算器及びビットノード処理演算器が少なくてすむ。従って、タイプ１の構成と比較すると、グループの数に応じてスループットが低下するが、小さな回路規模で実現できるため、符号長の大きな符号、パリティチェック数の多い符号への対応が可能となる。しかしながら、タイプ２の構成では、演算器への入出力を切り替えるために、メッセージを保存するメモリが必要となる。また、着目しているノードのデータ（メッセージ）を選択する機構、メッセージを保管する場所を制御する機構が必要となる。
【００８５】
特に、タイプ２の復号装置の場合、全てのノードを異なるグループに分割した場合、即ち、チェックノード処理演算器及びビットノード処理演算器を各１つずつとした場合には、完全なシリアル処理となり、高いスループットが得られない。
【００８６】
従って、上述した如く、繰り返し毎に異なる演算器を使用するようなタイプＡの復号装置であっても、繰り返し毎に同一の演算器を使用するようなタイプＢであっても、例えばタイプ２のように演算器を時分割で再利用するような復号装置の構成にした場合、高スループットを得るためには、同時に複数のメッセージを処理する必要があるが、同時にアクセスするデータの格納場所がリード時とライト時で異なるため、例えば上記非特許文献３、４に記載の復号装置においては、ＲＡＭを複数のバンクに分割する必要があり、構造が複雑となる。また、非特許文献５による復号装置においては、タイプＡ且つタイプ２の構成であり、共用した演算器への入出力を切り替えるために、演算器とメモリとの間にマルチプレクサ、及びデマルチプレクサが存在しており（図示せず）、それらの回路が複雑になるという問題点がある。
【００８７】
本発明は、このような従来の実情に鑑みて提案されたものであり、１回の繰り返し処理において２回以上演算器を使用して符号検出する際に、各ノード間でやりとりするメッセージを保存するメモリ等の回路構成を極めて簡略化することができる符号検出装置及び方法、またこれを使用した復号装置及び方法、並びに情報処理装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００８８】
上述した目的を達成するために、本発明に係る符号検出装置は、入力された低密度パリティ検査符号から、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて符号検出する符号検出装置において、各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算手段と、上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算手段とを有することを特徴とする。
【００８９】
本発明においては、従来は変数ノード処理演算手段の入出力データと、チェックノード処理演算手段の入出力データとが異なる要素からなるメッセージであったのに対し、本発明では、チェックノード処理演算手段は、変数ノード処理演算手段が出力した変数ノード毎の第１のメッセージを受け取り、算出したメッセージをチェックノード毎ではなく、変数ノード毎にまとめた第２のメッセージとして出力するため、変数ノード処理演算手段の出力データと、チェックノード処理演算手段の入力データとが同様の要素、即ち、少なくとも一の変数ノードと、該一の変数ノードに接続された全てのチェックノードとの間でやりとりするメッセージとすることができると共に、チェックノード処理演算手段が出力する第２のメッセージは、これを変数ノード処理演算手段がそのまま使用してチェックノードへのメッセージを算出することができるメッセージであり、チェックノード処理演算手段の出力データと変数ノード処理演算手段の入力データとが同様の要素、即ち、少なくとも一の変数ノードと、該一の変数ノードに接続された全てのチェックノードとの間でやりとりするメッセージとすることができる。
【００９０】
また、上記チェックノード処理演算手段は、入力された上記第１のメッセージからチェックを満たす確率又は当該確率に準じた値を求める第１の演算と、該第１の演算にて得られた該チェックを満たす確率又は当該確率に準じた値に基づき、上記第２のメッセージを求める第２の演算とを実行することができ、一旦チェックを満たす確率又は当該確率に準じた値を求めることで、変数ノード毎の第２のメッセージを出力可能となる。ここで、確率とは対数尤度比を含むものである。
【００９１】
更に、上記変数ノード処理演算手段からの上記第１のメッセージを保存する第１の記憶手段を有し、上記チェックノード処理演算手段は、上記第１の記憶手段から上記第１のメッセージを読み出すことができ、上述したように、チェックノード処理演算手段の入出力データと、変数ノード処理演算手段の入出力データが同一の要素からなるメッセージであるため、第１の記憶手段には、変数ノード処理演算手段から変数ノード毎の第１のメッセージが書き込まれ、チェックノード処理演算手段から変数ノード毎の第１のメッセージが読み出されることとなり、各処理演算手段が書き込むデータ・読み出すデータを同一アドレスで管理することができると共に、第１の記憶手段にアクセスを迅速化することができる。
【００９２】
更にまた、上記チェックノード処理演算手段における演算結果を記憶する第２の記憶手段を有し、上記第１の演算では、１以上の上記変数ノードからの１以上の上記第１のメッセージが逐次入力され、該１以上の上記第１のメッセージが渡された全てのチェックノードにおけるチェックを満たす確率又は当該確率に準じた値を逐次更新し、上記第２の演算では、再び上記１以上の上記変数ノードからの１以上の上記第１のメッセージが逐次入力され、上記第１の演算にて更新が終了したチェックを満たす確率又は当該確率に準じた値と、上記１以上の第１のメッセージとから、該１以上の上記第１のメッセージが渡された全てのチェックノードから該１以上の上記変数ノードへ渡す上記第２のメッセージを逐次算出し、上記第２の記憶手段は、上記逐次更新されるチェックを満たす確率又は当該確率に準じた値、又は更新が終了したチェックを満たす確率又は当該確率に準じた値を記憶することができる。
【００９３】
また、上記低密度パリティ検査符号は、任意の符号語をｐ回、巡回置換したものもまた符号語になる準巡回符号（quasi-cyclic code：ＱＣ符号）であって、更に上記ＱＣ符号は、ｐ＝１である巡回符号とすることができ、この場合、上記第２の記憶手段は、上記チェックノードと同数のシフトレジスタと、上記チェックノード処理演算手段からの演算結果により上記シフトレジスタのデータを更新する更新手段とを有し、上記シフトレジスタは、更新されたデータを出力することができ、パリティ検査行列をＱＣ符号とすることで、第２の記憶手段の構成を簡略化することができる。
【００９４】
更に、上記変数ノード処理演算手段は、上記ｐの倍数個の変数ノードから、該ｐの倍数個の変数ノードに接続される全てのチェックノードに渡す上記第１のメッセージを並列に演算し、上記第２の記憶手段は、上記ｐの倍数個の変数ノードにエッジにより接続された全てのチェックノードに対して当該ｐ個の変数ノードから渡される上記第１のメッセージにより更新された当該チェックノードにおけるチェックを満たす確率又は当該確率に準じた値を記憶することができ、ＱＣ符号であると、チェックノード処理演算におけるスループットを向上することができる。
【００９５】
更にまた、上記チェックノード処理演算手段が上記チェックを満たす確率又は当該確率に準じた値を算出する第１フェーズにおける演算処理と、上記チェックノード処理演算手段が上記第２のメッセージを算出し上記変数ノード処理演算手段が上記第１のメッセージを算出する第２フェーズにおける演算処理とを繰り返す繰り返し演算処理の繰り返し回数を制御する制御手段を有し、例えば上記繰り返し演算を所定の回数実行したり、上記事後確率が所定の条件を満たすまで実行したりすることができる。
【００９６】
また、上記チェックノード処理演算手段は、上記第１フェーズにおける上記第１の演算を実行する第１フェーズ用処理演算手段と、上記第２フェーズにおける上記第２の演算を行う第２フェーズ用処理演算手段とを有し、上記第１フェーズ用処理演算手段は、上記第２フェーズ用処理演算手段が上記第２の演算を実行直後に、次の繰り返し演算における上記第１の演算を実行することができ、第２フェーズと次の繰り返し演算の第１フェーズとをオーバーラップして行なうことにより、スループットを約２倍に向上することができる。
【００９７】
また、本発明に係る符号検出方法は、入力された低密度パリティ検査符号から、低密度パリティ検査行列に対応した複数のチェックノード及び複数の変数ノードの間でメッセージを伝搬させるメッセージパッシングアルゴリズムを用いて符号検出する符号検出方法において、各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算工程と、上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算工程とを有することを特徴とする。
【００９８】
本発明においては、チェックノード処理演算工程における入出力データ、即ちチェックノードから変数ノードへのメッセージと、変数ノード処理演算工程における入出力データ、即ち変数ノードからチェックノードへのメッセージとを同一の要素からなるメッセージとすることができ、データの入出力の制御が簡単化する。
【００９９】
本発明に係る復号装置は、入力された低密度パリティ検査符号から、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて符号検出して復号する復号装置において、各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算手段と、上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算手段と、上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号をする復号手段とを有することを特徴とする。
【０１００】
本発明においては、変数ノード処理演算手段の出力データと、チェックノード処理演算手段の入力データとが同様の要素、即ち、少なくとも一の変数ノードに接続された全てのチェックノードに対するメッセージとしたパリティ符号検出装置を備えた復号装置として利用することができ、例えば通信路を介して送信されることにより雑音の影響を受けた符号語から精度よく符号検出することができる。
【０１０１】
また、上記復号手段では、上記硬判定結果からパリティ部分を除去することができ、これにより組織符号のＬＤＰＣ符号の復号が可能になる。
【０１０２】
また、本発明に係る復号方法は、上述の入力された低密度パリティ検査符号から、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて符号検出して復号する方法である。
【０１０３】
本発明に係る情報処理装置は、メッセージから低密度パリティ検査符号に符号化され記録されたデータを再生する情報処理装置において、上記記録されたデータを読み出し、メッセージパッシングアルゴリズムを用いて複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて低密度パリティ検査符号の符号を検出して再生する再生手段を有し、上記再生手段は、各変数ノードについて、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを第１のメッセージとして各変数ノード毎に算出する変数ノード処理演算手段と、上記第１のメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージに基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力するチェックノード処理演算手段と、上記第２のメッセージから事後確率を算出し、該事後確率の硬判定復号をする復号手段とを有することを特徴とする。
【０１０４】
本発明においては、変数ノード処理演算手段の出力データと、チェックノード処理演算手段の入力データとが同様の要素、即ち、少なくとも一の変数ノードに接続された全てのチェックノードに対するメッセージとしたパリティ符号検出装置を備えた情報処理装置とすることができ、記録時又は再生時等におけるデータの誤りを精度よく訂正することができる。
【０１０５】
また、情報語を低密度パリティ検査符号に符号化する符号化手段と、上記低密度パリティ検査符号を記録する記録手段とを有することができ、記録再生装置として使用することができる。
【０１０６】
また、本発明に係る情報処理方法は、メッセージから低密度パリティ検査符号に符号化され記録されたデータを再生する方法である。
【発明の効果】
【０１０７】
本発明に係る符号検出装置及び方法においては、一の変数ノードに接続された全てのチェックノードへ渡すメッセージを入力とし、各チェックノードについて、一のチェックノードに接続された全ての変数ノードからのメッセージ（第１のメッセージ）に基づき、チェックノードから変数ノードへ渡すメッセージを算出し、一の変数ノードに接続された全てのチェックノードから当該一の変数ノードが受け取るメッセージを第２のメッセージとして出力することができ、このことにより、変数ノード処理演算手段の出力データと、チェックノード処理演算手段の入力データとを同様の要素、即ち、少なくとも一の変数ノードと、該少なくとも一の変数ノードに接続された全てのチェックノードとの間でやりとりするメッセージとすることができ、従ってノード間でやり取りするメッセージを保存するメモリ構成を簡略化することができると共にメモリへのアクセスが迅速化する。
【０１０８】
また、複数のチェックノードと複数の変数ノードとの間でメッセージを伝搬させて符号検出するメッセージパッシングアルゴリズムを用いて低密度パリティ検査符号を復号する際、ノード間でやり取りするメッセージを保存するメモリ構成を簡略化することにより、回路構成を簡略化及び小型化した復号装置及び情報処理装置、並びにメモリの書き込み・読み出しが容易な復号方法及び情報処理方法を提供することができる。
【発明を実施するための最良の形態】
【０１０９】
以下、本発明を適用した最良の実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、従来とは異なる手順により演算することで、回路構成を極めて簡素化したＬＤＰＣ符号の符号検出装置及びこれを備える各種情報処理装置に適用したものである。
【０１１０】
（１）パリティ検査行列
図１は、７行２１列のパリティ検査行列を示す図である。図１に示すパリティ検査行列は、階数が６、これによって定まる符号は符号長Ｎ＝２１、次元Ｋ＝１５の線形符号となる。この行列において各行における非零、即ち１の要素数Ｗｒは全て６で一定であり、各列における非零、即ち１の要素数Ｗｃは全て２で一定であるregular ＬＤＰＣ符号である。
【０１１１】
図２は、図１に示すパリティ検査行列に対応した２部グラフ示す図である。図２に示すように、Ｍ行Ｎ列のパリティ検査行列を表現した２部グラフは、チェックに対応するＭ個のノード（チェックノードＸｍ）、変数に対応するＮ個のノード（ビットノード（変数ノード）Ｙｎ）、及びチェックノードＸｍとビットノードＹｎとを接続するエッジにより構成される。エッジはパリティ検査行列の非零要素の場所に対応しており、第ｍ行第ｎ列の要素が零でない場合にのみｍ番目のチェックノードＸｍとｎ番目のビットノードＹｎとがエッジで接続される。
【０１１２】
（２）メッセージパッシングアルゴリズム
ここでは先ず、本発明の理解を容易とするため、エッジで接続されたチェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させる通常のメッセージパッシングアルゴリズムによるＬＤＰＣ符号の符号検出方法について説明する。メッセージパッシングアルゴリズムによるＬＤＰＣ符号の符号検出は、次のような手順を繰り返すことで実現される。
【０１１３】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、ビットノードＹｎからチェックノードＸｍに伝搬されるメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎを事前確率ｐ０ｎ，ｐ１ｎに初期化する。ここでｐｘｎとはビットｎが“ｘ”である事前確率を表すものとする。
【０１１４】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、チェックノードＸｍからビットノードＹｎに伝搬されるメッセージr０ｍ，ｎ，r１ｍ，ｎを次式に従って求める。
【０１１５】
【数１４】
2005045735.tif 000017
【０１１６】
［３］手順２−ビットノードにおける処理
必要に応じて各ビットの事後確率ｑ０ｎ、ｑ１ｎを、次式により求める。
【０１１７】
【数１５】
2005045735.tif 000018
【０１１８】
更に繰り返しが必要な場合、次式に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージを計算する。
【０１１９】
【数１６】
2005045735.tif 000019
【０１２０】
メッセージパッシングアルゴリズムによる復号は、終了条件を満たすまで手順１と手順２とを繰り返し、最後に硬判定復号で情報語が推定される。繰り返しの終了条件は、
１）繰り返しが予め定めた回数に達した時点で終了
２）予め定めた繰り返し回数に達していない場合でも硬判定結果がパリティチェックを満たせば終了
等が一般的である。ここで、パリティチェックは、下記（５）のように示される。
【０１２１】
【数１７】
2005045735.tif 000020
【０１２２】
このようなアルゴリズムと等価な計算方法として、対数尤度比ＬＬＲ（Log-Likelihood Ratio）を用いて対数領域での計算式に変形すれば、乗算に相当する演算は、全て加算に置き換えられ、ハードウェアやソフトウェアによる処理を簡略化できる。対数領域における演算のアルゴリズムを以下に示す。
【０１２３】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、エッジを伝搬するメッセージＱｍ，ｎを各ビットの事前対数尤度比Ｐｎで初期化する。ここで、エッジを伝搬するメッセージＱｍ，ｎ及び各ビットの事前対数尤度比Ｐｎは、夫々下記（６−１）及び（６−２）のように定義される。
【０１２４】
【数１８】
2005045735.tif 000021
【０１２５】
［２］手順１−チェックノードにおける処理
各チェックノードＸｍから出るすべてのエッジについて、エッジを伝搬するメッセージＲｍ，ｎを下記式（７−１）により計算する。ここで、Ａｍ、Ｂｍ、及びメッセージＲｍ，ｎは下記（７−２）乃至（７−４）のように定義され、ｆ（β）、αｍ，ｎ、及びβｍ，ｎは下記（７−５）乃至（７−７）で示される。
【０１２６】
【数１９】
2005045735.tif 000022
【０１２７】
［３］手順２−ビットノードにおける処理
各ビットの下記（８）に定義される事後対数尤度比Ｑｎを、下記式（９）により求める。
【０１２８】
【数２０】
2005045735.tif 000023
【０１２９】
【数２１】
2005045735.tif 000024
【０１３０】
更に繰り返しが必要な場合、下記式（１０）に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージＱｍ，ｎを計算する。
【０１３１】
【数２２】
2005045735.tif 000025
【０１３２】
ここで、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを求める際に使用される、上記（７−２）及び（７−３）にて定義されるＡｍ、Ｂｍの物理的な意味については次のように解釈できる。Ａｍｆ（Ｂｍ）を計算すると、下記式（１１）のように書ける。
【０１３３】
【数２３】
2005045735.tif 000026
【０１３４】
ここで、ｒ０ｍ、ｒ１ｍを、以下式（１２−１）及び（１２−２）のように定義した。
【０１３５】
【数２４】
2005045735.tif 000027
【０１３６】
ビットノードＹｎからチェックノードＸｍへのメッセージｑ０ｍ，ｎ及びｑ１ｍ，ｎを夫々下記（１３−１）及び（１３−２）としたとき、上記（１２−１）に示すｒ０ｍは、チェックを満たす確率に相当する。
【０１３７】
【数２５】
2005045735.tif 000028
【０１３８】
即ち、Ａｍ、Ｂｍは、各ビットノードＹｎ（ｎ∈Ｎ（ｍ））からチェックノードＸｍへのメッセージＱｍ，ｎ又はｑ０ｍ，ｎ、ｑ１ｍ，ｎに基づいた、チェックを満たす確率の間接的な表現に相当する。
【０１３９】
（３）第１の実施の形態
次に、本発明の第１の実施の形態について詳細に説明する。上述のようなパリティ検査行列によるＬＤＰＣ符号の通常の符号検出方法に対し、本発明では、繰り返し処理１回あたりの演算において演算器を複数回用いる方法であり、且つ先に示した従来のタイプ２の構成とは異なる回路構成を提案するものである。
【０１４０】
従来のタイプ２の構成は、チェックノードＸｍ（Ｘ０〜ＸＭ−１のＭ個）における処理で用いる演算器は、ビットノードＹｎ（Ｙ０〜ＹＮ−１のＮ個）からチェックノードＸｍへのメッセージＱｍ，ｎ（ｎ∈Ｎ（ｍ））を入力として受け取り、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｎ∈Ｎ（ｍ））を出力する構成であり、着目しているチェックノードＸｍを順次切り替えることにより、全てのチェックノードＸｍの処理を終える動作を行う。ここで、Ｎ（ｍ）は、パリティ検査行列第ｍ行における非零要素の列番号、Ｍ（ｎ）は、パリティ検査行列第ｎ列における非零要素の行番号に対応する。
【０１４１】
即ち、例えば図１に示すパリティ検査行列の場合であれば、最初に着目するチェックノードＸ０において、チェックＸ０のエッジに接続されたビットノードＹ０、Ｙ１、Ｙ３、Ｙ１１、Ｙ１３、Ｙ１７から夫々メッセージＱｍ，ｎ（ｎ∈Ｎ（ｍ））（計６個のメッセージＱｍ，ｎ）を受け取り、これらから、各ビットノードＹ０、Ｙ１、Ｙ３、Ｙ１１、Ｙ１３、Ｙ１７に渡すメッセージＲｍ，ｎ（ｎ∈Ｎ（ｍ））（計６個のメッセージＲｍ，ｎ）を算出する処理を行った後、次に着目するチェックノードＸ１における演算を行うといったように、着目するチェックノードＸｍを順次切替え演算を行っている。
【０１４２】
これに対して、本実施の形態にて用いられる演算器は、チェックノードＸｍに着目して演算を行わず、常にビットノードＹｎに着目した演算を行う。即ち、図１に示すパリティ検査行列であれば、着目しているビットノードＹｎを順次切り替えながら、ビットノードＹｎからチェックノードＸｍへの第１のメッセージとしてのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））（計２つのメッセージＱｍ，ｎ）を入力として受け取る。即ち、先ず、ビットノードＹ０に接続された全てのチェックノードＸ０、Ｘ６がビットノードＹ０からメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取り、次に、ビットノードＹ１に接続された全てのチェックノードＸ０、Ｘ３がビットノードＹ１からメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取るといったように、ビットノードＹｎから逐次メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取り、メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取ったチェックノードＸｍについて、逐次演算を繰り返すことで、一旦、上記式（７−２）及び（７−３）に示すＡｍ、Ｂｍ、或いはチェックを満たす確率ｒ０ｍやそれに準じた値等を求める。このように、全てのビットノードＹｎからのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取り終わった時点で、全てのチェックノードＸｍにおける上記式（７−２）及び（７−３）に示すＡｍ、Ｂｍ、或いはチェックを満たす確率ｒ０ｍやそれに準じた値が求まる。
【０１４３】
その後、再びビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を入力として受け取り、求めたＡｍ、Ｂｍと、受け取ったＱｍ，ｎ（ｍ∈Ｍ（ｎ））とから、チェックノードＸｍからビットノードＹｎへの第２のメッセージとしてのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））（計２つのメッセージＲｍ，ｎ）を出力する。即ち、上述と同様に、ビットノードＹ０に接続された全てのチェックノードＸ０、Ｘ６がビットノードＹ０からメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））（Ｑ０，０、Ｑ６，０）を受け取り、これにより、チェックノードＸ０、Ｘ６がメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を渡されたビットノードＹ０に対して送るメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））（Ｒ０，０、Ｒ６，０）を算出して出力し、次に、ビットノードＹ１に接続された全てのチェックノードＸ０、Ｘ３がビットノードＹ１からメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））（Ｑ０，１、Ｑ３，１）を受け取り、同じく、チェックノードＸ０、Ｘ３がメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を渡されたビットノードＹ１に対して送るメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））（Ｒ０，１、Ｒ３，１）を算出して出力するといったような処理を繰り返す。このように、ビットノードＹｎから、順次メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を渡さることで、ビットノードＹｎへメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））が順次出力されるものである。
【０１４４】
ここで、チェックを満たす確率に準じた値とは、ｒ０ｍをある特定の関数によって変換された値を指し、逆関数等の別の関数によって元のｒ０ｍやその近似値を導き出すことのできる値を指す。
【０１４５】
（３−１）符号検出装置
以下、本実施の形態について更に詳細に説明する。図３は、本発明の実施の形態における符号検出装置を示すブロック図である。本実施の形態における符号検出装置は、説明の簡単のため、図１に示すＭ行Ｎ列、各行における非零要素数Ｗｒ＝６、各列における非零要素数Ｗｃ＝２のパリティ検査行列を有するＬＤＰＣ符号、即ち、階数が６、これによって定まる符号は符号長Ｎ＝２１、次元Ｋ＝１５の線形符号の符号検出を行うものとして説明するが、実際には符号長は例えば１００〜６５Ｋ等で、例えば後述する記録再生装置等においてはセクタ単位を符号長とする等することができ、また、各列における非零要素数Ｗｃは３以上であるのが一般的である。また、この図３においては、初期化の処理を行う処理部、及び繰り返し終了条件の判断部は図示を省略している。更に、以下の実施の形態においては、ＬＬＲを用いた対数領域のアルゴリズムを示すが、確率を用いたアルゴリズムも同様に構成できることは勿論である。
【０１４６】
図３に示すように、符号検出装置１は、着目しているビットノードＹｎの番号（０〜Ｎ−１番目）を表すカウンタ２と、事前値（事前対数尤度比）Ｐｎを格納するメモリ３と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を格納する第１の記憶手段としてのメモリ４と、メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））から下記（７−２）及び（７−３）に示すＡｍ、Ｂｍを逐次更新し、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するチェックノード処理演算器５と、チェックノード処理演算器５により算出されたＡｍ、Ｂｍを格納する第２の記憶手段としてのメモリ６と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するビットノード処理演算器７とを有する。先ず、本符号検出装置１の動作に対応した手順について説明する。
【０１４７】
［１］手順０−初期化
各ビットノードＹｎから出るすべてのエッジについて、エッジを伝搬するメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を各ビットの事前対数尤度比（事前値）Ｐｎで初期化する。
【０１４８】
［２］手順１'
各チェックノードＸｍについて、下記式（７−２）、（７−３）に定義されるＡｍ、Ｂｍを求める。
【０１４９】
【数２６】
2005045735.tif 000029
【０１５０】
［３］手順２'
各ビットノードＹｎに入る全てのエッジに関して下記式（７−１）によりメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を求める。また、各ビットの事後対数尤度比（事後値）Ｑｎを、下記式（９）により求める。
【０１５１】
【数２７】
2005045735.tif 000030
【０１５２】
【数２８】
2005045735.tif 000031
【０１５３】
更に、繰り返し処理が必要な場合、次式に従ってビットノードＹｎからチェックノードＸｍに伝搬されるメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を下記式（１０）により更新する。
【０１５４】
【数２９】
2005045735.tif 000032
【０１５５】
上述した従来の手順１、手順２と比べると、チェックノードＸｍにおける従来の処理（［２］手順１）が、本発明においては手順１'と手順２'の２つの手順に分割されている。従来の構成では、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（αｍ，ｎ，βｍ，ｎ）は、上述の手順１に示すように、一度のみ参照していたが、本実施の形態における方式では手順１'と手順２'の２回参照することになる。即ち、各チェックノードＸｍは、手順１'と手順２'とで同じメッセージＱｍ，ｎを重複して受け取ることになる。また、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎは、従来は、図３２（ａ）に示すメッセージＱｍ，ｎ（ｎ∈Ｎ（ｍ））（データＤ１４）であったが、本実施の形態においては、図３２（ａ）に示すメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））（データＤ１３）となっている。
【０１５６】
チェックノード処理演算器５及びビットノード処理演算器７による繰り返し処理１回の動作は、２つのフェーズにより実行される。第１フェーズではチェックノード処理演算器５により手順１'に対応した演算を行い、続いて第２フェーズではチェックノード処理演算器５及びビットノード処理演算器７により手順２'に対応した演算を行う。
【０１５７】
次に、符号検出装置の各構成ブロックについて詳細に説明する。以上の処理を実行するために、各ブロックは次のような動作をする。
【０１５８】
カウンタ２は、着目しているビットノードＹｎの番号を表すカウンタであり、第１フェーズ、第２フェーズのそれぞれにおいて、０からＮ−１の値をカウントする。つまり、１回の繰り返し処理の間にＮ進カウンタは２周することになる。
【０１５９】
事前値Ｐｎを格納するメモリ３は、入力された事前値ＰｎをビットノードＹｎの番号のアドレスに格納する。またカウンタの値ｎに応じて事前値Ｐｎを出力する。
【０１６０】
ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を格納するメモリ４は、１つのアドレスｎでビットノードＹｎから出るすべてのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））、即ち本実施の形態においては、２つのメッセージＱｍ，ｎに同時にアクセスできる構成とする。第１フェーズでは読み出しのみ、第２フェーズでは読み出し及び書き込み共に行う。
【０１６１】
チェックノード処理演算器５は、第１フェーズ（手順１’）では、ビットノードＹｎに対応したメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を読み出し、αｍ，ｎ、ｆ（βｍ，ｎ）を計算し、ビットノードＹｎに接続された全てのチェックノードＸｍ（ｍ∈Ｍ（ｎ））に関してメモリ６から各々Ａｍ、Ｂｍを入力として受け取り、Ａｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ）を計算、即ちＡｍ、Ｂｍを更新してメモリ６に出力する。第２フェーズでは、再びビットノードＹｎに対応したメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を読み出し、ビットノードＹｎに接続された全てのチェックノードＸｍ（ｍ∈Ｍ（ｎ））に関してメモリ６から更新が終了したＡｍ、Ｂｍを入力として受け取り、Ｒｍ，ｎ＝（Ａｍ／αｍ，ｎ）ｆ（Ｂｍ−ｆ（βｍ，ｎ））（ｍ∈Ｍ（ｎ））を算出し、ビットノード処理演算器７に出力する。
【０１６２】
Ａｍ、Ｂｍを格納するメモリ６は、第１フェーズは、Ａｍ、Ｂｍを逐次更新するモードとして動作する。最初に全てのチェックノードＸｍに関してＡｍ＝１、Ｂｍ＝０に初期化を行う。ビットノードＹｎに関連するチェックノードＸｍ（ｍ∈Ｍ（ｎ））について、現在、途中まで求まっているＡｍ、Ｂｍをチェックノード処理演算器５に出力し、次に、チェックノード処理演算器５からＡｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ））を受け取ってＡｍ、Ｂｍを更新する。第１フェーズの終わりには手順１'の式（１６−１）及び（１６−２）で表された夫々Ａｍ及びＢｍが求まる。
【０１６３】
第２フェーズではビットノードＹｎに関連するチェックノードＸｍ（ｍ∈Ｍ（ｎ））について、Ａｍ、Ｂｍをチェックノード処理演算器５へ出力する。
【０１６４】
ビットノード処理演算器７は、第２フェーズでのみ動作する。ビットノードＹｎに入るメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））をチェックノード処理演算器５から受け取り、メモリ３から事前値Ｐｎを受け取り、上記式（９）に示す事後値Ｑｎ又は硬判定結果ｃｎ＾、及びチェックノードＸｍへのメッセージＱｍ，ｎ＝Ｑｎ−Ｒｍ，ｎ（ｍ∈Ｍ（ｎ））を出力する。
【０１６５】
以上の構成とすることで、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を格納するメモリ４は、読み出し時、書き込み時ともに、着目しているビットノードＹｎのアドレスで、Ｑｍ，ｎ（ｍ∈Ｍ（ｎ））にアクセスできるため、１つのＲＡＭで実現可能となる。
【０１６６】
図４は、本実施の形態におけるチェックノード処理演算器５とビットノード処理演算器７との間でやり取りされるデータの流れを示す図である。上述したように、手順１及び手順２の演算を繰り返す従来の符号検出装置においては、図３１及び図３２に示したように、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリは、チェックノード処理演算器における読み出し時には行方向（データＤ１４）に、ビットノード処理演算器による書き込み時には列方向（データＤ１３）にアクセスする必要があるため、行単位、列単位にアクセスしてスループットを向上させるためにはメモリを複数バンクに分ける等、構成が複雑化していた。
【０１６７】
これに対して、本実施の形態においては、チェックノード処理演算器５は、ビットノードに着目した演算を行うため、図４に示すように、ビットノード処理演算器７からメモリ４に書き込まれたデータＤ１（メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ）））と同じ列方向のデータＤ２（メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ）））をチェックノード処理演算器５が読み出して使用する。このように、上述の図３１に示すチェックノード処理演算器におけるメモリの読み出しデータは、データＤ１４（メッセージＱｍ，ｎ（ｎ∈Ｎ（ｍ）））ではなく、データＤ１３（メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ）））となるため、書き込み及び読み出しを同一のアドレスとすることができ、回路設計を極めて簡略にすることができる。
【０１６８】
具体的には、列方向の非零要素数がＷｃのレギュラーＬＤＰＣ符号の場合、１つのメッセージＱｍ，ｎを表現するビット数をｑとすると、メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））は（Ｗｃ×ｑ）ビットで表せるため、（Ｗｃ×ｑ）ビット、ＮワードのＲＡＭで実現できる。
【０１６９】
また、事前値Ｐｎを格納するメモリ３、ビットノードＹｎからチェックノードＸｍへのメッセージを格納するメモリ４は、いずれもアクセスするアドレスが１ずつ変化するため、巡回シフトレジスタによる構成とすることが可能である。
【０１７０】
更に、チェックノード処理演算器５におけるαｍ，ｎ、ｆ（βｍ，ｎ）の演算をビットノード処理演算器７で行って、ビットノードＹｎからチェックノードＸｍへのメッセージを格納するメモリにはαｍ，ｎ、ｆ（βｍ，ｎ）を保存する構成としてもよい。この場合、後述する第１フェーズ用チェックノード処理演算器７５ａと第２フェーズ用チェックノード処理演算器７５ｂ（図２０参照）とで重複していたαｍ，ｎ、ｆ（βｍ，ｎ）の計算をビットノード処理演算器の１箇所で行うことができる。
【０１７１】
（３−２）チェックノード処理演算器
上述した如く、本実施の形態における符号検出装置においては、ビットノード処理演算器７及びチェックノード処理演算器５が共にビットノードに着目した演算を行うため、メッセージＱｍ，ｎを格納するメモリの回路構成を簡略化できる。ここで、ビットノードＹｎに着目して上述の手順１’の演算を行うチェックノード処理演算器の具体例について詳細に説明する。
【０１７２】
図５は、本実施の形態の符号検出装置におけるチェックノード処理演算器の一具体例を示すブロック図である。図５に示すように、チェックノード処理演算器１０は、非零要素数Ｗｃと同数の処理部１００、１０１（以下、１０ｔという。）を有し、各処理部１０ｔには、メモリ４から読み出されたビットノードからチェックノードへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））と、メモリ６から読み出されたＡｍ、Ｂｍ（ｍ∈Ｍ（ｎ））とが入力され、第１フェーズでは、順次Ａｍ、Ｂｍを更新して出力し、第２フェーズでは、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を出力するための演算を行う。
【０１７３】
例えば、処理部１００には、メッセージＱｍ＿ｔ（ｎ），ｎ＝Ｑｍ＿０（ｎ），ｎ、Ａｍ＿ｔ（ｎ）＝Ａｍ＿０（ｎ）、Ｂｍ＿ｔ（ｎ）＝Ｂｍ＿０（ｎ）が入力される。ここで、Ｑｍ＿ｔ（ｎ），ｎ、Ａｍ＿ｔ（ｎ）、Ｂｍ＿ｔ（ｎ）は、ビットノードＹｎからエッジによって接続されたＷｃ個のチェックノードＸｍ（ｍ∈Ｍ（ｎ））のうち、ｔ番目のエッジに接続された夫々チェックノードＸｍに対するメッセージ、Ａｍ、Ｂｍを示す。本実施の形態においては、Ｗｃ＝２としているので、ｔ＝０又は１である。
【０１７４】
この処理部１００は、メッセージＱｍ＿０（ｎ），ｎが入力されると、メッセージＱｍ＿０（ｎ），ｎの符号部分であるαｍ＿０（ｎ），ｎと入力されるＡｍ＿０（ｎ）とを乗算又は除算したＡｍ＿０（ｎ）を出力する乗算器１１と、メッセージＱｍ＿０（ｎ），ｎの絶対値であるβｍ＿０（ｎ），ｎを上記式（７−５）に従って関数ｆで変換したｆ（βｍ＿０（ｎ），ｎ）を出力する変換器１２と、変換したｆ（βｍ＿０（ｎ），ｎ）と入力されるＢｍ＿０（ｎ）とを加算したＢｍ＿０（ｎ）を出力する加算器１３と、入力されるＢｍ＿０（ｎ）から変換したｆ（βｍ＿０（ｎ），ｎ）を減算する加算器１４と、加算器１４の減算結果を上記式（７−５）に従って変換する変換器１５と、変換器１５の変換結果と更新されたＡｍ＿０（ｎ）とを乗算してチェックノードＸｍからビットノードＹｎへのメッセージＲｍ＿０（ｎ），ｎを出力する乗算器１６とを有する。ここで加算器１３と加算器１４は加減算の制御信号を用いることで共用することも可能である。
【０１７５】
次に、このチェックノード処理演算器の動作について詳細に説明する。図６は、図１に示すパリティ検査行列（各列の非零要素数Ｗｃ＝２）を有するＬＰＤＣ符号の符号を検出する場合の、各時刻（カウント値）毎にビットノードＹｎからチェックノードに渡されるメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を説明するための２部グラフを示す図である。上述したように、図３に示すカウンタ２は、上記手順１’及び手順２’からなる演算のうち、ｉ回目の演算の第１フェーズでカウント値Ｔｉ＿１＝０〜Ｎ−１をカウントし、ｉ回目の演算の第２フェーズで、カウント値Ｔｉ＿２＝０〜Ｎ−１をカウントするものとする。図６（ａ）乃至（ｃ）は、夫々第１フェーズにおけるカウント値Ｔｉ＿１＝０、１、Ｎ−１において、チェックノード処理演算器１０がメモリ６から読み出すメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を示す。
【０１７６】
チェックノード処理演算器１０は、カウンタ２のカウント値Ｔｉ＿１＝０〜Ｎ−１の間の第１フェーズでは、乗算器１１、変換器１２及び加算器１３により、Ａｍ＿０（ｎ）、Ｂｍ＿０（ｎ）を更新する。全てのＡｍ、Ｂｍは、先ずＡｍ＝１、Ｂｍ＝０に初期化される。カウンタ２のカウント値Ｔｉ＿１が０からＮ−１へ変化すると、着目するビットノードＹｎもＹ０〜ＹＮ−１へ変化する。
【０１７７】
例えば、着目するビットノードＹｎの１番目のエッジに接続されたチェックノードＸｍへのメッセージＱｍ＿０（ｎ），ｎからＡｍ、Ｂｍを演算する処理部１００においては、図６（ａ）に示すように、カウント値Ｔｉ＿１＝０で、メモリ４からビットノードＹ０の１番目のエッジに接続されたチェックノードＸ０へのメセージＱｍ＿０（０），０（＝Ｑ０，０）が読み出され、メモリ６から初期値Ａｍ＿０（０）＝１、Ｂｍ＿０（０）＝０が読み出されて処理部１００に供給され、Ａｍ＿０（０）、Ｂｍ＿０（０）（チェックノードＸ０におけるＡｍ、Ｂｍ）が更新される。また、同時（カウント値Ｔｉ＿１＝０）に、処理部１０１には、メモリ４からビットノードＹ０の２番目のエッジに接続されたチェクノードＸ６へのメセージＱｍ＿１（０），０（＝Ｑ６，０）が読み出され、メモリ６から初期値Ａｍ＿１（０）＝１、Ｂｍ＿１（０）＝０が読み出されて処理部１０１に供給され、Ａｍ＿１（０）、Ｂｍ＿１（０）（チェックノードＸ６におけるＡｍ、Ｂｍ）が更新される。
【０１７８】
そして、図６（ｂ）に示すように、次のカウントＴｉ＿１＝１においては、着目するビットノードＹｎがＹ１に移動し、処理部１００には、ビットノードＹ１の１番目のエッジに接続されたチェックノードＸ０へのメセージＱｍ＿０（１），１（＝Ｑ０，１）がメモリ４から読み出され、Ａｍ＿０（１）、Ｂｍ＿０（１）（チェックノードＸ０におけるＡｍ、Ｂｍ）が更新される。また、処理部１０１には、ビットノードＹ１の２番目のエッジに接続されたチェックノードＸ３へのメセージＱｍ＿１（１），１（＝Ｑ３，１）がメモリ４から読み出され、Ａｍ＿１（１）、Ｂｍ＿１（１）（チェックノードＸ３におけるＡｍ、Ｂｍ）が更新される。
【０１７９】
そして、カウント値がＮ−１になるまで逐次Ａｍ＿ｔ（ｎ）、Ｂｍ＿ｔ（ｎ）を更新する。即ち、図６（ｃ）に示すように、カウント値がＮ−１において、着目するビットノードＹｎがＹＮ−１に移動し、処理部１００には、ビットノードＹＮ−１の１番目のエッジに接続されたチェックノードＸ１へのメッセージメセージＱｍ＿０（Ｎ−１），Ｎ−１（＝Ｑ１，Ｎ−１）が供給され、これによりＡｍ＿０（Ｎ−１）、Ｂｍ＿０（Ｎ−１）（チェックノードＸ１におけるＡｍ、Ｂｍ）が更新される。また、処理部１０１には、ビットノードＹＮ−１の２番目のエッジに接続されたチェックノードＸ３へのメッセージメセージＱｍ＿１（Ｎ−１），Ｎ−１（＝Ｑ３，Ｎ−１）が供給され、これによりＡｍ＿１（Ｎ−１）、Ｂｍ＿１（Ｎ−１）（チェックノードＸ３におけるＡｍ、Ｂｍ）が更新される。
【０１８０】
以上のカウントＴｉ＿１＝Ｎ−１までに更新されたＡｍ＿ｔ（ｎ）、Ｂｍ＿ｔ（ｎ）は、上記（７−２）及び（７−３）を満たすＡｍ、Ｂｍである。
【０１８１】
次のカウント値Ｔｉ＿２＝０〜Ｎ−１の間の第２フェーズにおいては、乗算器１１、変換器１２、加算器１４、変換器１５、及び乗算器１６により、第１フェーズにて求められたＡｍ、Ｂｍを使用してメッセージＲｍ＿ｔ（ｎ），ｎの演算が行われる。
【０１８２】
例えば、第２フェーズのカウント値Ｔｉ＿２＝０における処理部１００においては、図６（ｄ）に示すように、ビットノードＹ０の１番目のエッジに接続されたチェックノードＸ０へのメセージＱｍ＿０（０），０（＝Ｑ０，０）が再びメモリ４から読み出され、メモリ６から上述の第１フェーズで求めたＡｍ＿０（０）＝Ａ０、Ｂｍ＿０（０）＝Ｂ０が読み出されて処理部１００に供給される。
【０１８３】
そして、処理部１００では、乗算器１１にてＡ０とビットノードＹ０からのメッセージＱ０，０から求まるα０，０が除算され、Ａ０／α０，０が出力される。また、加算器１４にて、Ｂ０−ｆ（β０，０）が求められ、これを更に変換器１５にて関数ｆにて変換したものと、上記乗算器１１の出力Ａ０／α０，０とを乗算器１６にて乗算することで、上記式（７−１）に示す、ビットノードＹ０の１番目のエッジに接続されたチェックノードＸｍ＝Ｘ０からビットノードＹ０へ渡されるメッセージＲ０，０が算出される。
【０１８４】
このように、本実施の形態のチェックノード処理演算器１０においては、各ビットノードＹｎ毎からのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））により演算を行うため、ビットノードＹｎとエッジにより接続されたチェックノードの個数、即ちＷｃ個の処理部を有し、各処理部にて各ビットノードＹｎの各エッジにて伝搬されるメッセージを処理演算することで、チェックノード処理演算器において、ビットノードに着目した演算を行うようにしたものである。
【０１８５】
また、チェックノード処理演算器において第２フェーズで求めたチェックノードからビットノードへのメッセージＲｍ＿ｔ（ｎ），ｎが、図３に示すビットノード処理演算器７に供給される。ここで、図６（ｄ）に示す場合、カウント値Ｔｉ＿２＝０で出力されるメッセージＲｍ＿ｔ（ｎ），ｎは、Ｒｍ＿０（ｎ），ｎ（＝Ｒ０，０）、Ｒｍ＿１（ｎ），ｎ（＝Ｒ６，０）である。従って、これら２つの値から、ビットノード処理演算器７では、上述の式（１０）により、次の繰り返し演算における第１フェーズにて使用するためのメッセージＱｍ＿ｔ（ｎ），ｎを演算してメモリ４に格納することができる。即ち、チェックノード処理演算器から出力されるメッセージＲｍ，ｎは、従来は、図３２（ｂ）に示すように、行方向のデータＤ１１（Ｒｍ，ｎ（ｎ∈Ｎ（ｍ）））であったのに対し、本実施の形態においては、ビットノード処理演算器が読み出したい列方向のデータＤ１２（Ｒｍ，ｎ（ｍ∈Ｍ（ｎ）））となり、図４に示すように、入力されたデータＤ２（Ｑｍ，ｎ（ｍ∈Ｍ（ｎ）））を使用してそのまま演算することができるので、メッセージＲｍ，ｎを格納するメモリは不要となっている。
【０１８６】
（３−３）Ａｍ、Ｂｍを格納するメモリ
次に、上述のチェックノード処理演算器により更新されたＡｍ、Ｂｍを格納するメモリについて詳細に説明する。本実施の形態においては、ビットノード処理演算器がビットノードＹｎに着目しての第１フェーズ及び第２フェーズの演算を行うために、Ａｍ、Ｂｍを格納するメモリが必要である。図３に示す符号検出装置１において、このＡｍ、Ｂｍを格納するメモリ６は次の機能を備える。
【０１８７】
（機能１）ビットノードＹｎに関連するチェックノードＸｍ（ｍ∈Ｍ（ｎ）について、Ａｍ、Ｂｍを選択して出力する
（機能２）Ａｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ）を受け取って新たにＡｍ、Ｂｍとし、ｍ番目の保管場所に保存する
【０１８８】
任意のパリティ検査行列の場合、各列における非零要素数Ｗｃの最大値の数だけのリードポート、ライトポートが必要である。図７は、本実施の形態の符号検出装置におけるＡｍを格納するメモリを示すブロック図である。チェックノードＸｍの個数分、即ちＭ個の保存場所のうち適切なＷｃ箇所のＡｍを更新するための更新手段としての更新回路３１と、Ｍ個のＡｍを保存するＭ個の保管場所（メモリ）３２０〜３２６と、Ｍ個の保存場所３２０〜３２６から適切なＷｃ箇所のＡｍを選択して出力するための選択手段としての選択回路３３と、更新回路３１及び選択回路３３に対して適切なＷｃ箇所を指定する制御部３４とを有する。
【０１８９】
制御部３４は、着目するビットノードＹｎにエッジが接続されるチェックノードＸｍ（ｍ∈Ｍ（ｎ））を指定するための情報を保存するメモリを有し、図３に示すカウンタ２から入力されるカウント値のタイミングで、当該チェックノードＸｍ（（ｍ∈Ｍ（ｎ）））を指定する情報を読み出し、更新回路３１及び選択回路３３に供給する。即ち、例えば、ビットノードＹ０に対してはチェックノードＸ０、Ｘ６に対する保存場所３２０、３２６に各回路がアクセスするよう制御信号を出力する。これにより、選択回路３３は、保存場所３２０、３２６を指定してそのＡｍを読み出し、更新回路３１は、保存場所３２０、３２６のデータを更新する。
【０１９０】
図８は、図７に示すＡｍを格納するメモリ３０の更に具体的な構成を示すブロック図である。上述したように、各列における非零要素数Ｗｃ＝２である場合、各カウント値において、２つのＡｍ、Ｂｍが更新される。
【０１９１】
図８に示すように、Ａｍを格納するメモリ３０において、図７に示す更新回路３１として、更新されたＡｍ＿ｔ（ｎ）（ｔ＝０，１、ｍ＿ｔ（ｎ）＝０〜Ｍ−１、ｎ＝０〜Ｎ−１）を所定の保存箇所に選択出力するためにチェックノードＸｍ毎に、マルチプレクサ３６ｍ（３６０〜３６Ｍ−１）が設けられる。また、図７に示す保存場所３２０〜３２６としてレジスタ３７ｍ（３７０〜３７Ｍ−１）が設けられ、選択回路３３として、カウント値が示す着目しているビットノードＹｎにエッジが接続されたチェックノードＸｍ（ｍ∈Ｍ（ｎ））に対応したレジスタ３７ｍからのデータを選択してＡｍ＿ｔ（ｎ）を出力するマルチプレクサ３８ｔ（３８０〜３８Ｗｃ−１）が設けられ、更にこれら各部を制御する制御回路３９が設けられている。
【０１９２】
制御回路３９は、各マルチプレクサ３６ｍ、３８ｔの選択信号端子及びレジスタ３７ｍのイネーブル端子に、着目しているビットノードＹｎと接続されているチェックノードＸｍ＿ｔ（ｎ）に対応した制御信号を入力する。ここで、マルチプレクサ３６ｍの選択信号端子及びレジスタ３７ｍのイネーブル端子には、更新したＡｍ＿ｔ（ｎ）に対応するチェックノードＸｍ＿ｔ（ｎ）を示す制御信号が入力され、マルチプレクサ３８ｔの選択信号端子には、チェックノード処理演算器にて使用されるＡｍ＿ｔ（ｎ）に対応したチェックノードＸｍ＿ｔ（ｎ）を示す制御信号が供給され、このチェックノードＸｍ＿ｔ（ｎ）に対応したＡｍ＿ｔ（ｎ）がチェックノード処理演算器に読み出されるようになされる。即ち、上述したように、カウント値Ｔｉ＿１＝０のとき、着目しているビットノードＹｎ＝Ｙ０であり、これに接続されたチェックノードＸｍ＿０（０）、Ｘｍ＿１（０）、は、Ｘ０、Ｘ６である。
【０１９３】
入力されたＡｍ＿ｔ（ｎ）はマルチプレクサ３６ｍを介して制御信号により指定される、チェックノードＸｍ＿ｔ（ｎ）に対応したレジスタ３７ｍに供給される。一方、制御信号により、カウント値が示す着目しているビットノードＹｎにエッジが接続されたチェックノードＸｍ（ｍ∈Ｍ（ｎ））に対応したレジスタ３７ｍから所定のＡｍ＿ｔ（ｎ）が読み出されてマルチプレクサ３８０、３８１を介して出力される。
【０１９４】
このように、本実施の形態におけるＡｍを格納するメモリは、チェックノードＸｍと同数のレジスタを有し、ビットノードＹｎを順次選択するカウント値の回数分、更新されることで上記式（７−２）に示すＡｍが格納されたものとなる。Ｂｍを格納するメモリに関しても同様の構成とすることができる。
【０１９５】
（３−４）符号検出方法
次に、本実施の形態における符号検出方法について説明する。図９（ａ）は、本実施の形態における符号検出方法を示すフローチャートであり、図９（ｂ）は、各処理工程を擬似的に示すプログラムコードを示す図である。図９に示すように、先ず、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎが事前値Ｐｎにより初期化され（ステップＳ１、ＳＰ１）、第１フェーズの演算が行われる（ステップＳ２、ＳＰ２）。第１フェーズでは、まず、全てのＡｍ、ＢｍがＡｍ＝１、Ｂｍ＝０に初期化され、次いでチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するためのＡｍ、Ｂｍの更新が行なわれる。Ａｍ、Ｂｍの更新は、カウント値の順に一のビットノードＹｎからのメッセージが読み出され、メッセージに含まれる２つのチェックノードＸｍに対するＡｍ、Ｂｍが更新され、最後のビットノードＹ２０からのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））（Ｑ１，２０、Ｑ３，２０）によるＡ１、Ａ３、Ｂ１、Ｂ３の更新が終了した時点で、全てのチェックノードＸｍにおける上記（７−２）、（７−３）に示すＡｍ、Ｂｍが求まる。
【０１９６】
次に、更新済みのＡｍ、Ｂｍと、上述のステップＳ２で使用したビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））により、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））が算出される（ステップＳ３、ＳＰ３）。この場合も、カウント値の順に一のビットノードＹｎからのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））が読み出され、メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））が渡される２つのチェックノードＸｍにおいてメッセージＲｍ，ｎが算出され、この２つのメッセージメッセージＲｍ，ｎからなるメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））が出力される。
【０１９７】
そして、各カウント値が示すチェックノードＸｍ（ｍ∈Ｍ（ｎ））からのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））から、事後値Ｑｎ及び当該チェックノードに渡すメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））が算出される（ステップＳ４、ＳＰ４）。
【０１９８】
そして、以上のステップＳ２〜ステップＳ４までの繰り返し回数が規定の回数に達したか否かが判定され（ステップＳ５）、規定の繰り返し回数に達していない場合は、再びステップＳ２〜ステップＳ４までの処理を繰り返し、規定の繰り返し回数に達している場合は、硬判定復号が行われ、その結果が出力される（ステップＳ６）。また、ステップＳ４、ＳＰ４において、メッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を算出する過程において得られる事後値Ｑｎが所定の条件に達しているか否かを検出し、事後値Ｑｎが所定の条件、即ちパリティチェックを満たしている場合は、繰り返し処理を中止してステップＳ６の硬判定復号を行うようにしてもよい。
【０１９９】
（３−５）通信装置
次に、以上説明した符号検出装置を備えた情報処理装置の一例としての通信装置について説明する。本符号検出装置１により、符号検出を行うためには、先ず、情報語（メッセージ）を例えば図１に示すようなパリティ検査行列を有する符号語に符号化する必要がある。即ち、そのような符号語を通信路を介して伝送した場合、伝送過程で雑音等の影響により誤りが生じた場合であっても、受信された受信語は、本符号検出装置１により符号検出を行うことができ、もとのメッセージに復号することができる。
【０２００】
図１０は、本実施の形態における通信装置を示すブロック図である。図１０に示すように、通信装置８０は、情報語（メッセージ）からＬＤＰＣ符号を生成するＬＰＤＣ符号化部８１と、ＬＰＤＣ符号化された符号語を変調する変調部８２と、変調された符号語を伝送する通信路８３と、通信路８３からの受信語を受け取り復調する復調部８４と、復調された受信語から符号を検出する符号検出装置としてのＬＤＰＣ復号部８５とを有する。
【０２０１】
ＬＤＰＣ符号化部８１は、情報語をＬＤＰＣ符号に変換する。Ｍ行Ｎ列、Ｋ次元のパリティ検査行列Ｈにて符号検出が可能なＬＤＰＣ符号を得るためには、先ず、そのパリティ検査行列Ｈから、Ｋ行Ｎ列の生成行列Ｇ（ＧＨＴ＝０を満たす）を求める。即ち、図１に示すパリティ検査行列Ｈは、各行にＷｒ（＝６）個、各列にＷｃ（＝２）個の非零要素１を持ち、それ以外の成分はすべて０であるように構成される。このパリティ検査行列Ｈから生成行列ＧＴを、下記式（１４−１）に示す拘束条件を満たすように構成する。このような拘束条件を満たす生成行列は簡単に構成することができる。即ち、パリティ検査行列を、Ｈ＝（Ｈ１，Ｈ２）と、２つの部分行列Ｈ１：Ｍ×Ｋ行列、Ｈ２：Ｍ×Ｍ行列で表すと、生成行列ＧＴは、下記式（１４−２）により定義される。
【０２０２】
【数３０】
2005045735.tif 000033
【０２０３】
ただし、生成行列ＧＴを上記式（１４−２）右辺の形とするためには、生成行列Ｇおよび検査行列Ｈの適切な列の入れ替えを必要とする場合がある。その場合、列の入れ替えを行わない検査行列Ｈに対して上記式（１４−１）を満たす（転置後の）生成行列ＧＴは上記式（１４−２）右辺に対して行の入れ替えを施したものとなる。
【０２０４】
次に、送信者はＫビットの２元メッセージ（ｍ０ｍ１・・・ｍＫ−１）に対して、生成行列Ｇを乗算することによりＮビットの符号語（（ｍ０ｍ１・・・ｍＫ−１）Ｇ＝（ｃ０ｃ１・・・ｃＮ−１））を得る。
【０２０５】
そして、ＬＤＰＣ符号化部８１にて得られた符号語は、変調部８２を介して通信路８３へ送出され、受信側で受信信号として受信される。この受信信号が復調部８４にて復調されたのち、ＬＤＰＣ復号部８５にて符号検出がなされる。即ち、上述したように、受信信号から事前確率ｐ０ｎ，ｐ１ｎ、又は事前対数尤度比Ｐｎを求め、これをメッセージｑ０ｍ，ｎ，ｑ１ｍ，ｎ、又はメッセージＱｍ，ｎとして初期化する。そして、上述した手順１’及び手順２’で示される演算を所定の回数か又は上記式（５）に示すパリティチェックを満たすまで繰り返し演算することにより、下記（１５）に示す送信信号の推定値（Ｋビット）を推定結果を得る。更に、この推定結果を硬判定復号し、これを出力するものである。
【０２０６】
【数３１】
2005045735.tif 000034
【０２０７】
このように、本実施の形態における符号検出装置及びこれを備えた通信装置においては、ビットノードの演算は各ビットノード毎に、チェックノードの演算は各チェックノード毎に行っていた従来の演算方法と異なり、チェックノードの演算及びビットノードの演算共に各ビットノード毎に演算を行うようにしたので、ビットノード処理部とチェックノード処理部との間で伝送されるメッセージを格納しておくメモリが極めて簡便な構成となる。
【０２０８】
従来例で示したように、全てのメッセージ計算をパラレルに実行する復号回路は高いスループットが得られるが、スループット要求に余裕がある場合は、メッセージを計算する演算器を複数回利用する構成が回路規模や配線の実現の点で望ましい。このような構成による従来の方法は、メッセージを保存するＲＡＭを複数に分割する必要があったり、マルチプレクサなどの回路が複雑になっていた。即ち、ビットノード処理演算器が書き込むメッセージとチェックノード処理演算器が読み出すメッセージ、及びチェックノード処理演算器が書き込むメッセージとビットノード処理演算器が読み出すメッセージが従来は異なっていたため、メモリを複数バンクに分割する等して回路が複雑化していたのに対し、本実施の形態においては、ビットノード処理演算及びビットノード処理演算のいずれの演算においてもビットノード毎に行なうようにしたので、これらのメッセージを同一アドレスで管理することができ、回路設計を簡略化することができる。
【０２０９】
（４）第２の実施の形態
次に、本発明の第２の実施の形態について説明する。上述の第１の実施の形態においては、Ａｍ、Ｂｍを格納するメモリ６は、チェックノードＸｍの個数分のレジスタを用意し、更新されたチェックノードＸｍに対応するレジスタを選択して更新し、更に所定のレジスタを選択してレジスタからＡｍ、Ｂｍ、を読み出すものであったが、本実施の形態においては、このメモリ６の構成を更に簡略化するものである。なお、その他の構成は図３に示す符号検出装置と同様の構成であり、詳細な説明は省略する。
【０２１０】
（４−１）パリティ検査行列
パリティ検査表列が巡回符号の場合、パリティ検査行列の各列を他の列の巡回シフトとする構成にすることができる。パリティ検査行列第ｎ列の非零要素の行番号をＭ（ｎ）とすると、下記式（１６）としたとき、加算をmod Mの演算として、下記（１７）となるパリティ検査行列を構成することができる。
【０２１１】
【数３２】
2005045735.tif 000035
【０２１２】
【数３３】
2005045735.tif 000036
【０２１３】
図１１は、生成多項式ｘ４+ｘ３+ｘ２+１の（７，３）巡回符号のパリティ検査行列Ｈ２を示す図である。このパリティ検査行列Ｈ２のパリティの数は４であり、７つのパリティ検査方程式のうち３つは冗長なものである。この行列の場合、各列における非零要素数Ｗｃ＝３、行数（パリティ検査方程式）Ｍ＝７であり、下記（１８）となり、各列が巡回シフトの関係になっていることが確かめられる。
【０２１４】
【数３４】
2005045735.tif 000037
【０２１５】
（４−２）チェックノード処理演算器及びＡｍ、Ｂｍを格納するメモリ
このパリティ検査行列に先に示したＬＤＰＣ符号の符号検出装置を適用する場合、上述の第１の実施の形態と同様な構成のチェックノード処理演算器及びＡｍ、Ｂｍを格納するメモリとすると、夫々図１２及び図１３に示すようになる。
【０２１６】
即ち、図１２に示すように、本実施の形態におけるチェックノード処理演算器２０は、図１１に示すパリティ検査行列の各列における非零要素数Ｗｃ＝３と同数の処理部１００〜１０２（以下、１０ｔという。）を有し、各処理部１０ｔには、メモリ４から読み出されたビットノードからチェックノードへのメッセージＱｍ，ｎと、メモリ６から読み出されたＡｍ、Ｂｍが入力され、第１フェーズでは、順次Ａｍ、Ｂｍを更新し、第２フェーズでは、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを出力するための演算を行う。
【０２１７】
そして、上述の図５に示すチェックノード処理演算器１０と同様に、例えば、チェックノード処理演算器２０の処理部１００には、メッセージＱｍ＿ｔ（ｎ），ｎ＝Ｑｍ＿０（ｎ），ｎ、Ａｍ＿ｔ（ｎ）＝Ａｍ＿０（ｎ）、Ｂｍ＿ｔ（ｎ）＝Ｂｍ＿０（ｎ）が入力される。ここで、Ｑｍ＿ｔ（ｎ），ｎ、Ａｍ＿ｔ（ｎ）、Ｂｍ＿ｔ（ｎ）は、ビットノードＹｎからエッジによって接続されたＷｃ個のチェックノードＸｍのうち、ｔ番目のエッジに接続された夫々チェックノードＸｍに対するメッセージ、Ａｍ、Ｂｍを示し、本実施の形態においては、Ｗｃ＝３としているので、ｔ＝０〜２となる。
【０２１８】
このように、本実施の形態においても、チェックノード処理演算器２０は、各ビットノードＹｎ毎に演算を行うため、ビットノードＹｎとエッジにより接続されたチェックノードの個数、即ちＷｃ個の処理部を有し、各処理部にて各ビットノードＹｎの各エッジにて伝搬されるメッセージを処理演算することで、チェックノード処理演算器において、ビットノードに着目した演算を行うようにしたものである。これにより、第１の実施の形態において説明したように、ビットノード処理演算器から出力されるビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎと、チェックノード処理演算器にて使用されるメッセージＱｍ，ｎとは、いずれもメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））、即ち図３２（ｂ）に示すデータＤ１３となる。このことにより、ビットノード処理演算器により書き込みとチェックノード処理演算器による読み出しとが同一アドレスで管理することができるため、これを格納するメモリ４の構成を簡略化することができる。
【０２１９】
また、チェックノード処理演算器において第２フェーズで求めたチェックノードからビットノードへのメッセージＲｍ，ｎが、ビットノード処理演算器に供給され、ビットノード処理演算器では、上述の式（１０）により、次の繰り返し演算における第１フェーズにて使用するためのメッセージＱｍ，ｎを演算してメモリ４に格納することができる。即ち、チェックノード処理演算器から出力されるメッセージＲｍ，ｎは、従来は、図３２（ｂ）に示すように、行方向のデータＤ１１であったのに対し、本実施の形態においては、ビットノード処理演算器が読み出したい列方向のデータＤ１２となり、入力されたデータを使用してそのまま演算することができる。
【０２２０】
また、図１２に示すチェックノード処理演算器２０により更新されたＡｍ、Ｂｍを格納するメモリは、図８に示したメモリ３０と同様に構成することができる。即ち、ビットノードＹｎに関連するチェックノードＸｍ（ｍ∈Ｍ（ｎ））について、Ａｍ、Ｂｍを選択して出力する機能、及びＡｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ）を受け取って新たにＡｍ、Ｂｍとし、保管場所ｍに保存する機能とを有するもとして構成すればよい。
【０２２１】
例えば、図１３に示すように、Ａｍを格納するメモリ２１は、各列における非零要素数Ｗｃ＝３である場合、各カウント値において、３つのＡｍ、Ｂｍが更新されるものであり、上述の図８に示すメモリ２０に対して、マルチプレクサ３８２を付加したものとなっている。即ち、チェックノードＸｍ毎に設けられたマルチプレクサ３６ｍ（３６０〜３６Ｍ−１）及びレジスタ３７ｍ（３７０〜３７Ｍ−１）と、上述のチェックノード処理演算器に供給されるメッセージＱｍ＿ｔ（ｎ），ｎに対応したＡｍ＿ｔ（ｎ）を出力するマルチプレクサ３８ｔ（３８０〜３８Ｗｃ−１）と、これらを制御する制御回路３９とを有する。
【０２２２】
このように、本実施の形態におけるＡｍを格納するメモリは、チェックノードＸｍと同数のレジスタを有し、ビットノードＹｎを順次選択するカウント数回更新されることで、上記式（７−２）に示すＡｍが格納されたものとなる。Ｂｍを格納するメモリに関しても同様の構成とすることができる。
【０２２３】
（４−３）巡回行列の場合のＡｍ、Ｂｍを格納するメモリ
ところで、本実施の形態におけるパリティ検査行列は、上述した如く、巡回行列である。このように、パリティ検査行列が巡回行列である場合、行列の規則性を利用することで上述のＡｍを格納するメモリ２１及びＢｍを格納するメモリを簡単な構成で実現することができる。
【０２２４】
図１４（ａ）は、Ａｍを格納するメモリ４０を示すブロック図、図１４（ｂ）は、メモリ４０の一部を拡大して示すブロック図である。図中においてＡの添え字及びαの第１番目の添え字における加算はmod Mの演算である。本実施の形態においては、パリティ検査行列の構成から、Ａｍを格納するメモリにおいて、Ａｍを読み出す場所Ｗｃ個、書き込む場所Ｗｃ個の相対位置は、全ての列に共通していることから、上述の図７に示したように、Ｍ個からＷｃ個のデータを選択する選択回路（マルチプレクサ３８ｔ）、Ｍ個の保管場所であるレジスタ３７ｍの適切な場所に、Ｗｃ個のデータを保管させる回路（マルチプレクサ３６ｍ）は不要となる。
【０２２５】
即ち、図１４に示すように、本実施の形態におけるＡｍを格納するメモリ４０は、更新された各Ａｍ（Ａｎ〜Ａｎ＋６）を格納するため、チェックノードＸｍ（図１１に示す巡回行列の場合は、Ｍ＝７）と同数設けられたシフトレジスタ４１０〜４１６と、非零要素の位置に対応して設けられたＷｃ個（図１１に示す巡回行列の場合は、Ｗｃ＝３）の選択回路（マルチプレクサ）４２ａ〜４２ｃとから構成することができる。
【０２２６】
選択回路４２ａ〜４２ｃには、制御信号が供給され、繰り返し処理における第１フェーズ又は第２フェーズのうちどちらのフェーズを実行中かによって後述する２つのデータから出力する出力データを切り替える。図１１に示す巡回行列は、非零要素が最初に表れる行を０行目とすると、非零要素が２番目、３番目に表れる行は、＋４行目、＋５行目となっている。そして、図１４（ｂ）に示すように、メモリ４０における選択回路４２ａには、前段のレジスタ４１０に格納されたＡｎ（データＤ２２）と、更新されたＡｍ＝Ａｎ×αｎ，ｎ（データＤ２１）とが入力され、第１フェーズでは、データＤ２１を出力データＤ２３として出力する。同様に、選択回路４２ｂは更新されたＡｍ＝Ａｎ＋４×αｎ＋４，ｎを、選択回路４３ｃは更新されたＡｍ＝Ａｎ＋５×αｎ＋５，ｎを選択して出力する。一方、第２フェーズにおいては、前段のレジスタ４１０に格納されたＡｎ（データＤ２２）を出力データＤ２３として後段のレジスタ４１６に出力する。また、データＤ２２は、第１フェーズ及び第２フェーズ共に、レジスタ４１０〜４１６の内容を巡回する際に出力され、チェックノード処理演算器へ入力される。また、Ｂｍを格納するメモリに関しても同様の回路を実現することができることは勿論である。
【０２２７】
また、図１４に示すメモリ４０は、Ａｍ、Ｂｍを格納するメモリをシフトレジスタで構成するものとしたが、これらはＦＩＦＯでも同様に実現することができる。図１５は、図１４に示すシフトレジスタをＦＩＦＯに置き換えたもの、即ち図１１に示す（７，３）巡回符号の場合にＡｍを格納するメモリをＦＩＦＯで実現した場合の回路構成を示すブロック図である。
【０２２８】
図１５に示すように、メモリ４３は、長さが４のＦＩＦＯ４４０と、長さが１のＦＩＦＯ４４１と、長さが２のＦＩＦＯ４４２とを有し、更に各ＦＩＦＯ４４０〜４４２の出力を更新するための、図１４と同様に動作するマルチプレクサ４２ａ〜４２ｃとを有している。このように、シフトレジスタをＦＩＦＯに置き換えて構成してもよい。また、Ｂｍを格納するメモリについても同様にＦＩＦＯを利用して構成することができる。
【０２２９】
本実施の形態においても、第１の実施の形態と同様の効果を奏する。即ち、メッセージを格納するメモリの構成等を簡単にすることができる。更に、本実施の形態においては、行列の規則性を利用することにより、レジスタ４１０〜４１６の内容を巡回シフトさせるか、又はＦＩＦＯ４４０〜４４２を使用することによって、図１３に示すメモリ２１と同等の機能を実現することができるため、回路構成を更に簡単化することができる。
【０２３０】
（５）第３の実施の形態
次に、本発明の第３の実施の形態について説明する。上述の第２の実施の形態においては、巡回符号の規則性を利用してメモリの構成を簡略化するものであったが、本実施の形態においては、第２の実施の形態とは異なる検査行列の規則性を利用してメモリの構成の簡略化、演算のスループットの向上を図るものである。
【０２３１】
（５−１）パリティ検査行列
先ず、本実施の形態にて使用するパリティ検査行列について説明する。線形符号Ｃのうち、任意の符号語ｗ（Ｃの要素）をｐだけ巡回置換したものがまたＣに属するものを準巡回符号（Quasi-Cyclic Code：ＱＣ符号）と呼ぶ。ＱＣ符号のなかでもｐ＝１を満たすものは巡回符号である。上述の図１に示すパリティ検査行列は、ｐ＝３のＱＣ符号であり、例えば１乃至３列目の１行目の要素（１，１，０）は、４乃至６列目の２行目の要素（１，１，０）となっている。
【０２３２】
ＱＣ符号の場合、パリティ検査行列の列をｐずつ区切り、それぞれを組として見たとき、各組を他の組の巡回シフトとする構成にすることができる。パリティ検査行列第ｎ列の非零要素の行番号Ｍ（ｎ）を下記（１９）としたとき、加算をmod Mの演算として、下記（２０）となるパリティ検査行列を構成することができる。
【０２３３】
【数３５】
2005045735.tif 000038
【０２３４】
【数３６】
2005045735.tif 000039
【０２３５】
このようなパリティ検査行列に、ＬＤＰＣ符号の符号検出装置を適用する場合には、ｐ列１組の演算をパラレルに行う構成とすれば、巡回符号の場合と同様に行列の規則性を利用することでＡｍ、Ｂｍを格納するメモリを簡単に実現することができる。
【０２３６】
（５−２）符号検査装置
ｐ列１組の演算をパラレルに行う構成の場合も、基本的な回路構成は、上述の図３に示す第１の実施の形態の符号検査装置と同様であるが、各ブロックの動作が第１の実施の形態とは異なる。図１６は、本第３の実施の形態における符号検査装置を示すブロック図である。
【０２３７】
本実施の形態における符号検出装置５１は、カウンタ５２、事前値（事前対数尤度比）Ｐｎを格納するメモリ５３、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ５４と、ビットノードＹｎに着目したチェックノードの演算を行うチェックノード処理演算器５５と、Ａｍ、Ｂｍを格納するメモリ５６と、ビットノードの演算を行うビットノード処理演算器５７とを有する。
【０２３８】
カウンタ５２は、着目しているビットノードＹｎのｐ個１組の番号をカウント値により示す。第１フェーズ、第２フェーズの夫々において、０〜（Ｎ／ｐ）−１の値をカウントする。
【０２３９】
事前値Ｐｎを格納するメモリ５３は、入力された事前値ＰｎをビットノードＹｎのｐ個１組の番号のアドレスに格納する。また、カウンタ５２のカウント値ｃに応じて、下記（２１）で示される事前値Ｐｎを出力する。
【０２４０】
【数３７】
2005045735.tif 000040
【０２４１】
ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ５４は、１つのアドレスｃで、下記（２２）に示すビットノードＹｎの夫々から出るすべてのメッセージＱｍ，ｎが同時にアクセスできる構成とする。第１フェーズでは読み出し時のみ、第２フェーズでは書き込み、読み出し共に行う。
【０２４２】
【数３８】
2005045735.tif 000041
【０２４３】
チェックノード処理演算器５５は、上記（２２）に示すビットノードＹｎの夫々に対応したメッセージＱｍ，ｎを読み出し、αｍ，ｎ、ｆ（βｍ，ｎ）を計算する。第１フェーズでは下記（２３）に示すビットノードＸｍに関して各々Ａｍ、Ｂｍを入力として受け取り、下記（２４）、（２５）を計算して出力し、メモリ５６に格納されているＡｍ、Ｂｍを更新する。
【０２４４】
【数３９】
2005045735.tif 000042
【０２４５】
【数４０】
2005045735.tif 000043
【０２４６】
【数４１】
2005045735.tif 000044
【０２４７】
第２フェーズではＡｍ、Ｂｍをメモリ５６から入力として受け取り、また、上記（２２）に示すビットノードＹｎの夫々に対応したメッセージＱｍ，ｎを再び読み出し下記式（２６）で示すＲｍ，ｎを出力する。
【０２４８】
【数４２】
2005045735.tif 000045
【０２４９】
Ａｍ、Ｂｍを格納するメモリ５６は、第１フェーズでは、Ａｍ、Ｂｍを逐次求めるモードとして動作する。最初にすべてのビットノードＹｎに関してＡｍ＝１，Ｂｍ＝０に初期化を行う。次に、上記（２２）に示すビットノードＹｎの夫々に関連する上記（２３）に示すチェックノードＸｍについて、現在途中まで求まっているＡｍ、Ｂｍを出力し、チェックノード処理演算器で求まった上記（２４）及び（２５）に示す値を受け取り、これをＡｍ、Ｂｍとして更新する。第１フェーズの処理が終了すると手順１'の式で表された上記式（７−２）及び（７−３）で示すＡｍ、Ｂｍが求まる。
【０２５０】
第２フェーズでは、ビットノードＹｎに関連する上記（２３）に示すチェックノードＸｍについて、第１フェーズにて求められたＡｍ、Ｂｍを出力する。
【０２５１】
ビットノード処理演算器５７は、第２フェーズでのみ動作する。上記（２２）に示すビットノードＹｎの夫々に送られるメッセージＲｍ，ｎをチェックノード処理演算器５５から受け取り、事前値Ｐｎをメモリ５３から受け取り、上記式（２７）で示される事後値Ｑｎ又は硬判定結果ｃｎ＾、及びチェックノードＸｍへのメッセージＱｍ，ｎ＝Ｑｎ−Ｒｍ，ｎを出力する。
【０２５２】
【数４３】
2005045735.tif 000046
【０２５３】
また、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ５４は、列方向の非零要素数がＷｃのレギュラーＬＤＰＣ符号の場合、Ｑｍ，ｎを表現するビット数をｑとすると、第１の実施の形態と同様、ビットノード処理演算器５７による書き込みとチェックノード処理演算器５５による読み出しアドレスが同一なため、（Ｗｃ×ｑ×ｐ）ビット、Ｎ／ｐワードのＲＡＭで実現することができる。
【０２５４】
（５−３）Ａｍ、Ｂｍを格納するメモリの構成
次に、Ａｍ、Ｂｍを格納するメモリ５６について詳細に説明する。上述したように、図１に示すパリティ検査行列は、ｐ＝３である（２１，１５）ＱＣ符号（符号長２１、情報記号数１５）のパリティ検査行列となっている。この図１に示す行列の場合、各列の非零要素数Ｗｃ＝２、行数（パリティ検査方程式）Ｍ＝７であり、パリティ検査行列第ｎ列の非零要素の行番号Ｍ（ｎ）は下記（２８）のようになり、３列ずつの各組が巡回シフトの関係になっている。
【０２５５】
【数４４】
2005045735.tif 000047
【０２５６】
この図１に示すパリティ検査行列にＬＤＰＣ符号の符号検出装置を適用する場合、巡回符号の場合と同様に、Ａｍを格納するメモリを図１７のように構成することができる。即ち、図１７に示すように、３列の非零要素数は６であり、チェックノードの数は７であるので、７つのレジスタ６１０〜６１６と、６つのαｍ，ｎによりＡｍを更新するマルチプレクサ６２ａ〜６２ｅとを有する。図１７において、Ａの添え字及びαの第１番目の添え字における加算はmod Mの演算である。
【０２５７】
ここで、マルチプレクサ６２ａに入力される更新されたＡｍは、Ａｉ×αｉ，３ｉ×αｉ，３ｉ＋１である。これは、図１に示すパリティ検査行列において、例えば０列及び１列目において、０行目が共に非零要素となっているため、１回の処理で２つのメッセージＱｍ，ｎが入力され、従って、２つのαｍ，ｎが入力されるためであり、従ってマルチプレクサが非零要素数より１つ少なくなっている。
【０２５８】
このように、本実施の形態においても第１の実施の形態と同様の効果を奏すると共に、行列の規則性を利用することにより、第１の実施の形態における任意のパリティ検査行列に対するＡｍ、Ｂｍを格納可能なメモリに比較して、回路構成が更に簡単となる。また、第２の実施の形態においては、１つずつのビットノードを順に処理する構成であったのに対し、本実施の形態においては、３つずつのビットノードの処理をまとめて行うことにより、スループットを容易に向上することができる。また、Ｂｍを格納するメモリに関しても同様に構成でき、更にシフトレジスタの代わりにＦＩＦＯを使用したものとしてもよい。
【０２５９】
（６）第４の実施の形態
次に、本発明の第４の実施の形態について説明する。第３の実施の形態におけるＱＣ符号のＬＤＰＣ符号の符号検出装置は、ＱＣ符号の複数組の演算をパラレル処理することが可能である。本実施の形態においては、ＱＣ符号の複数組の演算をパラレル処理することにより更にスループットを向上したものである。
【０２６０】
（６−１）パリティ検査行列
ＱＣ符号のパラメータをｐ（巡回符号の場合はｐ＝１として考える）、処理のパラレルの度合いをｓとすれば、符号検出装置の回路構成は、図１６と同様となり、各ブロックの動作は、第３の実施の形態において説明したＱＣ符号の場合の「ｐ」を「ｐ×ｓ」としたものとすることができる。
【０２６１】
ここで、符号検出装置の回路構成は、図１６とほぼ同様のものとなるが、Ａｍ、Ｂｍを格納するメモリに関しては、その構成が異なり、各Ａｍ、Ｂｍを保存するレジスタの内容をｓ個間隔で巡回シフトさせる構造とすることで実現することができる。
【０２６２】
また、ビットノードＹｎからチェックノードＸｍへのメッセージを格納するメモリは、列方向の非零要素数がＷｃのレギュラーＬＤＰＣ符号の場合、Ｑｍ，ｎを表現するビット数をｑとすると、（Ｗｃ×ｑ×ｐ×ｓ）ビット、Ｎ／（ｐ×ｓ）ワードのＲＡＭで実現することができる。
【０２６３】
図１８は、生成多項式ｘ４+ｘ３＋ｘ＋１の（６，２）巡回符号のパリティ検査行列Ｈ３を示す。この行列Ｈ３の場合、各列における非零要素数Ｗｃ＝３、行数（パリティ検査方程式）Ｍ＝６であり、パリティ検査行列第ｎ列の非零要素の行番号Ｍ（ｎ）は下記（２９）となり、各列が巡回シフトの関係になっていることが確かめられる。
【０２６４】
【数４５】
2005045735.tif 000048
【０２６５】
（６−２）Ａｍ、Ｂｍを格納するメモリ
このパリティ検査行列Ｈ３にパラレル度ｓ＝２のＬＤＰＣ符号の符号検出装置を適用する場合のＡｍを格納するメモリを図１９に示す。図中においてＡの添え字及びαの第１番目の添え字における加算はmod Mの演算である。各Ａｍを保存するレジスタの内容をｓ＝２個間隔で巡回シフトさせることによって機能を実現している。即ち、第３の実施の形態においては、行列の巡回構造を利用して、シフトレジスタを巡回シフトさせるものであったが、本実施の形態においては、２列同時に処理することでスループットを向上するものである。
【０２６６】
図１９に示すように、例えば偶数行目及び奇数行目に対応した夫々レジスタ６３０、６３２、６３４及び６３１、６３３、６３５と、夫々マルチプレクサ６４ａ、６４ｂ及び６４ｃ、６４ｄとを備えることで、２つ分のビットノードＹｎに接続された全てのチェックノードＸｍに対応したＡｍを一度に更新することができる。なお、パラレル度ｓに伴い、メモリからメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を読み出す個数及びこれを処理するチェックノード処理演算器における各処理部も増やすものとする。
【０２６７】
また、パラレル度ｓを上げれば、回路が大型化するものの、より高いスループットを得ることができる。また、Ｂｍを格納するメモリに関しても同様に構成することができ、シフトレジスタの代わりにＦＩＦＯを使用してもよいことは勿論である。
【０２６８】
（７）第５の実施の形態
次に、本発明の第５の実施の形態について説明する。本実施の形態においては、第１フェーズ及び第２フェーズの処理を同時に行うことにより、第１フェーズの次に第２フェーズの処理を行う例えば第１の実施の形態に比してスループットを約２倍に向上させたものである。
【０２６９】
上述の第１乃至第４の実施の形態においては、ＬＤＰＣ符号の符号検出装置は、図３又は図１６に示したような構成である。即ち、繰り返し処理の１回の動作は２つのフェーズにより実行される。このような構成に対して、Ａｍ、Ｂｍを格納するメモリを二重化し、チェックノード処理演算器を第１フェーズ、第２フェーズのそれぞれに対応した動作が独立に行えるように回路を多重化することにより、連続した繰り返し処理において、２つのフェーズの処理をオーバーラップさせることができる。つまり、Ａｍ、Ｂｍを格納するメモリ及びチェックノード処理演算器を多重化することにより、着目しているビットノードＹｎに関して、ｉ回目の繰り返しの第２フェーズにおける処理の後に続けて（ｉ＋１）回目の繰り返しの第１フェーズにおける処理を実行することができ、これら２つのフェーズを時間的にオーバーラップさせることができる。
【０２７０】
（７−１）符号検出装置
図２０は、本実施の形態における符号検出装置を示すブロック図である。図２０に示すように、着目しているビットノードＹｎの番号（０〜Ｎ−１番目）を表すカウンタ７２と、事前値（事前対数尤度比）Ｐｎを格納するメモリ７３と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ７４と、着目するビットノードＹｎをカウント値に合わせて変化させながらチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎを算出する演算を行うチェックノード処理演算器７５と、上記（７−２）及び（７−３）に示すＡｍ、Ｂｍを格納するメモリ７６と、ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ等を算出するビットノード処理演算器７７とを有する。
【０２７１】
ここで、チェックノード処理演算器７５は、第１フェーズの演算を行う第１フェーズ用処理演算器７５ａと、第２フェーズの演算を行う第２フェーズ用処理演算器７５ｂとを有する。また、Ａｍ、Ｂｍを格納するメモリ７６は、第１フェーズにより更新されていくＡｍ、Ｂｍを格納するため、又は第１フェーズにて求められたＡｍ、Ｂｍを第２フェーズで出力するための第１のメモリ７６ａ及び第２のメモリ７６ｂと、第１のメモリ７６ａ及び第２のメモリ７６ｂの出力を第１フェーズ用処理演算器７５ａ又は第２フェーズ用処理演算器７５ｂに振り分けるための選択回路７６ｃとを有する。
【０２７２】
次に、本符号検出装置７０の各ブロックにおける動作について説明する。カウンタ７２は、着目しているビットノードＹｎの番号を表し、０からＮ−１の値をカウントするＮ進カウンタである。１回の繰り返し処理の間に、カウンタ７２は２周するが、ｉ回目の繰り返し処理の第２フェーズと、（ｉ＋１）回目の繰り返し処理の第１フェーズとは処理が時間的にオーバーラップする。
【０２７３】
事前値（事前対数尤度比）Ｐｎを格納するメモリ７３は、入力された事前値ＰｎをビットノードＹｎの番号ｎのアドレスに格納し、カウンタの値ｎに応じて事前値Ｐｎを出力する。
【０２７４】
ビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを格納するメモリ７４は、１つのアドレスでビットノードＹｎから出るすべてのメッセージ、即ちＱｍ，ｎ（ｍ∈Ｍ（ｎ））に含まれるメッセージに同時にアクセスできる構成とする。
【０２７５】
また、第１フェーズ用チェックノード処理演算器７５ａは、ビットノード処理演算器７７から出力されるメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取り、αｍ，ｎ、ｆ（βｍ，ｎ）を計算する。そして、ビットノードＹｎに接続されたチェックノードＸｍ（ｍ∈Ｍ（ｎ））に関して各々Ａｍ、Ｂｍを、例えば第１のメモリ７６ａから受け取り、Ａｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ）を計算して出力し、演算したＡｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ）を第１のメモリ７６ａに書き込む。
【０２７６】
第２フェーズ用チェックノード処理演算器７５ｂは、ビットノードＹｎに対応したメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を読み出し、αｍ，ｎ、ｆ（βｍ，ｎ）を計算する。そして、チェックノードＸｍ（ｍ∈Ｍ（ｎ））に関して例えば第２のメモリ７６ｂから各々Ａｍ、Ｂｍを入力として受け取り、Ｒｍ，ｎ＝（Ａｍ／αｍ，ｎ）ｆ（Ｂｍ−ｆ（βｍ，ｎ））を出力する。
【０２７７】
Ａｍ、Ｂｍを格納するメモリ７６は、第１フェーズにおいては、Ａｍ、Ｂｍを逐次更新するモードとして動作する。最初にすべてのチェックノードＸｍに関してＡｍ＝１，Ｂｍ＝０に初期化を行う。ビットノードＹｎに関連するチェックノードＸｍ（ｍ∈Ｍ（ｎ））について、現在途中まで求まっているＡｍ、Ｂｍを出力し、Ａｍ×αｍ，ｎ，Ｂｍ＋ｆ（βｍ，ｎ）を受け取ってＡｍ、Ｂｍとして更新する。第１フェーズの終わりには手順１'の式（７−２）及び（７−３）で示されるＡｍ、Ｂｍが求まる。また、第２フェーズにおいては、ビットノードＹｎに関連するチェックノードＸｍ（ｍ∈Ｍ（ｎ））について、Ａｍ、Ｂｍを出力する。
【０２７８】
図２１は、Ａｍ、Ｂｍを格納するメモリ７６が処理するデータをタイミングチャートに示した図である。図２１に示すように、第１のメモリ７６ａ、第２のメモリ７６ｂは、互いに異なるフェーズで動作する。つまり、第１のメモリ７６ａが第１フェーズで動作しているときには、第２のメモリ７６ｂは第２フェーズで動作し、第１のメモリ７６ａが第２フェーズで動作しているときには、第２のメモリ７６ｂは第１フェーズで動作する。（ｉ＋１）回目の第１のフェーズは、ｉ回目の第２のフェーズの結果を使用して行われる。
【０２７９】
選択回路７６ｃは、第１のメモリ７６ａ及び第２のメモリ７６ｂのうち、第１フェーズで動作している一方のメモリの出力を第１フェーズ用チェックノード処理演算器７５ａへ、第１のメモリ７６ａ及び第２のメモリ７６ｂのうち、第２フェーズで動作している他方のメモリの出力を第２フェーズ用チェックノード処理演算器７５ｂへ振り分ける。
【０２８０】
ビットノード処理演算器７７は、ビットノードＹｎに入るメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））と事前値Ｐｎを受け取り、上記式（９）で示す事後値Ｑｎ、又は硬判定結果、及び上記式（１０）に示すチェックノードＸｍへのメッセージＱｍ，ｎ＝Ｑｎ−Ｒｍ，ｎを出力する。
【０２８１】
ここで、メモリ７４にｉ回目の繰り返し演算処理の第２フェーズにより求められたＱｍ，ｎ（ｍ∈Ｍ（ｎ））が保存されているとする。このとき、第１のメモリ７６ａには、（ｉ＋２）回目の繰り返し演算処理の第１フェーズ用の、逐次更新されるＡｍ，Ｂｍを格納するメモリとなり、第２のメモリ７６ｂは、（ｉ＋１）回目の繰り返し演算処理の第２フェーズで使用される更新済みのＡｍ，Ｂｍを格納するメモリとなっているものとする。
【０２８２】
この場合、第２フェーズ用チェックノード処理演算器７５ｂは、（ｉ＋１）回目の繰り返し演算処理の第２フェーズの処理を実行する。即ち、メモリ７４の着目しているビットノードＹｎの番号に対応したアドレスｎから、ｉ回目の繰り返し演算処理の第２フェーズの演算結果（データＤ３１）としてのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を読み出し、例えば第２のメモリ７６ｂに格納されている、（ｉ＋１）回目の繰り返し演算処理の第１フェーズにより更新終了したＡｍ、Ｂｍを用いてチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を求める。続けてビットノード処理演算器７７はメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を受け取りビットノードＹｎからチェックノードＸｍへの（ｉ＋１）回目の繰り返し演算処理結果（データＤ３２）としてのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を求めて、メモリ７４のアドレスｎに格納すると同時に、この値（データＤ３２）を第１フェーズ用チェックノード処理演算器７５ａに送り、（ｉ＋２）回目の繰り返し演算処理の第１フェーズの処理を行い、例えば第１のメモリ７６ａのＡｍ、Ｂｍを更新しておく。以上の操作を、カウンタのカウント値に合わせて、着目するビットノード番号を変化させながら行う。
【０２８３】
（７−２）符号検出方法
次に、本実施の形態の符号検出方法について説明する。図２２（ａ）は、本実施の形態の符号検出方法を示すフローチャート、図２２（ｂ）は、図２２（ａ）の処理に対応する擬似的なプログラムコードを示す図である。
【０２８４】
図２２（ａ）及び（ｂ）に示すように、先ずビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎを、例えば受信するか又は読み出したデータ（以下、受信語という。）に基く値Ｐｎにより初期化する。そして、このメッセージＱｍ，ｎに基づき第１フェーズの演算が行われる。即ち、先ず、全てのＡｍ，ＢｍがＡｍ＝１、Ｂｍ＝０に初期化され、次いでチェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するためのＡｍ、Ｂｍの更新が行なわれる。Ａｍ、Ｂｍの更新は、図９に示した第１の実施の形態と同様であり、最後のビットノードＹＮ−１からのメッセージによるＡｍ、Ｂｍの更新が終了した時点で、上記（７−２）、（７−３）に示すＡｍ、Ｂｍが求まる。（ステップＳ１１、ＳＰ１１）。
【０２８５】
次に、チェックノード処理演算器にて第２フェーズの演算が行われると共に、ビットノード処理演算器にてメッセージＱｍ，ｎが求められ、続いてチェックノード処理演算器にて次の繰り返しの第１フェーズの処理が行われる（ステップＳ１２、ＳＰ１２）。即ち、第２フェーズ用処理演算器７５ｂでは、繰り返し演算処理（ｉ＋１）回目における更新済みのＡｍ、Ｂｍ（以下、Ａｍ’、Ｂｍ’という。）と、前のステップ（１回目はＳ１１、２回目以降はＳ１２）で得られた繰り返し処理ｉ回目におけるビットノードＹｎからチェックノードＸｍへのメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））により、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））が算出される。この値を用いてビットノード処理演算器において、ビットノードＹｎからチェックノードＸｍへの繰り返し演算処理（ｉ＋１）回目におけるメッセージＱｍ，ｎが算出される。
【０２８６】
また、第１フェーズ用処理演算器７５ａにおいては、全てのＡｍ，ＢｍがＡｍ＝１、Ｂｍ＝０に初期化され、次いで上述の繰り返し演算処理（ｉ＋１）回目におけるメッセージＱｍ，ｎを使用して、チェックノードＸｍからビットノードＹｎへのメッセージＲｍ，ｎ（ｍ∈Ｍ（ｎ））を算出するための、繰り返し演算処理（ｉ＋２）回目におけるＡｍ、Ｂｍの更新が行なわれる。
【０２８７】
ここで、図２０に示すチェックノード処理演算器７５の第２フェーズ用処理演算器７５ｂがメモリ７４から読み出すデータＤ３１は、前のステップ（１回目はＳ１１、２回目以降はＳ１２）にて得られたメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））であり、第１フェーズ用処理演算器７５ｂに入力されるデータＤ３２は、同じステップＳ１２中にて算出されるＱｍ，ｎ（ｍ∈Ｍ（ｎ））である。即ち、メモリ７４は、データＤ３１が第２フェーズ用処理演算器７５ｂにて読み出されると直ぐ、ビットノード処理演算器７７によりデータＤ３２が書き込まれる。
【０２８８】
そして、以上のステップＳ１２の繰り返し回数が規定の回数に達したか否かが判定され（ステップＳ１３）、規定の繰り返し回数に達していない場合は、ステップＳ１２の処理を繰り返し、規定の繰り返し回数に達している場合は、硬判定復号が行われ、その結果が出力される（ステップＳ１４）。また、ステップＳ１２において、事後値Ｑｎの硬判定結果がチェックを満たしているか否かを検出し、繰り返し処理を中止してステップＳ１４の硬判定復号を行うようにしてもよい。
【０２８９】
本実施の形態においては、第１の実施の形態と同様の効果を奏すると共に、チェックノード処理演算器及びメモリ７６を多重化することにより、第１の実施の形態に比して回路規模は若干大きくなるものの、ほぼ２倍の処理速度を得ることができ、スループットを向上することができ。また、本実施の形態においても、上述した如く、チェックノード処理演算器におけるαｍ，ｎ、ｆ（βｍ，ｎ）の演算をビットノード処理演算器で行って、ビットノードＹｎからチェックノードＸｍへのメッセージを格納するメモリにはαｍ，ｎ、ｆ（βｍ，ｎ）を保存する構成としてもよい。この場合、第１フェーズ用チェックノード処理演算器７５ａと第２フェーズ用チェックノード処理演算器７５ｂとで重複していたαｍ，ｎ、ｆ（βｍ，ｎ）の計算をビットノード処理演算器の１箇所で行うことができる。
【０２９０】
（７−３）復号装置
更に、図２０に示すＬＤＰＣ符号の符号検出装置７０からの硬判定結果から情報語を推定して出力する硬判定復号装置７８とを組み合わせることで、図２３に示すＬＤＰＣ符号の復号装置７９を実現することができる。特に、ＬＤＰＣ符号が組織符号である場合、硬判定復号装置７８は、パリティ部を除去する装置となる。また、本実施の形態に限らず、上述の第１乃至第４の実施の形態においても、同様に復号装置を構成することができる。
【０２９１】
本復号装置においても、第１の実施の形態と同様の効果を奏し、ビットノードから出力されるメッセージとチェックノードが読み出すメッセージとは同一のアドレスで管理することができるため装置の回路構成が簡略化すると共に、図２０に示す符号検出装置と組み合わせることで高スループットの復号装置を得ることができる。
【０２９２】
また、ＱＣ符号（巡回符号を含む）の場合や、ＱＣ符号の複数組の演算をパラレル処理する場合においても、本実施の形態と同様の構成、即ち、Ａｍ、Ｂｍを格納するメモリ、及びチェックノード処理演算器を多重化することによりスループットを向上することが可能である。
【０２９３】
（８）変形例
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。例えば、以上説明した第１乃至第５の実施の形態における符号検出装置や復号装置を利用したストレージ（記憶装置）、記録再生を行う情報処理装置、送受信装置等に適用することができる。
【０２９４】
図２４及び図２５は、本実施の形態における符号検出装置（復号装置）を備える記録再生装置を示すブロック図である。図２４に示すように、記録再生装置８６は、音楽又は映像等のメッセージに上記式（１４−２）に示す生成行列Ｇを乗算してＬＤＰＣ符号を生成するＬＤＰＣ符号化部８１と、生成されたＬＤＰＣ符号をチャネル符号化する符号化部８７と、チャネル符号化されたデータを記録し、記録された符号を読み出す記録／再生部８８と、読み出したデータからチャネルを検出し、チャネル毎に復号するチャネル復号部８９と、チャネル毎に復号されたデータから符号検出するＬＰＤＣ復号部８５とを有する。ＬＰＤＣ復号部８５にて符号検出されたデータは、メッセージに復号される。
【０２９５】
また、図２５に示す他の記録再生装置９０は、音楽又は映像等のメッセージをチャネル符号化する符号化部９１と、チャネル符号化された符号語に対するＬＤＰＣパリティを生成するパリティ生成部９２と、チャネル符号化部９１にパリティ生成部９２が生成したＬＤＰＣパリティを挿入した符号語を生成するパリティ挿入部９３と、パリティが挿入された符号語を記録し、記録された符号語を読み出す記録／再生部９４と、読み出した符号語からチャネルを検出するチャネル検出部９５と、チャネル毎のデータに対して符号検出するＬＰＤＣ復号部９６と、ＬＰＤＣ復号部９６にて符号検出されたデータからパリティを除去するパリティ除去部９７と、パリティが除去されたチャネル毎の符号を復号するチャネル復号部９８とを有する。
【０２９６】
このように、本実施の形態における符号検出装置は、通信路を介して送受信されるようなデータの雑音の影響を除去するような受信装置の他、記録再生時の書き込みエラーや、読み出しの際の信号の訛り等による誤りを訂正する各種記録再生装置等に適用することができ、このことにより、各種装置の回路構成を簡略化することができ、各種装置を小型化し、生産性を向上することができる。
【図面の簡単な説明】
【０２９７】
【図１】２元（binary）ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図２】図１に示すパリティ検査行列に対応した２部グラフ示す図である。
【図３】本発明の第１の実施の形態における符号検出装置を示すブロック図である。
【図４】本発明の第１の実施の形態におけるチェックノード処理演算器とビットノード処理演算器との間でやり取りされるデータの流れを示す図である。
【図５】本発明の第１の実施の形態におけるチェックノード処理演算器の一具体例を示す回路図である。
【図６】図１に示すパリティ検査行列（各列の非零要素数Ｗｃ＝２）を有する受信号の符号を検出する場合の、各時刻（カウント値）毎にビットノードＹｎからチェックノードに渡されるメッセージＱｍ，ｎ（ｍ∈Ｍ（ｎ））を説明するための２部グラフを示す図である。
【図７】本発明の第１の実施の形態の符号検出装置におけるＡｍを格納するメモリを示すブロック図である。
【図８】図７に示すＡｍを格納するメモリの更に具体的な構成を示すブロック図である。
【図９】（ａ）は、本発明の第１の実施の形態における符号検出方法を示すフローチャートであり、（ｂ）は、各処理工程を擬似的に示すプログラムコードを示す図である。
【図１０】本発明の第１の実施の形態における通信装置を示すブロック図である。
【図１１】生成多項式ｘ４+ｘ３+ｘ２+１の（７，３）巡回符号のパリティ検査行列Ｈ２を示す図である。
【図１２】図１１に示すパリティ検査行列を有するＬＤＰＣ符号の符号検出装置におけるチェックノード処理演算器を示す回路図である。
【図１３】図１１に示すパリティ検査行列を有するＬＤＰＣ符号の符号検出装置におけるＡｍ、Ｂｍを格納するメモリを示すブロック図である。
【図１４】図１３に示すメモリとは異なる構成を示すものであって、（ａ）は、Ａｍを格納するメモリ４０を示すブロック図、（ｂ）は、メモリ４０の一部を拡大して示すブロック図である。
【図１５】図１１に示すパリティ検査行列を有するＬＤＰＣ符号の符号検出装置におけるＡｍ、Ｂｍを格納するメモリをＦＩＦＯで実現した場合の回路を示すブロック図である。
【図１６】本発明の第３の実施の形態における符号検査装置を示すブロック図である。
【図１７】図１に示すパリティ検査行列を有するＬＤＰＣ符号の符号検出装置におけるＡｍを格納するメモリを示すブロック図である。
【図１８】生成多項式ｘ４+ｘ３+ｘ+１の（６，２）巡回符号のパリティ検査行列Ｈ３を示す図である。
【図１９】図１８に示すパリティ検査行列にパラレル度ｓ＝２のＬＤＰＣ符号の符号検出装置を適用する場合のＡｍを格納するメモリを示すブロック図である。
【図２０】図２０は、本発明の第５の実施の形態における符号検出装置を示すブロック図である。
【図２１】本発明の第５の実施の形態における符号検出装置において、Ａｍ、Ｂｍを格納するメモリ７６が処理するデータをタイミングチャートに示した図である。
【図２２】（ａ）は、本発明の第５の実施の形態における符号検出方法を示すフローチャート、（ｂ）は、（ａ）の処理に対応する擬似的なプログラムコードを示す図である。
【図２３】本発明の第５の実施の形態における符号検出装置を備える復号装置を示すブロック図である。
【図２４】本発明の実施の形態における符号検出装置を備える情報処理装置を示すブロック図である。
【図２５】本発明の実施の形態における符号検出装置を備える情報処理装置の他の例を示すブロック図である。
【図２６】従来のエッジで接続されたチェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させる繰り返し復号方法（メッセージパッシングアルゴリズム）を示すフローチャートである。
【図２７】従来のエッジで接続されたチェックノードＸｍとビットノードＹｎとのノード間にメッセージを伝搬させる繰り返し復号方法（メッセージパッシングアルゴリズム）であって、対数尤度比を用いた場合の復号方法を示すフローチャートである。
【図２８】非特許文献３に対応した復号装置を示すブロック図である。
【図２９】非特許文献４に対応した復号装置を示すブロック図である。
【図３０】非特許文献５に対応した復号装置を示すブロック図である。
【図３１】従来のメッセージパッシングアルゴリズムにおいて、手順１及び手順２を行う要部を模式的に示すブロック図である。
【図３２】（ａ）及び（ｂ）は、図１に示すパリティ検査行列を使用した復号装置において、夫々メッセージＱｍ，ｎを格納するＲＡＭ及びメッセージＲｍ，ｎを格納するＲＡＭのアドレスを模式的に示す図である。
【符号の説明】
【０２９８】
１，５１  符号検出装置、２，５２，７２  カウンタ、３，４，６，４０，４３，５４，７３，７４，７５，１０３，１０６，１０８，１１３，１１８ｋ-1，１１９ｋ-１  メモリ、５，１０，５５，７５，１０５，１１５ｋ-1  チェックノード処理演算器、７，５７，７７，１０４，１１４ｋ-1  ビットノード処理演算器、１０ｔ  処理部、３１  更新回路、３２０〜３２６  保管場所、３３，４２ａ〜４２ｃ  選択回路、３４，３９  制御部、３８ｔ，３６ｍ，４２ａ〜４２ｃ，６２ａ〜６２ｅ  マルチプレクサ、３７ｍ，６１０〜６１６  レジスタ、４１０〜４１６  シフトレジスタ、４４０〜４４２  ＦＩＦＯ、８０  通信装置、８１  ＬＰＤＣ符号化部、８２  変調部、８３  通信路、８４  復調部、５  ＬＤＰＣ復号部、８６  記録再生装置、８７  チャネル符号化部、８８  記録／再生部、８９  チャネル復号部、９０  記録再生装置、９１  チャネル符号化部、９２  パリティ生成部、９３  パリティ挿入部、９４  記録／再生部、９５  チャネル検出部、９６  ＬＰＤＣ復号部、９７  パリティ除去部、９８  チャネル復号部、１０１，１１０，１２０  復号装置、１０７  硬判定復号器、１２１０〜１２１ｋ-1  演算部Ｘｍ  チェックノード、Ｙｎ  ビットノード
【図１】
2005045735.tif 000049
【図２】
2005045735.tif 000050
【図３】
2005045735.tif 000051
【図４】
2005045735.tif 000052
【図５】
2005045735.tif 000053
【図６】
2005045735.tif 000054
【図７】
2005045735.tif 000055
【図８】
2005045735.tif 000056
【図９】
2005045735.tif 000057
【図１０】
2005045735.tif 000058
【図１１】
2005045735.tif 000059
【図１２】
2005045735.tif 000060
【図１３】
2005045735.tif 000061
【図１４】
2005045735.tif 000062
【図１５】
2005045735.tif 000063
【図１６】
2005045735.tif 000064
【図１７】
2005045735.tif 000065
【図１８】
2005045735.tif 000066
【図１９】
2005045735.tif 000067
【図２０】
2005045735.tif 000068
【図２１】
2005045735.tif 000069
【図２２】
2005045735.tif 000070
【図２３】
2005045735.tif 000071
【図２４】
2005045735.tif 000072
【図２５】
2005045735.tif 000073
【図２６】
2005045735.tif 000074
【図２７】
2005045735.tif 000075
【図２８】
2005045735.tif 000076
【図２９】
2005045735.tif 000077
【図３０】
2005045735.tif 000078
【図３１】
2005045735.tif 000079
【図３２】
2005045735.tif 000080