(57)【特許請求の範囲】
【請求項１】
パリティ検査行列に基づく行処理及び列処理を繰り返し行うパリティ検査復号装置において、
行処理の演算結果及び列処理の演算結果を記憶する記憶部と、
前記記憶部から取得した前記列処理の演算結果を用いて、前記パリティ検査行列に基づく行処理を行って、行処理の演算結果を前記記憶部へ出力する行処理部と、
前記記憶部から取得した前記行処理の演算結果を用いて、前記パリティ検査行列に基づく列処理を行って、列処理の演算結果を前記記憶部へ出力する列処理部と、
復号過程を制御する制御部と、
を備え、
前記行処理部は、パリティ検査行列の一部の複数行についての行処理を行う部分行処理部として構成され、
前記列処理部は、パリティ検査行列の一部の複数列についての列処理を行う部分列処理部として構成され、
前記制御部は、前記部分行処理部及び／又は前記部分列処理部が実行すべき行及び／又は列の順番を制御するとともに、制御された当該順番に応じて、前記部分行処理部及び／又は前記部分列処理部による前記記憶部へのアクセスを制御し、
前記記憶部は、
前記部分行処理部による行処理演算結果を記憶する第１の記憶部と、
前記部分列処理部による列処理演算結果を記憶する第２の記憶部と、
を有し、
前記第１の記憶部は、一つのエントリについて複数の行処理演算結果を記憶可能である記憶装置を、複数有することで、複数のエントリを備えており、各エントリについて指定されたアドレスに記憶された行処理演算結果が、前記部分列処理部へ出力されるよう構成され、
前記第２の記憶部は、一つのエントリについて複数の列処理演算結果を記憶可能である記憶装置を、複数有することで、複数のエントリを備えており、各エントリについて指定されたアドレスに記憶された列処理演算結果が、前記部分行処理部へ出力されるよう構成され、
前記部分列処理部によって同時に列処理が実行される複数の列に含まれる非零要素に対応する複数の行処理演算結果が、前記第１の記憶部を構成する複数の記憶装置の同一アドレスに格納され、
前記部分行処理部によって同時に行処理が実行される複数の行に含まれる非零要素に対応する複数の列処理演算結果が、前記第２の記憶部を構成する複数の記憶装置の同一アドレスに格納され、
前記制御部は、
前記部分行処理部が、前記第２の記憶部から列処理演算結果を取得する際には、前記部分行処理部が同時に行処理を実行する複数の行に含まれる非零要素に対応する複数の列処理演算結果が格納された一つのアドレスを、前記第２の記憶部の前記複数のエントリについて指定し、
前記部分列処理部が、前記第１の記憶部から行処理演算結果を取得する際には、前記部分列処理部が同時に列処理を実行する複数の列に含まれる非零要素に対応する複数の行処理演算結果が格納された一つのアドレスを、前記第１の記憶部の前記複数のエントリについて指定する
ことを特徴とするパリティ検査復号装置。
【請求項２】
前記部分行処理部及び／又は前記部分列処理部がアクセスする記憶装置を選択するための選択部を備え、
前記制御部は、前記選択部を制御することにより、前記部分行処理部及び／又は前記部分列処理部による前記記憶部へのアクセスを制御することを特徴とする請求項１記載のパリティ検査復号装置。
【請求項３】
前記制御部は、前記部分行処理部及び／又は前記部分列処理部が、前記複数の記憶装置のうち、どの記憶装置にいつアクセスするかを規定したスケジュールデータを有し、
前記制御部は、前記スケジュールデータに基づいて、前記選択部を制御することを特徴とする請求項２記載のパリティ検査復号装置。
【請求項４】
前記制御部は、前記部分行処理部が実行すべき行の順番については、パリティ検査行列における行の並びとは異なる順番になるように制御するとともに、前記部分列処理部が実行すべき列の順番については、パリティ検査行列における列の並びと同じ順番になるように制御することを特徴とする請求項１〜３のいずれかに記載のパリティ検査復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パリティ検査復号装置に関するものである。
【背景技術】
【０００２】
誤り訂正技術の一つとして、低密度パリティ検査（ＬＤＰＣ：Low-Density Parity-Check）符号と、その復号法であるsum−product復号法とが注目されている（特許文献１参照）。この符号の特性は、白色ガウス通信路のシャノン（Shannon）限界まで、０．００４ｄＢという復号特性が得られることが知られている。
【０００３】
ＬＤＰＣ符号は、理論上、すべての行についての行処理を同時に行うことができるとともにすべての列についての列処理を同時に行う全並列処理が可能であるため、高速な処理が可能である。
しかし、全ての行又は列についての演算を同時に行うには、回路が複雑で規模が大きくなり実現が困難である。
そこで、ＬＤＰＣの復号処理について回路技術を使って実現する場合、計算量を低減したmin-sum復号法が有効と考えられている。しかし、回路規模としてはまだ十分な大きさまで低減されていないのが現状である。
【０００４】
そこで、非特許文献１では、並列計算処理について、近似的なシリアル計算処理を施すことで、回路の小型化を図っている。
また、非特許文献２では、ビットシリアル（Bit-serial）処理に基づく部分並列処理型のＬＤＰＣデコーダが提案されている。
非特許文献１のものでは、完全なシリアル処理になるため、処理速度が低下するが、非特許文献２のものでは、処理速度を早くすることができる。
【特許文献１】特開２００５−２６９５３５号公報
【非特許文献１】Darabiha, A ,A bit-serial approximate min-sum LDPC decoder and FPGA implementation Proc.  IEEE ISCA2006
【非特許文献２】Kazuhiro Shimizu "Partially-Parallel LDPC Decoder Based on High Efficiency Message-Passing Algorithm", Proc. IEEE ICCD2005,pp.503-510
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１，２におけるビットシリアル処理においては、回路を小型化できる。しかし、ビットシリアル処理においては、アルゴリズムの特性上、受信信号を前から順に処理していくため、その復号結果は受信信号系列の前の方のデータに大きく依存する。この結果、受信信号系列の前の方に誤りが集中したデータを受け取った場合、正常に復号できない可能性が高い。
【０００６】
そこで、本発明は、ビットシリアル処理を用いることなく回路を小型化しつつ処理速度の低下を防止するとともに、復号性能が損なわれるのを防止するのに適したパリティ検査復号装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、パリティ検査行列に基づく行処理及び列処理を繰り返し行うパリティ検査復号装置において、行処理の演算結果及び列処理の演算結果を記憶する記憶部と、前記記憶部から取得した前記列処理の演算結果を用いて、前記パリティ検査行列に基づく行処理を行って、行処理の演算結果を前記記憶部へ出力する行処理部と、前記記憶部から取得した前記行処理の演算結果を用いて、前記パリティ検査行列に基づく列処理を行って、列処理の演算結果を前記記憶部へ出力する列処理部と、復号過程を制御する制御部と、を備え、前記行処理部は、パリティ検査行列の一部の複数行についての行処理を行う部分行処理部として構成され、前記列処理部は、パリティ検査行列の一部の複数列についての列処理を行う部分列処理部として構成され、前記制御部は、前記部分行処理部及び／又は前記部分列処理部が実行すべき行及び／又は列の順番を制御するとともに、制御された当該順番に応じて、前記部分行処理部及び／又は前記部分列処理部による前記記憶部へのアクセスを制御することを特徴とするパリティ検査復号装置である。
【０００８】
上記本発明によれば、行処理部が部分行処理部として構成されているとともに列処理部が部分列処理部として構成され部分並列処理が可能となっているため、全並列処理の場合に比べて行処理部及び列処理部の回路サイズを小さくすることができる。
しかも、部分行処理部及び部分列処理部の演算結果を記憶する記憶部を有しているため、行処理又は列処理を部分的に順次実行した結果を、記憶部に蓄積することができる。
つまり、行処理をすべての行について同時に行ったり、列処理をすべての列について同時に行ったりしなくても、部分的な行処理又は列処理を行って、その結果を順次、記憶部に記憶させることができる。したがって、すべての行又は列についての行処理演算結果又は列処理演算結果が記憶部に蓄積される。
【０００９】
さらに本発明では、行処理部及び／又は列処理部が実行すべき行及び／又は列の順番を制御する制御部を備えているため、行処理後の列処理を可能な限り早く実行できるように行の順番を制御するか、又は列処理後の行処理を可能な限り早く実行できるように列の順番を制御することができる。
また、制御部は、部分行処理部及び／又は部分列処理部が実行すべき行及び／又は列の順番に応じて、部分行処理部及び／又は部分列処理部による前記記憶部へのアクセスを制御するため、行又は列の順番を制御しても適切な記憶部へのアクセスが行われる。
【００１０】
また、前記記憶部は、一つのエントリについて複数の演算結果を記憶可能である記憶装置を複数有して構成され、前記部分行処理部及び／又は前記部分列処理部がアクセスする記憶装置を選択するための選択部を備え、前記制御部は、前記選択部を制御することにより、前記部分行処理部及び／又は前記部分列処理部による前記記憶部へのアクセスを制御するのが好ましい。この場合、記憶部が、一つのエントリについて複数の演算結果を記憶可能である記憶装置を複数有して構成されているため、エントリの数を少なくでき、記憶部の回路構成が簡素になる。しかも、エントリの数を少なくしても、部分行処理部及び／又は部分列処理部がアクセスする記憶装置を選択するための選択部を備えているため、適切な記憶装置へのアクセスが可能である。
【００１１】
前記制御部は、前記部分行処理部及び／又は前記部分列処理部が、前記複数の記憶装置のうち、どの記憶装置にいつアクセスするかを規定したスケジュールデータを有し、前記制御部は、前記スケジュールデータに基づいて、前記選択部を制御するのが好ましい。この場合、部分行処理部及び／又は前記部分列処理部が、複数の記憶装置のうち、どの記憶装置にいつアクセスするかをスケジュールデータでよって設定できるため、記憶部へのアクセススケジュールをハードウェアの変更を伴わずに容易に設計変更できる。そして、スケジュールデータを適切に設定することで、記憶部へのアクセスのために部分行処理部又は部分列処理部の待ち時間を減少させることができる。
【００１２】
前記制御部は、前記部分行処理部が実行すべき行の順番については、パリティ検査行列における行の並びとは異なる順番になるように制御するとともに、前記部分列処理部が実行すべき列の順番については、パリティ検査行列における列の並びと同じ順番になるように制御するのが好ましい。
この場合、部分行処理部が実行すべき行の順番については、列処理が可能な限り早く実行できるように適切な順番に制御することで、処理速度を向上させることができる。
一方、パリティ検査行列の列の並びは、受信信号系列の順序に対応するため、部分列処理部が実行すべき列の順番をパリティ検査行列の列の並びから変えると、検査行列に基づく演算結果を並び替える必要が生じるが、本発明のようにパリティ検査行列における列の並びの順番から変えずに同じ順番で制御することで、そのような並び替えが不要となって処理遅延を防止できる。
【発明の効果】
【００１３】
本発明によれば、回路を小型化しつつ処理速度の低下を防止するとともに復号性能が損なわれるのを防止するのに適したパリティ検査復号装置が得られる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態を、図面を参照して説明する。
図１は、本発明の実施形態に係る復号装置（復号器）を有する通信システムの構成の一例を示す図である。
図１において、通信システムは、送信側において、送信情報に誤り訂正用の冗長ビットを付加して送信符号を生成する符号化器１と、この符号化器１からの（Ｋ＋Ｍ）ビットの符号を所定の方式に従って変調して通信路３へ出力する変調器２とを含む。
【００１５】
符号化器１は、Ｋビットの情報に対し、パリティ計算用の冗長ビットＭビットを付加して、（Ｋ＋Ｍ）ビットのＬＤＰＣ（低密度パリティ検査）符号化データを生成する。低密度パリティ検査行列においては、行が冗長ビットに対応し、列が符号ビットに対応する。なお、（Ｋ＋Ｍ）ビットのＬＤＰＣ符号化データのどのビットに、Ｋ個の情報ビット及びＭ個の冗長ビットを配置するかは、送信側と受信側で取り決めていれば、どのように配置してもよい。
【００１６】
変調器２は、この通信路３の構成に応じて、振幅変調、位相変調、コード変調、周波数変調または直交周波数分割多重変調などの変調を行なう。たとえば、通信路３が、光ファイバの場合、変調器２においては、レーザダイオードの輝度を送信情報ビット値に応じて変更させることにより、光の強度変調（一種の振幅変調）を行なっている。たとえば、送信データビットが“０”の場合には、”＋１”に変換して、レーザダイオードの発光強度を強くして送信し、また送信データビットが“１”の場合、”−１”に変換して、レーザダイオードの発光強度を弱くして送信する。
【００１７】
通信システムは、受信側においては、通信路３を介して送信された変調信号に復調処理を施して、（Ｋ＋Ｍ）ビットのデジタル符号を復調する復調器４と、この復調器４からの（Ｋ＋Ｍ）ビットの符号にパリティ検査行列に基づく復号処理を施して元のＫビットの情報を再生する復号器（復号装置）５が設けられる。
【００１８】
復調器４は、この通信路３における送信形態に応じて復調処理を行なう。たとえば、振幅変調、位相変調、コード変調、周波数変調および直交周波数分割多重変調等の場合、復調器４において、振幅復調、位相復調、コード復調、および周波数復調等の処理が行なわれる。
【００１９】
図２は、通信路３が光ファイバの場合の変調器２および復調器４の出力データの対応関係を一覧にして示す図である。図２において、上述のように、通信路３が光ファイバの場合、変調器２においては、送信データが“０”のときには、”１”に変換され、送信用のレーザダイオード（発光ダイオード）の発光強度が強くなり、また送信データビットが“１”のときには、”−１”に変換され、レーザダイオードの発光強度を弱くして送信する。
【００２０】
この通信路３における伝送損失等により、復調器４に伝達される光強度は、最も強い強度から最も弱い強度までの間のアナログ的な強度分布を有する。復調器４においては、この入力された光信号に、量子化処理（アナログ／デジタル変換）を行なって、この受光レベルを検出する。
図２においては、８段階に受光レベルが量子化された場合の受信信号強度を示す。すなわち、受光レベルがデータ“７”のときには、発光強度がかなり強く、受光レベルが“０”のときには、光強度がかなり弱い状態である。各受光レベルは、符号付きデータに対応づけられ、復調器４から出力される。この復調器４の出力は、受光レベルが“７”のときにはデータ“３”が出力され、受光レベルが“０”のときには、データ“−４”が出力される。したがってこの復調器４からは、１ビットの受信信号に対し、多値量子化された信号が出力される。
【００２１】
復号器５は、この復調器４から与えられた（Ｋ＋Ｍ）ビットの受信情報（各ビットは、多値情報を含む）の入力を受け、sum-product復号法又はmin-sum復号法に従ってＬＤＰＣパリティ検査行列を適用して、元のＫビットの情報を復元する。
【００２２】
なお、この図２においては、復調器４において、８レベルに量子化されたビットが生成されている。しかしながら、一般に、この復調器４においては、Ｌ値（Ｌ≧２）に量子化されたビットを用いて復号処理を行なうことができる。
【００２３】
また、図２においては、比較器を用いて、あるしきい値を使って受信信号のレベルを判定し、２値信号を生成してもよい。
【００２４】
図３は、復号器５の構成を概略的に示す図である。この図３においては、復調器４および通信路３も併せて示す。復調器４は、通信路３から与えられた信号を復調する復調回路４ａと、この復調回路４ａにより生成されたアナログ復調信号をデジタル信号に変換するアナログ／デジタル変換回路４ｂを含む。
このアナログ／デジタル変換回路４ｂの出力データ（符号化データ）Ｘｎが復号器５へ与えられる。
【００２５】
復号器５へ与えられる符号化データＸｎは、Ｌ値（Ｌ≧２）のデータである。以下、符号化データＸｎは、多値量子化データであるため、シンボルと称す。復号器５は、この入力シンボルＸｎ系列に対しsum-product復号法又はmin-sum復号法などの復号法に従って復号処理を行なって復号ビットＣｎを復号データとして生成する。
【００２６】
復号器５は、復調器４からの復調シンボルＸｎの対数尤度比λｎを生成する対数尤度比算出部６を備えている。
対数尤度比算出部６は、この受信信号のノイズ情報と独立に、対数尤度比λｎを生成する。通常、ノイズ情報を考慮した場合、この対数尤度比λｎは、Ｘｎ／（２・σ・σ）で与えられる。ここで、σは、ノイズの分散を示す。
しかしながら、本実施の形態においては、この対数尤度比算出部６は、バッファ回路または定数乗算回路で形成され、対数尤度比λｎは、Ｘｎ・ｆで与えられる。ここで、fは非ゼロの正の数である。また、min-sum復号方法においては、検査行列に基づく復号処理（行処理）において、最小値を利用して演算を行なうため、信号処理において線形性が維持される。このため、ノイズ情報に従って出力データを正規化するなどの処理は不要である。この場合ノイズ情報を利用せずに、対数尤度比を算出することにより、回路構成が簡略化され、また計算処理も簡略化される。
【００２７】
また、復号器５は、パリティ検査行列の行処理を行なう行処理部９と、パリティ検査行列の列処理を行なう列処理部１０と、を備えている。
【００２８】
復号法がsum-product復号法である場合、行処理部９及び列処理部１０は、次式（１）及び（２）にしたがって、演算処理を行い、パリティ検査行列の行の各要素（非零要素）についての処理（行処理）、及び列についての各要素（非零要素）についての処理（列処理）を繰り返し実行する。
具体的には、行処理部９が、次式（１）にしたがって外部値対数比（第１変数）αｍｎを算出する演算を行い、列処理部１０が、次式（２）にしたがって事前値対数比βｍｎを算出する演算を行う。
【数１】
0004803134.tif 000002
【００２９】
ここで、上式（１）および（２）それぞれにおいて、ｎ’∈Ａ（ｍ）＼ｎおよびｍ’∈Ｂ（ｎ）＼ｍは、自身を除く要素を意味する。
外部値対数比αｍｎについては、ｎ’≠ｎであり、事前値対数比βｍｎについては、ｍ’≠ｍである。また、αおよびβの行列内の位置を示す添え字“ｍｎ”は、通常は下付文字で示されるが、本明細書においては、読みやすさのために、「横並びの文字」で示す。
なお、式（１）中において、ｆは、ギャラガ（Gallager）のｆ関数である。
【００３０】
また、関数ｓｉｇｎ（ｘ）は、次式（３）で定義される。
【数２】
0004803134.tif 000003
【００３１】
また、集合Ａ（ｍ）およびＢ（ｎ）は、２元Ｍ・Ｎ行列Ｈ＝［Ｈｍｎ］を復号対象のＬＤＰＣ符号の検査行列とした場合、集合［１，Ｎ］＝｛１，２，…，Ｎ｝の部分集合である。
Ａ（ｍ）＝｛ｎ：Ｈｍｎ＝１｝ …（４）
Ｂ（ｎ）＝｛ｍ：Ｈｍｎ＝１｝ …（５）
【００３２】
すなわち、上記部分集合Ａ（ｍ）は、検査行列Ｈの第ｍ行目において１（非零要素）が立っている列インデックスの集合を意味し、部分集合Ｂ（ｎ）は、検査行列Ｈの第ｎ列目において１（非零要素）が立っている行インデックスの集合を示す。
【００３３】
具体的に、今、図４に示す検査行列Ｈを考える。この図４に示す検査行列Ｈにおいては、第１行の第１列から第３列に“１”が立ち、また第２行の第３列および第４列に“１”が立ち、また第３行の第４列から第６列に、“１”が立つ。したがって、この場合、部分集合Ａ（ｍ）は以下のようになる。
【００３４】
Ａ（１）＝｛１，２，３｝
Ａ（２）＝｛３，４｝
Ａ（３）＝｛４，５，６｝
【００３５】
同様に、部分集合Ｂ（ｎ）については、以下のようになる。
Ｂ（１）＝Ｂ（２）＝｛１｝
Ｂ（３）＝｛１，２｝
Ｂ（４）＝｛２，３｝
Ｂ（５）＝Ｂ（６）＝｛３｝
【００３６】
この検査行列Ｈにおいて、タナー（Tanner）グラフを用いた場合、列に対応する変数ノードと行に対応するチェックノードの接続関係が、この“１”により示される。これを、本明細書においては「“１”が立つ」と称している。すなわち、図５に示すように、変数ノード１，２，３は、チェックノードＸ（第１行）に接続され、変数ノード３，４が、チェックノードＹ（第２行）に接続される。変数ノード４，５，６が、チェックノードＺ（第３行）に接続される。この変数ノードが検査行列Ｈの列に対応し、チェックノードＸ，ＹおよびＺが、この検査行列Ｈの各行に対応する。従って、図４に示す検査行列は、情報ビットが３ビット、冗長ビットが３ビットの合計６ビットの符号長の符号に対して適用される。
【００３７】
ＬＤＰＣの検査行列Ｈでは、“１”の数は少なく、低密度の検査行列であり、これにより、計算量を低減できる。
【００３８】
この変数ノードとチェックノードの間で各条件確率Ｐ（Ｘｉ｜Ｙｉ）を伝播させ、ＭＡＰアルゴリズムに従って、もっともらしい符号を各変数ノードについて決定する。ここで、条件付確率Ｐ（Ｘｉ｜Ｙｉ）は、Ｙｉの条件下でＸｉとなる確率を示す。
【００３９】
図３に戻り、復号器５は、行処理部９の演算結果である外部値対数比αｍｎ及び列処理の部１０の演算結果である事前値対数比βｍｎを記憶する記憶部１１を備えている。
行処理部９は、記憶部１１から事前値対数比βｍｎ（初期値は０）を取得し、取得したβｍｎと対数尤度比λｎとから、上式（１）に基づいて行処理演算を行う。行処理部９は、行処理の演算結果である外部値対数比αｍｎを、直接、列処理部１０に与えるのではなく、記憶部１１に対して出力する。記憶部１１に記憶されている外部値対数比αｍｎは、行処理部９から出力された外部値対数比αｍｎによって更新される。
【００４０】
列処理部１０は、記憶部１１から外部値対数比αｍｎを取得し、取得したαｍｎを用いて、上式（２）に基づいて列処理演算を行う。列処理部１０は、列処理の演算結果を、直接、行処理部９に与えるのではなく、記憶部１１に対して出力する。記憶部１１に記憶されている事前値対数比βｍｎは、列処理部９から出力された事前値対数比βｍｎによって更新される。
【００４１】
復号器５は、行処理及び列処理からなる復号演算の反復終了を判定するループ判定部１２を備えている。この判定部１２は、行処理及び列処理の反復回数が、終了回数に達したか否かを判定し、行処理と列処理の繰り返し回数が終了回数に達すると、復号演算の反復を終了させる。
【００４２】
また、判定部１２は、復号演算の反復が終了した後、外部値対数比αｍｎと対数尤度比λｎとを用いて符号を判定する機能を有している。
具体的には、判定部１１は、次式（６）に従って、Ｑｎを算出する。
【００４３】
【数３】
0004803134.tif 000004
【００４４】
さらに、判定部１１は、次式（７）に従って、推定符号Ｃｎを算出する。
【数４】
0004803134.tif 000005
【００４５】
さて、前記行処理部９は、図３に示すように、パリティ検査行列の任意の１行についての行処理を行って、当該行に含まれる非零要素についての外部値対数比αｍｎを算出する行計算部９ａ，９ｂを複数有して構成されている。本実施形態において、行計算部９ａ，９ｂは、復号処理に用いられるパリティ検査行列の行数分設けられているわけではなく、パリティ検査行列の行数よりも少ない数しか設けられていない。
つまり、行処理部９によって同時に行える行処理は、パリティ検査行列の一部の複数行についてのみであり、部分的な行処理部として構成されている。本実施形態では、部分的な行処理をシリアル的に実行することで、パリティ検査行列の全ての行についての行処理が行われる。
なお、本実施形態では、行処理部９が同時に処理できる複数の行を「行ブロック」というものとする。
【００４６】
ここで、パリティ検査行列として、図６（ａ）に示す検査行列Ｈを想定する。このパリティ検査行列Ｈは、６行×１２列である。図３の行処理部９は、第１行計算部９ａと第２行計算部９ｂの２つが設けられており、同時に２行の部分行処理が可能である。したがって、行処理部９では、３回の部分行処理の実行により、検査行列Ｈの全ての行（６行）についての行処理を行うことができる。
【００４７】
また、前記列処理部１０も、図３に示すように、パリティ検査行列の任意の１列についての列処理を行って、当該列に含まれる非零要素についての事前値対数比βｍｎを算出する列計算部１０ａ，１０ｂを複数有して構成されている。列計算部１０ａ，１０ｂも、復号処理に用いられるパリティ検査行列の列数分設けられているわけではなく、パリティ検査行列の列数よりも少ない数しか設けられていない。
つまり、列処理部９によって同時に行える列処理は、パリティ検査行列Ｈの一部の複数列についてのみであり、部分的な列処理部として構成されている。本実施形態では、部分的な列処理をシリアル的に実行することで、パリティ検査行列の全ての列についての列処理が行われる。
【００４８】
図３の列処理部１０は、第１列計算部１０ａと第２列計算部１０ｂの２つが設けられており、同時に２列の部分列処理が可能である。したがって、列処理部１０では、６回の部分行処理の実行により、図６（ａ）に示す検査行列Ｈの全ての列（１２列）についての列処理を行うことができる。
【００４９】
上記のような行処理部９と列処理部１０とで、図６（ａ）に示す検査行列Ｈに基づく行処理及び列処理を、その行及び列の並びの順番に従って行う場合、図６（ｂ）に示すように、９クロックの時間を要する。
つまり、検査行列Ｈの行及び列の並びの順番に従って行処理及び列処理を実行する際には、まず、最初の２行（図６（ａ）の行ブロックＡ）の部分行処理が行われ、順次、次の２行（図６（ａ）の行ブロックＢ）、最後の２行（図６（ａ）の行ブロックＣ）についての部分行処理行われて、これらがすべて完了して始めて、列処理が行える。列処理も、まず、最初の２列（図７（ａ）の列ブロック（１））の部分列処理が行われ、順次、２列ずつの部分列処理が最後の２列（図６（ａ）の列ブロック（６））まで行われる。以上が、行処理及び列処理の１サイクルであり、１サイクルあたり９クロックの時間を要する。なお、このサイクルの繰り返しループが、ループ判定部１２によって終了と判定されるまで繰り返されることになる。
【００５０】
これに対し、本実施形態の復号器５では、行処理及び／又は列処理において処理対象となる行（行ブロック）及び／又は列（列ブロック）の順番を制御するための制御部１４を備えており、検査行列Ｈの行及び列の並びの順番とは異なる順番で、行処理及び／又は列処理を行うことが可能である。
【００５１】
図７（ａ）は、図６に示す検査行列Ｈの行の配置を入れ替えた第１入替検査行列Ｈ1を示している。なお、検査行列Ｈ1は、検査行列Ｈの行のみを入れ替えたもので、列については入替を行っていない。第１入替検査行列Ｈ1は、図８に示す検査行列Ｈと第１入替検査行列Ｈ1との行変換対応表に従って、検査行列Ｈの行の配置を入れ替えたものである。なお、行処理において処理対象となる行の順番を代えるだけであれば、復号特性に影響はない。つまり、復号特性からみると検査行列Ｈと第１入替検査行列Ｈ1とは等価である。なお、列の順番を変えた場合も、列処理結果を、復号される受信信号系列の順番（つまり、検査行列Ｈの列の並びの順番）に戻せば、復号特性は変化しない。
【００５２】
図７（ａ）に示す第１入替検査行列Ｈ1の左下隅にある行ブロックＣの列ブロック（１）の部分に着目すると、行ブロックＣの列ブロック（１）の部分には、零要素しかなく非零要素（“１”）がない。一方、列ブロック（１）の行ブロックＡ，Ｂの部分には、非零要素が含まれる。したがって、列ブロック（１）についての列処理を行うには、行ブロックＡ，Ｂについての行処理が完了している必要があるが、行ブロックＣについての行処理が完了している必要はない。つまり、行ブロックＡ，Ｂについての行処理が完了すれば、列ブロック（１）についての列処理を開始できる。
【００５３】
図７（ｂ）は、これを利用して、行処理と列処理を部分的に並列処理化した場合の処理順序を示しており、行ブロックＣの行処理実行と列ブロック（１）の列処理実行を並列的に行うことで、行処理及び列処理の１サイクルの所要時間を８クロックに短縮することができる。
【００５４】
制御部１４は、行処理部９及び列処理部１０に図７（ｂ）に従った順番で行処理及び列処理を実行させるための指令を出力する。具体的には、制御部１４は、行処理部９に、検査行列Ｈ1の行の並びに従って行処理を行わせるとともに、検査行列Ｈ1の列の並びに従って列処理を行わせる。
【００５５】
より具体的には、制御部１４は、行処理部９に、最初に検査行列Ｈ1の行ブロックＡについての行処理を実行させる。これは、検査行列Ｈからみると、１行目と４行目についての行処理を最初に行うことになる。
【００５６】
つまり、制御部１４は、行処理部９に、検査行列Ｈの１行目と４行目の非零要素についての各βｍｎの値が記憶されているアドレスを指定する。行処理部９は、当該アドレスを用いてβｍｎの値を記憶部１１から取得する。そして、行処理部９は、λｎの値をも用いて、式（１）に従って、検査行列Ｈの１行目と４行目の非零要素についてのαｍｎをそれぞれ算出する。
さらに、制御部１４は、行処理部９に、検査行列Ｈの１行目と４行目の非零要素についてのαｍｎが記憶されるアドレスを指定する。行処理部９は、算出されたαｍｎを、当該アドレスに従って、記憶部１１に書き込む。これにより、当該αｍｎについての記憶部１１の値が更新される。
【００５７】
同様に、制御部１４は、行処理部９に、検査行列Ｈ1の行ブロックＢについての行処理を実行させる。これは、検査行列Ｈからみると、６行目と３行目についての行処理を行うことになる。さらに、制御部１４は、行処理部９に、検査行列Ｈ1の行ブロックＣについての行処理を実行させる。これは、検査行列Ｈからみると、５行目と２行目についての行処理を行うことになる。
【００５８】
また、制御部１４は、行処理部９に検査行列Ｈ1の行ブロックＣについての行処理を実行させるのと同時に、列処理部１０に列処理を開始させる。
つまり、制御部１４は、列処理部１０に、検査行列Ｈ1の行ブロックＣについての行処理と並列的に、検査行列Ｈ1の列ブロック（１）についての列処理を実行させる。検査行列Ｈ1において列の入替は行われていないので、列処理については、検査行列Ｈ1の各列ブロックについての列処理と検査行列Ｈの各列ブロックについての列処理とは、実質的に等価である。
【００５９】
列処理の際、制御部１４は、列処理部１０に、検査行列Ｈ（検査行列Ｈ1）の１列目と２列目からなる列ブロック（１）の非零要素についてのαｍｎの値が記憶されている記憶部１１のアドレスを指定する。列処理部１０は、当該アドレスを用いてαｍｎの値を記憶部１１から取得し、式（２）に従って、検査行列Ｈ（検査行列Ｈ1）の１列目と２列目の非零要素についてのβｍｎをそれぞれ算出する。
制御部１４は、さらに、列処理部１０に、記憶部１１の検査行列Ｈ（検査行列Ｈ1）の１列目と２列目の非零要素についてのβｍｎが記憶されるアドレスを指定する。列処理部１０は、当該アドレスに従って、算出した各βｍｎを記憶部１１に書き込む。これにより。当該βｍｎについての記憶部１１の値が更新される。
【００６０】
ただし、各列に含まれる非零要素の位置は、検査行列Ｈと検査行列Ｈ1とでは異なるため、列処理部１０がβｍｎの値を記憶部１１から取得したり、αｍｎの値を記憶部１１に書き込んだりする際には、行の入替に伴う非零要素の位置の違いに対応しつつ記憶部１１へアクセスする。
なお、本実施形態の記憶部１１は、検査行列Ｈ1における非零要素の配置に従って、αｍｎ及びβｍｎの値を格納している。この点については後述する。
【００６１】
列ブロック（１）についての列処理が完了すると、続いて、制御部１４は、上記と同様に列処理部１０に、残りの列ブロック（２）〜（６）までの列処理を行わせる。
【００６２】
図７に示す第１入替検査行列Ｈ1に従って行処理を行うと、前述のように行処理及び列処理の１サイクルの所要時間が短くなるほか、処理結果であるβｍｎ又はαｍｎを受信信号系列の並びに合わせて並び替えるための処理が不要であるという利点がある。つまり、検査行列の列の並びは受信信号系列の並びに対応しているため、列を入れ替えると、最終的に、処理結果を受信信号系列の並びに入れ替える手間が必要となり、処理の遅延が生じる場合があるが、検査行列Ｈ1では列の入替がないため、並び替えに伴う処理の遅延が回避されている。
【００６３】
ただし、並び替えに伴う処理の遅延が問題とならない場合には、行だけでなく列も入れ替えても良い。図９は、図６に示す検査行列Ｈの行及び列を入れ替えた第２入替検査行列Ｈ2を示している。この第２入替検査行列Ｈ2は、図１０（ａ）に示す検査行列Ｈと第２入替検査行列Ｈ2との行変換対応表に従って、検査行列Ｈの行の配置を入れ替えた後に、図１０（ｂ）に示す検査行列Ｈと第２入替検査行列Ｈ2との列変換対応表に従って、列の配置も入れ替えたものである。
【００６４】
図９（ａ）に示す第２検査行列Ｈ2では、左下隅にある行ブロックＣの列ブロック（１）の部分のほか、右上済みにある行ブロックＡの列ブロック（６）の部分も、零要素しかない。したがって、行ブロックＡについての行処理を行うには、少なくとも列ブロック（６）についての列処理が完了している必要はない。つまり、列ブロック（１）〜（５）までの列処理が完了すれば、列ブロック（６）についての列処理が完了せずとも、行ブロックＡについての行処理を開始できる。
【００６５】
図９（ｂ）は、これを利用して、行処理と列処理を部分的に並列処理化した場合の処理順序を示しており、検査行列Ｈ1と同様に行ブロックＣの行処理実行と列ブロック（１）の列処理実行を並列的に行えるほか、列ブロック（６）の列処理実行と行ブロックＡの行処理実行を並列的に行うことができる。したがって、検査行列Ｈに比べると２クロック分の高速化が可能である。
【００６６】
図１１は、記憶部１１及び記憶部１１に関連した構成の詳細を示している。なお、以下では、制御部１４が制御する行又は列の順序の制御として、第１入替検査行列Ｈ1の行と列の並びに従う場合について説明する。
【００６７】
図１１に示すように、記憶部１１は、外部値対数比αｍｎの記憶部１１ａと、事前値対数比βｍｎの記憶部１１ｂとを有して構成されている。
各記憶部１１ａ，１１ｂは、半導体記憶装置からなり、一つのエントリについて複数のデータを記憶可能である記憶装置２１〜２２，３１〜３４を複数有して構成されている。以下では、それぞれの「記憶装置」を単に「メモリ」という。
各メモリは、一つのエントリしか有していないため、ある一つのメモリに記憶されている複数のデータへ同時にアクセス（読み取り又は書き込み）することはできず、同時には一つのデータのみアクセスが可能である。
ただし、複数のエントリへは同時にアクセス可能である。
【００６８】
βｍｎ記憶部１１ｂは、βｍｎが行処理の演算に用いられるため、行処理演算に適した構成が採用されている。具体的には、行処理部９が２つの行計算部９ａ，９ｂを有していることに対応して、βｍｎ記憶部１１ｂは、２つのメモリ群１１ｂ−１，１１ｂ−２を有している。
【００６９】
第１メモリ群１１ｂ−１は、検査行列Ｈ1の行のうち、第１行計算部９ａが実行を担う行（具体的には、検査行列Ｈ1の１行目、３行目、５行目であり、検査行列Ｈでは１行目、６行目、５行目に相当する）に含まれる非零要素（“１”）に対応するβｍｎを格納するためのものである。
第２メモリ群１１ｂ−２は、検査行列Ｈ1の行のうち、第２行計算部９ｂが実行を担う行（具体的には、検査行列Ｈ1の２行目、４行目、６行目であり、検査行列Ｈでは４行目、３行目、２行目に相当する）に含まれる非零要素（“１”）に対応するβｍｎを格納するためのものである。
【００７０】
βｍｎ記憶部１１ｂの各メモリ群１１ｂ−１，１１ｂ−２は、検査行列Ｈ1（検査行列Ｈ）の行重み（各行に含まれる非零要素の数）に応じた数（＝４）のメモリ（記憶装置）を有して構成されている。なお、検査行列Ｈ1（検査行列Ｈ）では、各行の行重みが一定（＝４）である。
【００７１】
βｍｎ記憶部１１ｂの各メモリ群１１ｂ−１，１１ｂ−２を構成するメモリ２１〜２８は、各行計算部９ａ，９ｂがそれぞれ３つの行の行処理を担当することに対応して、それぞれ、３つのデータを格納可能である。
つまり、第１メモリ群１１ｂ−１を構成する「メモリ１」２１〜「メモリ４」２４の「アドレス１」には、検査行列Ｈ1の１行目に含まれる非零要素に対応するβｍｎの値が格納され、同様に、「アドレス２」には３行目のβｍｎの値が格納され、「アドレス３」には５行目のβｍｎの値が格納されている。
また、第２メモリ群１１ｂ−２を構成する「メモリ５」２５〜「メモリ８」２８の「アドレス１」には、検査行列Ｈ1の２行目に含まれる非零要素に対応するβｍｎの値が格納され、同様に、「アドレス２」には４行目のβｍｎの値が格納され、「アドレス３」には６行目のβｍｎの値が格納されている。
なお、図１１では、βｍｎを、検査行列Ｈ1における非零要素の位置を示す座標形式表示「（行、列）」で表している。また、αｍｎについても同様である。
【００７２】
図１１に示すように、βｍｎ記憶部１１ｂには、検査行列Ｈ1における非零要素の配置に従ってβｍｎが格納されているとともに、同時に実行される行のβｍｎが同じアドレスに格納されているため、行処理部９がβｍｎ記憶部１１ｂから読み出し（データの取得）をする際には、βｍｎ記憶部１１ｂのアドレスを一つ指定すれば足りる。
つまり、検査行列Ｈ1の１行目及び２行目からなる行ブロックＡの行処理を実行する際に必要なβｍｎは、βｍｎ記憶部のメモリ１〜メモリ８のアドレス１に格納されているため、βｍｎ記憶部１１ｂの８個の全エントリについて「アドレス１」を指定すれば、行処理部９は、検査行列Ｈ1の１行目及び２行目のβｍｎを一気に取得でき、第１行計算部９ａと第２行計算部９ｂは同時に行処理を行うことができる。
【００７３】
また、検査行列Ｈ1の３行目及び４行目からなる行ブロックＢについては、「アドレス２」を指定すればよく、検査行列Ｈ1の５行目及び６行目からなる行ブロックＣについては、「アドレス３」を指定すればよい。
【００７４】
αｍｎ記憶部１１ａは、αｍｎが列処理の演算に用いられるため、列処理演算に適した構成が採用されている。具体的には、列処理部１０が２つの行計算部１０ａ，１０ｂを有していることに対応して、αｍｎ記憶部１１ａは、２つのメモリ群１１ａ−１，１１ａ−２を有している。
【００７５】
αｍｎ記憶部１１ａの第１メモリ群１１ａ−１は、検査行列Ｈ1の列のうち、第１列計算部１０ａが実行を担う列（具体的には、検査行列Ｈ1の１列目、３列目、５列目、７列目、９列目、１１列目）に含まれる非零要素（“１”）に対応するαｍｎを格納するためのものである。
αｍｎ記憶部１１ａの第２メモリ群１１ａ−２は、検査行列Ｈ1の行のうち、第２列計算部１０ｂが実行を担う行（具体的には、検査行列Ｈ1の２列目、４列目、６列目、８列目、１０列目、１２列目）に含まれる非零要素（“１”）に対応するαｍｎを格納するためのものである。
【００７６】
αｍｎ記憶部１１ａの各メモリ群１１ａ−１，１１ａ−２は、検査行列Ｈ1（検査行列Ｈ）の列重み（各列に含まれる非零要素の数）に応じた数（＝２）のメモリ（記憶装置）を有して構成されている。なお、検査行列Ｈ1（検査行列Ｈ）では、各列の列重みが一定（＝２）である。
【００７７】
αｍｎ記憶部１１ａの各メモリ群１１ａ−１，１１ａ−２を構成するメモリ３１〜３４は、各列計算部１０ａ，１０ｂが、それぞれ６つの列の列処理を担当することに対応して、それぞれ、６つのデータを格納可能である。
つまり、第１メモリ群１１ａ−１を構成する「メモリ１」３１及び「メモリ２」３２の「アドレス１」には、検査行列Ｈ1の１列目に含まれる非零要素に対応するαｍｎの値が格納され、同様に、「アドレス２」には３列目のαｍｎの値が格納され、「アドレス３」には５列目のαｍｎの値が格納され、「アドレス４」には７列目のαｍｎの値が格納され、「アドレス５」には９列目のαｍｎの値が格納され、「アドレス６」には１１列目のαｍｎの値が格納されている。
【００７８】
また、第２メモリ群１１ａ−２を構成する「メモリ３」３３及び「メモリ４」３４の「アドレス１」には、検査行列Ｈ1の２列目に含まれる非零要素に対応するαｍｎの値が格納され、同様に、「アドレス２」には４列目のαｍｎの値が格納され、「アドレス３」には６列目のαｍｎの値が格納され、「アドレス４」には８列目のαｍｎの値が格納され、「アドレス５」には１０列目のαｍｎの値が格納され、「アドレス６」には１２列目のαｍｎの値が格納されている。
【００７９】
上記のように、αｍｎ記憶部１１ａには、検査行列Ｈ1における非零要素の配置に従ってαｍｎが格納されているとともに、同時に実行される列のαｍｎが同じアドレスに格納されているため、列処理部１０がαｍｎ記憶部１１ａから読み出し（データの取得）をする際には、αｍｎ記憶部１１ａのアドレスを一つ指定すれば足りる。
つまり、検査行列Ｈ1の１列目及び２列目からなる列ブロック（１）の列処理を実行する際に必要なαｍｎは、αｍｎ記憶部１１ａのメモリ１〜メモリ４のアドレス１に格納されているため、αｍｎ記憶部１１ａの４個の全エントリについて「アドレス１」を指定すれば、列処理部９は、検査行列Ｈ1の１列目及び２列目のαｍｎを一気に取得でき、第１列計算部１０ａと第２列計算部１０ｂは同時に列処理を行うことができる。
【００８０】
また、検査行列Ｈ1の３列目及び４列目からなる列ブロック（２）については、「アドレス２」を指定すればよく、検査行列Ｈ1の５列目及び６列目からなる列ブロック（３）については、「アドレス３」を指定すればよく、検査行列Ｈ1の７列目及び８列目からなる列ブロック（４）については、「アドレス４」を指定すればよく、検査行列Ｈ1の９列目及び１０列目からなる列ブロック（５）については、「アドレス５」を指定すればよく、検査行列Ｈ1の１１列目及び１２列目からなる列ブロック（６）については、「アドレス６」を指定すればよい。
【００８１】
さて、本実施形態の記憶部１１のαｍｎ記憶部１１ａ及びβｍｎ記憶部１１ｂは、上記のように、データの読み出しは、行処理及び列処理の手順に合わせて、一気に行えるように、αｍｎ及びβｍｎを保持している。
一方、データの書き込みについては、行計算ブロック９ａ，９ｂの出力とαｍｎ記憶部１１ａのエントリとが直接対応しておらず、列計算ブロック１０ａ，１０ｂとβｍｎ記憶部１１ｂのエントリとも直接対応していないため、計算結果をどのエントリに与えるかを選択する必要がある。
しかも、一つのメモリには一つのデータしか同時に書き込めないところ、一つのメモリに対し同時に複数の計算結果を書き込む必要が生じる場合があるため、タイミングの調整も必要となる。
【００８２】
そこで、本実施形態では、図１１にも示すように、行処理部９の出力とαｍｎ記憶部１１ａのエントリの間に第１選択部１７が設けられ、列処理部１０の出力とβｍｎ記憶部１１ｂのエントリの間に第２選択部１８が設けられており、これら選択部１７，１８は、制御部１４によって制御される。そして、これら選択部１７，１８が制御部１４によって適切に制御されることで、行計算ブロック９ａ，９ｂ及び列計算ブロック１０ａ，１０ｂの出力を、適切に、記憶部１１に書き込むことができる。
【００８３】
図１２は、第１選択部１７の詳細を示している。第１選択部１７は、αｍｎ記憶部１１ａのメモリ３１〜３４のメモリエントリの数に応じた数（＝４）のマルチプレクサＭ１〜Ｍ４を有している。具体的には、第１選択部１７は、「メモリ１」３１にデータを出力するように接続された第１マルチプレクサＭ１、「メモリ２」３２にデータを出力するように接続された第２マルチプレクサＭ２、「メモリ３」３３にデータを出力するように接続された第３マルチプレクサＭ３、「メモリ４」３４にデータを出力するように接続された第４マルチプレクサＭ４を有している。
【００８４】
各マルチプレクサＭ１〜Ｍ４の入力側は、第１及び第２行計算部９ａ，９ｂの出力に対して、必要に応じて接続されている。
ここで、図１２に示すように、第１及び第２行計算部９ａ，９ｂは、それぞれ４つの出力９ａ−１〜９ａ−４，９ｂ−５〜９ｂ−８を有している。第１行計算部９ａの第１の出力９ａ−１は、βｍｎ記憶部１１ｂの「メモリ１」２１に記憶されているβｍｎと同座標の非零要素に対応するαｍｎを行計算結果として出力する。つまり、第１行計算部９ａが１行目の行処理を行う場合、「メモリ１」２１には（１，１２）＝１行１２列目についてのβｍｎの値が記憶されているから、第１行計算部９ａは、他のメモリ２２〜２４の値を用いて、（１，１２）＝１行１２列目についてのαｍｎの値を計算し、当該αｍｎを出力する。
【００８５】
同様に、第１行計算部９ａの第２の出力９ａ−２は、βｍｎ記憶部１１ｂの「メモリ２」２２に記憶されているβｍｎに対応するαｍｎを行計算結果として出力し、第２行計算部９ａの第３の出力９ａ−３は、βｍｎ記憶部１１ｂの「メモリ３」２３に記憶されているβｍｎに対応するαｍｎを行計算結果として出力し、第１行計算部９ａの第４の出力９ａ−４は、βｍｎ記憶部１１ｂの「メモリ４」２４に記憶されているβｍｎに対応するαｍｎを行計算結果として出力する。
また、第２行計算部９の第５の出力９ｂ−５〜第８の出力９ｂ−８についても同様である。
【００８６】
さて、前記第１マルチプレクサＭ１の入力側には、出力９ａ−１〜９ａ−４，９ｂ−５〜９ｂ−８のうち、第３出力９ａ−３、第４出力９ａ−４、第６出力９ｂ−６、及び第７出力９ｂ−７が接続されている。これは、第１マルチプレクサＭ１の出力が接続されているαｍｎ記憶部１１ａの「メモリ１」３１は、（１，１），（２，３），（４，５），（４，７），（３，９），（１，１１）の非零要素についてのαｍｎの値を格納するための領域となっており、これらのαｍｎの出力するのは、上記４つの出力９ａ−３、９ａ−４、９ｂ−６、９ｂ−７だからである。
【００８７】
同様の観点から、第２〜第４マルチプレクサＭ２〜Ｍ４の入力側にも、出力９ａ−１〜９ａ−４，９ｂ−５〜９ｂ−８のうち、必要な出力が接続されている。このように本実施形態では、必要な出力だけがマルチプレクサに接続されているため、配線の数を少なくできる。
なお、各マルチプレクサには、それぞれ、全出力９ａ−１〜９ａ−４，９ｂ−５〜９ｂ−８を接続してもよい。この場合、記憶部１１におけるαｍｎ及びβｍｎの配置に影響を受けない汎用的な回路構成が得られる。
【００８８】
前記制御部１４は、行処理部９が行処理演算結果をαｍｎ記憶部に書き込む際には、第１選択部の各マルチプレクサＭ１〜Ｍ４に対し、どの入力を出力するかを選択するための選択信号Ｃ１〜Ｃ４を出力する。
選択信号Ｃ１〜Ｃ４は、制御部１４が有するスケジュールデータ１４ａに基づいて生成される。図１３は、行処理部９が行処理演算結果をαｍｎ記憶部に書き込む際のスケジュールデータの一例を示している。
【００８９】
図１３のスケジュールデータにおいて、「座標」は、検査行列Ｈ1における非零要素の座標を示している。また、「時刻」は、当該座標の非零要素についての行処理が行われる時刻を示しており、図６（ｂ）の「時間」と対応している。「メモリ番号」は、「座標」で示される非零要素についての行処理計算結果であるαｍｎの値が書き込まれるαｍｎ記憶部１１のメモリ１〜４の番号を示している。「メモリアドレス」は、「座標」で示される非零要素についての行処理計算結果であるαｍｎの値が書き込まれるメモリのアドレスを示している。「切り替え番号」は、マルチプレクサによって選択されるマルチプレクサ入力番号（１〜４又は１〜５）を示している。なお、メモリ３１〜３４とマルチプレクサＭ１〜Ｍ４は一対一で対応しているため、「切り替え番号」が与えられるべきマルチプレクサは、「メモリ番号」によって特定される。
【００９０】
図１３に示すように、検査行列Ｈ1の１行目及び２行目からなる行ブロックＡについての行処理が行われる時刻「１」においては、例えば、座標（１，１）のαｍｎは、αｍｎ記憶部１１ａの「メモリ１」（＝メモリ番号：１）の「メモリアドレス１」に書き込まれるべきものである。そして、図１１及び図１２から明らかなように、座標（１，１）のαｍｎは、第１行計算部９ａの第３出力９ａ−４から出力され、第１マルチプレクサＭ１の第１入力に与えられている。
このため、第１マルチプレクサＭ１に与えられる選択信号Ｃ１としては、第１入力を選択するための「１」であればよく、この「１」が、座標（１，１）についての「切り替え番号」として図１３のスケジュールデータ１４ａに登録されている。
【００９１】
図１３のスケジュールデータ１４ａには、他の座標のαｍｎについても同様に、αｍｎ記憶部１１ａに書き込む際の「切り替え番号」が登録されている。
制御部１４は、このスケジュールデータ１４ａに従って、それぞれの「時刻」ごとに第１〜第４マルチプレクサＭ１〜Ｍ４への選択信号Ｃ１〜Ｃ４を生成し、各マルチプレクサＭ１〜Ｍ４へ与える。
【００９２】
ただし、図１３のスケジュールデータ例は単純なものであるため、例えば、検査行列Ｈ1の１行目及び２行目からなる行ブロックＡが処理される時刻「１」においては、「メモリ番号」＝１で特定される「メモリ１」３１への書き込みが３回必要である。
また、検査行列Ｈ1の３行目及び４行目からなる行ブロックＢが処理される時刻「２」においても、「メモリ番号」＝１で特定される「メモリ２」３２への書き込みが３回必要である。
【００９３】
このように、同一「時刻」において、同一メモリへの書き込みが必要な場合には、当該「時刻」を細分化したクロックに従って、各書き込みが順次行われるように、マルチプレクサＭ１〜Ｍ４の選択信号Ｃ１〜Ｃ４の出力タイミングをずらせばよい。この場合、メモリ書き込みのための処理遅延が発生する。この処理遅延の発生を回避するには、それぞれのαｍｎの値を、どのメモリのどのアドレスに置くかを工夫すればよく、そして、そのメモリ配置に応じて適切なスケジュールデータを決定すれば、前記処理遅延を回避できる。
なお、αｍｎのメモリ配置を図１１に示すものと異なるものにした場合、選択部を、βｍｎ記憶部１１ｂと行処理部９との間に設けて、当該選択部を制御するためのスケジュールデータを用意すればよい。
【００９４】
また、前記第２選択部１８についても、第１選択部１７と同様に構成されており、具体的には、βｍｎ記憶部１１ｂが８個のメモリ２１〜２８から構成されていることに対応して、８個のマルチプレクサＭ１１〜Ｍ１８から構成されている。各マルチプレクサＭ１１〜Ｍ１８の出力は、βｍｎ記憶部１１ｂの各メモリ２１〜２８のエントリに接続されている。列処理部１０と第２選択部の各マルチプレクサＭ１１〜Ｍ１８との間の詳細な配線は図示を省略するが、第１選択部１７と同様に、列計算部１０ａ，１０ｂの出力と、βｍｎ記憶部に記憶されるβｍｎとの関係に従って配線される。
なお、第２選択部１８においても、列計算部１０ａ，１０ｂの全出力を、それぞれのマルチプレクサＭ１１〜Ｍ１８の入力側に接続してもよく、この場合、回路の汎用性が広がる。
【００９５】
第２選択部１８の各マルチプレクサＭ１１〜Ｍ１８に対しても、制御部１４は、スケジュールデータ（図示省略）に従って生成した制御信号Ｃ１１〜Ｃ１８を与える。これにより、列処理部１０の計算結果であるβｍｎの値が、βｍｎの所定のメモリの所定のアドレスに書き込まれる。
【００９６】
なお、αｍｎ記憶部１１ａと列処理部１０との間に選択部を設けて、当該選択部を制御するためのスケジュールデータを用意してもよい。
【００９７】
以上のように構成することで、行処理部９及び／又は列処理部１０の処理結果を、スケジュールデータに従って制御される選択部１７，１８によって、記憶部９の所定のメモリの所定のアドレスに書き込むことができる。また、行処理部９及び／又は列処理部１０が処理に必要なαｍｎ又はβｍｎを、スケジュールデータに従って制御される制御部によって、記憶部９の所定のメモリの所定のアドレスから読み出すことができる。
したがって、記憶部９におけるαｍｎ及び／又はβｍｎの配置、及びスケジュールデータを適切に設定することで、本実施形態のような記憶部９においても、メモリアクセス遅延を小さくすることができる。
【００９８】
図１４は、検査行列Ｈの行の並びだけを入れ替えた第１入替検査行列Ｈ1の行及び列の並びに従って復号処理を行った場合（実施例）と、検査行列Ｈの行及び列の並びに従って復号処理を行った場合（比較例）の誤り率（ビットエラーレート）を示したものである。図１４に示すように、実施例と比較例では、ほぼ同じ誤り率であり、実施例のように行の並びを入れ替えても復号特性に影響がないことがわかる。
【００９９】
本発明は、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲で様々な変形が可能である。
例えば、復号法は、sum-product復号法に限らず、min-sum復号法であってもよい。
【図面の簡単な説明】
【０１００】
【図１】通信システムの構成を概略的に示す図である。
【図２】送信データと復調データの対応の一例を示す図である。
【図３】復号器の構成を示す図である。
【図４】検査行列の一例である。
【図５】図４に示す検査行列のタナーグラフである。
【図６】（ａ）は検査行列Ｈを示し、（ｂ）は、検査行列Ｈの行及び列の並びに従った場合の処理過程を示すタイミングチャートである。
【図７】（ａ）は検査行列Ｈ1を示し、（ｂ）は、検査行列Ｈ1の行及び列の並びに従った場合の処理改訂を示すタイミングチャートである。
【図８】検査行列Ｈから検査行列Ｈ1への行変換対応表である。
【図９】（ａ）は検査行列Ｈ2を示し、（ｂ）は、検査行列Ｈ2の行及び列の並びに従った場合の処理改訂を示すタイミングチャートである。
【図１０】（ａ）は検査行列Ｈから検査行列Ｈ2へ変換するための行変換対応表であり、（ｂ）は列変換対応表である。
【図１１】記憶部及びそれに関連する構成の説明図である。
【図１２】第１選択部及びそれに関連する構成の説明図である。
【図１３】スケジュールデータの例を示す図である。
【図１４】誤り率に関するグラフである。
【符号の説明】
【０１０１】
１：符号化器、２：変調器、３：通信路、４：復調器、４ａ：復調回路、４ｂ：アナログ／デジタル変換回路、５：復号器、６：対数尤度比算出部、９：行処理部、９ａ：第１計算部、９ｂ：第２計算部、１０：列処理部、１０ａ：第１列計算部、１０ｂ：第２列計算部、１１：記憶部、１１ａ：αｍｎ記憶部、１１ｂ：βｍｎ記憶部、１２：判定部、１４：制御部、１４ａ：スケジュールデータ、１７：第１選択部、１８：第２選択部、Ｍ１〜Ｍ８：マルチプレクサ、Ｍ１１〜Ｍ１８：マルチプレクサ
【図１】
0004803134.tif 000006
【図２】
0004803134.tif 000007
【図３】
0004803134.tif 000008
【図４】
0004803134.tif 000009
【図５】
0004803134.tif 000010
【図６】
0004803134.tif 000011
【図７】
0004803134.tif 000012
【図８】
0004803134.tif 000013
【図９】
0004803134.tif 000014
【図１０】
0004803134.tif 000015
【図１１】
0004803134.tif 000016
【図１２】
0004803134.tif 000017
【図１３】
0004803134.tif 000018
【図１４】
0004803134.tif 000019