(57)【要約】  互いに異なる演算ビット幅に対応したバタフライ演算を行う第１及び第２のバタフライ回路を備え、第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して第１及び第２のバタフライ回路を選択制御する制御手段を備える高速フーリエ変換回路とする。
2014080617.tif 000002
【特許請求の範囲】
【請求項１】
互いに異なる演算ビット幅に対応したバタフライ演算を行う第１及び第２のバタフライ回路を備えた高速フーリエ変換回路であって、
前記第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、前記第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して前記第１及び第２のバタフライ回路を選択制御する制御手段を備えることを特徴とする高速フーリエ変換回路。
【請求項２】
異なる変調方式が混在した信号処理において、
前記第１のバタフライ回路は、第１の演算ビット幅に対応する第１のバタフライ演算を実行し、
前記第２のバタフライ回路は、前記第１のバタフライ演算とともに、前記第１の演算ビット幅よりも大きな第２の演算ビット幅に対応する第２のバタフライ演算を実行することを特徴とする請求項１に記載の高速フーリエ変換回路。
【請求項３】
前記第１の動作モードにおいて、
前記第１のバタフライ回路は、前記第１のバタフライ演算を実行し、
前記第２のバタフライ回路は、前記第２のバタフライ演算を実行し、
前記第２の動作モードにおいて、
前記第２のバタフライ回路は、前記第１または第２のバタフライ演算のうち少なくとも一方を実行することを特徴とする請求項２に記載の高速フーリエ変換回路。
【請求項４】
前記制御手段は、
上位装置から送信された動作設定信号に基づいて前記第１及び第２のバタフライ回路のいずれかを選択する選択回路を有することを特徴とする請求項１乃至３のいずれか一項に記載の高速フーリエ変換回路。
【請求項５】
前記選択回路は、
前記第１のバタフライ回路による演算処理後のデータもしくは前記第２のバタフライ回路による演算処理後のデータのいずれか一方を選択して出力する第１の選択回路と、
前記第１のバタフライ回路による演算処理前のデータもしくは前記第１の選択回路による選択処理後のデータのいずれか一方を選択して出力する第２の選択回路と、を含み、
前記第１の動作モードにおいて、
前記第１の選択回路は、前記第１のバタフライ回路による演算処理後のデータを選択して出力し、
前記第２の選択回路は、前記第１のバタフライ回路による演算処理を経たデータを選択して出力し、
前記第２の動作モードにおいて、
前記第１の選択回路は、前記第２のバタフライ回路による演算処理後のデータを選択して出力し、
前記第２の選択回路は、前記第２のバタフライ回路が前記第１のバタフライ演算を行う場合には前記第１のバタフライ回路による演算処理前のデータを選択して出力し、前記第２のバタフライ回路が前記第２のバタフライ演算を行う場合には前記第１の選択回路によるデータ選択を経たデータを選択して出力することを特徴とする請求項４に記載の高速フーリエ変換回路。
【請求項６】
前記第１のバタフライ回路と前記第２のバタフライ回路との間に、高速フーリエ変換処理における複素平面上の複素回転を処理するひねり乗算回路を有することを特徴とする請求項２乃至５のいずれか一項に記載の高速フーリエ変換回路。
【請求項７】
高速フーリエ変換処理においてデータシーケンスの並べ替えを行う並べ替え回路を有することを特徴とする請求項６に記載の高速フーリエ変換回路。
【請求項８】
時間領域のデータをフーリエ変換して周波数領域の信号に変換する高速フーリエ変換回路であって、
入力された前記時間領域のデータを高速フーリエ変換処理のアルゴリズム上のデータ依存に基づいて並べ替える第１の並べ替え回路と、
前記第１の並べ替え回路から入力されたデータに対して第１のバタフライ演算を行う第１のバタフライ回路と、
入力されたデータを高速フーリエ変換処理のアルゴリズム上のデータ依存に基づいて並べ替える第２の並べ替え回路と、
前記第２の並べ替え回路から入力されたデータに対して複素平面上の複素回転を処理するひねり乗算回路と、
入力された信号に対して前記第１バタフライ演算とは異なる演算ビット幅に対応する第２のバタフライ演算を行う第２のバタフライ回路と、
前記第２のバタフライ回路から入力されたデータを高速フーリエ変換処理のアルゴリズム上のデータ依存に基づいて並べ替えて周波数領域の信号を出力する第３の並べ替え回路と、
前記第１または第２のバタフライ回路から入力したデータのうち一方を選択して前記第２の並べ替え回路に出力する第１の選択回路と、
前記ひねり乗算回路または前記第１の並べ替え回路から入力したデータのうち一方を選択して前記第２のバタフライ回路に出力する第２の選択回路と、を備え、
前記第１及び第２の選択回路は、上位装置の動作設定信号に基づいて、出力する信号を選択し、
前記第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、
前記第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して前記第１及び第２のバタフライ回路を選択制御することを特徴とする高速フーリエ変換回路。
【請求項９】
互いに異なる演算ビット幅で動作してバタフライ演算を行う第１及び第２のバタフライ回路を備えた高速フーリエ変換回路において、
前記第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、前記第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して前記第１及び第２のバタフライ回路を選択制御することを特徴とする高速フーリエ変換処理方法。
【請求項１０】
互いに異なる演算ビット幅で動作してバタフライ演算を行う第１及び第２のバタフライ回路を備えた高速フーリエ変換回路において、
前記第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、前記第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して前記第１及び第２のバタフライ回路を選択制御する処理をコンピュータに実行させる高速フーリエ変換処理プログラムを含むプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル信号処理における演算処理回路に関し、特に高速フーリエ変換回路に関する。
【背景技術】
【０００２】
無線通信や有線通信における信号伝送中の波形歪みを補償する技術として、周波数領域等化（ＦＤＥ）技術が知られている（ＦＤＥ：Ｆｒｅｑｕｅｎｃｙ  ｄｏｍａｉｎ  ｅｑｕａｌｉｚａｔｉｏｎ）。周波数領域等化（ＦＤＥ）においては、デジタル信号処理において重要な処理の１つである高速フーリエ変換（ＦＦＴ）処理が用いられている（ＦＦＴ：Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）。【０００３】
周波数領域等化（ＦＤＥ）は、高速フーリエ変換（ＦＦＴ）により時間領域上の信号データを周波数領域上のデータに変換した後に、等化のためのフィルタ処理を実施した上で、逆高速フーリエ変換（ＩＦＦＴ）により時間領域上の信号データに再変換する（ＩＦＦＴ：Ｉｎｖｅｒｓｅ  Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）。その結果、周波数領域等化（ＦＤＥ）によって信号の波形歪みを補償することができる。【０００４】
効率的なＦＦＴ／ＩＦＦＴ処理方式としては、Ｃｏｏｌｅｙ−Ｔｕｋｅｙによるバタフライ演算が知られている（非特許文献１）。しかしながら、ポイント数が大きなＣｏｏｌｅｙ−ＴｕｋｅｙによるＦＦＴ／ＩＦＦＴは回路が複雑になるため、Ｐｒｉｍｅ  Ｆａｃｔｏｒ法により２つの小さなＦＦＴ／ＩＦＦＴに分解して処理を行うことが一般的である（非特許文献２）。しかしながら、非特許文献２のような処理の全てを回路で実現した場合、その回路規模が膨大になる。そのため、必要な処理性能に応じて必要な処理の一部分のみを回路で実現し、その回路を繰り返し使用することによってＦＦＴ処理を実現する。【０００５】
また、ＦＦＴ処理を実現する回路方式としては、パイプライン回路方式によるものが知られている。パイプライン回路方式は、ＦＦＴ処理を構成する複数の内部処理をそれぞれパイプライン状に処理していくため、高いスループット性能（時間当たりの処理性能）を実現できるという特徴がある。【０００６】
特許文献１には、入力されたデータに対してＦＦＴ処理を実行するフーリエ変換機構２１１を備えたフーリエ変換処理装置２１０について開示されている。図１３に示した特許文献１のフーリエ変換機構２１１は、第一のバタフライ演算回路２２０と、複素乗算機２２１と、遅延要素２２２，２２４と、第五のコミュテータ２２３と、第二のバタフライ演算回路２２５と、を含む。【０００７】
特許文献１のフーリエ変換処理装置２１０は、入力されたデータの配列を並び替える第一及び第二のコミュテータ２１５，２１６と、第一及び第二のコミュテータ２１５，２１６それぞれによって並び替えられたデータを格納する第一及び第二のメモリ２１３，２１４と、をさらに備えている。また、フーリエ変換処理装置２１０は、第一及び第二のメモリ２１３，２１４にそれぞれ格納されたデータを並び替える第二及び第四のコミュテータ２１７，２１８をさらに備えている。【０００８】
特許文献１のフーリエ変換処理装置２１０によれば、第一のバタフライ演算回路２２０に入力するデータの配列を第一及び第二のコミュテータ２１５，２１６によって並び換える。そのため、特許文献１以前においては第一のバタフライ演算回路２２０の前に設けるコミュテータの前後に必要であった遅延要素を、特許文献１のフーリエ変換処理装置２１０においては設ける必要がなくなる。その結果、特許文献１のフーリエ変換処理装置２１０によれば、フーリエ変換処理装置を小型化でき、消費電力を抑制することができる。【０００９】
また、ＦＦＴ処理に対して、その演算精度や処理スループットなどの要求性能が様々に変化する場合がある。例えば、データ通信における伝送路状況に応じて変調方式を変更する場合などである。【００１０】
フィルタ処理などのデジタル信号処理に要求される処理スループットは、シンボルレートに比例する。また、フィルタ処理などのデジタル信号処理に要求される演算精度は、シンボル間距離が小さくなるほど、より高い精度の演算が必要となる。【００１１】
一般に、デジタル信号処理回路の演算精度は、主にデータの表現形式及びデータのビット幅で決定される。しかしながら、どのような表現形式においても、演算精度を高くするためにはデータのビット幅を大きくする必要がある。そのため、回路規模や消費電力を小さくするには、要求される演算精度に応じて、データのビット幅を必要十分な値に最適化する必要がある。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２０１２−８９０５３号公報
【非特許文献】
【００１３】
【非特許文献１】Ｊ．Ｗ．Ｃｏｏｌｅｙ、Ｊ．Ｗ．Ｔｕｋｅｙ、“Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  Ｍａｃｈｉｎｅ  Ｃａｌｃｕｌａｔｉｏｎ  ｏｆ  Ｃｏｍｐｌｅｘ  Ｆｏｕｒｉｅｒ  Ｓｅｒｉｅｓ、”  Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎ、Ｖｏｌ．１９、Ｎｏ．９０（１９６５）、ｐｐ．２９７−３０１
【非特許文献２】Ｄ．Ｐ．Ｋｏｌｂａ、“Ａ  Ｐｒｉｍｅ  Ｆａｃｔｏｒ  ＦＦＴ  Ａｌｇｏｒｉｔｈｍ  Ｕｓｉｎｇ  Ｈｉｇｈ−Ｓｐｅｅｄ  Ｃｏｎｖｏｌｕｔｉｏｎ、”ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ａｃｏｕｓｔｉｃｓ、  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、Ｖｏｌ２９、Ｎｏ．４（１９８１）
【発明の概要】
【発明が解決しようとする課題】
【００１４】
変調方式によって異なる性能要求に応じて、処理スループットや演算精度に関してそれぞれ個別に最適化した別のＦＦＴ回路で処理すれば、それぞれの変調方式に対して消費電力を最小化することが可能である。【００１５】
しかしながら、特許文献１のフーリエ変換処理装置のような回路構成においては、それぞれの変調方式における性能要求に対して最適化した複数のＦＦＴ回路が必要になることから、回路規模が膨大になるという問題がある。【００１６】
一方、異なる変調方式に対する全ての性能要求を満足する回路を１つのＦＦＴ回路で実現させた場合、個別に最適化した別のＦＦＴ回路を備えるよりも回路規模を小さくすることができるものの、消費電力が大きくなるという問題がある。【００１７】
本発明の目的は、処理スループットや演算精度といった性能要求の異なる変調方式が混在したデジタル信号処理におけるＦＦＴ処理において、回路規模と消費電力とを小さくすることが可能な高速フーリエ変換処理回路、高速フーリエ変換処理方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１８】
本発明の高速フーリエ変換回路は、互いに異なる演算ビット幅に対応したバタフライ演算を行なう第１及び第２のバタフライ回路を備えた高速フーリエ変換回路であって、第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して第１及び第２のバタフライ回路を選択制御する制御手段を備える。【００１９】
本発明の高速フーリエ変換回路は、時間領域のデータをフーリエ変換して周波数領域の信号に変換する高速フーリエ変換回路であって、入力された時間領域のデータを高速フーリエ変換処理のアルゴリズム上のデータ依存に基づいて並べ替える第１の並べ替え回路と、第１の並べ替え回路から入力されたデータに対して第１のバタフライ演算を行う第１のバタフライ演算回路と、入力されたデータを高速フーリエ変換処理のアルゴリズム上のデータ依存に基づいて並べ替える第２の並べ替え回路と、第２の並べ替え回路から入力されたデータに対して複素平面上の複素回転を処理するひねり乗算回路と、入力された信号に対して第１バタフライ演算とは異なる演算ビット幅に対応する第２のバタフライ演算を行う第２のバタフライ回路と、第２のバタフライ回路から入力されたデータを高速フーリエ変換処理のアルゴリズム上のデータ依存に基づいて並べ替えて周波数領域の信号を出力する第３の並べ替え回路と、第１または第２のバタフライ回路から入力したデータのうち一方を選択して第２の並べ替え回路に出力する第１の選択回路と、ひねり乗算回路または第１の並べ替え回路から入力したデータのうち一方を選択して第２のバタフライ回路に出力する第２の選択回路と、を備え、第１及び第２の選択回路は、上位装置の動作設定信号に基づいて、出力する信号を選択し、第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して第１及び第２のバタフライ回路を選択制御する。【００２０】
本発明の高速フーリエ変換処理方法は、互いに異なる演算ビット幅で動作してバタフライ演算を行なう第１及び第２のバタフライ回路を備えた高速フーリエ変換回路において、第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して第１及び第２のバタフライ回路を選択制御する。【００２１】
本発明のプログラムは、互いに異なる演算ビット幅で動作してバタフライ演算を行なう第１及び第２のバタフライ回路を備えた高速フーリエ変換回路において、第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して第１及び第２のバタフライ回路を選択制御する処理をコンピュータに実行させる。
【発明の効果】
【００２２】
本発明の高速フーリエ変換処理回路によれば、処理スループットや演算精度といった性能要求の異なる変調方式が混在したデジタル信号処理における高速フーリエ変換処理において、回路規模と消費電力とを小さくすることが可能となる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態に係るＦＦＴ回路の構成を示すブロック図である。
【図２】本発明の実施形態に係るＦＦＴ回路の動作を示すブロック図である。
【図３】本発明の実施形態に係るＦＦＴ回路の動作を示すタイミング図である。
【図４】本発明の実施形態に係るＦＦＴ回路の動作を示すブロック図である。
【図５】本発明の実施形態に係るＦＦＴ回路の動作を示すタイミング図である。
【図６】本発明の実施形態に係るＦＦＴ回路の動作を示す説明図である。
【図７】ＦＦＴ回路の構成例を示すブロック図である。
【図８】バタフライ処理に関するデータフロー図である。
【図９】逐次順序を示すテーブルである。
【図１０】ビットリバース順序を示すテーブルである。
【図１１】ＦＦＴ回路の動作例を示すタイミング図である。
【図１２】データ通信における変調方式の例を示す説明図である。
【図１３】特許文献１に係るフーリエ変換処理装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２４】
以下に、本発明を実施するための形態について図面を用いて説明する。ただし、以下に述べる実施形態には、本発明を実施するために技術的に好ましい限定がされているが、発明の範囲を以下に限定するものではない。
【００２５】
（パイプライン処理）
本発明の実施形態を説明する前に、図７〜１１を用いてＦＦＴ処理を用いたパイプライン処理について説明する。
【００２６】
（構成）
まず、図７を参照して、パイプライン回路方式によるＦＦＴ回路の構成例を説明する。図７において、ＦＦＴ回路１００は、時間領域のデータｘ（ｎ）を入力し、ＦＦＴ処理によりフーリエ変換した周波数領域の信号Ｘ（ｋ）を生成して出力する回路である（ｎ＝０、１、・・・、Ｎ−１；ｋ＝０、１、・・・、Ｎ−１）。なお、ＮはＦＦＴブロックサイズをあらわす正整数である。
【００２７】
図８は、６４ポイントＦＦＴ／ＩＦＦＴをＰｒｉｍｅ  Ｆａｃｔｏｒ法を利用して２段階の基数８のバタフライ処理１１２に分解したデータフロー図である。図８においては、時間領域のデータｘ（ｎ）を入力し、ＦＦＴ処理によりフーリエ変換した周波数領域の信号Ｘ（ｋ）を出力する（ｋ＝０、１、・・・、６３）。ただし、一部のデータフローの図示は省略している。
【００２８】
このデータフロー図の全てを回路で実現した場合、その回路規模が膨大になる。そのため、必要な処理性能に応じて、一部分を回路で実現し、その回路を繰り返し使用することで、ＦＦＴ処理を実現する方法を用いることができる。
【００２９】
例えば、図８において、８データ並列でＦＦＴ処理を行うＦＦＴ回路１００を物理的な回路として実装した場合、合計８回の繰り返し処理により６４ポイントＦＦＴ／ＩＦＦＴ処理を実現することができる。具体的には、１回目に、部分データフロー１１０ａに当たる処理を行い、２回目に、部分データフロー１１０ｂに当たる処理を行う。同様に、３〜７回目の処理を実行し、８回目に、部分データフロー１１０ｈに当たる処理を行う。このようにして、６４ポイントＦＦＴ／ＩＦＦＴ処理を実現することができる。
【００３０】
具体的には、図８の例において、ＦＦＴ回路１００は、８データ並列で６４ポイントＦＦＴ処理を行うとすると、時間領域のデータｘ（ｎ）を入力し、ＦＦＴ処理によりフーリエ変換した周波数領域の信号Ｘ（ｋ）を生成して出力する（ｋ＝０、１、・・・、６３）。このとき、入力データｘ（ｎ）は、８データずつ８サイクルの期間に、図９の逐次順序テーブル８０に示す順序で６４データが入力されるとする。なお、図９の逐次順序テーブル８０中の数値は、ｘ（ｎ）の括弧内の数値ｎを示す。具体的には、１サイクル目に、データ組Ａを構成するｘ（０）、ｘ（１）、・・・、ｘ（７）の８データが入力される。２サイクル目に、データ組Ｂを構成するｘ（８）、ｘ（９）、・・・、ｘ（１５）の８データが入力される。以降、３サイクル目から８サイクル目まで同様にして、データ組Ｃ〜Ｈを構成するデータが入力される。
【００３１】
同様に、出力データＸ（ｋ）は、８データずつ８サイクルの期間に、図９の逐次順序テーブル８０に示す順序で６４データを出力する。なお、図９の逐次順序テーブル８０中の数値は、Ｘ（ｋ）の括弧内の数値ｋを示す。具体的には、１サイクル目に、データ組Ａを構成するＸ（０）、Ｘ（１）、・・・、Ｘ（７）の８データを出力する。２サイクル目に、データ組Ｂを構成するＸ（８）、Ｘ（９）、・・・、Ｘ（１５）の８データを出力する。以降、３サイクル目から８サイクル目まで同様にして、データ組Ｃ〜Ｈを構成するデータを出力する。
【００３２】
図７のＦＦＴ回路１００は、第１データ並べ替え処理回路１０１、第１バタフライ演算処理回路１０２、第２データ並べ替え処理回路１０３、ひねり乗算処理回路１０４、第２バタフライ演算処理回路１０５、第３データ並べ替え処理回路１０６を備えている。ＦＦＴ回路１００は、前述の各構成要素において、第１のデータ並べ替え処理と、第１のバタフライ演算処理と、第２のデータ並べ替え処理と、ひねり乗算処理と、第２のバタフライ演算処理と、第３のデータ並べ替え処理とをパイプライン状に処理する。
【００３３】
第１データ並べ替え処理回路１０１、第２データ並べ替え処理回路１０３及び第３データ並べ替え処理回路１０６は、データ並べ替えのためのバッファ回路である。第１データ並べ替え処理回路１０１、第２データ並べ替え処理回路１０３及び第３データ並べ替え処理回路１０６は、バタフライ演算処理回路の前後で、ＦＦＴ処理のアルゴリズム上のデータ依存に基づいたデータシーケンスの並べ替えを行う。
【００３４】
第１バタフライ演算処理回路１０２及び第２バタフライ演算処理回路１０５は、ＦＦＴ処理を構成するバタフライ演算処理を行う。具体的には、第1データ並べ替え処理回路１０１は、図９の逐次順序テーブル８０に示す入力データｘ（ｎ）の入力順序を、図１０のビットリバース順序テーブル９０に示す順序に並べ替える。なお、これ以降、図９の逐次順序テーブル８０に示す入力データｘ（ｎ）の入力順序を逐次順序と表記し、図１０のビットリバース順序テーブル９０に示す順序をビットリバース順序と表記する。
【００３５】
図１０のビットリバース順序テーブル９０に示すビットリバース順序は、図８に示したデータフロー図における１段目（左側）の基数８のバタフライ処理１１２への入力データ組に対応する。具体的には、まず、１サイクル目に、データ組Ａを構成するｘ（０）、ｘ（８）、・・・、ｘ（５６）の８データを入力する。次に、２サイクル目に、データ組Ｂを構成するｘ（１）、ｘ（９）、・・・、ｘ（５７）の８データを入力する。以降、３サイクル目から８サイクル目まで同様にして、データ組Ｃ〜Ｈを構成するデータを入力する。
【００３６】
第１のバタフライ演算処理回路１０２は、図８のデータフロー図における１段目（左側）の基数８のバタフライ演算処理１１２を実行するバタフライ回路である。第１のバタフライ演算処理回路１０２は、バタフライ演算処理結果を、データｙ（ｎ）として、図９の逐次順序で出力する（ｎ＝０、１、・・・、６３）。
【００３７】
第２のデータ並べ替え処理回路１０３は、第１のバタフライ演算処理回路１０２が逐次順序（図９）で出力するデータｙ［ｎ］を、第２のバタフライ演算処理回路１０５に入力するビットリバース順序（図１０）に並べ替えを行う。第２のデータ並べ替え処理回路１０３は、図８においては、データ並べ替え処理１１１に対応する。
【００３８】
ひねり乗算処理回路１０４は、第１のバタフライ演算処理後にＦＦＴ演算における複素平面上の複素回転を処理する。ひねり乗算処理回路１０４は、図８においては、ひねり乗算処理１１３に対応する。
【００３９】
第２のバタフライ演算処理回路１０５は、図８のデータフロー図における２段目（右側）の基数８のバタフライ処理１１２を処理するバタフライ回路である。第２のバタフライ演算処理回路１０５は、図１０のビットリバース順序で入力されるひねり乗算処理後のデータｙ’（ｎ）に対してバタフライ演算処理を行い、その結果Ｘ（ｋ）を、図１０のビットリバース順序で出力する（ｎ＝０、１、・・・、６３）。
【００４０】
第３のデータ並べ替え処理回路１０６は、第２のバタフライ演算処理回路１０５が図１０のビットリバース順序で出力するデータＸ（ｋ）を、ＦＦＴ回路１００がＦＦＴ処理結果として出力する順序である図９の逐次順序に並べ替えを行う。
【００４１】
（動作）
次に、図１１を参照して、ＦＦＴ回路１００の動作例を説明する。図１１は、ＦＦＴ回路１００の動作を示すタイミング図である。図１１では、ＦＦＴ処理の処理単位であるＦＦＴブロックの例として、ＦＦＴブロックＦ１、ＦＦＴブロックＦ２及びＦＦＴブロックＦ３に対して時間Ｔ１〜Ｔ６において実行する処理を図示している。このＦ１〜Ｆ３のＦＦＴブロックは、入力する時間領域の信号ｘ（ｎ）をＦＦＴブロックの大きさごとに分割したデータブロックに相当する。
【００４２】
（内部処理）
図１１には、ＦＦＴ処理を（１）〜（９）の内部処理に分割して図示している。
【００４３】
（１）並べ替え１（ｗｒｉｔｅ）の処理は、第１データ並べ替え処理回路１０１に対するデータの書き込み処理である。
【００４４】
（２）並べ替え１（ｒｅａｄ）の処理は、第１データ並べ替え処理回路１０１によって並べ替えられたデータの読み出し処理である。
【００４５】
（３）バタフライ演算１の処理は、第１バタフライ演算処理回路１０２による第１のバタフライ演算処理である。
【００４６】
（４）並べ替え２（ｗｒｉｔｅ）の処理は、第２データ並べ替え処理回路１０３に対するデータの書き込み処理である。
【００４７】
（５）並べ替え２（ｒｅａｄ）の処理は、第２データ並べ替え処理回路１０３によって並べ替えられたデータの読み出し処理である。
【００４８】
（６）ひねり乗算の処理は、ひねり乗算処理回路１０４によるひねり乗算処理である。
【００４９】
（７）バタフライ演算２の処理は、第２バタフライ演算処理回路１０５による第２のバタフライ演算処理である。
【００５０】
（８）並べ替え３（ｗｒｉｔｅ）の処理は、第３データ並べ替え処理回路１０６に対するデータの書き込み処理である。
【００５１】
（９）並べ替え３（ｒｅａｄ）の処理は、第３データ並べ替え処理回路１０６によって並べ替えられたデータの読み出し処理である。
【００５２】
以上が、図７に示したＦＦＴ回路１００におけるパイプライン処理の内部処理である。
【００５３】
以下において、各処理期間において実行される処理について詳細に説明する。以下の説明においては、図１１のタイミング図を参照する。
【００５４】
（Ｔ１）
時間Ｔ１の処理期間において実行される処理について説明する。
【００５５】
ＦＦＴ回路１００（図７）は、ＦＦＴブロックＦ１を構成する入力データｘ（ｎ）を第１データ並べ替え処理回路１０１に入力する。第１データ並べ替え処理回路１０１は、このＦＦＴブロックＦ１に対する並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ１（Ｍ１Ｗ））。
【００５６】
（Ｔ２）
時間Ｔ２の処理期間において実行される処理について説明する。
【００５７】
ＦＦＴ回路１００は、ＦＦＴブロックＦ２を構成する入力データｘ（ｎ）を第１データ並べ替え処理回路１０１に入力する。第１データ並べ替え処理回路１０１は、このＦＦＴブロックＦ２に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ２（Ｍ１Ｗ））。
【００５８】
さらに、第１データ並べ替え処理回路１０１は、Ｔ１で処理されたＦＦＴブロックＦ１に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ１Ｒ））。このとき、第１データ並べ替え処理回路１０１は、並べ替え１（ｗｒｉｔｅ）の処理におけるデータの書き込み順序とは異なる順序で、並べ替え１（ｒｅａｄ）の処理におけるデータの読み出しを行う。すなわち、第１データ並べ替え処理回路１０１は、ＦＦＴ処理のアルゴリズム上のデータ依存に基づいたデータシーケンスの並べ替えを行うことになる。
【００５９】
さらに、第１バタフライ演算処理回路１０２は、並べ替え１（ｒｅａｄ）による並べ替え処理後のＦＦＴブロックＦ１に対して、バタフライ演算１の処理を行う（Ｆ１（Ｂ１））。
【００６０】
続けて、第２データ並べ替え処理回路１０３は、バタフライ演算１の処理後のＦＦＴブロックＦ１に対して並べ替え２（ｗｒｉｔｅ）の処理を行う（Ｆ１（Ｍ２Ｗ））。
【００６１】
（Ｔ３）
以降同様にして、時間Ｔ３の処理期間において実行される処理について説明する。
【００６２】
ＦＦＴ回路１００は、第１データ並べ替え処理回路１０１にＦＦＴブロックＦ３を構成する入力データｘ（ｎ）を入力する。第１データ並べ替え処理回路１０１は、このＦＦＴブロックＦ３に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ３（Ｍ１Ｗ））。
【００６３】
さらに、第１データ並べ替え処理回路１０１は、ＦＦＴブロックＦ２に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ１Ｒ））。第１バタフライ演算処理回路１０２は、並べ替え１（ｒｅａｄ）の処理後のＦＦＴブロックＦ２に対してバタフライ演算１の処理を行う（Ｆ２（Ｂ１））。第２データ並べ替え処理回路１０３は、バタフライ演算１の処理後のＦＦＴブロックＦ２に対して並べ替え２（ｗｒｉｔｅ）の処理を続けて行う（Ｆ２（Ｍ２Ｗ））。
【００６４】
さらに、第２データ並べ替え処理回路１０３は、ＦＦＴブロックＦ１に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ２Ｒ））。ひねり演算処理回路１０４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ１に対してひねり乗算の処理を続けて行う（Ｆ１（ＴＷ））。第２バタフライ演算処理回路１０５は、ひねり乗算の処理後のＦＦＴブロックＦ１に対してバタフライ演算２の処理を行う（Ｆ１（Ｂ２））。第３データ並べ替え処理回路１０６は、バタフライ演算２の処理後のデータに対して並べ替え３（ｗｒｉｔｅ）の処理を続けて行う（Ｆ１（Ｍ３Ｗ））。
【００６５】
（Ｔ４）
時間Ｔ４の処理期間において実行される処理について説明する。
【００６６】
第１データ並べ替え処理回路１０１は、ＦＦＴブロックＦ３に対して並べ替え１（ｒｅａｄ）の処理（Ｆ３（Ｍ１Ｒ））を行う。第１バタフライ演算処理回路１０２は、並べ替え１（ｒｅａｄ）の処理後のＦＦＴブロックＦ３に対してバタフライ演算１の処理を行う（Ｆ３（Ｂ１））。第２データ並べ替え処理回路１０３は、ＦＦＴブロックＦ３に対して並べ替え２（ｗｒｉｔｅ）の処理を続けて行う（Ｆ３（Ｍ２Ｗ））。
【００６７】
さらに、第２データ並べ替え処理回路１０３は、ＦＦＴブロックＦ２に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ２Ｒ））。ひねり演算処理回路１０４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ２に対してひねり乗算の処理を行う（Ｆ２（ＴＷ））。続けて、第２バタフライ演算処理回路１０５は、ひねり乗算の処理後のＦＦＴブロックＦ２に対してバタフライ演算２の処理を行う（Ｆ２（Ｂ２））。さらに、第３データ並べ替え処理回路１０６は、バタフライ演算２の処理後のＦＦＴブロックＦ２に対して並べ替え３（ｗｒｉｔｅ）の処理（Ｆ２（Ｍ３Ｗ））を続けて行う。
【００６８】
さらに、第３データ並べ替え処理回路１０６は、ＦＦＴブロックＦ１に対して並べ替え３（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ３Ｒ））。ＦＦＴブロックＦ１に対するＦＦＴ処理が完了すると、ＦＦＴ回路１００は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ１）として出力する。
【００６９】
（Ｔ５）
時間Ｔ５の処理期間において実行される処理について説明する。
【００７０】
第２データ並べ替え処理回路１０３は、ＦＦＴブロックＦ３に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ３（Ｍ２Ｒ））。ひねり乗算処理回路１０４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ３に対してひねり乗算の処理を行う（Ｆ３（ＴＷ））。第２バタフライ演算処理回路１０５は、ひねり乗算の処理後のＦＦＴブロックＦ３に対してバタフライ演算２の処理を行う（Ｆ３（Ｂ２））。第３データ並べ替え処理回路１０６は、バタフライ演算２の処理後のＦＦＴブロックＦ３に対して並べ替え３（ｗｒｉｔｅ）の処理（図１１のＦ３（Ｍ３Ｗ））を行う。
【００７１】
さらに、第３データ並べ替え処理回路１０６は、ＦＦＴブロックＦ２に対して並べ替え３（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ３Ｒ））。ここで、ＦＦＴブロックＦ２に対するＦＦＴ処理が完了すると、ＦＦＴ回路１００は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ２）として出力する。
【００７２】
（Ｔ６）
時間Ｔ６の処理期間において実行される処理について説明する。
【００７３】
第３データ並べ替え処理回路１０６は、ＦＦＴブロックＦ３に対して並べ替え３（ｒｅａｄ）の処理を行う（Ｆ３（Ｍ３Ｒ））。ここで、ＦＦＴブロックＦ３に対するＦＦＴ処理が完了すると、ＦＦＴ回路１００は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ３）として出力する。
【００７４】
以上、ＦＦＴブロックＦ１〜Ｆ３に対する処理についてのみ説明したが、ＦＦＴブロックＦ３より後のＦＦＴブロックについても同様である。
【００７５】
以上のような処理によって、ＦＦＴ回路１００は、複数のＦＦＴブロックをパイプライン状に処理することで、入力データを連続的に処理し、高い処理スループット性能を達成する。
【００７６】
（変調方式）
ここで、変調方式の例として、ＱＰＳＫ、１６ＱＡＭ、２５６ＱＡＭについて図１２を用いて説明する（ＱＰＳＫ：Ｑｕａｄｒａｔｕｒｅ  Ｐｈａｓｅ  Ｓｈｉｆｔ  Ｋｅｙｉｎｇ、１６ＱＡＭ：１６  Ｑｕａｄｒａｔｕｒｅ  Ａｍｐｌｉｔｕｄｅ  Ｍｏｄｕｌａｔｉｏｎ、２５６ＱＡＭ：２５６  Ｑｕａｄｒａｔｕｒｅ  Ａｍｐｌｉｔｕｄｅ  Ｍｏｄｕｌａｔｉｏｎ）。
【００７７】
ＱＰＳＫ方式は、１シンボルに４値を割り当てるため、１シンボル当たり２ビットの情報を伝送することができる。１６ＱＡＭ方式は、１シンボルに１６値を割り当てるため、１シンボル当たり４ビットの情報を伝送することができる。２５６ＱＡＭ方式は、１シンボルに２５６値を割り当てるため、１シンボル当り８ビットの情報を伝送することができる。
【００７８】
すなわち、ＱＰＳＫ方式に対して１６ＱＡＭ方式は、１シンボル当たり２倍の情報を伝送することができるため、１／２のシンボルレートで同じ伝送速度を実現することができる。同様に、１６ＱＡＭ方式に対して２５６ＱＡＭ方式は、１シンボル当たり２倍の情報を伝送することができるため、１／２のシンボルレートで同じ伝送速度を実現することができる。
【００７９】
フィルタ処理などのデジタル信号処理に要求される処理スループットは、シンボルレートに比例する。そのため、同じ伝送速度を実現する場合において、ＦＦＴ処理に要求される処理スループットは、ＱＰＳＫ方式を１とすると、１６ＱＡＭ方式は１／２、２５６ＱＡＭ方式は１／４となる。
【００８０】
一方、ＱＰＳＫ方式よりも１６ＱＡＭ方式の方が、１シンボルに対して多値を割り当てるため、ＱＰＳＫ方式におけるシンボル間の距離（Ｄ１）よりも、１６ＱＡＭ方式におけるシンボル間距離（Ｄ２）は小さくなる（Ｄ１＞Ｄ２）。同様に、１６ＱＡＭ方式におけるシンボル間距離（Ｄ２）よりも２５６ＱＡＭ方式におけるシンボル間距離（Ｄ３）は、より多値を割り当てる分だけ小さくなる（Ｄ２＞Ｄ３）。
【００８１】
フィルタ処理などのデジタル信号処理に要求される演算精度は、シンボル間距離が小さくなるほど、より高い精度の演算が必要となる。そのため、ＦＦＴ処理に要求される演算精度も、ＱＰＳＫ方式よりも１６ＱＡＭ方式がより高い演算精度が要求され、２５６ＱＡＭ方式はさらに高い演算精度が要求される。
【００８２】
デジタル信号処理回路の演算精度は、主に、データの表現形式及びデータのビット幅で決定される。
【００８３】
デジタル信号処理におけるデータの表現形式としては、浮動小数点形式や固定小数点方式、ブロック浮動小数点方式が、主に用いられている。
【００８４】
浮動小数点形式は、扱う信号データの値の範囲が広い場合でも高い精度で演算できるという利点があるが、複雑な回路が必要になるため、回路規模や消費電力が大きいという問題がある。
【００８５】
固定小数点形式は、回路が単純で、回路規模や消費電力が小さいという利点があるが、扱う信号データの値の範囲が広い場合に演算精度が低下するという問題がある。
【００８６】
一方、浮動小数点形式と固定小数点形式の双方の利点を兼ね備えた演算方法として、ブロック浮動小数点形式がある。ブロック浮動小数点形式による演算では、複数の信号データを１つのブロックとしてまとめ、各ブロック単位で共通の指数をもつように、ブロック全体で正規化する。
【００８７】
いずれの表現形式においても、演算精度を高くするにはデータのビット幅を大きくする必要がある。そのため、回路規模や消費電力を小さくするには、要求される演算精度に応じて、データのビット幅を必要十分な値に最適化する必要がある。
【００８８】
ここで、複数の変調方式に対して、ＦＦＴ回路の構成方法を最適化することによって、回路規模や消費電力を低減することを考える。例えば、ＱＰＳＫ方式及び１６ＱＡＭ方式に対応する場合、ＱＰＳＫ方式に対しては、１６ＱＡＭ方式よりも高い処理スループットと低い演算精度が要求される。一方、１６ＱＡＭ方式に対しては、ＱＰＳＫ方式よりも低い処理スループット・高い演算精度が要求される。すなわち、データビットの幅を大きくすると演算精度は高くなるものの、処理スループットが低くなる。
【００８９】
以上が変調方式についての説明である。
【００９０】
以下において、本発明の実施形態に係るＦＦＴ回路について図面を参照しながら説明する。
【００９１】
（実施形態）
（構成）
図１は、本発明の第１の実施形態に係るＦＦＴ回路１０の構成例を示すブロック図である。
【００９２】
図１のＦＦＴ回路１０は、パイプライン回路方式によるＦＦＴ回路であり、時間領域のデータｘ（ｎ）を入力し、ＦＦＴ処理によりフーリエ変換した周波数領域の信号Ｘ（ｋ）を生成して出力する。ここで、ＮはＦＦＴブロックサイズをあらわす正整数である（ｎ＝０、１、・・・、Ｎ−１、ｋ＝０、１、・・・、Ｎ−１）。
【００９３】
ＦＦＴ回路１０は、第１データ並べ替え処理回路１１と、第１バタフライ演算処理回路１２と、第２データ並べ替え処理回路１３と、ひねり乗算処理回路１４と、第２バタフライ演算処理回路１５と、第３データ並べ替え処理回路１６とを備えている。さらに、ＦＦＴ回路１０は、第１データ選択回路２１と、第２データ選択回路２２とを備えている。なお、図７と同じ名称の構成要素は、それらの構成要素と同様の処理を行う。
【００９４】
第１データ並べ替え処理回路１１、第２データ並べ替え処理回路１３及び第３データ並べ替え処理回路１６は、データ並べ替えのためのバッファ回路である。第１データ並べ替え処理回路１１、第２データ並べ替え処理回路１３及び第３データ並べ替え処理回路１６は、バタフライ演算処理回路の前後で、ＦＦＴ処理のアルゴリズム上のデータ依存に基づいたデータシーケンスの並べ替えを行う。
【００９５】
第１バタフライ演算処理回路１２及び第２バタフライ演算処理回路１５は、ＦＦＴ処理を構成するバタフライ演算処理を行う。
【００９６】
ひねり乗算処理回路１４は、第１のバタフライ演算処理後にＦＦＴ演算における複素平面上の複素回転を処理する。
【００９７】
第１データ選択回路２１及び第２データ選択回路２２は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などの上位回路（図示せず）から与えられる動作設定信号３１を参照して、データの選択処理を行う。なお、第１及び第２データ選択回路２１，２２は、後述する動作モード１及び２を含む複数の動作モードのいずれかに対応して第１及び第２バタフライ演算処理回路１２，１５を選択制御する制御手段に含まれる。
【００９８】
具体的には、第１データ選択回路２１は、動作設定信号３１を参照して、入力する第１データ信号３２または第４データ信号３５のいずれか１つを選択して、第２データ並べ替え処理回路１３に出力する。
【００９９】
また、第２データ選択回路２２は、動作設定信号３１を参照して、入力する第２データ信号３３または第３データ信号３４のいずれか１つを選択して、第２バタフライ演算処理回路１５に出力する。
【０１００】
動作設定信号３１は、ＦＦＴ回路１０の動作モードを設定する信号である。動作設定信号３１は、具体的には、低演算精度・高処理スループットで動作するモードである動作モード１、または、高演算精度・低処理スループットで動作するモードである動作モード２、のいずれか１つの動作モードを設定する信号である。
【０１０１】
ＣＰＵなどの上位回路（図示せず）は、例えば、変調方式に応じて動作設定信号３１の値を設定する。
【０１０２】
具体的には、ＱＰＳＫ方式などのように低い演算精度・高い処理スループットのＦＦＴ処理が必要な場合、上位回路は動作モード１を指示する値を動作設定信号３１に設定する。
【０１０３】
また、１６ＱＡＭ方式などのように高い演算精度・低い処理スループットのＦＦＴ処理が必要な場合、上位回路は動作モード２を指示する値を動作設定信号３１に設定する。
【０１０４】
第１バタフライ演算処理回路１２の演算ビット幅は、動作モード１において要求される低い演算精度を実現するのに必要十分なビット幅であるＳビット幅の回路で実現されている。第１バタフライ演算処理回路１２では、Ｓビット幅に対応した第１のバタフライ演算が実行される。なお、Ｓビット幅におけるＳは、１以上の整数である。
【０１０５】
一方、第２バタフライ演算処理回路１５の演算ビット幅は、動作モード２において要求される高い演算精度を実現するのに必要十分なビット幅であるＬビット幅の回路で実現されている。第２バタフライ演算処理回路１５では、Ｌビット幅に対応した第２のバタフライ演算が実行される。なお、Ｌビット幅におけるＬは、１以上の整数である。また、ＳとＬは異なる整数であり、Ｌの方がＳよりも大きいものとする。
【０１０６】
第２バタフライ演算処理回路１５のビット幅Ｌよりも第１バタフライ演算処理回路１２のビット幅Ｓの方が小さい。そのため、第２バタフライ演算処理回路１５よりも第１バタフライ演算処理回路１２の方が、回路規模や消費電力を小さくすることができる。
【０１０７】
図７に示したようなＦＦＴ回路１００は常に同一のビット幅の回路で動作する。図７のようなＦＦＴ回路１００をビット幅Ｌのみの回路構成とした場合、常に高い演算精度で計算を実行するため、ＱＰＳＫ方式などの低い演算精度で十分な場合には余分な消費電力が生じる。また、例えば、図７のようなＦＦＴ回路１００をビット幅Ｓのみの回路構成とした場合、１６ＱＡＭ方式などに要求される高い演算精度を実現することができない。
【０１０８】
それに対し、本発明の実施形態のＦＦＴ回路１０では、高い演算精度が要求されない場合、ビット幅の小さなビット幅Ｓとビット幅Ｌの回路の両方を使用することによって消費電力を低下させることができる。また、高い演算精度が要求される場合は、一つのビット幅Ｌの回路を効率的に使用することによって高い演算精度を実現できる。
【０１０９】
（動作）
以下、図１に示すＦＦＴ回路１０の動作について、図２〜５を参照して説明する。
【０１１０】
（動作モード１）
図２は、動作モード１における図１に示すＦＦＴ回路１０の動作状態を示すブロック図である。
【０１１１】
図２において、動作設定信号３１は、動作モード１を指示する値に設定されており、ＦＦＴ回路１０は動作モード１で動作する。図２では、ＦＦＴ回路１０を構成する各回路・データ信号のうち、動作モード１において、実際に使用する回路・データ信号は実線で示し、使用しない回路・データ信号は点線で示している。
【０１１２】
動作モード１において、第１データ選択回路２１は、入力する第１データ信号３２を常に選択して、第２データ並べ替え処理回路１３に出力する。したがって、もう一方の入力である第４データ信号３５は使用されない。
【０１１３】
また、動作モード１において、第２データ選択回路２２は、入力する第２データ信号３３を常に選択して、第２バタフライ演算処理回路１５に出力する。したがって、もう一方の入力である第３データ信号３４は使用されない。
【０１１４】
次に、図３を参照して、動作モード１におけるＦＦＴ回路１０の動作例を説明する。
【０１１５】
図３は、動作モード１におけるＦＦＴ回路１０の動作を示すタイミング図である。図１１と同様に、図３では、ＦＦＴ処理の処理単位であるＦＦＴブロックの例として、ＦＦＴブロックＦ１、ＦＦＴブロックＦ２及びＦＦＴブロックＦ３に対する、時間Ｔ１〜Ｔ６における処理を図示している。このＦ１〜Ｆ３のＦＦＴブロックは、入力する時間領域の信号ｘ（ｎ）をＦＦＴブロックの大きさごとに分割したデータブロックに相当する。
【０１１６】
図３では、ＦＦＴ処理を１〜９の内部処理に分割して図示している。以下において、動作モード１における内部処理１〜９を説明する。
【０１１７】
（１）並べ替え１（ｗｒｉｔｅ）の処理は、第１データ並べ替え処理回路１１に対するデータの書き込み処理である。
【０１１８】
（２）並べ替え１（ｒｅａｄ）の処理は、第１データ並べ替え処理回路１１によって並べ替えられたデータの読み出し処理である。
【０１１９】
（３）バタフライ演算１の処理は、第１バタフライ演算処理回路１２による第１のバタフライ演算処理である。
【０１２０】
（４）並べ替え２（ｗｒｉｔｅ）の処理は、第２データ並べ替え処理回路１３に対するデータの書き込み処理である。
【０１２１】
（５）並べ替え２（ｒｅａｄ）の処理は、第２データ並べ替え処理回路１３によって並べ替えられたデータの読み出し処理である。
【０１２２】
（６）ひねり乗算の処理は、ひねり乗算処理回路１４によるひねり乗算処理である。
【０１２３】
（７）バタフライ演算２の処理は、第２バタフライ演算処理回路１５による第２のバタフライ演算処理である。
【０１２４】
（８）並べ替え３（ｗｒｉｔｅ）の処理は、第３データ並べ替え処理回路１６に対するデータの書き込み処理である。
【０１２５】
（９）並べ替え３（ｒｅａｄ）の処理は、第３データ並べ替え処理回路１６によって並べ替えられたデータの読み出し処理である。
【０１２６】
以上が動作モード１における内部処理１〜９の説明である。
【０１２７】
以下において、図３の各処理期間において実行する処理について説明する。
【０１２８】
（Ｔ１）
時間Ｔ１の処理期間において実行される処理について説明する。
【０１２９】
ＦＦＴ回路１０は、ＦＦＴブロックＦ１を構成する入力データｘ（ｎ）を第１データ並べ替え処理回路１１に入力する。第１データ並べ替え処理回路１１は、このＦＦＴブロックＦ１に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ１（Ｍ１Ｗ））。
【０１３０】
（Ｔ２）
時間Ｔ２の処理期間において実行される処理について説明する。
【０１３１】
ＦＦＴ回路１０は、ＦＦＴブロックＦ２を構成する入力データｘ（ｎ）を第１データ並べ替え処理回路１１に入力する。第１データ並べ替え処理回路１１は、この入力データに対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ２（Ｍ１Ｗ））。
【０１３２】
さらに、第１データ並べ替え処理回路１１は、ＦＦＴブロックＦ１に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ１Ｒ））。このとき、並べ替え１（ｗｒｉｔｅ）の処理におけるデータの書き込み順序とは異なる順序で、並べ替え１（ｒｅａｄ）の処理におけるデータの読み出しを行うことで、ＦＦＴ処理のアルゴリズム上のデータ依存に基づいたデータシーケンスの並べ替えを行う。第１バタフライ演算処理回路１２は、並べ替え１（ｒｅａｄ）による並べ替え処理後のＦＦＴブロックＦ１に対してバタフライ演算１の処理を行う（Ｆ１（Ｂ１））。第２データ並べ替え処理回路１３は、バタフライ演算１の処理後のＦＦＴブロックＦ１に対して並べ替え２（ｗｒｉｔｅ）の処理（Ｆ１（Ｍ２Ｗ））を続けて行う。
【０１３３】
（Ｔ３）
時間Ｔ３の処理期間において実行される処理について説明する。
【０１３４】
ＦＦＴ回路１０は、ＦＦＴブロックＦ３を構成する入力データｘ（ｎ）を第１データ並べ替え処理回路１１に入力する。第１データ並べ替え処理回路１１は、このＦＦＴブロックＦ３に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ３（Ｍ１Ｗ））。
【０１３５】
さらに、第１データ並べ替え処理回路１１は、処理期間Ｔ２において処理されたＦＦＴブロックＦ２に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ１Ｒ））。第１バタフライ演算処理回路１２は、並べ替え１（ｒｅａｄ）の処理後のＦＦＴブロックＦ２に対してバタフライ演算１の処理を行う（Ｆ２（Ｂ１））。第２データ並べ替え処理回路１３は、バタフライ演算１の処理後のＦＦＴブロックＦ２に対して並べ替え２（ｗｒｉｔｅ）の処理を行う（Ｆ２（Ｍ２Ｗ））。
【０１３６】
さらに、第２データ並べ替え処理回路１３は、処理期間Ｔ２において処理されたＦＦＴブロックＦ１に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ２Ｒ）。ひねり乗算処理回路１４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ１に対してひねり乗算の処理を行う（Ｆ１（ＴＷ））。第２バタフライ演算処理回路１５は、ひねり乗算の処理後のＦＦＴブロックＦ１に対してバタフライ演算２の処理を行う（Ｆ１（Ｂ２））。第３データ並べ替え処理回路１６は、バタフライ演算２の処理後のＦＦＴブロックＦ１に対して並べ替え３（ｗｒｉｔｅ）の処理（Ｆ１（Ｍ３Ｗ））を行う。
【０１３７】
（Ｔ４）
時間Ｔ４の処理期間において実行される処理について説明する。
【０１３８】
第１データ並べ替え処理回路１１は、処理期間Ｔ３において処理されたＦＦＴブロックＦ３に対して並べ替え１（ｒｅａｄ）の処理（Ｆ３（Ｍ１Ｒ））を行う。第１バタフライ演算処理回路１２は、並べ替え１（ｒｅａｄ）の処理後のＦＦＴブロックＦ３に対してバタフライ演算１の処理を行う（Ｆ３（Ｂ１））。第２データ並べ替え処理回路１３は、バタフライ演算１の処理後のＦＦＴブロックＦ３に対して並べ替え２（ｗｒｉｔｅ）の処理を行う（Ｆ３（Ｍ２Ｗ））。
【０１３９】
さらに、第２データ並べ替え処理回路１３は、処理期間Ｔ３において処理されたＦＦＴブロックＦ２に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ２Ｒ））。ひねり乗算処理回路１４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ２に対してひねり乗算の処理を行う（Ｆ２（ＴＷ））。第２バタフライ演算処理回路１５は、ひねり乗算の処理後のＦＦＴブロックＦ２に対してバタフライ演算２の処理を行う（Ｆ２（Ｂ２））。第３データ並べ替え処理回路１６は、バタフライ演算２の処理後のＦＦＴブロックＦ２に対して並べ替え３（ｗｒｉｔｅ）の処理（Ｆ２（Ｍ３Ｗ））を行う。
【０１４０】
さらに、第３データ並べ替え処理回路１６は、処理期間Ｔ３において処理されたＦＦＴブロックＦ１に対して並べ替え３（ｒｅａｄ）の処理（Ｆ１（Ｍ３Ｒ））を行う。ここで、ＦＦＴブロックＦ１に対するＦＦＴ処理が完了すると、ＦＦＴ回路１０は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ１）として出力する。
【０１４１】
（Ｔ５）
時間Ｔ５の処理期間において実行される処理について説明する。
【０１４２】
ＦＦＴ回路１０は、処理期間Ｔ４において処理されたＦＦＴブロックＦ３に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ３（Ｍ２Ｒ））。ひねり乗算処理回路１４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ３に対してひねり乗算の処理を行う（Ｆ３（ＴＷ））。第２バタフライ演算処理回路１５は、ひねり乗算の処理後のＦＦＴブロックＦ３に対してバタフライ演算２の処理を行う（Ｆ３（Ｂ２））。第３データ並べ替え処理回路１６は、バタフライ演算２の処理後のＦＦＴブロックＦ２に対して並べ替え３（ｗｒｉｔｅ）の処理（Ｆ３（Ｍ３Ｗ））を続けて行う。
【０１４３】
さらに、第３データ並べ替え処理回路１６は、処理期間Ｔ４において処理されたＦＦＴブロックＦ２に対して並べ替え３（ｒｅａｄ）の処理（Ｆ２（Ｍ３Ｒ））を行う。ここで、ＦＦＴブロックＦ２に対するＦＦＴ処理が完了すると、ＦＦＴ回路１０は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ２）として出力する。
【０１４４】
（Ｔ６）
時間Ｔ６の処理期間において実行される処理について説明する。
【０１４５】
第３データ並べ替え処理回路１６は、処理期間Ｔ３において処理されたＦＦＴブロックＦ３に対して並べ替え３（ｒｅａｄ）の処理を行う（Ｆ３（Ｍ３Ｒ））。ここで、ＦＦＴブロックＦ３に対するＦＦＴ処理が完了すると、ＦＦＴ処理回路１０は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ３）として出力する。
【０１４６】
以上、ＦＦＴブロックＦ１〜Ｆ３に対する処理について説明した。なお、ＦＦＴブロックＦ３より後のＦＦＴブロックについても同様である。
【０１４７】
また、動作モードは必ずしも２つに限定されず、３つ以上のバタフライ演算処理回路を備えた構成とし、それぞれのバタフライ演算処理回路に対応した演算ビット幅のバタフライ演算を行うようにしてもよい。その場合、複数のバタフライ演算に対応させた動作モードを選択することが好ましい。
【０１４８】
以上説明したように、ＦＦＴ回路１０は、動作モード１においては、第１バタフライ演算処理回路１２及び第２バタフライ演算処理回路１５の両方を使用して、バタフライ演算をパイプライン状に処理する。その結果、動作モード１において要求される高いスループット性能を実現することができる。
【０１４９】
また、第１バタフライ演算処理回路１２は、動作モード１において要求される演算精度に必要十分な演算ビット幅（Ｓビット）の回路で実現されている。さらに、第２バタフライ演算処理回路１５は、より広い演算ビット幅（Ｌビット）の回路で実現されている。その結果、動作モード１において要求される演算精度を実現することができる。
【０１５０】
（動作モード２）
次に、動作モード２におけるＦＦＴ回路１０の動作を説明する。図４は、動作モード２におけるＦＦＴ回路１０の動作状態を示すブロック図である。図４において、動作設定信号３１は、動作モード２を指示する値に設定されており、ＦＦＴ回路１０は動作モード２で動作する。図４では、ＦＦＴ回路１０を構成する各回路・データ信号のうち、動作モード２において、実際に使用する回路・データ信号は実線で示し、使用しない回路・データ信号は点線で示している。
【０１５１】
動作モード２において、第１データ選択回路２１は、入力された第４データ信号３５を常に選択して、第２データ並べ替え処理回路１３に出力する。したがって、もう一方の入力信号である第１データ信号３２は使用されない。
【０１５２】
第２データ選択回路２２は、入力された第２データ信号３３及び第３データ信号３４のいずれかを、第２バタフライ演算処理回路１５の処理内容に応じて適宜選択して、第２バタフライ演算処理回路１５に出力する。
【０１５３】
次に、図５を参照して、動作モード２におけるＦＦＴ回路１０の動作例を説明する。図５は、動作モード２におけるＦＦＴ回路１０の動作を示すタイミング図である。図５では、ＦＦＴ処理の処理単位であるＦＦＴブロックの例として、ＦＦＴブロックＦ１、ＦＦＴブロックＦ２及びＦＦＴブロックＦ３に対する時間Ｔ１’〜Ｔ５’における処理を図示している。このＦ１〜Ｆ３のＦＦＴブロックは、入力する時間領域の信号ｘ（ｎ）をＦＦＴブロックの大きさごとに分割したデータブロックに相当する。
【０１５４】
ここで、動作モード２では、データｘ（ｎ）の入力速度である入力スループットは、動作モード１における入力スループットの１／２であるとする。
【０１５５】
例えば、動作モード１が対応するＱＰＳＫ方式のシンボルレートに対して、動作モード２が対応する１６ＱＡＭ方式のシンボルレートは１／２でよい。そのため、入力スループットも１／２になることになる。したがって、動作モード２におけるＦＦＴ回路１０の処理スループットは、動作モード１におけるＦＦＴ回路１０の処理スループットの１／２になる。そのため、図５に示す動作モード２における時間Ｔ１’〜Ｔ５’のそれぞれの長さは、図３に示す動作モード１における時間Ｔ１〜Ｔ５それぞれの長さの２倍となっている。
【０１５６】
（動作モード２の内部処理）
図５において、ＦＦＴ処理を１〜９の内部処理に分割して図示している。以下において、動作モード２における内部処理１〜９を説明する。
【０１５７】
（１）並べ替え１（ｗｒｉｔｅ）の処理は、第１データ並べ替え処理回路１１に対するデータの書き込み処理である。
【０１５８】
（２）並べ替え１（ｒｅａｄ）の処理は、第１データ並べ替え処理回路１１によって並べ替えられたデータの読み出し処理である。
【０１５９】
（３）バタフライ演算１の処理は、第２バタフライ演算処理回路１５による第１のバタフライ演算処理である。
【０１６０】
（４）並べ替え２（ｗｒｉｔｅ）の処理は、第２データ並べ替え処理回路１３に対するデータの書き込み処理である。
【０１６１】
（５）並べ替え２（ｒｅａｄ）の処理は、第２データ並べ替え処理回路１３によって並べ替えられたデータの読み出し処理である。
【０１６２】
（６）ひねり乗算の処理は、ひねり乗算処理回路１４によるひねり乗算処理である。
【０１６３】
（７）バタフライ演算２の処理は、第２バタフライ演算処理回路１５による第２のバタフライ演算処理である。
【０１６４】
（８）並べ替え３（ｗｒｉｔｅ）の処理は、第３データ並べ替え処理回路１６に対するデータの書き込み処理である。
【０１６５】
（９）並べ替え３（ｒｅａｄ）の処理は、第３データ並べ替え処理回路１６によって並べ替えられたデータの読み出し処理である。
【０１６６】
以上が動作モード２における内部処理の説明である。
【０１６７】
すなわち、動作モード２の処理においては、第１バタフライ演算処理回路１２は使用されない。その一方で、第２バタフライ演算処理回路１５のみを２回使用して、バタフライ演算１及びバタフライ演算２の両方を処理する。
【０１６８】
以下において、図５の各処理期間において動作モード２で実行する処理について説明する。
【０１６９】
（Ｔ１’）
時間Ｔ１’の処理期間において実行される処理について説明する。
【０１７０】
ＦＦＴ回路１０は、第１データ並べ替え処理回路１１にＦＦＴブロックＦ１を構成する入力データｘ（ｎ）を入力する。第１データ並べ替え処理回路１１は、このＦＦＴブロックＦ１に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ１（Ｍ１Ｗ））。
【０１７１】
（Ｔ２’）
時間Ｔ２’の処理期間において実行される処理について説明する。
【０１７２】
ＦＦＴ回路１０は、ＦＦＴブロックＦ２を構成する入力データｘ（ｎ）を第１データ並べ替え処理回路１１に入力する。第１データ並べ替え処理回路１１は、このＦＦＴブロックＦ２に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ２（Ｍ１Ｗ））。
【０１７３】
さらに、第１データ並べ替え処理回路１１は、時間Ｔ１’の処理期間において処理されたＦＦＴブロックＦ１に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ１Ｒ））。並べ替え１（ｒｅａｄ）の処理は、動作モード１と同じ速度で処理されるため、時間Ｔ２’の１／２の処理時間、すなわち、動作モード１における時間Ｔ２と同じ処理時間に相当する「時間Ｔ２’の処理期間の前半」で完了する。
【０１７４】
データ並べ替え処理回路１１が出力した処理後のデータは、第３データ信号３４を通じて選択回路２２に入力される。選択回路２２は、入力された第３データ信号３４を選択して、第２バタフライ演算処理回路１５に出力する。
【０１７５】
第２バタフライ演算処理回路１５は、入力されたデータに対してバタフライ演算１の処理（Ｆ１（Ｂ２））を行う。続けて、第２データ並べ替え処理回路１３は、バタフライ演算１の処理後のＦＦＴブロックＦ１に対して並べ替え２（ｗｒｉｔｅ）の処理を行う（Ｆ１（Ｍ２Ｗ））。
【０１７６】
これらの処理（Ｆ１（Ｍ１Ｒ）、Ｆ１（Ｂ２）、Ｆ１（Ｍ２Ｗ））は、動作モード１と同じ速度で処理されるため、時間Ｔ２’の１／２の処理時間、すなわち、動作モード１における時間Ｔ２と同じ処理時間である「時間Ｔ２’の処理期間の前半」で完了する。
【０１７７】
次に、時間Ｔ２’の処理期間の後半において、第２データ並べ替え処理回路１３は、時間Ｔ２’の処理期間の前半において処理されたＦＦＴブロックＦ１に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ１（Ｍ２Ｒ））。ひねり乗算処理回路１４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ１に対してひねり乗算の処理を行う（Ｆ１（ＴＷ））。
【０１７８】
選択回路２２は、入力された第２データ信号３３を選択して、第２バタフライ演算処理回路１５に出力する。
【０１７９】
第２バタフライ演算処理回路１５は、入力されたＦＦＴブロックＦ１に対してバタフライ演算２の処理を行う（Ｆ１（Ｂ２））。続けて、第３データ並べ替え処理回路１６は、バタフライ演算２の処理後のＦＦＴブロックＦ２に対して並べ替え３（ｗｒｉｔｅ）の処理を行う（Ｆ１（Ｍ３Ｗ））。
【０１８０】
これらの処理（Ｆ１（Ｍ２Ｒ）・Ｆ１（ＴＷ）・Ｆ１（Ｂ２）・Ｆ１（Ｍ３Ｗ））も、動作モード１と同じの速度で処理されるため、時間Ｔ２’の１／２の処理時間、すなわち、動作モード１における時間Ｔ２と同じ処理時間に相当する「時間Ｔ２’の処理期間の後半」で全て完了する。
【０１８１】
（Ｔ３’）
時間Ｔ３’の処理期間において実行される処理について説明する。
【０１８２】
ＦＦＴ回路１０は、第１データ並べ替え処理回路１１にＦＦＴブロックＦ３を構成する入力データｘ（ｎ）を入力する。第１データ並べ替え処理回路１１は、このＦＦＴブロックＦ３に対して並べ替え１（ｗｒｉｔｅ）の処理を行う（Ｆ３（Ｍ１Ｗ））。
【０１８３】
さらに、第３データ並べ替え処理回路１６は、時間Ｔ２’の処理期間において処理されたＦＦＴブロックＦ１に対して並べ替え３（ｒｅａｄ）の処理（Ｆ１（Ｍ３Ｒ））を行う。ここで、ＦＦＴブロックＦ１に対するＦＦＴ処理が完了すると、第３データ並べ替え処理回路１６は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ１）として出力する。
【０１８４】
また、時間Ｔ３’の処理期間の前半において、第１データ並べ替え処理回路１１は、時間Ｔ２’の処理期間において処理されたＦＦＴブロックＦ２に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ１Ｒ））。
【０１８５】
第１データ並べ替え処理回路１１が出力した処理後のデータは、第３データ信号３４を通じて選択回路２２に入力される。選択回路２２は、入力された第３データ信号３４を選択して、第２バタフライ演算処理回路１５に出力する。
【０１８６】
第２バタフライ演算処理回路１５は、入力されたデータに対してバタフライ演算１の処理（Ｆ２（Ｂ２））を行う。続けて、第２データ並べ替え処理回路１３は、バタフライ演算１の処理後のＦＦＴブロックＦ２に対して並べ替え２（ｗｒｉｔｅ）の処理を行う（Ｆ２（Ｍ２Ｗ））。
【０１８７】
以上のように、時間Ｔ３’の処理期間の前半において、ＦＦＴブロックＦ２に対してＦ２（Ｍ１Ｒ）・Ｆ２（Ｂ２）・Ｆ２（Ｍ２Ｗ）の処理が実行される。
【０１８８】
次に、時間Ｔ３’の処理期間の後半において、第２データ並べ替え処理回路１３は、時間Ｔ３’の処理期間の前半において処理されたＦＦＴブロックＦ２に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ２Ｒ））。ひねり乗算処理回路１４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ２に対してひねり乗算の処理を行う（Ｆ２（ＴＷ））。
【０１８９】
ひねり乗算処理回路１４が出力したひねり乗算の処理後のＦＦＴブロックＦ２は、第２データ信号３３を通じて選択回路２２に入力される。選択回路２２は、入力された第２データ信号３３を選択して、第２バタフライ演算処理回路１５に出力する。
【０１９０】
第２バタフライ演算処理回路１５は、入力されたデータに対してバタフライ演算２の処理を行う（Ｆ２（Ｂ２））。続けて、第３データ並べ替え処理回路１６は、バタフライ演算２の処理後のＦＦＴブロックＦ２に対して並べ替え３（ｗｒｉｔｅ）の処理（Ｆ２（Ｍ３Ｗ））を行う。
【０１９１】
以上のように、時間Ｔ３’の処理期間の後半において、ＦＦＴブロックＦ２に対してＦ２（Ｍ２Ｒ）・Ｆ２（ＴＷ）・Ｆ２（Ｂ２）・Ｆ２（Ｍ３Ｗ）の処理が実行される。
【０１９２】
（Ｔ４’）
時間Ｔ４’の処理期間において実行される処理について説明する。
【０１９３】
第３データ並べ替え処理回路１６は、時間Ｔ３’の処理期間において処理されたＦＦＴブロックＦ２に対して並べ替え３（ｒｅａｄ）の処理を行う（Ｆ２（Ｍ３Ｒ））。ここで、ＦＦＴブロックＦ２に対するＦＦＴ処理が完了すると、第３データ並べ替え処理回路１６は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ２）として出力する。
【０１９４】
また、時間Ｔ４’の処理期間の前半において、第１データ並べ替え処理回路１１は、時間Ｔ３’の処理時間において処理されたＦＦＴブロックＦ３に対して並べ替え１（ｒｅａｄ）の処理を行う（Ｆ３（Ｍ１Ｒ））。
【０１９５】
第１データ並べ替え処理回路１１が出力した処理後のデータは、第３データ信号３４を通じて選択回路２２に入力される。選択回路２２は、入力された第３データ信号３４を選択して、第２バタフライ演算処理回路１５に出力する。
【０１９６】
第２バタフライ演算処理回路１５は、入力されたデータに対してバタフライ演算１の処理を行う（Ｆ３（Ｂ２））。続けて、第２データ並べ替え処理回路１３は、バタフライ演算１の処理後のＦＦＴブロックＦ３に対して並べ替え２（ｗｒｉｔｅ）の処理を行う（Ｆ３（Ｍ２Ｗ））。
【０１９７】
以上のように、時間Ｔ４’の処理期間の前半において、ＦＦＴブロックＦ３に対してＦ３（Ｍ１Ｒ）・Ｆ３（Ｂ２）・Ｆ３（Ｍ２Ｗ）の処理が実行される。
【０１９８】
次に、時間Ｔ４’の処理期間の後半において、第２データ並べ替え処理回路１３は、時間Ｔ４’の処理期間の前半において処理されたＦＦＴブロックＦ３に対して並べ替え２（ｒｅａｄ）の処理を行う（Ｆ３（Ｍ２Ｒ））。ひねり乗算処理回路１４は、並べ替え２（ｒｅａｄ）の処理後のＦＦＴブロックＦ３に対してひねり乗算の処理（Ｆ３（ＴＷ））を行う。
【０１９９】
ひねり乗算処理回路１４が出力したひねり乗算の処理後のＦＦＴブロックＦ３は、第２データ信号３３を通じて選択回路２２に入力される。選択回路２２は、入力された第２データ信号３３を選択して、第２バタフライ演算処理回路１５に出力する。
【０２００】
第２バタフライ演算処理回路１５は、入力されたデータに対してバタフライ演算２の処理を行う（Ｆ３（Ｂ２））。続けて、第３データ並べ替え処理回路１６は、バタフライ演算２の処理後のＦＦＴブロックＦ３に対して並べ替え３（ｗｒｉｔｅ）の処理を行う（Ｆ３（Ｍ３Ｗ））。
【０２０１】
以上のように、時間Ｔ４’の処理期間の後半においては、ＦＦＴブロックＦ３に対してＦ３（Ｍ２Ｒ）・Ｆ３（ＴＷ）・Ｆ３（Ｂ２）・Ｆ３（Ｍ３Ｗ）の処理が実行される。
【０２０２】
（Ｔ５’）
時間Ｔ５’の処理期間において実行される処理について説明する。
【０２０３】
第３データ並べ替え処理回路１６は、ＦＦＴブロックＦ３に対して並べ替え３（ｒｅａｄ）の処理（Ｆ３（Ｍ３Ｒ））を実行する。ここで、ＦＦＴブロックＦ３に対するＦＦＴ処理が完了すると、ＦＦＴ回路１０は、そのデータを周波数領域のデータＸ（ｋ）（Ｆ３）として出力する。
【０２０４】
以上、ＦＦＴブロックＦ１〜Ｆ３に対する処理についてのみ説明したが、ＦＦＴブロックＦ３より後のＦＦＴブロックについても同様である。
【０２０５】
以上説明したように、ＦＦＴ回路１０は、バタフライ演算処理において第２バタフライ演算処理回路１５のみを使用し、バタフライ演算１及び２の処理を行うことができる。
【０２０６】
動作モード２において要求される処理スループットは、動作モード１において要求される処理スループットの１／２である。動作モード２においては、演算ビット幅の大きい第２バタフライ演算処理回路１５のみを使用し、演算ビット幅の小さい第１バタフライ演算処理回路１２を使用しないので、要求される高い演算精度でＦＦＴ処理を行うことができる。
【０２０７】
なお、本実施形態では、第１バタフライ演算処理回路１２の演算ビット幅は小さく、第２バタフライ演算処理回路１５の演算ビット幅は大きいものとし、動作モード２では、演算ビット幅が大きい第２バタフライ演算処理回路１５のみを使用するとした。それとは反対に、第１バタフライ演算処理回路１２の演算ビット幅を大きく、第２バタフライ演算処理回路１５の演算ビット幅を小さいものとし、動作モード２では、演算ビット幅が大きい第１バタフライ演算処理回路１２のみを使用するとしてもよい。
【０２０８】
本実施形態によれば、ＦＦＴ回路１０は、要求される処理スループット及び演算精度に応じて、動作モードを切り替えることができる。図６に示すように、ＱＰＳＫ方式のような低演算精度・高処理スループットが要求される場合には動作モード１で対応し、１６ＱＡＭ方式のような高演算精度・低処理スループットが要求される場合には動作モード２で対応する、というように動作モードを変更する。
【０２０９】
一方、図７のＦＦＴ回路１００においては、動作モードが固定である。したがって、高い演算精度を要求される場合に備えて、ＦＦＴ回路１００を構成する２つのバタフライ演算処理回路の両方とも、高い演算精度を実現するのに必要な大きな演算ビット幅に合わせる必要がある。
【０２１０】
それに対して、本実施形態に係るＦＦＴ回路１０は、動作モードに応じて回路構成を変更し、２つのバタフライ演算処理回路のうち、処理に使用するバタフライ演算処理回路を選択制御する。したがって、少なくとも一方のバタフライ演算処理回路の演算ビット幅を、低い演算精度の要求に合わせて小さくすることができる。その結果、回路規模や消費電力を削減することができる。
【０２１１】
なお、本発明の実施形態に係るＦＦＴ処理方法及びそのＦＦＴ処理方法に関するプログラムについても本発明の範囲に含まれる。また、本発明の実施形態に係るＦＦＴ回路を含む半導体装置、コンピュータ、通信装置などといった装置、さらにはこれらの装置を含むシステムについても、本発明に係るＦＦＴ処理回路・処理方法・プログラムが含まれているならば本発明の範囲に含まれる。本発明の実施形態に係るＦＦＴ処理は、より具体的には、有線及び無線における伝送路の通信波形歪みに対するデジタル信号処理による歪み補償処理などに好適である。
【０２１２】
以上、実施形態及び実施例を参照して本願発明を説明してきたが、本願発明は上記実施形態及び実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０２１３】
この出願は、２０１２年１１月２６日に出願された日本出願特願２０１２−２５７７２８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２１４】
１０    ＦＦＴ回路
１１    第１データ並べ替え処理回路
１２    第１バタフライ演算処理回路
１３    第２データ並べ替え処理回路
１４    ひねり乗算処理回路
１５    第２バタフライ演算処理回路
１６    第３データ並べ替え処理回路
２１    第１データ選択回路
２２    第２データ選択回路
３１    動作設定信号
３２    第１データ信号
３３    第２データ信号
３４    第３データ信号
３５    第４データ信号
８０    逐次順序テーブル
９０    ビットリバース順序テーブル
１００    ＦＦＴ回路
１０１    第１データ並べ替え処理回路
１０２    第１バタフライ演算処理回路
１０３    第２データ並べ替え処理回路
１０４    ひねり乗算処理回路
１０５    第２バタフライ演算処理回路
１０６    第３データ並べ替え処理回路
１１０ａ−１１０ｈ    部分データフロー
１１１    データ並べ替え処理
１１２    基数８のバタフライ処理
１１３    ひねり乗算処理
【図１】
2014080617.tif 000003
【図２】
2014080617.tif 000004
【図３】
2014080617.tif 000005
【図４】
2014080617.tif 000006
【図５】
2014080617.tif 000007
【図６】
2014080617.tif 000008
【図７】
2014080617.tif 000009
【図８】
2014080617.tif 000010
【図９】
2014080617.tif 000011
【図１０】
2014080617.tif 000012
【図１１】
2014080617.tif 000013
【図１２】
2014080617.tif 000014
【図１３】
2014080617.tif 000015
【手続補正書】
【提出日】平成27年5月21日(2015.5.21)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
互いに異なる演算ビット幅で動作してバタフライ演算を行う第１及び第２のバタフライ回路を備えた高速フーリエ変換回路において、
前記第１及び第２のバタフライ回路の両方で演算を実行する第１の動作モードと、前記第１または第２のバタフライ回路のいずれか一方で演算を実行する第２の動作モードと、を含む複数の動作モードのいずれかに対応して前記第１及び第２のバタフライ回路を選択制御する処理をコンピュータに実行させる高速フーリエ変換処理プログラム。
【国際調査報告】
2014080617.tif 000016
2014080617.tif 000017