ＬＤＰＣ符号検出装置及びＬＤＰＣ符号検出方法
【課題】復号が収斂するための繰り返し回数が少なく復号特性に優れたＬＤＰＣ符号検出技術を提供する。
【解決手段】すべての検査ノードについて、検査ノード選択手段７が優先度の高い順に順次選択する。検査ノード演算手段８は、選択された検査ノードについて、信頼度βに基づき、当該検査ノードに接続する各ビットノードに向け伝搬する信頼度αを算出し伝搬する。優先度更新手段９は、信頼度βに基づき信頼度が大きい順に検査ノードの優先度を決定し優先度を更新する。ビットノード演算手段１１は、信頼度αが更新された場合、αの更新された検査行列の要素と同じ列に属するすべての非零要素に対応する各ビットノードについて信頼度βを算出し更新する。これにより、ノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。
【解決手段】すべての検査ノードについて、検査ノード選択手段７が優先度の高い順に順次選択する。検査ノード演算手段８は、選択された検査ノードについて、信頼度βに基づき、当該検査ノードに接続する各ビットノードに向け伝搬する信頼度αを算出し伝搬する。優先度更新手段９は、信頼度βに基づき信頼度が大きい順に検査ノードの優先度を決定し優先度を更新する。ビットノード演算手段１１は、信頼度αが更新された場合、αの更新された検査行列の要素と同じ列に属するすべての非零要素に対応する各ビットノードについて信頼度βを算出し更新する。これにより、ノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査（low density parity check：以下「ＬＤＰＣ」という。）符号を用いて受信値から送信符号を検出する符号検出技術に関する。
【背景技術】
【０００２】
ＬＤＰＣ符号は、１９６０年代にGallagerによって発案され（非特許文献１参照）、１９９０年代後半にMacKayやNealらによって再発見された符号である。その符号特性はShannonの限界に迫ることが知られており、次世代の誤り訂正符号として有望視されている（非特許文献２，３参照）。
【０００３】
ＬＤＰＣ符号は復号法としてサムプロダクト（Sum-Product）アルゴリズムを適用することにより、線形時間での復号と、優れた符号特性を達成することができる。このサムプロダクト・アルゴリズムは、パリティ・ビット数分の行処理と符号ビット数分の列処理からなるが、各行、各列処理は独立に計算してもよいことから、ハードウェアの並列実装に適している。
【０００４】
以下、ＬＤＰＣ符号とその復号法について簡単に説明する。ＬＤＰＣ符号は、非常に疎な検査行列により定義される線形符号である。ＬＤＰＣ符号のパリティ検査行列による検査式の例を式（１）に示す。
【０００５】
【数１】
【０００６】
ＬＤＰＣ符号により符号化された情報源符号は、通信路を経て受信値（ｙ１，ｙ２，…，ｙ９）となり、検査行列式（１）により誤りの有無が検査される。ここで、ＬＤＰＣ符号を定義する検査行列式（１）は、図１に示すタナーグラフ（Tanner graph）で表現される。このタナーグラフは符号長分のビットノードｂ１，ｂ２，…，ｂ９と検査ビット数分の検査ノードｃ１，ｃ２，…，ｃ６によって構成され、２種類のノードは検査行列式（１）の１の位置によって枝（以下「内部辺」という。）で接続される。受信符号に誤りが生じた場合には、図１のタナーグラフに受信値（ｙ１，ｙ２，…，ｙ９）を入力し、サムプロダクト・アルゴリズムを実行する。
【０００７】
サムプロダクト・アルゴリズムは、タナーグラフにおける信頼度を表す値αｍｎ，βｍｎを算出し、これらの信頼度を互いのノードで繰り返し交換しながら誤り訂正を実行するアルゴリズムである。信頼度を表す値αｍｎ，βｍｎとしては、確率量や対数尤度比などが用いられる。
【０００８】
タナーグラフの各検査ノードからビットノードへの内部辺は、検査行列の各行成分に対応し、各検査ノードで算出される信頼度αｍｎは検査ノードからビットノードへ伝搬される。この操作を「行処理」という。また、タナーグラフの各ビットノードから検査ノードへの内部辺は、検査行列の各列成分に対応し、各ビットノードで算出される信頼度βｍｎはビットノードから検査ノードへ伝搬される。この操作を「列処理」という。
【０００９】
以下ではサムプロダクト・アルゴリズムの詳細を説明するが、その前に、本明細書において使用する用語の定義を行う。
【００１０】
〔定義１〕（事前確率、事後確率、外部確率）
事象Ｂが生起する確率をＰ（Ｂ）と記す。事象Ａが起こったことが既知であるとき、事象Ｂが生起する条件付確率をＰ（Ｂ｜Ａ）と記す。このとき、ヘイズの定理より、式（２）が成立する。このとき、Ｐ（Ｂ）を「事前確率」、Ｐ（Ｂ｜Ａ）を「事後確率」、Ｐ（Ａ｜Ｂ）を「外部確率」という。
【００１１】
【数２】
（定義終わり）
【００１２】
〔定義２〕（レギュラーＬＤＰＣ符号、イレギュラーＬＤＰＣ符号）
ＬＤＰＣ符号のパリティ検査行列Ｈのｍ行目における非零要素の数（以下「行重み」という。）をｗｒ、ｎ列目における非零要素の数（以下「列重み」という。）をｗｃと記す。行重みｗｒが各行において均一で且つ列重みｗｃが各列において均一であるパリティ検査行列Ｈを持つＬＤＰＣ符号を「レギュラーＬＤＰＣ符号（regular LDPC code）」という。レギュラーＬＤＰＣ符号以外のＬＤＰＣ符号を「イレギュラーＬＤＰＣ符号（irregular LDPC code）」という。
（定義終わり）
【００１３】
〔定義３〕（非零成分のインデックス集合）
ＬＤＰＣ符号のパリティ検査行列を
【００１４】
【数３】
と表す。パリティ検査行列の列のインデックス集合｛１，２，…，Ｎ｝の部分集合Ａ（ｍ）及び行のインデックス集合｛１，２，…，Ｍ｝の部分集合Ｂ（ｎ）を式（４）及び式（５）により定義する。Ａ（ｍ），Ｂ（ｎ）を「非零成分のインデックス集合」という。
【００１５】
【数４】
（定義終わり）
【００１６】
〔定義４〕（Gallagerのｆ関数）
以下の式（６）で定義される関数ｆ（ｘ）を「Gallagerのｆ関数」という。
【００１７】
【数５】
（定義終わり）
【００１８】
〔定理１〕
Gallagerのｆ関数について、以下の関係が成立する。
【００１９】
【数６】
（定理終わり）
【００２０】
信頼度を表す値αｍｎ，βｍｎとして確率量ｒｍｎ，ｑｍｎを用いたサムプロダクト・アルゴリズムの詳細は、以下の（アルゴリズム１）に示す通りである。尚、受信値ｙｎ（ｎ＝１，２，…，Ｎ）の事前確率をｐｎｉｎｔ（ｙ）と記す。また、タナーグラフの各内部辺ｆｍｎにおいて、検査ノードｃｍからビットノードｂｎへ送られる外部確率量をｒｍｎ（ｆｍｎ）、ビットノードｂｎから検査ノードｃｍへ送られる外部確率量をｑｍｎ（ｆｍｎ）と記す。また、ビットノードｂｎにおける事後確率をｐｎｐｏｓｔ（ｙｎ）と記す。
【００２１】
〔アルゴリズム１〕（確率量を用いたサムプロダクト・アルゴリズム）
（ステップ１） ［初期化］
事前確率をｐｎｉｎｔ（ｙｎ＝０），ｐｎｉｎｔ（ｙｎ＝１）（ｎ＝１，２，…，Ｎ）とする。Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、内部辺における外部確率ｒｍｎをｒｍｎ（ｆｍｎ＝０）＝１／２，ｒｍｎ（ｆｍｎ＝１）＝１／２を初期設定し、外部確率ｑｍｎをｑｍｎ（ｆｍｎ）＝ｐｎｉｎｔ（ｙｎ）に初期設定する。また、繰り返し変数ｌを１に設定し、繰り返し最大回数をｌｍａｘに設定する。
【００２２】
（ステップ２） ［検査ノード（行処理）］
ｍ＝１，２，…，Ｍの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（８）（９）により外部確率ｒｍｎ（ｆｍｎ＝０），ｒｍｎ（ｆｍｎ＝１）を更新する。
【００２３】
【数７】
【００２４】
（ステップ３） ［ビットノード（列処理）］
ｎ＝１，２，…，Ｎの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（１０）（１１）により外部確率ｑｍｎ（ｆｍｎ＝０），ｑｍｎ（ｆｍｎ＝１）を更新する。
【００２５】
【数８】
【００２６】
（ステップ４） ［一時推定語の計算］
ｎ＝１，２，…，Ｎについて、式（１３）（１４）により事後確率ｐｎｐｏｓｔ（ｙｉ＝０），ｐｎｐｏｓｔ（ｙｉ＝１）を算出し、式（１６）により一時推定語ｙｎ＾を計算する。
【００２７】
【数９】
【００２８】
（ステップ５） ［パリティ検査］
一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）が以下のパリティ検査式（１７）を満たすか検査する。満たせばアルゴリズム終了。
【００２９】
【数１０】
【００３０】
（ステップ６） ［繰り返し回数カウント］
ｌ≦ｌｍａｘならばｌ←ｌ＋１とし、（ステップ２）へ。
ｌ＞ｌｍａｘならば、復号エラーとなり一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）を出力してアルゴリズムを終了。
（アルゴリズム１終わり）
【００３１】
また、信頼度を表す値αｍｎ，βｍｎとして対数尤度比ＬＬＲ（ｙ）＝ｌｎ（ｐ（ｙ＝０）／ｐ（ｙ＝１））を用いたサムプロダクト・アルゴリズムの詳細は、以下の（アルゴリズム２）に示す通りである。
【００３２】
〔アルゴリズム２〕（対数尤度比を用いたサムプロダクト・アルゴリズム）
（ステップ１） ［初期化］
ｎ＝１，２，…，Ｎに対して、ｙｎからλｎを式（１８）により算出する。式（１８）においてσは通信路の状態によって適宜設定される定数である。そして、Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、対数尤度比βｍｎをλｎに初期設定する（βｍｎ＝λｎ）。また、繰り返し変数ｌを１に設定し（ｌ＝１）、繰り返し最大回数をｌｍａｘに設定する。
【００３３】
【数１１】
【００３４】
（ステップ２） ［検査ノード（行処理）］
ｍ＝１，２，…，Ｍの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（１９）により対数尤度比αｍｎを更新する。ここで、ｆ（ｘ）はGallagerのｆ関数である。
【００３５】
【数１２】
【００３６】
（ステップ３） ［ビットノード（列処理）］
ｎ＝１，２，…，Ｎの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（２０）により対数尤度比βｍｎを更新する。
【００３７】
【数１３】
【００３８】
（ステップ４） ［一時推定語の計算］
ｎ＝１，２，…，Ｎについて、式（２１）により一時推定語ｙｎ＾を計算する。
【００３９】
【数１４】
【００４０】
（ステップ５） ［パリティ検査］
一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）が以下のパリティ検査式（２２）を満たすか検査する。満たせばアルゴリズム終了。
【００４１】
【数１５】
【００４２】
（ステップ６） ［繰り返し回数カウント］
ｌ≦ｌｍａｘならばｌ←ｌ＋１とし、（ステップ２）へ。
ｌ＞ｌｍａｘならば、復号エラーとなり一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）を出力してアルゴリズムを終了。
（アルゴリズム２終わり）
【００４３】
（アルゴリズム２）において、Gallagerのｆ関数をハードウェアで実装する場合、一般的にはルックアップ・テーブルによる表引き、線形補完といった方法が採られる。そのため、ハードウェア・コストのかかる回路となる。そこで、このｆ関数を近似するミニサム（min-sum）アルゴリズムが広く適用されている。Gallagerのｆ関数はｘ＞０のとき単調減少関数となり、特にｘの値が小さいときの出力が支配的となる。従って、式（１９）のｆ関数部を次の式（２３）で近似することができる。
【００４４】
【数１６】
【００４５】
式（２３）の第３項の変形は（定理１）を利用している。このミニサム・アルゴリズムを用いれば、加算、最小、正負の判定、及び正負の符号乗算のみで復号が可能となり、復号用ハードウェアにおける行処理演算ユニットの並列配置が十分に可能となる。
【００４６】
次に、従来のＬＤＰＣ復号器のハードウェアの実装について説明する。ＬＤＰＣ復号器のハードウェアへの実装については、非特許文献４〜８において報告されている。非特許文献４，５に記載されたＬＤＰＣ復号器は完全並列ＬＤＰＣ復号器（Full-Parallel LDPC Decoder）と呼ばれ、各行、各列処理用の演算ユニットをすべて実装し、すべての演算ユニットは、ＬＤＰＣ符号の検査行列に従って完全に結線されている。この実装法は復号器の処理性能を得る最も単純な方法であるが、符号長の大きなＬＤＰＣ符号に対しては極めて困難であるため、ハードウェアの実装が難しい。
【００４７】
このことから、ハードウェアの実装と処理性能の両面から見ると部分並列実装（Partial-Parallel LDPC Decoder）が最も有力かつ実用的な実装法であり、非特許文献６〜８などで報告されている。
【００４８】
非特許文献７，８等でみられる従来の部分並列ＬＤＰＣ復号器（Partial-Parallel LDPC Decoder）では、行重みｗｒと列重みｗｃが一定であるレギュラーＬＤＰＣ符号のパリティ検査行列に対し、（アルゴリズム２）の（ステップ２）の行処理と（ステップ３）の列処理を独立に並列実行する。
【００４９】
更に、（ステップ２）においては、Ｍ個の検査ノードを列重みｗｃ個に分割し、ｗｃ個の検査ノードを並列に処理する。（ステップ３）においては、Ｎ個のビットノードを行重みｗｒ個に分割しｗｒ個のビットノードを並列に処理する。このように、行処理、列処理をそれぞれ列重み、行重みで分割するために、レギュラーＬＤＰＣ符号のパリティ検査行列を図２のように区分けして構成する（非特許文献８参照）。
【００５０】
図２は、１区画がｐ×ｐ個の要素からなる部分行列（以下「ブロック」という。）を横にｗｒ個、縦にｗｃ個並べて、ｗｒ×ｗｃ個のブロックから、縦Ｍ行、横Ｎ列のパリティ検査行列が構成されている。各ブロック内の斜線は、ブロック内における１の要素の位置を表している。図２の斜線は、各ブロックにおいて、対角成分が１である単位行列の各行を規則的に右シフトしている。シフトによってあふれたビットはブロック内の最左列に挿入している。このように構成することで、行重み、列重みがそれぞれ横のブロック数ｗｒと縦のブロック数ｗｃとなるレギュラーＬＤＰＣ符号用のパリティ検査行列が得られる。図２の例では、行重みｗｒ＝６、列重みｗｃ＝３の（３，６）レギュラーＬＤＰＣ符号のパリティ検査行列である。
【００５１】
このように規則的に１を配置することによって、図１のタナーグラフにおいて、信頼度情報を交換するノード間の結線情報をメモリに記憶しておく必要がなくなる。
【００５２】
ここで、パリティ検査行列をランダムに構成したい場合には、規則的に生成した各ブロック内でランダムに列置換，行置換を実行すれば、ｗｃ並列の行処理とｗｒ並列の列処理が可能なパリティ検査行列が維持できる。この場合は、復号器は、パリティ検査行列の１の要素の位置を記憶するメモリが必要となる。
【特許文献１】特開２００５−４５７３５号公報
【非特許文献１】R. G. Gallager, Low-Density Parity-Check Codes, MIP Press, Cambridge, MA, 1963.
【非特許文献２】D. J. C. MacKay, "Good error-correcting codes based on very sparse matrices," IEEE Trans, on Information Theory, Vol.47, pp.498-519, 2001.
【非特許文献３】S.Y. Chung, G.P. Forney Jr., T.J. Richardson, R.L. Urbanke, "On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit," IEEE Communications letters, Vol.5, No.2, Feb. 2001.
【非特許文献４】A. Blanksby and C. Howland, "A 690-mW 1-Gbps 1024-b, rate-1/2 Low-Density Parity-Check Code Decoder," IEEE Journal of Solid State Circuits, Vol.37, pp.404-412, Mar., 2002.
【非特許文献５】E. Liao, E. Yeo and B. Nikolie, "Low-density parity-check code constructions for hardware implementation," Proceedings 2004 IEEE International Conference on Communications, ICCf04y Paris, pp.2573-2577, June, 2004.
【非特許文献６】Y. Chen and D. Hocevar, "A FPGA and ASIC Implementation of Rate 1/2 8088-b Irregular Low Density Parity Check Decoder," IEEE Global Telecommunications Conference, GLOBECOM'QS, pp.113-117, 2003.
【非特許文献７】M. Mansour and N. Shanbhag, "Low Power VLSI Decoder Architectures for LDPC Codes," Proceedings of the International Symposium on Low Power Electronics and Design, pp.284-289, 2002.
【非特許文献８】Marjan Karkooti and Joseph R. Cavallaro, "Semi-Parallel Reconfigurable Architectures for Real-Time LDPC Decoding," IEEE Proceedings of International Conference on Information Technology: Coding and Computing, ITCC'04,
【非特許文献９】T.J. Richardson and R,L. Urbanke, "The capacity of low-density parity-check codes under message-passing decoding", IEEE Trans, on Information Theory, vol.42, no.2, pp.599-618, 2001.
【発明の開示】
【発明が解決しようとする課題】
【００５３】
ここで、実用的な復号用ハードウェアを実装するために、一般的に必要とされる手続きは、以下の３点に要約される。
【００５４】
（１）行処理、列処理で扱う少数中間値の量子化。
（２）ハードウェア規模削減を目的とする、ミニサム（min-sum）アルゴリズムを用いた行処理の近似。
（３）行処理、列処理の各演算ユニットの結線を簡易にするパリティ検査行列の利用。
【００５５】
上記（１）（２）により、誤り訂正が完了するまで繰り返し実行される復号処理の計算精度が劣化する。また、（３）により、利用可能な検査行列が限定されてしまう。そのため、ランダムに構成された理想的なＬＤＰＣ符号（非特許文献９参照）への対応が難しい。結果的に、上記の手続きを適用したハードウェアによる復号では、復号処理が収斂するまでにかかる繰り返し回数が増加する。加えて、ＬＤＰＣ復号の復号特性の劣化も招く。
【００５６】
非特許文献５〜８に記載の従来のＬＤＰＣ復号用のハードウェアも、上記の手続きを適用して実用的なハードウェアを実現しているが、これらの問題点に関しては考慮されていない。
【００５７】
そこで、本発明の目的は、行処理、列処理で扱う中間値である信頼度情報の伝搬効率を改善することにより、復号が収斂するための繰り返し回数が少なく復号特性に優れたＬＤＰＣ符号検出技術を提供することを目的とする。
【課題を解決するための手段】
【００５８】
〔１〕本発明の基本的な考え方
上記目的を達成するために、本発明においては、以下の２つの手法を導入することにより、復号用ハードウェアにおける信頼度の伝搬効率を改善する。
【００５９】
（１）行処理、列処理を独立に実行するのではなく、各行処理に連動してその検査ノードに属するビットノードの列処理をパイプライン的に実行することで、信頼度の伝搬効率を改善する。
（２）各行処理に対し、その検査ノードに属するビットノードの信頼度の高さで分類し、信頼度の高い検査ノードから順に行処理を実行する。
【００６０】
上記従来の部分並列ＬＤＰＣ復号器では、図２における各ブロックの行処理と列処理をそれぞれ１行１列目から順に並列実行するため、信頼度の伝搬において以下の点で効率が悪い。
【００６１】
（ａ）パリティ検査行列（図２）の「１」の要素は各ブロックによって位置がまったくずれているため、行処理、列処理を１行１列目から順番に実行すると、各ブロックの行処理による信頼度の更新位置と列処理による信頼度の更新位置がずれる。従って、行処理の更新結果が列処理に反映されるタイミングはすべて異なり、その反映が遅れるブロックもある。
【００６２】
（ｂ）受信符号における信頼度の高いビットは、符号毎に異なるため、その信頼度が高いビットが計算に含まれる順番も受信符号毎に異なる。
【００６３】
これに対し、本発明では、行処理と列処理の信頼度の伝搬効率を改善する手法として以下の２つの手法を導入する。
【００６４】
（Ａ）各行処理に連動してその検査ノードに属するビットノードの列処理をパイプライン的に並列実行することで、信頼度の伝搬効率を改善する。
（Ｂ）各行処理に対し、その検査ノードに属するビットノードの信頼度の高さで分類し、信頼度の高い検査ノードから順に行処理を実行する。
【００６５】
これらの手法を図３を用いて説明する。図３は（３，６）レギュラーＬＤＰＣ符号のパリティ検査行列を表し、図２と同様にブロックに区分けされている。また、各ブロック内の斜線は、図２と同様、ブロック内における１の要素の位置を表している。
【００６６】
手法（Ａ）により、行処理は、まず図３の縦に並ぶ３つのブロックに対して、第ｉ１（１），ｉ１（２），ｉ１（３）行目を同時に実行する。この行処理によって、信頼度α（ｉ１（１），ｊ（１１）），…，α（ｉ１（１），ｊ（１６）），α（ｉ１（２），ｊ（２１）），…，α（ｉ１（２），ｊ（２６）），α（ｉ１（３），ｊ（３１）），…，α（ｉ１（３），ｊ（３６））が更新される。
【００６７】
次に、各ブロックで更新されたαに対応する列処理をすべて実行する。例えば、図３の第１行１列ブロックでは、α（ｉ１（１），ｊ（１１））が更新され、第２行１列ブロックでは、α（ｉ１（２），ｊ（２１））が更新され、第３行１列ブロックでは、α（ｉ１（３），ｊ（３１））が更新される。従って、第１列目のブロックで更新されたαに対応する列は第１列ブロック内の第ｊ（１１），ｊ（２１），ｊ（３１）列目であり、これらのすべての列に対して列処理を実行する。この処理によって、第ｊ（１１）列目の処理によるβ（ｉ１（１），ｊ（１１）），β（ｉ３（２１），ｊ（１１）），β（ｉ２（３１），ｊ（１１））と、第ｊ（２１）列目の処理によるβ（ｉ２（１１），ｊ（２１）），β（ｉ１（２），ｊ（２１）），β（ｉ３（３１），ｊ（２１））と、第ｊ（３１）列目の処理によるβ（ｉ３（１１），ｊ（３１）），β（ｉ２（２１），ｊ（３１）），β（ｉ１（３），ｊ（３１））との信頼度が更新される。
【００６８】
手法（Ｂ）では、まず、各行処理に対して、その検査ノードに属するビットノードに向けた信頼度αの大きさで分類する。信頼度αは、検査ノードからビットノードへ伝搬され、信頼度αを受け取ったビットノードは、（アルゴリズム２）の（ステップ４）で、他の検査ノードから伝搬される信頼度αとの総和式（２１）で、そのビットの推定語を算出する。ビットの推定語は総和式（２１）の符号で判定するため、総和の絶対値が大きいときは、特に信頼できる判定結果であるといえる。
【００６９】
ここで、総和の要素は検査ノードから伝搬される信頼度αであることから、行処理で算出されるαの値が或る閾値を超えた値であった場合は、その検査ノードは高い信頼度を伝搬するノードであるとする。そして、高い信頼度は早めに伝搬されると、信頼度の伝搬効率が改善されると考えられる。そこで、高い信頼度を伝搬する検査ノードに対する行処理を先に処理することとする。
【００７０】
ここで、ミニサム・アルゴリズムを利用した行処理は、式（２３）となる。つまり、この行処理によって、集合ｎ∈Ａ（ｍ）に関する｜βｍｎ｜の最小値か２番目の最小値かの何れかが信頼度αとして伝搬される。
【００７１】
そこで、行処理で算出される信頼度の高さは、以下の式（２４）で判定する。ここで、信頼度の高さの閾値をＴαとする。
【００７２】
【数１７】
【００７３】
式（２４）で閾値以上のときは信頼度が高く、下回るときは信頼度が低いとして、各検査ノードを２つに分類する。この判定式で信頼度が高い値を伝搬する検査ノードであると判定された時は、次の繰り返しの行処理において、先に実行される。尚、この判定は、すべての検査ノードに対して、行処理の繰り返し毎に実行される。
【００７４】
また、式（２４）では各検査ノードの優先度を２つのランクに分類する場合で説明したが、一般に、３以上のランクに優先度の分類を行うようにしてもよい。
【００７５】
〔２〕本発明の構成
本発明に係るＬＤＰＣ符号検出装置の第１の構成は、低密度パリティ検査（以下「ＬＤＰＣ」という。）符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収斂判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値からの符号検出を行うＬＤＰＣ符号検出装置において、前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段；前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段；前記各検査ノードの優先度を記憶する優先度記憶手段；すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択手段；前記検査ノード選択手段が選択する前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき、当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出し、前記ビットノード記憶手段内の対応する信頼度αを更新する検査ノード演算手段；前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき信頼度が大きい順に当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新手段；及び、前記ビットノード記憶手段内の信頼度αが更新された場合、前記パリティ検査行列における信頼度αの更新された要素と同じ列に属するすべての非零要素に対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算手段；を備えたことを特徴とする。
【００７６】
この構成により、検査ノード演算手段が当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを更新すると、ビットノード演算手段により、パリティ検査行列における信頼度αが更新された要素と同列の非零要素に対応する各ビットノードについて、当該ビットノードに接続する各検査ノードに向け伝搬される信頼度βがパイプライン的に更新される。これにより、各検査ノード及び各ビットノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。
【００７７】
また、各検査ノードは、優先度更新手段により、信頼度βに基づいて、信頼度が大きい順に優先度が決定される。そして、検査ノード選択手段により、優先度が高い順に、検査ノード演算手段によって信頼度αの更新を実行する検査ノードが選択される。従って、大きい信頼度βを持つ検査ノードから優先的に、各ビットノードへ信頼度情報が伝搬される。そして、その信頼度情報は、即座に（パイプライン的に）ビットノードから各検査ノードに伝搬される。このように、サムプロダクト・アルゴリズムの収斂を促進するのに寄与する信頼度情報ほど速くノード間を伝搬するため、サムプロダクト・アルゴリズムの収斂がより促進される。
【００７８】
ここで、「信頼度」としては、確率又はそれに準じた値（対数尤度比等）が使用される。
【００７９】
「優先度」とは、外部値演算手段により外部値の伝搬を行う際の優先順位を表す指標をいう。優先度更新手段が優先度を決定する方法としては、種々の方法が考えられるが、例えば、信頼度として対数尤度比を用いた場合には、式（２４）のように閾値判定を用いて尤度を複数のランクに分類することにより優先度を決定する方法を用いることができる。
【００８０】
尚、サムプロダクト・アルゴリズムの収束判定に使用する事後値の算出は、上述の式（１３）（１４）や式（２１）に示したような公知の方法が用いられる。
【００８１】
本発明に係るＬＤＰＣ符号検出装置の第２の構成は、前記第１の構成において、前記パリティ検査行列は、列方向にＭ個、行方向にＮ個の部分行列に区分けされ、各区画における部分行列の各行の非零成分の数は１個又は０個に設定されたものであり、Ｍ個の区画行の各々に対応して設けられたＭ個の前記検査ノード記憶手段、前記優先度記憶手段、前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段を備え、Ｎ個の区画列の各々に対応して設けられたＮ個の前記ビットノード記憶手段、及び前記ビットノード演算手段を備え、前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段は並列動作し、前記各区画列の前記ビットノード演算手段は並列動作することを特徴とする。
【００８２】
この構成により、図３のように、部分行列（以下「ブロック」という。）に区分けされたパリティ検査行列において、このブロック行列の行方向及び列方向に並列に信頼度伝搬の処理がされるため、サムプロダクト・アルゴリズムを高速に実行させることが可能となる。
【００８３】
本発明に係るＬＤＰＣ符号検出装置の第３の構成は、前記第２の構成において、前記各区画列の前記ビットノード演算手段は、その演算処理を、前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段の演算処理とパイプライン的に実行することを特徴とする。
【００８４】
この構成によれば、図３のように、部分行列（以下「ブロック」という。）に区分けされたパリティ検査行列において、各区画行の検査ノード選択手段、検査ノード演算手段、及び優先度更新手段により信頼度α及び優先度の演算処理が終了すると、パイプライン的に並行して各区画列のビットノード演算手段の信頼度βの演算処理が行われる。従って、各ノード間の信頼度情報の伝搬が速く、またハードウェアの待ち時間も最小限に抑えられるため、サムプロダクト・アルゴリズムを高速に実行させることが可能となる。
【００８５】
本発明に係るＬＤＰＣ符号検出装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記信頼度α，βは対数尤度比であり、前記優先度更新手段は、前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βの最小値を閾値判定で分類することにより当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新することを特徴とする。
【００８６】
このように、信頼度α，βとして対数尤度比を使用すれば、信頼度βからの優先度の決定処理の演算が容易化される。従って、ハードウェア・コストを下げ、高速化することが可能となる。
【００８７】
本発明に係るＬＤＰＣ符号検出装置の第５の構成は、前記第１乃至３の何れか一の構成において、前記検査ノード記憶手段には、前記各検査ノードｃｍに対し、当該検査ノードｃｍに接続する前記各ビットノードｂｎより伝搬される信頼度βｍｎが記憶されており、前記ビットノード記憶手段には、前記各ビットノードｂｎに対し、当該ビットノードｂｎに接続する前記各検査ノードｃｍより伝搬される信頼度αｍｎが記憶されており、前記検査ノード演算手段は、前記検査ノード選択手段が選択する前記検査ノードｃｍについて、当該検査ノードｃｍに向け伝搬される前記信頼度βｍｎに基づき、（数１８）により当該検査ノードｃｍに接続する前記各ビットノードｂｎに向け伝搬する信頼度αｍｎを算出し、前記ビットノード記憶手段内の対応する信頼度αｍｎを更新するものであり、前記優先度更新手段は、前記各検査ノードｃｍについて、（数１９）で算出されるηｍの値を２値以上に量子化して大きい順に高い優先度に決定し、前記優先度記憶手段内の対応する優先度を更新するものであり、前記ビットノード演算手段は、前記ビットノード記憶手段内の信頼度αｍｎが更新された場合、更新されたすべての信頼度αｍｎに対応する前記各ビットノードｂｎについて、当該ビットノードに接続する前記各検査ノードｃｍ’に向け伝搬する信頼度βｍ’ｎを（数２０）により算出し、前記検査ノード記憶手段内の対応する信頼度βｍ’ｎを更新するものであることを特徴とする。
【００８８】
【数１８】
【００８９】
【数１９】
【００９０】
【数２０】
【００９１】
このように、信頼度α，βとして対数尤度比を使用することにより、信頼度α，βの更新演算が式（２５）や式（２７）のように簡単化される。また、優先度更新手段による優先度の決定は、式（２６）の演算及びこれを量子化する演算となり簡略化される。
【００９２】
本発明に係るＬＤＰＣ符号検出装置の第６の構成は、前記第５の構成において、前記検査ノード演算手段及び前記優先度更新手段は、前記（数１８）及び（数１９）の演算を、それぞれ（数２１）及び（数２２）の近似式により実行することを特徴とする。
【００９３】
【数２１】
【００９４】
【数２２】
【００９５】
このように、Gallagerのｆ関数をミニサム・アルゴリズムを用いて近似化することにより、加算、最小、正負の判定、及び正負の符号乗算のみで復号が可能となる。従って、ハードウェア・コストを下げ、高速化することが可能となる。
【００９６】
本発明に係るＬＤＰＣ符号検出方法は、ＬＤＰＣ符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収斂判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値ｙからの符号検出を行うＬＤＰＣ符号検出方法において、前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段について、各信頼度βを前記受信値ｙにより初期化する検査ノード初期化ステップ；前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段について、各信頼度αを所定の初期値に初期化するビットノード初期化ステップ；前記各検査ノードの優先度を記憶する優先度記憶手段の各優先値を所定の初期値に初期化する優先値初期化ステップ；並びに、前記各検査ノード及び前記各ビットノードの間で前記信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収斂判定し送信符号の推定値を決定する推定ステップ；を備え、前記推定ステップにおいては、すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択ステップ；前記検査ノード選択ステップで選択された前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βを検査ノード記憶手段から読み出し、読み出された各信頼度βに基づき当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出する検査ノード演算ステップ；前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新ステップ；及び、前記ビットノード記憶手段内の信頼度αが更新された場合、更新されたすべての信頼度αに対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算ステップ；からなる一連の演算処理を、前記検査ノード記憶手段内の信頼度βから算出される事後値を硬判定して得られる一次推定語とパリティ検査行列の積が０となるまで繰り返し実行することを特徴とする。
【００９７】
本発明に係るプログラムは、コンピュータに読み込んで実行することにより、コンピュータを前記第１乃至６の何れか一の構成のＬＤＰＣ符号検出装置として機能させることを特徴とする。
【発明の効果】
【００９８】
以上のように、本発明によれば、検査ノードからビットノードに信頼度情報が伝搬されると、パリティ検査行列において伝搬された信頼度に対応する要素と同列の非零要素に対応する各ビットノードについて、当該ビットノードから各検査ノードに向け信頼度がパイプライン的に伝搬される。これにより、各検査ノード及び各ビットノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。更に、大きい信頼度を有する検査ノードから順に信頼度の伝搬を実行することにより、サムプロダクト・アルゴリズムの収斂を促進するのに寄与する信頼度情報ほど速くノード間を伝搬するため、サムプロダクト・アルゴリズムの収斂がより促進される。その結果、復号が収斂するための繰り返し回数が少なく復号特性に優れたＬＤＰＣ符号検出装置及びＬＤＰＣ符号検出方法を提供することができる。
【発明を実施するための最良の形態】
【００９９】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【０１００】
本実施例１においては、２元ＬＤＰＣ符号を取り扱う。図４は本発明の実施例１に係るＬＤＰＣ符号検出装置１の構成を表すブロック図である。図４において、ＬＤＰＣ符号検出装置１は、受信値記憶手段２、ノード初期化手段３、受信値対数尤度演算手段４、検査ノード記憶手段５、ビットノード記憶手段６、検査ノード選択手段７、検査ノード演算手段８、優先度更新手段９、優先度記憶手段１０、ビットノード演算手段１１、硬判定手段１２、及びパリティ判定手段１３を備えている。
【０１０１】
検査ノード記憶手段５は、図１に示したようなタナーグラフの各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）に対し、当該検査ノードｃｍに接続する各ビットノード｛ｂｎ｜ｎ∈Ａ（ｍ）｝より伝搬される信頼度｛βｍｎ｜ｎ∈Ａ（ｍ）｝を記憶する。ビットノード記憶手段６は、図１に示したようなタナーグラフの各ビットノードｂｎ（ｎ＝１，２，…，Ｎ）に対し、当該ビットノードｂｎに接続する各ビットノード｛ｂｎ｜ｎ∈Ａ（ｍ）｝より伝搬される信頼度｛βｍｎ｜ｎ∈Ａ（ｍ）｝を記憶する。優先度記憶手段１０は、各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）についての優先度を記憶する。受信値記憶手段２は、外部から入力されるＬＤＰＣ符号のＮビットの受信値（ｙ１，ｙ２，…，ｙＮ）を一時記憶する。
【０１０２】
ノード初期化手段３は、検査ノード記憶手段５及びビットノード記憶手段６内の対数尤度比βｍｎ、αｍｎの初期設定をする。また、内部変数として有する繰り返し変数ｌ及び繰り返し最大回数をｌｍａｘの初期設定をする。受信値対数尤度演算手段４は、受信値記憶手段２に一時記憶された受信値ｙｎから受信値対数尤度λｎを式（１８）により算出する。
【０１０３】
検査ノード選択手段７は、優先度記憶手段１０に記憶された優先度に基づいて、すべての検査ノードｃｍ（ｍ＝１，２，…，Ｍ）について優先度の高い順に順次選択する。
【０１０４】
検査ノード演算手段８は、検査ノード選択手段７が選択する検査ノードｃｍについて、当該検査ノードｃｍに向け伝搬される信頼度βｍｎ（ｎ∈Ａ（ｍ））に基づき、当該検査ノードｃｍに接続する各ビットノードｂｎに向け伝搬する信頼度αｍｎ（ｎ∈Ａ（ｍ））を算出し、ビットノード記憶手段６内の対応する信頼度αｍｎの値を更新する。
【０１０５】
優先度更新手段９は、各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）について、当該検査ノードｃｍに向け伝搬される信頼度βｍｎに基づき閾値判定により当該検査ノードｃｍの優先度を決定し、優先度記憶手段１０内の対応する優先度を更新する。
【０１０６】
ビットノード演算手段１１は、ビットノード記憶手段６内の信頼度αｍｎが更新された場合、パリティ検査行列Ｈにおける信頼度αｍｎの更新された要素Ｈｍｎと同じ列に属するすべての非零要素Ｈｉ，ｎ（ｉ∈Ｂ（ｎ））に対応する各ビットノードｂｉ，ｎについて、当該ビットノードｂｉ，ｎに接続する各検査ノードｃｉ，ｎに向け伝搬する信頼度βｉ，ｎを算出し、検査ノード記憶手段５内の対応する信頼度βｉ，ｎを更新する。
【０１０７】
硬判定手段１２は、ビットノード記憶手段６に記憶された信頼度αｍｎ（ｍ∈Ｂ（ｎ），ｎ∈Ａ（ｍ））及び受信値対数尤度演算手段４が出力する受信値対数尤度λｎに基づき式（２１）により一時推定語ｙｎ＾を算出する。
【０１０８】
パリティ判定手段１３は、硬判定手段１２が出力する一時推定語（ｙ１＾，ｙ２＾，…，ｙｎ＾）が式（２２）のパリティ検査式を満たすか否かの判定を行う。
【０１０９】
以上のように構成された本実施例１に係るＬＤＰＣ符号検出装置１において、以下その動作を図５のフローチャートを用いて説明する。尚、図５のフローチャートは、図３のパリティ検査行列の１つの区画行に関する処理を表すものであり、実際には各行区画において図５の処理が並列に実行されるものとする。
【０１１０】
まず、ステップＳ１において、受信値が受信値記憶手段２に入力され一時記憶されると、ノード初期化手段３は、受信値記憶手段２に一時記憶された受信値ｙｎからλｎを式（１８）により算出する。そして、Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、検査ノード記憶手段５内の信頼度βｍｎをｙｎに初期設定する。また、ビットノード記憶手段６内の信頼度αｍｎを０に初期設定する。また、内部変数として有するイテレータ（反復子）ｌを１に設定し、繰り返し最大回数をｌｍａｘに設定する。
【０１１１】
ステップＳ２において、受信値対数尤度演算手段４は、式（１８）により各受信値ｙｎ（ｎ＝１，２，…，Ｎ）に対する受信値対数尤度λｎを算出する。また、優先度記憶手段１０は、各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）の優先度のランクｒｍを１に設定する。
【０１１２】
ステップＳ３において、硬判定手段１２は、受信値記憶手段２に記憶された各受信値ｙｎ（ｎ＝１，２，…，Ｎ）に基づき、式（３０）による硬判定を行い一時推定値ｙｎ＾を求める。
【０１１３】
【数２３】
【０１１４】
ステップＳ４において、パリティ判定手段１３は、ステップＳ３で得られた一時推定語ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）とパリティ検査表列Ｈに基づき、式（３１）により一時推定語ｙ＾のパリティｐａｒ（ｙ＾）を計算する。
【０１１５】
【数２４】
【０１１６】
ステップＳ５において、パリティ判定手段１３は、パリティｐａｒ（ｙ＾）は０か１かを判定する。ｐａｒ（ｙ＾）が０であれば、ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）を復号語として出力して動作を終了する。ｐａｒ（ｙ＾）が１の場合、検査ノード選択手段７を呼び出して、ステップＳ６に移行する。
【０１１７】
ステップＳ６においては、検査ノード選択手段７は、選択する優先度レベルａを１に初期化する。そして、選択する行番号（検査ノードの番号）ｍを１に初期化する。
【０１１８】
ステップＳ７において、検査ノード選択手段７は、行番号ｍの優先度ｒｍが優先度レベルａと一致するか否かを判定する。一致しない場合にはステップＳ１１に移行し、一致した場合には検査ノード選択手段７は検査ノードｃｍを選択し次のステップＳ８へ移行する。
【０１１９】
ステップＳ８において、検査ノード演算手段８は、選択された行番号ｍの検査ノードｃｍについて行処理を実行する。すなわち、検査ノード演算手段８は、Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（１９）により信頼度αｍｎを計算する。そして、ビットノード記憶手段６内の信頼度αｍｎの値を更新する。図３の例では、このときα（ｉ１（ｐ），ｊ（ｐ１）），…，α（ｉ１（ｐ），ｊ（ｐ６））（ｐ＝１，２，３）が更新される。
【０１２０】
ステップＳ９において、優先度更新手段９は、選択された行番号ｍの検査ノードｃｍの優先度ｒｍを計算し、優先度記憶手段１０内の優先度ｒｍを更新する。ここで、優先度ｒｍの計算は式（３２）により行われる。
【０１２１】
【数２５】
【０１２２】
ステップＳ１０において、ビットノード演算手段１１は、すべての更新された信頼度αｍｎの属する各列について列処理を実行する。
【０１２３】
例えば、図３の例で言うと、第ｑ区画列（ｑ＝１，２，…，６）においては、ステップＳ８でα（ｉ１（１），ｊ（１ｑ）），α（ｉ１（２），ｊ（２ｑ）），α（ｉ１（３），ｊ（３ｑ））が更新される。これらのαの属する列は、ｊ（１ｑ），ｊ（２ｑ），ｊ（３ｑ）である。従って、ビットノード演算手段１１は、第ｑ区画列の各ブロックにおいて、列ｊ（１ｑ），ｊ（２ｑ），ｊ（３ｑ）に属する非零要素の内部辺に接続するビットノードについて、信頼度βの計算を行う。すなわち、第１区画行ｑ区画列では、β（ｉ１（１），ｊ（１ｑ）），β（ｉ２（１ｑ），ｊ（２ｑ）），β（ｉ３（１ｑ），ｊ（３ｑ））の計算を行い、第２区画行ｑ区画列では、β（ｉ１（２），ｊ（２ｑ）），β（ｉ２（２ｑ），ｊ（３ｑ）），β（ｉ３（３ｑ），ｊ（１ｑ））の計算を行い、第３区画行ｑ区画列では、β（ｉ１（３），ｊ（３ｑ）），β（ｉ２（１ｑ），ｊ（１ｑ）），β（ｉ３（２ｑ），ｊ（２ｑ））の計算を行う。
【０１２４】
計算されたそれぞれの信頼度βについて、検査ノード記憶手段５内の信頼度βが更新される。尚、ビットノード演算手段１１による信頼度βの計算は、式（２０）に従って実行される。
【０１２５】
ステップＳ１１において、検査ノード選択手段７は、ｍがＭに達したか否かを判定し、ｍ＜Ｍであれば、ｍ←ｍ＋１として（ステップＳ１２）、ステップＳ７に戻る。一方、ｍ＝Ｍならば、ステップＳ１３に進む。
【０１２６】
ステップＳ１３において、検査ノード選択手段７は、ａが１であれば、ａ←０として（Ｓ１４）、ステップＳ７に戻る。また、ａが０であれば、ステップＳ３に戻る。
【０１２７】
ステップＳ３においては、硬判定手段１２は、今度は検査ノード記憶手段５に記憶された信頼度αに基づき、式（２１）による硬判定を行い一時推定値ｙｎ＾を求める。また、イテレータｌをｌ←ｌ＋１とする。
【０１２８】
ステップＳ４において、パリティ判定手段１３は、ステップＳ３で得られた一時推定語ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）とパリティ検査表列Ｈに基づき、式（３１）により一時推定語ｙ＾のパリティｐａｒ（ｙ＾）を計算する。
【０１２９】
ステップＳ５において、パリティ判定手段１３は、パリティｐａｒ（ｙ＾）は０か１かを判定する。ｐａｒ（ｙ＾）が０であれば、ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）を復号語として出力して動作を終了する。また、イテレータｌがｌ＞ｌｍａｘとなった場合には、復号エラーの信号とともにｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）を出力し、動作を終了する。ｐａｒ（ｙ＾）が１で且つｌ≦ｌｍａｘの場合、検査ノード選択手段７を呼び出して、ステップＳ６に移行し、以下同様の動作を繰り返す。
【０１３０】
以上の動作により、検査ノード演算手段８が当該検査ノードｃｍに接続する各ビットノード｛ｂｎ｜ｎ∈Ａ（ｍ）｝に向け伝搬する信頼度αｍｎを更新すると、ビットノード演算手段１１により、パリティ検査行列Ｈにおける信頼度αｍｎが更新された要素と同列の非零要素に対応する各ビットノード｛ｂｊ｝について、当該ビットノード｛ｂｊ｝に接続する各検査ノードに向け伝搬される信頼度｛βｋｊ｝がパイプライン的に更新される。これにより、各検査ノード及び各ビットノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。
【０１３１】
また、各検査ノードｃｍは、優先度更新手段９により、信頼度｛βｍｎ｝に基づいて、信頼度ｒｍが大きい順に優先度が決定される。そして、検査ノード選択手段７により、優先度ｒｍが高い順に、検査ノード演算手段８による信頼度αｍｎの更新を実行する検査ノードｃｍが選択される。従って、大きい信頼度βを持つ検査ノードから優先的に、各ビットノードへ信頼度情報が伝搬される。そして、その信頼度情報は、即座に（パイプライン的に）ビットノードから各検査ノードに伝搬される。このように、サムプロダクト・アルゴリズムの収斂を促進するのに寄与する信頼度情報ほど速くノード間を伝搬するため、サムプロダクト・アルゴリズムの収斂がより促進される。
【実施例２】
【０１３２】
実施例２では、実施例１のＬＤＰＣ符号検出装置１をより具体的にハードウェアに実装した例について説明する。
【０１３３】
図６は、実施例２に係るＬＤＰＣ符号検出装置１のアルゴリズム実行エンジン１５のハードウェア構成を表す図である。図６は、図４において点線で囲まれたアルゴリズム実行エンジン１５の部分に相当する。尚、本実施例においては、行重みｗｒ＝６、列重みｗｃ＝３の（３，６）レギュラーＬＤＰＣ符号のＬＤＰＣ復号装置を示しているが、行重みｗｒ，列重みｗｃに関しては容易に一般化することができる。
【０１３４】
アルゴリズム実行エンジン１５は、３つの行処理モジュール２０−１〜２０−３と６つの列処理モジュール２１−１〜２１−６を備えている。また、各行処理モジュール２０−１〜２０−３と各列処理モジュール２１−１〜２１−６の間には、図１のタナーグラフの内部辺に対応して設けられた６本の分岐した内部接続線２６及び３本の内部接続線２７が設けられている。タナーグラフの内部辺で接続された行処理モジュール２０と列処理モジュール２１同士が、各内部接続線２６，２７により接続されている。内部接続線２６は、列処理モジュール２１から行処理モジュール２０へ信頼度βを伝達する線である。内部接続線２７は、行処理モジュール２０から列処理モジュール２１へ信頼度αを伝達する線である。
【０１３５】
また、６本の内部接続線２６のそれぞれには、６本の入力線２８が接続されている。３本の内部接続線２７のそれぞれには、３本の出力線２９が接続されている。入力線２８には、各βｍｎの初期値としての受信値ｙｎが入力される。また、出力線２９からは、硬判定手段１２に対してｙｎ＾の計算に使用する信頼度αｍｎが出力される。
【０１３６】
各行処理モジュール２０は、６組の検査ノード・メモリバンク２２と、１つの検査関数ユニット２３及び検査ノード選択ユニット３０を備えている。各検査ノード・メモリバンク２２が、図４の監査ノード記憶手段５に相当する。検査関数ユニット２３は、図４の検査ノード演算手段８に相当する。検査ノード選択ユニット３０は、図４の検査ノード選択手段７、優先度更新手段９、及び優先度記憶手段１０に相当する。
【０１３７】
列処理モジュール２１は、３つのビットノード・メモリバンク２４と１つのビット関数ユニット２５及びビットノード選択ユニット３１を備えている。ビットノード・メモリバンク２４は図４のビットノード記憶手段６に相当する。ビット関数ユニット２５及びビットノード選択ユニット３１は、図６のビットノード演算手段１１に相当する。
【０１３８】
図７は、図６の各行処理モジュール２０の詳細な構成を表す図である。６組の検査ノード・メモリバンク２２は、信頼度βを記憶するためのβメモリバンク２２ａ、及びパリティ検査行列Ｈにおけるβメモリバンク２２ａ内の各信頼度の位置（以下「要素座標」という。）の情報を記憶する要素座標メモリバンク２２ｂの組から構成されている。
【０１３９】
検査関数ユニット２３は、６つの入力レジスタ３５、セレクタ３６、最小値演算器３７、排他論理和回路３８、フリップフロップ３９、６つのマルチプレクサ４０、及び６つの出力レジスタ４１を備えている。
【０１４０】
検査ノード選択ユニット３０は、コントローラ４２、遅延レジスタ４３、デマルチプレクサ４４、第１アドレス・レジスタ４５、第２アドレス・レジスタ４６、及びマルチプレクサ４７を備えている。
【０１４１】
検査ノード選択ユニット３０の第１アドレス・レジスタ４５には、優先度レベルが１の行の信頼度β及びその要素座標が格納された、検査ノード・メモリバンク２２内のアドレスが記憶されている。また、第２アドレス・レジスタ４６には、優先度レベルが０の行の信頼度β及びその要素座標が格納された、検査ノード・メモリバンク２２内のアドレスが記憶されている。尚、第１アドレス・レジスタ４５及び第２アドレス・レジスタ４６は、シフト・レジスタにより構成されている。
【０１４２】
内部接続線２６を介して、各ビット関数ユニット２５から入力される信頼度β及びその要素座標が入力され、各βメモリバンク２２ａ及び要素座標メモリバンク２２ｂに保存される。
【０１４３】
図３より、第１区画行のブロックにおける１つの行処理では、６つの列ブロックから伝搬される信頼度β（ｉ１（１），ｊ（１１）），…，β（ｉ１（１），ｊ（１６））から計算するため、行処理モジュール２０の検査ノード・メモリバンク２２には、これらを保持する６つのβメモリバンク２２ａが用意されている。それぞれの列ブロックはｐ列のビットノードからなるため、各βメモリバンク２２ａはｐワードのデータを保持する。このβメモリバンク２２ａは、各行ブロックにおける行番号をアドレスとして、その行番号に対応する列から算出された信頼度βを出力する。
【０１４４】
また、本実施例では、パリティ検査行列の各ブロックがランダムに構成された検査行列に対応するため、行番号の入力アドレスに対して対応するパリティ検査行列の非零要素の列番号を出力する要素座標メモリバンク２２ｂも用意されている。
【０１４５】
各検査ノードにおける行処理演算を実行する場合、まず、検査ノード選択ユニット３０が検査ノード・メモリバンク２２から行処理を行う検査ノードにおける信頼度β及びその要素座標を選択する。
【０１４６】
この場合、検査ノード選択ユニット３０は、優先度レベル１の行を選択する時には、マルチプレクサ４７の接続を第１アドレス・レジスタ４５の入力側に切り替える。そして、第１アドレス・レジスタ４５から順次アドレス（行番号）を出力する。また、優先度レベル１の行を選択する時には、検査ノード選択ユニット３０は、マルチプレクサ４７の接続を第２アドレス・レジスタ４６の入力側に切り替える。そして、第２アドレス・レジスタ４６から順次アドレス（行番号）を出力する。
【０１４７】
第１アドレス・レジスタ４５又は第２アドレス・レジスタ４６から出力されたアドレスｍは、各検査ノード・メモリバンク２２及び遅延レジスタ４３に入力される。各検査ノード・メモリバンク２２は、入力されたアドレスｍに格納された信頼度βｍｎ及びその要素座標を出力する。これにより、優先度に応じて選択された行の信頼度βｍｎが検査関数ユニット２３に出力される。なお、選択された信頼度βｍｎの要素座標は、内部接続線２７を介して、タナーグラフの内部辺で接続された列処理モジュール２１へ直接出力される。
【０１４８】
検査関数ユニット２３においては、入力された信頼度βｍｎに基づき、信頼度αｍｎが式（１９），（２３）に従って計算され、出力される。出力された信頼度αｍｎは、内部接続線２７を介して、タナーグラフの内部辺で接続された列処理モジュール２１へ出力される。また、このとき、検査関数ユニット２３は、選択された行の優先度の決定のための式（３２）の左辺括弧内の｜βｍｎ｜の最小値の計算も行う。そして、この｜βｍｎ｜の最小値は検査ノード選択ユニット３０のコントローラ４２に出力される。
【０１４９】
コントローラ４２は、入力された｜βｍｎ｜の最小値と閾値Ｔαとを比較して式（３２）に従って、デマルチプレクサ４４の選択方向を切り換える。すなわち、｜βｍｎ｜の最小値が閾値Ｔα以上の場合、デマルチプレクサ４４は第１アドレス・レジスタ４５を選択する。これにより、遅延レジスタ４３に格納されたアドレスｍは、優先度レベルが１の第１アドレス・レジスタ４５に格納される。｜βｍｎ｜の最小値が閾値Ｔα未満の場合、デマルチプレクサ４４は第２アドレス・レジスタ４６を選択する。これにより、遅延レジスタ４３に格納されたアドレスｍは、優先度レベルが０の第２アドレス・レジスタ４６に格納される。
【０１５０】
検査関数ユニット２３においては、信頼度βｍｎが入力された場合、ミニマムサム・アルゴリズムを実行する。まず、入力された信頼度｛βｍｎ｜ｎ∈Ａ（ｍ）｝は、入力レジスタ３５に一旦格納される。セレクタ３６は、入力レジスタ３５に格納された信頼度βｍｎを順次選択する。排他論理和回路３８及びフリップフロップ３９は、式（１９）の左辺第１項の符号の計算を実行する。また、最小値演算器３７は、式（２３）に従って、｜β｜の最小値と２番目の最小値を求める。そして、何れかの値を信頼度αとして６つの列処理モジュール２１へ伝搬する。尚、優先度ｒｍの判定で用いる｜βｍｎ｜の最小値は、式（２３）の計算において同時に得られるためこれを利用する。
【０１５１】
図８は、図６の各列処理モジュール２１の詳細な構成を表す図である。３組のビットノード・メモリバンク２４は、信頼度αを記憶するためのαメモリバンク２４ａ、及びパリティ検査行列Ｈにおけるαメモリバンク２４ａ内の各信頼度αの要素座標の情報を記憶する要素座標メモリバンク２４ｂの組から構成されている。
【０１５２】
ビット関数ユニット２５は、入力レジスタ５０、加算器５１、中間レジスタ５２、加算器５３、及び出力レジスタ５４をそれぞれ３つずつ備えている。また、ビットノード選択ユニット３１は、アドレス・レジスタ５５及びセレクタ５６を備えている。
【０１５３】
行処理モジュール２０において、検査ノード選択ユニット３０により選択された行ｍに対して信頼度αｍｎが計算されると、同時に、その選択された行ｍに対応するパリティ検査行列内の行における零要素の列番号が要素座標メモリバンク２２ｂから出力される。この列番号は、内部接続線２７を介して列処理モジュール２１へ伝搬される。
【０１５４】
列処理モジュール２１内では、その列番号に対応する列処理が実行される。６つの列処理モジュール２１は、それぞれ３つの行処理モジュール２０から算出される信頼度αとそれに対応する列番号を受け取る。信頼度αは、対応する列番号をアドレスとして、それぞれの行ブロックに対応するαメモリバンク２４ａに上書きされる。また、列番号は、ビットノード選択ユニット３１内のアドレス・レジスタ５５に保持して、順次３つの列番号に対応する列処理を実行する。列処理モジュール２１内のビット関数ユニット２５では、３つの行処理モジュール２０から得られた新しい信頼度αから、式（２０）に従って和を求める。そして、新しい信頼度βを各行処理モジュール２０に伝搬する。
【０１５５】
ここで、１つの列処理に対して和を３つ出力するが、これを並列に実行するため、ビット関数ユニット２５内には加算器５１，５３が３つ並列に配置されている。
【０１５６】
図９に、実施例１に係るＬＤＰＣ符号検出装置１の行処理、列処理のタイミング・ダイアグラムを示す。行処理モジュール２０では、ミニサム・アルゴリズムにより、入力された｜β｜を比較するが、高速な動作周波数を得るためには、１回の比較をクロックサイクル毎に実行しなければならない。そのため、クロックサイクル数は行重みｗｒ回必要となる。また、絶対値、比較と出力を図９のようにパイプラインで構成することによって、１回の行処理にかかるクロックサイクル数は１０サイクルとなる。
【０１５７】
一方、列処理モジュール２１では、一つ前の行処理に対応する列処理をパイプライン的に並列実行する。本実施例２の列処理モジュール２１は、１回の行処理に対して３つの列処理が並列に実行されるが、これらを図９のように列処理内でパイプライン処理で実行する。これにより、合計６サイクルで列処理が完了する。
【０１５８】
従って、本実施例２のアーキテクチャでは、従来の復号と比較して３倍の列処理が必要となるが、この列処理は１回の行処理の処理サイクル数を超えない。そのため、１回の復号処理では、依然として行処理がネックとなり、従来の構成と比較しても処理速度が劣ることはない。
【図面の簡単な説明】
【０１５９】
【図１】（ａ）ＬＤＰＣ符号におけるパリティ検査行列の一例と、（ｂ）そのパリティ検査行列に対応するタナーグラフを示す図である。
【図２】部分並列ＬＤＰＣ復号で用いるレギュラーＬＤＰＣ符号のパリティ検査行列の区分け構造を表す図である。
【図３】（３，６）レギュラーＬＤＰＣ符号のパリティ検査行列を表す図である。
【図４】本発明の実施例１に係るＬＤＰＣ符号検出装置１の構成を表すブロック図である。
【図５】実施例１に係るＬＤＰＣ符号検出装置１の動作を表すフローチャートである。
【図６】実施例２に係るＬＤＰＣ符号検出装置１のアルゴリズム実行エンジン１５部分のハードウェア構成を表す図である。
【図７】図６の各行処理モジュール２０の詳細な構成を表す図である。
【図８】図６の各列処理モジュール２１の詳細な構成を表す図である。
【図９】実施例１に係るＬＤＰＣ符号検出装置１の行処理、列処理のタイミング・ダイアグラムである。
【符号の説明】
【０１６０】
１ ＬＤＰＣ符号検出装置
２ 受信値記憶手段
３ ノード初期化手段
４ 受信値対数尤度演算手段
５ 検査ノード記憶手段
６ ビットノード記憶手段
７ 検査ノード選択手段
８ 検査ノード演算手段
９ 優先度更新手段
１０ 優先度記憶手段
１１ ビットノード演算手段
１２ 硬判定手段
１３ パリティ判定手段
１５ アルゴリズム実行エンジン
２０ 行処理モジュール
２０−１，２０−２，２０−３ 行処理モジュール
２１−１，２１−２，２１−３，２１−４，２１−５，２１−６ 列処理モジュール
２１ 列処理モジュール
２２ 検査ノード・メモリバンク
２２ａ βメモリバンク
２２ｂ 要素座標メモリバンク
２３ 検査関数ユニット
２４ ビットノード・メモリバンク
２４ａ αメモリバンク
２４ｂ 要素座標メモリバンク
２５ ビット関数ユニット
２６，２７ 内部接続線
２８ 入力線
２９ 出力線
３０ 検査ノード選択ユニット
３１ ビットノード選択ユニット
３５ 入力レジスタ
３６ セレクタ
３７ 最小値演算器
３８ 排他論理和回路
３９ フリップフロップ
４０ マルチプレクサ
４１ 出力レジスタ
４２ コントローラ
４３ 遅延レジスタ
４４ デマルチプレクサ
４５ 第１アドレス・レジスタ
４６ 第２アドレス・レジスタ
４７ マルチプレクサ
５０ 入力レジスタ
５１ 加算器
５２ 中間レジスタ
５３ 加算器
５４ 出力レジスタ
５５ アドレス・レジスタ
５６ セレクタ
【技術分野】
【０００１】
本発明は、低密度パリティ検査（low density parity check：以下「ＬＤＰＣ」という。）符号を用いて受信値から送信符号を検出する符号検出技術に関する。
【背景技術】
【０００２】
ＬＤＰＣ符号は、１９６０年代にGallagerによって発案され（非特許文献１参照）、１９９０年代後半にMacKayやNealらによって再発見された符号である。その符号特性はShannonの限界に迫ることが知られており、次世代の誤り訂正符号として有望視されている（非特許文献２，３参照）。
【０００３】
ＬＤＰＣ符号は復号法としてサムプロダクト（Sum-Product）アルゴリズムを適用することにより、線形時間での復号と、優れた符号特性を達成することができる。このサムプロダクト・アルゴリズムは、パリティ・ビット数分の行処理と符号ビット数分の列処理からなるが、各行、各列処理は独立に計算してもよいことから、ハードウェアの並列実装に適している。
【０００４】
以下、ＬＤＰＣ符号とその復号法について簡単に説明する。ＬＤＰＣ符号は、非常に疎な検査行列により定義される線形符号である。ＬＤＰＣ符号のパリティ検査行列による検査式の例を式（１）に示す。
【０００５】
【数１】
【０００６】
ＬＤＰＣ符号により符号化された情報源符号は、通信路を経て受信値（ｙ１，ｙ２，…，ｙ９）となり、検査行列式（１）により誤りの有無が検査される。ここで、ＬＤＰＣ符号を定義する検査行列式（１）は、図１に示すタナーグラフ（Tanner graph）で表現される。このタナーグラフは符号長分のビットノードｂ１，ｂ２，…，ｂ９と検査ビット数分の検査ノードｃ１，ｃ２，…，ｃ６によって構成され、２種類のノードは検査行列式（１）の１の位置によって枝（以下「内部辺」という。）で接続される。受信符号に誤りが生じた場合には、図１のタナーグラフに受信値（ｙ１，ｙ２，…，ｙ９）を入力し、サムプロダクト・アルゴリズムを実行する。
【０００７】
サムプロダクト・アルゴリズムは、タナーグラフにおける信頼度を表す値αｍｎ，βｍｎを算出し、これらの信頼度を互いのノードで繰り返し交換しながら誤り訂正を実行するアルゴリズムである。信頼度を表す値αｍｎ，βｍｎとしては、確率量や対数尤度比などが用いられる。
【０００８】
タナーグラフの各検査ノードからビットノードへの内部辺は、検査行列の各行成分に対応し、各検査ノードで算出される信頼度αｍｎは検査ノードからビットノードへ伝搬される。この操作を「行処理」という。また、タナーグラフの各ビットノードから検査ノードへの内部辺は、検査行列の各列成分に対応し、各ビットノードで算出される信頼度βｍｎはビットノードから検査ノードへ伝搬される。この操作を「列処理」という。
【０００９】
以下ではサムプロダクト・アルゴリズムの詳細を説明するが、その前に、本明細書において使用する用語の定義を行う。
【００１０】
〔定義１〕（事前確率、事後確率、外部確率）
事象Ｂが生起する確率をＰ（Ｂ）と記す。事象Ａが起こったことが既知であるとき、事象Ｂが生起する条件付確率をＰ（Ｂ｜Ａ）と記す。このとき、ヘイズの定理より、式（２）が成立する。このとき、Ｐ（Ｂ）を「事前確率」、Ｐ（Ｂ｜Ａ）を「事後確率」、Ｐ（Ａ｜Ｂ）を「外部確率」という。
【００１１】
【数２】
（定義終わり）
【００１２】
〔定義２〕（レギュラーＬＤＰＣ符号、イレギュラーＬＤＰＣ符号）
ＬＤＰＣ符号のパリティ検査行列Ｈのｍ行目における非零要素の数（以下「行重み」という。）をｗｒ、ｎ列目における非零要素の数（以下「列重み」という。）をｗｃと記す。行重みｗｒが各行において均一で且つ列重みｗｃが各列において均一であるパリティ検査行列Ｈを持つＬＤＰＣ符号を「レギュラーＬＤＰＣ符号（regular LDPC code）」という。レギュラーＬＤＰＣ符号以外のＬＤＰＣ符号を「イレギュラーＬＤＰＣ符号（irregular LDPC code）」という。
（定義終わり）
【００１３】
〔定義３〕（非零成分のインデックス集合）
ＬＤＰＣ符号のパリティ検査行列を
【００１４】
【数３】
と表す。パリティ検査行列の列のインデックス集合｛１，２，…，Ｎ｝の部分集合Ａ（ｍ）及び行のインデックス集合｛１，２，…，Ｍ｝の部分集合Ｂ（ｎ）を式（４）及び式（５）により定義する。Ａ（ｍ），Ｂ（ｎ）を「非零成分のインデックス集合」という。
【００１５】
【数４】
（定義終わり）
【００１６】
〔定義４〕（Gallagerのｆ関数）
以下の式（６）で定義される関数ｆ（ｘ）を「Gallagerのｆ関数」という。
【００１７】
【数５】
（定義終わり）
【００１８】
〔定理１〕
Gallagerのｆ関数について、以下の関係が成立する。
【００１９】
【数６】
（定理終わり）
【００２０】
信頼度を表す値αｍｎ，βｍｎとして確率量ｒｍｎ，ｑｍｎを用いたサムプロダクト・アルゴリズムの詳細は、以下の（アルゴリズム１）に示す通りである。尚、受信値ｙｎ（ｎ＝１，２，…，Ｎ）の事前確率をｐｎｉｎｔ（ｙ）と記す。また、タナーグラフの各内部辺ｆｍｎにおいて、検査ノードｃｍからビットノードｂｎへ送られる外部確率量をｒｍｎ（ｆｍｎ）、ビットノードｂｎから検査ノードｃｍへ送られる外部確率量をｑｍｎ（ｆｍｎ）と記す。また、ビットノードｂｎにおける事後確率をｐｎｐｏｓｔ（ｙｎ）と記す。
【００２１】
〔アルゴリズム１〕（確率量を用いたサムプロダクト・アルゴリズム）
（ステップ１） ［初期化］
事前確率をｐｎｉｎｔ（ｙｎ＝０），ｐｎｉｎｔ（ｙｎ＝１）（ｎ＝１，２，…，Ｎ）とする。Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、内部辺における外部確率ｒｍｎをｒｍｎ（ｆｍｎ＝０）＝１／２，ｒｍｎ（ｆｍｎ＝１）＝１／２を初期設定し、外部確率ｑｍｎをｑｍｎ（ｆｍｎ）＝ｐｎｉｎｔ（ｙｎ）に初期設定する。また、繰り返し変数ｌを１に設定し、繰り返し最大回数をｌｍａｘに設定する。
【００２２】
（ステップ２） ［検査ノード（行処理）］
ｍ＝１，２，…，Ｍの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（８）（９）により外部確率ｒｍｎ（ｆｍｎ＝０），ｒｍｎ（ｆｍｎ＝１）を更新する。
【００２３】
【数７】
【００２４】
（ステップ３） ［ビットノード（列処理）］
ｎ＝１，２，…，Ｎの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（１０）（１１）により外部確率ｑｍｎ（ｆｍｎ＝０），ｑｍｎ（ｆｍｎ＝１）を更新する。
【００２５】
【数８】
【００２６】
（ステップ４） ［一時推定語の計算］
ｎ＝１，２，…，Ｎについて、式（１３）（１４）により事後確率ｐｎｐｏｓｔ（ｙｉ＝０），ｐｎｐｏｓｔ（ｙｉ＝１）を算出し、式（１６）により一時推定語ｙｎ＾を計算する。
【００２７】
【数９】
【００２８】
（ステップ５） ［パリティ検査］
一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）が以下のパリティ検査式（１７）を満たすか検査する。満たせばアルゴリズム終了。
【００２９】
【数１０】
【００３０】
（ステップ６） ［繰り返し回数カウント］
ｌ≦ｌｍａｘならばｌ←ｌ＋１とし、（ステップ２）へ。
ｌ＞ｌｍａｘならば、復号エラーとなり一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）を出力してアルゴリズムを終了。
（アルゴリズム１終わり）
【００３１】
また、信頼度を表す値αｍｎ，βｍｎとして対数尤度比ＬＬＲ（ｙ）＝ｌｎ（ｐ（ｙ＝０）／ｐ（ｙ＝１））を用いたサムプロダクト・アルゴリズムの詳細は、以下の（アルゴリズム２）に示す通りである。
【００３２】
〔アルゴリズム２〕（対数尤度比を用いたサムプロダクト・アルゴリズム）
（ステップ１） ［初期化］
ｎ＝１，２，…，Ｎに対して、ｙｎからλｎを式（１８）により算出する。式（１８）においてσは通信路の状態によって適宜設定される定数である。そして、Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、対数尤度比βｍｎをλｎに初期設定する（βｍｎ＝λｎ）。また、繰り返し変数ｌを１に設定し（ｌ＝１）、繰り返し最大回数をｌｍａｘに設定する。
【００３３】
【数１１】
【００３４】
（ステップ２） ［検査ノード（行処理）］
ｍ＝１，２，…，Ｍの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（１９）により対数尤度比αｍｎを更新する。ここで、ｆ（ｘ）はGallagerのｆ関数である。
【００３５】
【数１２】
【００３６】
（ステップ３） ［ビットノード（列処理）］
ｎ＝１，２，…，Ｎの順にＨｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（２０）により対数尤度比βｍｎを更新する。
【００３７】
【数１３】
【００３８】
（ステップ４） ［一時推定語の計算］
ｎ＝１，２，…，Ｎについて、式（２１）により一時推定語ｙｎ＾を計算する。
【００３９】
【数１４】
【００４０】
（ステップ５） ［パリティ検査］
一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）が以下のパリティ検査式（２２）を満たすか検査する。満たせばアルゴリズム終了。
【００４１】
【数１５】
【００４２】
（ステップ６） ［繰り返し回数カウント］
ｌ≦ｌｍａｘならばｌ←ｌ＋１とし、（ステップ２）へ。
ｌ＞ｌｍａｘならば、復号エラーとなり一時推定語（ｙ１＾，ｙ２＾，…，ｙＮ＾）を出力してアルゴリズムを終了。
（アルゴリズム２終わり）
【００４３】
（アルゴリズム２）において、Gallagerのｆ関数をハードウェアで実装する場合、一般的にはルックアップ・テーブルによる表引き、線形補完といった方法が採られる。そのため、ハードウェア・コストのかかる回路となる。そこで、このｆ関数を近似するミニサム（min-sum）アルゴリズムが広く適用されている。Gallagerのｆ関数はｘ＞０のとき単調減少関数となり、特にｘの値が小さいときの出力が支配的となる。従って、式（１９）のｆ関数部を次の式（２３）で近似することができる。
【００４４】
【数１６】
【００４５】
式（２３）の第３項の変形は（定理１）を利用している。このミニサム・アルゴリズムを用いれば、加算、最小、正負の判定、及び正負の符号乗算のみで復号が可能となり、復号用ハードウェアにおける行処理演算ユニットの並列配置が十分に可能となる。
【００４６】
次に、従来のＬＤＰＣ復号器のハードウェアの実装について説明する。ＬＤＰＣ復号器のハードウェアへの実装については、非特許文献４〜８において報告されている。非特許文献４，５に記載されたＬＤＰＣ復号器は完全並列ＬＤＰＣ復号器（Full-Parallel LDPC Decoder）と呼ばれ、各行、各列処理用の演算ユニットをすべて実装し、すべての演算ユニットは、ＬＤＰＣ符号の検査行列に従って完全に結線されている。この実装法は復号器の処理性能を得る最も単純な方法であるが、符号長の大きなＬＤＰＣ符号に対しては極めて困難であるため、ハードウェアの実装が難しい。
【００４７】
このことから、ハードウェアの実装と処理性能の両面から見ると部分並列実装（Partial-Parallel LDPC Decoder）が最も有力かつ実用的な実装法であり、非特許文献６〜８などで報告されている。
【００４８】
非特許文献７，８等でみられる従来の部分並列ＬＤＰＣ復号器（Partial-Parallel LDPC Decoder）では、行重みｗｒと列重みｗｃが一定であるレギュラーＬＤＰＣ符号のパリティ検査行列に対し、（アルゴリズム２）の（ステップ２）の行処理と（ステップ３）の列処理を独立に並列実行する。
【００４９】
更に、（ステップ２）においては、Ｍ個の検査ノードを列重みｗｃ個に分割し、ｗｃ個の検査ノードを並列に処理する。（ステップ３）においては、Ｎ個のビットノードを行重みｗｒ個に分割しｗｒ個のビットノードを並列に処理する。このように、行処理、列処理をそれぞれ列重み、行重みで分割するために、レギュラーＬＤＰＣ符号のパリティ検査行列を図２のように区分けして構成する（非特許文献８参照）。
【００５０】
図２は、１区画がｐ×ｐ個の要素からなる部分行列（以下「ブロック」という。）を横にｗｒ個、縦にｗｃ個並べて、ｗｒ×ｗｃ個のブロックから、縦Ｍ行、横Ｎ列のパリティ検査行列が構成されている。各ブロック内の斜線は、ブロック内における１の要素の位置を表している。図２の斜線は、各ブロックにおいて、対角成分が１である単位行列の各行を規則的に右シフトしている。シフトによってあふれたビットはブロック内の最左列に挿入している。このように構成することで、行重み、列重みがそれぞれ横のブロック数ｗｒと縦のブロック数ｗｃとなるレギュラーＬＤＰＣ符号用のパリティ検査行列が得られる。図２の例では、行重みｗｒ＝６、列重みｗｃ＝３の（３，６）レギュラーＬＤＰＣ符号のパリティ検査行列である。
【００５１】
このように規則的に１を配置することによって、図１のタナーグラフにおいて、信頼度情報を交換するノード間の結線情報をメモリに記憶しておく必要がなくなる。
【００５２】
ここで、パリティ検査行列をランダムに構成したい場合には、規則的に生成した各ブロック内でランダムに列置換，行置換を実行すれば、ｗｃ並列の行処理とｗｒ並列の列処理が可能なパリティ検査行列が維持できる。この場合は、復号器は、パリティ検査行列の１の要素の位置を記憶するメモリが必要となる。
【特許文献１】特開２００５−４５７３５号公報
【非特許文献１】R. G. Gallager, Low-Density Parity-Check Codes, MIP Press, Cambridge, MA, 1963.
【非特許文献２】D. J. C. MacKay, "Good error-correcting codes based on very sparse matrices," IEEE Trans, on Information Theory, Vol.47, pp.498-519, 2001.
【非特許文献３】S.Y. Chung, G.P. Forney Jr., T.J. Richardson, R.L. Urbanke, "On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit," IEEE Communications letters, Vol.5, No.2, Feb. 2001.
【非特許文献４】A. Blanksby and C. Howland, "A 690-mW 1-Gbps 1024-b, rate-1/2 Low-Density Parity-Check Code Decoder," IEEE Journal of Solid State Circuits, Vol.37, pp.404-412, Mar., 2002.
【非特許文献５】E. Liao, E. Yeo and B. Nikolie, "Low-density parity-check code constructions for hardware implementation," Proceedings 2004 IEEE International Conference on Communications, ICCf04y Paris, pp.2573-2577, June, 2004.
【非特許文献６】Y. Chen and D. Hocevar, "A FPGA and ASIC Implementation of Rate 1/2 8088-b Irregular Low Density Parity Check Decoder," IEEE Global Telecommunications Conference, GLOBECOM'QS, pp.113-117, 2003.
【非特許文献７】M. Mansour and N. Shanbhag, "Low Power VLSI Decoder Architectures for LDPC Codes," Proceedings of the International Symposium on Low Power Electronics and Design, pp.284-289, 2002.
【非特許文献８】Marjan Karkooti and Joseph R. Cavallaro, "Semi-Parallel Reconfigurable Architectures for Real-Time LDPC Decoding," IEEE Proceedings of International Conference on Information Technology: Coding and Computing, ITCC'04,
【非特許文献９】T.J. Richardson and R,L. Urbanke, "The capacity of low-density parity-check codes under message-passing decoding", IEEE Trans, on Information Theory, vol.42, no.2, pp.599-618, 2001.
【発明の開示】
【発明が解決しようとする課題】
【００５３】
ここで、実用的な復号用ハードウェアを実装するために、一般的に必要とされる手続きは、以下の３点に要約される。
【００５４】
（１）行処理、列処理で扱う少数中間値の量子化。
（２）ハードウェア規模削減を目的とする、ミニサム（min-sum）アルゴリズムを用いた行処理の近似。
（３）行処理、列処理の各演算ユニットの結線を簡易にするパリティ検査行列の利用。
【００５５】
上記（１）（２）により、誤り訂正が完了するまで繰り返し実行される復号処理の計算精度が劣化する。また、（３）により、利用可能な検査行列が限定されてしまう。そのため、ランダムに構成された理想的なＬＤＰＣ符号（非特許文献９参照）への対応が難しい。結果的に、上記の手続きを適用したハードウェアによる復号では、復号処理が収斂するまでにかかる繰り返し回数が増加する。加えて、ＬＤＰＣ復号の復号特性の劣化も招く。
【００５６】
非特許文献５〜８に記載の従来のＬＤＰＣ復号用のハードウェアも、上記の手続きを適用して実用的なハードウェアを実現しているが、これらの問題点に関しては考慮されていない。
【００５７】
そこで、本発明の目的は、行処理、列処理で扱う中間値である信頼度情報の伝搬効率を改善することにより、復号が収斂するための繰り返し回数が少なく復号特性に優れたＬＤＰＣ符号検出技術を提供することを目的とする。
【課題を解決するための手段】
【００５８】
〔１〕本発明の基本的な考え方
上記目的を達成するために、本発明においては、以下の２つの手法を導入することにより、復号用ハードウェアにおける信頼度の伝搬効率を改善する。
【００５９】
（１）行処理、列処理を独立に実行するのではなく、各行処理に連動してその検査ノードに属するビットノードの列処理をパイプライン的に実行することで、信頼度の伝搬効率を改善する。
（２）各行処理に対し、その検査ノードに属するビットノードの信頼度の高さで分類し、信頼度の高い検査ノードから順に行処理を実行する。
【００６０】
上記従来の部分並列ＬＤＰＣ復号器では、図２における各ブロックの行処理と列処理をそれぞれ１行１列目から順に並列実行するため、信頼度の伝搬において以下の点で効率が悪い。
【００６１】
（ａ）パリティ検査行列（図２）の「１」の要素は各ブロックによって位置がまったくずれているため、行処理、列処理を１行１列目から順番に実行すると、各ブロックの行処理による信頼度の更新位置と列処理による信頼度の更新位置がずれる。従って、行処理の更新結果が列処理に反映されるタイミングはすべて異なり、その反映が遅れるブロックもある。
【００６２】
（ｂ）受信符号における信頼度の高いビットは、符号毎に異なるため、その信頼度が高いビットが計算に含まれる順番も受信符号毎に異なる。
【００６３】
これに対し、本発明では、行処理と列処理の信頼度の伝搬効率を改善する手法として以下の２つの手法を導入する。
【００６４】
（Ａ）各行処理に連動してその検査ノードに属するビットノードの列処理をパイプライン的に並列実行することで、信頼度の伝搬効率を改善する。
（Ｂ）各行処理に対し、その検査ノードに属するビットノードの信頼度の高さで分類し、信頼度の高い検査ノードから順に行処理を実行する。
【００６５】
これらの手法を図３を用いて説明する。図３は（３，６）レギュラーＬＤＰＣ符号のパリティ検査行列を表し、図２と同様にブロックに区分けされている。また、各ブロック内の斜線は、図２と同様、ブロック内における１の要素の位置を表している。
【００６６】
手法（Ａ）により、行処理は、まず図３の縦に並ぶ３つのブロックに対して、第ｉ１（１），ｉ１（２），ｉ１（３）行目を同時に実行する。この行処理によって、信頼度α（ｉ１（１），ｊ（１１）），…，α（ｉ１（１），ｊ（１６）），α（ｉ１（２），ｊ（２１）），…，α（ｉ１（２），ｊ（２６）），α（ｉ１（３），ｊ（３１）），…，α（ｉ１（３），ｊ（３６））が更新される。
【００６７】
次に、各ブロックで更新されたαに対応する列処理をすべて実行する。例えば、図３の第１行１列ブロックでは、α（ｉ１（１），ｊ（１１））が更新され、第２行１列ブロックでは、α（ｉ１（２），ｊ（２１））が更新され、第３行１列ブロックでは、α（ｉ１（３），ｊ（３１））が更新される。従って、第１列目のブロックで更新されたαに対応する列は第１列ブロック内の第ｊ（１１），ｊ（２１），ｊ（３１）列目であり、これらのすべての列に対して列処理を実行する。この処理によって、第ｊ（１１）列目の処理によるβ（ｉ１（１），ｊ（１１）），β（ｉ３（２１），ｊ（１１）），β（ｉ２（３１），ｊ（１１））と、第ｊ（２１）列目の処理によるβ（ｉ２（１１），ｊ（２１）），β（ｉ１（２），ｊ（２１）），β（ｉ３（３１），ｊ（２１））と、第ｊ（３１）列目の処理によるβ（ｉ３（１１），ｊ（３１）），β（ｉ２（２１），ｊ（３１）），β（ｉ１（３），ｊ（３１））との信頼度が更新される。
【００６８】
手法（Ｂ）では、まず、各行処理に対して、その検査ノードに属するビットノードに向けた信頼度αの大きさで分類する。信頼度αは、検査ノードからビットノードへ伝搬され、信頼度αを受け取ったビットノードは、（アルゴリズム２）の（ステップ４）で、他の検査ノードから伝搬される信頼度αとの総和式（２１）で、そのビットの推定語を算出する。ビットの推定語は総和式（２１）の符号で判定するため、総和の絶対値が大きいときは、特に信頼できる判定結果であるといえる。
【００６９】
ここで、総和の要素は検査ノードから伝搬される信頼度αであることから、行処理で算出されるαの値が或る閾値を超えた値であった場合は、その検査ノードは高い信頼度を伝搬するノードであるとする。そして、高い信頼度は早めに伝搬されると、信頼度の伝搬効率が改善されると考えられる。そこで、高い信頼度を伝搬する検査ノードに対する行処理を先に処理することとする。
【００７０】
ここで、ミニサム・アルゴリズムを利用した行処理は、式（２３）となる。つまり、この行処理によって、集合ｎ∈Ａ（ｍ）に関する｜βｍｎ｜の最小値か２番目の最小値かの何れかが信頼度αとして伝搬される。
【００７１】
そこで、行処理で算出される信頼度の高さは、以下の式（２４）で判定する。ここで、信頼度の高さの閾値をＴαとする。
【００７２】
【数１７】
【００７３】
式（２４）で閾値以上のときは信頼度が高く、下回るときは信頼度が低いとして、各検査ノードを２つに分類する。この判定式で信頼度が高い値を伝搬する検査ノードであると判定された時は、次の繰り返しの行処理において、先に実行される。尚、この判定は、すべての検査ノードに対して、行処理の繰り返し毎に実行される。
【００７４】
また、式（２４）では各検査ノードの優先度を２つのランクに分類する場合で説明したが、一般に、３以上のランクに優先度の分類を行うようにしてもよい。
【００７５】
〔２〕本発明の構成
本発明に係るＬＤＰＣ符号検出装置の第１の構成は、低密度パリティ検査（以下「ＬＤＰＣ」という。）符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収斂判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値からの符号検出を行うＬＤＰＣ符号検出装置において、前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段；前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段；前記各検査ノードの優先度を記憶する優先度記憶手段；すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択手段；前記検査ノード選択手段が選択する前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき、当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出し、前記ビットノード記憶手段内の対応する信頼度αを更新する検査ノード演算手段；前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき信頼度が大きい順に当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新手段；及び、前記ビットノード記憶手段内の信頼度αが更新された場合、前記パリティ検査行列における信頼度αの更新された要素と同じ列に属するすべての非零要素に対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算手段；を備えたことを特徴とする。
【００７６】
この構成により、検査ノード演算手段が当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを更新すると、ビットノード演算手段により、パリティ検査行列における信頼度αが更新された要素と同列の非零要素に対応する各ビットノードについて、当該ビットノードに接続する各検査ノードに向け伝搬される信頼度βがパイプライン的に更新される。これにより、各検査ノード及び各ビットノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。
【００７７】
また、各検査ノードは、優先度更新手段により、信頼度βに基づいて、信頼度が大きい順に優先度が決定される。そして、検査ノード選択手段により、優先度が高い順に、検査ノード演算手段によって信頼度αの更新を実行する検査ノードが選択される。従って、大きい信頼度βを持つ検査ノードから優先的に、各ビットノードへ信頼度情報が伝搬される。そして、その信頼度情報は、即座に（パイプライン的に）ビットノードから各検査ノードに伝搬される。このように、サムプロダクト・アルゴリズムの収斂を促進するのに寄与する信頼度情報ほど速くノード間を伝搬するため、サムプロダクト・アルゴリズムの収斂がより促進される。
【００７８】
ここで、「信頼度」としては、確率又はそれに準じた値（対数尤度比等）が使用される。
【００７９】
「優先度」とは、外部値演算手段により外部値の伝搬を行う際の優先順位を表す指標をいう。優先度更新手段が優先度を決定する方法としては、種々の方法が考えられるが、例えば、信頼度として対数尤度比を用いた場合には、式（２４）のように閾値判定を用いて尤度を複数のランクに分類することにより優先度を決定する方法を用いることができる。
【００８０】
尚、サムプロダクト・アルゴリズムの収束判定に使用する事後値の算出は、上述の式（１３）（１４）や式（２１）に示したような公知の方法が用いられる。
【００８１】
本発明に係るＬＤＰＣ符号検出装置の第２の構成は、前記第１の構成において、前記パリティ検査行列は、列方向にＭ個、行方向にＮ個の部分行列に区分けされ、各区画における部分行列の各行の非零成分の数は１個又は０個に設定されたものであり、Ｍ個の区画行の各々に対応して設けられたＭ個の前記検査ノード記憶手段、前記優先度記憶手段、前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段を備え、Ｎ個の区画列の各々に対応して設けられたＮ個の前記ビットノード記憶手段、及び前記ビットノード演算手段を備え、前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段は並列動作し、前記各区画列の前記ビットノード演算手段は並列動作することを特徴とする。
【００８２】
この構成により、図３のように、部分行列（以下「ブロック」という。）に区分けされたパリティ検査行列において、このブロック行列の行方向及び列方向に並列に信頼度伝搬の処理がされるため、サムプロダクト・アルゴリズムを高速に実行させることが可能となる。
【００８３】
本発明に係るＬＤＰＣ符号検出装置の第３の構成は、前記第２の構成において、前記各区画列の前記ビットノード演算手段は、その演算処理を、前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段の演算処理とパイプライン的に実行することを特徴とする。
【００８４】
この構成によれば、図３のように、部分行列（以下「ブロック」という。）に区分けされたパリティ検査行列において、各区画行の検査ノード選択手段、検査ノード演算手段、及び優先度更新手段により信頼度α及び優先度の演算処理が終了すると、パイプライン的に並行して各区画列のビットノード演算手段の信頼度βの演算処理が行われる。従って、各ノード間の信頼度情報の伝搬が速く、またハードウェアの待ち時間も最小限に抑えられるため、サムプロダクト・アルゴリズムを高速に実行させることが可能となる。
【００８５】
本発明に係るＬＤＰＣ符号検出装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記信頼度α，βは対数尤度比であり、前記優先度更新手段は、前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βの最小値を閾値判定で分類することにより当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新することを特徴とする。
【００８６】
このように、信頼度α，βとして対数尤度比を使用すれば、信頼度βからの優先度の決定処理の演算が容易化される。従って、ハードウェア・コストを下げ、高速化することが可能となる。
【００８７】
本発明に係るＬＤＰＣ符号検出装置の第５の構成は、前記第１乃至３の何れか一の構成において、前記検査ノード記憶手段には、前記各検査ノードｃｍに対し、当該検査ノードｃｍに接続する前記各ビットノードｂｎより伝搬される信頼度βｍｎが記憶されており、前記ビットノード記憶手段には、前記各ビットノードｂｎに対し、当該ビットノードｂｎに接続する前記各検査ノードｃｍより伝搬される信頼度αｍｎが記憶されており、前記検査ノード演算手段は、前記検査ノード選択手段が選択する前記検査ノードｃｍについて、当該検査ノードｃｍに向け伝搬される前記信頼度βｍｎに基づき、（数１８）により当該検査ノードｃｍに接続する前記各ビットノードｂｎに向け伝搬する信頼度αｍｎを算出し、前記ビットノード記憶手段内の対応する信頼度αｍｎを更新するものであり、前記優先度更新手段は、前記各検査ノードｃｍについて、（数１９）で算出されるηｍの値を２値以上に量子化して大きい順に高い優先度に決定し、前記優先度記憶手段内の対応する優先度を更新するものであり、前記ビットノード演算手段は、前記ビットノード記憶手段内の信頼度αｍｎが更新された場合、更新されたすべての信頼度αｍｎに対応する前記各ビットノードｂｎについて、当該ビットノードに接続する前記各検査ノードｃｍ’に向け伝搬する信頼度βｍ’ｎを（数２０）により算出し、前記検査ノード記憶手段内の対応する信頼度βｍ’ｎを更新するものであることを特徴とする。
【００８８】
【数１８】
【００８９】
【数１９】
【００９０】
【数２０】
【００９１】
このように、信頼度α，βとして対数尤度比を使用することにより、信頼度α，βの更新演算が式（２５）や式（２７）のように簡単化される。また、優先度更新手段による優先度の決定は、式（２６）の演算及びこれを量子化する演算となり簡略化される。
【００９２】
本発明に係るＬＤＰＣ符号検出装置の第６の構成は、前記第５の構成において、前記検査ノード演算手段及び前記優先度更新手段は、前記（数１８）及び（数１９）の演算を、それぞれ（数２１）及び（数２２）の近似式により実行することを特徴とする。
【００９３】
【数２１】
【００９４】
【数２２】
【００９５】
このように、Gallagerのｆ関数をミニサム・アルゴリズムを用いて近似化することにより、加算、最小、正負の判定、及び正負の符号乗算のみで復号が可能となる。従って、ハードウェア・コストを下げ、高速化することが可能となる。
【００９６】
本発明に係るＬＤＰＣ符号検出方法は、ＬＤＰＣ符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収斂判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値ｙからの符号検出を行うＬＤＰＣ符号検出方法において、前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段について、各信頼度βを前記受信値ｙにより初期化する検査ノード初期化ステップ；前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段について、各信頼度αを所定の初期値に初期化するビットノード初期化ステップ；前記各検査ノードの優先度を記憶する優先度記憶手段の各優先値を所定の初期値に初期化する優先値初期化ステップ；並びに、前記各検査ノード及び前記各ビットノードの間で前記信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収斂判定し送信符号の推定値を決定する推定ステップ；を備え、前記推定ステップにおいては、すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択ステップ；前記検査ノード選択ステップで選択された前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βを検査ノード記憶手段から読み出し、読み出された各信頼度βに基づき当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出する検査ノード演算ステップ；前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新ステップ；及び、前記ビットノード記憶手段内の信頼度αが更新された場合、更新されたすべての信頼度αに対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算ステップ；からなる一連の演算処理を、前記検査ノード記憶手段内の信頼度βから算出される事後値を硬判定して得られる一次推定語とパリティ検査行列の積が０となるまで繰り返し実行することを特徴とする。
【００９７】
本発明に係るプログラムは、コンピュータに読み込んで実行することにより、コンピュータを前記第１乃至６の何れか一の構成のＬＤＰＣ符号検出装置として機能させることを特徴とする。
【発明の効果】
【００９８】
以上のように、本発明によれば、検査ノードからビットノードに信頼度情報が伝搬されると、パリティ検査行列において伝搬された信頼度に対応する要素と同列の非零要素に対応する各ビットノードについて、当該ビットノードから各検査ノードに向け信頼度がパイプライン的に伝搬される。これにより、各検査ノード及び各ビットノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。更に、大きい信頼度を有する検査ノードから順に信頼度の伝搬を実行することにより、サムプロダクト・アルゴリズムの収斂を促進するのに寄与する信頼度情報ほど速くノード間を伝搬するため、サムプロダクト・アルゴリズムの収斂がより促進される。その結果、復号が収斂するための繰り返し回数が少なく復号特性に優れたＬＤＰＣ符号検出装置及びＬＤＰＣ符号検出方法を提供することができる。
【発明を実施するための最良の形態】
【００９９】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【０１００】
本実施例１においては、２元ＬＤＰＣ符号を取り扱う。図４は本発明の実施例１に係るＬＤＰＣ符号検出装置１の構成を表すブロック図である。図４において、ＬＤＰＣ符号検出装置１は、受信値記憶手段２、ノード初期化手段３、受信値対数尤度演算手段４、検査ノード記憶手段５、ビットノード記憶手段６、検査ノード選択手段７、検査ノード演算手段８、優先度更新手段９、優先度記憶手段１０、ビットノード演算手段１１、硬判定手段１２、及びパリティ判定手段１３を備えている。
【０１０１】
検査ノード記憶手段５は、図１に示したようなタナーグラフの各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）に対し、当該検査ノードｃｍに接続する各ビットノード｛ｂｎ｜ｎ∈Ａ（ｍ）｝より伝搬される信頼度｛βｍｎ｜ｎ∈Ａ（ｍ）｝を記憶する。ビットノード記憶手段６は、図１に示したようなタナーグラフの各ビットノードｂｎ（ｎ＝１，２，…，Ｎ）に対し、当該ビットノードｂｎに接続する各ビットノード｛ｂｎ｜ｎ∈Ａ（ｍ）｝より伝搬される信頼度｛βｍｎ｜ｎ∈Ａ（ｍ）｝を記憶する。優先度記憶手段１０は、各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）についての優先度を記憶する。受信値記憶手段２は、外部から入力されるＬＤＰＣ符号のＮビットの受信値（ｙ１，ｙ２，…，ｙＮ）を一時記憶する。
【０１０２】
ノード初期化手段３は、検査ノード記憶手段５及びビットノード記憶手段６内の対数尤度比βｍｎ、αｍｎの初期設定をする。また、内部変数として有する繰り返し変数ｌ及び繰り返し最大回数をｌｍａｘの初期設定をする。受信値対数尤度演算手段４は、受信値記憶手段２に一時記憶された受信値ｙｎから受信値対数尤度λｎを式（１８）により算出する。
【０１０３】
検査ノード選択手段７は、優先度記憶手段１０に記憶された優先度に基づいて、すべての検査ノードｃｍ（ｍ＝１，２，…，Ｍ）について優先度の高い順に順次選択する。
【０１０４】
検査ノード演算手段８は、検査ノード選択手段７が選択する検査ノードｃｍについて、当該検査ノードｃｍに向け伝搬される信頼度βｍｎ（ｎ∈Ａ（ｍ））に基づき、当該検査ノードｃｍに接続する各ビットノードｂｎに向け伝搬する信頼度αｍｎ（ｎ∈Ａ（ｍ））を算出し、ビットノード記憶手段６内の対応する信頼度αｍｎの値を更新する。
【０１０５】
優先度更新手段９は、各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）について、当該検査ノードｃｍに向け伝搬される信頼度βｍｎに基づき閾値判定により当該検査ノードｃｍの優先度を決定し、優先度記憶手段１０内の対応する優先度を更新する。
【０１０６】
ビットノード演算手段１１は、ビットノード記憶手段６内の信頼度αｍｎが更新された場合、パリティ検査行列Ｈにおける信頼度αｍｎの更新された要素Ｈｍｎと同じ列に属するすべての非零要素Ｈｉ，ｎ（ｉ∈Ｂ（ｎ））に対応する各ビットノードｂｉ，ｎについて、当該ビットノードｂｉ，ｎに接続する各検査ノードｃｉ，ｎに向け伝搬する信頼度βｉ，ｎを算出し、検査ノード記憶手段５内の対応する信頼度βｉ，ｎを更新する。
【０１０７】
硬判定手段１２は、ビットノード記憶手段６に記憶された信頼度αｍｎ（ｍ∈Ｂ（ｎ），ｎ∈Ａ（ｍ））及び受信値対数尤度演算手段４が出力する受信値対数尤度λｎに基づき式（２１）により一時推定語ｙｎ＾を算出する。
【０１０８】
パリティ判定手段１３は、硬判定手段１２が出力する一時推定語（ｙ１＾，ｙ２＾，…，ｙｎ＾）が式（２２）のパリティ検査式を満たすか否かの判定を行う。
【０１０９】
以上のように構成された本実施例１に係るＬＤＰＣ符号検出装置１において、以下その動作を図５のフローチャートを用いて説明する。尚、図５のフローチャートは、図３のパリティ検査行列の１つの区画行に関する処理を表すものであり、実際には各行区画において図５の処理が並列に実行されるものとする。
【０１１０】
まず、ステップＳ１において、受信値が受信値記憶手段２に入力され一時記憶されると、ノード初期化手段３は、受信値記憶手段２に一時記憶された受信値ｙｎからλｎを式（１８）により算出する。そして、Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、検査ノード記憶手段５内の信頼度βｍｎをｙｎに初期設定する。また、ビットノード記憶手段６内の信頼度αｍｎを０に初期設定する。また、内部変数として有するイテレータ（反復子）ｌを１に設定し、繰り返し最大回数をｌｍａｘに設定する。
【０１１１】
ステップＳ２において、受信値対数尤度演算手段４は、式（１８）により各受信値ｙｎ（ｎ＝１，２，…，Ｎ）に対する受信値対数尤度λｎを算出する。また、優先度記憶手段１０は、各検査ノードｃｍ（ｍ＝１，２，…，Ｍ）の優先度のランクｒｍを１に設定する。
【０１１２】
ステップＳ３において、硬判定手段１２は、受信値記憶手段２に記憶された各受信値ｙｎ（ｎ＝１，２，…，Ｎ）に基づき、式（３０）による硬判定を行い一時推定値ｙｎ＾を求める。
【０１１３】
【数２３】
【０１１４】
ステップＳ４において、パリティ判定手段１３は、ステップＳ３で得られた一時推定語ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）とパリティ検査表列Ｈに基づき、式（３１）により一時推定語ｙ＾のパリティｐａｒ（ｙ＾）を計算する。
【０１１５】
【数２４】
【０１１６】
ステップＳ５において、パリティ判定手段１３は、パリティｐａｒ（ｙ＾）は０か１かを判定する。ｐａｒ（ｙ＾）が０であれば、ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）を復号語として出力して動作を終了する。ｐａｒ（ｙ＾）が１の場合、検査ノード選択手段７を呼び出して、ステップＳ６に移行する。
【０１１７】
ステップＳ６においては、検査ノード選択手段７は、選択する優先度レベルａを１に初期化する。そして、選択する行番号（検査ノードの番号）ｍを１に初期化する。
【０１１８】
ステップＳ７において、検査ノード選択手段７は、行番号ｍの優先度ｒｍが優先度レベルａと一致するか否かを判定する。一致しない場合にはステップＳ１１に移行し、一致した場合には検査ノード選択手段７は検査ノードｃｍを選択し次のステップＳ８へ移行する。
【０１１９】
ステップＳ８において、検査ノード演算手段８は、選択された行番号ｍの検査ノードｃｍについて行処理を実行する。すなわち、検査ノード演算手段８は、Ｈｍｎ＝１を満たすすべての組（ｍ，ｎ）に対して、更新式（１９）により信頼度αｍｎを計算する。そして、ビットノード記憶手段６内の信頼度αｍｎの値を更新する。図３の例では、このときα（ｉ１（ｐ），ｊ（ｐ１）），…，α（ｉ１（ｐ），ｊ（ｐ６））（ｐ＝１，２，３）が更新される。
【０１２０】
ステップＳ９において、優先度更新手段９は、選択された行番号ｍの検査ノードｃｍの優先度ｒｍを計算し、優先度記憶手段１０内の優先度ｒｍを更新する。ここで、優先度ｒｍの計算は式（３２）により行われる。
【０１２１】
【数２５】
【０１２２】
ステップＳ１０において、ビットノード演算手段１１は、すべての更新された信頼度αｍｎの属する各列について列処理を実行する。
【０１２３】
例えば、図３の例で言うと、第ｑ区画列（ｑ＝１，２，…，６）においては、ステップＳ８でα（ｉ１（１），ｊ（１ｑ）），α（ｉ１（２），ｊ（２ｑ）），α（ｉ１（３），ｊ（３ｑ））が更新される。これらのαの属する列は、ｊ（１ｑ），ｊ（２ｑ），ｊ（３ｑ）である。従って、ビットノード演算手段１１は、第ｑ区画列の各ブロックにおいて、列ｊ（１ｑ），ｊ（２ｑ），ｊ（３ｑ）に属する非零要素の内部辺に接続するビットノードについて、信頼度βの計算を行う。すなわち、第１区画行ｑ区画列では、β（ｉ１（１），ｊ（１ｑ）），β（ｉ２（１ｑ），ｊ（２ｑ）），β（ｉ３（１ｑ），ｊ（３ｑ））の計算を行い、第２区画行ｑ区画列では、β（ｉ１（２），ｊ（２ｑ）），β（ｉ２（２ｑ），ｊ（３ｑ）），β（ｉ３（３ｑ），ｊ（１ｑ））の計算を行い、第３区画行ｑ区画列では、β（ｉ１（３），ｊ（３ｑ）），β（ｉ２（１ｑ），ｊ（１ｑ）），β（ｉ３（２ｑ），ｊ（２ｑ））の計算を行う。
【０１２４】
計算されたそれぞれの信頼度βについて、検査ノード記憶手段５内の信頼度βが更新される。尚、ビットノード演算手段１１による信頼度βの計算は、式（２０）に従って実行される。
【０１２５】
ステップＳ１１において、検査ノード選択手段７は、ｍがＭに達したか否かを判定し、ｍ＜Ｍであれば、ｍ←ｍ＋１として（ステップＳ１２）、ステップＳ７に戻る。一方、ｍ＝Ｍならば、ステップＳ１３に進む。
【０１２６】
ステップＳ１３において、検査ノード選択手段７は、ａが１であれば、ａ←０として（Ｓ１４）、ステップＳ７に戻る。また、ａが０であれば、ステップＳ３に戻る。
【０１２７】
ステップＳ３においては、硬判定手段１２は、今度は検査ノード記憶手段５に記憶された信頼度αに基づき、式（２１）による硬判定を行い一時推定値ｙｎ＾を求める。また、イテレータｌをｌ←ｌ＋１とする。
【０１２８】
ステップＳ４において、パリティ判定手段１３は、ステップＳ３で得られた一時推定語ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）とパリティ検査表列Ｈに基づき、式（３１）により一時推定語ｙ＾のパリティｐａｒ（ｙ＾）を計算する。
【０１２９】
ステップＳ５において、パリティ判定手段１３は、パリティｐａｒ（ｙ＾）は０か１かを判定する。ｐａｒ（ｙ＾）が０であれば、ｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）を復号語として出力して動作を終了する。また、イテレータｌがｌ＞ｌｍａｘとなった場合には、復号エラーの信号とともにｙ＾＝（ｙ１＾，ｙ２＾，…，ｙＮ＾）を出力し、動作を終了する。ｐａｒ（ｙ＾）が１で且つｌ≦ｌｍａｘの場合、検査ノード選択手段７を呼び出して、ステップＳ６に移行し、以下同様の動作を繰り返す。
【０１３０】
以上の動作により、検査ノード演算手段８が当該検査ノードｃｍに接続する各ビットノード｛ｂｎ｜ｎ∈Ａ（ｍ）｝に向け伝搬する信頼度αｍｎを更新すると、ビットノード演算手段１１により、パリティ検査行列Ｈにおける信頼度αｍｎが更新された要素と同列の非零要素に対応する各ビットノード｛ｂｊ｝について、当該ビットノード｛ｂｊ｝に接続する各検査ノードに向け伝搬される信頼度｛βｋｊ｝がパイプライン的に更新される。これにより、各検査ノード及び各ビットノード間を信頼度が効率よく伝搬するため、サムプロダクト・アルゴリズムの収斂が促進される。
【０１３１】
また、各検査ノードｃｍは、優先度更新手段９により、信頼度｛βｍｎ｝に基づいて、信頼度ｒｍが大きい順に優先度が決定される。そして、検査ノード選択手段７により、優先度ｒｍが高い順に、検査ノード演算手段８による信頼度αｍｎの更新を実行する検査ノードｃｍが選択される。従って、大きい信頼度βを持つ検査ノードから優先的に、各ビットノードへ信頼度情報が伝搬される。そして、その信頼度情報は、即座に（パイプライン的に）ビットノードから各検査ノードに伝搬される。このように、サムプロダクト・アルゴリズムの収斂を促進するのに寄与する信頼度情報ほど速くノード間を伝搬するため、サムプロダクト・アルゴリズムの収斂がより促進される。
【実施例２】
【０１３２】
実施例２では、実施例１のＬＤＰＣ符号検出装置１をより具体的にハードウェアに実装した例について説明する。
【０１３３】
図６は、実施例２に係るＬＤＰＣ符号検出装置１のアルゴリズム実行エンジン１５のハードウェア構成を表す図である。図６は、図４において点線で囲まれたアルゴリズム実行エンジン１５の部分に相当する。尚、本実施例においては、行重みｗｒ＝６、列重みｗｃ＝３の（３，６）レギュラーＬＤＰＣ符号のＬＤＰＣ復号装置を示しているが、行重みｗｒ，列重みｗｃに関しては容易に一般化することができる。
【０１３４】
アルゴリズム実行エンジン１５は、３つの行処理モジュール２０−１〜２０−３と６つの列処理モジュール２１−１〜２１−６を備えている。また、各行処理モジュール２０−１〜２０−３と各列処理モジュール２１−１〜２１−６の間には、図１のタナーグラフの内部辺に対応して設けられた６本の分岐した内部接続線２６及び３本の内部接続線２７が設けられている。タナーグラフの内部辺で接続された行処理モジュール２０と列処理モジュール２１同士が、各内部接続線２６，２７により接続されている。内部接続線２６は、列処理モジュール２１から行処理モジュール２０へ信頼度βを伝達する線である。内部接続線２７は、行処理モジュール２０から列処理モジュール２１へ信頼度αを伝達する線である。
【０１３５】
また、６本の内部接続線２６のそれぞれには、６本の入力線２８が接続されている。３本の内部接続線２７のそれぞれには、３本の出力線２９が接続されている。入力線２８には、各βｍｎの初期値としての受信値ｙｎが入力される。また、出力線２９からは、硬判定手段１２に対してｙｎ＾の計算に使用する信頼度αｍｎが出力される。
【０１３６】
各行処理モジュール２０は、６組の検査ノード・メモリバンク２２と、１つの検査関数ユニット２３及び検査ノード選択ユニット３０を備えている。各検査ノード・メモリバンク２２が、図４の監査ノード記憶手段５に相当する。検査関数ユニット２３は、図４の検査ノード演算手段８に相当する。検査ノード選択ユニット３０は、図４の検査ノード選択手段７、優先度更新手段９、及び優先度記憶手段１０に相当する。
【０１３７】
列処理モジュール２１は、３つのビットノード・メモリバンク２４と１つのビット関数ユニット２５及びビットノード選択ユニット３１を備えている。ビットノード・メモリバンク２４は図４のビットノード記憶手段６に相当する。ビット関数ユニット２５及びビットノード選択ユニット３１は、図６のビットノード演算手段１１に相当する。
【０１３８】
図７は、図６の各行処理モジュール２０の詳細な構成を表す図である。６組の検査ノード・メモリバンク２２は、信頼度βを記憶するためのβメモリバンク２２ａ、及びパリティ検査行列Ｈにおけるβメモリバンク２２ａ内の各信頼度の位置（以下「要素座標」という。）の情報を記憶する要素座標メモリバンク２２ｂの組から構成されている。
【０１３９】
検査関数ユニット２３は、６つの入力レジスタ３５、セレクタ３６、最小値演算器３７、排他論理和回路３８、フリップフロップ３９、６つのマルチプレクサ４０、及び６つの出力レジスタ４１を備えている。
【０１４０】
検査ノード選択ユニット３０は、コントローラ４２、遅延レジスタ４３、デマルチプレクサ４４、第１アドレス・レジスタ４５、第２アドレス・レジスタ４６、及びマルチプレクサ４７を備えている。
【０１４１】
検査ノード選択ユニット３０の第１アドレス・レジスタ４５には、優先度レベルが１の行の信頼度β及びその要素座標が格納された、検査ノード・メモリバンク２２内のアドレスが記憶されている。また、第２アドレス・レジスタ４６には、優先度レベルが０の行の信頼度β及びその要素座標が格納された、検査ノード・メモリバンク２２内のアドレスが記憶されている。尚、第１アドレス・レジスタ４５及び第２アドレス・レジスタ４６は、シフト・レジスタにより構成されている。
【０１４２】
内部接続線２６を介して、各ビット関数ユニット２５から入力される信頼度β及びその要素座標が入力され、各βメモリバンク２２ａ及び要素座標メモリバンク２２ｂに保存される。
【０１４３】
図３より、第１区画行のブロックにおける１つの行処理では、６つの列ブロックから伝搬される信頼度β（ｉ１（１），ｊ（１１）），…，β（ｉ１（１），ｊ（１６））から計算するため、行処理モジュール２０の検査ノード・メモリバンク２２には、これらを保持する６つのβメモリバンク２２ａが用意されている。それぞれの列ブロックはｐ列のビットノードからなるため、各βメモリバンク２２ａはｐワードのデータを保持する。このβメモリバンク２２ａは、各行ブロックにおける行番号をアドレスとして、その行番号に対応する列から算出された信頼度βを出力する。
【０１４４】
また、本実施例では、パリティ検査行列の各ブロックがランダムに構成された検査行列に対応するため、行番号の入力アドレスに対して対応するパリティ検査行列の非零要素の列番号を出力する要素座標メモリバンク２２ｂも用意されている。
【０１４５】
各検査ノードにおける行処理演算を実行する場合、まず、検査ノード選択ユニット３０が検査ノード・メモリバンク２２から行処理を行う検査ノードにおける信頼度β及びその要素座標を選択する。
【０１４６】
この場合、検査ノード選択ユニット３０は、優先度レベル１の行を選択する時には、マルチプレクサ４７の接続を第１アドレス・レジスタ４５の入力側に切り替える。そして、第１アドレス・レジスタ４５から順次アドレス（行番号）を出力する。また、優先度レベル１の行を選択する時には、検査ノード選択ユニット３０は、マルチプレクサ４７の接続を第２アドレス・レジスタ４６の入力側に切り替える。そして、第２アドレス・レジスタ４６から順次アドレス（行番号）を出力する。
【０１４７】
第１アドレス・レジスタ４５又は第２アドレス・レジスタ４６から出力されたアドレスｍは、各検査ノード・メモリバンク２２及び遅延レジスタ４３に入力される。各検査ノード・メモリバンク２２は、入力されたアドレスｍに格納された信頼度βｍｎ及びその要素座標を出力する。これにより、優先度に応じて選択された行の信頼度βｍｎが検査関数ユニット２３に出力される。なお、選択された信頼度βｍｎの要素座標は、内部接続線２７を介して、タナーグラフの内部辺で接続された列処理モジュール２１へ直接出力される。
【０１４８】
検査関数ユニット２３においては、入力された信頼度βｍｎに基づき、信頼度αｍｎが式（１９），（２３）に従って計算され、出力される。出力された信頼度αｍｎは、内部接続線２７を介して、タナーグラフの内部辺で接続された列処理モジュール２１へ出力される。また、このとき、検査関数ユニット２３は、選択された行の優先度の決定のための式（３２）の左辺括弧内の｜βｍｎ｜の最小値の計算も行う。そして、この｜βｍｎ｜の最小値は検査ノード選択ユニット３０のコントローラ４２に出力される。
【０１４９】
コントローラ４２は、入力された｜βｍｎ｜の最小値と閾値Ｔαとを比較して式（３２）に従って、デマルチプレクサ４４の選択方向を切り換える。すなわち、｜βｍｎ｜の最小値が閾値Ｔα以上の場合、デマルチプレクサ４４は第１アドレス・レジスタ４５を選択する。これにより、遅延レジスタ４３に格納されたアドレスｍは、優先度レベルが１の第１アドレス・レジスタ４５に格納される。｜βｍｎ｜の最小値が閾値Ｔα未満の場合、デマルチプレクサ４４は第２アドレス・レジスタ４６を選択する。これにより、遅延レジスタ４３に格納されたアドレスｍは、優先度レベルが０の第２アドレス・レジスタ４６に格納される。
【０１５０】
検査関数ユニット２３においては、信頼度βｍｎが入力された場合、ミニマムサム・アルゴリズムを実行する。まず、入力された信頼度｛βｍｎ｜ｎ∈Ａ（ｍ）｝は、入力レジスタ３５に一旦格納される。セレクタ３６は、入力レジスタ３５に格納された信頼度βｍｎを順次選択する。排他論理和回路３８及びフリップフロップ３９は、式（１９）の左辺第１項の符号の計算を実行する。また、最小値演算器３７は、式（２３）に従って、｜β｜の最小値と２番目の最小値を求める。そして、何れかの値を信頼度αとして６つの列処理モジュール２１へ伝搬する。尚、優先度ｒｍの判定で用いる｜βｍｎ｜の最小値は、式（２３）の計算において同時に得られるためこれを利用する。
【０１５１】
図８は、図６の各列処理モジュール２１の詳細な構成を表す図である。３組のビットノード・メモリバンク２４は、信頼度αを記憶するためのαメモリバンク２４ａ、及びパリティ検査行列Ｈにおけるαメモリバンク２４ａ内の各信頼度αの要素座標の情報を記憶する要素座標メモリバンク２４ｂの組から構成されている。
【０１５２】
ビット関数ユニット２５は、入力レジスタ５０、加算器５１、中間レジスタ５２、加算器５３、及び出力レジスタ５４をそれぞれ３つずつ備えている。また、ビットノード選択ユニット３１は、アドレス・レジスタ５５及びセレクタ５６を備えている。
【０１５３】
行処理モジュール２０において、検査ノード選択ユニット３０により選択された行ｍに対して信頼度αｍｎが計算されると、同時に、その選択された行ｍに対応するパリティ検査行列内の行における零要素の列番号が要素座標メモリバンク２２ｂから出力される。この列番号は、内部接続線２７を介して列処理モジュール２１へ伝搬される。
【０１５４】
列処理モジュール２１内では、その列番号に対応する列処理が実行される。６つの列処理モジュール２１は、それぞれ３つの行処理モジュール２０から算出される信頼度αとそれに対応する列番号を受け取る。信頼度αは、対応する列番号をアドレスとして、それぞれの行ブロックに対応するαメモリバンク２４ａに上書きされる。また、列番号は、ビットノード選択ユニット３１内のアドレス・レジスタ５５に保持して、順次３つの列番号に対応する列処理を実行する。列処理モジュール２１内のビット関数ユニット２５では、３つの行処理モジュール２０から得られた新しい信頼度αから、式（２０）に従って和を求める。そして、新しい信頼度βを各行処理モジュール２０に伝搬する。
【０１５５】
ここで、１つの列処理に対して和を３つ出力するが、これを並列に実行するため、ビット関数ユニット２５内には加算器５１，５３が３つ並列に配置されている。
【０１５６】
図９に、実施例１に係るＬＤＰＣ符号検出装置１の行処理、列処理のタイミング・ダイアグラムを示す。行処理モジュール２０では、ミニサム・アルゴリズムにより、入力された｜β｜を比較するが、高速な動作周波数を得るためには、１回の比較をクロックサイクル毎に実行しなければならない。そのため、クロックサイクル数は行重みｗｒ回必要となる。また、絶対値、比較と出力を図９のようにパイプラインで構成することによって、１回の行処理にかかるクロックサイクル数は１０サイクルとなる。
【０１５７】
一方、列処理モジュール２１では、一つ前の行処理に対応する列処理をパイプライン的に並列実行する。本実施例２の列処理モジュール２１は、１回の行処理に対して３つの列処理が並列に実行されるが、これらを図９のように列処理内でパイプライン処理で実行する。これにより、合計６サイクルで列処理が完了する。
【０１５８】
従って、本実施例２のアーキテクチャでは、従来の復号と比較して３倍の列処理が必要となるが、この列処理は１回の行処理の処理サイクル数を超えない。そのため、１回の復号処理では、依然として行処理がネックとなり、従来の構成と比較しても処理速度が劣ることはない。
【図面の簡単な説明】
【０１５９】
【図１】（ａ）ＬＤＰＣ符号におけるパリティ検査行列の一例と、（ｂ）そのパリティ検査行列に対応するタナーグラフを示す図である。
【図２】部分並列ＬＤＰＣ復号で用いるレギュラーＬＤＰＣ符号のパリティ検査行列の区分け構造を表す図である。
【図３】（３，６）レギュラーＬＤＰＣ符号のパリティ検査行列を表す図である。
【図４】本発明の実施例１に係るＬＤＰＣ符号検出装置１の構成を表すブロック図である。
【図５】実施例１に係るＬＤＰＣ符号検出装置１の動作を表すフローチャートである。
【図６】実施例２に係るＬＤＰＣ符号検出装置１のアルゴリズム実行エンジン１５部分のハードウェア構成を表す図である。
【図７】図６の各行処理モジュール２０の詳細な構成を表す図である。
【図８】図６の各列処理モジュール２１の詳細な構成を表す図である。
【図９】実施例１に係るＬＤＰＣ符号検出装置１の行処理、列処理のタイミング・ダイアグラムである。
【符号の説明】
【０１６０】
１ ＬＤＰＣ符号検出装置
２ 受信値記憶手段
３ ノード初期化手段
４ 受信値対数尤度演算手段
５ 検査ノード記憶手段
６ ビットノード記憶手段
７ 検査ノード選択手段
８ 検査ノード演算手段
９ 優先度更新手段
１０ 優先度記憶手段
１１ ビットノード演算手段
１２ 硬判定手段
１３ パリティ判定手段
１５ アルゴリズム実行エンジン
２０ 行処理モジュール
２０−１，２０−２，２０−３ 行処理モジュール
２１−１，２１−２，２１−３，２１−４，２１−５，２１−６ 列処理モジュール
２１ 列処理モジュール
２２ 検査ノード・メモリバンク
２２ａ βメモリバンク
２２ｂ 要素座標メモリバンク
２３ 検査関数ユニット
２４ ビットノード・メモリバンク
２４ａ αメモリバンク
２４ｂ 要素座標メモリバンク
２５ ビット関数ユニット
２６，２７ 内部接続線
２８ 入力線
２９ 出力線
３０ 検査ノード選択ユニット
３１ ビットノード選択ユニット
３５ 入力レジスタ
３６ セレクタ
３７ 最小値演算器
３８ 排他論理和回路
３９ フリップフロップ
４０ マルチプレクサ
４１ 出力レジスタ
４２ コントローラ
４３ 遅延レジスタ
４４ デマルチプレクサ
４５ 第１アドレス・レジスタ
４６ 第２アドレス・レジスタ
４７ マルチプレクサ
５０ 入力レジスタ
５１ 加算器
５２ 中間レジスタ
５３ 加算器
５４ 出力レジスタ
５５ アドレス・レジスタ
５６ セレクタ
【特許請求の範囲】
【請求項１】
低密度パリティ検査（以下「ＬＤＰＣ」という。）符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値からの符号検出を行うＬＤＰＣ符号検出装置において、
前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段；
前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段；
前記各検査ノードの優先度を記憶する優先度記憶手段；
すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択手段；
前記検査ノード選択手段が選択する前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき、当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出し、前記ビットノード記憶手段内の対応する信頼度αを更新する検査ノード演算手段；
前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき信頼度が大きい順に当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新手段；
及び、前記ビットノード記憶手段内の信頼度αが更新された場合、前記パリティ検査行列における信頼度αの更新された要素と同じ列に属するすべての非零要素に対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算手段；
を備えたＬＤＰＣ符号検出装置。
【請求項２】
前記パリティ検査行列は、列方向にＭ個、行方向にＮ個の部分行列に区分けされ、各区画における部分行列の各行の非零成分の数は１個又は０個に設定されたものであり、
Ｍ個の区画行の各々に対応して設けられたＭ個の前記検査ノード記憶手段、前記優先度記憶手段、前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段を備え、
Ｎ個の区画列の各々に対応して設けられたＮ個の前記ビットノード記憶手段、及び前記ビットノード演算手段を備え、
前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段は並列動作し、前記各区画列の前記ビットノード演算手段は並列動作すること
を特徴とする請求項１記載のＬＤＰＣ符号検出装置。
【請求項３】
前記各区画列の前記ビットノード演算手段は、その演算処理を、前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段の演算処理とパイプライン的に実行することを特徴とする請求項２記載のＬＤＰＣ符号検出装置。
【請求項４】
前記信頼度α，βは対数尤度比であり、
前記優先度更新手段は、前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βの最小値を閾値判定で分類することにより当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新すること
を特徴とする請求項１乃至３の何れか一記載のＬＤＰＣ符号検出装置。
【請求項５】
前記検査ノード記憶手段には、前記各検査ノードｃｍに対し、当該検査ノードｃｍに接続する前記各ビットノードｂｎより伝搬される信頼度βｍｎが記憶されており、
前記ビットノード記憶手段には、前記各ビットノードｂｎに対し、当該ビットノードｂｎに接続する前記各検査ノードｃｍより伝搬される信頼度αｍｎが記憶されており、
前記検査ノード演算手段は、前記検査ノード選択手段が選択する前記検査ノードｃｍについて、当該検査ノードｃｍに向け伝搬される前記信頼度βｍｎに基づき、（数１）により当該検査ノードｃｍに接続する前記各ビットノードｂｎに向け伝搬する信頼度αｍｎを算出し、前記ビットノード記憶手段内の対応する信頼度αｍｎを更新するものであり、
前記優先度更新手段は、前記各検査ノードｃｍについて、（数２）で算出されるηｍの値を２値以上に量子化して大きい順に高い優先度に決定し、前記優先度記憶手段内の対応する優先度を更新するものであり、
前記ビットノード演算手段は、前記ビットノード記憶手段内の信頼度αｍｎが更新された場合、更新されたすべての信頼度αｍｎに対応する前記各ビットノードｂｎについて、当該ビットノードに接続する前記各検査ノードｃｍ’に向け伝搬する信頼度βｍ’ｎを（数３）により算出し、前記検査ノード記憶手段内の対応する信頼度βｍ’ｎを更新するものであること
を特徴とする請求項１乃至４の何れか一記載のＬＤＰＣ符号検出装置。
【数１】
【数２】
【数３】
【請求項６】
前記検査ノード演算手段及び前記優先度更新手段は、前記（数１）及び（数２）の演算を、それぞれ（数４）及び（数５）の近似式により実行することを特徴とする請求項５記載のＬＤＰＣ符号検出装置。
【数４】
【数５】
【請求項７】
ＬＤＰＣ符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値ｙからの符号検出を行うＬＤＰＣ符号検出方法において、
前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段について、各信頼度βを前記受信値ｙにより初期化する検査ノード初期化ステップ；
前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段について、各信頼度αを所定の初期値に初期化するビットノード初期化ステップ；
前記各検査ノードの優先度を記憶する優先度記憶手段の各優先値を所定の初期値に初期化する優先値初期化ステップ；
並びに、前記各検査ノード及び前記各ビットノードの間で前記信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定する推定ステップ；
を備え、
前記推定ステップにおいては、
すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択ステップ；
前記検査ノード選択ステップで選択された前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βを検査ノード記憶手段から読み出し、読み出された各信頼度βに基づき当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出する検査ノード演算ステップ；
前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき信頼度が大きい順に当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新ステップ；
及び、前記ビットノード記憶手段内の信頼度αが更新された場合、前記パリティ検査行列における信頼度αの更新された要素と同じ列に属するすべての非零要素に対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算ステップ；
からなる一連の演算処理を、前記検査ノード記憶手段内の信頼度βから算出される事後値を硬判定して得られる一次推定語とパリティ検査行列の積が０となるまで繰り返し実行すること
を特徴とするＬＤＰＣ符号検出方法。
【請求項８】
コンピュータに読み込んで実行することにより、コンピュータを請求項１乃至６の何れか一に記載のＬＤＰＣ符号検出装置として機能させることを特徴とするプログラム。
【請求項１】
低密度パリティ検査（以下「ＬＤＰＣ」という。）符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値からの符号検出を行うＬＤＰＣ符号検出装置において、
前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段；
前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段；
前記各検査ノードの優先度を記憶する優先度記憶手段；
すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択手段；
前記検査ノード選択手段が選択する前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき、当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出し、前記ビットノード記憶手段内の対応する信頼度αを更新する検査ノード演算手段；
前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき信頼度が大きい順に当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新手段；
及び、前記ビットノード記憶手段内の信頼度αが更新された場合、前記パリティ検査行列における信頼度αの更新された要素と同じ列に属するすべての非零要素に対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算手段；
を備えたＬＤＰＣ符号検出装置。
【請求項２】
前記パリティ検査行列は、列方向にＭ個、行方向にＮ個の部分行列に区分けされ、各区画における部分行列の各行の非零成分の数は１個又は０個に設定されたものであり、
Ｍ個の区画行の各々に対応して設けられたＭ個の前記検査ノード記憶手段、前記優先度記憶手段、前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段を備え、
Ｎ個の区画列の各々に対応して設けられたＮ個の前記ビットノード記憶手段、及び前記ビットノード演算手段を備え、
前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段は並列動作し、前記各区画列の前記ビットノード演算手段は並列動作すること
を特徴とする請求項１記載のＬＤＰＣ符号検出装置。
【請求項３】
前記各区画列の前記ビットノード演算手段は、その演算処理を、前記各区画行の前記検査ノード選択手段、前記検査ノード演算手段、及び前記優先度更新手段の演算処理とパイプライン的に実行することを特徴とする請求項２記載のＬＤＰＣ符号検出装置。
【請求項４】
前記信頼度α，βは対数尤度比であり、
前記優先度更新手段は、前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βの最小値を閾値判定で分類することにより当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新すること
を特徴とする請求項１乃至３の何れか一記載のＬＤＰＣ符号検出装置。
【請求項５】
前記検査ノード記憶手段には、前記各検査ノードｃｍに対し、当該検査ノードｃｍに接続する前記各ビットノードｂｎより伝搬される信頼度βｍｎが記憶されており、
前記ビットノード記憶手段には、前記各ビットノードｂｎに対し、当該ビットノードｂｎに接続する前記各検査ノードｃｍより伝搬される信頼度αｍｎが記憶されており、
前記検査ノード演算手段は、前記検査ノード選択手段が選択する前記検査ノードｃｍについて、当該検査ノードｃｍに向け伝搬される前記信頼度βｍｎに基づき、（数１）により当該検査ノードｃｍに接続する前記各ビットノードｂｎに向け伝搬する信頼度αｍｎを算出し、前記ビットノード記憶手段内の対応する信頼度αｍｎを更新するものであり、
前記優先度更新手段は、前記各検査ノードｃｍについて、（数２）で算出されるηｍの値を２値以上に量子化して大きい順に高い優先度に決定し、前記優先度記憶手段内の対応する優先度を更新するものであり、
前記ビットノード演算手段は、前記ビットノード記憶手段内の信頼度αｍｎが更新された場合、更新されたすべての信頼度αｍｎに対応する前記各ビットノードｂｎについて、当該ビットノードに接続する前記各検査ノードｃｍ’に向け伝搬する信頼度βｍ’ｎを（数３）により算出し、前記検査ノード記憶手段内の対応する信頼度βｍ’ｎを更新するものであること
を特徴とする請求項１乃至４の何れか一記載のＬＤＰＣ符号検出装置。
【数１】
【数２】
【数３】
【請求項６】
前記検査ノード演算手段及び前記優先度更新手段は、前記（数１）及び（数２）の演算を、それぞれ（数４）及び（数５）の近似式により実行することを特徴とする請求項５記載のＬＤＰＣ符号検出装置。
【数４】
【数５】
【請求項７】
ＬＤＰＣ符号のパリティ検査行列のタナーグラフに対応して設定された複数の検査ノード及び複数のビットノードの間で信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定するサムプロダクト・アルゴリズムを用いて、受信値ｙからの符号検出を行うＬＤＰＣ符号検出方法において、
前記各検査ノードに対し、当該検査ノードに接続する前記各ビットノードより伝搬される信頼度βを記憶する検査ノード記憶手段について、各信頼度βを前記受信値ｙにより初期化する検査ノード初期化ステップ；
前記各ビットノードに対し、当該ビットノードに接続する前記各検査ノードより伝搬される信頼度αを記憶するビットノード記憶手段について、各信頼度αを所定の初期値に初期化するビットノード初期化ステップ；
前記各検査ノードの優先度を記憶する優先度記憶手段の各優先値を所定の初期値に初期化する優先値初期化ステップ；
並びに、前記各検査ノード及び前記各ビットノードの間で前記信頼度α，βを反復伝搬させ、その過程において信頼度βから算出される事後値の硬判定値をパリティ検査行列でパリティ検査することにより収束判定し送信符号の推定値を決定する推定ステップ；
を備え、
前記推定ステップにおいては、
すべての前記検査ノードについて、前記優先度の高い順に順次選択する検査ノード選択ステップ；
前記検査ノード選択ステップで選択された前記検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βを検査ノード記憶手段から読み出し、読み出された各信頼度βに基づき当該検査ノードに接続する前記各ビットノードに向け伝搬する信頼度αを算出する検査ノード演算ステップ；
前記各検査ノードについて、当該検査ノードに向け伝搬される前記信頼度βに基づき信頼度が大きい順に当該検査ノードの優先度を決定し、前記優先度記憶手段内の対応する優先度を更新する優先度更新ステップ；
及び、前記ビットノード記憶手段内の信頼度αが更新された場合、前記パリティ検査行列における信頼度αの更新された要素と同じ列に属するすべての非零要素に対応する前記各ビットノードについて、当該ビットノードに接続する前記各検査ノードに向け伝搬する信頼度βを算出し、前記検査ノード記憶手段内の対応する信頼度βを更新するビットノード演算ステップ；
からなる一連の演算処理を、前記検査ノード記憶手段内の信頼度βから算出される事後値を硬判定して得られる一次推定語とパリティ検査行列の積が０となるまで繰り返し実行すること
を特徴とするＬＤＰＣ符号検出方法。
【請求項８】
コンピュータに読み込んで実行することにより、コンピュータを請求項１乃至６の何れか一に記載のＬＤＰＣ符号検出装置として機能させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００６−２７９３９６（Ｐ２００６−２７９３９６Ａ）
【公開日】平成１８年１０月１２日（２００６．１０．１２）
【国際特許分類】
【出願番号】特願２００５−９３９２０（Ｐ２００５−９３９２０）
【出願日】平成１７年３月２９日（２００５．３．２９）
【出願人】（８０２００００３１）財団法人北九州産業学術推進機構 (187)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成１８年１０月１２日（２００６．１０．１２）
【国際特許分類】
【出願日】平成１７年３月２９日（２００５．３．２９）
【出願人】（８０２００００３１）財団法人北九州産業学術推進機構 (187)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]