図面 (/)

技術 高速フーリエ変換装置、高速フーリエ変換方法、及び高速フーリエ変換プログラム

出願人 日本電気株式会社
発明者 柴山充文細川晃平
出願日 2014年1月22日 (7年9ヶ月経過) 出願番号 2014-558499
公開日 2017年1月26日 (4年9ヶ月経過) 公開番号 WO2014-115540
状態 特許登録済
技術分野 複合演算
主要キーワード 高速フーリエ変換装置 データ目 ディジタルフィルタ装置 FFT装置 変換サンプル バタフライ回路 ディジタルフィルタ回路 複素回転
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年1月26日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題・解決手段

「課題」処理対象のデータの入力や処理結果の出力を任意の順序で行うことが可能な高速フーリエ変換処理方法を提供する。[解決手段]高速フーリエ変換若しくは逆高速フーリエ変換により生成された複数の出力データの出力順序設定に基づく並べ替え、又は高速フーリエ変換若しくは逆高速フーリエ変換の複数の入力データの入力順序設定に基づく並べ替えを行う。

概要

背景

デジタル信号処理において重要な処理の1つとして、高速フーリエ変換(Fast Fourier Transform。以降、「FFT」という。)処理がある。例えば、無線通信有線通信における信号伝送中の波形歪み補償する技術として、周波数領域等化(Frequency domain equalization(FDE))技術が知られている。周波数領域等化では、まず高速フーリエ変換により時間領域上の信号データが周波数領域上のデータに変換され、次に等化のためのフィルタ処理が行われる。そして、フィルタ処理後のデータは、逆高速フーリエ変換(Inverse FFT。以降、「IFFT」という。)により時間領域上の信号データに再変換されることによって、元の時間領域上の信号の波形歪みが補償される。以降、FFTとIFFTを区別しないときは、「FFT/IFFT」と表記する。

一般に、FFT/IFFT処理では、「バタフライ演算」が用いられる。バタフライ演算を用いたFFT装置については、例えば特許文献1に記載がある。特許文献1には、後述の「ひねり乗算」、すなわち、ひねり係数を用いた乗算についても記載されている。

効率的なFFT/IFFT処理方式としては、例えば非特許文献1に記載されたCooley-Tukeyによるバタフライ演算が有名である。しかし、ポイント数の大きいCooley-TukeyによるFFT/IFFTは回路が複雑になる。そのため、例えば非特許文献2に記載されたPrime Factor法を用いて2つの小さなFFT/IFFTに分解して、FFT/IFFT処理が行われる。

図19は、例えばPrime Factor法を利用して2段階の基数8のバタフライ処理に分解された、64ポイントFFTのデータフロー500を示す。データフロー500は、データ並べ替え処理501、バタフライ演算処理502、503からなる延べ16回の基数8のバタフライ演算処理、ひねり乗算処理504を含む。

図19のデータフローでは、入力された時間領域のデータx(n)(n=0,1,・・・ ,63)が、FFT処理により、周波数領域の信号X(k)(k=0,1,・・・,63)にフーリエ変換される。図19では、一部のデータフローの図示は省略されている。なお、図19のデータフローは、IFFT処理を行う場合についても、基本構成は同じである。

図19のデータフローのすべてを回路で実現するためには、膨大な規模の回路を要する。そのため、必要な処理性能に応じて、データフローの一部分の処理を実現する回路を繰り返し使用することで、FFT処理の全体を実現する方法が一般的である。

例えば、図19のデータフローにおいて、8個のデータに対して並列に(以降、単に「8データ並列で」という。)FFT処理を行うFFT装置を物理的な回路として作成した場合、合計8回の繰り返し処理により64ポイントFFT処理を実現することができる。

8回の繰り返し処理は、8個のデータに対して行われる部分データフロー505a〜505hの、それぞれにあたる処理が順に行われるものであり、具体的には、次のように行われる。すなわち、1回目には、部分データフロー505aにあたる処理が、2回目には、部分データフロー505bにあたる処理が、3回目には、部分データフロー505c(図示せず)にあたる処理が行われる。以降同様に、8回目の部分データフロー505hにあたる処理までが順に行われる。以上の処理により、64ポイントFFT処理が実現される。

バタフライ演算では、逐次的な順序に並べられたデータが、所定の規則に従った順序で読み出され、処理される。そのため、バタフライ演算では、データの並べ替えが必要であり、そのためにはRAM(Random Access Memory)が用いられる。バタフライ演算においてRAMを用いたデータの並べ替えを行うFFT装置については、例えば特許文献2に記載がある。

また、メモリ使用量を削減したFFT演算装置については、バタフライ演算の並列処理による高速化技術が、例えば特許文献3に記載されている。

概要

「課題」処理対象のデータの入力や処理結果の出力を任意の順序で行うことが可能な高速フーリエ変換処理方法を提供する。[解決手段]高速フーリエ変換若しくは逆高速フーリエ変換により生成された複数の出力データの出力順序設定に基づく並べ替え、又は高速フーリエ変換若しくは逆高速フーリエ変換の複数の入力データの入力順序設定に基づく並べ替えを行う。

目的

本発明は、デジタル信号処理におけるFFT/IFFT処理において、処理対象のデータの入力や処理結果の出力を任意の順序で行うことが可能な高速フーリエ変換回路、高速フーリエ変換処理方法、及び高速フーリエ変換プログラム記憶媒体を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

高速フーリエ変換又は逆高速フーリエ変換を行って、複数の第1の出力データを生成し、第1の順序で出力する第1の変換手段と、前記第1の順序で出力された前記複数の第1の出力データを、出力順序設定に基づいて第2の順序に並べ替える第1のデータ並べ替え処理手段と、を備える高速フーリエ変換装置

請求項2

前記第1の変換処理手段は、バタフライ演算処理を行い、前記第1の順序で前記複数の第1の出力データを出力するバタフライ演算処理手段を含み、前記第1のデータ並べ替え処理手段は、前記バタフライ演算処理後の前記複数の第1のデータを前記第2の順序に並べ替えることを特徴とする請求項1に記載の高速フーリエ変換装置。

請求項3

前記第1のデータ並べ替え処理手段は、前記複数の第1の出力データを記憶する第1の記憶手段と、前記出力順序設定に基づいて、前記第1の記憶手段からの前記複数の第1の出力データの読み出しアドレスを生成する読み出しアドレス生成手段を備え、前記複数の第1の出力データを前記第1の順序で記憶し、前記第2の順序で読み出すことを特徴とする請求項1又は2に記載の高速フーリエ変換装置。

請求項4

前記複数の第1の出力データをX(k)(kは0≦k≦N−1の整数、NはN>0の高速フーリエ変換又は逆高速フーリエポイント数)とするとき、前記第1のデータ並べ替え処理手段は、任意のkに対してX(k)とX(N-k)とを高々サイクル以内の時間差で出力することを特徴とする請求項1乃至3のいずれかに記載の高速フーリエ変換装置。

請求項5

第3の順序で入力される複数の第2の入力データを、入力順序設定に基づいて第4の順序に並べ替える第2のデータ並べ替え処理手段と、前記第4の順序に並べ替えられた前記複数の第2の入力データに対して、高速フーリエ変換又は逆高速フーリエ変換を行う第2の変換手段と、を備える高速フーリエ変換装置。

請求項6

請求項1又は5に記載の高速フーリエ変換装置を含むディジタルフィルタ装置

請求項7

請求項1に記載の高速フーリエ変換装置と、前記高速フーリエ変換装置により、入力された時間領域の複素数である前記複数の第1の入力データがフーリエ変換され生成された周波数領域の複数の第1の複素数データを構成する、すべての複素数のそれぞれの共役複素数を含む第2の複素数データを生成する複素共役生成手段と、入力された複素数の第1、第2及び第3の入力フィルタ係数から、複素数の第1及び第2の周波数領域フィルタ係数を生成するフィルタ係数生成手段と、前記第1の複素数データに対して前記第1の周波数領域フィルタ係数によりフィルタ処理を行い、第3の複素数データを出力する第1のフィルタ手段と、前記第2の複素数データに対して前記第2の周波数領域フィルタ係数によりフィルタ処理を行い、第4の複素数データを出力する第2のフィルタ手段と、前記第3の複素数信号と、前記第4の複素数信号とを合成して第5の複素数データを生成する複素共役合成手段と、を備えることを特徴とするディジタルフィルタ装置。

請求項8

請求項5に記載の高速フーリエ変換装置を備え、前記第2のデータ並べ替え処理手段は、前記第3の順序で入力される前記第5の複素数データを、前記入力順序設定に基づいて前記第4の順序に並べ替え、前記第2の変換手段は、前記第4の順序に並べ替えられた前記第5の複素数データに対して逆フーリエ変換を行って時間領域の信号に変換することを特徴とする請求項7記載のディジタルフィルタ装置。

請求項9

高速フーリエ変換若しくは逆高速フーリエ変換により生成された複数の出力データの、出力順序設定に基づく並べ替え、又は前記高速フーリエ変換若しくは前記逆高速フーリエ変換の複数の入力データの、入力順序設定に基づく並べ替えを行う高速フーリエ変換方法。

請求項10

高速フーリエ変換装置が備えるコンピュータを、高速フーリエ変換又は逆高速フーリエ変換を行う手段、及び前記高速フーリエ変換若しくは前記逆高速フーリエ変換により生成された複数の出力データの、出力順序設定に基づいて並べ替える並べ替え手段、又は前記高速フーリエ変換若しくは前記逆高速フーリエ変換の複数の入力データの、入力順序設定に基づいて並べ替える並べ替え手段として機能させるための高速フーリエ変換プログラムを格納した非一時的な記憶媒体

技術分野

0001

本発明は、デジタル信号処理における演算処理に関し、特に高速フーリエ変換装置高速フーリエ変換方法、及び高速フーリエ変換プログラム記憶媒体に関する。

背景技術

0002

デジタル信号処理において重要な処理の1つとして、高速フーリエ変換(Fast Fourier Transform。以降、「FFT」という。)処理がある。例えば、無線通信有線通信における信号伝送中の波形歪み補償する技術として、周波数領域等化(Frequency domain equalization(FDE))技術が知られている。周波数領域等化では、まず高速フーリエ変換により時間領域上の信号データが周波数領域上のデータに変換され、次に等化のためのフィルタ処理が行われる。そして、フィルタ処理後のデータは、逆高速フーリエ変換(Inverse FFT。以降、「IFFT」という。)により時間領域上の信号データに再変換されることによって、元の時間領域上の信号の波形歪みが補償される。以降、FFTとIFFTを区別しないときは、「FFT/IFFT」と表記する。

0003

一般に、FFT/IFFT処理では、「バタフライ演算」が用いられる。バタフライ演算を用いたFFT装置については、例えば特許文献1に記載がある。特許文献1には、後述の「ひねり乗算」、すなわち、ひねり係数を用いた乗算についても記載されている。

0004

効率的なFFT/IFFT処理方式としては、例えば非特許文献1に記載されたCooley-Tukeyによるバタフライ演算が有名である。しかし、ポイント数の大きいCooley-TukeyによるFFT/IFFTは回路が複雑になる。そのため、例えば非特許文献2に記載されたPrime Factor法を用いて2つの小さなFFT/IFFTに分解して、FFT/IFFT処理が行われる。

