(57)【特許請求の範囲】
【請求項１】
入力サンプルストリームと各2進ビット値が＋１または−1を表す複数の２進ビットを有する所与の２進符号間の相関を形成する整合フィルタであって、
あらゆる符号パターンを信号サンプルストリームの連続する信号サンプル群に適用して該信号サンプル群の異なる複数の組合せを形成する組合せ手段（２５）と、
前記適用した符号パターンと前記2進符号内の前記信号サンプル群に対応するビット群を比較して，組合せ手段（２５）によって形成された組合せの中の１つを選択する選択手段（２３，２５）と、
前記選択された組合せを既に計算済みの部分相関値に加えて，相関値を計算する計算手段（２１，２４）と、
を含む整合フィルタ。
【請求項２】
請求項１記載の整合フィルタであって、前記組合せ手段（２５）はグレイ符号順に異なる組合わせを形成する整合フィルタ。
【請求項３】
請求項１記載の整合フィルタであって、前記計算手段（２１，２５）が、累積部分相関値の組を記憶するメモリ（２１）と、累積部分相関値の対応する値と／から選択された組み合わせを加算／減算して最終的な相関値を得るまで新しい部分相関値の組を計算する加算器／減算器を含む整合フィルタ。
【請求項４】
請求項１記載の整合フィルタであって、前記組合せ手段が、２つの入力サンプルの和と差を計算するバタフライ回路を含む整合フィルタ。
【請求項５】
請求項４記載の整合フィルタであって、前記選択手段は２進符号の対応するビット群をもとに２つの所与の入力サンプルの和または差のどちらかを選択する整合フィルタ。
【請求項６】
請求項５記載の整合フィルタであって、前記計算手段は選択された和と差の連続するものを遅延させて加算して相関を生成する遅延加算回路を含む整合フィルタ。
【請求項７】
請求項６記載の整合フィルタであって、前記遅延加算回路が、２進符号内の対応するビットをもとに、選択された和と差に符号変更を選択的に適用する符号インバータを含む整合フィルタ。
【請求項８】
入力サンプルストリームと各2進ビット値が＋１または−1を表す複数の２進ビットを有する所与の２進符号の間の相関を形成する方法であって、
あらゆる符号パターンを信号サンプルストリームの連続する信号サンプル群に適用して該信号サンプル群の異なる複数の組合せを形成し、
前記適用した符号パターンと前記2進符号内の前記信号サンプル群に対応するビット群を比較して，異なる組合せの中の１つを選択し、
前記選択された組合せを既に計算済みの部分相関値に加えて，相関値を計算する、
段階を含む方法。
【請求項９】
請求項８記載の方法であって、異なる組合わせはグレイ符号順に形成される方法。
【請求項１０】
請求項８記載の方法であって、相関値を計算する前記段階が、累積部分相関値の組をメモリに記憶する段階と、最終的な相関値を得るまでメモリ内の累積部分相関値と／から選択された組み合わせを加算／減算する段階を含む方法。
【請求項１１】
請求項８記載の方法であって、入力サンプルストリーム内の入力サンプル群の異なる複数の組合せを形成する前記段階が、２つの連続する入力サンプルの和と差を計算する段階を含む方法。
【請求項１２】
請求項１１記載の方法であって、選択された組合せをもとに相関値を計算する前記段階は、入力サンプルの連続する群から選択された組む合わせを遅延させて加算して相関を生成する段階を含む方法。
【請求項１３】
請求項１２記載の方法であって、選択された組合せをもとに相関値を計算する前記段階は、２進符号内の対応するビット群をもとに、選択された和と差の符号を変更する段階をさらに含む方法。
【発明の詳細な説明】
【０００１】
（背景）
本発明は一般的に無線電話通信システムの受信機に関し、特に符号分割多元接続（ＣＤＭＡ）信号を受信する無線受信機に関する。
【０００２】
セルラー電話機産業は米国において世界の他の国と同様に商業的運用において驚くべき進展を遂げている。主要都市エリアにおける発展は予想を遥かに越えてシステム容量を越えつつある。この傾向が続けば、高速な成長の影響はまもなく最も小さい市場にさえ及ぶであろう。高品質サービスを維持し価格上昇を回避するだけでなく、このような増大する容量を満たすための革新的解決策が必要とされている。
【０００３】
世界中で、セルラーシステムにおける１つの重要なステップはアナログ伝送からデジタル伝送への変化である。同等に重要なことは次世代セルラー技術を実現するための有効なデジタル伝送方式の選択である。さらに、快適に携行して家庭、事務所、街路、車等で発呼および受呼することができる低コスト、ポケットサイズ、コードレス電話機を利用する第１世代パーソナル通信網（ＰＣＮ）が次世代デジタルセルラーシステムインフラストラクチュアおよびセルラー周波数を使用するセルラーキャリアにより提供されるものと広く信じられている。これらの新しいシステムに要求される重要な特徴はトラフィック容量の増大である。
【０００４】
現在、チャネルアクセスは周波数分割多元接続（ＦＤＭＡ）、時数分割多元接続（ＴＤＭＡ）および符号分割多元接続（ＣＤＭＡ）方法により達成されている。ＦＤＭＡシステムでは、通信チャネルは単一無線周波数帯であり、その中に信号の送信電力が集中される。隣接チャネルとの干渉はフィルタの指定された周波数帯内の信号エネルギしか通さないバンドパスフィルタを使用して制限される。したがって、各チャネルに異なる周波数が割り当てられると、システム容量はチャネル再利用により課される制限だけでなく利用可能な周波数によっても制限される。
【０００５】
ＴＤＭＡシステムでは、チャネルは同じ周波数にわたる周期的な時間間隔列内のタイムスロットにより構成される。タイムスロットの各周期はフレームと呼ばれる。所与の信号のエネルギはこれらのタイムスロットの１つに閉じ込められる。隣接チャネル干渉はタイムゲートや適切な時間に受信された信号エネルギしか通さない他の同期化素子を使用して制限される。このようにして、異なる相対信号強度レベルによる干渉問題が低減される。
【０００６】
ＴＤＭＡシステムの容量は送信信号をより短いタイムスロット内へ圧縮して増大される。その結果、情報も高速バーストレートで送信しなければならず、スペクトル占有量が比例的に増大する。
【０００７】
ＦＤＭＡもしくはＴＤＭＡシステムもしくはハイブリッドＦＤＭＡ／ＴＤＭＡシステムでは、２つの潜在的な干渉信号が同じ周波数を同時に占有しないことが目的である。それに対して、ＣＤＭＡシステムでは時間と周波数の両方で信号は重なり合うことができる。したがって、全てのＣＤＭＡ信号が同じ周波数スペクトルを共用する。周波数および時間の両方のドメインにおいて、多元接続信号が重なり合う。ＣＤＭＡ通信のさまざまな特徴が、例えば、ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｖｅｈｉｃｕｌａｒ Ｔｅｃｈｎｏｌｏｇｙ， Ｍａｙ １９９１のギルハウセン、ヤコブ、ビタビ、ウィーバおよびホイートリの論文“Ｏｎ ｔｈｅ Ｃａｐａｃｉｔｙ ｏｆ ａ Ｃｅｌｌｕｌａｒ ＣＤＭＡ Ｓｙｓｔｅｍ”に記載されている。
【０００８】
典型的なＣＤＭＡシステムでは、送信される情報データストリームは擬似ランダムノイズ符号（ＰＮｃｏｄｅ）発生器により発生される遥かに高ビットレートのデータストリーム上に印加される。情報データストリームおよび高ビットレートデータストリームは典型的に一緒に乗算される。高ビットレート信号と低ビットレートデータストリームのこの結合は情報データストリーム信号の符号化すなわち拡散と呼ばれる。各情報データストリームすなわちチャネルに一意的な拡散符号が割り当てられる。複数の符号化情報信号が無線周波数キャリアにより送信され、受信機においてコンポジット信号として一緒に受信される。各符号化信号は周波数と時間の両方において、ノイズ関連信号だけでなく、他の全ての符号化信号と重なり合う。コンポジット信号を一意的な拡散符号の１つと相関させることにより、対応する情報信号が分離され復号される。
【０００９】
ＣＤＭＡ通信技術に関連するいくつかの利点がある。ＣＤＭＡベースセルラーシステムの容量限界は、改善された符号化利得／変調密度、音声アクティビティゲーティング、各セル内での同じスペクトルのセクター化および再利用等のワイドバンドＣＤＭＡシステムの特性により、既存のアナログ技術のそれの２０倍までにも突出している。ＣＤＭＡは実質的にマルチパス干渉を受けず、フェージングおよび空電を解消して都市エリアにおける性能を改善する。高ビットレートエンコーダによるＣＤＭＡ音声送信は優れた実際的な音声品質を保証する。また、ＣＤＭＡは可変データレートを提供し多くの異なる等級の音声品質を提供することができる。ＣＤＭＡのスクランブル信号フォーマットによりクロストークが解消されかつ盗聴や呼の追跡が非常に困難で費用のかかるものとなり、発呼者に対する優れたプライバシーおよびａｉｒ ｔｉｍｅ ｆｒａｕｄに対する優れた免疫性が保証される。ＣＤＭＡすなわち“スペクトル拡散”概念に従った通信システムでは、情報データストリームの周波数スペクトルはデータ信号のそれとは非相関の符号を使用して拡散される。符号は各ユーザに対しても一意的である。それが所期の送信機の符号に関する知識をもつ受信機が所望の信号を選択できる理由である。
【００１０】
いくつかの異なる信号拡散技術がある。最も普及している２つの方法はＤｉｒｅｃｔ−Ｓｅｑｕｅｎｃｅ（ＤＳ）およびＦｒｅｑｕｅｎｃｙ−Ｈｏｐｐｉｎｇ（ＦＨ）であり、両方共従来技術でよく知られている。ＤＳ技術に従って、データ信号には擬似ランダムノイズ符号（ＰＮｃｏｄｅ）と呼ばれる非相関符号が乗じられる。ＰＮｃｏｄｅは−１または１（有極）あるいは０または１（無極）の値をとりノイズ状特性を有する一連のチップ（ビット）である。ＰＮｃｏｄｅの１つの生成方法は少なくとも１つのシフトレジスタによるものである。このようなシフトレジスタの長さがＮであれば、周期ＮＤＳは等式ＮＤＳ＝２ｎ−１で与えられる。
【００１１】
ＣＤＭＡシステムの受信機では、受信信号に再度同じ（同期化された）ＰＮｃｏｄｅが乗じられる。符号は＋１および−１により構成されるため、この操作により信号から符号が除去されてオリジナルデータ信号が残される。すなわち、逆拡散操作は拡散操作と同じである。
【００１２】
図１は従来の相関器のブロック図であり、それは受信した最終Ｍ信号サンプルとＭ−ビット符号語間の相関を計算するのに使用される。Ｍ−素子遅延線１０が受信信号サンプルを格納し、Ｍ段の各々を介してそれらを逐次シフトする。したがって、遅延線メモリ素子は受信した最終Ｍ信号サンプル値を含んでいる。新しい各サンプルがシフトインされ１つの古いサンプルがシフトアウトされた後で、Ｍサンプル値は遅延線からＭ符号変更器１２へ読み出され、そこで相関が計算される所定符号のビットｂ．．．ｂに従ってＭサンプル値に＋１もしくは−１が乗じられる。符号変更された値は次に加算器１３により加算されて相関結果が得られる。
【００１３】
一般的に、６４個のサンプルからなる６４素子ベクトルＡ＝（ａ１，ａ２，．．．ａ６４）をもう１つの６４素子ベクトルＣ＝（ｃ１，ｃ２，．．．ｃ６４）と相関させるプロセスには内積Ａ*Ｃ＝ａ１*ｃ１＋ａ２*ｃ２＋．．．ａ６４*ｃ６４の形成が含まれる。一方のベクトル（例えば、Ｃ）の素子が２進値（数学的に＋１または−１）しか含まない場合には、ａ１*ｃ１等の積は±ａ１に単純化されるが、６４の値の加算プロセス±ａ１±ａ２．．．±ａ６４は、新しいサンプル値“ａ”が受信されるたびに実施しなければならない場合にはまだ相当な計算量である。前例では、ベクトル長（６４）は単なる説明の目的で使用されるにすぎない。当業者ならば任意長のベクトルを使用できることがお判りであろう。
【００１４】
従来技術は図１に示す相関器の多くのバリエーションを含んでいる。例えば、信号サンプルはマルチビット量ではなくシングルビットすなわち＋１または−１だけの“ハードリミテッド”量とすることができる。そこで使用される符号変更器は典型的には単純なＸＯＲゲートである。Ｍ個のシングルビット値の加算を行う場合、加算器１３は２つづシングルビット値を加えて，Ｍ／２個の２ビット値を得る。次に，Ｍ／４個の2ビット加算器が２つづつ２ビット値を加えてＭ／４個の３ビット値を得て、以下同様に加算を行う。“加算器ツリー”として知られるこのような構造は入力値がマルチビット値であるときよりもシングルビット値である時のほうが単純となる。
【００１５】
シングルビット値信号サンプルに対して、加算器ツリーはＭ値を走査し、＋１に遭遇すればカウントアップし−１に遭遇すればカウントダウンするアップダウンカウンタにより置換することができる。同様に、マルチビット信号サンプルに対して、並列加算器ツリーは遅延線メモリから順次Ｍ値の各々を抽出してアキュムレータに加算するシーケンシャル加算器により置換することができる。後者の場合、利用される論理は並列加算器の場合のＭ倍の速さで動作できなければならない。したがって、相関器の全体速度と論理の複雑さとの間にトレードオフがある。それにもかかわらず、前記した従来技術の相関器の各バリエーションにおいて、新しい各信号サンプルが受信された後でＭ値を新たに結合する必要がある。
【００１６】
従来の整合フィルタすなわち相関器のもう１つの例を図２に示す。受信信号はＦｃサンプル／秒のレートでサンプルされ、サンプルはＸで示す乗算器の入力へ逐次入る。図２に（６４の長さを有する整合フィルタに対して）Ｃ１，Ｃ２，Ｃ３．．．Ｃ６４として示すように、６４の乗算器の各々がＰＮｃｏｄｅの１ビットをその第２の入力値として有する。この従来の整合フィルタでは、最左乗算器内で電流入力サンプルａ（ｉ）にＣ１が乗じられ、乗算器出力Ｃ１・ａ（ｉ）が１サンプル遅延素子Ｄ１へ与えられる。この値は全ての乗算器にａ（ｉ＋１）が入力される次のサンプル周期において遅延素子Ｄ１から生じる。遅延素子Ｄ１から生じる値Ｃ１・ａ（ｉ）が第１の加算器の第１の入力へ入ると、Ｃ２が入力サンプルａ（ｉ＋１）に乗じられて値Ｃ２・ａ（ｉ＋１）が得られ、この積は第１の加算器の第２の入力へ加えられる。第１の加算器の出力はＣ１・ａ（ｉ）＋Ｃ２・ａ（ｉ＋１）となり遅延素子Ｄ２へ入る。この値はａ（ｉ＋２）が乗算器へ入力される次のサンプル周期にＤ２から生じる。したがって、Ｄ２からの出力はＣ３・ａ（ｉ＋２）へ加えられその結果が遅延素子Ｄ４へ入力され、以下同様である。したがって、６４サンプルが入力された後で最右加算器から下記の値が生じ、
Ｃ１・ａ（ｉ）＋Ｃ２・ａ（ｉ＋１）＋Ｃ３・ａ（ｉ＋２）＋．．． ＋Ｃ６４・ａ（ｉ＋６３）
それは値Ｃ１．．．Ｃ６４と信号サンプルａ（ｉ）．．．ａ（ｉ＋６３）間の６４サンプル相関であることがお判りであろう。
【００１７】
連続する各信号サンプルが入力されると、新しい６４ポイント相関が信号サンプル間で連続的に計算される。
ａ（ｉ＋１）．．．ａ（ｉ＋６４）
ａ（ｉ＋２）．．．ａ（ｉ＋６５）
得られる相関は係数Ｃ１．．．Ｃ６４とスライディングウィンドウ６４サンプル幅に従って選択された６４信号サンプルとの組合せに見える。したがって、この整合フィルタに対するもう１つの用語は“スライディング相関器”である。
【００１８】
図１の装置は各サンプルクロック周期において６４の乗算および６４の加算を実施する。それは、特に電源がバッテリ等の可般型電源である場合に、大量の電力を消費する。したがって、計算を最小限に抑えて消費電力を低減する整合フィルタが必要とされている。
【００１９】
（概要）
連続する各相関値を得るために実施される乗算および／もしくは加算数を減少することが本発明の目的である。乗算および加算数を減少することにより電源からの消費電力が低減され、ＣＤＭＡ信号を受信するセルラー電話機等のスライディング相関器すなわち整合フィルタを使用するバッテリ操作装置のバッテリ寿命が延びる。
【００２０】
典型的な実施例では、整合フィルタはその入力に信号サンプルのストリームを受信し、サンプルレートクロックの連続する各周期に１つの新しいサンプルが受信される。新しい各サンプル入力に対して、完全な相関値が出力される。この値は，最新のＮ個の入力サンプルと，Ｎ個のデジタルシンボルを含むPNcode間の相関である。相関器は、所与のPNcodeとは独立した限定数の連続入力サンプルの予組合せを形成することにより、相関値当たりＮ乗算およびＮ加算演算よりも著しく少数の演算しか必要としないように新しい各サンプルクロック周期において連続的な相関を計算する。
【００２１】
（詳細な説明）
典型的な実施例では、ＤＳ ＣＤＭＡシステムに使用する整合フィルタはあるサンプルクロックレートで入力サンプル信号を受信しその予組合せを形成する。整合フィルタは、所与のＰＮｃｏｄｅと共に、予組合せを使用して受信入力サンプル信号を復号しそのサンプルクロックレートで１つの相関値出力を作り出す。整合フィルタはより少ない論理演算を使用して従来の整合フィルタと同じ出力を生じ、したがってより非常に省電力とされてバッテリ寿命が延びる。
【００２２】
図３は、受信信号サンプルと相関させることができる、1５ビット符号の重なり合う連続シフトの構成を示す図表である。図３について、複数の受信信号サンプルには１からＩまでの番号が付される（横方向に）。信号サンプル番号の下に１５の受信サンプルが相関される1５ビット符号語の異なるシフトが示されている。最左縦方向番号は実施される相関数を示す。例えば、第１相関は第１行の符号語を第1,2,3...F信号サンプルと相関させなければならない。
【００２３】
図３は第Ｆサンプルが受信される直前の構成を示す。未受信サンプルは太字印刷で強調され既受信サンプルの右に配置される。未受信サンプル値と相関される符号語のビット間に分割線２が示されており、受信サンプルと既に相関されているビットは分割線の左に示されている。メモリ素子１からＥは、それぞれ、１からＥ行の符号語と受信サンプルの未完成な相関値に匹敵する部分結果（部分相関）を含んでいる。図３は第１相関を完了するために第Ｆサンプルを受信しなければならないことを示している。第Ｆ，Ｇ，Ｈ，Ｉサンプルの受信により第１，２，３および４相関を完了することができ、Ｆ，Ｇ，ＨおよびＩ行との相関を少なくとも開始させることができる。４つの新しい受信サンプルと符号語の部分相関である異なる組合せとメモリ素子５からＥに含まれる部分相関とを累算することにより、第Ｆ，Ｇ，Ｈ，Ｉサンプルの受信後に既に開始された第５からＥ行の相関計算を右へさらに４位置続けることができる。
【００２４】
第４相関を完了するのに必要な４つの新しいサンプルＳ（Ｆ），Ｓ（Ｇ），Ｓ（Ｈ），Ｓ（Ｉ）の組合せは−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）＋Ｓ（Ｉ）である。この組合せの符号は４行の４つの残りのビット１０１０に対応する。“１”はマイナス符号を示し、“０”はプラス符号を示す。５行からＥ行に対する相関の累算を継続するために他の符号パターンを使用する他の組合せが必要であり、４行からＥ行に対して図３の四角枠内の上１１行に相当する計１１の組合せが必要である。
【００２５】
グレイ符号順に１６の組合せ全てを計算するのに効率的方法を使用できるため、必要な組合せが１６よりも少ない場合であっても、合計１６のＳ（Ｆ），Ｓ（Ｇ），Ｓ（Ｈ）およびＳ（Ｉ）の可能な全ての組合せを計算する方法が使用される。さらに、ビットパターン１１００で示される符号を有する組合せは００１１で示される符号を有する組合せの符号を反転した値である。したがって、１６の組合せの半分しか形成する必要がなく、他方の半分は形成した半分の符号反転値である。そのため、８つの組合せが符号パターンのグレイ符号順で計算される場合には、第１の値の形成後新しい各値に対して１回の加算もしくは減算を使用するだけで計算される８つの組合せを形成することができる。後述するように、この順序では連続するパターン間で１個所の符号変更しか生じない。
【００２６】
例えば、４つの新しい値（４つの演算としてカウントされる）の和を必要とするパターン００００で開始して、組合せＣに対するグレイ符号順計算は次のように進められる。
0003585441.tif 000002
このプロセスは、第１の値を形成するための４つの演算および前記したグレイ符号順で後続組合せを形成するための１つの演算（前の組合せから受信したサンプルの２回の加算もしくは減算）を使用して、８つの組合せ全ての計算を完了する。１位置の右シフトが２の乗算と同等である２進算術の使用が想定されるため、サンプル値を２でスケーリングすることはここでは演算としてカウントされない。
【００２７】
前記した実施例は４つの値よりも多い全ての組合せの形成に拡張することができる。任意数の値に対する計算のグレイ符号順序付けは、前記したように、１ビット位置しか違わない連続２進符号を特徴とする。
【００２８】
合計１１の演算を使用して形成された前記組合せは次のように信号サンプル４からＥを表わす格納された値と結合され、Ｃ（５）が格納された値４から減算されて第４相関を完了し、Ｃ（２）が格納された値５から減算され、Ｃ（６）が格納された値６に加算され、Ｃ（３）が格納された値７に加算され、Ｃ（６）が格納された値８から減算され、Ｃ（４）が格納された値９に加算され、Ｃ（２）が格納された値Ａに加算され、Ｃ（１）が格納された値Ｂに加算され、Ｃ（７）が格納された値Ｃに加算され、Ｃ（３）が格納された値Ｄから減算され、Ｃ（１）が格納された値Ｅから減算され、Ｃ（０）が格納された値Ｆから減算される。前記したように、このプロセスには１２の演算が付加されている。
【００２９】
次に、第１行に対応する相関を完了するために信号サンプルＳ（Ｆ）が格納された値１から減算される。同様に、信号サンプルＳ（Ｆ）は格納された値２に加算され、信号サンプルＳ（Ｇ）が格納された値２から減算されて第２相関を完了する。また、−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）の信号サンプル組合せが格納された値３と結合されて第３相関を完了する。この点において、このプロセスはさらに１＋２＋３＝６演算を行っている。しかしながら、組合せ−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）±Ｓ（Ｉ）は既に計算されており、寄与±Ｓ（Ｉ）を除去するのに１演算しか必要としないことに注目すれば、この数を減少することができる。したがって、第３相関は３演算ではなく２演算で完了することができる。
【００３０】
さらによいことに、下記の組合せの形成で開始することにより、任意の点においてグレイ符号順で組合せ計算を開始することができる。
−Ｓ（Ｆ）＋Ｓ（Ｇ）；
−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）；および
−Ｓ（Ｆ）＋Ｓ（Ｇ）−Ｓ（Ｈ）＋Ｓ（Ｉ）
第３相関を完了するのに必要な３つの値の組合せが第２のステップで形成されることをお判り願いたい。第３ステップの後で、他方の組合せがグレイ符号順で形成される。
１０１０（前記第３ステップで形成された）
１０１１
１００１
１０００
１１００
１１０１
１１１１
１１１０
それは僅か７つの付加加算演算しか行わない。この点において、次式に従って拡張された総計算量に対して４つの相関が完了されていることをお判り願いたい（前例ではＮ＝４かつＭ＝１５）。
（１）Ｎ値の可能な２Ｎの符号組合せ全てを形成するＮ＋（２（ｎ−１））−１）；
（２）第１から（Ｎ−１）相関を完了する１＋２＋３．．．（Ｎ−１）＝０．５Ｎ（Ｎ−１）演算；および
（３）第Ｎ相関を完了してＭ−Ｎの他の相関を継続するＭ−Ｎ＋１演算。さらに３，２および１の値（信号サンプル１，２および３の値）の組合せを形成しそれらを完了した相関１，２および３により空にされた格納位置へ加算して、同じメモリ位置を巡回的に再使用することにより第Ｇ，ＨおよびＩ相関が開始される。このプロセスも０．５Ｎ（Ｎ−１）演算を必要とする。
【００３１】
これらの演算を全て加算して、新しいＮ信号サンプルの各受信後に下記の演算を使用してＮの完了した相関が形成されることが確認される。
０．５Ｎ（Ｎ−１）＋Ｍ−Ｎ＋１＋０．５Ｎ（Ｎ−１）＋Ｎ＋２（Ｎ−１）−１
Ｍ＋２（ｎ−１）＋Ｎ（Ｎ−１）相関当たり演算、もしくは
（Ｍ＋２（Ｎ−１）＋Ｎ（Ｎ−１））／Ｎ相関当たり演算。
【００３２】
Ｎ／２値よりも大きい組合せはＮ値全部の既に形成された組合せの１つからＮ／２値よりも小さい組合せを減算することにより形成できることに注目して、開始および終了三角フィレット（ｆｉｌｌｅｔ）をより効率的に計算することによりこのプロセスを幾分簡約することができる。したがって、フィレットの計算はＮ（Ｎ−１）演算ではなくおよそ０．５Ｎ（Ｎ−１）演算で済む。
【００３３】
次の例は前記した相関方法を使用して得られる計算量の節減を示す。この例は受信信号の前シフトとＭ＝１０２４ビット符号語間の相関の計算を示す。新しいサンプルＮの異なる値により得られる（１０２４ポイント）相関当たり演算の総数は次のように表わすことができる。
0003585441.tif 000003
Ｎ＝８もしくは９の値により１０２４ポイント相関を実施するのに必要な演算数は最適に減少され（およそ１５１演算）、その結果従来技術に比べて１／７の節減となる。前記した方法を使用すれば、従来技術の１５１ビット相関器と同じくらい魅力的な速度／電力／コストトレードオフを有する１０２４ビット相関器を作り出すことができ、速度、電力もしくはコストに関して同等なコストでより長い相関計算を達成することができる。このトレードオフはより高い通信装置性能と解釈される。
【００３４】
さらに、受信データサンプルの夥しいシフトを２つ以上の符号語と相関させなければならない場合には、さらなる節減を実現することができる。前記したように、Ｎデータサンプルの全ての組合せの計算にはそれらをグレイ符号順で実施して２（Ｎ−１）＋Ｎ−１演算を必要とする。次に、これらの組合せのＭ−Ｎ＋１が第１の符号語と相関させるために第１セットの記憶位置へ加算され、かつ第２の符号語と相関させるために第２セットの記憶位置へ加算される。前記したように、各符号語とのＮ相関を開始して完了するために加算しなければならない値の三角フィレットの計算には符号語当たりせいぜいＮ（Ｎ−１）演算しか必要とせず、Ｌ符号語とのＮ相関を完了するための総計算量は
Ｌ（Ｍ−Ｎ＋１）＋２（Ｎ−１）＋Ｎ−１＋ＬＮ（Ｎ−１）＝ＬＭ＋Ｌ（Ｎ−１）２＋２（Ｎ−１）＋（Ｎ−１）
演算となる。したがって、相関当たり総演算は次式で表わすことができる。
（ＬＭ＋Ｌ（Ｎ−１）２＋２（Ｎ−１）＋（Ｎ−１））／ＬＭ
【００３５】
例えば、スライディング１０２４信号−サンプルセグメントを６つの異なる１０２４ビット符号と相関させるのに下記の計算量が必要である。
0003585441.tif 000004
それはＮ＝１１が最も効率的な選択であることを示している。
【００３６】
前記した方法は任意の符号語に対してうまく使用することができる。特定の符号語との相関については、前記した原理に従ってより効率的な相関器を考案することができる。例えば、Ｎがｌｏｇ２（Ｍ）よりも大きく選択されるものとすると、必要とするものよりも多くのＮ信号サンプル値の組合せが計算される。しかしながら、それらは信号サンプル値当たり１演算しか必要としない効率的なグレイ符号順で計算される。ある組合せの計算を省くことにより、必要な組合せしか計算しないことが望ましいが、組合せ当たり１つの追加演算だけで必要な全ての組合せが得られるか確かではなくなる。実際上、ある組合せの計算を省くとばらばらに分離した組合せ群が作り出される。したがって、いずれの場合にも必要な組合せセットの各構成要素の配置を調べてもう１つの構成要素からそこへ達成するのにどれだけ多くの演算が必要であるかを確認する必要がある。演算数は信号サンプルを組み合わせるのに使用すべき符号（プラスもしくはマイナス）を示す対応するビットパターン間のハミング距離に等しい。計算されるセット内の各Ｎビット部分符号から他の各Ｎビット部分符号までの全ハミング距離のセットである距離構造が与えられると、最小計算量に対してそれら全てを計算するための最適順序は可能な全てのパスをテストするビタビアルゴリズムを使用して決定することができる。特定の符号についてＮ信号サンプルの必要な組合せを計算するための演算数は、任意の符号の一般的ケースに対して想定された、値２（Ｎ−１）＋Ｎ−１よりも小さいと判ることがある。そうであれば、前記した原理に従って、これら特定の符号に対してより効率的な相関器を作り出すことができる。
【００３７】
あるいは、効率的な相関器を使用できるように符号を特別に定式化することができる。例えば、このような符号は第１の組合せの後の付加組合せ当たり１つの演算しか使わずに信号組合せを計算できるように、Ｎビットの全ての重なり合うシフトが隣接Ｎビット符号の隣接セットを形成する（ハミング距離感覚で）特性を有する任意のＭビット符号とすることができる。さらに、隣接セット内の符号の半分は他方の半分の補数でなければならず、補組合せは他方の負数であるため、その計算を不要とされる。
【００３８】
図４は典型的な相関器１８の略ブロック図である。典型的な相関器１８はタイミングコントローラ２０を含み、それは信号サンプルクロックを発生することにより新しい信号サンプルの入力を制御する。タイミングコントローラ２０により制御される演算のシーケンスはＮサンプルクロックサイクルごとに繰返す。Ｎサンプルクロックサイクルごとに、タイミングコントローラ２０は新しいＮサンプル値（本例ではＮ＝４）の入力および加減算器（モディファイア（ｍｏｄｉｆｉｅｒ））２４を使用したメモリ２１内のＮ位置からのそれらの加減算を制御する。このような各加減算は、メモリ位置に格納された値が予め加減算された値の累算を表わすように、メモリリード、モディファイおよびリライトサイクルを含む。Ｎ入力サンプルの１つが加減算されるか否かは信号が相関される符号語の最初もしくは最後のＮビットの１つによって決まる。必要な符号パターンが論理回路２３をマッピングすることにより発生され、それは符号に従ってタイミングコントローラ２０の制御下で異なる時間にモディファイア２４へ正しい加減算コマンドを発生するように構成される。メモリ２１はＭの部分完了相関を保持する巡回バァッファとして利用される。
【００３９】
完了すべき次の相関はメモリ位置“ｋ”におけるものであり、そこでは“ｋ”に対するアドレスがアドレスオフセットレジスタ２２内に維持される。アドレス“ｋ”における部分相関はＮ素子ラッチ２６内に維持されたＮの予め入力したサンプルのＮサンプル組合せを加算して完了される。セレクタ２５は、メモリ位置“ｋ−Ｎ”に予め格納されているＮサンプル組合せで開始して、ラッチ２６内に維持されたＮの予め入力したサンプルの２（Ｎ−１）（すなわち、Ｎ＝４であれば８）組合せを計算してグレイ符号順で格納するように機能する論理を含んでいる。セレクタ２５は、マッピング論理２３からのＮ−１選択線の制御下で、相関“ｋ”を完了するのに必要なこれらの組合せの中の選択された１つを出力する。同時に、マッピング論理２３は組合せが加算されるか減算されるか（すなわち、加算の前に符号が反転されたか否か）に応じて加減算コマンドをモディファイア２４へ出力する。
【００４０】
次に、タイミングコントローラ２０は、出力ゲート２８が完了したばかりの相関“ｋ”値を出力に接続できるようにすることにより、完了したばかりの相関“ｋ”を出力しメモリ位置“ｋ”にゼロ値が書き込まれるように置換して、メモリ位置“ｋ”をゼロにクリアする。次に、タイミングコントローラ２０は加減算器２４へ通される最終入力サンプルを入力シフトレジスタ２７から選択するようにセレクタ２５を制御し、同時に新しい入力サンプルを加減算することにより変更されるメモリ位置ｋ，ｋ＋１，ｋ＋２，．．．ｋ＋１−Ｎを逐次選択するようにマッピング論理回路２３を制御する。マッピング論理回路２３も、符号語ビットによって決まる予め格納された符号パターンに従って、Ｎメモリ位置の各々に対する加減算を制御する。
【００４１】
例えば、符号語の最初の４ビットが１１０１であり、最後の４ビットが１０１０であれば、マッピング論理２３によりレジスタ２７への４つの新しいサンプル入力の内の第１のサンプルの減算（第１のビット位置に“１”（＝’−‘）を有する符号語に対応する）、位置ｋ＋１への加算（“０”（＝’＋’）である最終符号語に対応する）、位置ｋ＋２からの減算（“１”である最後から２番目の符号語に対応する）、および位置ｋ＋３への加算（“０”である最後から３番目の符号語ビットに対応する）が行われる。次の４つのサンプルの中の第２のサンプルがレジスタ２７へ入力されると、マッピング論理２３はメモリ位置“ｋ”に対する“−“符号（“１”である符号語の第２ビットに対応する）、位置ｋ＋１に対する“−”符号（“１”である第１の符号語ビットに対応する）、位置ｋ＋２に対する“＋”符号（“０”である符号語の最終ビットに対応する）、および位置ｋ＋３に対する“−”符号（“１”である符号語の最後から２番目のビットに対応する）を発生し、以下同様である。下記の図表は前記したパターンを理解するのを助ける。
ｋ      １１０１
ｋ＋１    ０１１０
ｋ＋２    １０１１
ｋ＋３    ０１０１
前記したアンダーラインビットは新しい相関を開始するためのサンプルの符号を決定する符号語の第１ビットであり、それは非アンダーラインビット（相関される符号語の最終ビット）を符号として使用して完了した相関により空とされた同じメモリ位置内に形成される。相関メモリ位置は相関を完了する最終非アンダーラインビットおよび同じ位置内で新しい相関を開始する第１のアンダーラインビットを使用する間にゼロへクリアされ、それは前記したように適切な時間に出力ゲート２８をイネーブルするタイミングコントローラ２０により実施される。
【００４２】
Ｎの新しいサンプルを処理してＮの相関を完了しＮの新しい相関を開始することとインターレースして、タイミングコントローラはセレクターに格納された前のＮサンプル組合せのメモリ２１他のＭ−Ｎ位置に対する加減算を制御する。サンプル周期当たり（Ｍ−Ｎ）／Ｎ＝Ｍ／Ｎ−１位置を更新することにり、この計算はＮの新しいサンプル周期にわたって多少とも均一に拡散することができる。ｉ＝Ｎで開始してＭ−Ｎ位置が更新されるまでｉ＝Ｍ−１を１だけ増加することにより、タイミングコントローラ２０はアドレスレジスタ２２に格納されたベースアドレス“ｋ”への増分“ｉ”をマッピング論理２３に与える。マッピング論理２３モジュロ−Ｍは増分“ｉ”をベースアドレス“ｋ”へ加えて更新すべきメモリアドレス位置を得る。
【００４３】
タイミングコントローラ２０により与えられる増分“ｉ”は、マッピング論理２３がセレクター２５により選択されるＮサンプル組合せを決定して、その組合せを反転すべきか否かを決定する（モディファイア２４に“＋”もしくは“−”符号を与える事によって）のにも使用される。特定メモリ位置の内容と結合すべき組合せの指標（“ｉ”の値）は、例としてＮ＝４の値が使用されている図３を見れば容易に判るように、符号語ビットによって決まる。４ビットセグメントの括弧付き列は各行の部分相関を更新するために加算すべき組合せを示す。組合せがこれらのビットパターンの補数に対応するセレクター２５内に格納される場合には、モディファイア２４へマイナス符号が与えられるのと同時に補組合せが選択され、そうでなければ、正しい組合せ（利用できれば）が“＋”符号で使用される。
【００４４】
セレクター２５のＮ−１選択制御線入力への増分“ｉ”のマッピング、およびモディファイア２４に対する＋／−の選択は、例えば、メモリエリア内にＭ−Ｎ，Ｎ−ビット制御信号を格納して達成することができる。相関符号語が選択されたり変更した場合には、このメモリエリア内に適切な値がロードされる。また、メモリエリアは開始および終了三角フィレットの情報を制御するのに必要なＮ×Ｎ符号ビットを含むように拡張することができ、合計Ｍ×Ｎビットのメモリとなる。
【００４５】
あるいは、固定相関符号に対して、リードオンリーメモリ（ＲＯＭ）にこの情報をプログラムすることができ、場合によっては、ハードワイヤード論理を有する増分“ｉ”のビットをモディファイア２４およびセレクター２５へのＮの選択および選択信号へ変換するほうが効率的である。前記したものだけでなく、これら全ての可能性がここで考慮される。
【００４６】
次に、図５にＮ＝４の値に対するステップの典型的なタイミングシーケンスを示す。シーケンスのステップ１ａにおいて、アドレス“ｋ”における予め完了した相関がメモリ位置から出力され、その位置がゼロとされる。ステップ１ｂにおいて、最初の４つの新しい信号サンプルが入力され、アドレス“ｋ”を含むアドレスオフセットレジスタ２２により決定される、メモリアドレスｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加減算される。加算するか減算するかはマッピング論理２３の内容によって決まる。
【００４７】
ステップ２ａにおいて、完了した相関がメモリ位置ｋ＋Ｉから出力され、メモリ位置ｋ＋１はゼロとされる。ステップ２ｂにおいて、第２の信号サンプルがメモリ位置ｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加減算される。
【００４８】
ステップ３ａにおいて、完了した相関がメモリ位置ｋ＋２から出力され、メモリ位置ｋ＋２はゼロとされる。ステップ３ｂにおいて、第３の信号サンプルがメモリ位置ｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加減算される。
【００４９】
ステップ４ａにおいて、完了した相関がメモリ位置ｋ＋３から出力され、メモリ位置ｋ＋３はゼロとされる。ステップ４ｂにおいて、第４の信号サンプルがメモリ位置ｋ，ｋ＋１，ｋ＋２およびｋ＋３に対して加減算される。ステップ４ｃにおいて、メモリアドレス“ｋ”内の４サンプル組合せで開始して、他の２（Ｎ−１）−１（すなわち、Ｎ＝４であるここでは７）の４サンプル組合せがグレイ符号順で計算される。ステップ４ｄにおいて、ステップ４ｃで計算された組合せの中の選択された１つが残りのメモリ位置ｋ＋４，ｋ＋６，．．．ｋ＋Ｍ−１の各々の内容に加算される。このような各メモリ位置に対して、その位置に加算すべく選択される組合せは符号語の特定の選択に対して予め定められている。ステップ４ｅにおいて、アドレスｋが４だけ増分され（モジュロ−Ｍ）、シーケンスはステップ１ａから繰り返される。
【００５０】
ステップ４ｂの完了後、メモリ位置“ｋ”は符号語の最初の４ビットに対応する符号を有する４つの信号値の組合せを含む。この組合せは、各負数と共に４つの信号サンプルの１６の可能な符号組合せを含む、合計８つの組合せの中の他の７つをステップ４ｃにおいて結合するための開始点として使用される。これらの組合せの中の１つはそれをメモリ位置ｋ＋４の内容へ加算することにより相関ｋ＋４を完了させる必要がある。一般的に、この値が計算される順序は信号が相関される符号によって決まり、計算すべき最終値とすることができる。したがって、相関ｋ＋４（すなわち、ｋの増分値）を完了するのに必要な組合せを時間内に確実に得るために、ステップ４ａ−４ｅは１サンプル周期内に完了する必要がある。このように完了した相関は次のサイクルのステップ１ａにおける出力である。ステップ４ｅおよび４ｄは逆にすることができる（すなわち、ステップ４ｂにおいて最初にｋを４だけ増分することができる）が、アドレスｋ＋４，ｋ＋５．．．ｋ＋Ｍ−１はステップ４ｅに対するｋ，ｋ＋１，ｋ＋２．．．ｋ＋Ｍ−５として新しいｋ値で換算しなければならない。
【００５１】
ステップ４ｃで計算された４つのサンプル組合せの他のＭ−５のメモリ位置ｋ＋５，ｋ＋６，．．．，Ｍ−１，０，１，．．．，ｋ−１への累算はステップ１−４の次の実行サイクル中に行わなければならない。したがって、全体として、計算された組合せの中の選択された組合せを、次のサイクルのステップ４ｄおよび４ｃの実行中に、メモリ位置ｋ＋４を含むＭ−４メモリ位置の内容Ｍ−４へ加算しなければならない。それ自体、ステップ４ｃは１サンプルクロック周期以内に７つの演算を完了する必要があるが、これらの演算はステップ４ｂの４つの演算と並列に実行することができる。他方のＭ−４演算は４つのサンプル周期の残りプラス他方の３演算中に完了しなければならず、それは４サンプルクロック周期以内に達成しなければならない合計Ｍ−４＋７演算である。それはサンプルクロック周期当たり少なくとも（Ｍ＋３）／４演算の計算速度を提供して達成することができる。
【００５２】
例えば、Ｍ＝６４であれば、ステップ１−４ｄの並列実行に加えてサンプルクロック周期当たり少なくとも１７演算の計算速度が必要である。各ステップ１−４ｄがサンプルクロック周期当たりさらに４算術演算を消化するため、タイミングコントローラ２１がサンプルクロック周波数の少なくとも２１倍の高速クロックを利用できる場合には、全演算に対処することができメモリ２１に対するサンプルクロック周期当たり２１のリード−モディファイ−リライトサイクルが許される。これは長さ６４の従来技術のスライディング相関器の１／３である。
【００５３】
必要な高速サンプルクロック周波数は前の７つの値が使用される間に新しい７つの４サンプル組合せが同時に生じる計算をできるようにして低減することができる。それは７つのメモリ位置の２つの代替セットが与えられば生じることができる。次に、新しい７つの組合せを計算するのに必要な７つの演算がＭ−４メモリ位置への前の組合せの加算と並列に生じ、メモリ２１に対するリード−モディファイ−リライトサイクルの速度はＭ＝６４相関器に対してサンプルクロック周期当たり４＋（Ｍ−４）／４すなわち１９サイクルまで低減される。もちろん、より高速に対する一層の並列処理の提供もしくは処理素子当たり低減された計算速度のトレードオフが可能である。例えば、メモリ２１は２つのバンクへ分割することができ、２つのリード−モディファイ−リライトサイクルが高速クロック周期ごとに並列に実施できるように２つの加減算器を設けることができる。
【００５４】
究極のパラレリズムはメモリ２１を、各々がＭ／Ｎ加減算器の中の対応するものと接続された、Ｎ素子のＭ／Ｎバンクへ分割することである。必要な全てのメモリリード−モディファイ−リライトサイクルが並列に生じるように他方の（Ｍ−Ｎ）／Ｎメモリ位置を格納できるように、新しいサンプルクロック周期ごとに更新される４つの連続するメモリ位置を異なるバンクに格納することができる。このような速度に整合するために、セレクター２５が必要とするＮサンプルの２（Ｎ−１）組合せを２（Ｎ−１）−１カスケード加算器のチェーンを使用してグレイ符号順に計算することができ、加算器は先行する加算器の出力に対してサンプル値を２回加減算して全組合せを論理のリップルスルー遅延だけと並列に得る。このような構成はハードウェアの複雑さがＭ−１並列加算器を必要とする完全並列相関器を有する従来技術のおよそ僅か１／Ｎである。
【００５５】
このようにして、前記した方法は従来技術の方法に比べてより長い相関長さ、より低いハードウェア複雑さ、より高い速度、より低い消費電力、もしくはこれらの利点を任意に組み合わせた相関器を形成するのに使用することができる。改善された相関器は１セットの受信信号サンプルの全シフトを相関するのに利用することができ、前記セットは信号の連続セットである必要はなく、例えば、バースト（例えば、時分割多元接続（ＴＤＭＡ）システムの場合、あるいは周波数ホッピングシステムにおける“ホップ”）で受信することができる。この方法に対する必要性は、例えば、受信信号のタイミングについて不確実性がある時はいつでも生じる。このような必要性は、信号サンプルの異なる遅延セットを逆拡散符号で逆拡散して異なる“ＲＡＫＥタップ”を形成することにより、“ＲＡＫＥ”受信機が異なる遅延パスに沿って受信された信号を結合するように構成される場合には符号分割多元接続（ＣＤＭＡ）システムでも生じる。相関器は複数の多くのＲＡＫＥタップを同時に逆拡散するように効率的に使用することができる。
【００５６】
さらに、この方法はＭの連続する信号サンプルの連続シフトと２進値には制約されず、例えば、＋１，−１および０の３進値を含むことができるＭの格納されたサンプル値の信号パターン間の相関を計算するのに使用することができる。Ｎ信号値の３＊＊Ｎの可能な全ての組合せをグレイ符号順で効率的に計算することができ、一時に１デジットだけがその許された値のセットを介して変更され、したがって前記した発明原理に従ってより高速の相関アルゴリズムを考案することができる。
【００５７】
この方法は、例えば、複数（例えば、４つ以上）の全地球測位システム（ＧＰＳ）衛星から受信したＣＤＭＡ信号を処理するナビゲーション受信機におけるいくつかの異なるＣＤＭＡ符号のいくつかのシフトにより相関を行わなければならない時にも有用である。
【００５８】
図４に示す相関器は従来の相関器よりも複雑ではなくしかも高速である。同等な利点を提供するさまざまな代替構成がある。そのような構成の一例を図６ａ−６ｃに示す。
【００５９】
図６ａにおいて、長さ６４の整合フィルタは３２の長さ２の整合フィルタ１，２，．．．３２により置換される。第１の整合フィルタは入力サンプルを遅延要素Ｄ１で遅延させ、遅延した出力を
0003585441.tif 000005
をかけた次のサンプルに加える。ここで演算子
0003585441.tif 000006
は係数値がブール記法における１または０（代数記法における＋１または−１）の１ビット２進値である時には“排他的ＯＲ”演算と同じである。したがって、＋１または−１の乗算演算は入力値（−１に対する）もしくは否定（＋１に対する）の符号変更と等価である。入力信号サンプルａ（ｉ）からａ（ｉ＋６３）を使用して、図６ａの第１の加算器の出力は次のようになる。
0003585441.tif 000007
これに再度Ｃ１を乗じると（符号変更）
Ｃ１・ａ（ｉ）＋Ｃ１２・Ｃ２・ａ（ｉ＋１）
となり、Ｃ１２＝１であるため、それは、
Ｃ１・ａ（ｉ）＋Ｃ２・ａ（ｉ＋１）  に等しく、それは２サンプル整合フィルタ出力に等しい。
【００６０】
次に、この値は図６ａの第１の２サンプル遅延要素により遅延され、２サンプル遅延後に第２の２サンプル整合フィルタの出力Ｃ３・ａ（ｉ＋２）＋Ｃ４・ａ（ｉ＋３）に加算されて次のようになる。
Ｃ１・ａ（ｉ）＋Ｃ２・ａ（ｉ＋１）＋ Ｃ３・ａ（ｉ＋２）＋Ｃ４・ａ（ｉ＋３）
【００６１】
これは４サンプル整合フィルタの出力と考えられる。次に、この出力は遅延されて第３の２サンプル整合フィルタの出力に加算され、６４素子整合フィルタに対応する出力が得られるまで続けられる。あるいは、一方を４サンプル周期だけ遅延させた後で２つの４サンプル整合フィルタの出力を結合して８サンプル整合フィルタ値を得、以下同様にして、整合フィルタ長を連続的に２倍とする２進ツリーを形成することができる。しかしながら、これらいずれのバリエーションにおいても、加算および乗算（符号変更）の総数は図２の従来の装置におけるものとほぼ同じである。
【００６２】
図６ａの３２の２サンプル整合フィルタの各々が最終２入力サンプル（もしくはその負数）の和もしくは差を計算する。したがって、形成する必要があるのは３２の値ではなく、和および差の２つの異なる値だけである。
【００６３】
図６ｂは遅延Ｄにおいてサンプルを遅延しバタフライ回路内の先行するサンプルと結合する、２つの連続するサンプルの和および差の予計算を示す。“バタフライ回路”という用語は、多くの同時和および差を計算するのにも必要である、高速フーリエ変換の理論から借りたものである。２つのマルチビット２進値の同時和および差は単一加減算回路の２倍よりも少なく単一加算回路よりも僅か４０％程度しか多くない複雑さの論理構造を使用して計算することができる。したがって、バタフライ回路を使用して一対のサンプル組合せを形成することは複雑さをおよそ４０％節減し消費電力は同等数の独立した加算器および減算器に匹敵することを表わす。
【００６４】
図６ｂにおいて、和および差値ａ（ｉ）＋ａ（ｉ＋１）およびａ（ｉ＋１）−ａ（ｉ）はいくつかの２方向スイッチすなわちセレクターへ与えられる。第１のセレクターはＣ１およびＣ２間の排他的ＯＲに依存して和もしくは差を選択する。Ｃ１＝Ｃ２であれば、図６ｂの装置においてａ（ｉ）およびａ（ｉ＋１）に同じ符号が乗じられて、それらの和もしくは負の和を発生する。したがって、Ｃ１＝Ｃ２（すなわち、Ｃ１．ＸＯＲ．Ｃ２＝０）であれば、第１のセレクター回路は和を選択する。逆に、Ｃ１．ＸＯＲ．Ｃ２＝１であれば、差が選択される。次に、選択された和もしくは差はさらにＣ１を乗じることにより符号変更されて第１段（２サンプル整合フィルタ）から所望の値Ｃ１．ａ（ｉ）＋Ｃ２．ａ（ｉ＋１）が得られる。
【００６５】
図６ａと同様に、第１段からのこの値は遅延素子２Ｄにより２サンプル周期遅延された後でＸ２の第２段出力へ加えられる。
値Ｃ３．ａ（ｉ＋２）＋Ｃ４．ａ（ｉ＋３）
【００６６】
したがって、６４段整合フィルタ出力値の形成が前と同様に進行する。しかしながら、この実施例ではバタフライ回路を使用した２つの連続する入力サンプルの予組合せにより加算および乗算（すなわち、符号変更）は６３−６４から３１へ低減されている。それにより積和演算の消費電力は半減される。
【００６７】
しかしながら、相当な量の電力が遅延素子により消費される。図６ａ，６ｂおよび６ｃにおいて、遅延素子数にその動作周波数を乗じたものはほぼ同じである。総消費電力を半減するためには、遅延素子数もしくはそのクロック周波数を低減しなければならない。
【００６８】
図６ｃは図６ｂの３１の２素子遅延（その６２素子の全てが同じレートＦｃでクロックされる）を、各々がＦｃ／２でクロックされる、３１の単素子遅延の２バンクへどのように仕切ることができるかを示す。したがって、消費電力は６２．Ｆｃ単位から２×３１．Ｆｃ／２単位、すなわち３１．Ｆｃ単位、へ低減され遅延素子内の消費電力は半減される。したがって、図６ｃの本発明の整合フィルタは図２の従来技術の整合フィルタのほぼ半分の消費電力で作動する。
【００６９】
第１の実施例では、入力サンプルはデジタル記憶素子、レジスタもしくはラッチ等の遅延素子Ｄを使用して１サンプルだけ遅延され、新しいサンプルおよび前のサンプルに対するアクセスを同時に提供する。バタフライ回路は現在および前の値の和および差を形成する。２つの連続する入力サンプルのこれら２つの予組合せが次にＮ／２のセレクター回路へ与えられる。セレクター回路は所与のＮビット語の連続する２進ビットの各対が同じであるか異なるかに従って和もしくは差を選択する。次に、選択された値は各ビット対の最初のビットに従って符号変更され、２進ビットの関連する対が、それぞれ、００，０１，１０または１１の値を有するかに従って符号変更した値が和、差、負和もしくは負差の１つに等しくなるようにされる。次に、符号変更され選択された値がＮ／２加算器回路へ与えられその出力がＮ／２の２サンプル周期遅延素子の各々へ与えられる。各加算器の第２の入力は先行する遅延素子から引出され、したがってチェーンを形成する。カスケードしないのであれば、チェーンの始めの加算器は省くことができ、最終加算器の後の遅延素子も省くことができる。カスケードが使用されない場合には、第１の２サンプル整合フィルタの出力は直接第１の遅延素子へ行き、最終加算器の出力は最終出力すなわち相関値である。したがって、各サンプルクロック周期において実施される加算数はバタフライ演算（２つの加算演算と等価）プラス、従来の整合フィルタに必要なＮ加算から、Ｎ／２−１加算へ低減される。
【００７０】
図６ｃに戻って、第１の実施例をさらに改良したものを示し、Ｎ／２−１の２サンプル遅延素子の各々がＮ／２−１の１サンプル遅延素子の２つのチェーンにより置換されている。第１のチェーンは偶数サンプル周期で使用されるように選択され、第２のチェーンは奇数サンプル周期で使用されるように選択される。それにより、各サンプル周期においてクロックしなければならない遅延素子数は従来技術のＮ−１からＮ／２−１へ低減される。加算数の半減とサンプル周期ごとにクロックされる遅延素子数の半減とを結合することにより整合フィルタの消費電力は有用に半減される。
【００７１】
図７はもう１つの実施例に従った整合フィルタ構成を示し、２つの連続する入力サンプルの４つの組合せＳＵＭ，ＤＩＦＦＥＲＥＮＣＥ，−ＳＵＭおよび−ＤＩＦＦＥＲＥＮＣＥの全てを形成するのにバタフライ回路が使用される。３２の４方向セレクター回路が（Ｃ１，Ｃ２），（Ｃ３，Ｃ４）等の２進係数対に依存して４つの組合せの中の１つを選択する。選択された組合せは偶数サンプル周期については３１の遅延素子Ｄ１ｅからＤ３１ｅの第１のバンクで、奇数サンプル周期については３１の遅延素子Ｄ１ｏからＤ３１ｏの第２のバンクで遅延され、遅延された各値は予め遅延された和に加算される。セレクタースイッチＳ１，Ｓ２，．．．Ｓ３２が偶数サンプル周期について偶数遅延バンクの遅延素子から、あるいは奇数サンプル周期について奇数バンク遅延素子から、予め遅延された和を選択する。したがって、４つの予組合せを全て形成すれば２方向セレクタースイッチを４方向セレクタースイッチと置換することにより３２の符号変更が解消される。この選択は詳細なトレードオフの後で特定の集積回路技術のパラメータを使用して最善の実現を決定するように行うことができる。このトレードオフを図８に詳細に示し、それは２つの予組合せしか形成せず、２方向セレクタースイッチを使用することにより４つの組合せを形成し４方向セレクタースイッチを使用することに替わるものであるが、Ｃ１の値に従って選択後符号変更を行う必要がある。
【００７２】
図９は４つの信号サンプルの予組合せを形成することにより本発明をさらに拡張したものを示す。３つの遅延回路Ｄを使用して、４つの連続するサンプル値ａ，ｂ，ｃおよびｄがプリコンバイナーへ与えられる。可能な予組合せ符号パターンは２の４乗、すなわち１６となる。符号が違うだけの組合せの形成は回避するのが有利であるため、プリコンバイナーはサンプル値‘ａ’について‘＋’符号を有する８つの組合せしか形成しない。したがって、１６のセレクタースイッチが１６方向スイッチではなく８方向スイッチしか必要としないことはハードウェアの節減となる。８方向スイッチは下記のような３つの２進ビットに従って８つの予組合せの中の１つを選択する。
Ｂ１＝Ｃ１．ＸＯＲ．Ｃ２
Ｂ２＝Ｃ１．ＸＯＲ．Ｃ３
Ｂ３＝Ｃ１．ＸＯＲ．Ｃ４
Ｃ１をＸＯＲすることにより、サンプル値‘ａ’に適用される符号は無視される。この全体符号はＣ１を使用する乗算器（符号変更器）において後選択に適用される。
【００７３】
第１の符号変更器からの出力は１５遅延素子の４バンクの１つで４サンプル周期遅延されている４サンプル整合フィルタに一致する。各遅延素子はクロック周波数Ｆｃ／４で駆動され、各バンクはクロックＦｃの４クロックパルスごとに使用される。したがって、クロックＦｃは４分割されて４つの遅延素子バンクをそれぞれクロックするジグザグタイミング位相の４つの１／４周波数クロックを生じる。図９において、６４サンプル整合フィルタは１５の遅延および加算段しか使わずに形成され、遅延素子の消費電力は図２の装置の６３．Ｆｃから４×１５．Ｆｃ／４、すなわち１５．Ｆｃへ低減されることがお判りであろう。したがって、消費電力は図２に示す装置の１／４に低減されている。
【００７４】
米国特許５９３１８９３（1999年8月３日登録）で説明されるように、前記原理は２つの連続する値の和および差だけでなくより多くの入力サンプルの予組合せの計算に拡張することができる。例えば、図９において、入力サンプルは３つの遅延素子のチェーンを介して供給して４つの連続するサンプル、すなわち現在サンプルプラス最後の３つ、に対する並列アクセスを提供することができる。プリコンバイナーが可能な全ての４ビット符号パターンを使用して４つの入力サンプルの可能な１６の加法的組合せを全て計算する。典型的な実施例では、他方の８つは一方の単なる負数にすぎないためこれらの８つだけを計算すればよい。また、８つの組合せは形成された連続する各予組合せ間で１つの符号しか変更されないグレイ符号順で計算され、したがって加算数は８×３＝２４から３＋７＝１０へ低減される。２つの加算よりも少ない複雑さで和および差を同時に形成することができるバタフライ回路の使用を開発する等の、他の技術を使用して予組合せを形成する複雑さを低減することができる。
【００７５】
各セレクター回路、Ｓ１−Ｓ１６、は次に所与のＮビット語の４つの２進ビットの極性に従って１６の予組合せの中の１つを選択することができる。図９に示すように、それは８つの予組合せの中の１つを選択し次にそれを否定することを含むことができる。次に、選択された予組合せは加算器回路を介して４サンプル遅延素子へ与えられる。セレクター回路数はＮ／４へ低減されており、加算器回路数はＮ／４−１となるように低減されて使用する４サンプル遅延素子数はＮ／４−１となる。やはり図９に示すように、Ｎ／４−１の４サンプル遅延素子は各々が１／４サンプルレートクロックの４つの位相の中の異なる１つによりクロックされるＮ／４−１の１サンプル遅延素子の４つのチェーンで置換することができる。したがって、クロックされた遅延段数および各サンプルクロック周期において実施される加算数はおよそＮ／４へ低減され、消費電力は３／４低減される。
【００７６】
前記した原理を４つよりも多い連続する入力サンプルを使用する１６よりも多い予組合せの形成に拡張しても相関器の消費電力はある点までしか低減されず、その後で多数の予組合せを形成してセレクター回路へ分配すると消費電力はもう一度上昇することがある。それは予組合せを運ぶワード線数が指数関数的に、すなわち２の結合する入力サンプル数乗で、増加するがシフトおよび加算数は比例的にしか減少しないためである。したがって、相関長Ｎの任意所与の値に対する消費電力を最小限に抑える設計が必要とされる。
【００７７】
図１０に示すもう１つの実施例では、予組合せを新しい入力サンプルが入力されるたびではなく、例えば４つの新しいサンプルの、グループが入力されるたびに形成することにより消費電力をさらに改善することができる。したがって、予組合せのワード線のトグルレートのように、予組合せの形成レートが低減される。この実施例では、ブロックΦ１内でＮ／４の４サンプル予組合せが加算されて第１のＮサンプル相関値を形成する。次に、ブロックΦ２内でＮ／４−１の予組合せが前の入力値の３サンプル組合せおよび現在サンプルに加算されて第２の相関値を形成する。ブロックΦ３内でもう１つのＮ／４−１の予組合せが前の入力値の２サンプル組合せと現在および前のサンプルの組合せに加算されて第３の相関値を形成する。最後に、ブロックΦ４内でさらにＮ／４−１の予組合せが選択され前の入力サンプル値および３つの最も最近の入力サンプル値の組合せと結合されて第４の相関値を形成する。このようにして、相関値当たりおよそＮ／４の加算−シフト演算により４つのサンプルクロック周期当たり４つの相関が発生され、予組合せの形成レートは４サンプルクロック周期当たり１回低減される。
【００７８】
消費電力の低減は指数関数的に増加する形成すべき予組合せ数、およびセレクタースイッチの複雑さの増大、等により挫折することがある。したがって、消費電力が最小となる最適予組合せ形成数がある。
【００７９】
図９の整合フィルタと図４のスライディング相関器の違いは、図９ではクロックＦｃの各サイクルにおいて８つの予組合せが形成されるが、図４では４つのサンプルの予組合せは４サンプルクロックごとにしか計算されないことである。１つの理由は、図４では１つの奇数サンプルの三角フィレット、２つのサンプルの和および４つの相関の各グループの第２、第３および第４の相関の始めと終りの３つのサンプルの和をそれぞれ加算して４つの相関の完全なグループが計算されることである。
【００８０】
図１０は図４のスライディング相関器が別の実施例に従ってどのように実現できるかを示す。レートＦｃで到来する入力サンプルは４方向コミュテータ１０によりａ，ｂ，ｃ，ｄで示す４つのメモリ素子へ分配される。それは入力サンプルが４つのグループへ分けられ第４サンプルクロックごとにプリコンバイナーＰ１の入力へラッチされるようなシリアル／４サンプル並列コンバータを形成する。入力ラッチからの４つのサンプルはプリコンバイナーＰ１においてＦｃ／４の低減されたレートで結合され、したがって８本の出力線はＦｃ／４のレートでしか変化しない。それによりプリコンバイナーＰ１の消費電力が低減される。Ｓ１で示す第１のセレクタースイッチは前と同様にＣ１×Ｃ２，Ｃ１×Ｃ３およびＣ１×Ｃ４に依存して予組合せの１つを選択し、次に選択は全体符号Ｃ１に従って符号変更されクロック位相１に対する４サンプル整合フィルタ値であるａＣ１＋ｂＣ２＋ｃＣ３＋ｄＣ４を得る。
【００８１】
クロック位相２に対して、プリコンバイナーＰ２はｂＣ１＋ｃＣ２＋ｄＣ３を形成し、
クロック位相３に対して、プリコンバイナーＰ１はｃＣ１＋ｄＣ２を形成し、
クロック位相４に対して、プリコンバイナーＰ１はｄＣ１を形成する。
各クロック位相に対して形成された値は４つの遅延素子バンクの各々において遅延され、その第１の素子はＤ１１，Ｄ１２，Ｄ１３およびＤ１４で示されている。
【００８２】
第１の遅延バンク素子Ｄ１１，Ｄ１２，Ｄ１３およびＤ１４からの遅延された出力はセレクターＳ２により選択されたもう１つの予組合せに加算される。しかしながら、図９とは対照的に、Ｓ２は第１のクロック位相に対してサンプルの異なるセットｅＣ５＋ｆＣ６＋ｇＣ７＋ｈＣ８を選択し、ｅ，ｆ，ｇ，ｈはａ，ｂ，ｃ，ｄの後の４つの入力サンプルである。加算後、下記の８サンプル整合フィルタ値が得られる。
ａＣ１＋ｂＣ２＋ｃＣ３＋ｄＣ４＋ｅＣ５＋ｆＣ６＋ｇＣ７＋ｈＣ８
第２のクロック位相に対して、セレクターＳ２は、
ｅＣ６＋ｆＣ７＋ｇＣ８＋ｈＣ９
を選択しなければならなず、Ｐ２からの、
ｂＣ１＋ｃＣ２＋ｄＣ３
に加算して７サンプル整合フィルタ値、
ｂＣ１＋ｃＣ２＋ｄＣ３＋ｅＣ６＋ｆＣ７＋ｇＣ８＋ｈＣ９
を得、以下同様である。セレクタースイッチＳ２を制御するのに使用されるビット組合せはＺｉで示され、ｉ＝２から１６である。符号スケジューラ１００が３つのセレクタースイッチ制御ビットのグループを予計算して格納する。
【００８３】
さらに、図１０について、Ｓ１６の機能は第１のクロック位相の６４サンプル相関を完了するのに必要な最後の４サンプル組合せを選択することである。第２のクロック位相に対しては異なる組合せが選択され、それは第２の相関の最後から２番目の４つのサンプル値に対応し、最後の値ａＣ６４は第３のプリコンバイナーＰ３により与えられる。同様に、Ｐ３は第３のＦｃ／４クロック位相で相関を完了する組合せａＣ６３＋ｂＣ６４および第４の相関を完了するａＣ６２＋ｂＣ６３＋ｃＣ６４を供給する。したがって、４つの相関が１つのＦｃ／４クロック周期内で完了する。それは相関当たり僅か１６の遅延と１６の加算演算により達成される。唯一の付加演算はサンプルレートクロックＦｃの第４クロックサイクルごとにＰ１，Ｐ２およびＰ３により実施される予組合せ演算である。したがって、形成される予組合せの合計数はクロックＦｃの４サイクル当たり８（Ｐ１）＋３（Ｐ２）＋３（Ｐ３）＝１４、すなわち１６の遅延および加算演算に加えて計算した相関当たり３．５組合せとなる。したがって、予組合せを形成する電力コストは図９の方式に比べて低減される。
【００８４】
もちろん、この原理を拡張して予組合せをグレイ符号順で形成することによりその電力コストをさらに低減することができ、また一時に５つ以上の入力サンプルの予結合に応用することができる。さらに、選択−遅延−加算素子を重複することにより、予結合回路Ｐ１を重複することなく、一時に６４ビット２進符号よりも多くの相関を実施することができる。図９の三角開始および終了フィレットのない方式もしくは開始および終了フィレットを実施する図１０の方式を使用して予結合する最適サンプル数は、共通予結合計算量の総電力予算における重要度が低くなるため、２つ以上の符号との同時相関が使用される場合には大きくなる。
【００８５】
本発明は複素符号が実符号および虚符号を有する実部および虚部を有する複素サンプルのストリームの相関にも応用することができる。このような相関器は本開示の一部としてここに組み入れられている同一譲受人のボトムリー等の「直接拡散によるスペクトラム拡散通信信号の逆拡散（Despreading of Direct Sequence Spread Spectrum Communications Signals）」のタイトルをもつ１９９９年１２月２１日に発行された米国特許第６００５８８７号に従って構成することができる。
【００８６】
また、省かれる相関に従って回路の異なる部分および遅延素子へのクロックパルスを適切に禁止することにより、所与の応用において形成する必要のないサンプルシフトとの相関を省くこともできる。したがって、全てのスライディング相関を計算する必要がない場合には消費電力をさらに低減することができる。
【００８７】
当業者ならば、本発明はその本質的な特性から逸脱することなく他の特定の形式で実施できることがお判りであろう。したがって、前記した実施例はあらゆる点において説明用であって制約的意味合いはない。
【図面の簡単な説明】
【図１】従来の相関器を示す図である。
【図２】従来の相関器を示すもう１つの図である。
【図３】受信信号サンプルと相関させることができる１５ビット符号の重畳する連続的シフトの構成を示す図である。
【図４】典型的な相関器の略ブロック図である。
【図５】図４の相関器を実現するのに使用することができるステップのシーケンスを示す図である。
【図６ａ】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図６ｂ】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図６ｃ】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図７】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図８】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図９】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図１０】本発明のさまざまな第１の実施例に従った整合フィルタ構成を示す図である。
【図１】
0003585441.tif 000008
【図２】
0003585441.tif 000009
【図３】
0003585441.tif 000010
【図４】
0003585441.tif 000011
【図５】
0003585441.tif 000012
【図６Ａ】
0003585441.tif 000013
【図６Ｂ】
0003585441.tif 000014
【図６Ｃ】
0003585441.tif 000015
【図７】
0003585441.tif 000016
【図８】
0003585441.tif 000017
【図９】
0003585441.tif 000018
【図１０】
0003585441.tif 000019