(57)【要約】【課題】フーリエ変換の処理時間を短くできるようにするとともに、その処理の際に使用する中間バッファメモリの容量を小さくできるようにする。【解決手段】横方向に周期ｎ1 、縦方向に周期ｎ2 の２次元状に配置された周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号に対して縦方向に対する周期ｎ2 のフーリエ変換をｎ1 回行うｎ2 長フーリエ変換手段２と、上記ｎ2 長フーリエ変換手段２による変換結果に対して回転演算を施す回転演算手段３と、上記回転演算手段３による演算結果に対して横方向に対する周期ｎ1 のフーリエ変換をｎ2回行うｎ1 長フーリエ変換手段５とを設け、周期Ｎの時間成分の信号の周波数解析を、上記周期Ｎよりも小さな周期ｎ1 ，ｎ2 のフーリエ変換の組み合わせによって行うようにすることにより、従来のＤＦＴよりも演算量を少なくすることができるようにする。【選択図】図１
2006164308.tif 000002
【特許請求の範囲】
【請求項１】
横方向に周期ｎ1 、縦方向に周期ｎ2 の２次元状に配置された周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号に対して、縦方向に対する周期ｎ2のフーリエ変換をｎ1 回行うｎ2 長フーリエ変換手段と、
上記ｎ2 長フーリエ変換手段による変換結果を一時記憶するための中間バッファメモリと、
上記中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、
上記回転演算手段による演算結果に対して、横方向に対する周期ｎ1 のフーリエ変換をｎ2 回行うｎ1 長フーリエ変換手段とを具備することを特徴とするフーリエ変換装置。
【請求項２】
周期Ｎの時間成分の信号を周波数解析することにより周波数成分の信号に変換するためのＮ長フーリエ変換装置において、
上記周期Ｎの時間成分の信号を横方向に周期ｎ1 、縦方向に周期ｎ2 （Ｎ＝ｎ1 ×ｎ2 ）の２次元状に配置する並べ替え手段と、
上記並べ替え手段により配置された２次元状の時間成分の信号に対して、縦方向に対する周期ｎ2 のフーリエ変換をｎ1 回行うｎ2 長フーリエ変換手段と、
上記ｎ2 長フーリエ変換手段による変換結果を一時記憶するための中間バッファメモリと、上記中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、
上記回転演算手段による演算結果に対して、横方向に対する周期ｎ1 のフーリエ変換をｎ2 回行うｎ1 長フーリエ変換手段とを具備することを特徴とするフーリエ変換装置。
【請求項３】
上記ｎ1 長フーリエ変換手段による変換結果を１次元状のデータに再配列する第２の並べ替え手段を更に具備することを特徴とする請求項１または２に記載のフーリエ変換装置。
【請求項４】
上記ｎ2 長フーリエ変換手段を複数個設け、上記ｎ1 回のｎ2 長フーリエ変換処理を上記複数個のｎ2 長フーリエ変換手段を用いて並列に行うようにしたことを特徴とする請求項１〜３の何れか１項に記載のフーリエ変換装置。
【請求項５】
上記ｎ1 長フーリエ変換手段を複数個設け、上記ｎ2 回のｎ1 長フーリエ変換処理を上記複数個のｎ1 長フーリエ変換手段を用いて並列に行うようにしたことを特徴とする請求項１〜３の何れか１項に記載のフーリエ変換装置。
【請求項６】
請求項１に記載のフーリエ変換装置を２個と、上記２個のフーリエ変換装置の間に直列に設けられる回転演算装置とを組み合わせてＮ2 長フーリエ変換装置を構成し、さらに、上記Ｎ2 長フーリエ変換装置と請求項１に記載のフーリエ変換装置とそれらの間に直列に設けられる回転演算装置とを組み合わせてＮ3 長フーリエ変換装置を構成するというように、請求項１に記載のフーリエ変換装置を複数個用いてそれらを上記回転演算装置を介してツリー構造となるように接続したことを特徴とするフーリエ変換装置。
【請求項７】
上記中間バッファメモリを高速ページモードを持つメモリを用いて構成したフーリエ変換装置であって、上記高速ページモードを持つメモリ上において所定ワード分の中間バッファメモリを縦横のブロック状に順次配置するようにしたことを特徴とする請求項１〜６の何れか１項に記載のフーリエ変換装置。
【請求項８】
上記ｎ2 長フーリエ変換手段と上記ｎ1 長フーリエ変換手段とを並列に動作させるようにしたフーリエ変換装置において、上記ｎ2 長フーリエ変換手段によりフーリエ変換されたデータを上記中間バッファメモリに記憶する際に、最初にｎ1 回のフーリエ変換が完了するまでは、上記ｎ1 長フーリエ変換手段で使用するために読み出されて空きにされた横方向の領域に上記データを書き込み、次にｎ1 回のフーリエ変換が完了するまでは、同様にして空にされた縦方向の領域に上記データを書き込むというように、データの書き込み方向を縦と横とで交互に変換するようにするとともに、上記ｎ1 長フーリエ変換手段において上記中間バッファメモリに記憶されたデータを使用する際に、最初にｎ2 回のフーリエ変換が完了するまでは横方向に上記データを読み出し、次にｎ2 回のフーリエ変換が完了するまでは縦方向に上記データを読み出すというようにデータの読み出し方向を縦と横とで交互に変換するようにするアドレッシング手段を設けたことを特徴とする請求項１〜６の何れか１項に記載のフーリエ変換装置。
【請求項９】
上記ｎ2 長フーリエ変換手段と上記ｎ1 長フーリエ変換手段とをそれぞれ複数個ずつ設け、上記ｎ1 回のｎ2 長フーリエ変換処理を上記複数個のｎ2 長フーリエ変換手段を用いて並列に行うとともに、上記ｎ2 回のｎ1長フーリエ変換処理を上記複数個のｎ1 長フーリエ変換手段を用いて並列に行うようにしたフーリエ変換装置において、上記中間バッファメモリを上記複数個のｎ2 長フーリエ変換手段および上記複数個のｎ1 長フーリエ変換手段と同じ数だけ設けるとともに、上記複数個のｎ2 長フーリエ変換手段により同時に求められた複数個のデータを上記複数個の中間バッファメモリに１個ずつ振り分けて記憶するようにするデータ振り分け手段を設けたことを特徴とする請求項１〜３の何れか１項に記載のフーリエ変換装置。
【請求項１０】
上記データ振り分け手段は、同じｎ2 長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないように順次得られるデータを振り分けて記憶するようにすることを特徴とする請求項９に記載のフーリエ変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フーリエ変換装置に関するものである。
【背景技術】
【０００２】
従来、時間成分の信号を周波数成分の信号に変換するための手法の１つに、ＤＦＴ（離散的フーリエ変換）と呼ばれる手法がある。Ｎ点の信号（周期がＮであることを示す）を周波数変換するためのＤＦＴの一般式は、時間成分の信号値をＳi 、周波数成分の信号値をＳk とすると、次の（式１）のように表せる。
【０００３】
【数１】
2006164308.tif 000003
【０００４】
この（式１）の演算を行うためには、乗算を４Ｎ2 回、加減算を２Ｎ2 ＋２Ｎ（Ｎ−１）回行う必要がある。すなわち、（式１）から分かるように、ＤＦＴは複素演算を行うものであるから、実際には次の（式２）で示される回転演算を引数ｋ，ｉの各値について行っている。
【０００５】
【数２】
2006164308.tif 000004
【０００６】
（式２）において、周波数成分の信号値Ｓk [real]（実部）、Ｓk [imag]（虚部）を求めるためには、時間成分の信号値Ｓi [real]と cosθ、信号値Ｓi [real]と sinθ、信号値Ｓi [imag]と sinθ、信号値Ｓi [imag]と cosθとの乗算をそれぞれｉについてＮ回、それを更にｋについてＮ回、２重のループで計算するから、全部で４Ｎ2 回の乗算が必要になる。
【０００７】
さらに、上述の乗算により得られる信号値Ｓi [real] cosθと信号値Ｓi [imag] sinθとの減算、信号値Ｓi [real] sinθと信号値Ｓi [imag] cosθとの加算をそれぞれｉについてＮ回、それを更にｋについてＮ回、２重のループで計算するから、全部で２Ｎ2 ＋２Ｎ（Ｎ−１）回の加減算が必要になる。上述のようなフーリエ変換を行う装置の従来例は、例えば、特許文献１、２によって提案されている。
【０００８】
【特許文献１】特開平０７−００６１６０号公報
【特許文献２】特開平０２−１０１５７４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
以上のように、従来のＤＦＴでは、数多くの乗算および加減算を行う必要があった。このため、処理に膨大な時間がかかってしまうという問題があった。そこで、従来、上記ＤＦＴの処理時間をできるだけ短くすることができるようにするために、ＦＦＴ（高速フーリエ変換）と呼ばれる手法が開発され、デジタル信号処理の分野で多く用いられてきた。
【００１０】
このＦＦＴは、バタフライ演算と呼ばれる基本演算を数段階に渡って繰り返して行うことにより、ＤＦＴの演算量を削減できるようにしたものである。つまり、ＦＦＴにおいて周期Ｎのフーリエ変換を実施する場合には、上記周期Ｎを所定の基数ごとに数段階に分けて、各基数のバタフライ演算をそれぞれ行うことで周波数解析を行っていた。
【００１１】
このＦＦＴでは、数段階のバタフライ演算をパイプライン処理で並列に行うことが可能である。その場合には、数段階に渡って演算した結果をそれぞれ一時記憶しておくための中間バッファメモリが必要になる。しかしながら、従来のＦＦＴでは、各中間バッファメモリの全メモリ容量が非常に大きくなってしまうという問題があった。
【００１２】
すなわち、ＦＦＴを構成する各バタフライ演算の性質上、その基数は比較的小さいものしか選択することができないため、バタフライ演算の段数が多くなってしまう。そのため、各バタフライ演算の結果を一時記憶しておくための中間バッファメモリの数が多くなるとともに、個々の中間バッファメモリの容量も大きくなってしまい、その結果、全メモリ容量が非常に大きくなってしまっていた。
【００１３】
本発明は、このような問題を解決するために成されたものであり、デジタル信号処理においてフーリエ変換を行うための処理時間を短くすることができるようにするとともに、その処理の際に使用する中間バッファメモリの容量を小さくすることができるようにすることを目的とする。
【課題を解決するための手段】
【００１４】
本発明のフーリエ変換装置は、横方向に周期ｎ1 、縦方向に周期ｎ2 の２次元状に配置された周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号に対して、縦方向に対する周期ｎ2 のフーリエ変換をｎ1 回行うｎ2 長フーリエ変換手段と、上記ｎ2長フーリエ変換手段による変換結果を一時記憶するための中間バッファメモリと、上記中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、上記回転演算手段による演算結果に対して、横方向に対する周期ｎ1 のフーリエ変換をｎ2 回行うｎ1 長フーリエ変換手段とを具備する。
【００１５】
本発明の他の特徴とするところは、周期Ｎの時間成分の信号を周波数解析することにより周波数成分の信号に変換するためのＮ長フーリエ変換装置において、上記周期Ｎの時間成分の信号を横方向に周期ｎ1 、縦方向に周期ｎ2 （Ｎ＝ｎ1×ｎ2 ）の２次元状に配置する並べ替え手段と、上記並べ替え手段により配置された２次元状の時間成分の信号に対して、縦方向に対する周期ｎ2 のフーリエ変換をｎ1 回行うｎ2 長フーリエ変換手段と、上記ｎ2 長フーリエ変換手段による変換結果を一時記憶するための中間バッファメモリと、上記中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、上記回転演算手段による演算結果に対して、横方向に対する周期ｎ1 のフーリエ変換をｎ2 回行うｎ1 長フーリエ変換手段とを具備する。
【００１６】
本発明のその他の特徴とするところは、上記ｎ1 長フーリエ変換手段による変換結果を１次元状のデータに再配列する第２の並べ替え手段を更に具備することを特徴とする。
【００１７】
本発明のその他の特徴とするところは、上記ｎ2 長フーリエ変換手段を複数個設け、上記ｎ1 回のｎ2 長フーリエ変換処理を上記複数個のｎ2 長フーリエ変換手段を用いて並列に行うようにしたことを特徴とする。
【００１８】
本発明のその他の特徴とするところは、上記ｎ1 長フーリエ変換手段を複数個設け、上記ｎ2 回のｎ1 長フーリエ変換処理を上記複数個のｎ1 長フーリエ変換手段を用いて並列に行うようにしたことを特徴とする。
【００１９】
本発明のその他の特徴とするところは、請求項１に記載のフーリエ変換装置を２個と、上記２個のフーリエ変換装置の間に直列に設けられる回転演算装置とを組み合わせてＮ2 長フーリエ変換装置を構成し、さらに、上記Ｎ2 長フーリエ変換装置と請求項１に記載のフーリエ変換装置とそれらの間に直列に設けられる回転演算装置とを組み合わせてＮ3 長フーリエ変換装置を構成するというように、請求項１に記載のフーリエ変換装置を複数個用いてそれらを上記回転演算装置を介してツリー構造となるように接続したことを特徴とする。
【００２０】
本発明のその他の特徴とするところは、上記中間バッファメモリを高速ページモードを持つメモリを用いて構成したフーリエ変換装置であって、上記高速ページモードを持つメモリ上において所定ワード分の中間バッファメモリを縦横のブロック状に順次配置するようにしたことを特徴とする。
【００２１】
本発明のその他の特徴とするところは、上記ｎ2 長フーリエ変換手段と上記ｎ1 長フーリエ変換手段とを並列に動作させるようにしたフーリエ変換装置において、上記ｎ2 長フーリエ変換手段によりフーリエ変換されたデータを上記中間バッファメモリに記憶する際に、最初にｎ1 回のフーリエ変換が完了するまでは、上記ｎ1 長フーリエ変換手段で使用するために読み出されて空きにされた横方向の領域に上記データを書き込み、次にｎ1 回のフーリエ変換が完了するまでは、同様にして空にされた縦方向の領域に上記データを書き込むというように、データの書き込み方向を縦と横とで交互に変換するようにするとともに、上記ｎ1 長フーリエ変換手段において上記中間バッファメモリに記憶されたデータを使用する際に、最初にｎ2 回のフーリエ変換が完了するまでは横方向に上記データを読み出し、次にｎ2 回のフーリエ変換が完了するまでは縦方向に上記データを読み出すというようにデータの読み出し方向を縦と横とで交互に変換するようにするアドレッシング手段を設けたことを特徴とする。
【００２２】
本発明のその他の特徴とするところは、上記ｎ2 長フーリエ変換手段と上記ｎ1 長フーリエ変換手段とをそれぞれ複数個ずつ設け、上記ｎ1 回のｎ2 長フーリエ変換処理を上記複数個のｎ2 長フーリエ変換手段を用いて並列に行うとともに、上記ｎ2 回のｎ1 長フーリエ変換処理を上記複数個のｎ1 長フーリエ変換手段を用いて並列に行うようにしたフーリエ変換装置において、上記中間バッファメモリを上記複数個のｎ2 長フーリエ変換手段および上記複数個のｎ1 長フーリエ変換手段と同じ数だけ設けるとともに、上記複数個のｎ2 長フーリエ変換手段により同時に求められた複数個のデータを上記複数個の中間バッファメモリに１個ずつ振り分けて記憶するようにするデータ振り分け手段を設けたことを特徴とする。
【００２３】
本発明のその他の特徴とするところは、上記データ振り分け手段は、同じｎ2長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないように順次得られるデータを振り分けて記憶するようにすることを特徴とする。
【００２４】
本発明は上記技術手段より成るので、本発明によれば、周期Ｎの時間成分の信号が周期Ｎのフーリエ変換によって一度に周波数変換されるのではなく、上記周期Ｎよりも小さな周期ｎ1 、ｎ2 のフーリエ変換の組み合わせによって周波数変換されることとなるので、フーリエ変換演算の性質上、上記小さな周期ｎ1 、ｎ2 のフーリエ変換でそれぞれ行われる演算量は、上記周期Ｎのフーリエ変換で行われる演算量に比べて格段に少ないものとなり、上記小さな周期ｎ1 、ｎ2 のフーリエ変換で行われる各演算量と回転演算で行われる演算量とを合計しても、上記周期Ｎのフーリエ変換によって一度に周波数変換を行うようになされた従来のＤＦＴの演算量よりも演算量が少なくなる。
【００２５】
また、本発明のその他の特徴によれば、複数のｎ2 長フーリエ変換処理を複数のｎ2長フーリエ変換手段を用いて同時に行うことができるようになり、また、請求項５に記載の発明によれば、複数のｎ1 長フーリエ変換処理を複数のｎ1 長フーリエ変換手段を用いて同時に行うことができるようになる。
【００２６】
また、本発明のその他の特徴によれば、請求項１〜３に記載の発明と同様に、小さな周期のフーリエ変換の組み合わせによって、より大きな周期のフーリエ変換を実施することが可能となるので、大きな周期のフーリエ変換を一度に行う場合の演算量に比べて演算量を格段に少なくすることが可能となる。しかも、上記小さな周期として任意の周期を選択することが可能であり、ツリー構造のルート付近では、ある程度大きな周期を選択することが可能であるので、各フーリエ変換の結果を一時記憶しておくための中間バッファメモリの数が従来のＦＦＴにおけるバタフライ演算を並列化動作させる場合に比べて少なくて済むとともに、個々の中間バッファメモリの容量もそれほど大きくしなくても済む。
【００２７】
また、本発明のその他の特徴によれば、ブロック状に配置された中間バッファメモリの縦方向に対してデータの読み書きを行うときには高速ページモードを使って高速に読み書きをすることが可能となるので、縦方向に対しても横方向に対してもメモリアクセスを高速に行うことが可能となる。これにより、ストライプ状に配置した場合に、縦横の一方の方向に対するデータの読み書きは速いが、他方の方向に対するデータの読み書きが非常に遅くなり、その結果、縦方向と横方向とのそれぞれに対してフーリエ変換を行う際に必要なデータを読み書きするのにかかる時間が長くなってしまうという不都合を防止することが可能となる。
【００２８】
また、本発明のその他の特徴によれば、ｎ1 長フーリエ変換手段で使用するためにデータが読み出されることによって順次空きにされた領域に、ｎ2 長フーリエ変換手段でフーリエ変換されたデータが順次記憶されていくこととなり、データの読み出しによって空にされた領域を有効に使って、１つの中間バッファメモリをｎ2 長フーリエ変換用とｎ1 長フーリエ変換用とで共用することが可能となる。
【００２９】
また、本発明のその他の特徴によれば、複数のフーリエ変換手段により同時に求められた複数のデータが複数のバッファメモリに同時に記憶されるようになる。
【００３０】
また、本発明のその他の特徴によれば、複数のｎ1 長フーリエ変換手段で同時に使用されるデータが複数のバッファメモリに１個ずつ分散して記憶されることとなるので、それらのデータの読み出しを同時に行うことが可能となる。
【発明の効果】
【００３１】
本発明は上述したように、本発明によれば、周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号の周波数解析を、上記周期Ｎよりも小さな周期である横方向に対する周期ｎ1 のフーリエ変換と縦方向に対する周期ｎ2 のフーリエ変換との組み合わせによって行うようにしたので、周期Ｎの信号を周期Ｎのフーリエ変換によって一度に周波数変換するようになされた従来のＤＦＴに比べて演算量を少なくすることができるようになり、これにより、フーリエ変換の処理速度を高速にすることができる。
【００３２】
また、本発明の他の特徴によれば、ｎ2 長フーリエ変換手段を複数個設け、ｎ1回のｎ2 長フーリエ変換処理を上記複数個のｎ2 長フーリエ変換手段を用いて並列に行うようにしたので、複数のｎ2 長フーリエ変換処理を同時に行うことができるようになる。
【００３３】
また、本発明のその他の特徴によれば、ｎ1 長フーリエ変換手段を複数個設け、ｎ2回のｎ1 長フーリエ変換処理を上記複数個のｎ1 長フーリエ変換手段を用いて並列に行うようにしたので、複数のｎ1 長フーリエ変換処理を同時に行うことができるようになる。したがって、それぞれのフーリエ変換処理を１回ずつ順番に行う場合に比べて処理時間を短くすることができるようになる。
【００３４】
また、本発明のその他の特徴によれば、小さな周期のフーリエ変換装置を複数個用いてそれらを回転演算装置を介してツリー構造となるように接続することによってより大きな周期のフーリエ変換装置を構成したので、請求項１〜３に記載の発明と同様に、大きな周期のフーリエ変換を一度に行う場合の演算量に比べて演算量を格段に少なくすることができ、処理を高速化することができる。しかも、上記小さな周期として任意の周期を選択することが可能であるので、各フーリエ変換の結果を一時記憶しておくための中間バッファメモリの数を従来のＦＦＴにおけるバタフライ演算を並列化動作させる場合に比べて少なくすることができるとともに、個々の中間バッファメモリの容量を小さくすることができるようになり、全体としての中間バッファメモリの容量を格段に小さくすることができる。
【００３５】
また、本発明のその他の特徴によれば、高速ページモードを持つメモリ上において所定ワード分の中間バッファメモリを縦横のブロック状に順次配置するようにして中間バッファメモリを構成したので、ブロック状に配置された中間バッファメモリの縦方向に対してデータの読み書きを行うときには高速ページモードを使って高速に読み書きをすることが可能となり、縦方向に対しても横方向に対してもメモリアクセスを高速に行うことができるようになる。したがって、演算量の削減によってフーリエ変換の処理速度を速くすることができるだけでなく、メモリアクセス時間の削減によっても処理速度を速くすることができ、より高速にフーリエ変換を行うことができるようになる。
【００３６】
また、本発明のその他の特徴によれば、ｎ2 長フーリエ変換手段によりフーリエ変換されたデータを中間バッファメモリに書き込む際、およびｎ1 長フーリエ変換手段において中間バッファメモリに記憶されたデータを読み出す際に、データの読み書きの方向を縦と横とで交互に変換するようにし、ｎ1 長フーリエ変換手段で使用するためにデータが読み出されることによって順次空きにされた領域に、ｎ2 長フーリエ変換手段でフーリエ変換されたデータを順次記憶していくようにしたので、データの読み出しによって空にされた領域を有効に使って、１つの中間バッファメモリをｎ2 長フーリエ変換用とｎ1 長フーリエ変換用とで共用するようにすることができ、１ページ分の中間バッファメモリを用意するだけでｎ2 長フーリエ変換処理とｎ1 長フーリエ変換処理とを並列に動作させることができるようになる。
【００３７】
また、本発明のその他の特徴によれば、複数個のｎ2 長フーリエ変換手段および複数個のｎ1 長フーリエ変換手段と同じ数だけ中間バッファメモリを設けるとともに、複数個のｎ2 長フーリエ変換手段により同時に求められる複数個のデータを上記複数個の中間バッファメモリに１個ずつ振り分けて記憶するように構成したので、複数のフーリエ変換手段により同時に求められた複数のデータを複数のバッファメモリに同時に記憶するようにすることができる。したがって、ｎ2 長フーリエ変換手段とｎ1 長フーリエ変換手段とをそれぞれ複数個ずつ設けて各処理を並列に行うようにしたにもかかわらずメモリアクセスを並列に行うことができないという不都合をなくすことができ、処理の並列動作性を高めることができる。
【００３８】
また、本発明のその他の特徴によれば、上記データの振り分けの際に、同じｎ2 長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにして順次得られるデータを振り分けるようにしたので、複数のｎ1 長フーリエ変換手段で同時に使用するデータを複数のバッファメモリに１個ずつ分散して記憶するようにすることができ、それらのデータの読み出しを同時に行うことができるようになる。したがって、処理の並列動作性を更に高めることができる。
【発明を実施するための最良の形態】
【００３９】
以下、本発明の一実施例を図面に基づいて説明する。時間成分の信号を周波数成分の信号に周期Ｎで変換するための処理、すなわちＮ点ＤＦＴの処理を、従来は図２（０）に示すようにＮ長フーリエ変換で一度に行っていた。これに対し、本実施例のフーリエ変換装置では、図２（ａ）〜（ｅ）に示すように第１〜第５のフェーズに分けて行っている。
【００４０】
すなわち、第１のフェーズでは、図２（ａ）に示すように、入力される１次元状のＮ個のデジタル信号を横ｎ1 個×縦ｎ2 個の２次元状の配置に並べ替える。第２のフェーズでは、図２（ｂ）に示すように、上記並べ替えた２次元状のデータ配置において、縦方向に対するｎ2 個のデータを用いてｎ2 長ＤＦＴ処理を横方向の数ｎ1 だけ行う。
【００４１】
次に、第３のフェーズでは、図２（ｃ）に示すように、上記ｎ2 長ＤＦＴ処理で得られた結果に対して回転演算を施す。第４のフェーズでは、図２（ｄ）に示すように、上記回転演算の結果に対して、横方向に対するｎ1 個のデータを用いてｎ1 長ＤＦＴ処理を縦方向の数ｎ2 だけ行う。最後に、第５のフェーズでは、図２R>２（ｅ）に示すように、上記ｎ1 長ＤＦＴ処理で得られた結果を１次元状のデータ配置に並べ替える。
【００４２】
図１は、本実施例によるフーリエ変換装置の構成を示す図であって、図２に示した５つのフェーズの処理を行うための構成を示す図である。図１において、１は第１の並べ替え手段であり、上記第１のフェーズの処理を行う。この第１の並べ替え手段１は、例えば、メモリとアドレッシング装置とにより簡単に構成することが可能である。この並べ替え処理を式で表すと、次の（式３）のようになる。
【００４３】
【数３】
2006164308.tif 000005
【００４４】
２はｎ2 長フーリエ変換手段であり、次の（式４）に従って上記第２のフェーズの処理を行う。すなわち、上記第１の並べ替え手段１で並べ替えられた２次元状のデータ配置において、縦方向に対するｎ2 長のＤＦＴ処理をｎ1 回行う。
【００４５】
【数４】
2006164308.tif 000006
【００４６】
３は回転演算手段であり、次に示す（式５）に従って上記第３のフェーズの処理を行う。すなわち、上記ｎ2 長フーリエ変換手段２による演算処理の結果得られたデータに対して回転演算を施す。
【００４７】
【数５】
2006164308.tif 000007
【００４８】
４は中間バッファメモリであり、上記ｎ2 長フーリエ変換手段２によりフーリエ変換されたデータを一時記憶する。上述の回転演算手段３は、この中間バッファメモリ４に記憶されたデータに対して回転演算を行い、その演算結果をｎ1 長フーリエ変換手段５に供給するようになされている。
【００４９】
上記ｎ1 長フーリエ変換手段５は、上記回転演算手段３による回転演算の結果得られるデータを用いて、次の（式６）に従って上記第４のフェーズの処理を行う。すなわち、上記並べ替えられた２次元状のデータ配置において、横方向に対するｎ1 長のＤＦＴ処理をｎ2 回行う。
【００５０】
【数６】
2006164308.tif 000008
【００５１】
６は第２の並べ替え手段であり、上記第５のフェーズの処理を行う。すなわち、上記ｎ1 長フーリエ変換手段５により求められたデータを次の（式７）に従って再び１次元状に並べ替えることにより、周波数成分の信号Ｓk を得る。なお、この第２の並べ替え手段６は、上記第１の並べ替え手段１と同様に、メモリとアドレッシング装置とにより構成することが可能である。
【００５２】
【数７】
2006164308.tif 000009
【００５３】
上記（式３）〜（式７）に示した５つのフェーズに分けて行っている本実施例のＤＦＴ処理は、従来の（式１）で行っているＤＦＴ処理と等価であり、同じ演算結果（同じ周波数成分の信号Ｓk ）を得ることができる。一方、その演算結果を得るまでの演算量は、従来に比べて本実施例の方が少なくなっている。このことを以下に説明する。
【００５４】
本実施例のＤＦＴ処理における第１のフェーズと第５のフェーズの処理は、単なるデータの並べ替え処理（メモリアドレッシング処理）であるから、演算は行っていない。そこで、本実施例における総演算量は、第２〜第４のフェーズにおける各処理の演算量を合計したものとなる。次に示す表１は、その演算量を示したものである。
【００５５】
【表１】
2006164308.tif 000010
【００５６】
この表１から明らかなように、本実施例のＤＦＴ処理で行う乗算の回数は、４ｎ1 ｎ2 （ｎ1 ＋ｎ2 ＋１）回であり、加減算を行う回数は、２ｎ1 ｎ2 （２ｎ1 ＋２ｎ2 ＋１）回である。一方、従来例のところで述べたように、従来のＤＦＴ処理で行う乗算の回数は、４Ｎ2 ＝４ｎ12ｎ22回である。また、加減算を行う回数は、２Ｎ2 ＋２Ｎ（Ｎ−１）＝４ｎ12ｎ22−２ｎ1 ｎ2 回であり、２ｎ1 ｎ2 は殆ど無視できるほど小さいと考えてよいから、結局４ｎ12ｎ22回である。
【００５７】
乗算を行う回数および加減算を行う回数をそれぞれ本実施例と従来とで比較してみれば分かるように、ｎ1 とｎ2 の値を共に３以上とすれば、本実施例のＤＦＴ処理における演算量を従来のＤＦＴ処理における演算量よりも確実に少なくすることができる。
【００５８】
次に、本実施例のＤＦＴ処理と従来のＦＦＴ処理とを比較してみると、従来のＦＦＴは、本実施例のＤＦＴの特別な例であると言える。すなわち、本実施例のＤＦＴでは、実演算を第２〜第４のフェーズの３段に分離して行っている。これに対し、従来のＦＦＴは、第２のフェーズと第３のフェーズまたは第３のフェーズと第４のフェーズとを一まとめにして演算の流れを再配置し、バタフライ演算という形にまとめて行うものである。
【００５９】
このため、演算量の観点からすれば、本実施例のＤＦＴと従来のＦＦＴとで差ほど変わりはないと言える。ところが、各フェーズの処理をパイプライン化して並列に行う場合に必要な中間バッファメモリの容量という観点からすると、本実施例のＤＦＴでは、従来のＦＦＴよりも格段に小さいメモリ容量で済むというメリットがある。
【００６０】
すなわち、本実施例の場合、上記中間バッファメモリ４に必要なメモリ容量はｎ1 ×ｎ2 ワード分である。さらに、第２のフェーズにおけるｎ1 長ＤＦＴ処理の周期ｎ1 を更に細かく分離して横方向ｎ11、縦方向ｎ12（ｎ1 ＝ｎ11×ｎ12）として処理することとすれば、その中間部にｎ11×ｎ12ワード分のメモリが必要になる。また、第４のフェーズにおけるｎ2 長ＤＦＴ処理の周期ｎ2 を更に細かく分離して横方向ｎ21、縦方向ｎ22（ｎ2 ＝ｎ21×ｎ22）として処理することとすれば、その中間部にｎ21×ｎ22ワード分のメモリが必要になる。
【００６１】
以下同様にして、更に細かく周期を分離して縦方向のＤＦＴ処理と横方向のＤＦＴ処理とを行うようにすれば、例えばＮ＝２16点の周波数解析を行う場合、各中間バッファメモリで必要なメモリ容量は、図３（ａ）の各四角の中に示す数字のようになる。したがって、中間バッファメモリの全メモリ容量は、各中間バッファメモリのメモリ容量を合計して、６６１７６ワード分となる。
【００６２】
もちろん、図３（ａ）に示したように周期が最も小さくなるまで細分化する必要は必ずしもなく、その場合に必要なメモリ容量は、上記６６１７６ワードよりも小さくなる。
【００６３】
一方、従来のＦＦＴでは、数段階のバタフライ演算によって周波数解析を実施しているが、上述したように各バタフライ演算の基数は小さい値しかとることができない。そこで、基数を２とした場合に各中間バッファメモリとして必要なメモリ容量を、図３（ｂ）に示した。この図３（ｂ）から、中間バッファメモリとして必要な全メモリ容量は、１３１１０２ワード分であることが分かる。
【００６４】
図３（ａ）と図３（ｂ）とを比較すれば明らかなように、本実施例のＤＦＴ処理によれば、各フェーズの処理を並列化動作させる場合に必要な中間バッファメモリのメモリ容量を、従来のＦＦＴで各バタフライ演算を並列化動作させる場合に必要なメモリ容量よりも小さくすることができる。
【００６５】
以上説明したように、本実施例のフーリエ変換装置によれば、一連のフーリエ変換処理にかかる演算量を少なくすることができ、しかも、各フェーズを並列化動作させた場合に使用する中間バッファメモリの全メモリ容量を小さくすることもできるようになる。
【００６６】
なお、以上の実施例では、第１の並べ替え手段１と第２の並べ替え手段６とを含めたものを１つのフーリエ変換装置として扱っているが、このようなデータの並べ替えを行う手段が外部に存在すれば、これらの手段はフーリエ変換装置内に必ずしも設ける必要はない。
【００６７】
以上のような本実施例のフーリエ変換装置を利用して、以下に述べる幾つかの応用例を実現することができる。
【００６８】
まず第１番目の例は、ある小さな周期のフーリエ変換装置を２個直列に設けるとともに、その間に小規模の回転演算装置を付加することにより、より大きな周期のフーリエ変換装置を構成したものである。
【００６９】
例えば、図４に示すように、ｎ2 長ＤＦＴ装置１１とｎ1 長ＤＦＴ装置１４とを直列に設けるとともに、その間に回転演算装置１２と（ｎ1 ×ｎ2 ）ワード分の容量を持つ中間バッファメモリ１３とを付加することにより、Ｎ＝ｎ1 ×ｎ2長の大きな周期のＤＦＴ装置を構成する。そして、ｎ2 長ＤＦＴとｎ1 長ＤＦＴとをパイプライン処理することにより、Ｎ点の周波数解析を実施する。
【００７０】
上述したように、大きな周期Ｎの周波数解析を１個のＤＦＴ装置で一度に行うのは演算負荷が非常に大きいのに対して、小さな周期ｎ1 、ｎ2 の組み合わせで周波数解析を行うのは演算負荷が小さい。したがって、本装置によれば、全体としての処理速度を高速にすることができるというメリットがある。
【００７１】
第２番目の例は、第２のフェーズにおけるｎ2 長ＤＦＴ処理と第４のフェーズにおけるｎ1 長ＤＦＴ処理とがそれぞれ独立性が高いことを利用して、上記ｎ2長ＤＦＴ処理を行う装置と上記ｎ1 長ＤＦＴ処理を行う装置とをそれぞれ複数個ずつ設けて１つのフーリエ変換装置を構成したものである。
【００７２】
例えば、図５に示すように、ｍ1(ワード／秒) の演算能力を持つｎ2 長ＤＦＴ装置２１ａ，２１ｂ，…，２１ｃをｌ1 個設けてｎ2 長ＤＦＴ装置群２１を構成するとともに、ｍ2(ワード／秒) の演算能力を持つｎ1 長ＤＦＴ装置２４ａ，２４ｂ，…，２４ｃをｌ2 個設けてｎ1 長ＤＦＴ装置群２４を構成する。
【００７３】
そして、上記ｎ2 長ＤＦＴ装置群２１と上記ｎ1 長ＤＦＴ装置群２４との間にｍ3(ワード／秒) の演算能力を持つ回転演算装置２２と（ｎ1 ×ｎ2 ）ワード分の容量を持つ中間バッファメモリ２３とを設けることにより、１つのフーリエ変換装置を構成する。
【００７４】
既に説明したように、第２のフェーズではｎ2 長ＤＦＴ処理をｎ1 回行う必要がある。そこで、ｎ2 長ＤＦＴ装置群２１を構成するｎ2 長ＤＦＴ装置２１ａ，２１ｂ，…，２１ｃをｎ1 個、あるいは適当な数で割った個数だけ設けることにより、ｎ1 回のｎ2 長ＤＦＴ処理を並列に行うようにする。これにより、ｎ2 長ＤＦＴ処理をより短時間で行うようにすることができる。
【００７５】
例えば、ｎ1 ＝４の場合、先に示した図４の例のように、１個のｎ2 長ＤＦＴ装置１１でｎ1 回のｎ2 長ＤＦＴ処理を行うのでは４サイクルかかっていたのに対し、ｎ2 長ＤＦＴ装置を２個設ければ２サイクルで行うことができる。また、ｎ2 長ＤＦＴ装置を４個設ければ、１サイクルで行うことができる。
【００７６】
また、第４のフェーズについても同様に、ｎ1 長ＤＦＴ装置群２４を構成するｎ1 長ＤＦＴ装置２４ａ，２４ｂ，…，２４ｃをｎ2 個、あるいは適当な数で割った個数だけ設けることにより、ｎ2 回のｎ1 長ＤＦＴ処理を行う際の演算サイクル数を少なくすることができる。これにより、より高速なフーリエ変換装置を得ることができる。
【００７７】
なお、上記ｎ2 長ＤＦＴ装置群２１の全体としての演算能力はｌ1 ×ｍ1(ワード／秒) であり、上記ｎ1 長ＤＦＴ装置群２４の全体としての演算能力はｌ2 ×ｍ2(ワード／秒) である。ここで、ｍ3 ≦ｌ1 ×ｍ1 あるいはｍ3 ≦ｌ2 ×ｍ2が成立すると、上記ｎ2 長ＤＦＴ装置群２１およびｎ1 長ＤＦＴ装置群２４は、ｍ3(ワード／秒) の演算能力に制限される。
【００７８】
第３番目の例は、ある小さな周期のフーリエ変換装置を複数個用い、それらを回転演算装置を介して積み重ねるようにして接続する（イメージとしては、図３（ａ）に示したツリー構造となるように接続する）ことにより、より大きな周期のフーリエ変換装置を構成したものである。
【００７９】
例えば、複数個の４点フーリエ変換装置を用いて、より大きな周期の４０９６点フーリエ変換装置を構成する場合について考える。この場合、図６に示すように、４０９６点フーリエ変換装置は、大きく分けて１６点フーリエ変換装置３１と、４０９６点回転演算装置３２と、４０９６ワード分の容量を持つ４０９６点バッファメモリ３３と、２５６点フーリエ変換装置３４とにより構成される。
【００８０】
そして、上記１６点フーリエ変換装置３１は、２つの４点フーリエ変換装置３１ａ，３１ｄと、１６点回転演算装置３１ｂと、１６ワード分の容量を持つ１６点バッファメモリ３１ｃとにより構成される。また、上記２５６点フーリエ変換装置３４は、２つの１６点フーリエ変換装置３４ａ，３４ｄと、２５６点回転演算装置３４ｂと、２５６ワード分の容量を持つ２５６点バッファメモリ３４ｃとにより構成される。
【００８１】
さらに、上記２５６点フーリエ変換装置３４内にある一方の１６点フーリエ変換装置３４ａは、上記１６点フーリエ変換装置３１と同様に、２つの４点フーリエ変換装置３４ａ1 ，３４ａ4 と、１６点回転演算装置３４ａ2 と、１６ワード分の容量を持つ１６点バッファメモリ３４ａ3 とにより構成される。
【００８２】
他方の１６点フーリエ変換装置３４ｄについても上記１６点フーリエ変換装置３１と同様に、２つの４点フーリエ変換装置３４ｄ1 ，３４ｄ4 と、１６点回転演算装置３４ｄ2 と、１６ワード分の容量を持つ１６点バッファメモリ３４ｄ3とにより構成される。
【００８３】
このように、小さな周期の４点フーリエ変換装置を複数個用い、それらを回転演算装置を介してツリー構造となるように接続することにより、より大きな周期の４０９６点フーリエ変換装置を構成している。なお、本装置において用いられている各回転演算装置は、ツリーの枝を結ぶ乗算の役目を果たしている。
【００８４】
つまり、この図６に示した装置では、４０９６点の周波数解析を、縦１６点×横２５６点に分割して行う。そして、縦１６点の周波数解析を行う際には、更に縦４点×横４点に分割して行う。また、横２５６点の周波数解析を行う場合も同様にして、縦４点×横４点のフーリエ変換にまで細分化して行う。
【００８５】
４０９６点の周波数解析を１個の４０９６点フーリエ変換装置で一度に行うのは演算負荷が非常に大きいが、小さな周期の４点フーリエ変換装置の組み合わせで周波数解析を行うのは演算負荷が小さいことは上述した通りである。したがって、本装置によれば、全体としての演算負荷を小さくして処理速度を高速にすることができる。
【００８６】
また、本装置において用いている中間バッファメモリの総メモリ容量は、4096＋16＋256 ＋16＋16＝4440ワードである。これに対して、従来のＦＦＴにより４０９６点フーリエ変換装置を構成すると、各バタフライ演算の基数を４とした場合でも、バッファメモリの総メモリ容量は、4096＋1024＋256 ＋64＋16＋4 ×6＝5480ワードである。
【００８７】
以上のことから明らかなように、図６の装置によれば、４０９６点のＤＦＴ処理にかかる演算量を少なくしてＦＦＴと同程度にまで処理時間を短くすることができるだけでなく、演算の過程で使用する中間バッファメモリのメモリ容量を、ＦＦＴを行う場合に比べて小さくすることもできている。
【００８８】
第４番目の例は、図６に示した第３番目の例を応用した例である。すなわち、窓かけ演算にも流用できるようにした回転演算装置と１６点フーリエ変換装置とを用いて１つのフーリエ変換装置を構成する。そして、これをタイムシェアリング（時分割）で用いることにより、より大きな周期（４０９６点）の周波数解析を行うことができるようにしたものである。
【００８９】
フーリエ変換は、数学上の話では本来は無限長の周期で行うものである。しかし、これを実際に行うのは現実問題として無理である。そこで、実際には、周期Ｎで一定区間を区切り、その端点をつなげることによって無限長とみなして周波数解析を行っている。ところが、この場合に、端点に不連続点が存在すると、正常でない周波数成分、すなわち、周波数もれ成分が生じることがある。
【００９０】
上述した窓かけ演算は、この端点の不連続点をなくし、周波数もれ成分を少なくすることを目的として行われるものであり、次の（式８）に示す演算式によって行われる。なお、（式８）中のＳk はフーリエ解析するデータ、ｗ(k) は窓関数、Ｓk ' は実サンプルデータを示している。
【００９１】
【数８】
2006164308.tif 000011
【００９２】
ところで、この窓かけ演算は、精密ではないが、次の（式９）に示す回転演算とほぼ同じと考えることができる。したがって、係数をうまく与えれば、回転演算装置を用いて窓かけ演算を行うことが可能である。そこで、この第４番目の例では、回転演算装置を窓かけ演算にも流用できるようにしている。
【００９３】
【数９】
2006164308.tif 000012
【００９４】
図７は、この第４番目の例を実現するための装置の構成を示す図である。図７に示したように、本装置は、窓かけ演算にも流用可能な窓かけ／回転演算装置４１と、１６点フーリエ変換装置４２と、４０９６ワード分の容量を持つ４０９６点バッファメモリ４３と、２５６ワード分の容量を持つ２５６点バッファメモリ４４と、データ入力部４５と、データ出力部４６とにより構成されている。
【００９５】
上記回転演算装置４１は、窓かけ演算を行う際に適当な係数を与える手段を具備している。また、上記１６点フーリエ変換装置４２は、図６中に示した各１６点フーリエ変換装置と同様に、２つの４点フーリエ変換装置４２ａ，４２ｄと、１６点回転演算装置４２ｂと、１６点バッファメモリ４２ｃとにより構成されている。
【００９６】
このように構成したフーリエ変換装置は、図６中にα、β、γで示した部分（何れの部分も１６点フーリエ変換装置と回転演算装置、あるいは１６点フーリエ変換装置と窓かけ演算装置とを含んでいる）の処理を時分割で行うことにより、４０９６点の周波数解析を実施する。
【００９７】
すなわち、図８に示すように、まず最初に、データ入力部４５を介して入力されるデータを用いて、図６中のαの部分に相当する演算が行われる。このとき、窓かけ／回転演算装置４１では、適当な係数が与えられることにより窓かけ演算が行われる。このαの部分の演算結果は、データ出力部４６を介して４０９６点バッファメモリ４３に順次格納される。
【００９８】
そして、この４０９６点バッファメモリ４３にデータがたまると、次にそのデータがデータ入力部４５を介して入力され、図６中のβに相当する演算が行われる。このβの部分の演算結果は、データ出力部４６を介して２５６点バッファメモリ４４に順次格納される。次に、この２５６点バッファメモリ４４にデータがたまると、そのデータがデータ入力部４５を介して入力され、図６中のγに相当する演算が行われる。
【００９９】
このように、図７の装置によれば、小さな周期のフーリエ変換の組み合わせによって大きな周期のフーリエ変換を行っているので、４０９６点のＤＦＴ処理にかかる演算量を少なくして処理時間を短くすることができる。さらに、図６の装置と異なり、同じ装置を時分割で何度も用いているので、図６の装置に比べて、４点フーリエ変換装置や中間バッファメモリの使用数を減らすことができ、装置全体の規模を小さくすることができる。
【０１００】
第５番目の例は、高速ページモードを持つメモリを用いて中間バッファメモリを構成し、その高速ページモードを持つメモリに中間バッファメモリを配置するときに、ストライプ状に配置するのではなく、縦横のブロック状に配置することにより、メモリアクセスタイムを短くできるようにしたものである。
【０１０１】
一般に、高速ページモードを持つＩＣメモリは、２次元マトリクス状に作製される。そして、その行（カラム）と列（ロウ）とで位置を指定することにより所望のデータを得るようになされている。この場合、ＤＲＡＭに代表されるメモリでは、その機構上の特徴により、先にロウアドレスを指定し、次にカラムアドレスを指定するようになっている。
【０１０２】
そして、高速ページモードでは、同じロウアドレスについてカラムアドレスを連続して指定する場合には、異なるロウアドレスについてカラムアドレスを指定する場合に比べて高速にアクセスすることができるようになっている。このような高速ページモードを持つメモリの一例として、日立製のメモリ（HM511OOOA-6）がある。
【０１０３】
ところで、上述したように、本実施例のフーリエ変換装置では、第２のフェーズで縦方向に対するＤＦＴ処理を行い、第４のフェーズで横方向に対するＤＦＴ処理を行っている。このため、２次元状に作られた中間バッファメモリの縦方向と横方向に対してそれぞれデータの読み書きを行っている。
【０１０４】
ここで、中間バッファメモリ４を横方向にストライプ状に配置した場合には、縦方向に対する高速ページモードが使えないので、横方向に対するメモリアクセスタイムは速いが、縦方向に対するメモリアクセスタイムが遅くなってしまう。一方、ブロック状に配置すれば、縦方向に対するデータの読み書き時に高速ページモードが使えるので、横方向に対するアクセスタイムも縦方向に対するアクセスタイムも共に速くすることができるようになる。
【０１０５】
図９は、上記した日立製のメモリのアクセスタイムの様子を示すタイムチャートである。この図９の例では、同じロウアドレスについて２つのカラムアドレスを連続して指定した場合について示している。
【０１０６】
すなわち、通常、１ワードのアクセスを行うのにかかる時間（サイクルタイム）は１２０ｎｓｅｃであるのに対して、高速ページモードにおいて２ワードのアクセスを行うのにかかる時間は１５５（＝６０＋４５＋５０）ｎｓｅｃである。つまり、１ワード当たりでは、７７．５ｎｓｅｃと通常時よりもアクセス時間が短くなっていることが図９から読み取れる。
【０１０７】
このような日立製のメモリを中間バッファメモリとして用いた場合の具体例を次に示す。なお、ここでは、中間バッファメモリの全メモリ容量は２18ワード（縦２9 ワード×横２9 ワード）であるとする。
【０１０８】
まず、図１０に示すように、中間バッファメモリを２9 ワード分ずつ横方向にストライプ状に配置する場合について考える。この場合、第２のフェーズで求められたデータを中間バッファメモリに縦方向に書き込む際には、高速ページモードが使えないので、縦方向に対して１ワード当たり１２０ｎｓｅｃの時間がかかる。
【０１０９】
また、第４のフェーズにおいて上記中間バッファメモリからデータを読み出す際に、横方向に対して１ワード当たりにかかるアクセス時間は、（６０＋４５×（２9 −１）＋５０）／２9 ≒４５．１３ｎｓｅｃである。よって、メモリアクセスに関するデータレートの上限は、１２０＋４５．１３＝１６５．１３ｎｓｅｃ／ワードとなる。
【０１１０】
次に、図１１に示すように、中間バッファメモリを２9 ワード分ずつブロック状（縦２4 個×横２5 個）に配置する場合について考える。この場合、縦方向に対するメモリアクセス時に高速ページモードを使うことが可能であるので、第２のフェーズで求められたデータを中間バッファメモリに書き込む際にかかる時間は、縦方向に対して１ワード当たり（６０＋４５×１５＋５０）／１６≒４９．０６ｎｓｅｃである。
【０１１１】
また、第４のフェーズにおいて上記中間バッファメモリからデータを読み出す際に、横方向に対して１ワード当たりにかかるアクセス時間は、（６０＋４５×３１＋５０）／３２≒４７．０３ｎｓｅｃである。よって、メモリアクセスに関するデータレートの上限は、４９．０６＋４７．０３＝９６．０９ｎｓｅｃ／ワードとなる。
【０１１２】
以上の計算結果から明らかなように、中間バッファメモリをブロック状に配置することにより、ストライプ状に配置する場合に比べてメモリアクセス時間を短くすることができる。これにより、上述したようにフーリエ変換処理を行う際の演算量を減らすことができるだけでなく、処理の過程で使用する中間バッファメモリへのアクセス時間を削減することもできるようになり、全体としての処理時間を更に短くすることができる。
【０１１３】
第６番目の例は、第２のフェーズの処理と第４のフェーズの処理とを並列に動作させる場合に、中間バッファメモリにデータを読み書きする際のアドレッシング動作を工夫することにより、中間バッファメモリを１ページ分だけ用意すれば済むようにしたものである。
【０１１４】
第４のフェーズの処理を行う際には、第２のフェーズで求められたデータを用いるため、第２のフェーズの処理が終わらなければ第４のフェーズの処理は行うことができない。したがって、第２のフェーズの処理と第４のフェーズの処理とを並列に動作させる場合は、通常は、図１２に示すように、第２のフェーズ用と第４のフェーズ用との２ページ分の中間バッファメモリが必要になる。
【０１１５】
すなわち、第２のフェーズと第４のフェーズとを並列動作させる場合には、図１２（ａ）に示すように、第２のフェーズにおける縦方向のＤＦＴ処理で求められるデータを縦方向に順次記憶していくと同時に、図１２（ｂ）に示すように、既に求められたデータを第４のフェーズにおいて横方向に読み出して横方向のＤＦＴ処理を順次行っていく必要がある。
【０１１６】
したがって、第２のフェーズで求められるデータを縦方向に順次記憶していくためのページと、第４のフェーズでデータを横方向に読み出して使用するためのページとの２ページが中間バッファメモリとして必要になる。しかし、このように中間バッファメモリを２ページも用意したのでは、メモリ容量が非常に大きくなってしまう。
【０１１７】
そこで、この第６番目の例では、今までのように第２のフェーズで求められたデータは縦方向に書き込み、第４のフェーズの処理ではデータを横方向に読み出すというように一定としないで、図１３に示すように、１回目に行う第２、第４のフェーズではデータを縦方向に読み書きする。２回目に行う第２、第４のフェーズではデータを横方向に読み書きするというように、アドレッシングの方向を縦と横で交互に切り換えていくようにする。
【０１１８】
すなわち、図１３（ａ）において、１回目に行う第４のフェーズの処理では、中間バッファメモリに既に記憶されているデータ（この第４のフェーズの処理よりも前に行われた０回目の第２のフェーズの処理で求められたデータ）が縦方向に順次読み出される。
【０１１９】
そして、この第４のフェーズの処理と同時に行われている１回目の第２のフェーズの処理で求められたデータが、上記読み出しによって空になった縦方向の領域に順次書き込まれる。すると、最終的には、中間バッファメモリの全ての領域に、１回目の第２のフェーズの処理で求められたデータが記憶される。
【０１２０】
次に、図１３（ｂ）において、２回目に行う第４のフェーズの処理では、中間バッファメモリに記憶されているデータ（上記１回目の第２のフェーズの処理で求められたデータ）が横方向に順次読み出される。
【０１２１】
そして、この第４のフェーズの処理と同時に行われている２回目の第２のフェーズの処理で求められたデータが、上記読み出しによって空になった横方向の領域に順次書き込まれる。すると、最終的には、中間バッファメモリの全ての領域に、２回目の第２のフェーズの処理で求められたデータが記憶される。この後は、再び図１３（ａ）に示す処理が行われる。
【０１２２】
以上のように、アドレッシングの方向を交互に切り換えてデータの読み書きを行うようにすれば、データを読み出して空きになった領域を有効に活用して、１つの中間バッファメモリを第２のフェーズ用と第４のフェーズ用とで共用することができ、中間バッファメモリを１ページ分だけ用意すれば済むようになる。
【０１２３】
第７番目の例は、図５に示した第２番目の例を応用した例である。図５に示したように複数のＤＦＴ装置を用いて処理を並列化させた場合には、中間バッファメモリ２３へのアクセスが非常に多くなる。そこで、この第７番目の例は、上記中間バッファメモリ２３を複数のメモリに分割して用意するとともに、クロスバスイッチなどのデータ振り分け装置を用いることにより、メモリアクセス時における並列動作性を高めることができるようにしたものである。
【０１２４】
図１４は、この第７番目の例を実現するための装置の構成を示す図である。なお、この図１４に示す装置は、図５に示した装置を変形したものであり、図５R>５中に示した周期ｎ1 、ｎ2 の値をそれぞれ４とし、ｎ1 長ＤＦＴ処理を行う装置の数ｌ1 、ｎ2 長ＤＦＴ処理を行う装置の数ｌ2 をそれぞれ４個とした場合について示したものである。
【０１２５】
すなわち、本装置は、第２のフェーズの処理を行う４個の４点フーリエ変換装置５１ａ，５１ｂ，５１ｃ，５１ｄと、データ振り分け装置５２と、並列動作可能な４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄと、第４のフェーズの処理を行う４個の４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄとにより構成される。なお、ここでは、説明の簡略化のため、回転演算装置は図示を省略している。
【０１２６】
次に、上記のように構成した装置の動作を、図１５に示す中間データの配置図を参照しながら説明する。本装置では、第２のフェーズで縦方向に４点フーリエ変換を行い、第４のフェーズで横方向に４点フーリエ変換を行うことにより、第１〜第１６ワード（図１５R>５に丸付の数字で示している）の１６点周波数解析を実行する。
【０１２７】
このとき、上述した第２のフェーズの処理を行う４個の４点フーリエ変換装置５１ａ，５１ｂ，５１ｃ，５１ｄは、それぞれ図１５の縦方向に対するデータを用いてフーリエ変換を同時に行う。これにより、第１サイクルでは、第１、第２、第３、第４ワードについてフーリエ変換されたデータが同時に得られる。
【０１２８】
このようにして同時に得られた４個のデータは、データ振り分け装置５２により４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに１ワードずつ振り分けられて記憶される。ここで、各ワードのデータが記憶される中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄの種類を、それぞれＡ〜Ｄの符号を付して示した。
【０１２９】
通常、４個のデータを１個の中間バッファメモリに書き込むためには、４サイクル必要であるが、本実施例では、４個のデータを４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに振り分けて書き込むようにしているので、１サイクルで書き込みを行うことができる。
【０１３０】
また、第２サイクル〜第４サイクルの各サイクルで同時にフーリエ変換されたデータについても同様に、データ振り分け装置５２により４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに１ワードずつ振り分けられて記憶される。このとき、同じフーリエ変換装置で変換されたデータが同じ中間バッファメモリ内に記憶されないように振り分けが行われる。
【０１３１】
以上のような書き込み動作により、４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄには、図１５に示すような関係で各ワードのデータが記憶されることになる。すなわち、第１の中間バッファメモリ５３ａには、第１、第６、第１１、第１６ワードのデータが記憶され、第２の中間バッファメモリ５３ｂには、第５、第１０、第１５、第４ワードのデータが記憶される。
【０１３２】
また、第３の中間バッファメモリ５３ｃには、第９、第１４、第３、第８ワードのデータが記憶され、第４の中間バッファメモリ５３ｄには、第１３、第２、第７、第１２ワードのデータが記憶される。
【０１３３】
次に、第４のフェーズの処理を行う際には、上述した第４のフェーズの処理を行う４個の４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄは、それぞれ図１５の横方向に対するデータを用いてフーリエ変換を同時に行う。すなわち、第１サイクルでは、上記４個の４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄは、それぞれ第１、第５、第９、第１３ワードのデータを読み出してフーリエ変換を同時に行う。
【０１３４】
この場合、図１５から明らかなように、各４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄで同時に使用する４個のデータは、上記４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに１ワードずつ分散して記憶されている。したがって、１個の中間バッファメモリに上記４個のデータが全て記憶されていたとしたなら読み出しに４サイクルかかるところを、本実施例では、１サイクルで読み出すことができる。
【０１３５】
以上説明したように、図１４に示した第７番目の例の装置によれば、複数のフーリエ変換装置を用いてＤＦＴ処理を並列化動作させた場合に、中間バッファメモリへのアクセスも効率よく並列化させることができ、装置全体の並列動作性を向上させることができる。なお、参考のために、上述したデータの読み書きの手順を、図１６に示しておく。
【図面の簡単な説明】
【０１３６】
【図１】本発明の一実施例であるフーリエ変換装置の構成を示すブロック図である。
【図２】図１のフーリエ変換装置によって行われる第１〜第５のフェーズの処理内容を説明するための図である。
【図３】本実施例のフーリエ変換装置をツリー構造にした場合に必要な中間バッファメモリの容量を、ＦＦＴの各バタフライ演算を並列化動作させた場合に必要な中間バッファメモリの容量と比較するための図である。
【図４】第１番目の応用例による装置の構成を示す図である。
【図５】第２番目の応用例による装置の構成を示す図である。
【図６】第３番目の応用例による装置の構成を示す図である。
【図７】第４番目の応用例による装置の構成を示す図である。
【図８】図７に示した装置によって行われる時分割処理の様子を説明するための図である。
【図９】第５番目の応用例で使用される高速ページモードを持つ中間バッファメモリのアクセスタイムの様子を示すタイムチャートである。
【図１０】中間バッファメモリをストライプ状に配置した様子を示す図である。
【図１１】中間バッファメモリをブロック状に配置した様子を示す図である。
【図１２】２ページ分の中間バッファメモリを用いてデータの読み書きを行う様子を説明するための図である。
【図１３】第６番目の応用例によるデータの読み書きの様子を説明するための図であり、１ページ分の中間バッファメモリを用いてデータの読み書きを行う様子を説明するための図である。
【図１４】第７番目の応用例による装置の構成を示す図である。
【図１５】複数の中間バッファメモリとそれに記憶されるデータとの関係を説明するための図である。
【図１６】第７番目の応用例によるデータの読み書きの手順を示す図である。
【符号の説明】
【０１３７】
１  第１の並べ替え手段
２  ｎ2 長フーリエ変換手段
３  回転演算手段
４  中間バッファメモリ
５  ｎ1 長フーリエ変換手段
６  第２の並べ替え手段
【図１】
2006164308.tif 000013
【図２】
2006164308.tif 000014
【図３】
2006164308.tif 000015
【図４】
2006164308.tif 000016
【図５】
2006164308.tif 000017
【図６】
2006164308.tif 000018
【図７】
2006164308.tif 000019
【図８】
2006164308.tif 000020
【図９】
2006164308.tif 000021
【図１０】
2006164308.tif 000022
【図１１】
2006164308.tif 000023
【図１２】
2006164308.tif 000024
【図１３】
2006164308.tif 000025
【図１４】
2006164308.tif 000026
【図１５】
2006164308.tif 000027
【図１６】
2006164308.tif 000028
【手続補正書】
【提出日】平成18年3月10日(2006.3.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
横方向に周期ｎ1 、縦方向に周期ｎ2 の２次元状に配置された周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号に対して、縦方向に対する周期ｎ2のフーリエ変換を行うｍ個のｎ2 長フーリエ変換手段と、
上記ｍ個のｎ2 長フーリエ変換手段による変換結果を一時記憶するためのｍ個の中間バッファメモリと、
上記ｍ個の中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、
上記回転演算手段による演算結果に対して、横方向に対する周期ｎ1 のフーリエ変換を行うｍ個のｎ1 長フーリエ変換手段と、
上記ｍ個のｎ2 長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにするデータ振り分け手段とを有し、
上記ｍ個のｎ2 長フーリエ変換手段を用いてｎ1 回のｎ2 長フーリエ変換処理を並列に行うとともに、上記ｍ個のｎ1 長フーリエ変換手段を用いてｎ2 回のｎ1長フーリエ変換処理を並列に行うようにし、上記回転演算手段の演算能力は、上記ｎ2 長フーリエ変換手段の演算能力のｍ倍、及び上記ｎ1 長フーリエ変換手段の演算能力のｍ倍をも上回るようにしたことを特徴とするフーリエ変換装置。
【請求項２】
上記データ振り分け手段は、同じｎ2 長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ1 長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして、順次得られるデータを振り分けて記憶するようにすることを特徴とする請求項１に記載のフーリエ変換装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
すなわち、ＦＦＴを構成する各バタフライ演算の性質上、その基数は比較的小さいものしか選択することができないため、バタフライ演算の段数が多くなってしまう。そのため、各バタフライ演算の結果を一時記憶しておくための中間バッファメモリの数が多くなるとともに、個々の中間バッファメモリの容量も大きくなってしまい、その結果、全メモリ容量が非常に大きくなってしまっていた。さらに、基本演算を数段階に渡って繰り返して行うことにより、容量が大きい中間バッファメモリへのアクセスが多くなる。大容量の中間バッファメモリにアクセスする場合は、１回のアクセスタイムが長くかかるのでアクセス回数が多くなると、アクセスタイムが膨大となり、フーリエ変換を行うための処理速度を低下させてしまうという問題点があった。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
本発明のフーリエ変換装置は、横方向に周期ｎ1 、縦方向に周期ｎ2 の２次元状に配置された周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号に対して、縦方向に対する周期ｎ2のフーリエ変換を行うｍ個のｎ2 長フーリエ変換手段と、上記ｍ個のｎ2 長フーリエ変換手段による変換結果を一時記憶するためのｍ個の中間バッファメモリと、上記ｍ個の中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、上記回転演算手段による演算結果に対して、横方向に対する周期ｎ1 のフーリエ変換を行うｍ個のｎ1 長フーリエ変換手段と、上記ｍ個のｎ2 長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにするデータ振り分け手段とを有し、上記ｍ個のｎ2 長フーリエ変換手段を用いてｎ1 回のｎ2 長フーリエ変換処理を並列に行うとともに、上記ｍ個のｎ1 長フーリエ変換手段を用いてｎ2 回のｎ1長フーリエ変換処理を並列に行うようにし、上記回転演算手段の演算能力は、上記ｎ2 長フーリエ変換手段の演算能力のｍ倍を上回るとともに、上記ｎ1 長フーリエ変換手段の演算能力のｍ倍をも上回っていることを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】削除
【補正の内容】
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】削除
【補正の内容】
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】削除
【補正の内容】
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】削除
【補正の内容】
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】削除
【補正の内容】
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】削除
【補正の内容】
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】削除
【補正の内容】
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】削除
【補正の内容】
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
本発明の他の特徴とするところは、上記データ振り分け手段は、同じｎ2 長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ1 長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして、順次得られるデータを振り分けて記憶するようにすることを特徴とする。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
本発明は、上記技術手段より成り、周期Ｎの時間成分の信号が周期Ｎのフーリエ変換によって一度に周波数変換されるのではなく、上記周期Ｎよりも小さな周期ｎ1 、ｎ2 のフーリエ変換の組み合わせによって周波数変換されることとなるので、フーリエ変換演算の性質上、上記小さな周期ｎ1 、ｎ2 のフーリエ変換でそれぞれ行われる演算量は、上記周期Ｎのフーリエ変換で行われる演算量に比べて格段に少ないものとなり、上記小さな周期ｎ1 、ｎ2 のフーリエ変換で行われる各演算量と回転演算で行われる演算量とを合計しても、上記周期Ｎのフーリエ変換によって一度に周波数変換を行うようになされた従来のＤＦＴの演算量よりも演算量が少なくなる。また、上記小さな周期ｎ1 、ｎ2 のフーリエ変換をｍ個のｎ2長フーリエ変換手段及びｎ1 長フーリエ変換手段を用いて並列に行うようにするとともに、同じ数の中間バッファメモリを用意して、上記ｍ個のｎ2 長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにし、さらに回転演算手段の演算能力をｎ2長フーリエ変換手段及びｎ1 長フーリエ変換手段のｍ倍を上回るようにしたので、演算サイクル数が少なくなるとともに、中間バッファメモリへのアクセスも効率よく並列化することが可能となり、アクセスタイムを格段と短くすることが可能となる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】削除
【補正の内容】
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】削除
【補正の内容】
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】削除
【補正の内容】
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】削除
【補正の内容】
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】削除
【補正の内容】
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
また、本発明の他の特徴によれば、複数のｎ1 長フーリエ変換手段で同時に使用されるデータが複数のバッファメモリに１個ずつ分散して記憶されるとともに、複数のｎ1 長フーリエ変換手段で同時に使用されるデータが複数のバッファメモリに１個ずつ分散するように記憶されることとなるので、処理の並列動作性を更に高めることができる。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
本発明によれば、周期Ｎ（＝ｎ1 ×ｎ2 ）の時間成分の信号の周波数解析を、上記周期Ｎよりも小さな周期である横方向に対する周期ｎ1 のフーリエ変換と縦方向に対する周期ｎ2 のフーリエ変換との組み合わせによって行うようにして、上記小さな周期ｎ1 、ｎ2 のフーリエ変換をｍ個のｎ2長フーリエ変換手段及びｎ1 長フーリエ変換手段を用いて並列に行うとともに、同じ数の中間バッファメモリを用意して、上記ｍ個のｎ2 長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにし、さらに回転演算手段の演算能力をｎ2長フーリエ変換手段及びｎ1 長フーリエ変換手段のｍ倍をそれぞれ上回るようにしたので、上記周期Ｎのフーリエ変換によって一度に周波数変換を行うようになされた従来のＤＦＴの演算量よりも演算量を少なくすることができる。また、演算サイクル数を少なくすることができるとともに、中間バッファメモリへのアクセスを効率よく並列化してアクセスタイムを短くすることができる。これにより、全体としての中間バッファメモリの容量を格段に小さくすることができるとともに、フーリエ変換の処理速度を高速にすることができる。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】削除
【補正の内容】
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】削除
【補正の内容】
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】削除
【補正の内容】
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】削除
【補正の内容】
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】削除
【補正の内容】
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】削除
【補正の内容】
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
また、本発明の他の特徴によれば、上記データの振り分けの際に、同じｎ2 長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ1 長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして順次得られるデータを振り分けるようにしたので、処理の並列動作性を更に高めることができる。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】００４１
【補正方法】変更
【補正の内容】
【００４１】
次に、第３のフェーズでは、図２（ｃ）に示すように、上記ｎ2 長ＤＦＴ処理で得られた結果に対して回転演算を施す。第４のフェーズでは、図２（ｄ）に示すように、上記回転演算の結果に対して、横方向に対するｎ1 個のデータを用いてｎ1 長ＤＦＴ処理を縦方向の数ｎ2 だけ行う。最後に、第５のフェーズでは、図２（ｅ）に示すように、上記ｎ1 長ＤＦＴ処理で得られた結果を１次元状のデータ配置に並べ替える。
【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】０１２４
【補正方法】変更
【補正の内容】
【０１２４】
図１４は、この第７番目の例を実現するための装置の構成を示す図である。なお、この図１４に示す装置は、図５に示した装置を変形したものであり、図５中に示した周期ｎ1 、ｎ2 の値をそれぞれ４とし、ｎ1 長ＤＦＴ処理を行う装置の数ｌ1 、ｎ2 長ＤＦＴ処理を行う装置の数ｌ2 をそれぞれ４個とした場合について示したものである。
【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】０１２６
【補正方法】変更
【補正の内容】
【０１２６】
次に、上記のように構成した装置の動作を、図１５に示す中間データの配置図を参照しながら説明する。本装置では、第２のフェーズで縦方向に４点フーリエ変換を行い、第４のフェーズで横方向に４点フーリエ変換を行うことにより、第１〜第１６ワード（図１５に丸付の数字で示している）の１６点周波数解析を実行する。