0005

図19は、例えばPrime Factor法を利用して2段階の基数8のバタフライ処理に分解された、64ポイントFFTのデータフロー500を示す。データフロー500は、データ並べ替え処理501、バタフライ演算処理502、503からなる延べ16回の基数8のバタフライ演算処理、ひねり乗算処理504を含む。

0006

図19のデータフローでは、入力された時間領域のデータx(n)(n=0,1,・・・ ,63)が、FFT処理により、周波数領域の信号X(k)(k=0,1,・・・,63)にフーリエ変換される。図19では、一部のデータフローの図示は省略されている。なお、図19のデータフローは、IFFT処理を行う場合についても、基本構成は同じである。

0007

図19のデータフローのすべてを回路で実現するためには、膨大な規模の回路を要する。そのため、必要な処理性能に応じて、データフローの一部分の処理を実現する回路を繰り返し使用することで、FFT処理の全体を実現する方法が一般的である。

0008

例えば、図19のデータフローにおいて、8個のデータに対して並列に(以降、単に「8データ並列で」という。)FFT処理を行うFFT装置を物理的な回路として作成した場合、合計8回の繰り返し処理により64ポイントFFT処理を実現することができる。

0009

8回の繰り返し処理は、8個のデータに対して行われる部分データフロー505a〜505hの、それぞれにあたる処理が順に行われるものであり、具体的には、次のように行われる。すなわち、1回目には、部分データフロー505aにあたる処理が、2回目には、部分データフロー505bにあたる処理が、3回目には、部分データフロー505c(図示せず)にあたる処理が行われる。以降同様に、8回目の部分データフロー505hにあたる処理までが順に行われる。以上の処理により、64ポイントFFT処理が実現される。

0010

バタフライ演算では、逐次的な順序に並べられたデータが、所定の規則に従った順序で読み出され、処理される。そのため、バタフライ演算では、データの並べ替えが必要であり、そのためにはRAM(Random Access Memory)が用いられる。バタフライ演算においてRAMを用いたデータの並べ替えを行うFFT装置については、例えば特許文献2に記載がある。

0011

また、メモリ使用量を削減したFFT演算装置については、バタフライ演算の並列処理による高速化技術が、例えば特許文献3に記載されている。

0012

特開平8−137832号公報
特開2001−56806号公報
特開2012−22500号公報

先行技術

0013

J.W.Cooley, J.W.Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Mathematics of Computation, US,American Mathematical Society, Apr. 1965, Vol.19, No. 90, pp. 297-301
D.P.Kolba, "A Prime FactorFFTAlgorithm Using High-Speed Convolution,"IEEE Trans. on Acoustics, US, IEEE Signal Processing Society, Aug. 1977, Vol.29, No.4 , pp. 281-294

発明が解決しようとする課題

0014

FFT処理によりフーリエ変換された周波数領域の信号X(k)(k=0,1,・・・,N-1)に対して、kの値が異なる複数のX(k)の間で演算が行われる場合がある。例えば、2個のデータX(k)、X(N-k)の間で演算が行われる場合がある。この場合、X(k)とX(N-k)は、ある一つの演算の入力信号であるため、同サイクル、あるいは極力、近いサイクルで入力されることが望ましい。なぜなら、演算を開始するためには、すべての入力信号が揃っていることが必要であるからである。このように、FFT処理の結果、得られる複数の信号には、FFT処理の後段での処理を高速化するために、同時、あるいは、極力、近いタイミングで後段へ入力することが有効である、特定の組み合わせがある。さらに一般的には、複数の信号を後段へ出力するときの出力順序を、後段の処理にとって最適なものとすることが有効である。

0015

しかしながら、非特許文献1、2に記載されたFFT回路は、後段の演算の高速化を考慮した順序でFFT処理結果の信号X(k)を出力することはなく、演算が完了した順にFFT処理結果X(k)を出力する。そのため、X(k)とX(N-k)とが、最小の出力間隔である1サイクルよりも多い、複数サイクル離れたサイクルで出力されることがある。例えば、極端な場合では、N=128の場合、X(0)とX(127)のように、127サイクル離れて出力されることがある。

0016

このような場合に、X(k)とX(N-k)との間で演算を行うためには、FFT回路の後に、X(k)とX(N-k)とを同サイクル、あるいは近傍のサイクルで出力するためのデータ並べ替え手段を設ける必要がある。

0017

FFT回路601の後段にデータ並べ替え処理回路602を接続した、FFT装置600の構成例を図20に示す。上記のように、FFTのポイント数に近いサイクル数だけ離れたサイクルで出力されることを考慮すると、データ並べ替え回路602は、すくなくともFFTの1ブロック分のデータを保持可能な記憶手段を備えることが必要である。さらに、複数の処理結果の、個々の処理結果についての後段への出力タイミングあるいは出力順序は、後段の処理にとって最適であることが望ましい。

0018

ところが、非特許文献1、2に記載されたFFT回路では、データ並べ替え回路を備えていないため、処理結果の出力タイミングも出力順序も制御することができない。そのため、FFT処理を含む処理全体にかかる処理遅延レイテンシ)が増大するという問題がある。

0019

特許文献2、3のFFT装置においても、FFT処理によって得られる、複数の結果の出力タイミングは考慮されていない。特許文献2のFFT装置では、バタフライ演算部への入力データの並べ替えは行われる。特許文献3のFFT演算装置は、バタフライ演算を並列化することによって高速化を図っている。しかし、特許文献2、3のFFT装置においても、FFT処理の結果の信号の出力順序については、特に考慮されていない。そのため、FFT処理の演算が完了した順に、信号が出力されることとなり、その順序は必ずしも後段の処理の高速化に適したものではない。従って、特許文献2、3のFFT装置にも、処理全体にかかる処理遅延が増大するという、上記と同様の問題がある。

0020

以上のように、非特許文献1、2及び特許文献2、3の技術は、FFT処理の処理結果の出力タイミングや出力順序を最適化することができないという問題がある。

0021

処理結果のタイミングあるいは出力順序の最適化が有効であることは、IFFT処理の後段において、IFFT処理の結果を用いた処理が行われる場合についても同様である。

0022

さらに、FFT処理やIFFT処理の前段における処理の結果の出力順序が、FFT処理やIFFT処理において行われる演算の実行順序にとって最適でない場合も考えられる。そのような場合には、FFT処理やIFFT処理にとって最適な順序となるように、前段からの入力データを並べ替えることが有効である。
(発明の目的)
本発明は、デジタル信号処理におけるFFT/IFFT処理において、処理対象のデータの入力や処理結果の出力を任意の順序で行うことが可能な高速フーリエ変換回路高速フーリエ変換処理方法、及び高速フーリエ変換プログラム記憶媒体を提供することを目的とする。

課題を解決するための手段

0023

本発明の高速フーリエ変換装置は、高速フーリエ変換又は逆高速フーリエ変換を行って、複数の第1の出力データを生成し、第1の順序で出力する第1の変換部と、第1の順序で出力された複数の第1の出力データを、出力順序設定に基づいて第2の順序に並べ替える第1のデータ並べ替え処理部と、を備えることを特徴とする。

0024

本発明の高速フーリエ変換装置は、第3の順序で入力される複数の第2の入力データを、入力順序設定に基づいて第4の順序に並べ替える第2のデータ並べ替え処理部と、第4の順序に並べ替えられた複数の第2の入力データに対して、高速フーリエ変換又は逆高速フーリエ変換を行う第2の変換部と、を備えることを特徴とする。

0025

本発明の高速フーリエ変換方法は、高速フーリエ変換若しくは逆高速フーリエ変換により生成された複数の出力データの出力順序設定に基づく並べ替え、又は高速フーリエ変換若しくは逆高速フーリエ変換の複数の入力データの入力順序設定に基づく並べ替えを行うことを特徴とする。

0026

本発明の高速フーリエ変換プログラム記憶媒体は、高速フーリエ変換装置が備えるコンピュータを、高速フーリエ変換又は逆高速フーリエ変換を行う手段、及び高速フーリエ変換若しくは逆高速フーリエ変換により生成された複数の出力データの出力順序設定に基づいて並べ替える並べ替え手段、又は高速フーリエ変換若しくは逆高速フーリエ変換の複数の入力データの入力順序設定に基づいて並べ替える並べ替え手段として機能させるためのプログラムを格納する非一時的な記憶媒体であることを特徴とする。

発明の効果

0027

本発明によれば、デジタル信号処理におけるFFT/IFFT処理において、処理対象のデータの入力や処理結果の出力を任意の順序で行うことができる。

図面の簡単な説明

0028

本発明の第1の実施形態に係るFFT装置10の構成を示すブロック図である。
本発明の第1の実施形態に係る逐次順序に従うデータ組の配列を示す図である。
本発明の第1の実施形態に係るビットリバース順序に従うデータ組の配列を示す図である。
本発明の第1の実施形態に係る任意データ組逐次順序に従うデータ組の配列を示す図である。
本発明の第1の実施形態に係る第1のデータ並べ替え回路11、第2のデータ並べ替え回路12の構成例100を示すブロック図である。
本発明の第1の実施形態に係る第3のデータ並べ替え処理回路13の構成例200を示すブロック図である。
本発明の第2の実施形態に係るIFFT装置20の構成を示すブロック図である。
本発明の第2の実施形態に係る第1のデータ並べ替え処理回路14の構成例300を示すブロック図である。
本発明の第3の実施形態に係るFFT装置30の構成を示すブロック図である。
本発明の第3の実施形態に係る任意データ組ビットリバース順序に従うデータ組の配列を示す図である。
本発明の第4の実施形態に係るIFFT装置40の構成を示すブロック図である。
本発明の高速フーリエ変換装置が備える必須の構成を示すブロック図である。
本発明の第5の実施形態に係るディジタルフィルタ回路の構成例400を示すブロック図である。
本発明の第5の実施形態に係る複素共役生成回路415の構成を示すブロック図である。
本発明の第5の実施形態に係るフィルタ回路421の構成を示すブロック図である。
本発明の第5の実施形態に係るフィルタ回路422の構成を示すブロック図である。
本発明の第5の実施形態に係る複素共役合成回路416の構成を示すブロック図である。
本発明の第5の実施形態に係るフィルタ係数生成回路441の構成を示すブロック図である。
2段階のバタフライ演算を用いる64ポイントFFT処理のデータフロー500を示す図である。
データ並べ替え回路を備えるFFT装置600の構成を示すブロック図である。

実施例

0029

(第1の実施形態)
図1は、本発明の第1の実施形態に係るFFT装置10の構成例を示すブロック図である。FFT装置10は、図19に示されたデータフロー500に従って、2段階の基数8のバタフライ処理に分解された64ポイントFFTを、パイプライン回路方式によって処理する。FFT装置10は、時間領域のデータx(n)(n=0,1,・・・ ,N-1)を入力し、x(n)をFFT処理によりフーリエ変換して周波数領域の信号X(k)(k=0,1,・・・,N-1)を生成し、出力する。ここで、NはFFTブロックサイズを表す正整数である。

0030

