(57)【要約】【課題】Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰを補正する演算回路において、その回路規模を縮小し、データパス遅延を減少させること。【解決手段】演算回路１は、複数ビットから構成されるパスメトリック値の上位０ビット以上からなる第１のビット群ｘ（６）〜ｘ（１０）の全てから１ビットの反転論理和ｓｆを出力するＮＯＲ回路２１と、第２のビット群ｘ（２）〜ｘ（５）の各ビットを反転して第３のビット群ｒｓ（０）〜ｒｓ（３）を出力するインバータ２２と、ｓｆとｒｓ（０）〜ｒｓ（３）それぞれの論理積を求めた第４のビット群ｎｓ（０）〜ｎｓ（３）を出力するＮＡＤ回路２３と、ｎｓ（０）〜ｎｓ（３）に基づき補正項ＣＦを出力するＣＦ出力部２４とを有する。【選択図】  図１
2007174057.tif 000002
【特許請求の範囲】
【請求項１】
Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路であって、
複数ビットから構成されるパスメトリック値の上位１ビット以上からなる第１のビット群全てから１ビットの反転論理和を出力する第１の論理回路と、
前記複数ビットから構成されるパスメトリック値の前記第１のビット群を除いた残りの上位１ビット以上からなる第２のビット群の各ビットを反転して第３のビット群を出力する第２の論路回路と、
前記第１の論理回路の出力と前記第３のビット群の各ビットそれぞれとの論理積を求めた第４のビット群を出力する第３の論理回路と、
前記第４のビット群に基づき補正項を出力する補正項出力部とを有する演算回路。
【請求項２】
前記パスメトリック値のビット幅をｗ、前記パスメトリック値の各ビットをｘ（ｊ）（０≦ｊ≦ｗ−１）、前記第１のビット群のビット幅をａ（１≦ａ≦ｗ−１）、前記第２のビット群のビット幅をｂ（１≦ｂ≦ｗ−ａ−１）、前記第４のビット群と前記補正項出力部との関係を規定するパラメータをｃ（−（ｗ−１）≦ｃ≦ｗ−１）としたとき、前記第１の論理回路の出力値ｓｆ、第３のビット群ｒｓ（ｉ）、前記第３の論理回路の出力値ｎｓ、前記補正項出力部の出力値ＣＦは下記数式を満たすことを特徴とする請求項１記載の演算回路。
【数１】
2007174057.tif 000019
【請求項３】
ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムにおける最大値を出力する最大値出力回路と、
前記補正項出力部の出力と前記最大値とを加算する加算器とを有する
ことを特徴とする請求項１又は２記載の演算回路。
【請求項４】
前記最大値出力回路は、トレリスの一時点におけるそれぞれの状態について、その状態への全ての入力である到達確率の対数近似から、その最大値を求める
ことを特徴とする請求項３記載の演算回路。
【請求項５】
前記最大値出力回路は、
前記到達確率を対数近似した第１の入力及び第２の入力の差を求める演算部と、
前記演算結果に基づき前記第１及び第２の入力のうち大きい方を選択出力する選択部と、
前記演算部の出力の絶対値を前記パスメトリック値として出力する絶対値回路とを有する
ことを特徴とする請求項４記載の演算回路。
【請求項６】
ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムにおける最小値を出力する最小値出力回路と、
前記最小値から前記補正項出力部の出力を減算する減算器とを有する
ことを特徴とする請求項１又は２記載の演算回路。
【請求項７】
前記最小値出力回路は、トレリスの一時点におけるそれぞれの状態について、その状態への全ての入力である到達確率の対数近似から、その最小値を求める
ことを特徴とする請求項６記載の演算回路。
【請求項８】
前記最小値出力回路は、
前記到達確率を対数近似した第１の入力及び第２の入力の差を求める演算部と、
前記演算結果に基づき前記第１及び第２の入力のうち小さい方を選択出力する選択部と、
前記演算部の出力の絶対値を前記パスメトリック値として出力する絶対値回路とを有する
ことを特徴とする請求項７記載の演算回路。
【請求項９】
Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路であって、
ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムにおける最大値を出力する最大値出力回路と、
前記最大値の補正をする補正回路とを備え、
前記補正回路は、複数ビットから構成されるパスメトリック値に基づきマスク値を算出するマスク値生成部と、前記マスク値に基づき前記パスメトリック値に対してマスク処理を施すマスク処理部と、前記最大値と前記マスク処理部の出力との論理和を求める論理回路とを有する演算回路。
【請求項１０】
前記マスク値生成部は、
複数ビットから構成されるパスメトリック値の上位１ビット以上からなる第１のビット群全てから１ビットの反転論理和を求める第１の論理回路と、
前記複数ビットから構成されるパスメトリック値の前記第１のビット群を除いた残りの上位１ビット以上からなる第２のビット群を論理演算して１ビット以上からなる第３のビット群を生成する第２の論理回路と、
前記第１の論理回路の出力と、前記第３のビット群の各ビットとの論理積を求めた前記マスク値を出力する第３の論理回路とを有し、
前記マスク処理部は、
前記マスク値に基づき前記パスメトリック値と同ビットの補正出力を生成する出力部と、
前記補正出力と前記最大値との論理和を求める第４の論理回路とを有する
ことを特徴とする請求項９記載の演算回路。
【請求項１１】
前記パスメトリック値のビット幅をｗ、前記パスメトリック値の各ビットをｘ（ｊ）（０≦ｊ≦ｗ−１）、前記第１のビット群のビット幅をａ（１≦ａ≦ｗ−１）、前記第２のビット群のビット幅をｂ（１≦ｂ≦ｗ−ａ−１）、前記マスク値と前記補正出力との関係を規定するパラメータをｃ（−ｗ≦ｃ≦ｗ）としたとき、前記第１の論理回路の出力値ｓｆ、前記第２のビット群ｙ（ｉ）、第２の論理回路の出力値ｒｓ、前記第３の論理回路の出力値ｎｓ、前記出力部の出力値ＣＦは下記数式を満たすことを特徴とする請求項１０記載の演算回路。
【数２】
2007174057.tif 000020
【請求項１２】
Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路であって、
ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムにおける最小値を出力する最小値出力回路と、
前記最小値の補正をする補正回路とを備え、
前記補正回路は、複数ビットから構成されるパスメトリック値に基づきマスク値を算出するマスク値生成部と、前記マスク値に基づき前記パスメトリック値に対してマスク処理を施すマスク処理部と、前記最小値と前記マスク処理部の反転出力との論理積を求める論理回路とを有する演算回路。
【請求項１３】
前記マスク値生成部は、
複数ビットから構成されるパスメトリック値の上位１ビット以上からなる第１のビット群全てから１ビットの反転論理和を求める第１の論理回路と、
前記複数ビットから構成されるパスメトリック値の前記第１のビット群を除いた残りの上位１ビット以上からなる第２のビット群を論理演算して１ビット以上からなる第３のビット群を生成する第２の論理回路と、
前記第１の論理回路の出力と、前記第３のビット群の各ビットとの論理積を求めた前記マスク値を出力する第３の論理回路とを有し、
前記マスク処理部は、
前記マスク値に基づき前記パスメトリック値と同ビットの補正出力を生成し反転して出力する出力部と、
前記反転出力と前記最小値との論理積を求める第４の論理回路とを有する
ことを特徴とする請求項１２記載の演算回路。
【請求項１４】
前記パスメトリック値のビット幅をｗ、前記パスメトリック値の各ビットをｘ（ｊ）（０≦ｊ≦ｗ−１）、前記第１のビット群のビット幅をａ（１≦ａ≦ｗ−１）、前記第２のビット群のビット幅をｂ（１≦ｂ≦ｗ−ａ−１）、前記マスク値と前記補正出力との関係を規定するパラメータをｃ（−ｗ≦ｃ≦ｗ）としたとき、前記第１の論理回路の出力値ｓｆ、前記第２のビット群ｙ（ｉ）、第２の論理回路の出力値ｒｓ、前記第３の論理回路の出力値ｎｓ、前記出力部の出力値ＣＦは下記数式を満たすことを特徴とする請求項１３記載の演算回路。
【数３】
2007174057.tif 000021
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路に関する。
【背景技術】
【０００２】
ディジタル通信システムでは、伝送路において生じる誤りを訂正する誤り訂正符号が用いられている。特に移動通信システムでは、フェージングの影響により電波強度が激しく変動して誤りが生じ易いため、誤り訂正符号には高い訂正能力が要求される。誤り訂正符号の一例であるターボ符号は、シャノン限界に近い誤り訂正能力を有する符号として注目されており、例えば、第３世代の移動通信方式であるＷ−ＣＤＭＡ（Wideband Code Division Multiple Access）やＣＤＭＡ−２０００で使用されている。
【０００３】
図１５のブロック図は、ターボ符号を生成するための一般的な符号化装置の構成を示している。この符号化装置１０１は、例えば、通信システムの送信側に設けられ、符号化前データである情報ビット（Systematic Bits：組織部）Ｕを、並列連接畳込み符号（ＰＣＣＣｓ：Parallel Concatenated Convolutional Codes）のターボ符号に符号化し、伝送路等の外部へ出力する。なお、ターボ符号は、並列連接符号に限らず、直列連接畳み込み符号など、ターボ復号が可能であればよい。
【０００４】
符号化装置１０１は、図１５に示すように、組織的畳み込み符号化器（Systematic Convolutional Coder）である第１の符号化器１０２及び第２の符号化器１０３と、データをインタリーブする（並び替える）インタリーバ（Interleaving）１０４とを備えている。
【０００５】
第１の符号化器１０２は、入力された組織部Ｕを符号化して冗長ビット（パリティビット：Parity Bits）１Ｐを生成し、この冗長ビット１Ｐを外部へ出力する。インタリーバ１０４は、入力された組織部Ｕの各ビットを所定のインタリーブパターンに並べ替えて組織部Ｕｉｎｔを生成し、この組織部Ｕｉｎｔを第２の符号化器１０２へ出力する。第２の符号化器１０２は、組織部Ｕｉｎｔを符号化して冗長ビット２Ｐを生成し、この冗長ビット２Ｐを外部へ出力する。
【０００６】
符号化装置１０１では、組織部Ｕ、冗長ビット１Ｐ、組織部Ｕｉｎｔ、冗長ビット２Ｐが生成される。組織部Ｕと冗長ビット１Ｐの組（Ｕ，Ｐ）を第１の要素符号（Elemental Code）Ｅといい、組織部Ｕｉｎｔと冗長ビット２Ｐの組（Ｕｉｎｔ，２Ｐ）を第２の要素符号Ｅｉｎｔという。
【０００７】
ターボ復号の特徴は次の２点にある。
１）比較的簡易で小さい構成の組織符号化器を複数個使用する
２）それぞれの符号化器は、符号化器入力である情報ビットに対して、インターリーバ（並べ替え器）を介して連接されている。
【０００８】
上記において、２）の目的は、情報ビットの順番を入換えて符号化器に入力することで、符号化器間において異なる符号語系列を生成することにある。これは、復号側にて、それぞれの符号語の復号結果を、互いの符号語間で補完しあうことにより、誤り訂正能力を向上させるためである。
【０００９】
１）の目的は、符号語間における復号結果の相互補完を、情報ビットを用いて行うためである。例えば３ＧＰＰ（3rd Generation Partnership Project）では、１）に、８状態の組織的畳み込み符号化器（8 states Systematic Convolutional Coder)を２個用いている。この３ＧＰＰでは、Ｗ−ＣＤＭＡなどの第３世代の移動体通信システムの標準化が行なわれている。
【００１０】
図１５における符号化器1の出力{Ｕ,Ｐ１}の組を第１の要素符号（Elemental Code 1）、他方の出力{Ｕｉｎｔ,Ｐ２}の組を第２の要素符号（Elemental Code 2）と呼んでいる。ただし、Ｕｉｎｔは実際は出力されずＵ、Ｐ１、Ｐ２の３つが後段に出力される。なお、実際はターミネーションビット（Termination bits）も出力されるが、ここでは、説明簡易化のため省略する。このため、３ＧＰＰ規定のターボ符号の符号化率（Coding Rate）は１／３ということになる。
【００１１】
このように符号化されたターボ符号を復号することをターボ復号という。ターボ復号では、第１の要素符号Ｅを復号する１番目の復号器と第２の要素符号Ｅｉｎｔを復号する２番目の復号器との間で外部情報を交換しながら繰り返し復号が行われる。なお、復号器は、２つに限らず、ターボ符号の要素符号数に従って２以上の複数段の復号器を用いてもよい。
【００１２】
図１６に代表的なターボ復号の復号装置を示す。ターボ復号の特徴は次の１点にある。
１）複数の要素符号間にて外部情報（Extrinsic Information）を交換しながら、複数回処理を繰り返す。
【００１３】
図１６に示すように、代表的な復号装置２０１は、第１の復号器２０２、第２の復号器２０２、インタリーブメモリ２０４、デインタリーブメモリ２０５及び硬判定・ＣＲＣ判定部２０６を有する。
【００１４】
このような復号装置２０１におけるターボ復号は以下の工程からなる。
Ａ）第２の復号器２０３の外部情報をデインタリーブメモリ２０５から読み出し、第１の要素符号と共に第１の復号器２０２に入力する。第１の復号器２０２から外部情報を出力し、インタリーブメモリ２０４に書き込む。
Ｂ）第１の復号器２０２の外部情報をインタリーブメモリ２０４から読出し、第２の要素符号と共に第２の復号器２０３に入力する。第２の復号器２０３から外部情報を出力し、デインタリーブメモリ２０５に書き込む。
Ｃ）復号の最終繰り返しでは、第２の復号器２０３の対数尤度比ＬＬＲをデインタリーブメモリ２０５から読出し、硬判定・ＣＲＣ判定部２０６にて硬判定を行なった後、ＣＲＣによりエラーチェックを行なっている。
【００１５】
そして、先ず、Ａ）を実行する。このときの第２の復号器からの外部情報は初期値（＝０）とする。次に、Ｂ）を実行する。そして、再びＡ）を実行し、任意の回数だけＢ）とＡ）とを繰り返す。そして、最終繰り返しにおいて、Ｂ）を実行する。この際、第２の復号器２０３は、外部情報ではなく対数尤度比を出力する。最後にＣ）を実行する。
【００１６】
ターボ符号は組織符号であるため、受信系列には情報ビットＵが含まれている。外部情報とはこの情報ビットＵに対して復号の前に分かっている、"０"らしさ（"１"らしさと同義）を表す値（事前値）である。つまりターボ復号とは、第１、第２の要素符号間の復号において、それぞれの情報ビットが"０"である確率を交換（相互補完）しながら、その確率の確度を上げ、誤り訂正能力を強化する処理である。
【００１７】
この外部情報は軟出力復号化器の出力（対数尤度比ＬＬＲ：Log Likelihood Ratio）から生成することができる。この軟出力を生成する方法にはＭＡＰ系とＳＯＶＡ系の２種類があり、誤り訂正能力がより高いＭＡＰ系の手法が一般によく用いられている。ＭＡＰ系には主に、ＭＡＰ、Ｌｏｇ−ＭＡＰ、Ｍａｘ−Ｌｏｇ−ＭＡＰの３種が知られている。
【００１８】
次に、ＭＡＰ、Ｌｏｇ−ＭＡＰ、Ｍａｘ−Ｌｏｇ−ＭＡＰの各アルゴリズムについて説明するが、ここでは先ず、上記対数尤度比ＬＬＲについて説明する対数尤度比ＬＬＲも外部情報と同様に、情報ビットＵの"０"'らしさを表す値であるが、外部情報が事前値であるのに対し、対数尤度比ＬＬＲは事後値と呼ばれる。
【００１９】
対数尤度比は、下記式（１）にて表される。
【００２０】
【数１】
2007174057.tif 000003
【００２１】
【数２】
2007174057.tif 000004
【００２２】
ＬＬＲは上記式（１）で表される。ここでは、"０"を＋１、"１"を−１で表現している。上記の"０"である確率と"１"である確率の対数比を取ることで、"０"と"１"のどちらがより確からしいかの尤度値を得ることができる。すなわち、"０"である確率の方が大きければ、両者の比は１より大きくなり、対数比は０より大（正の数）となる。逆に"１"である確率が大きければ、両者の比は１未満の小数点以下の数値となり、対数比は０よりも小（負の数）となる。よって、"０"であるか"１"であるかの確率の高さは、対数尤度比の符号（正又は負）により判定することができる。よって、"０"である確率と"１"である確率が等しければ両者の比は１となり、その対数は０となり、いずれの確率が高いかは不明となる。
【００２３】
上記式（２）は、ｋ番目の情報ビットｕｋに関するＬＬＲを表している。上記式（２）で表されるｕｋはｋ番目の情報ビットに対する受信側での推定値であり、ＬＬＲを硬判定した結果（＝"０"又は"１"）となる。硬判定ｓｉｇｎ[  ]は、２進数値の符号ビットを取り出す処理であり、値が正の場合は"０"、負では"１"となる。よって、上記式（２）は、ｋ番目の情報ビットに対するＬＬＲの硬判定を意味する。
【００２４】
次に、ＭＡＰ、Ｌｏｇ−ＭＡＰ、Ｍａｘ−Ｌｏｇ−ＭＡＰの各アルゴリズムについて説明する。
【００２５】
ＭＡＰアルゴリズム(Maximum A priori Probability)アルゴリズム
ＭＡＰとはMaximum A priori Probabilityの略であり、事後値（事後確率：A priori Probability）であるＬＬＲを最大にする復号方法であり、事後確率最大復号とも呼ばれる。
【００２６】
ＭＡＰでは上記式（１）に幾つかの数式変換を施した、下記式（３）を用いて対数尤度比Ｌ（ｕｋ）を算出する。γはトレリスの遷移確率を表し、αは始点から終点の方向へ遷移した場合の、トレリスの各状態への到達確率を示し、βは逆に終点からの到達確率を表している。ここで、トレリスとは符号化器の状態遷移図を時間軸上に展開したものである。これをトレリス線図という。
【００２７】
【数３】
2007174057.tif 000005
【００２８】
ＭＡＰアルゴリズムでは、トレリス線図（状態遷移図）に基づいてビタビ復号を行う。トレリス線図で各時点の各状態を結ぶパスが復号すべき符号系列に対応しており、とりうるパスに対する尤度（パスメトリック）を計算し、最も尤度の高いパスを生き残りパスとして復号する。
【００２９】
先ず、トレリス線図について説明する。図１７は、再帰的畳込み符号を出力する再帰的畳込み符号化器を示す図、図１８は、その状態遷移を示す模式図である。
【００３０】
再帰的畳込み符号化器では、入力ＩＮＰＵＴからの入力ビットによって、Ｄ１、Ｄ２に格納される値が変化する。再帰的符号化器では、Ｄ２の出力が入力ＩＮＰＵＴ側へ戻されることで、再帰的な畳込み符号を実現する。図１８は、このＤ１、Ｄ２のとりうる値（００）、（０１）、（１０）、（１１）の状態遷移図を示し、図中、０／０のように示すのは、入力ビット／出力ビットを表している。入力ＩＮＰＵＴからの入力ビットが"０"、又は"１"に応じてＤ１、Ｄ２の値が遷移する。例えば、畳込み符号化器では、（Ｄ１  Ｄ２）が（００）の状態のとき、入力ＩＮＰＵＴから"０"が入力された場合、出力ＯＵＴＰＵＴから"０"を出力し、Ｄ１、Ｄ２は、（００）の状態に戻る。また、"１"が入力された場合には"１"を出力し、Ｄ１、Ｄ２は（１０）の状態に遷移する。
【００３１】
この状態遷移図を時間軸上に展開したものが図１９に示すトレリス線図となる。図１９において、実線の矢印は、入力ビットが"０"である場合のＤ１、Ｄ２の状態遷移を示し、破線の矢印は、入力ビットが"１"である場合のＤ１、Ｄ２の状態遷移を示している。横軸は、時間軸を示し、ｋ−１、ｋは任意のタイミングを示す。
【００３２】
トレリス線図上で順方向にビタビ復号を行ってパスメトリックを算出する処理をフォワード処理といい、フォワード処理とは逆方向にビタビ復号を行ってパスメトリックを算出する処理をバックワード処理という。フォワード処理で算出されるパスメトリック値をαパスメトリック、バックワード処理で算出されるパスメトリック値をβパスメトリック値という。そして、γは、タイミング（ｋ−１）におけるある状態（例えば状態（１１））からタイミングｋにおけるある状態（例えば状態（１１））へ遷移する確率（ブランチメトリック）を示す。α、βは、タイミング（ｋ−１）、ｋにおけるその状態（例えば状態（１１））である確率を示している。αパスメトリック、βパスメトリック及びブランチメトリック（γ）から対数尤度比ＬＬＲが算出される。
【００３３】
図２０は、トレリス線図を使用した遷移確率の求め方を説明する図である。また、α、βの算出式を下記式（４）、（５）に示す。上述の通り、γはトレリスの一時点上の各状態における遷移確率である。αは、下記式（４）により示され、順方向（トレリス線図上の始点から終点へ向かう方向：後方向））への各状態の到達確率であり、順方向にγを積算してくことになる。βは下記式（５）で示され、逆方向（終点から始点へ向かう方向：前方向）への積算になる。
【００３４】
【数４】
2007174057.tif 000006
【００３５】
例えばαｋ（００）を、タイミングｋにおける状態（００）（以下状態（００）ｋと記載する）にある（存在する）順方向の到達確率とすると、このαｋ（００）は、図２０及び式（４）に示すように、例えば、αｋ−１（００）と、状態（００）ｋ−１にある到達確率αｋ―1（００）から状態（００）ｋへ遷移する遷移確率γｋ（００,００）との積と、状態（０１）ｋ−１にある到達確率αｋ−１（０１）と、状態（００）ｋ−１から状態（００）ｋへ遷移する遷移確率γｋ（０１,００）との積との和となる。
【００３６】
また、βｋ−１（００）を、タイミングｋ−１における状態（００）（以下状態（００）ｋと記載する）にある逆方向の到達確率とすると、このβｋ−１（００）は、図２０及び式（５）に示すように、例えば、βｋ−１（００）と、状態（００）ｋ−１にある到達確率βｋ―1（００）から状態（００）ｋへ遷移する遷移確率γｋ（００,００）との積と、状態（０１）ｋ−１にある到達確率βｋ−１（００）と、状態（００）ｋ−１から状態（１０）ｋへ遷移する遷移確率γｋ（００,１０）との積との和となる。
【００３７】
なお、上記式（４）、（５）において、α（ｓ）、β（ｓ）は現在の状態ｓ、前回の状態ｓ' におけるパスメトリック、γ（ｓ',ｓ）は、ｓ'からｓへ状態遷移する確率を示す。
【００３８】
図２１は、α、β、γから対数尤度比ＬＬＲを算出する方法を説明する図である。図２１に示すように、順方向の到達確率αと、逆方向の到達確率βと、状態間の遷移確率γとを乗算することにより、トレリスの全時点を考慮した場合の、該当時点の遷移確率が求まる。このうちの、入力"０"に対応する遷移確率の積をδ０、"１"に対応する確率積をδ１と呼ぶ。δ０とδ１の対数比ｌｏｇ（δ０／δ１）が、上記式（３）に示す対数尤度比ＬＬＲとなる。
【００３９】
対数尤度比と外部情報は下記の数式（６）を満たす。すなわち、ターボ復号では、この対数尤度比ＬＬＲを示す式（６）の両辺から内部情報を減算することで外部情報を算出する。
【００４０】
【数５】
2007174057.tif 000007
【００４１】
Ｌｏｇ−ＭＡＰアルゴリズム
次に、Ｌｏｇ−ＭＡＰアルゴリズムについて説明する。上述のように、ＭＡＰアルゴリズムでは確率の積を求めるため、乗算器が必要になり、回路規模が著しく増加する。ゆえに、実使用上ではＭＡＰにおける確率演算を対数領域にて近似し、又は簡略化したＬｏｇ−ＭＡＰ、又はＭａｘ−Ｌｏｇ−ＭＡＰが使用される。近似式を下記式（７）乃至（１１）に示す。
【００４２】
【数６】
2007174057.tif 000008
【００４３】
【数７】
2007174057.tif 000009
【００４４】
上記のように、α、γ、βを式（７）〜（９）に示すように、それぞれ対数ｌｏｇで近似してＡ、Γ、Ｂと定義し、上記（４）、（５）を変形した式が下記（１０）、（１１）である。ただし、下記（１０）、（１１）は、ｅｘｐ内の演算をＡｉに置き換えて示すと式（１２）となる演算が含まれており、実使用上問題となる。そこで、式（１２）を更に分解して式(１３)を導く。
【００４５】
【数８】
2007174057.tif 000010
【００４６】
ここで、ｉは、ある状態へ遷移するパスの数を示し、例えば図２０に示す例では、順方向において状態（００）ｋに遷移するパスの数は２であり、ＡＭは、このうちの大きい方を示す。実際は、この式（１３）として演算を進めることになる。これがＬｏｇ−ＭＡＰであり、特に式（１３）の右辺第２項を、ｌｏｇ(１＋ｅ−ｘ)としてＬＵＴで実装する手法が一般的である。その他には、固定値や、−ａｘ＋ｂで更に近似する方法も知られている。このｌｏｇ(１＋ｅ−ｘ)加算の操作を、特にＬｏｇ−ｓｕｍと呼ぶこともある。また、第２項の｜Ａｉ−ＡＭ｜をパスメトリック値という。
【００４７】
ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズム
Ｍａｘ−Ｌｏｇ−ＭＡＰは、上記（１０）、（１１）に示すＬｏｇ−ＭＡＰを更に近似した方法である。その近似式を下記式（１４）、（１５）に示す。すなわち、Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムでは、上記式（１０）、（１１）からＬｏｇ−ｓｕｍの項を省いたものである。ｍａｘ（  )は最大値を選択する操作であり、Viterbi AlgorithmのＡＣＳ（Add Compare Select）演算と同義である。つまり、確率演算をViterbi Algorithmで行うことができる、一番安価で簡易な方法になる。
【００４８】
【数９】
2007174057.tif 000011
【特許文献１】特開２００４−８０５０８号公報
【特許文献２】特開２００４−１９４３２６号公報
【特許文献３】特開２００２−３４４３３０号公報
【特許文献４】特開２００２−１００９９５号公報
【非特許文献１】A. Taffin, "Generalized stopping criterion for iterative decoders", IEEE Electronics Letters, 26th, June, 2003, Vol. 39, No.13
【発明の開示】
【発明が解決しようとする課題】
【００４９】
上述したとおり、Ｌｏｇ−ＭＡＰにおける確率演算は、Viterbi AlgorithmのＡＣＳ演算に、Ｌｏｇ−ｓｕｍによる補正（以下、ヤコビアン補正項という。）を加えることに等しい。図２２は、従来のＬｏｇ−ＭＡＰにおける確率演算を行なう回路を模式的に示す図である。図２２に示すように、上記式（１３）の演算を行なう回路３０１は、入力される値を比較し、大きい方を選択して出力するＡＳＣ回路３０１と、ヤコビアン補正項を算出し、ＡＳＣ回路３０２の演算結果との和を求めるＬｏｇ-Ｓｕｍ回路３０３とを有する。
【００５０】
ＡＣＳ回路３０１には、２つのＡｉが入力される。以下、入力Ｉ１、入力Ｉ２とする。ＡＣＳ回路３０２は、入力Ｉ１と入力Ｉ２の反転した値とを加算する加算器３１１と、選択器３１２と、絶対値回路３１３とを有する。加算器３１１は、入力Ａと入力Ｂの反転とを加算し、結果が正になるか負になるかで入力Ｉ１、Ｉ２の大小を判定し、その判定結果を選択器３１２へ供給する。選択器３１２には、判定結果に基づき入力Ｉ１、Ｉ２のうち大きな方（＝ＡＭ）を選択出力する。また、絶対値回路３１３は、加算器３１１の結果、すなわち入力Ｉ１と入力Ｉ２との差の絶対値を出力する。この値は、上記式（１３）におけるパスメトリック値｜Ａｉ−ＡＭ｜である。
【００５１】
Ｌｏｇ−Ｓｕｍ回路３０２は、この値に基づきｌｏｇ（１＋ｅ＾（−｜Ａｉ−ＡＭ｜））を算出する。この補正項の演算としては、上述のとおり、固定値、−ａｘ＋ｂの近似式の使用、又はｌｏｇ(１＋ｅ−ｘ)のＬＵＴを使用して実装する方法が知られている。そして、得られた結果を、加算器３２１によりＡＣＳ回路３０１からの出力ＡＭと加算し、結果ｓを出力する。
【００５２】
しかしながら、このような従来方式ではＬＵＴの実装、又は近似式に含まれる乗算加算回路の実装が必要になり、回路規模が大きく、また、データパス遅延も大きくなるという問題点がある。そこで、ＬＵＴや乗算加算回路を実装せずに、ｘのビット演算のみの簡易な回路でＬｏｇ−ｓｕｍ補正項を算出することができれば、より小さい回路、小さい遅延の復号装置を提供することができる。
【課題を解決するための手段】
【００５３】
本発明にかかる演算回路は、Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路であって、複数ビットから構成されるパスメトリック値の上位１ビット以上からなる第１のビット群全てから１ビットの反転論理和を出力する第１の論理回路と、前記複数ビットから構成されるパスメトリック値の前記第１のビット群を除いた残りにおける１ビット以上からなる第２のビット群の各ビットを反転して第３のビット群を出力する第２の論路回路と、前記第１の論理回路の出力と前記第３のビット群の各ビットそれぞれとの論理積を求めた第４のビット群を出力する第３の論理回路と、前記第４のビット群に基づき補正項を出力する補正項出力部とを有するものである。
【００５４】
本発明においては、Ｌｏｇ−ＭＡＰアルゴリズムにおける補正項をパスメトリック値（Path Metric Difference：ＰＭＤ）のビット演算により求めることで、回路規模を縮小し、データパス遅延を減少させることができる。
【００５５】
本発明にかかる演算回路は、Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路であって、ＭＡＸ−Ｌｏｇ−ＭＡＰを出力する最大値出力回路と、前記最大値の補正をする補正回路とを備え、前記補正回路は、複数ビットから構成されるパスメトリック値に基づきマスク値を算出するマスク値生成部と、前記マスク値に基づき前記パスメトリック値に対してマスク処理を施すマスク処理部と、前記最大値と前記マスク処理部の出力との論理和を求める論理回路とを有するものである。
【００５６】
本発明においては、Ｌｏｇ−ＭＡＰアルゴリズムにおける補正項の加算をパスメトリック値のビット演算によるマスク値の算出及びマスク処理により行なうことで、回路規模を縮小し、データパス遅延を減少させることができる。
【発明の効果】
【００５７】
本発明によれば、Ｌｏｇ−ＭＡＰアルゴリズムに基づきＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路において、その回路規模を縮小し、データパス遅延を減少させることができる。
【発明を実施するための最良の形態】
【００５８】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、ターボ復号装置における外部情報又は対数尤度比を算出する軟出力復号部に使用されるものであって、ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正するための、Ｌｏｇ−ＭＡＸアルゴリズムにおけるヤコビアン補正項を算出する演算回路、又はＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムで得られる近似値を補正する演算回路に適用したものである。
【００５９】
実施の形態１．  
図１は、本実施の形態にかかる演算回路を示す図である。本実施の形態にかかる演算回路は、例えば図９に示すターボ符号を復号する復号装置における各復号器２０２、２０３に設けられる、復号器２０２、２０３においては、式（１６）に示す対数尤度比が算出される。
【００６０】
【数１０】
2007174057.tif 000012
【００６１】
上記対数尤度比から外部情報が算出され、これらを復号器２０２、２０３にてやり取りし、繰り返し演算することで、受信データを復号する。この対数尤度比を求める際には式（１７）、（１８）で近似した式（１９）、（２０）を求める。本実施の形態にかかる演算回路は、この式（１９）、（２０）を求めるための回路である。
【００６２】
【数１１】
2007174057.tif 000013
【００６３】
【数１２】
2007174057.tif 000014
【００６４】
ここで、例えば式（１９）であれば、下記（２１）のように近似することができる。
【００６５】
【数１３】
2007174057.tif 000015
【００６６】
すなわち、この演算回路１は、トレリスにおける一時点の到達確率を対数近似した値Ａｉを入力とし、Ａｋ（ｓ）又はＢｋ−１（ｓ）を求める。本例においては、入力Ａｉは、Ａ１（＝Ｉ１）、Ａ２（＝Ｉ２）の２つであるが、２以上であってもよい。
【００６７】
演算回路１は、入力Ｉ１、Ｉ２のうち、最大値ＡＭを求めるＡＳＣ回路２と、ＡＳＣ回路２からパスメトリック値（｜Ａｉ−ＡＭ｜）が供給され、このパスメトリック値から上述のヤコビアン補正項を求め、それを最大値ＡＭに加算することで最大値ＡＭの補正を行なう補正回路３とを有する。最大値ＡＭは、は、ＭＡＸ−Ｌｏｇ−ＭＡＰアルゴリズムによって得られる近似値（最大値）である。補正回路３は、算出した補正項とＡＳＣ回路２にて得られた最大値ＡＭとを加算し、式（１９）又は式（２０）に示すＡｋ（ｓ）又はＢｋ（ｓ）を出力する。
【００６８】
ＡＳＣ回路２は、加算器（Ａｄｄｅｒ）と、選択器１２と、絶対値回路１３とを有する。加算器１１には、入力Ｉ１と入力Ｉ２の反転入力とが供給され、その大小関係に応じたキャリーアウトを出力する。すなわち、Ｉ１＜Ｉ２であればＩ１とＩ２との差は−となり、キャリーアウトが選択器１２に出力される。選択器１２にも入力Ｉ１、Ｉ２が供給され、上記キャリーアウトに基づき値の大きな方を選択して出力する。すなわち、上記式（１０）におけるＡＭを出力する。また、加算器１１の出力、すなわち、Ｉ１−Ｉ２は、絶対値回路１３に供給され、絶対値｜Ｉ１−Ｉ２｜（＝｜Ａｉ−ＡＭ｜）とされ補正回路３へ供給される。
【００６９】
ここで、本実施の形態においては、Ｉ１、Ｉ２として、１１ビットのデータが供給される例について説明するが、データは１１ビットに限らず、これより少ない又は大きいビット数であってもよいことは勿論である。以下の説明においては、各ビットをＭＳＢから（１０）,ｘ（９）,・・・,ｘ（０）と表し、１ビット目ｘ（０）、２ビット目ｘ（１）などと記載することとする。また、本実施の形態においては、入力は、Ｉ１、Ｉ２の２つとして説明するが、３以上であってもよい。
【００７０】
補正回路３は、第1の論理回路としてのＮＯＲ回路２１、第２の論理回路としてのインバータ２２、第３の論理回としてのＡＮＤ回路２３、補正項出力部としてのＣＦ出力部２４、及び加算器２５を有する。本実施の形態においては、ＮＯＲ回路２１は、入力される１１ビットのデータのうち、第１のビット群としての上位５ビット（ｘ（１０）〜ｘ（６））の全てからもとめた１ビットの反転論理和を出力する。インバータ２２は、第２のビット群としての３ビット目ｘ（２）〜６ビット目ｘ（５）の各ビットを反転して第３のビット群として出力する。ＡＮＤ回路２３は、ＮＯＲ回路２１の出力と、各インバータ２２の出力との論理積を第４のビット群とし出力する。そして、ＣＦ出力部２４により、このＡＮＤ回路の出力４ビットを下位４ビットとし、上位７ビット分を０とし、合計１１ビットとなった補正ビットＣＦ（０）〜ＣＦ（１０）（補正値ＣＦ）を加算器２５へ供給する。加算器２５には、ＡＳＣ回路２からの最大値ＡＭが供給され、この最大値ＡＭと上記補正値ＣＦとを加算し、対数尤度比ＲＲＬ（ｓ）として出力する。
【００７１】
図１に示す演算回路の詳細を図２に示す。補正回路３において、入力｜Ｉ１−Ｉ２｜（パスメトリック値＝｜Ａｉ−ＡＭ｜）のビット幅をｗ、入力の各ビットをｘ（ｊ）（０≦ｊ≦ｗ−１）、ＮＯＲ回路２１に入力するビット群のビット幅をａ（１≦ａ≦ｗ−１）、インバータ２２に入力するビット群のビット幅をｂ（１≦ｂ≦ｗ−ａ−１）、ＡＮＤ回路２３が出力するビット群とＣＦ出力部２４との関係を規定するパラメータをｃ（−（ｗ−１）≦ｃ≦ｗ−１）とする。このとき、ＮＯＲ回路２１の出力をｓｆ、各インバータ２２ａ〜２２ｄの出力ビットをｒｓ（ｉ）、各ＡＮＤ回路２３ａ〜２３ｄの出力ビットが示す値をｎｓ、ＣＦ出力部２４が出力するＣＦの各値は下記の式（２２）〜（２５）を満たす。
【００７２】
【数１４】
2007174057.tif 000016
【００７３】
本実施の形態においては、ａ＝５、ｂ＝４、ｃ＝０の例を示している。後述するように、これらのパラメータａ，ｂ，ｃを変更することで所望の補正値ＣＦを得ることができる。この補正回路３は、図２に示すように、ＮＯＲ回路２１は、ｘ（６）〜ｘ（１０）の反転論理和ｓｆを求める。インバータ２２は、インバータ２２ａ〜２２ｄを有し、それぞれｘ（５）〜ｘ（２）の反転値をｒｓ（３）〜ｒｓ（０）として出力する。ＡＮＤ回路２３は、ＡＮＤ回路２３ａ〜２３ｄを有し、それぞれ反転論理和ｓｆとｒｓ（３）〜ｒｓ（０）との論理積をｎｓ（３）〜ｎｓ（０）として出力する。ＣＦ出力部２４は、ＣＦ（０）〜ＣＤ（１０）の１１ビットを出力するが、本実施の形態においては、後述するパラメータｃが０のため、ＣＦ（０）〜ＣＦ（３）をｎｓ（０）〜ｎｓ（３）として出力する。ＣＦ（４）以上の上位ビットは全て０とする。この出力ＣＦと選択器１２の出力ＡＭが加算器２５で加算されて出力ｓを得る。
【００７４】
次に、上記式（２２）〜（２５）におけるパラメータａ、ｂ、ｃについて詳細に説明する。図３は、補正回路３において求まるＣＦ出力部２４の出力ＣＦを示すグラフ図である。図３は、パラメータａ、ｂ、ｃを種々変更した場合の出力部２４の出力結果ＣＦ（以下補正曲線という。）を示している。図３において、各補正曲線Ｌ１〜Ｌ４は、パラメータｘ、ｙ、ｚの値をｃｆ＿ｘ＿ｙ＿ｚとして示す。パラメータａ＝ｗ−ｘ、パラメータｂ＝ｚ、パラメータｃ＝２−ｌｏｇ２（ｙ）に対応する。補正曲線は基本的には、階段状の曲線となる。上述の図２に示す本実施の形態においては、ｗ＝１１、ａ＝５、ｂ＝４、ｃ＝０であり、（ｘ,ｙ,ｚ）＝（ｗ−ａ,２２−ｃ,ｂ）＝（６,４,４）となり、図３におけるＬ１を示す。先ず、ＮＯＲ回路２１へ出力するビット数ａ、すなわちパラメータｘを変更すると、ＣＦ出力部２４の出力は、Ｌ１、Ｌ２に示すように、階段の大きさが指数的に変化する。パラメータｘ＝４の階段に比べパラメータｘ＝６の階段は、その全体の幅、高さが略４倍になっている。
【００７５】
ｒｓ（ｉ）は、図３に示す補正線の傾きを負にするための演算であり、最下位ビットからｓｆに使用した上位ビット以下で任意のビットｘについて演算される。このｒｓ（ｉ）を求めるビット数ｂ、すなわちパラメータｚを変化させると、Ｌ１、Ｌ４に示すように、各階段の幅（分解能）が変化する。ｚ＝４のＬ１では４ビット分、ｚ＝２のＬ３では２ビット分の幅（精度）となる。
【００７６】
ＡＮＤ回路２３の出力値ｎｓは、図３において、ｘがある値以上であるときその出力ｎｓを０にするための演算である。図３では、ｘが６０以上の値をとる場合には、出力が全て０になるようになっている。このＡＮＤ回路２３の各出力ビットｎｓ（０）〜ｎｓ（３）をＣＦ（ｊ）のいずれのビットとするかを決定するパラメータｃ、すなわちパラメータｙが変化すると、Ｌ１、Ｌ３に示すように、階段の段数自体は変化しないものの、その高さが異なる曲線となる。ｙ＝４では、高さが１であるのに対し、ｙ＝２では高さが２になっている。
【００７７】
なお、本例では、ｃ＝０であり、ｎｓ（０）〜ｎｓ（３）＝ＣＦ（０）〜ＣＦ（３）に対応する。例えばｃ＝２であれば、ｎｓ（０）〜ｎｓ（３）＝ＣＦ（２）〜ＣＦ（５）となり、ｃ＝−２であれば、ｎｓ（２）〜ｎｓ（３）＝ＣＦ（０）〜ＣＦ（１）となる。すなわち、パラメータｃは、ｎｓ（ｉ）の最下位ビットＣＦ（０）からのシフト量を示す。ｎｓビットに対応しないＣＦは全て０とされる。
【００７８】
これらのパラメータａ、ｂ、ｃは、求める補正線の形状に応じて適宜設定することができる値である。例えば階段状の補正線の解像度（段数）を増やすことでｌｏｇ（１＋ｅ＾（−ｘ））に近づけることができる。ここで、このように段階的にＬＵＴにより補正を行なう場合、本実施の形態にかかる演算回路は、段数が多いほど、ＬＵＴに比して回路規模の点で優位となる。ＬＵＴは、段数が多いほどテーブルを記憶するためのメモリ容量が増大すると共に、どの範囲に入るかを比較し選択する選択回路の回路規模が大きくなるためである。
【００７９】
このように、パラメータａ、ｂ、ｃ、すなわち（ｘ,ｙ,ｚ）＝（ｗ−ａ,２２−ｃ,ｂ）を種々変化させることで、補正曲線の形状を自在に変化させることができる。ここで、ＣＦ出力部２４の出力ＣＦは、ＡＭに加算するヤコビアン補正項であるため、パラメータａ、ｂ、ｃを適宜選択し、本来のヤコビアン補正項を示す線に近いものとすることが好ましい。
【００８０】
図４は、ＣＦ（補正曲線）Ｌ１２と実際のヤコビアン補正項（理想曲線）Ｌ１１とを対比して示す図である。パラメータａ、ｂ、ｃが適切な値であると、理想曲線Ｌ１１にほぼ沿ったＣＦ（補正曲線）Ｌ１２を得ることができる。図４には、ビット幅ｗ＝９のときの補正曲線Ｌ１４及び理想曲線Ｌ１３もあわせて示す。
【００８１】
図２に示す加算器２５の出力は、図３、図４に示すようなＣＦの値に最大値ＡＭを加算したものとなる。図５は、ＣＦを固定値とし、最大値ＡＭを可変とした場合の補正回路３の出力ｓを示すグラフ図である。また、図６は、ＣＦを可変とし、最大値ＡＭを固定値とした場合の補正回路３の出力ｓを示すグラフ図である。
【００８２】
図５に示す曲線Ｌ２１は、補正なしのもの、曲線Ｌ２２、Ｌ２３は、ＣＦ＝３、１５とした場合の補正回路の出力ｓを示す。また、図６に示す曲線Ｌ３１は、最大値ＡＭ＝０とした場合、曲線Ｌ３２、３３は、最大値ＡＭ＝３、１５とした場合の補正回路３の出力ｓを示している。実際には、ＣＦ及び最大値ＡＭのいずれも変化するため、補正回路３の出力ｓは、これらを組み合せた３次元的な変化有する値となる。
【００８３】
なお、本実施の形態においては、入力Ｉ１、Ｉ２の最大値を求め、補正項を加算する演算回路について説明したが、入力Ｉ１、Ｉ２の最小値を求め、補正項を減算するようにしてもよい。その場合、補正回路３において、ＣＦのｎｓビット以外のビットは全て"１"とし、加算器２５の一方の入力を反転入力とすればよい。
【００８４】
本実施の形態においては、ＮＯＲ回路２１への入力ビット幅ａ、インバータ２２により反転するビット幅ｂ、ｎｓ（０）〜ｎｓ（３）のＣＦ（０）〜ＣＦ（１０）への接続位置を決定するパラメータｃを適宜設定することで、ヤコビアン補正項ｌｏｇ（１＋ｅ＾（−ｘ））の近似値をビット演算のみで実現することができ、精度よくかつ回路規模を増大させずにＡｋ（ｓ）、Ｂｋ−１（ｓ）を求めることができる。
【００８５】
実施の形態２．  
次に、本発明の実施の形態２について説明する。上述の実施の形態１にかかる演算回路は、補正項を算出してこれを加算するものであったが、上述の補正回路には加算器が含まれる。そこで、更に回路規模の縮小化を図ったものが本実施の形態にかかる演算回路である。
【００８６】
図７は、本実施の形態にかかる演算回路、図８は、その演算回路の詳細を示す図である。なお、図７、図８に示す本実施の形態において、図１、図２に示す実施の形態１と同一構成要素には同一の符号を付してその詳細な説明は省略する。
【００８７】
図７に示すように、本実施の形態に係る補正回路３３は、ＡＣＳ回路２からの出力に対し、下位何ビットかをマスク値として決定するマスク値生成回路４１と、マスク値生成回路４１の出力に基づきマスク処理し、補正値ＣＦ（０）〜ＣＦ（１０）を出力するマスク処理部としてのＣＦ出力部４２と、その結果とＡＳＣ回路２からの出力との論理和を求めるＯＲ回路４３とを有する。
【００８８】
マスク値生成回路４１は、図８に示すように、第１の論理回路としてのＮＯＲ回路５０ａ、第２の論理回路としての論理回路５０ｂ、及び第３の論理回路としてのＡＮＤ回路５０ｃを有する。
【００８９】
ＮＯＲ回路５０ａは、ビット幅ａ、本例では、第１のビット群としてのａ＝４の上位４ビット（ｘ（７）〜ｘ（１０））から反転論理和ｓｆを得る。
【００９０】
論理回路５０ｂは、ビット幅ｂ、本例においては、第２のビット群としてのｂ＝３の３ビット（ｘ（４）〜ｘ（６））に基づき、第３のビット群としてのｒｓ（０）〜ｒｓ（６）を算出する。ｘ（６）〜ｘ（４）＝ｙ（２）〜ｙ（０）とすると、論理回路５０ｂは、ｙ（０）とｙ（１）との論理積を求めるＡＮＤ回路５３と、ｙ（０）とｙ（１）のＯＲを求めるＯＲ回路５２とを有する。更にＮＯＲ回路５４〜５６、インバータ５７、反転論理積回路５８〜６０を有する。ＮＯＲ回路５４は、ｙ（２）とＯＲ回路５２の出力とのＮＯＲを求めてｒｓ（６）を出力する。ＮＯＲ回路５５は、ｙ（２）とｙ（１）のＮＯＲを求めてｒｓ（５）を出力する。ＮＯＲ回路５６は、ｙ（２）とＡＮＤ回路５３の出力のＮＯＲを求めてｒｓ（４）を出力する。インバータ５７は、ｙ（２）のインバータを求めてｒｓ（３）を出力する。反転論理積回路５８は、ｙ（２）とＯＲ回路５２の出力とのＡＮＤを求めてｒｓ（２）を出力する。反転論理積回路５９は、ｙ（２）とｙ（１）のＡＮＤを求めてｒｓ（１）を出力する。反転論理積回路６０は、ｙ（２）とＡＮＤ回路５３の出力のＡＮＤを求めてｒｓ（０）を出力する。
【００９１】
ＡＮＤ回路５０ｃは、ｓｆと各ｒｓとの論理積をマスク値として求める。このＡＮＤ回路５０ｃは、ＡＮＤ回路６１〜６７を有する、本実施の形態においては、ＡＮＤ回路６１〜６５は、それぞれｒｓ（６）〜ｒｓ（２）とｓｆとの論理積を求め、ｎｓ（４）〜ｎｓ（０）を出力する。ＡＮＤ回路６６、６７は、本実施の形態においては、使用しない。ＣＦ出力部４２は、ｎｓ（４）〜ｎｓ（０）をそれぞれＣＦ（４）〜ＣＦ（０）として出力する。また、ｎｓビットが供給されない他のＣＦは、全て０として出力する。
【００９２】
補正回路３３への入力（パスメトリック値）のビット幅をｗ、その各ビットをｘ（ｊ）（０≦ｊ≦ｗ−１）、ＮＯＲ回路５１へ入力するビット群のビット幅をａ（１≦ａ≦ｗ−１）、ｙ（ｉ）とするビット幅をｂ（１≦ｂ≦ｗ−ａ−１）、マスク値とＣＦ（ｊ）との関係を規定するパラメータをｃ（−（ｗ−１）≦ｃ≦ｗ１）とする。このとき、ＮＯＲ回路５１の出力値ｓｆ、ｙ（ｉ）、論理回路の出力値ｒｓ、マスク値ｎｓ、ＣＦは下記式（２６）〜（２９）を満たす。
【００９３】
【数１５】
2007174057.tif 000017
【００９４】
次に、上記式（２６）〜（２９）におけるパラメータａ、ｂ、ｃについて説明する。図９は、補正回路３３において求まるＣＦ出力部４２の出力ＣＦを示すグラフ図である。図９は、パラメータａ、ｂ、ｃを種々変更した場合のＣＦ出力部４２の出力結果（補正曲線）を示している。図９においても、図３と同様、各補正曲線Ｌ４１〜Ｌ１４は、パラメータｘ、ｙ、ｚの値をｃｆ＿ｘ＿ｙ＿ｚとして示す。パラメータａ＝ｗ−ｘ、パラメータｂ＝ｚ、パラメータｃ＝ｌｏｇ２（ｙ）に対応し（（ｘ,ｙ,ｚ）＝（ｗ−ａ,２２−ｃ,ｂ））、補正曲線は基本的には、階段状の曲線となる。先ず、パラメータｘ、すなわち、ＮＯＲ回路５１へ出力するビット幅ａを変更すると、ＣＦ出力部４２の出力は、Ｌ４１、Ｌ４２に示すように、階段の大きさが指数的に変化する。パラメータｘ＝５の階段に比べパラメータｘ＝６の階段は、その全体の幅、高さが略４倍になっている。
【００９５】
また、パラメータｚ、すなわち、ｒｓを求めるビット幅ｂを変化させると、Ｌ４１、Ｌ４４に示すように、各階段の幅（分解能）が変化する。ｚ＝４のＬ４１では４ビット分、ｚ＝２のＬ４３では２ビット分の幅となる。
【００９６】
更に、パラメータｙ、すなわち、ｎｓ（０）〜ｎｓ（３）がＣＦのいずれの値となるかを決めるパラメータｃが変化すると、Ｌ４１、Ｌ４３に示すように、階段の段数自体は変化しないものの、最大値が変化する。すなわち、マスク値シフト量に対応する。ｙ＝４とｙ＝２の高さの差は２ビットとなる。
【００９７】
このように、（ｘ,ｙ,ｚ）＝（ｗ−ａ,２ｃ,ｂ）を種々変化させることで、ＣＦ出力部４２の出力を自在に変化させることができる。本実施の形態においては、このＣＦ出力とＡＭのＯＲを求めて補正後の値とする。
【００９８】
図１０に示す曲線Ｌ５１は、ＡＭの値（補正なし）、曲線Ｌ５２、Ｌ５３は、ＣＦ出力＝２、４とした場合の補正回路の出力ｓを示す。また、図１１に示す曲線Ｌ６１は、ＡＭ＝０とした場合、曲線Ｌ６２、Ｌ６３は、ＡＭ＝２、３４１として、ＣＦ出力４２とのＯＲをとった補正回路の出力ｓを示している。実施の形態１と同様、実際には、ＣＦ出力及びＡＭ値のいずれも変化するため、補正回路の出力ｓは、これらを組み合せた３次元的な変化有する値となる。
【００９９】
図１０に示すように、Ｌ５２は、ＬＳＢの２ビットを１にマスクした場合、Ｌ５３は、ＬＳＢの４ビットを１にマスクした場合を示す。｜Ａｉ−ＡＭ｜の値が小さいほど大きく補正されることがわかる。また、図１１も同様に、｜Ａｉ−ＡＭ｜が大きいほど補正量が小さくなる。
【０１００】
本実施の形態においても、パラメータａ、ｂ、ｃの値を適宜調整することで、回路規模を増大させることなくヤコビアン補正項を正確に算出することができる。特に、本実施の形態においては、加算器も不要とするため、実施の形態１に比して更に回路規模を縮小することができる。
【０１０１】
次に、本発明の効果について説明する。図１２は、本発明の上述の実施の形態１、２の演算回路により算出した結果を、従来技術（Ｍａｘ−Ｌｏｇ−ＭＡＰ）、及びＬｏｇ−ｓｕｍ−ＭＡＰ（ＬＵＴを使用）を使用した場合の結果と比較して示すグラフ図である。実施の形態１、２においても、Ｌｏｇ−ｓｕｍ−ＭＡＰと同等の、Ｍａｘ−Ｌｏｇ−ＭＡＰに比べ遥かに優れたＢＥＲを示している。なお、実施の形態１の演算回路は加算器を要するため実施の形態２の演算回路より回路規模が大きくなるものの、より精度よくＡＭの補正を行なうことができる。
【０１０２】
図１３及び図１４は、それぞれ回路規模及びデータ遅延率についての本発明の効果を示す図である。図１３に示すように、Ｌｏｇ−ｓｕｍ−ＭＡＰ（ＬＵＴを使用）を使用した場合は、回路規模及びデータ遅延率が大きくなるのに比べ、本実施の形態１，２における演算回路では、回路規模、データ遅延率共に飛躍的な改善が見られる。
【０１０３】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。例えば、本実施の形態においても、入力Ｉ１、Ｉ２の最大値を求め、これを補正回路３３にて補正する場合について説明したが、入力Ｉ１、Ｉ２の最小値を求め、これを補正するものとしても同様の効果を奏する。この場合、ＡＣＳ回路２にて最小値を求め、補正回路３３の代わりに当該最小値の補正をする補正回路を設ける。補正回路は、複数ビットから構成されるパスメトリック値に基づきマスク値を算出するマスク値生成部と、マスク値に基づき前記パスメトリック値に対してマスク処理を施すマスク処理部と、最小値とマスク処理部の反転出力との論理積を求める論理回路とから構成すればよい。
【０１０４】
マスク値生成部は、複数ビットから構成されるパスメトリック値の上位０ビット以上からなる第１のビット群全てから１ビットの反転論理和を求める第１の論理回路と、複数ビットから構成されるパスメトリック値の第１のビット群を除いた残りの上位１ビット以上からなる第２のビット群を論理演算して１ビット以上からなる第３のビット群を生成する第２の論理回路と、第１の論理回路の出力と、第３のビット群の各ビットとの論理積を求めた前記マスク値を出力する第３の論理回路とから構成することができる。また、マスク処理部は、マスク値に基づき前記パスメトリック値と同ビットの補正値を生成して反転出力する出力部と、この反転出力とＡＣＳ回路からの最小値との論理積を求める第４の論理回路とから構成することができる。
【０１０５】
この場合、上述の実施の形態と同様、パスメトリック値のビット幅をｗ、パスメトリック値の各ビットをｘ（ｊ）（０≦ｊ≦ｗ−１）、第１のビット群のビット幅をａ（１≦ａ≦ｗ−１）、第２のビット群のビット幅をｂ（１≦ｂ≦ｗ−ａ−１）、マスク値と補正出力との関係を規定するパラメータをｃ（−ｗ≦ｃ≦ｗ）としたとき、第１の論理回路の出力値ｓｆ、第２のビット群ｙ（ｉ）、第２の論理回路の出力値ｒｓ、第３の論理回路の出力値ｎｓ、出力部の出力値ＣＦは下記数式を満たす。このように、最小値を補正する場合には、ＣＦは１の補数、すなわち補正値に対して反転処理が必要となる。
【０１０６】
【数１６】
2007174057.tif 000018
【図面の簡単な説明】
【０１０７】
【図１】本発明の実施の形態１にかかる演算回路を示す図である。
【図２】本発明の実施の形態１にかかる演算回路の一詳細例を示す回路図である。
【図３】実施の形態１における補正回路において求まるＣＦ出力部の出力ＣＦを示すグラフ図である。
【図４】ＣＦ（補正曲線）と実際のヤコビアン補正項（理想曲線）とを対比して示す図である。
【図５】ＣＦを固定値とし、最大値ＡＭを可変とした場合の補正回路の出力ｓを示すグラフ図である。
【図６】ＣＦを可変とし、最大値ＡＭを固定値とした場合の補正回路の出力ｓを示すグラフ図である。
【図７】本発明の実施の形態２にかかる演算回路を示す図である・
【図８】本発明の実施の形態２にかかる演算回路の一詳細例を示す回路図である。
【図９】実施の形態２における補正回路において求まるＣＦ出力部の出力ＣＦを示すグラフ図である。
【図１０】ＡＭの値（補正なし）、ＣＦ出力＝２、４とした場合の補正回路の出力を示すグラフ図である。
【図１１】ＡＭ＝０とした場合、ＡＭ＝２、３４１として、ＣＦ出力４２との論理和をとった場合の補正回路の出力を示すグラフ図である。
【図１２】本発明の上述の実施の形態１、２の演算回路により算出した結果を、従来技術（Ｍａｘ−Ｌｏｇ−ＭＡＰ）、及びＬｏｇ−ｓｕｍ−ＭＡＰ（ＬＵＴを使用）を使用した場合の結果と比較して示すグラフ図である。
【図１３】回路規模についての本発明の効果を示す図である。
【図１４】データ遅延率についての本発明の効果を示す図である。
【図１５】ターボ符号を生成するための一般的な符号化装置を示す図である。
【図１６】代表的なターボ復号の復号装置を示す図である。
【図１７】再帰的畳込み符号を出力する再帰的畳込み符号化器を示す図である。
【図１８】図１７に示す再帰的畳込み符号の状態遷移を示す模式図である
【図１９】トレリス線図を示す図である。
【図２０】トレリス線図を使用した遷移確率の求め方を説明する図である。
【図２１】確率α、β、γから対数尤度比ＬＬＲを算出する方法を説明する図である。
【図２２】従来のＬｏｇ−ＭＡＰにおける確率演算を行なう回路を模式的に示す図である。
【符号の説明】
【０１０８】
1  符号化器
２  ＡＣＳ回路
３  補正回路
１１  加算器
１２  選択器
１３  絶対値回路
２１,５０ａ,５４〜５６  ＮＯＲ回路
２２,２２ａ〜２２ｄ  インバータ
２３,２３ａ〜２３ｄ,５０ｃ,５３,６１〜６７  ＡＮＤ回路
２４,４２  ＣＦ出力部
２５  加算器
３３  補正回路
４１  マスク値生成回路
４２  出力部
４３,５２  ＯＲ回路
５０ｂ  論理回路
５７  インバータ
５８〜６０  反転論理積回路
１０１  符号化装置
１０２  符号化器
１０３  符号化器
１０４  インタリーバ
２０１  復号装置
２０２  第１の復号器
２０３  第２の復号器
２０４  インタリーブメモリ
２０５  デインタリーブメモリ
２０６  判定部
【図１】
2007174057.tif 000022
【図２】
2007174057.tif 000023
【図３】
2007174057.tif 000024
【図４】
2007174057.tif 000025
【図５】
2007174057.tif 000026
【図６】
2007174057.tif 000027
【図７】
2007174057.tif 000028
【図８】
2007174057.tif 000029
【図９】
2007174057.tif 000030
【図１０】
2007174057.tif 000031
【図１１】
2007174057.tif 000032
【図１２】
2007174057.tif 000033
【図１３】
2007174057.tif 000034
【図１４】
2007174057.tif 000035
【図１５】
2007174057.tif 000036
【図１６】
2007174057.tif 000037
【図１７】
2007174057.tif 000038
【図１８】
2007174057.tif 000039
【図１９】
2007174057.tif 000040
【図２０】
2007174057.tif 000041
【図２１】
2007174057.tif 000042
【図２２】
2007174057.tif 000043