(57)【特許請求の範囲】
【請求項１】
予め定義された第１複数のビットを含み複数のシフトした２進符号語と、対応する複数の連続する入力信号サンプルとの間の相関を生成する方法であって、前記複数のシフトした２進符号語の各シフトでは、前記複数の連続する入力信号サンプルに対して異なる数のビット位置だけシフトされている、前記方法において
第１複数の部分完成相関を第１の記憶位置に格納するステップと、
前記第１複数のビットよりも少ない第２複数の前記入力信号サンプルを第２の記憶位置へ入力するステップと、
前記第２複数の入力信号サンプルと正負符号の可能なパターンとの所定の複数の可能なサンプル組み合わせに対して、前記第２複数の入力信号サンプルと正負符号の可能なパターンとの前記可能なサンプル組み合わせの第１半数が前記可能なサンプル組み合わせの第２半数と負の関係になることから、前記可能なサンプル組み合わせの第１半数を選択し、且つ、前記複数の可能な組み合わせから１つのサンプル組み合わせを選択する１つの対応する計算されたサンプル組み合わせを生成するために、前記選択された第１半数の可能なサンプル組み合わせの各々に前記第２の記憶位置に記憶された前記第２複数の入力信号サンプルを組み合わせるステップであって、前記選択されたサンプル組み合わせの各入力信号サンプルの正負符号が前記複数のシフトした２進符号語の特定のシフト位置の各ビットの符号に対応する、前記ステップと、
前記選択されたサンプル組み合わせが前記可能なサンプル組み合わせから選択された第１半数の構成要素の補数に対応する場合は、相補的なサンプル組み合わせを選択して、第２複数の部分完成相関及び１つの完成相関を生成するために、前記選択されたサンプル組み合わせに対応する前記計算されたサンプル組み合わせを、前記複数のシフトした２進符号語の特定のシフトに対応する前記第１の記憶位置に記憶された第１複数の部分完成相関中の１つの特定の部分完成相関から減算するステップと、
前記選択されたサンプル組み合わせが前記可能なサンプル組み合わせから選択された第１半数の構成要素に対応する場合は、前記組み合わせを選択して、第２複数の部分完成相関及び１つの完成相関を生成するために、前記選択されたサンプル組み合わせに対応する前記計算されたサンプル組み合わせを、前記複数のシフトした２進符号語の特定のシフトに対応する前記第１の記憶位置に記憶された第１複数の部分完成相関中の１つの特定の部分完成相関に加算するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１記載の方法であって、さらに、
前記第２複数の前記入力信号サンプル中の選択された複数の入力信号サンプルを選択された第２複数の前記部分完成相関と組み合わせて、完成相関の合計数が前記第２複数の部分完成相関と等しい複数の完成相関を発生するステップと、
前記第２複数の前記入力信号サンプルに応答して、新しい第１複数の部分完成相関を生成するステップと、
前記記載の全ステップを繰り返すステップと、を含むことを特徴とする方法。
【請求項３】
請求項２記載の方法であって、複数の完成相関を生成するための前記選択された第１半数の可能なサンプル組み合わせの各々の前記入力信号サンプルの前記組み合わせは、正負符号を選択するグレイ符号順序付けに応じて計算されることを特徴とする方法。
【請求項４】
請求項３記載の方法であって、
前記サンプル組み合わせの少なくとも１つは、前記第２複数の入力信号サンプルの１つの値を２回加算もしくは２回減算することによって、予め計算されている値から計算されることを特徴とする方法。
【請求項５】
請求項３記載の方法であって、
前記計算された組み合わせに続く前記サンプル組み合わせの全てが、前記第２複数の入力信号サンプルの１つの値を２回加算もしくは２回減算することによって、既に計算されている値から誘導されることを特徴とする方法。
【請求項６】
予め定義された第１複数のビットを含み複数のシフトした２進符号語と、対応する複数の連続する入力信号サンプルとの間の相関を生成する相関器であって、前記複数のシフトした２進符号語の各シフトでは、前記複数の連続する入力信号サンプルに対して異なる数のビット位置だけシフトされている、前記相関器において、
クロック信号に応答して各構成要素の同期をとるためのタイミング信号を出力するタイミングコントローラ（２０）と、
入力信号を格納する入力信号記憶装置（２７）と、
前記入力信号記憶装置（２７）の出力に接続されて、前記入力信号を前記第１複数のビットよりも少ない第２複数の入力信号の単位でサンプリングするラッチ（２６）と、
前記ラッチ（２６）、マッピング論理手段（２３）、および前記入力信号記憶装置（２７）の出力に接続されて、前記マッピング論理手段（２３）から発生される符号パターンに基づいて前記入力信号のサンプル組合せを選択する信号結合および選択手段（２５）と、
前記信号結合および選択手段（２５）の入力および前記タイミングコントローラ（２０）の出力に接続されて、前記入力信号と相関される前記第２複数の２進符号語のビットパターンに基づいて、グレイ符号順序付けとなるように前記ビットパターンの半数の前記符号パターンと符号変更器（２４）での加算と減算を選択するコマンドとを発生する前記マッピング論理手段（２３）と、
前記マッピング論理手段（２３）、前記信号結合および選択手段（２５）、出力信号記憶手段（２１）、および前記タイミングコントローラ（２０）に接続されて、前記信号結合および選択手段（２５）から入力される前記入力信号のサンプル組合せと前記出力信号記憶手段（２１）から読み出される一時的に格納された部分相関とを、前記マッピング論理手段（２３）からの前記加算と減算を選択するコマンドに対応して加算または減算して、計算結果を前記出力信号記憶手段（２１）に再書き込みする前記符号変更器（２４）と、
前記出力信号記憶手段（２１）および前記タイミングコントローラ（２０）に接続されて、前記出力信号記憶手段（２１）のアドレッシングに使用される前記第２複数の単位で更新されるアドレスオフセット値を記憶するアドレスオフセット記憶手段（２２）と、
前記アドレスオフセット記憶手段（２２）、前記符号変更器（２４）、および前記タイミングコントローラ（２０）に接続され、前記符号変更器（２４）で更新された部分相関及び完成相関の前記第１複数の出力値を一時的に格納し、前記アドレスオフセット記憶手段（２２）からのアドレスオフセット値を使用して、前記部分相関の出力値を前記符号変更器（２４）に出力すると共に前記完成相関の出力値を当該相関器の出力値として出力するアドレス巡回型の前記出力信号記憶手段（２１）と、
を含むことを特徴とする相関器。
【発明の詳細な説明】
【０００１】
（発明の背景）
(発明の技術分野)
本発明は一般的に電気通信分野に関し、特に、デジタル相関器を利用してノイズ内の所定のデジタル符号の存在を検出する、スペクトル拡散受信機、パケットデータ受信機、等の通信装置もしくは周波数ホッピング応用における通信装置に関する。
【０００２】
(関連技術の説明)
図１は受信した最後のＭ信号サンプルとＭ−ビット符号語間の相関を計算するのに使用される従来技術の相関器のブロック図である。Ｍ−要素遅延線１０が受信信号サンプルを格納しＭステージの各々を介してそれらを逐次シフトする。したがって、遅延線メモリ要素は受信した最後のＭ信号サンプルを含んでいる。新しい各サンプルがシフトインされ古いサンプルがシフトアウトされた後で、Ｍサンプル値が遅延線からＭ信号チェンジャー１２へ読み出され、そこで相関が計算される所定符号のビットｂ1．．．．．ｂMに従ってＭサンプル値に＋１もしくは−１が乗じられる。次に符号変化した値が加算器１３で合計されて相関結果が得られる。
【０００３】
一般的に、Ｍ−要素ベクトルＡ＝（ａ１，ａ２．．．．ａＭ）とＭ−要素ベクトルＢ＝（ｂ１，ｂ２．．．．ｂＭ）の相関過程には内積Ａ・Ｂ＝ａ１・ｂ１＋ａ２・ｂ２＋．．．．．ａＭ・ｂＭを形成することが含まれる。一方のベクトル（例えば、Ｂ）が２進値（数学的に、＋１もしくは−１）だけで構成される場合には、ａ１・ｂ１等の積は±ａ１に簡約されるが、Ｍ値の加算過程±ａ１±ａ２．．．．．±ａＭは受信する“ａ”の新しい各値について実施しなければならない場合には大変な計算量（ｅｆｆｏｒｔ）である。
【０００４】
従来技術は図１に示す相関器の多くのバリエーションを含んでいる。例えば、信号サンプルは１ビットあるいは多ビット量の替わりの＋１もしくは−１の“ハードリミット”量とすることができる。そこで使用される符号チェンジャーは典型的には単純なＸＯＲゲートである。その場合、加算器１３は最初に１ビット値の対を加算してＭ／２の２ビット値を得、次にＭ／４の２ビット加算器が２ビット値を加算してＭ／４の３ビット値を得、以下同様とされる。“加算器ツリー”として知られるこのような構造は入力値が多ビット値ではなく１ビット値であればより単純となる。
【０００５】
1ビット値信号サンプルに対して、加算器ツリーはＭ値を走査して＋１に出会ったらアップカウントし−１に出会ったらダウンカウントするアップダウンカウンタで置換することができる。同様に、多ビット値信号サンプルに対して、並列加算器ツリーは遅延線メモリからＭ値の各々を順に抽出してアキュムレータに加える逐次加算器で置換することができる。後者の場合、利用される論理は並列加算器の場合よりもＭ倍高速で動作しなければならない。したがって、相関器の全体速度と論理の複雑さとの間にはトレードオフがある。それにもかかわらず、前記した従来技術の相関器の各バリエーションにおいて、新しい各信号サンプルが受信された後でＭ値を改めて組み合わせる必要がある。しかしながら、後述するように、これらの問題は本出願により解決される。
欧州特許出願（日本電信電話（ＮＴＴ）へのＥＰ０７０７３８５）は多数のソースから符号分割多重信号を受信する方法および装置を開示している。逆相関マトリクスを計算して多数のソースからの信号の逆拡散出力シーケンスを乗じることにより信号は拡散符号シーケンスと相互相関される。この出願には既に計算されている逆相関マトリクスの拡張により後続逆相関マトリクスを計算するための単純化された方法も開示されている。ＰＣＴ特許出願（エリクソン社へのＷＯ９６／２６５７８）には複数の端末から受信する信号間の同一チャネル干渉を処理する方法およびシステムが開示されている。関連する部分で、エリクソンの出願は基地局で受信した全体信号の可能な値の全てを計算数を減少して算出するステップを開示している。この出願に開示されているように、これらの値は、例えば、グレイ符号順で計算することができる。しかしながら、これら２つの発行された特許出願のいずれもが相関器の論理的複雑さを低減しかつ／もしくは相関器の速度を高めるための後述するシフトおよび部分相関に頼ってはいない。
【０００６】
（発明の概要）
本発明に従って、最後のＭの受信信号サンプルを所与のＭビット２進符号語のすべてのシフトと比較するのに使用する相関器および相関方法が提案される。符号語の対応するシフトがその位置に２進“１”を含むか“０”を含むかに従って、相関器は信号サンプルの各々を加算もしくは減算する。受信する新しい各信号サンプルに対する合計が出力され、信号サンプルと符号語との間には１つの位置シフトがある。好ましい実施例では、メモリユニットがＭの連続部分重複相関に対するＭの部分相関を格納する。Ｍよりも小さいＮの新しい各サンプルを受信した後で、算術ユニットはＮの新しい値を正および負符号の可能な各パターンと組み合わせる。組合せの半分は他方の半分の負数であり、残りの２の（Ｎ−１）乗の組合せはグレイ符号順に組合せを形成することにより値当り１回の加算もしくは減算だけで計算できることに注目すればこの過程は効率的に遂行される。所望するＮの全相関の計算を完了するために、そのように形成された組合せの選択されたものが次にＮ−１までの受信サンプル値と共に選択された格納された部分相関に加算される。したがって、スライディングウィンドウにわたってＮの連続相関を計算するための全体計算量はほぼ次式で表わされる。
計算される相関値当り（Ｍ＋２(N-1)＋Ｎ（Ｎ−１））／Ｎ演算。Ｎの値は好ましくは前式を最小限に抑えるように選択され、演算数は従来技術により実現される計算値当りＭ演算に比べて著しく少ないものとなる。そのため、複数Ｌの異なる所定の符号とのスライディングウィンドウ上の相関の組合せを含むように本発明の範囲を有利に拡張することができる。相関当り演算数はほぼ次式で表わされ、
（ＬＭ＋２(N-1)＋Ｌ（Ｎ−１）2＋（Ｎ−１））／ＬＮ，それは好ましくはＮに対する最適数を選択することにより最小限に抑えられる。
【０００７】
（図面の詳細な説明）
本発明の好ましい実施例およびその利点は、さまざまな図面において同様な対応する部品には同じ番号が使用されている、図１−図４を参照すればよく理解することができる。
【０００８】
図２は本発明の好ましい実施例に従って受信信号サンプルと相関することができる１５ビット符号の重複連続シフトの配列を示す線図である。図２において、複数の受信信号サンプルは１からＩまで１６進の番号が付されている（水平に）。信号サンプル番号の下には１５の受信サンプルが相関される１５ビット符号語のさまざまなシフトが示されている。左端の垂直番号付けは実施される相関の番号を示している。例えば、１番相関はロー番号１内の符号語を信号サンプル１，２，３．．．Ｆ番と相関させなければならない。
【０００９】
この実施例では、図２はＦ番サンプルが受信される直前の配列を示している。まだ受信されないサンプルはボールドプリントにより強調され既に受信されているサンプルの右に配置されている。まだ受信されていないサンプルと相関される符号語のビット間に分割線２が示されており、受信サンプルと既に相関されているビットは分割線の左に示されている。メモリ要素１−Ｅは、それぞれ、ロー１−Ｅとの未完成相関にたとえられる部分結果を含んでいる。図２は１番相関を完成できる前にＦ番サンプルを受信しなければならないことを示している。Ｆ，Ｇ，Ｈ，Ｉ番サンプルの受信により１，２，３，４番相関を完成することができ、かつローＦ，Ｇ，Ｈ，Ｉとの相関を少なくとも開始することができる。メモリ要素５−Ｅ内に含まれる部分相関との４つの新しいサンプルの異なる組合せを累算することにより、既に開始した５−Ｅ番相関をＦ，Ｇ，Ｈ，Ｉ番サンプルの受信後さらに右へ４位置継続することができる。
【００１０】
４番相関を完成するのに必要な４つの新しいサンプルＳ（Ｆ），Ｓ（Ｇ），Ｓ（Ｈ），Ｓ（Ｉ）の組合せは−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）＋Ｓ（Ｉ）であることをお判り願いたい。この組合せの符号はロー４内の残りの４ビット１０１０に対応する。“１”は負符号を示し、“０”は正符号を示す。ロー５−Ｅに対する相関の累算を継続するのに他の符号パターンを使用する他の組合せが必要であり、ロー４とロー５−Ｅに対して合計１１の組合せが必要である。
【００１１】
本発明の一実施例では、１６組合せの全てをグレイ符号順に計算するのに効率的な方法を使用することができるため、たとえ１６組合せよりも少なくて済む場合であっても、Ｓ（Ｆ），Ｓ（Ｇ），Ｓ（Ｈ），Ｓ（Ｉ）の可能な全ての符号組合せ、合計１６組合せ、を計算する方法が使用される。さらに、ビットパターン１１００で示される符号を有する組合せはまさに００１１で示される符号を有する組合せの負数である。したがって、１６組合せの半分しか形成する必要がなく、他方の半分は形成した半分の負数である。そのため、８つの組合せが符号パターンのグレイ符号順で計算されれば、計算すべき８つの組合せは最初の値が形成された後で新しい各値に対する１回だけの加算もしくは減算を使用して形成することができる。後述するように、この順序付けでは連続するパターン間で１つの符号変化しか生じない。
【００１２】
例えば、４つの新しい値（４つの演算としてカウントされた）の和を必要とするパターン００００で開始して、組合せＣに対するグレイ符号順計算は次のようである。
【数１】
００００  Ｓ（Ｆ）＋Ｓ（Ｇ）＋Ｓ（Ｈ）＋Ｓ（Ｉ）＝Ｃ（０）
０００１  Ｓ（Ｆ）＋Ｓ（Ｇ）＋Ｓ（Ｈ）−Ｓ（Ｉ）＝Ｃ（１）＝Ｃ（０）−２Ｓ（Ｉ）
００１１  Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）−Ｓ（Ｉ）＝Ｃ（３）＝Ｃ（１）−２Ｓ（Ｈ）
００１０  Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）＋Ｓ（Ｉ）＝Ｃ（２）＝Ｃ（３）＋２Ｓ（Ｉ）
０１１０  Ｓ（Ｆ）−Ｓ（Ｇ）−Ｓ（Ｈ）＋Ｓ（Ｉ）＝Ｃ（６）＝Ｃ（２）−２Ｓ（Ｇ）
０１１１  Ｓ（Ｆ）−Ｓ（Ｇ）−Ｓ（Ｈ）−Ｓ（Ｉ）＝Ｃ（７）＝Ｃ（６）−２Ｓ（Ｉ）
０１０１  Ｓ（Ｆ）−Ｓ（Ｇ）＋Ｓ（Ｈ）−Ｓ（Ｉ）＝Ｃ（５）＝Ｃ（７）＋２Ｓ（Ｈ）
０１００  Ｓ（Ｆ）−Ｓ（Ｇ）＋Ｓ（Ｈ）＋Ｓ（Ｉ）＝Ｃ（４）＝Ｃ（５）＋２Ｓ（Ｉ）
この過程により最初の値を形成する４つの演算、および前記グレイ符号順で後の組合せを形成する１つの演算（前の組合せから受信したサンプルの２倍の加算もしくは減算）を使用する８つの組合せの全ての計算が完了する。１位置右へシフトする２進算術を使用することは２を乗算することと等価であると推定されるため、サンプル値を２でスケーリングすることはここでは演算としてカウントされない。
【００１３】
前記した典型的な実施例は５つ以上の値の全ての組合せの形成に拡張することができる。任意数の値に対する計算のグレイ符号順序付けは、前記したように、１ビット位置しか違わない連続２進符号を特徴となる。
【００１４】
合計１１の演算を使用して形成された前記組合せは信号サンプル４−Ｅを表わす格納された値と次のように組み合わされる、格納された値４からＣ（５）が減算されて４番相関を完成する、格納された値５からＣ（２）が減算される、格納された値６にＣ（６）が加算される、格納された７にＣ（３）が加算される、格納された値８からＣ（６）が減算される、格納された９にＣ（４）が加算される、格納されたＡにＣ（２）が加算される、格納されたＢにＣ（１）が加算される、格納されたＣにＣ（７）が加算される、格納された値ＤからＣ（３）が減算される、格納された値ＥからＣ（１）が減算される、かつ格納された値ＦからＣ（０）が減算される。例示したように、この過程は１２の付加ステップをとっている。
【００１５】
次に１番ローに対応する相関を完成するために格納された値１から信号サンプルＳ（Ｆ）が減算される。同様に、格納された値２に信号サンプルＳ（Ｆ）が加算され、かつ格納された値２から信号サンプルＳ（Ｇ）が減算されて２番相関を完成する。また、−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）の信号サンプル組合せが格納された値３と組み合わされて３番相関が完成する。この点において、この過程はさらに１＋２＋３＝６演算を行っている。しかしながら、組合せ−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）±Ｓ（Ｉ）が既に計算されており、かつ寄与±Ｓ（Ｉ）が１演算を要することに注目すればこの数は低減することができる。したがって、３番相関は３つではなく２つだけの演算で完成することができる。
【００１６】
さらに良いことに、下記の組合せの形成で開始することにより、任意の点においてグレイ符号順で組合せの計算を開始することができる。
【数２】
−Ｓ（Ｆ）＋Ｓ（Ｇ）；
−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）；および
−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）＋Ｓ（Ｉ）；
３番相関を完成するのに必要な３つの値の組合せは第２ステップで形成されることをお判り願いたい。第３ステップの後で、他の組合せがグレイ符号順で形成される。
【数３】
１０１０（前記第３ステップで形成される）
１０１１
１００１
１０００
１１００
１１０１
１１１１
１１１０
それは７つの付加演算しか行わない。
【００１７】
この点において、次式（ここに、前例ではＮ＝４かつＭ＝１５）に従って拡張した総計算量に対して４つの相関が完成されていることをお判り願いたい。
（１）  Ｎ値の２Nの可能な符号組合せの全てを形成するＮ＋（２(N-1)−１），
（２）  １番から（Ｎ−１）番相関を完成する１＋２＋３．．．（Ｎ−１）＝０．５Ｎ（Ｎ−１）演算，
（３）  Ｎ番相関を完成しＭ−Ｎの他の相関を継続するＭ−Ｎ＋１演算。さらに、３，２および１値（信号サンプル１，２および３の値）の組合せを形成し完成した相関１，２および３により空にされた記憶位置にそれらを加算して同じ記憶位置を巡回的に再使用することによりＧ，ＨおよびＩ番相関が開始される。この過程も０．５Ｎ（Ｎ−１）演算を必要とする。
【００１８】
これら全ての演算の加算において、新しいＮ信号サンプルの各々を受信した後で、完成したＮ相関が相関当り
【数４】
０．５Ｎ（Ｎ−１）＋Ｍ−Ｎ＋１＋０．５Ｎ（Ｎ−１）＋Ｎ＋２(N-1)−１＝Ｍ＋２(N-1)＋Ｎ（Ｎ−１）演算、もしくは
（Ｍ＋２(N-1)＋Ｎ（Ｎ−１））／Ｎ演算
を使用して形成されることが確認される。
Ｎ／２値よりも大きい組合せはＮ値全ての既に形成された組合せの中の１つからＮ／２値よりも小さい組合せを減算することにより形成できることに注目して三角フィレット（ｆｉｌｌｅｔ）の開始および終了をより効率的に計算することによりこの過程は幾分簡約することができる。したがって、フィレットの計算にはＮ（Ｎ−１）演算ではなくおよそ０．５Ｎ（Ｎ−１）演算が必要である。
【００１９】
次の例は本発明の前記相関方法を使用して得られる計算量の節減を示す。この例は受信信号とＭ＝１０２４ビット符号語の全てのシフト間の相関の計算を示す。新しいサンプルＮのさまざまな値により得られる（１０２４ポイント）相関当り総演算数は次のように表わすことができる。
【数５】
Ｎ＝４      ５      ６      ７      ８      ９      １０
２６１  ２１２  １８１  １６２  １５１  １５１  １６１
Ｎ＝８もしくは９の値により１０２４ポイント相関を実施するのに必要な演算数（およそ１５１演算）が最適に低減され、従来技術に比べて１／７に節減されることをお判り願いたい。本発明の方法を使用して、従来技術の１５１ビット相関器のように魅力的な速度／電力／コストトレードオフを有し、したがって速度、電力もしくはコストに関して同じコストでより長い相関計算を達成する１０２４ビット相関器を製作することができる。このトレードオフにより本発明を実用化する際により高い通信装置性能が得られる。
【００２０】
さらに、受信データサンプルのおびただしいシフトを２つ以上の符号語と相関しなければならない場合には、さらなる節減を実現することができる。前記したように、Ｎデータサンプルの全ての組合せの計算には、
グレイ符号順で実施することにより２(N-1)＋（Ｎ−１）演算を必要とする。次に、これらの組合せのＭ−Ｎ＋１が第１の符号語と相関される第１セットの記憶位置、および第２の符号語と相関される第２セットの記憶位置に加算される。各符号語とのＮ相関を開始し完成するために加算すべき値の三角フィレットの計算には、前記したように、符号語当りせいぜいＮ（Ｎ−１）演算しか必要とせず、その結果、
【数６】
Ｌ（Ｍ−Ｎ＋１）＋２(N-1)＋Ｎ−１＋ＬＮ（Ｎ−１）＝ＬＭ＋Ｌ（Ｎ−１）2  ＋２(N-1)＋（Ｎ−１）
演算の総計算量によりＬ符号語とのＮ相関を完成することができる。したがって、相関当り総演算は次のように表わすことができる。
【数７】
（ＬＭ＋Ｌ（Ｎ−１）2＋２(N-1)＋（Ｎ−１））／ＬＮ
【００２１】
例えば、スライディング１０２４信号サンプルセグメントを６つの異なる１０２４ビット符号と相関させるのに下記の計算量を必要とし、
【数８】
Ｎ＝９      １０    １１    １２
１２６  １２０  １１８  １２５
それはＮ＝１１が最も効率的な選択であることを示している。
【００２２】
前記した方法は任意の符号語にうまく使用することができる。特定の符号語との相関に対しては、本発明の前記した原理に従ってさらに効率的な相関器を考案することができる。例えば、Ｎがｌｏｇ2（Ｍ）よりも大きく選択される場合には、必要以上のＮ信号サンプル値の組合せが計算される。しかしながら、それらは信号サンプル値当り１演算しか必要としない効率的なグレイ符号順で計算される。必要な組合せしか計算しないことが望ましいが、ある組合せの計算を省いてしまうと、組合せ当り１つの追加演算だけで必要な全ての組合せを確実に得られなくなってしまう。実際上、ある組合せの計算を省くとばらばらに分離されたグループの組合せが生じる。したがって、いずれの場合にも所要組合せセットの各構成要素の性質を調べてもう１つの構成要素からそれに達するのにどれだけ多くの演算が必要であるかを確認する必要がある。演算数は信号サンプル組み合わせるのに使用すべき符号（正負）を記述する対応するビットパターン間のハミング距離に等しい。計算されるセット内の各Ｎビット部分符号から１つおきのＮビット部分符号までの全てのハミング距離のセットである距離構造が与えられると、最小計算量とするためのそれら全ての最適計算順序は可能な全てのパスをテストするためのビタビアルゴリズムを使用して求めることができる。特定の符号についてはＮ信号サンプルの必要な組合せを計算するための演算数は、任意符号の一般的なケースに対して仮定された、値２(N-1)＋Ｎ−１よりも小さくなることがある。そのため、本発明の前記した原理に従って、これらの特定符号に対するより効率的な相関器を製作することができる。
【００２３】
あるいは、効率的な相関器を使用できるように符号を特定的に公式化することができる。例えば、このような符号はＮビットの全ての重複シフトが隣接Ｎビット符号の隣接セットを形成する（ハミング距離感覚で）性質を有する任意のＭビット符号として、最初の組合せの後の付加組合せ当り１つの演算を使用するだけで信号組合せを計算できるようにすることができる。さらに、隣接セット内の符号の半分は他方の半分の補数として、他方の負数であるため、相補組合せの計算を不要としなければならない。
【００２４】
図３は本発明の実施例を実現するのに使用することができる典型的な相関器１８の略ブロック図である。典型的な相関器１８は信号サンプルクロックを発生することにより新しい信号サンプルの入力を制御するタイミングコントローラ２０を含んでいる。タイミングコントローラ２０により制御される動作のシーケンスはＮサンプルクロックサイクル毎に繰り返される。Ｎサンプルクロックサイクル毎に、タイミングコントローラ２０は新しいＮサンプル値（本例ではＮ＝４）の入力および加減算器（変更器）２４を使用するメモリ２１内のＮ位置からのそれらの加算もしくは減算を制御する。このような各加算もしくは減算にはメモリ位置に格納された値が予め加算もしくは減算された値の累算を表わすようにするメモリリード、モディファイおよびリライトサイクルが含まれる。Ｎ入力サンプルの１つが加算されるか減算されるかは信号が相関される符号語の最初もしくは最後のＮビットによって決まる。符号語に従ってタイミングコントローラ２０の制御下で異なる時間に正しい加減算コマンドを変更器２４へ発生するように構成されるマッピング論理回路２３により所要信号パターンが発生される。メモリ２１はＭの部分間性相関を保持する巡回バッファとして利用される。完成される次の相関はメモリ位置“ｋ”であり、そこで“ｋ”のアドレスはアドレスオフセットレジスタ２２内に維持されている。アドレス“ｋ”における部分相関はＮ要素ラッチ２６内に維持された前に入力したＮサンプルのＮサンプル組合せを加算することにより完成される。セレクタ２５はメモリ位置“ｋ−Ｎ”に予め格納されたＮサンプル組合せで開始して、ラッチ２６内に維持された前のＮ入力サンプルの２(N-1)（すなわち、Ｎ＝４ならば８）組合せをグレイ符号順で計算して格納するように機能する論理を含んでいる。マッピング論理２３からのＮ−１選択線の制御下で、セレクタ２５は相関“ｋ”を完成するのに必要なこれらの組合せの中の選択された１つを出力する。同時に、組合せが加算されるか減算されるか（すなわち、加算の前に符号が反転されるか否か）に応じて、マッピング論理２３は加減算コマンドを変更器２４へ出力する。
【００２５】
次に、タイミングコントローラ２０は出力ゲート２８が完成したばかりの相関“ｋ”値を出力に接続できるようにすることにより完成したばかりの相関“ｋ”を出力し、ゼロ値をメモリ位置“ｋ”に書き込まれるように置換してメモリ位置“ｋ”をゼロにクリヤする。次に、タイミングコントローラ２０はセレクタ２５を制御して加減算器２４へ通される最終入力サンプルを入力シフトレジスタ２７から選択させ、同時にマッピング論理回路２３の時間制御を行って新しい入力サンプルを加算もしくは減算することにより変更されるメモリ位置ｋ，ｋ＋１，ｋ＋２，．．．，ｋ＋１−Ｎを逐次選択する。マッピング論理回路２３はまた、符号語ビットによって決まる予め格納された符号パターンに従って、Ｎメモリ位置の各々に対する加算もしくは減算を制御する。
【００２６】
例えば、符号語の最初の４ビットが１１０１であり、最後の４ビットが１０１０であれば、マッピング論理２３によりレジスタ２７へ入力される４つの新しいサンプルの中の第１のサンプルの減算（最初のビット位置の“１”（＝‘−’）を有する符号語に対応する）、位置ｋ＋１への加算（“０”（＝‘＋’）である最後の符号語に対応する）、位置ｋ＋２からの減算（“１”である第２から最後までの符号語ビットに対応する）、および位置ｋ＋３への加算（“０”である第３から最後までの符号語ビットに対応する）が行われる。次の４つのサンプルの中の第２のサンプルがレジスタ２７へ入力されると、マッピング論理２３はメモリ位置“ｋ”に対する“−”符号（“１”である符号語の第２ビットに対応する）、位置ｋ＋１に対する“−”符号（“１”である第１の符号語ビットに対応する）、位置ｋ＋２に対する“＋”符号（“０”である符号語の最後のビットに対応する）、および位置ｋ＋３に対する“−”符号（“１”である符号語の第２から最後までのビットに対応する）、等を発生する。次の図表は前記したパターンの理解を助ける。
【数９】
ｋ        １１０１
ｋ＋１    ０１１０
ｋ＋２    １０１１
ｋ＋３    ０１０１
前記アンダーラインしたビットは新しい相関を初期化するサンプルの符号を決定する符号語の最初のビットであり、それはアンダーラインしていないビット（相関される符号語の最後のビット）を符号として使用して完成された相関により空とされる同じメモリ位置に形成される。アンダーラインしていない最後のビットを使用して相関を完成することと最初のアンダーラインしたビットを使用して同じ位置に新しい相関を開始することとの間で相関メモリ位置がゼロにクリヤされ、それは前記したように適切な時間に出力ゲート２８をイネーブルするタイミングコントローラ２０により実施される。
【００２７】
新しいＮサンプルを処理してＮ相関を完成し新しいＮ相関を初期化するのと交錯して、タイミングコントローラ２０はセレクタ２５内に格納された前のＮサンプル組合せのメモリ２１の他のＭ−Ｎ位置への加算もしくは減算を制御する。この計算はサンプル期間当り（Ｍ−Ｎ）／Ｎ＝Ｍ／Ｎ−１位置を更新することにより、新しいＮサンプル期間にわたって多少とも均一に広げることができる。タイミングコントローラ２０は、Ｍ−Ｎ位置が更新されるまで、ｉ＝Ｎで始まってｉ＝Ｍ−１まで１だけ増してアドレスレジスタ２２に格納されたベースアドレス“ｋ”への増分“ｉ”をマッピング論理２３に与える。マッピング論理２３は増分“ｉ”をベースアドレス“ｋ”にモジュロ−Ｍ加算して更新されるメモリアドレス位置を得る。
【００２８】
タイミングコントローラ２０から与えられる増分“ｉ”はセレクタ２５により選択されるＮサンプル組合せを決定し、かつ組合せを反転すべきか否かを確認する（変更器２４へ“＋”もしくは“−”符号を与えることにより）ためにマッピング論理２３によっても使用される。Ｎ＝４が例として使用されている図２を見れば容易に理解できるように、特定のメモリ位置の内容と組み合わせなければならない組合せの指標（“ｉ”の値）は符号語ビットによって決まる。４ビットセグメントの括弧でくくったカラムは各ローの部分相関を更新するために加算される組合せを示す。これらのビットパターンの補数に対応するセレクタ２５内に組合せが格納される場合には、変更器２４に負符号が与えられると同時に相補組合せが選択され、そうでなければ“＋”符号を有する正しい組合せ（利用できる場合）が使用される。
【００２９】
セレクタ２５のＮ−１選択制御線入力への増分“ｉ”のマッピング、および変更器２４に対する＋／−の選択は、例えば、Ｍ−Ｎ，Ｎビット制御信号をメモリエリア内に格納して遂行することができる。相関符号語が選択もしくは変更された場合には、このメモリエリアに適切な値をロードすることができる。また、三角フィレットの開始および終了の形成を制御するのに必要なＮｘＮ符号ビットを含むようにメモリエリアを拡張することができ、そのため合計ＭｘＮビットのメモリとなる。
【００３０】
あるいは、固定相関符号に対しては、リードオンリーメモリ（ＲＯＭ）にこの情報をプログラムすることができ、状況によっては、増分“ｉ”のビットをハードワイヤド論理により変更器２４およびセレクタ２５へのＮの制御および選択信号へ変換することがより効率的である。前記したものだけでなく、これら全ての可能性も本発明の範囲内である。
【００３１】
次に、図４にＮ＝４に対するステップの典型的なタイミングシーケンスを示す。シーケンスのステップ１ａにおいて、アドレス“ｋ”における予め完成された相関がメモリ位置から出力され、その位置はゼロとされる。ステップ１ｂにおいて、４つの新しい信号サンプルの中の最初の信号サンプルが入力され、アドレス“ｋ”を含むアドレスオフセットレジスタ２２により決定される、メモリアドレスｋ，ｋ＋１，ｋ＋２およびｋ＋３へ加算もしくは減算される。加算するか減算するかはマッピング論理２３の内容により決定される。
【００３２】
ステップ２ａにおいて、完成された相関がメモリ位置ｋ＋１から出力され、メモリ位置ｋ＋１はゼロとされる。ステップ２ｂにおいて、第２の信号サンプルがメモリ位置ｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加算もしくは減算される。
【００３３】
ステップ３ａにおいて、完成された相関がメモリ位置ｋ＋２から出力され、メモリ位置ｋ＋２はゼロとされる。ステップ３ｂにおいて、第３の信号サンプルがメモリ位置ｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加算もしくは減算される。
【００３４】
ステップ４ａにおいて、完成された相関がメモリ位置ｋ＋３から出力され、メモリ位置ｋ＋３はゼロとされる。ステップ４ｂにおいて、第４の信号サンプルがメモリ位置ｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加算もしくは減算される。ステップ４ｃにおいて、メモリアドレス“ｋ”の４サンプル組合せで開始して、他の２(N-1)−１（すなわち、Ｎ＝４であるこのケースでは７）の４サンプル組合せがグレイ符号順で計算される。ステップ４ｄにおいて、ステップ４ｃで計算された組合せの中の選択された１つの組合せが残りのメモリ位置ｋ＋４，ｋ＋６．．．．ｋ＋Ｍ−１の各々の内容に加算される。このような各メモリ位置に対して、その位置に加算されるように選択される組合せは符号語の特定の選択に対して予め定められている。ステップ４ｅにおいて、アドレスｋが４だけ増加され（モジュロ−Ｍ）、ステップ１ａからシーケンスが繰り返される。
【００３５】
ステップ４ｂの完了後、メモリ位置“ｋ”は符号語の最初の４ビットに対応する符号を有する４つの信号値の組合せを含んでいる。この組合せは合計８つの組合せの中の他の７つの組合せのステップ４ｃにおける計算の開始点として使用され、それらはその負数と共に４つの信号サンプルの１６の可能な符号組合せを含んでいる。これらの組合せの中の１つはそれをメモリ位置ｋ＋４の内容に加算することにより相関ｋ＋４を完成するのに必要である。一般的に、この値が計算される順序は信号が相関される符号によって決まり、計算される最後の値となることがある。したがって、相関ｋ＋４（すなわち、ｋの増分した値）を完成するのに必要な組合せを確実に遅れずに得るために、ステップ４ａから４ｅは１サンプルクロック期間内に完了する必要がある。そのように完成された相関が次のサイクルのステップ１ａで出力される。ステップ４ｅおよび４ｄは逆にすることができるが（すなわち、ステップ４ｄにおいて最初にｋを４だけ増分することができる）、アドレスｋ＋４，ｋ＋５．．．．ｋ＋Ｍ−１は新しいｋ値に関してステップ４ｅに対するｋ，ｋ＋１，ｋ＋２．．．．ｋ＋Ｍ−５として表現しなければならない。
【００３６】
ステップ４ｃで計算された４つのサンプル組合せの他のＭ−５メモリ位置ｋ＋５，ｋ＋６，．．．．．Ｍ−１，０，１，．．．．ｋ−１への累算はステップ１から４の次の実行サイクル中に行われなければならない。したがって、全体として、次のサイクルのステップ４ｄおよび４ｃの実行中にメモリ位置ｋ＋４を含むＭ−４メモリ位置の内容に計算された組合せの中の選択された組合せを加算しなければならない。それ自体、ステップ４ｃは７つの演算を１サンプルクロック期間内で完了させる必要があるが、これらの演算はステップ４ｂの４つの演算と並列に実行することができる。他のＭ−４の演算は第４サンプル期間の残りプラス他の３つの演算中に完了しなければならず、それは４サンプルクロック期間内に遂行しなければならない合計Ｍ−４＋７演算である。それはサンプルクロック期間当り少なくとも（Ｍ＋３）／４演算の計算速度を提供することにより遂行することができる。
【００３７】
例えば、Ｍ＝６４であれば、ステップ１から４ｄまでの並列実行に加えてサンプルクロック期間当り少なくとも１７演算の計算速度が必要である。ステップ１−４ｄの各々がサンプルクロック期間当りさらに４算術演算を消耗し、そのためタイミングコントローラ２０がサンプルクロック周波数の少なくとも２１倍の高速クロックを利用できればすべての演算に対処することができ、それはサンプルクロック期間当りメモリ２１への２１リード−モディファイ−リライトサイクルを許す。それは長さ６４の従来技術のスライディング相関器の１／３である。
【００３８】
前の７つの値が使用されているのと同じ時間に新しい７つの４サンプル組合せの計算を行えるようにすれば所要高速サンプルクロック周波数を低減することができる。それは７つのメモリ位置の２つの代替セットが与えられれば行うことができる。７つの新しい組合せを計算するのに必要な７つの演算を次にＭ−４メモリ位置への前の組合せの加算と並列に行うことができ、メモリ２１に必要なリード−モディファイ−リライトサイクルの速度はＭ−６４相関器に対してサンプルクロック期間当り４＋（Ｍ−４）／４すなわち１９サイクルへ低減される。もちろん、並列処理の提供と処理要素当りの速度もしくは計算速度の低減とをトレードオフすることができる。例えば、メモリ２１は２つのバンクに分割することができ、また２つの加減算器を設けて２つのリード−モディファイ−リライトサイクルを高速クロック期間ごとに並列に実施することができる。
【００３９】
パラレリズムの根本原理はメモリ２１を、各バンクがＭ／Ｎ加減算器の対応する１つに接続される、Ｎ要素のＭ／Ｎバンクへ分割することである。新しいサンプルクロック期間毎に更新される４つの連続メモリ位置は、全ての所要リード−モディファイ−リライトサイクルが並列に行われるように他の（Ｍ−Ｎ）／Ｎメモリ位置を格納できるように、異なるバンク内に格納することができる。このような速度を整合するために、２(N-1)−１のカスケード加算器チェーンを使用してセレクタ２５が必要とするＮサンプルの２(N-1)組合せをグレイ符号順で計算することができ、加算器は先行する加算器の出力に対してサンプル値を２回加算もしくは減算して論理のリップルスルー遅延だけで全ての組合せを並列に得ることができる。このような構成はハードウェア複雑さがＭ−１並列加算器を必要とする従来技術の完全並列相関器のおよそ１／Ｎである。
【００４０】
このように、本発明の方法を使用して従来技術の方法に比べて相関長さがより長い、ハードウェアの複雑さがより低い、より速度が高い、消費電力がより低い、あるいはそれらの利点が任意に組み合わさった相関器を形成することができる。本発明に従って、改良型相関器を利用して受信信号サンプルセットの全てのシフトを相関することができ、セットは信号の隣接セットである必要がなく、例えば、バーストとして受信することができる（例えば、時分割多元接続（ＴＤＭＡ）システムにおけるバースト、もしくは周波数ホッピングシステムにおける“ホップ”）。本発明の方法に対する必要性は、例えば、受信信号のタイミングに関して不確定性がある場合に常に生じる。このような必要性は信号サンプルの異なる遅延セットを逆拡散符号で逆拡散して異なる“レーキタップ”を形成することにより、異なる遅延パスに沿って受信した信号を結合するように“レーキ”受信機が構成される場合に符号分割多元接続（ＣＤＭＡ）システム内でも生じる。本発明に従って、本相関器を効率的に使用して多数の複数のレーキタップを同時に逆拡散することができる。
【００４１】
さらに、本発明の方法を使用してＭ連続信号サンプルの連続シフトと２進値には制約されず、例えば、＋１，−１および０の３進値を含むことができるＭ格納サンプル値の信号パターン間の相関を計算することができる。Ｎ信号値の可能な３**Ｎ組合せの全てをグレイ符号順で効率的に計算することができ、その許された値セットを通して一時に１桁しか変化されず、前記した発明の原理に従って高速相関アルゴリズムを考案することができる。
【００４２】
本発明は、例えば、複数の（例えば、４つ以上の）Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ（ＧＰＳ）衛星から受信したＣＤＭＡ信号を処理するナビゲーション受信機等のいくつかの異なるＣＤＭＡ符号のいくつかのシフトと相関しなければならない場合にも有用である。
【００４３】
本発明の方法および装置の好ましい実施例を添付図に例示し前記詳細な説明において説明してきたが、本発明は開示した実施例に限定はされず特許請求の範囲に記載され明示された発明の精神を逸脱することなく非常に多くの再構成、修正および置換が可能であることがお判りであろう。
【図面の簡単な説明】
【図１】  従来技術の相関器のブロック図である。
【図２】  本発明の好ましい実施例に従って受信信号サンプルと相関することができる１５ビット符号の重複連続シフトの配列を示す線図である。
【図３】  本発明の実施例を実現するのに使用することができる典型的な相関器の略ブロック図である。
【図４】  本発明を実現するのに使用することができる典型的なステップのシーケンスを示す図である。
【図１】
0004149665.tif 000002
【図２】
0004149665.tif 000003
【図３】
0004149665.tif 000004
【図４】
0004149665.tif 000005