FFT装置10は、8データ並列で64ポイントFFT処理を行うものとする。この場合、FFT回路10は、時間領域のデータx(n)を入力し、FFT処理によりフーリエ変換した周波数領域の信号X(k)を生成して出力する。このとき、入力データx(n) として、8データずつ、8サイクルの期間に、図2に示す順序で、合計で64個のデータが入力される。なお、ここでは、図2の表の内容として示された、0から63までの数字は、x(n)の添え字nを意味する。

0031

具体的には、1サイクル目に、データ組P1を構成するx(0),x(1),・・・,x(7)の8データが入力される。そして、2サイクル目に、データ組P2を構成するx(8),x(9),・・・,x(15)の8データが入力される。以降同様に、3サイクル目から8サイクル目まで、データ組P3〜P8を構成するデータが入力される。

0032

同様に、出力データX(k)として、8データずつ、8サイクルの期間に、図2に示す順序で、64データを出力される。なお、ここでは、図2の表の内容として示された、0から63までの数字は、X(k)の添え字kを意味する。

0033

具体的には、1サイクル目に、データ組P1を構成するX(0),X(1),・・・,X(7)の8データが出力される。2サイクル目に、データ組P2を構成するX(8),X(9),・・・,X(15)の8データが出力される。以降同様に、3サイクル目から8サイクル目まで、データ組P3〜P8を構成するデータが出力される。

0034

FFT装置10は、第1のデータ並べ替え処理部11、第1のバタフライ演算処理部21、第2のデータ並べ替え処理部12、ひねり乗算処理部31、第2のバタフライ演算処理部22、第3のデータ並べ替え処理部13、読み出しアドレス生成部41を備える。FFT装置10は、第1のデータ並べ替え処理、第1のバタフライ演算処理、第2のデータ並べ替え処理、ひねり乗算処理、第2のバタフライ演算処理、第3のデータ並べ替え処理を、パイプライン処理する。

0035

第1のデータ並べ替え処理部11、第2のデータ並べ替え処理部12は、データ並べ替えのためのバッファ回路である。第1のデータ並べ替え処理部11、第2のデータ並べ替え処理部12は、それぞれ、第1のバタフライ演算処理部21の前と後で、FFT処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。

0036

第3のデータ並べ替え処理部13も、同様に、データ並べ替えのためのバッファ回路である。すなわち、第3のデータ並べ替え処理部13は、第2のバタフライ演算処理部22の後で、FFT処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。さらに、第3のデータ並べ替え処理部13は、上記の並べ替えに加えて、FFT装置10の出力X(k)において、任意のkに対して、出力X(k)とX(N-k)とを高々1サイクル以内の時間差で出力するための並べ替え処理も行う。

0037

具体的には、第1のデータ並べ替え処理部11は、入力データx(n)の入力順序である図2に示す「逐次順序」を、第1のバタフライ演算処理部21に入力する順序である図3に示す「ビットリバース順序」に並べ替える。

0038

図3に示すビットリバース順序は、図19に示したデータフロー図における、1段目の基数8のバタフライ処理502への入力データ組に対応する。具体的には、具体的には、1サイクル目に、データ組P1を構成するx(0),x(8),・・・,x(56)の8データを入力する。そして、2サイクル目に、データ組P2を構成するx(1),x(9),・・・,x(57)の8データを入力する。以降、3サイクル目から8サイクル目まで同様にして、データ組P3〜P8を構成するデータを入力する。

0039

ここで、「逐次順序」と「ビットリバース順序」について、具体的に説明する。「逐次順序」とは、図2に示された、8つのデータ組P1、P2、P3、P4、P5、P6、P7、P8の順序をいう。データ組Ps(sは処理サイクルの順を示す値。s=1,・・・,8)は、それぞれ、ps(0)からps(7)まで、順に並んだ8個のデータからなり、ps(i)は、
ps(i)=8(s−1)+i
である。そして、各データ組は、処理のサイクルの進行に対応して、P1、P2、P3、P4、P5、P6、P7、P8の順に並べられている。つまり、逐次順序とは、is個のデータを、先頭のデータからi個ずつデータ順に並べてデータ組をs個作成し、そのデータ組をサイクル順に並べたものである。

0040

「ビットリバース順序」とは、図3に示された、8つのデータ組Q1、Q2、Q3、Q4、Q5、Q6、Q7、Q8の順序をいう。データ組Qsは、それぞれ、qs(0)からqs(7)までの8個のデータからなり、qs(i)は、
qs(i)=(s−1)+8i
である。そして、各データ組は、処理のサイクルの進行に対応して、Q1、Q2、Q3、Q4、Q5、Q6、Q7、Q8の順に並べられている。つまり、ビットリバース順序とは、逐次順序で入力されたis個のデータを、先頭のデータからs個ずつサイクル順に並べ、同じサイクルのi個のデータを1つの組としてデータ順に並べたものである。

0041

以上のように、ビットリバース順序の各データ組は、逐次順序の各組が設定されれば一意に定まる。ビットリバース順序の各データ組Qs(s=1,・・・,8)を構成するデータのiデータ目は、逐次順序に従ったサイクルiにおける、sデータ目のデータである。すなわち、
Qs(i)=Pi(s)
である。このように、Qs(i)とPi(s)とは、各データ組を構成するデータについての、サイクルの進行に対する順序とデータ位置に対する順序が入れ替えられた関係にある。従って、ビットリバース順序で入力されたデータを、ビットリバース順序に従って並べ替えると、逐次順序になる。

0042

図2における各行ps(i)、及び図3における8つの行qs(i)は、それぞれ、次段のiデータ目に入力されるデータを示す。各データ組に含まれる8個の数字は、FFTのポイントのうちの1個を特定する識別情報であり、具体的にはx(n)の添え字nの値である。

0043

図2のデータ組Psと、図3のデータ組Qsとの間の並べ替え、すなわち各データ組とそれに含まれる識別情報との対応関係の入れ替えは、第2の実施形態以降に示す他のデータ並べ替え回路においても行われることがある。

0044

なお、逐次順序及びビットリバース順序は、図2、3に例示されたものに限定されない。すなわち、逐次順序の各データ組は、上記のように、FFTのポイント数、サイクル数、並列に処理するデータ数に応じて、データを順に並べて作成すればよい。そして、ビットリバース順序の各データ組は、上記のように、逐次順序で入力されるデータの、サイクルの進行に対する順序とデータ位置に対する順序を入れ替えて作成すればよい。

0045

第1のバタフライ演算処理部21は、図19のデータフロー500において2回行われる基数8のバタフライ演算処理の、1回目のバタフライ演算処理502(第1のバタフライ演算処理)を処理するバタフライ回路である。第1のバタフライ演算処理部21は、バタフライ演算処理の結果を、データy(n)(n=0,1,・・・ ,63)として、図2の逐次順序で出力する。

0046

第2のデータ並べ替え処理部12は、第1のバタフライ演算処理部21が逐次順序で出力するデータy(n)を、第2のバタフライ演算処理部22に入力するために、図3のビットリバース順序に並べ替える。

0047

ひねり乗算処理部31は、第1のバタフライ演算処理後に、FFT演算における複素平面上の複素回転を処理する回路であり、図19のデータフロー500における、ひねり乗算処理504に対応する。なお、ひねり乗算処理では、データの並べ替えは行われない。

0048

第2のバタフライ演算処理部22は、図19のデータフロー図における、2回目の基数8のバタフライ処理503を処理するバタフライ回路である。第2のバタフライ演算処理部22は、ビットリバース順序で入力されるひねり乗算処理後のデータy'(n)(n=0,1,・・・ ,63)に対してバタフライ演算処理を行い、その結果X(k)(n=0,1,・・・ ,63)を、同じくビットリバース順序で出力する。

0049

第3のデータ並べ替え処理部13は、第2のバタフライ演算処理部22がビットリバース順序で出力するデータX(k)を、図4の順序(以降、「任意データ組逐次順序」という。)に並べ替える。「任意データ組逐次順序」は、FFT装置10が、FFT処理の最終結果として出力する順序である。任意データ組逐次順序は、逐次順序で作成されたs個のデータ組Psが、サイクルの進行に合わせて出力されるときの順序であり、出力順序指定52によって指定することができる。本実施形態では、任意データ組逐次順序は、P1、P8、P2、P7、P3、P6、P4、P5という順序に指定される。

0050

図4における各行ps(i)は、次段のiデータ目に入力されるデータを示す。各データ組に含まれる8個の数字は、FFTのポイントのうちの1個を特定する識別情報であり、具体的にはX(k)の添え字kの値である。

0051

第3のデータ並べ替え処理部13は、読み出しアドレス生成部41が出力する読み出しアドレス51を入力して、データX(k)の出力順序を決定する。

0052

読み出しアドレス生成部41は、CPU(Central Processing Unit)などの上位回路(図示せず)から与えられる出力順序設定52を参照して、データ並べ替え処理部13に出力する読み出しアドレス51を生成する。

0053

データ並べ替え処理部が、入力されたデータを一旦記憶し、記憶したデータの選択及び出力を制御することによって、図2の逐次順序、図3のビットリバース順序、図4の任意データ組逐次順序のそれぞれに従ったデータの並べ替え処理が実現される。以下に、データ並べ替え処理部の具体例を示す。

0054

第1のデータ並べ替え処理部11、及び第2のデータ並べ替え処理部12は、例えば図5に示すデータ並べ替え処理部100で実現することができる。

0055

データ並べ替え処理部100は、入力情報103として入力される8個のデータからなるデータ組D1〜D8を、FIFOバッファ(First In First Out Buffer。先入れ先出しバッファ)における先入れ順序で入力して、データ記憶位置101a〜101hに書き込み、記憶する。具体的には、データ記憶位置101a〜101hのそれぞれに、データ組D1〜D8が記憶される。

0056

次に、データ並べ替え処理部100は、FIFOバッファにおける先出し順序で、記憶しているデータを出力する。具体的には、データ並べ替え処理部100は、データ読み出し位置102a〜102hのそれぞれから8個のデータを読み出して1つのデータ組とし、8つのデータ組D1’〜D8’を出力情報104として出力する。このように、データ組D1’ 〜D8’は、サイクル順に並べられたデータ組D1〜D8に含まれるデータを、データ位置の順に並べ替えて1つの組としたものである。

0057

一方、図6は、第3のデータ並べ替え処理部13の実現例を示すデータ並べ替え処理部200の構成図である。データ並べ替え処理部200は、入力情報203として入力される8個のデータからなるデータ組P1〜P8を、FIFOバッファにおける先入れ順序で入力して、データ記憶位置201a〜201hに書き込み、記憶する。すなわち、サイクル順に対応するデータ記憶位置201a〜201hのそれぞれに、データ組D1〜D8が順に記憶される。このとき、記憶されたデータをデータ位置の順、すなわち、データ記憶位置202a〜202hの順に見ると、データ記憶位置202a〜202hのそれぞれには、データ組D1’〜D8’が記憶されている。

0058

