(57)【特許請求の範囲】
【請求項１】
入力データａと入力データｂを変数として関数ｌｏｇ（ｅa＋ｅb）を近似演算する近似演算装置において、
前記入力データａと前記入力データｂのうち値が大きい方を選択してｍａｘ（ａ、ｂ）のデータを出力する選択手段と、
前記入力データａと前記入力データｂの差の絶対値のデータから、関数ｌｏｇ（１＋ｅ-|a-b|）を折れ線近似する傾きが２のｎ乗（ｎは整数）で表される直線の傾きに対応したｍビット（ｍは自然数）のデータとその直線の切片を示すデータとを出力するデコード手段と、
前記入力データａと前記入力データｂの差の絶対値のデータを、前記デコード手段からのｍビットのデータでｎビットシフトするシフト手段と、
このシフト手段によってシフトされたデータと前記切片を示すデータとから関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータを出力する手段と、
前記選択手段から出力されるｍａｘ（ａ、ｂ）のデータと前記関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータとを加算する加算手段と、を備えたことを特徴とする近似演算装置。
【請求項２】
前記入力データａと前記入力データｂの差を演算して差のデータを出力する減算手段を備え、前記選択手段は、前記差のデータに基づいて前記選択を行い、前記デコード手段および前記シフト手段は、前記差の絶対値のデータに基づいてそれぞれの処理を行うことを特徴とする請求項１に記載の近似演算装置。
【請求項３】
ＭＡＰ復号における各演算を指数部のみで行うlog#BCJRアルゴリズムを用いてＭＡＰ復号を行うＭＡＰ復号装置において、
前方繰り返し演算による状態確率の演算および後方繰り返し演算による状態確率の演算を、入力データａと入力データｂを変数として関数ｌｏｇ（ｅa＋ｅb）の近似演算にて行うものであって、前記関数ｌｏｇ（ｅa＋ｅb）の近似演算のために、前記入力データａと前記入力データｂのうち値が大きい方を選択してｍａｘ（ａ、ｂ）のデータを出力する選択手段と、
前記入力データａと前記入力データｂの差の絶対値のデータから、関数ｌｏｇ（１＋ｅ-|a-b|）を折れ線近似する傾きが２のｎ乗（ｎは整数）で表される直線の傾きに対応したｍビット（ｍは自然数）のデータとその直線の切片を示すデータとを出力するデコード手段と、
前記入力データａと前記入力データｂの差の絶対値のデータを、前記デコード手段からのｍビットのデータでｎビットシフトするシフト手段と、
このシフト手段によってシフトされたデータと前記切片を示すデータとから関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータを出力する手段と、
前記選択手段から出力されるｍａｘ（ａ、ｂ）のデータと前記関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータとを加算する加算手段と、を備えたことを特徴とするＭＡＰ復号装置。
【請求項４】
前記入力データａと前記入力データｂの差を演算して差のデータを出力する減算手段を備え、前記選択手段は、前記差のデータに基づいて前記選択を行い、前記デコード手段および前記シフト手段は、前記差の絶対値のデータに基づいてそれぞれの処理を行うことを特徴とする請求項３に記載のＭＡＰ復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、非線形関数の近似演算装置、関数ｌｏｇ（１＋ｅ-x）の近似演算装置、関数ｌｏｇ（ｅa＋ｅb）の近似演算装置、およびＭＡＰ復号装置に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】
従来、畳込み符号とインタリーブとを組合せたターボ符号に変換して送信された符号化データを受信し、その誤りを訂正して復号を行うターボデコーダが提案されている。
【０００３】
このターボデコーダの構成を図８に示す。このターボデコーダは、２つの軟出力復号器１０１、１０２と、２つのインターリーバ１０３、１０４と、デインターリーバ１０５と、硬判定器１０６から構成された公知のものである。ターボデコーダの構成要素である軟出力復号器１０１、１０２の復号としては、ＭＡＰ（最大事後確率：Maximum A Posteriori Probabi1ity）復号が用いられる。
【０００４】
図９に、ＭＡＰ復号の演算処理を示す。入力データが１、０のいずれであるかの確率ＰＤＦ（受信信号の確率密度関数：probability density function）を演算するステップ２０１、トレリスの各枝（ブランチ）の確率（状態遷移確率）γを演算するステップ２０２、トレリスをデータの先頭から演算して個々のビットの各状態の確率（前方繰り返し演算による状態確率）αを演算するステップ２０３、トレリスをデータの最後尾から演算してαと同様に個々のビットの各状態の確率（後方繰り返し演算による状態確率）βを演算するステップ２０４、先に求めたγ、α、βからトレリスの各ビットが１、０のいずれであるかの確率（情報シンボルの尤度）λを演算するステップ２０５、λで得られた確率を尤度としてフィードバックするために事前尤度（ＬＤＫ）を演算するステップ２０６、およびλで得られた確率を硬判定して入力データを復号するステップ２０７からなる。
【０００５】
図１０に、このＭＡＰ復号の各演算処理を演算器で行う場合のブロック構成を示す。図９に示したＰＤＦ、γ、α、β、λ、ＬＤＫは、式を簡略化すれば、図１０に示す演算式を各々の演算器で演算していることになる。このようなＭＡＰ復号の演算式をそのままハードウェアあるいはソフトウェアで実現すると、各中間結果（データ）のビット数が大きくなり、非実現的なものとなってしまう。
【０００６】
そこで、ＭＡＰ復号を、より小さな演算及び小型な回路で実現するために、様々なアルゴリズムが提案されている。その一例として、log#BCJRアルゴリズム（S. Bebedetto et. al "Soft-output decoding of parallel concatenated convolutional codes" , ICC 96）は、演算量を減らしながら復号能力を維持できるものとして広く用いられている。
【０００７】
log#BCJRアルゴリズムでは、図１０に示した各演算を指数部のみで演算する。具体的には、対数をとることにより、ＰＤＦは、−（ｘ−１）2／２σで求められる（ｘは入力テータ、σは分散値を示す）。また、ｐｄｆ・ｐｄｆ・ｐｒｂは指数部を示しているので、γはｐｄｆ＋ｐｄｆ＋ｐｒｂのように加算で求められる、λは（分子−分母）の減算で求められる。
【０００８】
しかし、α、βに関しては、新たにｌｏｇ（ｅa＋ｅb）の演算が生じてしまう。すなわち、αは、α・γ＋α・γの演算で求められるが、具体的には、１つ前の２つのトレリスの状態α1、α2と、α1、α2からの枝γ1、γ2によって、α1・γ1＋α2・γ2の演算式で求められる。ここで、α・γ＋α・γの各項は、指数関数で表されているため、α・γ＋α・γの指数部は、ｌｏｇ（ｅa＋ｅb）の演算で求められる。同様に、βは、β・γ＋β・γの演算で求められるが、具体的には、１つ前の２つのトレリスの状態β1、β2と、β1、β2からの枝γ3、γ4によって、β1・γ3＋β2・γ4の演算式で求められる。ここで、β・γ＋β・γの各項は、指数関数で表されているため、β・γ＋β・γの指数部は、ｌｏｇ（ｅa＋ｅb）の演算で求められる。
【０００９】
そこで、log#BCJRアルゴリズムでは、ｌｏｇ（ｅa＋ｅb）を数式１に変形して演算することで、演算を簡略化している。
【００１０】
【数１】
ｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）
すなわち、ａ＞ｂの場合、ｌｏｇ（ｅa＋ｅb）は、ｌｏｇｅa（１＋ｅbーa）＝ａ＋ｌｏｇ（１＋ｅbーa）と変形され、ｂ＞ａの場合、ｌｏｇ（ｅa＋ｅb）は、ｌｏｇｅb（１＋ｅa-b）＝ｂ＋ｌｏｇ（１＋ｅa-b）と変形される。このことから、ｌｏｇ（ｅa＋ｅb）は、数式１のように変形することができる。
【００１１】
ここで、数式１の第２項ｌｏｇ（１＋ｅ-|a-b|）をどのようにして求めるかが問題となる。２０００年電子情報通信学会総合大会の「Ｗ−ＣＤＭＡターボ復号器のＶＬＳＩ化と評価」（Ｂ−５−２６）では、テーブルルックアップによりｌｏｇ（１＋ｅ-|a-b|）を求めることが提案されている。
【００１２】
図１１に、テーブルルックアップを用いて、数式１を演算する場合の構成を示す。２つの入力データａ、ｂが減算器３０１に入力され、この減算器３０１でａ、ｂの差（ａ−ｂ）が求められる。また、入力データａ、ｂは選択器３０２に入力され、この選択器３０２で、減算器３０１から出力される差（ａ−ｂ）の符号に応じてｍａｘ（ａ、ｂ）が求められる。また、減算器３０１から出力される差（ａ−ｂ）は、テーブルルックアップ３０３に入力され、このテーブルルックアップ３０３で、差（ａ−ｂ）に応じたｌｏｇ（１＋ｅ-|a-b|）の値がテーブルから求められる。そして、加算器３０４で、ｍａｘ（ａ、ｂ）とｌｏｇ（１＋ｅ-|a-b|）の値が加算され、数式１の出力ｙが得られる。
【００１３】
しかし、このように数式１の第２項ｌｏｇ（１＋ｅ-|a-b|）をテーブルルックアップ３０３で実現した場合、復号能力を維持するためには、テーブルを詳細に用意する必要があり、回路規模あるいは演算量の削減を妨げる要因となる。
【００１４】
また、一般に、ｌｏｇ（１＋ｅーx）とか、その他の非線形関数をデジタル処理で求める場合にも、テーブルルックアップを用いることが考えられるが、テーブルルックアップを用いたのでは、テーブルを詳細に用意する必要があり、回路規模ないし演算量の削減を妨げる要因となる。
【００１５】
本発明は上記問題に鑑みたもので、log#BCJRアルゴリズムにおける数式１の第２項を、より小型な回路あるいは少ない演算量で演算できるようにすることを第１の目的とする。
【００１６】
また、ｌｏｇ（１＋ｅーx）、およびその他の非線形関数において、より小型な回路あるいは少ない演算量で演算できるようにすることを第２の目的とする。
【００２１】
【課題を解決するための手段】
上記目的を達成するため、請求項１に記載の発明では、入力データａと入力データｂを変数として関数ｌｏｇ（ｅa＋ｅb）を近似演算する近似演算装置において、前記入力データａと前記入力データｂのうち値が大きい方を選択してｍａｘ（ａ、ｂ）のデータを出力する選択手段と、前記入力データａと前記入力データｂの差の絶対値のデータから、関数ｌｏｇ（１＋ｅ-|a-b|）を折れ線近似する傾きが２のｎ乗（ｎは整数）で表される直線の傾きに対応したｍビット（ｍは自然数）のデータとその直線の切片を示すデータとを出力するデコード手段と、前記入力データａと前記入力データｂの差の絶対値のデータを、前記デコード手段からのｍビットのデータでｎビットシフトするシフト手段と、このシフト手段によってシフトされたデータと前記切片を示すデータとから関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータを出力する手段と、前記選択手段から出力されるｍａｘ（ａ、ｂ）のデータと前記関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータとを加算する加算手段とを備えたことを特徴としている。
【００２２】
このことにより、関数ｌｏｇ（ｅa＋ｅb）を、より小型な回路あるいは少ない演算量で演算することができる。
【００２３】
この場合、請求項２に記載の発明のように、入力データａと前記入力データｂの差を演算して差のデータを出力する減算手段を備え、前記選択手段が、前記差のデータに基づいて前記選択を行い、前記デコード手段および前記シフト手段が、前記差の絶対値のデータに基づいてそれぞれの処理を行うようにすることができる。
【００２４】
請求項３に記載の発明では、ＭＡＰ復号における各演算を指数部のみで行うlog#BCJRアルゴリズムを用いてＭＡＰ復号を行うＭＡＰ復号装置において、前方繰り返し演算による状態確率の演算および後方繰り返し演算による状態確率の演算を、入力データａと入力データｂを変数として関数ｌｏｇ（ｅa＋ｅb）の近似演算にて行うものであって、前記関数ｌｏｇ（ｅa＋ｅb）の近似演算のために、前記入力データａと前記入力データｂのうち値が大きい方を選択してｍａｘ（ａ、ｂ）のデータを出力する選択手段と、前記入力データａと前記入力データｂの差の絶対値のデータから、関数ｌｏｇ（１＋ｅ-|a-b|）を折れ線近似する傾きが２のｎ乗（ｎは整数）で表される直線の傾きに対応したｍビット（ｍは自然数）のデータとその直線の切片を示すデータとを出力するデコード手段と、前記入力データａと前記入力データｂの差の絶対値のデータを、前記デコード手段からのｍビットのデータでｎビットシフトするシフト手段と、このシフト手段によってシフトされたデータと前記切片を示すデータとから関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータを出力する手段と、前記選択手段から出力されるｍａｘ（ａ、ｂ）のデータと前記関数ｌｏｇ（１＋ｅ-|a-b|）を示すデータとを加算する加算手段とを備えたことを特徴としている。
【００２５】
このことにより、log#BCJRアルゴリズムを用いたＭＡＰ復号処理において、ｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）の演算を、より小型な回路あるいは少ない演算量で演算することができる。
【００２６】
この場合、請求項４に記載の発明のように、入力データａと前記入力データｂの差を演算して差のデータを出力する減算手段を備え、前記選択手段が、前記差のデータに基づいて前記選択を行い、前記デコード手段および前記シフト手段が、前記差の絶対値のデータに基づいてそれぞれの処理を行うようにすることができる。
【００２７】
なお、上記した関数ｌｏｇ（ｅa＋ｅb）の近似は、傾きが２のｎ乗（ｎは整数）の直線を隣接する直線との交点を区切りとしてつなぎ合わせ、関数との誤差を最小とするように折れ線グラフで近似することの他、傾きが２のｎ乗（ｎは整数）の接線を隣接する接線との交点を区切りとしてつなぎ合わせ、折れ線グラフで近似するようにして求めることができる。
【００２８】
【発明の実施の形態】
（第１実施形態）
図１に、非線形関数を近似演算する装置の構成を示す。この装置は、図２に示すような非線形関数を直線近似して、入力データｘに対する出力データｙを求めるものである。
【００２９】
ここで、直線近似するための各直線は、図２に示す非線形関数において、傾きが４、２、１、０、０．５、０．２５のような２のｎ乗（ｎは整数）となる各直線を図のように沿わせることにより求められる。隣り合った直線の交点を区切りとして、各直線を図のように折れ線グラフとしてつなぐことで非線形関数を近似する。この場合、非線形関数のグラフ上の任意のサンプル点における非線形関数のｙ座標と、切片を任意に変更できる当該直線上のｙ座標との差分を誤差として、この誤差を最小とするように切片が決定される。このサンプル点の数を増やせば、より精度の高い近似が可能となる。
【００３０】
このようにして求められた直線の傾きＡと切片Ｂから、出力ｙは、ｙ＝Ａ・ｘ＋Ｂで求められる。
【００３１】
デジタルの入力データｘは、デコーダ１１に入力される。デコーダ１１は、入力データｘから、上記のようにして求めておいた直線の傾きＡを示す２のｎ乗（ｎは整数）の直線の傾きに対応したｍビット（ｍは自然数）のデータと切片Ｂのデータをそれぞれ出力する。シフター１２は、入力データｘをｍビットのデータでｎビットだけシフトして、Ａ・ｘのデータを出力する。そして、加算器１３にて、Ａ・ｘのデータと切片Ｂのデータが加算され、出力データｙが得られる。
【００３２】
なお、上記した例では、非線形関数のグラフ上の任意のサンプル点における非線形関数のｙ座標と、切片を任意に変更できる当該直線上のｙ座標との差分を誤差として、この誤差を最小とするように切片を決定するものを示したが、図３に示すように、非線形関数に対し傾きが４、２、１、０、０．５、０．２５のような２のｎ乗（ｎは整数）となる各接線を、図のように隣り合った直線の交点を区切りとして、各直線を折れ線グラフとしてつなぐことで非線形関数を近似するようにしてもよい。具体的には、各接線は、非線形関数を微分し、この微分式が各傾き（４、２、１、０、０．５、０．２５）になるようにして求められる。
【００３３】
従来のテーブルルックアップによる近似では、図４に示すように、非線形関数を図２、図３と同程度に近似するためには、非常に沢山の参照点を必要とする。このような参照点の増加は、回路規模の増加につながるという問題がある。また、参照点を減らし、参照点間を直線で近似する方式を用いた場合には、精度的には図１と同等に成り得るが、各参照点間を結ぶ直線の傾きは任意であるため、乗算及び除算を必要とし、回路規模及び演算量が増大するという問題がある。図２、図３に示す近似によれば、各直線の区切りを少なくでき、また各直線の傾きが２のｎ乗（ｎは整数）で表されるため、ビットシフトで演算でき、回路規模及び演算量を削減することができる。
【００３４】
また、非線形関数として、ｌｏｇ（１＋ｅ-x）とした場合にも、上記と同様の直線近似にて、入力データｘに対する出力データｙを得ることができる。この場合、図５に、図２と同様、傾きが２のｎ乗（但し、ｎは負の整数で、−０．５、−０．２５、−０．１２５、−０．０６２５、−０．０３１２５…）となる直線と非線形関数との誤差を最小とするように切片を決定するものを示し、図６に、図３と同様、非線形関数に対し傾きが２のｎ乗（但し、ｎは負の整数で、−０．５、−０．２５、−０．１２５、−０．０６２５、−０．０３１２５…）となる各接線を用い、各直線を折れ線グラフとしてつなぐことで非線形関数を近似するものを示す。
【００３５】
このように非線形関数としてｌｏｇ（１＋ｅ-x）とした場合も、図１に示す構成によって、入力データｘに対する出力データｙを得ることができる。但し、この例では、傾きが２のｎ乗で指数部ｎが必ず負の整数になる。このため、デコーダ１１が、傾きが２のｎ乗の指数部ｎを正の整数としたｍビットのデータを出力するようにすれば、シフター１２は入力データｘをｎビットだけシフトし、それを加算器１３の代わりに用いた減算器にて切片Ｂのデータから減算するようにすれば、ｌｏｇ（１＋ｅ-x）の値を示すデータを得ることができる。
（第２実施形態）
図７に、ＭＡＰ復号におけるα演算を行う演算器、β演算を行う演算器のぞれぞれにおいて、log#BCJRアルゴリズムに従い、数式１に示すｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）の演算を行う構成を示す。
【００３６】
図７に示す構成において、２つのデジタルの入力データａ、ｂが減算器２１に入力され、この減算器２１でａ、ｂの差（ａ−ｂ）が求められる。また、入力データａ、ｂは選択器２２に入力され、この選択器２２で、減算器２１から出力される差（ａ−ｂ）の符号に応じてｍａｘ（ａ、ｂ）が求められる。また、減算器２１から出力される差（ａ−ｂ）は、デコーダ２３に入力される。
【００３７】
ここで、ｌｏｇ（１＋ｅ-|a-b|）は、｜ａ−ｂ｜をｘとすれば、図５、図６に示す実施形態と同じ形になるため、まず、絶対値回路（絶対値検出手段）２７で、減算器２１から出力される差（ａ−ｂ）の絶対値を求める。そして、（ａ−ｂ）の絶対値を入力データｘとして、デコーダ２３およびシフター２４のそれぞれの処理が行われる。すなわち、デコーダ２３は、入力データｘを用いて、直線の傾きＡを示す２のｎ乗（ｎは負の整数）の指数部ｎを正の整数としたｍビットのデータと切片Ｂのデータをそれぞれ出力する。シフター２４は、入力データｘをｎビットだけシフトして、Ａ・ｘのデータを出力する。
【００３８】
そして、減算器２５にて、切片ＢのデータからＡ・ｘのデータが減算される。この減算結果は、ｌｏｇ（１＋ｅ-|a-b|）の値を示す。
【００３９】
最後に、加算器２６で、ｌｏｇ（１＋ｅ-|a-b|）の値と選択器２２から出力されるｍａｘ（ａ、ｂ）が加算され、ｙ＝ｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）が出力される。
【００４０】
上記した構成により、log#BCJRアルゴリズムにおけるｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）の演算を行うことができる。このような演算を用いるＭＡＰ復号器は、複数の演算器により図１０に示すようなハードウェアで実現される他、図９に示すようなソフトウェアで実現することができる。ソフトウェアで実現した場合、上記した処理は、図９の演算α、演算βの処理（ステップ２０３、２０４）で用いられる。また、このようなＭＡＰ復号器は、例えば図８に示すターボデコーダの軟出力復号器１０１、１０２として用いられる。
【００４１】
また、α、β以外にλについてもｌｏｇ（ｅa＋ｅb）の演算が必要であれば、上記と同様の演算処理を行うようにしてもよい。
【図面の簡単な説明】
【図１】非線形関数を近似演算する装置の構成を示す図である。
【図２】非線形関数を直線近似する方法を説明するための図である。
【図３】非線形関数を直線近似する他の方法を説明するための図である。
【図４】従来のテーブルルックアップによる近似を説明するための図である。
【図５】ｌｏｇ（１＋ｅ-x）を直線近似する方法を説明するための図である。
【図６】ｌｏｇ（１＋ｅ-x）を直線近似する他の方法を説明するための図である。
【図７】  log#BCJRアルゴリズムを用いたＭＡＰ復号処理において、ｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）の演算を行う装置の構成を示す図である。
【図８】ターボデコーダの構成を示す図である。
【図９】ＭＡＰ復号の演算処理を示す図である。
【図１０】ＭＡＰ復号の各演算処理を演算器で行う場合のブロック構成を示す図である。
【図１１】テーブルルックアップを用いて、ｍａｘ（ａ、ｂ）＋ｌｏｇ（１＋ｅ-|a-b|）の演算を行う装置の構成を示す図である。
【符号の説明】
１１…デコーダ、１２…シフター、１３…加算器、２１…減算器、
２２…選択器、２３…デコーダ、２４…シフター、２５…減算器、
２６…加算器、２７…絶対値回路。
【図１】
0004269520.tif 000002
【図２】
0004269520.tif 000003
【図３】
0004269520.tif 000004
【図４】
0004269520.tif 000005
【図５】
0004269520.tif 000006
【図６】
0004269520.tif 000007
【図７】
0004269520.tif 000008
【図８】
0004269520.tif 000009
【図９】
0004269520.tif 000010
【図１０】
0004269520.tif 000011
【図１１】
0004269520.tif 000012