(57)【要約】【課題】  少ない演算量で相互相関値を算出する。【解決手段】  本発明は、２種類の離散的時間信号Ｘ（ｎ），Ｙ（ｎ）の、両信号間に時間差ｋがある場合の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）を算出する相関演算器に関する。そして、離散的時間信号Ｘ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｘｂｉｎ（ｎ）に変換する第１の２値符号化手段と、離散的時間信号Ｙ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｙｂｉｎ（ｎ）に変換する第２の２値符号化手段と、第１及び第２の２値符号化手段からの１ビット信号Ｘｂｉｎ（ｎ）及びＹｂｉｎ（ｎ）の相互相関値を算出し、上述の相互相関係数Ｃｏｒｒ（ｎ，ｋ）として出力する演算手段とを有する。【選択図】      図１
2008158855.tif 000002
【特許請求の範囲】
【請求項１】
２種類の離散的時間信号Ｘ（ｎ），Ｙ（ｎ）の、両信号間に時間差ｋがある場合の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）を算出する相関演算器において、
離散的時間信号Ｘ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｘｂｉｎ（ｎ）に変換する第１の２値符号化手段と、
離散的時間信号Ｙ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｙｂｉｎ（ｎ）に変換する第２の２値符号化手段と、
上記第１及び第２の２値符号化手段からの１ビット信号Ｘｂｉｎ（ｎ）及びＹｂｉｎ（ｎ）に基づき、（Ａ）式に従う演算を実行し、その演算結果を上記相互相関係数Ｃｏｒｒ（ｎ，ｋ）として出力する演算手段と
を有することを特徴とする相関演算器。
【数１】
2008158855.tif 000013
但し、Ｎは相関の算出に用いられる各信号のサンプル数であり、＋を丸で囲んだ記号は排他的論理和演算を表している。
【請求項２】
上記演算手段は、
上記第１の２値符号化手段からの１ビット信号Ｘｂｉｎ（ｎ）を、少なくとも（Ａ）式で必要となるＮビット分だけ保持、出力する第１のＮビット信号保持部と、
上記第２の２値符号化手段からの１ビット信号Ｙｂｉｎ（ｎ）を、少なくとも（Ａ）式で必要となるＮビット分だけ保持、出力する第２のＮビット信号保持部と、
上記第１及び第２の１ビット信号保持手段から出力された計Ｎビットの１ビット信号に対し、ビット単位に排他的論理和演算を行う排他的論理和演算部と、
Ｎビットの排他的論理和演算の出力の中から論理「１」のビット数を整数値に変換すると共に、この整数値を２倍する総和・２倍化部と、
Ｎから、上記総和・２倍化部による整数値を減算する減算部と
を有することを特徴とする請求項１に記載の相関演算器。
【請求項３】
２種類の離散的時間信号Ｘ（ｎ），Ｙ（ｎ）の、両信号間に時間差ｋがある場合の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）を算出する相関演算方法において、
第１の２値符号化手段と、第２の２値符号化手段と、演算手段とを有し、
上記第１の２値符号化手段は、離散的時間信号Ｘ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｘｂｉｎ（ｎ）に変換し、
上記第２の２値符号化手段は、離散的時間信号Ｙ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｙｂｉｎ（ｎ）に変換し、
上記演算手段は、上記第１及び第２の２値符号化手段からの１ビット信号Ｘｂｉｎ（ｎ）及びＹｂｉｎ（ｎ）に基づき、（Ｂ）式に従う演算を実行し、その演算結果を上記相互相関係数Ｃｏｒｒ（ｎ，ｋ）として出力する
ことを特徴とする相関演算方法。
【数２】
2008158855.tif 000014
但し、Ｎは相関の算出に用いられる各信号のサンプル数であり、＋を丸で囲んだ記号は排他的論理和演算を表している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は相関演算器及び相関演算方法に関し、例えば、通信や計測分野の即時性システムで使用される離散値系の相関演算に適用し得るものである。
【背景技術】
【０００２】
［離散的正規化相互相関係数の定義］
２種類の信号の類似度を算出する相関演算は、広範囲の科学技術分野で頻繁に実施されており、その応用範囲は極めて広いことが知られている。
【０００３】
一般に、２つの離散値系の時間信号Ｘ（ｎ）とＹ（ｎ−ｋ）の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）は次式で定義されている。
【数３】
2008158855.tif 000003
【０００４】
ここで、離散値系の時間信号Ｘ（ｎ）とＹ（ｎ）は単位時間で標本化されており、指標ｎは現時刻を表すものとする。また、０≦ｋ＜Ｍとする。
【０００５】
（１）式の定性的な意味を説明する。時刻ｎを固定するとき、Ｎサンプルで構成される信号Ｘ（ｎ−ｉ），０≦ｉ＜ＮとＹ（ｎ−ｋ−ｉ），０≦ｉ＜Ｎの類似度を算出している。そして、その探索範囲は０≦ｋ＜Ｍとしている。つまり、現時刻ｎにおいてＭ個の正規化相互相関係数Ｃｏｒｒ（ｎ、０），Ｃｏｒｒ（ｎ，１），…，Ｃｏｒｒ（ｎ，Ｍ−１）が得られるので、その中からＣｏｒｒ（ｎ，ｋ）の絶対値｜Ｃｏｒｒ（ｎ，ｋ）｜が最大値となるときのｋをｋｍａｘと表記すると、Ｘ（ｎ−ｉ），０≦ｉ＜Ｎに対して最も類似度が高い信号はＹ（ｎ−ｋｍａｘ−ｉ），０≦ｉ＜Ｎである。
【０００６】
以上の手順を時刻ｎが更新されるごとに繰り返す。
【０００７】
［演算量］
（１）式で表す離散的正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）、の演算量を見積もるに当たり、前提条件を設ける。
【０００８】
（前提条件１）  離散時刻ｎを更新するごとに、（１）式の変数ｋを０≦ｋ＜Ｍの範囲で変化させるので、（１）式をＭ回計算することになるが、高速フーリエ変換を利用した相関演算の演算量算出の簡易化を図るため、Ｍ＝Ｎとしておく。よって、（１）式をＮ回計算するときの演算量を算出する。
【０００９】
（前提条件２）  ａ×ｂ＋ｃの形式で表せる積和演算は、ハードウェアにより１マシンサイクル（１クロック期間）で算出可能とする。
【００１０】
以上の前提条件に基づき、（１）式の演算をＮ回繰り返すときの演算量を算出する。
【００１１】
まず、（１）式の分子はＮ回の積和演算を要する。さらにこれを０≦ｋ＜Ｎについて実施するので、Ｎ２回の積和演算を要する。
【００１２】
次に、分母の左側の平方根について演算量を求める。この項には変数ｋが現れないので、ｎが更新されるたびに１回算出しておけば良い。（２）式に示すように時刻ｎ−１のときの２乗和ＳＸを定義すると、時刻がｎ−１からｎに更新されるときに、（３）式に示す演算を要するので、上式の演算量を積和演算の回数に換算してα回で算出できると仮定しよう。同じく、分母の右側の平方根については、ｋが更新されるたびに（３）式と同様の処理を要する。
【数４】
2008158855.tif 000004
【００１３】
以上から、（１）式をＮ回演算するのに要する処理量は、積和演算の回数で換算すると、Ｎ２＋αＮ＋αとなる。ここで、Ｎが大きいときはＮの１次と０次の項は無視でき、（１）式をＮ回演算するのに要する処理量はＮ２に比例する。つまり、処理量のオーダはＯ（Ｎ２＋αＮ＋α）＝Ｎ２となる。
【００１４】
［従来技術による演算量の低減］
非特許文献１によると、高速フーリエ変換（ＦＦＴ：Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）の登場により、（１）式の演算は時間領域で実現するよりも、一旦、時間領域の信号Ｘ（ｎ）及びＹ（ｎ）をＦＦＴを利用して周波数領域の信号Ｘ（ｒ）とＹ（ｒ）に変換し、Ｚ（ｒ）＝Ｘ（ｒ）Ｙ＊（ｒ）を算出し（＊は共役複素数を表す）、次に、Ｚ（ｒ）をＦＦＴを利用して逆フーリエ変換すれば時間領域での相関演算を得ることができ、この方が演算量が低減できることが知られている。例えば、（１）式をＮ回演算するときの演算量は、ＦＦＴを利用すれば、Ｎｌｏｇ２Ｎに比例した処理量に低減可能である。処理量のオーダがＮ２からＮｌｏｇ２Ｎに低減するので、Ｎの値が大きいほどＦＦＴを利用するメリットも大きくなる。
【００１５】
なお、ＦＦＴの具体的な実現例については、特許文献１に記載されている。
【特許文献１】特開平５−１７４０４６号公報
【非特許文献１】Ｅ．ＯＲＡＮ  ＢＲＩＧＨＡＭ著／宮川訳、「高速フーリエ変換」、１３章、科学技術出版発行
【発明の開示】
【発明が解決しようとする課題】
【００１６】
上述したように、（１）式の相関演算は高速フーリエ変換（ＦＦＴ）を利用することで演算量の低減を図ることができる。これは、（１）式をなるべく正確、かつ、短時間で算出する要求があるときには有効な方法である。
【００１７】
しかしながら、応用上の観点からは、相関係数を数学的に正確に求めることよりも、極力短時間に、かつ、ハードウェア規模が小さな演算器を利用して相関係数を得たいとする要求が多い。とりわけこのような要求は、即時性に厳しい信号処理の分野で強い傾向がある。
【００１８】
これを具体例で説明すると、レーダシステムにおいて被測定物までの距離を求めようとするとき、送信信号をＳ（ｎ−ｋ）、反射信号をＲ（ｎ）とし、両信号Ｓ（ｎ−ｋ）及びＲ（ｎ）の正規化相互相関係数を計算し、相関係数の絶対値が最も大きくなるときのｋをｋｍａｘと表記すると、ｋｍａｘは被測定物までの往復伝搬遅延時間に相当し、これより、被測定物までの距離を算出することを可能にする。この場合、最も相関係数を大きくするｋｍａｘの値を知りたいのであって、相関係数の正確な値それ自体は陽に知る必要はない。換言すれば、ｋを変化させて得られる複数の相関係数の相対的な大小関係が適度に保たれていれば、相関係数の値それ自体は正確に求める必要はないということになる。
【００１９】
このような要求条件においては、ＦＦＴを利用した相関演算はその演算精度が過剰品質になる場合があり、演算精度を多少犠牲にしてでも演算量をさらに低減したいという要求に対して、必ずしも応じることができない。
【００２０】
さらに、相関演算をＦＦＴで実施しても積和演算器ならびにデータを保持するメモリは依然として必要とされ、時間領域で相関演算を実施するときと比べて、ハードウェア規模に大差はない。
【００２１】
これは、とりわけ、遠隔探査で使用されるセンサーなどのような小型装置に相関演算器を組み込む際に、装置容積、消費電力及びコストの増大を招くこととなる。
【００２２】
本発明は、以上の点に鑑みなされたものであり、少ない演算量で相互相関値を算出することができる相関演算器や、そのような相関演算器に適用可能な相関演算方法を提供しようとしたものである。
【課題を解決するための手段】
【００２３】
第１の本発明は、２種類の離散的時間信号Ｘ（ｎ），Ｙ（ｎ）の、両信号間に時間差ｋがある場合の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）を算出する相関演算器において、（１）離散的時間信号Ｘ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｘｂｉｎ（ｎ）に変換する第１の２値符号化手段と、（２）離散的時間信号Ｙ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｙｂｉｎ（ｎ）に変換する第２の２値符号化手段と、（３）上記第１及び第２の２値符号化手段からの１ビット信号Ｘｂｉｎ（ｎ）及びＹｂｉｎ（ｎ）に基づき、（Ａ）式に従う演算を実行し、その演算結果を上記相互相関係数Ｃｏｒｒ（ｎ，ｋ）として出力する演算手段とを有することを特徴とする。
【数５】
2008158855.tif 000005
【００２４】
但し、Ｎは相関の算出に用いられる各信号のサンプル数であり、＋を丸で囲んだ記号は排他的論理和演算を表している。
【００２５】
第２の本発明は、２種類の離散的時間信号Ｘ（ｎ），Ｙ（ｎ）の、両信号間に時間差ｋがある場合の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）を算出する相関演算方法において、（０）第１の２値符号化手段と、第２の２値符号化手段と、演算手段とを有し、（１）上記第１の２値符号化手段は、離散的時間信号Ｘ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｘｂｉｎ（ｎ）に変換し、（２）上記第２の２値符号化手段は、離散的時間信号Ｙ（ｎ）を、そのダイナミックレンジの中間値未満か中間値か中間値超過かに応じた１ビット信号Ｙｂｉｎ（ｎ）に変換し、（３）上記演算手段は、上記第１及び第２の２値符号化手段からの１ビット信号Ｘｂｉｎ（ｎ）及びＹｂｉｎ（ｎ）に基づき、（Ｂ）式に従う演算を実行し、その演算結果を上記相互相関係数Ｃｏｒｒ（ｎ，ｋ）として出力することを特徴とする。
【数６】
2008158855.tif 000006
【００２６】
但し、Ｎは相関の算出に用いられる各信号のサンプル数であり、＋を丸で囲んだ記号は排他的論理和演算を表している。
【発明の効果】
【００２７】
本発明によれば、入力信号を１ビット信号に変換して相互相関値を算出するようにしたので、少ない演算量で相互相関値を算出することができる。
【発明を実施するための最良の形態】
【００２８】
（Ａ）主たる実施形態  
以下、本発明による相関演算器及び相関演算方法の一実施形態を、図面を参照しながら説明する。
【００２９】
（Ａ−１）実施形態における技術思想
この実施形態は、相関を取ろうとする２種類の信号をそれぞれ＋１と−１の２値に符号化することで相関演算に要する演算量とハードウェア規模を大幅に低減させようとしたものである。
【００３０】
［２値信号の正規化相互相関演算アルゴリズム］
まず、±１に２値化された信号の正規化相互相関演算アルゴリズムを説明する。
【００３１】
一般に、２つの離散値系の時間信号Ｘ（ｎ）とＹ（ｎ−ｋ）の正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）は（４）式で定義される。
【数７】
2008158855.tif 000007
【００３２】
ここで、０≦ｋ＜Ｍとする。また、一般に、信号Ｘ（ｎ）とＹ（ｎ）の数値フォーマットは、複数ビットで構成される浮動小数点若しくは固定小数点である。
【００３３】
次に、各信号Ｘ（ｎ）、Ｙ（ｎ）を±１の２値に符号化した信号をそれぞれＸｓｇｎ（ｎ）、Ｙｓｇｎ（ｎ）と表記し、（５）式のように定義する。
【数８】
2008158855.tif 000008
【００３４】
ここで、動作開始直後に信号Ｘ（ｎ）が０であるとき、Ｘ（ｎ−１）とＸｓｇｎ（ｎ−１）がまだ存在していないので、Ｘｓｇｎ（ｎ）の値は、＋１と−１のどちらでも良いこととする。これは、信号Ｙ（ｎ）に関しても同様とする。
【００３５】
両信号Ｘｓｇｎ（ｎ）及びＹｓｇｎ（ｎ）の正規化相互相関係数Ｃｏｒｒｓｇｎ（ｎ，ｋ）は（６）式で表すことができる。（６）式において、０≦ｋ＜Ｍとする。
【数９】
2008158855.tif 000009
【００３６】
（５）式に示すように、各信号Ｘｓｇｎ（ｎ）、Ｙｓｇｎ（ｎ）は±１の２値であるが、実際のインプリメント（製品）上では１ビットの２進数データとして扱われるので、ここでは、正負を表す符号ビットの一般的な定義に従って、数値＋１を２進数「０」に対応させ、数値−１を２進数「１」に対応させることとする。図２は、２値化信号Ｘｓｇｎ（ｎ）及びＹｓｇｎ（ｎ）の２進数表現をＸｂｉｎ（ｎ）及びＹｂｉｎ（ｎ）と表記し、対応関係を示したものである。
【００３７】
次に、図２の対応関係を用いて、（６）式における乗算Ｘｓｇｎ（ｎ−ｉ）Ｙｓｇｎ（ｎ−ｉ）について考察する。この乗算は４通りしか存在せず、このときの２進数との対応は、図３に示すようになる。図３においては、＋を白丸で囲んだ記号は排他的論理和を表している。明細書では、かかる記号を用いられないので、明細書の中では、「∧」を、排他的論理和を表すものとして用いる。
【００３８】
図３から明らかなように、±１に２値化された信号の乗算は、２進数では排他的論理和∧に対応している。これにより、Ｘｂｉｎ（ｎ−ｉ）∧Ｙｂｉｎ（ｎ−ｋ−ｉ）についてのｉ＝０からＮ−１までの総和ΣＸｂｉｎ（ｎ−ｉ）∧Ｙｂｉｎ（ｎ−ｋ−ｉ）は、ΣＸｓｇｎ（ｎ−ｉ）Ｙｓｇｎ（ｎ−ｋ−ｉ）（総和はｉ＝０からＮ−１まで）において、Ｘｓｇｎ（ｎ−ｉ）Ｙｓｇｎ（ｎ−ｋ−ｉ）が−１となる個数を表すこととなる。逆に、Ｘｓｇｎ（ｎ−ｉ）Ｙｓｇｎ（ｎ−ｋ−ｉ）が１となる個数は、Ｎ−ΣＸｂｉｎ（ｎ−ｉ）∧Ｙｂｉｎ（ｎ−ｋ−ｉ）である。それ故に（７）式が成立する。ここで、正規化相互相関係数Ｃｏｒｒｓｇｎ（ｎ，ｋ）を２進数表記Ｘｂｉｎ（ｎ）、Ｙｂｉｎ（ｎ）を使用して表現すると、（８）式が得られる。（８）式において、正規化処理である１／Ｎは単なる定数になっており、応用上は演算する価値はないので、（８）式を（９）式のように変形する。
【数１０】
2008158855.tif 000010
【００３９】
（Ａ−２）実施形態の相関演算器
図１は、実施形態の相関演算器の全体構成を示すブロック図である。実施形態の相関演算器１００は、（９）式に従って、２つの入力信号の相関係数を演算するものである。
【００４０】
図１において、実施形態の相関演算器１００は、２個の符号ビット抽出器１０１、１０２、２個のシフトレジスタ１０３、１０４、排他的論理和ゲート群１０５、加算器１０６及び減算器１０７を有する。
【００４１】
符号ビット抽出器１０１には離散的時間信号Ｘ（ｎ）が入力され、符号ビット抽出器１０１は、入力信号Ｘ（ｎ）の正値、負値、０に応じて、（１０）式に従って、１ビット信号Ｘｂｉｎ（ｎ）を出力するものである。（１０）式における上バーの付与は、付与されているビット値の否定、つまり、付与されているビット値のビット反転を表している。なお、この明細書では、ビット反転を、反転対象の値を表す符号の前に「／」を付与して表すこととする。
【数１１】
2008158855.tif 000011
【００４２】
なお、処理対象の離散的時間信号が０及び正値の範囲をとる信号である場合には、処理対象信号から、そのダイナミックレンジの中央値を減算して、正負をとる離散的時間信号Ｘ（ｎ）に変換して符号ビット抽出器１０１に入力することを要する。
【００４３】
同様に、符号ビット抽出器１０２は、他方の入力信号である離散的時間信号Ｙ（ｎ）の正値、負値、０に応じて、（１１）式に従って、１ビット信号Ｙｂｉｎ（ｎ）を出力するものである。
【００４４】
図４は、離散的時間信号Ｘ（ｎ）の数値フォーマットが２の補数であるときの符号ビット抽出器１０１の具体的構成例を示している。なお、説明は省略するが、符号ビット抽出器１０２も同様である。
【００４５】
図４において、符号ビット抽出器１０１は、ＮＯＲゲート２０１、２−１セレクタ２０２、ＮＯＴゲート２０３及びレジスタ２０４を有する。
【００４６】
入力信号Ｘ（ｎ）の数値フォーマットは２の補数であるので、ＭＳＢビットは符号ビットである。符号ビットは、０≦Ｘ（ｎ）のとき０、Ｘ（ｎ）＜０のとき１である。また、入力信号Ｘ（ｎ）＝０のときには、入力信号Ｘ（ｎ）の全てのビットは０となっている。
【００４７】
入力信号Ｘ（ｎ）の全てのビットは、ＮＯＲゲート２０１に入力され、Ｘ（ｎ）＝０のときのみＮＯＲゲート２０１の出力は１となり、それ以外のときは０となり、この出力信号は、２−１セレクタ２０２の選択制御端子に与えられる。
【００４８】
２−１セレクタ２０２の一方の入力端子には入力信号Ｘ（ｎ）の符号ビットであるＭＳＢビットが入力され、２−１セレクタ２０２の他方の入力端子には当該符号ビット抽出器１０１からの出力信号Ｘｂｉｎ（ｎ）の１単位時間前の信号Ｘｂｉｎ（ｎ−１）をビット反転した／Ｘｂｉｎ（ｎ−１）が入力されている。２−１セレクタ２０２は、ＮＯＲゲート２０１の出力信号に応じ、入力信号Ｘ（ｎ）が０のときのみ／Ｘｂｉｎ（ｎ−１）を選択し、２−１セレクタ２０２の出力にＸｂｉｎ（ｎ）として現れ、これ以外のときは、入力信号Ｘ（ｎ）の符号ビットを選択し、セレクタ２０２の出力にＸｂｉｎ（ｎ）として現れる。
【００４９】
レジスタ２０４は、２−１セレクタ２０２の出力信号Ｘｂｉｎ（ｎ）を格納するレジスタであり、格納値は、入力信号Ｘ（ｎ）の標本化レートに同期して更新される。よって、当該レジスタ２０４の出力は、出力信号Ｘｂｉｎ（ｎ）の１単位時間前の値であるＸｂｉｎ（ｎ−１）となる。
【００５０】
レジスタ２０４からの出力信号Ｘｂｉｎ（ｎ−１）はＮＯＴゲート２０３に入力され、ＮＯＴゲート２０３は、この信号Ｘｂｉｎ（ｎ−１）をビット反転した／Ｘｂｉｎ（ｎ−１）を２−１セレクタ２０２に与える。
【００５１】
図４に示す符号ビット抽出器１０１の構成例は、あくまでも上述した（１０）式を具現化するための単なる一例である。例えば、符号ビット抽出器１０１からの出力信号Ｘｂｉｎ（ｎ）を標本化レートに同期して更新した方が望ましいときは、レジスタ２０４の出力を符号ビット抽出器１０１からの出力信号Ｘｂｉｎ（ｎ）としても良い。また、数値フォーマットが２の補数でないときであっても、（１０）式を満足させるように、その数値フォーマットに応じて符号ビット抽出器を設計すれば良い。
【００５２】
図１の２つのシフトレジスタ１０３及び１０４、並びに、排他的論理和ゲート群１０５は、上述した（９）式の要素演算である、（１２）式に示す排他的論理和演算を、ｉについて０≦ｉ＜Ｎの範囲でパラレルに１マシンサイクルで実施し、かつ、ｋについて０≦ｋ＜Ｍの範囲でＭマシンサイクルで実施するものである。
【００５３】
Ｘｂｉｎ（ｎ−ｉ）∧Ｙｂｉｎ（ｎ−ｋ−ｉ）                        …（１２）
シフトレジスタ１０３は、（１２）式の左側の要素Ｘｂｉｎ（ｎ−ｉ）を（９）式の総和に必要な分だけ形成させるものであり、シフトレジスタ１０４は、（１２）式の右側の要素Ｙｂｉｎ（ｎ−ｋ−ｉ）を（９）式の総和に必要な分だけ形成させるものであり、排他的論理和ゲート群１０５は、（９）式の総和に係るＮ個の排他的論理和の値を形成させるものである。
【００５４】
図５は、シフトレジスタ１０３及び１０４、並びに、排他的論理和ゲート群１０５の具体的な構成例を示すブロック図である。
【００５５】
なお、以下で説明するが、図５の構成例では、ｋは、Ｍ−１を初期値とし、デクリメントしながら０まで変化させており、動作の理解のために、このことに留意すべきである。また、図５では、表記を簡単にするため、排他的論理和ゲート群１０５からの出力については、Ｘｂｉｎ（ｎ）、Ｙｂｉｎ（ｎ）と記載すべき所を、単に、Ｘ（ｎ）、ｙ（ｎ）と記載している。
【００５６】
一方のシフトレジスタ１０３は、シリアル入力パラレル出力機能を具備したＮビットのシフトレジスタである。シフトレジスタ１０３は、シリアル入力端子ＳＩ、シフトイネーブル入力端子ＳＥ、クロック入力端子ＣＫ及びパラレル出力端子（このパラレル出力端子に対応する格納部を適宜、レジスタと呼ぶ）Ｑ（０）〜Ｑ（Ｎ−１）を有する。以下の説明では、入出力端子に係る信号も、入出力端子と同じ符号を用いて説明する。
【００５７】
シフトレジスタ１０３において、シフトイネーブル信号ＳＥがアクティブであるとき、標本化レートに同期したクロック信号ＣＫに同期して、レジスタＱ（Ｎ−２）のビット情報はレジスタＱ（Ｎ−１）にシフトされ、レジスタＱ（Ｎ−３）のビット情報はレジスタＱ（Ｎ−２）にシフトされ、以下同様に、レジスタＱ（０）のビット情報はレジスタＱ（１）にシフトされ、符号ビット抽出器１０１から入力された信号Ｘｂｉｎ（ｎ）はシリアル入力端子ＳＩを経由してレジスタＱ（０）に格納される。
【００５８】
従って、時刻ｎの時点で、当該シフトレジスタ１０３のパラレル出力端子Ｑ（０）〜Ｑ（Ｎ−１）には、信号Ｘｂｉｎ（ｎ）〜Ｘｂｉｎ（ｎ−（Ｎ−１））までのＮビットが現れ、次の入力信号Ｘｂｉｎ（ｎ＋１）が入力されるまでの間保持されると同時に、これらＮビットＸｂｉｎ（ｎ）〜Ｘｂｉｎ（ｎ−（Ｎ−１））が排他的論理和ゲート群１０５に供給される。
【００５９】
他方のシフトレジスタ１０４は、シリアル入力パラレル出力機能、パラレル入力ローディング機能、並びに、ローテイトシフト機能（巡回シフト機能）を具備したＮ＋Ｍ−１ビットのシフトレジスタである。
【００６０】
シフトレジスタ１０４は、符号ビット抽出器１０２から出力される１ビット情報を保持し、標本化周期で時系列的にビットシフトされ、かつ、１つの標本化周期内で一定回数ローテイトシフトされ、かつ、このローテイトシフト後に再度符号ビット抽出器１０２から出力される１ビット情報を入力する際に、前回入力時から１ビットシフトした状態にすることが可能なローディング機能を有する。
【００６１】
シフトレジスタ１０４は、シリアル入力端子ＳＩ、シフトイネーブル入力端子ＳＥ、ロードイネーブル入力端子ＬＥ、クロック入力端子ＣＫ、パラレル入力端子Ｄ（０）〜Ｄ（Ｎ＋Ｍ−２）、及び、パラレル出力端子Ｑ（０）〜Ｑ（Ｎ＋Ｍ−２）を有する。
【００６２】
パラレル出力端子（レジスタ）Ｑ（Ｍ−１）〜Ｑ（Ｎ＋Ｍ−２）のＮビットは排他的論理和ゲート群１０５に接続され、シリアル入力端子ＳＩには当該シフトレジスタ１０４の最終段のレジスタ出力Ｑ（Ｎ＋Ｍ−２）が入力されるようになされている。
【００６３】
パラレル入力端子Ｄ（０）には符号ビット抽出器１０２から出力される信号Ｙｂｉｎ（ｎ）が入力され、パラレル入力端子Ｄ（１）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（Ｍ−１）が接続され、…、パラレル入力端子Ｄ（Ｍ−３）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（（２Ｍ−５）ｍｏｄ（Ｎ＋Ｍ−１））が接続され、パラレル入力端子Ｄ（Ｍ−２）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（（２Ｍ−４）ｍｏｄ（Ｎ＋Ｍ−１））が接続され、パラレル入力端子Ｄ（Ｍ−１）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（（２Ｍ−３）ｍｏｄ（Ｎ＋Ｍ−１））が接続され、パラレル入力端子Ｄ（Ｍ）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（（２Ｍ−２）ｍｏｄ（Ｎ＋Ｍ−１））が接続され、…、パラレル入力端子Ｄ（Ｎ＋Ｍ−３）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（Ｍ−４）が接続され、パラレル入力端子Ｄ（Ｎ＋Ｍ−２）には当該シフトレジスタ１０４のパラレル出力端子Ｑ（Ｍ−３）が接続されている。
【００６４】
ここで、ｓ  ｍｏｄ  ｔは、ｔを法としたときのｓの剰余を表す。例えば、９  ｍｏｄ８＝１である。上述したシフトレジスタ１０４のパラレル出力端子からパラレル入力端子へのフィードバック経路を、このｍｏｄを使用して汎用的に表現すると、パラレル入力端子Ｄ（ｘ）にはパラレル出力端子Ｑ（（ｘ＋Ｍ−２）ｍｏｄ（Ｎ＋Ｍ−１））が接続されている。但し、ｘ≠０とする。なお、シフトレジスタ１０４を上述のように接続する理由は後述する。
【００６５】
シフトレジスタ１０４のロードイネーブル信号ＬＥがアクティブであるとき、クロック信号ＣＫに同期して、パラレル入力端子Ｄ（０）〜Ｄ（Ｎ＋Ｍ−２）はパラレル出力端子Ｑ（０）〜Ｑ（Ｎ＋Ｍ−２）にローディングされる。これに対して、シフトレジスタ１０４のシフトイネーブル信号ＳＥがアクティブであるとき、クロック信号ＣＫに同期して、レジスタＱ（０）のビット情報はレジスタＱ（１）にシフトされ、レジスタＱ（１）のビット情報はレジスタＱ（２）にシフトされ、以下同様に、レジスタＱ（Ｎ＋Ｍ−３）のビット情報はレジスタＱ（Ｎ＋Ｍ−２）にシフトされる。但し、最終段のレジスタＱ（Ｎ＋Ｍ−２）のビット情報は、シリアル入力端子ＳＩを経由して、レジスタＱ（０）にローテイトシフトされる。なお、ロードイネーブル信号ＬＥとシフトイネーブル信号ＳＥとが、同時にアクティブになることはない。
【００６６】
時刻ｎの時点で、シフトレジスタ１０４のロードイネーブル信号ＬＥをアクティブし、符号ビット抽出器１０２からの出力信号Ｙｂｉｎ（ｎ）を当該シフトレジスタ１０４のレジスタＱ（０）にローディングする。次に、シフトレジスタ１０４のロードイネーブル信号ＬＥをインアクティブにし、シフトイネーブル信号ＳＥをアクティブにし、クロック信号ＣＫに同期して、Ｍ−１回ほどシフトさせる。この動作は、符号ビット抽出器１０２からの次の信号Ｙｂｉｎ（ｎ＋１）が入力されるまでの間に完了しなければならない。よって、シフトレジスタ１０４のクロック信号ＣＫの周波数をｆｃｋとし、信号Ｙｂｉｎ（ｎ）の標本化周波数をｆｓとするときには、（１３）式に示す関係を成立させておかなければならない。こうすることにより、（１２）式の要素別の演算を、１標本化周期内に、０≦ｉ≦Ｎ−１，Ｍ−１≧ｋ≧０について、Ｍマシンサイクルで実施することが可能となる。
【００６７】
ｆｃｋ≧（Ｍ＋１）・ｆｓ                                          …（１３）
なお、シフトレジスタ１０４をＭ−１ビットほどシフトさせた時点で、信号Ｙｂｉｎ（ｎ）はレジスタＱ（Ｍ−１）に移動している。この信号Ｙｂｉｎ（ｎ）は、次の信号（ビット情報）Ｙｂｉｎ（ｎ＋１）が到来した際にはレジスタＱ（１）にローディングさせる必要がある。これが、上述したシフトレジスタ１０４のパラレル出力端子を自身のパラレル入力端子にツイストして接続している理由である。
【００６８】
ところで、上述したように、シフトレジスタ１０４のパラレル出力端子（Ｍ−１）〜Ｑ（Ｎ＋Ｍ−２）のＮビットが排他的論理和ゲート群１０５に出力されているので、当該シフトレジスタ１０４のローディング時に、これは（１２）式においてｋ＝Ｍ−１のときに対応し、次に、当該シフトレジスタ１０４がビットシフトされるごとに、Ｋ＝Ｍ−２，Ｍ−３，…，０の順序で、（１２）式の０≦ｉ＜Ｎ−１についてのパラレル論理演算が合計Ｍ回実施されることとなる。
【００６９】
図５の排他的論理和ゲート群１０５は、Ｎ個の排他的論理和ゲートで構成され、２個のシフトレジスタ１０３及び１０４から、それぞれ出力されているＮビットの信号を入力とし、（１２）式の０≦ｉ＜Ｎ−１についての排他的論理和演算をパラレルに実施し、Ｎビットの演算結果情報は、図１の加算器１０６に供給される。
【００７０】
図１に示す加算器１０６は、排他的論理和ゲート群１０５から出力されるＮビットの情報中の論理値が１となっているビット数を符号無し整数で算出し、当該算出結果を２倍し、さらに、符号ビットを付与して符号付き整数にすることで、（１４）式に示すような、上述した（９）式の右辺第２項の値を算出するものである。加算器１０６による算出結果は、減算器１０７に提供される。
【数１２】
2008158855.tif 000012
【００７１】
図６は、加算器１０６の具体的な構成例を示すブロック図である。図６において、加算器１０６は、第１ステージ〜第ｒステージの符号無し整数加算器と、ＭＳＢ・ＬＳＢ付加部とで構成される。ここで、ｒ＝Ｆ（ｌｏｇ２Ｎ）であり、関数Ｆ（ｘ）はセイリング関数であり、ｘ未満ではない最小の整数を表している。
【００７２】
まず、第１ステージでは、Ｎビットの信号を２つずつペアを取り、符号無し整数加算器に入力して加算する。なお、図６では、Ｎを偶数として描いているが、奇数の場合には、ペアを取った後の残り１ビットは次の第２ステージの入力となる。この奇偶による構成の違いは、第２ステージ以降でも同様である。なお、第１ステージにおける符号無し整数加算器の数は、Ｎが偶数の場合にはＮ／２個であり、Ｎが奇数の場合には（Ｎ−１）／２個である。
【００７３】
第１ステージの加算結果はそれぞれ、第２ステージの符号無し整数加算器に入力され、第１ステージと同様に、２つずつペアを取った加算が実行される。以後、このような処理が、ステージに所属する符号無し整数加算器が１個の第ｒステージまで繰り返し実行される。
【００７４】
最終段である第ｒステージの符号無し整数加算器の出力は、（１４）式に示す値の半分であり、この値の最大値はＮであるから、これは、符号無し整数のビット数Ｒで換算すると、Ｒ＝Ｇ（ｌｏｇ２Ｎ）＋１となる。ここで、Ｇ（ｘ）はフロア関数であり、ｘを超過しない最大の整数を表す。
【００７５】
第ｒステージの符号無し整数加算器のＲビット出力に対し、「０」でなるＬＳＢを追加することで、第ｒステージの符号無し整数加算器のＲビット出力を２倍し、かつ、第ｒステージの符号無し整数加算器のＲビット出力に対し、「０」でなるＭＳＢを追加することで、符号付き整数に変換している。
【００７６】
ところで、図６に示す加算器１０６の演算は、第１ステージから最終ステージ（第ｒステージ）まで１マシンサイクルで実施できることを想定している。しかし、ｒが大きくなると加算器１０６での処理遅延が増大し、１マシンサイクルでは実施できない可能性がでてくる。このような場合には、クロック信号に同期して入力信号を保持することが可能なレジスタを適切なステージ間隔で配備すれば良い。すなわち、このようにパイプライン演算とすることで、処理遅延は増大するものの、処理スループットは低減しないこととなり、（９）式をＭマシンサイクル周期で実施することを可能とする。
【００７７】
図１の減算器１０７は、特に、具体的構成例を挙げるまでもなく、Ｎから加算器１０６の出力（（９）式の右辺第２項）を減算するものであり、これにより、（９）式が完全に演算されたことになる。
【００７８】
（Ａ−３）実施形態の効果
［効果１］少ない演算量
２つの離散的時間信号Ｘ（ｎ）及びＹ（ｎ）の（４）式で表す正規化相互相関係数Ｃｏｒｒ（ｎ，ｋ）の演算量のオーダと、実施形態における、２つの離散的時間信号Ｘ（ｎ）及びＹ（ｎ）を２値化したときの（９）式で表す正規化相互相関係数Ｎ・Ｃｏｒｒｓｇｎ（ｎ、ｋ）の演算量を０≦ｉ＜Ｎ，０≦ｋ＜Ｎの条件で比較する。
【００７９】
従来技術並びに実施形態について、正規化相互相関係数の演算量を積和演算の回数で換算すると、図７に示すようになる。
【００８０】
図７において、従来技術の周波数領域の演算量に現れるαは比例定数である。これは、従来技術で説明したように、周波数領域での演算量はＮｌｏｇ２Ｎに比例するからである。これに対して、実施形態は、まさにＮ回であり、比例定数は１である。
【００８１】
従って、上記実施形態は、従来技術の時間領域での演算に対して１／Ｎ、周波数領域での演算に対して１／（αｌｏｇ２Ｎ）の低減化を達成しており、Ｎが大きくなる程、演算量は相対的に小さくなる。例えば、Ｎ＝１０２４＝２１０の場合、従来技術の時間領域での演算に対して数千分の１、周波数領域での演算に対して数十分の１に演算量を低減化している。
【００８２】
［効果２］乗算／除算／平方根の排除
一般に、乗算、除算、平方根演算と加算演算を比較すると、ハードウェア規模と処理時間はいずれも加算演算の方が小さい。上記実施形態は（９）式に従って処理されるので、乗算、除算、平方根演算が不要であり、ハードウェア規模、処理時間、消費電力を低減化することを可能としている。
【００８３】
（Ｂ）他の実施形態
上記実施形態では、相関演算器を概ねハードウェアで構成したものを示したが、ＣＰＵが実行するソフトウェア（相関演算プログラム）として構成するようにしても良い。この場合であっても、ハードウェア規模の削減を除けば、上記実施形態と同様な効果を奏することができる。
【００８４】
また、上記実施形態の説明では相関演算器の用途に言及しなかったが、２種類の離散的時間信号の正規化相互相関係数を演算する各種通信装置や計測装置に応用可能である。
【００８５】
本発明の相関演算器は、上記実施形態のような構成要素の組で構成されたものに限定されず、要は、入力信号Ｘ（ｎ），Ｙ（ｎ）を１ビット信号Ｘｂｉｎ（ｎ），Ｙｂｉｎ（ｎ）に変換した後に、上述した（９）式を実行できる構成であれば良い。
【００８６】
上記実施形態においては、入力信号Ｘ（ｎ），Ｙ（ｎ）を１ビット信号Ｘｂｉｎ（ｎ），Ｙｂｉｎ（ｎ）に変換した後、相関を算出する時間差ｋを考慮するものを示したが、入力信号Ｘ（ｎ），Ｙ（ｎ）に対し、相関を求める信号間の時間差ｋを付与する処理（例えば、一方を遅延させる処理）を行った後に、１ビット信号に変換するようにしても良い。特許請求の範囲の表現は、このような変形例を必ずしも含んでいないが、このような変形例を特許請求の範囲はカバーしているものとする。
【図面の簡単な説明】
【００８７】
【図１】実施形態の相関演算器１００の構成を示すブロック図である。
【図２】実施形態の２値化信号Ｘｓｇｎ（ｎ）、Ｙｓｇｎ（ｎ）と２進数表現をＸｂｉｎ（ｎ）、Ｙｂｉｎ（ｎ）との対応関係を説明する図表である。
【図３】実施形態の乗算Ｘｓｇｎ（ｎ−ｉ）Ｙｓｇｎ（ｎ−ｋ−ｉ）における２進数表現との対応関係を説明する図表である。
【図４】実施形態における符号ビット抽出器１０１（及び１０２）の具体的構成例を示すブロック図である。
【図５】実施形態におけるシフトレジスタ１０３及び１０４、並びに、排他的論理和ゲート群１０５の具体的な構成例を示すブロック図である。
【図６】実施形態における加算器１０６の具体的な構成例を示すブロック図である。
【図７】実施形態における性能面の効果の説明図である。
【符号の説明】
【００８８】
１００：相関演算器、１０１、１０２：符号ビット抽出器、１０３、１０４：シフトレジスタ、１０５：排他的論理和ゲート群、１０６：加算器、１０７：減算器。
【図１】
2008158855.tif 000015
【図２】
2008158855.tif 000016
【図３】
2008158855.tif 000017
【図４】
2008158855.tif 000018
【図５】
2008158855.tif 000019
【図６】
2008158855.tif 000020
【図７】
2008158855.tif 000021