(57)【特許請求の範囲】
【請求項１】
Ｋ×Ｍ（Ｋは２以上の整数、Ｍは２以上の整数）個のデータのうち、ｋ（ｋ＝１，・・・，Ｋ）番目のデータがＫ個のデータ列におけるそれぞれの先頭のデータであり、前記Ｋ個のデータ列が、前記Ｋ×Ｍ個のデータのうち、それぞれの先頭のデータを起点とする並び順でＫ個おきのＭ個のデータをそれぞれ含んでおり、
前記Ｋ個のデータ列のうち、いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点のフーリエ変換、又は、前記いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点の逆フーリエ変換を実施し、Ｍ点の変換結果として、Ｍ点のフーリエ変換の変換結果、又は、Ｍ点の逆フーリエ変換の変換結果を出力するＫ個の変換器と、
前記Ｋ個の変換器の中の、２番目の変換器からＫ番目の変換器のうち、いずれか１つの変換器から出力されたＭ点の変換結果に含まれているｃ（ｃ＝１，・・・，Ｍ）番目の変換結果の位相を、２π（（ｃ−１）（ｋ−１）／（Ｋ×Ｍ））（ｋ＝２，・・・，Ｋ）だけ遅らせる移相を実施し、位相移相後のＭ点の変換結果を出力する（Ｋ−１）個の第１の位相乗算器と、
前記Ｋ個の変換器の中の、１番目の変換器から出力されたＭ点の変換結果と、前記（Ｋ−１）個の第１の位相乗算器から出力されたＭ点の変換結果とを加算する加算器と
を備えたフーリエ変換装置。
【請求項２】
前記１番目の変換器から出力されたＭ点の変換結果を前記加算器に出力し、前記（Ｋ−１）個の第１の位相乗算器のうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器から出力されたＭ点の変換結果の位相を、２π（（ｋ−１）／Ｋ）だけ進める移相を実施し、位相移相後のＭ点の変換結果を前記加算器に出力する第２の位相乗算器を備え、
前記加算器は、前記１番目の変換器から出力されたＭ点の変換結果と、前記第２の位相乗算器から出力された（Ｋ−１）個のＭ点の変換結果とを加算することを特徴とする請求項１記載のフーリエ変換装置。
【請求項３】
前記第２の位相乗算器は、前記１番目の変換器から出力されたＭ点の変換結果を前記加算器に出力し、前記（Ｋ−１）個の第１の位相乗算器のうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器から出力されたＭ点の変換結果の位相を、２πｉ（（ｋ−１）／Ｋ）（ｉは１以上の整数）だけ進める移相を実施し、位相移相後のＭ点の変換結果を前記加算器に出力することを特徴とする請求項２記載のフーリエ変換装置。
【請求項４】
前記（Ｋ−１）個の第１の位相乗算器と、前記第２の位相乗算器とが、１つの位相乗算器に含まれていることを特徴とする請求項２記載のフーリエ変換装置。
【請求項５】
Ｋ×Ｍ（Ｋは２以上の整数、Ｍは２以上の整数）個のデータのうち、ｋ（ｋ＝１，・・・，Ｋ）番目のデータがＫ個のデータ列におけるそれぞれの先頭のデータであり、前記Ｋ個のデータ列が、前記Ｋ×Ｍ個のデータのうち、それぞれの先頭のデータを起点とする並び順でＫ個おきのＭ個のデータをそれぞれ含んでおり、
Ｋ個の変換器のそれぞれが、前記Ｋ個のデータ列のうち、いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点のフーリエ変換、又は、前記いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点の逆フーリエ変換を実施し、Ｍ点の変換結果として、Ｍ点のフーリエ変換の変換結果、又は、Ｍ点の逆フーリエ変換の変換結果を出力し、
（Ｋ−１）個の第１の位相乗算器のそれぞれが、前記Ｋ個の変換器の中の、２番目の変換器からＫ番目の変換器のうち、いずれか１つの変換器から出力されたＭ点の変換結果に含まれているｃ（ｃ＝１，・・・，Ｍ）番目の変換結果の位相を、２π（（ｃ−１）（ｋ−１）／（Ｋ×Ｍ））（ｋ＝２，・・・，Ｋ）だけ遅らせる移相を実施して、位相移相後のＭ点の変換結果を出力し、
加算器が、前記Ｋ個の変換器の中の、１番目の変換器から出力されたＭ点の変換結果と、前記（Ｋ−１）個の第１の位相乗算器から出力されたＭ点の変換結果とを加算する
フーリエ変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、フーリエ変換又は逆フーリエ変換を実施するフーリエ変換装置及びフーリエ変換方法に関するものである。
【背景技術】
【０００２】
以下の特許文献１には、ポイント数２ＮのＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）回路よりも、低ポイント数のＦＦＴ回路として、ポイント数ＮのＦＦＴ回路を用いて、ポイント数２Ｎのデータ列をフーリエ変換するフーリエ変換回路が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−１１５８１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１に開示されているフーリエ変換回路は、後段の回路が、フーリエ変換結果の一部のみを必要とする場合であっても、ポイント数２Ｎのデータ列をフーリエ変換しなければならない。したがって、後段の回路が、フーリエ変換結果の一部のみを必要とする場合であっても、フーリエ変換の処理時間を短縮することができないという課題があった。【０００５】
この発明は上記のような課題を解決するためになされたもので、後段の回路が、フーリエ変換結果の一部、又は、逆フーリエ変換結果の一部のみを必要とする場合、フーリエ変換結果の全部、又は、逆フーリエ変換結果の全部を必要する場合よりも、フーリエ変換の処理時間、又は、逆フーリエ変換の処理時間を短縮することができるフーリエ変換装置及びフーリエ変換方法を得ることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係るフーリエ変換装置は、Ｋ×Ｍ（Ｋは２以上の整数、Ｍは２以上の整数）個のデータのうち、ｋ（ｋ＝１，・・・，Ｋ）番目のデータがＫ個のデータ列におけるそれぞれの先頭のデータであり、Ｋ個のデータ列が、Ｋ×Ｍ個のデータのうち、それぞれの先頭のデータを起点とする並び順でＫ個おきのＭ個のデータをそれぞれ含んでおり、Ｋ個のデータ列のうち、いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点のフーリエ変換、又は、いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点の逆フーリエ変換を実施し、Ｍ点の変換結果として、Ｍ点のフーリエ変換の変換結果、又は、Ｍ点の逆フーリエ変換の変換結果を出力するＫ個の変換器と、Ｋ個の変換器の中の、２番目の変換器からＫ番目の変換器のうち、いずれか１つの変換器から出力されたＭ点の変換結果に含まれているｃ（ｃ＝１，・・・，Ｍ）番目の変換結果の位相を、２π（（ｃ−１）（ｋ−１）／（Ｋ×Ｍ））（ｋ＝２，・・・，Ｋ）だけ遅らせる移相を実施し、位相移相後のＭ点の変換結果を出力する（Ｋ−１）個の第１の位相乗算器と、Ｋ個の変換器の中の、１番目の変換器から出力されたＭ点の変換結果と、（Ｋ−１）個の第１の位相乗算器から出力されたＭ点の変換結果とを加算する加算器とを備えるようにしたものである。
【発明の効果】
【０００７】
この発明によれば、後段の回路が、フーリエ変換結果の一部、又は、逆フーリエ変換結果の一部のみを必要とする場合、フーリエ変換結果の全部、又は、逆フーリエ変換結果の全部を必要する場合よりも、フーリエ変換の処理時間、又は、逆フーリエ変換の処理時間を短縮することができる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１に係るフーリエ変換装置を示す構成図である。
【図２】実施の形態１に係る他のフーリエ変換装置を示す構成図である。
【図３】フーリエ変換装置が、ソフトウェア又はファームウェア等によって実現される場合のコンピュータのハードウェア構成図である。
【図４】図１に示すフーリエ変換装置の処理手順であるフーリエ変換方法を示すフローチャートである。
【図５】実施の形態２に係るフーリエ変換装置を示す構成図である。
【図６】実施の形態２に係る他のフーリエ変換装置を示す構成図である。
【図７】実施の形態３に係るフーリエ変換装置を示す構成図である。
【図８】実施の形態３に係る他のフーリエ変換装置を示す構成図である。
【図９】実施の形態４に係るフーリエ変換装置を示す構成図である。
【図１０】実施の形態４に係る他のフーリエ変換装置を示す構成図である。
【図１１】実施の形態５に係るフーリエ変換装置を示す構成図である。
【発明を実施するための形態】
【０００９】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
【００１０】
実施の形態１．
図１は、実施の形態１に係るフーリエ変換装置を示す構成図である。
図１に示すフーリエ変換装置には、Ｋ個のデータ列１ｋ（ｋ＝１，・・・，Ｋ）が入力される。Ｋは、２以上の整数である。
Ｋ個のデータ列１ｋは、Ｋ×Ｍ個のデータのうち、１番目のデータを起点とする並び順で（（ｋ−１）Ｍ＋１）番目のデータを先頭のデータとして含んでいる。
Ｋ個のデータ列１ｋは、それぞれの先頭のデータのほかに、Ｋ×Ｍ個のデータのうち、それぞれの先頭のデータを起点とする並び順で、連続している（Ｍ−１）個のデータをそれぞれ含んでいる。
Ｍは、２以上の整数である。Ｋ×Ｍ個のデータは、実数のデータであってもよいし、複素数のデータであってもよい。
Ｋ個のデータ列１ｋの具体例は、以下の通りである。
【００１１】
データ列１１は、データＤ１、データＤ２、・・・、データＤＭを含んでおり、データＤ１、データＤ２、・・・、データＤＭの順番で加算器２に入力される。
データ列１１＝｛Ｄ１、Ｄ２、・・・、ＤＭ｝
データ列１２は、データＤＭ＋１、データＤＭ＋２、・・・、データＤ２Ｍを含んでおり、データＤＭ＋１、データＤＭ＋２、・・・、データＤ２Ｍの順番で加算器２に入力される。
データ列１２＝｛ＤＭ＋１、ＤＭ＋２、・・・、Ｄ２Ｍ｝
データ列１３は、データＤ２Ｍ＋１、データＤ２Ｍ＋２、・・・、データＤ３Ｍを含んでおり、データＤ２Ｍ＋１、データＤ２Ｍ＋２、・・・、データＤ３Ｍの順番で加算器２に入力される。
データ列１３＝｛Ｄ２Ｍ＋１、Ｄ２Ｍ＋２、・・・、Ｄ３Ｍ｝
データ列１Ｋは、データＤ（Ｋ−１）Ｍ＋１、データＤ（Ｋ−１）Ｍ＋２、・・・、データＤＫ×Ｍを含んでおり、データＤ（Ｋ−１）Ｍ＋１、データＤ（Ｋ−１）Ｍ＋２、・・・、データＤＫ×Ｍの順番で加算器２に入力される。
データ列１Ｋ＝｛Ｄ（Ｋ−１）Ｍ＋１、Ｄ（Ｋ−１）Ｍ＋２、・・・、ＤＫ×Ｍ｝
【００１２】
加算器２は、例えば、加算回路によって実現される。
加算器２は、Ｋ個のデータ列１ｋに含まれているそれぞれのＭ個のデータの中から、それぞれの先頭のデータを起点とする並び順でｍ（ｍ＝１，・・・，Ｍ）番目のデータであるＫ個のデータの入力を受け付ける。
加算器２は、Ｋ個のデータの入力を受け付ける毎に、Ｋ個のデータの総和を算出し、算出したＫ個のデータの総和を変換器３に出力する。
【００１３】
変換器３は、例えば、変換回路によって実現される。
変換器３は、加算器２により算出されたＭ個の総和に対するＭ点のフーリエ変換、又は、Ｍ個の総和に対するＭ点の逆フーリエ変換を実施する。
変換器３は、変換結果４として、Ｍ点のフーリエ変換の変換結果（以下、「フーリエ変換結果」と称する）、又は、Ｍ点の逆フーリエ変換の変換結果（以下、「逆フーリエ変換結果」と称する）を外部に出力する。
変換器３により実施されるフーリエ変換は、高速フーリエ変換に限るものではなく、例えば、離散フーリエ変換も含まれる。
また、変換器３により実施される逆フーリエ変換は、逆高速フーリエ変換に限るものではなく、例えば、逆離散フーリエ変換も含まれる。
【００１４】
図１に示すフーリエ変換装置では、加算器２と変換器３とがシリアルに接続されている。しかし、これは一例に過ぎず、図２に示すように、加算器２と変換器３とがバス接続されているフーリエ変換装置であってもよい。図２は、実施の形態１に係る他のフーリエ変換装置を示す構成図である。
図１及び図２では、フーリエ変換装置の構成要素である加算器２及び変換器３のそれぞれが、専用のハードウェアによって実現されるものを想定している。
フーリエ変換装置の構成要素である加算器２及び変換器３のそれぞれは、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）、又は、これらを組み合わせたものが該当する。
【００１５】
フーリエ変換装置の構成要素は、専用のハードウェアによって実現されるものに限るものではなく、フーリエ変換装置が、ソフトウェア、ファームウェア、又は、ソフトウェアとファームウェアとの組み合わせによって実現されるものであってもよい。
ソフトウェア又はファームウェアは、プログラムとして、コンピュータのメモリに格納される。コンピュータは、プログラムを実行するハードウェアを意味し、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサ、あるいは、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）が該当する。
図３は、フーリエ変換装置が、ソフトウェア又はファームウェア等によって実現される場合のコンピュータのハードウェア構成図である。
フーリエ変換装置が、ソフトウェア又はファームウェア等によって実現される場合、加算器２及び変換器３の処理手順をコンピュータに実行させるためのプログラムがメモリ２１に格納される。そして、コンピュータのプロセッサ２２がメモリ２１に格納されているプログラムを実行する。
【００１６】
また、図１及び図２では、フーリエ変換装置の構成要素のそれぞれが専用のハードウェアによって実現される例を示し、図３では、フーリエ変換装置がソフトウェア又はファームウェア等によって実現される例を示している。しかし、これは一例に過ぎず、フーリエ変換装置における一部の構成要素が専用のハードウェアによって実現され、残りの構成要素がソフトウェア又はファームウェア等によって実現されるものであってもよい。
【００１７】
次に、図１に示すフーリエ変換装置の動作について説明する。
図４は、図１に示すフーリエ変換装置の処理手順であるフーリエ変換方法を示すフローチャートである。
Ｋ個のデータ列１Ｋ（ｋ＝１，・・・，Ｋ）は、並列に並べられている。
例えば、データ列１１に含まれているデータＤ１が加算器２に入力されるタイミングでは、データ列１２に含まれているデータＤＭ＋１と、データ列１３に含まれているデータＤ２Ｍ＋１と、データ列１Ｋに含まれているデータＤ（Ｋ−１）Ｍ＋１とが加算器２に入力される。
また、例えば、データ列１１に含まれているデータＤＭが加算器２に入力されるタイミングでは、データ列１２に含まれているデータＤ２Ｍと、データ列１３に含まれているデータＤ３Ｍと、データ列１Ｋに含まれているデータＤＫ×Ｍとが加算器２に入力される。
【００１８】
加算器２は、Ｋ個のデータ列１ｋに含まれているそれぞれのＭ個のデータの中から、それぞれの先頭のデータを起点とする並び順でｍ（ｍ＝１，・・・，Ｍ）番目のデータであるＫ個のデータの入力を受け付ける。
加算器２は、Ｋ個のデータの入力を受け付ける毎に、入力を受け付けたＫ個のデータの総和Σｍ（ｍ＝１，・・・，Ｍ）を算出する（図４のステップＳＴ１）。
ｍ＝１，・・・，Ｍであるため、加算器２は、Ｋ個のデータの総和ΣｍをＭ回算出し、Ｍ個の総和Σｍを変換器３に出力する。
加算器２によるＫ個のデータの具体的な総和算出は、以下の通りである。
【００１９】
加算器２は、例えば、ｍ＝１であれば、データＤ１、データＤＭ＋１、データＤ２Ｍ＋１、・・・及びデータＤ（Ｋ−１）Ｍ＋１の入力を受け付ける。
加算器２は、以下の式（１）に示すように、データＤ１、データＤＭ＋１、データＤ２Ｍ＋１、・・・及びデータＤ（Ｋ−１）Ｍ＋１の総和Σ１を算出する。
Σ１＝Ｄ１＋ＤＭ＋１＋Ｄ２Ｍ＋１＋・・・＋Ｄ（Ｋ−１）Ｍ＋１            （１）
加算器２は、例えば、ｍ＝２であれば、データＤ２、データＤＭ＋２、データＤ２Ｍ＋２、・・・及びデータＤ（Ｋ−１）Ｍ＋２の入力を受け付ける。
加算器２は、以下の式（２）に示すように、データＤ２、データＤＭ＋２、データＤ２Ｍ＋２、・・・及びデータＤ（Ｋ−１）Ｍ＋２の総和Σ２を算出する。
Σ２＝Ｄ２＋ＤＭ＋２＋Ｄ２Ｍ＋２＋・・・＋Ｄ（Ｋ−１）Ｍ＋２            （２）
加算器２は、例えば、ｍ＝Ｍであれば、データＤＭ、データＤ２Ｍ、データＤ３Ｍ、・・・及びデータＤＫ×Ｍの入力を受け付ける。
加算器２は、以下の式（３）に示すように、データＤＭ、データＤ２Ｍ、データＤ３Ｍ、・・・及びデータＤＫ×Ｍの総和ΣＭを算出する。
ΣＭ＝ＤＭ＋Ｄ２Ｍ＋Ｄ３Ｍ＋・・・＋ΣＫ×Ｍ        （３）
【００２０】
変換器３は、加算器２からＭ個の総和Σｍを受けると、Ｍ個の総和Σｍに対するＭ点のフーリエ変換、又は、Ｍ個の総和Σｍに対するＭ点の逆フーリエ変換を実施する（図４のステップＳＴ２）。
変換器３は、変換結果４として、フーリエ変換結果｛Ｒ１、ＲＭ＋１、Ｒ２Ｍ＋１、・・・、Ｒ（Ｋ−１）Ｍ＋１｝、又は、逆フーリエ変換結果｛Ｒ’１、Ｒ’Ｍ＋１、Ｒ’２Ｍ＋１、・・・、Ｒ’（Ｋ−１）Ｍ＋１｝を外部に出力する。
【００２１】
例えば、Ｋ＝２、Ｍ＝４であり、Ｋ×Ｍ（＝８）個のデータが｛Ｄ１、Ｄ２、・・・、Ｄ８｝であれば、データ列１ｋ（ｋ＝１，２）は、以下の通りである。
１１＝｛Ｄ１、Ｄ２、Ｄ３、Ｄ４｝
１２＝｛Ｄ５、Ｄ６、Ｄ７、Ｄ８｝
データ列１ｋ（ｋ＝１，２）が加算器２に入力されると、変換器３から、変換結果４として、４点のフーリエ変換結果｛Ｒ１、Ｒ３、Ｒ５、Ｒ７｝、又は、４点の逆フーリエ変換結果｛Ｒ’１、Ｒ’３、Ｒ’５、Ｒ’７｝が外部に出力される。
したがって、変換器３から変換結果４を受ける外部の回路が、例えば、８点のフーリエ変換結果｛Ｒ１、Ｒ２、・・・、Ｒ８｝のうち、４点のフーリエ変換結果｛Ｒ１、Ｒ３、Ｒ５、Ｒ７｝のみを必要とする場合、図１に示すフーリエ変換装置を外部の回路に適用することができる。
また、変換器３から変換結果４を受ける外部の回路が、例えば、８点の逆フーリエ変換結果｛Ｒ’１、Ｒ’２、・・・、Ｒ’８｝のうち、４点の逆フーリエ変換結果｛Ｒ’１、Ｒ’３、Ｒ’５、Ｒ’７｝のみを必要とする場合、図１に示すフーリエ変換装置を外部の回路に適用することができる。
【００２２】
図１に示すフーリエ変換装置は、Ｋ×Ｍ点のフーリエ変換を実施するＦＦＴ回路と比べて、処理速度が約Ｋ倍速くなり、かつ、回路規模が約Ｋ分の１になる。
例えば、Ｋ＝２であれば、図１に示すフーリエ変換装置は、Ｋ×Ｍ点のフーリエ変換を実施するＦＦＴ回路と比べて、処理速度が約２倍速くなり、かつ、回路規模が約２分の１になる。
例えば、Ｋ＝３であれば、図１に示すフーリエ変換装置は、Ｋ×Ｍ点のフーリエ変換を実施するＦＦＴ回路と比べて、処理速度が約３倍速くなり、かつ、回路規模が約３分の１になる。
なお、加算器２の回路規模は、変換器３の回路規模と比べて十分に小さいため、図１に示すフーリエ変換装置の回路規模として、加算器２の回路規模を考慮していない。
【００２３】
以上の実施の形態１は、Ｋ×Ｍ個のデータのうち、１番目のデータを起点とする並び順で（（ｋ−１）Ｍ＋１）（ｋ＝１，２）番目のデータがＫ個のデータ列におけるそれぞれの先頭のデータであり、Ｋ個のデータ列が、Ｋ×Ｍ個のデータのうち、それぞれの先頭のデータを起点とする並び順で、連続しているＭ個のデータをそれぞれ含んでいる。Ｋ個のデータ列に含まれているそれぞれのＭ個のデータの中で、それぞれの先頭のデータを起点とする並び順でｍ（ｍ＝１，・・・，Ｍ）番目のデータであるＫ個のデータの総和を算出する加算器２と、加算器２により算出されたＭ個の総和に対するＭ点のフーリエ変換、又は、Ｍ個の総和に対するＭ点の逆フーリエ変換を実施する変換器３とを備えるように、フーリエ変換装置を構成した。したがって、フーリエ変換装置は、後段の回路である外部の回路が、フーリエ変換結果の一部、又は、逆フーリエ変換結果の一部のみを必要とする場合、フーリエ変換結果の全部、又は、逆フーリエ変換結果の全部を必要する場合よりも、フーリエ変換の処理時間、又は、逆フーリエ変換の処理時間を短縮することができる。
【００２４】
実施の形態２．
実施の形態２では、加算器２及び変換器３のほかに、第１の位相乗算器５及び第２の位相乗算器６を備えるフーリエ変換装置について説明する。
図５は、実施の形態２に係るフーリエ変換装置を示す構成図である。
図５に示すフーリエ変換装置では、図１に示すフーリエ変換装置と同様に、Ｋは２以上の整数、Ｍは２以上の整数である。
【００２５】
図５において、図１と同一符号は同一又は相当部分を示すので説明を省略する。
第１の位相乗算器５は、例えば、位相乗算回路によって実現される。
第１の位相乗算器５は、Ｋ個のデータ列１ｋ（ｋ＝１，・・・，Ｋ）に含まれているそれぞれのＭ個のデータの中から、それぞれの先頭のデータを起点とする並び順でｍ番目のデータであるＫ個のデータの入力を受け付ける。
第１の位相乗算器５は、Ｋ個のデータの入力を受け付ける毎に、入力を受け付けたＫ個のデータのうち、ｋ（ｋ＝１，・・・，Ｋ）番目のデータの位相を、２π（ｋ−１）ｓ／Ｋだけ進ませる移相を実施する。
第１の位相乗算器５は、位相移相後のＭ個のデータを含むＫ個のデータ列１ｋを加算器２に出力する。
【００２６】
ｓは、０以上（Ｋ−１）以下のうちのいずれかの整数であり、変換器３によるＭ点のフーリエ変換結果｛Ｒ１＋ｓ、Ｒ（Ｋ＋１）＋ｓ、Ｒ（２Ｋ＋１）＋ｓ、・・・、Ｒ（（Ｍ−１）Ｋ＋１）＋ｓ｝、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’１＋ｓ、Ｒ’（Ｋ＋１）＋ｓ、Ｒ’（２Ｋ＋１）＋ｓ、・・・、Ｒ’（（Ｍ−１）Ｋ＋１）＋ｓ｝に応じて決定される。
具体的には、例えば、Ｋ＝２、Ｍ＝４であるとき、４点のフーリエ変換結果｛Ｒ１、Ｒ３、Ｒ５、Ｒ７｝、又は、４点の逆フーリエ変換結果｛Ｒ’１、Ｒ’３、Ｒ’５、Ｒ’７｝を外部の回路に出力する必要がある場合、ｓは、０に決定される。
例えば、Ｋ＝２、Ｍ＝４であるとき、４点のフーリエ変換結果｛Ｒ２、Ｒ４、Ｒ６、Ｒ８｝、又は、４点の逆フーリエ変換結果｛Ｒ’２、Ｒ’４、Ｒ’６、’Ｒ８｝を外部の回路に出力する必要がある場合、ｓは、１に決定される。
ｓは、第１の位相乗算器５及び第２の位相乗算器６におけるそれぞれの内部メモリに格納されていてもよいし、図５に示すフーリエ変換装置の外部から与えられるものであってもよい。
【００２７】
第２の位相乗算器６は、例えば、位相乗算回路によって実現される。
第２の位相乗算器６は、加算器２により算出されたＭ個の総和Σｍの位相を、２π（ｍ−１）ｓ／Ｎだけ遅らせる移相を実施し、位相移相後のＭ個の総和Σ’ｍを変換器３に出力する。Ｎ＝Ｋ×Ｍである。
【００２８】
図５に示すフーリエ変換装置では、第１の位相乗算器５と、加算器２と、第２の位相乗算器６と、変換器３とがシリアルに接続されている。しかし、これは一例に過ぎず、図６に示すように、第１の位相乗算器５と、加算器２と、第２の位相乗算器６と、変換器３とがバス接続されているフーリエ変換装置であってもよい。図６は、実施の形態２に係る他のフーリエ変換装置を示す構成図である。
図５及び図６では、フーリエ変換装置の構成要素である第１の位相乗算器５、加算器２、第２の位相乗算器６及び変換器３のそれぞれが、専用のハードウェアによって実現されるものを想定している。
フーリエ変換装置の構成要素である第１の位相乗算器５、加算器２、第２の位相乗算器６及び変換器３のそれぞれは、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡ、又は、これらを組み合わせたものが該当する。
【００２９】
フーリエ変換装置の構成要素は、専用のハードウェアによって実現されるものに限るものではなく、フーリエ変換装置が、ソフトウェア、ファームウェア、又は、ソフトウェアとファームウェアとの組み合わせによって実現されるものであってもよい。
フーリエ変換装置が、ソフトウェア又はファームウェア等によって実現される場合、第１の位相乗算器５、加算器２、第２の位相乗算器６及び変換器３の処理手順をコンピュータに実行させるためのプログラムが図３に示すメモリ２１に格納される。そして、図３に示すプロセッサ２２がメモリ２１に格納されているプログラムを実行する。
【００３０】
次に、図５に示すフーリエ変換装置の動作について説明する。
第１の位相乗算器５は、Ｋ個のデータ列１ｋ（ｋ＝１，・・・，Ｋ）に含まれているそれぞれのＭ個のデータの中から、それぞれの先頭のデータを起点とする並び順でｍ（ｍ＝１，・・・，Ｍ）番目のデータであるＫ個のデータの入力を受け付ける。
第１の位相乗算器５は、Ｋ個のデータの入力を受け付ける毎に、入力を受け付けたＫ個のデータのうち、ｋ番目のデータの位相を、２π（ｋ−１）ｓ／Ｋだけ進ませる移相を実施する。
第１の位相乗算器５は、位相移相後のＭ個のデータを含むＫ個のデータ列１ｋを加算器２に出力する。
第１の位相乗算器５によるｋ番目のデータの位相を進ませる具体的な移相は、以下の通りである。
【００３１】
例えば、ｍ＝１であれば、第１の位相乗算器５は、データＤ１、データＤＭ＋１、データＤ２Ｍ＋１、・・・及びデータＤ（Ｋ−１）Ｍ＋１の入力を受け付ける。
第１の位相乗算器５は、例えば、ｓ＝０であれば、入力を受け付けたＫ個のデータ｛Ｄ１、ＤＭ＋１、Ｄ２Ｍ＋１、・・・、Ｄ（Ｋ−１）Ｍ＋１｝のうち、ｋ番目のデータの位相を、０だけ進ませる移相を実施する。
第１の位相乗算器５は、例えば、ｓ＝１であれば、入力を受け付けたＫ個のデータ｛Ｄ１、ＤＭ＋１、Ｄ２Ｍ＋１、・・・、Ｄ（Ｋ−１）Ｍ＋１｝のうち、ｋ番目のデータの位相を、２π（ｋ−１）／Ｋだけ進ませる移相を実施する。
第１の位相乗算器５は、例えば、ｓ＝２であれば、入力を受け付けたＫ個のデータ｛Ｄ１、ＤＭ＋１、Ｄ２Ｍ＋１、・・・、Ｄ（Ｋ−１）Ｍ＋１｝のうち、ｋ番目のデータの位相を、４π（ｋ−１）／Ｋだけ進ませる移相を実施する。
第１の位相乗算器５は、例えば、ｓ＝Ｋ−１であれば、入力を受け付けたＫ個のデータ｛Ｄ１、ＤＭ＋１、Ｄ２Ｍ＋１、・・・、Ｄ（Ｋ−１）Ｍ＋１｝のうち、ｋ番目のデータの位相を、２π（ｋ−１）（Ｋ−１）／Ｋだけ進ませる移相を実施する。
【００３２】
加算器２は、第１の位相乗算器５から出力されたＫ個のデータ列１ｋに含まれているそれぞれのＭ個のデータの中から、それぞれの先頭のデータを起点とする並び順でｍ（ｍ＝１，・・・，Ｍ）番目のデータであるＫ個のデータの入力を受け付ける。
加算器２は、Ｋ個のデータの入力を受け付ける毎に、図１に示す加算器２と同様に、入力を受け付けたＫ個のデータの総和Σｍを算出する。ｍ＝１，・・・，Ｍであるため、加算器２は、Ｋ個のデータの総和ΣｍをＭ回算出し、Ｍ個の総和Σｍを第２の位相乗算器６に出力する。
【００３３】
第２の位相乗算器６は、加算器２から出力されたＭ個の総和Σｍを取得する。
第２の位相乗算器６は、取得したＭ個の総和Σｍの位相を、２π（ｍ−１）ｓ／Ｎだけ遅らせる移相を実施する。
第２の位相乗算器６は、位相移相後のＭ個の総和Σ’ｍを変換器３に出力する。
【００３４】
第２の位相乗算器６による総和Σｍの位相を遅らせる移相の移相量は、以下の通りである。
例えば、ｓ＝０であれば、総和Σｍの位相を遅らせる移相の移相量は、０である。
例えば、ｓ＝１、ｍ＝１であれば、総和Σｍの位相を遅らせる移相の移相量は、２π（１−１）×１／Ｎ＝０である。
例えば、ｓ＝１、ｍ＝２であれば、総和Σｍの位相を遅らせる移相の移相量は、２π（２−１）×１／Ｎ＝２π／Ｎである。
例えば、ｓ＝１、ｍ＝３であれば、総和Σｍの位相を遅らせる移相の移相量は、２π（３−１）×１／Ｎ＝４π／Ｎである。
例えば、ｓ＝１、ｍ＝Ｍであれば、総和Σｍの位相を遅らせる移相の移相量は、２π（Ｍ−１）×１／Ｎ＝２π（Ｍ−１）／Ｎである。
例えば、ｓ＝２、ｍ＝１であれば、総和Σｍの位相を遅らせる移相の移相量は、２π（１−１）×２／Ｎ＝０である。
例えば、ｓ＝２、ｍ＝２であれば、総和Σｍの位相を遅らせる移相の移相量は、２π（２−１）×２／Ｎ＝４π／Ｎである。
例えば、ｓ＝２、ｍ＝３であれば、総和Σｍの位相を遅らせる移相の移相量は、２π（３−１）×２／Ｎ＝８π／Ｎである。
例えば、ｓ＝２、ｍ＝Ｍであれば、総和Σｍの位相を遅らせる移相の移相量は、２π（Ｍ−１）×２／Ｎ＝４π（Ｍ−１）／Ｎである。
【００３５】
変換器３は、第２の位相乗算器６から位相移相後のＭ個の総和Σ’ｍ（ｍ＝１，・・・，Ｍ）を受けると、Ｍ個の総和Σ’ｍに対するＭ点のフーリエ変換、又は、Ｍ個の総和Σ’ｍに対するＭ点の逆フーリエ変換を実施する。
変換器３は、変換結果４として、Ｍ点のフーリエ変換結果｛Ｒ１＋ｓ、Ｒ（Ｋ＋１）＋ｓ、Ｒ（２Ｋ＋１）＋ｓ、・・・、Ｒ（（Ｍ−１）Ｋ＋１）＋ｓ｝、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’１＋ｓ、Ｒ’（Ｋ＋１）＋ｓ、Ｒ’（２Ｋ＋１）＋ｓ、・・・、Ｒ’（（Ｍ−１）Ｋ＋１）＋ｓ｝を外部に出力する。
例えば、Ｋ＝４、Ｍ＝４であるとき、ｓ＝０であれば、Ｍ＝４点のフーリエ変換結果は、｛Ｒ１、Ｒ５、Ｒ９、Ｒ１３｝、Ｍ＝４点の逆フーリエ変換結果は、｛Ｒ’１、Ｒ’５、Ｒ’９、Ｒ’１３｝である。
例えば、Ｋ＝４、Ｍ＝４であるとき、ｓ＝１であれば、Ｍ＝４点のフーリエ変換結果は、｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝、Ｍ＝４点の逆フーリエ変換結果は、｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝である。
【００３６】
図５に示すフーリエ変換装置は、Ｋ×Ｍ点のフーリエ変換を実施するＦＦＴ回路と比べて、処理速度が約Ｋ倍速くなり、かつ、回路規模が約Ｋ分の１になる。
なお、第１の位相乗算器５、加算器２及び第２の位相乗算器６の回路規模は、変換器３の回路規模と比べて十分に小さいため、図５に示すフーリエ変換装置の回路規模として、第１の位相乗算器５、加算器２及び第２の位相乗算器６の回路規模を考慮していない。
【００３７】
図５に示すフーリエ変換装置は、図１に示すフーリエ変換装置と同様に、後段の回路である外部の回路が、フーリエ変換結果の一部、又は、逆フーリエ変換結果の一部のみを必要とする場合、フーリエ変換結果の全部、又は、逆フーリエ変換結果の全部を必要する場合よりも、フーリエ変換の処理時間、又は、逆フーリエ変換の処理時間を短縮することができる。
また、図５に示すフーリエ変換装置は、ｓの値を変えることで、変換器３の変換結果４を変えることができる。
【００３８】
実施の形態３．
実施の形態３では、Ｋ個の変換器３２１〜３２Ｋを備えるフーリエ変換装置について説明する。
図７は、実施の形態３に係るフーリエ変換装置を示す構成図である。
【００３９】
図７に示すフーリエ変換装置には、Ｋ個のデータ列３１ｋ（ｋ＝１，・・・，Ｋ）が入力される。Ｋは、２以上の整数である。
Ｋ個のデータ列３１ｋは、Ｋ×Ｍ個のデータのうち、ｋ番目のデータを先頭のデータとして含んでいる。
Ｋ個のデータ列３１ｋは、先頭のデータのほかに、Ｋ×Ｍ個のデータのうち、先頭のデータを起点とする並び順でＫ個おきの（Ｍ−１）個のデータをそれぞれ含んでいる。
Ｍは、２以上の整数である。Ｋ×Ｍ個のデータは、実数のデータであってもよいし、複素数のデータであってもよい。
Ｋ個のデータ列３１ｋの具体例は、以下の通りである。
【００４０】
データ列３１１は、データＤ１、データＤＫ＋１、・・・、データＤ（Ｍ−１）Ｋ＋１を含んでおり、データＤ１、データＤＫ＋１、・・・、データＤ（Ｍ−１）Ｋ＋１の順番で変換器３２１に入力される。
データ列３１１＝｛Ｄ１、ＤＫ＋１、・・・、Ｄ（Ｍ−１）Ｋ＋１｝
データ列３１２は、データＤ２、データＤＫ＋２、・・・、データＤ（Ｍ−１）Ｋ＋２を含んでおり、データＤ２、データＤＫ＋２、・・・、データＤ（Ｍ−１）Ｋ＋２の順番で変換器３２２に入力される。
データ列３１２＝｛Ｄ２、ＤＫ＋２、・・・、Ｄ（Ｍ−１）Ｋ＋２｝
データ列３１３は、データＤ３、データＤＫ＋３、・・・、データＤ（Ｍ−１）Ｋ＋３を含んでおり、データＤ３、データＤＫ＋３、・・・、データＤ（Ｍ−１）Ｋ＋３の順番で変換器３２３に入力される。
データ列３１３＝｛Ｄ３、ＤＫ＋３、・・・、Ｄ（Ｍ−１）Ｋ＋３｝
データ列３１Ｋは、データＤＫ、データＤ２Ｋ、・・・、データＤＭＫを含んでおり、データＤＫ、データＤ２Ｋ、・・・、データＤＭＫの順番で変換器３２Ｋに入力される。
データ列３１Ｋ＝｛ＤＫ、Ｄ２Ｋ、・・・、ＤＭＫ｝
【００４１】
変換器３２ｋ（ｋ＝１，・・・，Ｋ）は、例えば、変換回路によって実現される。
変換器３２ｋは、データ列３１ｋに対するＭ点のフーリエ変換、又は、データ列３１ｋに対するＭ点の逆フーリエ変換を実施する。
変換器３２１は、Ｍ点の変換結果として、Ｍ点のフーリエ変換結果｛Ｒ１、ＲＫ＋１、・・・、Ｒ（Ｍ−１）Ｋ＋１｝、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’１、Ｒ’Ｋ＋１、・・・、Ｒ’（Ｍ−１）Ｋ＋１｝を加算器３４に出力する。
変換器３２ｋ（ｋ＝２，・・・，Ｋ）は、Ｍ点の変換結果として、Ｍ点のフーリエ変換結果｛Ｒｋ、ＲＫ＋ｋ、・・・、Ｒ（Ｍ−１）Ｋ＋ｋ｝、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’ｋ、Ｒ’Ｋ＋ｋ、・・・、Ｒ’（Ｍ−１）Ｋ＋ｋ｝を第１の位相乗算器３３ｋに出力する。
変換器３２ｋ（ｋ＝１，・・・，Ｋ）により実施されるフーリエ変換は、高速フーリエ変換に限るものではなく、例えば、離散フーリエ変換も含まれる。
また、変換器３２ｋ（ｋ＝１，・・・，Ｋ）により実施される逆フーリエ変換は、逆高速フーリエ変換に限るものではなく、例えば、逆離散フーリエ変換も含まれる。
【００４２】
第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）は、例えば、位相乗算回路によって実現される。
第１の位相乗算器３３ｋは、変換器３２ｋから出力されたＭ点のフーリエ変換結果｛Ｒｋ、ＲＫ＋ｋ、・・・、Ｒ（Ｍ−１）Ｋ＋ｋ｝、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’ｋ、Ｒ’Ｋ＋ｋ、・・・、Ｒ’（Ｍ−１）Ｋ＋ｋ｝の入力を受け付ける。
第１の位相乗算器３３ｋは、Ｍ点のフーリエ変換結果｛Ｒｋ、ＲＫ＋ｋ、・・・、Ｒ（Ｍ−１）Ｋ＋ｋ｝に含まれているｃ（ｃ＝１，・・・，Ｍ）番目の変換結果の位相、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’ｋ、Ｒ’Ｋ＋ｋ、・・・、Ｒ’（Ｍ−１）Ｋ＋ｋ｝に含まれているｃ番目の変換結果の位相を、２π（（ｃ−１）（ｋ−１）／（Ｋ×Ｍ））だけ遅らせる移相を実施する。
第１の位相乗算器３３ｋは、位相移相後のＭ点の変換結果を加算器３４に出力する。
【００４３】
加算器３４は、例えば、加算回路によって実現される。
加算器３４は、変換器３２１から出力されたＭ点の変換結果と、変換器３２２〜３２Ｋから出力されたＭ点の変換結果とを加算し、加算後の変換結果３５を外部に出力する。
【００４４】
図７に示すフーリエ変換装置では、変換器３２１と、加算器３４とがシリアルに接続され、また、変換器３２ｋ（ｋ＝２，・・・，Ｋ）と、第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）と、加算器３４とがシリアルに接続されている。しかし、これは一例に過ぎず、図８に示すように、変換器３２ｋ（ｋ＝１，・・・，Ｋ）と、第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）と、加算器３４とがバス接続されているフーリエ変換装置であってもよい。図８は、実施の形態３に係る他のフーリエ変換装置を示す構成図である。
図７及び図８では、フーリエ変換装置の構成要素である変換器３２ｋ（ｋ＝１，・・・，Ｋ）、第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）及び加算器３４のそれぞれが、専用のハードウェアによって実現されるものを想定している。
フーリエ変換装置の構成要素である変換器３２ｋ、第１の位相乗算器３３ｋ及び加算器３４のそれぞれは、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡ、又は、これらを組み合わせたものが該当する。
【００４５】
フーリエ変換装置の構成要素は、専用のハードウェアによって実現されるものに限るものではなく、フーリエ変換装置が、ソフトウェア、ファームウェア、又は、ソフトウェアとファームウェアとの組み合わせによって実現されるものであってもよい。
フーリエ変換装置が、ソフトウェア又はファームウェア等によって実現される場合、変換器３２ｋ、第１の位相乗算器３３ｋ及び加算器３４の処理手順をコンピュータに実行させるためのプログラムが図３に示すメモリ２１に格納される。そして、図３に示すプロセッサ２２がメモリ２１に格納されているプログラムを実行する。
【００４６】
次に、図７に示すフーリエ変換装置の動作について説明する。
変換器３２ｋ（ｋ＝１，・・・，Ｋ）は、データ列３１ｋの入力を受け付ける。
例えば、Ｋ＝４、Ｍ＝４であれば、以下に示すデータ列３１１が変換器３２１に入力され、以下に示すデータ列３１２が変換器３２２に入力される。また、以下に示すデータ列３１３が変換器３２３に入力され、以下に示すデータ列３１４が変換器３２４に入力される。
データ列３１１＝｛Ｄ１、Ｄ５、Ｄ９、Ｄ１３｝
データ列３１２＝｛Ｄ２、Ｄ６、Ｄ１０、Ｄ１４｝
データ列３１３＝｛Ｄ３、Ｄ７、Ｄ１１、Ｄ１５｝
データ列３１４＝｛Ｄ４、Ｄ８、Ｄ１２、Ｄ１６｝
【００４７】
変換器３２ｋは、データ列３１ｋに対するＭ点のフーリエ変換、又は、データ列３１ｋに対するＭ点の逆フーリエ変換を実施する。
例えば、Ｋ＝４、Ｍ＝４であれば、変換器３２１は、４点のフーリエ変換結果｛Ｒ１、Ｒ５、Ｒ９、Ｒ１３｝、又は、４点の逆フーリエ変換結果｛Ｒ’１、Ｒ’５、Ｒ’９、Ｒ’１３｝を加算器３４に出力する。変換器３２２は、４点のフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝、又は、４点の逆フーリエ変換結果｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝を第１の位相乗算器３３２に出力する。
変換器３２３は、４点のフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝、又は、４点の逆フーリエ変換結果｛Ｒ’３、Ｒ’７、Ｒ’１１、Ｒ’１５｝を第１の位相乗算器３３３に出力する。変換器３２４は、４点のフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝、又は、４点の逆フーリエ変換結果｛Ｒ’４、Ｒ’８、Ｒ’１２、Ｒ’１６｝を第１の位相乗算器３３４に出力する。
【００４８】
第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）は、変換器３２ｋから出力されたＭ点のフーリエ変換結果｛Ｒｋ、ＲＫ＋ｋ、・・・、Ｒ（Ｍ−１）Ｋ＋ｋ｝、又は、Ｍ点の逆フーリエ変換結果｛Ｒ’ｋ、Ｒ’Ｋ＋ｋ、・・・、Ｒ’（Ｍ−１）Ｋ＋ｋ｝の入力を受け付ける。
例えば、Ｋ＝４、Ｍ＝４であれば、第１の位相乗算器３３２は、４点のフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝、又は、４点の逆フーリエ変換結果｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝の入力を受け付ける。第１の位相乗算器３３３は、４点のフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝、又は、４点の逆フーリエ変換結果｛Ｒ’３、Ｒ’７、Ｒ’１１、Ｒ’１５｝の入力を受け付ける。第１の位相乗算器３３４は、４点のフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝、又は、４点の逆フーリエ変換結果｛Ｒ’４、Ｒ’８、Ｒ’１２、Ｒ’１６｝の入力を受け付ける。
【００４９】
第１の位相乗算器３３ｋは、入力を受け付けたＭ点のフーリエ変換結果｛Ｒｋ、ＲＫ＋ｋ、・・・、Ｒ（Ｍ−１）Ｋ＋ｋ｝に含まれているｃ（ｃ＝１，・・・，Ｍ）番目の変換結果の位相、又は、入力を受け付けたＭ点の逆フーリエ変換結果｛Ｒ’ｋ、Ｒ’Ｋ＋ｋ、・・・、Ｒ’（Ｍ−１）Ｋ＋ｋ｝に含まれているｃ番目の変換結果の位相を、２π（（ｃ−１）（ｋ−１）／（Ｋ×Ｍ））だけ遅らせる移相を実施する。
第１の位相乗算器３３ｋは、位相移相後のＭ点の変換結果を加算器３４に出力する。
例えば、Ｋ＝４、Ｍ＝４であれば、第１の位相乗算器３３２は、４点のフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝、又は、４点の逆フーリエ変換結果｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝の入力を受け付ける。
第１の位相乗算器３３２は、４点のフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝のうち、ｃ＝１番目の変換結果Ｒ２の位相、又は、４点の逆フーリエ変換結果｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝のうち、ｃ＝１番目の変換結果Ｒ’２の位相を、２π×（１−１）×（２−１）／（４×４）＝０だけ遅らせる移相を実施する。第１の位相乗算器３３２は、ｃ＝２番目の変換結果Ｒ６の位相、又は、ｃ＝２番目の変換結果Ｒ’６の位相を、２π×（２−１）×（２−１）／（４×４）＝π／８だけ遅らせる移相を実施する。第１の位相乗算器３３２は、ｃ＝３番目の変換結果Ｒ１０の位相、又は、ｃ＝３番目の変換結果Ｒ’１０の位相を、２π×（３−１）×（２−１）／（４×４）＝π／４だけ遅らせる移相を実施する。第１の位相乗算器３３２は、ｃ＝４番目の変換結果Ｒ１４の位相、又は、ｃ＝４番目の変換結果Ｒ’１４の位相を、２π×（４−１）×（２−１）／（４×４）＝３π／８だけ遅らせる移相を実施する。
第１の位相乗算器３３３は、４点のフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝、又は、４点の逆フーリエ変換結果｛Ｒ’３、Ｒ’７、Ｒ’１１、Ｒ’１５｝の入力を受け付ける。
第１の位相乗算器３３３は、４点のフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝のうち、ｃ＝１番目の変換結果Ｒ３の位相、又は、４点の逆フーリエ変換結果｛Ｒ’３、Ｒ’７、Ｒ’１１、Ｒ’１５｝のうち、ｃ＝１番目の変換結果Ｒ’３の位相を、２π×（１−１）×（３−１）／（４×４）＝０だけ遅らせる移相を実施する。第１の位相乗算器３３３は、ｃ＝２番目の変換結果Ｒ７の位相、又は、ｃ＝２番目の変換結果Ｒ’７の位相を、２π×（２−１）×（３−１）／（４×４）＝π／４だけ遅らせる移相を実施する。第１の位相乗算器３３３は、ｃ＝３番目の変換結果Ｒ１１の位相、又は、ｃ＝３番目の変換結果Ｒ’１１の位相を、２π×（３−１）×（３−１）／（４×４）＝π／２だけ遅らせる移相を実施する。第１の位相乗算器３３３は、ｃ＝４番目の変換結果Ｒ１５の位相、又は、ｃ＝４番目の変換結果Ｒ’１５の位相を、２π×（４−１）×（３−１）／（４×４）＝３π／４だけ遅らせる移相を実施する。
第１の位相乗算器３３４は、４点のフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝、又は、４点の逆フーリエ変換結果｛Ｒ’４、Ｒ’８、Ｒ’１２、Ｒ’１６｝の入力を受け付ける。
第１の位相乗算器３３４は、４点のフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝のうち、ｃ＝１番目の変換結果Ｒ４の位相、又は、４点の逆フーリエ変換結果｛Ｒ’４、Ｒ’８、Ｒ’１２、Ｒ’１６｝のうち、ｃ＝１番目の変換結果Ｒ’４の位相を、２π×（１−１）×（４−１）／（４×４）＝０だけ遅らせる移相を実施する。第１の位相乗算器３３４は、ｃ＝２番目の変換結果Ｒ８の位相、又は、ｃ＝２番目の変換結果Ｒ’８の位相を、２π×（２−１）×（４−１）／（４×４）＝３π／８だけ遅らせる移相を実施する。第１の位相乗算器３３４は、ｃ＝３番目の変換結果Ｒ１２の位相、又は、ｃ＝３番目の変換結果Ｒ’１２の位相を、２π×（３−１）×（４−１）／（４×４）＝３π／４だけ遅らせる移相を実施する。第１の位相乗算器３３４は、ｃ＝４番目の変換結果Ｒ１６の位相、又は、ｃ＝４番目の変換結果Ｒ’１６の位相を、２π×（４−１）×（４−１）／（４×４）＝９π／８だけ遅らせる移相を実施する。
【００５０】
加算器３４は、変換器３２１から出力されたＭ点の変換結果と、変換器３２２〜３２Ｋから出力された位相移相後のＭ点の変換結果とを加算する。
加算器３４は、加算後の変換結果３５を外部に出力する。
【００５１】
例えば、Ｋ＝４、Ｍ＝４であれば、加算器３４は、変換器３２１から出力されたフーリエ変換結果｛Ｒ１、Ｒ５、Ｒ９、Ｒ１３｝と、第１の位相乗算器３３２から出力されたフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝と、第１の位相乗算器３３３から出力されたフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝と、第１の位相乗算器３３４から出力されたフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝とを加算する。
加算器３４は、４点のフーリエ変換結果として、｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝を外部に出力する。
４点のフーリエ変換結果｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ１６｝に含まれているフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、Ｒ４｝に相当する。
あるいは、加算器３４は、変換器３２１から出力された逆フーリエ変換結果｛Ｒ’１、Ｒ’５、Ｒ’９、Ｒ’１３｝と、第１の位相乗算器３３２から出力された逆フーリエ変換結果｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝と、第１の位相乗算器３３３から出力された逆フーリエ変換結果｛Ｒ’３、Ｒ’７、Ｒ’１１、Ｒ’１５｝と、第１の位相乗算器３３４から出力された逆フーリエ変換結果｛Ｒ’４、Ｒ’８、Ｒ’１２、Ｒ’１６｝とを加算する。加算器３４は、４点の逆フーリエ変換結果として、｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝を外部に出力する。
４点の逆フーリエ変換結果｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点の逆フーリエ変換結果｛Ｒ’１、Ｒ’２、Ｒ’３、・・・Ｒ’１６｝に含まれている逆フーリエ変換結果｛Ｒ’１、Ｒ’２、Ｒ’３、Ｒ’４｝に相当する。
【００５２】
図７に示すフーリエ変換装置は、Ｋ×Ｍ点のフーリエ変換を実施するＦＦＴ回路と比べて、処理速度が約Ｋ倍速くなる。
例えば、Ｋ＝４であれば、処理速度が約４倍速くなり、例えば、Ｋ＝８であれば、処理速度が約８倍速くなる。
【００５３】
以上の実施の形態３では、Ｋ個のデータ列のうち、いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点のフーリエ変換、又は、いずれか１つのデータ列に含まれているＭ個のデータに対するＭ点の逆フーリエ変換を実施し、Ｍ点の変換結果として、Ｍ点のフーリエ変換の変換結果、又は、Ｍ点の逆フーリエ変換の変換結果を出力するＫ個の変換器３２１〜３２Ｋと、Ｋ個の変換器３２１〜３２Ｋの中の、２番目の変換器３２２からＫ番目の変換器３２Ｋのうち、いずれか１つの変換器３２ｋから出力されたＭ点の変換結果に含まれているｃ（ｃ＝１，・・・，Ｍ）番目の変換結果の位相を、２π（（ｃ−１）（ｋ−１）／（Ｋ×Ｍ））（ｋ＝２，・・・，Ｋ）だけ遅らせる移相を実施し、位相移相後のＭ点の変換結果を出力する（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋと、Ｋ個の変換器３２１〜３２Ｋの中の、１番目の変換器３２１から出力されたＭ点の変換結果と、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋから出力されたＭ点の変換結果とを加算する加算器３４とを備えるように、フーリエ変換装置を構成した。したがって、フーリエ変換装置は、後段の回路である外部の回路が、フーリエ変換結果の一部、又は、逆フーリエ変換結果の一部のみを必要とする場合、フーリエ変換結果の全部、又は、逆フーリエ変換結果の全部を必要する場合よりも、フーリエ変換の処理時間、又は、逆フーリエ変換の処理時間を短縮することができる。
【００５４】
実施の形態４．
実施の形態４では、第２の位相乗算器３６を備えるフーリエ変換装置について説明する。
図９は、実施の形態４に係るフーリエ変換装置を示す構成図である。
図９に示すフーリエ変換装置では、図７に示すフーリエ変換装置と同様に、Ｋは２以上の整数、Ｍは２以上の整数である。
【００５５】
図９において、図７と同一符号は同一又は相当部分を示すので説明を省略する。
第２の位相乗算器３６は、例えば、位相乗算回路によって実現される。
第２の位相乗算器３６は、Ｋ個の変換器３２１〜３２Ｋの中の、１番目の変換器３２１から出力されたＭ点の変換結果を加算器３４に出力する。
第２の位相乗算器３６は、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋのうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋから出力されたＭ点の変換結果の位相を、２π（（ｋ−１）／Ｋ）だけ進める移相を実施する。
第２の位相乗算器３６は、位相移相後のＭ点の変換結果を加算器３４に出力する。
【００５６】
図９に示すフーリエ変換装置では、変換器３２１と、第２の位相乗算器３６と、加算器３４とがシリアルに接続され、また、変換器３２ｋ（ｋ＝２，・・・，Ｋ）と、第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）と、第２の位相乗算器３６と、加算器３４とがシリアルに接続されている。しかし、これは一例に過ぎず、図１０に示すように、変換器３２ｋ（ｋ＝１，・・・，Ｋ）と、第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）と、第２の位相乗算器３６と、加算器３４とがバス接続されているフーリエ変換装置であってもよい。図１０は、実施の形態４に係る他のフーリエ変換装置を示す構成図である。
図９及び図１０では、フーリエ変換装置の構成要素である変換器３２ｋ（ｋ＝１，・・・，Ｋ）、第１の位相乗算器３３ｋ（ｋ＝２，・・・，Ｋ）、第２の位相乗算器３６及び加算器３４のそれぞれが、専用のハードウェアによって実現されるものを想定している。
フーリエ変換装置の構成要素である変換器３２ｋ、第１の位相乗算器３３ｋ、第２の位相乗算器３６及び加算器３４のそれぞれは、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡ、又は、これらを組み合わせたものが該当する。
【００５７】
フーリエ変換装置の構成要素は、専用のハードウェアによって実現されるものに限るものではなく、フーリエ変換装置が、ソフトウェア、ファームウェア、又は、ソフトウェアとファームウェアとの組み合わせによって実現されるものであってもよい。
フーリエ変換装置が、ソフトウェア又はファームウェア等によって実現される場合、変換器３２ｋ、第１の位相乗算器３３ｋ、第２の位相乗算器３６及び加算器３４の処理手順をコンピュータに実行させるためのプログラムが図３に示すメモリ２１に格納される。そして、図３に示すプロセッサ２２がメモリ２１に格納されているプログラムを実行する。
【００５８】
次に、図９に示すフーリエ変換装置の動作について説明する。
第２の位相乗算器３６以外は、図７に示すフーリエ変換装置と同様であるため、ここでは、主に、第２の位相乗算器３６の動作を説明する。
【００５９】
第２の位相乗算器３６は、変換器３２１から出力されたＭ点の変換結果と、変換器３２２〜３２Ｋから出力された位相移相後のＭ点の変換結果とを取得する。
第２の位相乗算器３６は、変換器３２１から出力されたＭ点の変換結果の位相については、移相せずに、Ｍ点の変換結果を加算器３４に出力する。
第２の位相乗算器３６は、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋのうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋから出力された変換結果の位相については、２π（（ｋ−１）／Ｋ）だけ進める移相を実施し、位相移相後のＭ点の変換結果を加算器３４に出力する。
例えば、Ｋ＝４、Ｍ＝４であれば、第２の位相乗算器３６は、第１の位相乗算器３３２から出力された４点のフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝の位相を２π（（２−１）／４）＝π／２だけ進める移相を実施する。第２の位相乗算器３６は、第１の位相乗算器３３３から出力された４点のフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝の位相を２π（（３−１）／４）＝πだけ進める移相を実施する。第２の位相乗算器３６は、第１の位相乗算器３３３から出力された４点のフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝の位相を２π（（４−１）／４）＝３π／２だけ進める移相を実施する。
【００６０】
加算器３４は、第２の位相乗算器３６から出力されたＫ個のフーリエ変換結果を加算し、又は、第２の位相乗算器３６から出力されたＫ個の逆フーリエ変換結果を加算する。
加算器３４は、加算後の変換結果３５を外部に出力する。
【００６１】
例えば、Ｋ＝４、Ｍ＝４であれば、加算器３４は、第２の位相乗算器３６から出力されたフーリエ変換結果｛Ｒ１、Ｒ５、Ｒ９、Ｒ１３｝と、第２の位相乗算器３６から出力されたフーリエ変換結果｛Ｒ２、Ｒ６、Ｒ１０、Ｒ１４｝と、第２の位相乗算器３６から出力されたフーリエ変換結果｛Ｒ３、Ｒ７、Ｒ１１、Ｒ１５｝と、第２の位相乗算器３６から出力されたフーリエ変換結果｛Ｒ４、Ｒ８、Ｒ１２、Ｒ１６｝とを加算する。
加算器３４は、４点のフーリエ変換結果として、｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝を外部に出力する。
４点のフーリエ変換結果｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ１６｝に含まれているフーリエ変換結果｛Ｒ５、Ｒ６、Ｒ７、Ｒ８｝に相当する。
あるいは、加算器３４は、変換器３２１から出力された逆フーリエ変換結果｛Ｒ’１、Ｒ’５、Ｒ’９、Ｒ’１３｝と、第１の位相乗算器３３２から出力された逆フーリエ変換結果｛Ｒ’２、Ｒ’６、Ｒ’１０、Ｒ’１４｝と、第１の位相乗算器３３３から出力された逆フーリエ変換結果｛Ｒ’３、Ｒ’７、Ｒ’１１、Ｒ’１５｝と、第１の位相乗算器３３４から出力された逆フーリエ変換結果｛Ｒ’４、Ｒ’８、Ｒ’１２、Ｒ’１６｝とを加算する。
加算器３４は、４点の逆フーリエ変換結果として、｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝を外部に出力する。
４点の逆フーリエ変換結果｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点の逆フーリエ変換結果｛Ｒ’１、Ｒ’２、Ｒ’３、・・・Ｒ’１６｝に含まれている逆フーリエ変換結果｛Ｒ’５、Ｒ’６、Ｒ’７、Ｒ’８｝に相当する。
【００６２】
以上の実施の形態４では、Ｋ個の変換器３２１〜３２Ｋの中の、１番目の変換器３２１から出力されたＭ点の変換結果を加算器３４に出力し、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋのうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋから出力されたＭ点の変換結果の位相を、２π（（ｋ−１）／Ｋ）だけ進める移相を実施し、位相移相後のＭ点の変換結果を加算器３４に出力する第２の位相乗算器３６を備えるように、フーリエ変換装置を構成した。したがって、フーリエ変換装置は、後段の回路である外部の回路が、フーリエ変換結果の一部、又は、逆フーリエ変換結果の一部のみを必要とする場合、フーリエ変換結果の全部、又は、逆フーリエ変換結果の全部を必要する場合よりも、フーリエ変換の処理時間、又は、逆フーリエ変換の処理時間を短縮することができる。
【００６３】
図９に示すフーリエ変換装置では、第２の位相乗算器３６が、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋのうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋから出力されたＭ点の変換結果の位相を、２π（（ｋ−１）／Ｋ）だけ進める移相を実施している。
しかし、これは一例に過ぎず、第２の位相乗算器３６は、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋのうち、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋから出力されたＭ点の変換結果の位相を、２πｉ（（ｋ−１）／Ｋ）（ｉは１以上の整数）だけ進める移相を実施するものであってもよい。
例えば、Ｋ＝４、Ｍ＝４であるとき、ｉ＝１であれば、加算器３４から外部に出力される４点のフーリエ変換結果｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ１６｝に含まれているフーリエ変換結果｛Ｒ５、Ｒ６、Ｒ７、Ｒ８｝に相当する。ｉ＝２であれば、加算器３４から外部に出力される４点のフーリエ変換結果｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ１６｝に含まれているフーリエ変換結果｛Ｒ９、Ｒ１０、Ｒ１１、Ｒ１２｝に相当する。ｉ＝３であれば、加算器３４から外部に出力される４点のフーリエ変換結果｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ１６｝に含まれているフーリエ変換結果｛Ｒ１３、Ｒ１４、Ｒ１５、Ｒ１６｝に相当する。
【００６４】
あるいは、例えば、Ｋ＝４、Ｍ＝４であるとき、ｉ＝１であれば、加算器３４から外部に出力される４点の逆フーリエ変換結果｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点の逆フーリエ変換結果｛Ｒ’１、Ｒ’２、Ｒ’３、・・・Ｒ’１６｝に含まれている逆フーリエ変換結果｛Ｒ’５、Ｒ’６、Ｒ’７、Ｒ’８｝に相当する。ｉ＝２であれば、加算器３４から外部に出力される４点の逆フーリエ変換結果｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点の逆フーリエ変換結果｛Ｒ’１、Ｒ’２、Ｒ’３、・・・Ｒ’１６｝に含まれている逆フーリエ変換結果｛Ｒ’９、Ｒ’１０、Ｒ’１１、Ｒ’１２｝に相当する。ｉ＝３であれば、加算器３４から外部に出力される４点の逆フーリエ変換結果｛Ｒ’１＋Ｒ’２＋Ｒ’３＋Ｒ’４、Ｒ’５＋Ｒ’６＋Ｒ’７＋Ｒ’８、Ｒ’９＋Ｒ’１０＋Ｒ’１１＋Ｒ’１２、Ｒ’１３＋Ｒ’１４＋Ｒ’１５＋Ｒ’１６｝は、Ｋ×Ｍ（＝４×４）個のデータに対する１６点の逆フーリエ変換結果｛Ｒ’１、Ｒ’２、Ｒ’３、・・・Ｒ’１６｝に含まれている逆フーリエ変換結果｛Ｒ’１３、Ｒ’１４、Ｒ’１５、Ｒ’１６｝に相当する。
【００６５】
また、第２の位相乗算器３６は、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋから出力されたＭ点の変換結果のうち、一部の変換結果の位相を０だけ進める移相を実施して、残りの変換結果の位相を、２π（（ｋ−１）／Ｋ）だけ進める移相を実施するようにしてもよい。
ここでは、Ｋ＝４、Ｍ＝１６、Ｎ＝６４であるとき、加算器３４が、６４点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ６４｝のうち、ｇ（ｇは、１以上、４９以下の整数）番目のフーリエ変換結果を起点とする１６点のフーリエ変換結果｛Ｒｇ、Ｒｇ＋１、Ｒｇ＋２、・・・Ｒｇ＋１４、Ｒｇ＋１５｝を出力する場合の動作を説明する。以下、ｇ＝１１の例を説明する。なお、ｇは、第２の位相乗算器３６及び加算器３４におけるそれぞれの内部メモリに格納されているものとする。ただし、ｇは、フーリエ変換装置の外部から与えられるものであってもよい。
【００６６】
第２の位相乗算器３６は、ｋ（ｋ＝２，・・・，Ｋ）番目の第１の位相乗算器３３ｋにより移相が進められた１６点の変換結果を取得する例を説明する。
第２の位相乗算器３６は、例えば、第１の位相乗算器３３２により移相が進められた１６点の変換結果｛Ｒ２、Ｒ６、Ｒ１０、・・・、Ｒ６２｝を取得し、例えば、第１の位相乗算器３３３により移相が進められた１６点の変換結果｛Ｒ３、Ｒ７、Ｒ１１、・・・、Ｒ６３｝を取得する。また、第２の位相乗算器３６は、例えば、第１の位相乗算器３３４により移相が進められた１６点の変換結果｛Ｒ４、Ｒ８、Ｒ１２、・・・、Ｒ６４｝を取得する。
なお、第２の位相乗算器３６は、変換器３２１から出力された１６点の変換結果｛Ｒ１、Ｒ５、Ｒ９、・・・、Ｒ６１｝も取得する。
【００６７】
第２の位相乗算器３６は、変換器３２１から出力された１６点の変換結果｛Ｒ１、Ｒ５、Ｒ９、・・・、Ｒ６１｝の位相については、移相せずに、１６点の変換結果｛Ｒ１、Ｒ５、Ｒ９、・・・、Ｒ６１｝を加算器３４に出力する。
第２の位相乗算器３６は、取得した１６点の変換結果｛Ｒ２、Ｒ６、Ｒ１０、・・・、Ｒ６２｝のうち、先頭の変換結果Ｒ２を起点として、並び順でｇ−１（＝１０）点の変換結果｛Ｒ２、Ｒ６、Ｒ１０、・・・、Ｒ３８｝の位相を、０だけ進める移相を実施する。０だけ進める移相の実施は、１０点の変換結果｛Ｒ２、Ｒ６、Ｒ１０、・・・、Ｒ３８｝の位相を進めないことに相当する。
第２の位相乗算器３６は、取得した１６点の変換結果｛Ｒ２、Ｒ６、Ｒ１０、・・・、Ｒ６２｝のうち、残りの６点の変換結果｛Ｒ４２、Ｒ４６、Ｒ５０、・・・、Ｒ６２｝の位相を、２π（（２−１）／４）＝π／２だけ進める移相を実施する。
【００６８】
第２の位相乗算器３６は、取得した１６点の変換結果｛Ｒ３、Ｒ７、Ｒ１１、・・・、Ｒ６３｝のうち、先頭の変換結果Ｒ３を起点として、並び順でｇ−１（＝１０）点の変換結果｛Ｒ３、Ｒ７、Ｒ１１、・・・、Ｒ３９｝の位相を、０だけ進める移相を実施する。
第２の位相乗算器３６は、取得した１６点の変換結果｛Ｒ３、Ｒ７、Ｒ１１、・・・、Ｒ６３｝のうち、残りの６点の変換結果｛Ｒ４３、Ｒ４７、Ｒ５１、・・・、Ｒ６３｝の位相を、２π（（３−１）／４）＝πだけ進める移相を実施する。
【００６９】
第２の位相乗算器３６は、取得した１６点の変換結果｛Ｒ４、Ｒ８、Ｒ１２、・・・、Ｒ６４｝のうち、先頭の変換結果Ｒ４を起点として、並び順でｇ−１（＝１０）点の変換結果｛Ｒ４、Ｒ８、Ｒ１２、・・・、Ｒ４０｝の位相を、０だけ進める移相を実施する。
第２の位相乗算器３６は、取得した１６点の変換結果｛Ｒ４、Ｒ８、Ｒ１２、・・・、Ｒ６４｝のうち、残りの６点の変換結果｛Ｒ４４、Ｒ４８、Ｒ５２、・・・、Ｒ６４｝の位相を、２π（（４−１）／４）＝３π／２だけ進める移相を実施する。
【００７０】
加算器３４は、第２の位相乗算器３６から出力された変換結果｛Ｒ１、Ｒ５、Ｒ９、・・・、Ｒ６１｝と、第２の位相乗算器３６から出力された変換結果｛Ｒ２、Ｒ６、Ｒ１０、・・・、Ｒ６２｝と、第２の位相乗算器３６から出力された変換結果｛Ｒ３、Ｒ７、Ｒ１１、・・・、Ｒ６３｝と、第２の位相乗算器３６から出力された変換結果｛Ｒ４、Ｒ８、Ｒ１２、・・・、Ｒ６４｝とを加算する。
加算器３４は、フーリエ変換結果として、｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６、・・・、Ｒ６１＋Ｒ６２＋Ｒ６３＋Ｒ６４｝を外部に出力する。
フーリエ変換結果｛Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４、Ｒ５＋Ｒ６＋Ｒ７＋Ｒ８、Ｒ９＋Ｒ１０＋Ｒ１１＋Ｒ１２、Ｒ１３＋Ｒ１４＋Ｒ１５＋Ｒ１６、・・・、Ｒ６１＋Ｒ６２＋Ｒ６３＋Ｒ６４｝は、Ｎ（＝６４）個のデータに対する６４点のフーリエ変換結果｛Ｒ１、Ｒ２、Ｒ３、・・・Ｒ６４｝に含まれているフーリエ変換結果｛Ｒ１１、Ｒ１２、Ｒ１３、Ｒ１４、Ｒ１５、Ｒ１６、Ｒ１７、Ｒ１８、Ｒ１９、Ｒ２０、Ｒ２１、Ｒ２２、Ｒ２３、Ｒ２４、Ｒ２５、Ｒ２６｝に相当する。
【００７１】
実施の形態５．
図９に示すフーリエ変換装置では、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋと、第２の位相乗算器３６とが別々のハードウェアであるものを示している。
しかし、これは一例に過ぎず、図１１に示すように、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋと、第２の位相乗算器３６とが、１つの位相乗算器３７に含まれているものであってもよい。
【００７２】
図１１は、実施の形態５に係るフーリエ変換装置を示す構成図である。
図１１において、図９と同一符号は同一又は相当部分を示すので説明を省略する。
位相乗算器３７は、（Ｋ−１）個の第１の位相乗算器３３２〜３３Ｋと、第２の位相乗算器３６とを備えている。
図１１に示すフーリエ変換装置の動作は、図９に示すフーリエ変換装置の動作と同様である。
位相乗算器３７は、図９に示す第１の位相乗算器３３２〜３３Ｋにおける移相の実施と、図９に示す第２の位相乗算器３６における移相の実施とを別々に行ってもよい。しかし、これに限るものではなく、位相乗算器３７は、図９に示す第１の位相乗算器３３２〜３３Ｋにおける移相処理と、図９に示す第２の位相乗算器３６における移相処理とを統合し、統合した移相処理を実施するようにしてもよい。
【００７３】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００７４】
この発明は、フーリエ変換又は逆フーリエ変換を実施するフーリエ変換装置及びフーリエ変換方法に適している。
【符号の説明】
【００７５】
１１，１２，１３，・・・，１Ｋ  データ列、２  加算器、３  変換器、４  変換結果、５  第１の位相乗算器、６  第２の位相乗算器、２１  メモリ、２２  プロセッサ、３１１，３１２，３１３，・・・，３１Ｋ  データ列、３２１〜３２Ｋ  変換器、３３２〜３３Ｋ  第１の位相乗算器、３４  加算器、３５  変換結果、３６  第２の位相乗算器、３７  位相乗算器。
【要約】
Ｋ×Ｍ個のデータのうち、１番目のデータを起点とする並び順で（（ｋ−１）Ｍ＋１）（ｋ＝１，２）番目のデータがＫ個のデータ列におけるそれぞれの先頭のデータであり、Ｋ個のデータ列が、Ｋ×Ｍ個のデータのうち、それぞれの先頭のデータを起点とする並び順で、連続しているＭ個のデータをそれぞれ含んでいる。Ｋ個のデータ列に含まれているそれぞれのＭ個のデータの中で、それぞれの先頭のデータを起点とする並び順でｍ（ｍ＝１，・・・，Ｍ）番目のデータであるＫ個のデータの総和を算出する加算器（２）と、加算器（２）により算出されたＭ個の総和に対するＭ点のフーリエ変換、又は、Ｍ個の総和に対するＭ点の逆フーリエ変換を実施する変換器（３）とを備えるように、フーリエ変換装置を構成した。【図１】
0006861887.tif 000002
【図２】
0006861887.tif 000003
【図３】
0006861887.tif 000004
【図４】
0006861887.tif 000005
【図５】
0006861887.tif 000006
【図６】
0006861887.tif 000007
【図７】
0006861887.tif 000008
【図８】
0006861887.tif 000009
【図９】
0006861887.tif 000010
【図１０】
0006861887.tif 000011
【図１１】
0006861887.tif 000012