(57)【特許請求の範囲】
【請求項１】
ｕin＝０ 又はδin＝０であれば
ｘ＝β2 ｘ，ｓ＝０，ｚ＝ｕin，δout ＝δin
その他の場合は
ｚ＝ｕin，ｘ′＝β2 ｘ＋δin｜ｚ｜2 ，
ｃ＝β2 ｘ／ｘ′，ｓ＝δinｚ／ｘ′，ｘ＝ｘ′，δout ＝ｃδin
の演算を行うバウンダリーセルと、インターナルセルと、ファイナルセルの各セルで演算を繰り返すことで逐次最小二乗アルゴリズムの計算を行うシストリックアレイプロセッサの構成方法において、
前記バウンダリーセルは、ｕin＜min 又はδin＜min 又はβ2 ｘ＋δin｜ｚ｜2 ＜min であれば
ｘ＝β2 ｘ，ｓ＝０，ｚ＝ｕin，δout ＝δin
但しｍｉｎは使用条件に応じて選定されたしきい値
の演算を行うことを特徴とするシストリックアレイプロセッサの構成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は逐次最小二乗アルゴリズム（以下、ＲＬＳアルゴリズムと略記する）の処理を行うためのシストリックアレイプロセッサの構成法に関する。
【０００２】
【従来の技術】
図１に適応フィルタの基本モデルを示す。適応フィルタとはｕ（ｎ）を入力信号、ｙ（ｎ）を出力信号とする可変係数フィルタ１１であり、出力信号ｙ（ｎ）が参照信号ｄ（ｎ）に近づくように係数更新アルゴリズム１２によりフィルタ係数が更新される。ここで、それぞれの信号はシンボルタイミングごとにサンプリングされるので、サンプリングされた後の信号をタイミングインデックスｎを用いて表す。適応フィルタとして図２に示されるようなトランスバーサル形フィルタを考える。遅延量が１タイミング周期の遅延素子Ｄ１，Ｄ２，…，ＤＮ−１が直列に接続され、その一端の遅延素子Ｄ１に入力信号ｕ（ｎ）が入力され、その入力信号ｕ（ｎ）と、各遅延素子Ｄ１，…，ＤＮ−１の各出力ｕ（ｎ−１），…，ｕ（ｎ−Ｎ＋１）とに対し、乗算器Ｍ０，Ｍ１，…，ＭＮ−１でそれぞれタップ係数ｗ0(ｎ），ｗ1(ｎ），…，ｗN-1(n)が乗算され、これら乗算結果が加算器１３で加算されて出力信号ｙ（ｎ）となる。フィルタのタップ係数ｗk とし、入力と出力の関係は以下の式で表される。
【０００３】
ｙ(n) ＝Σk=0 N-1 ｗk (n) ｕ(n−k)                    （１）
ここで、タップ数をＮとして、入力信号とタップ係数のベクトルをそれぞれ以下の式で定義する。
ｕ(n) ＝（ｕ(n) ，ｕ(n−1)，…，ｕ(n−Ｎ＋１))t         （２）
ｗ(n) ＝（ｗ0(n)，ｗ1(n)，…，ｗN-1(n)）t               （３）
添字ｔは転置を表す。このとき、フィルタの入出力関係は以下の式で表される。
【０００４】
ｙ(n) ＝ｗt (n) ｕ(n)                                 （４）
また、誤差信号ｅ（ｎ）は以下の式で表される。
ｅ(n) ＝ｄ(n）−ｗt (n) ｕ(n)                         （５）
この誤差信号の荷重二乗平均を評価関数Ｊ（ｗ）とする。
Ｊ（ｗ）＝Σm=0 n λn-m ｜ｅ(m) ｜2                 （６）
ただし、λは忘却係数である。適応フィルタは評価関数Ｊ（ｗ）を最小とす
るようにフィルタの各タップ係数を更新する。評価関数Ｊ（ｗ）を最小とす
る解ｗ(n) は、
Ｒxx(n) ｗ(n) ＝Ｐ(n)                               （７）
を満足する。ここでＲxx(n) は入力信号の自己相関行列であり、Ｐ(n) は入
力信号と参照信号の相互相関行列である。式（７）は正規方程式と呼ばれている。ここでＲxx(n) が正則であれば、式（７）により最適な係数ベクトルｗ(n
) は以下の式で与えられる。
【０００５】
ｗ(n) ＝Ｒxx-1(n) Ｐ(n)                             （８）
式(8) に基づいてフィルタのタップ係数を更新する方法は評価関数Ｊ（ｗ
）を最小にするという意味で最適であるが、Ｒxx(n) の逆行列演算を行わなけ
ればならないので計算量が多い。そこで、より少ない計算量でフィルタのタップ係数を求めるアルゴリズムがいくつか知られている。その中で特に収束の速いアルゴリズムがＲＬＳアルゴリズムである。ＲＬＳアルゴリズムはフィルタのタップ係数を逐次的に求める。これにより、式（８）の逆行列演算を行う必要がなくなり計算量が少なくなる。具体的に、ＲＬＳアルゴリズムでは以下の演算を行う。
【０００６】
Ｘ(n) ＝（１／λ）Ｒ-1（ｎ−１）ｕ(n)
Ｋ(n) ＝Ｘ(n) ／（１＋ｕH (n) Ｘ(n) ）
α(n) ＝ｙ(n) −ｗH （ｎ−１）ｕ(n)
ｗ(n) ＝ｗ（ｎ−１）＋Ｋ(n) α* (n)
Ｒ-1(n) ＝（１／λ）Ｒ-1（ｎ−１）−Ｋ(n) ＸH (n)   （９）
ここで、添字＊は複素共役を表し、Ｈは共役転置を表す。
【０００７】
ＲＬＳアルゴリズムを用いても適応フィルタのタップ数が多くなると、計算量が増えるために実時間処理が困難となる。そこで、ＲＬＳアルゴリズムの処理をパイプライン並列的に行うことのできるシストリックアレイプロセッサが知られている。シストリックアレイプロセッサとは同一の機能を持つセルを規則的に配置して、ＲＬＳアルゴリズムの計算をパイプライン的に並列に行うものである。原理的には行列のＱＲ分解（与えられた行列の固有値を効率的に求めるために、行列を直交行列と上三角行列に分解すること）とギブンズローテーション（与えられた行列に対して、その行列の値により導出される直交行列を用いて、与えられた行列の上三角行列化を行うこと）を用いることにより、処理のパイプライン並列化を可能としている。シストリックアレイプロセッサでは、各セルにおいて単純な計算を行い、計算結果を隣接セルに渡すということを繰り返すことによりＲＬＳアルゴリズムの計算が行われる。従来のシストリックアレイプロセッサの構成を図３Ａに示す。ここでフィルタのタップ数は３としている。シストリックアレイプロセッサにはバウンダリーセル（以下、boundary cell)ＢＣ（図３Ｂ）とインターナルセル（以下、internal cell)ＩＣ（図３Ｃ）とファイナルセル（以下、final cell) ＦＣ（図３Ｄ）の３種類のセルがあり、それぞれのセルにおいて図３に示される演算が行われる。delay unitはデータの転送を１タイミング遅らせる働きを持つ。ｕ(n) はフィルタの各タップへの入力信号を表し、ｄ（ｎ）は参照信号を表す。
【０００８】
タップ数のバウンダリーセルＢＣ１，ＢＣ２，ＢＣ３が順次、遅延量が１タイミング周期の遅延素子Ｄを介して直列に接続され、バウンダリーセルＢＣ３の出力側は遅延素子Ｄ３を介してファイナルセルＦＣに接続される。バウンダリーセルＢＣ１の他方の出力側にインターナルセルＩＣ１１，ＩＣ１２，ＩＣ１３が順次接続され、バウンダリーセルＢＣ２の他方の出力側にインターナルセルＩＣ２２，ＩＣ２３が順次接続され、バウンダリーセルＢＣ３の他方の出力側にインターナルセルＩＣ３３が接続される。インターナルセルＩＣ１１，ＩＣ１２，ＩＣ１３の各他方の出力側はバウンダリーセルＢＣ２、インターナルセルＩＣ２２，ＩＣ２３とそれぞれ接続され、インターナルセルＩＣ２２，ＩＣ２３の各他方の出力側はバウンダリーセルＢＣ３、インターナルセルＩＣ３３に接続され、インターナルセルＩＣ３３の他方の出力側はファイナルセルＦＣに接続される。つまりこれらセルＢＣ，ＩＣ，ＦＣは三角形の行列に配されている。
【０００９】
各バウンダリーセルＢＣには遅延素子Ｄを介しての前段のバウンダリーセルよりの入力δinと、そのバウダリーセルＢＣに接続されているインターナルセルＩＣからの入力ｕinとが与えられ、ｕin＝０もしくはδin＝０の時、次の計算を
行う。
ｘ＝β2 ｘ，ｓ＝０，ｚ＝ｕin，δout ＝δin                  （10）
ｕin≠０かつδin≠０の時、以下の計算を行う。
【００１０】
ｚ＝ｕin，ｘ′＝β2 ｘ＋δin｜ｚ｜2 ，ｃ＝β2 ｘ／ｘ′，ｓ＝δinｚ／ｘ′，ｘ＝ｘ′，δout ＝ｃδin                                  （11）
ここで、ｘはバウンダリーセル自身が持つ値であり正の実数となる。またβはＲＬＳアルゴリズムにおける忘却係数λの平方根である。そのバウンダリーセルＢＣにおいて計算されたｓ，ｚは行方向の隣接するインターナルセルＩＣに渡され、δinを用いて計算されたδout は遅延素子を介して１タイミング遅延されて次のバウンダリーセルに渡される。式（10）、（11）において、ｘ，β，δin，δout ，ｃは正の実数でありｓ，ｚ，ｕinは複素数となる。
【００１１】
各インターナルセルにおいては行方向からの入力ｓ，ｚと列方向からの入力ｕinとにより以下の計算を行う。
ｕout ＝ｕin−ｚｘ，ｘ＝ｘ＋ｓ* ｕout                       （12）
ｕout は列方向に出力され、ｓ，ｚはそのまま行方向に出力され、セルの持つ値ｘが更新される。この時、ｘの値は複素数となる。
【００１２】
最後にファイナルセルＦＣにおいてこれに接続されたインターナルセルＩＣ３３からのｕinと直前のバウンダリーセルＢＣ３よりの遅延素子Ｄ３を介して入力されるδinとをかけることにより誤差信号ｅ（ｎ）が導出される。
ｅ（ｎ）＝ｕinδin                                          （13）
図３Ａに示すように初段のバウンダリーセルＢＣ１には入力信号ｕ（１），ｕ（２），ｕ（３），…がタイミングごとに順次入力され、インターナルセルＩＣ１１にはバウンダリーセルＢＣ１に対し、１タイミング遅れて０，ｕ（１），ｕ（２），…が順次入力され、インターナルセルＩＣ１２には、バウンダリーセルＢＣ１に対し、２タイミング遅れて０，０，ｕ（１），ｕ（２），…が順次入力され、インターナルセルＩＣ１３にはバウンダリーセルＢＣ１に対し、３タイミング遅れて参照信号ｄ（１），ｄ（２），ｄ（３），…が順次入力される。
【００１３】
バウンダリーセル・インターナルセルで以上の計算を行い、隣接セルにその結果を渡して、再び各セルで計算を行うという処理を繰り返すことにより、全体としてＲＬＳアルゴリズムが処理され、誤差信号及びタップ係数を得ることができる。
上記、ＲＬＳアルゴリズムの処理を行うシストリックアレイプロセッサをＡＳＩＣ（Application Specific IC ）などのプログラマブルデバイスを用いて設計する場合、内部で行われる演算として、浮動小数点演算ではなく固定小数点演算を用いると動作速度が速い。しかし、固定小数点演算を行う場合、桁あふれや丸め誤差等の問題が生じてしまう。スケーリング（入力される値を、あらかじめ１に正規化すること）を行うことにより乗算による桁あふれの問題は回避できるが、除算や和差算による桁あふれの問題が残る。そこで、各演算毎に最適なビットシフト量を求めてビットシフトを行う擬似浮動小数点演算を行うことにより、桁あふれの問題はなくなるが動作速度が遅くなる。動作速度の点では、固定小数点演算が最も速く、次に擬似浮動小数点演算となり、浮動小数点演算が最も遅い。
【００１４】
シストリックアレイプロセッサにおいて固定小数点演算を行う場合、スケーリングを用いても除算と和差算の影響により桁あふれの問題が生じる可能性がある。式（11）、（12）においては和算の影響により桁あふれが生じる可能性がある。また、式（11）においてβ2 ｘ≪δin｜ｚ｜2 かつ｜ｚ｜≪１の時に、ｘ′≒δin｜ｚ｜2 、よって｜ｓ｜＝１／｜ｚ｜となってしまうので、ｓの値が大きくなり桁あふれを生じる可能性がある。桁あふれが生じてしまうと、ＲＬＳアルゴリズムの処理が正しく行われない。
【００１５】
【発明が解決しようとする課題】
この発明は、シストリックアレイプロセッサをＡＳＩＣ（Application Specific IC ）などのプログラマブルデバイスにより固定小数点演算を用いて設計する場合、桁あふれ等の影響により生ずる誤差を小さくすることを目的とする。
【００１６】
【課題を解決するための手段】
この発明においては、固定小数点演算を用い、バウンダリーセルの演算の際に、しきい値を設け、入力のいずれかがしきい値以下である場合と他の場合とに応じて実行する演算を分ける。
この構成により、固定小数点演算により得られる結果の誤差を小さくして、浮動小数点演算により得られる結果の誤差に近ずける。
【００１７】
【発明の実施の形態】
この発明の実施例においても、図３に示した従来と同様なＲＬＳアルゴリズムの処理を行うシストリックアレイプロセッサを構成するが、この発明ではバウンダリーセルの演算のための条件文に小さな値のしきい値ｍｉｎを設けて以下の計算を行う。
【００１８】
ｕin＜min 又はδin＜min 又はβ2 ｘ＋δin｜ｚ｜2 ＜min であれば
｛ｘ＝β2 ｘ，ｓ＝０，ｚ＝ｕin，δout ＝δin｝
を演算し、その他の場合は
｛ｚ＝ｕin，ｘ′＝β2 ｘ＋δin｜ｚ｜2 ，
ｃ＝β2 ｘ／ｘ′，ｓ＝δinｚ／ｘ′，ｘ＝ｘ′，
δout ＝ｃδin｝                                        （14）
を演算する。これにより、β2 ｘ≪δin｜ｚ｜2 かつ｜ｚ｜≪１であっても、あるしきい値（min)の値より入力ｕinが小さければ、ｕin＜ｍｉｎとなるのでｓ＝０となり、除算の影響によりｓの値が桁あふれを生じるという問題を回避することができる。またｃやｓの演算において（１／ｘ′）を演算するため、ｘ′が小さな値となったり、βは忘却係数λの平方根であり、従ってβ2 は著しく小さな値となり、かつδinが著しく小さな値であれば、ｘ′が小さな値となり、（１／ｘ′）の演算で桁あふれの問題が生じるが、この発明ではδin＜ｍｉｎ又はｘ′＜ｍｉｎの場合は、ｃやｓの演算は行わず、つまり１／ｘ′の演算は行なわないため、１／ｘ′が大きな値となって桁あふれが生じる問題は生じない。
【００１９】
しきい値ｍｉｎの値は入力信号の変動状態や、演算ビット数などによって好ましい値が異なる。よって予めシミュレーションにより各種条件と対応した好ましいしきい値を求めておき、使用条件に適したしきい値ｍｉｎを選定すればよい。これらにより、桁あふれの影響により生じる誤差を小さくすることができる。
【００２０】
【発明の効果】
この発明により、シストリックアレイプロセッサをＡＳＩＣ（Application Specific IC ）などのプログラマブルデバイスにより固定小数点演算を用いて設計する場合、桁あふれ等の影響により生ずる誤差を小さくすることができる。その結果、浮動小数点演算により得られる結果の誤差に、固定小数点演算により得られる結果の誤差を近づけることができ、誤差を小さくすることができる。
【００２１】
ここで、一例として推定するパラメータ数１６におけるこの発明の効果について示す。図４は、ある適当な入力信号ｕ(n) と参照信号ｄ(n) を用いて、適応フィルタのタップ数１６とした場合の、式（９）を用いて浮動小数点演算により導出したタップ係数と、シストリックアレイプロセッサを用いて導出したタップ係数との誤差を表している。誤差の単位は％である。boundary cell におけるしきい値を設定しない従来のシストリックアレイプロセッサにおいて、浮動小数点演算を用いて導出したタップ係数と、式（９）を用いて浮動小数点演算により導出したタップ係数との誤差は殆どない。これは、式（９）における計算と、シストリックアレイプロセッサにおいて行われる計算が数学的に等価なためである。次に、boundary cell においてしきい値（ここでは、一例としてしきい値を０．０００１とした。）の設定を行う式（14）の方法を用いて、浮動小数点演算によりタップ係数を導出した場合、若干の誤差が生じている。これは、しきい値を設定することにより、式（９）の計算とシストリックアレイプロセッサ内部で行われる演算が数学的に等価でなくなったためである。次に、固定小数点演算（整数部１０ビット、小数部２２ビット）を行い、boundary cell 内部ではしきい値の設定を行わない式（10）、（11）の演算を行った場合は、大きな誤差を生じている。これは、桁あふれ等の影響のためと考えられる。最後に、固定小数点演算（整数部１０ビット、小数部２２ビット）を行い、boundary cell 内部における演算において条件文にしきい値を設定したこの発明の場合は、しきい値の設定を行わない場合と比較して誤差が大幅に減少している。これは、β2 ｘ≪δin｜ｚ｜2 かつ｜ｚ｜≪１の時に除算の影響によりｓの値が桁あふれを生じるという問題を回避することができているためである。したがって、この発明により、固定小数点演算を用いた場合の桁あふれ等の影響により生じる誤差の影響を小さくできる。
【図面の簡単な説明】
【図１】適応フィルタの基本モデルを表す図。
【図２】トランスバーサル形フィルタを表す図。
【図３】ＡはＲＬＳアルゴリズムの処理を行う従来のシストリックアレイプロセッサの構成を示す図、Ｂ、Ｃ、Ｄはそれぞれboundary cell とinternal cell とfinal cellで行われる計算を示す図である。
【図４】推定するパラメータ数１６として、従来のＲＬＳアルゴリズムの数式により浮動小数点演算を用いて導出したタップ係数と、シストリックアレイプロセッサを用いて導出したタップ係数との誤差を表し、浮動小数点演算及び固定小数点演算のそれぞれについて、boundary cell におけるしきい値の設定を行う場合と行わない場合の４通りについて誤差を示す図。
【図１】
0003784990.tif 000002
【図２】
0003784990.tif 000003
【図３】
0003784990.tif 000004
【図４】
0003784990.tif 000005