(57)【要約】【課題】復号回路を複数の部分処理回路で構成しても、複数の部分回路同士を繋ぐ配線数の増加を抑える。【解決手段】複数の入力データに対して、検査行列に基づく処理を行う処理部を備えたＬＤＰＣ復号回路であって、前記処理部は、前記検査行列を複数に分割した複数の部分検査行列にそれぞれ対応する複数の部分処理回路によって構成され、それぞれの部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての処理を行うよう構成されている。【選択図】図４
2008288710.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力データに対して、検査行列に基づく処理を行う処理部を備えたＬＤＰＣ復号回路であって、
前記処理部は、前記検査行列を複数に分割した複数の部分検査行列にそれぞれ対応する複数の部分処理回路によって構成され、
それぞれの部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての処理を行うよう構成されていることを特徴とするＬＤＰＣ復号回路。
【請求項２】
前記部分検査行列は、前記検査行列を列方向に複数に分割したものであることを特徴とする請求項１記載のＬＤＰＣ復号回路。
【請求項３】
前記部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての行処理を行うよう構成されていることを特徴とする請求項１又は２記載のＬＤＰＣ復号回路。
【請求項４】
前記部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての行処理を行うとともに、当該部分処理回路が対応する部分検査行列の非零要素についての列処理を行うよう構成されていることを特徴とする請求項１〜３のいずれかに記載のＬＤＰＣ復号回路。
【請求項５】
前記部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素における処理の演算を行うために必要とされる演算情報のうち、他の部分処理回路が有する演算情報を、当該他の部分処理回路から取得するための取得部を備えていることを特徴とする請求項１〜４のいずれかに記載のＬＤＰＣ復号回路。
【請求項６】
前記取得部は、
事前値対数比及び入力データの対数尤度比、又は
事前値対数比及び入力データの対数尤度比を用いた演算によって得られた値、
を前記演算情報として、他の部分処理回路から取得することを特徴とする請求項５記載のＬＤＰＣ復号回路。
【請求項７】
前記取得部は、他の部分処理回路が行った部分演算結果を、前記演算情報として、当該他の部分処理回路から取得するよう構成され、
前記部分演算結果は、行処理の演算又は列処理の演算における部分的な演算を前記他の部分処理回路が行った演算結果であることを特徴とする請求項５又は６記載のＬＤＰＣ復号回路。
【請求項８】
前記部分的な演算は、
事前値対数比と当該事前値対数比に対応する入力データの対数尤度比との和の絶対値を変数とするギャラガのｆ関数値に関し、部分検査行列の非零要素に対応するギャラガのｆ関数値の和を求める演算、又は
事前値対数比と当該事前値対数比に対応する入力データの対数尤度比との和の絶対値に関し、部分検査行列の非零要素に対応する前記絶対値の最小値を求める最小値演算、
を含むことを特徴とする請求項７記載のＬＤＰＣ復号回路。
【請求項９】
前記部分的な演算は、
事前値対数比と当該事前値対数比に対応する入力データの対数尤度比との和から求めた符号情報に関し、部分検査行列の非零要素に対応する符号情報の積を求める符号演算、
を含むことを特徴とする請求項７又は８記載のＬＤＰＣ復号回路。
【請求項１０】
前記情報取得部は、他の部分処理回路が対応する部分検査行列の非零要素それぞれに対応する演算情報を、当該他の部分処理回路から取得することを特徴とする請求項５〜９のいずれかに記載のＬＤＰＣ復号回路。
【請求項１１】
前記複数の部分処理回路は、列同士が入れ替えられた検査行列を、列方向に複数に分割した複数の部分検査行列にそれぞれ対応するよう構成されていることを特徴とする請求項２記載のＬＤＰＣ復号回路。
【請求項１２】
複数の入力データが、列同士が入れ替えられた検査行列に対応するように、複数の入力データ同士の入れ替えを行うデータ入替部を備えていることを特徴とする請求項１１記載のＬＤＰＣ復号回路。
【請求項１３】
前記部分処理回路は、前記複数の入力データのうち、当該部分処理回路が対応する部分検査行列についての処理を行うために必要なデータを選択するように構成されていることを特徴とする請求項１〜１２のいずれかに記載のＬＤＰＣ復号回路。
【請求項１４】
前記部分処理回路は、複数の演算情報を、共通の情報送信配線を介して、他の部分処理回路へ送信するための情報送信部を備えていることを特徴とする請求項１〜１３のいずれかに記載のＬＤＰＣ復号回路。
【請求項１５】
前記情報送信部が送信する演算情報の順序を制御する制御部を備えていることを特徴とする請求項１４記載のＬＤＰＣ復号回路。
【請求項１６】
前記制御部は、列処理が実行される列の順序に応じて、送信される行処理演算情報の順序を制御することを特徴とする請求項１５記載のＬＤＰＣ復号回路。
【請求項１７】
前記複数の部分処理回路は、行処理及び列処理を実行した結果から推定符号を判定する判定部をそれぞれ備え、
前記判定部によって判定した推定符号がそれぞれの部分処理回路から出力されることを特徴とする請求項１〜１６のいずれかに記載のＬＤＰＣ復号回路。
【請求項１８】
他の部分処理回路と協調して、複数の入力データに対して行処理を行う行処理部を備えた部分処理回路であって、
前記処理部が行処理の演算を行うために必要な行処理演算情報を、他の部分処理回路から取得する取得部と、
他の部分処理回路が行処理の演算を行うために必要な行処理演算情報を、他の部分処理回路へ送信する送信部と、
を備え、
前記取得部及び送信部によって、前記行処理演算情報を他の部分処理回路との間で交換することにより、他の部分処理回路と協調して行処理を行うように構成されている、
ことを特徴とする部分処理回路。
【請求項１９】
一つの半導体チップで構成されていることを特徴とする請求項１８記載の部分処理回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＤＰＣ復号回路及び部分処理回路に関するものである。
【背景技術】
【０００２】
誤り訂正技術の一つとして、低密度パリティ検査（ＬＤＰＣ：Low-Density Parity-Check）符号と、その復号法であるsum−product復号法とが注目されている。
このＬＤＰＣ符号では、白色ガウス通信路のシャノン（Shannon）限界まで、０．００４ｄＢという復号特性が得られることが知られている。また、sum-product復号法は、並列処理による復号処理を実行するため、符号長を長くすることができるとともに処理能力を向上させることができる。
特許文献１は、このようなＬＤＰＣ符号の復号装置の構成を開示している。
【特許文献１】特開平２００５−２６９５３５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ＬＤＰＣでは、符号長を長くすると高い訂正能力が得られる。したがって、より高い訂正能力を得るには長い符号長を処理可能な復号回路を設計すればよい。
しかし、符号長を長くするには、いくつかの問題がある。
例えば、符号長が長くなると（例えば、４０００ｂｉｔ以上）、演算量が多くなるため、集積度の限界のため一つの復号回路を一つの半導体チップで構成することが困難となる。
【０００４】
仮に、一つの復号回路を一つの半導体チップで構成したとしても、符号長さが長くなると高速で動作させる必要があり、動作速度の限界のため動作不能となることがある。例えば、１０Ｇｂ／ｓのシリアルデータを半導体チップに入力しようとすると、電気的な応答が追いつかず、動作させるのが困難となる。
【０００５】
そこで、一つの復号回路を複数の半導体チップで構成し、各半導体チップで復号処理を分散処理することが考えられる。複数の半導体チップに分けて、復号回路外部のＳ／Ｐ変換器によって、シリアルデータを各半導体チップに分けて入力すれば、一つの半導体チップについての入力速度が低下するため、高速化への対応が容易となる。
【０００６】
また、コストの面からみると、長い符号長を処理可能な復号回路を、一つの半導体チップで構成すると、高度に集積化されたチップが必要となり非常にコスト高となる。したがって、半導体チップを複数用いて復号回路を構成することは、コストの観点からも望まれる。
【０００７】
ところが、復号回路を複数の半導体チップ（部分処理回路）に分割すると、複数の半導体チップ同士を繋ぐ配線の数が問題となる。
つまり、復号回路を複数の部分処理回路に分割すれば、部分処理回路間で、処理に必要な情報を共有する必要が生じる。つまり、部分処理回路間で共有される情報をやりとりする配線が必要となる。したがって、符号長が長くなれば、共有すべき情報も増大するため、非常に多くの配線が必要となる。
よって、復号回路を分割するには、適切な分割方法が必要である。
【０００８】
例えば、単純な分割方法として、sum-product復号法の復号回路における主な機能単位で分割することを考える。前記復号回路における主な機能は、行処理と列処理である。
そこで、復号回路を、行処理を行う行処理用半導体チップと列処理を行う列処理用半導体チップとで構成したとする。
【０００９】
上記の場合、行処理用半導体チップと列処理用半導体チップの間には、少なくとも、行処理用半導体チップにおける行処理の結果である外部値対数比（αｍｎ）を、列処理用半導体チップに渡すための配線が必要である。
行処理の結果である外部値対数比の数は、符号長に応じて多くなるため、符号長が膨大になれば、膨大な数の配線が両チップ間に必要となる。この結果、符号長が長くなった場合、復号回路を複数の半導体チップ（部分処理回路）で構成することは、現実的ではなくなる。
【００１０】
そこで、本発明は、復号回路を複数の部分処理回路で構成しても、複数の部分処理回路同士を繋ぐ配線数の増加を抑えることができる新たな技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、複数の入力データに対して、検査行列に基づく処理（例えば行処理及び／又は列処理）を行う処理部を備えたＬＤＰＣ復号回路であって、前記処理部は、前記検査行列を複数に分割した複数の部分検査行列にそれぞれ対応する複数の部分処理回路によって構成され、それぞれの部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての処理を行うよう構成されている。
【００１２】
処理部を、検査行列を複数に分割した複数の部分検査行列にそれぞれ対応する複数の部分処理回路によって構成することで、処理部を行処理部と列処理部とに分割した単純な分割方法に比べて、部分処理回路同士を繋ぐ配線数の増加を抑えることができる。
【００１３】
なお、分割は、後述のように検査行列を列方向に複数に分割するほか、行方向に複数に分割してもよく、分割方向は特に限定されない。また、検査行列を直線的に分割する必要はなく、検査行列を分割する分割ラインを想定した場合、当該分割ラインがジグザグであってもよい。また、分割ラインは、行方向又は列方向から斜めに傾いていてもよい。
さらに、検査行列を分割した際、検査行列の各要素は、いずれかの部分検査行列のみに含まれている必要はなく、検査行列中のある要素が、複数の部分検査行列に含まれていてもよい。つまり、部分検査行列同士に重複部分があってもよい。
【００１４】
前記部分検査行列は、前記検査行列を列方向に複数に分割したものであるのが好ましい。検査行列を列方向に分割することで、部分処理回路同士を繋ぐ配線数の増加を更に抑えることができる。
【００１５】
前記部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての行処理を行うよう構成されているのが好ましい。
また、前記部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素についての行処理を行うとともに、当該部分処理回路が対応する部分検査行列の非零要素についての列処理を行うよう構成されているのが好ましい。検査行列を列方向に分割しても、列処理には影響がないため、各部分処理回路に列処理を含めると効率的である。
【００１６】
ここで、前記行処理には、検査行列又は部分検査行列に基づく行処理のほか、検査行列又は部分検査行列の「転置行列」に基づく列処理を含むものである。転置行列は行と列を入れ替えたものであるので、検査行列等に基づく行処理と当該検査行列等の転置行列に基づく列処理とは、実質的に等価だからである。
同様の理由により、前記列処理には、検査行列又は部分検査行列に基づく列処理のほか、検査行列又は部分検査行列の「転置行列」に基づく行処理を含むものである。
【００１７】
前記部分処理回路は、当該部分処理回路が対応する部分検査行列の非零要素における処理の演算を行うために必要とされる演算情報のうち、他の部分処理回路が有する演算情報を、当該他の部分処理回路から取得するための取得部を備えているのが好ましい。検査行列のある行に含まれる非零要素が複数の部分検査行列に跨っていたり、又は検査行列のある列に含まれる非零要素が複数の部分検査行列に跨っていたりしても、他の部分処理回路から演算情報を取得することで、検査行列に基づいて行処理又は列処理を行うことができる。
【００１８】
前記取得部は、事前値対数比及び入力データの対数尤度比、又は事前値対数比及び入力データの対数尤度比を用いた演算によって得られた値、を前記行処理演算情報として、他の部分処理回路から取得するのが好ましい。
【００１９】
前記取得部は、他の部分処理回路が行った部分演算結果を、前記演算情報として、当該他の部分処理回路から取得するよう構成され、前記部分演算結果は、行処理の演算又は列処理の演算における部分的な演算を前記他の部分処理回路が行った演算結果であるのが好ましい。この場合、取得する情報量を少なくすることができる。
【００２０】
前記部分的な演算は、事前値対数比と当該事前値対数比に対応する入力データの対数尤度比との和の絶対値を変数とするギャラガのｆ関数値に関し、部分検査行列の非零要素に対応するギャラガのｆ関数値の和を求める演算、又は事前値対数比と当該事前値対数比に対応する入力データの対数尤度比との和の絶対値に関し、部分検査行列の非零要素に対応する前記絶対値の最小値を求める最小値演算、を含むのが好ましい。
【００２１】
前記部分的な演算は、事前値対数比と当該事前値対数比に対応する入力データの対数尤度比との和から求めた符号情報に関し、部分検査行列の非零要素に対応する符号情報の積を求める符号演算、を含むのが好ましい。
【００２２】
前記情報取得部は、他の部分処理回路が対応する部分検査行列の非零要素それぞれに対応する演算情報を、当該他の部分処理回路から取得するのが好ましい。
【００２３】
前記複数の部分処理回路は、列同士が入れ替えられた検査行列を、列方向に複数に分割した複数の部分検査行列にそれぞれ対応するよう構成されているのが好ましい。この場合、列を適切に入れ替えることで、部分処理回路間での情報のやりとりを低減できる。
【００２４】
複数の入力データが、列同士が入れ替えられた検査行列に対応するように、複数の入力データ同士の入れ替えを行うデータ入替部を備えているのが好ましい。
【００２５】
前記部分処理回路は、前記複数の入力データのうち、当該部分処理回路が対応する部分検査行列の非零要素についての処理を行うために必要なデータを選択するように構成されているのが好ましい。この場合、部分検査行列がどのようなものであるかを考慮しなくても、部分処理回路は、与えられた入力データのうち、自己が必要なデータを選択するため、回路の設計が容易である。
【００２６】
前記部分処理回路は、複数の行処理演算情報を、共通の情報送信配線を介して、他の部分処理回路へ送信するための情報送信部を備えているのが好ましい。この場合、さらに配線数を低減できる。
【００２７】
なお、前記情報送信部は、複数の行処理演算情報を、多重化して共通の情報送信配線で送信するのが好ましい。複数の行処理演算情報を、多重化することで、効率よく情報を送信することができる。なお、多重化としては、時分割多重、周波数分割多重、符号分割多重などが採用できる。
【００２８】
前記情報送信部が送信する演算情報の順序を制御する制御部を備えているのが好ましい。また、前記制御部は、列処理が実行される列の順序に応じて、送信される行処理演算情報の順序を制御するのが好ましい。
【００２９】
前記複数の部分処理回路は、行処理及び列処理を実行した結果から推定符号を判定する判定部をそれぞれ備え、前記判定部によって判定した推定符号がそれぞれの部分処理回路から出力されるのが好ましい。
【００３０】
なお、前記処理部が複数段備わっているＬＤＰＣ復号回路であって、複数段の処理部には、行処理及び列処理を行う一の処理部と、前記一の処理部において行処理及び列処理を実行した結果を受け取って更に行処理及び列処理を行う他の一の処理部とを含み、前記一の処理部は、前記複数の部分処理回路によって構成され、前記一の処理部の前記複数の部分処理回路は、行処理及び列処理を実行した結果を、前記他の一の処理部に与えるために出力するものであってもよい。
【００３１】
他の観点から見た本発明は、他の部分処理回路と協調して、複数の入力データに対して行処理を行う行処理部を備えた部分処理回路であって、前記行処理部が行処理の演算を行うために必要な行処理演算情報を、他の部分処理回路から取得する取得部と、他の部分処理回路が行処理の演算を行うために必要な行処理演算情報を、他の部分処理回路へ送信する送信部と、を備え、前記取得部及び送信部によって、前記行処理演算情報を他の部分処理回路との間で交換することにより、他の部分処理回路と協調して行処理を行うように構成されている。
前記部分処理回路は、一つの半導体チップで構成されているのが好ましい。
【発明の効果】
【００３２】
本発明によれば、検査行列を複数に分割した部分検査行列に対応させて部分処理回路を構成したので、部分処理回路同士を繋ぐ配線の数の増加を抑えることができる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の実施形態を、図面を参照して説明する。
［第１実施形態］
図１は、本発明の第１実施形態に係る復号回路を有する通信システムの構成の一例を示す図である。図１において、通信システムは、送信側において、送信情報に誤り訂正用の冗長ビットを付加して送信符号を生成する符号化器１と、この符号化器１からの（Ｋ＋Ｍ）ビットの符号を所定の方式に従って変調して通信路３へ出力する変調器２とを含む。
【００３４】
符号化器１は、Ｋビットの情報に対し、パリティ計算用の冗長ビットＭビットを付加して、（Ｋ＋Ｍ）ビットのＬＤＰＣ符号（低密度パリティ検査符号）を生成する。低密度パリティ検査行列においては、行が冗長ビットに対応し、列が符号ビットに対応する。なお、（Ｋ＋Ｍ）ビットのＬＤＰＣ符号のどのビットに、Ｋ個の情報ビット及びＭ個の冗長ビットを配置するかは、送信側と受信側で取り決めていれば、どのように配置してもよい。
【００３５】
変調器２は、この通信路３の構成に応じて、振幅変調、位相変調、コード変調、周波数変調または直交周波数分割多重変調などの変調を行なう。たとえば、通信路３が、光ファイバの場合、変調器２においては、レーザダイオードの輝度を送信情報ビット値に応じて変更させることにより、光の強度変調（一種の振幅変調）を行なっている。たとえば、送信データビットが０の場合には、＋１に変換して、レーザダイオードの発光強度を強くして送信し、また送信データビットが１の場合、−１に変換して、レーザダイオードの発光強度を弱くして送信する。
【００３６】
受信部においては、通信路３を介して送信された変調信号に復調処理を施して、（Ｋ＋Ｍ）ビットのデジタル符号を復調する復調器４と、この復調器４からの（Ｋ＋Ｍ）ビットの符号にパリティ検査行列に基づく復号処理を施して元のＫビットの情報を再生する復号化器５が設けられる。
【００３７】
復調器４は、この通信路３における送信形態に応じて復調処理を行なう。たとえば、振幅変調、位相変調、コード変調、周波数変調および直交周波数分割多重変調等の場合、復調器４において、振幅復調、位相復調、コード復調、および周波数復調等の処理が行なわれる。
【００３８】
図２は、通信路３が光ファイバの場合の変調器２および復調器４の出力データの対応関係を一覧にして示す図である。図２において、上述のように、通信路３が光ファイバの場合、変調器２においては、送信データが０のときには、１に変換され、送信用のレーザダイオード（発光ダイオード）の発光強度が強くなり、また送信データビットが１のときには、−１に変換され、レーザダイオードの発光強度を弱くして送信する。
【００３９】
この通信路３における伝送損失等により、復調器４に伝達される光強度は、最も強い強度から最も弱い強度までの間のアナログ的な強度分布を有する。復調器４においては、この入力された光信号を量子化処理（アナログ／デジタル変換）を行なって、この受光レベルを検出する。
図２においては、８段階に受光レベルが量子化された場合の受信信号強度を示す。すなわち、受光レベルがデータ７のときには、発光強度がかなり強く、受光レベルが０のときには、光強度がかなり弱い状態である。各受光レベルは、符号付きデータに対応づけられ、復調器４から出力される。この復調器４の出力は、受光レベルが７のときにはデータ３が出力され、受光レベルが０のときには、データ−４が出力される。したがってこの復調器４からは、１ビットの受信信号に対し、多値量子化された信号が出力される。
【００４０】
復号化器５は、この復調器４から与えられた（Ｋ＋Ｍ）ビットの受信情報（各ビットは、多値情報を含む）を入力し、sum-product復号法又はmin-sum復号法に従ってＬＤＰＣパリティ検査行列を適用して、元のＫビットの情報を復元する。
【００４１】
なお、この図２においては、復調器４において、８レベルに量子化されたビットが生成されている。しかしながら、一般に、この復調器４においては、Ｌ値（Ｌ≧２）に量子化されたビットを用いて復号処理を行なうことができる。
【００４２】
また、図２においては、比較器を用いて、あるしきい値を使って受信信号のレベルを判定し、２値信号を生成してもよい。
【００４３】
図３は、この発明に従う復号化器５の構成を概略的に示す図である。この図３においては、復調器４および通信路３も併せて示す。復調器４は、通信路３から与えられた信号を復調する復調回路４ａと、この復調回路４ａにより生成されたアナログ復調信号をデジタル信号に変換するアナログ／デジタル変換回路４ｂを含む。
このアナログ／デジタル変換回路４ｂの出力データＸｎが復号化器５へ与えられる。この復号化器５へ与えられるデータＸｎは、Ｌ値（Ｌ≧２）のデータである。以下、データＸｎは、多値量子化データであるため、シンボルと称す。復号化器５は、この入力シンボルＸｎ系列に対しsum-product復号法又はmin-sum復号法などの復号法に従って復号処理を行なって符号ビットＣｎを生成する。
【００４４】
復号化器５は、復調器４からの復調シンボルＸｎの対数尤度比ｎを生成する対数尤度比算出部６と、復号処理部（単に、「処理部」ともいう）７とを含む。
【００４５】
対数尤度比算出部６は、この受信信号のノイズ情報と独立に、対数尤度比ｎを生成する。通常、ノイズ情報を考慮した場合、この対数尤度比ｎは、Ｘｎ／（２・・）で与えられる。ここで、は、ノイズの分散を示す。
しかしながら、本実施の形態においては、この対数尤度比算出部６は、バッファ回路または定数乗算回路で形成され、対数尤度比ｎは、Ｘｎ・ｆで与えられる。ここで、fは非ゼロの正の数である。また、min-sum復号方法においては、検査行列に基づく復号処理（行処理）において、最小値を利用して演算を行なうため、信号処理において線形性が維持される。このため、ノイズ情報に従って出力データを正規化するなどの処理は不要である。この場合ノイズ情報を利用せずに、対数尤度比を算出することにより、回路構成が簡略化され、また計算処理も簡略化される。
【００４６】
本実施形態の復号処理部７は、ハードウェア構成としては、図４に示すようなものである。ただし、ここでは、理解を容易にするため、図４に示す復号処理部７のハードウェア構成に依存することなく、図５〜図１４に基づいて、復号処理部７の機能を先に説明し、その後、本実施形態の復号処理部７のハードウェア構成について説明する。
【００４７】
図５に示すように復号処理部７は、対数尤度比λｎをシリアルデータからパラレルデータに変換するＳ／Ｐ変換部８と、パリティ検査行列の行処理を行なう行処理部９と、パリティ検査行列の列処理を行なう列処理部１０と、対数尤度比算出部６からの対数尤度比ｎと行処理部９の出力ビット（外部値対数比）とに従って符号を生成する判定部１１と、判定部１１によって判定された符号をパラレルデータからシリアルデータに変換するＰ／Ｓ変換部１２と、を含む。
【００４８】
復号法がsum-product復号法である場合、行処理部９及び列処理部１０は、次式（１）及び（２）にしたがって、演算処理を行い、パリティ検査行列の行の各要素（非零要素：１）についての処理（行処理）、及び列についての各要素（非零要素：１）についての処理（列処理）を繰り返し実行する。なお、行処理部９及び列処理部１０における演算は、零要素についても行っても良いが、検査行列の非零要素についてのみ行うのが効率的であって、好ましい。
具体的には、行処理部９が、次式（１）にしたがって外部値対数比（第１変数）αｍｎを算出する演算を行い、列処理部１０が、次式（２）にしたがって事前値対数比βｍｎを算出する演算を行う。
【数１】
2008288710.tif 000003
【００４９】
ここで、上式（１）および（２）それぞれにおいて、ｎ’∈Ａ（ｍ）＼ｎおよびｍ’∈Ｂ（ｎ）＼ｍは、自身を除く要素を意味する。
外部値対数比αｍｎについては、ｎ’≠ｎであり、事前値対数比βｍｎについては、ｍ’≠ｍである。また、αおよびβの行列内の位置を示す添え字ｍｎは、通常は下付文字で示されるが、本明細書においては、読みやすさのために、「横並びの文字」で示す。
なお、式（１）中において、ｆは、ギャラガ（Gallager）のｆ関数である。
【００５０】
また、関数ｓｉｇｎ（ｘ）は、次式（３）で定義される。
【数２】
2008288710.tif 000004
【００５１】
また、集合Ａ（ｍ）およびＢ（ｎ）は、２元Ｍ・Ｎ行列Ｈ＝［Ｈｍｎ］を復号対象のＬＤＰＣ符号の検査行列とした場合、集合［１，Ｎ］＝｛１，２，…，Ｎ｝の部分集合である。
Ａ（ｍ）＝｛ｎ：Ｈｍｎ＝１｝ …（４）
Ｂ（ｎ）＝｛ｍ：Ｈｍｎ＝１｝ …（５）
【００５２】
すなわち、上記部分集合Ａ（ｍ）は、検査行列Ｈの第ｍ行目において１（非零要素）が立っている列インデックスの集合を意味し、部分集合Ｂ（ｎ）は、検査行列Ｈの第ｎ列目において１（非零要素）が立っている行インデックスの集合を示す。
【００５３】
具体的に、今、図６に示す検査行列Ｈを考える。この図６に示す検査行列Ｈにおいては、第１行の第１列から第３列に１が立ち、また第２行の第３列および第４列に１が立ち、また第３行の第４列から第６列に、１が立つ。したがって、この場合、部分集合Ａ（ｍ）は以下のようになる。
【００５４】
Ａ（１）＝｛１，２，３｝
Ａ（２）＝｛３，４｝
Ａ（３）＝｛４，５，６｝
【００５５】
同様に、部分集合Ｂ（ｎ）については、以下のようになる。
Ｂ（１）＝Ｂ（２）＝｛１｝
Ｂ（３）＝｛１，２｝
Ｂ（４）＝｛２，３｝
Ｂ（５）＝Ｂ（６）＝｛３｝
【００５６】
この検査行列Ｈにおいて、タナー（Tanner）グラフを用いた場合、列に対応する変数ノードと行に対応するチェックノードの接続関係が、この１により示される。これを、本明細書においては「１が立つ」と称している。すなわち、図７に示すように、変数ノード１，２，３は、チェックノードＸ（第１行）に接続され、変数ノード３，４が、チェックノードＹ（第２行）に接続される。変数ノード４，５，６が、チェックノードＺ（第３行）に接続される。この変数ノードが検査行列Ｈの列に対応し、チェックノードＸ，ＹおよびＺが、この検査行列Ｈの各行に対応する。従って、図６に示す検査行列は、情報ビットが３ビット、冗長ビットが３ビットの合計６ビットの符号長の符号に対して適用される。
【００５７】
ＬＤＰＣの検査行列Ｈでは、１の数は少なく、低密度の検査行列であり、これにより、計算量を低減できる。
【００５８】
この変数ノードとチェックノードの間で各条件確率Ｐ（Ｘｉ｜Ｙｉ）を伝播させ、ＭＡＰアルゴリズムに従って、もっともらしい符号を各変数ノードについて決定する。ここで、条件付確率Ｐ（Ｘｉ｜Ｙｉ）は、Ｙｉの条件下でＸｉとなる確率を示す。
【００５９】
復号法がmin-sum復号法である場合、行処理部９及び列処理部１０は、次式（６）及び（７）にしたがって、演算処理を行う。min-sum復号法は、sum-product復号法を簡略化したものである。具体的には、外部値対数比αｍｎを求める式（１）を、式（６）のように簡略化したものである。式（６）において、関数ｍｉｎは、最小値を求める演算を示す。
なお、式（２）及び式（７）は同じものである。
【数３】
2008288710.tif 000005
【００６０】
なお、行処理部９及び列処理部１０の演算は、次式（８）及び（９）に従ったものであってもよい。下記式によれば、βｍｎの記憶部とλｎの記憶部を共用できるので、メモリを節約することができる。なお、次式において、ｌは行処理と列処理の繰り返し回数である。
【数４】
2008288710.tif 000006
【００６１】
以下では、min-sum復号法における、行処理及び列処理の一例を詳細に説明する。なお、ここでは、検査行列として図６に示すものを用いて説明する。
まず、行処理及び列処理で用いられる値の記憶部について、図８に基づいて説明する。
図８（ａ）は行処理部９が算出する外部値対数比（第１変数）αｍｎの記憶部を示し、図８（ｂ）は列処理部１９が算出する事前値対数比（第２変数）βｍｎの記憶部を示している。図８（ａ）（ｂ）に示すように、両変数αｍｎ，βｍｎの記憶部は、検査行列Ｈにおいて１が立っている要素（非零要素）に関して設けられていればよい。
【００６２】
また、図８（ｃ）は、復号処理部７への入力データである対数尤度比λｎ（ｎ＝６ビット）の記憶部を示し、図８（ｂ）は、対数尤度比λｎと事前値対数値βｍｎの和（λｎ＋βｍｎ）の記憶部を示している。
【００６３】
図９（ａ）に示すように、式（６）で示す外部値対数比αｍｎを求める行処理演算は、行処理部９が、対数尤度比λｎと事前値対数値βｍｎの和（λｎ＋βｍｎ）からαｍｎを求める演算ということができる（式（１）についても同様）。
また、図９（ｂ）に示すように、また、式（７）又は式（２）で示す事前値対数比βｍｎを求める列処理演算は、αｍｎからβｍｎを求める演算ということができる。
【００６４】
図１０は、検査行列Ｈのｍ＝１行目の行処理演算を示している。図６の検査行列Ｈの１行目では１，２，３列目の要素が非零要素（１）であるので、当該非零要素についての外部値対数比α１１，α１２，α１３を求める演算が式（６）に従って行われる。
【００６５】
図１０（ａ）は、α１１を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの１行目の１列目の要素について行処理演算を行う第１行演算処理部１９ａ−１は、（λ２＋β１２）及び（λ３＋β１３）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α１１を算出する。
【００６６】
図１０（ｂ）は、α１２を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの１行目の２列目の要素について行処理演算を行う第１行演算処理部１９ａ−２は、（λ１＋β１１）及び（λ３＋β１３）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α１２を算出する。
【００６７】
図１０（ｃ）は、α１３を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの１行目の３列目の要素について行処理演算を行う第１行演算処理部１９ａ−３は、（λ１＋β１１）及び（λ２＋β１２）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α１３を算出する。
【００６８】
図１１は、検査行列Ｈのｍ＝２行目の行処理演算を示している。図６の検査行列Ｈの２行目では３，４列目の要素が非零要素（１）であるので、当該非零要素についての外部値対数比α２３，α２４を求める演算が式（６）に従って行われる。
【００６９】
図１１（ａ）は、α２３を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの２行目の３列目の要素について行処理演算を行う第２行演算処理部１９ｂ−３は、（λ４＋β２４）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α２３を算出する。
【００７０】
図１１（ｂ）は、α２４を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの２行目の４列目の要素について行処理演算を行う第２行演算処理部１９ｂ−４は、（λ３＋β２３）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α２４を算出する。
【００７１】
図１２は、検査行列Ｈのｍ＝３行目の行処理演算を示している。図６の検査行列Ｈの３行目では４，５，６列目の要素が非零要素（１）であるので、当該非零要素についての外部値対数比α３４，α３５，α３６を求める演算が式（６）に従って行われる。
【００７２】
図１２（ａ）は、α３４を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの３行目の４列目の要素についての行処理演算を行う第３行演算処理部１９ｃ−４は、（λ５＋β３５）及び（λ６＋β３６）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α３４を算出する。
【００７３】
図１２（ｂ）は、α３５を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの３行目の５列目の行処理演算を行う第３行演算処理部１９ｃ−５は、（λ４＋β３４）及び（λ６＋β３６）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α３５を算出する。
【００７４】
図１２（ｃ）は、α３６を求める際の、（λｎ＋βｍｎ）の記憶部からαｍｎの記憶部へのデータの流れを示している。検査行列Ｈの３行目の６列目の行処理演算を行う第３行演算処理部１９ｃ−６は、（λ４＋β３４）及び（λ５＋β２５）から値を取得し、最小値演算（Ｍｉｎ関数による演算）と符号演算（ｓｉｇｎ関数による演算と積を求める演算）を行って、α３６を算出する。
【００７５】
図１３は、検査行列Ｈのｎ＝３列目の列処理演算を示している。図６の検査行列Ｈの３列目では１，２行目の要素が非零要素（１）であるので、当該非零要素についての事前値対数比β１３，β２３を求める演算が式（７）に従って行われる。
【００７６】
図１３（ａ）は、β１３を求める際の、αｍｎの記憶部からβｍｎの記憶部へのデータの流れを示している。検査行列Ｈの３列目の１行目の要素についての行処理演算を行う第３列演算処理部２０ｃ−１は、α２３から値を取得し、（αｍｎの和を求める演算を行って）、β１３を算出する。
【００７７】
図１３（ｂ）は、β２３を求める際の、αｍｎの記憶部からβｍｎの記憶部へのデータの流れを示している。検査行列Ｈの３列目の２行目の要素についての行処理演算を行う第３列演算処理部２０ｃ−２は、α１３から値を取得し、（αｍｎの和を求める演算を行って）、β２３を算出する。
【００７８】
図１４は、検査行列Ｈのｎ＝４列目の列処理演算を示している。図６の検査行列Ｈの３列目では２，３行目の要素が非零要素（１）であるので、当該非零要素についての事前値対数比β１３，β２３を求める演算が式（５）に従って行われる。
【００７９】
図１４（ａ）は、β２４を求める際の、αｍｎの記憶部からβｍｎの記憶部へのデータの流れを示している。検査行列Ｈの４列目の２行目の要素についての行処理演算を行う第４列演算処理部２０ｄ−２は、α３４から値を取得し、（αｍｎの和を求める演算を行って）、β２４を算出する。
【００８０】
図１４（ｂ）は、β３４を求める際の、αｍｎの記憶部からβｍｎの記憶部へのデータの流れを示している。検査行列Ｈの４列目の３行目の要素についての行処理演算を行う第４列演算処理部２０ｄ−３は、α２４から値を取得し、（αｍｎの和を求める演算を行って）、β３４を算出する。
【００８１】
なお、図６の検査行列では、説明を簡単にするために、列重みが２以上である列を３及び４列目だけとしたため、βｍｎを更新する演算は、３及び４列目についてしか行われないが、一般的な検査行列の場合、すべての列の列重みは２以上又は３以上であるため、すべての列についてβｍｎを更新する演算が式（７）に従って行われる。
【００８２】
［処理部の分割方法の基本概念］
さて、本実施形態では、処理部７が複数の部分処理回路に分割して構成されている。図１５は、本実施形態における処理部７の分割方法の基本的概念を示している。図１５には、処理部７の構成要素として、行処理及び列処理の手順に従い、上から順に、（λｎ＋βｍｎ）加算器３０Ａ，３０Ｂ、（λｎ＋βｍｎ）記憶部３１Ａ，３１Ｂ、行演算処理部１９Ａ，１９Ｂ、αｍｎ記憶部３２Ａ，３２Ｂ、列演算処理部２０Ａ，２０Ｂ、βｍｎ記憶部３３Ａ，３３Ｂを示した。
【００８３】
図１５の中央において上下に延びる点線は、処理部７の分割ラインであり、分割ラインの左側に、第１の部分処理回路３０Ａ，３１Ａ，１９Ａ，３２Ａ，２０Ａ，３３Ａがあり、分割ラインの右側に第２の部分処理回路３０Ｂ，３１Ｂ，１９Ｂ，３２Ｂ，２０Ｂ，３３Ｂがある。
ここで、図１６に示すように、図６の検査行列Ｈを列方向に複数（２つ）に分割した部分検査行列ＨＡ，ＨＢ（図１６参照）を考える。
図１５の第１部分処理回路は、部分検査行列ＨＡの非零要素に関する行処理及び列処理を行う回路である。また、図１５の第２部分処理回路は、部分検査行列ＨＢの非零要素に関する行処理及び列処理を行う回路である。
【００８４】
図１５に示すように、行演算処理部１９Ａ，１９Ｂは、列方向に複数に分割されているが、行演算処理部は、処理対象の行に含まれる非零要素が、一つの部分検査行列のみに存在する場合、当該行については、前記非零要素を含む部分検査行列に対応する部分処理回路単独で、行処理を行うことができる。
これに対し、処理対象の行に含まれる非零要素が、分割された複数の部分検査行列ＨＡ，ＨＢに跨っている場合、一つの部分処理回路単独では、行処理を行うことができない。なぜなら、行処理を行うには、処理対象の行に含まれる非零要素すべてに対応する行処理演算情報が必要である。換言すると、検査行列Ｈを列方向に分割した部分検査行列ＨＡ，ＨＢを作ったとしても、行処理はあくまでも検査行列Ｈで行わなければならないのである。
【００８５】
このことを、図１０〜図１２も参照して説明する。なお、図１０〜図１４において上下方向の点線は、図１５と同様の分割ラインである。つまり、図１０〜図１４において、分割ラインである点線の左側が第１部分処理回路の演算に対応し、右側が第２部分処理回路の演算に対応する。
【００８６】
まず、検査行列Ｈの第１行目についてみると、非零要素は、部分検査行列ＨＡ側のみに存在し、部分検査行列ＨＢ側には存在しない（図１６参照）。したがって、図１０に示すように、第１行目についての行処理は、第１部分処理回路（図１０の点線で示す分割ラインよりも左側）が有する（λｎ＋βｍｎ）の情報（行処理演算情報）を用いて、第１部分処理回路の第１行演算処理部１９ａ−１〜１９ａ−３が行うことができる。
【００８７】
また、検査行列Ｈの第３行目についてみると、非零要素は、部分検査行列ＨＢ側のみに存在し、部分検査行列ＨＡ側には存在しない（図１６参照）。したがって、図１２に示すように、第３行目についての行処理は、第２部分処理回路（図１２の点線で示す分割ラインよりも右側）が有する（λｎ＋βｍｎ）の情報（行処理演算情報）を用いて、第２部分処理回路の第３行演算処理部１９ｃ−４〜１９ｃ−６が行うことができる。
【００８８】
これに対し、検査行列Ｈの第２行目についてみると、非零要素は、部分検査行列ＨＡと部分検査行列ＨＢに分散して存在する（図１６参照）。したがって、図１１に示すように、第２行目についての行処理を行う際には、両部分処理回路が持つ（λｎ＋βｍｎ）の情報（行処理演算情報）を、交換する必要がある。
【００８９】
つまり、図１１（ａ）に示すように、部分検査行列ＨＡ側の２行目の非零要素に対応するαｍｎであるα２３を、第１部分処理回路の第２行演算処理部１９ｂ−３（行演算処理部１９Ａ）が行うには、第２部分処理回路の（λｎ＋βｍｎ）記憶部３１Ｂが保有する（λ４＋β２４）の情報（行処理演算情報）を取得する必要がある。
【００９０】
また、図１１（ｂ）に示すように、部分検査行列ＨＡ側の２行目の非零要素に対応するαｍｎであるα２４を、第１部分処理回路の第２行演算処理部１９ｂ−４（行演算処理部１９Ｂ）が行うには、第１部分処理回路の（λｎ＋βｍｎ）記憶部３１Ａが保有する（λ３＋β２３）の情報（行処理演算情報）を取得する必要がある。
【００９１】
上記のように、行処理に関しては、部分処理回路間で行処理情報の交換が必要となる場合があったが、列処理に関しては、処理部７を列方向に分割しても、部分処理回路間で情報の交換は不要である。
すなわち、図１３及び図１４に示すように、列処理は、検査行列Ｈの各列について列方向に演算を行うだけであるから、検査行列Ｈを列方向に複数に分割すれば、各部分処理回路は、当該部分処理回路に対応する部分検査行列ＨＡ，ＨＢに基づいて、列処理を行えば足りる。
【００９２】
以上によれば、検査行列Ｈを列方向に複数の部分検査行列に分割したときに、各行に含まれる非零要素が、いずれかの部分検査行列一つだけに集中して存在するように、検査行列とその部分検査行列を適切に設計すれば、一つの処理部７を複数の部分処理回路で構成しても、各部分処理回路間で行処理演算情報を交換するための配線は不要となる。
【００９３】
また、検査行列Ｈを列方向に複数の部分検査行列に分割したときに、各行に含まれる非零要素が、複数の部分検査行列に分散して存在することがあったとしても、ＬＤＰＣの場合、非零要素の数は、行列の大きさに比べて十分に少ないため、部分処理回路間での行処理演算情報の交換量を抑えることができる。
つまり、ＬＤＰＣでは、非零要素の数は行列の大きさに比べて十分に少ないため、検査行列中の比較的多くの行（例えば、半分以上の行）については、自然に、非零要素がいずれかの部分検査行列一つだけに集中して存在することになる。したがって、検査行列のすべての行について、行処理演算情報を交換する必要がなく、各部分処理回路間で行処理演算情報を交換するための配線の数の増加を抑えることができる。
【００９４】
なお、検査行列を分割する際の分割ラインは直線状である必要はなく、非零要素の配置に応じて、ジグザグであってもよい。つまり、非零要素が、いずれかの部分検査行列だけに集中して存在するように分割ラインを適切に曲げて設定することで、部分処理回路間で交換が必要な行処理演算情報を少なくすることができる。
また、検査行列のある要素が、複数の部分検査行列において含まれていてもよい。
【００９５】
［処理部７のハードウェア構成］
図４に戻り、上記基本概念に沿って設計された処理部７のハードウェア基本構成について説明する。
図４の処理部７は、複数（２つ）の部分処理回路７１，７２を有している。これらの第１部分処理回路７１及び第２部分処理回路７２は、それぞれ、半導体チップ（半導体チップパッケージ）として構成されている。第１部分処理回路７１を構成する第１半導体チップと第２部分処理回路７２を構成する第２半導体チップとは、それぞれ、処理部７を構成する回路基板上に配置され、両半導体チップ７１，７２間には、行処理演算情報を交換するための配線７４（複数本の配線）が形成されている。
【００９６】
また、図示はしないが、部分処理回路７１，７２を構成する半導体チップのパッケージには、前記行処理演算情報を交換するための配線７４に接続されるピン（行処理演算情報の入力端子又は出力端子）が設けられている。なお、複数の半導体チップを一つのパッケージに封入したマルチチップパッケージであってもよいが、一つの半導体チップパッケージあたりのピンの数を減らすには、一パッケージあたり一つの半導体チップが好ましい。
【００９７】
また、処理部７は、前述のとおり、入力データである対数尤度比λｎをシリアルデータからパラレルデータに変換するＳ／Ｐ変換部８と、部分処理回路７１，７２から出力された符号Ｃｎをパラレルデータからシリアルデータに変換するＰ／Ｓ変換部１２と、を含む。
前記Ｓ／Ｐ変換部８は、入力データλｎを、それぞれの部分処理回路７１，７２へ振り分ける機能をもつ。また、前記Ｐ／Ｓ変換部は、それぞれの部分処理回路７１，７２から出力された符号Ｃｎをまとめる機能をもつ。
【００９８】
各部分処理回路７１，７２の基本的構成は、共通している。すなわち、各部分処理回路７１，７２は、それぞれ、行処理を行って外部値対数比αｍｎを出力する行処理部９０Ａ，９０Ｂ、及び列処理を行って事前値対数比βｍｎを出力する列処理部１００Ａ，１００Ｂを有する。また、各部分処理回路７１，７２は、それぞれの部分処理回路７１，７２への入力データλｎをパラレルデータに分解するＳ／Ｐ変換部８０Ａ，８０Ｂと、後述の判定部１１０Ａ，１１０Ｂの出力をシリアルデータに変換するＰ／Ｓ変換部１２０Ａ，１２０Ｂを有している。
【００９９】
さらに、各部分処理回路７１，７２は、判定部（符号判定部）１１０Ａ，１１０Ｂを有している。判定部１１０Ａ，１１０Ｂは、行処理及び列処理の繰り返し回数を判定して、繰り返しを制御する機能を有する。つまり、判定部１１０Ａ，１１０Ｂは、行処理と列処理の繰り返し回数が所定値を超えると、繰り返し演算を終了させる。
【０１００】
また、判定部１１０Ａ，１１０Ｂは、繰り返し演算が終了した後、外部値対数比αｍｎ（又は事前値対数比βｍｎ）と対数尤度比λｎとを用いて符号を判定する機能を有している。
具体的には、判定部１１０Ａ，１１０Ｂは、次式（１０）に従って、Ｑｎを算出する。
【０１０１】
【数５】
2008288710.tif 000007
【０１０２】
さらに、判定部１１０Ａ，１１０Ｂは、次式（１１）に従って、推定符号Ｃｎを算出する。
【数６】
2008288710.tif 000008
【０１０３】
なお、各判定部１１０Ａ，１１０Ｂは、他の部分処理の判定部１１０Ａ，１１０Ｂから推定符号Ｃｎを収集して得られた一次推定語Ｃｎと検査行列Ｈとから、一次推定語Ｃｎが符号語を構成しているかどうか検査してもよい。行処理と列処理の繰り返し中に、この検査を行った結果、一次推定語Ｃｎが符号語を構成している場合には、判定部１１０Ａ，１１０Ｂは、行処理部９０Ａ，９０Ｂ及び列処理部１００Ａ，１００Ｂの繰り返し演算を終了させて、当該一次推定語Ｃｎを出力することができる。
【０１０４】
図１７は、図４の部分処理回路７１，７２における行処理部９０Ａ，９０Ｂと列処理部１００Ａ，１００Ｂの詳細を示している。
図１７に示す行処理部９０Ａ，９０Ｂ及び１００Ａ，１００Ｂは、図１５に示すものとほぼ対応しており、行処理部９０Ａ，９０Ｂは、加算器３０Ａ，３０Ｂと行演算処理部１９Ａ，１９Ｂを含み、列処理部１００Ａ，１００Ｂは、列演算処理部２０Ａ，２０Ｂを含む。
なお、図１７では、図１５に示す（λｎ＋βｍｎ）記憶部３１Ａ，３１Ｂ、αｍｎ記憶部３２Ａ，３２Ｂ記憶部、βｍｎ記憶部３３Ａ，３３Ｂを図示していないが、これらの記憶部も、必要に応じて部分処理回路７１，７２に含ませることができる。
【０１０５】
さて、図１７では、行演算処理部１９Ａ，１９Ｂ及び列演算処理２０Ａ，２０Ｂそれぞれを、３つのブロックに分けて描いている。３つのブロックに分かれているのは、検査行列の構造と関連する。そこで、以下では、一般的な検査行列の生成方法を説明する。
【０１０６】
図１８は、列重みがＸ（各列の非零要素の数がＸ）であるパリティ検査行列Ｈの生成方法を示している。
パリティ検査行列Ｈは、検査行列Ｈの行方向にＸ個のブロック（Ｈ１，Ｈ２・・・，ＨＸに分割される。例えば、行重みが６（各行の非零要素の数が６）の場合に、まず、第１ブロック（Ｈ１）において、第１行目の第１列目〜第６列目に「１」（非零要素）が配置され、第２行目の第７〜第１２列目に「１」（非零要素）が配置され、以下同様に、第１ブロック内の以下の行についても「１」（非零要素）が配置される。ここでは、第１ブロックにおける各列の列重みが１となるように配置される。
【０１０７】
そして、第１ブロック内の任意の列を、乱数を用いて再配置（入れ替え）し、これを適当な回数繰り返したものを第１ブロックとする。第１ブロックの各列の重みは１であるので、列を入れ替えても列の重みは１のままである。
第２ブロック以降についても、第１ブロックと同様に乱数（他のブロックとは別の乱数）を用いて列の入れ替え処理を行い、非零要素の配置が各ブロックで異なるようにする。
以上の処理をＸ個のブロックについて行えば、列重みがＸのパリティ検査行列が生成される。
【０１０８】
さて、図１７に戻る。図１７の行演算処理部１９Ａ，１９Ｂ及び列処理部２０Ａ，２０Ｂは、列重みＸ＝３の検査行列Ｈを前提としており、前述のように、それぞれ、３つのブロックに分割されている。
【０１０９】
つまり、第１部分処理回路７１の行演算処理部１９Ａは、第１部分検査行列ＨＡの第１ブロック部分に含まれる非零要素についての演算を行う第１ブロック行演算処理部１０Ａ−１と、第１部分検査行列ＨＡの第２ブロック部分に含まれる非零要素についての演算を行う第２ブロック行演算処理部１９Ａ−２と、第１部分検査行列ＨＡの第３ブロック部分に含まれる非零要素についての演算を行う第３ブロック行演算処理部１９Ａ−３と、を備える。
なお、行処理部９０Ａの（λｎ＋βｍｎ）加算器３０Ａは、第１ブロック行演算処理部１０Ａ−１に対応する第１加算器３０Ａ−１と、第２ブロック行演算処理部１９Ａ−２に対応する第２加算器３０Ａ−２と、第３ブロック行演算処理部１９Ａ−３に対応する第３加算器３０Ａ−３と、を備える。
【０１１０】
また、第２部分処理回路７２の行演算処理部１９Ｂは、第２部分検査行列ＨＢの第１ブロック部分に含まれる非零要素についての演算を行う第１ブロック行演算処理部１９Ｂ−１と、第２部分検査行列ＨＢの第２ブロック部分に含まれる非零要素についての演算を行う第２ブロック行演算処理部１９Ｂ−２と、第２部分検査行列ＨＢの第３ブロック部分に含まれる非零要素についての演算を行う第３ブロック行演算処理部１９Ｂ−３と、を備える。
なお、行処理部９０Ｂの（λｎ＋βｍｎ）加算器３０Ｂは、第１ブロック行演算処理部１０Ｂ−１に対応する第１加算器３０Ｂ−１と、第２ブロック行演算処理部１９Ｂ−２に対応する第２加算器３０Ｂ−２と、第３ブロック行演算処理部１９Ｂ−３に対応する第３加算器３０Ｂ−３と、を備える。
【０１１１】
第１部分処理回路７１の列演算処理部２０Ａは、第１部分検査行列ＨＡの第１ブロック部分に含まれる非零要素についての演算を行う第１ブロック列演算処理部（加算器）２０Ａ−１と、第１部分検査行列ＨＡの第２ブロック部分に含まれる非零要素についての演算を行う第２ブロック列演算処理部（加算器）２０Ａ−２と、第１部分検査行列ＨＡの第３ブロック部分に含まれる非零要素についての演算を行う第３ブロック列演算処理部（加算器）２０Ａ−３とを備える。
【０１１２】
第２部分処理回路７２の列演算処理部２０Ｂは、第２部分検査行列ＨＢの第１ブロック部分に含まれる非零要素についての演算を行う第１ブロック列演算処理部（加算器）２０Ｂ−１と、第２部分検査行列ＨＢの第２ブロック部分に含まれる非零要素についての演算を行う第２ブロック列演算処理部（加算器）２０Ｂ−２と、第２部分検査行列ＨＢの第３ブロック部分に含まれる非零要素についての演算を行う第３ブロック列演算処理部（加算器）２０Ｂ−３とを備える。
【０１１３】
図１９は、各第１〜第３ブロック行演算処理部から各第１〜第３ブロック列演算処理部への外部値対数比αｍｎの受け渡し方を示している。なお、図１９は、両部分処理回路７１，７２について共通である。第１ブロック列演算処理部２０Ａ−１は第２及び第３ブロック行演算処理部１９Ａ−２，１９Ａ−３からαｍｎを取得し、第２ブロック列演算処理部２０Ａ−２は、第１及び第３ブロック行演算処理部１９Ａ−１，１９Ａ−３からαｍｎを取得し、第３ブロック列演算処理部２０Ａ−３は、第１及び第２ブロック行演算処理部１９Ａ−１，１９Ａ−２からαｍｎを取得する。
【０１１４】
図２０は、図１７に示す行演算処理部１９Ａ，１９Ｂが前提としている検査行列（列重み＝３）Ｈを示している。
図２０に示すように、検査行列Ｈの第１ブロックＨ１の各行についてみた場合、ある行に含まれる複数の非零要素は、２つの部分検査行列ＨＡ，ＨＢのいずれか一方のみに偏在する。
したがって、第１部分検査行列ＨＡの第１ブロックＨ１部分に対応する第１ブロック行演算処理部１９Ａ−１、及び第２部分検査行列ＨＢの第１ブロックＨ１部分に対応する第１ブロック行演算処理部１９Ｂ−１は、他方の行演算処理部１９Ａ−１，１９Ｂ−１が保有する行処理演算情報（λｎ＋βｍｎ）を取得しなくとも、自己が保有する行処理演算情報（λｎ＋βｍｎ）だけでαｍｎを演算することができる。
【０１１５】
これに対し、検査行列の第２ブロックＨ２及び第３ブロックＨ３では、同一行に含まれる複数の非零要素が２つの部分検査行列ＨＡ，ＨＢに跨って存在する行が含まれている。
したがって、第１部分検査行列ＨＡの第２ブロックＨ２部分に対応する第２ブロック行演算処理部１９Ａ−２、及び第２部分検査行列ＨＢの第２ブロックＨ２部分に対応する第２ブロック行演算処理部１９Ｂ−２は、他方の行演算処理部１９Ａ−２，１９Ｂ−２が保有する行処理演算情報（λｎ＋βｍｎ）を取得しなければ、αｍｎを演算することができない。
【０１１６】
このため、図１７に示す、部分処理回路７１，７２は、それぞれ、情報交換部１４２Ａ，１４２Ｂ，１４３Ａ，１４３Ｂを有している。情報交換部は、部分処理回路７１，７２間に設けられた配線７４（図４参照）を介して、他の部分処理回路７１，７２との間で、行処理演算情報（λｎ＋βｍｎ）をやり取りする。
【０１１７】
図２１は、前記情報交換部１４２Ａ，１４２Ｂの一例を示している。なお、情報交換部１４３Ａ，１４３Ｂについても図２１と同様である。
情報交換部１４２Ａ，１４２Ｂは、それぞれ、情報送信部１４２Ａ−１，１４２Ｂ−１と、情報受信部（情報取得部；単に「取得部」ともいう）１４２Ａ−２，１４２Ｂ−２とを有している。
図２１の例では、情報交換部１４２Ａ，１４２Ｂは、行処理の演算情報として、検査行列の非零要素に対応する（λｎ＋βｍｎ）のやり取りを行う。
【０１１８】
ここで、第２ブロックのある行ｍに関し、第１部分処理回路７１の保有する４つの（λｎ＋βｍｎ）を、Ｘ１，Ｘ２，Ｘ３，Ｘ４とし、第２部分処理回路７２の保有する２つの（λｎ＋βｍｎ）を、Ｘ５，Ｘ６とする。
第１部分処理回路７１の情報受信部（情報取得部１４２Ａ−２）は、第２部分処理回路７２の情報送信部１４２Ｂ−１から、Ｘ５，Ｘ６を取得する。
同様に、第２部分処理回路７２の情報受信部（情報取得部１４２Ｂ−２）は、第１部分処理回路７１の情報送信部１４２Ａ−１から、Ｘ１〜Ｘ４を取得する。
【０１１９】
したがって、各行演算処理部１９Ａ−２，１９Ｂ−２は、それぞれ、Ｘ１〜Ｘ６の情報を有することになるため、それぞれが、対応する部分検査行列ＨＡ，ＨＢの第２ブロック部分のｍ行に含まれる非零要素に対応するαｍｎについて演算することができる。
すなわち、各部分処理回路７１，７２の行演算処理部は、情報を交換することで、検査行列全体に従った行処理が可能なのである。
【０１２０】
図２２は、前記情報交換部１４２Ａ，１４２Ｂの他の例を示している。図２２の例では、個々の非零要素に対応する（λｎ＋βｍｎ）のやりとりをするのではなく、各部分処理回路７１，７２が保有する１又は複数の（λｎ＋βｍｎ）を用いて、各部分処理回路７１，７２それぞれが、所定の演算（行処理における部分的な演算）を行った上で、その演算結果（部分行処理演算結果）を、それぞれの部分処理回路７１，７２を代表する行処理演算情報として、他方の部分処理回路７１，７２に渡す。そして、当該他方の部分処理回路７１，７２は、その演算結果を受け取って、完全な行処理を行う。
【０１２１】
より具体的には、図２２の例は、sum-product復号法によって行処理を行う場合の情報交換の方法である。情報送信部１４２Ａ−１，４２Ｂ−１は、前記所定の演算（行処理における部分的な演算）を行うため、符号演算部１４２Ａ−１−１，４２Ｂ−１−１と、ｆ関数の和の演算部１４２Ａ−１−２，１４２Ｂ−１−２とを有している。
【０１２２】
符号演算部１４２Ａ−１−１，４２Ｂ−１−１は、符号情報である（λｎ＋βｍｎ）＝Ｘｉの積を求める符号演算を行い、その演算結果として部分符号情報Ａｓｉｇｎ，Ｂｓｉｇｎを求める。
部分符号情報Ａｓｉｇｎ及びＢｓｉｇｎの演算式は下記式（１０）（１１）の通りである。
【０１２３】
Ａｓｉｇｎ＝Ｓｉｇｎ（Ｘ１）Ｓｉｇｎ（Ｘ２）Ｓｉｇｎ（Ｘ３）Ｓｉｇｎ（Ｘ４）…（１０）
Ｂｓｉｇｎ＝Ｓｉｇｎ（Ｘ５）Ｓｉｇｎ（Ｘ６）…（１１）
【０１２４】
ｆ関数の和の演算部１４２Ａ−１−２，１４２Ｂ−１−２は、（λｎ＋βｍｎ）＝Ｘｉの絶対値（データ信頼度）を変数としてギャラガのｆ関数の値を求め、当該ｆ関数値の和を求める演算を行い、その演算結果として、部分信頼度Ａ，Ｂを求める。
部分信頼度Ａ，Ｂの演算式は、下記式（１２）（１３）の通りである。
【０１２５】
Ａ＝ｆ（｜Ｘ１｜）＋ｆ（｜Ｘ２｜）＋ｆ（｜Ｘ３｜）＋ｆ（｜Ｘ４｜）…（１２）
Ｂ＝ｆ（｜Ｘ５｜）＋ｆ（｜Ｘ６｜）…（１３）
【０１２６】
各部分処理回路７１，７２の情報受信部１４２Ａ−２，１４２Ｂ−２は、Ａｓｉｎｇ及びＡ又はＢｓｉｇｎ及びＢを、他方の部分処理回路７１，７２側から受け取る。
したがって、各部分処理回路７１，７２は、Ａｓｉｇｎ，Ｂｓｉｇｎ，Ａ，及びＢの情報（行処理演算情報）を保有する。
【０１２７】
そして、行演算処理部１９Ａ−２，１９Ｂ−２は、下記式（１４）に従って、αｍｉ（ｉ：１〜６）を求めることができる。
ａｍｉ＝Ｓｉｇｎ（Ｘｉ）×Ａｓｉｇｎ×Ｂｓｉｇｎ×ｆ｛Ａ＋Ｂ−ｆ（｜Ｘｉ｜）｝    …（１４）
【０１２８】
図２２の例では、行処理の部分的な演算を、個々の部分処理回路７１，７２において行ってから、その演算結果（ｆ関数の和、符号）を他方の部分処理回路７１，７２に渡すため、図２１の例に比べて、部分処理回路７１，７２をつなぐ配線７４の本数が少なくて済む。
【０１２９】
図２３は、前記情報交換部１４２Ａ，１４２Ｂの他の例を示している。図２３の例においても、各部分処理回路７１，７２が保有する１又は複数の（λｎ＋βｍｎ）を用いて、各部分処理回路７１，７２それぞれが、所定の演算（行処理における部分的な演算）を行った上で、その演算結果（部分行処理演算結果）を、それぞれの部分処理回路７１，７２を代表する行処理演算情報として、他方の部分処理回路７１，７２に渡す。そして、当該他方の部分処理回路７１，７２は、その演算結果を受け取って、完全な行処理を行う。
【０１３０】
より具体的には、図２３の例は、min-sum復号法によって行処理を行う場合の情報交換の方法である。情報送信部１４２Ａ−１，１４２Ｂ−１は、それぞれ、最小値演算部１５１と符号演算部１５２を有している。最小値演算部１５１は、与えられた２つの値のうち小さい方の値を出力するものである。また、符号演算部は、与えられた２つの符号情報ｓｉｇｎ（λｎ＋βｍｎ）の積を求めるものである。
【０１３１】
Ｘｉ（ｉ：１〜６）＝（λｎ＋βｍｎ）が与えられたときに、図２３に示すように最小値演算部１５１と符号演算部１５１が接続されている場合、min-sum復号法における部分符号情報Ａｓｉｇｎ及びＢｓｉｇｎは下記式（１５）（１６）の通り求まる。
【０１３２】
Ａｓｉｇｎ＝Ｓｉｇｎ（Ｘ１）Ｓｉｇｎ（Ｘ２）Ｓｉｇｎ（Ｘ３）Ｓｉｇｎ（Ｘ４）…（１５）
Ｂｓｉｇｎ＝Ｓｉｇｎ（Ｘ５）Ｓｉｇｎ（Ｘ６）…（１６）
【０１３３】
また、min-sum復号法における部分信頼度Ａ，Ｂは、下記式（１７）（１８）の通り求まる。
【０１３４】
Ａ＝ｍｉｎ（｜Ｘ１｜，｜Ｘ２｜，｜Ｘ３｜，｜Ｘ４｜）…（１７）
Ｂ＝ｍｉｎ（｜Ｘ５｜，｜Ｘ６｜）…（１８）
【０１３５】
各部分処理回路７１，７２の情報受信部１４２Ａ−２，１４２Ｂ−２は、Ａｓｉｎｇ及びＡ又はＢｓｉｇｎ及びＢを、他方の部分処理回路７１，７２側から受け取る。
【０１３６】
図２３の例では、行演算処理部１９Ａ−２，１９Ｂ−２も、最小値演算部１５１と符号演算部１５２を有しており、さらに、行演算処理部１９Ａ−２，１９Ｂ−２は、最終演算部１５３も有している。
行演算処理部１９Ａ−２，１９Ｂ−２に含まれる最小値演算部１５１は、図２３のように接続されていることによって、
αｍ１を求めるための信頼度：ｍｉｎ（Ｘ２，Ｘ３，Ｘ４，Ｂ） 
αｍ２を求めるための信頼度：ｍｉｎ（Ｘ１，Ｘ３，Ｘ４，Ｂ）
αｍ３を求めるための信頼度：ｍｉｎ（Ｘ１，Ｘ２，Ｘ４，Ｂ）
αｍ４を求めるための信頼度：ｍｉｎ（Ｘ１，Ｘ２，Ｘ３，Ｂ）
αｍ５を求めるための信頼度：ｍｉｎ（Ａ，Ｘ６）
αｍ６を求めるための信頼度：ｍｉｎ（Ａ，Ｘ５）
を算出することができる。
【０１３７】
また、行演算処理部１９Ａ−２，１９Ｂ−２に含まれる符号演算部１５２は、図２３のように接続されていることによって、αｍ１を求めるための符号情報Ｘ１ｓｉｇｎ，αｍ２を求めるための符号情報Ｘ２ｓｉｇｎ，αｍ３を求めるための符号情報Ｘ３ｓｉｇｎ，αｍ４を求めるための符号情報Ｘ４ｓｉｇｎ，αｍ５を求めるための符号情報Ｘ５ｓｉｇｎ，αｍ６を求めるための符号情報Ｘ６ｓｉｇｎを求めることができる。
【０１３８】
ここで、Ｘ１ｓｉｇｎ，Ｘ２ｓｉｇｎ，Ｘ３ｓｉｇｎ，Ｘ４ｓｉｇｎ，Ｘ５ｓｉｇｎ，Ｘ６ｓｉｇｎは、下記式（１９）〜式（２４）のとおりである。
Ｘ１ｓｉｇｎ＝Ｓｉｇｎ（Ｘ２）・Ｓｉｇｎ（Ｘ３）・Ｓｉｇｎ（Ｘ４）・Ｂｓｉｇｎ
…（１９）
Ｘ２ｓｉｇｎ＝Ｓｉｇｎ（Ｘ１）・Ｓｉｇｎ（Ｘ３）・Ｓｉｇｎ（Ｘ４）・Ｂｓｉｇｎ
…（２０）
Ｘ３ｓｉｇｎ＝Ｓｉｇｎ（Ｘ１）・Ｓｉｇｎ（Ｘ２）・Ｓｉｇｎ（Ｘ４）・Ｂｓｉｇｎ
…（２１）
Ｘ４ｓｉｇｎ＝Ｓｉｇｎ（Ｘ１）・Ｓｉｇｎ（Ｘ２）・Ｓｉｇｎ（Ｘ３）・Ｂｓｉｇｎ
…（２２）
Ｘ５ｓｉｇｎ＝Ａｓｉｇｎ・ｓｉｇｎ（Ｘ６）  …（２３）
Ｘ６ｓｉｇｎ＝Ａｓｉｇｎ・ｓｉｇｎ（Ｘ５）  …（２４）
【０１３９】
なお、最終演算部１５３では、αｍｉを求めるための信頼度とαｍｉを求めるための符号情報との積を求めて、αｍｉを得る。
【０１４０】
図２３の例においても、図２２の例と同様に、行処理の部分的な演算を、個々の部分処理回路７１，７２において行ってから、その演算結果（最小値、符号）を他方の部分処理回路７１，７２に渡すため、図２１の例に比べて、部分処理回路７１，７２をつなぐ配線７４の本数が少なくて済む。
【０１４１】
ここで、一の部分処理回路から、他の部分処理回路へ渡す情報は、当該情報そのものではなく、当該情報の近似値や、当該情報の情報量を削減してビット数を少なくしたものであってもよい。このようにすることで、部分処理回路７１，７２間の配線の数を少なくすることができる。
例えば、部分信頼度Ａ，Ｂである「最小値」は、最小値そのもの以外に、最小値を近似したものを含む。
また、一つの情報（最小値）が６ｂｉｔで表される場合、当該情報は、０〜６３の６４種類の値をとることができるが、これを、例えば、０，１，２，４，８，１６，３２の７つの値に丸めて表現し、これら７つの値を示すインデックスで表現すれば、３ｂｉｔあれば足りる。このように、部分信頼度Ａ，Ｂである「最小値」は、最小値そのもの以外に、最小値の近似値のインデックスをも含む。
【０１４２】
図２４及び図２５は、部分処理回路７１，７２間での情報の交換方法に関する２つの例を示している。
図２４の例では、行演算処理部１９Ａの各行の行演算処理部単位で、行処理演算情報（λｎ＋βｍｎ等）のやり取りを行う。したがって、検査行列Ｈにおいて非零要素が２つの行に跨っている行の数に応じて、情報を交換するための配線数を用いることにすれば、他の行処理に影響されず、情報を高速にやり取りできる。
【０１４３】
図２５の例では、複数の行の行処理演算情報を、共通の配線（情報送信配線）７４を介して、送信する。情報交換部１４２，１４３は、各行の行処理演算情報を、時分割多重、周波数分割多重、又は符号分割多重等によって多重化して送受信する。したがって、少ない配線で、情報のやりとりが行える。
なお、複数の行処理演算情報のやりとりを行う共通配線７４は、１本である必要はなく、複数本であってもよく、この場合、配線数を抑えつつ、高速化も図ることができる。
【０１４４】
また、一つの行について複数の行処理演算情報を送る必要がある場合には、当該複数の行処理演算情報を共通の配線７４で送っても良い。
【０１４５】
図２５の情報交換部１４２、１４３は、制御部２１０Ａ、２１０Ｂによって、送信する行処理演算情報の順序が制御される。行処理演算情報の送信順序は、単純に、１行目から昇順であってもよいが、次のように制御するのが好ましい。
【０１４６】
すなわち、図２６示すような検査行列Ｈを考えた場合、当該検査行列Ｈの１列目の非零要素は１，５００，８００行目に存在する。したがって、１列目の列処理は、これら３つの行の処理が完了すれば、直ちに実行可能となる。
ところが、行処理演算情報の送信順序が、１行目からの単純な昇順であると、８００行分の行処理演算情報の送信が完了しなければ、８００行目の行処理が完了しない。
したがって、列処理部１００Ａは、少なくとも１〜８００行目までの行処理が完了するまで、１列目の列処理を実行開始することができない。この結果、実質的には、行処理がすべて完了しなければ、列処理を実行することができないことになり、行処理と列処理の並列処理が妨げられる。
【０１４７】
そこで、制御部１４２は、１列目の列処理に必要な行についての行処理実行が優先して行われるように、１，５００，８００の順で、行処理演算情報を送信すれば、その後、直ちに１列目の列処理が可能になる。続いて、２列目の列処理に必要な行についての行処理演算情報を送信すれば、１列目の列処理の後に、２列目の列処理が行える。以降、同様に、行処理演算情報の送信順序を、列処理が実行される列の順序に応じて、必要な行の行処理演算情報から優先して順次送るように制御することで、行処理と列処理の並列処理が可能となる。
【０１４８】
しかも、制御部１４２，１４３が上記のように制御すれば、各部分処理回路７１，７２の列処理部において同時に行われる加算が少なくなる（最も少ない場合で１つ）。この結果、列処理部１００Ａ，１００Ｂの加算器の数を減少させて、回路構成を簡素化することができる。
【０１４９】
［第２実施形態］
図２７は、第２実施形態に係る処理部７を示している。なお、第２実施形態において説明を省略する点については、第１実施形態と同様である。
図２７の第２実施形態では、行処理部９０Ａ，９０Ｂ及び列処理部１００Ａ，１００Ｂは、検査行列Ｈそのものに対応しているのではなく、検査行列Ｈの列同士を入れ替えた列入替検査行列Ｈ’に対応している。
【０１５０】
つまり、図２８（ａ）に示すように、検査行列Ｈの第１ブロックの３行目のように、非零要素が２つの部分検査行列Ｈ１，Ｈ２にまたがっている行の場合、当該非零要素を有する列と、当該行において零要素を有する列とを入れ替える。これによって、図２８（ｂ）に示すような列入替検査行列Ｈ’が生成できる。
【０１５１】
図２７の第１部分処理回路７１の行処理部９０Ａ及び列処理部１００Ａは、前記列入替検査行列’を列方向に分割した部分検査行列ＨＡ’に対応する。また、第２部分処理回路７２の行処理部９０Ｂ及び列処理部１００Ｂは、前記列入替検査行列Ｈ’を列方向に分割した部分検査行列ＨＢ’に対応する。
列を適切に入れ替えることで、非零要素が複数の部分検査行列ＨＡ’，ＨＢ’に跨る行が少なくなる。この結果、部分処理回路７１，７２間でやりとりする情報が少なくなり、部分処理回路７１，７２間の配線数を少なくすることができる。
【０１５２】
なお、列を入れ替える場所は、何カ所であってもよい。また、まとめて入れ替えられる列の数は、複数列であってもよいし、１列であってもよい。
【０１５３】
第２実施形態では、列入替検査行列Ｈ’を用いるため、複数の入力データλｎの並びを、列入替検査行列Ｈ’と同様に入れ替えなければならない。このため、第２実施形態の処理部７は、複数の入力データλｎ同士の入れ替えを行うデータ入替部２００を備えている。また、各部分処理回路７１，７２から出力されるデータも、本来のデータの並びとは異なっているため、入れ替えを元に戻す必要がある。このため、第２実施形態の処理部７は、複数の出力データ同士の入れ替えを行うデータ入替部２０１も備えている。
【０１５４】
図２９は、データ入替部２００，２０１を用いずに、列入替検査行列Ｈ’を採用するための構成法を示している。
図２９では、入力データλｎを２つの部分処理回路７１，７２に振り分けて与えるのではなく、全入力データλｎをそれぞれの部分処理回路７１，７２に与えるようにしている。そして、与えられた入力データのうち、各部分処理回路７１，７２が必要なものを使用し、必要ないものは使用しないことで、列入替検査行列Ｈ’の部分検査行列Ｈ１’，Ｈ２’がどのようなものであっても対応できる。
【０１５５】
また、部分検査行列の大きさ（列数）が、各部分検査行列ごとに異なる場合、各部分処理回路７１，７２に与える入力データの数も異なり、入力データ用の配線数が部分処理７１，７２ごとに異なってしまい、汎用性に欠ける。これに対し、全入力データを、各部分処理回路７１，７２に与えることで、部分処理回路の大きさにかかわらず入力データ用の配線数を共通化でき、部分処理回路の汎用性が高まる。
なお、全入力データを各部分処理回路７１，７２に与える点については、入替検査行列Ｈ’を採用した場合に限らず、通常の検査行列を採用した場合についても適用できる。
【０１５６】
全入力データを各部分処理回路７１，７２与えるための配線は、部分処理回路７１，７２外だけで行っても良いが、図２９に示すように、各部分処理回路７１，７２のデータ入力部（入力端子）２３０Ａ，２３０Ｂに入力された入力データλｎを、そのまま出力するデータ出力部（出力端子）２３１Ａ，２３１Ｂを設けておくのが好ましい。図２９のように構成することで、一の部分処理回路７１のデータ出力部２３１Ａから出力した入力データλｎを他の部分処理回路７２の入力部２３０Ｂに入力できる。すなわち、入力データλｎを部分処理回路７１，７２間で受け渡すことができ、配線配置が容易となる。
【０１５７】
［第３実施形態］
図３０は、第３実施形態を示している。なお、第３実施形態において説明を省略した点については、第１及び第２実施形態と同様である。
第３実施形態では、処理部が、行処理及び列処理を行う第１段処理部７−１と、第１段処理部において行処理及び列処理を実行した結果を受け取って更に行処理及び列処理を行う第２段処理部７−２とを有した、多段構成の処理部として構成されている。
第１段処理部７−１及び第２段処理部７−２は、それぞれ、複数の部分処理回路７１，７２，７３によって構成されている。
第１段処理部７−１の部分処理回路７１，７２，７３が行処理及び列処理を実行したそれぞれの結果は、前記第２段処理部に与えられる。
第３実施形態では、各処理部７−１，７−２における、行処理及び列処理の繰り返しがなく、図３０に示すように、複数の処理部７を多段接続することで、行処理及び列処理を繰り返すのと等価な結果を得ている。なお、多段の処理部７の最終段に、符号を判定して推定符号語を生成する判定部を設けても良い。
【０１５８】
第１段及び第２段処理部７−１，７−２の各部分処理回路７１，７２，７３は、軟判定出力をするように構成されている。すなわち、図４のようにＣｎを出力するのではなく、行処理及び列処理の結果としてＱｎを出力する。そのため、図３０の各部分処理回路７１，７２，７３は、図４の部分処理回路７１，７２の判定部１１０Ａ，１１０Ｂに代えて、Ｑｎを推定する推定部１３０Ａ，１３０Ｂ，１３０Ｃを有している。推定部１３０Ａ，１３０Ｂは、αｍｎ又はβｍｎと入力データλｎとからＱｎを推定する。
なお、第１段処理部７−１は、行処理及び列処理の結果として、Ｑｎに代えて、行処理αｍｎ又はβｍｎと入力データλｎとを第２段処理部７−２に与えてもよい。例えば、第１段処理部７−１が、βｍｎを第２段処理部７−２に与える場合、第２段処理部７−２では、与えられたβｍｎを初期値として行処理及び列処理を行うことができる。
また、処理部の段数は、２つに限られるものではなく、３以上の任意の段数としてもよい。また、部分処理回路で構成される処理部は、すべての段でなくてもよく、複数段の処理部の一部の段の処理部だけであってもよい。
【０１５９】
［実施形態に係る分割方法と他の分割方法との比較］
図３１は、上記実施形態における処理部の分割方法とは異なる分割方法を示している。
図３１の分割方法では、行処理部と列処理部の間に分割ライン（点線）があることから明らかなように、図３１の左側は行処理部を構成する部分処理回路（行処理部チップ）とし、図３１の右側は列処理部を構成する部分処理回路（列処理チップ）としたものである。なお、図３１では、行処理部及び列処理部は、検査行列の３つのブロック毎に描かれている。
【０１６０】
さて、図３１の分割方法の場合、左側の行処理部チップと右側の列処理部チップとの間で行き交う配線の数は、点線で示す分割ラインに交差する線の数にほぼ等しい。
図３１の場合、３つの行処理部ブロックから３つの列処理部ブロックへ延びる計６本の線が分割ラインと交差する。したがって、行処理部チップと列処理部チップとの間で、６ｎ（ｎは符号長）の線が必要となる。ここで、符号長ｎ＝６０００、１符号あたり６本（６ｂｉｔ）必要であるとすると、２１６，０００本もの膨大な数の配線が必要となる。
よって、図３１の分割方法は、符号長が長くなった場合には、現実的ではない。
【０１６１】
一方、本発明の実施形態である図４に示す分割方法の場合、符号長６０００ビット、１符号あたり６本（６ｂｉｔ）、符号化率１／２とすると、検査行列の行数は３０００となる。そして、少なくとも、検査行列Ｈの３つのブロックＨ１，Ｈ２，Ｈ３（図２０参照）のうち、少なくとも１つのブロックＨ１は、行処理演算情報のやりとりを不要にできるため、行処理演算情報のやりとりが必要となる行は、最大、残りの２０００行となる。ただし、検査行列は低密度であるため、少なくとも半分の行については、自然に、非零要素がいずれかの部分処理回路に偏る。よって、１０００行について、行処理演算情報のやりとりが必要になる。
そして、部分処理回路間の双方向のやりとりを考慮すれば、１行あたり、２本必要となるため、２×６×１０００＝１２，０００本となる。このように、図３１の例に比べて、１／１８の配線数で済むことになる。
【０１６２】
また、本発明においては、図３２の分割方法も採用可能である。図３２では、行処理部及び列処理部の第１ブロックα１と第２ブロックα２との間に分割ライン（点線）があることから明らかなように、行処理部及び列処理部をブロック単位で分割したものである。
つまり、検査行列を行方向に複数に分割して、ブロック単位で部分処理回路を構成したものである。
この場合、一つの行処理部ブロックには、ｎ列分のｎ個の変数（α）があり、一つの行処理ブロックから出力されたｎ個のαを他の２つのブロックの列処理部に与えればよい。このため、符号長ｎ＝６０００、１符号あたり６本（６ｂｉｔ）必要であるとすると、７２，０００本の配線でよく、図３１の分割方法に比べると配線数を削減できる。
なお、検査行列を行方向に複数に分割する場合、ブロック単位で分割する必要はなく、任意の位置で分割することができる。
【０１６３】
本発明は、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲で様々な変形が可能である。例えば、部分処理回路間で交換される行処理演算情報は、上記のものに限られず、採用される復号方式に応じた適切な行処理演算情報を交換すればよい。また、分割方法も、前記列方向へ複数に分割することや、行方向に複数に分割することに限られない。
また、部分処理回路間で交換される演算情報は、行処理演算情報に限らず、列処理演算情報であってもよい。すなわち、検査行列のある列の列処理を行うために、複数の部分処理間で列処理のための演算情報を交換する必要がある場合には、行処理演算情報と同様に、複数の部分処理回路間で列処理演算情報を交換すればよい。
【図面の簡単な説明】
【０１６４】
【図１】通信システムの構成を概略的に示す図である。
【図２】送信データと復調データの対応の一例を示す図である。
【図３】復号化器の構成を概略的に示す図である。
【図４】部分処理回路に分割された処理部のハードウェア構成を示す図である。
【図５】処理部の機能ブロック図である。
【図６】検査行列の一例である。
【図７】図６に示す検査行列のタナーグラフである。
【図８】処理部における各記憶部を示す図であり、（ａ）はαｍｎ記憶部、（ｂ）はβｍｎ記憶部、（ｃ）はλｎ記憶部、（ｄ）は、（λｎ＋βｍｎ）記憶部である。
【図９】（ａ）は行処理の概念を示す図であり、（ｂ）は列処理の概念を示す図である。
【図１０】図６の検査行列Ｈの第１行目についての行処理を示す図である。
【図１１】図６の検査行列Ｈの第２行目についての行処理を示す図である。
【図１２】図６の検査行列Ｈの第３行目についての行処理を示す図である。
【図１３】図６の検査行列Ｈの第３列目についての列処理を示す図である。
【図１４】図６の検査行列Ｈの第４列目についての列処理を示す図である。
【図１５】処理部の分割方法を示す概念図である。
【図１６】図６の検査行列Ｈに対応する第１部分検査行列ＨＡ及び第２部分検査行列である。
【図１７】図４の行処理部及び列処理部の詳細を示す図である。
【図１８】検査行列の生成方法の説明図である。
【図１９】ブロック単位での行演算処理部から列演算処理部への値の受け渡し方を示す図である。
【図２０】図１８の生成方法で生成された検査行列Ｈ（列重み＝３）の例である。
【図２１】情報交換部の一例を示す図である。
【図２２】情報交換部の他の例を示す図である。
【図２３】情報交換部の他の例を示す図である。
【図２４】情報交換部の他の例を示す図である。
【図２５】情報交換部の他の例を示す図である。
【図２６】検査行列の一例を示す図である。
【図２７】第２実施形態に係る処理部を示す図である。
【図２８】検査行列の列の入れ替えの説明図である。
【図２９】入力データの与え方の説明図である。
【図３０】第３実施形態に係る処理部を示す図である。
【図３１】他の分割方法の説明図である。
【図３２】実施形態に係る他の分割方法の説明図である。
【符号の説明】
【０１６５】
４  復調器
５  復号化器
６  対数尤度比算出部
７  復号処理部（処理部）
１９Ａ  行演算処理部
１９Ｂ  行演算処理部
２０Ａ  列演算処理部
２０Ｂ  列演算処理部
７１  部分処理回路
７２  部分処理回路
７４  配線（情報送信配線）
９０Ａ  行処理部
１００Ａ  列処理部
１４２Ａ  情報交換部（取得部；送信部）
１４２Ｂ  情報交換部（取得部；送信部）
１４３Ａ  情報交換部（取得部；送信部）
１４３Ｂ  情報交換部（取得部；送信部）
２００  入替部
２０１  入替部
２１０Ａ  制御部
２２０Ｂ  制御部
【図１】
2008288710.tif 000009
【図２】
2008288710.tif 000010
【図３】
2008288710.tif 000011
【図４】
2008288710.tif 000012
【図５】
2008288710.tif 000013
【図６】
2008288710.tif 000014
【図７】
2008288710.tif 000015
【図８】
2008288710.tif 000016
【図９】
2008288710.tif 000017
【図１０】
2008288710.tif 000018
【図１１】
2008288710.tif 000019
【図１２】
2008288710.tif 000020
【図１３】
2008288710.tif 000021
【図１４】
2008288710.tif 000022
【図１５】
2008288710.tif 000023
【図１６】
2008288710.tif 000024
【図１７】
2008288710.tif 000025
【図１８】
2008288710.tif 000026
【図１９】
2008288710.tif 000027
【図２０】
2008288710.tif 000028
【図２１】
2008288710.tif 000029
【図２２】
2008288710.tif 000030
【図２３】
2008288710.tif 000031
【図２４】
2008288710.tif 000032
【図２５】
2008288710.tif 000033
【図２６】
2008288710.tif 000034
【図２７】
2008288710.tif 000035
【図２８】
2008288710.tif 000036
【図２９】
2008288710.tif 000037
【図３０】
2008288710.tif 000038
【図３１】
2008288710.tif 000039
【図３２】
2008288710.tif 000040