ＧＰＳ信号の迅速な捕捉方法及び装置
特有の周期的に反復するシーケンスを含む送信された信号を使用して、受信機の位置を確定するための方法及び装置を開示している。この装置及び方法は、通信システムで、特に、ＧＳＭおよびＵＭＴＳセルラ電話システムで使用されるＡ−ＧＰＳのような非同期化されるシステムでは有効である。受信された信号は周期的に反復するシーケンスの少なくとも２反復だけ受信機により記憶される。ＦＦＴ演算が行われ、結果的なデータ周波数サンプルは、仮説された残留周波数に応答して枝刈りされる。これは必要とされるその後の計算数と処理時間を減少する。相関シリーズは仮説された送信機に対応する枝刈りされたサンプルと基準周波数サンプルから決定される。一致が発見されたならば、コード位相オフセットが決定され、発見されないならば、プロセスは別の仮説された残留周波数で反復される。類似して得られる多数の相関シリーズも、この検査前に非コヒーレントで組合わされることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＧＰＳシステムのような、無線信号の使用により移動体装置の位置を計算する装置及び方法に関する。
【背景技術】
【０００２】
位置検出装置は、ますます人気が高まっている。これによって、位置の決定に使用される信号を捕捉するための迅速で高感度な方法の開発が奨励されている。
【０００３】
位置検出技術は、典型的に、位置を決定するため、既知の位置から同時に送信された無線信号を使用する。ＧＰＳシステムでは、これらの信号は既知の時間において、予め限定された周波数で、多数の衛星から同時に送信される。地上では、ＧＰＳ受信機は、空の視界範囲内にある各衛星から信号を捕捉する。視界内の衛星の正確な位置を伴った信号の到着時間と、信号が各衛星から送信される正確な時間は、三辺測量計算によりＧＰＳ受信機の位置を決定するために使用される。
【０００４】
ＧＰＳ衛星からの信号の捕捉は、複数の要因のために困難である。例えば、ＧＰＳ信号は比較的低電力で、長距離から送信される。ＧＰＳ信号が地球軌道から受信機へ伝播するまでの時間に、それらの最初の低い電力は非常に減少され、信号は受信機に至って、極めて弱くなる。受信された信号レベルはさらに、室内での受信、または都市の峡谷環境での受信中に生じるような、ビルの障害効果により弱められうる。
【０００５】
ＧＰＳ受信機には２つの主要な機能が存在し、即ち（１）種々のＧＰＳ衛星までの擬距離の計算と、（２）これらの擬距離と、衛星のタイミングと、暦表（位置）データとを使用するＧＰＳ受信機の位置の計算である。擬距離は、ローカルクロックによるバイアスを有する、衛星とＧＰＳ受信機との間の時間遅延（または距離に等しい）を測定する。通常の自律ＧＰＳ受信機では、衛星の暦表と送信データの時間は、それが捕捉及び追跡されると、ＧＰＳ信号から抽出される。この情報の補正は通常、比較的長時間（３０秒から数分間）かかり、低い誤り率を実現するために良好な受信信号レベルで実現されなければならない。
【０００６】
事実上、全ての既知のＧＰＳ受信機は擬距離を計算するために相関方法、またはそれらの数学的に等価する方法を使用する。これらの相関方法は実時間で、しばしばハードウェア相関器で行われる。ＧＰＳ信号は、擬似ランダム（ＰＮ）シーケンスと呼ばれる特別なシーケンスまたは“コード”にしたがって変調される高率の反復信号を含んでいる。民間の応用に利用可能なコードはＣ／Ａコードと呼ばれ、１．０２３ＭＨｚであり、１ｍｓｅｃの１コード期間に１０２３チップの反復期間である２進位相反転レート、または“チッピング”レートを与えるために使用されている。ＧＰＳシステムの擬似ランダムシーケンスは“ゴールドコード”として知られている系統に属している。各ＧＰＳ衛星は特有のゴールドコードを有する信号を放送する。
【０００７】
簡略する目的で、以下の説明には、信号が“擬似ランダムシーケンス（またはコード）を含んでいる”という用語を使用するが、このことは信号が、擬似ランダムシーケンスまたはコードにしたがって変調された波形を含んでいることを意味する。擬似ランダムシーケンスの１フレームの長さはそれが反復する前のシーケンスのシンボル数である。擬似ランダムシーケンスの継続期間（時間）により、擬似ランダムシーケンスにしたがって変調される波形の継続期間を意味している。同様に、擬似ランダムシーケンスのフレーム率を言う場合、擬似ランダムシーケンスにしたがって変調された波形の反復率を意味する。用語「擬似ランダムシーケンス」が、数のシーケンスまたは、このような数のシーケンスにしたがって変調される波形を指すかは、文脈から明白であろう。
【０００８】
信号が所定のＧＰＳ衛星から受信された後、ベースバンドへの下方変換プロセスに続いて、信号は基準信号と相関される。例えば、簡単な相関受信機は、受信された信号を、そのローカルメモリ内に含まれる適切なゴールドコードの記憶されたレプリカを含んでいる局部的に発生された基準信号によって乗算し、その後、信号が存在するという指示を得るために、その積を積分（例えばローパスフィルタ処理）する。
【０００９】
簡単な個々の相関プロセスは、単一数（おそらく複素数）を生じる可能性がある。しかしながら、問題となる多くの場合、このような数の乗算は異なる基準シーケンス（例えば遅延されたバージョン）に対応して、直列または並列して、類似の演算を行うことにより計算される。このような数のセットを“相関シリーズ”と呼ぶ。１以上の連続する相関シリーズを結合する最終結果は“最終的な相関シリーズ”と呼ばれる。
【００１０】
受信された信号に関して、この記憶されたレプリカの相対的なタイミングを逐次的に調節し、高いエネルギが結果的な最終的な相関シリーズで生じるときを観察することにより、簡単な受信機で、受信された信号とローカルクロックとの間の時間遅延を決定できる。この時間遅延、モジュロ １ミリ秒コード期間は、“コード位相”と名づけられている。残念ながら、相関捕捉プロセスは、特に受信された信号が弱いならば、時間を要する。捕捉時間を改良するため、最も一般的なＧＰＳ受信機は、相関ピークの平行サーチを可能にする（典型的には１２個までの）多数の相関器を使用する。
【００１１】
幾つかのＧＰＳは、受信されたＧＰＳ信号のドップラ周波数を決定するためにＦＦＴ技術を使用する。これらの受信機はＧＰＳ信号を逆拡散し、典型的に１０ｋＨｚから３０ｋＨｚの範囲の帯域幅を有する狭帯域幅信号を提供するために通常の相関動作を使用する。結果的な狭帯域幅信号はその後、搬送周波数を決定するためにＦＦＴアルゴリズムを使用してフーリエ解析される。このような搬送波の決定は同時に、ローカルＰＮ基準が受信された信号の正確なコード位相に調節されたという指示を与え、搬送周波数の正確な測定を行う。この周波数はその後の受信機の追跡動作に利用される。
【００１２】
１つの位置決定方法は例えば、移動体装置ではなく中央処理位置の擬距離を計算するためにＦＦＴアルゴリズムを使用する。その方法にしたがって、データのスナップショットはＧＰＳ受信機により集められ、その後、データリンクにわたって遠隔受信機へ送信され、ここで最終的な相関シリーズを計算するためにＦＦＴ処理を受ける。しかしながら、典型的に、（４つのＰＮ期間に対応する）単一の順方向および逆方向の高速フーリエ変換のみが相関のセットを実行するために計算される。
【００１３】
別の方法は、ＧＰＳ信号を捕捉するための高速フーリエ変換方法を使用し、生のデータの長いブロックをデジタル化し、記憶し、処理することを含んでいる。例えば１秒間隔に対応するデータはデジタル化され、その後ＦＦＴベースの信号処理方法を使用して局部的に処理されて、この捕捉されたデータブロック内に存在するＧＰＳ信号を捕捉することができる。この方法では、多数のＦＦＴ演算が行われ、それぞれ相関シリーズを発生し、その結果は最終的な相関シリーズを発生するためにコヒーレントと、非コヒーレントの処理演算の両者を受ける。
【００１４】
残念ながら、このようなシステムのＧＰＳ信号の捕捉方法は、１データビットの１期間（例えば２０ミリ秒の時間に等しい２０ＧＰＳフレーム）を超えるような、長いコヒーレントな積分を行うときには効率が劣る。特にＧＰＳ搬送周波数の不確定さが大きいとき、効率の損失も大きい。さらに、現在のＧＰＳ受信システムでは、１データビットを超える期間にわたるコヒーレントな積分は、ＧＰＳ受信機がビットシーケンスの演繹的な知識をもつことを必要とする。それ故、１データビットを超える期間にわたるコヒーレントな積分は通常、サーバから移動局へこのような情報を送信することにより行われる。この一般的な方法は、ＩＳ−９５、ＣＤＭＡ２０００、ＧＳＭ、ＵＭＴＳ標準規格を含む幾つかのセルラ通信標準規格で標準化されている。
【００１５】
コヒーレントな処理に対する他の従来の方法は、（１）長いコヒーレントな積分が必要なとき、（２）広いドップラ距離にわたるサーチが必要とされるとき、（３）コード位相サーチが処理される各ＧＰＳ信号の全１０２３チップにわたって行われなければならないときに有効であろう。しかしながら、このような従来の方法には複数の限定と制限がある。例えばこれらのアルゴリズムは２次元アレイとして処理データを必要とし、またドップラサーチが効率的に実行されることのできる程度を限定し得る。
【概要】
【００１６】
予め定められた周波数で、複数の送信機から送信される１以上の信号を受信し処理するための方法及び装置を説明する。各送信される信号は、各それぞれの信号を送信する送信機を特有に識別する周期的に反復するシーケンスにしたがってコード化された波形を含んでいる。受信された信号は受信機の位置決定に使用される。送信機はＧＰＳ周波数でＧＰＳ信号を送信する複数のＧＰＳ衛星を含むことができ、それぞれのＧＰＳ衛星は、特有の周期的に反復するシーケンスにしたがってコード化された波形を送信する。受信機における信号のコード位相オフセットが発見され、複数の送信機からのこの情報を使用して、受信機の位置はＧＰＳアルゴリズムを用いて確定されることができる。
【００１７】
さらに高い感度と高い処理速度が、観察されるデータにおいてＦＦＴ演算を行うことにより実現されることができ、ＦＦＴと共に、特別な枝刈り動作が、仮説された残留（見逃し）周波数エラーに基づいて使用され、計算の総数を減少し、それ故、処理時間を減少する。
【００１８】
特に受信機では、予め定められた周波数の信号が観察され、周期的に反復するシーケンスの少なくとも２回の反復（２フレーム）に対応する予め限定された時間期間にわたってデジタル化される。複数の送信機のうち１つが仮説され、仮説された送信機に対応する基準周波数サンプルの１セットが与えられる。デジタル化されたデータの第１のサブセットが少なくとも２フレームに等しい期間として選択され、したがって、データの１ブロックを規定する。データ周波数サンプルの１セットは、その後、フーリエ変換技術等を使用することによって、このブロックから計算される。
【００１９】
第１の残留周波数が仮説され、その後、データ周波数サンプルがその仮説された第１の残留周波数に応答して枝刈りされ、周期的に間隔を隔てられたデータ周波数サンプルの第１のサブセットを与える。データ周波数サンプルの第１のサブセットと基準周波数サンプルは第１の相関データシリーズを与えるために、（典型的には乗算および逆ＦＦＴ手順によって）さらに処理される。
【００２０】
この手順はその後、付加的なデータブロック（典型的に隣接する）で反復され、そうして発見された多数の相関シリーズが検出され、共に付加されて最終的な相関シリーズを形成することができる。この後者のシリーズはその後、典型的には最終的な相関シリーズの強いピークを探すことによって、信号の一致を識別するためにサーチされる。一致された信号が発見されたならば、コード位相オフセットが、最終的な相関シリーズから決定される。しかしながら、一致された信号が発見されなかったならば、別の残留周波数が仮説され、典型的にデータ周波数サンプルの同一のセットと基準周波数サンプルを使用して、プロセスが反復され、信号の一致をサーチする。類似の処理が、信号の一致が発見されるまで、または一致を発見せずに十分な残留周波数が仮説されて、仮説された送信機からの信号が捕捉されることができないことを想定するまで進行する。
【００２１】
典型的に、受信機により観察可能な複数の送信機が存在し、このプロセスは、信号を識別し、可能ならば各送信機からコード位相オフセットを決定するために、このような各送信機で反復されることができる。
【００２２】
多数の異なる実施形態が実行されることができる。１実施形態では、枝刈りステップはさらに、データ周波数サンプルのサブセットを選択することを含み、そのサブセットは、整数Ｋだけ相互に関して隔てられているインデックスを有する複数のサンプルを含んでおり、ここでＫはデータブロック中のＰＮシーケンスのフレーム数である。
【００２３】
この際に、ここでは時折、Ｆ（ｔ）における用語“ＰＮシーケンス”または“ＰＮフレーム”、即ちＰＮシーケンスのフレームの反復するセット、を使用しているが、ＰＮシーケンスは実際には搬送波の変調する信号を構成するために使用される数のシーケンスであり、したがって波形Ｆ（ｔ）を発生するので、これは厳密には正しくないことに注意する。しかしながら、“ＰＮシーケンス”がＰＮシーケンスＦ（ｔ）により変調される波形か或いはシーケンス自体を意味することに使用されているかは、文脈から明白であろう。
【００２４】
別の実施形態では、方法はさらに、重み付けされた周波数サンプルの１セットを形成するため、データ周波数サンプルのサブセットを基準周波数サンプルの１セットで乗算することを含んでいる。
【００２５】
基準周波数サンプルは任意の適切な方法によって得られ、例えば受信機は基準周波数サンプルを規定するために周期的に反復された周波数の１以上の期間において、ディスクリートなフーリエ変換（ＤＦＴ）を行ってもよく、基準周波数サンプルは各送信機で予め計算され、受信機に記憶されてもよく、或いは基準周波数サンプルはここで説明されるＰＤＥのようなサーバからダウンロードされてもよい。
【００２６】
相関動作を行うステップは、相関データシリーズを発生するために、重み付けされた周波数サンプルのセットで逆ＤＦＴを行うことを含むことができる。
【００２７】
各データブロックは２以上、例えば５、１０、２０以上の周期的に反復するシーケンスの整数回の反復に対応するサイズを有することができる。幾つかの実施形態のデータブロックは、周期的に反復するシーケンスの約５乃至２０の反復範囲内のサイズを有することができる。他の実施形態では、データブロックは１００程度のこのような反復のサイズを有することができる。
【００２８】
前述の方法は、適切なハードウェアおよび／または受信機中のソフトウェア、および／または無線ネットワークの１以上のサーバで実行される。例えばある機能は受信機で実行され、ある機能は位置決定エンティティ（ＰＤＥ）で実行されることができる。
【００２９】
ここで説明する装置及び方法は、補助ＧＰＳ（“Ａ−ＧＰＳ”）システムでは特に有効である。この補助ＧＰＳシステムでは、補助情報をＧＰＳ受信機へ提供する通信システムが、ＧＳＭおよびＵＭＴＳセルラ標準規格の場合のように、非同期化される。ＣＤＭＡ２０００標準規格のように同期された通信システムでは、コード位相サーチに課される要求は非常に軽減されるが、ここで説明する改良されたアルゴリズムの使用からさらに利点が得られよう。
【詳細な説明】
【００３０】
図面の種々の図形では、同一の参照符号は同一または類似の部分を示している。
【００３１】
図１は、複数のＧＰＳ衛星（ＳＶ）11を含むＧＰＳ環境を示している。ＧＰＳ環境について説明するが、ここで説明されるシステムは任意の位置付けシステムで構成されることができる。衛星11は、通信ネットワークの一部である複数のランドベースの基地局10と、基地局と通信する移動局（ＭＳ）14とによって受信されるＧＰＳ信号12を発射する。ＭＳ14はＧＰＳ受信機と、双方向通信信号20を使用して基地局と通信するための双方向通信システムとを含んでいる。ＧＰＳ受信機は、１以上の基地局と通信する（セル電話以外の）広い範囲の移動体実施形態で構成されることができる。広い範囲の環境に位置付けられることのできるＭＳ14を所有するユーザ13は、静止または移動することができる。
【００３２】
ＧＰＳ衛星（ＳＶ）11は、ＧＰＳ受信機の位置付けに使用される信号を放送する衛星のグループを含んでいる。衛星はＧＰＳ時間に同調される無線信号12を送信するように同期される。これらの信号は予め定められた周波数で、予め定められたフォーマットで発生される。現在のＧＰＳ構造では、各ＳＶはＧＰＳ標準規格にしたがってフォーマットされた（１５７５．４２ＭＨｚの）Ｌ１周波数帯域で民間タイプのＧＰＳ信号を送信する。ＧＰＳ信号がＭＳの通常のＧＰＳ受信機により検出されるとき、ＧＰＳシステムは各ＧＰＳ衛星の擬距離を計算し、その擬距離から、ＭＳの位置が計算される。
【００３３】
擬距離は、ｃ・（Ｔｕｓｅｒ−ＴＳＶ）＋ｃＴｂｉａｓとして規定され、ここでｃは光速度であり、Ｔｕｓｅｒは所定のＳＶから信号が受信されるときのＧＰＳ時間であり、ＴＳＶは衛星が信号を送信したときのＧＰＳ時間であり、Ｔｂｉａｓは通常はＧＰＳ受信機に存在するローカルユーザクロックの誤差である。時折、擬距離は定数“ｃ”を省略して規定される。通常の場合、受信機は４つの未知数Ｘ、Ｙ、Ｚ（受信機アンテナの座標）とＴｂｉａｓを解くことを必要とする。これらの４つの未知数を解くことは、通常４つの異なるＳＶからの測定を必要する。しかしながら、ある状況では、この制約は緩和されることができる。例えば、正確な高度の推定が得られるならば、必要なＳＶ数は４から３へ減少されることができる。Ａ−ＧＰＳ動作では、ＴＳＶは必ずしも受信機に対して利用可能ではなく、真の擬距離を処理する代わりに、受信機は主にコード位相に依存する。現在のＧＰＳ構成では、ＰＮコードは１ミリ秒毎に反復するので、コード位相は１ミリ秒の時間の曖昧さを有する。時折、データビットの境界が確認されるので、したがって２０ミリ秒のみの曖昧さが生じる。
【００３４】
基地局10は、無線信号20を使用してＭＳ14と通信する通信ネットワークの一部として使用される基地局の任意の集合を具備している。基地局はセルラインフラストラクチャネットワーク15に接続され、このネットワーク15は、公共電話システム16のような複数の他の通信ネットワーク、インターネットのようなコンピュータネットワーク17、位置決定エンティティ（ＰＤＥ）18、ブロック17aで集合的に示されている種々の他の通信システムに通信サービスを提供する。基地局10に存在するかその近くに存在する可能性のある、または任意の他の適切な位置に存在する可能性のあるＧＰＳ基準受信機（または受信機）19は、ＰＤＥ18と通信し、ＳＶ位置（暦）情報のような、位置を決定するのに有効な情報を提供する。
【００３５】
地上ベースのセルラインフラストラクチャネットワーク15は典型的に、セル電話のユーザが公共電話システム16にわたって別の電話機と接続することを可能にする通信サービスを提供する。しかしながら、基地局はさらに、他の装置との通信、および／またはハンドヘルド型パーソナルデジタルアシスタント（ＰＤＡ）とのインターネット接続のような、他の通信目的で使用されることもできる。例えば基地局10はＧＳＭ通信ネットワークの一部であってもよいが、他のタイプの同期（例えばＣＤＭＡ２０００）または非同期通信ネットワークでも同様に使用できる。
【００３６】
図２は、通信および位置検出システムを組込んでいる移動体装置14の１実施形態のブロック図である。セルラ通信システムのような双方向通信システム22は、セルラ信号20を使用して通信するアンテナ21に接続されている。セルラ通信システム22は、基地局と通信しおよび／または基地局からの信号20を検出し、送信されたまたは受信された情報を処理するため、モデム23、ハードウェア、ソフトウェアのような適切な装置を含むことができる。
【００３７】
ＭＳのＧＰＳ位置検出システム27は、理想的なＧＰＳ周波数のまたはそれに近い周波数で送信されたＧＰＳ信号12を受信するためのＧＰＳアンテナ28に接続されている。ＧＰＳシステム27は、周波数変換回路およびアナログデジタル変換器を含んでいるＧＰＳ受信機29と、ＧＰＳクロックと、ＧＰＳ受信機の所望の機能を制御するための制御論理装置と、ＧＰＳ信号を受信して処理し、適切な位置検出アルゴリズムを使用して位置を決定するのに必要な計算を行うための適切なハードウェア及びソフトウェアとを具備している。示されている実施形態では、アナログデジタル変換器は位置検出システムのバッファメモリに接続され、バッファメモリはＤＦＴ動作中にデータを提供し記憶するためＤＦＴ回路に結合されている。幾つかのＡ−ＧＰＳ構造では、最終的な位置検出計算（例えば緯度と経度）は、ＧＰＳ受信機から遠隔サーバへ送信されるコード位相及びその他の情報に基づいて、遠隔サーバで実行されることができる。ＧＰＳシステムの幾つかの例は米国特許第5,841,396号、第6,002,363号、第6,421,002号明細書に開示されている。
【００３８】
ＧＰＳクロックは正確なＧＰＳ時間を維持することを意図されているが、多くは、正確な時間は位置の確定前には得られないので、その推定された値と、その値に関する不定さによって、ＧＰＳクロックソフトウェアで時間を維持することが一般的である。正確なＧＰＳ位置の確定後、ＧＰＳ時間はしばしば正確に（現在のＧＰＳ構造では数十ナノ秒内の不定さ）知らされることに注意する。しかしながら、最終的な位置検出計算が遠隔サーバで行われるとき、この正確な時間はサーバでのみ利用可能である可能性がある。
【００３９】
移動体装置の制御システム25は双方向通信システム22と位置検出システム27との両者に接続されている。移動体装置の制御システム25は、それが接続されているシステムに対して適切な制御機能を行うために、１以上のマイクロプロセッサ、メモリ、他のハードウェア、ファームウェア、ソフトウェアのような任意の適切な構造を含んでいる。ここで説明する処理ステップは任意の適切な方法で実行されることができる。
【００４０】
制御システム25はユーザインターフェース26に接続され、ユーザインターフェース26は、キーパッド、音声通信サービスのためのマイクロホン／スピーカ、バックライトのＬＣＤディスプレイのようなディスプレイ等の、ユーザとインターフェースするための任意の適切なコンポーネントを含んでいる。位置検出システム27に接続されている移動体装置の制御システム25とユーザインターフェース26は、ユーザ入力の制御および結果の表示のような、ＧＰＳ受信機と双方向通信システムに対して適切な入力−出力機能を与える。
【００４１】
コヒーレントな処理方法の１例について図３及びその他の図面を参照して説明する。図３は、受信されたＧＰＳ信号を処理して、それがＧＳＰコードと搬送周波数オフセットを選択する仮説に一致するか否かを識別するために、移動局で行われる一連のステップを示すフローチャートである。アルゴリズムは、選択されたＧＰＳコードでコード位相オフセットの一致を発見しようとするため、全ての可能なコードオフセット（例えば１０２３オフセット）を検査できる。コヒーレントな処理アルゴリズムはその後、移動局により観察可能であり得る各ＧＰＳコードで反復される。付加的な非コヒーレントな処理が、さらに感度を改良するため、図３のアルゴリズムに対して付加されることができる。簡潔にする目的で、この付加された複雑さについて図１１と共に後に説明する。
【００４２】
図３では、30で、ＧＰＳ信号を観察する動作が示されている。本質的に、受信機は、ＧＰＳ信号が存在し検出可能であることを予想した上で、ＧＰＳ搬送周波数に近い搬送周波数を有する電磁エネルギを受信する。ＧＰＳ信号は（それが存在するならば）少なくとも期間Ｔｃ程の長さの時間期間、即ちデータのブロックがコヒーレント処理で取られる時間期間にわたり観察される（Ｔｃは“データブロック期間”または信号のコヒーレントな積分（処理）時間としても呼ばれることができる）。
【００４３】
雑音がない場合、ＧＰＳ信号の関数形態ｓ（ｔ）が任意の時間ｔにおいて理論的に、以下のように表される。
ｓ（ｔ）＝Ａｄ（ｔ）Ｐ（ｔ）ｅｘｐ（ｊ２□ｆｔ＋□） （Ａ１）
ここで、Ａは信号振幅であり、ｄ（ｔ）は搬送波を（例えば二相変調により）変調する比較的低速度（例えば５０ボー）を有するデータシーケンスであり、Ｐ（ｔ）はＰＮシーケンスＦ（ｔ）のフレームの反復するセットからなる波形であり、ｆは（理想的にはｆ０に等しい）搬送周波数であり、□は搬送波位相である。例えば伝送（例えばチップ）レートは１．０２３ＭＨｚであり、Ｆ（ｔ）は１０２３チップの長さを有し、ＰＮフレームレートは１ｋＨｚであり、Ｐ（ｔ）は長さＫ□１０２３チップを有する。
【００４４】
等式（Ａ１）は搬送波の複素数表現であり、これは直角サンプリング方法が信号の処理に使用されるならば有用であり、勿論、他の表現も適切なときに使用されることができることに注意する。実世界の状態では、種々のパラメータは完全に安定とはいえないが、説明目的で、信号振幅と種々の変調レートがほぼ一定であることを想定することが認識されるべきである。
【００４５】
図４は、等式（Ａ１）で説明された理想的なＧＰＳ信号の構造を表す図である。ＧＰＳ信号は45で示されている一連のＰＮフレームから構成されており、それぞれ特定の擬似雑音（または“ＰＮ”）シーケンスにしたがって二相変調された波形Ｆ（ｔ）46と、搬送周波数47を含んでいる。Ｆ（ｔ）の個々の反復は“ＰＮフレーム”と名づけられている。各ＰＮフレームは予め定められた期間Ｔｒを有する。48で、データシーケンスｄ（ｔ）のデータ遷移が示されており、これは示されているＰＮフレームのうちの１つの開始において生じる。しかしながら、データシーケンスｄ（ｔ）は比較的低速度なので、（米国のＧＰＳ Ｃ／Ａコードでは）データ遷移48は２０ＰＮフレームに一度のみ生じ、それ故データ遷移は任意に選択されたＰＮフレームの開始で生じるかまたは生じない。
【００４６】
各ＧＰＳ衛星（ＳＶ）は46で示されている特有のＰＮ波形Ｆ（ｔ）を送信し、これは予め定められたレートで送信される一連のシンボル（チップ）である。ＰＮ波形は、搬送波の二層変調に使用される特定のＰＮシーケンスによって、相互から弁別される。例えばこれらのシーケンスは米国のＧＰＳシステムのＣ／Ａ波形では、ゴールドコードの１セットから選択されることができる。
【００４７】
１つの例では、チップレートは１．０２３ＭＨｚであり、したがってＰＮフレームレートは約１ｋＨＺである。この波形Ｆ（ｔ）は連続して反復され、例えば第１の衛星ＳＶ１からの第１のコードは特有のシーケンスＦ１（ｔ）を繰返し送信し、ＳＶ２は特有のＰＮシーケンスＦ２（ｔ）を繰返し送信する。ＧＰＳ受信機は、視界内にある得る全てのＧＰＳ衛星の特有のＰＮシーケンスでプログラムされる。これらのＰＮシーケンスは特定の衛星を識別するためのアルゴリズムで使用されることができ、特に衛星の信号がＧＰＳ受信機で受信されるとき、ＰＮシーケンスは受信された信号を送信した衛星の識別に使用される。しかしながら、初めは、ＧＰＳ受信機は実際の受信されたコード位相のエポックを知らず、これは前述したように全ＰＮフレームにわたる距離（例えば１ミリ秒の期間或いは１０２３チップ）であってもよい。さらに、受信機は、特定のＰＮコードに関連されるＧＳ信号が検出可能であるか否かを知らない。それはこの信号が種々の障害により減衰されるかおよび／または特定のＳＶが視界内ではないからである。それ故、受信機は、仮説された信号の検出を試みるためエポックの不確定の距離にわたって直列または並列にサーチし、受信されたＧＰＳフレームのエポックを、ローカルに発生された基準フレームと整列しなければならない。
【００４８】
実際のＧＰＳ環境では、ＧＰＳ受信機は等式（Ａ１）で特定された理論信号のような、それぞれ特有のＰＮシーケンスＦ（ｔ）を有する多数の信号を同時に受信する。例えば、典型的な状態では、ＧＰＳ受信機は任意の時間に種々の視界内の衛星から８乃至１２の信号を典型的に受信し、種々のパラメータは、例えばパスの長さ、到着方向、ドップラ周波数シフトが異なるために、相互に異なっている。説明の目的で、等式（Ａ１）の理論形態の信号のうちの１つを処理することを最初に説明し、その後、ここで説明する処理アルゴリズムがどのように多数の信号の処理に使用されることができるかを証明する。それぞれの信号は等式（Ａ１）の理論形態を有する。
【００４９】
ＧＰＳ信号が受信機に到達するとき、これらはしばしば付加的な雑音により非常に崩壊され、恐らく、他の雑音または緩衝によっても崩壊される。さらに搬送周波数及びチップレートは主にドップラ効果によって、その本来の値から僅かにシフトされると考えられることができる。したがって搬送周波数は、ＳＶの動作とＭＳの動作により、ＭＳの受信機により観察されるとき僅かにシフトする可能性があり、それ故受信機が信号を受信するとき、実際に受信された搬送周波数はその理想的な予め定められた搬送周波数ｆ０から、“残留周波数”と呼ばれる量だけ変化する可能性がある。さらに、ＭＳ局部発振器のエラーは搬送周波数をその理想的な周波数から変化させる。
【００５０】
図３を参照すると、31で搬送周波数は、適切な周波数変換回路によってＧＰＳ信号から“取り除かれ”、残留周波数ｆｅを残す。搬送周波数を除去するために、ＧＰＳ信号は典型的に、最初にミキサによって中間周波数（ＩＦ）へ変換され、その後、任意の適切なアナログまたはデジタル技術により、残留するＩＦ成分をほぼゼロまで減少するように処理される。例えば、ＩＦ周波数は別のミキサにより、ほぼ除去されることができ、またはアナログデジタル変換器で、ＧＰＳをデジタル信号に変換後、デジタル処理混合技術が使用されてもよい。幾つかの構造では、周波数変換回路は小さい既知の周波数オフセットにプラスして前述の残留周波数を有する最終的な周波数を提供できる。この小さい既知の周波数オフセットは、一定であることが知られているので、その後の処理は残留周波数の決定だけを必要とする。以下の説明を簡潔にするため、この小さい既知のオフセットをゼロと想定する。しかしながら、ここで説明する方法及び装置はこのような既知のオフセットがゼロではないケースにも同等に応用可能である。
【００５１】
典型的に、残留周波数は主にドップラ効果により生じる。さらに受信機自体は信号の処理期間中に僅かな周波数シフトを誘発し得る。理想的な搬送周波数からのこれらの２つのエラーの和は、ある最大の許容度（Δｆ）により表されることができる。それ故、実際の受信された搬送周波数は典型的にｆ０±Δｆの範囲内である。残留周波数は多かれ少なかれ、状況の任意の特定のセットにあるが、受信機がオリジナル搬送波をゼロまで減少することを試みた後に残る周波数に等しい残留周波数ｆｅは、典型的に数百ヘルツから数ｋＨｚの範囲にある。
【００５２】
Ａ−ＧＰＳシステムでは、全てのＧＰＳ信号における予想されるドップラ補正はＰＤＥからＧＰＳ受信機へ（１形態または別の形態で）送信され、視界内にある得るＧＰＳ衛星のリストはまた受信機に送信され、それによってＧＰＳ受信機は衛星信号をさらに効率的にサーチできる。予想されるデータストリームはまたＰＤＥによって提供されることもできる。
【００５３】
そのメモリ内で、受信機は視界内にあり得る全てのＧＰＳ衛星に対応するＰＮコード（またはこれらのコードのＤＦＴのようなその表示）を記憶している。
【００５４】
32で、処理されたＧＰＳ信号は（前もって変換されていないならば）アナログデジタル変換器で、予め定められた時間にわたってデジタル化（即ちサンプル）され、その後ＧＰＳ受信機のバッファメモリに記憶される。サンプルレートが１．０２４ＭＨｚの倍数であり、データセットのサイズが１０２４の倍数であることが時折有用であるが、データセットのサイズ、またはデータのサンプルレートには理論的限定はない。それ故、等式（Ａ２）の信号はサンプルされた信号であると考慮され、ここではサンプルレートは１．０２４ＭＨｚまたは２．０４８ＭＨｚの数に設定されることができ、それによって１０２４または２０４８サンプルは１ミリ秒のＰＮフレーム期間にわたって生じる。ドップラ誘発エラーによって、このサンプルレートはチップレートまたはそのチップレートの２倍に全く等しいわけではない。このサンプルレートを選択する１つの理由は、サンプリングが１．０２４または２．０４８ＭＨｚで実行されるならば、結果的なサンプル数は、１ミリ秒フレーム期間にわたって、２の累乗であり、これは効率的なＦＦＴで便利である。即ち、データの１フレームは１０２４サンプルの倍数であり、効率的なＦＦＴで便利なサイズであり、（コヒーレントな処理における）総データセットサイズも１０２４の倍数であり、２の累乗×この長さである。しかしながら、フレーム当りのサンプル数が２の累乗ではないときに効率的なアルゴリズムが依然として存在するので、この限定は絶対的ではない。
【００５５】
33で、コヒーレント処理のためのデータブロックは、予め定められたコヒーレントな処理期間Ｔｃにわたって、記憶されたデジタルデータの一部を選択することにより規定される。データがコヒーレントな処理で組合わされる時間期間は典型的に、ＰＮフレームの大きい整数（例えば２０ＰＮフレーム）を含むように選択される。コヒーレントな処理ブロックはしかしながら、長い時間期間にわたる残留搬送周波数の安定性とその他のマルチパス効果（及び恐らく他の要因）が性能の改良を限定するか妨げる可能性があるので、非常に長いようには選択されるべきではない。以下説明するように、Ｔｃを１ＰＮフレーム期間Ｔｒの厳密な倍数になるように選択することが有効であろう。
【００５６】
図４をさらに参照すると、ＧＰＳ信号は時間Ｔｃにわたり観察され、これは第１のデータブロック49aまたは第２のデータブロック49bのようなデータブロックを規定し、時間Ｔｃはデータブロックが整数個のＰＮフレーム45を有するように選択される。実際のデータブロックはＰＮフレームが開始するときを前もって知らされずに受信されるので、データブロックの開始及び終了はＰＮフレーム境界内のどこにでも存在できる。例えば、データブロックは偶然に、49a（コード位相オフセット＝０）で示されているように、第１のフレームの開始から最後のＰＮフレームの最後まで延在できるが、より多くの可能性としては、データブロックは（49bで示されているように）第１のＰＮフレームの中間地点の何れかの場所から、最後の全ＰＮフレームに続くフレームの中間地点の何れかの場所まで延在し、それによって、コード位相オフセットはゼロに等しくない。図３のステップ39乃至42を参照して説明するように、例えばコード位相オフセットは整合フィルタ動作を使用して決定されることができる。
【００５７】
図３の34で、データシーケンスは随意選択的に除去される。データシーケンスｄ（ｔ）が除去され、等式（Ａ１）の理論信号が残留信号ｓｂ（ｔ）のベースバンドに近い周波数に変換された後、無視する雑音と干渉は以下の形態を有する。
ｓｂ（ｔ）＝ＡＰ（ｔ）ｅｘｐ（ｊ２□ｆｅｔ＋□） （Ａ２）
ここでｆｅは搬送周波数をほぼベースバンドに変換した後の残留周波数である。
【００５８】
随意選択的であるが、処理前にデータシーケンスｄ（ｔ）を除去することが有用であろう。データシーケンスの除去を助けるため、幾つかのＡ−ＧＰＳシステムでは、予想されるデータシーケンスｄ（ｔ）は、ＧＰＳ信号の幾つかのおおよその到着時間と共に、（例えばサーバから）ＧＰＳ受信機へ送信される。これらの場合、ＧＰＳ受信機はデータシーケンスｄ（ｔ）を除去でき、それ故、データシーケンスｄ（ｔ）により等式（Ａ１）の信号で２０ミリ秒毎に生じ得る擬似ランダム極性反転を除去できる。ランダム極性反転の除去により（即ちｄ（ｔ）の除去により）コヒーレントな積分時間は１データビット期間よりも長い時間、例えば１００ミリ秒よりも大きい時間の間隔まで増加されることができる。コヒーレントな積分時間の増加はＧＰＳ捕捉プロセスの感度を改良できる。先に示したように、ＧＰＳの幾つかの将来のモードは、データを含まないシグナリング成分を含むことができる。これらの状態では、コヒーレントな積分期間は１つのデータビット期間に限定されない。
【００５９】
図３を再度参照すると、搬送周波数は式（Ａ２）の信号ｓｂ（ｔ）に残留周波数ｆｅを提供するためにおおよそ除去され、ブロック期間ＴｃはＰＮフレーム期間Ｔｒの厳密な倍数であるように選択された。換言すると、Ｔｃ＝ＫＴｒであり、ここでＫはブロック期間のフレーム数である。例えばＫ＝１００で、Ｔｒ＝１ｍｓｅｃであるならば、Ｔｃは１００ミリ秒であることができる。
【００６０】
35で、データブロックはフーリエ変換プロセスを使用してコヒーレントに処理される。このステップは“順方向変換”プロセスと呼ばれることができる。例えば時間期間Ｔｃにわたってサンプルされた信号ｓｂ（ｔ）の高速度フーリエ変換（例えばＦＦＴまたはＤＦＴ）は次式のように行われることができる。
ｙ（ｆ）＝ＦＦＴ（ｓｂ（ｔ）、ｔ＝０からｔ＝Ｔｃまで） （Ａ３）
順方向変換プロセスは種々の方法で実行されることができる。１つの良く知られた方法は、時間におけるデシメーションであり、別の方法は周波数におけるデシメーションである。チャープｚ変換または数理論変換のような、１つの高速度アルゴリズムが適切または有用であるとして使用されることができる。
【００６１】
（例えば図９で示され、それを参照して説明する）随意選択的な信号のＦＦＴはデータブロックが処理されている期間の逆数により、周波数において分離される一連のデータ周波数サンプルを含んでいる。例えばブロック期間（Ｔｃ）が２０ミリ秒であるならば、周波数サンプルは５０Ｈｚだけ隔てられる。ブロック期間が８０ミリ秒であるならば、周波数サンプルは１２．５Ｈｚだけ隔てられる。各データ周波数サンプルはその周波数Ｈｚにより、より便宜的にはその周波数インデックスにより識別されることができる。特に、ＤＦＴの各データ周波数サンプルは整数（周波数インデックス）で指定されることができ、これは例えばゼロ周波数ではゼロインデックスで開始する。Ｎ点のＦＦＴでは、周波数インデックスＮ／２はサンプルレートの半分の周波数Ｈｚ、即ちＳ／２に対応する。インデックスＮ／２＋１，Ｎ／２＋２等を有する周波数サンプルは−Ｓ／２＋１／Ｔｃ，−Ｓ／２＋２／Ｔｃ等に等しい周波数Ｈｚに対応し、即ち、これらは負の周波数に対応するデータを表す。インデックスＮ／２，Ｎ／２＋１，Ｎ／２＋２，…，Ｎ−１，０，１，２，…，Ｎ／２−１を有するサンプルを選択することによってデータサンプルを配列し直すならば、周波数データは最も負の周波数で開始し、最高の周波数に進行する（Ｈｚにおいて）昇順で集合される。この配列のやり直しが例えば図５と図６で使用される。結果として、周波数インデックスは循環的であると考えられ、それによってインデックスｍはｍ＋Ｎとｍ−Ｎに等しい。それ故、インデックスＮ／２＋ｍはインデックス−Ｎ／２＋ｍに等しい。
【００６２】
図５は、前述の配列のやり直しをした、ゼロ（０）周波数に近い周波数の理論的に雑音のないＧＰＳ信号の周波数スペクトルのグラフである。図５はＰＮシーケンスの周期的反復による特徴外観を有するＦＦＴを示しており、これは米国のＧＰＳ Ｃ／Ａコードでは１ミリ秒毎に反復される。示されている雑音のないＦＦＴは、低エネルギを有する中間サンプル（図示せず）の数によって分離されている強力なエネルギを有するデータ周波数サンプル（スペクトルライン）51のサブセットを含んでいる。このようなスペクトルは時折“櫛形”スペクトルと呼ばれ、連続する強力なサンプル間の分離はＫの周波数インデックスの倍数にある。
【００６３】
特に、図５で示されている櫛形スペクトルは、２０ミリ秒の期間にわたり２０回反復され、サンプルされ、残留搬送周波数ｆｅ＝０であり、（グラフでは図示されていないが２０９ｋＨｚにおける）最大の振幅ラインで正規化されている、ＧＰＳゴールドコード＃１に対応するパワースペクトルにおける大きさ対周波数のグラフである。この例では、強力なエネルギを有するスペクトルラインのシリーズは約１０００Ｈｚ（１ｋＨＺ）により間隔を隔てられている。０．０Ｈｚライン51aは約−３８ｄｂの振幅を有し、１．０ｋＨｚライン51bは約−１１ｄｂの振幅を有し、２．０ｋＨｚライン51cは約−１３ｄｂの振幅を有している。強力なスペクトルラインの各対の間には、図５の対数グラフで表されているように振幅が非常に低い１９の中間ラインが存在している。例えば51aで、スペクトルラインは０Ｈｚと１０００Ｈｚに存在する。スペクトルラインは５０Ｈｚ、１００Ｈｚから９５０Ｈｚまで存在するが、低いエネルギを有するので、これらは図面では表示されていない。類似の解析が各強力なスペクトルラインの対に対して存在する。Ｈｚで測定された櫛形の強力なスペクトルラインの分離はフレームレートｆｒに等しい。周波数のインデックス差で測定されるのは、Ｋインデックス、即ちコヒーレントなデータブロックのフレーム数である。
【００６４】
図５が雑音が存在しない理論結果を示している一方で、図９に示されているような実際の受信された信号のＦＦＴは、スペクトルラインが直接的に観察されることができないこのような雑音を示している。図５の例では、52で示されているＦＦＴの平均雑音レベルは典型的に、最も強いスペクトルラインの振幅さえも超える。
【００６５】
図９をさらに参照すると、これは実際のデータに典型的な周波数内容（ＦＦＴ）が、概して90で示されている複数のデータ周波数のサンプルを含んでいることを示すグラフであり、これらの複数のデータ周波数のサンプルは集合的に“データ周波数セット”と名づけられている。データ周波数セットは（Ｓ−１／ＴｃのＨｚの周波数に対応する）最高の周波数インデックスまで延在する。各データ周波数サンプル間の周波数分離はブロック期間の逆数（即ちサンプル１／Ｔｃの時間期間の逆数）に等しく、それ故、オリジナルＦＦＴの順序付けが使用されると、最大のインデックスはＳＴｃ−１にある。
【００６６】
図５と異なり、図９の各データ周波数サンプル90は雑音を含み、それ故、（周波数インデックスＫにおける）周期的なスペクトルラインだけが多量のエネルギを有する図５の理論的ＧＰＳスペクトルとは異なって、多量のエネルギが各周波数インデックスで発見される。換言すると、雑音のために、受信されたＧＰＳ信号に関連されるスペクトルラインの振幅は雑音レベルよりも低く、それ故直接的に観察可能ではない。別の言い方をすれば、実際のデータのＦＦＴでは、平均雑音エネルギレベルは全ての周波数ラインと類似する可能性があり、それ故、図５の櫛形スペクトルは観察可能ではなく、その後の処理まで未知の状態であろう。
【００６７】
図３に戻ると、36aで、アルゴリズムを開始するために、初期想定が行われる。等式（Ａ１）で特定される理論信号のように、ＧＰＳＫ受信機は同時に多数の信号を受信し、それぞれ特有のＰＮシーケンスＦ（ｔ）を有し、それ故、それぞれそのＰＮシーケンスの特有のＦＦＴを提供することに注意すべきである。例えば典型的な状態では、ＧＰＳ受信機は典型的に８乃至１２の信号を、任意の時間に種々の視界内の衛星から受信するが、これらの信号の多くは非常に弱いために検出ができない可能性がある。それ故、何れの衛星が受信可能な信号を提供しているかについて不定であり、さらに、検出可能であっても、到着時間を決定する任意の受信可能な信号のコード位相オフセットは、演繹的に未知である。
【００６８】
36aで、視界内に存在し得る特定の衛星が選択されるかまたは“推測”される。任意の特定の衛星の選択はランダムであってもよく、またはＰＤＥにより与えられる経歴或いはリストのような任意の適切な情報に基づくことができる。以下説明するように。選択された衛星のＰＮコードは、少なくとも一致が発見されるか、全ての仮説がなくなるまで、（典型的に受信機により決定される距離内の）複数の周波数仮説にわたって検査され、その後36cで、次の衛星が選択され、全ての候補衛星が選択されるまで、または十分な数の衛星からの信号が位置の確定を完了したことが分かるまで、対応するＰＮコードが複数の周波数仮説にわたって検査される。
【００６９】
36aで、初期仮説が残留周波数に対して行われる。十分な情報がＧＰＳ受信機に利用可能である（例えば前もって位置確定が行われたか、評価されたドップラ補正が得られる）ならば、この初期仮説及びその後の仮説はこの情報に基づいて行われることができる。利用可能な情報がないならば、最良の推定が行われ、サーチが開始されることができる。
【００７０】
図３を再度参照すると、37で、仮説された衛星に対応するＧＰＳコードのフーリエ変換が行われる。事前にローカルに発生されまたは計算され、記憶されることのできるこのコードは時折、“基準”コードと呼ばれる。これらのＧＰＳコードはよく知られており、ＧＰＳ受信機のＧＰＳコード毎に値を予め計算し、記憶することが実行可能である。これらのＧＰＳコードはその後、ＧＰＳ受信機での記憶前または記憶後にフーリエ変換されることができる。例えばフーリエ変換（例えばＦＦＴまたはＤＦＴ）は、次式のように、Ｐ（ｔ）で示されるＰＮシーケンスＦ（ｔ）のＫ反復からなる基準データセットで実行されることができる。
Ｂ（ｆ）＝ＦＦＴ（Ｐ（ｔ）、ｔ＝０からｔ＝ＫＴｒ＝Ｔｃまで） （Ａ４）
この結果は図５に示されている例のように、一連の均等に隔てられたラインを含んでいる櫛形スペクトルであり、これは“基準周波数サンプル”と名づけられることができる。Ｂ（ｆ）のＫ番目の周波数サンプル毎にのみゼロではなく、ゼロではない値だけが記憶される必要があるので、即ち、必要な記憶を減少する。
【００７１】
しかしながら、反復されるシーケンスＰ（ｔ）のフーリエ変換を予め計算し、各ＧＰＳコードでゼロではないフーリエ変換された値だけを記憶し、必要なときはいつでも迅速な使用を可能にすることがさらに効率的であろう。これらのゼロではない値がＰ（ｔ）ではなくＦ（ｔ）のフーリエ変換から得られることを観察するのは容易であり、即ち計算上の負担を減少できる。反復されるシーケンスのＦＦＴはこの短いＦＦＴから得られることができるので、（Ａ４）で示されたように、通常は、Ｋ反復ではなくＦ（ｔ）の１反復のみのＦＦＴを計算することが十分である。また、基準ＧＰＳコードは通常、ゼロのコード位相オフセットと、ゼロの搬送周波数オフセットを有することが想定され、それ故、０．０Ｈｚを中心とすべきであり、図６ではなく図５のグラフ図に類似すべきである。
【００７２】
前述の計算の細部は、米国のＧＰＳ ＰＮコードが長さ１０２３であり、好ましいＦＦＴサイズが２の累乗であり、典型的にはこの説明では１０２４または２０４８であることに関する。ＦＦＴが予め計算されるならば、１．０２３ＭＨｚのサンプルレートに対応して、適切なサイズのＦＦＴを生成するための適切な手順が、基準の１０２３点ＦＦＴを実行し、インデックス512と513との間に余分なゼロ値のサンプルを添付する。同様に、２．０４６ＭＨｚのサンプルレートに対応して、適切なサイズのＦＦＴを生成するための適切な手順が、（チップ当り２サンプルでサンプルされた）基準ＰＮの２０４６点ＦＦＴを実行し、インデックス1024と1025との間に２つの余分なゼロ値のサンプルを添付する。これらの手順は周波数ドメインで行われる補間技術であり、時間ドメインの等価の再サンプリング方法の実行よりも、計算においては効率的である。いずれにせよ、反復される基準シーケンスのＦＦＴはその後、１ＰＮフレームのＦＦＴに対応する各基準周波数サンプル間に適切な数のゼロではない値のサンプルを単に挿入することによって計算されることができる。
【００７３】
データ周波数サンプルがブロック35でＦＦＴプロセスで最初に計算されたとき、残留周波数は知られていなかった。ＧＰＳ信号を正確に効率的に捕捉するために、この未知の残留周波数が発見されなければならない。残留周波数を決定するために、“試行錯誤”のプロセスが使用されることができ、一連の残留周波数は仮説され、各仮説で計算が行われ、その結果は位置をサーチするために解析される。仮説数は大きく、処理時間が検査される仮説数と共に増加する可能性があることを認識すべきである。
【００７４】
38で、37で与えられたデータ周波数サンプルのサブセットが、仮説された残留周波数に応答して選択され、即ち“枝刈り”される。図５で示され、それと共に説明されるように、理想的なＧＰＳ信号Ｐ（ｔ）は周期的な周波数スペーシングｆｒを有する櫛形スペクトルを有し、これはブロックのサンプル数により乗算されたＦＦＴ周波数スペーシングであリ、即ち（１／Ｔｃ）□Ｋ＝ｆｒである。この櫛形スペクトルは実際のデータ周波数サンプルの数分の１だけを占有するゼロではないサンプルを有するので、周波数サーチの複雑性および時間要求において減少が可能である。前述したように、Ｈｚで表される周波数スペーシングｆｒはＰＮフレームレートに等しい。インデックスで表すと、これはデータブロック中の反復されるＰＮフレーム（Ｋ）の数に等しい。
【００７５】
例えば、再度図９を参照すると、Ｋ＝２０であるならば、仮説された残留周波数に対応するデータ周波数サンプルは92aまたは92bのように、スペクトルラインの特定のグループの選択によって選ばれることができる。Ｐ（ｔ）は櫛形スペクトルを有するので、ベースバンドの、雑音のない受信された信号ｓｂ（ｔ）（等式Ａ−２参照）も同様であり、それはこの信号がＰ（ｔ）の周波数変換されたバージョンを含んでいるからである。しかしながら、ｓｂの実際の櫛形ラインは１ｋＨｚの厳密な倍数で位置付けられないが、残留周波数（図６参照）によりオフセットされ、これは決定される必要がある。
【００７６】
サンプリングレートが１．０２４ＭＨｚであり、ブロックサイズが２０ｍｓｅｃであり、ブロックには２０ＰＮシーケンスが存在するならば、受信される信号の隣接する櫛形ラインのスペーシングは１ｋＨｚであるので、認識可能なエネルギを有するＰ（ｔ）のＤＦＴの１０２４ラインだけが存在する。この櫛形スペーシングはサブセットを１０２４データ周波数ラインにのみ限定し、それ故、対応して減少するサイズの逆ＦＦＴがその後の処理で使用されることができる。
【００７７】
別の例として、サンプリングレートが２．０４８ＭＨｚであるならば、１．０ｋＨｚの櫛形周波数スペーシングを有する２０４８のゼロではない値の櫛形ラインが存在するが、エネルギはさらに大きい２．０４８ＭＨｚの通過域を超えて延在する。周波数分離の倍数であるレート（例えば１．０ｋＨｚ）でサンプルする必要はなく、サンプルレートが２の累乗×１．０ｋＨｚである必要もなく、ｓｂ（ｔ）の櫛形スペクトルは依然として残る。しかしながら、総サンプル期間Ｔｃが真の周期的なコンボルーションを実現するために１ミリ秒の倍数であることが望ましい。この要求は省かれることができるが、後に説明するように、幾らか性能を犠牲にするか、速度の劣化を招く可能性がある。
【００７８】
図６を参照すると、これは図５のように、約１．５ｋＨｚ（即ちｆｅ＝１．５ｋＨｚ）の残留搬送周波数を有し、（２０９ｋＨｚで生じる）最大の振幅ラインにより正規化されているスペクトルを有する、２０回反復された１例のＧＰＳ信号（コード＃１）のパワースペクトルのグラフである。図５及び図６の比較によって、両者のケースで櫛形スペクトルが存在することが示され、また図６のスペクトルはこの例では約１５００Ｈｚの残留周波数ｆｅにより、図５のスペクトルに関して単にオフセットされていることも示されている。それ故、１５００Ｈｚ（この例では真の搬送周波数オフセット）の仮説は信号エネルギを含む周波数ラインのセットを適切に選択する結果となる。図６のようにＧＰＳ信号スペクトルが現われても、（単なる櫛形サンプルではなく）各周波数サンプルで現れる図９に示されているような雑音によって妨げられる可能性がある。しかし、ＧＰＳ信号櫛形の周波数サンプル間で生じる雑音は、これらがＧＰＳ信号エネルギをほとんど含んでいないので、ＧＰＳ信号の検出には不適切である。したがって、ＧＰＳ信号の検出目的で、櫛形ライン位置の周波数情報だけを使用する必要がある。詳細に説明するように、各周波数仮説は、可能な櫛形周波数の異なるセットが処理されることを述べ、結果的に、これらの可能な櫛形周波数の異なるセットは、単に相互に循環的にシフトされたバージョンである。
【００７９】
用語“枝刈り”は、周波数データからＫ番目のサンプル毎にのみ選択していることを指している。従来の例では、Ｔｃは２０ＰＮフレームに等しく、Ｋは２０に等しく、即ちその後の処理で使用するためにＦＦＴデータの２０番目毎のサンプルだけを選択する必要がある。さらに一般的には、Ｋは処理されているコヒーレントなデータブロックのＰＮコードの反復数である。このような枝刈りはその後の処理量の減少につながる。
【００８０】
図９と図１０を参照する。図９はＧＰＳ信号を妨害する雑音を含む典型的なデータ周波数サンプルの例である。図１０は、（説明を簡潔にするために）仮説された正の周波数オフセットに対応するデータ周波数サンプルのサブセットを示す表であり、Ｋ番目毎のサンプルがいかにして、仮説された残留周波数の周波数選択のため、サブセットを規定するように選択されるかを示している。ゼロ周波数オフセットを仮説するため、選択を第１のサブセット92aに変換し、これは図９及び図１０の92aに示されている周波数インデックスゼロ（Ａ０，ＡK…）で開始するＫ番目毎のサンプルを含み、図１０の行０に対応する。１インデックス周波数オフセットを仮説するために、第２のサブセット92bが選択され、これはＫ番目毎のサンプルを含んでいるが、周波数インデックス１（Ａ１，ＡK+１…）によりオフセットされ、図１０の行１に対応する。２インデックス周波数オフセットを仮説するために、第３のサブセット92cが選択され、これは周波数インデックス１（Ａ２，ＡK+２…）でオフセットされるＫ番目毎のサンプルを含んでいる。各その次の周波数オフセットを仮説するため、時折、循環的なローテーションと呼ばれるこのプロセスは選択されたデータ周波数サンプルを整数によって変換することにより継続する。周波数オフセット数は（フレームレートを超えるレートに対応して）Ｋを超過することができる。
【００８１】
周波数データセットは循環的と考えられ、即ち周波数Ｋは例えばＫ−ＮおよびＫ＋Ｎと同様である。したがって、所定の行の最後の幾つかのデータサンプルは実際に、第１の行の第１のデータサンプルに対応できることが分かる。例えば92cでは、Ｋが２に等しいならば、92cの最後のインデックスはＮ−Ｋ＋２−Ｎ＝−Ｋ＋２＝０であり、92dの最後のインデックスはＮ−Ｋ＋３−Ｎ＝−Ｋ＋３＝１である。この例では、92cと92dの最後のエレメントはしたがって、それぞれＡ０とＡ１である。同様に、（表では示されていない）負の周波数オフセットは最初に“負の周波数”を選択することにより仮説された。１例として、最小の負の周波数仮説は、選択するデータＡ−１，ＡＫ−１，Ａ２Ｋ−１，Ａ３Ｋ−１，…，ＡＮ−Ｋ−１に対応し、これはＡＮ−１，ＡＫ−１，Ａ２Ｋ−１，Ａ３Ｋ−１，…，ＡＮ−Ｋ−１と同一である。したがって、このアレイの第１のサンプルは実際に、ＦＦＴの周波数サンプルの最後である。ＡＮ／２で開始するアレイの配列をやり直すことが便利であり、それによって周波数データの大半は周波数において増加する。
【００８２】
図１０では、列は“櫛形”周波数インデックス、即ちＮ／Ｋエレメントだけを有する枝刈りされたアレイのインデックスを示している。各行は仮説された櫛形周波数インデックスでの値を示している。勿論、負の周波数オフセットで開始する櫛形は許容され、前述したように構成される行を有する。
【００８３】
したがって、ＧＰＳ信号の存在を識別するのに有用な情報は、一定量（この例では１ｋＨｚ）だけ相互に変位され、残留周波数によりオフセットされているスペクトルライン内に実質的に含まれる。それ故、残留周波数の仮説に続いて、仮説された残留周波数に対応するその後の整合フィルタ計算目的で、その周波数オフセットに対応するスペクトルラインのセット（櫛形）はＦＦＴから選択されることができ、残りは無視される。この減少されたスペクトルライン数は必要とされる次の計算数を減少でき、したがって、各仮説された残留周波数の処理時間を減少する。例えば、ステップ39の整合フィルタ動作で必要とされる、サイズＳＴｃの逆ＦＦＴを行う必要がある代わりに、Ｓのサンプルレートが使用されるならば、サイズＳ／１ｋＨｚの逆ＦＦＴだけが実行される必要がある。したがって、Ｔｃ＝１２８ミリ秒であると想定すると、サンプルレートが１．０２４ＭＨｚであるならば、通常、サイズ１２８□１０２４の逆ＦＦＴを実行する必要がある。スペクトルの疎性（即ちＧＰＳ信号が櫛形スペクトルを有する事実）を利用して、サイズ１．０２４ＭＨｚ／１ｋＨｚ（即ち１０２４）の逆ＦＦＴの計算だけを必要とし、処理の節約は１２８（さらに正確には１．７□１２８）の係数を超える。さらに、処理の節約は、総コヒーレント処理時間Ｔｃが増加するときに改善される。それ故、ＦＦＴサイズの減少がＰＮシーケンスＦ（ｔ）の反復数に関連されることが分かり、即ちＦＦＴサイズの減少係数は、コヒーレントに積分されるＰＮフレーム数が大きい程改良される。
【００８４】
39で、データ周波数サンプルと基準周波数サンプル（例えばＧＰＳコード）のサブセットから相関シリーズを形成するための動作が実行される。これを実現するため、ＦＦＴベースの整合フィルタ動作が以下のように実行されることができる。
データ周波数の選択されたサブセットを、ＧＰＳコードのＦＦＴの複素共役によって乗算する。 （Ａ５）
等式Ａ５の結果の逆ＦＦＴを実行し、この結果的なデータセットで検出動作を行う。 （Ａ６）
結果として、Ｓｂ（ｔ）とＰ（ｔ）の循環的コンボルーションが生じ、これは適切な相関情報を提供し、Ｓｂ（ｔ）の期間がＰＮフレームの整数であることを想定する。この基本的な手順は期間Ｔｃの長いデータセットの処理を必要とし、即ちこの手順は大きいサイズの順方向ＦＦＴの実行を必要とした。しかしながら、よく知られているように、このような大きなＦＦＴを実行する効率的な方法が存在する。計算上の便宜さは、枝刈り手順のために、小さいサイズの逆ＦＦＴだけを行う必要があることから得られる。多くの逆ＦＦＴは多くの周波数仮説に対応して実行される必要があるので、計算上の節約が実現されることができる。これは後の説明で、さらに数学的に証明される。
【００８５】
説明の目的で、ステップ33−39の方法はコヒーレントな方法でデータの１ブロックの処理に対応しており、これはここでは“コヒーレントな相関”または“コヒーレントな処理”と呼ばれるタイプの相関である。感度を改良するため、複数のコヒーレントな相関プロセスからの相関出力は検出されることができ、相関結果を与えるため隣接する時間間隔の数（例えば２乃至２０００ブロック、典型的には５乃至２００ブロック）にわたり結合される。このプロセスは“非コヒーレント相関”と呼ばれ、図１１と共にさらに詳細に後述する。
【００８６】
図３の40で、相関結果（シリーズ）が、一致が発見されるか否かを決定するために解析される。この演算は以下説明するように、任意の数の適切なアルゴリズムで実行されることができる。
【００８７】
図７は、ステップ39の相関動作の結果の図例であり、仮説されたコード位相の関数として振幅を示している。ステップ39の整合フィルタ動作、又は相関演算の結果は“相関シリーズ”と呼ばれる。以下説明するように、多数の相関シリーズは改良された性能を提供するように（コヒーレントおよび／または非コヒーレントに）組合わされることができる。この組合わされたシリーズは、この数のシリーズが一致された状態を決定するために検査されることができるので、“最終的な相関シリーズ”と呼ばれる。図７に戻ると、グラフの結果として、異なるコード位相の一連のライン70は、典型的には１チップのインクリメントまたは２分の１チップのインクリメントで均等に隔てられている。一致が発見されたか否かを決定するため、任意の適切なピーク発見タイプのサーチアルゴリズムが使用されることができる。例えば、各ラインの大きさが考慮されてもよい。例えば、特定の仮説されたコード位相のラインの大きさが全てのラインの中で最大であり、その振幅が予め定められたしきい値を満たすかそれを超えるならば、一致が発見されたことを想定させることができる。図７では、ライン72が最大であるように見え、それ故、（例えば74で示されている）検出しきい値が予め定められたしきい値であるならば、ライン72のコード位相（即ちコード位相位置18）は一致を示すものと想定されよう。所定のしきい値を超える全てのピークを決定し、全てのこのようなピークを潜在的な一致として保持するような、その他のアルゴリズムが使用されてもよい。
【００８８】
図３を再度参照すると、ステップ40後、一致が識別されないならば、動作は決定ステップ41へ移動する。41で、サーチをされる残留周波数がさらに存在するならば、別の周波数仮説がステップ36bで行われ、ステップ37−40が反復される。しかしながら、サーチをされる残留周波数がこれ以上存在しないならば、動作は41から決定ステップ43へ移動し、以下説明するように、サーチするための衛星がさらに存在するか否かを決定する。ステップ40の決定に戻り、一致が発見されたならば、動作はステップ42へ移動し、ここでコード位相オフセットが決定される。
【００８９】
例えば図４を参照して前述したように、データブロックがサンプルされたならば、コード位相は知られておらず、即ちＰＮフレーム期間の開始と終了はまだ突き止められていない。特に、データブロックが整数個のＰＮフレーム45を有するが、データブロックの開始位置が知られておらず、それ故、データブロックの開始及び終了はＰＮフレーム内の何れかの場所に存在することができる。例えばデータブロックが偶然に、49a（コード位相オフセット＝０）で示されているように、第１のＰＮフレームの開始から最後のＰＮフレームの最後まで延在できるが、より多くの可能性としては、データブロックは49bで示されているように、第１のＰＮフレーム内の随意選択的に選択された点から、最後の全ＰＮフレームに続くフレーム内の同一点まで延在する（コード位相オフセット≠０）。
【００９０】
42で、正のサーチ結果に続いて（即ちステップ40で一致が発見された後）、コード位相オフセットはステップ39の整合フィルタ動作の結果から決定される。特に、整合フィルタ動作前に、可能なコードオフセット数が知られている。図７のここで説明した例では、可能なコードオフセット数はゼロから１０２３の範囲（１０２４点のＦＦＴが使用されるならば、全部で１０２４の可能なコード位相）であり、これは１ミリ秒間隔にわたるコード位相オフセットステップ数である。整合フィルタ動作後、（一致の存在を識別した）ライン72も、ゼロからのステップ数としてコード位相オフセットを示す。図７の例では、コード位相オフセットはコード位相位置18にあり、これはこの例では約１８／１０２４ミリ秒に変換する。この位相オフセットはＧＰＳ受信器内のローカルで発生されたクロックの位相に関連する。多くの場合、この位相オフセットの正確性は、特定されたコード位相におけるレベルを、その近傍のコード位相のレベルと組合わせる補間手順を通して改良される。
【００９１】
43で、付加的な衛星からの信号がサーチされるか否かについて決定が行われる。この決定は任意の適切な基準にしたがって行われる。例えば、十分な衛星からの信号が既に位置の確定を行ったことを発見したならば、または可能な視界内の衛星のリストが尽きたならば、サーチの停止をする決定が行われ、44で示されているように、捕捉動作が完了される。しかしながら、より多くの衛星からの信号がサーチされるならば、36cで、次の衛星が選択され、初期の残留周波数が仮説され、ステップ37−42が新しい想定で実行される。
【００９２】
ここで説明されるように、ＰＮシーケンスＦ（ｔ）がコヒーレント処理するデータブロックで複数回反復する知識を使用すると、さらに簡単な逆ＦＦＴ手順が全体的な整合フィルタ手順の一部として可能であることが分かり、そうすれば計算時間が減少する。唯一のドップラ仮説がサーチされるべきならば、処理時間における改良は特に大きい。しかしながら、サーチは通常、多数のドップラ仮説（例えば±５００Ｈｚにわたるサーチは普通である）にわたって実行されるので、ここで記述するようにこの処理の節約の利点はすぐに重要になる。処理を節約する１つの理由は、別々の逆ＦＦＴが実行されるべきことを各ドップラ仮説が必要とすることである。しかしながら、ここで説明する方法では、仮説された櫛形周波数位置での処理周波数サンプルだけを必要とする事実のために、逆ＦＦＴサイズはコヒーレントな周波数ブロックのサイズから独立している。このような周波数サンプルの数は、１ＰＮフレームにわたるデータ周波数サンプルの数と等しいことが容易に分かる。先の例では、１２８ミリ秒の処理プロックサイズでは、必要とされる逆ＦＦＴサイズは係数１２８だけ減少され、結果として、１２８よりも大きい係数だけ改良された処理速度である。大きい順方向ＦＦＴはステップ35のように行われなければならないが、この大きい演算はサーチされるＧＰＳコード当り一度のみ行われる必要があり、幾つかのケースでは、１つの順方向ＦＦＴは多数の仮説されたＧＰＳコードで共有されることができる。
【００９３】
典型的に、大きいドップラ範囲にわたってサーチするため、対応して大きい数のドップラ仮説が逐次的に作られ、代わるがわる実行され、したがって多数の逆ＦＦＴの実行を必要とする。例えば、残留搬送周波数ｆｅ＝±２ｋＨｚの範囲にわたってサーチするために、１２８ミリ秒のコヒーレントな積分時間では、複数のドップラ仮説が必要とされ、即ち、少なくとも５１２に等しい逆ＦＦＴ数（４０００ｋＨｚ×１２８ｍｓｅｃ）が実行される。前の例では、逆ＦＦＴサイズは１３１０７２ではなく１０２４点だけを必要とし、この結果、係数約２１８だけ計算時間を節約できる（ＦＦＴ処理時間はＮｌｏｇ（Ｎ）に比例し、Ｎは変換サイズであることに注意）。例えば、現在利用可能な技術を使用すると、１０２４点のＦＦＴは廉価のＤＳＰ集積回路を使用して、０．５ミリ秒以下で実行されることができ、逆ＦＦＴの全セットの全体的な処理時間は０．２６秒に満たない結果となる。一方、まばらなデータの利点を利用せずに、処理時間は約１分であることが可能である。さらに、多数の仮説されたＧＰＳ ＰＮコードにわたって検索しなければならないので、従来のＦＦＴ処理で必要とされる処理時間は実用的ではないが、開示した方法での処理時間は容易に実用的となる。
【００９４】
種々のドップラ仮説にわたるサーチは、ＦＦＴの隣接するスペクトルラインが予め定められた数、この例では１／ＴｃＨｚ（例えばＴｃ＝１２８ｍｓｅｃならば、１／Ｔｃ＝１／１２８ｍｓｅｃ＝７．８１３Ｈｚ）だけ相互から離れているということを認識することにより簡略化される。それ故、所定のＰＮコードでは、再度、各周波数において順方向ＦＦＴを実行する必要はない。周波数の仮説を変更するため、１インデックス位置だけｓｂのＦＦＴをシフトしさえすればよい（インデックス値は不必要な労力をせずに、信号の捕捉の見込みがあるよう、適切に決定される）。ｙをｓｂのＦＦＴに等しくする。サンプルレートが１．０２４ＭＨｚであり、Ｔ＝１２８ｍｓｅｃである例では、周波数仮説がゼロであるならば、０、１２８、２５６、…等の数を付けられたｙのサンプルを処理する。残留周波数仮説が７．８１３Ｈｚであるならば、１、１２９、２５７等の数を付けられたサンプルを処理する。残留周波数仮説が−７．８１３Ｈｚであるならば、１３１０７１、１２７、２５５等のサンプルを処理する（スペクトルは周期１３１０７１で周期的であるので、インデックス１３１０７１は−１に等しいことに注意）。各ケースで枝刈り処理を受けたブロックは、基準ＧＰＳ波形のゼロではないＦＦＴサンプルの複素共役により乗算される。結果は、１ＰＮフレームを表す整合フィルタ出力を与えるために逆変換される。
【００９５】
この出力のしきい値を超えて発見されるピークの大きさ（または二乗された大きさ）は、処理シーケンスで使用されたものに対応するＧＰＳ信号数とドップラ周波数を有している受信されたＧＰＳ信号の存在及び到着時間を表している。以下説明するように、幾つかのケースでは、インデックス数の数分の１だけＦＦＴをシフトすることが好ましい。これは以下説明するように、周波数セットの単なるローテーションまたはシフトではなく、周波数補間方法を使用して行われることができる。
【００９６】
図８のＡ、図８のＢ、図８のＣは、Ｔｃ＝２０ミリ秒であるときの場合の各３つの仮説された周波数（ｆｈ−５０Ｈｚ、ｆｈ、ｆｈ＋５０Ｈｚ）におけるそれぞれの整合フィルタ動作の実行結果の１例を示している（したがって順方向ＦＦＴのスペクトルラインは５０Ｈｚだけ分離される）。図８のＢでは、仮説された周波数は真の周波数であり、強力な検出されたピーク82は１つの特定のコード位相オフセット（インデックス18）で生じることが分かる。図８のＡ、図８のＣではそれぞれ、仮説された周波数は真の周波数を５０Ｈｚだけ下回るか超えることが分かり、それ故、これらの場合、インデックス位置18の強力なピークは（81および83で示されているように）もはや存在せず、検出しきい値を超える任意の他のピークも存在しないことが分かる。図を簡単にするために、図８のＡ、図８のＢ、図８のＣのプロットは３０までのコード位相インデックスだけを示し、一方１０２４点のＦＦＴが使用されるならば、そのインデックスは実際には０乃至１０２３の範囲であることに注意すること。
【００９７】
図３の方法はコヒーレントな方法によるデータの１ブロック処理に対応し、これはここでは“コヒーレントな相関”と呼ばれる相関のタイプである。しかしながら実際には、コヒーレントな相関は、弱いＧＰＳ信号を検出し、そのコード位相を測定するのに十分な感度をもつことができない。感度を改良するため、複数のコヒーレントな相関プロセス（即ち相関シリーズ）からの相関出力は検出され、組合わされることができ、この手順は“非コヒーレントな相関”または“非コヒーレントな処理”と名づけられている。特に、前述のステップ33−39のコヒーレントな積分プロセスは１以上の付加的な、隣接する時間間隔（典型的に５乃至２０００ブロックの範囲）で反復されることができ、その結果は検出され（例えばそれらの大きさまたは二乗された大きさが計算され）、組合せられる。
【００９８】
この変形は図１１により、さらに正確に理解されるであろう。図１１は、一致された状態をサーチする前に、多数の相関シリーズの組合せが行われる図３の変形である。図１１のブロックの番号付けは、先頭に“１”が付加されている点を除いて、図３の番号付けに類似している。例えば２つの図面の上部ブロックである“ＧＰＳ帯域のエネルギを観察する”が30と130で示されている。図１１は多数の相関シリーズの後検出累算に関連される付加的な処理を含んでいる。即ち、データの多数のブロックにわたって反復するブロック147の出力から138の入力へのフィードバックループが主に付加されている。多数の相関シリーズの組合せが146で実行される。
【００９９】
図１１を吟味すると、133で、33の単一のブロックと比較して、長さＴｃの多数のブロックに対応するデータを選択したことが分かる。その後、ステップ134で、各個々のデータブロックでＦＦＴを実行する。このデータはその後、典型的に、後に使用するためにバッファに記憶される。ステップ136aと137は36aと37と同一である。ステップ138と139はその後、（所定のＳＶと残留周波数に対応する）基準周波数サンプルと所定のデータブロックの周波数サンプルからの相関シリーズの計算の一部として、枝刈りアルゴリズムを使用する。これは38と39に類似している。しかしながら、ステップ146で、結果的な相関シリーズを、先のデータブロックで類似して実行されたものと組合わせる。典型的に、この組合せは、大きさ、二乗された大きさのタイプの検出動作を相関シリーズにおいて実行し、その後、その結果を先のブロックで類似して行われたものに付加することにより行われる。幾つかのケースでは、組合せは単なる付加または他のコヒーレントな組み合わせであってもよい。後者のケースは、大きいデータセットでコヒーレントな処理を行う能力を計算のリソースが限定する場合に、適切である。
【０１００】
147で、右への分岐は、全てのデータブロックが処理されていない場合に、次のデータブロックで138、139、146の処理を反復するためのものであり、その点（147）で処理の流れは140へ進む。処理が140へ進むとき、一致される状態を決定するために所望な全ての相関シリーズを組合わせる。この点で組合わされた相関シリーズは“最終的な相関シリーズ”と呼ばれる。図３で説明した方法と類似の方法で、最終的な相関シリーズは一致された状態、典型的には検出しきい値を超えるピークで検査され、対応するコード位相オフセットが発見される。
【０１０１】
先の説明では、動作138、139、146はデータの連続するブロックで反復されるが、仮説されたＳＶ、基準周波数サンプル、残留周波数は各反復で同一であることに注意する。140で一致が発見されないならば、（セットが完全にサーチされていないならば）新しい残留周波数が136bで選択され、処理138、139、146は第１のデータブロックで新たに開始する（145はブロック番号を再度初期化する）。ステップ135で、全てのデータブロックにおいてＦＦＴを先に計算したので、仮説された次の残留周波数を変更するときに、さらに順方向ＦＦＴを行う必要がない。即ち、各データブロックの周波数サンプルはバッファに記憶されており、それぞれその後の残留周波数仮説で再使用されることができる。
【０１０２】
一致が発見された後、または全ての残留周波数が尽きた後、処理は143へ進み、ここでさらにＳＶが検査を必要とされるならば、136cで、次のＳＶと初期周波数を選択し、ステップ133へ進む。データシーケンスが存在しないときのような、いくつかのケースでは、この点でステップ136aへ代わりに進み、先のＦＦＴ演算により既に計算された135からのデータ周波数サンプルを再使用する。
【０１０３】
以下の説明はここで説明される１方法の動作の１説明である。
【０１０４】
最初に、逆ＦＦＴ演算が行われる方法を考慮する。最初にサンプルされた時間データはｘ（ｎ）：ｎ＝０，１，２，…，として表されることができ、これはデータサンプルｘ（０），ｘ（ＴＳ），ｘ（２ＴＳ）の簡略表記であり、ここでＴＳはサンプル時間期間である。このサンプルされたデータのディスクリートなフーリエ変換（“ＤＦＴ”）はｙ（０，１，２，…）により示される。このデータのＤＦＴは周波数０，１／（ＮＴＳ），２／（ＮＴＳ）…，ｍ／（ＮＴＳ）,…，における周波数サンプルを効率的に示し、ここでｍはサンプル数である。ＤＦＴｙ（ｍ）は各ｍにおいて、次式によって示される。
【数１】
【０１０５】
循環的な対称により、インデックスｍに対応する周波数（即ち周波数ｍ／（ＮＴＳ））はインデックスｍ−Ｎに対応する周波数（即ち周波数（ｍ−Ｎ）／（ＮＴＳ））に等しいので、Ｍ＞Ｎ／２に対応するＤＦＴの周波数は、実際には負の周波数である。ここで、この説明目的で、１）ＧＰＳフレーム期間がＲ入力サンプルに対応し、２）先のように、任意の衛星データは除去されており、３）ブロックサイズＮはＫフレームに対応し、即ちＫ＝ＫＲであり、４）信号変調における任意のドップラ効果は無視できる程度であることを想定する。これらの想定はＦＦＴアルゴリズムが周期的なコンボルーションを行うことを可能にする。
【０１０６】
前述したように、整合フィルタ動作は根本的に、信号データと、周期的に反復された基準の循環コンボルーションであるので、Ｒサンプルを整合フィルタ動作から発見することにのみ関心がもてる。したがって、整合フィルタ結果も周期Ｒにより周期的である。これらの状態下で、既知の方法により、等式（Ｂ１）のｙ（ｍ）における演算によって整合フィルタ出力を与えることができる。
【数２】
【０１０７】
ここでｇは、Ｋ回反復された［ｘ（ｎ）と同一のレートでサンプルされた］ＧＰＳ基準ＰＮ波形のＦＦＴであり、＊は複素共役を表し、ｒは出力時間変数であり、これは［０，１，…，Ｒ−１］にわたる範囲だけを必要とする。等式（Ｂ２）では、信号ｙ（ｍ）の残留搬送周波数はゼロであることを仮説している。前述したように、ＰＮシーケンスはフレーム毎、即ちＲサンプル毎に周期的であるので、関数ｇ（ｍ）は（周波数において）Ｎ／Ｒ＝（ＫＲ／Ｒ）＝Ｋサンプル毎にゼロではない値を有する。例えばＮがＧＰＳデータの２０フレームに対応するならば、ｇの（最初から開始する）ＦＦＴの２０番目毎のサンプルがゼロではない。したがって、等式（Ｂ２）の和内の積は２０番目のサンプル毎にのみゼロではなく、したがって（Ｂ２）を次式のように書くことができる。
【数３】
【０１０８】
最後の和はＲ点の逆ＤＦＴである。したがって、整合フィルタ動作で必要とされる逆ＤＦＴがＲサンプルＦＦＴアルゴリズムだけを使用して行われてもよいことが示されており、これは処理時間とメモリの要求を減少する。さらに、データＫのＰＮフレームが幾つ処理されても、前述の条件が満たされる限り、Ｒ点の逆ＤＦＴだけが必要である。等式（Ｂ３）は全Ｎ点の逆ＦＦＴが等式（Ｂ２）のように実行される場合に得られる等式と数学的に同一であることに注意する。等式（Ｂ３）は逆ＦＦＴの実行においてｙのＦＦＴからのＫ番目の点毎の選択を明白に示していることにも注意する。これは“枝刈り”手順、即ち逆ＦＦＴを行うための点のサブセットの選択のベースである。等式（Ｂ３）は、仮説された残留搬送周波数エラーが正しいか否かを決定する。しかしながら、このプロセスは、残留搬送周波数エラーが１／Ｔｃと比較して、小さいときに強力な検出指示を発生するだけである。
【０１０９】
前述の等式（Ｂ３）は、残留搬送周波数をゼロと想定して、変換されたデータサンプルの処理に対応する。これは残留周波数がゼロに近いときのみ強力な相関ピークを発生する。この想定を変更するため、ドップラシフトはｄ／（ＮＴＳ）であると想定され、ここでｄは整数であり、等式（Ｂ３）は以下のように変更される。
【数４】
【０１１０】
ここで［］ｍｏｄ Ｎは、括弧を付けられた量のモジュロＭである。本質的に、ドップラ仮説が正しいことを想定して、ゼロではない（即ち１／Ｔｃよりも非常に小さい）残留周波数を有するように、入力信号を周波数シフトしている。等式（Ｂ４）はｙの循環特性を利用する。この変換は、単にｄスペクトルラインによるｙの単なる周波数変換であり、ｙの第１のエレメントに関してｄ位置で開始する（循環方法による）シーケンスｙをインデックスすることにより率直に実行されることに注意する。この方法は、背景部分で説明した従来の制限をなくし、そうでなければ、この従来の制限は約−５００乃至５００Ｈｚよりも大きい範囲にわたるサーチを効率的に限定する。ドップラ仮説ｄにおける唯一の制限は、時間ドップラ効果（即ち信号変調におけるドップラ）による、ｙの拡張に関する盲目的な制限である。この制限は以下説明するようにして除去されることができる。
【０１１１】
等式（Ｂ４）の１つの便利な面は、異なるＧＰＳコードを処理するために、別の順方向変換を行う必要がないことである。幾つかの状態では、“ｇ”の適切なＧＰＳコード（例えば適切なゴールドコード）は先の式に代入されることができ、従来変換されたデータが使用され続けることができる。これは、２以上の同時に受信されたＧＰＳ信号に存在する衛星データ情報（メッセージ）が実質的に同一であるならば、行われることができる。この状態により、同時に受信された信号におけるデータ送信を同時に除去することが可能である。これは２つの条件が満たされた場合に可能であリ、その条件は（Ａ）衛星からの差距離がかなり小さい（例えば３００ｋｍ内）ことと、（Ｂ）メッセージデータ情報がＳＶ送信間で類似であることである。項目（Ｂ）は例えば衛星の暦が送信されるとき、しばしば生じる。また項目Ｂはコヒーレントな積分時間が２０ミリ秒よりも小さいならば、重要ではない。、将来の構造で提案されているような、データを含まないＧＰＳモードでは、条件（Ｂ）は適用せず、この変形はさらに一般的に行われることができる。
【０１１２】
先の説明では、（受信機の基準局部発振器が誘発する“ドップラ”を含めた）ドップラシフトの効果は主に搬送周波数に影響することが想定されている。しかしながら、コヒーレントな積分時間ＮＴＳが十分に大きくなるならば、信号の変調における（即ちＰＮシーケンスＰ（ｔ）における）ドップラの効果を無視することができない可能性がある。本発明の目的では、この変調のドップラ効果、または“時間ドップラ”効果は、主に変調レートを変更し、その結果、ＧＰＳ受信機で発生された基準に関する信号波形の“拡張”または“圧縮”が生じる。
【０１１３】
例えば、ＧＰＳの標準的な位置サービス（民間サービス）のためのＣ／Ａコードを処理するため、チップ変調レートに対する搬送周波数の比は約１５７５．４２ｅ６／１．０２３ｅ６＝１５４０である。したがって搬送波における約５００Ｈｚのドップラシフトは変調において約５０００／１５４０＝３．２５Ｈｚのドップラシフトになる。データの短いブロック（例えば２０ミリ秒）をコヒーレントに処理するため、このような時間ドップラは重要ではない可能性がある。しかし、データの長いブロックを処理するとき、その効果は整合フィルタのピーク出力の大きさを減少することによって、システムの感度を劣化する可能性がある。経験則として、（局部発振器効果を含める）変調ドップラがｐヘルツであるならば、総ブロックサイズＮはＴｃ秒に対応し、付加的な処理なしに、量ｐＴｃは有害作用を減少するために約１／２よりも下に維持されるべきである。
【０１１４】
搬送波における１０，０００ＨｚのドップラシフトがＰＮ変調における７．１４３Ｈｚドップラシフトを生じる前述のケースを考慮する。コヒーレントなブロックサイズが約１００ミリ秒であるならば、ｐＴｃは＝０．７１４３であり、システム性能における幾らかの劣化が顕著であろう。さらに、整合フィルタからのピーク出力の時間が、ゼロではないドップラのケースに関してｐＴｃ／２チップにより変位されるであろう。したがって大きいドップラサーチ範囲と、長いコヒーレントな積分時間は、修正されていない状態であるならば、時間ドップラ効果からの損失になる。この問題は特に以下の２つの重要な状態で増幅される。
（１）ＧＰＳ受信機により観察されるように、１つのＧＰＳ衛星信号から別のＧＰＳ衛生信号へのドップラシフト間の大きな差。この項目については既に前述した。
（２）ＧＰＳ局部発振器周波数のその理想的な周波数に関するエラーによる効率的なドップラシフト。
【０１１５】
項目（２）に関して、ＧＰＳ局部発振器は理想的なＧＰＳ周波数から異なる可能性がある。例えば、時折、ＧＰＳ受信機は、同期されたセル電話の周波数からその局部発振器周波数を得ることができ、したがって低エラーを実現できる。しかしながら、幾つかの状態では、これは可能ではないことがある。良好に温度補償された水晶振動子でさえもＧＰＳ周波数（１５７５．４２ＭＨｚ）で、±３０００Ｈｚを超える周波数エラーを有する可能性がある。このような周波数エラーは真のドップラシフトではないが、これらは移動するプラットフォームから観察されるドップラシフトに類似して、ＧＰＳ受信機で搬送波と変調シフトの両者を発生する。このような周波数エラーは全てのＧＰＳ受信機に対して共通であり、それ故、ある程度まで処理された全てのＧＰＳ信号に影響する。それにもかかわらず、これらの周波数エラーは特に、長いコヒーレントなブロックサイズでは劣化した性能を生じ得る。
【０１１６】
前述の問題に対処する１方法は、ＧＰＳ ＳＶ（衛星ビークル）のドップラ仮説に釣り合うレートで、および／または局部発振器エラーのために、入力データシーケンスを再度サンプルすることである。信号の再サンプリングにより、デジタル信号処理方法を使用して、入力信号は結果として拡張または圧縮されることができ、それによってコヒーレントな処理ブロック内には再度、ＧＰＳデータのＰＮフレームが整数個、存在する。このような再サンプリングなしでは、コヒーレントなブロック中のこのようなフレームの数はもはや整数ではないが、多かれ少なかれ幾つかのサンプル数程度に大きい量であり、これは整合フィルタ動作により発生するピーク信号の深刻な劣化を生じる可能性がある。
【０１１７】
しかしながら、時間ドメインにおける再サンプリングは、周波数の範囲及び所定のＳＶで、再サンプルし、大きい順方向ＦＦＴを実行することを必要とする可能性がある。前述したように、その範囲は｜ｐＴｃ｜が約１／２よりも小さい。残念ながら、この多数の順方向ＦＦＴを実行する要求は、システムメモリ増加の要求と、処理時間の増加との両者を生じる。
【０１１８】
しかしながら、周波数ドメインで再サンプリング機能を行うことにより、前述の欠点は削除され、特に付加的な順方向ＦＦＴを実行するための要求は削除される。換言すると、再サンプリング機能は時間ドメインではなく、変換された信号ｙで実行されることができる。この方法は付加的な順方向ＦＦＴを実行する要求を回避するが、構成にしたがって、幾つかの付加的な記憶が必要とされる可能性がある。
【０１１９】
周波数ドメインの再サンプリングの裏付ける基本的な原理は以下のフーリエ変換関係式から説明されることができる。
【数５】
【０１２０】
ここでｘは時間波形であり、ｙはｘのフーリエ変換であり、ａはスケールシフトまたは拡張である。このようにして、何れかのドメインの拡張が行われることができる。
【０１２１】
拡張または圧縮は周波数サンプルの再サンプリング、即ち部分的再サンプリング方法を含むプロセスを含んでいる。（Ｂ５）から、周波数サンプルがｙ（ｍ）と呼ばれ、したがってこれらのサンプルが最初に周波数ｍ＝［０，１，２，…］／（ＮＴＳ）で与えられるならば、これらのサンプルは周波数ｍ／ａで推定されるサンプルによって、即ちｍｒ＝［０，１，２，…］／（ａＮＴＳ）＝［０，１／ａ，２／ａ，…］の周波数で推定されるサンプルによって置換されることが分かる。
【０１２２】
データサンプルが対称的に約０Ｈｚ隔てられることを確実にしなければならないので、この最後の結果は正の周波数で補正されるだけである。これを行うため、初期セットを−Ｎ／２−１，−Ｎ／２，…−１，０，１…，Ｎ／２−１，ｎ／２の順序に順序付けし直すならば、再度サンプルされるセットは周波数で再度サンプルされる。
［（−Ｎ／２−１）ａ，（−Ｎ／２）／ａ，…，−２／ａ，−１／ａ，０，１／ａ，２／ａ，…，（Ｎ／２）／ａ］／（ＮＴＳ） （Ｂ６）
即ち、オリジナルの順序を使用するならば、周波数において再度サンプルされる。
ｍ／ａ：ｍ＝０，１，２，…，Ｎ／２の場合 （Ｂ７）
N＋(ｍ-Ｎ）/ａ：ｍ＝Ｎ／２＋１，Ｎ／２＋２，…，Ｎ−１の場合 （Ｂ８）
ここで、周波数インデックスｍがｍ＋Ｎまたはｍ−Ｎと同一であるような周波数の循環特性であることに注意する。
【０１２３】
等式（Ｂ６）または（Ｂ７）の再サンプリングは、ＤＦＴにより推定される通常のディスクリートな周波数の“間”にある周波数の周波数応答を推定することを含んでいる。これは例えば“ｓｉｎｃ”補間回路により行うのが比較的容易である。入力データは時間を限定されているので、コンボルーション手順を通して、スペクトルラインの１セットに関して、周波数□｜□｜＜０．５Ｈｚの（複素数）周波数応答を推定できる。例えば周波数ｙ（ｍ０＋□）のスペクトル応答を推定するため、以下の積を形成し、ここでｍ０は整数である。
【数６】
【０１２４】
ここでｍの範囲は全ての可能な値（即ち、ｍ−Ｎ／２＋１からｍ＋Ｎ／２）にわたる。
【０１２５】
この計算に対する簡単な概算は２または３値のみのｍを必要とする。等式（Ｂ９）の２項の推定による損失の推定は、□が−０．５乃至０．５Ｈｚの範囲にわたるならば、このような感度損失が１ｄＢよりも小さいことを示す。問題とするほとんどの変調のドップラシフトでは、等式（Ｂ５）による拡張が、比較的多数の連続する周波数サンプルでかなり一定であることが考えられる。したがって、等式（Ｂ９）の補間手順は、多数の連続する再サンプルされたスペクトル値を決定するために、ｓｉｎｃ重み付け係数で同一値を使用することができる。
【０１２６】
前述の再サンプリング方法はしたがって、アルゴリズムの使用を可能にし、周波数データｙが一連の小さいブロック、例えばそれぞれ１０２４のサイズに分解され、各ブロックは固定された係数のセットによる補間手順を使用して再サンプルされる。ブロックを処理する前に、係数が計算されるか、表で参照される。この手順は再サンプリング動作の処理負担を非常に減少できる。例えば、等式（Ｂ９）のような２点補間手順が使用されるならば、再サンプリング手順は（前述の表参照を無視して）各補間された値を計算するために４つの実数倍と２つの加算だけを必要とする。この方法は例えば６４Ｋに等しいブロックサイズでＦＦＴを計算するのに必要なデータサンプル当り８つのバタフライと比較されることができる。これらのバタフライは３２の実数倍と４８の加算を必要とし、周波数ドメインにおける補間に関して約１６の係数だけ計算を増加する。したがって、周波数ドメインの再サンプリングは、時間ドメインの再サンプリングよりも、非常に実践的で効率的であると考えられている。
【０１２７】
再サンプリングは、大きな範囲のドップラシフトの処理時、および／または異なるＳＶからの信号の処理時に、変調ドップラを補償するのに有用である。このような場合、同一のフーリエ変換されたデータセットが使用されることができ、それ故、オリジナル時間データの処理は必要ではない。しかしながら前述したように、同一のフーリエ変換されたデータセットを有する異なるＳＶの処理は、初期のコヒーレントな処理前に除去が可能であるように、衛星メッセージデータが類似する状態に限定される可能性がある。いずれにせよ、再サンプリング動作が実行された後でさえも、第２及び付加的な再サンプリングが必要とされる場合に、オリジナルのフーリエ変換されたデータセットを維持することが有用である。オリジナルのフーリエ変換されたデータセットが利用可能ではないならば、再サンプルされたセットで再サンプリングを行う必要があるが、この方法では、正確な再サンプリングが実行されないと累積エラーを生じかねない。
【０１２８】
反復されるＰＮ信号に関連するスペクトルがまだらであること、即ち櫛形ライン型であることにより、枝刈り動作は、順方向ＦＦＴからの周波数データのサブセットの選択として規定されている。スペクトルの補間が必要とされるとき、前述したように、サブセットを単に選択するのではなく、周波数サンプル間の補間により構成する。それにもかかわらず、そのように構成されたサブセットのサイズは、簡単な選択が行われるケースに類似している。即ち、これは典型的に１ＰＮフレーム当りの信号サンプル数に等しい。例えば先の例では、これはサンプルレート１．０２４ＭＨｚまたは２．０４８ＭＨｚに対応して、１０２４または２０４８サンプルであった。逆ＦＦＴサイズはしたがって、同様にこれらのサイズである。結果として、“枝刈り”の定義は、補間手順による周波数サンプルのサブセットの構成と、周波数サンプルのサブセットの直接的な選択に及ぶ。
【０１２９】
類似の方法では、補間手順は、ＦＦＴのラインスペーシングよりも小さいインクリメントにより連続する周波数仮説を変更したいときに使用されることができ、例えば１／２ラインスペーシングのインクリメントが望ましい。さらに、枝刈りの定義は、周波数仮説がＦＦＴラインスペーシングの数分の１だけ変更される補間手順による周波数サンプルのサブセットの構成に及ぶ。
【０１３０】
これらの教示を考慮して、代わりの実施形態が容易に実行されることができることを当業者は認識するであろう。
【０１３１】
例えば、先の説明では、図２または図３により例示されているように、信号をゼロに近い周波数へ周波数変換するための初期周波数変換動作が存在する。これは技術でよく知られている方法により、通常の局部発振器及びミキサで行われることができる。また、ＧＰＳ周波数帯域に近い入来ＲＦエネルギを濾波し、フィルタ帯域幅に釣り合うレートで、この濾波されたエネルギを直接サンプリングすることによっても行われることができる。この方法は効率的な周波数変換を結果とすることができることが良く知られている。したがって、用語“周波数変換”はこれらの直接ＲＦサンプリング方法と、通常の周波数変換方法に適用する。さらに、図３は、搬送周波数がデジタル化の前に除去され、残留周波数ｆｅを残すことを示しているが、大抵の場合、搬送周波数の大半が除去されるだけであり、信号はデジタル化の前に低ＩＦ周波数、例えばｆＩＦ＋ｆｅに変換された周波数である。デジタル化動作に続いて、ＩＦ周波数ｆＩＦは典型的に、デジタル信号処理方法により実質的に除去される。処理結果はその後、図３のステップ33で示されているように続く。初期の信号事前処理におけるこのような変形は当業者に明白であろう。
【図面の簡単な説明】
【０１３２】
【図１】複数の基地局と通信する移動局のＧＰＳ受信機により受信されるＧＰＳ信号を発射する衛星を含む通信および位置検出システムの斜視図。
【図２】ＧＰＳ受信機及びセルラ通信システムを含む移動局の１実施形態のブロック図。
【図３】ここで説明されているコヒーレントな積分プロセスを示すフローチャート。
【図４】理論的ＧＰＳ信号の構造および波形成分を示すブロック図。
【図５】残留搬送周波数ｆｅ＝０における、２０回反復されたＧＰＳ信号（この例ではゴールドコード＃１）の周波数の関数として、パワースペクトルを示すグラフ。
【図６】残留搬送周波数が約４．５ｋＨｚにおける、２０回反復されたＧＰＳ信号（この例ではゴールドコード＃１）の周波数の関数として、パワースペクトルを示すグラフ。
【図７】周波数の関数として振幅を示している、整合フィルタ動作の結果の１例のグラフ。
【図８】異なるドップラ周波数仮説における整合フィルタ動作の結果を比較しているグラフのセット。
【図９】実際のデータに典型的な周波数内容を表すデータ周波数セットを示すグラフ。
【図１０】仮説された残留周波数の周波数選択においてサブセットが規定される方法を示している、仮説された周波数オフセットに対応するデータ周波数サンプルのサブセットを示す表。
【図１１】多数のコヒーレントな積分プロセスの結果を組合わせることを含んだプロセスを示すフローチャート。
【技術分野】
【０００１】
本発明は、ＧＰＳシステムのような、無線信号の使用により移動体装置の位置を計算する装置及び方法に関する。
【背景技術】
【０００２】
位置検出装置は、ますます人気が高まっている。これによって、位置の決定に使用される信号を捕捉するための迅速で高感度な方法の開発が奨励されている。
【０００３】
位置検出技術は、典型的に、位置を決定するため、既知の位置から同時に送信された無線信号を使用する。ＧＰＳシステムでは、これらの信号は既知の時間において、予め限定された周波数で、多数の衛星から同時に送信される。地上では、ＧＰＳ受信機は、空の視界範囲内にある各衛星から信号を捕捉する。視界内の衛星の正確な位置を伴った信号の到着時間と、信号が各衛星から送信される正確な時間は、三辺測量計算によりＧＰＳ受信機の位置を決定するために使用される。
【０００４】
ＧＰＳ衛星からの信号の捕捉は、複数の要因のために困難である。例えば、ＧＰＳ信号は比較的低電力で、長距離から送信される。ＧＰＳ信号が地球軌道から受信機へ伝播するまでの時間に、それらの最初の低い電力は非常に減少され、信号は受信機に至って、極めて弱くなる。受信された信号レベルはさらに、室内での受信、または都市の峡谷環境での受信中に生じるような、ビルの障害効果により弱められうる。
【０００５】
ＧＰＳ受信機には２つの主要な機能が存在し、即ち（１）種々のＧＰＳ衛星までの擬距離の計算と、（２）これらの擬距離と、衛星のタイミングと、暦表（位置）データとを使用するＧＰＳ受信機の位置の計算である。擬距離は、ローカルクロックによるバイアスを有する、衛星とＧＰＳ受信機との間の時間遅延（または距離に等しい）を測定する。通常の自律ＧＰＳ受信機では、衛星の暦表と送信データの時間は、それが捕捉及び追跡されると、ＧＰＳ信号から抽出される。この情報の補正は通常、比較的長時間（３０秒から数分間）かかり、低い誤り率を実現するために良好な受信信号レベルで実現されなければならない。
【０００６】
事実上、全ての既知のＧＰＳ受信機は擬距離を計算するために相関方法、またはそれらの数学的に等価する方法を使用する。これらの相関方法は実時間で、しばしばハードウェア相関器で行われる。ＧＰＳ信号は、擬似ランダム（ＰＮ）シーケンスと呼ばれる特別なシーケンスまたは“コード”にしたがって変調される高率の反復信号を含んでいる。民間の応用に利用可能なコードはＣ／Ａコードと呼ばれ、１．０２３ＭＨｚであり、１ｍｓｅｃの１コード期間に１０２３チップの反復期間である２進位相反転レート、または“チッピング”レートを与えるために使用されている。ＧＰＳシステムの擬似ランダムシーケンスは“ゴールドコード”として知られている系統に属している。各ＧＰＳ衛星は特有のゴールドコードを有する信号を放送する。
【０００７】
簡略する目的で、以下の説明には、信号が“擬似ランダムシーケンス（またはコード）を含んでいる”という用語を使用するが、このことは信号が、擬似ランダムシーケンスまたはコードにしたがって変調された波形を含んでいることを意味する。擬似ランダムシーケンスの１フレームの長さはそれが反復する前のシーケンスのシンボル数である。擬似ランダムシーケンスの継続期間（時間）により、擬似ランダムシーケンスにしたがって変調される波形の継続期間を意味している。同様に、擬似ランダムシーケンスのフレーム率を言う場合、擬似ランダムシーケンスにしたがって変調された波形の反復率を意味する。用語「擬似ランダムシーケンス」が、数のシーケンスまたは、このような数のシーケンスにしたがって変調される波形を指すかは、文脈から明白であろう。
【０００８】
信号が所定のＧＰＳ衛星から受信された後、ベースバンドへの下方変換プロセスに続いて、信号は基準信号と相関される。例えば、簡単な相関受信機は、受信された信号を、そのローカルメモリ内に含まれる適切なゴールドコードの記憶されたレプリカを含んでいる局部的に発生された基準信号によって乗算し、その後、信号が存在するという指示を得るために、その積を積分（例えばローパスフィルタ処理）する。
【０００９】
簡単な個々の相関プロセスは、単一数（おそらく複素数）を生じる可能性がある。しかしながら、問題となる多くの場合、このような数の乗算は異なる基準シーケンス（例えば遅延されたバージョン）に対応して、直列または並列して、類似の演算を行うことにより計算される。このような数のセットを“相関シリーズ”と呼ぶ。１以上の連続する相関シリーズを結合する最終結果は“最終的な相関シリーズ”と呼ばれる。
【００１０】
受信された信号に関して、この記憶されたレプリカの相対的なタイミングを逐次的に調節し、高いエネルギが結果的な最終的な相関シリーズで生じるときを観察することにより、簡単な受信機で、受信された信号とローカルクロックとの間の時間遅延を決定できる。この時間遅延、モジュロ １ミリ秒コード期間は、“コード位相”と名づけられている。残念ながら、相関捕捉プロセスは、特に受信された信号が弱いならば、時間を要する。捕捉時間を改良するため、最も一般的なＧＰＳ受信機は、相関ピークの平行サーチを可能にする（典型的には１２個までの）多数の相関器を使用する。
【００１１】
幾つかのＧＰＳは、受信されたＧＰＳ信号のドップラ周波数を決定するためにＦＦＴ技術を使用する。これらの受信機はＧＰＳ信号を逆拡散し、典型的に１０ｋＨｚから３０ｋＨｚの範囲の帯域幅を有する狭帯域幅信号を提供するために通常の相関動作を使用する。結果的な狭帯域幅信号はその後、搬送周波数を決定するためにＦＦＴアルゴリズムを使用してフーリエ解析される。このような搬送波の決定は同時に、ローカルＰＮ基準が受信された信号の正確なコード位相に調節されたという指示を与え、搬送周波数の正確な測定を行う。この周波数はその後の受信機の追跡動作に利用される。
【００１２】
１つの位置決定方法は例えば、移動体装置ではなく中央処理位置の擬距離を計算するためにＦＦＴアルゴリズムを使用する。その方法にしたがって、データのスナップショットはＧＰＳ受信機により集められ、その後、データリンクにわたって遠隔受信機へ送信され、ここで最終的な相関シリーズを計算するためにＦＦＴ処理を受ける。しかしながら、典型的に、（４つのＰＮ期間に対応する）単一の順方向および逆方向の高速フーリエ変換のみが相関のセットを実行するために計算される。
【００１３】
別の方法は、ＧＰＳ信号を捕捉するための高速フーリエ変換方法を使用し、生のデータの長いブロックをデジタル化し、記憶し、処理することを含んでいる。例えば１秒間隔に対応するデータはデジタル化され、その後ＦＦＴベースの信号処理方法を使用して局部的に処理されて、この捕捉されたデータブロック内に存在するＧＰＳ信号を捕捉することができる。この方法では、多数のＦＦＴ演算が行われ、それぞれ相関シリーズを発生し、その結果は最終的な相関シリーズを発生するためにコヒーレントと、非コヒーレントの処理演算の両者を受ける。
【００１４】
残念ながら、このようなシステムのＧＰＳ信号の捕捉方法は、１データビットの１期間（例えば２０ミリ秒の時間に等しい２０ＧＰＳフレーム）を超えるような、長いコヒーレントな積分を行うときには効率が劣る。特にＧＰＳ搬送周波数の不確定さが大きいとき、効率の損失も大きい。さらに、現在のＧＰＳ受信システムでは、１データビットを超える期間にわたるコヒーレントな積分は、ＧＰＳ受信機がビットシーケンスの演繹的な知識をもつことを必要とする。それ故、１データビットを超える期間にわたるコヒーレントな積分は通常、サーバから移動局へこのような情報を送信することにより行われる。この一般的な方法は、ＩＳ−９５、ＣＤＭＡ２０００、ＧＳＭ、ＵＭＴＳ標準規格を含む幾つかのセルラ通信標準規格で標準化されている。
【００１５】
コヒーレントな処理に対する他の従来の方法は、（１）長いコヒーレントな積分が必要なとき、（２）広いドップラ距離にわたるサーチが必要とされるとき、（３）コード位相サーチが処理される各ＧＰＳ信号の全１０２３チップにわたって行われなければならないときに有効であろう。しかしながら、このような従来の方法には複数の限定と制限がある。例えばこれらのアルゴリズムは２次元アレイとして処理データを必要とし、またドップラサーチが効率的に実行されることのできる程度を限定し得る。
【概要】
【００１６】
予め定められた周波数で、複数の送信機から送信される１以上の信号を受信し処理するための方法及び装置を説明する。各送信される信号は、各それぞれの信号を送信する送信機を特有に識別する周期的に反復するシーケンスにしたがってコード化された波形を含んでいる。受信された信号は受信機の位置決定に使用される。送信機はＧＰＳ周波数でＧＰＳ信号を送信する複数のＧＰＳ衛星を含むことができ、それぞれのＧＰＳ衛星は、特有の周期的に反復するシーケンスにしたがってコード化された波形を送信する。受信機における信号のコード位相オフセットが発見され、複数の送信機からのこの情報を使用して、受信機の位置はＧＰＳアルゴリズムを用いて確定されることができる。
【００１７】
さらに高い感度と高い処理速度が、観察されるデータにおいてＦＦＴ演算を行うことにより実現されることができ、ＦＦＴと共に、特別な枝刈り動作が、仮説された残留（見逃し）周波数エラーに基づいて使用され、計算の総数を減少し、それ故、処理時間を減少する。
【００１８】
特に受信機では、予め定められた周波数の信号が観察され、周期的に反復するシーケンスの少なくとも２回の反復（２フレーム）に対応する予め限定された時間期間にわたってデジタル化される。複数の送信機のうち１つが仮説され、仮説された送信機に対応する基準周波数サンプルの１セットが与えられる。デジタル化されたデータの第１のサブセットが少なくとも２フレームに等しい期間として選択され、したがって、データの１ブロックを規定する。データ周波数サンプルの１セットは、その後、フーリエ変換技術等を使用することによって、このブロックから計算される。
【００１９】
第１の残留周波数が仮説され、その後、データ周波数サンプルがその仮説された第１の残留周波数に応答して枝刈りされ、周期的に間隔を隔てられたデータ周波数サンプルの第１のサブセットを与える。データ周波数サンプルの第１のサブセットと基準周波数サンプルは第１の相関データシリーズを与えるために、（典型的には乗算および逆ＦＦＴ手順によって）さらに処理される。
【００２０】
この手順はその後、付加的なデータブロック（典型的に隣接する）で反復され、そうして発見された多数の相関シリーズが検出され、共に付加されて最終的な相関シリーズを形成することができる。この後者のシリーズはその後、典型的には最終的な相関シリーズの強いピークを探すことによって、信号の一致を識別するためにサーチされる。一致された信号が発見されたならば、コード位相オフセットが、最終的な相関シリーズから決定される。しかしながら、一致された信号が発見されなかったならば、別の残留周波数が仮説され、典型的にデータ周波数サンプルの同一のセットと基準周波数サンプルを使用して、プロセスが反復され、信号の一致をサーチする。類似の処理が、信号の一致が発見されるまで、または一致を発見せずに十分な残留周波数が仮説されて、仮説された送信機からの信号が捕捉されることができないことを想定するまで進行する。
【００２１】
典型的に、受信機により観察可能な複数の送信機が存在し、このプロセスは、信号を識別し、可能ならば各送信機からコード位相オフセットを決定するために、このような各送信機で反復されることができる。
【００２２】
多数の異なる実施形態が実行されることができる。１実施形態では、枝刈りステップはさらに、データ周波数サンプルのサブセットを選択することを含み、そのサブセットは、整数Ｋだけ相互に関して隔てられているインデックスを有する複数のサンプルを含んでおり、ここでＫはデータブロック中のＰＮシーケンスのフレーム数である。
【００２３】
この際に、ここでは時折、Ｆ（ｔ）における用語“ＰＮシーケンス”または“ＰＮフレーム”、即ちＰＮシーケンスのフレームの反復するセット、を使用しているが、ＰＮシーケンスは実際には搬送波の変調する信号を構成するために使用される数のシーケンスであり、したがって波形Ｆ（ｔ）を発生するので、これは厳密には正しくないことに注意する。しかしながら、“ＰＮシーケンス”がＰＮシーケンスＦ（ｔ）により変調される波形か或いはシーケンス自体を意味することに使用されているかは、文脈から明白であろう。
【００２４】
別の実施形態では、方法はさらに、重み付けされた周波数サンプルの１セットを形成するため、データ周波数サンプルのサブセットを基準周波数サンプルの１セットで乗算することを含んでいる。
【００２５】
基準周波数サンプルは任意の適切な方法によって得られ、例えば受信機は基準周波数サンプルを規定するために周期的に反復された周波数の１以上の期間において、ディスクリートなフーリエ変換（ＤＦＴ）を行ってもよく、基準周波数サンプルは各送信機で予め計算され、受信機に記憶されてもよく、或いは基準周波数サンプルはここで説明されるＰＤＥのようなサーバからダウンロードされてもよい。
【００２６】
相関動作を行うステップは、相関データシリーズを発生するために、重み付けされた周波数サンプルのセットで逆ＤＦＴを行うことを含むことができる。
【００２７】
各データブロックは２以上、例えば５、１０、２０以上の周期的に反復するシーケンスの整数回の反復に対応するサイズを有することができる。幾つかの実施形態のデータブロックは、周期的に反復するシーケンスの約５乃至２０の反復範囲内のサイズを有することができる。他の実施形態では、データブロックは１００程度のこのような反復のサイズを有することができる。
【００２８】
前述の方法は、適切なハードウェアおよび／または受信機中のソフトウェア、および／または無線ネットワークの１以上のサーバで実行される。例えばある機能は受信機で実行され、ある機能は位置決定エンティティ（ＰＤＥ）で実行されることができる。
【００２９】
ここで説明する装置及び方法は、補助ＧＰＳ（“Ａ−ＧＰＳ”）システムでは特に有効である。この補助ＧＰＳシステムでは、補助情報をＧＰＳ受信機へ提供する通信システムが、ＧＳＭおよびＵＭＴＳセルラ標準規格の場合のように、非同期化される。ＣＤＭＡ２０００標準規格のように同期された通信システムでは、コード位相サーチに課される要求は非常に軽減されるが、ここで説明する改良されたアルゴリズムの使用からさらに利点が得られよう。
【詳細な説明】
【００３０】
図面の種々の図形では、同一の参照符号は同一または類似の部分を示している。
【００３１】
図１は、複数のＧＰＳ衛星（ＳＶ）11を含むＧＰＳ環境を示している。ＧＰＳ環境について説明するが、ここで説明されるシステムは任意の位置付けシステムで構成されることができる。衛星11は、通信ネットワークの一部である複数のランドベースの基地局10と、基地局と通信する移動局（ＭＳ）14とによって受信されるＧＰＳ信号12を発射する。ＭＳ14はＧＰＳ受信機と、双方向通信信号20を使用して基地局と通信するための双方向通信システムとを含んでいる。ＧＰＳ受信機は、１以上の基地局と通信する（セル電話以外の）広い範囲の移動体実施形態で構成されることができる。広い範囲の環境に位置付けられることのできるＭＳ14を所有するユーザ13は、静止または移動することができる。
【００３２】
ＧＰＳ衛星（ＳＶ）11は、ＧＰＳ受信機の位置付けに使用される信号を放送する衛星のグループを含んでいる。衛星はＧＰＳ時間に同調される無線信号12を送信するように同期される。これらの信号は予め定められた周波数で、予め定められたフォーマットで発生される。現在のＧＰＳ構造では、各ＳＶはＧＰＳ標準規格にしたがってフォーマットされた（１５７５．４２ＭＨｚの）Ｌ１周波数帯域で民間タイプのＧＰＳ信号を送信する。ＧＰＳ信号がＭＳの通常のＧＰＳ受信機により検出されるとき、ＧＰＳシステムは各ＧＰＳ衛星の擬距離を計算し、その擬距離から、ＭＳの位置が計算される。
【００３３】
擬距離は、ｃ・（Ｔｕｓｅｒ−ＴＳＶ）＋ｃＴｂｉａｓとして規定され、ここでｃは光速度であり、Ｔｕｓｅｒは所定のＳＶから信号が受信されるときのＧＰＳ時間であり、ＴＳＶは衛星が信号を送信したときのＧＰＳ時間であり、Ｔｂｉａｓは通常はＧＰＳ受信機に存在するローカルユーザクロックの誤差である。時折、擬距離は定数“ｃ”を省略して規定される。通常の場合、受信機は４つの未知数Ｘ、Ｙ、Ｚ（受信機アンテナの座標）とＴｂｉａｓを解くことを必要とする。これらの４つの未知数を解くことは、通常４つの異なるＳＶからの測定を必要する。しかしながら、ある状況では、この制約は緩和されることができる。例えば、正確な高度の推定が得られるならば、必要なＳＶ数は４から３へ減少されることができる。Ａ−ＧＰＳ動作では、ＴＳＶは必ずしも受信機に対して利用可能ではなく、真の擬距離を処理する代わりに、受信機は主にコード位相に依存する。現在のＧＰＳ構成では、ＰＮコードは１ミリ秒毎に反復するので、コード位相は１ミリ秒の時間の曖昧さを有する。時折、データビットの境界が確認されるので、したがって２０ミリ秒のみの曖昧さが生じる。
【００３４】
基地局10は、無線信号20を使用してＭＳ14と通信する通信ネットワークの一部として使用される基地局の任意の集合を具備している。基地局はセルラインフラストラクチャネットワーク15に接続され、このネットワーク15は、公共電話システム16のような複数の他の通信ネットワーク、インターネットのようなコンピュータネットワーク17、位置決定エンティティ（ＰＤＥ）18、ブロック17aで集合的に示されている種々の他の通信システムに通信サービスを提供する。基地局10に存在するかその近くに存在する可能性のある、または任意の他の適切な位置に存在する可能性のあるＧＰＳ基準受信機（または受信機）19は、ＰＤＥ18と通信し、ＳＶ位置（暦）情報のような、位置を決定するのに有効な情報を提供する。
【００３５】
地上ベースのセルラインフラストラクチャネットワーク15は典型的に、セル電話のユーザが公共電話システム16にわたって別の電話機と接続することを可能にする通信サービスを提供する。しかしながら、基地局はさらに、他の装置との通信、および／またはハンドヘルド型パーソナルデジタルアシスタント（ＰＤＡ）とのインターネット接続のような、他の通信目的で使用されることもできる。例えば基地局10はＧＳＭ通信ネットワークの一部であってもよいが、他のタイプの同期（例えばＣＤＭＡ２０００）または非同期通信ネットワークでも同様に使用できる。
【００３６】
図２は、通信および位置検出システムを組込んでいる移動体装置14の１実施形態のブロック図である。セルラ通信システムのような双方向通信システム22は、セルラ信号20を使用して通信するアンテナ21に接続されている。セルラ通信システム22は、基地局と通信しおよび／または基地局からの信号20を検出し、送信されたまたは受信された情報を処理するため、モデム23、ハードウェア、ソフトウェアのような適切な装置を含むことができる。
【００３７】
ＭＳのＧＰＳ位置検出システム27は、理想的なＧＰＳ周波数のまたはそれに近い周波数で送信されたＧＰＳ信号12を受信するためのＧＰＳアンテナ28に接続されている。ＧＰＳシステム27は、周波数変換回路およびアナログデジタル変換器を含んでいるＧＰＳ受信機29と、ＧＰＳクロックと、ＧＰＳ受信機の所望の機能を制御するための制御論理装置と、ＧＰＳ信号を受信して処理し、適切な位置検出アルゴリズムを使用して位置を決定するのに必要な計算を行うための適切なハードウェア及びソフトウェアとを具備している。示されている実施形態では、アナログデジタル変換器は位置検出システムのバッファメモリに接続され、バッファメモリはＤＦＴ動作中にデータを提供し記憶するためＤＦＴ回路に結合されている。幾つかのＡ−ＧＰＳ構造では、最終的な位置検出計算（例えば緯度と経度）は、ＧＰＳ受信機から遠隔サーバへ送信されるコード位相及びその他の情報に基づいて、遠隔サーバで実行されることができる。ＧＰＳシステムの幾つかの例は米国特許第5,841,396号、第6,002,363号、第6,421,002号明細書に開示されている。
【００３８】
ＧＰＳクロックは正確なＧＰＳ時間を維持することを意図されているが、多くは、正確な時間は位置の確定前には得られないので、その推定された値と、その値に関する不定さによって、ＧＰＳクロックソフトウェアで時間を維持することが一般的である。正確なＧＰＳ位置の確定後、ＧＰＳ時間はしばしば正確に（現在のＧＰＳ構造では数十ナノ秒内の不定さ）知らされることに注意する。しかしながら、最終的な位置検出計算が遠隔サーバで行われるとき、この正確な時間はサーバでのみ利用可能である可能性がある。
【００３９】
移動体装置の制御システム25は双方向通信システム22と位置検出システム27との両者に接続されている。移動体装置の制御システム25は、それが接続されているシステムに対して適切な制御機能を行うために、１以上のマイクロプロセッサ、メモリ、他のハードウェア、ファームウェア、ソフトウェアのような任意の適切な構造を含んでいる。ここで説明する処理ステップは任意の適切な方法で実行されることができる。
【００４０】
制御システム25はユーザインターフェース26に接続され、ユーザインターフェース26は、キーパッド、音声通信サービスのためのマイクロホン／スピーカ、バックライトのＬＣＤディスプレイのようなディスプレイ等の、ユーザとインターフェースするための任意の適切なコンポーネントを含んでいる。位置検出システム27に接続されている移動体装置の制御システム25とユーザインターフェース26は、ユーザ入力の制御および結果の表示のような、ＧＰＳ受信機と双方向通信システムに対して適切な入力−出力機能を与える。
【００４１】
コヒーレントな処理方法の１例について図３及びその他の図面を参照して説明する。図３は、受信されたＧＰＳ信号を処理して、それがＧＳＰコードと搬送周波数オフセットを選択する仮説に一致するか否かを識別するために、移動局で行われる一連のステップを示すフローチャートである。アルゴリズムは、選択されたＧＰＳコードでコード位相オフセットの一致を発見しようとするため、全ての可能なコードオフセット（例えば１０２３オフセット）を検査できる。コヒーレントな処理アルゴリズムはその後、移動局により観察可能であり得る各ＧＰＳコードで反復される。付加的な非コヒーレントな処理が、さらに感度を改良するため、図３のアルゴリズムに対して付加されることができる。簡潔にする目的で、この付加された複雑さについて図１１と共に後に説明する。
【００４２】
図３では、30で、ＧＰＳ信号を観察する動作が示されている。本質的に、受信機は、ＧＰＳ信号が存在し検出可能であることを予想した上で、ＧＰＳ搬送周波数に近い搬送周波数を有する電磁エネルギを受信する。ＧＰＳ信号は（それが存在するならば）少なくとも期間Ｔｃ程の長さの時間期間、即ちデータのブロックがコヒーレント処理で取られる時間期間にわたり観察される（Ｔｃは“データブロック期間”または信号のコヒーレントな積分（処理）時間としても呼ばれることができる）。
【００４３】
雑音がない場合、ＧＰＳ信号の関数形態ｓ（ｔ）が任意の時間ｔにおいて理論的に、以下のように表される。
ｓ（ｔ）＝Ａｄ（ｔ）Ｐ（ｔ）ｅｘｐ（ｊ２□ｆｔ＋□） （Ａ１）
ここで、Ａは信号振幅であり、ｄ（ｔ）は搬送波を（例えば二相変調により）変調する比較的低速度（例えば５０ボー）を有するデータシーケンスであり、Ｐ（ｔ）はＰＮシーケンスＦ（ｔ）のフレームの反復するセットからなる波形であり、ｆは（理想的にはｆ０に等しい）搬送周波数であり、□は搬送波位相である。例えば伝送（例えばチップ）レートは１．０２３ＭＨｚであり、Ｆ（ｔ）は１０２３チップの長さを有し、ＰＮフレームレートは１ｋＨｚであり、Ｐ（ｔ）は長さＫ□１０２３チップを有する。
【００４４】
等式（Ａ１）は搬送波の複素数表現であり、これは直角サンプリング方法が信号の処理に使用されるならば有用であり、勿論、他の表現も適切なときに使用されることができることに注意する。実世界の状態では、種々のパラメータは完全に安定とはいえないが、説明目的で、信号振幅と種々の変調レートがほぼ一定であることを想定することが認識されるべきである。
【００４５】
図４は、等式（Ａ１）で説明された理想的なＧＰＳ信号の構造を表す図である。ＧＰＳ信号は45で示されている一連のＰＮフレームから構成されており、それぞれ特定の擬似雑音（または“ＰＮ”）シーケンスにしたがって二相変調された波形Ｆ（ｔ）46と、搬送周波数47を含んでいる。Ｆ（ｔ）の個々の反復は“ＰＮフレーム”と名づけられている。各ＰＮフレームは予め定められた期間Ｔｒを有する。48で、データシーケンスｄ（ｔ）のデータ遷移が示されており、これは示されているＰＮフレームのうちの１つの開始において生じる。しかしながら、データシーケンスｄ（ｔ）は比較的低速度なので、（米国のＧＰＳ Ｃ／Ａコードでは）データ遷移48は２０ＰＮフレームに一度のみ生じ、それ故データ遷移は任意に選択されたＰＮフレームの開始で生じるかまたは生じない。
【００４６】
各ＧＰＳ衛星（ＳＶ）は46で示されている特有のＰＮ波形Ｆ（ｔ）を送信し、これは予め定められたレートで送信される一連のシンボル（チップ）である。ＰＮ波形は、搬送波の二層変調に使用される特定のＰＮシーケンスによって、相互から弁別される。例えばこれらのシーケンスは米国のＧＰＳシステムのＣ／Ａ波形では、ゴールドコードの１セットから選択されることができる。
【００４７】
１つの例では、チップレートは１．０２３ＭＨｚであり、したがってＰＮフレームレートは約１ｋＨＺである。この波形Ｆ（ｔ）は連続して反復され、例えば第１の衛星ＳＶ１からの第１のコードは特有のシーケンスＦ１（ｔ）を繰返し送信し、ＳＶ２は特有のＰＮシーケンスＦ２（ｔ）を繰返し送信する。ＧＰＳ受信機は、視界内にある得る全てのＧＰＳ衛星の特有のＰＮシーケンスでプログラムされる。これらのＰＮシーケンスは特定の衛星を識別するためのアルゴリズムで使用されることができ、特に衛星の信号がＧＰＳ受信機で受信されるとき、ＰＮシーケンスは受信された信号を送信した衛星の識別に使用される。しかしながら、初めは、ＧＰＳ受信機は実際の受信されたコード位相のエポックを知らず、これは前述したように全ＰＮフレームにわたる距離（例えば１ミリ秒の期間或いは１０２３チップ）であってもよい。さらに、受信機は、特定のＰＮコードに関連されるＧＳ信号が検出可能であるか否かを知らない。それはこの信号が種々の障害により減衰されるかおよび／または特定のＳＶが視界内ではないからである。それ故、受信機は、仮説された信号の検出を試みるためエポックの不確定の距離にわたって直列または並列にサーチし、受信されたＧＰＳフレームのエポックを、ローカルに発生された基準フレームと整列しなければならない。
【００４８】
実際のＧＰＳ環境では、ＧＰＳ受信機は等式（Ａ１）で特定された理論信号のような、それぞれ特有のＰＮシーケンスＦ（ｔ）を有する多数の信号を同時に受信する。例えば、典型的な状態では、ＧＰＳ受信機は任意の時間に種々の視界内の衛星から８乃至１２の信号を典型的に受信し、種々のパラメータは、例えばパスの長さ、到着方向、ドップラ周波数シフトが異なるために、相互に異なっている。説明の目的で、等式（Ａ１）の理論形態の信号のうちの１つを処理することを最初に説明し、その後、ここで説明する処理アルゴリズムがどのように多数の信号の処理に使用されることができるかを証明する。それぞれの信号は等式（Ａ１）の理論形態を有する。
【００４９】
ＧＰＳ信号が受信機に到達するとき、これらはしばしば付加的な雑音により非常に崩壊され、恐らく、他の雑音または緩衝によっても崩壊される。さらに搬送周波数及びチップレートは主にドップラ効果によって、その本来の値から僅かにシフトされると考えられることができる。したがって搬送周波数は、ＳＶの動作とＭＳの動作により、ＭＳの受信機により観察されるとき僅かにシフトする可能性があり、それ故受信機が信号を受信するとき、実際に受信された搬送周波数はその理想的な予め定められた搬送周波数ｆ０から、“残留周波数”と呼ばれる量だけ変化する可能性がある。さらに、ＭＳ局部発振器のエラーは搬送周波数をその理想的な周波数から変化させる。
【００５０】
図３を参照すると、31で搬送周波数は、適切な周波数変換回路によってＧＰＳ信号から“取り除かれ”、残留周波数ｆｅを残す。搬送周波数を除去するために、ＧＰＳ信号は典型的に、最初にミキサによって中間周波数（ＩＦ）へ変換され、その後、任意の適切なアナログまたはデジタル技術により、残留するＩＦ成分をほぼゼロまで減少するように処理される。例えば、ＩＦ周波数は別のミキサにより、ほぼ除去されることができ、またはアナログデジタル変換器で、ＧＰＳをデジタル信号に変換後、デジタル処理混合技術が使用されてもよい。幾つかの構造では、周波数変換回路は小さい既知の周波数オフセットにプラスして前述の残留周波数を有する最終的な周波数を提供できる。この小さい既知の周波数オフセットは、一定であることが知られているので、その後の処理は残留周波数の決定だけを必要とする。以下の説明を簡潔にするため、この小さい既知のオフセットをゼロと想定する。しかしながら、ここで説明する方法及び装置はこのような既知のオフセットがゼロではないケースにも同等に応用可能である。
【００５１】
典型的に、残留周波数は主にドップラ効果により生じる。さらに受信機自体は信号の処理期間中に僅かな周波数シフトを誘発し得る。理想的な搬送周波数からのこれらの２つのエラーの和は、ある最大の許容度（Δｆ）により表されることができる。それ故、実際の受信された搬送周波数は典型的にｆ０±Δｆの範囲内である。残留周波数は多かれ少なかれ、状況の任意の特定のセットにあるが、受信機がオリジナル搬送波をゼロまで減少することを試みた後に残る周波数に等しい残留周波数ｆｅは、典型的に数百ヘルツから数ｋＨｚの範囲にある。
【００５２】
Ａ−ＧＰＳシステムでは、全てのＧＰＳ信号における予想されるドップラ補正はＰＤＥからＧＰＳ受信機へ（１形態または別の形態で）送信され、視界内にある得るＧＰＳ衛星のリストはまた受信機に送信され、それによってＧＰＳ受信機は衛星信号をさらに効率的にサーチできる。予想されるデータストリームはまたＰＤＥによって提供されることもできる。
【００５３】
そのメモリ内で、受信機は視界内にあり得る全てのＧＰＳ衛星に対応するＰＮコード（またはこれらのコードのＤＦＴのようなその表示）を記憶している。
【００５４】
32で、処理されたＧＰＳ信号は（前もって変換されていないならば）アナログデジタル変換器で、予め定められた時間にわたってデジタル化（即ちサンプル）され、その後ＧＰＳ受信機のバッファメモリに記憶される。サンプルレートが１．０２４ＭＨｚの倍数であり、データセットのサイズが１０２４の倍数であることが時折有用であるが、データセットのサイズ、またはデータのサンプルレートには理論的限定はない。それ故、等式（Ａ２）の信号はサンプルされた信号であると考慮され、ここではサンプルレートは１．０２４ＭＨｚまたは２．０４８ＭＨｚの数に設定されることができ、それによって１０２４または２０４８サンプルは１ミリ秒のＰＮフレーム期間にわたって生じる。ドップラ誘発エラーによって、このサンプルレートはチップレートまたはそのチップレートの２倍に全く等しいわけではない。このサンプルレートを選択する１つの理由は、サンプリングが１．０２４または２．０４８ＭＨｚで実行されるならば、結果的なサンプル数は、１ミリ秒フレーム期間にわたって、２の累乗であり、これは効率的なＦＦＴで便利である。即ち、データの１フレームは１０２４サンプルの倍数であり、効率的なＦＦＴで便利なサイズであり、（コヒーレントな処理における）総データセットサイズも１０２４の倍数であり、２の累乗×この長さである。しかしながら、フレーム当りのサンプル数が２の累乗ではないときに効率的なアルゴリズムが依然として存在するので、この限定は絶対的ではない。
【００５５】
33で、コヒーレント処理のためのデータブロックは、予め定められたコヒーレントな処理期間Ｔｃにわたって、記憶されたデジタルデータの一部を選択することにより規定される。データがコヒーレントな処理で組合わされる時間期間は典型的に、ＰＮフレームの大きい整数（例えば２０ＰＮフレーム）を含むように選択される。コヒーレントな処理ブロックはしかしながら、長い時間期間にわたる残留搬送周波数の安定性とその他のマルチパス効果（及び恐らく他の要因）が性能の改良を限定するか妨げる可能性があるので、非常に長いようには選択されるべきではない。以下説明するように、Ｔｃを１ＰＮフレーム期間Ｔｒの厳密な倍数になるように選択することが有効であろう。
【００５６】
図４をさらに参照すると、ＧＰＳ信号は時間Ｔｃにわたり観察され、これは第１のデータブロック49aまたは第２のデータブロック49bのようなデータブロックを規定し、時間Ｔｃはデータブロックが整数個のＰＮフレーム45を有するように選択される。実際のデータブロックはＰＮフレームが開始するときを前もって知らされずに受信されるので、データブロックの開始及び終了はＰＮフレーム境界内のどこにでも存在できる。例えば、データブロックは偶然に、49a（コード位相オフセット＝０）で示されているように、第１のフレームの開始から最後のＰＮフレームの最後まで延在できるが、より多くの可能性としては、データブロックは（49bで示されているように）第１のＰＮフレームの中間地点の何れかの場所から、最後の全ＰＮフレームに続くフレームの中間地点の何れかの場所まで延在し、それによって、コード位相オフセットはゼロに等しくない。図３のステップ39乃至42を参照して説明するように、例えばコード位相オフセットは整合フィルタ動作を使用して決定されることができる。
【００５７】
図３の34で、データシーケンスは随意選択的に除去される。データシーケンスｄ（ｔ）が除去され、等式（Ａ１）の理論信号が残留信号ｓｂ（ｔ）のベースバンドに近い周波数に変換された後、無視する雑音と干渉は以下の形態を有する。
ｓｂ（ｔ）＝ＡＰ（ｔ）ｅｘｐ（ｊ２□ｆｅｔ＋□） （Ａ２）
ここでｆｅは搬送周波数をほぼベースバンドに変換した後の残留周波数である。
【００５８】
随意選択的であるが、処理前にデータシーケンスｄ（ｔ）を除去することが有用であろう。データシーケンスの除去を助けるため、幾つかのＡ−ＧＰＳシステムでは、予想されるデータシーケンスｄ（ｔ）は、ＧＰＳ信号の幾つかのおおよその到着時間と共に、（例えばサーバから）ＧＰＳ受信機へ送信される。これらの場合、ＧＰＳ受信機はデータシーケンスｄ（ｔ）を除去でき、それ故、データシーケンスｄ（ｔ）により等式（Ａ１）の信号で２０ミリ秒毎に生じ得る擬似ランダム極性反転を除去できる。ランダム極性反転の除去により（即ちｄ（ｔ）の除去により）コヒーレントな積分時間は１データビット期間よりも長い時間、例えば１００ミリ秒よりも大きい時間の間隔まで増加されることができる。コヒーレントな積分時間の増加はＧＰＳ捕捉プロセスの感度を改良できる。先に示したように、ＧＰＳの幾つかの将来のモードは、データを含まないシグナリング成分を含むことができる。これらの状態では、コヒーレントな積分期間は１つのデータビット期間に限定されない。
【００５９】
図３を再度参照すると、搬送周波数は式（Ａ２）の信号ｓｂ（ｔ）に残留周波数ｆｅを提供するためにおおよそ除去され、ブロック期間ＴｃはＰＮフレーム期間Ｔｒの厳密な倍数であるように選択された。換言すると、Ｔｃ＝ＫＴｒであり、ここでＫはブロック期間のフレーム数である。例えばＫ＝１００で、Ｔｒ＝１ｍｓｅｃであるならば、Ｔｃは１００ミリ秒であることができる。
【００６０】
35で、データブロックはフーリエ変換プロセスを使用してコヒーレントに処理される。このステップは“順方向変換”プロセスと呼ばれることができる。例えば時間期間Ｔｃにわたってサンプルされた信号ｓｂ（ｔ）の高速度フーリエ変換（例えばＦＦＴまたはＤＦＴ）は次式のように行われることができる。
ｙ（ｆ）＝ＦＦＴ（ｓｂ（ｔ）、ｔ＝０からｔ＝Ｔｃまで） （Ａ３）
順方向変換プロセスは種々の方法で実行されることができる。１つの良く知られた方法は、時間におけるデシメーションであり、別の方法は周波数におけるデシメーションである。チャープｚ変換または数理論変換のような、１つの高速度アルゴリズムが適切または有用であるとして使用されることができる。
【００６１】
（例えば図９で示され、それを参照して説明する）随意選択的な信号のＦＦＴはデータブロックが処理されている期間の逆数により、周波数において分離される一連のデータ周波数サンプルを含んでいる。例えばブロック期間（Ｔｃ）が２０ミリ秒であるならば、周波数サンプルは５０Ｈｚだけ隔てられる。ブロック期間が８０ミリ秒であるならば、周波数サンプルは１２．５Ｈｚだけ隔てられる。各データ周波数サンプルはその周波数Ｈｚにより、より便宜的にはその周波数インデックスにより識別されることができる。特に、ＤＦＴの各データ周波数サンプルは整数（周波数インデックス）で指定されることができ、これは例えばゼロ周波数ではゼロインデックスで開始する。Ｎ点のＦＦＴでは、周波数インデックスＮ／２はサンプルレートの半分の周波数Ｈｚ、即ちＳ／２に対応する。インデックスＮ／２＋１，Ｎ／２＋２等を有する周波数サンプルは−Ｓ／２＋１／Ｔｃ，−Ｓ／２＋２／Ｔｃ等に等しい周波数Ｈｚに対応し、即ち、これらは負の周波数に対応するデータを表す。インデックスＮ／２，Ｎ／２＋１，Ｎ／２＋２，…，Ｎ−１，０，１，２，…，Ｎ／２−１を有するサンプルを選択することによってデータサンプルを配列し直すならば、周波数データは最も負の周波数で開始し、最高の周波数に進行する（Ｈｚにおいて）昇順で集合される。この配列のやり直しが例えば図５と図６で使用される。結果として、周波数インデックスは循環的であると考えられ、それによってインデックスｍはｍ＋Ｎとｍ−Ｎに等しい。それ故、インデックスＮ／２＋ｍはインデックス−Ｎ／２＋ｍに等しい。
【００６２】
図５は、前述の配列のやり直しをした、ゼロ（０）周波数に近い周波数の理論的に雑音のないＧＰＳ信号の周波数スペクトルのグラフである。図５はＰＮシーケンスの周期的反復による特徴外観を有するＦＦＴを示しており、これは米国のＧＰＳ Ｃ／Ａコードでは１ミリ秒毎に反復される。示されている雑音のないＦＦＴは、低エネルギを有する中間サンプル（図示せず）の数によって分離されている強力なエネルギを有するデータ周波数サンプル（スペクトルライン）51のサブセットを含んでいる。このようなスペクトルは時折“櫛形”スペクトルと呼ばれ、連続する強力なサンプル間の分離はＫの周波数インデックスの倍数にある。
【００６３】
特に、図５で示されている櫛形スペクトルは、２０ミリ秒の期間にわたり２０回反復され、サンプルされ、残留搬送周波数ｆｅ＝０であり、（グラフでは図示されていないが２０９ｋＨｚにおける）最大の振幅ラインで正規化されている、ＧＰＳゴールドコード＃１に対応するパワースペクトルにおける大きさ対周波数のグラフである。この例では、強力なエネルギを有するスペクトルラインのシリーズは約１０００Ｈｚ（１ｋＨＺ）により間隔を隔てられている。０．０Ｈｚライン51aは約−３８ｄｂの振幅を有し、１．０ｋＨｚライン51bは約−１１ｄｂの振幅を有し、２．０ｋＨｚライン51cは約−１３ｄｂの振幅を有している。強力なスペクトルラインの各対の間には、図５の対数グラフで表されているように振幅が非常に低い１９の中間ラインが存在している。例えば51aで、スペクトルラインは０Ｈｚと１０００Ｈｚに存在する。スペクトルラインは５０Ｈｚ、１００Ｈｚから９５０Ｈｚまで存在するが、低いエネルギを有するので、これらは図面では表示されていない。類似の解析が各強力なスペクトルラインの対に対して存在する。Ｈｚで測定された櫛形の強力なスペクトルラインの分離はフレームレートｆｒに等しい。周波数のインデックス差で測定されるのは、Ｋインデックス、即ちコヒーレントなデータブロックのフレーム数である。
【００６４】
図５が雑音が存在しない理論結果を示している一方で、図９に示されているような実際の受信された信号のＦＦＴは、スペクトルラインが直接的に観察されることができないこのような雑音を示している。図５の例では、52で示されているＦＦＴの平均雑音レベルは典型的に、最も強いスペクトルラインの振幅さえも超える。
【００６５】
図９をさらに参照すると、これは実際のデータに典型的な周波数内容（ＦＦＴ）が、概して90で示されている複数のデータ周波数のサンプルを含んでいることを示すグラフであり、これらの複数のデータ周波数のサンプルは集合的に“データ周波数セット”と名づけられている。データ周波数セットは（Ｓ−１／ＴｃのＨｚの周波数に対応する）最高の周波数インデックスまで延在する。各データ周波数サンプル間の周波数分離はブロック期間の逆数（即ちサンプル１／Ｔｃの時間期間の逆数）に等しく、それ故、オリジナルＦＦＴの順序付けが使用されると、最大のインデックスはＳＴｃ−１にある。
【００６６】
図５と異なり、図９の各データ周波数サンプル90は雑音を含み、それ故、（周波数インデックスＫにおける）周期的なスペクトルラインだけが多量のエネルギを有する図５の理論的ＧＰＳスペクトルとは異なって、多量のエネルギが各周波数インデックスで発見される。換言すると、雑音のために、受信されたＧＰＳ信号に関連されるスペクトルラインの振幅は雑音レベルよりも低く、それ故直接的に観察可能ではない。別の言い方をすれば、実際のデータのＦＦＴでは、平均雑音エネルギレベルは全ての周波数ラインと類似する可能性があり、それ故、図５の櫛形スペクトルは観察可能ではなく、その後の処理まで未知の状態であろう。
【００６７】
図３に戻ると、36aで、アルゴリズムを開始するために、初期想定が行われる。等式（Ａ１）で特定される理論信号のように、ＧＰＳＫ受信機は同時に多数の信号を受信し、それぞれ特有のＰＮシーケンスＦ（ｔ）を有し、それ故、それぞれそのＰＮシーケンスの特有のＦＦＴを提供することに注意すべきである。例えば典型的な状態では、ＧＰＳ受信機は典型的に８乃至１２の信号を、任意の時間に種々の視界内の衛星から受信するが、これらの信号の多くは非常に弱いために検出ができない可能性がある。それ故、何れの衛星が受信可能な信号を提供しているかについて不定であり、さらに、検出可能であっても、到着時間を決定する任意の受信可能な信号のコード位相オフセットは、演繹的に未知である。
【００６８】
36aで、視界内に存在し得る特定の衛星が選択されるかまたは“推測”される。任意の特定の衛星の選択はランダムであってもよく、またはＰＤＥにより与えられる経歴或いはリストのような任意の適切な情報に基づくことができる。以下説明するように。選択された衛星のＰＮコードは、少なくとも一致が発見されるか、全ての仮説がなくなるまで、（典型的に受信機により決定される距離内の）複数の周波数仮説にわたって検査され、その後36cで、次の衛星が選択され、全ての候補衛星が選択されるまで、または十分な数の衛星からの信号が位置の確定を完了したことが分かるまで、対応するＰＮコードが複数の周波数仮説にわたって検査される。
【００６９】
36aで、初期仮説が残留周波数に対して行われる。十分な情報がＧＰＳ受信機に利用可能である（例えば前もって位置確定が行われたか、評価されたドップラ補正が得られる）ならば、この初期仮説及びその後の仮説はこの情報に基づいて行われることができる。利用可能な情報がないならば、最良の推定が行われ、サーチが開始されることができる。
【００７０】
図３を再度参照すると、37で、仮説された衛星に対応するＧＰＳコードのフーリエ変換が行われる。事前にローカルに発生されまたは計算され、記憶されることのできるこのコードは時折、“基準”コードと呼ばれる。これらのＧＰＳコードはよく知られており、ＧＰＳ受信機のＧＰＳコード毎に値を予め計算し、記憶することが実行可能である。これらのＧＰＳコードはその後、ＧＰＳ受信機での記憶前または記憶後にフーリエ変換されることができる。例えばフーリエ変換（例えばＦＦＴまたはＤＦＴ）は、次式のように、Ｐ（ｔ）で示されるＰＮシーケンスＦ（ｔ）のＫ反復からなる基準データセットで実行されることができる。
Ｂ（ｆ）＝ＦＦＴ（Ｐ（ｔ）、ｔ＝０からｔ＝ＫＴｒ＝Ｔｃまで） （Ａ４）
この結果は図５に示されている例のように、一連の均等に隔てられたラインを含んでいる櫛形スペクトルであり、これは“基準周波数サンプル”と名づけられることができる。Ｂ（ｆ）のＫ番目の周波数サンプル毎にのみゼロではなく、ゼロではない値だけが記憶される必要があるので、即ち、必要な記憶を減少する。
【００７１】
しかしながら、反復されるシーケンスＰ（ｔ）のフーリエ変換を予め計算し、各ＧＰＳコードでゼロではないフーリエ変換された値だけを記憶し、必要なときはいつでも迅速な使用を可能にすることがさらに効率的であろう。これらのゼロではない値がＰ（ｔ）ではなくＦ（ｔ）のフーリエ変換から得られることを観察するのは容易であり、即ち計算上の負担を減少できる。反復されるシーケンスのＦＦＴはこの短いＦＦＴから得られることができるので、（Ａ４）で示されたように、通常は、Ｋ反復ではなくＦ（ｔ）の１反復のみのＦＦＴを計算することが十分である。また、基準ＧＰＳコードは通常、ゼロのコード位相オフセットと、ゼロの搬送周波数オフセットを有することが想定され、それ故、０．０Ｈｚを中心とすべきであり、図６ではなく図５のグラフ図に類似すべきである。
【００７２】
前述の計算の細部は、米国のＧＰＳ ＰＮコードが長さ１０２３であり、好ましいＦＦＴサイズが２の累乗であり、典型的にはこの説明では１０２４または２０４８であることに関する。ＦＦＴが予め計算されるならば、１．０２３ＭＨｚのサンプルレートに対応して、適切なサイズのＦＦＴを生成するための適切な手順が、基準の１０２３点ＦＦＴを実行し、インデックス512と513との間に余分なゼロ値のサンプルを添付する。同様に、２．０４６ＭＨｚのサンプルレートに対応して、適切なサイズのＦＦＴを生成するための適切な手順が、（チップ当り２サンプルでサンプルされた）基準ＰＮの２０４６点ＦＦＴを実行し、インデックス1024と1025との間に２つの余分なゼロ値のサンプルを添付する。これらの手順は周波数ドメインで行われる補間技術であり、時間ドメインの等価の再サンプリング方法の実行よりも、計算においては効率的である。いずれにせよ、反復される基準シーケンスのＦＦＴはその後、１ＰＮフレームのＦＦＴに対応する各基準周波数サンプル間に適切な数のゼロではない値のサンプルを単に挿入することによって計算されることができる。
【００７３】
データ周波数サンプルがブロック35でＦＦＴプロセスで最初に計算されたとき、残留周波数は知られていなかった。ＧＰＳ信号を正確に効率的に捕捉するために、この未知の残留周波数が発見されなければならない。残留周波数を決定するために、“試行錯誤”のプロセスが使用されることができ、一連の残留周波数は仮説され、各仮説で計算が行われ、その結果は位置をサーチするために解析される。仮説数は大きく、処理時間が検査される仮説数と共に増加する可能性があることを認識すべきである。
【００７４】
38で、37で与えられたデータ周波数サンプルのサブセットが、仮説された残留周波数に応答して選択され、即ち“枝刈り”される。図５で示され、それと共に説明されるように、理想的なＧＰＳ信号Ｐ（ｔ）は周期的な周波数スペーシングｆｒを有する櫛形スペクトルを有し、これはブロックのサンプル数により乗算されたＦＦＴ周波数スペーシングであリ、即ち（１／Ｔｃ）□Ｋ＝ｆｒである。この櫛形スペクトルは実際のデータ周波数サンプルの数分の１だけを占有するゼロではないサンプルを有するので、周波数サーチの複雑性および時間要求において減少が可能である。前述したように、Ｈｚで表される周波数スペーシングｆｒはＰＮフレームレートに等しい。インデックスで表すと、これはデータブロック中の反復されるＰＮフレーム（Ｋ）の数に等しい。
【００７５】
例えば、再度図９を参照すると、Ｋ＝２０であるならば、仮説された残留周波数に対応するデータ周波数サンプルは92aまたは92bのように、スペクトルラインの特定のグループの選択によって選ばれることができる。Ｐ（ｔ）は櫛形スペクトルを有するので、ベースバンドの、雑音のない受信された信号ｓｂ（ｔ）（等式Ａ−２参照）も同様であり、それはこの信号がＰ（ｔ）の周波数変換されたバージョンを含んでいるからである。しかしながら、ｓｂの実際の櫛形ラインは１ｋＨｚの厳密な倍数で位置付けられないが、残留周波数（図６参照）によりオフセットされ、これは決定される必要がある。
【００７６】
サンプリングレートが１．０２４ＭＨｚであり、ブロックサイズが２０ｍｓｅｃであり、ブロックには２０ＰＮシーケンスが存在するならば、受信される信号の隣接する櫛形ラインのスペーシングは１ｋＨｚであるので、認識可能なエネルギを有するＰ（ｔ）のＤＦＴの１０２４ラインだけが存在する。この櫛形スペーシングはサブセットを１０２４データ周波数ラインにのみ限定し、それ故、対応して減少するサイズの逆ＦＦＴがその後の処理で使用されることができる。
【００７７】
別の例として、サンプリングレートが２．０４８ＭＨｚであるならば、１．０ｋＨｚの櫛形周波数スペーシングを有する２０４８のゼロではない値の櫛形ラインが存在するが、エネルギはさらに大きい２．０４８ＭＨｚの通過域を超えて延在する。周波数分離の倍数であるレート（例えば１．０ｋＨｚ）でサンプルする必要はなく、サンプルレートが２の累乗×１．０ｋＨｚである必要もなく、ｓｂ（ｔ）の櫛形スペクトルは依然として残る。しかしながら、総サンプル期間Ｔｃが真の周期的なコンボルーションを実現するために１ミリ秒の倍数であることが望ましい。この要求は省かれることができるが、後に説明するように、幾らか性能を犠牲にするか、速度の劣化を招く可能性がある。
【００７８】
図６を参照すると、これは図５のように、約１．５ｋＨｚ（即ちｆｅ＝１．５ｋＨｚ）の残留搬送周波数を有し、（２０９ｋＨｚで生じる）最大の振幅ラインにより正規化されているスペクトルを有する、２０回反復された１例のＧＰＳ信号（コード＃１）のパワースペクトルのグラフである。図５及び図６の比較によって、両者のケースで櫛形スペクトルが存在することが示され、また図６のスペクトルはこの例では約１５００Ｈｚの残留周波数ｆｅにより、図５のスペクトルに関して単にオフセットされていることも示されている。それ故、１５００Ｈｚ（この例では真の搬送周波数オフセット）の仮説は信号エネルギを含む周波数ラインのセットを適切に選択する結果となる。図６のようにＧＰＳ信号スペクトルが現われても、（単なる櫛形サンプルではなく）各周波数サンプルで現れる図９に示されているような雑音によって妨げられる可能性がある。しかし、ＧＰＳ信号櫛形の周波数サンプル間で生じる雑音は、これらがＧＰＳ信号エネルギをほとんど含んでいないので、ＧＰＳ信号の検出には不適切である。したがって、ＧＰＳ信号の検出目的で、櫛形ライン位置の周波数情報だけを使用する必要がある。詳細に説明するように、各周波数仮説は、可能な櫛形周波数の異なるセットが処理されることを述べ、結果的に、これらの可能な櫛形周波数の異なるセットは、単に相互に循環的にシフトされたバージョンである。
【００７９】
用語“枝刈り”は、周波数データからＫ番目のサンプル毎にのみ選択していることを指している。従来の例では、Ｔｃは２０ＰＮフレームに等しく、Ｋは２０に等しく、即ちその後の処理で使用するためにＦＦＴデータの２０番目毎のサンプルだけを選択する必要がある。さらに一般的には、Ｋは処理されているコヒーレントなデータブロックのＰＮコードの反復数である。このような枝刈りはその後の処理量の減少につながる。
【００８０】
図９と図１０を参照する。図９はＧＰＳ信号を妨害する雑音を含む典型的なデータ周波数サンプルの例である。図１０は、（説明を簡潔にするために）仮説された正の周波数オフセットに対応するデータ周波数サンプルのサブセットを示す表であり、Ｋ番目毎のサンプルがいかにして、仮説された残留周波数の周波数選択のため、サブセットを規定するように選択されるかを示している。ゼロ周波数オフセットを仮説するため、選択を第１のサブセット92aに変換し、これは図９及び図１０の92aに示されている周波数インデックスゼロ（Ａ０，ＡK…）で開始するＫ番目毎のサンプルを含み、図１０の行０に対応する。１インデックス周波数オフセットを仮説するために、第２のサブセット92bが選択され、これはＫ番目毎のサンプルを含んでいるが、周波数インデックス１（Ａ１，ＡK+１…）によりオフセットされ、図１０の行１に対応する。２インデックス周波数オフセットを仮説するために、第３のサブセット92cが選択され、これは周波数インデックス１（Ａ２，ＡK+２…）でオフセットされるＫ番目毎のサンプルを含んでいる。各その次の周波数オフセットを仮説するため、時折、循環的なローテーションと呼ばれるこのプロセスは選択されたデータ周波数サンプルを整数によって変換することにより継続する。周波数オフセット数は（フレームレートを超えるレートに対応して）Ｋを超過することができる。
【００８１】
周波数データセットは循環的と考えられ、即ち周波数Ｋは例えばＫ−ＮおよびＫ＋Ｎと同様である。したがって、所定の行の最後の幾つかのデータサンプルは実際に、第１の行の第１のデータサンプルに対応できることが分かる。例えば92cでは、Ｋが２に等しいならば、92cの最後のインデックスはＮ−Ｋ＋２−Ｎ＝−Ｋ＋２＝０であり、92dの最後のインデックスはＮ−Ｋ＋３−Ｎ＝−Ｋ＋３＝１である。この例では、92cと92dの最後のエレメントはしたがって、それぞれＡ０とＡ１である。同様に、（表では示されていない）負の周波数オフセットは最初に“負の周波数”を選択することにより仮説された。１例として、最小の負の周波数仮説は、選択するデータＡ−１，ＡＫ−１，Ａ２Ｋ−１，Ａ３Ｋ−１，…，ＡＮ−Ｋ−１に対応し、これはＡＮ−１，ＡＫ−１，Ａ２Ｋ−１，Ａ３Ｋ−１，…，ＡＮ−Ｋ−１と同一である。したがって、このアレイの第１のサンプルは実際に、ＦＦＴの周波数サンプルの最後である。ＡＮ／２で開始するアレイの配列をやり直すことが便利であり、それによって周波数データの大半は周波数において増加する。
【００８２】
図１０では、列は“櫛形”周波数インデックス、即ちＮ／Ｋエレメントだけを有する枝刈りされたアレイのインデックスを示している。各行は仮説された櫛形周波数インデックスでの値を示している。勿論、負の周波数オフセットで開始する櫛形は許容され、前述したように構成される行を有する。
【００８３】
したがって、ＧＰＳ信号の存在を識別するのに有用な情報は、一定量（この例では１ｋＨｚ）だけ相互に変位され、残留周波数によりオフセットされているスペクトルライン内に実質的に含まれる。それ故、残留周波数の仮説に続いて、仮説された残留周波数に対応するその後の整合フィルタ計算目的で、その周波数オフセットに対応するスペクトルラインのセット（櫛形）はＦＦＴから選択されることができ、残りは無視される。この減少されたスペクトルライン数は必要とされる次の計算数を減少でき、したがって、各仮説された残留周波数の処理時間を減少する。例えば、ステップ39の整合フィルタ動作で必要とされる、サイズＳＴｃの逆ＦＦＴを行う必要がある代わりに、Ｓのサンプルレートが使用されるならば、サイズＳ／１ｋＨｚの逆ＦＦＴだけが実行される必要がある。したがって、Ｔｃ＝１２８ミリ秒であると想定すると、サンプルレートが１．０２４ＭＨｚであるならば、通常、サイズ１２８□１０２４の逆ＦＦＴを実行する必要がある。スペクトルの疎性（即ちＧＰＳ信号が櫛形スペクトルを有する事実）を利用して、サイズ１．０２４ＭＨｚ／１ｋＨｚ（即ち１０２４）の逆ＦＦＴの計算だけを必要とし、処理の節約は１２８（さらに正確には１．７□１２８）の係数を超える。さらに、処理の節約は、総コヒーレント処理時間Ｔｃが増加するときに改善される。それ故、ＦＦＴサイズの減少がＰＮシーケンスＦ（ｔ）の反復数に関連されることが分かり、即ちＦＦＴサイズの減少係数は、コヒーレントに積分されるＰＮフレーム数が大きい程改良される。
【００８４】
39で、データ周波数サンプルと基準周波数サンプル（例えばＧＰＳコード）のサブセットから相関シリーズを形成するための動作が実行される。これを実現するため、ＦＦＴベースの整合フィルタ動作が以下のように実行されることができる。
データ周波数の選択されたサブセットを、ＧＰＳコードのＦＦＴの複素共役によって乗算する。 （Ａ５）
等式Ａ５の結果の逆ＦＦＴを実行し、この結果的なデータセットで検出動作を行う。 （Ａ６）
結果として、Ｓｂ（ｔ）とＰ（ｔ）の循環的コンボルーションが生じ、これは適切な相関情報を提供し、Ｓｂ（ｔ）の期間がＰＮフレームの整数であることを想定する。この基本的な手順は期間Ｔｃの長いデータセットの処理を必要とし、即ちこの手順は大きいサイズの順方向ＦＦＴの実行を必要とした。しかしながら、よく知られているように、このような大きなＦＦＴを実行する効率的な方法が存在する。計算上の便宜さは、枝刈り手順のために、小さいサイズの逆ＦＦＴだけを行う必要があることから得られる。多くの逆ＦＦＴは多くの周波数仮説に対応して実行される必要があるので、計算上の節約が実現されることができる。これは後の説明で、さらに数学的に証明される。
【００８５】
説明の目的で、ステップ33−39の方法はコヒーレントな方法でデータの１ブロックの処理に対応しており、これはここでは“コヒーレントな相関”または“コヒーレントな処理”と呼ばれるタイプの相関である。感度を改良するため、複数のコヒーレントな相関プロセスからの相関出力は検出されることができ、相関結果を与えるため隣接する時間間隔の数（例えば２乃至２０００ブロック、典型的には５乃至２００ブロック）にわたり結合される。このプロセスは“非コヒーレント相関”と呼ばれ、図１１と共にさらに詳細に後述する。
【００８６】
図３の40で、相関結果（シリーズ）が、一致が発見されるか否かを決定するために解析される。この演算は以下説明するように、任意の数の適切なアルゴリズムで実行されることができる。
【００８７】
図７は、ステップ39の相関動作の結果の図例であり、仮説されたコード位相の関数として振幅を示している。ステップ39の整合フィルタ動作、又は相関演算の結果は“相関シリーズ”と呼ばれる。以下説明するように、多数の相関シリーズは改良された性能を提供するように（コヒーレントおよび／または非コヒーレントに）組合わされることができる。この組合わされたシリーズは、この数のシリーズが一致された状態を決定するために検査されることができるので、“最終的な相関シリーズ”と呼ばれる。図７に戻ると、グラフの結果として、異なるコード位相の一連のライン70は、典型的には１チップのインクリメントまたは２分の１チップのインクリメントで均等に隔てられている。一致が発見されたか否かを決定するため、任意の適切なピーク発見タイプのサーチアルゴリズムが使用されることができる。例えば、各ラインの大きさが考慮されてもよい。例えば、特定の仮説されたコード位相のラインの大きさが全てのラインの中で最大であり、その振幅が予め定められたしきい値を満たすかそれを超えるならば、一致が発見されたことを想定させることができる。図７では、ライン72が最大であるように見え、それ故、（例えば74で示されている）検出しきい値が予め定められたしきい値であるならば、ライン72のコード位相（即ちコード位相位置18）は一致を示すものと想定されよう。所定のしきい値を超える全てのピークを決定し、全てのこのようなピークを潜在的な一致として保持するような、その他のアルゴリズムが使用されてもよい。
【００８８】
図３を再度参照すると、ステップ40後、一致が識別されないならば、動作は決定ステップ41へ移動する。41で、サーチをされる残留周波数がさらに存在するならば、別の周波数仮説がステップ36bで行われ、ステップ37−40が反復される。しかしながら、サーチをされる残留周波数がこれ以上存在しないならば、動作は41から決定ステップ43へ移動し、以下説明するように、サーチするための衛星がさらに存在するか否かを決定する。ステップ40の決定に戻り、一致が発見されたならば、動作はステップ42へ移動し、ここでコード位相オフセットが決定される。
【００８９】
例えば図４を参照して前述したように、データブロックがサンプルされたならば、コード位相は知られておらず、即ちＰＮフレーム期間の開始と終了はまだ突き止められていない。特に、データブロックが整数個のＰＮフレーム45を有するが、データブロックの開始位置が知られておらず、それ故、データブロックの開始及び終了はＰＮフレーム内の何れかの場所に存在することができる。例えばデータブロックが偶然に、49a（コード位相オフセット＝０）で示されているように、第１のＰＮフレームの開始から最後のＰＮフレームの最後まで延在できるが、より多くの可能性としては、データブロックは49bで示されているように、第１のＰＮフレーム内の随意選択的に選択された点から、最後の全ＰＮフレームに続くフレーム内の同一点まで延在する（コード位相オフセット≠０）。
【００９０】
42で、正のサーチ結果に続いて（即ちステップ40で一致が発見された後）、コード位相オフセットはステップ39の整合フィルタ動作の結果から決定される。特に、整合フィルタ動作前に、可能なコードオフセット数が知られている。図７のここで説明した例では、可能なコードオフセット数はゼロから１０２３の範囲（１０２４点のＦＦＴが使用されるならば、全部で１０２４の可能なコード位相）であり、これは１ミリ秒間隔にわたるコード位相オフセットステップ数である。整合フィルタ動作後、（一致の存在を識別した）ライン72も、ゼロからのステップ数としてコード位相オフセットを示す。図７の例では、コード位相オフセットはコード位相位置18にあり、これはこの例では約１８／１０２４ミリ秒に変換する。この位相オフセットはＧＰＳ受信器内のローカルで発生されたクロックの位相に関連する。多くの場合、この位相オフセットの正確性は、特定されたコード位相におけるレベルを、その近傍のコード位相のレベルと組合わせる補間手順を通して改良される。
【００９１】
43で、付加的な衛星からの信号がサーチされるか否かについて決定が行われる。この決定は任意の適切な基準にしたがって行われる。例えば、十分な衛星からの信号が既に位置の確定を行ったことを発見したならば、または可能な視界内の衛星のリストが尽きたならば、サーチの停止をする決定が行われ、44で示されているように、捕捉動作が完了される。しかしながら、より多くの衛星からの信号がサーチされるならば、36cで、次の衛星が選択され、初期の残留周波数が仮説され、ステップ37−42が新しい想定で実行される。
【００９２】
ここで説明されるように、ＰＮシーケンスＦ（ｔ）がコヒーレント処理するデータブロックで複数回反復する知識を使用すると、さらに簡単な逆ＦＦＴ手順が全体的な整合フィルタ手順の一部として可能であることが分かり、そうすれば計算時間が減少する。唯一のドップラ仮説がサーチされるべきならば、処理時間における改良は特に大きい。しかしながら、サーチは通常、多数のドップラ仮説（例えば±５００Ｈｚにわたるサーチは普通である）にわたって実行されるので、ここで記述するようにこの処理の節約の利点はすぐに重要になる。処理を節約する１つの理由は、別々の逆ＦＦＴが実行されるべきことを各ドップラ仮説が必要とすることである。しかしながら、ここで説明する方法では、仮説された櫛形周波数位置での処理周波数サンプルだけを必要とする事実のために、逆ＦＦＴサイズはコヒーレントな周波数ブロックのサイズから独立している。このような周波数サンプルの数は、１ＰＮフレームにわたるデータ周波数サンプルの数と等しいことが容易に分かる。先の例では、１２８ミリ秒の処理プロックサイズでは、必要とされる逆ＦＦＴサイズは係数１２８だけ減少され、結果として、１２８よりも大きい係数だけ改良された処理速度である。大きい順方向ＦＦＴはステップ35のように行われなければならないが、この大きい演算はサーチされるＧＰＳコード当り一度のみ行われる必要があり、幾つかのケースでは、１つの順方向ＦＦＴは多数の仮説されたＧＰＳコードで共有されることができる。
【００９３】
典型的に、大きいドップラ範囲にわたってサーチするため、対応して大きい数のドップラ仮説が逐次的に作られ、代わるがわる実行され、したがって多数の逆ＦＦＴの実行を必要とする。例えば、残留搬送周波数ｆｅ＝±２ｋＨｚの範囲にわたってサーチするために、１２８ミリ秒のコヒーレントな積分時間では、複数のドップラ仮説が必要とされ、即ち、少なくとも５１２に等しい逆ＦＦＴ数（４０００ｋＨｚ×１２８ｍｓｅｃ）が実行される。前の例では、逆ＦＦＴサイズは１３１０７２ではなく１０２４点だけを必要とし、この結果、係数約２１８だけ計算時間を節約できる（ＦＦＴ処理時間はＮｌｏｇ（Ｎ）に比例し、Ｎは変換サイズであることに注意）。例えば、現在利用可能な技術を使用すると、１０２４点のＦＦＴは廉価のＤＳＰ集積回路を使用して、０．５ミリ秒以下で実行されることができ、逆ＦＦＴの全セットの全体的な処理時間は０．２６秒に満たない結果となる。一方、まばらなデータの利点を利用せずに、処理時間は約１分であることが可能である。さらに、多数の仮説されたＧＰＳ ＰＮコードにわたって検索しなければならないので、従来のＦＦＴ処理で必要とされる処理時間は実用的ではないが、開示した方法での処理時間は容易に実用的となる。
【００９４】
種々のドップラ仮説にわたるサーチは、ＦＦＴの隣接するスペクトルラインが予め定められた数、この例では１／ＴｃＨｚ（例えばＴｃ＝１２８ｍｓｅｃならば、１／Ｔｃ＝１／１２８ｍｓｅｃ＝７．８１３Ｈｚ）だけ相互から離れているということを認識することにより簡略化される。それ故、所定のＰＮコードでは、再度、各周波数において順方向ＦＦＴを実行する必要はない。周波数の仮説を変更するため、１インデックス位置だけｓｂのＦＦＴをシフトしさえすればよい（インデックス値は不必要な労力をせずに、信号の捕捉の見込みがあるよう、適切に決定される）。ｙをｓｂのＦＦＴに等しくする。サンプルレートが１．０２４ＭＨｚであり、Ｔ＝１２８ｍｓｅｃである例では、周波数仮説がゼロであるならば、０、１２８、２５６、…等の数を付けられたｙのサンプルを処理する。残留周波数仮説が７．８１３Ｈｚであるならば、１、１２９、２５７等の数を付けられたサンプルを処理する。残留周波数仮説が−７．８１３Ｈｚであるならば、１３１０７１、１２７、２５５等のサンプルを処理する（スペクトルは周期１３１０７１で周期的であるので、インデックス１３１０７１は−１に等しいことに注意）。各ケースで枝刈り処理を受けたブロックは、基準ＧＰＳ波形のゼロではないＦＦＴサンプルの複素共役により乗算される。結果は、１ＰＮフレームを表す整合フィルタ出力を与えるために逆変換される。
【００９５】
この出力のしきい値を超えて発見されるピークの大きさ（または二乗された大きさ）は、処理シーケンスで使用されたものに対応するＧＰＳ信号数とドップラ周波数を有している受信されたＧＰＳ信号の存在及び到着時間を表している。以下説明するように、幾つかのケースでは、インデックス数の数分の１だけＦＦＴをシフトすることが好ましい。これは以下説明するように、周波数セットの単なるローテーションまたはシフトではなく、周波数補間方法を使用して行われることができる。
【００９６】
図８のＡ、図８のＢ、図８のＣは、Ｔｃ＝２０ミリ秒であるときの場合の各３つの仮説された周波数（ｆｈ−５０Ｈｚ、ｆｈ、ｆｈ＋５０Ｈｚ）におけるそれぞれの整合フィルタ動作の実行結果の１例を示している（したがって順方向ＦＦＴのスペクトルラインは５０Ｈｚだけ分離される）。図８のＢでは、仮説された周波数は真の周波数であり、強力な検出されたピーク82は１つの特定のコード位相オフセット（インデックス18）で生じることが分かる。図８のＡ、図８のＣではそれぞれ、仮説された周波数は真の周波数を５０Ｈｚだけ下回るか超えることが分かり、それ故、これらの場合、インデックス位置18の強力なピークは（81および83で示されているように）もはや存在せず、検出しきい値を超える任意の他のピークも存在しないことが分かる。図を簡単にするために、図８のＡ、図８のＢ、図８のＣのプロットは３０までのコード位相インデックスだけを示し、一方１０２４点のＦＦＴが使用されるならば、そのインデックスは実際には０乃至１０２３の範囲であることに注意すること。
【００９７】
図３の方法はコヒーレントな方法によるデータの１ブロック処理に対応し、これはここでは“コヒーレントな相関”と呼ばれる相関のタイプである。しかしながら実際には、コヒーレントな相関は、弱いＧＰＳ信号を検出し、そのコード位相を測定するのに十分な感度をもつことができない。感度を改良するため、複数のコヒーレントな相関プロセス（即ち相関シリーズ）からの相関出力は検出され、組合わされることができ、この手順は“非コヒーレントな相関”または“非コヒーレントな処理”と名づけられている。特に、前述のステップ33−39のコヒーレントな積分プロセスは１以上の付加的な、隣接する時間間隔（典型的に５乃至２０００ブロックの範囲）で反復されることができ、その結果は検出され（例えばそれらの大きさまたは二乗された大きさが計算され）、組合せられる。
【００９８】
この変形は図１１により、さらに正確に理解されるであろう。図１１は、一致された状態をサーチする前に、多数の相関シリーズの組合せが行われる図３の変形である。図１１のブロックの番号付けは、先頭に“１”が付加されている点を除いて、図３の番号付けに類似している。例えば２つの図面の上部ブロックである“ＧＰＳ帯域のエネルギを観察する”が30と130で示されている。図１１は多数の相関シリーズの後検出累算に関連される付加的な処理を含んでいる。即ち、データの多数のブロックにわたって反復するブロック147の出力から138の入力へのフィードバックループが主に付加されている。多数の相関シリーズの組合せが146で実行される。
【００９９】
図１１を吟味すると、133で、33の単一のブロックと比較して、長さＴｃの多数のブロックに対応するデータを選択したことが分かる。その後、ステップ134で、各個々のデータブロックでＦＦＴを実行する。このデータはその後、典型的に、後に使用するためにバッファに記憶される。ステップ136aと137は36aと37と同一である。ステップ138と139はその後、（所定のＳＶと残留周波数に対応する）基準周波数サンプルと所定のデータブロックの周波数サンプルからの相関シリーズの計算の一部として、枝刈りアルゴリズムを使用する。これは38と39に類似している。しかしながら、ステップ146で、結果的な相関シリーズを、先のデータブロックで類似して実行されたものと組合わせる。典型的に、この組合せは、大きさ、二乗された大きさのタイプの検出動作を相関シリーズにおいて実行し、その後、その結果を先のブロックで類似して行われたものに付加することにより行われる。幾つかのケースでは、組合せは単なる付加または他のコヒーレントな組み合わせであってもよい。後者のケースは、大きいデータセットでコヒーレントな処理を行う能力を計算のリソースが限定する場合に、適切である。
【０１００】
147で、右への分岐は、全てのデータブロックが処理されていない場合に、次のデータブロックで138、139、146の処理を反復するためのものであり、その点（147）で処理の流れは140へ進む。処理が140へ進むとき、一致される状態を決定するために所望な全ての相関シリーズを組合わせる。この点で組合わされた相関シリーズは“最終的な相関シリーズ”と呼ばれる。図３で説明した方法と類似の方法で、最終的な相関シリーズは一致された状態、典型的には検出しきい値を超えるピークで検査され、対応するコード位相オフセットが発見される。
【０１０１】
先の説明では、動作138、139、146はデータの連続するブロックで反復されるが、仮説されたＳＶ、基準周波数サンプル、残留周波数は各反復で同一であることに注意する。140で一致が発見されないならば、（セットが完全にサーチされていないならば）新しい残留周波数が136bで選択され、処理138、139、146は第１のデータブロックで新たに開始する（145はブロック番号を再度初期化する）。ステップ135で、全てのデータブロックにおいてＦＦＴを先に計算したので、仮説された次の残留周波数を変更するときに、さらに順方向ＦＦＴを行う必要がない。即ち、各データブロックの周波数サンプルはバッファに記憶されており、それぞれその後の残留周波数仮説で再使用されることができる。
【０１０２】
一致が発見された後、または全ての残留周波数が尽きた後、処理は143へ進み、ここでさらにＳＶが検査を必要とされるならば、136cで、次のＳＶと初期周波数を選択し、ステップ133へ進む。データシーケンスが存在しないときのような、いくつかのケースでは、この点でステップ136aへ代わりに進み、先のＦＦＴ演算により既に計算された135からのデータ周波数サンプルを再使用する。
【０１０３】
以下の説明はここで説明される１方法の動作の１説明である。
【０１０４】
最初に、逆ＦＦＴ演算が行われる方法を考慮する。最初にサンプルされた時間データはｘ（ｎ）：ｎ＝０，１，２，…，として表されることができ、これはデータサンプルｘ（０），ｘ（ＴＳ），ｘ（２ＴＳ）の簡略表記であり、ここでＴＳはサンプル時間期間である。このサンプルされたデータのディスクリートなフーリエ変換（“ＤＦＴ”）はｙ（０，１，２，…）により示される。このデータのＤＦＴは周波数０，１／（ＮＴＳ），２／（ＮＴＳ）…，ｍ／（ＮＴＳ）,…，における周波数サンプルを効率的に示し、ここでｍはサンプル数である。ＤＦＴｙ（ｍ）は各ｍにおいて、次式によって示される。
【数１】
【０１０５】
循環的な対称により、インデックスｍに対応する周波数（即ち周波数ｍ／（ＮＴＳ））はインデックスｍ−Ｎに対応する周波数（即ち周波数（ｍ−Ｎ）／（ＮＴＳ））に等しいので、Ｍ＞Ｎ／２に対応するＤＦＴの周波数は、実際には負の周波数である。ここで、この説明目的で、１）ＧＰＳフレーム期間がＲ入力サンプルに対応し、２）先のように、任意の衛星データは除去されており、３）ブロックサイズＮはＫフレームに対応し、即ちＫ＝ＫＲであり、４）信号変調における任意のドップラ効果は無視できる程度であることを想定する。これらの想定はＦＦＴアルゴリズムが周期的なコンボルーションを行うことを可能にする。
【０１０６】
前述したように、整合フィルタ動作は根本的に、信号データと、周期的に反復された基準の循環コンボルーションであるので、Ｒサンプルを整合フィルタ動作から発見することにのみ関心がもてる。したがって、整合フィルタ結果も周期Ｒにより周期的である。これらの状態下で、既知の方法により、等式（Ｂ１）のｙ（ｍ）における演算によって整合フィルタ出力を与えることができる。
【数２】
【０１０７】
ここでｇは、Ｋ回反復された［ｘ（ｎ）と同一のレートでサンプルされた］ＧＰＳ基準ＰＮ波形のＦＦＴであり、＊は複素共役を表し、ｒは出力時間変数であり、これは［０，１，…，Ｒ−１］にわたる範囲だけを必要とする。等式（Ｂ２）では、信号ｙ（ｍ）の残留搬送周波数はゼロであることを仮説している。前述したように、ＰＮシーケンスはフレーム毎、即ちＲサンプル毎に周期的であるので、関数ｇ（ｍ）は（周波数において）Ｎ／Ｒ＝（ＫＲ／Ｒ）＝Ｋサンプル毎にゼロではない値を有する。例えばＮがＧＰＳデータの２０フレームに対応するならば、ｇの（最初から開始する）ＦＦＴの２０番目毎のサンプルがゼロではない。したがって、等式（Ｂ２）の和内の積は２０番目のサンプル毎にのみゼロではなく、したがって（Ｂ２）を次式のように書くことができる。
【数３】
【０１０８】
最後の和はＲ点の逆ＤＦＴである。したがって、整合フィルタ動作で必要とされる逆ＤＦＴがＲサンプルＦＦＴアルゴリズムだけを使用して行われてもよいことが示されており、これは処理時間とメモリの要求を減少する。さらに、データＫのＰＮフレームが幾つ処理されても、前述の条件が満たされる限り、Ｒ点の逆ＤＦＴだけが必要である。等式（Ｂ３）は全Ｎ点の逆ＦＦＴが等式（Ｂ２）のように実行される場合に得られる等式と数学的に同一であることに注意する。等式（Ｂ３）は逆ＦＦＴの実行においてｙのＦＦＴからのＫ番目の点毎の選択を明白に示していることにも注意する。これは“枝刈り”手順、即ち逆ＦＦＴを行うための点のサブセットの選択のベースである。等式（Ｂ３）は、仮説された残留搬送周波数エラーが正しいか否かを決定する。しかしながら、このプロセスは、残留搬送周波数エラーが１／Ｔｃと比較して、小さいときに強力な検出指示を発生するだけである。
【０１０９】
前述の等式（Ｂ３）は、残留搬送周波数をゼロと想定して、変換されたデータサンプルの処理に対応する。これは残留周波数がゼロに近いときのみ強力な相関ピークを発生する。この想定を変更するため、ドップラシフトはｄ／（ＮＴＳ）であると想定され、ここでｄは整数であり、等式（Ｂ３）は以下のように変更される。
【数４】
【０１１０】
ここで［］ｍｏｄ Ｎは、括弧を付けられた量のモジュロＭである。本質的に、ドップラ仮説が正しいことを想定して、ゼロではない（即ち１／Ｔｃよりも非常に小さい）残留周波数を有するように、入力信号を周波数シフトしている。等式（Ｂ４）はｙの循環特性を利用する。この変換は、単にｄスペクトルラインによるｙの単なる周波数変換であり、ｙの第１のエレメントに関してｄ位置で開始する（循環方法による）シーケンスｙをインデックスすることにより率直に実行されることに注意する。この方法は、背景部分で説明した従来の制限をなくし、そうでなければ、この従来の制限は約−５００乃至５００Ｈｚよりも大きい範囲にわたるサーチを効率的に限定する。ドップラ仮説ｄにおける唯一の制限は、時間ドップラ効果（即ち信号変調におけるドップラ）による、ｙの拡張に関する盲目的な制限である。この制限は以下説明するようにして除去されることができる。
【０１１１】
等式（Ｂ４）の１つの便利な面は、異なるＧＰＳコードを処理するために、別の順方向変換を行う必要がないことである。幾つかの状態では、“ｇ”の適切なＧＰＳコード（例えば適切なゴールドコード）は先の式に代入されることができ、従来変換されたデータが使用され続けることができる。これは、２以上の同時に受信されたＧＰＳ信号に存在する衛星データ情報（メッセージ）が実質的に同一であるならば、行われることができる。この状態により、同時に受信された信号におけるデータ送信を同時に除去することが可能である。これは２つの条件が満たされた場合に可能であリ、その条件は（Ａ）衛星からの差距離がかなり小さい（例えば３００ｋｍ内）ことと、（Ｂ）メッセージデータ情報がＳＶ送信間で類似であることである。項目（Ｂ）は例えば衛星の暦が送信されるとき、しばしば生じる。また項目Ｂはコヒーレントな積分時間が２０ミリ秒よりも小さいならば、重要ではない。、将来の構造で提案されているような、データを含まないＧＰＳモードでは、条件（Ｂ）は適用せず、この変形はさらに一般的に行われることができる。
【０１１２】
先の説明では、（受信機の基準局部発振器が誘発する“ドップラ”を含めた）ドップラシフトの効果は主に搬送周波数に影響することが想定されている。しかしながら、コヒーレントな積分時間ＮＴＳが十分に大きくなるならば、信号の変調における（即ちＰＮシーケンスＰ（ｔ）における）ドップラの効果を無視することができない可能性がある。本発明の目的では、この変調のドップラ効果、または“時間ドップラ”効果は、主に変調レートを変更し、その結果、ＧＰＳ受信機で発生された基準に関する信号波形の“拡張”または“圧縮”が生じる。
【０１１３】
例えば、ＧＰＳの標準的な位置サービス（民間サービス）のためのＣ／Ａコードを処理するため、チップ変調レートに対する搬送周波数の比は約１５７５．４２ｅ６／１．０２３ｅ６＝１５４０である。したがって搬送波における約５００Ｈｚのドップラシフトは変調において約５０００／１５４０＝３．２５Ｈｚのドップラシフトになる。データの短いブロック（例えば２０ミリ秒）をコヒーレントに処理するため、このような時間ドップラは重要ではない可能性がある。しかし、データの長いブロックを処理するとき、その効果は整合フィルタのピーク出力の大きさを減少することによって、システムの感度を劣化する可能性がある。経験則として、（局部発振器効果を含める）変調ドップラがｐヘルツであるならば、総ブロックサイズＮはＴｃ秒に対応し、付加的な処理なしに、量ｐＴｃは有害作用を減少するために約１／２よりも下に維持されるべきである。
【０１１４】
搬送波における１０，０００ＨｚのドップラシフトがＰＮ変調における７．１４３Ｈｚドップラシフトを生じる前述のケースを考慮する。コヒーレントなブロックサイズが約１００ミリ秒であるならば、ｐＴｃは＝０．７１４３であり、システム性能における幾らかの劣化が顕著であろう。さらに、整合フィルタからのピーク出力の時間が、ゼロではないドップラのケースに関してｐＴｃ／２チップにより変位されるであろう。したがって大きいドップラサーチ範囲と、長いコヒーレントな積分時間は、修正されていない状態であるならば、時間ドップラ効果からの損失になる。この問題は特に以下の２つの重要な状態で増幅される。
（１）ＧＰＳ受信機により観察されるように、１つのＧＰＳ衛星信号から別のＧＰＳ衛生信号へのドップラシフト間の大きな差。この項目については既に前述した。
（２）ＧＰＳ局部発振器周波数のその理想的な周波数に関するエラーによる効率的なドップラシフト。
【０１１５】
項目（２）に関して、ＧＰＳ局部発振器は理想的なＧＰＳ周波数から異なる可能性がある。例えば、時折、ＧＰＳ受信機は、同期されたセル電話の周波数からその局部発振器周波数を得ることができ、したがって低エラーを実現できる。しかしながら、幾つかの状態では、これは可能ではないことがある。良好に温度補償された水晶振動子でさえもＧＰＳ周波数（１５７５．４２ＭＨｚ）で、±３０００Ｈｚを超える周波数エラーを有する可能性がある。このような周波数エラーは真のドップラシフトではないが、これらは移動するプラットフォームから観察されるドップラシフトに類似して、ＧＰＳ受信機で搬送波と変調シフトの両者を発生する。このような周波数エラーは全てのＧＰＳ受信機に対して共通であり、それ故、ある程度まで処理された全てのＧＰＳ信号に影響する。それにもかかわらず、これらの周波数エラーは特に、長いコヒーレントなブロックサイズでは劣化した性能を生じ得る。
【０１１６】
前述の問題に対処する１方法は、ＧＰＳ ＳＶ（衛星ビークル）のドップラ仮説に釣り合うレートで、および／または局部発振器エラーのために、入力データシーケンスを再度サンプルすることである。信号の再サンプリングにより、デジタル信号処理方法を使用して、入力信号は結果として拡張または圧縮されることができ、それによってコヒーレントな処理ブロック内には再度、ＧＰＳデータのＰＮフレームが整数個、存在する。このような再サンプリングなしでは、コヒーレントなブロック中のこのようなフレームの数はもはや整数ではないが、多かれ少なかれ幾つかのサンプル数程度に大きい量であり、これは整合フィルタ動作により発生するピーク信号の深刻な劣化を生じる可能性がある。
【０１１７】
しかしながら、時間ドメインにおける再サンプリングは、周波数の範囲及び所定のＳＶで、再サンプルし、大きい順方向ＦＦＴを実行することを必要とする可能性がある。前述したように、その範囲は｜ｐＴｃ｜が約１／２よりも小さい。残念ながら、この多数の順方向ＦＦＴを実行する要求は、システムメモリ増加の要求と、処理時間の増加との両者を生じる。
【０１１８】
しかしながら、周波数ドメインで再サンプリング機能を行うことにより、前述の欠点は削除され、特に付加的な順方向ＦＦＴを実行するための要求は削除される。換言すると、再サンプリング機能は時間ドメインではなく、変換された信号ｙで実行されることができる。この方法は付加的な順方向ＦＦＴを実行する要求を回避するが、構成にしたがって、幾つかの付加的な記憶が必要とされる可能性がある。
【０１１９】
周波数ドメインの再サンプリングの裏付ける基本的な原理は以下のフーリエ変換関係式から説明されることができる。
【数５】
【０１２０】
ここでｘは時間波形であり、ｙはｘのフーリエ変換であり、ａはスケールシフトまたは拡張である。このようにして、何れかのドメインの拡張が行われることができる。
【０１２１】
拡張または圧縮は周波数サンプルの再サンプリング、即ち部分的再サンプリング方法を含むプロセスを含んでいる。（Ｂ５）から、周波数サンプルがｙ（ｍ）と呼ばれ、したがってこれらのサンプルが最初に周波数ｍ＝［０，１，２，…］／（ＮＴＳ）で与えられるならば、これらのサンプルは周波数ｍ／ａで推定されるサンプルによって、即ちｍｒ＝［０，１，２，…］／（ａＮＴＳ）＝［０，１／ａ，２／ａ，…］の周波数で推定されるサンプルによって置換されることが分かる。
【０１２２】
データサンプルが対称的に約０Ｈｚ隔てられることを確実にしなければならないので、この最後の結果は正の周波数で補正されるだけである。これを行うため、初期セットを−Ｎ／２−１，−Ｎ／２，…−１，０，１…，Ｎ／２−１，ｎ／２の順序に順序付けし直すならば、再度サンプルされるセットは周波数で再度サンプルされる。
［（−Ｎ／２−１）ａ，（−Ｎ／２）／ａ，…，−２／ａ，−１／ａ，０，１／ａ，２／ａ，…，（Ｎ／２）／ａ］／（ＮＴＳ） （Ｂ６）
即ち、オリジナルの順序を使用するならば、周波数において再度サンプルされる。
ｍ／ａ：ｍ＝０，１，２，…，Ｎ／２の場合 （Ｂ７）
N＋(ｍ-Ｎ）/ａ：ｍ＝Ｎ／２＋１，Ｎ／２＋２，…，Ｎ−１の場合 （Ｂ８）
ここで、周波数インデックスｍがｍ＋Ｎまたはｍ−Ｎと同一であるような周波数の循環特性であることに注意する。
【０１２３】
等式（Ｂ６）または（Ｂ７）の再サンプリングは、ＤＦＴにより推定される通常のディスクリートな周波数の“間”にある周波数の周波数応答を推定することを含んでいる。これは例えば“ｓｉｎｃ”補間回路により行うのが比較的容易である。入力データは時間を限定されているので、コンボルーション手順を通して、スペクトルラインの１セットに関して、周波数□｜□｜＜０．５Ｈｚの（複素数）周波数応答を推定できる。例えば周波数ｙ（ｍ０＋□）のスペクトル応答を推定するため、以下の積を形成し、ここでｍ０は整数である。
【数６】
【０１２４】
ここでｍの範囲は全ての可能な値（即ち、ｍ−Ｎ／２＋１からｍ＋Ｎ／２）にわたる。
【０１２５】
この計算に対する簡単な概算は２または３値のみのｍを必要とする。等式（Ｂ９）の２項の推定による損失の推定は、□が−０．５乃至０．５Ｈｚの範囲にわたるならば、このような感度損失が１ｄＢよりも小さいことを示す。問題とするほとんどの変調のドップラシフトでは、等式（Ｂ５）による拡張が、比較的多数の連続する周波数サンプルでかなり一定であることが考えられる。したがって、等式（Ｂ９）の補間手順は、多数の連続する再サンプルされたスペクトル値を決定するために、ｓｉｎｃ重み付け係数で同一値を使用することができる。
【０１２６】
前述の再サンプリング方法はしたがって、アルゴリズムの使用を可能にし、周波数データｙが一連の小さいブロック、例えばそれぞれ１０２４のサイズに分解され、各ブロックは固定された係数のセットによる補間手順を使用して再サンプルされる。ブロックを処理する前に、係数が計算されるか、表で参照される。この手順は再サンプリング動作の処理負担を非常に減少できる。例えば、等式（Ｂ９）のような２点補間手順が使用されるならば、再サンプリング手順は（前述の表参照を無視して）各補間された値を計算するために４つの実数倍と２つの加算だけを必要とする。この方法は例えば６４Ｋに等しいブロックサイズでＦＦＴを計算するのに必要なデータサンプル当り８つのバタフライと比較されることができる。これらのバタフライは３２の実数倍と４８の加算を必要とし、周波数ドメインにおける補間に関して約１６の係数だけ計算を増加する。したがって、周波数ドメインの再サンプリングは、時間ドメインの再サンプリングよりも、非常に実践的で効率的であると考えられている。
【０１２７】
再サンプリングは、大きな範囲のドップラシフトの処理時、および／または異なるＳＶからの信号の処理時に、変調ドップラを補償するのに有用である。このような場合、同一のフーリエ変換されたデータセットが使用されることができ、それ故、オリジナル時間データの処理は必要ではない。しかしながら前述したように、同一のフーリエ変換されたデータセットを有する異なるＳＶの処理は、初期のコヒーレントな処理前に除去が可能であるように、衛星メッセージデータが類似する状態に限定される可能性がある。いずれにせよ、再サンプリング動作が実行された後でさえも、第２及び付加的な再サンプリングが必要とされる場合に、オリジナルのフーリエ変換されたデータセットを維持することが有用である。オリジナルのフーリエ変換されたデータセットが利用可能ではないならば、再サンプルされたセットで再サンプリングを行う必要があるが、この方法では、正確な再サンプリングが実行されないと累積エラーを生じかねない。
【０１２８】
反復されるＰＮ信号に関連するスペクトルがまだらであること、即ち櫛形ライン型であることにより、枝刈り動作は、順方向ＦＦＴからの周波数データのサブセットの選択として規定されている。スペクトルの補間が必要とされるとき、前述したように、サブセットを単に選択するのではなく、周波数サンプル間の補間により構成する。それにもかかわらず、そのように構成されたサブセットのサイズは、簡単な選択が行われるケースに類似している。即ち、これは典型的に１ＰＮフレーム当りの信号サンプル数に等しい。例えば先の例では、これはサンプルレート１．０２４ＭＨｚまたは２．０４８ＭＨｚに対応して、１０２４または２０４８サンプルであった。逆ＦＦＴサイズはしたがって、同様にこれらのサイズである。結果として、“枝刈り”の定義は、補間手順による周波数サンプルのサブセットの構成と、周波数サンプルのサブセットの直接的な選択に及ぶ。
【０１２９】
類似の方法では、補間手順は、ＦＦＴのラインスペーシングよりも小さいインクリメントにより連続する周波数仮説を変更したいときに使用されることができ、例えば１／２ラインスペーシングのインクリメントが望ましい。さらに、枝刈りの定義は、周波数仮説がＦＦＴラインスペーシングの数分の１だけ変更される補間手順による周波数サンプルのサブセットの構成に及ぶ。
【０１３０】
これらの教示を考慮して、代わりの実施形態が容易に実行されることができることを当業者は認識するであろう。
【０１３１】
例えば、先の説明では、図２または図３により例示されているように、信号をゼロに近い周波数へ周波数変換するための初期周波数変換動作が存在する。これは技術でよく知られている方法により、通常の局部発振器及びミキサで行われることができる。また、ＧＰＳ周波数帯域に近い入来ＲＦエネルギを濾波し、フィルタ帯域幅に釣り合うレートで、この濾波されたエネルギを直接サンプリングすることによっても行われることができる。この方法は効率的な周波数変換を結果とすることができることが良く知られている。したがって、用語“周波数変換”はこれらの直接ＲＦサンプリング方法と、通常の周波数変換方法に適用する。さらに、図３は、搬送周波数がデジタル化の前に除去され、残留周波数ｆｅを残すことを示しているが、大抵の場合、搬送周波数の大半が除去されるだけであり、信号はデジタル化の前に低ＩＦ周波数、例えばｆＩＦ＋ｆｅに変換された周波数である。デジタル化動作に続いて、ＩＦ周波数ｆＩＦは典型的に、デジタル信号処理方法により実質的に除去される。処理結果はその後、図３のステップ33で示されているように続く。初期の信号事前処理におけるこのような変形は当業者に明白であろう。
【図面の簡単な説明】
【０１３２】
【図１】複数の基地局と通信する移動局のＧＰＳ受信機により受信されるＧＰＳ信号を発射する衛星を含む通信および位置検出システムの斜視図。
【図２】ＧＰＳ受信機及びセルラ通信システムを含む移動局の１実施形態のブロック図。
【図３】ここで説明されているコヒーレントな積分プロセスを示すフローチャート。
【図４】理論的ＧＰＳ信号の構造および波形成分を示すブロック図。
【図５】残留搬送周波数ｆｅ＝０における、２０回反復されたＧＰＳ信号（この例ではゴールドコード＃１）の周波数の関数として、パワースペクトルを示すグラフ。
【図６】残留搬送周波数が約４．５ｋＨｚにおける、２０回反復されたＧＰＳ信号（この例ではゴールドコード＃１）の周波数の関数として、パワースペクトルを示すグラフ。
【図７】周波数の関数として振幅を示している、整合フィルタ動作の結果の１例のグラフ。
【図８】異なるドップラ周波数仮説における整合フィルタ動作の結果を比較しているグラフのセット。
【図９】実際のデータに典型的な周波数内容を表すデータ周波数セットを示すグラフ。
【図１０】仮説された残留周波数の周波数選択においてサブセットが規定される方法を示している、仮説された周波数オフセットに対応するデータ周波数サンプルのサブセットを示す表。
【図１１】多数のコヒーレントな積分プロセスの結果を組合わせることを含んだプロセスを示すフローチャート。
【特許請求の範囲】
【請求項１】
複数の送信機のうちの１つから予め定められた搬送周波数で送信され、前記１つの送信機を識別する擬似雑音（ＰＮ）シーケンスにしたがって変調される波形を含んでいる信号の処理方法において、
前記搬送周波数に近い電磁エネルギを受信し、前記エネルギを前記予め規定された時間期間でデジタル化し、
前記送信機のうちの１つのアイデンティティを仮説し、それに関連する信号を決定し、
前記決定された信号に対応する基準周波数サンプルの１セットを提供し、
前記決定された信号の第１の残留周波数を仮説し、
前記デジタル化されたエネルギから、少なくとも前記反復するＰＮシーケンスの２反復に等しい長さのデータの第１のサブセットを選択し、
データの前記第１のサブセットを使用して、データ周波数サンプルの第１のセットを計算し、
前記仮説された第１の残留周波数を使用して、データ周波数サンプルの前記第１のセットを枝刈りして、前記データ周波数サンプルの第１のサブセットを発生し、
データ周波数サンプルの前記第１のサブセットと前記基準周波数サンプルから、少なくとも１つの相関シリーズを入力として使用して、最終的な相関シリーズを計算し、前記送信された信号と、前記仮説された信号との間に一致された状態が存在するか否かの指示を発生することを含んでいる方法。
【請求項２】
前記デジタル化されたエネルギから、少なくとも前記ＰＮシーケンスの２反復に等しい長さのデータの第２のサブセットを選択し、
データの前記第２のサブセットを使用してデータ周波数サンプルの第２のセットを計算し、
データ周波数サンプルの前記第２のセットのサブセットを提供するため、前記仮説された第１の残留周波数に応答して、データ周波数サンプルの前記第２のセットを枝刈りすることををさらに含み、
前記計算は、データ周波数サンプルの前記第１のサブセットと前記基準周波数サンプルから計算される少なくとも前記相関シリーズと、データ周波数サンプルの前記第２のサブセットと前記基準周波数サンプルから計算された相関シリーズとを、入力として使用して、最終的な相関シリーズを計算し、前記送信された信号と、前記仮説された信号との間に一致された状態が存在するか否かの前記指示を発生する請求項１記載の方法。
【請求項３】
前記計算は、前記第１の相関シリーズと、前記第２の相関シリーズを少なくとも検出し、組合わせることを含んでいる請求項２記載の方法。
【請求項４】
前記枝刈りはさらに、データ周波数サンプルの前記第１のサブセットから、整数Ｋによって相互に関して隔てられているインデックスを有する複数のサンプルを選択することを含み、ここでＫは前記データブロック中のＰＮシーケンスの数である請求項１記載の方法。
【請求項５】
前記第１のサブセットは、前記ＰＮシーケンスの反復率により相互に関して隔てられている複数のデータ周波数サンプルを具備している請求項１記載の方法。
【請求項６】
前記枝刈りは、データ周波数サンプルの前記第１のセットの間で補間することを含んでいる請求項１記載の方法。
【請求項７】
基準周波数サンプルの前記提供は、前記ＰＮシーケンスでＤＦＴ動作を行うことを含んでいる請求項１記載の方法。
【請求項８】
前記計算は、重み付けされた周波数サンプルの１セットを形成するために、前記データ周波数サンプルの前記第１のサブセットを、基準周波数サンプルの前記セットで乗算することを含んでいる請求項１記載の方法。
【請求項９】
前記計算は、前記第１の相関データシリーズを発生するために、重み付けされた周波数サンプルの前記セットで逆ＤＦＴを行うことを含んでいる請求項８記載の方法。
【請求項１０】
前記送信機は、ＧＳＰ周波数でＧＰＳ信号を送信する複数のＧＰＳ衛星を具備し、各ＧＰＳ衛星は特有のＰＮシーケンスを送信する請求項１記載の方法。
【請求項１１】
前記最終的な相関シリーズは、ＧＰＳ信号の存在を識別するためにサーチされ、ＧＰＳ信号の存在が識別されたならば、ＰＮコードの位相オフセットを決定し、前記受信機におけるＧＰＳ信号の到着時間を決定する請求項１記載の方法。
【請求項１２】
第２の残留周波数を仮説し、
データ周波数サンプルの第３のサブセットを提供するため、前記仮説された第２の残留周波数に応答して、データ周波数サンプルの前記第１のセットを枝刈りし、
データ周波数サンプルの前記第３のサブセットと前記基準周波数サンプルから、第３の相関シリーズを計算し、
少なくとも前記第３の相関シリーズを具備する第２の最終的な相関シリーズを計算し、
前記送信された信号と前記仮説された信号との間に一致された状態が生じるか否かを決定するため、前記第２の最終的な相関シリーズを検査することをさらに含んでいる請求項１記載の方法。
【請求項１３】
前記データブロックは、前記ＰＮシーケンスの約５乃至２０の反復範囲内のサイズを有する請求項１２記載の方法。
【請求項１４】
さらに、前記受信機の位置を決定するため、到着時間情報を使用することを含んでいる請求項１記載の方法。
【請求項１５】
複数の送信機のうちの１つから送信され、反復するＰＮシーケンスにより変調される波形を含んだ信号の処理方法において、
前記送信機のうちの１つおよびその搬送周波数に関連する信号を仮説し、
処理される前記信号の搬送周波数に近い周波数で受信される電磁エネルギから、前記反復するＰＮシーケンスの少なくとも２反復に等しい長さのデータのサブセットを抽出し、
前記データ周波数サンプルのサブセットを発生するため、前記仮説された搬送周波数に応答して、データの前記サブセットから計算される１セットのデータ周波数サンプルを枝刈りし、
前記仮説された信号に対応するデータ周波数サンプルの前記サブセットと基準周波数サンプルから決定される少なくとも１つの相関シリーズを入力として使用して、最終的な相関シリーズを計算し、
前記送信された信号と前記仮説された信号との間に一致された状態が生じるか否かを決定するため、前記最終的な相関シリーズを検査することを含んでいる方法。
【請求項１６】
複数の送信機のうちの１つから予め定められた周波数で送信される信号を受信する位置検出システムを含んでいる移動局であって、前記送信される信号は、信号を送信する送信機を特有に識別する周期的に反復するシーケンスを含んでいる移動局において、
予め定められた周波数の電磁エネルギを予め規定された時間期間だけ観察し、デジタル化する手段と、
前記複数の送信機のうちの１つを仮説し、前記仮説された送信機から送信される仮説された信号に対応する基準周波数サンプルの１セットを提供する手段と、
残留周波数を仮説する手段と、
前記周期的に反復するシーケンスの少なくとも２反復に等しい長さの前記デジタル化された電磁エネルギの第１の部分を選択し、それによってデータブロックを規定する手段と、
前記データブロックに応答して、データ周波数サンプルの１セットを計算する手段と、
前記データ周波数サンプルの周期的に隔てられたサブセットを提供するため、前記仮説された残留周波数に応答して、前記データ周波数サンプルを枝刈りする手段と、
前記データ周波数サンプルの前記サブセットと、前記基準周波数サンプルとから、第１の相関シリーズを計算する手段と、
少なくとも前記第１の相関シリーズを具備する最終的な相関シリーズを計算する手段と、
前記仮説された信号と、前記受信された信号との間に信号の一致状態が生じるか否かを識別するため、前記最終的な相関シリーズをサーチし、一致された状態が前記仮説された信号と、前記受信された信号との間で発見されたならば、タイミング情報を決定する手段とを具備している移動局。
【請求項１７】
前記周期的に隔てられたサブセットは、整数Ｋによって相互に関して隔てられているインデックスを有する複数のサンプルを具備し、ここでＫは前記データブロック中の前記周期的に反復するシーケンスの反復数である請求項１６記載の方法。
【請求項１８】
前記周期的に隔てられたサブセットは、前記周期的に反復するシーケンスの反復率により相互に関して隔てられている隣接するサンプルを有する複数のサンプルを具備している請求項１６記載の移動局。
【請求項１９】
前記枝刈り手段は、前記データ周波数サンプル間で補間する手段を含んでいる請求項１６記載の移動局。
【請求項２０】
前記移動局は前記基準周波数サンプルを記憶するためのメモリを具備している請求項１６記載の移動局。
【請求項２１】
最終的な相関シリーズを計算するための前記手段は、前記第１の部分とは異なる、前記デジタル化された電磁エネルギの第２の部分から計算された第２の相関シリーズに前記第１の相関シリーズを非コヒーレントで結合するための手段を含んでいる請求項１６記載の移動局。
【請求項２２】
前記第１の相関シリーズを計算するための前記手段は、重み付けされた周波数サンプルのセットを形成するため、前記データ周波数サンプルの前記第１のサブセットを基準周波数のサンプルの前記セットで乗算するための手段と、前記第１の相関シリーズを発生するため、重み付けされた周波数サンプルの前記セットで逆ＤＦＴを行う手段とを含んでいる請求項１６記載の移動局。
【請求項２３】
前記送信機はＧＰＳ周波数でＧＰＳ信号を送信する複数のＧＰＳ衛星を具備し、各ＧＰＳ衛星は特有の周期的に反復するシーケンスを送信する請求項１６記載の移動局。
【請求項２４】
前記データブロックは前記周期的に反復するシーケンスの整数回の反復に対応するサイズを有する請求項１６記載の移動局。
【請求項２５】
さらに、前記移動局の位置を決定するために前記タイミング情報を利用するＧＰＳ検出システムを具備している請求項１６記載の移動局。
【請求項１】
複数の送信機のうちの１つから予め定められた搬送周波数で送信され、前記１つの送信機を識別する擬似雑音（ＰＮ）シーケンスにしたがって変調される波形を含んでいる信号の処理方法において、
前記搬送周波数に近い電磁エネルギを受信し、前記エネルギを前記予め規定された時間期間でデジタル化し、
前記送信機のうちの１つのアイデンティティを仮説し、それに関連する信号を決定し、
前記決定された信号に対応する基準周波数サンプルの１セットを提供し、
前記決定された信号の第１の残留周波数を仮説し、
前記デジタル化されたエネルギから、少なくとも前記反復するＰＮシーケンスの２反復に等しい長さのデータの第１のサブセットを選択し、
データの前記第１のサブセットを使用して、データ周波数サンプルの第１のセットを計算し、
前記仮説された第１の残留周波数を使用して、データ周波数サンプルの前記第１のセットを枝刈りして、前記データ周波数サンプルの第１のサブセットを発生し、
データ周波数サンプルの前記第１のサブセットと前記基準周波数サンプルから、少なくとも１つの相関シリーズを入力として使用して、最終的な相関シリーズを計算し、前記送信された信号と、前記仮説された信号との間に一致された状態が存在するか否かの指示を発生することを含んでいる方法。
【請求項２】
前記デジタル化されたエネルギから、少なくとも前記ＰＮシーケンスの２反復に等しい長さのデータの第２のサブセットを選択し、
データの前記第２のサブセットを使用してデータ周波数サンプルの第２のセットを計算し、
データ周波数サンプルの前記第２のセットのサブセットを提供するため、前記仮説された第１の残留周波数に応答して、データ周波数サンプルの前記第２のセットを枝刈りすることををさらに含み、
前記計算は、データ周波数サンプルの前記第１のサブセットと前記基準周波数サンプルから計算される少なくとも前記相関シリーズと、データ周波数サンプルの前記第２のサブセットと前記基準周波数サンプルから計算された相関シリーズとを、入力として使用して、最終的な相関シリーズを計算し、前記送信された信号と、前記仮説された信号との間に一致された状態が存在するか否かの前記指示を発生する請求項１記載の方法。
【請求項３】
前記計算は、前記第１の相関シリーズと、前記第２の相関シリーズを少なくとも検出し、組合わせることを含んでいる請求項２記載の方法。
【請求項４】
前記枝刈りはさらに、データ周波数サンプルの前記第１のサブセットから、整数Ｋによって相互に関して隔てられているインデックスを有する複数のサンプルを選択することを含み、ここでＫは前記データブロック中のＰＮシーケンスの数である請求項１記載の方法。
【請求項５】
前記第１のサブセットは、前記ＰＮシーケンスの反復率により相互に関して隔てられている複数のデータ周波数サンプルを具備している請求項１記載の方法。
【請求項６】
前記枝刈りは、データ周波数サンプルの前記第１のセットの間で補間することを含んでいる請求項１記載の方法。
【請求項７】
基準周波数サンプルの前記提供は、前記ＰＮシーケンスでＤＦＴ動作を行うことを含んでいる請求項１記載の方法。
【請求項８】
前記計算は、重み付けされた周波数サンプルの１セットを形成するために、前記データ周波数サンプルの前記第１のサブセットを、基準周波数サンプルの前記セットで乗算することを含んでいる請求項１記載の方法。
【請求項９】
前記計算は、前記第１の相関データシリーズを発生するために、重み付けされた周波数サンプルの前記セットで逆ＤＦＴを行うことを含んでいる請求項８記載の方法。
【請求項１０】
前記送信機は、ＧＳＰ周波数でＧＰＳ信号を送信する複数のＧＰＳ衛星を具備し、各ＧＰＳ衛星は特有のＰＮシーケンスを送信する請求項１記載の方法。
【請求項１１】
前記最終的な相関シリーズは、ＧＰＳ信号の存在を識別するためにサーチされ、ＧＰＳ信号の存在が識別されたならば、ＰＮコードの位相オフセットを決定し、前記受信機におけるＧＰＳ信号の到着時間を決定する請求項１記載の方法。
【請求項１２】
第２の残留周波数を仮説し、
データ周波数サンプルの第３のサブセットを提供するため、前記仮説された第２の残留周波数に応答して、データ周波数サンプルの前記第１のセットを枝刈りし、
データ周波数サンプルの前記第３のサブセットと前記基準周波数サンプルから、第３の相関シリーズを計算し、
少なくとも前記第３の相関シリーズを具備する第２の最終的な相関シリーズを計算し、
前記送信された信号と前記仮説された信号との間に一致された状態が生じるか否かを決定するため、前記第２の最終的な相関シリーズを検査することをさらに含んでいる請求項１記載の方法。
【請求項１３】
前記データブロックは、前記ＰＮシーケンスの約５乃至２０の反復範囲内のサイズを有する請求項１２記載の方法。
【請求項１４】
さらに、前記受信機の位置を決定するため、到着時間情報を使用することを含んでいる請求項１記載の方法。
【請求項１５】
複数の送信機のうちの１つから送信され、反復するＰＮシーケンスにより変調される波形を含んだ信号の処理方法において、
前記送信機のうちの１つおよびその搬送周波数に関連する信号を仮説し、
処理される前記信号の搬送周波数に近い周波数で受信される電磁エネルギから、前記反復するＰＮシーケンスの少なくとも２反復に等しい長さのデータのサブセットを抽出し、
前記データ周波数サンプルのサブセットを発生するため、前記仮説された搬送周波数に応答して、データの前記サブセットから計算される１セットのデータ周波数サンプルを枝刈りし、
前記仮説された信号に対応するデータ周波数サンプルの前記サブセットと基準周波数サンプルから決定される少なくとも１つの相関シリーズを入力として使用して、最終的な相関シリーズを計算し、
前記送信された信号と前記仮説された信号との間に一致された状態が生じるか否かを決定するため、前記最終的な相関シリーズを検査することを含んでいる方法。
【請求項１６】
複数の送信機のうちの１つから予め定められた周波数で送信される信号を受信する位置検出システムを含んでいる移動局であって、前記送信される信号は、信号を送信する送信機を特有に識別する周期的に反復するシーケンスを含んでいる移動局において、
予め定められた周波数の電磁エネルギを予め規定された時間期間だけ観察し、デジタル化する手段と、
前記複数の送信機のうちの１つを仮説し、前記仮説された送信機から送信される仮説された信号に対応する基準周波数サンプルの１セットを提供する手段と、
残留周波数を仮説する手段と、
前記周期的に反復するシーケンスの少なくとも２反復に等しい長さの前記デジタル化された電磁エネルギの第１の部分を選択し、それによってデータブロックを規定する手段と、
前記データブロックに応答して、データ周波数サンプルの１セットを計算する手段と、
前記データ周波数サンプルの周期的に隔てられたサブセットを提供するため、前記仮説された残留周波数に応答して、前記データ周波数サンプルを枝刈りする手段と、
前記データ周波数サンプルの前記サブセットと、前記基準周波数サンプルとから、第１の相関シリーズを計算する手段と、
少なくとも前記第１の相関シリーズを具備する最終的な相関シリーズを計算する手段と、
前記仮説された信号と、前記受信された信号との間に信号の一致状態が生じるか否かを識別するため、前記最終的な相関シリーズをサーチし、一致された状態が前記仮説された信号と、前記受信された信号との間で発見されたならば、タイミング情報を決定する手段とを具備している移動局。
【請求項１７】
前記周期的に隔てられたサブセットは、整数Ｋによって相互に関して隔てられているインデックスを有する複数のサンプルを具備し、ここでＫは前記データブロック中の前記周期的に反復するシーケンスの反復数である請求項１６記載の方法。
【請求項１８】
前記周期的に隔てられたサブセットは、前記周期的に反復するシーケンスの反復率により相互に関して隔てられている隣接するサンプルを有する複数のサンプルを具備している請求項１６記載の移動局。
【請求項１９】
前記枝刈り手段は、前記データ周波数サンプル間で補間する手段を含んでいる請求項１６記載の移動局。
【請求項２０】
前記移動局は前記基準周波数サンプルを記憶するためのメモリを具備している請求項１６記載の移動局。
【請求項２１】
最終的な相関シリーズを計算するための前記手段は、前記第１の部分とは異なる、前記デジタル化された電磁エネルギの第２の部分から計算された第２の相関シリーズに前記第１の相関シリーズを非コヒーレントで結合するための手段を含んでいる請求項１６記載の移動局。
【請求項２２】
前記第１の相関シリーズを計算するための前記手段は、重み付けされた周波数サンプルのセットを形成するため、前記データ周波数サンプルの前記第１のサブセットを基準周波数のサンプルの前記セットで乗算するための手段と、前記第１の相関シリーズを発生するため、重み付けされた周波数サンプルの前記セットで逆ＤＦＴを行う手段とを含んでいる請求項１６記載の移動局。
【請求項２３】
前記送信機はＧＰＳ周波数でＧＰＳ信号を送信する複数のＧＰＳ衛星を具備し、各ＧＰＳ衛星は特有の周期的に反復するシーケンスを送信する請求項１６記載の移動局。
【請求項２４】
前記データブロックは前記周期的に反復するシーケンスの整数回の反復に対応するサイズを有する請求項１６記載の移動局。
【請求項２５】
さらに、前記移動局の位置を決定するために前記タイミング情報を利用するＧＰＳ検出システムを具備している請求項１６記載の移動局。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公表番号】特表２００７−５１９９３６（Ｐ２００７−５１９９３６Ａ）
【公表日】平成１９年７月１９日（２００７．７．１９）
【国際特許分類】
【出願番号】特願２００６−５５１６３４（Ｐ２００６−５５１６３４）
【出願日】平成１７年１月２７日（２００５．１．２７）
【国際出願番号】ＰＣＴ／ＵＳ２００５／００３５４０
【国際公開番号】ＷＯ２００５／０７４１５３
【国際公開日】平成１７年８月１１日（２００５．８．１１）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
【公表日】平成１９年７月１９日（２００７．７．１９）
【国際特許分類】
【出願日】平成１７年１月２７日（２００５．１．２７）
【国際出願番号】ＰＣＴ／ＵＳ２００５／００３５４０
【国際公開番号】ＷＯ２００５／０７４１５３
【国際公開日】平成１７年８月１１日（２００５．８．１１）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
[ Back to top ]