(57)【要約】【課題】  相互相関値の計算に必要な演算回路の数または演算回数を削減し、回路規模および消費電力がともに小さくする。【解決手段】  各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算方法において、第１の信号系列の先頭および最後の要素を除く要素を差動符号化して第２の信号系列を生成し、この第２の信号系列と受信信号系列との間の相互相関計算による第１の演算値を計算し、この第１の演算値と前回の第１の演算値との和から第１の演算値を再帰的に計算する第１の演算ステップと、第１の信号系列の先頭の信号値と受信信号系列の先頭の信号値との積と、第１の演算ステップで得られた第１の演算値とを加算して相互相関値を出力する第２の演算ステップとを有する。【選択図】        図１
2010011391.tif 000002
【特許請求の範囲】
【請求項１】
各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算方法において、
前記第１の信号系列の先頭および最後の要素を除く要素を差動符号化して第２の信号系列を生成し、この第２の信号系列と前記受信信号系列との間の相互相関計算による第１の演算値と、前回までの該第１の演算値の累積加算により得られた第２の演算値との和を新たな第２の演算値として計算する第１の演算ステップと、
前記第１の信号系列の先頭の信号値と前記受信信号系列の先頭の信号値との積と、前記第１の演算ステップで得られた前記新たな第２の演算値とを加算して前記相互相関値を出力する第２のステップと
を有し、前記受信信号系列が更新されるごとに、更新された受信信号系列に対して前記第１の演算ステップと前記第２の演算ステップを繰り返す
ことを特徴とする相互相関値演算方法。
【請求項２】
各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算方法において、
前記第１の信号系列の各要素について、その先頭の要素が前記第１の信号系列の２番目の要素の符号を反転したものであり、次の要素が１つ後の要素と同符号の場合には当該要素を０に置き換え、１つ後の要素と同符号でない場合には当該要素を後の要素との差に置き換え、その最後の要素が前記第１の信号系列の最後の要素である第２の信号系列に変換し、この第２の信号系列の０以外の要素と、その要素の第２の信号系列内の位置と同じ位置関係にある前記受信信号系列の要素とを乗算し、前記第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して得られた第１の演算値と、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する第１の演算ステップと、
前記第１の信号系列の先頭の要素と前記受信信号系列の先頭の要素との乗算の結果と、前記新たな第２の演算値とを加算して前記相互相関値を出力する第２の演算ステップと
を有し、前記受信信号系列が更新されるごとに、更新された受信信号系列に対して前記第１の演算ステップと前記第２の演算ステップを繰り返す
ことを特徴とする相互相関値演算方法。
【請求項３】
請求項２に記載の相互相関値演算方法において、
前記第１の信号系列の各要素について、１つ後の要素と同符号でない場合には後の要素との差が負のときは−１、正のときは＋１に置き換えて前記第２の信号系列に変換し、前記第１の演算ステップおよび前記第２の演算ステップにおける乗算をビットシフトと符号変換により行う
ことを特徴とする相互相関値演算方法。
【請求項４】
各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算回路において、
前記第１の信号系列の各要素について、その先頭の要素が前記第１の信号系列の２番目の要素の符号を反転したものであり、次の要素が１つ後の要素と同符号の場合には当該要素を０に置き換え、１つ後の要素と同符号でない場合には当該要素を後の要素との差に置き換え、その最後の要素が前記第１の信号系列の最後の要素である第２の信号系列に変換し、この第２の信号系列の０以外の要素と、その要素の第２の信号系列内の位置と同じ位置関係にある前記受信信号系列の要素とを乗算し、前記第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して得られた第１の演算値と、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する第１の演算ブロックと、
前記第１の信号系列の先頭の要素と前記受信信号系列の先頭の要素との乗算の結果と、前記新たな第２の演算値とを加算して前記相互相関値を出力する第２の演算ブロックと
を備え、前記受信信号系列が更新されるごとに、更新された受信信号系列に対して前記第１の演算ブロックによる演算処理と前記第２の演算ブロックによる演算処理を繰り返す構成である
を備えたことを特徴とする相互相関値演算回路。
【請求項５】
請求項４に記載の相互相関値演算回路において、
前記第１の演算ブロックは、
前記第１の信号系列から前記第２の信号系列に変換し、この第２の信号系列の０以外の要素を出力する変換回路と、
前記第２の信号系列の０以外の要素を格納する第１の記憶回路と、
前記第２の信号系列の０以外の要素と、その要素の第２の信号系列内の位置と同じ位置関係にある前記受信信号系列の要素との乗算を行う乗算回路と、
前記第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して第１の演算値を出力し、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する加算回路および第２の記憶回路とを備え、
前記第２の演算ブロックは、前記乗算回路を用いて前記第１の信号系列の先頭の要素と前記受信信号系列の先頭の要素との乗算を行い、前記加算回路および第２の記憶回路を用いて前記相互相関値を出力する構成である
ことを特徴とする相互相関値演算回路。
【請求項６】
請求項４に記載の相互相関値演算回路において、
前記第１の演算ブロックは、
前記第１の信号系列から前記第２の信号系列に変換し、この第２の信号系列の０以外の要素を出力する変換回路と、
前記第２の信号系列の０以外の要素を格納する第１の記憶回路と、
前記第２の信号系列の０以外のすべての要素と、それぞれの要素の第２の信号系列内の位置と同じ位置関係にある前記受信信号系列の要素との乗算を行う乗算回路アレーと、
前記第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して第１の演算値を出力し、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する加算回路ツリーおよび第２の記憶回路とを備え、
前記第２の演算ブロックは、
前記第１の信号系列の先頭の要素と前記受信信号系列の先頭の要素との乗算を行う乗算回路と、
前記第１の信号系列の先頭の要素と前記受信信号系列の先頭の要素との乗算の結果と、前記新たな第２の演算値とを加算して前記相互相関値を出力する加算回路とを備えた
ことを特徴とする相互相関値演算回路。
【請求項７】
請求項５に記載の相互相関値演算回路において、
前記変換回路は、前記第１の信号系列の各要素について、１つ後の要素と同符号でない場合には後の要素との差が負のときは−１、正のときは＋１に置き換えて前記第２の信号系列に変換する構成であり、
前記乗算回路は、前記乗算処理をビットシフトと符号変換により行う構成である
ことを特徴とする相互相関値演算回路。
【請求項８】
請求項６に記載の相互相関値演算回路において、
前記変換回路は、前記第１の信号系列の各要素について、１つ後の要素と同符号でない場合には後の要素との差が負のときは−１、正のときは＋１に置き換えて前記第２の信号系列に変換する構成であり、
前記乗算回路アレーを構成する乗算回路は、前記乗算処理をビットシフトと符号変換により行う構成である
ことを特徴とする相互相関値演算回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、外部から入力する受信信号の中から所定の信号パターンに一致する部分の特定に用いる相互相関値演算方法および相互相関値演算回路に関する。
【背景技術】
【０００２】
図１１は、従来の相互相関値演算回路のシリアル型の構成例を示す（特許文献１）。図１２は、従来の相互相関値演算回路のシリアル型の動作例タイミングチャートを示す。
【０００３】
図において、外部から入力する受信信号はシフトレジスタ３１に格納され、所定の信号パターンを表す疑似ランダム信号はレジスタ３２に格納され、選択回路３３，３４を介してそれぞれ順次出力される。選択回路３３，３４の各出力は乗算回路３５で乗算され、乗算結果が加算回路３６を介してレジスタ３７に入力する。レジスタ３７の出力は、加算回路３６に入力して乗算結果と加算されるとともに、レジスタ３８を介して受信信号と所定の信号パターンとの相互相関値として出力される。制御回路３９は、外部から入力するクロックに同期してシフトレジスタ３１、選択回路３３，３４、レジスタ３７，３８の動作を制御する。
【０００４】
シフトレジスタ３１は、時刻(ｓ＋１)において相互相関値の計算対象となるＭ個の受信信号の系列｛ｘs+1 ，ｘs+2 ，…，ｘs+M ｝を格納し、新たな受信信号を１つ受信するごとに最も古い受信信号を１つ破棄し、最新の受信信号を初段に格納する。ｘs+i(ｉは１〜Ｍの整数）は、Ｎビット幅（Ｎは１以上の整数）の２の補数表現されたディジタルデータとする。レジスタ３２は、所定の信号パターンを表す疑似ランダム信号系列｛ｂ1 ，ｂ2 ，…，ｂM ｝を格納する。ｂi は、−１または＋１の１ビット幅のディジタルデータとする。
【０００５】
選択回路３３はシフトレジスタ３１内のＭ個の受信信号から１つ（ｘs+i ）を選択し、選択回路３４はレジスタ３２内から１つの疑似ランダム信号（ｂi ）を選択し、乗算回路３５はそれぞれ選択された信号の乗算処理（ｘs+i・ｂi）を行う。この乗算処理を各信号を入れ換えて通算Ｍ回行う。Ｍ回の乗算結果は、加算回路３６とレジスタ３７を用いて逐次累積加算される。なお、レジスタ３７の内容は、相互相関値の計算開始時にクリアされる。
【０００６】
すなわち、本構成のシリアル型の相互相関値演算処理では、シフトレジスタ３１に新たな受信信号が１つ入力するごとに、乗算処理をＭ回、加算処理をＭ回行い、
【数１】
2010011391.tif 000003
で表される相互相関値Ｃs+1 が求められ、シフトレジスタ３８から出力される。そのため従来のシリアル型の相互相関値演算処理は、乗算回路３５および加算回路３６はともに受信信号の入力速度のＭ倍の速度で動作させる必要がある。例えば、受信信号の速度が 100ＭHz程度、Ｍ＝32の場合、乗算回路３５および加算回路３６は 3.2ＧHzもの高いクロック周波数で動作させることになり、消費電力が著しく増大する問題があった。
【０００７】
図１３は、従来の相互相関値演算回路の並列型の構成例を示す。図１４は、従来の相互相関値演算回路の並列型の動作例タイミングチャートを示す。
【０００８】
並列型の相互相関値演算回路は、式(1) の演算をＭ個の乗算回路からなる乗算回路アレー５１と、（Ｍ−１）個の加算回路からる加算回路ツリー５２を用いて並列演算する構成である。
【０００９】
シフトレジスタ３１は、時刻(ｓ＋１)において相互相関値の計算対象となるＭ個の受信信号の系列｛ｘs+1 ，ｘs+2 ，…，ｘs+M ｝を格納し、新たな受信信号を１つ受信するごとに最も古い受信信号を１つ破棄し、最新の受信信号を初段に格納する。レジスタ３２は、所定の信号パターンを表す疑似ランダム信号系列｛ｂ1 ，ｂ2 ，…，ｂM ｝を格納する。シフトレジスタ３１内のＭ個の受信信号（ｘs+i ）と、レジスタ３２内のＭ個の疑似ランダム信号（ｂi ）は、乗算回路アレー５１のＭ個の乗算回路で並列に乗算処理（ｘs+i ・ｂi ）され、さらに各乗算結果が加算回路ツリー５２の（Ｍ−１）個の加算回路で順次加算され、式(1) の相互相関値Ｃs+1 が並列演算によって求められ、シフトレジスタ３８から出力される。
【００１０】
このような従来の並列型の相互相関値演算回路は、Ｍ個の乗算回路と（Ｍ−１）個の加算回路が必要となり、Ｍが大きい場合には回路規模が増大し、生産コストおよび消費電力が上昇する問題があった。
【特許文献１】特開平０５−０４８５７１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来の相互相関値演算回路は、シリアル型および並列型ともに、受信信号系列内の全ての要素に対して、所定の疑似ランダム信号系列の要素と積和演算を行う必要があるため、対象となる疑似ランダム信号系列の長さが長い場合、演算回数あるいは回路規模が大きくなり消費電力が増大する。このため、無線端末などの電池駆動型装置に従来の相互相関値演算回路を搭載すると、装置の消費電力増大によって電池寿命が著しく短くなる問題があった。
【００１２】
本発明は、相互相関値の計算に必要な演算回路の数または演算回数を削減し、回路規模および消費電力がともに小さい相互相関値演算方法および相互相関値演算回路を提供することを目的とする。
【課題を解決するための手段】
【００１３】
第１の発明は、各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算方法において、  前記第１の信号系列の先頭および最後の要素を除く要素を差動符号化して第２の信号系列を生成し、この第２の信号系列と受信信号系列との間の相互相関計算による第１の演算値と、前回までの該第１の演算値の累積加算により得られた第２の演算値との和を新たな第２の演算値として計算する第１の演算ステップと、第１の信号系列の先頭の信号値と受信信号系列の先頭の信号値との積と、第１の演算ステップで得られた新たな第２の演算値とを加算して相互相関値を出力する第２のステップとを有し、受信信号系列が更新されるごとに、更新された受信信号系列に対して第１の演算ステップと第２の演算ステップを繰り返す。
【００１４】
第２の発明は、各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算方法において、第１の信号系列の各要素について、その先頭の要素が第１の信号系列の２番目の要素の符号を反転したものであり、次の要素が１つ後の要素と同符号の場合には当該要素を０に置き換え、１つ後の要素と同符号でない場合には当該要素を後の要素との差に置き換え、その最後の要素が第１の信号系列の最後の要素である第２の信号系列に変換し、この第２の信号系列の０以外の要素と、その要素の第２の信号系列内の位置と同じ位置関係にある受信信号系列の要素とを乗算し、第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して得られた第１の演算値と、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する第１の演算ステップと、第１の信号系列の先頭の要素と受信信号系列の先頭の要素との乗算の結果と、新たな第２の演算値とを加算して相互相関値を出力する第２の演算ステップととを有し、受信信号系列が更新されるごとに、更新された受信信号系列に対して第１の演算ステップと第２の演算ステップを繰り返す。
【００１５】
ここで、第１の信号系列の各要素について、１つ後の要素と同符号でない場合には後の要素との差が負のときは−１、正のときは＋１に置き換えて第２の信号系列に変換し、第１の演算ステップおよび第２の演算ステップにおける乗算をビットシフトと符号変換により行ってもよい。
【００１６】
第３の発明は、各要素が絶対値が等しく正または負の値をとる所定の系列長の第１の信号系列と、この第１の信号系列と同じ系列長の受信信号系列との間の相互相関値を計算する相互相関値演算回路において、第１の信号系列の各要素について、その先頭の要素が第１の信号系列の２番目の要素の符号を反転したものであり、次の要素が１つ後の要素と同符号の場合には当該要素を０に置き換え、１つ後の要素と同符号でない場合には当該要素を後の要素との差に置き換え、その最後の要素が第１の信号系列の最後の要素である第２の信号系列に変換し、この第２の信号系列の０以外の要素と、その要素の第２の信号系列内の位置と同じ位置関係にある受信信号系列の要素とを乗算し、第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して得られた第１の演算値と、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する第１の演算ブロックと、第１の信号系列の先頭の要素と受信信号系列の先頭の要素との乗算の結果と、新たな第２の演算値とを加算して相互相関値を出力する第２の演算ブロックとを備え、受信信号系列が更新されるごとに、更新された受信信号系列に対して第１の演算ブロックによる演算処理と第２の演算ブロックによる演算処理を繰り返す構成である。
【００１７】
第１の演算ブロックは、第１の信号系列から第２の信号系列に変換し、この第２の信号系列の０以外の要素を出力する変換回路と、第２の信号系列の０以外の要素を格納する第１の記憶回路と、第２の信号系列の０以外の要素と、その要素の第２の信号系列内の位置と同じ位置関係にある受信信号系列の要素との乗算を行う乗算回路と、第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して第１の演算値を出力し、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する加算回路および第２の記憶回路とを備え、第２の演算ブロックは、乗算回路を用いて第１の信号系列の先頭の要素と受信信号系列の先頭の要素との乗算を行い、加算回路および第２の記憶回路を用いて相互相関値を出力する構成である。
【００１８】
また、第１の演算ブロックは、第１の信号系列から第２の信号系列に変換し、この第２の信号系列の０以外の要素を出力する変換回路と、第２の信号系列の０以外の要素を格納する第１の記憶回路と、第２の信号系列の０以外のすべての要素と、それぞれの要素の第２の信号系列内の位置と同じ位置関係にある受信信号系列の要素との乗算を行う乗算回路アレーと、第２の信号系列の０以外のすべての要素に対して行った乗算の結果を累積加算して第１の演算値を出力し、前回までの該第１の演算値を累積加算して得られた第２の演算値との和を新たな第２の演算値として計算する加算回路ツリーおよび第２の記憶回路とを備え、第２の演算ブロックは、第１の信号系列の先頭の要素と受信信号系列の先頭の要素との乗算を行う乗算回路と、第１の信号系列の先頭の要素と受信信号系列の先頭の要素との乗算の結果と、新たな第２の演算値とを加算して相互相関値を出力する加算回路とを備える。
【００１９】
ここで、変換回路は、第１の信号系列の各要素について、１つ後の要素と同符号でない場合には後の要素との差が負のときは−１、正のときは＋１に置き換えて第２の信号系列に変換する構成であり、乗算回路または乗算回路アレーを構成する乗算回路は、乗算処理をビットシフトと符号変換により行う構成としてもよい。
【発明の効果】
【００２０】
本発明は、所定の系列長の第１の信号系列（例えば疑似ランダム信号系列など）を差動符号化によって系列長の短い第２の信号系列に変換し、この第２の信号系列と受信信号系列との間で中間的な演算を逐次行い、得られた第１の演算値を受信信号ごとに再帰的に利用することにより、相互相関値計算あたりの演算回路数および演算回数を削減する。これにより、回路規模と消費電力をともに削減した相互相関値演算回路を実現することができる。
【発明を実施するための最良の形態】
【００２１】
（第１の実施形態）
図１は、本発明の相互相関値演算回路の第１の実施形態を示す。
図において、本実施形態の相互相関値演算回路は、シフトレジスタ３１、レジスタ３２、演算ブロックＡ１０、レジスタ１１、演算ブロックＢ２０により構成される。シフトレジスタ３１は、時刻（ｓ＋１）において相互相関値の計算対象となるＭ個の受信信号の系列｛ｘs+1 ，ｘs+2 ，…，ｘs+M ｝を格納し、新たな受信信号を１つ受信するごとに最も古い受信信号を１つ破棄し、最新の受信信号を初段に格納する。レジスタ３２は、所定の信号パターンを表す疑似ランダム信号系列｛ｂ1 ，ｂ2 ，…，ｂM ｝を格納する。
【００２２】
演算ブロックＡ１０は、受信信号系列が更新されるごとに、シフトレジスタ３１内の受信信号系列と、レジスタ３２内の疑似ランダム信号系列と、レジスタ１１に格納されている演算ブロックＡ１０における前回の中間的な演算結果Ｐs とを入力し、中間的な演算結果Ｐs+1 を生成してレジスタ１１に格納する。演算ブロックＢ２０は、受信信号系列が更新されるごとに、シフトレジスタ３１内の受信信号系列ｘs+1 と、レジスタ３２内の疑似ランダム信号系列ｂ1 と、演算ブロックＡ２０の中間的な演算結果Ｐs+1 とを入力し、相互相関値Ｃs+1 を計算して出力する。
【００２３】
図２は、本発明の相互相関値演算回路の第１の実施形態の動作例タイミングチャートを示す。演算ブロックＡ１０と演算ブロックＢ２０は、受信信号系列が更新されるごとに、それぞれ中間的な演算結果Ｐs ，Ｐs+1 と、相互相関値Ｃs ，Ｃs+1 を生成する。
【００２４】
ここで、演算ブロックＡ１０と演算ブロックＢ２０における演算処理について説明する。時刻ｓにおいてシフトレジスタ３１内に格納されている受信信号の系列Ｄs をＭ行１列の行列で
【数２】
2010011391.tif 000004
と表す。レジスタ３２に格納している疑似ランダム信号の系列Ｂを１行Ｍ列の行列で
Ｂ＝ [ｂ1   ｂ2   …  ｂM ]           …(3) 
と表す。
【００２５】
時刻（ｓ＋１）の受信信号系列Ｄs+1 に対する演算ブロックＡ１０の演算結果Ｐs+1 を次式により求める。なお、時刻（ｓ＋１）の受信信号系列Ｄs+1 は、時刻ｓの受信信号系列Ｄs の各要素を上方に１要素分シフトし、その先頭要素ｘs を破棄するとともに、その末尾の要素に新たな受信信号ｘs+M が挿入される。
【数３】
2010011391.tif 000005
【００２６】
ここで、Ｇはその要素｛ｇ1 ，ｇ2 ，…，ｇM ｝について、疑似ランダム信号Ｂを次式のように差動符号化変換して求めた１行Ｍ列の行列である。
【数４】
2010011391.tif 000006
すなわち、式(5) で表される系列Ｇは、疑似ランダム信号Ｂの先頭と末尾の要素を除いた中間の要素ｂk （ｋ＝２，３，…，Ｍ−１）が、自身の１つ後の要素ｂk+1 と同じ符号であれば、要素ｇk を０とすることが特徴である。
【００２７】
演算ブロックＡ１０の演算結果Ｐs+1 は、式(4) を再帰的に適用することにより、２番目から（ｓ＋１）番目までの受信信号系列｛Ｄ2 ，Ｄ3 ，…，Ｄs+1 ｝と、２番目からＭ番目までの受信信号｛ｘ2 ，ｘ3 ，…，ｘM ｝を用いて
【数５】
2010011391.tif 000007
と表される。
【００２８】
次に、時刻（ｓ＋１）の受信信号系列Ｄs+1 に対する演算ブロックＢ２０の演算結果である相互相関値Ｃs+1 は、
Ｃs+1 ＝Ｐs+1 ＋ｘs+1ｂ1       …(7) 
と求められる。
【００２９】
以上により求めた相互相関値Ｃs+1 と、従来方法の式(1) で与えられる値が等しいことについて以下に説明する。式(1) から
【数６】
2010011391.tif 000008
【００３０】
式(11)の両辺の和をとると、
【数７】
2010011391.tif 000009
【００３１】
ここで、式(5) のｇk を用いることにより、
【数８】
2010011391.tif 000010
式(6),(13)から
Ｃs+1 ＝Ｐs+1 ＋ｘs+1ｂ1                                  …(14)
となる。よって、式(1) は、式(7) と同値であることが示された。すなわち、本実施形態の手法を用いても、正しい相互相関値が得られることが証明される。
【００３２】
演算ブロックＡ１０における演算回数は、式(4) を用いて求めることができる。疑似ランダム信号Ｂを式(5) に基づいて変換したＧの要素｛ｇ1 ，ｇ2 ，…，ｇM ｝がすべてゼロでない場合、受信信号系列Ｄs+1 の行列積においてＭ回の乗算と（Ｍ−１）回の加算が必要である。また、受信信号系列Ｄs+1 の行列積と中間的な演算結果Ｐs+1 との和を求めるのに１回の加算が必要である。すなわち、演算ブロックＡ１０では、Ｍ回の加算とＭ回の乗算が必要となる。一方、Ｇの要素にゼロがある場合、１つのゼロ要素につき、行列積を求める際の乗算と加算を１回ずつ省略することができる。Ｇの要素のゼロでない要素数をＬで表すと、演算ブロックＡ１０において中間的な演算結果Ｐs+1 を求めるのに必要な演算回数は、乗算がＬ回、加算がＬ回となる。
【００３３】
演算ブロックＢ２０における演算回数は、式(7) を用いて求めることができる。Ｇのゼロでない要素数に関係なく、相互相関値Ｃs+1 あたり乗算１回、加算１回となる。相互相関値Ｃs+1 あたりの回路全体の演算回数は、演算ブロックＡ１０と演算ブロックＢ２０のそれぞれの演算回数の和となるため、乗算および加算の回数はそれぞれ（Ｌ＋１）回となる。
【００３４】
このように、本実施形態では受信信号系列が更新されるごとに、目的とする相互相関値Ｃs+1 とは別に、少ない演算回数で生成される中間的な演算結果Ｐs+1 をレジスタ１１に格納する。相互相関値Ｃs+1 は、この中間的な演算結果Ｐs+1 から少ない演算回数で求めることができるので、全体として相互相関値あたりの演算回数を大幅に削減することができる。
【００３５】
代表的な系列長Ｍの疑似ランダム信号Ｂに対して、本実施形態における相互相関値あたりの演算回数を表１の第４列に示す。比較のために、従来構成における相互相関値あたりの演算回数を第５列に示す。従来構成における相互相関値あたりの演算回数は、式(1) から乗算Ｍ回、加算Ｍ回となる。一方、本実施形態の構成では、相互相関値あたりの演算回数は乗算（Ｌ＋１）、加算（Ｌ＋１）回となるので、ほぼ半減できることがわかる。
【００３６】
【表１】
2010011391.tif 000011
【００３７】
（第２の実施形態）
図３は、本発明の相互相関値演算回路の第２の実施形態（シリアル型）の構成例を示す。
図において、シフトレジスタ３１、レジスタ３２、演算ブロックＡ１０、レジスタ１１、演算ブロックＢ２０は、図１に示す第１の実施形態のそれぞれに対応する。演算ブロックＡ１０は、変換回路１２、レジスタ１３、選択回路１４，１５、乗算回路１６および加算回路１７により構成される。演算ブロックＢ２０は、演算ブロックＡ１０の乗算回路１６および加算回路１７を共用し、さらにレジスタ２１を加えた構成である。
【００３８】
シフトレジスタ３１は、Ｍ個の受信信号系列｛ｘs+1 ，ｘs+2 ，…，ｘs+M ｝を格納し、新たな受信信号を１つ受信するごとにその内容を更新する。レジスタ３２は、所定の信号パターンを表す疑似ランダム信号系列Ｂ｛ｂ1 ，ｂ2 ，…，ｂM ｝を格納する。
【００３９】
変換回路１２は、レジスタ３２の疑似ランダム信号系列Ｂを式(5) に従って変換し、生成された系列Ｇのうちゼロでない要素数をＬとし、各要素を｛ｇp1，ｇp2，…，ｇpL｝をレジスタ１３に格納する。選択回路１５は、レジスタ１３から１要素ずつ選択して乗算回路１６に出力する。一方、選択回路１４は、シフトレジスタ３１に格納された受信信号系列から、ゼロでない系列Ｇの要素に対応するアドレス｛ｐ1 ，ｐ2 ，…，ｐL ｝の要素｛ｘs+pk，ｋ＝１，２，…，Ｌ｝を１要素ずつ選択して乗算回路１６に出力する。乗算回路１６は選択回路１４，１５の各出力を乗算し、加算回路１７は乗算回路１６の出力と、レジスタ１１に格納されている前回の中間的な演算結果Ｐs とを加算して中間的な演算結果Ｐs+1 をレジスタ１１に格納する。
【００４０】
次に、選択回路１５がレジスタ３２に格納された疑似ランダム信号ｂ1 を選択し、選択回路１４がシフトレジスタ３１に格納された受信信号ｘs+1 を選択する。乗算回路１６はその乗算結果を加算回路１７に出力し、加算回路１７はレジスタ１１に格納されている前回の中間的な演算結果Ｐs+1 を加算し、相互相関値Ｃs+1 としてレジスタ２１に格納する。制御回路３９は、シフトレジスタ３１に格納された受信信号系列の更新、各レジスタの格納タイミングを制御する。
【００４１】
なお、レジスタ３２に格納される疑似ランダム信号系列Ｂは予め決められており、相互相関値演算中に動的に変化することはない。このため、事前に式(5) に従って系列Ｇを生成してレジスタ１３に格納しておいてもよい。
【００４２】
図４は、本発明の相互相関値演算回路の第２の実施形態の動作例タイミングチャートを示す。乗算回路１６、加算回路１７およびレジスタ１１は、受信信号が新たに入力されるごとに制御回路３９の制御により時分割で、式(4) および式(7) に示す演算を以下のように実施する。
【００４３】
(1) 最初のＬサイクル期間に、選択回路１４，１５、乗算回路１６、加算回路１７、レジスタ１１は、式(4) に示す計算を行い、中間的な演算結果Ｐs+1 をレジスタ１１に格納する。１サイクルごとに系列Ｇの非ゼロ要素と受信信号系列Ｄs+1 の要素の積をとり、同時に累積加算する。ここで、系列Ｇのアドレスと受信信号系列Ｄs+1 のアドレス｛ｐ1 ，ｐ2 ，…，ｐL ｝が選択回路１４，１５で選択される。
【００４４】
(2) 次の１サイクル期間に、選択回路１４，１５、乗算回路１６、加算回路１７、レジスタ１１は、式(7) に示す計算を行い、相互相関値Ｃs+1 をレジスタ２１に格納する。
【００４５】
なお、相互相関値Ｃs+1 の計算に必要な時間を図４にＴnew として模式的に示す。受信信号系列Ｄs+1 内のゼロでない要素数をＬとすると、相互相関値Ｃs+1 の計算に必要な乗算回数は、式(4) と式(7) から行列式ＧＤs+1 の計算にＬ回、ｘs+1ｂ1の計算に１回の合計（Ｌ＋１）回となる。また、Ｃs+1 の計算に必要な加算回数は、式(4) と式(7) から行列式ＧＤs+1 の計算に（Ｌ−１）回、Ｐs との和に１回、ｘs+1ｂ1との和に１回の合計（Ｌ＋１）回となる。すなわち、表１の第４列のような演算回数になる。
【００４６】
一方、図１１に示す従来回路では、相互相関値Ｃs+1 の計算に必要な乗算回数および加算回路はともにＭ回となる。表１から、Ｌは疑似ランダム信号系列Ｂの長さの約半分となるので、本実施形態の演算回数は従来回路の約半分となる。これにより、演算時間をほぼ半減でき、相互相関値演算回路の消費電力を著しく削減することができる。
【００４７】
（第３の実施形態）
図５は、本発明の相互相関値演算回路の第３の実施形態（並列型）の構成例を示す。
図において、シフトレジスタ３１、レジスタ３２、演算ブロックＡ１０、レジスタ１１、演算ブロックＢ２０は、図１に示す第１の実施形態のそれぞれに対応する。演算ブロックＡ１０は、変換回路１２、レジスタ１３、選択回路１４、乗算回路アレー１８および加算回路ツリー１９により構成される。演算ブロックＢ２０は、乗算回路２２および加算回路２３により構成される。
【００４８】
シフトレジスタ３１，レジスタ３２、変換回路１２およびレジスタ１３は、第２の実施形態のものと同じである。選択回路１４は、シフトレジスタ３１に格納された受信信号から、そのアドレスが、ゼロでない系列Ｇの要素の指数と一致するもの、すなわち｛ｐ1 ，ｐ2 ，…，ｐL ｝であるものを選択して乗算回路アレー１８に入力する。図５(2) に示す乗算回路アレー１８は、系列Ｇのうちゼロでない要素数のＬ個の２入力１出力の乗算回路をアレー状に並べた構成であり、選択回路１４およびレジスタ１３の各出力を並列に乗算処理する。
【００４９】
図５(3) に示す加算回路ツリー１９は、乗算回路アレー１８から出力されるＬ個の信号値と、レジスタ１１に格納された中間値Ｐs の総和をとるため、Ｌ個の加算回路をツリー状に配置した構成である。加算回路ツリー１９から出力される中間的な演算結果Ｐs+1 はレジスタ１１に格納される。なお、図示していないが、加算回路ツリー１９における桁上げ処理は適切に行われるものとする。制御回路３９は、シフトレジスタ３１に格納された受信信号系列の更新、各レジスタの格納タイミングを制御する。
【００５０】
また、乗算回路２２は、シフトレジスタ３１内の受信信号系列の１番目の要素ｘs+1 と、レジスタ３２内の疑似ランダム信号系列Ｂの１番目の要素ｂ1 とを乗算する。加算回路２３は、加算回路ツリー１９から出力される中間値Ｐs+1 と乗算回路２２の出力を加算し、式(7) に従って相互相関値Ｃs+1 を出力する。
【００５１】
図６は、本発明の相互相関値演算回路の第３の実施形態の動作例タイミングチャートを示す。本実施形態は並列処理のため、受信信号が新たに入力されるのとほぼ同時に相互相関値が生成される。
【００５２】
本実施形態における相互相関値Ｃs+1 の計算に必要な乗算回路数および加算回路数を従来回路と比較して表２に示す。図５(2) から、本実施形態の乗算回路アレー１８内の乗算回路数はＬである。これに、演算ブロックＢ２０を構成する乗算回路２２を加えて合計（Ｌ＋１）個となる。また、本実施形態の（Ｌ＋１）入力の加算回路ツリー１９内の加算回路数はＬである。これに、演算ブロックＢ２０を構成する加算回路２３を加えて合計（Ｌ＋１）個となる。表２から、Ｌは疑似ランダム信号系列Ｂの長さの約半分となるので、本実施形態の演算回路数は従来回路数の約半分となる。これにより、相互相関値演算回路の回路規模および消費電力を著しく削減することができる。
【００５３】
【表２】
2010011391.tif 000012
【００５４】
（第４の実施形態）
図７は、本発明の相互相関値演算回路の第４の実施形態（シリアル型）の構成例を示す。
本実施形態は、図３に示す第２の実施形態の変換回路１２に代えて変換回路４１と、乗算回路１６に代えてビットシフト・符号変換回路４２を用いたことを特徴とする。
【００５５】
本実施形態の変換回路４１は、疑似ランダム信号系列Ｂの各要素の絶対値が１であるので、これを変換して得た系列Ｇの各要素を以下のように求める。ここで、sign(x) は、ｘが負のとき−１、ｘが正のとき＋１、ｘが０のとき０とする。
【数９】
2010011391.tif 000013
【００５６】
すなわち、変換回路４１は、レジスタ３２の疑似ランダム信号系列Ｂを式(15)に従って変換し、生成された系列Ｇのうちゼロでない要素数をＬとし、＋１，−１で表される各要素｛ｇp1，ｇp2，…，ｇpL｝をレジスタ１３に格納する。選択回路１５は、レジスタ１３から１要素ずつ選択してビットシフト・符号変換回路４２に入力する。一方、選択回路１４は、シフトレジスタ３１に格納された受信信号系列から、ゼロでない系列Ｇの要素に対応するアドレス｛ｐ1 ，ｐ2 ，…，ｐL ｝の要素｛ｘs+pk，ｋ＝１，２，…，Ｌ｝を１要素ずつ選択してビットシフト・符号変換回路４２に入力する。
【００５７】
ビットシフト・符号変換回路４２はこのようにして入力するＬ組の対｛（ｇpk，ｘs+pk），ｋ＝１，２，…，Ｌ｝に対して、次の演算を行い、それぞれの結果ｙpkを順番に加算回路１７に入力する。
【数１０】
2010011391.tif 000014
【００５８】
ここで、leftshift(ｘs+pk) は、２の補数表示された数値ｘに対し、符号ビットを除くすべてのビットをＬＳＢ側からＭＳＢ側に１ビットシフトして得られる２進数を表す。なお、ＬＳＢには０を入力するものとする。さらにｇpkの乗算が符号変換となり、ｇpk＝＋１の場合は符号反転なし、ｇpk＝−１の場合は符号反転となる。これにより、第２の実施形態における系列Ｇの中で絶対値が２となる要素と受信信号系列との乗算処理が、本実施形態では、変換回路４１とビットシフト・符号変換回路４２の演算により実現される。すなわち、絶対値２の情報は不要となり、符号情報だけで対応可能となる。
【００５９】
次に、選択回路１５がレジスタ３２に格納された疑似ランダム信号ｂ1 を選択し、選択回路１４がシフトレジスタ３１に格納された受信信号ｘs+1 を選択する。ビットシフト・符号変換回路４２は sign(ｂ1)・ｘs+1 の計算を符号変換により行い、加算回路１７に入力する。
【００６０】
図８は、本発明の相互相関値演算回路の第４の実施形態の動作例タイミングチャートを示す。ビットシフト・符号変換回路４２、加算回路１７およびレジスタ１１は、受信信号が新たに入力されるごとに制御回路３９の制御により時分割で、式(4) および式(7) に示す演算を以下のように実施する。
【００６１】
(1) 最初のＬサイクル期間に、選択回路１４，１５、ビットシフト・符号変換回路４２、加算回路１７、レジスタ１１は、式(4) に示す計算を行う。具体的には式(16)に示す演算をＬ回実施し、加算回路１７とレジスタ１１を用いて、これらＬ個の計算値とレジスタ１１内の初期値Ｐs との累積和を計算する。得られた累積和をＰs+1 としてレジスタ１１に格納する。
【００６２】
(2) 次の１サイクル期間に、選択回路１４，１５、ビットシフト・符号変換回路４２、加算回路１７、レジスタ１１は、式(7) に示す計算を行う。具体的には、シフトレジスタ３１からｘs+1 を選択し、レジスタ３２からｂ1 を選択し、ビットシフト・符号変換回路４２で sign(ｂ1)・ｘs+1 を計算し、加算回路１７とレジスタ１１を用いて、前回の中間的な演算結果Ｐs+1 を加算する。そして得られた値を相互相関値Ｃs+1 としてレジスタ２１に格納する。
【００６３】
以上の演算は、受信信号が新たに入力するごとに実施され、中間的な演算結果Ｐs+1 がレジスタ１１に格納され、相互相関値Ｃs+1 がレジスタ２１に格納される。
【００６４】
本実施形態では、式(16)に示すように、乗算処理を演算負荷の軽いビットシフトと符号変換だけで実現できる。このため、本実施形態の構成は、相互相関値あたりの演算量を第２の実施形態の構成に比べて大幅に減少させることができ、相互相関値演算回路の回路規模および消費電力を著しく削減することができる。
【００６５】
（第５の実施形態）
図９は、本発明の相互相関値演算回路の第５の実施形態（並列型）の構成例を示す。
本実施形態は、図５に示す第３の実施形態の変換回路１２に代えて変換回路４１と、演算ブロックＡ１０の乗算回路アレー１８に代えてビットシフト・符号変換回路アレー４３を用い、演算ブロックＢ２０の乗算回路２２に代えてビットシフト・符号変換回路４４を用いたことを特徴とする。
【００６６】
本実施形態の変換回路４１は、第４の実施形態と同様に、レジスタ３２の疑似ランダム信号系列Ｂを式(15)に従って変換し、生成された系列Ｇのうちゼロでない要素数をＬとし、＋１，−１で表される各要素｛ｇp1，ｇp2，…，ｇpL｝をレジスタ１３に格納する。レジスタ１３の各要素はビットシフト・符号変換回路アレー４３に入力する。一方、選択回路１４は、シフトレジスタ３１に格納された受信信号系列から、ゼロでない系列Ｇの要素に対応するアドレス｛ｐ1 ，ｐ2 ，…，ｐL ｝の要素｛ｘs+pk，ｋ＝１，２，…，Ｌ｝を選択してビットシフト・符号変換回路アレー４３に入力する。
【００６７】
図９(2) に示すビットシフト・符号変換回路アレー４３は、系列Ｇのうちゼロでない要素数のＬ個に対応するビットシフト・符号変換回路をアレー状に並べた構成であり、選択回路１４およびレジスタ１３の各出力を並列に乗算処理する。各ビットシフト・符号変換回路の処理は、第４の実施形態に示すビットシフト・符号変換回路４１と同様であり、第３の実施形態における系列Ｇの中で絶対値が２となる要素と受信信号系列との乗算処理が、本実施形態では、変換回路１２とビットシフト・符号変換回路アレー４３の演算により実現される。すなわち、絶対値２の情報は不要となり、符号情報だけで対応可能となる。  
【００６８】
図９(3) に示す加算回路ツリー１９は、ビットシフト・符号変換回路アレー４３から出力されるＬ個の信号値と、レジスタ１１に格納された中間値Ｐs の総和をとるため、Ｌ個の加算回路をツリー状に配置した構成である。加算回路ツリー１９から出力される中間的な演算結果Ｐs+1 はレジスタ１１に格納される。なお、図示していないが、加算回路ツリー１９における桁上げ処理は適切に行われるものとする。制御回路３９は、シフトレジスタ３１に格納された受信信号系列の更新、各レジスタの格納タイミングを制御する。
【００６９】
また、ビットシフト・符号変換回路４４は、シフトレジスタ３１内の受信信号系列の１番目の要素ｘs+1 と、レジスタ３２内の疑似ランダム信号系列Ｂの１番目の要素ｂ1 との乗算処理をビットシフトと符号変換により行う。加算回路２３は、加算回路ツリー１９から出力される中間値Ｐs+1 とビットシフト・符号変換回路４４の出力を加算し、式(7) に従って相互相関値Ｃs+1 を出力する。
【００７０】
図１０は、本発明の相互相関値演算回路の第５の実施形態の動作例タイミングチャートを示す。本実施形態は並列処理のため、受信信号が新たに入力されるのとほぼ同時に相互相関値が生成される。
【００７１】
本実施形態における相互相関値Ｃs+1 の計算に必要な乗算回路数および加算回路数を従来回路と比較して表３に示す。図９(2) から、本実施形態のビットシフト・符号変換回路アレー４３およびビットシフト・符号変換回路４４の乗算回路数は０である。また、本実施形態の（Ｌ＋１）入力の加算回路ツリー１９内の加算回路数はＬである。これに、演算ブロックＢ２０を構成する加算回路２３を加えて合計（Ｌ＋１）個となる。
【００７２】
【表３】
2010011391.tif 000015
【００７３】
本実施形態では、式(16)に示すように、乗算処理を演算負荷の軽いビットシフトと符号変換だけで実現できる。このため、本実施形態の構成は、相互相関値あたりの演算量を第３の実施形態の構成に比べて大幅に減少させることができ、相互相関値演算回路の回路規模および消費電力を著しく削減することができる。
【００７４】
なお、以上の説明では、受信信号と比較するための所定の信号パターンとして系列長Ｍの疑似ランダム信号系列を用いて説明したが、所定の信号パターンはこれに限定されるものではなく、ランダムな信号系列であればどのような信号パターンであってもよい。
【図面の簡単な説明】
【００７５】
【図１】本発明の相互相関値演算回路の第１の実施形態を示す図。
【図２】本発明の相互相関値演算回路の第１の実施形態の動作例を示すタイミングチャート。
【図３】本発明の相互相関値演算回路の第２の実施形態を示す図。
【図４】本発明の相互相関値演算回路の第２の実施形態の動作例を示すタイミングチャート。
【図５】本発明の相互相関値演算回路の第３の実施形態を示す図。
【図６】本発明の相互相関値演算回路の第３の実施形態の動作例を示すタイミングチャート。
【図７】本発明の相互相関値演算回路の第４の実施形態を示す図。
【図８】本発明の相互相関値演算回路の第４の実施形態の動作例を示すタイミングチャート。
【図９】本発明の相互相関値演算回路の第５の実施形態を示す図。
【図１０】本発明の相互相関値演算回路の第５の実施形態の動作例を示すタイミングチャート。
【図１１】従来の相互相関値演算回路のシリアル型の構成例を示す図。
【図１２】従来の相互相関値演算回路のシリアル型の動作例を示すタイミングチャート。
【図１３】従来の相互相関値演算回路の並列型の構成例を示す図。
【図１４】従来の相互相関値演算回路の並列型の動作例を示すタイミングチャート。
【符号の説明】
【００７６】
１０  演算ブロックＡ
１１  レジスタ
１２  変換回路
１３  レジスタ
１４，１５  選択回路
１６  乗算回路
１７  加算回路
１８  乗算回路アレー
１９  加算回路ツリー
２０  演算ブロックＢ
２１  レジスタ
２２  乗算回路
２３  加算回路
３１  シフトレジスタ
３２  レジスタ
３３，３４  選択回路
３５  乗算回路
３６  加算回路
３７，３８  レジスタ
４１  変換回路
４２，４４  ビットシフト・符号変換回路
４３  ビットシフト・符号変換回路アレー
５１  乗算回路アレー
５２  加算回路ツリー
１００  制御回路
【図１】
2010011391.tif 000016
【図２】
2010011391.tif 000017
【図３】
2010011391.tif 000018
【図４】
2010011391.tif 000019
【図５】
2010011391.tif 000020
【図６】
2010011391.tif 000021
【図７】
2010011391.tif 000022
【図８】
2010011391.tif 000023
【図９】
2010011391.tif 000024
【図１０】
2010011391.tif 000025
【図１１】
2010011391.tif 000026
【図１２】
2010011391.tif 000027
【図１３】
2010011391.tif 000028
【図１４】
2010011391.tif 000029