(57)【要約】【課題】基数４ｍのバタフライ演算を行うバタフライ演算部を用いて、ＦＦＴポイント数が２（２ｎ−１）であるデータについてバタフライ演算を行うことが可能な演算装置を提供する。【解決手段】バタフライ演算制御部２５０は、基数４バタフライ演算部２５２および切替部２５４を有する。基数４バタフライ演算部２５２は、端子ａ，ｂ，ｃ，ｄから入力されたデータに対してバタフライ演算を行い、演算結果データを端子Ａ，Ｂ，Ｃ，Ｄに出力する。切替部２５４は、所定のタイミングで、状態０と状態１との間を交互に切り替わる。ここで、基数４バタフライ演算部２５２の端子ａは、メモリ２４４に接続されており、端子ｂは、Ａ／Ｄ変換部１０４に接続されており、端子ｃ，ｄは、どこにも接続されていない。つまり、端子ｃ，ｄには、値０のデータが入力されている。【選択図】図１０
2011133957.tif 000002
【特許請求の範囲】
【請求項１】
演算装置であって、
演算対象のデータに対して基数４ｍ（ｍは１以上の整数）のバタフライ演算を行うバタフライ演算部と、
前記演算対象のデータおよび前記バタフライ演算部からの演算結果データまたはこれらのいずれかを格納するメモリと、
所定のタイミングで前記バタフライ演算部がバタフライ演算を行うように、前記メモリからのデータおよび当該演算装置に入力された演算対象データについて、前記バタフライ演算部を迂回させるか、あるいは前記バタフライ演算部に入力させてバタフライ演算させるかを切り替える切替手段と
を有し、
前記バタフライ演算部は、演算対象である２ｎ個（ｎは１以上の整数）の演算対象データと値が０である（４ｍ−２ｎ）個のデータとを入力され、入力されたデータに対して基数４ｍのバタフライ演算を行い、
前記切替手段は、前記バタフライ演算部から２ｎ個の演算結果データを受け入れ、
前記メモリは、前記切替手段から出力された２ｎ個のデータのうちの（２ｎ−１）個のデータを格納する
演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置に関する。
【背景技術】
【０００２】
例えば、特許文献１は、ＦＦＴ（Fast Fourier Transform：高速フーリエ変換）における演算処理をパイプライン化した演算装置を開示する。
また、非特許文献１は、pipeline FFT processorを開示する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２２９４３６号公報
【非特許文献】
【０００４】
【非特許文献１】Shousheng He and Mats Torkelson, "New Approach to Pipeline FFT Processor", Department of Applied Electronics, Lund University
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、上述した背景からなされたものであり、基数４ｍ（ｍは１以上の整数。但し、ｍが常に同じ数とは限らない）のバタフライ演算を行うバタフライ演算部を用いて、ＦＦＴポイント数が２（２ｎ−１）（ｎは１以上の整数。但し、ｎが常に同じ数とは限らない）であるデータについてバタフライ演算を行うことが可能な演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る中継装置は、演算装置であって、演算対象のデータに対して基数４ｍ（ｍは１以上の整数）のバタフライ演算を行うバタフライ演算部と、前記演算対象のデータおよび前記バタフライ演算部からの演算結果データまたはこれらのいずれかを格納するメモリと、所定のタイミングで前記バタフライ演算部がバタフライ演算を行うように、前記メモリからのデータおよび当該演算装置に入力された演算対象データについて、前記バタフライ演算部を迂回させるか、あるいは前記バタフライ演算部に入力させてバタフライ演算させるかを切り替える切替手段とを有し、前記バタフライ演算部は、演算対象である２ｎ個（ｎは１以上の整数）の演算対象データと値が０である（４ｍ−２ｎ）個のデータとを入力され、入力されたデータに対して基数４ｍのバタフライ演算を行い、前記切替手段は、前記バタフライ演算部から２ｎ個の演算結果データを受け入れ、前記メモリは、前記切替手段から出力された２ｎ個のデータのうちの（２ｎ−１）個のデータを格納する。
【発明の効果】
【０００７】
本発明に係る演算装置によれば、基数４ｍのバタフライ演算を行うバタフライ演算部を用いて、ＦＦＴポイント数が２（２ｎ−１）であるデータについてバタフライ演算を行うことができる。
【図面の簡単な説明】
【０００８】
【図１】受信機を示す図である。
【図２】第１の実施形態にかかるＦＦＴ処理部の構成を示す図である。
【図３】図２に示した基数２バタフライ演算制御部の構成を示す図である。
【図４】第１の実施形態にかかるバタフライ演算の処理を示す図である。
【図５】図２に示したＦＦＴ処理部の処理の概要を示す図である。
【図６】第２の実施形態にかかるＦＦＴ処理部の構成を示す図である。
【図７】図６に示した基数４バタフライ演算制御部の構成を示す図である。
【図８】第２の実施形態にかかるバタフライ演算の処理を示す図である。
【図９】図６に示したＦＦＴ処理部の処理の概要を示す図である。
【図１０】第３の実施形態にかかるＦＦＴ処理部の構成を示す図である。
【図１１】図１０に示した基数４バタフライ演算部の構成を示す図である。
【図１２】図１０に示したＦＦＴ処理部の処理の概要を示す図である。
【図１３】第４の実施形態にかかるＦＦＴ処理部の構成を示す図である。
【図１４】図１３に示したバタフライ演算制御部および基数４バタフライ演算制御部の構成を示す図である。
【図１５】図１３に示したＦＦＴ処理部の処理フロー図である。
【図１６】図１３に示したＦＦＴ処理部の処理の概要を示す図である。
【図１７】図１３に示したＦＦＴ処理部の処理の概要を示す図である。
【発明を実施するための形態】
【０００９】
［本発明の背景］
本発明の理解を助けるために、まず、本発明がなされるに至った背景を説明する。
【００１０】
［第１の実施形態］
図１は受信機１を示す図である。
図１に示すように、受信機１は、アンテナ１００、受信回路１０２、Ａ／Ｄ変換部１０４、ＦＦＴ処理部２０、および復調部１０６から構成される。
受信回路１０２は、アンテナ１００を介して伝送信号を受信し、増幅等の処理を行って、Ａ／Ｄ変換部１０４に対して出力する。
Ａ／Ｄ変換部１０４は、受信回路１０２からのアナログ信号をディジタル信号に変換し、ＦＦＴ処理部２０に対して出力する。
【００１１】
ＦＦＴ処理部２０は、後述する構成要素を有しており、それらの構成要素により、Ａ／Ｄ変換部１０４によって変換されたディジタル信号（データ）に対してＦＦＴ処理を行う。
なお、以下の説明において、説明の具体化、明確化のために、ＦＦＴ処理部２０が、ＤＳＰ（Digital Signal Processor）等によってソフトウェアで構成される場合を具体例とするが、ＦＦＴ処理部２０は、ハードウェアで構成されてもよい。
復調部１０６は、ＦＦＴ処理を施されたデータに対して復調処理を行い、復調データを作成する。
【００１２】
図２は、図１に示したＦＦＴ処理部２０の構成を示す図である。
図２には、処理対象のブロック中の信号の数（ＦＦＴポイント数：Ｎ）が４（２２）である場合の例が示されている。
図２に示すように、ＦＦＴ処理部２０は、フィードバック演算部２００−１，２００−２、乗算部２０２およびクロック生成部３から構成される。
なお、以下、フィードバック演算部２００−１，２００−２など、複数ある構成部分のいずれかを特定せずに示す場合には、単にフィードバック演算部２００などと略記することがある。
【００１３】
また、フィードバック演算部２００−１および乗算部２０２までをステージ１とし、フィードバック演算部２００−２をステージ２とする。
フィードバック演算部２００−１は、Ａ／Ｄ変換部１０４からの処理対象のデータ（処理対象データ）に対して、基数２のバタフライ演算を行い、算出されたデータ（演算結果データ）を乗算部２０２に対して出力する。
乗算部２０２は、フィードバック演算部２００−１からの演算結果データに対して、回転因子ＷＮｑ［ｑ＝０，１，・・・，（Ｎ／２）−１］を乗算し、算出されたデータ（乗算結果データ）をフィードバック演算部２００−２に対して出力する。
フィードバック演算部２００−２は、乗算部２０２からの乗算結果データに対して、基数２のバタフライ演算を行い、算出された演算結果データを復調部１０６に対して出力する。
クロック生成部３は、クロック信号を生成して、フィードバック演算部２００の後述する基数２バタフライ演算制御部２１０に対して生成したクロック信号を出力する。
【００１４】
フィードバック演算部２００−１は、メモリ２０４−１および基数２バタフライ演算制御部２１０−１から構成される。
また、フィードバック演算部２００−２は、メモリ２０４−２および基数２バタフライ演算制御部２１０−２から構成される。
メモリ２０４−１は、２サンプル分のデータ容量を有し、メモリ２０４−２は、１サンプル分のデータ容量を有する。
基数２バタフライ演算制御部２１０は、後述する所定のタイミングで、処理対象データに対してバタフライ演算を行うように制御する。
この所定のタイミングは、ＦＦＴポイント数Ｎと、バタフライ演算部の基数と、メモリ容量等から決定されうる（以下の実施形態についても同様）。
【００１５】
図３は、図２に示した基数２バタフライ演算制御部２１０の構成を示す図であり、（Ａ）は基数２バタフライ演算制御部２１０−１の構成を示し、（Ｂ）は基数２バタフライ演算制御部２１０−２の構成を示す。
図３に示すように、基数２バタフライ演算制御部２１０−１，２１０−２は、実質的に同じ構成であり、それぞれ、基数２バタフライ演算部２１２−１，２１２−２、および切替部２１４−１，２１４−２を有する。
【００１６】
基数２バタフライ演算部２１２は、図４を用いて後述する構成を有しており、図３に示すように、端子ａと端子ｂとから入力されたデータに対してバタフライ演算を行い、演算結果データを端子Ａと端子Ｂとに出力する。
切替部２１４は、クロック生成部３からのクロック信号に基づいて、所定のタイミングで、状態０と状態１との間を交互に切り替わる。
ここで、基数２バタフライ演算部２１２−１の端子ａは、メモリ２０４−１に接続されており、端子ｂは、Ａ／Ｄ変換部１０４に接続されている。
また、基数２バタフライ演算部２１２−２の端子ａは、メモリ２０４−２に接続されており、端子ｂは、乗算部２０２に接続されている。
【００１７】
また、切替部２１４−１は、２個のスイッチ２１６ａ−１，２１６ｂ−１を有している。
状態０にある場合、スイッチ２１６ａ−１は、端子Ａ'に接続されて、端子ａを介して入力されたデータに対してバタフライ演算されることなく、このデータを乗算部２０２に対して出力する。
一方、状態１にある場合、スイッチ２１６ａ−１は、端子Ａに接続されて、基数２バタフライ演算部２１２−１から出力された演算結果データを、乗算部２０２に対して出力する。
また、状態０にある場合、スイッチ２１６ｂ−１は、端子Ｂ'に接続されて、端子ｂを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２０４−１に対して出力する。
また、状態１にある場合、スイッチ２１６ｂ−１は、端子Ｂに接続されて、基数２バタフライ演算部２１２−１から出力された演算結果データを、メモリ２０４−１に対して出力する。
【００１８】
同様に、切替部２１４−２は、２個のスイッチ２１６ａ−２，２１６ｂ−２を有している。
状態０にある場合、スイッチ２１６ａ−２は、端子Ａ'に接続されて、端子ａを介して入力されたデータに対してバタフライ演算されることなく、このデータを復調部１０６に対して出力する。
一方、状態１にある場合、スイッチ２１６ａ−２は、端子Ａに接続されて、基数２バタフライ演算部２１２−２から出力された演算結果データを、復調部１０６に対して出力する。
【００１９】
また、状態０にある場合、スイッチ２１６ｂ−２は、端子Ｂ'に接続されて、端子ｂを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２０４−２に対して出力する。
また、状態１にある場合、スイッチ２１６ｂ−２は、端子Ｂに接続されて、基数２バタフライ演算部２１２−２から出力された演算結果データを、メモリ２０４−２に対して出力する。
【００２０】
図４は、バタフライ演算の処理を示す図であり、（Ａ）は図３に示した基数２バタフライ演算部２１２の構成を示す図であり、（Ｂ）は、図２に示すＦＦＴ処理部２０の処理フロー図である。
図４（Ａ）に示すように、入力をａ，ｂとし、出力をＡ，Ｂとすると、Ａ＝ａ＋ｂ、Ｂ＝ａ−ｂとなる。
また、第１の実施形態にかかるＦＦＴ処理部２０は、図４（Ｂ）に示すようなフローで、ＦＦＴポイント数Ｎ＝４の処理対象データに対してＦＦＴ演算処理を行う。
【００２１】
図５は、図２に示したＦＦＴ処理部２０の処理の概要を示す図である。
まず、ステージ１について説明する。
時刻ｔ＝０において、切替部２１４−１は、状態０である。
このとき、基数２バタフライ演算制御部２１０−１は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（０）を受け入れ、この処理対象データｘ（０）は、基数２バタフライ演算部２１２−１を迂回して、メモリ２０４−１に格納される。
【００２２】
時刻ｔ＝１において、切替部２１４−１は、状態０のままである。
このとき、基数２バタフライ演算制御部２１０−１は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（１）を受け入れ、この処理対象データｘ（１）は、基数２バタフライ演算部２１２−１を迂回して、メモリ２０４−１に格納される。
つまり、このとき、メモリ２０４−１は、処理対象データｘ（０）および処理対象データｘ（１）を格納している。
【００２３】
時刻ｔ＝２において、切替部２１４−１は、状態１に切り替わる。
このとき、基数２バタフライ演算制御部２１０−１は、端子ａを介して、メモリ２０４−１に格納されていた処理対象データｘ（０）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（２）を受け入れる。
このとき、基数２バタフライ演算部２１２−１は、受け入れた処理対象データｘ（０）と処理対象データｘ（２）とに対してバタフライ演算を行い、端子Ａから演算結果データｘ'（０）を出力し、端子Ｂから演算結果データｘ'（２）を出力する。
さらに、演算結果データｘ'（０）は、乗算部２０２に対して出力され、演算結果データｘ'（２）は、メモリ２０４−１に格納される。
また、乗算部２０２は、演算結果データｘ'（０）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（０）を基数２バタフライ演算処理部２１０−２に対して出力する。
【００２４】
時刻ｔ＝３において、切替部２１４−１は、状態１のままである。
このとき、基数２バタフライ演算制御部２１０−１は、端子ａを介して、メモリ２０４−１に格納されていた処理対象データｘ（１）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（３）を受け入れる。
このとき、基数２バタフライ演算部２１２−１は、受け入れた処理対象データｘ（１）と処理対象データｘ（３）とに対してバタフライ演算を行い、端子Ａから演算結果データｘ'（１）を出力し、端子Ｂから演算結果データｘ'（３）を出力する。
さらに、演算結果データｘ'（１）は、乗算部２０２に対して出力され、演算結果データｘ'（３）は、メモリ２０４−１に格納される。
また、乗算部２０２は、演算結果データｘ'（１）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（１）を基数２バタフライ演算処理部２１０−２に対して出力する。
【００２５】
時刻ｔ＝４において、切替部２１４−１は、状態０に切り替わる。
このとき、基数２バタフライ演算制御部２１０−１は、端子ａを介して、メモリ２０４−１に格納されていた演算結果データｘ'（２）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（４）を受け入れる。
さらに、演算結果データｘ'（２）は、基数２バタフライ演算部２１２−１を迂回して、乗算部２０２に対して出力され、処理対象データｘ（４）は、基数２バタフライ演算部２１２−１を迂回して、メモリ２０４−１に格納される。
また、乗算部２０２は、演算結果データｘ'（２）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（２）を基数２バタフライ演算処理部２１０−２に対して出力する。
【００２６】
時刻ｔ＝５において、切替部２１４−１は、状態０のままである。
このとき、基数２バタフライ演算制御部２１０−１は、端子ａを介して、メモリ２０４−１に格納されていた演算結果データｘ'（３）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（５）を受け入れる。
さらに、演算結果データｘ'（３）は、基数２バタフライ演算部２１２−１を迂回して、乗算部２０２に対して出力され、処理対象データｘ（５）は、基数２バタフライ演算部２１２−１を迂回して、メモリ２０４−１に格納される。
また、乗算部２０２は、演算結果データｘ'（３）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（３）を基数２バタフライ演算処理部２１０−２に対して出力する。
【００２７】
以下同様に処理が実行される。
なお、第１の実施形態においては、ＦＦＴポイント数はＮ＝４であるので、乗算部２０２で乗算される回転因子ＷＮｑにおいて、Ｎ＝４，ｑ＝０，１であり、したがって、演算結果データｘ'（０），ｘ'（１），ｘ'（２），ｘ'（３）に乗算される回転因子は、Ｗ４０＝１、Ｗ４１＝−ｊ（ｊは虚数単位）となる。
乗算結果データの具体的な計算式は後述する。
【００２８】
次に、ステージ２について説明する。
ｔ＝２において、切替部２１４−２は、状態０である。
このとき、基数２バタフライ演算制御部２１０−２は、乗算部２０２から端子ｂを介して乗算結果データｘ''（０）を受け入れ、この乗算結果データｘ''（０）は、基数２バタフライ演算部２１２−２を迂回して、メモリ２０４−２に格納される。
【００２９】
ｔ＝３において、切替部２１４−２は、状態１に切り替わる。
このとき、基数２バタフライ演算制御部２１０−２は、端子ａを介して、メモリ２０４−２に格納されていた乗算結果データｘ''（０）を受け入れ、乗算部２０２から端子ｂを介して乗算結果データｘ''（１）を受け入れる。
このとき、基数２バタフライ演算部２１２−２は、受け入れた乗算結果データｘ''（０）と乗算結果データｘ''（１）とに対してバタフライ演算を行い、端子Ａから演算結果データｘ'''（０）を出力し、端子Ｂから演算結果データｘ'''（１）を出力する。
さらに、演算結果データｘ'''（０）は、４点ＦＦＴの結果として復調部１０６に対して出力され、演算結果データｘ'''（１）は、メモリ２０４−２に格納される。
【００３０】
ｔ＝４において、切替部２１４−２は、状態０に切り替わる。
このとき、基数２バタフライ演算制御部２１０−２は、端子ａを介して、メモリ２０４−２に格納されていた演算結果データｘ'''（１）を受け入れ、乗算部２０２から端子ｂを介して乗算結果データｘ''（２）を受け入れる。
さらに、演算結果データｘ'''（１）は、基数２バタフライ演算部２１２−２を迂回して、復調部１０６に対して出力され、乗算結果データｘ''（２）は、基数２バタフライ演算部２１２−２を迂回して、メモリ２０４−２に格納される。
【００３１】
ｔ＝５において、切替部２１４−２は、状態１に切り替わる。
このとき、基数２バタフライ演算制御部２１０−２は、端子ａを介して、メモリ２０４−２に格納されていた乗算結果データｘ''（２）を受け入れ、乗算部２０２から端子ｂを介して乗算結果データｘ''（３）を受け入れる。
このとき、基数２バタフライ演算部２１２−２は、受け入れた乗算結果データｘ''（２）と乗算結果データｘ''（３）とに対してバタフライ演算を行い、端子Ａから演算結果データｘ'''（２）を出力し、端子Ｂから演算結果データｘ'''（３）を出力する。
さらに、演算結果データｘ'''（２）は、復調部１０６に対して出力され、演算結果データｘ'''（３）は、メモリ２０４−２に格納される。
【００３２】
ｔ＝６において、切替部２１４−２は、状態０に切り替わる。
このとき、基数２バタフライ演算制御部２１０−２は、端子ａを介して、メモリ２０４−２に格納されていた演算結果データｘ'''（３）を受け入れ、乗算部２０２から端子ｂを介して乗算結果データｘ''（４）を受け入れる。
さらに、演算結果データｘ'''（３）は、基数２バタフライ演算部２１２−２を迂回して、復調部１０６に対して出力され、乗算結果データｘ''（４）は、基数２バタフライ演算部２１２−２を迂回して、メモリ２０４−２に格納される。
【００３３】
以下同様に処理が実行され、ＦＦＴ処理部２０は、ＦＦＴ演算処理が施されたデータを出力する。
ここで、各構成要素でなされる具体的な計算について説明する。
ステージ１において、フィードバック演算部２００−１は、以下の計算を行う。
ｘ'（０）＝ｘ（０）＋ｘ（２）
ｘ'（１）＝ｘ（１）＋ｘ（３）
ｘ'（２）＝ｘ（０）−ｘ（２）
ｘ'（３）＝ｘ（１）−ｘ（３）
・・・式（１−１）
【００３４】
また、乗算部２０２は、以下のように、演算結果データに対して回転因子ＷＮｑを乗算して、乗算結果データを生成する。
ｘ''（０）＝ｘ'（０）×Ｗ４０
ｘ''（１）＝ｘ'（１）×Ｗ４０
ｘ''（２）＝ｘ'（２）×Ｗ４０
ｘ''（３）＝ｘ'（３）×Ｗ４１
・・・式（１−２）
【００３５】
ステージ２において、フィードバック演算部２００−２は、以下の計算を行う。
ｘ'''（０）＝ｘ''（０）＋ｘ''（１）＝ｘ（０）＋ｘ（１）＋ｘ（２）＋ｘ（３）
ｘ'''（１）＝ｘ''（０）−ｘ''（１）＝ｘ（０）−ｘ（１）＋ｘ（２）−ｘ（３）
ｘ'''（２）＝ｘ''（２）＋ｘ''（３）＝ｘ（０）−ｊｘ（１）−ｘ（２）＋ｊｘ（３）
ｘ'''（３）＝ｘ''（２）−ｘ''（３）＝ｘ（０）＋ｊｘ（１）−ｘ（２）−ｊｘ（３）
・・・式（１−３）
【００３６】
［第２の実施形態］
図６は、第２の実施形態にかかるＦＦＴ処理部２２の構成を示す図である。
ここで、第２の実施形態にかかる受信機は、上述した第１の実施形態にかかる受信機１において、図１に示したＦＦＴ処理部２０をＦＦＴ処理部２２に置き換えた構成となっている。
図６には、処理対象のＦＦＴポイント数がＮ＝４（４１）である場合の例が示されている。
図６に示すように、ＦＦＴ処理部２２は、フィードバック演算部２２０およびクロック生成部３から構成される。
フィードバック演算部２２０は、Ａ／Ｄ変換部１０４からの処理対象データに対して、基数４のバタフライ演算を行い、算出された演算結果データを復調部１０６に対して出力する。
クロック生成部３は、フィードバック演算部２２０の後述する基数４バタフライ演算制御部２３０に対してクロック信号を出力する。
【００３７】
フィードバック演算部２２０は、メモリ２２４，２２６，２２８および基数４バタフライ演算制御部２３０から構成される。
メモリ２２４，２２６，２２８は、それぞれ、１サンプル分のデータ容量を有する。
基数４バタフライ演算制御部２３０は、後述する所定のタイミングで、処理対象データに対してバタフライ演算を行うように制御する。
【００３８】
図７は、図６に示した基数４バタフライ演算制御部２３０の構成を示す図である。
図７に示すように、基数４バタフライ演算制御部２３０は、基数４バタフライ演算部２３２および切替部２３４を有する。
基数４バタフライ演算部２３２は、図８を用いて後述する構成を有しており、図７に示すように、端子ａ，ｂ，ｃ，ｄから入力されたデータに対してバタフライ演算を行い、演算結果データを端子Ａ，Ｂ，Ｃ，Ｄに出力する。
【００３９】
切替部２３４は、クロック生成部３からのクロック信号に基づいて、所定のタイミングで、状態０と状態１との間を交互に切り替わる。
ここで、基数４バタフライ演算部２３２の端子ａは、メモリ２２８に接続されており、端子ｂは、メモリ２２６に接続されており、端子ｃは、メモリ２２４に接続されており、端子ｄは、Ａ／Ｄ変換部１０４に接続されている。
【００４０】
また、切替部２３４は、４個のスイッチ２３６ａ，２３６ｂ，２３６ｃ，２３６ｄを有している。
状態０にある場合、スイッチ２３６ａは、端子Ａ'に接続されて、端子ａを介して入力されたデータに対してバタフライ演算されることなく、このデータを復調部１０６に対して出力する。
一方、状態１にある場合、スイッチ２３６ａは、端子Ａに接続されて、基数４バタフライ演算部２３２から出力された演算結果データを、復調部１０６に対して出力する。
また、状態０にある場合、スイッチ２３６ｂは、端子Ｂ'に接続されて、端子ｂを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２２８に対して出力する。
一方、状態１にある場合、スイッチ２３６ｂは、端子Ｂに接続されて、基数４バタフライ演算部２３２から出力された演算結果データを、メモリ２２８に対して出力する。
【００４１】
また、状態０にある場合、スイッチ２３６ｃは、端子Ｃ'に接続されて、端子ｃを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２２６に対して出力する。
一方、状態１にある場合、スイッチ２３６ｃは、端子Ｃに接続されて、基数４バタフライ演算部２３２から出力された演算結果データを、メモリ２２６に対して出力する。
また、状態０にある場合、スイッチ２３６ｄは、端子Ｄ'に接続されて、端子ｄを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２２４に対して出力する。
一方、状態１にある場合、スイッチ２３６ｄは、端子Ｄに接続されて、基数４バタフライ演算部２３２から出力された演算結果データを、メモリ２２４に対して出力する。
【００４２】
図８は、バタフライ演算の処理を示す図であり、（Ａ）は図７に示した基数４バタフライ演算部２３２の構成を示す図であり、（Ｂ）は、図６に示すＦＦＴ処理部２２の処理フロー図である。
図８（Ａ）に示すように、基数４バタフライ演算部２３２の入力をａ，ｂ，ｃ，ｄとし、出力をＡ，Ｂ，Ｃ，Ｄとすると、Ａ＝ａ＋ｂ＋ｃ＋ｄ、Ｂ＝ａ−ｊｂ−ｃ＋ｊｄ、Ｃ＝ａ−ｂ＋ｃ−ｄ、Ｄ＝ａ＋ｊｂ−ｃ−ｊｄとなる。
第２の実施形態にかかるＦＦＴ処理部２２は、図８（Ｂ）に示すようなフローで、ＦＦＴポイント数Ｎ＝４の処理対象データに対してＦＦＴ演算処理を行う。
【００４３】
図９は、図６に示したＦＦＴ処理部２２の処理の概要を示す図である。
時刻ｔ＝０において、切替部２３４は、状態０である。
このとき、基数４バタフライ演算制御部２３０は、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（０）を受け入れ、この処理対象データｘ（０）は、基数４バタフライ演算部２３２を迂回して、メモリ２２４に格納される。
【００４４】
時刻ｔ＝１において、切替部２３４は、状態０のままである。
このとき、基数４バタフライ演算制御部２３０は、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（１）を受け入れ、この処理対象データｘ（１）は、基数４バタフライ演算部２３２を迂回して、メモリ２２４に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｃを介して、メモリ２２４に格納されていた処理対象データｘ（０）を受け入れ、この処理対象データｘ（０）は、基数４バタフライ演算部２３２を迂回して、メモリ２２６に格納される。
【００４５】
時刻ｔ＝２において、切替部２３４は、状態０のままである。
このとき、基数４バタフライ演算制御部２３０は、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（２）を受け入れ、この処理対象データｘ（２）は、基数４バタフライ演算部２３２を迂回して、メモリ２２４に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｃを介して、メモリ２２４に格納されていた処理対象データｘ（１）を受け入れ、この処理対象データｘ（１）は、基数４バタフライ演算部２３２を迂回して、メモリ２２６に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｂを介して、メモリ２２６に格納されていた処理対象データｘ（０）を受け入れ、この処理対象データｘ（０）は、基数４バタフライ演算部２３２を迂回して、メモリ２２８に格納される。
【００４６】
時刻ｔ＝３において、切替部２３４は、状態１に切り替わる。
このとき、基数４バタフライ演算制御部２３０は、端子ａを介して、メモリ２２８に格納されていた処理対象データｘ（０）を受け入れ、端子ｂを介して、メモリ２２６に格納されていた処理対象データｘ（１）を受け入れ、端子ｃを介して、メモリ２２４に格納されていた処理対象データｘ（２）を受け入れ、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（３）を受け入れる。
このとき、基数４バタフライ演算部２３２は、受け入れた処理対象データｘ（０）〜ｘ（３）に対してバタフライ演算を行い、端子Ａ，Ｂ，Ｃ，Ｄから、それぞれ、演算結果データｘ'（０）〜ｘ'（３）を出力する。
さらに、演算結果データｘ'（０）は、４点ＦＦＴの結果として復調部１０６に対して出力され、演算結果データｘ'（１）はメモリ２２８に格納され、演算結果データｘ'（２）はメモリ２２６に格納され、演算結果データｘ'（３）はメモリ２２４に格納される。
【００４７】
ｔ＝４において、切替部２３４は、状態０に切り替わる。
このとき、基数４バタフライ演算制御部２３０は、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（４）を受け入れ、この処理対象データｘ（４）は、基数４バタフライ演算部２３２を迂回して、メモリ２２４に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｃを介して、メモリ２２４に格納されていた演算結果データｘ'（３）を受け入れ、この演算結果データｘ'（３）は、基数４バタフライ演算部２３２を迂回して、メモリ２２６に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｂを介して、メモリ２２６に格納されていた演算結果データｘ'（２）を受け入れ、この演算結果データｘ'（２）は、基数４バタフライ演算部２３２を迂回して、メモリ２２８に格納される。
さらに、このとき、基数４バタフライ演算制御部２３０は、端子ａを介して、メモリ２２８に格納されていた演算結果データｘ'（１）を受け入れ、この演算結果データｘ'（１）は、基数４バタフライ演算部２３２を迂回して、４点ＦＦＴの結果として復調部１０６に対して出力される。
【００４８】
ｔ＝５において、切替部２３４は、状態０のままである。
このとき、基数４バタフライ演算制御部２３０は、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（５）を受け入れ、この処理対象データｘ（５）は、基数４バタフライ演算部２３２を迂回して、メモリ２２４に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｃを介して、メモリ２２４に格納されていた処理対象データｘ（４）を受け入れ、この処理対象データｘ（４）は、基数４バタフライ演算部２３２を迂回して、メモリ２２６に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｂを介して、メモリ２２６に格納されていた演算結果データｘ'（３）を受け入れ、この演算結果データｘ'（３）は、基数４バタフライ演算部２３２を迂回して、メモリ２２８に格納される。
さらに、このとき、基数４バタフライ演算制御部２３０は、端子ａを介して、メモリ２２８に格納されていた演算結果データｘ'（２）を受け入れ、この演算結果データｘ'（２）は、基数４バタフライ演算部２３２を迂回して、４点ＦＦＴの結果として復調部１０６に対して出力される。
【００４９】
ｔ＝６において、切替部２３４は、状態０のままである。
このとき、基数４バタフライ演算制御部２３０は、Ａ／Ｄ変換部１０４から端子ｄを介して処理対象データｘ（６）を受け入れ、この処理対象データｘ（６）は、基数４バタフライ演算部２３２を迂回して、メモリ２２４に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｃを介して、メモリ２２４に格納されていた処理対象データｘ（５）を受け入れ、この処理対象データｘ（５）は、基数４バタフライ演算部２３２を迂回して、メモリ２２６に格納される。
また、このとき、基数４バタフライ演算制御部２３０は、端子ｂを介して、メモリ２２６に格納されていた処理対象データｘ（４）を受け入れ、この処理対象データｘ（４）は、基数４バタフライ演算部２３２を迂回して、メモリ２２８に格納される。
さらに、このとき、基数４バタフライ演算制御部２３０は、端子ａを介して、メモリ２２８に格納されていた演算結果データｘ'（３）を受け入れ、この演算結果データｘ'（３）は、基数４バタフライ演算部２３２を迂回して、４点ＦＦＴの結果として復調部１０６に対して出力される。
【００５０】
以下同様に処理が実行され、ＦＦＴ処理部２２は、ＦＦＴ演算処理が施されたデータを出力する。
ここで、各構成要素でなされる具体的な計算について説明する。
フィードバック演算部２２０は、以下の計算を行う。
ｘ'（０）＝ｘ（０）＋ｘ（１）＋ｘ（２）＋ｘ（３）
ｘ'（１）＝ｘ（０）−ｊｘ（１）−ｘ（２）＋ｊｘ（３）
ｘ'（２）＝ｘ（０）−ｘ（１）＋ｘ（２）−ｘ（３）
ｘ'（３）＝ｘ（０）＋ｊｘ（１）−ｘ（２）−ｊｘ（３）
・・・式（２−１）
【００５１】
一方、４点ＤＦＴ（discrete Fourier transform：離散フーリエ変換）の計算結果は、以下の式（２−２）から、式（２−３）のように表される。
【００５２】
【数１】
2011133957.tif 000003
【００５３】
Ｘ（０）＝ｘ（０）Ｗ４０＋ｘ（１）Ｗ４０＋ｘ（２）Ｗ４０＋ｘ（３）Ｗ４０＝ｘ（０）＋ｘ（１）＋ｘ（２）＋ｘ（３）
Ｘ（１）＝ｘ（０）Ｗ４０＋ｘ（１）Ｗ４１＋ｘ（２）Ｗ４２＋ｘ（３）Ｗ４３＝ｘ（０）−ｊｘ（１）−ｘ（２）＋ｊｘ（３）
Ｘ（２）＝ｘ（０）Ｗ４０＋ｘ（１）Ｗ４２＋ｘ（２）Ｗ４４＋ｘ（３）Ｗ４６＝ｘ（０）−ｘ（１）＋ｘ（２）−ｘ（３）
Ｘ（３）＝ｘ（０）Ｗ４０＋ｘ（１）Ｗ４３＋ｘ（２）Ｗ４６＋ｘ（３）Ｗ４９＝ｘ（０）＋ｊｘ（１）−ｘ（２）−ｊｘ（３）
・・・式（２−３）
【００５４】
上記式（２−１）と式（２−３）とから、第２の実施形態にかかるＦＦＴ処理部２２は、４点ＤＦＴと同様の演算結果を得ることが分かる。
よって、基数２バタフライ演算アルゴリズムおよび基数４バタフライ演算アルゴリズムともに、ＦＦＴポイント数Ｎ＝４の処理対象データに対してＦＦＴ演算処理を行うことができる。
【００５５】
上述した第２の実施形態にかかるＦＦＴ処理部２２は、基数が４であるバタフライ演算を行うので、ＦＦＴポイント数がＮ＝４ｎ（ｎは１以上の整数）の場合には適用可能である。
しかしながら、基数４のバタフライ演算アルゴリズム（単一パス遅延フィードバックアルゴリズム：single-path delay feedback algorithm）は、例えば、ＦＦＴポイント数がＮ＝６４（４３）からＮ＝１２８（２７）に拡張される場合に、適用することができない。
以下に示す実施形態は、上述した不具合を解決し得るように改良されている。
【００５６】
［本発明の実施形態］
以下、本発明の実施形態を説明する。
［第３の実施形態］
図１０は、第３の実施形態にかかるＦＦＴ処理部２４の構成を示す図であり、（Ａ）はＦＦＴ処理部２４の構成を示し、（Ｂ）はバタフライ演算制御部２５０の構成を示す。
ここで、第３の実施形態にかかる受信機は、上述した第１の実施形態にかかる受信機１において、図１に示したＦＦＴ処理部２０をＦＦＴ処理部２４に置き換えた構成となっている。
図１０には、処理対象のＦＦＴポイント数がＮ＝２（２１）である場合の例が示されている。
【００５７】
図１０（Ａ）に示すように、ＦＦＴ処理部２４は、フィードバック演算部２４０およびクロック生成部３から構成される。
フィードバック演算部２４０は、Ａ／Ｄ変換部１０４からの処理対象データに対して、基数４のバタフライ演算を行い、算出された演算結果データを復調部１０６に対して出力する。
クロック生成部３は、フィードバック演算部２４０の後述するバタフライ演算制御部２５０に対してクロック信号を出力する。
【００５８】
フィードバック演算部２４０は、メモリ２４４およびバタフライ演算制御部２５０から構成される。
メモリ２４４は、１サンプル分のデータ容量を有する。
バタフライ演算制御部２５０は、後述する所定のタイミングで、処理対象データに対してバタフライ演算を行うように制御する。
【００５９】
図１０（Ｂ）は、図１０（Ａ）に示したバタフライ演算制御部２５０の構成を示す図である。
図１０（Ｂ）に示すように、バタフライ演算制御部２５０は、基数４バタフライ演算部２５２および切替部２５４を有する。
【００６０】
基数４バタフライ演算部２５２は、図１１を用いて後述する構成を有しており、図１０（Ｂ）に示すように、端子ａ，ｂ，ｃ，ｄから入力されたデータに対してバタフライ演算を行い、演算結果データを端子Ａ，Ｂ，Ｃ，Ｄに出力する。
切替部２５４は、クロック生成部３からのクロック信号に基づいて、所定のタイミングで、状態０と状態１との間を交互に切り替わる。
ここで、基数４バタフライ演算部２５２の端子ａは、メモリ２４４に接続されており、端子ｂは、Ａ／Ｄ変換部１０４に接続されており、端子ｃ，ｄは、どこにも接続されていない。
つまり、端子ｃ，ｄには、値０のデータが入力されている。
【００６１】
また、切替部２５４は、２個のスイッチ２５６ａ，２５６ｃを有している。
状態０にある場合、スイッチ２５６ａは、端子Ａ'に接続されて、端子ａを介して入力されたデータに対してバタフライ演算されることなく、このデータを復調部１０６に対して出力する。
一方、状態１にある場合、スイッチ２５６ａは、端子Ａに接続されて、基数４バタフライ演算部２５２から出力された演算結果データを、復調部１０６に対して出力する。
【００６２】
また、状態０にある場合、スイッチ２５６ｃは、端子Ｃ'に接続されて、端子ｂを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２４４に対して出力する。
一方、状態１にある場合、スイッチ２５６ｃは、端子Ｃに接続されて、基数４バタフライ演算部２５２から出力された演算結果データを、メモリ２４４に対して出力する。
ここで、基数４バタフライ演算部２５２の出力端子Ｂ，Ｄは、どこにも接続されていない。
つまり、本実施形態においては、基数４バタフライ演算部２５２の出力Ｂ，Ｄは、使用されない。
【００６３】
図１１は、図１０に示した基数４バタフライ演算部２５２の構成を示す図である。
基数４バタフライ演算部２５２は、第２の実施形態にかかる基数４バタフライ演算部２３２と実質的に同様の構成を有している。
図１１に示すように、基数４バタフライ演算部２５２の入力をａ，ｂ，ｃ，ｄとし、出力をＡ，Ｂ，Ｃ，Ｄとすると、ｃ＝０，ｄ＝０であるので、Ａ＝ａ＋ｂ、Ｂ＝ａ−ｊｂ、Ｃ＝ａ−ｂ、Ｄ＝ａ＋ｊｂとなる。
本実施形態では、上述のように、Ａ＝ａ＋ｂおよびＣ＝ａ−ｂが使用される。
【００６４】
図１２は、図１０に示したＦＦＴ処理部２４の処理の概要を示す図である。
時刻ｔ＝０において、切替部２５４は、状態０である。
このとき、バタフライ演算制御部２５０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（０）を受け入れ、この処理対象データｘ（０）は、基数４バタフライ演算部２５２を迂回して、メモリ２４４に格納される。
【００６５】
時刻ｔ＝１において、切替部２５４は、状態１に切り替わる。
このとき、バタフライ演算制御部２５０は、端子ａを介して、メモリ２４４に格納されていた処理対象データｘ（０）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（１）を受け入れる。
このとき、基数４バタフライ演算部２５２は、受け入れた処理対象データｘ（０），ｘ（１）に対してバタフライ演算を行い、端子Ａ，Ｃから、それぞれ、演算結果データｘ'（０），ｘ'（１）を出力する。
さらに、演算結果データｘ'（０）は、２点ＦＦＴの結果として復調部１０６に対して出力され、演算結果データｘ'（１）はメモリ２４４に格納される。
【００６６】
時刻ｔ＝２において、切替部２５４は、状態０に切り替わる。
このとき、バタフライ演算制御部２５０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（２）を受け入れ、この処理対象データｘ（２）は、基数４バタフライ演算部２５２を迂回して、メモリ２４４に格納される。
さらに、このとき、バタフライ演算制御部２５０は、端子ａを介して、メモリ２４４に格納されていた演算結果データｘ'（１）を受け入れ、この演算結果データｘ'（１）は、基数４バタフライ演算部２５２を迂回して、４点ＦＦＴの結果として復調部１０６に対して出力される。
【００６７】
時刻ｔ＝３において、切替部２５４は、状態１に切り替わる。
このとき、バタフライ演算制御部２５０は、端子ａを介して、メモリ２４４に格納されていた処理対象データｘ（３）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（２）を受け入れる。
このとき、基数４バタフライ演算部２５２は、受け入れた処理対象データｘ（２），ｘ（３）に対してバタフライ演算を行い、端子Ａ，Ｃから、それぞれ、演算結果データｘ'（２），ｘ'（３）を出力する。
さらに、演算結果データｘ'（２）は、４点ＦＦＴの結果として復調部１０６に対して出力され、演算結果データｘ'（３）はメモリ２４４に格納される。
【００６８】
以下同様に処理が実行され、ＦＦＴ処理部２２は、ＦＦＴ演算処理が施されたデータを出力する。
以上のようにして、基数４のバタフライ演算アルゴリズムを適用して、ＦＦＴポイント数Ｎ＝２１の処理対象データに対して、ＦＦＴ演算処理を行うことができる。
【００６９】
［第４の実施形態］
図１３は、第４の実施形態にかかるＦＦＴ処理部２６の構成を示す図である。
図１３は、処理対象のＦＦＴポイント数がＮ＝８（２３）である場合の例が示されている。
ここで、第４の実施形態にかかる受信機は、上述した第１の実施形態にかかる受信機１において、図１に示したＦＦＴ処理部２０をＦＦＴ処理部２６に置き換えた構成となっている。
【００７０】
図１３に示すように、ＦＦＴ処理部２６は、フィードバック演算部２６０、乗算部２６２、フィードバック演算部２８０およびおよびクロック生成部３から構成される。
また、フィードバック演算部２６０および乗算部２６２までをステージ１とし、フィードバック演算部２８０をステージ２とする。
フィードバック演算部２６０は、Ａ／Ｄ変換部１０４からの処理対象データに対して、基数４のバタフライ演算を行い、算出された演算結果データを乗算部２６２に対して出力する。
乗算部２６２は、フィードバック演算部２６０からの演算結果データに対して、回転因子ＷＮｑ［ｑ＝０，１，・・・，（Ｎ／２）−１］を乗算し、算出された乗算結果データをフィードバック演算部２８０に対して出力する。
フィードバック演算部２８０は、乗算部２６２からの乗算結果データに対して、基数４のバタフライ演算を行い、算出された演算結果データを復調部１０６に対して出力する。
クロック生成部３は、フィードバック演算部２６０の後述するバタフライ演算制御部２７０およびフィードバック演算部２８０の後述するバタフライ演算制御部２９０に対して生成したクロック信号を出力する。
【００７１】
フィードバック演算部２６０は、メモリ２６４およびバタフライ演算制御部２７０から構成される。
また、フィードバック演算部２８０は、メモリ２８４，２８６，２８８および基数４バタフライ演算制御部２９０から構成される。
メモリ２６４は、４サンプル分のデータ容量を有し、メモリ２８４，２８６，２８８は、それぞれ１サンプル分のデータ容量を有する。
バタフライ演算制御部２７０および基数４バタフライ演算制御部２９０は、後述する所定のタイミングで、処理対象データに対してバタフライ演算を行うように制御する。
【００７２】
図１４は、図１３に示したバタフライ演算制御部２７０および基数４バタフライ演算制御部２９０の構成を示す図であり、（Ａ）はバタフライ演算制御部２７０の構成を示し、（Ｂ）は基数４バタフライ演算制御部２９０の構成を示す。
図１４（Ａ）に示すように、バタフライ演算制御部２７０は、上述した第３の実施形態にかかるバタフライ演算制御部２５０と実質的に同様の構成を有しており、基数４バタフライ演算部２７２および切替部２７４を有している。
基数４バタフライ演算部２７２は、図１１を用いて上述した構成を有しており、図１４（Ａ）に示すように、端子ａ，ｂ，ｃ，ｄから入力されたデータに対してバタフライ演算を行い、演算結果データを端子Ａ，Ｂ，Ｃ，Ｄに出力する。
【００７３】
切替部２７４は、クロック生成部３からのクロック信号に基づいて、所定のタイミングで、状態０と状態１との間を交互に切り替わる。
ここで、基数４バタフライ演算部２７２の端子ａは、メモリ２６４に接続されており、端子ｂは、Ａ／Ｄ変換部１０４に接続されており、端子ｃ，ｄは、どこにも接続されていない。
つまり、端子ｃ，ｄは、値０のデータが入力されている。
【００７４】
また、切替部２７４は、２個のスイッチ２７６ａ，２７６ｃを有している。
状態０にある場合、スイッチ２７６ａは、端子Ａ'に接続されて、端子ａを介して入力されたデータに対してバタフライ演算されることなく、このデータを復調部１０６に対して出力する。
一方、状態１にある場合、スイッチ２７６ａは、端子Ａに接続されて、基数４バタフライ演算部２７２から出力された演算結果データを、乗算部２６２に対して出力する。
【００７５】
また、状態０にある場合、スイッチ２７６ｃは、端子Ｃ'に接続されて、端子ｂを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２６４に対して出力する。
一方、状態１にある場合、スイッチ２７６ｃは、端子Ｃに接続されて、基数４バタフライ演算部２７２から出力された演算結果データを、メモリ２６４に対して出力する。
ここで、基数４バタフライ演算部２７２の出力端子Ｂ，Ｄは、どこにも接続されていない。
つまり、本実施形態においては、基数４バタフライ演算部２７２の出力Ｂ，Ｄは、使用されない。
【００７６】
図１４（Ｂ）に示すように、基数４バタフライ演算制御部２９０は、上述した第２の実施形態にかかるバタフライ演算制御部２３０と実質的に同様の構成を有しており、基数４バタフライ演算部２９２および切替部２９４を有している。
基数４バタフライ演算部２９２は、図８を用いて上述した構成を有しており、図１４（Ｂ）に示すように、端子ａ，ｂ，ｃ，ｄから入力されたデータに対してバタフライ演算を行い、演算結果データを端子Ａ，Ｂ，Ｃ，Ｄに出力する。
切替部２９４は、クロック生成部３からのクロック信号に基づいて、所定のタイミングで、状態０と状態１との間を交互に切り替わる。
ここで、基数４バタフライ演算部２９２の端子ａは、メモリ２８８に接続されており、端子ｂは、メモリ２８６に接続されており、端子ｃは、メモリ２８４に接続されており、端子ｄは、乗算部２６２に接続されている。
【００７７】
また、切替部２９４は、４個のスイッチ２９６ａ，２９６ｂ，２９６ｃ，２９６ｄを有している。
状態０にある場合、スイッチ２９６ａは、端子Ａ'に接続されて、端子ａを介して入力されたデータに対してバタフライ演算されることなく、このデータを復調部１０６に対して出力する。
一方、状態１にある場合、スイッチ２９６ａは、端子Ａに接続されて、基数４バタフライ演算部２９２から出力された演算結果データを、復調部１０６に対して出力する。
また、状態０にある場合、スイッチ２９６ｂは、端子Ｂ'に接続されて、端子ｂを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２８８に対して出力する。
一方、状態１にある場合、スイッチ２９６ｂは、端子Ｂに接続されて、基数４バタフライ演算部２９２から出力された演算結果データを、メモリ２８８に対して出力する。
【００７８】
また、状態０にある場合、スイッチ２９６ｃは、端子Ｃ'に接続されて、端子ｃを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２８６に対して出力する。
一方、状態１にある場合、スイッチ２９６ｃは、端子Ｃに接続されて、基数４バタフライ演算部２９２から出力された演算結果データを、メモリ２８６に対して出力する。
また、状態０にある場合、スイッチ２９６ｄは、端子Ｄ'に接続されて、端子ｄを介して入力されたデータに対してバタフライ演算されることなく、このデータをメモリ２８４に対して出力する。
一方、状態１にある場合、スイッチ２９６ｄは、端子Ｄに接続されて、基数４バタフライ演算部２９２から出力された演算結果データを、メモリ２８４に対して出力する。
【００７９】
図１５は、図１３に示すＦＦＴ処理部２６の処理フロー図である。
第４の実施形態にかかるＦＦＴ処理部２６は、図１５に示すようなフローで、ＦＦＴポイント数Ｎ＝８の処理対象データに対してＦＦＴ演算処理を行う。
【００８０】
図１６および図１７は、図１３に示したＦＦＴ処理部２６の処理の概要を示す図であり、図１６はステージ１の処理を示し、図１７はステージ２の処理を示す。
まず、ステージ１について説明する。
時刻ｔ＝０において、切替部２７４は、状態０である。
このとき、バタフライ演算制御部２７０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（０）を受け入れ、この処理対象データｘ（０）は、基数４バタフライ演算部２７２を迂回して、メモリ２６４に格納される。
【００８１】
時刻ｔ＝１において、切替部２７４は、状態０のままである。
このとき、バタフライ演算制御部２７０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（１）を受け入れ、この処理対象データｘ（１）は、基数４バタフライ演算部２７２を迂回して、メモリ２６４に格納される。
時刻ｔ＝２において、切替部２７４は、状態０のままである。
このとき、バタフライ演算制御部２７０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（２）を受け入れ、この処理対象データｘ（２）は、基数４バタフライ演算部２７２を迂回して、メモリ２６４に格納される。
【００８２】
時刻ｔ＝３において、切替部２７４は、状態０のままである。
このとき、バタフライ演算制御部２７０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（３）を受け入れ、この処理対象データｘ（３）は、基数４バタフライ演算部２７２を迂回して、メモリ２６４に格納される。
なお、このとき、メモリ２６４は、処理対象データｘ（０）〜ｘ（３）を格納している。
【００８３】
時刻ｔ＝４において、切替部２７４は、状態１に切り替わる。
このとき、バタフライ演算制御部２７０は、端子ａを介して、メモリ２６４に格納されていた処理対象データｘ（０）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（４）を受け入れる。
このとき、基数４バタフライ演算部２７２は、受け入れた処理対象データｘ（０），ｘ（４）に対してバタフライ演算を行い、端子Ａ，Ｃから、それぞれ、演算結果データｘ'（０），ｘ'（４）を出力する。
さらに、演算結果データｘ'（０）は、乗算部２６２に対して出力され、演算結果データｘ'（４）はメモリ２６４に格納される。
また、乗算部２６２は、演算結果データｘ'（０）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（０）を基数４バタフライ演算処理部２９０に対して出力する。
【００８４】
時刻ｔ＝５において、切替部２７４は、状態１のままである。
このとき、バタフライ演算制御部２７０は、端子ａを介して、メモリ２６４に格納されていた処理対象データｘ（１）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（５）を受け入れる。
このとき、基数４バタフライ演算部２７２は、受け入れた処理対象データｘ（１），ｘ（５）に対してバタフライ演算を行い、端子Ａ，Ｃから、それぞれ、演算結果データｘ'（１），ｘ'（５）を出力する。
さらに、演算結果データｘ'（１）は、乗算部２６２に対して出力され、演算結果データｘ'（５）はメモリ２６４に格納される。
また、乗算部２６２は、演算結果データｘ'（１）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（１）を基数４バタフライ演算処理部２９０に対して出力する。
【００８５】
時刻ｔ＝６において、切替部２７４は、状態１のままである。
このとき、バタフライ演算制御部２７０は、端子ａを介して、メモリ２６４に格納されていた処理対象データｘ（２）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（６）を受け入れる。
このとき、基数４バタフライ演算部２７２は、受け入れた処理対象データｘ（２），ｘ（６）に対してバタフライ演算を行い、端子Ａ，Ｃから、それぞれ、演算結果データｘ'（２），ｘ'（６）を出力する。
さらに、演算結果データｘ'（２）は、乗算部２６２に対して出力され、演算結果データｘ'（６）はメモリ２６４に格納される。
また、乗算部２６２は、演算結果データｘ'（２）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（２）を基数４バタフライ演算処理部２９０に対して出力する。
【００８６】
時刻ｔ＝７において、切替部２７４は、状態１のままである。
このとき、バタフライ演算制御部２７０は、端子ａを介して、メモリ２６４に格納されていた処理対象データｘ（３）を受け入れ、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（７）を受け入れる。
このとき、基数４バタフライ演算部２７２は、受け入れた処理対象データｘ（３），ｘ（７）に対してバタフライ演算を行い、端子Ａ，Ｃから、それぞれ、演算結果データｘ'（３），ｘ'（７）を出力する。
さらに、演算結果データｘ'（３）は、乗算部２６２に対して出力され、演算結果データｘ'（７）はメモリ２６４に格納される。
また、乗算部２６２は、演算結果データｘ'（３）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（３）を基数４バタフライ演算処理部２９０に対して出力する。
【００８７】
時刻ｔ＝８において、切替部２７４は、状態０に切り替わる。
このとき、バタフライ演算制御部２７０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（８）を受け入れ、この処理対象データｘ（８）は、基数４バタフライ演算部２７２を迂回して、メモリ２６４に格納される。
さらに、このとき、バタフライ演算制御部２７０は、端子ａを介して、メモリ２６４に格納されていた演算結果データｘ'（４）を受け入れ、この演算結果データｘ'（４）は、基数４バタフライ演算部２７２を迂回して、乗算部２６２に対して出力される。
また、乗算部２６２は、演算結果データｘ'（４）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（４）を基数４バタフライ演算処理部２９０に対して出力する。
【００８８】
時刻ｔ＝９において、切替部２７４は、状態０のままである。
このとき、バタフライ演算制御部２７０は、Ａ／Ｄ変換部１０４から端子ｂを介して処理対象データｘ（９）を受け入れ、この処理対象データｘ（９）は、基数４バタフライ演算部２７２を迂回して、メモリ２６４に格納される。
さらに、このとき、バタフライ演算制御部２７０は、端子ａを介して、メモリ２６４に格納されていた演算結果データｘ'（５）を受け入れ、この演算結果データｘ'（５）は、基数４バタフライ演算部２７２を迂回して、乗算部２６２に対して出力される。
また、乗算部２６２は、演算結果データｘ'（５）に回転因子ＷＮｑを乗算し、乗算結果データｘ''（５）を基数４バタフライ演算処理部２９０に対して出力する。
【００８９】
以下同様に処理が実行される。
なお、第４の実施形態においては、ＦＦＴポイント数はＮ＝８であるので、乗算部２６２で乗算される回転因子ＷＮｑにおいて、Ｎ＝８，ｑ＝０，１，２，３であり、したがって、演算結果データｘ'（０），ｘ'（１），ｘ'（２），ｘ'（３），ｘ'（４），ｘ'（５），ｘ'（６），ｘ'（７）に乗算される回転因子は、Ｗ８０，Ｗ８１，Ｗ８２，Ｗ８３となる。
乗算結果データの具体的な計算式は後述する。
【００９０】
次に、ステージ２について説明する。
ｔ＝４において、切替部２９４は、状態０である。
このとき、基数４バタフライ演算制御部２９０は、乗算部２６２から端子ｄを介して乗算結果データｘ''（０）を受け入れ、この乗算結果データｘ''（０）は、基数４バタフライ演算部２９２を迂回して、メモリ２８４に格納される。
【００９１】
ｔ＝５において、切替部２９４は、状態０のままである。
このとき、基数４バタフライ演算制御部２９０は、乗算部２６２から端子ｄを介して乗算結果データｘ''（１）を受け入れ、この乗算結果データｘ''（１）は、基数４バタフライ演算部２９２を迂回して、メモリ２８４に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｃを介して、メモリ２８４に格納されていた乗算結果データｘ''（０）を受け入れ、この乗算結果データｘ''（０）は、基数４バタフライ演算部２９２を迂回して、メモリ２８６に格納される。
【００９２】
ｔ＝６において、切替部２９４は、状態０のままである。
このとき、基数４バタフライ演算制御部２９０は、乗算部２６２から端子ｄを介して乗算結果データｘ''（２）を受け入れ、この乗算結果データｘ''（２）は、基数４バタフライ演算部２９２を迂回して、メモリ２８４に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｃを介して、メモリ２８４に格納されていた乗算結果データｘ''（１）を受け入れ、この乗算結果データｘ''（１）は、基数４バタフライ演算部２９２を迂回して、メモリ２８６に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｂを介して、メモリ２８６に格納されていた乗算結果データｘ''（０）を受け入れ、この乗算結果データｘ''（０）は、基数４バタフライ演算部２９２を迂回して、メモリ２８８に格納される。
【００９３】
時刻ｔ＝７において、切替部２９４は、状態１に切り替わる。
このとき、基数４バタフライ演算制御部２９０は、端子ａを介して、メモリ２８８に格納されていた乗算結果データｘ''（０）を受け入れ、端子ｂを介して、メモリ２８６に格納されていた乗算結果データｘ''（１）を受け入れ、端子ｃを介して、メモリ２８４に格納されていた乗算結果データｘ''（２）を受け入れ、乗算部２６２から端子ｄを介して乗算結果データｘ''（３）を受け入れる。
このとき、基数４バタフライ演算部２９２は、受け入れた乗算結果データｘ''（０）〜ｘ''（３）に対してバタフライ演算を行い、端子Ａ，Ｂ，Ｃ，Ｄから、それぞれ、演算結果データｘ'''（０）〜ｘ'''（３）を出力する。
さらに、演算結果データｘ'''（０）は、８点ＦＦＴの結果として復調部１０６に対して出力され、演算結果データｘ'''（１）はメモリ２８８に格納され、演算結果データｘ'''（２）はメモリ２８６に格納され、演算結果データｘ'''（３）はメモリ２８４に格納される。
【００９４】
ｔ＝８において、切替部２９４は、状態０に切り替わる。
このとき、基数４バタフライ演算制御部２９０は、乗算部２６２から端子ｄを介して乗算結果データｘ''（４）を受け入れ、この乗算結果データｘ''（４）は、基数４バタフライ演算部２９２を迂回して、メモリ２８４に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｃを介して、メモリ２８４に格納されていた演算結果データｘ'''（３）を受け入れ、この演算結果データｘ'''（３）は、基数４バタフライ演算部２９２を迂回して、メモリ２８６に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｂを介して、メモリ２８６に格納されていた演算結果データｘ'''（２）を受け入れ、この演算結果データｘ'''（２）は、基数４バタフライ演算部２９２を迂回して、メモリ２８８に格納される。
さらに、このとき、基数４バタフライ演算制御部２９０は、端子ａを介して、メモリ２８８に格納されていた演算結果データｘ'''（１）を受け入れ、この演算結果データｘ'''（１）は、基数４バタフライ演算部２９２を迂回して、復調部１０６に対して出力される。
【００９５】
ｔ＝９において、切替部２９４は、状態０のままである。
このとき、基数４バタフライ演算制御部２９０は、乗算部２６２から端子ｄを介して乗算結果データｘ''（５）を受け入れ、この乗算結果データｘ''（５）は、基数４バタフライ演算部２９２を迂回して、メモリ２８４に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｃを介して、メモリ２８４に格納されていた乗算結果データｘ''（４）を受け入れ、この乗算結果データｘ''（４）は、基数４バタフライ演算部２９２を迂回して、メモリ２８６に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｂを介して、メモリ２８６に格納されていた演算結果データｘ'''（３）を受け入れ、この演算結果データｘ'''（３）は、基数４バタフライ演算部２９２を迂回して、メモリ２８８に格納される。
さらに、このとき、基数４バタフライ演算制御部２９０は、端子ａを介して、メモリ２８８に格納されていた演算結果データｘ'''（２）を受け入れ、この演算結果データｘ'''（２）は、基数４バタフライ演算部２９２を迂回して、復調部１０６に対して出力される。
【００９６】
ｔ＝１０において、切替部２９４は、状態０のままである。
このとき、基数４バタフライ演算制御部２９０は、乗算部２６２から端子ｄを介して乗算結果データｘ''（６）を受け入れ、この乗算結果データｘ''（６）は、基数４バタフライ演算部２９２を迂回して、メモリ２８４に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｃを介して、メモリ２８４に格納されていた乗算結果データｘ''（５）を受け入れ、この乗算結果データｘ''（５）は、基数４バタフライ演算部２９２を迂回して、メモリ２８６に格納される。
また、このとき、基数４バタフライ演算制御部２９０は、端子ｂを介して、メモリ２８６に格納されていた乗算結果データｘ''（４）を受け入れ、この乗算結果データｘ''（４）は、基数４バタフライ演算部２９２を迂回して、メモリ２８８に格納される。
さらに、このとき、基数４バタフライ演算制御部２９０は、端子ａを介して、メモリ２８８に格納されていた演算結果データｘ'''（３）を受け入れ、この演算結果データｘ'''（３）は、基数４バタフライ演算部２９２を迂回して、復調部１０６に対して出力される。
【００９７】
以下同様に処理が実行され、ＦＦＴ処理部２６は、ＦＦＴ演算処理が施されたデータを出力する。
以上のようにして、基数４のバタフライ演算アルゴリズムを適用して、ＦＦＴポイント数Ｎ＝２３の処理対象データに対して、ＦＦＴ演算処理を行うことができる。
【００９８】
ここで、各構成要素でなされる具体的な計算について説明する。
ステージ１において、フィードバック演算部２６０は、以下の計算を行う。
ｘ'（０）＝ｘ（０）＋ｘ（４）
ｘ'（４）＝ｘ（０）−ｘ（４）
ｘ'（１）＝ｘ（１）＋ｘ（５）
ｘ'（５）＝ｘ（１）−ｘ（５）
ｘ'（２）＝ｘ（２）＋ｘ（６）
ｘ'（６）＝ｘ（２）−ｘ（６）
ｘ'（３）＝ｘ（３）＋ｘ（７）
ｘ'（３）＝ｘ（３）−ｘ（７）
・・・式（４−１）
【００９９】
また、乗算部２６２は、以下のように、演算結果データに対して回転因子ＷＮｑを乗算して、乗算結果データを生成する。
ｘ''（０）＝ｘ'（０）×Ｗ８０
ｘ''（１）＝ｘ'（１）×Ｗ８０
ｘ''（２）＝ｘ'（２）×Ｗ８０
ｘ''（３）＝ｘ'（３）×Ｗ８０
ｘ''（４）＝ｘ'（４）×Ｗ８０
ｘ''（５）＝ｘ'（５）×Ｗ８１
ｘ''（６）＝ｘ'（６）×Ｗ８２
ｘ''（７）＝ｘ'（７）×Ｗ８３
・・・式（４−２）
【０１００】
また、ステージ２において、フィードバック演算部２８０は、以下の計算を行う。
ｘ'''（０）＝ｘ''（０）＋ｘ''（１）＋ｘ''（２）＋ｘ''（３）
ｘ'''（１）＝ｘ''（０）−ｊｘ''（１）−ｘ''（２）＋ｊｘ''（３）
ｘ'''（２）＝ｘ''（０）−ｘ''（１）＋ｘ''（２）−ｘ''（３）
ｘ'''（３）＝ｘ''（０）＋ｊｘ''（１）−ｘ''（２）−ｊｘ''（３）
ｘ'''（４）＝ｘ''（４）＋ｘ''（５）＋ｘ''（６）＋ｘ''（７）
ｘ'''（５）＝ｘ''（４）−ｊｘ''（５）−ｘ''（６）＋ｊｘ''（７）
ｘ'''（６）＝ｘ''（４）−ｘ''（５）＋ｘ''（６）−ｘ''（７）
ｘ'''（７）＝ｘ''（４）＋ｊｘ''（５）−ｘ''（６）−ｊｘ''（７）
・・・式（４−３）
【０１０１】
上記計算式を整理すると以下のようになる。
ｘ'''（０）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８０＋ｘ（２）Ｗ８０＋ｘ（３）Ｗ８０＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８０＋ｘ（６）Ｗ８０＋ｘ（７）Ｗ８０
ｘ'''（１）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８２＋ｘ（２）Ｗ８４＋ｘ（３）Ｗ８６＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８２＋ｘ（６）Ｗ８４＋ｘ（７）Ｗ８６
ｘ'''（２）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８４＋ｘ（２）Ｗ８０＋ｘ（３）Ｗ８４＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８４＋ｘ（６）Ｗ８０＋ｘ（７）Ｗ８４
ｘ'''（３）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８６＋ｘ（２）Ｗ８４＋ｘ（３）Ｗ８２＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８６＋ｘ（６）Ｗ８４＋ｘ（７）Ｗ８２
ｘ'''（４）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８１＋ｘ（２）Ｗ８２＋ｘ（３）Ｗ８３＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８５＋ｘ（６）Ｗ８６＋ｘ（７）Ｗ８７
ｘ'''（５）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８３＋ｘ（２）Ｗ８６＋ｘ（３）Ｗ８１＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８７＋ｘ（６）Ｗ８２＋ｘ（７）Ｗ８５
ｘ'''（６）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８５＋ｘ（２）Ｗ８２＋ｘ（３）Ｗ８７＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８１＋ｘ（６）Ｗ８６＋ｘ（７）Ｗ８３
ｘ'''（７）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８７＋ｘ（２）Ｗ８６＋ｘ（３）Ｗ８５＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８３＋ｘ（６）Ｗ８２＋ｘ（７）Ｗ８１
・・・式（４−４）
【０１０２】
ここで、８点ＤＦＴの計算結果は、以下の式（４−５）から、式（４−６）のように表される。
【０１０３】
【数２】
2011133957.tif 000004
【０１０４】
Ｘ（０）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８０＋ｘ（２）Ｗ８０＋ｘ（３）Ｗ８０＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８０＋ｘ（６）Ｗ８０＋ｘ（７）Ｗ８０
Ｘ（１）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８１＋ｘ（２）Ｗ８２＋ｘ（３）Ｗ８３＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８５＋ｘ（６）Ｗ８６＋ｘ（７）Ｗ８７
Ｘ（２）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８２＋ｘ（２）Ｗ８４＋ｘ（３）Ｗ８６＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８２＋ｘ（６）Ｗ８４＋ｘ（７）Ｗ８６
Ｘ（３）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８３＋ｘ（２）Ｗ８６＋ｘ（３）Ｗ８１＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８７＋ｘ（６）Ｗ８２＋ｘ（７）Ｗ８５
Ｘ（４）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８４＋ｘ（２）Ｗ８０＋ｘ（３）Ｗ８４＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８４＋ｘ（６）Ｗ８０＋ｘ（７）Ｗ８４
Ｘ（５）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８５＋ｘ（２）Ｗ８２＋ｘ（３）Ｗ８７＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８１＋ｘ（６）Ｗ８６＋ｘ（７）Ｗ８３
Ｘ（６）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８６＋ｘ（２）Ｗ８４＋ｘ（３）Ｗ８２＋ｘ（４）Ｗ８０＋ｘ（５）Ｗ８６＋ｘ（６）Ｗ８４＋ｘ（７）Ｗ８２
Ｘ（７）＝ｘ（０）Ｗ８０＋ｘ（１）Ｗ８７＋ｘ（２）Ｗ８６＋ｘ（３）Ｗ８５＋ｘ（４）Ｗ８４＋ｘ（５）Ｗ８３＋ｘ（６）Ｗ８２＋ｘ（７）Ｗ８１
・・・式（４−６）
【０１０５】
したがって、第４の実施形態にかかるＦＦＴ処理部２６は、８点ＤＦＴと同様の演算結果を得ることが分かる。
以上のように、基数４のバタフライ演算アルゴリズムを適用したバタフライ演算制御部と、基数４バタフライ演算処理部とを組み合わせることによって、ＦＦＴポイント数がＮ＝２（２ｎ−１）（ｎは１以上の整数）の処理対象データに対して、ＦＦＴ演算処理を行うことができる。
【０１０６】
なお、本実施形態においては、基数が４であるバタフライ演算アルゴリズムを適用して、ＦＦＴポイント数がＮ＝２（２ｎ−１）の処理対象データに対してＦＦＴ演算処理を行うとしたが、基数が４ｍ（ｍは１以上の整数）であるバタフライ演算アルゴリズムを適用して、ＦＦＴポイント数がＮ＝２（２ｎ−１）であるデータについてバタフライ演算を行うように構成してもよい。
この場合、基数４ｍのバタフライ演算部は、Ａ／Ｄ変換部１０４からの１個の処理対象データと、メモリからの（２Ｍ−１）個（Ｍは１以上の整数）の処理対象データと、値が０である（４ｍ−２Ｍ）個のデータとを入力され、入力されたデータに対して基数４ｍのバタフライ演算を行うようにしてもよい。
このとき、切替部は、このバタフライ演算部から２Ｍ個の演算結果データを受け入れ、メモリは、切替部から出力された２ｍ個のデータのうちの（２ｍ−１）個のデータを格納するようにしてもよい。
【産業上の利用可能性】
【０１０７】
本発明は、演算装置に利用可能である。
【符号の説明】
【０１０８】
１・・・受信機、１００・・・アンテナ、１０２・・・受信回路、１０４・・・Ａ／Ｄ変換部、２０・・・ＦＦＴ処理部、１０６・・・復調部、２００・・・フィードバック演算部、２０２・・・乗算部、２０４・・・メモリ、２１０・・・基数２バタフライ演算制御部、２１２・・・基数２バタフライ演算部、２１４・・・切替部、２２・・・ＦＦＴ処理部、２２０・・・フィードバック演算部、２２４，２２６，２２８・・・メモリ、２３０・・・基数４バタフライ演算制御部、２３２・・・基数４バタフライ演算部、２３４・・・切替部、２４・・・ＦＦＴ処理部、２４０・・・フィードバック演算部、２４４・・・メモリ、２５０・・・バタフライ演算制御部、２５２・・・基数４バタフライ演算部、２５４・・・切替部、２６・・・ＦＦＴ処理部、２６０・・・フィードバック演算部、２６２・・・乗算部、２８０・・・フィードバック演算部、２６４・・・メモリ、２７０・・・バタフライ演算制御部、２８４，２８６，２８８・・・メモリ、２９０・・・基数４バタフライ演算制御部、２７２・・・基数４バタフライ演算部、２７４・・・切替部、２９２・・・基数４バタフライ演算部、２９４・・・切替部
【図１】
2011133957.tif 000005
【図２】
2011133957.tif 000006
【図３】
2011133957.tif 000007
【図４】
2011133957.tif 000008
【図５】
2011133957.tif 000009
【図６】
2011133957.tif 000010
【図７】
2011133957.tif 000011
【図８】
2011133957.tif 000012
【図９】
2011133957.tif 000013
【図１０】
2011133957.tif 000014
【図１１】
2011133957.tif 000015
【図１２】
2011133957.tif 000016
【図１３】
2011133957.tif 000017
【図１４】
2011133957.tif 000018
【図１５】
2011133957.tif 000019
【図１６】
2011133957.tif 000020
【図１７】
2011133957.tif 000021