(57)【特許請求の範囲】
【請求項１】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する通信装置において、
復号アルゴリズムにおける所定の処理により得られる中間値を保持する保持手段と、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値の最小値と、前記行処理用ＬＬＲの符号の乗算結果と、を乗算することにより、つぎの列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理手段と、
列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算し、さらに、行処理用ＬＬＲの絶対値の最小ｋ値を前記保持手段に保持する列処理、を実行する列処理手段と、
を備え、
前記行処理手段は、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、処理対象の列番号よりも小さい列番号については、繰り返しｌ回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、また、処理対象の列番号よりも大きい列番号については、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、さらに、それらの乗算結果同士を乗算し、
前記列処理手段が行の前記最小ｋ値を更新しながら復号を行うことを特徴とする通信装置。
【請求項２】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する通信装置において、
復号アルゴリズムにおける所定の処理により得られる中間値を保持する保持手段と、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値の最小値と、前記行処理用ＬＬＲの符号の乗算結果と、を乗算することにより、つぎの列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理手段と、
列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算し、さらに、行処理用ＬＬＲの絶対値の最小ｋ値を前記保持手段に保持する列処理、を実行する列処理手段と、
を備え、
前記行処理手段は、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、繰り返し（ｌ−１）回目の列処理で更新された行重みに対応した行処理用ＬＬＲの符号の乗算結果Ｓと、処理対象の列番号に対応する、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号と、を乗算し、当該乗算結果Ｓ´を前記保持手段に保持し、
前記列処理手段が行の前記最小ｋ値を更新しながら復号を行うことを特徴とする通信装置。
【請求項３】
前記列処理手段は、繰り返しｌ回目において、特定の列に対する列処理を行う場合、
処理対象の列番号に対応する受信ＬＬＲと、ｌ回目の行処理で更新された、処理対象の行番号以外の列重みに対応した列処理用ＬＬＲの合計値と、の加算結果を行処理用ＬＬＲとし、当該行処理用ＬＬＲの絶対値が、処理対象の行の最小ｋ値の少なくともいずれか一つよりも小さい場合に、当該最小ｋ値を更新し、
さらに、前記加算結果である行処理用ＬＬＲの符号と、前記保持手段に保持された符号の乗算結果Ｓ´と、を乗算し、当該乗算結果を繰り返し（ｌ＋１）回目の行処理で用いる符号の乗算結果Ｓとして更新しておくことを特徴とする請求項２に記載の通信装置。
【請求項４】
前記検査行列の列を所定数に分割し、分割後の行列単位に並列に前記行処理および列処理を実行し、さらに、前記最小ｋ値を保持する前記保持手段の領域を共有し、並列に実行される各列処理においてそれぞれ前記最小ｋ値を更新することを特徴とする請求項１または２に記載の通信装置。
【請求項５】
前記行処理手段は、さらに、予め規定された固定の正規化ファクターにより前記行処理用ＬＬＲの絶対値の最小値を補正し、補正後の値を用いて列処理用ＬＬＲを求めることを特徴とする請求項１または２に記載の通信装置。
【請求項６】
前記行処理手段は、前記行重みに対応した行処理用ＬＬＲの絶対値の最小値を、所定の補正式に基づいて最適値に補正し、補正後の値と前記行処理用ＬＬＲの符号の乗算結果とを乗算することにより、つぎの列処理で用いる列処理用ＬＬＲを求めることを特徴とする請求項１または２に記載の通信装置。
【請求項７】
前記行処理手段は、前記行重みに対応した行処理用ＬＬＲの絶対値の最小値に対して、ＴＬＵ（テーブルックアップ）を用いた所定の演算を行い、当該演算処理後の値と前記行処理用ＬＬＲの符号の乗算結果とを乗算することにより、つぎの列処理で用いる列処理用ＬＬＲを求めることを特徴とする請求項１または２に記載の通信装置。
【請求項８】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する通信装置において、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値に基づいて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理手段と、
列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算する列処理を実行する列処理手段と、
を備え、
前記行処理手段と前記列処理手段が所定回数ずつ交互に処理を行い、前記行処理用ＬＬＲおよび列処理用ＬＬＲの更新を巡回的に行う場合に、
前記行処理手段は、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、処理対象の列番号よりも小さい列番号については、繰り返しｌ回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、また、処理対象の列番号よりも大きい列番号については、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、さらに、それらの乗算結果同士を乗算することを特徴とする通信装置。
【請求項９】
前記行処理手段は、前記行重みに対応した行処理用ＬＬＲの絶対値の最小値と、前記行処理用ＬＬＲの符号の乗算結果と、を乗算することにより、つぎの列処理で用いる列処理用ＬＬＲを求めることを特徴とする請求項８に記載の通信装置。
【請求項１０】
前記行処理手段は、さらに、予め規定された固定の正規化ファクターにより前記行処理用ＬＬＲの絶対値の最小値を補正し、補正後の値を用いて列処理用ＬＬＲを求めることを特徴とする請求項９に記載の通信装置。
【請求項１１】
前記行処理手段は、前記行重みに対応した行処理用ＬＬＲの絶対値の最小値を、所定の補正式に基づいて最適値に補正し、補正後の値と前記行処理用ＬＬＲの符号の乗算結果とを乗算することにより、つぎの列処理で用いる列処理用ＬＬＲを求めることを特徴とする請求項８に記載の通信装置。
【請求項１２】
前記行処理手段は、前記行重みに対応した行処理用ＬＬＲの絶対値の最小値に対して、ＴＬＵ（テーブルックアップ）を用いた所定の演算を行い、当該演算処理後の値と前記行処理用ＬＬＲの符号の乗算結果とを乗算することにより、つぎの列処理で用いる列処理用ＬＬＲを求めることを特徴とする請求項８に記載の通信装置。
【請求項１３】
前記行処理手段は、繰り返し１回目の復号時、前記最小値として受信ＬＬＲの絶対値の最小値を用いることを特徴とする請求項１、２または８に記載の通信装置。
【請求項１４】
前記列処理手段は、前記列処理を実行する毎に事後値を算出し、当該事後値を硬判定し、パリティ検査結果がＯＫの場合か、または、繰り返し回数が規定された最大回数の場合に、そのときの硬判定値を復号結果として出力することを特徴とする請求項１、２または８に記載の通信装置。
【請求項１５】
前記行処理の開始列を任意とし、最終列まで処理が終了した段階で、再度最初の列から繰り返し復号を行うことを特徴とする請求項１、２または８に記載の通信装置。
【請求項１６】
前記行処理の開始列を任意とし、重複しない任意の列に対して処理を行い、すべての列が終了した段階で、再度同一の順番で繰り返し復号を行うことを特徴とする請求項１、２または８に記載の通信装置。
【請求項１７】
前記行処理の開始列を任意とし、重複しない任意の列に対して処理を行い、すべての列が終了した段階で、続いて異なる順番で重複しない任意の列に対してすべての列が終了するまで繰り返し復号を行うことを特徴とする請求項１、２または８に記載の通信装置。
【請求項１８】
検査行列における行重みの列番号を、列番号の小さい順に０から昇順に表記することを特徴とする請求項１、２または８に記載の通信装置。
【請求項１９】
前記行処理手段と前記列処理手段が所定回数ずつ交互に処理を行う度に、前記行処理用ＬＬＲおよび列処理用ＬＬＲの更新を行うことを特徴とする請求項８に記載の通信装置。
【請求項２０】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する復号方法であって、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値、および前記行処理用ＬＬＲの符号の乗算結果を用いて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理ステップと、
前記行処理により演算された列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算し、さらに、行重みに対応した行処理用ＬＬＲの絶対値の最小ｋ値をメモリの特定領域に保持する列処理、を実行する列処理ステップと、
を行の最小ｋ値を更新しながら実行し、復号を行う場合に、
前記行処理ステップでは、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、処理対象の列番号よりも小さい列番号については、繰り返しｌ回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、また、処理対象の列番号よりも大きい列番号については、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、さらに、それらの乗算結果同士を乗算することを特徴とする復号方法。
【請求項２１】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する復号方法であって、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値、および前記行処理用ＬＬＲの符号の乗算結果を用いて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理ステップと、
前記行処理により演算された列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算し、さらに、行重みに対応した行処理用ＬＬＲの絶対値の最小ｋ値をメモリの特定領域に保持する列処理、を実行する列処理ステップと、
を行の最小ｋ値を更新しながら実行し、復号を行う場合に、
前記行処理ステップでは、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、繰り返し（ｌ−１）回目の列処理で更新された行重みに対応した行処理用ＬＬＲの符号の乗算結果Ｓと、処理対象の列番号に対応する、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号と、を乗算し、当該乗算結果Ｓ´をメモリの特定領域に保持することを特徴とする復号方法。
【請求項２２】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する復号方法であって、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値、および前記行処理用ＬＬＲの符号の乗算結果を用いて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理ステップと、
前記行処理により演算された列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算する列処理を実行する列処理ステップと、
を所定回数ずつ交互に実行し、前記行処理用ＬＬＲおよび列処理用ＬＬＲの更新を巡回的に行う場合に、
前記行処理ステップでは、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、処理対象の列番号よりも小さい列番号については、繰り返しｌ回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、また、処理対象の列番号よりも大きい列番号については、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号を乗算し、さらに、それらの乗算結果同士を乗算することを特徴とする復号方法。
【請求項２３】
ＬＤＰＣ符号化された符号語を検査行列を用いて復号する復号方法であって、
検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値、および前記行処理用ＬＬＲの符号の乗算結果を用いて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理ステップと、
前記行処理により演算された列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算する列処理を実行する列処理ステップと、
を所定回数ずつ交互に実行し、前記行処理用ＬＬＲおよび列処理用ＬＬＲの更新を巡回的に行う場合に、
前記行処理ステップでは、繰り返しｌ回目において、特定の行における行重みに対応した行処理用ＬＬＲの符号を乗算する場合、繰り返し（ｌ−１）回目の列処理で更新された行重みに対応した行処理用ＬＬＲの符号の乗算結果Ｓと、処理対象の列番号に対応する、繰り返し（ｌ−１）回目の列処理で更新された行処理用ＬＬＲの符号と、を乗算し、当該乗算結果Ｓ´をメモリの特定領域に保持することを特徴とする復号方法。
【請求項２４】
前記列処理ステップでは、繰り返しｌ回目において、特定の列に対する列処理を行う場合、
処理対象の列番号に対応する受信ＬＬＲと、ｌ回目の行処理で更新された、処理対象の行番号以外の列重みに対応した列処理用ＬＬＲの合計値と、の加算結果を行処理用ＬＬＲとし、当該行処理用ＬＬＲの絶対値が、処理対象の行の最小ｋ値の少なくともいずれか一つよりも小さい場合に、当該最小ｋ値を更新し、
さらに、前記加算結果である行処理用ＬＬＲの符号と、前記メモリの特定領域に保持された符号の乗算結果Ｓ´と、を乗算し、当該乗算結果を繰り返し（ｌ＋１）回目の行処理で用いる符号の乗算結果Ｓとして更新しておくことを特徴とする請求項２１または２３に記載の復号方法。
【請求項２５】
繰り返し１回目の復号時、前記最小値として受信ＬＬＲの絶対値の最小値を用いることを特徴とする請求項２０〜２３のいずれか１つに記載の復号方法。
【請求項２６】
前記列処理ステップを実行する毎に事後値を算出し、当該事後値を硬判定し、パリティ検査結果がＯＫの場合か、または、繰り返し回数が規定された最大回数の場合に、そのときの硬判定値を復号結果として出力することを特徴とする請求項２０〜２３のいずれか１つに記載の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル通信における誤り訂正技術に関するものであり、特に、ＬＤＰＣ（Low-Density  Parity  Check）符号化された信号を復号する受信側の通信装置およびその復号方法に関するものである。
【背景技術】
【０００２】
ＬＤＰＣ符号を復号する基本的なアルゴリズムとして、「Sum-Productアルゴリズム」と「Min-Sumアルゴリズム」があり、これらは、受信信号の確率的な信頼度情報である対数尤度比（ＬＬＲ：Log  Likelihood  Ratio）を算出しながら繰り返し演算を行うことにより復号処理を行う（非特許文献１参照）。上記「Sum-Productアルゴリズム」は、復号性能は高いが、数学関数を用いた演算が要求されるため、テーブルを保持する必要が生じるなど実装するには計算コストが高い。また、少なくとも“０”，“１”の２元の検査行列に含まれる“１”の数の分だけ中間値を記憶するメモリが必要である。一方、「Min-Sumアルゴリズム」は、数学関数を必要とせず、計算コストは小さくなるが、復号性能が劣化する。【０００３】
ここで、上記「Sum-Productアルゴリズム」について説明する。まず、送信機側では、Ｍ行×Ｎ列のパリティ検査行列Ｈを用いて送信データをＬＤＰＣ符号化し、符号語ｃ＝（ｃ1，ｃ2，…，ｃN）、ｃn＝０，１を生成する（ｎ＝１，２，…，Ｎ）。そして、この符号語ｃに対して、たとえば、ＢＰＳＫ（Binary  Phase  Shift  Keying）変調等の変調処理を実行し、変調信号ｘ＝（ｘ1，ｘ2，…，ｘN）を送信する。【０００４】
一方、受信機側では、加法性白色ガウス通信路（Additive  White  Gaussian  Noise  Channel：ＡＷＧＮ通信路）経由で、下記（１）式のように表記される信号ｙ＝（ｙ1，ｙ2，…，ｙN）を受信する。
ｙn＝ｘn＋ｅn                            …（１）
なお、ｅnは、平均０，分散値σ2＝Ｎ0／２となるガウス雑音系列である。【０００５】
そして、受信機側では、上記通信路を介して受け取った変調信号に対して、上記ＢＰＳＫ変調に応じた所定のディジタル復調を行い、さらに、復調結果から得られる対数尤度比（ＬＬＲ）に対して「Sum-Productアルゴリズム」による繰り返し復号を実施し、最終的に硬判定結果を出力する。【０００６】
つづいて、上記受信機において実施される、従来の復号方法「Sum-Productアルゴリズム」を以下に示す。【０００７】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定し、さらに、初期時における、ビットノードからチェックノードへのＬＬＲ：βmn(l=1)として、下記（２）式に示すように受信ＬＬＲ：λnを入力する。
βmn(1)＝λn
ｎ＝１，２，…，Ｎ
ｍ＝１，２，…，Ｍ                …（２）【０００８】
（行処理ステップ）
つぎに、行処理として、各ｍ，ｎについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（３）式により更新する。【０００９】
【数１】
0004627317.tif 000002
…（３）【００１０】
ただし、Ｎ（ｍ）はｍ行目の“１”を持つ列番号の集合を表し、ｎ´はｎ以外のＮ（ｍ）を表し、βmn'(l-1)はｎ列目以外の（ｌ−１）回のビットノードからチェックノードへのＬＬＲを表す。【００１１】
（列処理ステップ）
つぎに、列処理として、各ｍ，ｎについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（４）式により更新する。【００１２】
【数２】
0004627317.tif 000003
…（４）【００１３】
また、各ｎについて、硬判定のための、ビットｎの繰り返しｌ回目の事後値βn(l)を下記（５）式により更新する。【００１４】
【数３】
0004627317.tif 000004
…（５）【００１５】
ただし、Ｍ（ｎ）はｎ列目の“１”を持つ行番号の集合を表し、ｍ´はｍ以外のＭ（ｎ）を表し、αm'n(l)はｍ行目以外のｌ回目のチェックノードからビットノードへのＬＬＲを表す。【００１６】
（停止規範）
その後、たとえば、ビットｎの繰り返しｌ回目の事後値βn(l)が「βn(l)＞０」の場合には、復号結果「ｘn´＝１」とし（ｘ´は元の送信信号ｘに対応）、一方、「βn(l)≦０」の場合には、復号結果「ｘn´＝０」とし、復号結果ｘ´＝（ｘ1´，ｘ2´，…，ｘN´）を得る。【００１７】
そして、パリティ検査の結果が「Ｈｘ´＝０」または繰り返し回数が「ｌ＝ｌmax」の場合（いずれか１つの条件を満たしている場合）に、そのときの復号結果ｘ´を出力する。なお、上記２つの条件のどちらも満たしていない場合は、「ｌ＝ｌ＋１」とし、上記行処理に戻り、以降、順に演算を実行する。【００１８】
【非特許文献１】低密度パリティ検査符号とその復号法  ＬＤＰＣ（Low  Density  Parity  Check）符号／sum-product復号法、和田山正著、トリケップス
【発明の開示】
【発明が解決しようとする課題】
【００１９】
しかしながら、上記「Sum-Productアルゴリズム」は、復号性能が高いことは知られているが、一方で、数学関数を用いた繰り返し演算（tanh-1の演算）が要求されるため、ハードウェア，ソフトウェアのどちらで実現しても受信機側の計算負荷が高くなる、という問題があった。また、計算負荷を低減させるために所定のテーブルを保持する方法（テーブルルックアップ）もあるが、当該テーブルを保持するために必要なメモリ量が増大する、という問題があった。【００２０】
また、上記「Sum-Productアルゴリズム」においては、少なくとも“０”，“１”の２元の検査行列に含まれる“１（重み）”の数の分だけ中間値（行毎の対数尤度比，繰り返し毎の更新値等）を記憶するためのメモリが必要となる。すなわち、メモリの消費量が非常に多くなる、という問題があった。また、「Sum-Productアルゴリズム」においては、量子化ビット数が多い，繰り返し回数が多い、等の問題もある。【００２１】
本発明は、上記に鑑みてなされたものであって、ＬＤＰＣ符号化された符号語の復号処理において、計算量およびメモリ量を削減可能な通信装置および復号方法を得ることを目的とする。また、量子化サイズの縮小、さらには、繰り返し回数の削減、を実現する通信装置および復号方法を得ることを目的とする。
【課題を解決するための手段】
【００２２】
上述した課題を解決し、目的を達成するために、本発明にかかる通信装置は、ＬＤＰＣ符号化された符号語を検査行列を用いて復号する通信装置において、復号アルゴリズムにおける所定の処理により得られる中間値を保持する保持手段と、検査行列における行重みに対応した対数尤度比（ビットノードからチェックノードへ送る対数尤度比：行処理用ＬＬＲと呼ぶ）の絶対値に基づいて、列処理で用いる対数尤度比（チェックノードからビットノードへ送る対数尤度比：列処理用ＬＬＲと呼ぶ）を演算する行処理を実行する行処理手段と、列重みに対応した列処理用ＬＬＲを用いて、行処理で用いる行処理用ＬＬＲを演算し、さらに、行処理用ＬＬＲの絶対値の最小ｋ値を前記保持手段に保持する列処理、を実行する列処理手段と、を備え、前記列処理手段が行の前記最小ｋ値を更新しながら復号を行うことを特徴とする。
【発明の効果】
【００２３】
この発明によれば、ＬＤＰＣ復号において、行処理のためのＬＬＲの絶対値を、巡回構造により行単位に最小ｋ値に縮小することとしたので、それらを保持するためのメモリ量を大幅に削減することができる、という効果を奏する。また、本発明によれば、従来の「Min-Sumアルゴリズム」よりも確率伝搬を効率的に行うことができるので、復号の繰り返し回数を大幅に削減することができ、ひいては、復号処理における計算量を大幅に低減させることができる、という効果を奏する。
【図面の簡単な説明】
【００２４】
【図１】図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む通信システムの構成例を示す図である。
【図２】図２は、ＬＤＰＣ復号器において「Min-Sumアルゴリズム」の行処理ステップを実行する場合の行処理部の構成例を示す図である。
【図３】図３は、ＬＤＰＣ復号器において「Min-Sumアルゴリズム」の列処理ステップを実行する場合の列処理部の構成例を示す図である。
【図４】図４は、「Min-Sumアルゴリズム」における処理の流れを示すフローチャートである。
【図５−１】図５−１は、実施の形態１のＬＤＰＣ復号器の構成例を示す図である。
【図５−２】図５−２は、実施の形態１のＬＤＰＣ復号器の構成例を示す図である。
【図６】図６は、「巡回近似minアルゴリズム」において行処理を実行する行処理部の構成例を示す図である。
【図７−１】図７−１は、「巡回近似minアルゴリズム」において列処理を実行する列処理部の構成例を示す図である。
【図７−２】図７−２は、「巡回近似minアルゴリズム」において列処理を実行する列処理部の構成例を示す図である。
【図８】図８は、ｎ＝１５の列処理において、Ｍｉｎ２ＬＬＲにｎ＝１５の情報が保持されている場合の処理を示す図である。
【図９】図９は、「巡回近似minアルゴリズム」における処理の流れを示すフローチャートである。
【図１０】図１０は、列番号表記を示す図である。
【図１１】図１１は、「巡回近似minアルゴリズム」と「Min-Sumアルゴリズム」の比較シミュレーションの結果を示す図である。
【図１２】図１２は、「巡回近似minアルゴリズム」と「Min-Sumアルゴリズム」の比較シミュレーションの結果を示す図である。
【図１３】図１３は、実施の形態２のＬＤＰＣ復号器の構成例を示す図である。
【図１４】図１４は、繰り返し回数についての性能比較を示す図である。
【図１５】図１５は、実施の形態３の行処理を実行する行処理部の構成例を示す図である。
【図１６】図１６は、実施の形態４の行処理を実行する行処理部の構成例を示す図である。
【図１７】図１７は、「δ  minアルゴリズム」に対して「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用した復号アルゴリズムと、「Sum-Productアルゴリズム」と、の比較結果を示す図である。
【図１８】図１８は、実施の形態５の行処理を実行する行処理部の構成例を示す図である。
【図１９】図１９は、実施の形態６の「シリアル巡回近似minアルゴリズム」において列処理を実行する列処理部の構成例を示す図である。
【符号の説明】
【００２５】
１  ＬＤＰＣ符号化器
２  変調器
３  通信路
４  復調器
５  ＬＤＰＣ復号器
１１  受信ＬＬＲ算出部
１２  復号コア部
２１，２１ａ  途中結果保持部
２２，２２−１，２２−２，２２−Ｇ  行処理部
２３，２３−１，２３−２，２３−Ｇ  列処理部
２４  復号結果判定部
２５，２５ａ  制御部
３１，３１ａ，３１ｂ，３１ｃ  最小値選択部
３２  符号演算部
３３  ＬＬＲ算出部
４１  α加算部
４２  λ加算部
４３  最小ｋ値比較部
４４  符号演算部
４５  スイッチ
【発明を実施するための最良の形態】
【００２６】
以下に、本発明にかかる通信装置および復号方法の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。また、本発明にかかる復号方法は、一例として、携帯電話等の無線通信において、端末および基地局における復号処理として適用可能である。また、衛星通信，ＨＤＤ，光通信，無線ＬＡＮ，量子暗号，その他の復号処理として適用可能である。【００２７】
実施の形態１．
まず、本発明にかかる通信装置および復号方法を実現するためのＬＤＰＣ復号器の、通信システム内における位置付けについて説明する。図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む通信システムの構成例を示す図である。図１において、送信側の通信装置（送信装置と呼ぶ）は、ＬＤＰＣ符号化器１と変調器２を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とＬＤＰＣ復号器５を含む構成とする。【００２８】
ここで、ＬＤＰＣ符号を採用する通信システムにおける符号化処理，復号処理の流れを簡単に説明する。送信装置内のＬＤＰＣ符号化器１では、たとえば、既知の方法によりＫ行×Ｎ列の生成行列Ｇ（Ｋ：情報長，Ｎ：符号語長）を生成する。そして、情報長Ｋのメッセージ（ｍ1，ｍ2，…，ｍK）を受け取り、このメッセージおよび上記生成行列Ｇを用いて、下記（６）式のように、符号語Ｃを生成する。ただし、ＬＤＰＣ用のパリティ検査行列をＨ（Ｍ行×Ｎ列）とした場合、生成行列Ｇは、ＧＨT＝０（Ｔは転置行列），Ｈ（ｃ1，ｃ2，…，ｃN）T＝０を満たす行列となる。
Ｃ＝（ｍ1，ｍ2，…，ｍK）Ｇ
＝（ｃ1，ｃ2，…，ｃN）                    …（６）【００２９】
そして、変調器２では、ＬＤＰＣ符号化器１で生成した符号語Ｃに対して、ＢＰＳＫ，多値ＰＳＫ，多値ＱＡＭ等の所定の変調方式によりディジタル変調を行い、その変調信号ｘ＝（ｘ1，ｘ2，…，ｘN）を、通信路３を介して受信装置に送信する。【００３０】
一方、受信装置では、復調器４が、通信路３を介して受け取った変調信号ｙ＝（ｙ1，ｙ2，…，ｙN）に対して、上記ＢＰＳＫ，多値ＰＳＫ，多値ＱＡＭ等の変調方式に応じたディジタル復調を行い、さらに、ＬＤＰＣ復号器５が、復調結果から得られる対数尤度比（ＬＬＲ）を用いて、後述する本実施の形態の復号アルゴリズムによる繰り返し復号を実施し、その復号結果として硬判定値（元のメッセージｍ1，ｍ2，…，ｍKに対応）を出力する。【００３１】
つづいて、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる従来の復号アルゴリズムである「Min-Sumアルゴリズム」について説明する。【００３２】
「Min-Sumアルゴリズム」では、まず、前述した「Sum-Productアルゴリズム」と同様の初期化ステップを実行し、つぎに、当該「Min-Sumアルゴリズム」の行処理ステップを実行し、その後、前述した「Sum-Productアルゴリズム」と同様の列処理ステップおよび停止規範を実行することにより、確率情報の算出処理および更新処理を行う。以下では、「Sum-Productアルゴリズム」と処理の異なる、「Min-Sumアルゴリズム」の行処理ステップについて説明する。【００３３】
図２は、ＬＤＰＣ復号器において「Min-Sumアルゴリズム」の行処理ステップを実行する場合の行処理部の構成例を示す図である。この行処理部は、パリティ検査行列Ｈの行重み分のＬＬＲ：βmn'(l-1)を保持するメモリ部１１１，各ＬＬＲを大小比較してＬＬＲの最小値を出力する比較部１１２を備えた最小値選択部１０１と、上記行重み分のＬＬＲの符号を保持するメモリ部１１３，各ＬＬＲの符号（＋または−）を乗算する乗算器１１４を備えた符号演算部１０２と、最小値選択部１０１から得られる最小値と符号演算部１０２から得られる符号の乗算結果（＋または−）とを乗算することによってＬＬＲ：αmn(l)を算出するＬＬＲ算出部１０３と、から構成されている。【００３４】
上記行処理部において、最小値選択部１０１の比較部１１２は、２入力（ａ，ｂ）の比較器を複数備え、上記メモリ部１１１および前段の比較器（１段目の比較器は上記メモリ部１１１のみ）から比較対象のＬＬＲを受け取った各比較器が、「｜ａ｜＜｜ｂ｜」の場合は｜ａ｜を出力し、その以外の場合は｜ｂ｜を出力することによって、ＬＬＲの絶対値の最小値を出力する。そして、ＬＬＲ算出部１０３が、上記最小値と上記符号の乗算結果とを乗算し、その乗算結果であるＬＬＲ：αmn(l)を列処理部へ受け渡す。【００３５】
なお、図３は、ＬＤＰＣ復号器において「Min-Sumアルゴリズム」の列処理ステップを実行する場合の列処理部の構成例を示しており、この列処理部では、パリティ検査行列Ｈの列重みのＬＬＲ：αm'n(l)を保持し、各ＬＬＲを加算することにより、繰り返しｌ回目の事後値βn(l)を出力している。【００３６】
（行処理ステップ）
また、上記「Min-Sumアルゴリズム」の行処理を一般化すると、下記（７）式のように表すことができる。ここでは、行処理として、各ｍ，ｎについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（７）式により更新している。【００３７】
【数４】
0004627317.tif 000005
…（７）【００３８】
ただし、ｍｉｎ｜βmn'(l-1)｜は、パリティ検査行列Ｈのｍ行目においてｎ列目を除くＬＬＲ：βmn'(l-1)の絶対値の最小値を表し、ｓｇｎ（βmn'(l-1)）は、ｎ列目を除くＬＬＲ：βmn'(l-1)の符号を表す。【００３９】
上記のように、行処理ステップを実行後、「Min-Sumアルゴリズム」では、さらに、前述した「Sum-Productアルゴリズム」と同様の列処理および停止規範に基づく処理を実行し、最終的な符号結果を得る。【００４０】
つぎに、上記「Min-Sumアルゴリズム」における処理の流れを、図４のフローチャートを用いて簡単に説明する。【００４１】
上記「Min-Sumアルゴリズム」においては、まず、受信情報から受信ＬＬＲを算出し（ステップＳ１，Ｓ２）、その結果を初期値としてメモリ部１１１に設定し、さらに、繰り返し回数をｌ＝１と初期化する（ステップＳ３）。つぎに、繰り返し処理（ステップＳ４：繰り返し復号１回目〜繰り返し復号最終回）として、まず、繰り返しｌ回目の復号演算における行処理を行い（行処理）、つぎに、繰り返しｌ回目の復号演算における列処理を行い（列処理）、その後、繰り返しｌ回目で算出した事後値を硬判定し、その判定値を復号結果として決定し、さらに、パリティ検査を行う（停止規範）。そして、上記停止規範において、パリティ検査結果がＯＫとなるか、または繰り返し回数がｌ＝ｌmaxとなった場合に、最終的にそのときの復号結果を出力する（ステップＳ５）。【００４２】
このように、上記「Min-Sumアルゴリズム」においては、前述した「Sum-Productアルゴリズム」の行処理、すなわち、（３）式を近似することにより、「Sum-Productアルゴリズム」よりも計算量およびメモリ量を削減している。しかしながら、上記「Min-Sumアルゴリズム」においては、中間値を保持するために、パリティ検査行列Ｈに含まれる“１（重み）”の数に対応する膨大なメモリ量が必要であり、よりメモリ量を削減するためには、さらなる改良が必要である。【００４３】
以下において説明する本実施の形態の復号アルゴリズムは、上記さらなるメモリ量の削減および計算量の低減を実現するものであり、たとえば、「Sum-Productアルゴリズム」の近似復号法である「Min-Sumアルゴリズム」を改良したアルゴリズムである。【００４４】
つづいて、本発明にかかる受信装置を構成するＬＤＰＣ復号器５の構成、およびＬＤＰＣ復号器５による復号方法（復号アルゴリズム）を、図面にしたがって詳細に説明する。【００４５】
図５−１は、本実施の形態のＬＤＰＣ復号器５の構成を示す図であり、このＬＤＰＣ復号器５は、受信情報から受信ＬＬＲを算出する受信ＬＬＲ算出部１１と本実施の形態の復号処理を行う復号コア部１２で構成されている。また、復号コア部１２は、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１と、本実施の形態の行処理を実行する行処理部２２と、本実施の形態の列処理を実行する列処理部２３と、本実施の形態の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５と、を備えている。【００４６】
なお、本実施の形態の復号アルゴリズムは、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新していく方法であり、正確な最小値ではなく近似的な最小値を用いて復号する方法であることから、以降、「巡回近似minアルゴリズム」と呼ぶこととする。また、上記最小ｋ値とは、「最小値から昇順にｋ番目まで」を表す。【００４７】
ここで、上記受信装置において実施される「巡回近似minアルゴリズム」を以下に示す。【００４８】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（８）式に示すようにＢmn(i)を求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（８）式に示すようにＳmを求める。【００４９】
【数５】
0004627317.tif 000006
…（８）【００５０】
ただし、Ｂmn(i)は、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、ｎ（ｉ）は、Ｂmn(i)の中で最小ｉ番目のＬＬＲの列番号であり、Ｓmは、ｍ行目のＬＬＲ：βmnの符号（＋または−）の積である。【００５１】
（行処理ステップ）
つぎに、行処理として、１≦ｎ≦Ｎおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（９）式により更新する。なお、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【００５２】
【数６】
0004627317.tif 000007
…（９）【００５３】
具体的には、現在の列番号がｎの場合、「ｎ´＜ｎ」を満たす列番号については、ｌ回目の列処理で更新されたＬＬＲ：βmn'(l)の符号の積をとり、また、「ｎ´＞ｎ」を満たす列番号については、（ｌ−１）回目の列処理で更新されたＬＬＲ：βmn'(l-1)の符号の積をとり、そして、それらの結果とｍ行目の最小ｋ値中の最小のＬＬＲ：ｍｉｎ［βmn'］との乗算結果を、列番号ｎの更新後のＬＬＲ：αmn(l)としている。なお、本実施の形態においては、さらに、上記βmn'(l)の符号の積と上記βmn'(l-1)の符号の積と乗算する項を、（ｌ−１）回目に更新されたＳmと（ｌ−１）回目に更新されたβmn'の符号とを乗算する項に、置き換えることとした。これにより、さらに、計算量およびメモリ量を削減できる。なお、上記（９）式のＮk（ｍ）は、ｍ行目のｎ（ｉ）の集合であり、Ｎk（ｍ）＝｛ｎ（１），ｎ（２），…，ｎ（ｋ）｝と表す。【００５４】
（列処理ステップ）
つぎに、列処理として、各ｍ，ｎについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（１０）式により更新する。【００５５】
【数７】
0004627317.tif 000008
…（１０）【００５６】
具体的には、列番号ｎにおいて、受信ＬＬＲ：λnと、ｌ回目の行処理で更新されたｍ行目以外のＬＬＲ：αm'n(l)の合計値と、の加算結果を、更新後のＬＬＲ：βmn(l)としている。また、上記Ｓm´とｌ回目の列処理で更新されたβmn(l)の符号（＋または−）とを乗算することにより、行処理にて使用するＳmを更新している。なお、上記（１０）式における下の２つの式は、Ｂmn(1)の並べ替え処理（最小ｋ値）を規定したものである。【００５７】
また、各ｎについて、硬判定のための、ビットｎの繰り返しｌ回目の事後値βn(l)を下記（１１）式により更新する。【００５８】
【数８】
0004627317.tif 000009
…（１１）【００５９】
（停止規範）
その後、たとえば、ビットｎの繰り返しｌ回目の事後値βn(l)が「βn(l)＞０」の場合には、復号結果を「ｘn´＝１」とし（ｘ´は元の送信信号ｘに対応）、一方、「βn(l)≦０」の場合には、復号結果を「ｘn´＝０」とし、復号結果ｘ´＝（ｘ1´，ｘ2´，…，ｘN´）を得る。【００６０】
そして、パリティ検査の結果が「Ｈｘ´＝０」または繰り返し回数が「ｌ＝ｌmax」の場合（いずれか１つの条件を満たしている場合）に、そのときの復号結果ｘ´を出力する。なお、上記２つの条件のどちらも満たしていない場合は、「ｌ＝ｌ＋１」とし、上記行処理に戻り、以降、順に演算を実行する。【００６１】
つぎに、上記「巡回近似minアルゴリズム」を実行するＬＤＰＣ復号器５の特徴的な動作を、構成図を用いて具体的に説明する。【００６２】
図６は、上記「巡回近似minアルゴリズム」において行処理を実行する行処理部２２の構成例を示す図であり、この行処理部２２は、最小値選択部３１と符号演算部３２とＬＬＲ算出部３３から構成されている。なお、図示のＭｉｎ１ＬＬＲ（ｍ行目における最小のＬＬＲ）はＢmn(1)であり、Ｍｉｎ２ＬＬＲ（ｍ行目における最小２番目のＬＬＲ）はＢmn(2)であり、それぞれ途中結果保持部２１に保持された値である。また、図示のＳmおよび「（１−１）回目のｍ行ｎ列目のＬＬＲ：βmnの符号」についても、それぞれ途中結果保持部２１に保持された値である。【００６３】
最小値選択部３１では、行処理の対象となっている列番号ｎとＭｉｎ１ＬＬＲ（Ｂmn(1)）の列番号ｎ（１）とが一致している場合は、Ｍｉｎ２ＬＬＲ（Ｂmn(2)）を選択し、それ以外の場合は、Ｍｉｎ１ＬＬＲ（Ｂmn(1)）を選択し、出力する。また、符号演算部３２は、「（ｌ−１）回目の列処理で更新されたＳm」および「（１−１）回目のｍ行ｎ列目のＬＬＲ：βmnの符号」を乗算し、その結果としてＳm´を出力する。このとき、Ｓm´は、途中結果保持部２１に保持される。また、ＬＬＲ算出部３３は、最小値選択部３１から得られる最小のＬＬＲと符号演算部３２から得られる符号の乗算結果Ｓm´（＋または−）とを乗算することによって、ＬＬＲ：αmn(l)を算出する。この構成により、「Min-Sumアルゴリズム」においては行重み分だけ必要であったメモリを、ｋ値分に縮小できる。【００６４】
図７−１は、上記「巡回近似minアルゴリズム」において列処理を実行する列処理部２３の構成例を示す図であり、この列処理部２３は、α加算部４１とλ加算部４２と最小ｋ値比較部４３と符号演算部４４から構成されている。なお、本実施の形態では、ｋ＝３の場合を一例として記載している。また、図示の列重み分のＬＬＲ，αmn，λn，Ｓm´，Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲ（ｍ行目における最小３番目のＬＬＲ）は、それぞれ途中結果保持部２１に保持された値である。【００６５】
上記列処理部２３では、α加算部４１が、ｌ回目の行処理で更新されたｍ行目以外のすべてのＬＬＲ：αm'n(l)を加算し、さらに、λ加算部４２が、α加算部４１による加算結果に受信ＬＬＲ：λnを加算し、βmn(l)を出力する。そして、最小ｋ値比較部４３（ｋ＝３）は、｜βmn(l)｜を受け取る。ここで、図７−１に図示はしていないが、たとえば、列処理の対象となるｎ列目のｎと、Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲにそれぞれ保持されているＢmn(1)，Ｂmn(2)，Ｂmn(3)に対応する列番号を示すｎ（１），ｎ（２），ｎ（３）のいずれかが一致した場合、ｎ＝ｎ（ｉ）となるＢmn(i)を間引きし、図８に示すような操作を行う。具体的には、Ｍｉｎ２ＬＬＲに保持されている情報を削除し、Ｍｉｎ３ＬＬＲに保持されている情報をＭｉｎ２ＬＬＲに移動し、さらに、Ｍｉｎ３ＬＬＲには、たとえば（１６ビットの場合）、最大値“ＦＦＦＦ”を格納する。これにより、処理対象の列を除いた比較処理が可能となるとともに、少なくともＭｉｎ３ＬＬＲが列処理において必ず更新されることになる。この処理後、図７−１に示すとおり、｜βmn(l)｜と、Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲと、をそれぞれ比較し、「｜βmn(l)｜＜Ｍｉｎ３ＬＬＲ」であれば、最小３値のＬＬＲを更新する。一方、λ加算部４２が出力するβmn(l)の符号を「ｌ回目のｍ行ｎ列目のＬＬＲ：βmn(l)の符号」として途中結果保持部２１に保持し、さらに、符号演算部４４が、ｌ回目の行処理で更新されたＳm´と上記βmn(l)の符号とを乗算し、その結果を用いて途中結果保持部２１に保持されたＳmを更新する。なお、｜βmn(l)｜とＭｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲとの比較の際に、｜βmn(l)｜をＢmn(i)の中心の値であるＭｉｎ２ＬＬＲと最初に比較し、それ以降、図示のように、ツリー状に比較するようにしたが、たとえば、最小値であるＭｉｎ１ＬＬＲから比較する場合に比べ、実行時間が｛（ｋ＋１）／２｝／ｋ（ｋが奇数の場合）となる効果がある。また、ｋが偶数の場合には、Ｂmn(i)の中心の値は２個になるが、最初に比較を開始する対象は、そのいずれであってもよい。ｋが偶数の場合は、最小値であるＭｉｎ１ＬＬＲから比較する場合に比べ、実行時間が｛ｋ／２＋１｝／ｋ（ｋが偶数の場合）となる効果がある。【００６６】
また、上記と同じ処理を、図７−２に示す構成でも実現することができ、その際、α加算部４１では、列重み分のすべてのＬＬＲの加算のみを行い、その後、λ加算部４２でλnの加算を行い、その結果を復号結果判定部２４に出力するとともに、ｍ行目のＬＬＲであるαmnの減算を行う。このような手順でも上記処理の手順と同一の結果を得ることができる。この際のＬＤＰＣ符号器の構成は図５−２のようになる。【００６７】
つぎに、本実施の形態の「巡回近似minアルゴリズム」における処理の流れを、図９のフローチャートを用いて説明する。【００６８】
上記「巡回近似minアルゴリズム」においては、まず、受信ＬＬＲ計算部１１が、受信情報から受信ＬＬＲを算出し（ステップＳ１１，Ｓ１２）、その結果を初期値として途中結果保持部２１に設定し（ステップＳ１３）、さらに、制御部２５が、繰り返し回数をｌ＝１と初期化する（ステップＳ１３）。また、列処理部２３のうち、λ加算部４２，最小ｋ値比較部４３，符号演算部４４を用いて、ｎ＝１からｎ＝Ｎまで巡回的に、上記（８）式の演算を行う（ステップＳ１３）。【００６９】
つぎに、復号コア部１２は、制御部２５の制御により、ｌ回目（１回目〜最終回）の繰り返し復号演算を行う（ステップＳ１４）。具体的には、繰り返し復号の１回目として、行処理部２２が、１列目に“１”を持つ行に対して行処理（受信ＬＬＲを使用）を行い、その結果を列処理部２３へ受け渡す。その後、列処理部２３が、１列目の列処理を行い、その結果であるＢmn(i)とＳmを、途中結果保持部２１に保持する（更新する）。以降、２列目，３列目，…Ｎ列目の順に、上記と同様の処理を行い、それぞれＢmn(i)とＳmを、途中結果保持部２１に保持する（繰り返し復号１回目に相当）。その後、繰り返し復号の２回目以降は、１つ前の処理で更新されたＬＬＲおよびＳmを用いて行処理を行い、それ以外は、上記１回目と同様に復号処理を行う。【００７０】
また、上記ｌ回目の繰り返し復号を実施後、復号結果判定部２４が、繰り返しｌ回目で算出した事後値を硬判定し、その判定値を復号結果ｘ´として決定し、さらにパリティ検査を行う（停止規範）。そして、この停止規範において、パリティ検査結果がＯＫ（「Ｈｘ´＝０」）となるか、または繰り返し回数がｌ＝ｌmaxとなった場合に、最終的にそのときの復号結果ｘ´を出力する（ステップＳ１５）。なお、上記２つの条件を満たしていない場合は、制御部２５がｌ＝ｌ＋１とし、復号コア部１２においては、（ｌ＋１）回目の繰り返し復号を実行する。【００７１】
つぎに、列番号の表記方法によるメモリサイズの削減について説明する。図１０は、本実施の形態の列番号表記を示す図である。「巡回近似minアルゴリズム」では、たとえば、列番号をｎ＝０から昇順に表記することとした。また、従来、列番号ｎを、パリティ検査行列の列番号そのもの（絶対列番号）で表現していたが、本実施の形態においては、パリティ検査行列におけるｍ行目の“１”の最小の列番号をｎ＝０とし、ｍ行目の次の“１”の列番号をｎ=１とし、以降、“１”毎にｎ＝２，３，…とする相対的列番号で表現することとした。すなわち、従来は、パリティ検査行列の“１”の絶対列番号が、たとえば、“３２７６８”である場合、列番号を表現するために必要なビット数が１５ビットとなるが、一方、本実施の形態においては、たとえば、行重みが８個であれば０〜７を表現できる３ビットまで、行重みが１６個であれば０〜１５を表現できる４ビットまで、メモリサイズを縮小することできる。【００７２】
以上にように、本実施の形態では、ＬＤＰＣ復号において、行処理のためのＬＬＲの絶対値｜βmn｜を、巡回構造により行単位に最小ｋ値に縮小することとしたので、それらを保持するためのメモリ量を大幅に削減することができる。たとえば、行重みが２０でｋ＝３の場合は、従来と比較してメモリ量を３／２０に削減することができる。また、列番号を、絶対列番号（1,3,10,15…）から相対的列番号（0,1,2,3…）に変更することにより、さらにメモリ量を削減することができる。【００７３】
また、本実施の形態の「巡回近似minアルゴリズム」においては、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を巡回的に１ビットずつ行うこととした。これにより、従来の「Min-Sumアルゴリズム」よりも確率伝搬を効率的に行うことができる。【００７４】
たとえば、図１１、図１２に、「巡回近似minアルゴリズム」と「Min-Sumアルゴリズム」の比較シミュレーションの結果を示す。ＬＤＰＣ符号は、イレギュラーＥＧ符号で最大行重みは８である。図１１においては、復号繰り返し回数を１００回に固定し、「巡回近似minアルゴリズム」の保存する最小値の個数を３，４，５個と変えて、「Min-Sumアルゴリズム」と性能比較を行った場合を表している。図中、CyclicXminは最小Ｘ値を保持した「巡回近似minアルゴリズム」を表し、Min-Sumは「Min-Sumアルゴリズム」を表す。図１１からも明らかなように、本実施の形態の「巡回近似minアルゴリズム」によって、メモリを削減しつつ復号性能が劣化しないことが確認できる。【００７５】
また、図１２には、「巡回近似minアルゴリズム」と「Min-Sumアルゴリズム」において、復号が成功するまでに要した平均繰り返し回数を比較した結果を示している。図中、CyclicXminは最小Ｘ値を保存した「巡回近似minアルゴリズム」を表し、Min-Sumは「Min-Sumアルゴリズム」を表す。この結果からも明らかなように、「巡回近似minアルゴリズム」では確率伝搬が効率的に行われ、復号繰り返し回数が大幅に削減されている。すなわち、本実施の形態の「巡回近似minアルゴリズム」により、復号処理における計算量を大幅に低減させることができる。【００７６】
なお、本実施の形態において、行処理の演算対象のＬＬＲは、１値であるが、ｋの個数は、２値以上であれば何値でもよい。また、本実施の形態においては、行処理と列処理とを交互に１回ずつ実行し、これに応じて、行処理と列処理による確率情報（ＬＬＲ）の更新を１ビットずつ巡回的に行う場合について説明したが、これに限定されるものではなく、行処理を複数回実行した後、列処理を複数回実行するようにしてもよい。すなわち、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を巡回的に複数ビットずつ行うようにしてもよい。【００７７】
実施の形態２．
つづいて、実施の形態２の受信装置および復号方法について説明する。本実施の形態のＬＤＰＣ復号は、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を、１ビットずつまたは予め定めた複数ビットずつ行う場合に適用可能であり、たとえば、演算処理を並列化することにより、繰り返し回数の低減を図る。なお、本実施の形態においては、途中結果保持部のＢmn(i)およびＳmを、並列化の数にかかわらず１セットとし、並列化されたすべての処理部が同一のＢmnCおよびＳmを更新していく、いわゆる「Overlapped」されたＢmnCおよびＳmを用いた「巡回近似minアルゴリズム」を実行する。以降、本実施の形態の復号アルゴリズムを、「Overlapped巡回近似minアルゴリズム」と呼ぶ。【００７８】
ここで、本実施の形態の受信装置において実施される「Overlapped巡回近似minアルゴリズム」を以下に示す。【００７９】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（１２）式に示すようにＢmn(i)Cを求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（１２）式に示すようにＳmを求める。【００８０】
【数９】
0004627317.tif 000010
…（１２）【００８１】
ただし、Ｂmn(i)Cは、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、並列処理の際に共通に用いられる。また、ｎ（ｉ）は、Ｂmn(i)Cの中で最小ｉ番目のＬＬＲの列番号である。【００８２】
（行処理ステップ）
つぎに、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（１３）式により更新する。なお、Ｇは並列数であり、ＮGは並列化された各復号回路が処理する列数である。また、Ｇ・Ｎg＝Ｎである。また、本実施の形態においては、各行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【００８３】
【数１０】
0004627317.tif 000011
…（１３）【００８４】
具体的には、たとえば、列数：ＮG毎にＧ個に分割された各列郡にそれぞれ割り当てられたＧ個の行処理部が、並列に行処理を実行する。なお、Ｇ個の行処理部が並列に処理を行い、すべての処理部が同一のＢmnCを用いる以外は、前述した「巡回近似minアルゴリズム」と同様に動作する。【００８５】
（列処理ステップ）
つぎに、列処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（１４）式により更新する。すなわち、本実施の形態においては、上記のように並列に行処理が行われた後の各列について、並列に、下記（１４）式に示す列処理を実行する。【００８６】
【数１１】
0004627317.tif 000012
…（１４）【００８７】
また、各ｎについて、硬判定のための、ビットｎの繰り返しｌ回目の事後値βn(l)を下記（１５）式により更新する。【００８８】
【数１２】
0004627317.tif 000013
…（１５）【００８９】
なお、停止規範については、前述した「巡回近似minアルゴリズム」と同様である。【００９０】
つづいて、上記「Overlapped巡回近似minアルゴリズム」を実現する実施の形態２のＬＤＰＣ復号器５の構成および動作について説明する。【００９１】
図１３は、本実施の形態のＬＤＰＣ復号器５の構成例を示す図であり、受信情報から受信ＬＬＲを算出する受信ＬＬＲ算出部１１と本実施の形態の復号処理を行う復号コア部１２ａで構成されている。また、復号コア部１２ａは、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１ａと、本実施の形態の行処理（並列処理）を実行する行処理部２２−１〜２２−Ｇと、本実施の形態の列処理（並列処理）を実行する列処理部２３−１〜２３−Ｇと、本実施の形態の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５ａと、を備えている。【００９２】
図１３において、本実施の形態のＬＤＰＣ復号器５は、各行処理部および各列処理部が並列に処理を行う際、上記（１２）式，（１３）式，（１４）式に従って、途中結果保持部２１ａのＢmnCおよびＳmを共通に使用し、それぞれが更新する。この並列処理により、ＢmnCおよびＳmは、並列数に応じて急速に更新され、それに伴って、復号の繰り返し回数を大幅に削減することができる。【００９３】
なお、本実施の形態では、並列処理において、同一クロックで同一行の演算が発生し、同一バッファを参照するような問題が生じる場合には、たとえば、各処理部にメモリアクセスの優先順位を設定する、メモリバンクを区切る、シフトレジスタを用いてメモリアクセスのタイミングを調整する、等の対策を行う。【００９４】
以上のように、本実施の形態の「Overlapped巡回近似minアルゴリズム」は、前述した「巡回近似minアルゴリズム」を応用し、行処理および列処理をそれぞれ並列に実行することとした。また、並列に実行される各列処理において更新される最小ｋ値を保持する途中結果保持部を共有し、並列に実行される各列処理においてそれぞれ最小ｋ値を更新することとした。これにより、「Min-Sumアルゴリズム」および前述した実施の形態１と比較して、復号の繰り返し回数を大幅に削減することができる。【００９５】
図１４は、繰り返し回数についての性能比較を示す図である。詳細には、並列数を２とした場合の「Overlapped巡回近似minアルゴリズム」、「巡回近似minアルゴリズム」、「Min-Sumアルゴリズム」について、復号の繰り返し回数を固定した状態で、それぞれの復号性能を比較した結果である。図１４において、復号の繰り返し回数が少なく制限された場合、「巡回近似minアルゴリズム」は、従来法である「Min-Sumアルゴリズム」と比較して、復号性能が高いことが確認でき、さらに、「Overlapped巡回近似minアルゴリズム」は、「巡回近似minアルゴリズム」の半分の復号繰り返し回数で同程度の復号性能を持つことが確認できる。なお、図１４においては、並列数を２としたため、復号の繰り返し回数が半分程度であったが、「Overlapped巡回近似minアルゴリズム」を用いた場合、繰り返し回数は、「巡回近似minアルゴリズム」の「１／並列数」となる。【００９６】
実施の形態３．
つづいて、実施の形態３の受信装置および復号方法について説明する。本実施の形態においては、「Min-Sumアルゴリズム」を応用した既知の復号アルゴリズムである「Normalized  BP-basedアルゴリズム」に対して、実施の形態１の「巡回近似minアルゴリズム」または実施の形態２の「Overlapped巡回近似minアルゴリズム」における、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新する処理、および近似的な最小値を用いた復号処理、を適用する。【００９７】
ここで、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる既知の「Normalized  BP-basedアルゴリズム」を以下に示す。なお、ここでは、「Min-Sumアルゴリズム」と処理が異なる、行処理について説明する。【００９８】
（行処理ステップ）
たとえば、「Normalized  BP-basedアルゴリズム」の行処理を一般化すると、下記（１６）式のように表すことができる。ここでは、行処理として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（１６）式により更新している。また、式中のＡは正規化ファクターと呼ばれる定数であり、「Normalized  BP-basedアルゴリズム」では、「Min-Sumアルゴリズム」により得られる繰り返しｌ回目のＬＬＲを、正規化ファクターＡにより補正している。【００９９】
【数１３】
0004627317.tif 000014
…（１６）【０１００】
つづいて、上記「Normalized  BP-basedアルゴリズム」に対して「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」と処理の異なる、行処理について説明する。【０１０１】
（巡回近似minアルゴリズムを適用した場合の行処理ステップ）
たとえば、「巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（１７）式のように表すことができる。ここでは、行処理として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（１７）式により更新している。すなわち、下記（１７）式においては、「巡回近似minアルゴリズム」により得られる繰り返しｌ回目のＬＬＲを、正規化ファクターＡにより補正している。なお、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０１０２】
【数１４】
0004627317.tif 000015
…（１７）【０１０３】
（Overlapped巡回近似minアルゴリズムを適用した場合の行処理ステップ）
また、「Overlapped巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（１８）式のように表すことができる。ここでは、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（１８）式により更新している。すなわち、下記（１８）式においては、「Overlapped巡回近似minアルゴリズム」により得られる繰り返しｌ回目のＬＬＲを、正規化ファクターＡにより補正している。【０１０４】
【数１５】
0004627317.tif 000016
…（１８）【０１０５】
なお、本実施の形態の復号アルゴリズムでは、上記のように行処理ステップを実行後、さらに、前述した「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」と同様の列処理および停止規範に基づく処理を実行し、最終的な符号結果を得ている。【０１０６】
つづいて、上記本実施の形態の復号アルゴリズムを実行するＬＤＰＣ復号器５の行処理部の特徴的な動作を、図面を用いて説明する。なお、ＬＤＰＣ復号器５の全体構成については、前述した図５または図１３と同様である。【０１０７】
図１５は、本実施の形態における行処理を実行する行処理部２２，２２−１〜２２−Ｇの構成例を示す図であり、この行処理部は、最小値選択部３１ａを備えている。なお、前述した図６と同様の構成については、同一の符号を付してその説明を省略する。本実施の形態の最小値選択部３１ａでは、たとえば、途中結果保持部２１（または２１ａ）から読み出したＬＬＲの最小値（Ｍｉｎ１ＬＬＲまたはＭｉｎ２ＬＬＲ）を、正規化ファクターＡを用いて補正している。具体的には、ＬＬＲの最小値をＡで除算することにより正規化を行っている。【０１０８】
以上のように、本実施の形態においては、「Min-Sumアルゴリズム」よりも性能が良好とされている「Normalized  BP-basedアルゴリズム」に「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用することとした。これにより、前述した実施の形態１，２と同様の効果が得られるとともに、さらに、ほぼ「Min-Sumアルゴリズム」と同等の回路量にもかかわらず「Sum-Productアルゴリズム」に近い性能を実現できる。【０１０９】
なお、本実施の形態においては、「Normalized  BP-basedアルゴリズム」に「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用することとしたが、これに限らず、既知の「Offset  BP-basedアルゴリズム」、またはそれ以外のアルゴリズムに巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用することも可能であり、この場合についても、上記と同様の効果を得ることができる。【０１１０】
実施の形態４．
つづいて、実施の形態４の受信装置および復号方法について説明する。本実施の形態においては、「Normalized  BP-basedアルゴリズム」や「Offset  BP-basedアルゴリズム」よりもＬＬＲ：βmnの補正性能が優れている既知の復号アルゴリズムである「δ  minアルゴリズム」に対して、実施の形態１の「巡回近似minアルゴリズム」または実施の形態２の「Overlapped巡回近似minアルゴリズム」における、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新する処理、および近似的な最小値を用いた復号処理、を適用する。【０１１１】
ここで、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる既知の「δ  minアルゴリズム」を以下に示す。なお、ここでは、「Min-Sumアルゴリズム」と処理が異なる、行処理について説明する。【０１１２】
（行処理ステップ）
たとえば、「δ  minアルゴリズム」の行処理を一般化すると、下記（１９）式のように表すことができる。ここでは、行処理として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（１９）式により更新している。「δ  minアルゴリズム」の行処理では、繰り返しｌ−１回目に更新されたＬＬＲの絶対値：｜βmn'(i-1)｜から、Θの演算によりαmn(l)を算出する。【０１１３】
【数１６】
0004627317.tif 000017
…（１９）【０１１４】
つづいて、上記「δ  minアルゴリズム」に対して「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」と処理の異なる、行処理について説明する。また、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０１１５】
（巡回近似minアルゴリズムを適用した場合の行処理ステップ）
たとえば、「巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（２０）式のように表すことができる。ここでは、行処理として、１≦ｎ≦Ｎおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２０）式により更新している。また、この復号アルゴリズムの行処理では、繰り返しｌ−１回目に更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'から、Θの演算によりαmn(l)を算出する。【０１１６】
【数１７】
0004627317.tif 000018
…（２０）【０１１７】
（Overlapped巡回近似minアルゴリズムを適用した場合の行処理ステップ）
また、「Overlapped巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（２１）式のように表すことができる。ここでは、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２１）式により更新している。また、この復号アルゴリズムの行処理では、繰り返しｌ−１回目に並列処理にて更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'Cから、Θの演算によりαmn(l)を算出する。【０１１８】
【数１８】
0004627317.tif 000019
…（２１）【０１１９】
なお、本実施の形態の復号アルゴリズムでは、上記のように行処理ステップを実行後、さらに、前述した「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」と同様の列処理および停止規範に基づく処理を実行し、最終的な符号結果を得ている。【０１２０】
つづいて、上記本実施の形態の復号アルゴリズムを実行するＬＤＰＣ復号器５の行処理部の特徴的な動作を、図面を用いて説明する。なお、ＬＤＰＣ復号器５の全体構成については、前述した図５または図１３と同様である。【０１２１】
図１６は、本実施の形態における行処理を実行する行処理部２２，２２−１〜２２−Ｇの構成例を示す図であり、この行処理部は、最小値選択部３１ｂを備えている。なお、前述した図６と同様の構成については、同一の符号を付してその説明を省略する。また、ここでは、一例として、図５のＬＤＰＣ復号器５の場合について説明するが、図１３のＬＤＰＣ復号器５についても同様に適用可能である。【０１２２】
本実施の形態の最小値選択部３１ｂでは、たとえば、途中結果保持部２１からＭｉｎ１ＬＬＲ（Ｂmn(1)），Ｍｉｎ２ＬＬＲ（Ｂmn(2)），ＭｉｎｋＬＬＲ（Ｂmn(k)）とそれぞれの列番号を読み出し、演算部がΘの演算を行う。すなわち、本実施の形態の最小値選択部３１ｂでは、処理対象となっているｎ列目と、途中結果保持部２１に保持されたＢmn(k)の列番号ｎ（ｋ）と、が一致しないＢmn(k)に対して、演算部が、「δ  minアルゴリズム」における以下の演算を行う。【０１２３】
たとえば、演算部は、符号を除く更新値｜αmn(l)｜（＝Θ［Ｂmn'］）を下記（２２）式のように求める。【０１２４】
【数１９】
0004627317.tif 000020
…（２２）【０１２５】
また、演算対象のＬＬＲをｋ値から最小３値に限定することで演算量を削減することができ、演算部は、符号を除く更新値｜αmn(l)｜（＝Θ［Ｂmn'］）を下記（２３）式のように求める。【０１２６】
【数２０】
0004627317.tif 000021
…（２３）【０１２７】
なお、上記では、一例として、演算対象のＬＬＲをｋ値から最小３値に限定した場合について説明したが、最小４，５…値と限定した場合においても同様に適用可能である。【０１２８】
以上のように、本実施の形態においては、「Min-Sumアルゴリズム」よりも性能が良好とされている「δ  minアルゴリズム」に「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用することとした。これにより、前述した実施の形態１，２と同様の効果が得られるとともに、さらに、ほぼ「Min-Sumアルゴリズム」と同等の回路量にもかかわらず「Sum-Productアルゴリズム」に近い性能を実現できる。また、本実施の形態においては、行処理用のＬＬＲの絶対値の最小値を、既知の「δ  minアルゴリズム」にて規定された所定の補正式に基づいて最適値に補正する場合について記載したが、補正式はこれに限定されるものではなく、「δ  minアルゴリズム」以外のアルゴリズムにて規定された補正式を用いることとしてもよい。この場合も上記と同様の効果を得ることができる。【０１２９】
図１７は、「δ  minアルゴリズム」に対して「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用した復号アルゴリズムと、「Sum-Productアルゴリズム」と、の比較結果を示す図である。たとえば、overlap5delta10は「Overlapped巡回近似minアルゴリズム」を適用した本実施の形態の復号アルゴリズム（並列数が２，最小５値，ｌ＝１０）、Cyclic5delta50は「巡回近似minアルゴリズム」を適用した本実施の形態の復号アルゴリズム（並列なし，最小５値，ｌ＝５０）、Sum-Product100は「Sum-Productアルゴリズム」（ｌ＝１００）を示し、ほぼ重なっている。この結果から、「δ  minアルゴリズム」に対して「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用することにより、「Sum-Productアルゴリズム」と同程度の性能を持つだけでなく、復号の繰り返し回数についても大幅に削減することができる。【０１３０】
実施の形態５．
つづいて、実施の形態５の受信装置および復号方法について説明する。本実施の形態においては、「Sum-Productアルゴリズム」に対して、実施の形態１の「巡回近似minアルゴリズム」または実施の形態２の「Overlapped巡回近似minアルゴリズム」における、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新する処理、および近似的な最小値を用いた復号処理、を適用する。【０１３１】
ここで、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる既知の「Sum-Productアルゴリズム」を以下に示す。なお、本実施の形態では、数学関数をテーブル化して演算を行う方法、すなわち、ＴＬＵ（テーブルルックアップ）を利用した一般的な「Sum-Productアルゴリズム」について記載する。また、ここでは、従来技術において説明した「Sum-Productアルゴリズム」と処理が異なる、行処理について記載する。【０１３２】
（行処理ステップ（１））
たとえば、ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理を一般化すると、下記（２４）式のように表すことができる。ここでは、行処理として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２４）式により更新している。ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理では、繰り返しｌ−１回目に更新されたＬＬＲの絶対値：｜βmn'(l-1)｜に対して、ＴＬＵを用いた演算を行っている。【０１３３】
【数２１】
0004627317.tif 000022
…（２４）【０１３４】
（行処理ステップ（２））
また、上記とは異なる方法で、ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理を実現することもできる。たとえば、上記とは異なる、ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理を一般化すると、下記（２５）式のように表すことができる。ここでは、行処理として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２５）式により更新している。【０１３５】
【数２２】
0004627317.tif 000023
…（２５）【０１３６】
なお、ＴＬＵ１（ｘ）は、下記（２６）に基づいて予めテーブルを用意しておく。
ＴＬＵ１（ｘ）＝ｌｎ（１＋ｅｘｐ（−ｘ））                …（２６）【０１３７】
また、上記ＴＬＵを利用した「Sum-Productアルゴリズム」において、上記（２４）式に示した行処理は、テーブルは大きくなるが演算回数が少ないという特徴があり、一方、上記（２５）に示した行処理は、テーブルは小さくなるが演算回数が多いという特徴がある。【０１３８】
つづいて、上記ＴＬＵを利用した「Sum-Productアルゴリズム」に対して「巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「巡回近似minアルゴリズム」と処理の異なる、行処理について説明する。また、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０１３９】
（巡回近似minアルゴリズムを適用した場合の行処理ステップ（１））
たとえば、上記行処理ステップ（１）に対して「巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（２７）式のように表すことができる。ここでは、行処理として、１≦ｎ≦Ｎおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２７）式により更新している。また、この復号アルゴリズムの行処理では、繰り返しｌ−１回目に更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'に対して、ＴＬＵを用いた演算を行っている。【０１４０】
【数２３】
0004627317.tif 000024
…（２７）【０１４１】
（巡回近似minアルゴリズムを適用した場合の行処理ステップ（２））
また、上記行処理ステップ（２）に対して「巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（２８）式のように表すことができる。ここでは、行処理として、１≦ｎ≦Ｎおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２８）式により更新している。【０１４２】
【数２４】
0004627317.tif 000025
…（２８）【０１４３】
つづいて、上記ＴＬＵを利用した「Sum-Productアルゴリズム」に対して「Overlapped巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「Overlapped巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「Overlapped巡回近似minアルゴリズム」と処理の異なる、行処理について説明する。【０１４４】
（Overlapped巡回近似minアルゴリズムを適用した場合の行処理ステップ（１））
たとえば、上記行処理ステップ（１）に対して「Overlapped巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（２９）式のように表すことができる。ここでは、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２９）式により更新している。また、この復号アルゴリズムの行処理では、繰り返しｌ−１回目に並列処理にて更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'Cに対して、ＴＬＵを用いた演算を行っている。【０１４５】
【数２５】
0004627317.tif 000026
…（２９）【０１４６】
（Overlapped巡回近似minアルゴリズムを適用した場合の行処理ステップ（２））
また、上記行処理ステップ（２）に対して「Overlapped巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理を一般化すると、下記（３０）式のように表すことができる。ここでは、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（３０）式により更新している。【０１４７】
【数２６】
0004627317.tif 000027
…（３０）【０１４８】
つづいて、上記本実施の形態の復号アルゴリズムを実行するＬＤＰＣ復号器５の行処理部の特徴的な動作を、図面を用いて説明する。なお、ＬＤＰＣ復号器５の全体構成については、前述した図５または図１３と同様である。【０１４９】
図１８は、本実施の形態における行処理を実行する行処理部２２，２２−１〜２２−Ｇの構成例を示す図であり、この行処理部は、最小値選択部３１ｃを備えている。なお、前述した図６と同様の構成については、同一の符号を付してその説明を省略する。また、ここでは、一例として、図５のＬＤＰＣ復号器５の場合について説明するが、図１３のＬＤＰＣ復号器５についても同様に適用可能である。【０１５０】
本実施の形態の最小値選択部３１ｃでは、たとえば、途中結果保持部２１からＭｉｎ１ＬＬＲ（Ｂmn(1)），Ｍｉｎ２ＬＬＲ（Ｂmn(2)），ＭｉｎｋＬＬＲ（Ｂmn(k)）とそれぞれの列番号を読み出し、演算部がＴＬＵを用いた演算を行う。すなわち、本実施の形態の最小値選択部３１ｃでは、処理対象となっているｎ列目と、途中結果保持部２１に保持されたＢmn(k)の列番号ｎ（ｋ）と、が一致しないＢmn(k)に対して、演算部が、「Sum-Productアルゴリズム」における以下の演算を行う。【０１５１】
たとえば、演算部は、符号を除く更新値を下記（３１）式のように求める。【０１５２】
【数２７】
0004627317.tif 000028
…（３１）【０１５３】
また、演算対象のＬＬＲをｋ値から最小３値に限定することで演算量を削減することができ、演算部は、符号を除く更新値を下記（３２）式のように求める。【０１５４】
【数２８】
0004627317.tif 000029
…（３２）  【０１５５】
なお、上記では、一例として、演算対象のＬＬＲをｋ値から最小３値に限定した場合について説明したが、最小４，５…値と限定した場合においても同様に適用可能である。【０１５６】
以上のように、本実施の形態においては、ＴＬＵを利用した「Sum-Productアルゴリズム」に「巡回近似minアルゴリズム」または「Overlapped巡回近似minアルゴリズム」を適用することとした。これにより、他の実施の形態と比較して、計算量およびメモリ量は多くなるが、復号性能を向上させることができる。なお、本実施の形態においては、ＴＬＵを用いた「Sum-Productアルゴリズム」を例に説明したが、数学関数に対してＴＬＵを行う他の復号アルゴリズムにおいても同様である。また、本実施の形態においては、行処理用のＬＬＲの絶対値の最小値に対して、既知の「Sum-Productアルゴリズム」にて規定されたＴＬＵを用いた場合について記載したが、ＴＬＵはこれに限定されるものではなく、「Sum-Productアルゴリズム」にて規定されたＴＬＵ以外のＴＬＵを用いることとしてもよい。この場合も上記と同様の効果を得ることができる。【０１５７】
実施の形態６．
つづいて、実施の形態６の通信装置および復号方法について説明する。本実施の形態の復号処理は、完全なビット単位のシリアル復号に対応させることにより、さらに繰り返し回数の低減を図る。【０１５８】
前述の実施の形態と同様に、図５−１は、本実施の形態のＬＤＰＣ復号器５の構成を示す図であり、このＬＤＰＣ復号器５は、受信情報から受信ＬＬＲを算出する受信ＬＬＲ算出部１１と本実施の形態の復号処理を行う復号コア部１２で構成されている。また、復号コア部１２は、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１と、本実施の形態の行処理を実行する行処理部２２と、本実施の形態の列処理を実行する列処理部２３と、本実施の形態の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５と、を備えている。【０１５９】
なお、本実施の形態の復号アルゴリズムは、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新していく方法であり、正確な最小値ではなく近似的な最小値を用いて復号する方法であり、シリアル復号法であることから、以降、「シリアル巡回近似minアルゴリズム」と呼ぶこととする。また、上記最小ｋ値とは、「最小値から昇順にｋ番目まで」を表す。【０１６０】
ここで、上記受信装置において実施される「シリアル巡回近似minアルゴリズム」を以下に示す。【０１６１】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（３３）式に示すようにＢmn(i)を求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（３３）式に示すようにＳmを求める。【０１６２】
【数２９】
0004627317.tif 000030
…（３３）【０１６３】
ただし、Ｂmn(i)は、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、ｎ（ｉ）は、Ｂmn(i)の中で最小ｉ番目のＬＬＲの列番号であり、Ｓmは、ｍ行目のＬＬＲ：βmnの符号（＋または−）の積である。【０１６４】
（行処理ステップ１）
つぎに、行処理として、１≦ｎ≦Ｎおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（３４）式により更新する。なお、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０１６５】
【数３０】
0004627317.tif 000031
…（３４）【０１６６】
具体的には、現在の列番号がｎの場合、「ｎ´＜ｎ」を満たす列番号については、ｌ回目の列処理で更新されたＬＬＲ：βmn'(l)の符号の積をとり、また、「ｎ´＞ｎ」を満たす列番号については、（ｌ−１）回目の列処理で更新されたＬＬＲ：βmn'(l-1)の符号の積をとり、そして、それらの結果とｍ行目の最小ｋ値中の最小のＬＬＲ：ｍｉｎ［βmn'］との乗算結果を、列番号ｎの更新後のＬＬＲ：αmn(l)としている。なお、本実施の形態においては、さらに、上記βmn'(l)の符号の積と上記βmn'(l-1)の符号の積と乗算する項を、（ｌ−１）回目に更新されたＳmと（ｌ−１）回目に更新されたβmn'の符号とを乗算する項に、置き換えることとした。これにより、さらに、計算量およびメモリ量を削減できる。なお、上記（３４）式のＮk（ｍ）は、ｍ行目のｎ（ｉ）の集合であり、Ｎk（ｍ）＝｛ｎ（１），ｎ（２），…，ｎ（ｋ）｝と表す。【０１６７】
（列処理ステップ）
つぎに、列処理として、行処理ステップ１で行った列番号ｎの各ｍについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（３５）式により更新する。これ以降の列処理ステップおよび行処理ステップ２は例えば行番号ｍの最も小さい行番号から順に１行ずつ計算を実行する。但し実行する行番号の順番は重複せずにすべての「1」の立っている行が実行されれば、どの順番で実行してもよい。【０１６８】
【数３１】
0004627317.tif 000032
…（３５）【０１６９】
具体的には、列番号ｎにおいて、受信ＬＬＲ：λnと、ｌ回目の行処理で更新されたｍ行目以外のＬＬＲ：αm'n(l)の合計値と、の加算結果を、更新後のＬＬＲ：βmn(l)としている。この計算はβn(l)から、αmn(l)を引く事によっても得られる。また、上記Ｓm´とｌ回目の列処理で更新されたβmn(l)の符号（＋または−）とを乗算することにより、行処理にて使用するＳmを更新している。なお、上記（３５）式における下の２つの式は、Ｂmn(1)の並べ替え処理（最小ｋ値）を規定したものである。【０１７０】
（行処理ステップ２）
さらに、再度行処理として、列番号ｎの列処理で実行した行と同一のｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：α'mn(l)を、下記（３６）式により更新する。【０１７１】
【数３２】
0004627317.tif 000033
…（３６）【０１７２】
具体的には再度行処理として、α'mn(l)を更新し、さらにその結果を用いてβmn(l)にその更新したα'mn(l)を加算してβn(l)を更新する。この後、列番号ｎのすべてのｍに対して計算が完了するまで列処理ステップに戻り計算を繰り返す。また、列番号ｎの検査行列に“1”が立っている全ての行ｍに対して列処理ステップと行処理ステップ２が処理終了したら停止規範の処理に移る。【０１７３】
（停止規範）
その後、たとえば、ビットｎの繰り返しｌ回目の事後値βn(l)が「βn(l)＞０」の場合には、復号結果を「ｘn´＝１」とし（ｘ´は元の送信信号ｘに対応）、一方、「βn(l)≦０」の場合には、復号結果を「ｘn´＝０」とし、復号結果ｘ´＝（ｘ1´，ｘ2´，…，ｘN´）を得る。【０１７４】
そして、パリティ検査の結果が「Ｈｘ´＝０」または繰り返し回数が「ｌ＝ｌmax」の場合（いずれか１つの条件を満たしている場合）に、そのときの復号結果ｘ´を出力する。なお、上記２つの条件のどちらも満たしていない場合は、「ｌ＝ｌ＋１」とし、上記行処理ステップ１に戻り、以降、順に演算を実行する。【０１７５】
つぎに、上記「シリアル巡回近似minアルゴリズム」を実行するＬＤＰＣ復号器５の特徴的な動作を、構成図を用いて具体的に説明する。【０１７６】
前述の実施の形態と同様に、図６は、上記「シリアル巡回近似minアルゴリズム」において行処理を実行する行処理部２２の構成例を示す図であり、この行処理部２２は、最小値選択部３１と符号演算部３２とＬＬＲ算出部３３から構成されている。なお、図示のＭｉｎ１ＬＬＲ（ｍ行目における最小のＬＬＲ）はＢmn(1)であり、Ｍｉｎ２ＬＬＲ（ｍ行目における最小２番目のＬＬＲ）はＢmn(2)であり、それぞれ途中結果保持部２１に保持された値である。また、図示のＳmおよび「（１−１）回目のｍ行ｎ列目のＬＬＲ：βmnの符号」についても、それぞれ途中結果保持部２１に保持された値である。【０１７７】
最小値選択部３１では、行処理の対象となっている列番号ｎとＭｉｎ１ＬＬＲ（Ｂmn(1)）の列番号ｎ（１）とが一致している場合は、Ｍｉｎ２ＬＬＲ（Ｂmn(2)）を選択し、それ以外の場合は、Ｍｉｎ１ＬＬＲ（Ｂmn(1)）を選択し、出力する。また、符号演算部３２は、「（ｌ−１）回目の列処理で更新されたＳm」および「（１−１）回目のｍ行ｎ列目のＬＬＲ：βmnの符号」を乗算し、その結果としてＳm´を出力する。このとき、Ｓm´は、途中結果保持部２１に保持される。また、ＬＬＲ算出部３３は、最小値選択部３１から得られる最小のＬＬＲと符号演算部３２から得られる符号の乗算結果Ｓm´（＋または−）とを乗算することによって、ＬＬＲ：αmn(l)を算出する。この構成により、「Min-Sumアルゴリズム」においては行重み分だけ必要であったメモリを、ｋ値分に縮小できる。【０１７８】
図１９は、上記「シリアル巡回近似minアルゴリズム」において列処理を実行する列処理部２３の構成例を示す図であり、この列処理部２３は、α加算部４１とλ加算部４２と最小ｋ値比較部４３と符号演算部４４から構成されている。なお、本実施の形態では、ｋ＝３の場合を一例として記載している。また、図示の列重み分のＬＬＲ，α'mn，αmn，λn，Ｓm´，Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲ（ｍ行目における最小３番目のＬＬＲ）は、それぞれ途中結果保持部２１に保持された値である。【０１７９】
上記列処理部２３では、α加算部４１が、ｌ回目の行処理で更新されたｍ行目を含めたすべてのＬＬＲ：αmn(l)を加算し、さらに、λ加算部４２が、α加算部４１による加算結果に受信ＬＬＲ：λnを加算し、スイッチ４５が最初にその下のブロックに接続されるように制御され、そこからαmn(l)を引いてβmn(l)を出力する。そして、最小ｋ値比較部４３（ｋ＝３）は、｜βmn(l)｜を受け取る。【０１８０】
ここで、図１９に図示はしていないが、前述の実施の形態と同様に、たとえば、列処理の対象となるｎ列目のｎと、Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲにそれぞれ保持されているＢmn(1)，Ｂmn(2)，Ｂmn(3)に対応する列番号を示すｎ（１），ｎ（２），ｎ（３）のいずれかが一致した場合、ｎ＝ｎ（ｉ）となるＢmn(i)を間引きし、図８に示すような操作を行う。具体的には、Ｍｉｎ２ＬＬＲに保持されている情報を削除し、Ｍｉｎ３ＬＬＲに保持されている情報をＭｉｎ２ＬＬＲに移動し、さらに、Ｍｉｎ３ＬＬＲには、たとえば（１６ビットの場合）、最大値“ＦＦＦＦ”を格納する。これにより、処理対象の列を除いた比較処理が可能となるとともに、少なくともＭｉｎ３ＬＬＲが列処理において必ず更新されることになる。【０１８１】
この処理後、図１９に示すとおり、｜βmn(l)｜と、Ｍｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲと、をそれぞれ比較し、「｜βmn(l)｜＜Ｍｉｎ３ＬＬＲ」であれば、最小３値のＬＬＲを更新する。一方、λ加算部４２が出力するβmn(l)の符号を「ｌ回目のｍ行ｎ列目のＬＬＲ：βmn(l)の符号」として途中結果保持部２１に保持し、さらに、符号演算部４４が、ｌ回目の行処理で更新されたＳm´と上記βmn(l)の符号とを乗算し、その結果を用いて途中結果保持部２１に保持されたＳmを更新する。なお、｜βmn(l)｜とＭｉｎ１ＬＬＲ，Ｍｉｎ２ＬＬＲ，Ｍｉｎ３ＬＬＲとの比較の際に、｜βmn(l)｜をＢmn(i)の中心の値であるＭｉｎ２ＬＬＲと最初に比較し、それ以降、図示のように、ツリー状に比較するようにしたが、たとえば、最小値であるＭｉｎ１ＬＬＲから比較する場合に比べ、実行時間が｛（ｋ＋１）／２｝／ｋ（ｋが奇数の場合）となる効果がある。また、ｋが偶数の場合には、Ｂmn(i)の中心の値は２個になるが、最初に比較を開始する対象は、そのいずれであってもよい。ｋが偶数の場合は、最小値であるＭｉｎ１ＬＬＲから比較する場合に比べ、実行時間が｛ｋ／２＋１｝／ｋ（ｋが偶数の場合）となる効果がある。この比較結果のＭｉｎ１ＬＬＲとＭｉｎ２ＬＬＲから図６の回路によりα'mn(l))を求めβmn(l)と加算してβn(l)を算出し、スイッチ４５により次の列処理に移る。【０１８２】
つぎに、本実施の形態の「シリアル巡回近似minアルゴリズム」における処理の流れを、図９のフローチャートを用いて説明する。なお、図中、「繰り返し復号１回目」，「繰り返し復号２回目」，…，「繰り返し復号最終回」において、「行処理」，「列処理」，「行処理」，…，「列処理」と処理されるように記載されているが、本実施の形態においては、「行処理ステップ１」を処理した後、「列処理ステップ」，「行処理ステップ２」を列番号ｎのすべてのｍに対して計算が完了するまで繰り返す処理を、繰り返すものとする。即ち、「行処理ステップ１」，「列処理ステップ」，「行処理ステップ２」，「列処理ステップ」，「行処理ステップ２」「列処理ステップ」，…，「行処理ステップ２」，「行処理ステップ１」，「列処理ステップ」，「行処理ステップ２」，「列処理ステップ」，「行処理ステップ２」「列処理ステップ」，…，「行処理ステップ２」と処理されるものとする。【０１８３】
上記「シリアル巡回近似minアルゴリズム」においては、まず、受信ＬＬＲ計算部１１が、受信情報から受信ＬＬＲを算出し（ステップＳ１１，Ｓ１２）、その結果を初期値として途中結果保持部２１に設定し（ステップＳ１３）、さらに、制御部２５が、繰り返し回数をｌ＝１と初期化する（ステップＳ１３）。また、列処理部２３のうち、λ加算部４２，最小ｋ値比較部４３，符号演算部４４を用いて、ｎ＝１からｎ＝Ｎまで巡回的に、上記（３３）式の演算を行う（ステップＳ１３）。【０１８４】
つぎに、復号コア部１２は、制御部２５の制御により、ｌ回目（１回目〜最終回）の繰り返し復号演算を行う（ステップＳ１４）。具体的には、繰り返し復号の１回目として、行処理部２２が、１列目に“１”を持つ行に対して行処理ステップ１（受信ＬＬＲを使用）を行い、その結果を列処理部２３へ受け渡す。その後、列処理部２３が、１列目の列処理ステップを行い、その結果であるＢmn(i)とＳmを、途中結果保持部２１に保持する（更新する）。またその後、行処理部２２が、行処理ステップ２を行い、その結果を列処理部２３へ渡し、行処理部２２と列処理部２３によって、列処理ステップと行処理ステップ２を繰り返す。以降、２列目，３列目，…Ｎ列目の順に、上記と同様の処理を行い、それぞれＢmn(i)とＳmを、途中結果保持部２１に保持する（繰り返し復号１回目に相当）。その後、繰り返し復号の２回目以降は、１つ前の処理で更新されたＬＬＲおよびＳmを用いて行処理を行い、それ以外は、上記１回目と同様に復号処理を行う。【０１８５】
また、上記ｌ回目の繰り返し復号を実施後、復号結果判定部２４が、繰り返しｌ回目で算出した事後値を硬判定し、その判定値を復号結果ｘ´として決定し、さらにパリティ検査を行う（停止規範）。そして、この停止規範において、パリティ検査結果がＯＫ（「Ｈｘ´＝０」）となるか、または繰り返し回数がｌ＝ｌmaxとなった場合に、最終的にそのときの復号結果ｘ´を出力する（ステップＳ１５）。なお、上記２つの条件を満たしていない場合は、制御部２５がｌ＝ｌ＋１とし、復号コア部１２においては、（ｌ＋１）回目の繰り返し復号を実行する。【０１８６】
つぎに、前述の実施の形態と同様に列番号の表記方法によるメモリサイズの削減について説明する。図１０は、本実施の形態の列番号表記を示す図である。「シリアル巡回近似minアルゴリズム」では、たとえば、列番号をｎ＝０から昇順に表記することとした。また、従来、列番号ｎを、パリティ検査行列の列番号そのもの（絶対列番号）で表現していたが、本実施の形態においては、パリティ検査行列におけるｍ行目の“１”の最小の列番号をｎ＝０とし、ｍ行目の次の“１”の列番号をｎ=１とし、以降、“１”毎にｎ＝２，３，…とする相対的列番号で表現することとした。すなわち、従来は、パリティ検査行列の“１”の絶対列番号が、たとえば、“３２７６８”である場合、列番号を表現するために必要なビット数が１５ビットとなるが、一方、本実施の形態においては、たとえば、行重みが８個であれば０〜７を表現できる３ビットまで、行重みが１６個であれば０〜１５を表現できる４ビットまで、メモリサイズを縮小することできる。【０１８７】
以上にように、本実施の形態では、ＬＤＰＣ復号において、行処理のためのＬＬＲの絶対値｜βmn｜を、巡回構造により行単位に最小ｋ値に縮小することとしたので、それらを保持するためのメモリ量を大幅に削減することができる。たとえば、行重みが２０でｋ＝３の場合は、従来と比較してメモリ量を３／２０に削減することができる。また、列番号を、絶対列番号（1,3,10,15…）から相対的列番号（0,1,2,3…）に変更することにより、さらにメモリ量を削減することができる。【０１８８】
また、本実施の形態の「シリアル巡回近似minアルゴリズム」においては、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を巡回的に１ビットずつ行うこととした。これにより、従来の「Min-Sumアルゴリズム」よりも確率伝搬を効率的に行うことができる。【０１８９】
また、本実施の形態の「シリアル巡回近似minアルゴリズム」においては、行処理ステップ２として、α'mn(l)を更新し、さらにその結果を用いてβmn(l)にその更新したα'mn(l)を加算してβn(l)を更新するようにしたので、完全なビット単位のシリアル復号に対応させることができ、さらに繰り返し回数を削減することができる。【０１９０】
なお、本実施の形態において、行処理の演算対象のＬＬＲは、１値であるが、ｋの個数は、２値以上であれば何値でもよい。また、本実施の形態においては、行処理ステップ１を実行した後、列処理ステップと行処理ステップ２とを交互に実行し、これに応じて、行処理と列処理による確率情報（ＬＬＲ）の更新を１ビットずつ巡回的に行う場合について説明したが、これに限定されるものではなく、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を巡回的に複数ビットずつ行うようにしてもよい。【０１９１】
実施の形態７．
つづいて、実施の形態７の受信装置（通信装置）および復号方法について説明する。本実施の形態のＬＤＰＣ復号は、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を、１ビットずつまたは予め定めた複数ビットずつ行う場合に適用可能であり、たとえば、演算処理を並列化することにより、繰り返し回数の低減を図る。なお、本実施の形態においては、途中結果保持部のＢmn(i)およびＳmを、並列化の数にかかわらず１セットとし、並列化されたすべての処理部が同一のＢmnCおよびＳmを更新していく、いわゆる「Overlapped」されたＢmnCおよびＳmを用いた「シリアル巡回近似minアルゴリズム」を実行する。以降、本実施の形態の復号アルゴリズムを、「Overlappedシリアル巡回近似minアルゴリズム」と呼ぶ。【０１９２】
ここで、本実施の形態の受信装置において実施される「Overlappedシリアル巡回近似minアルゴリズム」を以下に示す。【０１９３】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（３７）式に示すようにＢmn(i)Cを求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（３７）式に示すようにＳmを求める。【０１９４】
【数３３】
0004627317.tif 000034
…（３７）【０１９５】
ただし、Ｂmn(i)Cは、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、並列処理の際に共通に用いられる。また、ｎ（ｉ）は、Ｂmn(i)Cの中で最小ｉ番目のＬＬＲの列番号である。【０１９６】
（行処理ステップ１）
つぎに、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（３８）式により更新する。なお、Ｇは並列数であり、ＮGは並列化された各復号回路が処理する列数である。また、Ｇ・Ｎg＝Ｎである。また、本実施の形態においては、各行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０１９７】
【数３４】
0004627317.tif 000035
…（３８）【０１９８】
具体的には、たとえば、列数：ＮG毎にＧ個に分割された各列郡にそれぞれ割り当てられたＧ個の行処理部が、並列に行処理を実行する。なお、Ｇ個の行処理部が並列に処理を行い、すべての処理部が同一のＢmnCを用いる以外は、前述した「シリアル巡回近似minアルゴリズム」と同様に動作する。【０１９９】
（列処理ステップ）
つぎに、列処理として、行処理ステップ１で行った列番号ｎの各ｍについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（３９）式により更新する。すなわち、本実施の形態においては、上記のように並列に行処理が行われた後の各列について、並列に、下記（３９）式に示す列処理を実行する。ただし、並列に列処理をする際、処理対象となる列番号ｎに対して、これ以降の列処理ステップおよび行処理ステップ２は例えば行番号ｍの最も小さい行番号から順に１行ずつ計算を実行する。但し実行する行番号の順番は重複せずにすべての「1」の立っている行が実行されれば、どの順番で実行してもよい。【０２００】
【数３５】
0004627317.tif 000036
…（３９）【０２０１】
（行処理ステップ２）
さらに、再度行処理として、列番号ｎの列処理で実行した行と同一のｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：α'mn(l)を、下記（４０）式により更新する。【０２０２】
【数３６】
0004627317.tif 000037
…（４０）【０２０３】
具体的には再度行処理として、α'mn(l)を更新し、さらにその結果を用いてβmn(l)にその更新したα'mn(l)を加算してβn(l)を更新する。この後、列番号ｎのすべてのｍに対して計算が完了するまで列処理ステップに戻り計算を繰り返す。また、列番号ｎの検査行列に“1”が立っている全ての行ｍに対して列処理ステップと行処理ステップ２が処理終了したら停止規範の処理に移る。【０２０４】
なお、停止規範については、前述した「シリアル巡回近似minアルゴリズム」と同様である。【０２０５】
つづいて、上記「Overlappedシリアル巡回近似minアルゴリズム」を実現する実施の形態７のＬＤＰＣ復号器５の構成および動作について説明する。【０２０６】
図１３は、前述の実施の形態と同様に、本実施の形態のＬＤＰＣ復号器５の構成例を示す図であり、受信情報から受信ＬＬＲを算出する受信ＬＬＲ算出部１１と本実施の形態の復号処理を行う復号コア部１２ａで構成されている。また、復号コア部１２ａは、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１ａと、本実施の形態の行処理（並列処理）を実行する行処理部２２−１〜２２−Ｇと、本実施の形態の列処理（並列処理）を実行する列処理部２３−１〜２３−Ｇと、本実施の形態の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５ａと、を備えている。【０２０７】
図１３において、本実施の形態のＬＤＰＣ復号器５は、各行処理部および各列処理部が並列に処理を行う際、上記（３７）式、（３８）式、（３９）式、（４０）式に従って、途中結果保持部２１ａのＢmnCおよびＳmを共通に使用し、それぞれが更新する。この並列処理により、ＢmnCおよびＳmは、並列数に応じて急速に更新され、それに伴って、復号の繰り返し回数を大幅に削減することができる。【０２０８】
なお、本実施の形態では、並列処理において、同一クロックで同一行の演算が発生し、同一バッファを参照するような問題が生じる場合には、たとえば、各処理部にメモリアクセスの優先順位を設定する、メモリバンクを区切る、シフトレジスタを用いてメモリアクセスのタイミングを調整する、等の対策を行う。【０２０９】
以上のように、本実施の形態の「Overlappedシリアル巡回近似minアルゴリズム」は、前述した「シリアル巡回近似minアルゴリズム」を応用し、行処理および列処理をそれぞれ並列に実行することとした。また、並列に実行される各列処理において更新される最小ｋ値を保持する途中結果保持部を共有し、並列に実行される各列処理においてそれぞれ最小ｋ値を更新することとした。これにより、「Min-Sumアルゴリズム」および前述した実施の形態６と比較して、復号の繰り返し回数を大幅に削減することができる。【０２１０】
また、本実施の形態の「Overlappedシリアル巡回近似minアルゴリズム」においては、行処理ステップ２として、α'mn(l)を更新し、さらにその結果を用いてβmn(l)にその更新したα'mn(l)を加算してβn(l)を更新するようにしたので、完全なビット単位のシリアル復号に対応させることができ、前述した実施の形態２と比較して、さらに繰り返し回数を削減することができる。【０２１１】
実施の形態８．
つづいて、実施の形態８の受信装置（通信装置）および復号方法について説明する。本実施の形態においては、「Min-Sumアルゴリズム」を応用した既知の復号アルゴリズムである「Normalized  BP-basedアルゴリズム」に対して、実施の形態６の「シリアル巡回近似minアルゴリズム」または実施の形態７の「Overlappedシリアル巡回近似minアルゴリズム」における、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新する処理、および近似的な最小値を用いた復号処理、を適用する。【０２１２】
ここで、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる既知の「Normalized  BP-basedアルゴリズム」を以下に示す。なお、ここでは、「Min-Sumアルゴリズム」と処理が異なる、行処理について説明する。【０２１３】
（行処理ステップ1）
たとえば、「Normalized  BP-basedアルゴリズム」の行処理ステップ１を一般化すると、下記（４１）式のように表すことができる。ここでは、行処理ステップ１として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４１）式により更新している。また、式中のＡは正規化ファクターと呼ばれる定数であり、「Normalized  BP-basedアルゴリズム」では、「Min-Sumアルゴリズム」により得られる繰り返しｌ回目のＬＬＲを、正規化ファクターＡにより補正している。【０２１４】
【数３７】
0004627317.tif 000038
…（４１）【０２１５】
つづいて、上記「Normalized  BP-basedアルゴリズム」に対して「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」と処理の異なる、行処理ステップ１について説明する。【０２１６】
（シリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ1）
たとえば、「シリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（４２）式のように表すことができる。ここでは、行処理ステップ１として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４２）式により更新している。すなわち、下記（４２）式においては、「シリアル巡回近似minアルゴリズム」により得られる繰り返しｌ回目のＬＬＲを、正規化ファクターＡにより補正している。なお、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０２１７】
【数３８】
0004627317.tif 000039
…（４２）【０２１８】
（Overlappedシリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ1）
また、「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（４３）式のように表すことができる。ここでは、行処理ステップ１として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４３）式により更新している。すなわち、下記（４３）式においては、「Overlappedシリアル巡回近似minアルゴリズム」により得られる繰り返しｌ回目のＬＬＲを、正規化ファクターＡにより補正している。【０２１９】
【数３９】
0004627317.tif 000040
…（４３）【０２２０】
なお、本実施の形態の復号アルゴリズムでは、上記のように行処理ステップ１を実行後、さらに、前述した「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」と同様の列処理および停止規範に基づく処理を実行し、最終的な符号結果を得ている。【０２２１】
つづいて、上記本実施の形態の復号アルゴリズムを実行するＬＤＰＣ復号器５の行処理部の特徴的な動作を、図面を用いて説明する。なお、ＬＤＰＣ復号器５の全体構成については、前述した図５または図１３と同様である。【０２２２】
図１５は、前述した実施の形態と同様に、本実施の形態における行処理を実行する行処理部２２，２２−１〜２２−Ｇの構成例を示す図であり、この行処理部は、最小値選択部３１ａを備えている。なお、前述した図６と同様の構成については、同一の符号を付してその説明を省略する。本実施の形態の最小値選択部３１ａでは、たとえば、途中結果保持部２１（または２１ａ）から読み出したＬＬＲの最小値（Ｍｉｎ１ＬＬＲまたはＭｉｎ２ＬＬＲ）を、正規化ファクターＡを用いて補正している。具体的には、ＬＬＲの最小値をＡで除算することにより正規化を行っている。【０２２３】
以上のように、本実施の形態においては、「Min-Sumアルゴリズム」よりも性能が良好とされている「Normalized  BP-basedアルゴリズム」に「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用することとした。これにより、前述した実施の形態６、７と同様の効果が得られるとともに、さらに、ほぼ「Min-Sumアルゴリズム」と同等の回路量にもかかわらず「Sum-Productアルゴリズム」に近い性能を実現できる。【０２２４】
なお、本実施の形態においては、「Normalized  BP-basedアルゴリズム」に「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用することとしたが、これに限らず、既知の「Offset  BP-basedアルゴリズム」、またはそれ以外のアルゴリズムに「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用することも可能であり、この場合についても、上記と同様の効果を得ることができる。【０２２５】
実施の形態９．
つづいて、実施の形態９の受信装置（通信装置）および復号方法について説明する。本実施の形態においては、「Normalized  BP-basedアルゴリズム」や「Offset  BP-basedアルゴリズム」よりもＬＬＲ：βmnの補正性能が優れている既知の復号アルゴリズムである「δ  minアルゴリズム」に対して、実施の形態６の「シリアル巡回近似minアルゴリズム」または実施の形態７の「Overlappedシリアル巡回近似minアルゴリズム」における、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新する処理、および近似的な最小値を用いた復号処理、を適用する。【０２２６】
ここで、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる既知の「δ  minアルゴリズム」を以下に示す。なお、ここでは、「Min-Sumアルゴリズム」と処理が異なる、行処理について説明する。【０２２７】
（行処理ステップ１）
たとえば、「δ  minアルゴリズム」の行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（４４）式のように表すことができる。ここでは、行処理ステップ１として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４４）式により更新している。「δ  minアルゴリズム」の行処理ステップ１では、繰り返しｌ−１回目に更新されたＬＬＲの絶対値：｜βmn'(i-1)｜から、Θの演算によりαmn(l)を算出する。【０２２８】
【数４０】
0004627317.tif 000041
…（４４）【０２２９】
つづいて、上記「δ  minアルゴリズム」に対して「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」と処理の異なる、行処理ステップ１について説明する。また、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０２３０】
（シリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ１）
たとえば、「シリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（４５）式のように表すことができる。ここでは、行処理ステップ１として、１≦ｎ≦Ｎおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４５）式により更新している。また、この復号アルゴリズムの行処理ステップ１では、繰り返しｌ−１回目に更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'から、Θの演算によりαmn(l)を算出する。【０２３１】
【数４１】
0004627317.tif 000042
…（４５）【０２３２】
（Overlappedシリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ１）
また、「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（４６）式のように表すことができる。ここでは、行処理ステップ１として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４６）式により更新している。また、この復号アルゴリズムの行処理ステップ１では、繰り返しｌ−１回目に並列処理にて更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'Cから、Θの演算によりαmn(l)を算出する。【０２３３】
【数４２】
0004627317.tif 000043
…（４６）【０２３４】
なお、本実施の形態の復号アルゴリズムでは、上記のように行処理ステップ１を実行後、さらに、前述した「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」と同様の列処理、行処理ステップ２および停止規範に基づく処理を実行し、最終的な符号結果を得ている。【０２３５】
つづいて、上記本実施の形態の復号アルゴリズムを実行するＬＤＰＣ復号器５の行処理部の特徴的な動作を、図面を用いて説明する。なお、ＬＤＰＣ復号器５の全体構成については、前述した図５または図１３と同様である。【０２３６】
図１６は、前述の実施の形態と同様に、本実施の形態における行処理を実行する行処理部２２，２２−１〜２２−Ｇの構成例を示す図であり、この行処理部は、最小値選択部３１ｂを備えている。なお、前述した図６と同様の構成については、同一の符号を付してその説明を省略する。また、ここでは、一例として、図５のＬＤＰＣ復号器５の場合について説明するが、図１３のＬＤＰＣ復号器５についても同様に適用可能である。【０２３７】
本実施の形態の最小値選択部３１ｂでは、たとえば、途中結果保持部２１からＭｉｎ１ＬＬＲ（Ｂmn(1)），Ｍｉｎ２ＬＬＲ（Ｂmn(2)），ＭｉｎｋＬＬＲ（Ｂmn(k)）とそれぞれの列番号を読み出し、演算部がΘの演算を行う。すなわち、本実施の形態の最小値選択部３１ｂでは、処理対象となっているｎ列目と、途中結果保持部２１に保持されたＢmn(k)の列番号ｎ（ｋ）と、が一致しないＢmn(k)に対して、演算部が、「δ  minアルゴリズム」における以下の演算を行う。【０２３８】
たとえば、演算部は、符号を除く更新値｜αmn(l)｜（＝Θ［Ｂmn'］）を下記（４７）式のように求める。【０２３９】
【数４３】
0004627317.tif 000044
…（４７）【０２４０】
また、演算対象のＬＬＲをｋ値から最小３値に限定することで演算量を削減することができ、演算部は、符号を除く更新値｜αmn(l)｜（＝Θ［Ｂmn'］）を下記（４８）式のように求める。【０２４１】
【数４４】
0004627317.tif 000045
…（４８）【０２４２】
なお、上記では、一例として、演算対象のＬＬＲをｋ値から最小３値に限定した場合について説明したが、最小４，５…値と限定した場合においても同様に適用可能である。【０２４３】
以上のように、本実施の形態においては、「Min-Sumアルゴリズム」よりも性能が良好とされている「δ  minアルゴリズム」に「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用することとした。これにより、前述した実施の形態６、７と同様の効果が得られるとともに、さらに、ほぼ「Min-Sumアルゴリズム」と同等の回路量にもかかわらず「Sum-Productアルゴリズム」に近い性能を実現できる。また、本実施の形態においては、行処理用のＬＬＲの絶対値の最小値を、既知の「δ  minアルゴリズム」にて規定された所定の補正式に基づいて最適値に補正する場合について記載したが、補正式はこれに限定されるものではなく、「δ  minアルゴリズム」以外のアルゴリズムにて規定された補正式を用いることとしてもよい。この場合も上記と同様の効果を得ることができる。【０２４４】
実施の形態１０．
つづいて、実施の形態１０の受信装置（通信装置）および復号方法について説明する。本実施の形態においては、「Sum-Productアルゴリズム」に対して、実施の形態６の「シリアル巡回近似minアルゴリズム」または実施の形態７の「Overlappedシリアル巡回近似minアルゴリズム」における、巡回的に最小ｋ値のＬＬＲの絶対値のみを更新する処理、および近似的な最小値を用いた復号処理、を適用する。【０２４５】
ここで、本実施の形態の復号アルゴリズムについて説明を行う前に、その前提となる既知の「Sum-Productアルゴリズム」を以下に示す。なお、本実施の形態では、数学関数をテーブル化して演算を行う方法、すなわち、ＴＬＵ（テーブルルックアップ）を利用した一般的な「Sum-Productアルゴリズム」について記載する。また、ここでは、従来技術において説明した「Sum-Productアルゴリズム」と処理が異なる、行処理について記載する。【０２４６】
（行処理ステップ１（１））
たとえば、ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（４９）式のように表すことができる。ここでは、行処理ステップ１として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（４９）式により更新している。ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理ステップ１では、繰り返しｌ−１回目に更新されたＬＬＲの絶対値：｜βmn'(l-1)｜に対して、ＴＬＵを用いた演算を行っている。【０２４７】
【数４５】
0004627317.tif 000046
…（４９）【０２４８】
（行処理ステップ１（２））
また、上記とは異なる方法で、ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理ステップ１を実現することもできる。たとえば、上記とは異なる、ＴＬＵを利用した「Sum-Productアルゴリズム」の行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（５０）式のように表すことができる。ここでは、行処理ステップ１として、各ｍ，ｎについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（５０）式により更新している。【０２４９】
【数４６】
0004627317.tif 000047
…（５０）【０２５０】
なお、ＴＬＵ１（ｘ）は、下記（５１）に基づいて予めテーブルを用意しておく。
ＴＬＵ１（ｘ）＝ｌｎ（１＋ｅｘｐ（−ｘ））                …（５１）【０２５１】
また、上記ＴＬＵを利用した「Sum-Productアルゴリズム」において、上記（４９）式に示した行処理ステップ１は、テーブルは大きくなるが演算回数が少ないという特徴があり、一方、上記（５０）式に示した行処理ステップ１は、テーブルは小さくなるが演算回数が多いという特徴がある。【０２５２】
つづいて、上記ＴＬＵを利用した「Sum-Productアルゴリズム」に対して「シリアル巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「シリアル巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「シリアル巡回近似minアルゴリズム」と処理の異なる、行処理ステップ１について説明する。また、本実施の形態においては、行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０２５３】
（シリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ１（１））
たとえば、上記行処理ステップ１（１）に対して「シリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（５２）式のように表すことができる。ここでは、行処理ステップ１として、１≦ｎ≦Ｎおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（５２）式により更新している。また、この復号アルゴリズムの行処理ステップ１では、繰り返しｌ−１回目に更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'に対して、ＴＬＵを用いた演算を行っている。【０２５４】
【数４７】
0004627317.tif 000048
…（５２）【０２５５】
（シリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ１（２））
また、上記行処理ステップ１（２）に対して「シリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（５３）式のように表すことができる。ここでは、行処理ステップ１として、１≦ｎ≦Ｎおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（５３）式により更新している。【０２５６】
【数４８】
0004627317.tif 000049
…（５３）【０２５７】
つづいて、上記ＴＬＵを利用した「Sum-Productアルゴリズム」に対して「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の復号アルゴリズムを以下に示す。なお、本実施の形態では、前述した「Overlappedシリアル巡回近似minアルゴリズム」と同様の処理（初期化，列処理，停止規範）についてはその説明を省略する。以下では、前述した「Overlappedシリアル巡回近似minアルゴリズム」と処理の異なる、行処理ステップ１について説明する。【０２５８】
（Overlappedシリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ１（１））
たとえば、上記行処理ステップ１（１）に対して「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（５４）式のように表すことができる。ここでは、行処理ステップ１として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（５４）式により更新している。また、この復号アルゴリズムの行処理ステップ１では、繰り返しｌ−１回目に並列処理にて更新された最小ｋ値のＬＬＲの絶対値：Ｂmn'Cに対して、ＴＬＵを用いた演算を行っている。【０２５９】
【数４９】
0004627317.tif 000050
…（５４）【０２６０】
（Overlappedシリアル巡回近似minアルゴリズムを適用した場合の行処理ステップ１（２））
また、上記行処理ステップ１（２）に対して「Overlappedシリアル巡回近似minアルゴリズム」を適用した場合の本実施の形態の復号アルゴリズムの行処理ステップ１、２のαmn(l)、α'mn(l)を一般化すると、下記（５５）式のように表すことができる。ここでは、行処理ステップ１として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（５５）式により更新している。【０２６１】
【数５０】
0004627317.tif 000051
…（５５）【０２６２】
つづいて、上記本実施の形態の復号アルゴリズムを実行するＬＤＰＣ復号器５の行処理部の特徴的な動作を、図面を用いて説明する。なお、ＬＤＰＣ復号器５の全体構成については、前述した図５または図１３と同様である。【０２６３】
図１８は、前述の実施の形態と同様に、本実施の形態における行処理を実行する行処理部２２，２２−１〜２２−Ｇの構成例を示す図であり、この行処理部は、最小値選択部３１ｃを備えている。なお、前述した図６と同様の構成については、同一の符号を付してその説明を省略する。また、ここでは、一例として、図５のＬＤＰＣ復号器５の場合について説明するが、図１３のＬＤＰＣ復号器５についても同様に適用可能である。【０２６４】
本実施の形態の最小値選択部３１ｃでは、たとえば、途中結果保持部２１からＭｉｎ１ＬＬＲ（Ｂmn(1)），Ｍｉｎ２ＬＬＲ（Ｂmn(2)），ＭｉｎｋＬＬＲ（Ｂmn(k)）とそれぞれの列番号を読み出し、演算部がＴＬＵを用いた演算を行う。すなわち、本実施の形態の最小値選択部３１ｃでは、処理対象となっているｎ列目と、途中結果保持部２１に保持されたＢmn(k)の列番号ｎ（ｋ）と、が一致しないＢmn(k)に対して、演算部が、「Sum-Productアルゴリズム」における以下の演算を行う。【０２６５】
たとえば、演算部は、符号を除く更新値を下記（５６）式のように求める。【０２６６】
【数５１】
0004627317.tif 000052
…（５６）【０２６７】
また、演算対象のＬＬＲをｋ値から最小３値に限定することで演算量を削減することができ、演算部は、符号を除く更新値を下記（５７）式のように求める。【０２６８】
【数５２】
0004627317.tif 000053
…（５７）【０２６９】
なお、上記では、一例として、演算対象のＬＬＲをｋ値から最小３値に限定した場合について説明したが、最小４，５…値と限定した場合においても同様に適用可能である。【０２７０】
以上のように、本実施の形態においては、ＴＬＵを利用した「Sum-Productアルゴリズム」に「シリアル巡回近似minアルゴリズム」または「Overlappedシリアル巡回近似minアルゴリズム」を適用することとした。これにより、他の実施の形態と比較して、計算量およびメモリ量は多くなるが、復号性能を向上させることができる。なお、本実施の形態においては、ＴＬＵを用いた「Sum-Productアルゴリズム」を例に説明したが、数学関数に対してＴＬＵを行う他の復号アルゴリズムにおいても同様である。また、本実施の形態においては、行処理用のＬＬＲの絶対値の最小値に対して、既知の「Sum-Productアルゴリズム」にて規定されたＴＬＵを用いた場合について記載したが、ＴＬＵはこれに限定されるものではなく、「Sum-Productアルゴリズム」にて規定されたＴＬＵ以外のＴＬＵを用いることとしてもよい。この場合も上記と同様の効果を得ることができる。【０２７１】
以上、各実施の形態においては、行処理の開始列を１とし、昇順に処理を行ったが、これに限らない。たとえば、開始列を任意とし、重複しない任意の列に対して処理を行い、すべての列が終了した段階で、再度同一の順番で繰り返し復号を行うこととしてもよい。または、行処理の開始列を任意とし、重複しない任意の列に対して処理を行い、すべての列が終了した段階で、続いて異なる順番で重複しない任意の列に対してすべての列が終了するまで繰り返し復号を行うこととしてもよい。これらの処理においても、上記各実施の形態と同様の効果が得られる。また、上記実施の形態の説明では、確率情報として対数尤度比ＬＬＲを用いる場合について説明したが、対数尤度比ＬＬＲ以外の確率情報を用いるようにしてもよい。
【産業上の利用可能性】
【０２７２】
以上のように、本発明にかかる受信装置および復号方法は、ディジタル通信における誤り訂正技術として有用であり、特に、ＬＤＰＣ符号化された信号を復号する通信装置に適している。
【図１】
0004627317.tif 000054
【図２】
0004627317.tif 000055
【図３】
0004627317.tif 000056
【図４】
0004627317.tif 000057
【図５−１】
0004627317.tif 000058
【図５−２】
0004627317.tif 000059
【図６】
0004627317.tif 000060
【図７−１】
0004627317.tif 000061
【図７−２】
0004627317.tif 000062
【図８】
0004627317.tif 000063
【図９】
0004627317.tif 000064
【図１０】
0004627317.tif 000065
【図１１】
0004627317.tif 000066
【図１２】
0004627317.tif 000067
【図１３】
0004627317.tif 000068
【図１４】
0004627317.tif 000069
【図１５】
0004627317.tif 000070
【図１６】
0004627317.tif 000071
【図１７】
0004627317.tif 000072
【図１８】
0004627317.tif 000073
【図１９】
0004627317.tif 000074