次に、データ並べ替え処理部200は、記憶しているデータを、読み出し回路205により読み出して、出力情報204として出力する。このとき、読み出し回路205は、読み出しアドレス51を参照して、データ記憶位置202a〜202hの中からいずれか1つを選択して、データ記憶位置202a〜202hに記憶されている8個のデータのいずれか1つを1回の読み出し動作で読み出す。このように、読み出しアドレス51に任意に指定可能な所望順番で読み出しアドレスを与えることにより、任意の順番でデータを読み出すことができる。例えば、読み出しアドレス51に、アドレス1、8、2、7、3、6、4、5、の順番で読み出しアドレスを与えた場合、データ並べ替え処理部200は、データ組D1’、D8’、D2’、D7’、D3’、D6’、D4’、D5’、の順番で、記憶しているデータを出力する。すなわち、図4に示した任意データ組逐次順序で、データが出力される。ここで、データ組D1’ 〜D8’は、サイクル順に並べられたデータ組D1〜D8に含まれるデータを、データ位置の順に並べ替えて1つの組としたものである。

0059

以上説明したように、FFT装置10において、第1のデータ並べ替え処理部11、第2のデータ並べ替え処理部12、及び第3のデータ並べ替え処理部13によって、図2の逐次順序、図3のビットリバース順序、図4の任意データ組逐次順序のそれぞれに従った3回の並べ替え処理が行われる。

0060

第1のデータ並べ替え処理部11、第2のデータ並べ替え処理部12、及び第3のデータ並べ替え処理部13のそれぞれを、以上のように制御することによって、次段の処理に必要な複数のデータを近いタイミングで出力することができるので、さらにデータの並べ替えを行う必要がない。以下に、第3のデータ並べ替え処理部13におけるデータの並べ替えを例として、説明する。

0061

図1に示したFFT装置10を用いて、8データ並列で64ポイントFFT処理を行う場合を例として説明する。FFT装置10は、時間領域のデータx(n)(n=0,1,・・・ ,63)を入力し、FFT処理によりフーリエ変換した周波数領域の信号X(k)(k=0,1,・・・,63)を生成して出力する。入力データx(n)は、8データずつ8サイクルの期間に、図2に示す順序で入力され、合計で64個のデータx(n)が入力される。なお、図2には、x(n)の添え字nのみが表記されている。

0062

具体的には、1サイクル目に、データ組P1を構成するx(0),x(1),・・・,x(7)の8データが入力される。そして、2サイクル目に、データ組P2を構成するx(8),x(9),・・・,x(15)の8データが入力される。以降、3サイクル目から8サイクル目まで同様にして、データ組P3〜P8を構成するデータが入力される。

0063

一方、出力データX(k)は、8データずつ8サイクルの期間に、例えば図4に示す順序で、合計64個のデータを出力する。なお、図4には、X(k)の添え字kのみが表記されている。具体的には、各サイクルにおいて、以下のデータが出力される。
1サイクル目:
データ組D1を構成するX(0),X(1),・・・,X(7)の8データが出力される。
2サイクル目:
データ組D8を構成するX(56),X(57),・・・,X(63)の8データが出力される。
3サイクル目:
データ組D2を構成するX(8),X(9),・・・,X(15)の8データが出力される。
4サイクル目:
データ組D7を構成するX(48),X(49),・・・,X(55)の8データが出力される。
5サイクル目:
データ組D3を構成するX(16),X(17),・・・,X(23)の8データが出力される。
6サイクル目:
データ組D6を構成するX(40),X(41),・・・,X(47)の8データが出力される。
7サイクル目:
データ組D4を構成するX(24),X(25),・・・,X(31)の8データが出力される。
8サイクル目:
データ組D5を構成するX(32),X(33),・・・,X(39)の8データが出力される。

0064

このように、添え字k1、k2の合計が、FFTのポイント数に対応する63になるような、2個の出力データX1(k1)、X2(k2)は、常に、連続したサイクルに出力される。すなわち、FFT装置10は、任意の添え字kに対して、出力X(k)とX(N-k)(N=63)とを、高々1サイクル以内の時間差で出力することができる。
(第1の実施形態の効果)
以上のように、本実施形態では、FFT装置10は、出力順序設定52を用いて順序を指定することによって、任意の順序でデータを出力することができる。

0065

例えば、FFT装置10の後段において、出力データX(k)(k=0,1,・・・,N-1)に対して、kの異なる複数のX(k)の間で演算が行われる場合に、演算の入力値である2つのX(k)をできるだけ近いサイクルで出力することができる。X(k)とX(N-k)との間で演算をする場合、X(k)とX(N-k)を高々1サイクル以内の時間差で出力することができる。その結果、出力に対する新たな並べ替えを行うための回路の追加を必要としない。

0066

また、出力データを出力する順序を指定可能とするために、追加すべき回路は、読み出しアドレス生成部41のみであり、回路規模としては非常に小さい。

0067

従って、後段の処理を含め、全体としての回路規模、及び消費電力の増大を抑制することができる。

0068

なお、本実施形態では、FFT処理を例として説明したが、IFFTにおいても同様である。すなわち、本実施形態の制御方法をIFFT処理装置に適用して、IFFT処理の後段の処理内容を考慮して処理結果の出力順序を最適化すれば、IFFT処理の後段の処理を高速化することができる。
(第2の実施形態)
第1の実施形態とは逆に、FFT/IFFT処理の前段の処理結果が、その処理に独自の順序で出力され、FFT/IFFT処理装置に入力される場合がある。この場合は、入力された前段の処理結果を、FFT/IFFT処理に適した順序に並べ替えることが、FT/IFFT処理の高速化や、回路規模及び消費電力の増加の抑制のために有効である。

0069

第2の実施形態では、前段のFFT装置10の出力の順序である任意データ組逐次順序(例えば図4に示す順序)に対応して動作するIFFT装置について説明する。

0070

図7は、本発明の第2の実施形態に係るIFFT装置20の構成例を示すブロック図である。IFFT装置20は、図19に示されたFFTのデータフロー500と同様のデータフローで、2段階の基数8のバタフライ処理に分解された64ポイントIFFTを、パイプライン回路方式によって処理する。IFFT装置20は、FFT装置10によりフーリエ変換された周波数領域の信号X(k)(k=0,1,・・・,N-1)を入力し、X(k)をフーリエ逆変換により時間領域のデータy(n)(n=0,1,・・・ ,N-1)を生成し、出力する。ここで、NはIFFTブロックサイズを表す正整数である。

0071

図7において、IFFT装置20は、8データ並列で64ポイントIFFT処理を行う。IFFT装置20は、FFT装置10の出力と同様の、図4に示す任意データ組逐次順序で入力X(k)を入力する。一方、IFFT装置20は、図2に示す逐次順序で出力y(n)を出力する。

0072

IFFT装置20は、第1のデータ並べ替え処理部14、第1のバタフライ演算処理部21、第2のデータ並べ替え処理部12、ひねり乗算処理部31、第2のバタフライ演算処理部22、第3のデータ並べ替え処理部15、書き込みアドレス生成部42を備える。IFFT装置20は、第1のデータ並べ替え処理、第1のバタフライ演算処理、第2のデータ並べ替え処理、ひねり乗算処理、第2のバタフライ演算処理、第3のデータ並べ替え処理を、パイプライン処理する。

0073

第1のデータ並べ替え処理部14は、データ並べ替えのためのバッファ回路である。すなわち、第1のデータ並べ替え処理部14は、第1のバタフライ回路21の前で、IFFT処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。さらに、第1のデータ並べ替え処理部14は、上記の並べ替えに加えて、任意データ組逐次順序でデータを入力するための並べ替え処理も行う。

0074

具体的には、第1のデータ並べ替え処理部14は、入力データX(k)の入力順序である図4に示す任意データ組逐次順序を、第1のバタフライ演算処理部21に入力する順序である図3に示すビットリバース順序に並べ替える。

0075

第2のデータ並べ替え処理部12、第3のデータ並べ替え処理部15も、同様に、データ並べ替えのためのバッファ回路である。第2のデータ並べ替え処理部12、第3のデータ並べ替え処理部15は、それぞれ、第1のバタフライ演算回路21、第2のバタフライ演算回路22の後で、IFFT処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。

0076

第1のバタフライ演算処理部21は、図19のデータフロー500において2回行われる基数8のバタフライ演算処理の、1回目のバタフライ演算処理502(第1のバタフライ演算処理)を処理するバタフライ回路である。第1のバタフライ演算処理部21は、バタフライ演算処理の結果を、データy(n)(n=0,1,・・・ ,63)として、図2の逐次順序で出力する。

0077

第2のデータ並べ替え処理部12は、第1のバタフライ演算処理部21が逐次順序で出力するデータy(n)を、ひねり乗算処理部31に入力するために、図3のビットリバース順序に並べ替える。

0078

ひねり乗算処理部31は、第1のバタフライ演算処理後に、IFFT演算における複素平面上の複素回転を処理する回路であり、図19のデータフロー500における、ひねり乗算処理504に対応する。なお、ひねり乗算処理では、データの並べ替えは行われない。

0079

第2のバタフライ演算処理部22は、図19のデータフロー500における、2回目の基数8のバタフライ処理503を処理するバタフライ回路である。第2のバタフライ演算処理部22は、ビットリバース順序で入力されるひねり乗算処理後のデータy'(n)(n=0,1,・・・ ,63)に対してバタフライ演算処理を行い、その結果X(k)(n=0,1,・・・ ,63)を、同じくビットリバース順序で出力する。

0080

第3のデータ並べ替え処理部15は、第2のバタフライ演算処理部22がビットリバース順序で出力するデータX(k)を、図2の逐次順序に並べ替える。すなわち、IFFT装置20は、IFFT処理の最終結果を逐次順序で出力する。

0081

第1のデータ並べ替え処理部14は、書き込みアドレス生成部42が出力する書き込みアドレス53を入力して、データX(k)の入力順序を決定する。

0082

書き込みアドレス生成部42は、CPUなどの上位回路(図示せず)から与えられる入力順序設定54を参照して、データ並べ替え処理部14に出力する書き込みアドレス53を生成する。

0083

第2のデータ並べ替え処理部12、及び第3のデータ並べ替え処理部15は、例えば図5に示すデータ並べ替え処理部100で実現することができる。

0084

図8は、第1のデータ並べ替え処理部14の実現例を示すデータ並べ替え処理部300の構成図である。データ並べ替え処理部300は、入力情報303として任意データ組逐次順序で入力される8個のデータからなるデータ組D1〜D8を、書き込み回路305により、書き込み位置301a〜301hに書き込む。このとき、書き込み回路305は、書き込みアドレス53を参照して、書き込み位置301a〜301hの中から、いずれか1つを選択して、1回の書き込み動作を行う。すなわち、書き込みアドレス53に指定された所定の順番で書き込みアドレスを与えることにより、所望の順番でデータを書き込むことができる。

0085

例えば、書き込みアドレス53に、アドレス1、8、2、7、3、6、4、5、の順番で書き込みアドレスを与えた場合、データ並べ替え処理部300は、データ組D1、D8、D2、D7、D3、D6、D4、D5、の順番で入力したデータを、書き込み位置301a〜301hに対してD1、D2、D3、D4、D5、D6、D7、D8、の順番で書き込み、記憶する。すなわち、データ記憶位置301a〜301hのそれぞれに、データ組D1〜D8が順に記憶される。このとき、記憶されたデータをサイクル順、すなわち、データ記憶位置302a〜302hの順に見ると、データ記憶位置302a〜302hのそれぞれには、データ組D1’〜D8’が記憶されている。

0086

