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