(57)【要約】【課題】ＣＤＭＡ方式の逆拡散処理をソフトウェア的に実現する。【解決手段】受信回路２００が移動局からのＲＡＣＨプリアンブルを受信し、Ａ／Ｄ２０２は、デジタル形式の受信データに変換する。ＦＦＴ部３−１は、受信データをＦＦＴ処理し、ＦＦＴ結果Ａとする。ＲＡＣＨコード記憶部２４０は、ＲＡＣＨプリアンブルのコードを記憶し、ＦＦＴ部３−２は、ＲＡＣＨプリアンブルのコードをＦＦＴ処理し、ＦＦＴ結果Ｂとする。乗算部２２０は、ＦＦＴ結果ＡとＦＦＴ結果Ｂとを乗算する。ＩＦＦＴ部４は、乗算部２２０から入力された乗算結果をＩＦＦＴ処理し、遅延プロファイルとする。データ復号部２５０は、遅延プロファイルを用いて受信データを復号し、復号データとする。【選択図】　　　　　図７
2004032568.tif 000002
【特許請求の範囲】
【請求項１】
所定の符号を含む時間領域の第１の信号と、前記第１の信号と前記所定の符号との相関を検出する相関検出装置であって、
前記時間領域の第１の信号を、周波数領域に変換する変換手段と、
周波数領域に変換された前記所定の符号と、前記周波数領域に変換された第１の信号との相関を示す相関信号を生成する相関信号生成手段と、
前記生成された相関信号を、時間領域の信号に逆変換して、前記第１の信号と前記所定の符号との相関を検出する相関検出手段と
を有する相関検出装置。
【請求項２】
前記変換手段は、前記時間領域の第１の信号に対してフーリエ変換処理を行うことにより、前記第１の信号を周波数領域に変換し、
前記相関信号生成手段は、前記周波数領域に変換された所定の符号と、前記周波数領域に変換された第１の信号とを乗算して、前記相関信号を生成し、
前記相関検出手段は、前記生成された相関信号を、逆フーリエ変換して、前記第１の信号と前記所定の符号との相関を検出する
請求項１に記載の相関検出装置。
【請求項３】
連続したＭＮ（Ｍはフーリエ変換の基数；Ｎ＝１，２，．．．）個の記憶領域を用いて、ＭＮ個の時系列に続くデータに対して、Ｎ段のバタフライ演算を行うことによりフーリエ変換を行うフーリエ変換装置であって、
第（Ｉ；Ｉ＝０，１，．．．，ＭＮ−１）番目のデータを、第（ＭＮ−１（［Ｉ／Ｍ０］ｍｏｄＭ）＋ＭＮ−２（［Ｉ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｉ／ＭＮ−１］ｍｏｄＭ）；但し、［Ｘ］はＸを超えない整数，ＹｍｏｄＺは整数Ｙの整数Ｚに対する剰余系）番目の前記記憶領域に記憶させるデータ記憶手段と、
第（ＭＪ＋Ｈ；Ｊ＝０，１，．．．，ＭＮ−１−１，Ｈ＝０〜Ｍ−１）番目のＭ個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））番目のＭ個の前記記憶領域に記憶させる処理を（Ｎ−１）回、繰り返す第１のバタフライ演算処理手段と、
前記（Ｎ−１）回のバタフライ演算の結果として得られ、第（ＭＪ＋Ｈ）番目のＭ個の前記記憶領域に記憶されたデータに対して、バタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ）＋Ｈ）番目のＭ個の前記記憶領域に記憶させる処理を行う第２のバタフライ演算処理手段と
を有するフーリエ変換装置。
【請求項４】
連続したＭＮ（Ｍは逆フーリエ変換の基数；Ｎ＝１，２，．．．）個の記憶領域を用いて、ＭＮ個の時系列に続くデータに対して、Ｎ段のバタフライ演算を行うことにより逆フーリエ変換を行う逆フーリエ変換装置であって、
第（ＭＪ＋Ｈ；Ｊ＝０，１，．．．，ＭＮ−１−１，Ｈ＝０，１，．．．，Ｍ−１）番目のＭ個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋・・・＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））番目のＭ個の前記記憶領域に記憶させる処理を（Ｎ）回、繰り返す第３のバタフライ演算処理手段
を有する逆フーリエ変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＣＤＭＡ通信方式などにおいて、受信データと符号との相関を検出し、同期捕捉・追従を行うための相関検出装置、および、この装置に適したフーリエ変換装置に関する。
【０００２】
【従来の技術】
Ｗ−ＣＤＭＡ方式の基地局・移動局間の通信の際の同期捕捉・追従のためには、拡散された受信信号とコードとの相関を求める逆拡散処理（相関検出処理）が必要になり、この処理のためには、例えば、マッチトフィルタ（Ｍａｔｃｈｅｄ
Ｆｉｌｔｅｒ）が用いられている。
マッチトフィルタを用いて、ランダムアクセスチャネル（ＲＡＣＨ）のプリアンブル（ＲＡＣＨプリアンブル）を検出しようとすると、基地局・移動局間の信号伝送遅延のために、タップ数が多くなってしまうので、マッチトフィルタの回路規模が非常に大きくなる。
従って、ＲＡＣＨプリアンブルの検出を、ハードウェア的な処理のみにより行うことは難しい。
【０００３】
これに対し、ＤＳＰを用いて、ソフトウェア的に逆拡散処理を行い、ＲＡＣＨプリアンブルを検出する方法が考えられる。
このように、逆拡散処理をソフトウェア的に行うと、基地局・移動局の開発コストの軽減および高機能化が容易であるといった利点がある。
しかしながら、ＤＳＰによるＲＡＣＨプリアンブルの検出に、非常に多くの演算量が必要とされるので、従来、ソフトウェア的に、このような逆拡散処理を行うことは難しかった。
【０００４】
【発明が解決しようとする課題】
本発明は、上述した背景からなされたものであり、ＣＤＭＡ方式の逆拡散処理をソフトウェア的に実現することができる相関検出装置、および、この相関検出装置で用いられるフーリエ変換装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】
［相関検出装置］
上記課題を解決するために、本発明にかかる相関検出装置は、所定の符号を含む時間領域の第１の信号と、前記第１の信号と前記所定の符号との相関を検出する相関検出装置であって、前記時間領域の第１の信号を、周波数領域に変換する変換手段と、周波数領域に変換された前記所定の符号と、前記周波数領域に変換された第１の信号との相関を示す相関信号を生成する相関信号生成手段と、
前記生成された相関信号を、時間領域の信号に逆変換して、前記第１の信号と前記所定の符号との相関を検出する相関検出手段とを有する。
【０００６】
好適には、前記変換手段は、前記時間領域の第１の信号に対してフーリエ変換処理を行うことにより、前記第１の信号を周波数領域に変換し、前記相関信号生成手段は、前記周波数領域に変換された所定の符号と、前記周波数領域に変換された第１の信号とを乗算して、前記相関信号を生成し、前記相関検出手段は、前記生成された相関信号を、逆フーリエ変換して、前記第１の信号と前記所定の符号との相関を検出する。
【０００７】
［フーリエ変換装置］
また、本発明にかかるフーリエ変換装置は、連続したＭＮ（Ｍはフーリエ変換の基数；Ｎ＝１，２，．．．）個の記憶領域を用いて、ＭＮ個の時系列に続くデータに対して、Ｎ段のバタフライ演算を行うことによりフーリエ変換を行うフーリエ変換装置であって、第（Ｉ；Ｉ＝０，１，．．．，ＭＮ−１）番目のデータを、第（ＭＮ−１（［Ｉ／Ｍ０］ｍｏｄＭ）＋ＭＮ−２（［Ｉ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｉ／ＭＮ−１］ｍｏｄＭ）；但し、［Ｘ］はＸを超えない整数，ＹｍｏｄＺは整数Ｙの整数Ｚに対する剰余系）番目の前記記憶領域に記憶させるデータ記憶手段と、第（ＭＪ＋Ｈ；Ｊ＝０，１，．．．，ＭＮ−１−１，Ｈ＝０〜Ｍ−１）番目のＭ個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））番目のＭ個の前記記憶領域に記憶させる処理を（Ｎ−１）回、繰り返す第１のバタフライ演算処理手段と、前記（Ｎ−１）回のバタフライ演算の結果として得られ、第（ＭＪ＋Ｈ）番目のＭ個の前記記憶領域に記憶されたデータに対して、バタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ）＋Ｈ）番目のＭ個の前記記憶領域に記憶させる処理を行う第２のバタフライ演算処理手段とを有する。
【０００８】
［逆フーリエ変換装置］
また、本発明にかかる逆フーリエ変換装置は、連続したＭＮ（Ｍは逆フーリエ変換の基数；Ｎ＝１，２，．．．）個の記憶領域を用いて、ＭＮ個の時系列に続くデータに対して、Ｎ段のバタフライ演算を行うことにより逆フーリエ変換を行う逆フーリエ変換装置であって、第（ＭＪ＋Ｈ；Ｊ＝０，１，．．．，ＭＮ−１−１，Ｈ＝０，１，．．．，Ｍ−１）番目のＭ個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋・・・＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））番目のＭ個の前記記憶領域に記憶させる処理を（Ｎ）回、繰り返す第３のバタフライ演算処理手段を有する。
【０００９】
【発明の実施の形態】
［本発明の背景］
本発明の実施例の説明に先立ち、その理解を助けるために、本発明がなされるに至った背景を説明する。
図１は、Ｗ−ＣＤＭＡ方式の移動体通信システム１を例示する図である。
既に述べたように、例えば、図１に示すようなＷ−ＣＤＭＡ方式の移動体通信システム１において、拡散処理された信号を逆拡散処理（相関検出処理）するためには、従来、ハードウェア的に構成されたマッチトフィルタ・スライディングコリレータなどが用いられてきた。
移動体通信システム１において、ネットワーク１０を介して接続された基地局２−１〜２−３それぞれが受け持つセルの半径は、一定とは限らないので、基地局２−１〜２−３と移動局１２との間で伝送される拡散信号は、セルそれぞれの半径に応じて異なる遅延を受ける。
【００１０】
このような遅延の差異を吸収可能なほどにタップ数を多すると、マッチトフィルタの回路規模が非常に大きくなる。
例えば、移動局１２よりも大きな拡散利得が要求される基地局２−１〜２−３において、１０２４ｃｈｉｐｓの拡散利得を、マッチトフィルタを用いて得ようとすると、１ｃｈｉｐにつき４回ずつオーバーサンプリングした信号を処理するために、そのタップ数は４０９６にもなってしまう。
また、例えば、セル半径が５０ｋｍである場合には、基地局２〜移動局１２の間の伝送距離は往復で最長１００ｋｍにもなり、信号が１００ｋｍ伝送される間には２５６０ｃｈｉｐｓ（約６６６μｓ）分の遅延が加わる。
このような遅延が加わったＷ−ＣＤＭＡ信号を、マッチトフィルタを用いて逆拡散しようとすると、そのタップ数は１４３３６（＝（２５６０＋１０２４）×４（４はオーバーサンプリング））にもなる。
このように多数のタップを含むマッチトフィルタをハードウェア的に実現することは、現状、かなりの困難を伴う。
【００１１】
一方、例えば、ＤＳＰなどによるマッチトフィルタのソフトウェア的な実現は、演算量が非常に多いので、困難である。
本発明は、ソフトウェア的にマッチトフィルタの演算を行う代わりに、高速フーリエ変換（ＦＦＴ）および逆高速フーリエ変換（ＩＦＦＴ）の演算を行うことにより演算量を減らし、ＤＳＰなどを用いたソフトウェア的な逆拡散処理（相関検出処理）を可能にし、基地局２の「ソフトラジオ化」を可能にしている。
また、本発明は、ＦＦＴ・ＩＦＦＴのさらなる高速化、および、セルの半径に応じたＦＦＴ・ＩＦＦＴのサイズなどの最適化により、逆拡散処理に要する時間を短くし、ソフトウェア的な逆拡散処理の実現を容易にしている。
【００１２】
［ＦＦＴを用いた逆拡散処理］
まず、ＦＦＴ・ＩＦＦＴによる逆拡散処理について説明する。
マッチトフィルタを用いて行う逆拡散処理は、下式１により表される。
なお、下式１において、ｎは、ｃｈｉｐまたはサンプルを示し、ｍは、受信データとコードとのタイミング差を示し、ｙｍは、逆拡散結果を示し、χｎは、受信データを示し、γｎ＋ｍは、拡散コードの共役をとった数を示す。
【００１３】
ｙｍ＝Σχｎγｎ＋ｍ・・・（式１）、但し、Σはｎ＝０〜Ｎ−１までの総和を示す。
【００１４】
これに対し、式１に示したｙｎ，χｎ，γｎをＦＦＴ処理した値を、それぞれＹｋ，Χｋ，Ｖｋと表すと、ＦＦＴ処理における畳み込み演算は、下式２に示すように、単純なかけ算になる。
なお、下式２は、上式１を一般化したものであって、下式２におけるｎ，ｋは、ある特定の値を示さない。
【００１５】
Ｙｋ＝Χｋ×Ｖｋ・・・（式２）
【００１６】
式２に示したＹｋをＩＦＦＴ処理することにより、式１に示したｙｍを求めることができる。
【００１７】
受信信号を逆拡散処理して電力化し、時間軸上にプロットすると、遅延プロファイルが得られる。
なお、上記「電力化」とは、電圧で検出された信号を、相互に９０°位相が異なるＩ，Ｑの２つの信号とし、電力の次元のＩ２＋Ｑ２を求めることを意味する。Ｗ−ＣＤＭＡ方式においては、遅延を受けた信号波を有効に利用するためにＲＡＫＥ合成が行われ、このＲＡＫＥ合成のためには、プリアンブル（例えば、ランダムアクセスチャネル（ＲＡＣＨ）のＲＡＣＨプリアンブル）から得られる遅延プロファイルが用いられる。
以上の説明したように、ＲＡＣＨプリアンブルを逆拡散処理して遅延プロファイルを得るためには、ＲＡＣＨの受信信号をＦＦＴ処理して得られるＦＦＴ結果と、ＲＡＣＨプリアンブルのコードをＦＦＴして得られるＦＦＴ結果とを乗算し、さらに、ＩＦＦＴ処理すればよい。
【００１８】
このように、マッチトフィルタをＦＦＴ・ＩＦＦＴに置換すると、逆拡散処理の演算量を、数十分の一〜数百分の１（タップ数などにより異なる）とすることができ、ＤＳＰを用いたソフトウェア的な逆拡散処理が実現可能となる。
以下の説明においては、Ｗ−ＣＤＭＡ方式のＲＡＣＨプリアンブルの検出を行う場合を具体例とする。
【００１９】
［ＦＦＴ・ＩＦＦＴの高速化］
以上説明したように、ＦＦＴ・ＩＦＦＴ処理を用いることにより、ソフトウェア的な逆拡散処理が可能になる。
しかしながら、さらに、ＦＦＴ・ＩＦＦＴ処理の高速化を図ることができれば、ハードウェアに要求される性能を軽減することができ、より、システム構成に柔軟性を持たせることができる。
ここでは、本発明におけるＦＦＴ・ＩＦＦＴの高速化の手法を説明する。
【００２０】
図２は、一般的なＦＦＴ処理を示すフローチャートである。
図３は、一般的なＦＦＴ処理におけるデータの並びの変遷を示す変遷図である。
本発明にかかるＦＦＴ処理の基数は４に限定されず、また、段数も３に限定されないが、図示および説明の簡略化・具体化のために、以下の説明においては、基数４、３段のバタフライ演算を行うＦＦＴ・ＩＦＦＴ処理を具体例とする。
【００２１】
図２に示すように、一般的なＦＦＴ処理においては、まず、ビットリバース処理が実行されて、処理の対象となる時間領域の入力データが並び替えられる。
並び替えられた入力データに対して、３段のバタフライ演算が実行され、図３に示すように、この結果として得られる周波数領域の出力データは、正しい順番になる。
しかしながら、一般的なＦＦＴ処理においては、データの並びの変遷が複雑なので、ＤＳＰのレジスタ〜メモリ間のデータ転送は１ワード単位で行われなければならない。
【００２２】
図４は、本発明にかかるＦＦＴ処理を示す図である。
図５は、基数４のバタフライ演算を示す図である。
図６は、本発明にかかるＦＦＴ処理におけるデータの並びの変遷を示す変遷図である。
図４に示すように、ＦＦＴ処理における演算は、時間領域におけるビットを、図５に示すバタフライ演算により、周波数領域におけるビットに置き換えてゆく処理である。
ここで、ＤＳＰによる処理の特性として、メモリ〜ＤＳＰのレジスタ間で、１ワード単位のデータ転送を行うよりも、これらの間で、バタフライ演算の単位である４ワード単位のデータ転送を行う方が、全体として処理時間を大幅に短くすることができる。
【００２３】
基数４のＦＦＴ処理においては、６４個の記憶領域に記憶された６４個のデータに対して３段のバタフライ演算が行われる。
上記６４個の記憶領域が１６個ずつ４つの領域に分けて用いられ、１段目および２段目のバタフライ演算の４つの結果それぞれは、これら４つの領域において、４個ずつ離れた記憶領域に記憶される。
【００２４】
また、最終段（ここで示す例においては３段目）のバタフライ演算の結果は、ＬＳＢが入れ替えられずに並び替えられる。
つまり、最終段（３段目）のバタフライ演算の結果は、最下位ビットを除くビットでの展開になっている。
このように、バタフライ演算の結果を並び替えることにより、ＦＦＴ・ＩＦＦＴ処理におけるビットリバース処理を省略することができ、しかも、バタフライ演算において、メモリ〜ＤＳＰのレジスタ間のデータ転送を、１ワード単位ではなく、４ワード単位で行うことができるので、ＦＦＴ・ＩＦＦＴ処理に要する時間が大幅（数分の１）に短くなる。
【００２５】
なお、例えば、基数２のＦＦＴ処理に、本発明にかかるＦＦＴ処理・ＩＦＦＴ処理の高速化を適用する場合には、記憶領域を２分割して、２つのバタフライ演算結果それぞれが、２つの記憶領域それぞれにおいて、２つずつ離れた領域記憶されるようにすればよい。
また、例えば、基数８のＦＦＴ処理に、本発明にかかるＦＦＴ処理・ＩＦＦＴ処理の高速化を適用する場合には、記憶領域を８分割して、８つのバタフライ演算結果それぞれが、８つの記憶領域それぞれにおいて、８つずつ離れた領域記憶されるようにすればよい。
【００２６】
具体的には、基数４のＦＦＴ処理における３段のバタフライ演算に先だって、処理の対象となる６４個の入力データＤ（０）〜Ｄ（６３）それぞれは、下式３に示す順序で６４個の記憶領域Ｍ（０）〜Ｍ（６３）それぞれに記憶される。
【００２７】
Ｄ（Ｉ）→Ｒ（ＭＮ−１（［Ｉ／Ｍ０］ｍｏｄＭ）＋ＭＮ−２（［Ｉ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｉ／ＭＮ−１］ｍｏｄＭ）・・・（式３）、但し、Ｎ＝１，２，３・・・、基数４のＦＦＴの場合、Ｍ＝４、Ｉ＝０〜ＭＮ−１であって、［Ｘ］はＸを超えない整数、ＹｍｏｄＺは整数Ｙの整数Ｚに対する剰余系である（以下同じ）。
【００２８】
また、基数４のＦＦＴ処理における１段目および２段目のバタフライ演算それぞれの４つの結果Ｒ（０）〜Ｒ（３），・・・，Ｒ（６０）〜Ｒ（６３）それぞれは、下式４に示す順序で６４個のメモリ領域０〜６３に記憶される。
【００２９】
Ｂ（ＭＪ＋Ｈ）→Ｒ（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋・・・＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））・・・（式４）、但し、基数４のＦＦＴの場合、Ｊ＝０〜ＭＮ−１−１、Ｈ＝０〜３である（以下同じ）。
【００３０】
また、基数４のＦＦＴ処理における最終段（３段目）のバタフライ演算それぞれの４つの結果Ｒ（０）〜Ｒ（３），・・・，Ｒ（６０）〜Ｒ（６３）それぞれは、下式５に示す順序で６４個のメモリ領域Ｒ（０）〜Ｒ（６３）に記憶される。
【００３１】
Ｂ（ＭＪ＋Ｈ）→Ｒ（ＭＮ−１（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ）＋Ｈ）・・・（式５）
【００３２】
また、基数４のＩＦＦＴ処理における３段のバタフライ演算に先だって、処理の対象となる６４個の入力データＤ（０）〜Ｄ（６３）それぞれは、下式６に示す順序に並び替えられ、６４個の記憶領域Ｒ（０）〜Ｒ（６３）それぞれに記憶される。
なお、下に述べる実施例においては、ＦＦＴ結果の並び順が、ＩＦＦＴ処理の対象となるデータの並び順に適合しているので、この並び替えは行われない。
つまり、式５に示した処理が行われる場合には、下式６に示す処理は省略される。
【００３３】
Ｄ（Ｉ）→Ｒ（ＭＮ−１（｛Ｉ／Ｍ０］ｍｏｄＭ）＋ＭＮ−２（［Ｉ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｉ／ＭＮ−１］ｍｏｄＭ）・・・（式６）
【００３４】
また、基数４のＩＦＦＴ処理における１段目〜最終段（３段目）のバタフライ演算それぞれの４つの結果Ｂ（０）〜Ｂ（３），・・・，Ｂ（６０）〜Ｂ（６３）それぞれは、下式７に示す順序で６４個のメモリ領域０〜６３に記憶される。
【００３５】
Ｄ（ＮＪ＋Ｈ）→Ｒ（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））・・・（式７）
【００３６】
［実施例］
以下、ＦＦＴ・ＩＦＦＴを用いた逆拡散処理、および、ＦＦＴ・ＩＦＦＴの高速化を説明する。
図７は、図１に示した基地局２のハードウェアおよびソフトウェア構成を示す図である。
図７に示すように、移動体通信システム１（図１）の基地局２は、受信部２０および送信部２１０を含む。
受信部２０は、受信回路２００、アナログ／デジタル変換回路（Ａ／Ｄ）２０２、遅延プロファイル検出部２２およびデータ復号部２５０から構成される。
【００３７】
図８は、図７に示した受信部２０のハードウェア構成を示す図である。
なお、遅延プロファイル検出部２２（図２）は、例えば、受信部２０のＤＳＰ回路２６（図３）のＲＯＭ２６４に記憶され、ＤＳＰ２６２により実行されるソフトウェアとして実現される。
また、受信回路２００（図７）、Ａ／Ｄ２０２およびデータ復号部２５０は、専用のハードウェアおよびＤＳＰ回路２６（図８）により実行されるソフトウェアまたはこれらのいずれかにより、適宜、実現される。
【００３８】
遅延プロファイル検出部２２は、第１の高速フーリエ変換部（ＦＦＴ部）３−１、逆高速フーリエ変換部（ＩＦＦＴ部）４、乗算部２２０およびコード発生部２４から構成される。
コード発生部２４は、単にＲＡＣＨプリアンブルのコードをＦＦＴ処理して得られるＦＦＴ結果を、ＲＯＭ２６４またはＲＡＭ２６６に記憶することにより実現してもよいが、以下の説明においては、ＲＡＣＨコード記憶部２４０および第２のＦＦＴ部３−２を含む場合を具体例とする。
遅延プロファイル検出部２２の各構成部分は、例えば、それぞれ独立したソフトウェアモジュールとして作成され、必要に応じて、適宜、追加あるいは削除されうるようになっており、ＯＳ（図示せず）などにより、任意のタイミングで起動されうる。
【００３９】
［送信部２１０］
送信部２１０（図７）は、ネットワーク１０（図１）などから供給される送信データを送信する。
【００４０】
［受信回路２００］
受信回路２００（図７，図８）は、移動局１２から信号を受信し、ベースバンドの信号に復調してＡ／Ｄ２０２に対して出力する。
【００４１】
［Ａ／Ｄ２０２］
Ａ／Ｄ２０２は、受信回路２００から入力されたアナログ形式のベースバンド信号を、デジタル形式の受信データに変換し、遅延プロファイル検出部２２のＦＦＴ部３−１およびデータ復号部２５０に対して出力する。
【００４２】
［データ復号部２５０］
データ復号部２５０は、遅延プロファイル検出部２２から入力される遅延プロファイルを用いて受信データを復号し、復号データとしてネットワーク１０（図１）などに対して出力する。
【００４３】
［遅延プロファイル検出部２２］
遅延プロファイル検出部２２は、Ａ／Ｄ２０２から入力される受信データに含まれるＲＡＣＨのＲＡＣＨプリアンブルを、図２〜６を参照して上述したように、ＦＦＴ・ＩＦＦＴ処理を用いて逆拡散し、遅延プロファイルを生成してデータ復号部２５０に対して出力する。
以下、遅延プロファイル検出部２２の各構成部分をさらに説明する。
【００４４】
［ＦＦＴ部３−１］
図９は、図７に示した第１のＦＦＴ部３−１の処理およびデータの並びの変遷を示す図である。
第１のＦＦＴ部３−１は、Ａ／Ｄ２０２から入力される６４ポイントの受信データに対して、順次、基数４・３段のバタフライ演算を実行してＦＦＴ変換処理を行い、ＦＦＴ変換処理の結果として得られたＦＦＴ結果Ａを、乗算部２２０に対して出力する。
以下、ＦＦＴ部３−１の処理を段階ごとに、さらに詳しく説明する。
【００４５】
［受信データの記憶］
遅延プロファイル検出部２２において、ＦＦＴ部３−１は、Ａ／Ｄ２０２から入力された６４ポイントの受信データＤ（Ｉ；Ｉ＝０〜６３）を、式３を参照して上述した順番で、ＲＡＭ２６６（図８）に受信データＤ（Ｉ）の数に応じて６４個、連続した領域に設けられた記憶領域Ｒ（Ｉ’；Ｉ’＝０〜６３）に記憶する。
つまり、ＦＦＴ部３−１は、受信データＤ（０）〜Ｄ（６３）それぞれを、図９の左端に示すように、記憶領域Ｒ（０），Ｒ（１６），Ｒ（３２），Ｒ（４８），Ｒ（１），・・・Ｒ（６３）に記憶する。
この受信データ記憶処理により、受信データＤ（Ｉ）の順番は、図９の左端に示す通り、「ねじれた」状態になる。
以下、説明を具体化・明確化のために、ＦＦＴ部３−１が処理するデータそれぞれが、ＤＳＰ２６２にとって１ワードである場合を説明する。
【００４６】
［第１段目のバタフライ演算］
図９の左端〜左から２番目の間に示すように、ＦＦＴ部３−１は、ＲＡＭ２６６の連続する１６×４個の記憶領域Ｒ（０）〜Ｒ（３），Ｒ（４）〜Ｒ（７），・・・，Ｒ（６０）〜Ｒ（６３）それぞれに記憶された１６×４個の受信データ［Ｄ（０），Ｄ（１６），Ｄ（３２），Ｄ（４８）］，［Ｄ（４），Ｄ（２０），Ｄ（３６），Ｄ（５２）］，・・・，［Ｄ（１５），Ｄ（３１），Ｄ（４７），Ｄ（６３）］それぞれを、４ワード単位で一度に読み出す。
【００４７】
さらに、図９の左端〜左から２番目の間に示したように、ＦＦＴ部３−１は、読み出した１６×４個の受信データ［Ｄ（０），Ｄ（１６），Ｄ（３２），Ｄ（４８）］，［Ｄ（４），Ｄ（２０），Ｄ（３６），Ｄ（５２）］，・・・，［Ｄ（１５），Ｄ（３１），Ｄ（４７），Ｄ（６３）］に対して、図５に示した第１段目のバタフライ演算を行い、それぞれの演算の結果として、１６×４個の演算結果［Ｂ（０）〜Ｂ（３）］，［Ｂ（４）〜Ｂ（７）］，・・・，［Ｂ（６０）〜Ｂ（６３）］それぞれを得る。
【００４８】
さらに、ＦＦＴ部３−１は、１６×４個の演算結果［Ｂ（０）〜Ｂ（３）］，［Ｂ（４）〜Ｂ（７）］，・・・，［Ｂ（６０）〜Ｂ（６３）それぞれを、式４を参照して上述した順番で、ＲＡＭ２６６に設けられた６４個の記憶領域Ｒ’（０）〜Ｒ’（６３）それぞれに記憶する。
つまり、図９の２番目の間に示すように、ＦＦＴ部３−１は、図９の左端〜左から２番目の間に示したように、１６×４個の演算結果［Ｂ（０）〜Ｂ（３）］，［Ｂ（４）〜Ｂ（７）］，・・・，［Ｂ（６０）〜Ｂ（６３）それぞれを、記憶領域［Ｒ’（０），Ｒ’（１６），Ｒ’（３２），Ｒ’（４８）］，［Ｒ’（４），Ｒ’（２０），Ｒ’（３６），Ｒ’（５２）］，・・・，［Ｒ’（１５），Ｒ’（３１），Ｒ’（４７），Ｒ’（６３）］に記憶する。
【００４９】
［第２段目のバタフライ演算］
図９の左から２〜３番目の間に示すように、ＦＦＴ部３−１は、ＲＡＭ２６６の連続する１６×４個の記憶領域Ｒ’（０）〜Ｒ’（３），Ｒ’（４）〜Ｒ’（７），・・・，Ｒ’（６０）〜Ｒ’（６３）それぞれに記憶された１６×４個のバタフライ演算結果［Ｂ（０），Ｂ（１６），Ｂ（３２），Ｂ（４８）］，［Ｂ（４），Ｂ（２０），Ｂ（３６），Ｂ（５２）］，・・・，［Ｂ（１５），Ｂ（３１），Ｂ（４７），Ｂ（６３）］それぞれを、４ワード単位で一度に読み出す。
【００５０】
さらに、図９の左から２〜３番目の間に示したように、ＦＦＴ部３−１は、読み出した１６×４個のバタフライ演算結果［Ｂ（０），Ｂ（１６），Ｂ（３２），Ｂ（４８）］，［Ｂ（４），Ｂ（２０），Ｂ（３６），Ｂ（５２）］，・・・，［Ｂ（１５），Ｂ（３１），Ｂ（４７），Ｂ（６３）］に対して、図５に示した第２段目のバタフライ演算を行い、それぞれの演算の結果として、１６×４個の演算結果［Ｂ’（０）〜Ｂ’（３）］，［Ｂ’（４）〜Ｂ’（７）］，・・・，［Ｂ’（６０）〜Ｂ’（６３）］それぞれを得る。
【００５１】
さらに、ＦＦＴ部３−１は、１６×４個の演算結果［Ｂ’（０）〜Ｂ’（３）］，［Ｂ’（４）〜Ｂ’（７）］，・・・，［Ｂ’（６０）〜Ｂ’（６３）それぞれを、式４を参照して上述した順番で、ＲＡＭ２６６に設けられた６４個の記憶領域Ｒ”（０）〜Ｒ”（６３）それぞれに記憶する。
つまり、図９の左から２番目の間に示すように、ＦＦＴ部３−１は、図９の左から３番目に示すように、１６×４個の演算結果［Ｂ’（０）〜Ｂ’（３）］，［Ｂ’（４）〜Ｂ’（７）］，・・・，［Ｂ’（６０）〜Ｂ’（６３）それぞれを、記憶領域［Ｒ”（０），Ｒ”（１６），Ｒ”（３２），Ｒ”（４８）］，［Ｒ”（４），Ｒ”（２０），Ｒ”（３６），Ｒ”（５２）］，・・・，［Ｒ”（１５），Ｒ”（３１），Ｒ”（４７），Ｒ”（６３）］に記憶する。
【００５２】
［最終段（第３段目）のバタフライ演算］
図９の左から３〜４番目の間に示すように、ＦＦＴ部３−１は、ＲＡＭ２６６の連続する１６×４個の記憶領域Ｒ”（０）〜Ｒ”（３），Ｒ”（４）〜Ｒ”（７），・・・，Ｒ”（６０）〜Ｒ”（６３）それぞれに記憶された１６×４個のバタフライ演算結果［Ｂ’（０），Ｂ’（１６），Ｂ’（３２），Ｂ’（４８）］，［Ｂ’（４），Ｂ’（２０），Ｂ’（３６），Ｂ’（５２）］，・・・，［Ｂ’（１５），Ｂ’（３１），Ｂ’（４７），Ｂ’（６３）］それぞれを、４ワード単位で一度に読み出す。
【００５３】
さらに、図９の左から３番目〜４番目の間に示したように、ＦＦＴ部３−１は、読み出した１６×４個のバタフライ演算結果［Ｂ’（０），Ｂ’（１６），Ｂ’（３２），Ｂ’（４８）］，［Ｂ’（４），Ｂ’（２０），Ｂ’（３６），Ｂ’（５２）］，・・・，［Ｂ’（１５），Ｂ’（３１），Ｂ’（４７），Ｂ’（６３）］に対して、図５に示した最終段（第３段目）のバタフライ演算を行い、それぞれの演算の結果として、１６×４個の演算結果［Ｂ”（０）〜Ｂ”（３）］，［Ｂ”（４）〜Ｂ”（７）］，・・・，［Ｂ”（６０）〜Ｂ”（６３）］それぞれを得る。
【００５４】
さらに、ＦＦＴ部３−１は、１６×４個の演算結果［Ｂ”（０）〜Ｂ”（３）］，［Ｂ”（４）〜Ｂ”（７）］，・・・，［Ｂ”（６０）〜Ｂ”（６３）それぞれを、式５を参照して上述した順番で、ＲＡＭ２６６に設けられた６４個の記憶領域Ｒ”’（０）〜Ｒ”’（６３）それぞれに記憶する。
つまり、図９の左から４番目に示すように、ＦＦＴ部３−１は、図９の左３〜４番目の間に示したように、１６×４個の演算結果［Ｂ”（０）〜Ｂ”（３）］，［Ｂ”（４）〜Ｂ”（７）］，・・・，［Ｂ”（６０）〜Ｂ”（６３）それぞれを、記憶領域［Ｒ”’（０）〜Ｂ（３）］，［Ｒ”’（１６）〜（２０），・・・，［Ｒ”’（６０）〜Ｒ”’（６３）］に記憶する。
このように、最終段（第３段目）のバタフライ演算の結果のみ、第２段目および最終段（第３段目）のバタフライ演算の結果とは異なる並び順でＲＡＭ２６６に記憶される理由は、ＦＦＴ部３−１が出力するＦＦＴ結果の並び順を、ＩＦＦＴ部４の入力データとしての並び順に適合させるためである。
【００５５】
さらに、図１０を参照して、第１のＦＦＴ部３−１（図７）による第１〜３段目（最終段）のバタフライ演算処理（図９）を説明する。
図１０は、第１のＦＦＴ部３−１（図７）による第１〜３段目（最終段）のバタフライ演算処理（Ｓ１０）を示すフローチャートである。
図１０に示すように、図９の左端に示した受信データの記憶処理が終わると、ステップ１００−１（Ｓ１００−１）において、ＦＦＴ部３−１は、第１段目のバタフライ演算を行う。
【００５６】
ステップ１０２（Ｓ１０２）において、ＦＦＴ部３−１（図７）の処理を実行中のＤＳＰ２６２（図８）は、ＲＡＭ２６６の連続した４ワードの記憶領域に記憶された受信データＤ（Ｉ）を、４ワード単位でレジスタに転送する。
【００５７】
ステップ１０４（Ｓ１０４）において、ＤＳＰ２６２は、図５に示したバタフライ演算を行う。
【００５８】
ステップ１０６（Ｓ１０６）において、ＤＳＰ２６２は、図９の左端〜左から２番目の間に示したように、バタフライ演算結果を、４ワード単位でレジスタからＲＡＭ２６６の記憶領域に転送し、記憶させる。
この４ワード単位の転送は、複数のバタフライ演算を同時に行うことにより、あるいは、結果をＤＳＰ２６２のレジスタにストックしておくことにより実現される。
【００５９】
ステップ１０８（Ｓ１０８）において、ＤＳＰ２６２は、受信データの全てのポイントについてＳ１０２〜Ｓ１０６の処理が終了したか否かを判断し、処理が終了した場合には次段のバタフライ演算処理に進み、これ以外の場合にはＳ１０２の処理に戻る。
【００６０】
ステップ１００−２（Ｓ１００−２）において、ＤＳＰ２６２は、Ｓ１００−１の処理と同様に、第２段目のバタフライ演算処理を行う。
【００６１】
、ステップ１００−３（Ｓ１００−３）において、ＤＳＰ２６２は、最終段（第３段目）のバタフライ演算を行う。
【００６２】
ステップ１１２（Ｓ１１２）において、ＤＳＰ２６２（図８）は、Ｓ１０２の処理においてと同様に、第２段目のバタフライ演算の結果Ｂ’を、４ワード単位でレジスタに転送する。
【００６３】
ステップ１１４（Ｓ１１４）において、ＤＳＰ２６２は、Ｓ１０４の処理においてと同様に、図５に示したバタフライ演算を行う。
【００６４】
ステップ１１６（Ｓ１１６）において、ＤＳＰ２６２は、図９の左から３〜４番目の間に示したように、バタフライ演算結果を、式５を参照して上述したように、４ワード単位でレジスタからＲＡＭ２６６の記憶領域に転送し、記憶させる。
【００６５】
ステップ１１８（Ｓ１１８）において、ＤＳＰ２６２は、Ｓ１０８の処理においてと同様に、受信データの全てのポイントについてＳ１０２〜Ｓ１０６の処理が終了したか否かを判断し、処理が終了した場合には処理を終了し、これ以外の場合にはＳ１１２の処理に戻る。
【００６６】
［コード発生部２４］
コード発生部２４において、ＲＡＣＨコード記憶部２４０は、ＲＡＣＨプリアンブルのコードを記憶し、ＦＦＴ部３−２に対して出力する。
ＦＦＴ部３−２は、ＲＡＣＨコード記憶部２４０から入力されたＲＡＣＨプリアンブルのコードをＦＦＴ処理し、ＦＦＴ結果Ｂとして乗算部２２０に対して出力する。
【００６７】
［乗算部２２０］
乗算部２２０は、ＦＦＴ部３−１およびコード発生部２４から入力されたＦＦＴ結果ＡとＦＦＴ結果Ｂとを乗算し、乗算結果として得られるをＩＦＦＴ部４に対して出力する。
つまり、乗算部２２０は、ＦＦＴ結果ＡとＦＦＴ結果Ｂとを乗算することにより、式２を参照して上述した畳み込み演算を実現する。
【００６８】
［ＩＦＦＴ部４］
図１１は、図７に示した第１のＩＦＦＴ部４の処理およびデータの並びの変遷を示す図である。
第１のＩＦＦＴ部４は、乗算部２２０から入力される６４ポイントの乗算結果に対して、順次、基数４・３段のバタフライ演算を実行してＩＦＦＴ変換処理を行い、ＩＦＦＴ変換処理の結果として得られた遅延プロファイルを、データ復号部２５０に対して出力する。
【００６９】
以下、ＩＦＦＴ部４の処理を段階ごとに、さらに詳しく説明する。
上述したように、ＦＦＴ部３−１，３−２（図７）が出力するＦＦＴ結果ＡおよびＦＦＴ結果Ｂの並び順（図９の左から４番目（右端））と、ＩＦＦＴ部４に入力されるデータの並び順（図１１左端）と同じである。
従って、遅延プロファイル検出部２２においては、式６を参照して上述したＩＦＦＴ部４のデータの並び替え処理は、ＦＦＴ部３−１，３−２によるＳ１１６（図１０）で代用されている。
従って、ＩＦＦＴ部４においては、ＦＦＴ部３−１，３−２の処理におけるような、データの並び替えは必要とされない。
【００７０】
［第１段目のバタフライ演算］
図１１の左端〜左から２番目の間に示すように、ＩＦＦＴ部４は、乗算部２２０から入力される１６×４個の乗算結果データ［Ｐ（０），Ｐ（１６），Ｐ（３２），Ｐ（４８）］，［Ｐ（４），Ｐ（２０），Ｐ（３６），Ｐ（５２）］，・・・，［Ｐ（１５），Ｐ（３１），Ｐ（４７），Ｐ（６３）］それぞれを、４ワード単位で一度に読み出す。
【００７１】
さらに、図１１の左端〜左から２番目の間に示したように、ＩＦＦＴ部４は、読み出した１６×４個の受信データ［Ｐ（０），Ｐ（１６），Ｐ（３２），Ｐ（４８）］，［Ｐ（４），Ｐ（２０），Ｐ（３６），Ｐ（５２）］，・・・，［Ｐ（１５），Ｐ（３１），Ｐ（４７），Ｐ（６３）］に対して、図５に示した第１段目のバタフライ演算を行い、それぞれの演算の結果として、１６×４個の演算結果［Ｂ（０）〜Ｂ（３）］，［Ｂ（４）〜Ｂ（７）］，・・・，［Ｂ（６０）〜Ｂ（６３）］それぞれを得る。
【００７２】
さらに、ＩＦＦＴ部４は、１６×４個の演算結果［Ｂ（０）〜Ｂ（３）］，［Ｂ（４）〜Ｂ（７）］，・・・，［Ｂ（６０）〜Ｂ（６３）それぞれを、式７を参照して上述した順番で、ＲＡＭ２６６に設けられた６４個の記憶領域Ｒ’（０）〜Ｒ’（６３）それぞれに記憶する。
つまり、図１１の２番目の間に示すように、ＩＦＦＴ部４は、図１１の左端〜左から２番目の間に示したように、１６×４個の演算結果［Ｂ（０）〜Ｂ（３）］，［Ｂ（４）〜Ｂ（７）］，・・・，［Ｂ（６０）〜Ｂ（６３）それぞれを、記憶領域［Ｒ’（０），Ｒ’（１６），Ｒ’（３２），Ｒ’（４８）］，［Ｒ’（４），Ｒ’（２０），Ｒ’（３６），Ｒ’（５２）］，・・・，［Ｒ’（１５），Ｒ’（３１），Ｒ’（４７），Ｒ’（６３）］に記憶する。
【００７３】
［第２段目のバタフライ演算］
図１１の左から２〜３番目の間に示すように、ＩＦＦＴ部４は、ＲＡＭ２６６の連続する１６×４個の記憶領域Ｒ’（０）〜Ｒ’（３），Ｒ’（４）〜Ｒ’（７），・・・，Ｒ’（６０）〜Ｒ’（６３）それぞれに記憶された１６×４個のバタフライ演算結果［Ｂ（０），Ｂ（１６），Ｂ（３２），Ｂ（４８）］，［Ｂ（４），Ｂ（２０），Ｂ（３６），Ｂ（５２）］，・・・，［Ｂ（１５），Ｂ（３１），Ｂ（４７），Ｂ（６３）］それぞれを、４ワード単位で一度に読み出す。
【００７４】
さらに、図１１の左から２〜３番目の間に示したように、ＩＦＦＴ部４は、読み出した１６×４個のバタフライ演算結果［Ｂ（０），Ｂ（１６），Ｂ（３２），Ｂ（４８）］，［Ｂ（４），Ｂ（２０），Ｂ（３６），Ｂ（５２）］，・・・，［Ｂ（１５），Ｂ（３１），Ｂ（４７），Ｂ（６３）］に対して、図５に示した第２段目のバタフライ演算を行い、それぞれの演算の結果として、１６×４個の演算結果［Ｂ’（０）〜Ｂ’（３）］，［Ｂ’（４）〜Ｂ’（７）］，・・・，［Ｂ’（６０）〜Ｂ’（６３）］それぞれを得る。
【００７５】
さらに、ＩＦＦＴ部４は、１６×４個の演算結果［Ｂ’（０）〜Ｂ’（３）］，［Ｂ’（４）〜Ｂ’（７）］，・・・，［Ｂ’（６０）〜Ｂ’（６３）それぞれを、式７を参照して上述した順番で、ＲＡＭ２６６に設けられた６４個の記憶領域Ｒ”（０）〜Ｒ”（６３）それぞれに記憶する。
つまり、図１１の左から２番目の間に示すように、ＩＦＦＴ部４は、図１１の左から３番目に示すように、１６×４個の演算結果［Ｂ’（０）〜Ｂ’（３）］，［Ｂ’（４）〜Ｂ’（７）］，・・・，［Ｂ’（６０）〜Ｂ’（６３）それぞれを、記憶領域［Ｒ”（０），Ｒ”（１６），Ｒ”（３２），Ｒ”（４８）］，［Ｒ”（４），Ｒ”（２０），Ｒ”（３６），Ｒ”（５２）］，・・・，［Ｒ”（１５），Ｒ”（３１），Ｒ”（４７），Ｒ”（６３）］に記憶する。
【００７６】
［最終段（第３段目）のバタフライ演算］
図１１の左から３〜４番目の間に示すように、ＩＦＦＴ部４は、ＲＡＭ２６６の連続する１６×４個の記憶領域Ｒ”（０）〜Ｒ”（３），Ｒ”（４）〜Ｒ”（７），・・・，Ｒ”（６０）〜Ｒ”（６３）それぞれに記憶された１６×４個のバタフライ演算結果［Ｂ’（０），Ｂ’（１６），Ｂ’（３２），Ｂ’（４８）］，［Ｂ’（４），Ｂ’（２０），Ｂ’（３６），Ｂ’（５２）］，・・・，［Ｂ’（１５），Ｂ’（３１），Ｂ’（４７），Ｂ’（６３）］それぞれを、４ワード単位で一度に読み出す。
【００７７】
さらに、図１１の左から３番目〜４番目の間に示したように、ＩＦＦＴ部４は、読み出した１６×４個のバタフライ演算結果［Ｂ’（０），Ｂ’（１６），Ｂ’（３２），Ｂ’（４８）］，［Ｂ’（４），Ｂ’（２０），Ｂ’（３６），Ｂ’（５２）］，・・・，［Ｂ’（１５），Ｂ’（３１），Ｂ’（４７），Ｂ’（６３）］に対して、図５に示した最終段（第３段目）のバタフライ演算を行い、それぞれの演算の結果として、１６×４個の演算結果［Ｂ”（０）〜Ｂ”（３）］，［Ｂ”（４）〜Ｂ”（７）］，・・・，［Ｂ”（６０）〜Ｂ”（６３）］それぞれを得る。
【００７８】
さらに、ＩＦＦＴ部４は、１６×４個の演算結果［Ｂ”（０）〜Ｂ”（３）］，［Ｂ”（４）〜Ｂ”（７）］，・・・，［Ｂ”（６０）〜Ｂ”（６３）それぞれを、式７を参照して上述した順番で、ＲＡＭ２６６に設けられた６４個の記憶領域Ｒ”’（０）〜Ｒ”’（６３）それぞれに記憶する。
つまり、図１１の左から４番目に示すように、ＩＦＦＴ部４は、図１１の左から３〜４番目の間に示したように、１６×４個の演算結果［Ｂ”（０）〜Ｂ”（３）］，［Ｂ”（４）〜Ｂ”（７）］，・・・，［Ｂ”（６０）〜Ｂ”（６３）それぞれを、記憶領域［Ｒ”’（０），Ｒ”’（１６），Ｒ”’（３２），Ｒ”’（４８）］，［Ｒ”’（４），Ｒ”’（２０），Ｒ”’（３６），Ｒ”’（５２）］，・・・，［Ｒ”’（１５），Ｒ”’（３１），Ｒ”’（４７），Ｒ”’（６３）］に記憶する。
ＦＦＴ部３−１，３−２の処理においてとは異なり、ＩＦＦＴ部４の処理において、最終段（第３段目）のバタフライ演算の結果を、第１段目および第２段目と同じに並び替える理由は、この並び替えにより、図１１の左から４番目（右端）に示すように、ＩＦＦＴの結果として得られる遅延プロファイルが正しい順番となるからである。
【００７９】
さらに、図１２を参照して、第１のＩＦＦＴ部４（図７）による第１〜３段目（最終段）のバタフライ演算処理（図１１）を説明する。
図１２は、第１のＩＦＦＴ部４（図７）による第１〜３段目（最終段）のバタフライ演算処理を示すフローチャートである。
図１２に示すように、図１１の左端に示した受信データの記憶処理が終わると、ステップ１２０−１（Ｓ１２０−１）において、Ｓ１００−１（図１０）の処理においてと同様に、ＩＦＦＴ部４は、第１段目のバタフライ演算を行う。
【００８０】
ステップ１２２（Ｓ１２２）において、Ｓ１０２の処理においてと同様に、ＩＦＦＴ部４（図７）の処理を実行中のＤＳＰ２６２（図８）は、ＲＡＭ２６６の連続した４ワードの記憶領域に記憶された受信データＤ（Ｉ）を、４ワード単位でレジスタに転送する。
【００８１】
ステップ１２４（Ｓ１２４）において、Ｓ１０４の処理においてと同様に、ＤＳＰ２６２は、図５に示したバタフライ演算を行う。
【００８２】
ステップ１２６（Ｓ１２６）において、Ｓ１０６の処理においてと同様に、ＤＳＰ２６２は、図１１の左端〜左から２番目の間に示したように、バタフライ演算結果を、４ワード単位でレジスタからＲＡＭ２６６の記憶領域に転送し、記憶させる。
この４ワード単位の転送は、Ｓ１０６の処理においてと同様に実現される。
【００８３】
ステップ１２８（Ｓ１２８）において、Ｓ１０８の処理においてと同様に、ＤＳＰ２６２は、受信データの全てのポイントについてＳ１２２〜Ｓ１２６の処理が終了したか否かを判断し、処理が終了した場合には次段のバタフライ演算処理に進み、これ以外の場合にはＳ１２２の処理に戻る。
【００８４】
ステップ１２０−２（Ｓ１２０−２）において、ＤＳＰ２６２は、Ｓ１２０−１の処理と同様に、第２段目のバタフライ演算処理を行う。
【００８５】
、ステップ１２０−３（Ｓ１２０−３）において、ＤＳＰ２６２は、Ｓ１２０−１の処理と同様に、第３段目（最終段）のバタフライ演算処理を行う。
【００８６】
［全体動作］
以下、基地局２（図１，図７，図８）の受信部２０の全体的な動作を説明する。
基地局２の受信部２０（図７，図８）の受信回路２００が移動局１２（図１）からのＲＡＣＨプリアンブルを受信し、ベースバンド信号としてＡ／Ｄ２０２に対して出力し、Ａ／Ｄ２０２は、ベースバンド信号をデジタル形式の受信データに変換して遅延プロファイル検出部２２に対して出力する。
【００８７】
遅延プロファイル検出部２２において、ＦＦＴ部３−１は、受信データをＦＦＴ処理し、ＦＦＴ結果Ａとして乗算部２２０に対して出力する。
コード発生部２４において、ＲＡＣＨコード記憶部２４０は、記憶したＲＡＣＨプリアンブルのコードをＦＦＴ部３−２に対して出力し、ＦＦＴ部３−２は、ＲＡＣＨプリアンブルのコードをＦＦＴ処理し、ＦＦＴ結果Ｂとして乗算部２２０に対して出力する。
【００８８】
乗算部２２０は、ＦＦＴ部３−１から入力されたＦＦＴ結果Ａと、コード発生部２４のＦＦＴ部３−２から入力されたＦＦＴ結果Ｂとを乗算し、乗算結果をＩＦＦＴ部４に対して出力する。
ＩＦＦＴ部４は、乗算部２２０から入力された乗算結果をＩＦＦＴ処理し、遅延プロファイルとしてデータ復号部２５０に対して出力する。
データ復号部２５０は、ＩＦＦＴ部４から入力された遅延プロファイルを用いて、Ａ／Ｄ２０２から入力された受信データを復号し、復号データとしてネットワーク１０（図１）などに対して出力する。
［まとめ］
なお、本願明細書および図面には、以下の発明が開示されている。
（１）所定の符号を含む時間領域の第１の信号と、前記第１の信号と前記所定の符号との相関を検出する相関検出装置であって、
前記時間領域の第１の信号を、周波数領域に変換する変換手段と、
周波数領域に変換された前記所定の符号と、前記周波数領域に変換された第１の信号との相関を示す相関信号を生成する相関信号生成手段と、
前記生成された相関信号を、時間領域の信号に逆変換して、前記第１の信号と前記所定の符号との相関を検出する相関検出手段と
を有する相関検出装置。
【００８９】
（２）前記変換手段は、前記時間領域の第１の信号に対してフーリエ変換処理を行うことにより、前記第１の信号を周波数領域に変換し、
前記相関信号生成手段は、前記周波数領域に変換された所定の符号と、前記周波数領域に変換された第１の信号とを乗算して、前記相関信号を生成し、
前記相関検出手段は、前記生成された相関信号を、逆フーリエ変換して、前記第１の信号と前記所定の符号との相関を検出する
（１）に記載の相関検出装置。
【００９０】
（３）前記第１の信号は、ＣＤＭＡ信号であって、前記所定の符号はプリアンブルであって、
前記変換手段は、前記ＣＤＭＡ信号に対してフーリエ変換処理を行って、前記ＣＤＭＡ信号のＦＦＴ演算を行い、
前記相関信号生成手段は、前記生成されたＣＤＭＡ信号のＦＦＴ演算結果と、前記プリアンブルに対してフーリエ変換処理を行って得られるプリアンブルのＦＦＴ演算結果とを乗算して、前記相関信号を生成し、
前記相関検出信号は、前記生成された相関信号に対して逆フーリエ変換処理を行い、遅延プロファイルを生成して、前記ＣＤＭＡ信号と前記プリアンブルとの相関を検出する
（１）または（２）に記載の相関検出装置。
【００９１】
（４）連続したＭＮ（Ｍはフーリエ変換の基数；Ｎ＝１，２，．．．）個の記憶領域を用いて、ＭＮ個の時系列に続くデータに対して、Ｎ段のバタフライ演算を行うことによりフーリエ変換を行うフーリエ変換装置であって、
第（Ｉ；Ｉ＝０，１，．．．，ＭＮ−１）番目のデータを、第（ＭＮ−１（［Ｉ／Ｍ０］ｍｏｄＭ）＋ＭＮ−２（［Ｉ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｉ／ＭＮ−１］ｍｏｄＭ）；但し、［Ｘ］はＸを超えない整数，ＹｍｏｄＺは整数Ｙの整数Ｚに対する剰余系）番目の前記記憶領域に記憶させるデータ記憶手段と、
第（ＭＪ＋Ｈ；Ｊ＝０，１，．．．，ＭＮ−１−１，Ｈ＝０〜Ｍ−１）番目のＭ個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））番目のＭ個の前記記憶領域に記憶させる処理を（Ｎ−１）回、繰り返す第１のバタフライ演算処理手段と、
前記（Ｎ−１）回のバタフライ演算の結果として得られ、第（ＭＪ＋Ｈ）番目のＭ個の前記記憶領域に記憶されたデータに対して、バタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１（［Ｊ／Ｍ１］ｍｏｄＭ）＋．．．＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ）＋Ｈ）番目のＭ個の前記記憶領域に記憶させる処理を行う第２のバタフライ演算処理手段と
を有するフーリエ変換装置。
【００９２】
（５）連続した６４（Ｎ＝３）個の記憶領域を用いて、６４個の時系列に続くデータに対して、３段のバタフライ演算を行うことによりフーリエ変換を行うフーリエ変換装置であって、
データ記憶手段は、第（Ｉ；Ｉ＝０〜６３）番目のデータを、第（１６（Ｉｍｏｄ４）＋４（［Ｉ／４］ｍｏｄ４）＋（［Ｉ／１６］ｍｏｄ４））番目の前記記憶領域に記憶させ、
前記第１のバタフライ演算処理手段は、第（４Ｊ＋Ｈ；Ｊ＝０〜１５，Ｈ＝０〜３）番目の４個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（４Ｊ＋Ｈ）番目の４個のデータそれぞれを、第（１６Ｈ＋４（［Ｊ／４］ｍｏｄ４）＋（［Ｊ／１６］ｍｏｄ４））番目の４個の前記記憶領域に記憶させる処理を２回、繰り返し、
前記第２のバタフライ演算処理手段は、前記２回のバタフライ演算の結果として得られ、第（４Ｊ＋Ｈ）番目の４個の前記記憶領域に記憶されたデータに対して、バタフライ演算を行って得られる第（４Ｊ＋Ｈ）番目の４個のデータそれぞれを、第（１６（［Ｊ／４］ｍｏｄ４）＋４（［Ｊ／１６］ｍｏｄ４）＋Ｈ）番目の４個の前記記憶領域に記憶させる処理を行う
（４）に記載のフーリエ変換装置。
【００９３】
（６）　連続したＭＮ（Ｍは逆フーリエ変換の基数；Ｎ＝１，２，．．．）個の記憶領域を用いて、ＭＮ個の時系列に続くデータに対して、Ｎ段のバタフライ演算を行うことにより逆フーリエ変換を行う逆フーリエ変換装置であって、第（ＭＪ＋Ｈ；Ｊ＝０，１，．．．，ＭＮ−１−１，Ｈ＝０，１，．．．，Ｍ−１）番目のＭ個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（ＭＪ＋Ｈ）番目のＭ個のデータそれぞれを、第（ＭＮ−１Ｈ＋ＭＮ−２（［Ｊ／Ｍ１］ｍｏｄＭ）＋・・・＋Ｍ０（［Ｊ／ＭＮ−１］ｍｏｄＭ））番目のＭ個の前記記憶領域に記憶させる処理を（Ｎ）回、繰り返す第２のバタフライ演算処理手段を有する逆フーリエ変換装置。
【００９４】
（７）連続した６４（Ｍ＝４，Ｎ＝３）個の記憶領域を用いて、６４個の時系列に続くデータに対して、３段のバタフライ演算を行うことにより逆フーリエ変換を行うフーリエ変換装置であって、
前記第３のバタフライ演算処理手段は、第（４Ｊ＋Ｈ；Ｊ＝０〜１５，Ｈ＝０〜３）番目の４個の前記記憶領域に記憶されたデータに対して、第（Ｊ）番目のバタフライ演算を行って得られる第（４Ｊ＋Ｈ）番目の４個のデータそれぞれを、第（１６Ｈ＋４（［Ｊ／４］ｍｏｄ４）＋（［Ｊ／１６］ｍｏｄ４））番目の４個の前記記憶領域に記憶させる処理を３回、繰り返す（６）に記載の逆フーリエ変換装置。
【００９５】
【発明の効果】
以上説明したように、本発明にかかる相関検出装置で用いられるフーリエ変換装置によれば、ＣＤＭＡ方式などの逆拡散処理をソフトウェア的に実現することができる。
【図面の簡単な説明】
【図１】Ｗ−ＣＤＭＡ方式の移動体通信システムを例示する図である。
【図２】一般的なＦＦＴ処理を示すフローチャートである。
【図３】一般的なＦＦＴ処理におけるデータの並びの変遷を示す変遷図である。
【図４】本発明にかかるＦＦＴ処理を示す図である。
【図５】基数４のバタフライ演算を示す図である。
【図６】本発明にかかるＦＦＴ処理におけるデータの並びの変遷を示す変遷図である。
【図７】図１に示した基地局のハードウェアおよびソフトウェア構成を示す図である。
【図８】図７に示した受信部のハードウェア構成を示す図である。
【図９】図７に示した第１のＦＦＴ部の処理およびデータの並びの変遷を示す図である。
【図１０】第１のＦＦＴ部（図７）による第１〜３段目（最終段）のバタフライ演算処理（Ｓ１０）を示すフローチャートである。
【図１１】図７に示した第１のＩＦＦＴ部の処理およびデータの並びの変遷を示す図である。
【図１２】第１のＩＦＦＴ部（図７）による第１〜３段目（最終段）のバタフライ演算処理を示すフローチャートである。
【符号の説明】
１・・・移動体通信システム
１０・・・ネットワーク、
１２・・セル、
２・・・基地局、
２１０・・・送信部
２０・・・受信部、
２００・・・受信回路、
２０２・・・Ａ／Ｄ、
２２・・・遅延プロファイル検出部、
３・・・ＦＦＴ部、
２４・・・コード発生部、
２４０・・・ＲＡＣＨコード記憶部、
４・・・ＩＦＦＴ部
２６・・・ＤＳＰ回路部、
２６２・・・ＤＳＰ、
２６４・・・ＲＯＭ、
２６６・・・ＲＡＭ、
２５０・・・データ復号部
【図１】
2004032568.tif 000003
【図２】
2004032568.tif 000004
【図３】
2004032568.tif 000005
【図４】
2004032568.tif 000006
【図５】
2004032568.tif 000007
【図６】
2004032568.tif 000008
【図７】
2004032568.tif 000009
【図８】
2004032568.tif 000010
【図９】
2004032568.tif 000011
【図１０】
2004032568.tif 000012
【図１１】
2004032568.tif 000013
【図１２】
2004032568.tif 000014