次に、データ並べ替え処理部300は、記憶しているデータを、FIFOバッファにおける先出し順序で読み出して出力する。具体的には、データ並べ替え処理部300は、データ記憶位置302a〜302hのそれぞれに記憶されている、データ組D1’〜D8 ’を、D1’、D2’、D3’、D4’、D5’、D6’、D7’、D8’、の順序で読み出して出力する。

0087

すなわち、第1のデータ並べ替え処理部14に相当するデータ並べ替え処理部300は、書き込みアドレス53に任意に指定可能な所望の順番で書き込みアドレスを与えることにより、任意の順番でデータを入力することができる。例えば、書き込みアドレス53に、アドレス1、8、2、7、3、6、4、5、の順番で書き込みアドレスを与えた場合、データ並べ替え処理部300は、データ組D1、D8、D2、D7、D3、D6、D4、D5、の順番でデータを入力する。すなわち、図4に示した任意データ組逐次順序でデータ入力して記憶する。

0088

一方、第2のデータ並べ替え処理部12、第3のデータ並べ替え処理部15に相当するデータ並べ替え処理部100は、記憶しているデータを、D1、D2、D3、D4、D5、D6、D7、D8、の順番、すなわち図1の逐次順序で、データを出力する。
(第2の実施形態の効果)
以上のように、本実施形態では、IFFT装置20は、入力順序設定54を用いて順序を指定することによって、任意の順序でデータを入力することができる。従って、FFT装置10の出力順序に対応して、入力に対する新たな並べ替え手段を必要としない。

0089

また、任意の順序で入力される入力データに対応するために、追加すべき回路は、書き込みアドレス生成部42のみであり、回路規模としては非常に小さい。

0090

従って、前段の処理を含め、全体としての回路規模、及び消費電力の増大を抑制することができる。

0091

なお、本実施形態では、IFFT処理を例として説明したが、FFTにおいても同様である。すなわち、本実施形態の制御方法をFFT処理装置に適用して、FFT処理の前段の処理内容を考慮して入力信号の入力順序を最適化すれば、FFT処理を高速化することができる。
(第3の実施形態)
FFT装置10において、第2のデータ並べ替え処理部12に改造を加えることによって、第3のデータ並べ替え処理部13は省略することができる。FFT装置10から第3のデータ並べ替え処理部13を除いたFFT装置30の構成を、図9を参照して説明する。

0092

図9は、本発明の第3の実施形態に係るFFT装置30の構成例を示すブロック図である。FFT装置30は、図19に示されたFFTのデータフローと同様のデータフローで、2段階の基数8のバタフライ処理に分解された64ポイントFFTを、パイプライン回路方式によって処理する。FFT装置30は、時間領域のデータx(n)(n=0,1,・・・ ,N-1)を入力し、x(n)をFFT処理によりフーリエ変換して周波数領域の信号X(k)(k=0,1,・・・,N-1)を生成し、出力する。ここで、NはFFTブロックサイズを表す正整数である。

0093

図9に示したFFT装置30を用いて、8データ並列で64ポイントFFT処理を行う場合を例として説明する。FFT装置30は、時間領域のデータx(n)(n=0,1,・・・ ,63)を入力し、FFT処理によりフーリエ変換した周波数領域の信号X(k)(k=0,1,・・・,63)を生成して出力する。入力データx(n)は、8データずつ8サイクルの期間に、図2に示す順序で入力され、合計で64個のデータx(n)が入力される。

0094

一方、出力データX(k)は、8データずつ8サイクルの期間に、例えば図10に示す順序(以降、「任意データ組ビットリバース順序」という。)で、合計で64個が出力される。

0095

図10における各行qs(i)は、次段のiデータ目に入力されるデータを示す。各データ組に含まれる8個の数字は、FFTのポイントのうちの1個を特定する識別情報であり、具体的にはx(k)の添え字kの値である。

0096

具体的には、各サイクルにおいて、以下のデータが出力される。
1サイクル目:
データ組Q1を構成するX(0),X(8),・・・,X(56)の8データが出力される。
2サイクル目:
データ組Q8を構成するX(7),X(15),・・・,X(63)の8データが出力される。
3サイクル目:
データ組Q2を構成するX(1),X(9),・・・,X(57)の8データが出力される。
4サイクル目:
データ組Q7を構成するX(6),X(14),・・・,X(62)の8データが出力される。
5サイクル目:
データ組Q3を構成するX(2),X(10),・・・,X(58)の8データが出力される。
6サイクル目:
データ組Q6を構成するX(5),X(13),・・・,X(61)の8データが出力される。
7サイクル目:
データ組Q4を構成するX(3),X(11),・・・,X(59)の8データが出力される。
8サイクル目:
データ組Q5を構成するX(4),X(12),・・・,X(60)の8データが出力される。

0097

このように、添え字k1、k2の合計が、FFTのポイント数に対応する63になるような、2個の出力データX1(k1)、X2(k2)は、常に、連続したサイクルに出力される。すなわち、FFT装置30は、FFT装置10と同様に、任意の添え字kに対して、出力X(k)とX(N-k) (N=63)とを、高々1サイクル以内の時間差で出力することができる。

0098

FFT装置30は、第1のデータ並べ替え処理部11、第1のバタフライ演算処理部21、第2のデータ並べ替え処理部16、ひねり乗算処理部31、第2のバタフライ演算処理部22、読み出しアドレス生成部43を備える。FFT装置30において、FFT装置10と同一の構成には同一の符号を付加し、詳細な説明は省略する。FFT装置30は、第1のデータ並べ替え処理、第1のバタフライ演算処理、第2のデータ並べ替え処理、ひねり乗算処理、第2のバタフライ演算処理を、パイプライン処理する。

0099

FFT装置30は、FFT装置10の構成から第3のデータ並べ替え処理部13を除いた構成をもつ。FFT装置10における第3のデータ並べ替え処理部13が、読み出しアドレス51を参照して行っていた並べ替え処理は、FFT装置30では、第2のデータ並べ替え処理部16が行う。すなわち、第2のデータ並べ替え処理部16は、読み出しアドレス55を入力して、FFT処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。さらに、第2のデータ並べ替え処理部16は、上記の並べ替えに加えて、FFT装置30の出力X(k)において、任意のkに対して、出力X(k)とX(N-k)とを高々1サイクル以内の時間差で出力するための並べ替え処理を行う。

0100

具体的には、第2のデータ並べ替え処理部16は、第1のバタフライ演算処理部21が図2の逐次順序で出力するデータを、ひねり乗算処理部31に入力する順序である図10に示す任意データ組ビットリバース順序に並べ替える。

0101

第2のデータ並べ替え処理部16は、図6に示したデータ並べ替え処理部200と同様の構成で実現することができる。

0102

ひねり乗算処理部31、及び第2のバタフライ演算処理部22は、データ組間の順序を変更しないため、第2のバタフライ演算処理部22は、FFT処理結果X(k)を、図10の任意データ組ビットリバース順序で出力する。
(第3の実施の形態の効果)
以上のように、本実施形態では、FFT装置30は、出力順序設定56を用いて順序を指定することによって、任意の順序でデータを出力することができる。

0103

例えば、FFT装置30の後段において、出力データX(k)(k=0,1,・・・,N-1)に対して、kの異なる複数のX(k) の間で演算が行われる場合に、演算の入力値であるX(k)をできるだけ近いサイクルで出力することができる。X(k)とX(N-k)との間で演算をする場合、X(k)とX(N-k)を高々1サイクル以内の時間差で出力することができる。その結果、出力に対する新たな並べ替えを行うための回路の追加を必要としない。

0104

また、出力データを出力する順序を指定可能とするために、追加すべき回路は、読み出しアドレス生成部43のみであり、回路規模としては非常に小さい。

0105

従って、後段の処理を含め、全体としての回路規模、及び消費電力の増大を抑制することができる。

0106

さらに、FFT装置10と比較して、第3のデータ並べ替え処理部13を省略することができる。その結果、回路規模、及び消費電力をさらに削減することができる。

0107

なお、本実施形態では、FFT処理を例として説明したが、IFFTにおいても同様である。すなわち、本実施形態の制御方法をIFFT処理装置に適用して、IFFT処理の後段の処理内容を考慮して処理結果の出力順序を最適化すれば、IFFT処理の後段の処理を高速化することができる。
(第4の実施形態)
次に、FFT装置30の出力の順序である任意データ組ビットリバース順序に対応して動作するIFFT装置について説明する。

0108

図11は、本発明の第4の実施形態に係るIFFT装置40の構成例を示すブロック図である。IFFT装置40は、図19に示されたFFTのデータフローと同様のデータフローで、2段階の基数8のバタフライ処理に分解された64ポイントIFFTを、パイプライン回路方式によって処理する。IFFT装置40は、FFT装置30によりフーリエ変換された周波数領域の信号X(k)(k=0,1,・・・,N-1)を入力し、X(k)をフーリエ逆変換により時間領域のデータy(n)(n=0,1,・・・ ,N-1)を生成し、出力する。ここで、NはIFFTブロックサイズを表す正整数である。

0109

図7において、IFFT装置40は、8データ並列で64ポイントIFFT処理を行う。IFFT装置40は、FFT装置30の出力と同様の、図10に示す任意データ組ビットリバース順序で入力X(k)を入力する。一方、IFFT装置40は、図2に示す逐次順序で出力y(n)を出力する。

0110

IFFT装置40は、第1のバタフライ演算処理部21、第1のデータ並べ替え処理部17、ひねり乗算処理部31、第2のバタフライ演算処理部22、第2のデータ並べ替え処理部15、書き込みアドレス生成部44を備える。IFFT装置40において、IFFT装置20と同一の構成には同一の符号を付加し、詳細な説明は省略する。IFFT装置40は、第1のバタフライ演算処理、第1のデータ並べ替え処理、ひねり乗算処理、第2のバタフライ演算処理、第2のデータ並べ替え処理を、パイプライン処理する。

0111

IFFT装置40は、IFFT装置20の構成から第1のデータ並べ替え処理部14を除いた構成をもつ。IFFT装置20における第1のデータ並べ替え処理部14が、書き込みアドレス53を参照して行っていた並べ替え処理は、IFFT装置40では、第2のデータ並べ替え処理部17が行う。すなわち、第2のデータ並べ替え処理部17は、書き込みアドレス57を入力して、IFFT処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。さらに、第2のデータ並べ替え処理部17は、上記の並べ替えに加えて、任意データ組逐次順序でデータを入力するための並べ替え処理を行う。

0112

具体的には、第2のデータ並べ替え処理部17は、第1のバタフライ演算処理部21が図4の任意データ組逐次順序で出力するデータを、第2のバタフライ演算処理部22に入力する順序である図3のビットリバース順序に並べ替える。

0113

第2のデータ並べ替え処理部17は、図8に示したデータ並べ替え処理部300と同様の構成で実現することができる。
(第4の実施形態の効果)
以上のように、本実施形態では、IFFT装置40は、入力順序設定58を用いて順序を指定することによって、任意の順序でデータを入力することができる。従って、FFT装置30の出力順序に対応して、入力に対する新たな並べ替え手段を必要としない。

0114

また、任意の順序で入力される入力データに対応するために、追加すべき回路は、書き込みアドレス生成部44のみであり、回路規模としては非常に小さい。

