(57)【特許請求の範囲】
【請求項１】
デジタル信号値のシーケンスのための重畳値差のシーケンスを形成する方法であって、
各デジタル信号値がＲ回数サンプリングされたものであり、各桁の大きさが連続２進数Ｎとして表現できるものである（ＮとＲは、選択された正の整数）、デジタル信号値からなる第１の順序付きシーケンス{s(tk;rec)}(k = 0, 1, 2, ...)を供給すること、
少なくともＭ・Ｎ・Ｒ２進数の順序付きシーケンスとして表現できる、選択された値からなる第２の順序付きシーケンス{s(tp - tk;ref)}を供給して、前記第１のシーケンス及び前記第２のシーケンスの生成部分から少なくとも２つの重畳値を形成すると共に、少なくとも１つの選択された整数Pに関し、２つの重畳値C(tp)及びC(tp-1)の少なくとも１つの差ΔC(tp)を形成することであって、ここで前記差が、多くともＭ・Ｎ＋１個（Ｍは、前記信号値の大きさを表す最大桁数を示す整数）のゼロでない項を有する和の形で表現されること、
を備える方法。
【請求項２】
前記差ΔC(tp)を、下記和として形成することを更に備える請求項１に記載の方法。
【数１】
0004495382.tif 000009
ここで、Ｋは、少なくともＭ・Ｎ・Ｒ＋１に等しい選択された正の整数であり、W(p;k)は、それらの係数がゼロでない多くともＭ・Ｎ＋１を持つ選択された係数である。
【請求項３】
＋２，＋１，０，−１，−２の数字からなる値の群から、前記係数W(p;k)のそれぞれを抽出することを更に備える請求項２に記載の方法。
【請求項４】
係数W(p;k)がゼロでないところの前記整数ｋが、条件ｐ−ｋ＝Ｒ・ｕ＋ｖ（ここで、ｕは何れかの整数であり、ｖは選択された整数である。）を満足する整数の群から抽出されるものである請求項２に記載の方法。
【請求項５】
前記整数Ｒを、｛２，３，４，５，６，７，８，９，１０｝からなる整数の群から選択することを更に備える請求項２に記載の方法。
【請求項６】
少なくとも１つの前記供給された信号値s(tk;ref)を１６進法で表現し、前記整数Ｎに４を選択することを更に備える請求項２に記載の方法。
【請求項７】
少なくとも１つの前記供給された信号値s(tk;ref)を８進法で表現し、前記整数Ｎに３を選択することを更に備える請求項２に記載の方法。
【請求項８】
生成項s(tk;rec)・s(tp - tk;ref)から少なくとも１つの重畳値を、
第１の重畳値C(t1)を供給すること、および
下記相関によって、少なくとも１つの追加の重畳値C(tq)を計算すること、
によって計算することを更に備える請求項２に記載の方法。
【数２】
0004495382.tif 000010
ここで、ｑは１よりも大きい選択された整数。
【請求項９】
少なくとも２つの連続差値ΔC(tq)及びΔC(tq+1)のシーケンスを計算すること、
２つの連続差値が２つの関係、ΔC(tm)≧０およびΔC(tm+1)≦０を満足する整数ｍを決定すること、および
前記重畳値が最大に達する時間値ｔ＝τを、
τ = -c1/(2・c2),
c2 = {-(ΔC(tm+1) + ΔC(tm))・(tm - tm+1)
- ΔC(tm+1)・(tm+1 - tm-1)},
c1 = {-(ΔC(tm+1) + ΔC(tm))・(tm+12 - tm2)
- ΔC(tm+1)・(tm-12 - tm+12)},
に従って推定すること、
によって、前記重畳値が最大に達する時間値ｔ＝τを推定することを更に備える請求項２に記載の方法。
【請求項１０】
少なくとも２つの連続差値ΔC(tq)及びΔC(tq+1)のシーケンスを計算すること、
２つの連続差値が２つの関係、ΔC(tm)≧０およびΔC(tm+1)≦０を満足する整数ｍを決定すること、
時間値ｔ＝τを、
τ = -c1/(2・c2),
c2 = {-(ΔC(tm+1) + ΔC(tm))・(tm - tm+1)
- ΔC(tm+1)・(tm+1 - tm-1)},
c1 = {-(ΔC(tm+1) + ΔC(tm))・(tm+12 - tm2)
- ΔC(tm+1)・(tm-12 - tm+12)},
に従って推定すること、
|tm' - τ| = min{|tm-1 - τ|,|tm - τ|,|tm+1 - τ|}であるところの時間値ｔ = tm'（m' = m-1, m 又は m-1である）を選択すること、および
前記時間値tm'を、前記重畳値が最大に達する、離散的な集合から抽出された時間値として解釈すること、
によって、前記重畳値が最大に達する時間値を推定することを更に備える請求項２に記載の方法。
【請求項１１】
少なくとも２つの連続差値ΔC(tq)及びΔC(tq+1)のシーケンスを計算すること、
２つの連続差値が２つの関係、ΔC(tm)≧０およびΔC(tm+1)≦０を満足する整数ｍを決定すること、および
前記時間値tmを、前記重畳値が最大に達する、離散的な集合から抽出された時間値として解釈すること、
によって、前記重畳値が最大に達する時間値を推定することを更に備える請求項２に記載の方法。
【請求項１２】
デジタル信号値のシーケンスのための重畳値差のシーケンスを形成するシステムであって、
各デジタル信号値がＲ回数サンプリングされたものであり、各桁の大きさが連続２進数Ｎとして表現できるものである（ＮとＲは、選択された正の整数）、デジタル信号値からなる第１の順序付きシーケンス{s(tk;rec)}(k = 0, 1, 2, ...)を供給すること、
少なくともＭ・Ｎ・Ｒ２進数の順序付きシーケンスとして表現できる、選択された値からなる第２の順序付きシーケンス{s(tp - tk;ref)}を供給して、前記第１のシーケンス及び前記第２のシーケンスの生成部分から少なくとも２つの重畳値を形成すると共に、少なくとも１つの選択された整数Pに関し、２つの重畳値C(tp)及びC(tp-1)の少なくとも１つの差ΔC(tp)を形成することであって、ここで前記差が、多くともＭ・Ｎ＋１個（Ｍは、前記信号値の大きさを表す最大桁数を示す整数）のゼロでない項を有する和の形で表現されること、
をプログラムされたコンピュータを備えるシステム。
【請求項１３】
前記差ΔC(tp)が、下記和として表現されるものである請求項１２に記載のシステム。
【数３】
0004495382.tif 000011
ここで、Ｋは、少なくともＭ・Ｎ・Ｒ＋１に等しい選択された正の整数であり、W(p;k)は、それらの係数がゼロでない多くともＭ・Ｎ＋１を持つ選択された係数である。
【請求項１４】
＋２，＋１，０，−１，−２の数字からなる値の群から、前記係数W(p;k)のそれぞれが抽出されるものである請求項１３に記載のシステム。
【請求項１５】
係数W(p;k)がゼロでないところの前記整数ｋが、条件ｐ−ｋ＝Ｒ・ｕ＋ｖ（ここで、ｕは何れかの整数であり、ｖは選択された整数である。）を満足する整数の群から抽出されるものである請求項１３に記載のシステム。
【請求項１６】
前記整数Ｒが、｛２，３，４，５，６，７，８，９，１０｝からなる整数の群から選択されるものである請求項１３に記載のシステム。
【請求項１７】
少なくとも１つの前記供給された信号値s(tk;ref)が１６進法で表現され、前記整数Ｎに４が選択される請求項１３に記載のシステム。
【請求項１８】
少なくとも１つの前記供給された信号値s(tk;ref)が８進法で表現され、前記整数Ｎに３が選択される請求項１３に記載のシステム。
【請求項１９】
前記コンピュータは、生成項s(tk;rec)・s(tp - tk;ref)から少なくとも１つの重畳値を、
第１の重畳値C(t1)を供給すること、および
下記相関によって、少なくとも１つの追加の重畳値C(tq)を計算すること、
によって計算することをプログラムされている請求項１３に記載のシステム。
【数４】
0004495382.tif 000012
ここで、ｑは１よりも大きい選択された整数。
【請求項２０】
前記コンピュータは、
少なくとも２つの連続差値ΔC(tq)及びΔC(tq+1)のシーケンスを計算すること、
２つの連続差値が２つの関係、ΔC(tm)≧０およびΔC(tm+1)≦０を満足する整数ｍを決定すること、および
前記重畳値が最大に達する時間値ｔ＝τを、
τ = -c1/(2・c2),
c2 = {-(ΔC(tm+1) + ΔC(tm))・(tm - tm+1)
- ΔC(tm+1)・(tm+1 - tm-1)},
c1 = {-(ΔC(tm+1) + ΔC(tm))・(tm+12 - tm2)
- ΔC(tm+1)・(tm-12 - tm+12)},
に従って推定すること、
によって、前記重畳値が最大に達する時間値ｔ＝τを推定することをプログラムされている請求項１３に記載のシステム。
【請求項２１】
前記コンピュータは、
少なくとも２つの連続差値ΔC(tq)及びΔC(tq+1)のシーケンスを計算すること、
２つの連続差値が２つの関係、ΔC(tm)≧０およびΔC(tm+1)≦０を満足する整数ｍを決定すること、
時間値ｔ＝τを、
τ = -c1/(2・c2),
c2 = {-(ΔC(tm+1) + ΔC(tm))・(tm - tm+1)
- ΔC(tm+1)・(tm+1 - tm-1)},
c1 = {-(ΔC(tm+1) + ΔC(tm))・(tm+12 - tm2)
- ΔC(tm+1)・(tm-12 - tm+12)},
に従って推定すること、
|tm' - τ| = min{|tm-1 - τ|,|tm - τ|,|tm+1 - τ|}であるところの時間値ｔ = tm'（m' = m-1, m 又は m-1である）を選択すること、および
前記時間値tm'を、前記重畳値が最大に達する、離散的な集合から抽出された時間値として解釈すること、
によって、前記重畳値が最大に達する時間値を推定することをプログラムされている請求項１３に記載のシステム。
【請求項２２】
前記コンピュータは、
少なくとも２つの連続差値ΔC(tq)及びΔC(tq+1)のシーケンスを計算すること、
２つの連続差値が２つの関係、ΔC(tm)≧０およびΔC(tm+1)≦０を満足する整数ｍを決定すること、および
前記時間値tmを、前記重畳値が最大に達する、離散的な集合から抽出された時間値として解釈すること、
によって、前記重畳値が最大に達する時間値を推定することをプログラムされている請求項１３に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の技術分野】
本発明は、多数のビット入力信号のデジタル・フィルタリングおよび相関または重畳値の計算に関する。
【０００２】
【発明の背景】
デジタル信号からの相関値の形成において、従来の手法が相関値の計算に使用された場合、単一の相関値を形成するために必要とされる乗算の数は、信号を定義するために使用されたタイムスロットまたは「チップ」の数Ｐと同じように大きくなる可能性がある。通信に対する符号分割多重アクセス（ＣＤＭＡ）手法では、通信シンボルが、擬似乱数（ＰＮ）コードと呼ばれる参照シンボルの固定パターンを使用して乗算あるいは「スプレッド」され、伝送される。受信側では、受信シンボルを検出するため、かつスプレッド用に使用された特定のコードを識別するための最適な解法は、最尤（ＭＬ）決定規則を使用する。コード化されたシンボルのためのＭＬ解法は、同じＰＮコードによって与えられた係数を有する、合致したフィルタまたは相関子であり、「デスプレッド」として知られるプロセスである。受信信号のための相関曲線の解析、および、そのピーク値の時間シフトおよび振幅の決定により、２つの問題に答えることができる。すなわち、（１）相関曲線を形成するために使用された参照パターンが、送信器で使用されたスプレッド・パターンと同じである可能性が高いか、および（２）最初の問題に対する答えが「イエス」であった場合、受信信号に関連付けられたもっとも可能性の高い時間シフトは何かである。
【０００３】
ＣＤＭＡ通信システム受信器は、少なくとも３・Ｎ個の合致したフィルタ値の使用を必要とする（ただしＮは、通信に使用されたレーキのフィンガ数である。）。デスプレッドについて使用された合致したフィルタ係数は、ＣＤＭＡチップにおけるゲート数の最大分数を説明し、必要とされる実質的な信号処理のために関連付けられた組み込みの時間遅延を有する。たとえば、符号分割多重アクセス（ＣＤＭＡ）を全地球測位システム（ＧＰＳ）における信号認識のために使用すると、使用されたチップの数はＰ＝１０２３であり、これは、単一の相関値を計算するために約１０２３の加算器を必要とし、これが約１０またはそれより多い層において配列され、相関曲線全体のための値のセットを計算するために、この計算がおよそ１０２３の各時間シフトについて繰り返される。（最低でも）１０の処理層についての時間遅延は、数１０ナノ秒となる可能性がある。
【０００４】
ＰＮコードが使用される第２のカテゴリは、デジタル通信におけるフレーム同期化におけるものである。伝送された情報シンボルがフレームに分割され、パックされ、これらはヘッダおよびトレーラ情報（オーバーヘッド）も搬送し、これは非同期で伝送されたフレームの残余の同期化のためのプリアンブルを含む。ＰＮコードまたは「ユニーク・ワード」（ＵＷ）が、フレーム内のペイロードの開始点の検出における支援のために含まれる。受信器はフレーム内のＵＷについて探索し、最適な解法はＭＬ同期装置である。再度、これには、フレームにおいて使用されたＵＷによって与えられた係数を有する、合致したフィルタまたは相関子の使用が必要である。再度、パターン認識について使用された合致したフィルタ係数は、フレーム同期化におけるゲート数の最大分数を説明する。
【０００５】
必要とされるものは、ＣＤＭＡ通信において使用される相関値の形成において、フレーム同期化において、かつ１つまたは複数の相関値の形成を必要とする他のいかなる信号処理手順においても、使用される算術演算の数を減らす手法である。この手法は複雑さが低減されているべきであり、はるかに少数のゲート数の使用を可能にし、各相関値の計算についてより小さい関連時間遅延を有するべきであることが好ましい。この手法は、いかなる大きさの信号にも対応するために十分な柔軟性を有するべきであり、いかなる信号表現フォーマット（２進、四元数、８進、２進化１０進、１６進など）も使用し、かついかなる信号オーバーサンプリング・レートも使用することが好ましい。
【０００６】
【発明の概要】
これらの必要性が本発明によって満たされ、これは追加の演算の数をＭ・Ｎ・Ｒから最大でＭ・Ｎに減らす。ここで、Ｍは信号の大きさを表すために必要とされた桁の最大数であり（たとえば、最大１０ではＭ＝１、最大１００ではＭ＝２など、１０進ベースにおける）、Ｎは単一の「桁」を表すために使用された２進数字の数であり（たとえば、８進ではＮ＝３、１０進または１６進の桁ではＮ＝４）、Ｒは、信号受信のために使用されたオーバーサンプリング・レートである（たとえば、Ｒ＝２−１０、またはそれより上）。本発明は、各相関値を別々に計算するのではなく、２つの連続相関値の間の差を計算し、これにより、少なくともＲの乗算因数によって、参照またはコーディング・ワードの構造に応じて、相対値の計算のための算術演算の数を減らすことができる。必要とされるゲートの数が、同じ因数によって減らされ、相関値の計算についての関連時間遅延が、少なくともΔt(add)・log2(R)だけ減らされる。ここで、Δt(add)は、２つの値の加算を実行するために必要とされた時間である。任意選択的に、相関曲線が最大に到達する時間シフト点が自動的にこの手法によって識別され、対応する（最大）相関値が、この時間シフト点が識別された後に高速で回復される。
【０００７】
図１は、理想化された自己相関関数のグラフであり、これは受信デジタル信号s(t;rec)から形成することができ、これは一般にマルチビット数値として表現可能である。各時点tnは、重畳値C(tn)についての時間シフトに対応し、これは以下のように計算される。
【０００８】
【数５】
0004495382.tif 000002
【０００９】
ここで、s(t;ref)は、受信器で受信信号のためのパターン認識を実施するために使用された参照信号であり、{tk}は、受信信号についての相関値を計算するために使用された時点のシーケンス（必ずしも等距離の間隔ではない）である。時間シフトΔt(max)は、図１における相関曲線の最大振幅が、そうである必要はないが、重畳値を計算するために使用された時間シフト値tnのうち１つと正確に等しい可能性がある位置に対応する。
【００１０】
本発明の使用を最初に実施例によって例示する。ＰＮコード信号は振幅s(t;ref)＝７８９を有し、これは１６進フォーマットにおいて順序付きシーケンス０１１１／１０００／１００１として表される。受信信号は、選択されたレートＲでオーバーサンプリングされ、たとえば、Ｒ＝４であり、受信信号を表す１２個の各信号値s(t;rec)が４回連続して現れるようにされる。「修正１６進フォーマット」では、２進値「０」が数値「−１」によって置き換えられ、ここではより容易に本発明の演算を例示するために採用される。本発明の修正された形式は、従来の１６進フォーマット表現も取り扱う。修正１６進フォーマットを採用すると、ＰＮコード振幅s(t;ref)＝７８９について、オーバーサンプリングされた式は以下のようになる。
【００１１】
{s(t;ref)}= -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1  （２）
【００１２】
この数は４８＝３・４・４個の２進数字を有し、この実施例では、桁数Ｍ＝３、１６進（または１０進）表現数Ｎ＝４、およびオーバーサンプリング・レート数Ｒ＝４に対応する因数を含む。時間シフトtnは等距離であり、tn+1 - tn = Δt = 一定となる。
【００１３】
このＰＮコードを使用して相関値を計算するための従来の手法では、時間シフトのシーケンスtnが、オーバーサンプリングされた参照信号値s(tk;ref)）に適用され、結果として生じる信号値が受信信号値によって、式（１）に示すように乗算される。選択されたいかなる時間シフトtnの値でも、対応する相関値の計算には、４８個の信号値乗算器の使用および４７（または４８）個の加算器の使用が必要であり、これらを６層で配列することができ、これらは図２に示すように２４、１２、６、３、２および１個の半加算器を含む。従来のように受信信号を処理して単一の相関値を提供することについての関連時間遅延Δt(conv)は、単一の加算器での２つの値の加算に関連付けられた時間遅延Δt(add)の６倍である。より一般的には、関連時間遅延はおよそ{log2[M・N・R]}+であり、ただし{P}+は実数Ｐ以上である、より小さい整数であり、これは実数Ｐの整数部[P]+に関係付けられるが、これと同じではない。この実施例では、関連時間遅延はΔt(add)・{log2[3・4・4]}+であり、＝Δt(add)・{5.585}+ ＝ 6・Δt(add)である。
【００１４】
選択された実施例では、式（１）において定義された重畳値C(tn)は、以下のようになる。
【００１５】
【数６】
0004495382.tif 000003
【００１６】
ただし、ＰＮコード値のシーケンスは式（２）において示される。２つの連続重畳値の差は、以下となるように証明される。
【００１７】
【数７】
0004495382.tif 000004
【００１８】
w(n;k) = 0(n-kは4で割り切れない)
= PN((n+1-48)・Δt)  (k = 48)
= -PN(n・Δt)  (k = 0)
= 2 (n-k = 4・u; PN(4・u) = -PN(4・u+1) = -1; k≠0,48)
= 0 (n-k = 4・u; PN(4・u) = PN(4・u+1))
= -2(n-k = 4・u; PN(4・u) = -PN(4・u+1)=+1)          （５）
【００１９】
ただし、u=0,±1,±2,±3,...である。重畳値差C((n+1)・Δt)-C(n・Δt)が、多くとも１３＝３・４＋１個の項を含み、これは、整数差n-kが４によって除算可能である（n-k =0,1,2,...,48)、式（３）における重畳和におけるｋの整数値に対応することが証明される。n-kが４によって除算可能である指数の、７８９のＰＮコードによる特定の実施例では、１３個の連続した係数の値のシーケンスw(n;k)は以下のようになる。
【００２０】
{w(n;k)} = {-1, 2, 0, 0, 0, -2, 0, 0, 2, -2, 0, 2, 1}  （６）
【００２１】
最初および１３番目の値w(n;k)（＝＋１または−１）は、コードの差ではなく個々のＰＮコード値によって決定される。
【００２２】
この実施例では、特定の選択、すなわち、
Ｍ＝参照信号の最大桁＝３、
Ｎ＝各桁について使用された２進数字の数＝４、
Ｒ＝オーバーサンプリング・レート＝４を使用した。
【００２３】
図３は、式（２）において表されたＰＮコードの４８個の値を、シフト時間値s(t;ref)、s(t+Δt;ref)およびs(t+2Δt;ref)について例示する。これらの３つの４８個の数の各シーケンスが、式（１）に示すように、デジタル信号シーケンスの対応するメンバs(t;rec)によって乗算される。この実施例において採用されたオーバーサンプリング・レート(R = 4)のため、図３においてs(t;ref)を表すシーケンスの４番目毎の値が潜在的な「境界点」であり、これはＰＮコードのシーケンスのメンバs(t;ref)およびs(t+Δt;ref)が異なる符号（たとえば、+1/-1または-1/+1）を有することができるところである。同様に、s(t+Δt;ref)を表すシーケンスの４番目毎の値が潜在的な「境界点」であり、これはs(t+Δt;ref)およびs(t+2Δt;ref)が異なる符号を有するところである。s(t;ref)およびs(t+Δt;ref)など、２つの時間シフト・シーケンスが、このような境界点で同じ符号（たとえば、+1/+1または-1/-1）を有する場合、この境界点は、ゼロでない値を重畳値差C(tn) - C(tn-1)に与えない。
【００２４】
図４は、係数乗算器および信号加算器のアレイ４１を例示し、これは、ここで考察する実施例についての重畳値差をＭ＝３、Ｎ＝４およびＲ＝４で、しかし任意のＰＮコードにより形成するために使用することができる。アレイの最上位レベルは、最大でＭ・Ｎ−１＝１１個の係数乗算器モジュール４３−ｋを有し、それぞれが関連付けられた係数w(n;k)を有し(k=1,2,...,11)、これは、使用された特定のＰＮコードに応じて、値＋２、０または−２を有し、加えて信号s(48・Δt;rec)およびs(0;rec)を受信し、かつ重み付けされた差を形成して出す１つの信号差分器を有する。
【００２５】
Δs(n) = s(48・Δt;rec)・PN((n+1-48)・Δt) - s(0;rec)・PN(n・Δt)  （７）
【００２６】
係数乗算器モジュール４３−ｋについての出力信号は、以下のようになる。
【００２７】
O(43-k) = w(n;k)・s(4・k・Δt;rec)                           （８）
【００２８】
前述の実施例において使用されたＰＮコード７８９では、
w(n;1) = w(n;8) = w(n;11) = +2、
w(n;4) = w(n;10) = -2、
w(n;2) = w(n;3) = w(n;5) = w(n;6) = w(n;7) = w(n;9) = 0となる。
【００２９】
これは式（６）から証明できる通りである。最上位から２番目のアレイ・レベルは、６個の半信号加算器４５−ｊ（ｊ＝１，２，．．．，６）を有し、これらが６個の出力合計信号を生成する。最上位から３番目のアレイ・レベルは、３個の半信号加算器４７−ｈ（ｈ＝１，２，３）を有し、これらが３つの出力合計信号を生成する。最上位から４番目のアレイ・レベルは１つの半加算器４９を有し、最上位から５番目のアレイ・レベルは１つの半信号加算器５１を有し、この出力信号が、同じ指数値ｎについての重畳値差ΔC(tn)である。図４におけるアレイ４１は、最上位レベルでＭ・Ｎ−１＝１１個の信号係数乗算器、および追加の１２個の信号加算器を有する４レベルを有する。最大関連時間遅延はおよそ５・Δt(add)である。従来の重畳の手法での４７と比較して、必要とされるゲートの数は最大で２３（この実施例について選択されたＰＮコード７８９では１８）である。
【００３０】
より一般的には、式（４）において示した重畳値を以下のように表すことができる。
【００３１】
【数８】
0004495382.tif 000005
【００３２】
w(n;k) = 0 (n-kはRで割り切れない)
= PN((n+1-M・N・R)・Δt)  (k = M・N・R)
= -PN(n・Δt)  (k = 0)
= 2  (n-k = R・u; PN(R・u) = -PN(R・u+1) = -1)
= 0  (n-k = R・u; PN(R・u) = PN(R・u+1))
= -2 (n-k = R・u; PN(R・u)= -PN(R・u+1) = +1)        （１０）
【００３３】
重畳差を計算するために追加される項の最大数はＭ・Ｎ＋１である。２の因数による乗算は、２進表現された値の１ビット・シフトを使用して実施される。
【００３４】
革新的な手順は、第１の重畳値の計算または供給により開始する。
【００３５】
【数９】
0004495382.tif 000006
【００３６】
第１の重畳値を他の考察（たとえば、C(t1)=0）から知ることができ、計算する必要のない可能性がある。ｎ≧１では、図（９）において示したような重畳差ΔC(tn+1)=C(tn+1)-C(tn)のみが計算される。ここで必要とされた加算（および２による乗算）の総数は多くともＭ・Ｎであり、式（１０）において示したような係数W(n;k)の値に応じて、より少なくなる可能性がある。これらのＭ・Ｎ値加算を実施するために必要とされる半加算器の層の数は、多くとも{log2[M・N}+であることを証明することができる。Ｋ入力加算器（Ｋ≧２）が半加算器の代わりに使用された場合、これらのＭ・Ｎ値加算を実施するために必要とされるＫ入力加算器の層の数は、多くとも{logk[M・N}+に減らされる。式（１０）における係数W(n;k)によって必要とされる各２の因数の乗算を、シフト・レジスタにおいて１つの２進数字だけ左にシフトすることによって実施することができる。特定の重畳値、たとえばC(tm)が必要とされた場合、この値は、以下の関係を使用して計算される。
【００３７】
【数１０】
0004495382.tif 000007
【００３８】
前述において論じた特定の実施例では、図４は、重畳値差を計算するための適切なアレイを例示する。このアレイは多くとも{log2[M・N}+ ＝ ４層を必要とし、これは従来の手法での{log2[M・N・R]}+ ＝６とは対照的であり、また多くともＭ・Ｎ＝１２個の加算器を必要とし、これは従来の手法でのＭ・Ｎ・Ｒ＝４８とは対照的である。
【００３９】
整数Ｍは、ＰＮコードについて選択された「桁」によって決まる。前述の考察は、１６進フォーマットの使用に依拠しており、Ｎ＝４個の連続２進数字が、１０進などの各桁値を表現するために使用される。１０進フォーマットの使用にはＮ＝４も必要となり、これは少なくとも４個の２進数字の使用が、２進システムにおいて値８および９を表現するために必要とされるからである。桁値を８進フォーマットにおいて、Ｎ＝３個の連続２進数字を使用して表現することもできる。８進フォーマットでは、最大桁値が７となり（８進フォーマットでは１１１として表現される）、１０進フォーマットの最大桁値９または１６進フォーマットの値Ｆ（１５に等しい）ではない。
【００４０】
本明細書で開示する革新的な方法は、式（９）に示すように単一単位差ΔC(tn+1) = C(tn+1) - C(tn)を使用して、式（１２）に示すように重畳値自体を高速に計算する。以下は二重単位差である。
【００４１】
Δ2C(tn+2) = C(tn+2)-C(tn)
= ΔC(tn+2) + ΔC(tn+1)                  （１３）
【００４２】
望むなら、これを類似の方法で、前述において計算したように単一単位差の和を使用して計算することができる。より一般的には、望むなら、類似の方法で、ｐ単位差を以下のように計算することができる。
【００４３】
【数１１】
0004495382.tif 000008
【００４４】
本明細書で開示する革新的手法は、重畳値C(tn)のローカル最大値に対応する時間シフト値Δt(max)の推定においても有用であり、ただしΔt(max)は離散的時間シフト値tnのうち１つに一致する必要はないが、２つの離散的時間シフト値の間にある可能性がある。tm-1,tmおよびtm+1が図１における相関曲線についての３つの連続時間シフト点であり、時間シフト値Δt(max)がtm-1とtm+1の間にあると仮定する。この状況は、連続重畳値C(tm-1)、C(tm)およびC(tm+1)が以下の制約を満たすことを仮定する。
【００４５】
C(tm) ≧ max{C(tm-1),C(tm+1)}              （１５）
【００４６】
この制約を、重畳信号差についての同等の形式において、１対の制約として表現することができる。
【００４７】
ΔC(tm) ≧ 0,                              （１６Ａ）
ΔC(tm+1) ≦ 0                             （１６Ｂ）
【００４８】
値τ(max)を以下のように計算することができる。時間シフト点tm-1、tmおよびtm+1での相関値に適合された２次(またはそれより高い次数の)多項式は、以下のようになる。
【００４９】
P(τ;2) = c0 + c1・τ + c2・τ2 (tm-1 ≦ τ ≦ tm+1),      （１７）
c2 = {[C(tm-1) - C(tm+1)]・(tm - tm+1)
+ [C(tm) - C(tm+1)]・(tm+1 - tm-1)}/(det),            （１８）
c1 = {[C(tm-1) - C(tm+1)]・(tm+12 - tm2)
+ [C(tm) - C(tm+1)]・(tm-12 - tm+12)}/(det),          （１９）
c0 = C(tm) - c1・(tm) - c2・(tm)2,                           （２０）
det = {(tm-1 - tm)・(tm - tm+1)・(tm-1 - tm+1)}-1            （２１）
【００５０】
最大振幅についての時間シフトは、以下によって与えられる。
【００５１】
τ(max) = -c1(2./c2)                                  （２２）
【００５２】
時間シフト値τ(max)は、２つの相関信号差、ΔC(tm)=C(tm)-C(Δtm-1)-C(Δtm+1)およびΔC(tm+1)=ΔC(Δtm+1)-C(Δtm)のみによって決まり、これらは前述において示した手順に従ってすでに計算されている。
【００５３】
より一般的には、２次多項式P(τ;2)を、n次多項式P(τ;n)(n≧2)によって置き換えることができ、適切な制約が、3つまたはそれより多い離散的時点{tk}での多項式の値に課せられ、間隔tm-1≦τ≦tm+1内の多項式P(τ;n)を最大にする時間シフト値τ(max)を決定することができる。
【００５４】
1つの解釈では、時間シフト値τ(max)は、重畳が時間変数tの連続値へ拡張された場合、重畳値C(tk)が到達する最大値に対応する時間シフト値の推定値として識別される。
【００５５】
第２の解釈では、条件（１６Ａ）および（１６Ｂ）を課し、以下についての時間変数値t = tm'を決定あるいは計算する。
【００５６】
|tm' - τ| = min{|tm' - tm-1|,|tm' - tm|,|tm' - tm+1|}    （２３）
【００５７】
次いで、時間変数値tm'が時間シフト値として解釈され、これは最大重畳値を生ずる離散集合{tk}から引き出される。
【００５８】
第３の解釈では、条件（１６Ａ）および（１６Ｂ）を課し、以下についての時間変数値t = tm''を決定あるいは計算する。
【００５９】
C(tm'') = max {C(tm-1),C(tm),C(tm+1)},                      （２４）
【００６０】
これは通常ｔm''＝ｔmとなる。
【００６１】
時間シフト値t=τ(max)またはt=tm'またはt=tm''を、CDMA通信におけるもっとも可能性の高い時間シフト、フレーム同期化においてペイロード（データ）が開始する可能性のもっとも高いポイントを決定するために使用することができ、あるいは重畳信号の使用に関係するいかなる他の類似の目的にも使用することができる。
【図面の簡単な説明】
【図１】受信信号についての典型的な相関曲線のグラフ図である。
【図２】相関値を従来の手法によって計算するために使用されたゲート・アレイを例示する図である。
【図３】本発明の使用を説明する実施例において使用された、オーバーサンプリングされたＰＮコード値（±１）のオーバーラップするアレイを例示する図である。
【図４Ａ】図２における従来の手法に対応する、本発明による相関値を計算するために使用されたゲート・アレイを例示する図である。
【図４Ｂ】図２における従来の手法に対応する、本発明による相関値を計算するために使用されたゲート・アレイを例示する図である。
【図１】
0004495382.tif 000013
【図２】
0004495382.tif 000014
【図３】
0004495382.tif 000015
【図４Ａ】
0004495382.tif 000016
【図４Ｂ】
0004495382.tif 000017