0115

従って、前段の処理を含め、全体としての回路規模、及び消費電力の増大を抑制することができる。

0116

さらに、IFFT装置20と比較して、第1のデータ並べ替え処理部14を省略することができる。その結果、回路規模、及び消費電力をさらに削減することができる。

0117

なお、本実施形態では、IFFT処理を例として説明したが、FFTにおいても同様である。すなわち、本実施形態の制御方法をFFT処理装置に適用して、FFT処理の前段の処理内容を考慮して入力信号の入力順序を最適化すれば、FFT処理を高速化することができる。

0118

以上の説明から明らかなように、本発明の高速フーリエ変換装置の特徴は、FFT/IFFTの変換前、又は変換後に、任意の順序へのデータの並べ替えを行うことができる点にある。それによって、データ並べ替え後の処理の高速化が可能となる。FFT/IFFTが、複数の段階の処理に分けて行われるときは、データの並べ替えは、ある段階の処理と次の段階の処理との間に行われてもよい。

0119

図12(a)、(b)、(c)は、本発明の高速フーリエ変換装置が備える必須の構成を示すブロック図である。

0120

高速フーリエ変換装置60は、フーリエ変換部61、データ並べ替え処理部62を備える。フーリエ変換部61は、高速フーリエ変換又は逆高速フーリエ変換を行って、複数の出力データを生成し、第1の順序で出力する。データ並べ替え処理部62は、第1の順序で出力された複数の第1の出力データを、出力順序設定に基づいて第2の順序に並べ替える。このように、高速フーリエ変換装置60は、フーリエ変換後に、データの並べ替えを行う。

0121

高速フーリエ変換装置70は、フーリエ変換部72、データ並べ替え処理部71を備える。データ並べ替え処理部71は、第3の順序で入力される複数の入力データを、入力順序設定に基づいて第4の順序に並べ替える。フーリエ変換部72は、第4の順序に並べ替えられた複数の入力データに対して、高速フーリエ変換又は逆高速フーリエ変換を行う。このように、高速フーリエ変換装置70は、フーリエ変換前に、データの並べ替えを行う。

0122

高速フーリエ変換装置80は、処理部81、82、データ並べ替え処理部831を備える。高速フーリエ変換装置80は、処理部81、82を用いて、2段階に分けて、高速フーリエ変換又は逆高速フーリエ変換を行う。処理部81は、複数の中間データを生成し、第5の順序で出力する。データ並べ替え処理部83は、第5の順序で入力される複数の中間データを、順序設定に基づいて第6の順序に並べ替える。処理部82は、第6の順序に並べ替えられた複数の中間データに対して、所定の処理を行い、高速フーリエ変換又は逆高速フーリエ変換結果の出力データを生成する。このように、高速フーリエ変換装置80では、データの並べ替えは、高速フーリエ変換又は逆高速フーリエ変換の、処理の途中の段階で行われる。
(第5の実施形態)
図13は、本発明の第1の実施形態に係るディジタルフィルタ回路400の構成を示すブロック図である。ディジタルフィルタ回路400は、FFT回路413、IFFT回路414、複素共役生成回路415、複素共役合成回路416、フィルタ回路421、フィルタ回路422、フィルタ係数生成回路441、を備える。

0123

ディジタルフィルタ回路400は、時間領域における複素数信号
x(n)=r(n)+js(n) ・・・(1)
を入力する。

0124

FFT回路413は、入力された複素数信号x(n)を、FFTにより周波数領域の複素数信号431
X(k)=A(k)+jB(k) ・・・(2)
に変換する。

0125

ここで、nは時間領域上の信号サンプル番号を示す0≦n≦N−1の整数、NはFFTの変換サンプル数を示す0<Nの整数、kは周波数領域上の周波数番号を示す0≦k≦N−1の整数である。

0126

また、FFT回路413は、X(k)から、
X(N−k)=A(N−k)+jB(N−k) ・・・(3)
を生成して出力する。

0127

複素共役生成回路415は、0≦k≦N−1の周波数番号kのそれぞれについて、FFT回路413が出力するX(N−k)を入力し、X(N−k)の複素共役
X*(N−k)=A(N−k)−jB(N−k) ・・・(4)
を生成する。

0128

複素共役生成回路415は、入力した複素数信号X(k)を複素数信号432として出力し、生成した複素数信号X*(N−k)を複素数信号433として出力する。

0129

次に、フィルタ係数生成回路441は、0≦k≦N−1の周波数番号kのそれぞれについて、入力した複素数係数V(k)、W(k)、及びH(k)から、複素数係数
C1(k)={V(k)+W(k)}×H(k) ・・・(5)
及び、複素数係数
C2(k)={V(k)−W(k)}×H(k) ・・・(6)
を生成する。

0130

ここで複素数係数V(k)、W(k)、及びH(k)は、ディジタルフィルタ回路400の上位回路(図示せず)から与えられる周波数領域での係数で、時間領域での実数演算によるフィルタ処理を行った場合の、実数フィルタ係数に対応する。V(k)、W(k)、及びH(k)の詳細に関しては後述する。

0131

フィルタ係数生成回路441は、生成した複素数係数C1(k)を複素数信号445として出力する。また、フィルタ係数生成回路441は、複素数信号C2(k)(式(6))から複素数信号C2(N−k)を生成し、複素数信号446として出力する。

0132

次に、フィルタ回路421は、複素共役生成回路415が複素数信号432に出力するX(k)(式(2))に対して、フィルタ係数生成回路441が複素数信号445に出力するC1(k)(式(5))を用いて、複素数乗算による複素数フィルタ処理を行う。具体的には、フィルタ回路421は、0≦k≦N−1の周波数番号kのそれぞれについて、複素数信号
X'(k)=X(k)×C1(k) ・・・(7)
を計算して、複素数信号434として出力する。

0133

同様に、フィルタ回路422は、複素共役生成回路415が複素数信号433に出力するX*(N−k)(式(4))に対して、フィルタ係数生成回路441が複素数信号446に出力するC2(N−k)(式(6))を用いて、複素数乗算による複素数フィルタ処理を行う。具体的には、フィルタ回路422は、0≦k≦N−1の周波数番号kのそれぞれについて、複素数信号
X*'(N−k)=X*(N−k)×C2(N−k) ・・・(8)
を計算して、複素数信号435として出力する。

0134

C1(k)、C2(k)は、それぞれ、実数部虚数部に分けて、
C1(k)=C1I(k)+jC1Q(k) ・・・(9)
C2(k)=C2I(k)+jC2Q(k) ・・・(10)
と書くことができる。

0135

次に、複素共役合成回路416は、フィルタ回路21が複素数信号434に出力するX'(k)(式(7))と、フィルタ回路422が複素数信号435に出力するX*'(N−k)(式(8))とを合成した複素数信号X"(k)を生成する。具体的には、複素共役合成回路416は、0≦k≦N−1の周波数番号kのそれぞれについて、
X"(k)=1/2×{X'(k)+X*'(N−k)} ・・・(11)
を計算して、複素数信号436として出力する。

0136

次に、IFFT回路414は、0≦k≦N−1の周波数番号kのそれぞれについて、複素共役合成回路416が複素数信号436に出力するX"(k)(式(11))に対して、IFFTにより時間領域の複素数信号x"(n)を生成して出力する。

0137

FFT回路413の実現方法として、本発明の第1の実施形態に係るFFT回路10を使用することができる。同様に、IFFT回路414の実現方法として、本発明の第2の実施形態に係るIFFT回路20を使用することができる。

0138

あるいは、FFT回路413の実現方法として、本発明の第3の実施形態に係るFFT回路20を使用することができる。同様に、IFFT回路414の実現方法として、本発明の第4の実施形態に係るIFFT回路40を使用することができる。

0139

図14は、複素共役生成回路415の構成の詳細を示すブロック図である。複素共役生成回路415は、データ記憶部452、453、データ選択部454、455を備える。

0140

複素共役生成回路415は、FFT回路413の出力に含まれるX(k)(=A(k)+jB(k)。式(2))を入力してそのまま出力する。さらに、複素共役生成回路415は、FFT回路413の出力に含まれる出力X(N−k)(=A(N−k)+jB(N−k)。式(3))を入力して、
X*(N−k)=A(N−k)−jB(N−k) ・・・(4)
を計算して出力する。

0141

X(k)、X*(N−k)は、それぞれ、実数部と虚数部に分けて、
X(k)=XI(k)+jXQ(k) ・・・(12)
X*(N−k)=X*I(N−k)+jX*Q(N−k) ・・・(13)
と書くことができる。

0142

図15は、フィルタ回路421の構成の詳細を示すブロック図である。フィルタ回路421は、複素共役生成回路415が複素信号線432に出力するX(k)(=XI(k)+jXQ(k)。式(12))と、複素数係数C1(k)(=C1I(k)+jC1Q(k)。式(9))を入力して、
X'(k)=XI'(k)+jXQ'(k)
=X(k)×C1(k) ・・・(14)
を計算して出力する。

0143

ここで、XI'(k)及びXQ'(k)は、それぞれX'(k)の実数部と虚数部であり、次式で与えられる。

0144

XI'(k)=XI(k)×C1I(k)−XQ(k)×C1Q(k) ・・・(15)
XQ'(k)=XI(k)×C1Q(k)+XQ(k)×C1I(k) ・・・(16)
図16は、フィルタ回路422の構成の詳細を示すブロック図である。フィルタ回路422は、複素共役生成回路415が複素信号線433に出力するX*(N−k)(=X*I(N−k)+jX*Q(N−k)。式(13))と複素数係数C2(k)(=C2I(k)+jC2Q(k)。式(10))を入力して、
X*'(N−k)=X*I'(N−k)+jX*Q'(N−k)
=X*(N−k)×C2(N−k) ・・・(17)
を計算して出力する。

0145

ここで、X*I'(N−k)及びX*Q'(N−k)は、それぞれX*'(N−k)の実数部と虚数部であり、次式で与えられる。

0146

X*I'(N−k)=X*I(N−k)×C2I(N−k)−X*Q(N−k)×C2Q(N−k)・・・(18)
X*Q'(N−k)=X*I(N−k)×C2Q(N−k)+X*Q(N−k)×C2I(N−k)・・・(19)
図17は、複素共役合成回路416の構成の詳細を示すブロック図である。複素共役合成回路416は、0≦k≦N−1の周波数番号kのそれぞれについて、フィルタ回路421が複素数信号434に出力するX'(k)(=XI'(k)+jXQ'(k)。式(14))と、フィルタ回路422が複素数信号435に出力するX*'(N−k)(=X*I'(N−k)+jX*Q'(N−k)。式(17))とを入力して、
X"(k)=XI"(k)+jXQ"(k)
=1/2{X'(k)+X*'(N−k)} ・・・(20)
を計算して出力する。

0147

ここで、XI"(k)及びXQ"(k)は、それぞれX"(k)の実数部と虚数部であり、次式で与えられる。

0148

XI"(k)=1/2{XI'(k)+X*I'(N−k)} ・・・(21)
XQ"(k)=1/2{XQ'(k)+X*Q'(N−k)} ・・・(22)
ここで、XI'(k)、XQ'(k)、X*I'(N−k)、X*Q'(N−k)は、それぞれ式(15)、(16)、(18)、(19)の通りである。

0149

フィルタ係数生成回路441は、フィルタ回路421、422で用いられる複素数係数C1(k)、C2(k)を生成する。図18は、フィルタ係数生成回路441の構成の詳細を示すブロック図である。フィルタ係数生成回路441は、0≦k≦N−1の周波数番号kのそれぞれについて、上位回路(図示せず)から入力された複素数係数V(k)、W(k)から、V(k)+W(k)及びV(k)−W(k)を計算する。

0150

ここで、
V(k)+W(k)=VI(k)+WI(k)+jVQ(k)+jWQ(k) ・・・(23)
V(k)−W(k)=VI(k)−WI(k)+jVQ(k)−jWQ(k) ・・・(24)
である。VI(k)及びVQ(k)は、それぞれV(k)の実数部と虚数部であり、WI(k)及びWQ(k)は、それぞれW(k)の実数部と虚数部である。

0151

また、H(k)も実数部と虚数部とに分けて、
H(k)=HI(k)+jHQ(k) ・・・(25)
と書くことができる。

0152

次に、フィルタ係数生成回路441は、以下の式で定義された複素数係数C1(k)及びC2(k)を計算して出力する。

0153

C1(k)=C1I(k)+jC1Q(k)
={V(k)+W(k)}×H(k) ・・・(26)
C2(k)=C2I(k)+jC2Q(k)
={V(k)−W(k)}×H(k) ・・・(27)
ここで、C1I(k)、C1Q(k)は、それぞれC1(k)の実数部と虚数部であり、C2I(k)、C2Q(k)は、それぞれC2(k)の実数部と虚数部である。

0154

式(26)に式(23)、(25)を代入して、
C1(k)={VI(k)+WI(k)+jVQ(k)+jWQ(k)}×{HI(k)+jHQ(k)}・・・(28)
である。

0155

従って、
C1I(k)={VI(k)+WI(k)}×HI(k)−{VQ(k)+WQ(k)}×HQ(k)・・・(29)
C1Q(k)={VQ(k)+WQ(k)}×HI(k)+{VI(k)+WI(k)}×HQ(k)・・・(30)
である。

0156

同様に、式(27)に式(24)、(25)を代入して、
C2(k)=C2I(k)+jC2Q(k)
={V(k)−W(k)}×H(k)
={VI(k)−WI(k)+jVQ(k)−jWQ(k)}×{HI(k)+jHQ(k)}・・・(31)
である。

0157

従って、
C2I(k)={VI(k)−WI(k)}×HI(k)−{VQ(k)−WQ(k)}×HQ(k)・・・(32)
C2Q(k)={VQ(k)−WQ(k)}×HI(k)+{VI(k)−WI(k)}×HQ(k)・・・(33)
である。

0158

以上のように、ディジタルフィルタ回路400は、時間領域の入力信号をFFT変換して周波数領域の複素数信号を生成する。そして、ディジタルフィルタ回路400は、周波数領域の複素数信号の実数部、虚数部のそれぞれを、V(k)、W(k)、H(k)から生成された2種類の係数を用いて独立にフィルタ処理し、その結果をIFFTによって時間領域の信号に変換する。このように、ディジタルフィルタ回路400では、FFTとIFFTは、それぞれ、時間領域の入力信号に対して1回のみ実行される。

0159

フィルタ処理に用いられる2種類の係数が、FFT及びIFFTの回数の最小化を可能にする。以下に、V(k)、W(k)、H(k)の物理的な意味と、これらから生成された係数C1(k)及びC2(k)を用いたフィルタ処理により、時間領域での所望のフィルタ処理と同等の、周波数領域でのフィルタ処理が可能となる原理を説明する。

0160

本実施形態では、入力する時間領域の複素数信号x(n)(=r(n)+js(n)。式(1))を複素FFTした周波数領域の複素数信号
X(k)=R(k)+jS(k) ・・・(34)
から、複素共役生成回路15がX*(N−k)を生成する。

0161

ここで、R(k)は、時間領域における実数の実数部信号r(n)が実数FFTにより変換された周波数領域の複素数信号、S(k)は時間領域における実数の虚数部信号s(n)が実数FFTにより変換された周波数領域の複素数信号である。このとき、複素共役の対称性から次式が成立する。

0162

X*(N−k)=R(k)−jS(k) ・・・(35)
ここで、X*(N−k)は、X(N−k)の複素共役である。

0163

式(14)、(34)、(26)から、
X'(k)=X(k)×C1(k)
={R(k)+jS(k)}×{V(k)+W(k)}×H(k)
=R(k)V(k)H(k)+R(k)W(k)H(k)+jS(k)V(k)H(k)+jS(k)W(k)H(k)・・・(36)
となる。

0164

また、式(17)、(35)、(27)から、
X*'(N−k)=X*(N−k)×C2(N−k)
={R(k)−jS(k)}×{V(k)−W(k)}×H(k)
=R(k)V(k)H(k)−R(k)W(k)H(k)−jS(k)V(k)H(k)+jS(k)W(k)H(k) ・・・(37)
となる。

0165

式(20)に、式(36)、(37)を代入すると、
X"(k)=1/2×{X'(k)+X*'(N−k)}
=1/2×{2×R(k)V(k)H(k)+2×jS(k)W(k)H(k)}
=R(k)V(k)H(k)+jS(k)W(k)H(k)
={R(k)V(k)+jS(k)W(k)}×H(k) ・・・(38)
となる。

0166

式(38)は、IFFT前の信号X"(k)を、フィルタ係数V(k)、W(k)及びH(k)と、FFT後の信号X(k)におけるR(k)及びS(k)を用いて表したものである。R(k)は、時間領域における実数の実数部信号r(n)が実数FFTにより変換された周波数領域の複素数信号である。S(k)は、時間領域における実数の虚数部信号s(n)が実数FFTにより変換された周波数領域の複素数信号である。つまり、式(38)は、FFT後の信号X(k)に対して施されるフィルタ処理の内容を表す。式(38)から、ディジタルフィルタ回路400は、複素数信号x(n)=r(n)+js(n)が実数FFTにより変換されて生成された、周波数領域の複素数信号X(k)(=R(k)+jS(k)。式(34))に対して、以下の3つのフィルタ処理と同等の処理を行うことがわかる。
1)R(k)に対する係数V(k)によるフィルタ処理
まず、ディジタルフィルタ回路400は、時間領域における実数部信号r(n)が実数FFTにより変換された周波数領域の複素数信号R(k)に対して、フィルタ係数V(k)によるフィルタ処理を行う。従って、V(k)には、実数部信号r(n)に対して時間領域で実数演算によるフィルタ処理を行った場合の、実数フィルタ係数に対応する、周波数領域での複素数フィルタ係数が割り当てられる。
2)S(k)に対する係数W(k)によるフィルタ処理
同様に、ディジタルフィルタ回路400は、時間領域における虚数部信号s(n)が実数FFTにより変換された周波数領域の複素数信号S(k)に対して、フィルタ係数W(k)によるフィルタ処理を行う。従って、W(k)には、虚数部信号s(n)に対して時間領域で実数演算によるフィルタ処理を行った場合の、実数フィルタ係数に対応する、周波数領域での複素数フィルタ係数が割り当てられる。
3)1)、2)のフィルタ処理結果に対する係数H(k)によるフィルタ処理
次に、ディジタルフィルタ回路400は、それぞれ独立に処理された上記の2つのフィルタ処理後の、R(k)V(k)及びS(k)W(k)からなる複素数信号R(k)V(k)+jS(k)W(k)に対して、フィルタ係数H(k)によるフィルタ処理を行う。

0167

R(k)V(k)+jS(k)W(k)は、時間領域における実数部信号r(n)及び虚数部信号s(n)のそれぞれに独立にフィルタ処理した2つの信号からなる時間領域の信号に対応する、周波数領域の複素数信号である。実数部信号r(n)及び虚数部信号s(n)をそれぞれに独立にフィルタ処理した信号とは、図15、16における、X'(k)、X*'(N-k)に相当する。そして、r'(n)、s'(n)からなる時間領域の信号とは、図13のx"(n)に相当する。このように、R(k)V(k)+jS(k)W(k)は、時間領域において実数部及び虚数部のそれぞれに独立にフィルタ処理した時間領域の信号に対応する、周波数領域の信号である。

0168

従って、時間領域における複素数信号に対する複素数演算によるフィルタ処理に相当する処理を、周波数領域の信号R(k)V(k)+jS(k)W(k)に対して行うには、次のような係数を用いればよい。すなわち、H(k)には、複素数信号x(n)に対して時間領域で複素数演算によるフィルタ処理を行った場合の、複素数フィルタ係数に対応する、周波数領域での複素数フィルタ係数が割り当てればよい。

0169

以上のように、本実施形態では、外部から3種類の係数が設定される。すなわち、複素数信号x(n)の実数部及び虚数部のそれぞれに対する時間領域でのフィルタ係数に対応する周波数領域のフィルタ係数V(k)、W(k)と、x(n)に対する時間領域でのフィルタ係数に対応する周波数領域の係数H(k)が設定される。以上の3つの係数から求めた2つの係数を用いたフィルタ処理を行うことにより、フィルタ処理の前のFFT及びフィルタ処理後のIFFTをそれぞれ1回のみとすることができる。
(第5の実施形態の効果)
以上のように、本実施形態によれば、複素数信号の実数部及び虚数部のそれぞれに対する時間領域でのフィルタ係数に対応する、2種類の周波数領域のフィルタ係数と、複素信号に対する時間領域でのフィルタ係数に対応する周波数領域の係数を用いたフィルタ処理が行われる。すなわち、時間領域における複素数信号の実数部及び虚数部のそれぞれに対する実数演算による独立したフィルタ処理と、時間領域における複素数信号に対する複素数演算によるフィルタ処理と、に対応する周波数領域におけるフィルタ処理が行われる。従って、フィルタ処理前のFFTを行うFFT回路及びフィルタ処理後のIFFTを行うIFFT回路を、それぞれ1個のみを用いて、所望のフィルタ処理を実現することができる。その結果、フィルタ処理を行うための回路規模や消費電力の低減を図ることができるという効果がある。

0170

さらに、FFT回路、IFFT回路の実現に、それぞれ、本発明の第1の実施形態に係るFFT回路10、本発明の第2の実施形態に係るIFFT回路20を使用することができる。あるいは、FFT回路、IFFT回路の実現に、それぞれ、本発明の第3の実施形態に係るFFT回路30、及び本発明の第4の実施形態に係るIFFT回路40を使用することができる。前述のように、本発明の実施形態に係るFFT回路、IFFT回路は、それぞれ、FFT処理、IFFT処理を行うための回路規模や消費電力の削減することができる。従って、本発明の実施形態に係るFFT回路又はIFFT回路をフィルタ処理に用いることによって、フィルタ処理を行うための回路規模や消費電力の削減することができるという効果がある。

0171

第1から第5の実施形態では、FFT、IFFT、共役複素数の生成及び合成、フィルタ係数の算出、フィルタ処理等、各処理は、すべて個別の回路等の構成要素によって処理されることが想定されている。しかし、各実施形態の処理は、所定の装置が備えるコンピュータ、例えば、DSP(Digital Signal Processor)等を用いたソフトウェアによって実行されてもよい。すなわち、各処理を行うコンピュータプログラムは、DSP(図示なし)によって読み込まれ、実行される。

0172

例えば、データの並べ替え処理を、プログラムを用いて行ってもよい。すなわち、DSPとメモリを用いて、メモリへのデータの書き込み及びメモリからのデータの読み出しをプログラムによって制御することによって、データの並べ替え処理を行ってもよい。

0173

さらに、第1、第3の実施形態ではFFT処理を、第2、第4の実施形態ではIFFT処理を、プログラムを用いて行ってもよい。第5の実施形態では、V(k)、W(k)、及びH(k)から、C1(k)、C2(k)を求める処理、FFT処理、X(N−k)の共役複素数X*(N−k)を求める処理、フィルタ処理、IFFT処理を、プログラムを用いて行ってもよい。

0174

以上のように、プログラムを用いて各処理を行っても、上述の実施形態の処理と同内容の処理を行うことができる。 なお、本プログラムは、ROM(Read Only Memory)、RAM(Random Access Memory)、フラッシュメモリ等の半導体記憶装置光ディスク磁気ディスク光磁気ディスク等、非一時的な媒体に格納されてもよい。

0175

なお、以上の実施形態は各々他の実施形態と組み合わせることができる。

0176

上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
(付記1)
高速フーリエ変換又は逆高速フーリエ変換を行って、複数の第1の出力データを生成し、第1の順序で出力する第1の変換部と、前記第1の順序で出力された前記複数の第1の出力データを、出力順序設定に基づいて第2の順序に並べ替える第1のデータ並べ替え処理部と、を備える高速フーリエ変換装置。
(付記2)
前記第1の変換処理部は、バタフライ演算処理を行い、前記第1の順序で前記複数の第1の出力データを出力するバタフライ演算処理部を含み、前記第1のデータ並べ替え処理部は、前記バタフライ演算処理後の前記複数の第1のデータを前記第2の順序に並べ替えることを特徴とする付記1に記載の高速フーリエ変換装置。
(付記3)
前記第1のデータ並べ替え処理部は、前記複数の第1の出力データを記憶する第1の記憶部と、前記出力順序設定に基づいて、前記第1の記憶部からの前記複数の第1の出力データの読み出しアドレスを生成する読み出しアドレス生成部を備え、前記複数の第1の出力データを前記第1の順序で記憶し、前記第2の順序で読み出すことを特徴とする付記1又は2に記載の高速フーリエ変換装置。
(付記4)
前記複数の第1の出力データをX(k)(kは0≦k≦N−1の整数、NはN>0の高速フーリエ変換又は逆高速フーリエのポイント数)とするとき、前記第1のデータ並べ替え処理部は、任意のkに対してX(k)とX(N-k)とを高々1サイクル以内の時間差で出力することを特徴とする付記1乃至3のいずれかに記載の高速フーリエ変換装置。
(付記5)
第3の順序で入力される複数の第2の入力データを、入力順序設定に基づいて第4の順序に並べ替える第2のデータ並べ替え処理部と、前記第4の順序に並べ替えられた前記複数の第2の入力データに対して、高速フーリエ変換又は逆高速フーリエ変換を行う第2の変換部と、を備える高速フーリエ変換装置。

0177

(付記6)
前記第2の変換処理部は、バタフライ演算処理を行うバタフライ演算処理部を含み、前記第2のデータ並べ替え処理部は、前記第4の順序で前記バタフライ演算処理部に前記複数の第2のデータを入力することを特徴とする付記5に記載の高速フーリエ変換装置。

0178

(付記7)
前記第2のデータ並べ替え処理部は、前記複数の第2の入力データを記憶する第2の記憶部と、前記入力順序設定に基づいて、前記第2の記憶部への前記複数の第2のデータの書き込みアドレスを生成する書き込みアドレス生成部を備え、前記複数の第2の出力データを前記第3の順序で記憶し、前記第4の順序で読み出すことを特徴とする付記5又は6に記載の高速フーリエ変換装置。

0179

(付記8)
前記複数の第1の入力データをX(k)(kは0≦k≦N−1の整数、NはN>0の高速フーリエ変換又は逆高速フーリエのポイント数)とするとき、前記第2のデータ並べ替え処理部は、任意のkに対してX(k)とX(N-k)とを高々1サイクル以内の時間差で前記バタフライ演算処理部に入力することを特徴とする付記5乃至7のいずれかに記載の高速フーリエ変換装置。
(付記9)
付記1又は5に記載の高速フーリエ変換装置を含むディジタルフィルタ装置
(付記10)
付記1に記載の高速フーリエ変換装置と、
前記高速フーリエ変換装置により、入力された時間領域の複素数である前記複数の第1の入力データがフーリエ変換され生成された周波数領域の複数の第1の複素数データを構成する、すべての複素数のそれぞれの共役複素数を含む第2の複素数データを生成する複素共役生成部と、入力された複素数の第1、第2及び第3の入力フィルタ係数から、複素数の第1及び第2の周波数領域フィルタ係数を生成するフィルタ係数生成部と、前記第1の複素数データに対して前記第1の周波数領域フィルタ係数によりフィルタ処理を行い、第3の複素数データを出力する第1のフィルタ部と、前記第2の複素数データに対して前記第2の周波数領域フィルタ係数によりフィルタ処理を行い、第4の複素数データを出力する第2のフィルタ部と、前記第3の複素数信号と、前記第4の複素数信号とを合成して第5の複素数データを生成する複素共役合成部と、を備えることを特徴とするディジタルフィルタ装置。
(付記11)
付記5に記載の高速フーリエ変換装置を備え、前記第2のデータ並べ替え処理部は、前記第3の順序で入力される前記第5の複素数データを、前記入力順序設定に基づいて前記第4の順序に並べ替え、前記第2の変換部は、前記第4の順序に並べ替えられた前記第5の複素数データに対して逆フーリエ変換を行って時間領域の信号に変換することを特徴とする付記10記載のディジタルフィルタ装置。

0180

(付記12)
前記フーリエ変換及び前記逆フーリエ変換の変換サンプル数をN(NはN>0の整数)とするとき、前記複素共役生成部は、前記第1の複素数データに含まれる周波数番号(N−k)の複素数の共役複素数を前記第2の複素数データとして生成することを特徴とする付記10又は11記載のディジタルフィルタ装置。

0181

(付記13)
前記複素共役合成部は、0≦k≦N−1の範囲の周波数番号kのそれぞれについて、前記第3の複素数データに含まれる周波数番号kの第1の複素数と、前記第4の複素数データに含まれる周波数番号(N−k)の第2の複素数とを、複素加算して前記第5の複素数信号を生成する、ことを特徴とする付記12に記載のディジタルフィルタ装置。

0182

(付記14)
前記フィルタ係数生成部は、前記第1の周波数領域フィルタ係数を、前記第1の入力フィルタ係数に前記第2の入力フィルタ係数を複素加算したのち、さらに前記第3の入力フィルタ係数を複素乗算して生成し、前記第2の周波数領域フィルタ係数を、前記第1の入力フィルタ係数から前記第2の入力フィルタ係数を複素減算したのち、さらに前記第3の入力フィルタ係数を複素乗算して生成する、
ことを特徴とする付記10乃至13のいずれかに記載のディジタルフィルタ装置。

0183

(付記15)
前記第1の周波数領域フィルタ係数は、前記第1の入力データに対する時間領域でのフィルタ処理である時間領域フィルタ処理における、前記複素入力信号の実数部に対するフィルタ係数に対応する、周波数領域での複素数フィルタ係数であり、前記第2の周波数領域フィルタ係数は、前記時間領域フィルタ処理における、前記第1の入力データの虚数部に対するフィルタ係数に対応する、周波数領域での複素数フィルタ係数であり、前記第3の周波数領域フィルタ係数は、前記時間領域フィルタ処理における、前記第1の入力データに対するフィルタ係数に対応する、周波数領域での複素数フィルタ係数であることを特徴とする付記10乃至14のいずれかに記載のディジタルフィルタ装置。
(付記16)
高速フーリエ変換若しくは逆高速フーリエ変換により生成された複数の出力データの、出力順序設定に基づく並べ替え、又は前記高速フーリエ変換若しくは前記逆高速フーリエ変換の複数の入力データの、入力順序設定に基づく並べ替えを行う高速フーリエ変換方法。
(付記17)
高速フーリエ変換装置が備えるコンピュータを、高速フーリエ変換又は逆高速フーリエ変換を行う手段、及び前記高速フーリエ変換若しくは前記逆高速フーリエ変換により生成された複数の出力データの、出力順序設定に基づいて並べ替える並べ替え手段、又は前記高速フーリエ変換若しくは前記逆高速フーリエ変換の複数の入力データの、入力順序設定に基づいて並べ替える並べ替え手段として機能させるための高速フーリエ変換プログラムを格納した非一時的な記憶媒体。

0184

以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

0185

この出願は、2013年1月23日に出願された日本出願特願2013−010183を基礎とする優先権を主張し、その開示の全てをここに取り込む。

0186

10、30FFT装置
20、40IFFT装置
11、12、13、14、15、16、17 データ並べ替え処理部
21、22バタフライ演算処理部
31ひねり乗算処理部
41、43読み出しアドレス生成部
42、44書き込みアドレス生成部
51、55 読み出しアドレス
52、56出力順序設定
53、57 書き込みアドレス
54、58入力順序設定
60、70、80高速フーリエ変換装置
61、72フーリエ変換部
62、71、83 データ並べ替え処理部
81、82 処理部
100、200、300 データ並べ替え処理部
101a〜101hデータ記憶位置
102a〜102hデータ読み出し位置
201a〜201h データ記憶位置
301a〜301h データ記憶位置
400ディジタルフィルタ回路
413FFT回路
414IFFT回路
415複素共役生成回路
416 複素共役合成回路
421フィルタ回路
422 フィルタ回路
431〜436複素数信号
441フィルタ係数生成回路
445、446 複素数信号
500データフロー
501 データ並べ替え処理
502、503 バタフライ演算処理
504 ひねり演算処理
505部分データフロー
600 FFT装置
601 FFT部
602 データ並べ替え処理部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 新妻弘崇の「 遅延メモリ行列を用いたotsu-gram」が 公開されました。( 2021/08/19)

    【課題】自然言語処理などで時系列データの特徴量として良く利用されるn-gramにおいてnを職人芸で調節しないといけない問題を解決し、自動的に適切な特徴が選択されるotsu-gramを提供する。【解決手... 詳細

  • 富士通株式会社の「 計算プログラム、計算方法及び計算装置」が 公開されました。( 2021/08/19)

    【課題】物体検知技術を利用した異常判定の精度を向上させること。【解決手段】計算装置は、対象物を撮影した動画データに含まれる複数フレーム画像それぞれについて、複数種類の特徴量それぞれの検出結果と複数フレ... 詳細

  • 中科寒武紀科技股▲分▼有限公司の「 データ処理装置及び関連製品」が 公開されました。( 2021/08/19)

    【課題】人工ニューラルネットワーク演算に関連した計算命令を提供するデータ処理装置及び関連製品を提供する。【解決手段】データ処理装置は、制御ユニット11aと実行ユニット12aとを備える。制御ユニット11... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