JP3950466B2

JP3950466B2 - フーリエ変換装置

Info

Publication number: JP3950466B2
Application number: JP2006033084A
Authority: JP
Inventors: 弥章佐藤
Original assignee: United Module Corp
Current assignee: United Module Corp
Priority date: 2006-02-09
Filing date: 2006-02-09
Publication date: 2007-08-01
Anticipated expiration: 2015-07-18
Also published as: JP2006164308A

Description

本発明は、フーリエ変換装置に関するものである。

従来、時間成分の信号を周波数成分の信号に変換するための手法の１つに、ＤＦＴ（離散的フーリエ変換）と呼ばれる手法がある。Ｎ点の信号（周期がＮであることを示す）を周波数変換するためのＤＦＴの一般式は、時間成分の信号値をＳ_i、周波数成分の信号値をＳ_kとすると、次の（式１）のように表せる。

この（式１）の演算を行うためには、乗算を４Ｎ²回、加減算を２Ｎ²＋２Ｎ（Ｎ−１）回行う必要がある。すなわち、（式１）から分かるように、ＤＦＴは複素演算を行うものであるから、実際には次の（式２）で示される回転演算を引数ｋ，ｉの各値について行っている。

（式２）において、周波数成分の信号値Ｓ_k[real]（実部）、Ｓ_k[imag]（虚部）を求めるためには、時間成分の信号値Ｓ_i[real]と cosθ、信号値Ｓ_i[real]と sinθ、信号値Ｓ_i[imag]と sinθ、信号値Ｓ_i[imag]と cosθとの乗算をそれぞれｉについてＮ回、それを更にｋについてＮ回、２重のループで計算するから、全部で４Ｎ²回の乗算が必要になる。

さらに、上述の乗算により得られる信号値Ｓ_i[real] cosθと信号値Ｓ_i[imag] sinθとの減算、信号値Ｓ_i[real] sinθと信号値Ｓ_i[imag] cosθとの加算をそれぞれｉについてＮ回、それを更にｋについてＮ回、２重のループで計算するから、全部で２Ｎ²＋２Ｎ（Ｎ−１）回の加減算が必要になる。上述のようなフーリエ変換を行う装置の従来例は、例えば、特許文献１、２によって提案されている。

特開平０７−００６１６０号公報特開平０２−１０１５７４号公報

以上のように、従来のＤＦＴでは、数多くの乗算および加減算を行う必要があった。このため、処理に膨大な時間がかかってしまうという問題があった。そこで、従来、上記ＤＦＴの処理時間をできるだけ短くすることができるようにするために、ＦＦＴ（高速フーリエ変換）と呼ばれる手法が開発され、デジタル信号処理の分野で多く用いられてきた。

このＦＦＴは、バタフライ演算と呼ばれる基本演算を数段階に渡って繰り返して行うことにより、ＤＦＴの演算量を削減できるようにしたものである。つまり、ＦＦＴにおいて周期Ｎのフーリエ変換を実施する場合には、上記周期Ｎを所定の基数ごとに数段階に分けて、各基数のバタフライ演算をそれぞれ行うことで周波数解析を行っていた。

このＦＦＴでは、数段階のバタフライ演算をパイプライン処理で並列に行うことが可能である。その場合には、数段階に渡って演算した結果をそれぞれ一時記憶しておくための中間バッファメモリが必要になる。しかしながら、従来のＦＦＴでは、各中間バッファメモリの全メモリ容量が非常に大きくなってしまうという問題があった。

すなわち、ＦＦＴを構成する各バタフライ演算の性質上、その基数は比較的小さいものしか選択することができないため、バタフライ演算の段数が多くなってしまう。そのため、各バタフライ演算の結果を一時記憶しておくための中間バッファメモリの数が多くなるとともに、個々の中間バッファメモリの容量も大きくなってしまい、その結果、全メモリ容量が非常に大きくなってしまっていた。さらに、基本演算を数段階に渡って繰り返して行うことにより、容量が大きい中間バッファメモリへのアクセスが多くなる。大容量の中間バッファメモリにアクセスする場合は、１回のアクセスタイムが長くかかるのでアクセス回数が多くなると、アクセスタイムが膨大となり、フーリエ変換を行うための処理速度を低下させてしまうという問題点があった。

本発明は、このような問題を解決するために成されたものであり、デジタル信号処理においてフーリエ変換を行うための処理時間を短くすることができるようにするとともに、その処理の際に使用する中間バッファメモリの容量を小さくすることができるようにすることを目的とする。

本発明のフーリエ変換装置は、横方向に周期ｎ₁、縦方向に周期ｎ₂の２次元状に配置された周期Ｎ（＝ｎ₁×ｎ₂）の時間成分の信号に対して、縦方向に対する周期ｎ₂のフーリエ変換を行うｍ個のｎ₂長フーリエ変換手段と、上記ｍ個のｎ₂長フーリエ変換手段による変換結果を一時記憶するためのｍ個の中間バッファメモリと、上記ｍ個の中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、上記回転演算手段による演算結果に対して、横方向に対する周期ｎ₁のフーリエ変換を行うｍ個のｎ₁長フーリエ変換手段と、複数サイクルに亘って同じｎ₂長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ₁長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして、上記ｍ個のｎ₂長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにするデータ振り分け手段とを有し、上記ｍ個のｎ₂長フーリエ変換手段を用いてｎ₁回のｎ₂長フーリエ変換処理を並列に行うとともに、上記ｍ個のｎ₁長フーリエ変換手段を用いてｎ₂回のｎ₁長フーリエ変換処理を並列に行うようにし、上記データ振り分け手段によって同一サイクルで振り分けられたｍ個のデータに対して、同じｎ₁長フーリエ変換手段を用いて互いに異なるサイクルでｎ₁長フーリエ変換処理を行うようにしたことを特徴とする。

本発明は、上記技術手段より成り、周期Ｎの時間成分の信号が周期Ｎのフーリエ変換によって一度に周波数変換されるのではなく、上記周期Ｎよりも小さな周期ｎ₁、ｎ₂のフーリエ変換の組み合わせによって周波数変換されることとなるので、フーリエ変換演算の性質上、上記小さな周期ｎ₁、ｎ₂のフーリエ変換でそれぞれ行われる演算量は、上記周期Ｎのフーリエ変換で行われる演算量に比べて格段に少ないものとなり、上記小さな周期ｎ₁、ｎ₂のフーリエ変換で行われる各演算量と回転演算で行われる演算量とを合計しても、上記周期Ｎのフーリエ変換によって一度に周波数変換を行うようになされた従来のＤＦＴの演算量よりも演算量が少なくなる。また、上記小さな周期ｎ₁、ｎ₂のフーリエ変換をｍ個のｎ₂長フーリエ変換手段及びｎ₁長フーリエ変換手段を用いて並列に行うようにするとともに、同じ数の中間バッファメモリを用意して、複数サイクルに亘って同じｎ₂長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ₁長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして、上記ｍ個のｎ₂長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにし、さらに上記データ振り分け手段によって同一サイクルで振り分けられたｍ個のデータに対して、同じｎ₁長フーリエ変換手段を用いて互いに異なるサイクルでｎ₁長フーリエ変換処理を行うようにしたので、演算サイクル数が少なくなるとともに、中間バッファメモリへのアクセスも効率よく並列化することが可能となり、アクセスタイムを格段と短くすることが可能となる。

本発明によれば、周期Ｎ（＝ｎ₁×ｎ₂）の時間成分の信号の周波数解析を、上記周期Ｎよりも小さな周期である横方向に対する周期ｎ₁のフーリエ変換と縦方向に対する周期ｎ₂のフーリエ変換との組み合わせによって行うようにして、上記小さな周期ｎ₁、ｎ₂のフーリエ変換をｍ個のｎ₂長フーリエ変換手段及びｎ₁長フーリエ変換手段を用いて並列に行うとともに、同じ数の中間バッファメモリを用意して、複数サイクルに亘って同じｎ₂長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ₁長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして、上記ｍ個のｎ₂長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにし、さらに上記データ振り分け手段によって同一サイクルで振り分けられたｍ個のデータに対して、同じｎ₁長フーリエ変換手段を用いて互いに異なるサイクルでｎ₁長フーリエ変換処理を行うようにしたので、上記周期Ｎのフーリエ変換によって一度に周波数変換を行うようになされた従来のＤＦＴの演算量よりも演算量を少なくすることができる。また、演算サイクル数を少なくすることができるとともに、中間バッファメモリへのアクセスを効率よく並列化してアクセスタイムを短くすることができる。これにより、全体としての中間バッファメモリの容量を格段に小さくすることができるとともに、フーリエ変換の処理速度を高速にすることができる。

以下、本発明の一実施例を図面に基づいて説明する。時間成分の信号を周波数成分の信号に周期Ｎで変換するための処理、すなわちＮ点ＤＦＴの処理を、従来は図２（０）に示すようにＮ長フーリエ変換で一度に行っていた。これに対し、本実施例のフーリエ変換装置では、図２（ａ）〜（ｅ）に示すように第１〜第５のフェーズに分けて行っている。

すなわち、第１のフェーズでは、図２（ａ）に示すように、入力される１次元状のＮ個のデジタル信号を横ｎ₁個×縦ｎ₂個の２次元状の配置に並べ替える。第２のフェーズでは、図２（ｂ）に示すように、上記並べ替えた２次元状のデータ配置において、縦方向に対するｎ₂個のデータを用いてｎ₂長ＤＦＴ処理を横方向の数ｎ₁だけ行う。

次に、第３のフェーズでは、図２（ｃ）に示すように、上記ｎ₂長ＤＦＴ処理で得られた結果に対して回転演算を施す。第４のフェーズでは、図２（ｄ）に示すように、上記回転演算の結果に対して、横方向に対するｎ₁個のデータを用いてｎ₁長ＤＦＴ処理を縦方向の数ｎ₂だけ行う。最後に、第５のフェーズでは、図２（ｅ）に示すように、上記ｎ₁長ＤＦＴ処理で得られた結果を１次元状のデータ配置に並べ替える。

図１は、本実施例によるフーリエ変換装置の構成を示す図であって、図２に示した５つのフェーズの処理を行うための構成を示す図である。図１において、１は第１の並べ替え手段であり、上記第１のフェーズの処理を行う。この第１の並べ替え手段１は、例えば、メモリとアドレッシング装置とにより簡単に構成することが可能である。この並べ替え処理を式で表すと、次の（式３）のようになる。

２はｎ₂長フーリエ変換手段であり、次の（式４）に従って上記第２のフェーズの処理を行う。すなわち、上記第１の並べ替え手段１で並べ替えられた２次元状のデータ配置において、縦方向に対するｎ₂長のＤＦＴ処理をｎ₁回行う。

３は回転演算手段であり、次に示す（式５）に従って上記第３のフェーズの処理を行う。すなわち、上記ｎ₂長フーリエ変換手段２による演算処理の結果得られたデータに対して回転演算を施す。

４は中間バッファメモリであり、上記ｎ₂長フーリエ変換手段２によりフーリエ変換されたデータを一時記憶する。上述の回転演算手段３は、この中間バッファメモリ４に記憶されたデータに対して回転演算を行い、その演算結果をｎ₁長フーリエ変換手段５に供給するようになされている。

上記ｎ₁長フーリエ変換手段５は、上記回転演算手段３による回転演算の結果得られるデータを用いて、次の（式６）に従って上記第４のフェーズの処理を行う。すなわち、上記並べ替えられた２次元状のデータ配置において、横方向に対するｎ₁長のＤＦＴ処理をｎ₂回行う。

６は第２の並べ替え手段であり、上記第５のフェーズの処理を行う。すなわち、上記ｎ₁長フーリエ変換手段５により求められたデータを次の（式７）に従って再び１次元状に並べ替えることにより、周波数成分の信号Ｓ_kを得る。なお、この第２の並べ替え手段６は、上記第１の並べ替え手段１と同様に、メモリとアドレッシング装置とにより構成することが可能である。

上記（式３）〜（式７）に示した５つのフェーズに分けて行っている本実施例のＤＦＴ処理は、従来の（式１）で行っているＤＦＴ処理と等価であり、同じ演算結果（同じ周波数成分の信号Ｓ_k）を得ることができる。一方、その演算結果を得るまでの演算量は、従来に比べて本実施例の方が少なくなっている。このことを以下に説明する。

本実施例のＤＦＴ処理における第１のフェーズと第５のフェーズの処理は、単なるデータの並べ替え処理（メモリアドレッシング処理）であるから、演算は行っていない。そこで、本実施例における総演算量は、第２〜第４のフェーズにおける各処理の演算量を合計したものとなる。次に示す表１は、その演算量を示したものである。

この表１から明らかなように、本実施例のＤＦＴ処理で行う乗算の回数は、４ｎ₁ｎ₂（ｎ₁＋ｎ₂＋１）回であり、加減算を行う回数は、２ｎ₁ｎ₂（２ｎ₁＋２ｎ₂＋１）回である。一方、従来例のところで述べたように、従来のＤＦＴ処理で行う乗算の回数は、４Ｎ²＝４ｎ₁ ²ｎ₂ ²回である。また、加減算を行う回数は、２Ｎ²＋２Ｎ（Ｎ−１）＝４ｎ₁ ²ｎ₂ ²−２ｎ₁ｎ₂回であり、２ｎ₁ｎ₂は殆ど無視できるほど小さいと考えてよいから、結局４ｎ₁ ²ｎ₂ ²回である。

乗算を行う回数および加減算を行う回数をそれぞれ本実施例と従来とで比較してみれば分かるように、ｎ₁とｎ₂の値を共に３以上とすれば、本実施例のＤＦＴ処理における演算量を従来のＤＦＴ処理における演算量よりも確実に少なくすることができる。

次に、本実施例のＤＦＴ処理と従来のＦＦＴ処理とを比較してみると、従来のＦＦＴは、本実施例のＤＦＴの特別な例であると言える。すなわち、本実施例のＤＦＴでは、実演算を第２〜第４のフェーズの３段に分離して行っている。これに対し、従来のＦＦＴは、第２のフェーズと第３のフェーズまたは第３のフェーズと第４のフェーズとを一まとめにして演算の流れを再配置し、バタフライ演算という形にまとめて行うものである。

このため、演算量の観点からすれば、本実施例のＤＦＴと従来のＦＦＴとで差ほど変わりはないと言える。ところが、各フェーズの処理をパイプライン化して並列に行う場合に必要な中間バッファメモリの容量という観点からすると、本実施例のＤＦＴでは、従来のＦＦＴよりも格段に小さいメモリ容量で済むというメリットがある。

すなわち、本実施例の場合、上記中間バッファメモリ４に必要なメモリ容量はｎ₁×ｎ₂ワード分である。さらに、第２のフェーズにおけるｎ₁長ＤＦＴ処理の周期ｎ₁を更に細かく分離して横方向ｎ₁₁、縦方向ｎ₁₂（ｎ₁＝ｎ₁₁×ｎ₁₂）として処理することとすれば、その中間部にｎ₁₁×ｎ₁₂ワード分のメモリが必要になる。また、第４のフェーズにおけるｎ₂長ＤＦＴ処理の周期ｎ₂を更に細かく分離して横方向ｎ₂₁、縦方向ｎ₂₂（ｎ₂＝ｎ₂₁×ｎ₂₂）として処理することとすれば、その中間部にｎ₂₁×ｎ₂₂ワード分のメモリが必要になる。

以下同様にして、更に細かく周期を分離して縦方向のＤＦＴ処理と横方向のＤＦＴ処理とを行うようにすれば、例えばＮ＝２¹⁶点の周波数解析を行う場合、各中間バッファメモリで必要なメモリ容量は、図３（ａ）の各四角の中に示す数字のようになる。したがって、中間バッファメモリの全メモリ容量は、各中間バッファメモリのメモリ容量を合計して、６６１７６ワード分となる。

もちろん、図３（ａ）に示したように周期が最も小さくなるまで細分化する必要は必ずしもなく、その場合に必要なメモリ容量は、上記６６１７６ワードよりも小さくなる。

一方、従来のＦＦＴでは、数段階のバタフライ演算によって周波数解析を実施しているが、上述したように各バタフライ演算の基数は小さい値しかとることができない。そこで、基数を２とした場合に各中間バッファメモリとして必要なメモリ容量を、図３（ｂ）に示した。この図３（ｂ）から、中間バッファメモリとして必要な全メモリ容量は、１３１１０２ワード分であることが分かる。

図３（ａ）と図３（ｂ）とを比較すれば明らかなように、本実施例のＤＦＴ処理によれば、各フェーズの処理を並列化動作させる場合に必要な中間バッファメモリのメモリ容量を、従来のＦＦＴで各バタフライ演算を並列化動作させる場合に必要なメモリ容量よりも小さくすることができる。

以上説明したように、本実施例のフーリエ変換装置によれば、一連のフーリエ変換処理にかかる演算量を少なくすることができ、しかも、各フェーズを並列化動作させた場合に使用する中間バッファメモリの全メモリ容量を小さくすることもできるようになる。

なお、以上の実施例では、第１の並べ替え手段１と第２の並べ替え手段６とを含めたものを１つのフーリエ変換装置として扱っているが、このようなデータの並べ替えを行う手段が外部に存在すれば、これらの手段はフーリエ変換装置内に必ずしも設ける必要はない。

以上のような本実施例のフーリエ変換装置を利用して、以下に述べる幾つかの応用例を実現することができる。

まず第１番目の例は、ある小さな周期のフーリエ変換装置を２個直列に設けるとともに、その間に小規模の回転演算装置を付加することにより、より大きな周期のフーリエ変換装置を構成したものである。

例えば、図４に示すように、ｎ₂長ＤＦＴ装置１１とｎ₁長ＤＦＴ装置１４とを直列に設けるとともに、その間に回転演算装置１２と（ｎ₁×ｎ₂）ワード分の容量を持つ中間バッファメモリ１３とを付加することにより、Ｎ＝ｎ₁×ｎ₂長の大きな周期のＤＦＴ装置を構成する。そして、ｎ₂長ＤＦＴとｎ₁長ＤＦＴとをパイプライン処理することにより、Ｎ点の周波数解析を実施する。

上述したように、大きな周期Ｎの周波数解析を１個のＤＦＴ装置で一度に行うのは演算負荷が非常に大きいのに対して、小さな周期ｎ₁、ｎ₂の組み合わせで周波数解析を行うのは演算負荷が小さい。したがって、本装置によれば、全体としての処理速度を高速にすることができるというメリットがある。

第２番目の例は、第２のフェーズにおけるｎ₂長ＤＦＴ処理と第４のフェーズにおけるｎ₁長ＤＦＴ処理とがそれぞれ独立性が高いことを利用して、上記ｎ₂長ＤＦＴ処理を行う装置と上記ｎ₁長ＤＦＴ処理を行う装置とをそれぞれ複数個ずつ設けて１つのフーリエ変換装置を構成したものである。

例えば、図５に示すように、ｍ₁(ワード／秒) の演算能力を持つｎ₂長ＤＦＴ装置２１ａ，２１ｂ，…，２１ｃをｌ₁個設けてｎ₂長ＤＦＴ装置群２１を構成するとともに、ｍ₂(ワード／秒) の演算能力を持つｎ₁長ＤＦＴ装置２４ａ，２４ｂ，…，２４ｃをｌ₂個設けてｎ₁長ＤＦＴ装置群２４を構成する。

そして、上記ｎ₂長ＤＦＴ装置群２１と上記ｎ₁長ＤＦＴ装置群２４との間にｍ₃(ワード／秒) の演算能力を持つ回転演算装置２２と（ｎ₁×ｎ₂）ワード分の容量を持つ中間バッファメモリ２３とを設けることにより、１つのフーリエ変換装置を構成する。

既に説明したように、第２のフェーズではｎ₂長ＤＦＴ処理をｎ₁回行う必要がある。そこで、ｎ₂長ＤＦＴ装置群２１を構成するｎ₂長ＤＦＴ装置２１ａ，２１ｂ，…，２１ｃをｎ₁個、あるいは適当な数で割った個数だけ設けることにより、ｎ₁回のｎ₂長ＤＦＴ処理を並列に行うようにする。これにより、ｎ₂長ＤＦＴ処理をより短時間で行うようにすることができる。

例えば、ｎ₁＝４の場合、先に示した図４の例のように、１個のｎ₂長ＤＦＴ装置１１でｎ₁回のｎ₂長ＤＦＴ処理を行うのでは４サイクルかかっていたのに対し、ｎ₂長ＤＦＴ装置を２個設ければ２サイクルで行うことができる。また、ｎ₂長ＤＦＴ装置を４個設ければ、１サイクルで行うことができる。

また、第４のフェーズについても同様に、ｎ₁長ＤＦＴ装置群２４を構成するｎ₁長ＤＦＴ装置２４ａ，２４ｂ，…，２４ｃをｎ₂個、あるいは適当な数で割った個数だけ設けることにより、ｎ₂回のｎ₁長ＤＦＴ処理を行う際の演算サイクル数を少なくすることができる。これにより、より高速なフーリエ変換装置を得ることができる。

なお、上記ｎ₂長ＤＦＴ装置群２１の全体としての演算能力はｌ₁×ｍ₁(ワード／秒) であり、上記ｎ₁長ＤＦＴ装置群２４の全体としての演算能力はｌ₂×ｍ₂(ワード／秒) である。ここで、ｍ₃≦ｌ₁×ｍ₁ あるいはｍ₃≦ｌ₂×ｍ₂が成立すると、上記ｎ₂長ＤＦＴ装置群２１およびｎ₁長ＤＦＴ装置群２４は、ｍ₃(ワード／秒) の演算能力に制限される。

第３番目の例は、ある小さな周期のフーリエ変換装置を複数個用い、それらを回転演算装置を介して積み重ねるようにして接続する（イメージとしては、図３（ａ）に示したツリー構造となるように接続する）ことにより、より大きな周期のフーリエ変換装置を構成したものである。

例えば、複数個の４点フーリエ変換装置を用いて、より大きな周期の４０９６点フーリエ変換装置を構成する場合について考える。この場合、図６に示すように、４０９６点フーリエ変換装置は、大きく分けて１６点フーリエ変換装置３１と、４０９６点回転演算装置３２と、４０９６ワード分の容量を持つ４０９６点バッファメモリ３３と、２５６点フーリエ変換装置３４とにより構成される。

そして、上記１６点フーリエ変換装置３１は、２つの４点フーリエ変換装置３１ａ，３１ｄと、１６点回転演算装置３１ｂと、１６ワード分の容量を持つ１６点バッファメモリ３１ｃとにより構成される。また、上記２５６点フーリエ変換装置３４は、２つの１６点フーリエ変換装置３４ａ，３４ｄと、２５６点回転演算装置３４ｂと、２５６ワード分の容量を持つ２５６点バッファメモリ３４ｃとにより構成される。

さらに、上記２５６点フーリエ変換装置３４内にある一方の１６点フーリエ変換装置３４ａは、上記１６点フーリエ変換装置３１と同様に、２つの４点フーリエ変換装置３４ａ₁，３４ａ₄と、１６点回転演算装置３４ａ₂と、１６ワード分の容量を持つ１６点バッファメモリ３４ａ₃とにより構成される。

他方の１６点フーリエ変換装置３４ｄについても上記１６点フーリエ変換装置３１と同様に、２つの４点フーリエ変換装置３４ｄ₁，３４ｄ₄と、１６点回転演算装置３４ｄ₂と、１６ワード分の容量を持つ１６点バッファメモリ３４ｄ₃とにより構成される。

このように、小さな周期の４点フーリエ変換装置を複数個用い、それらを回転演算装置を介してツリー構造となるように接続することにより、より大きな周期の４０９６点フーリエ変換装置を構成している。なお、本装置において用いられている各回転演算装置は、ツリーの枝を結ぶ乗算の役目を果たしている。

つまり、この図６に示した装置では、４０９６点の周波数解析を、縦１６点×横２５６点に分割して行う。そして、縦１６点の周波数解析を行う際には、更に縦４点×横４点に分割して行う。また、横２５６点の周波数解析を行う場合も同様にして、縦４点×横４点のフーリエ変換にまで細分化して行う。

４０９６点の周波数解析を１個の４０９６点フーリエ変換装置で一度に行うのは演算負荷が非常に大きいが、小さな周期の４点フーリエ変換装置の組み合わせで周波数解析を行うのは演算負荷が小さいことは上述した通りである。したがって、本装置によれば、全体としての演算負荷を小さくして処理速度を高速にすることができる。

また、本装置において用いている中間バッファメモリの総メモリ容量は、4096＋16＋256 ＋16＋16＝4440ワードである。これに対して、従来のＦＦＴにより４０９６点フーリエ変換装置を構成すると、各バタフライ演算の基数を４とした場合でも、バッファメモリの総メモリ容量は、4096＋1024＋256 ＋64＋16＋4 ×6＝5480ワードである。

以上のことから明らかなように、図６の装置によれば、４０９６点のＤＦＴ処理にかかる演算量を少なくしてＦＦＴと同程度にまで処理時間を短くすることができるだけでなく、演算の過程で使用する中間バッファメモリのメモリ容量を、ＦＦＴを行う場合に比べて小さくすることもできている。

第４番目の例は、図６に示した第３番目の例を応用した例である。すなわち、窓かけ演算にも流用できるようにした回転演算装置と１６点フーリエ変換装置とを用いて１つのフーリエ変換装置を構成する。そして、これをタイムシェアリング（時分割）で用いることにより、より大きな周期（４０９６点）の周波数解析を行うことができるようにしたものである。

フーリエ変換は、数学上の話では本来は無限長の周期で行うものである。しかし、これを実際に行うのは現実問題として無理である。そこで、実際には、周期Ｎで一定区間を区切り、その端点をつなげることによって無限長とみなして周波数解析を行っている。ところが、この場合に、端点に不連続点が存在すると、正常でない周波数成分、すなわち、周波数もれ成分が生じることがある。

上述した窓かけ演算は、この端点の不連続点をなくし、周波数もれ成分を少なくすることを目的として行われるものであり、次の（式８）に示す演算式によって行われる。なお、（式８）中のＳ_kはフーリエ解析するデータ、ｗ(k) は窓関数、Ｓ_k' は実サンプルデータを示している。

ところで、この窓かけ演算は、精密ではないが、次の（式９）に示す回転演算とほぼ同じと考えることができる。したがって、係数をうまく与えれば、回転演算装置を用いて窓かけ演算を行うことが可能である。そこで、この第４番目の例では、回転演算装置を窓かけ演算にも流用できるようにしている。

図７は、この第４番目の例を実現するための装置の構成を示す図である。図７に示したように、本装置は、窓かけ演算にも流用可能な窓かけ／回転演算装置４１と、１６点フーリエ変換装置４２と、４０９６ワード分の容量を持つ４０９６点バッファメモリ４３と、２５６ワード分の容量を持つ２５６点バッファメモリ４４と、データ入力部４５と、データ出力部４６とにより構成されている。

上記回転演算装置４１は、窓かけ演算を行う際に適当な係数を与える手段を具備している。また、上記１６点フーリエ変換装置４２は、図６中に示した各１６点フーリエ変換装置と同様に、２つの４点フーリエ変換装置４２ａ，４２ｄと、１６点回転演算装置４２ｂと、１６点バッファメモリ４２ｃとにより構成されている。

このように構成したフーリエ変換装置は、図６中にα、β、γで示した部分（何れの部分も１６点フーリエ変換装置と回転演算装置、あるいは１６点フーリエ変換装置と窓かけ演算装置とを含んでいる）の処理を時分割で行うことにより、４０９６点の周波数解析を実施する。

すなわち、図８に示すように、まず最初に、データ入力部４５を介して入力されるデータを用いて、図６中のαの部分に相当する演算が行われる。このとき、窓かけ／回転演算装置４１では、適当な係数が与えられることにより窓かけ演算が行われる。このαの部分の演算結果は、データ出力部４６を介して４０９６点バッファメモリ４３に順次格納される。

そして、この４０９６点バッファメモリ４３にデータがたまると、次にそのデータがデータ入力部４５を介して入力され、図６中のβに相当する演算が行われる。このβの部分の演算結果は、データ出力部４６を介して２５６点バッファメモリ４４に順次格納される。次に、この２５６点バッファメモリ４４にデータがたまると、そのデータがデータ入力部４５を介して入力され、図６中のγに相当する演算が行われる。

このように、図７の装置によれば、小さな周期のフーリエ変換の組み合わせによって大きな周期のフーリエ変換を行っているので、４０９６点のＤＦＴ処理にかかる演算量を少なくして処理時間を短くすることができる。さらに、図６の装置と異なり、同じ装置を時分割で何度も用いているので、図６の装置に比べて、４点フーリエ変換装置や中間バッファメモリの使用数を減らすことができ、装置全体の規模を小さくすることができる。

第５番目の例は、高速ページモードを持つメモリを用いて中間バッファメモリを構成し、その高速ページモードを持つメモリに中間バッファメモリを配置するときに、ストライプ状に配置するのではなく、縦横のブロック状に配置することにより、メモリアクセスタイムを短くできるようにしたものである。

一般に、高速ページモードを持つＩＣメモリは、２次元マトリクス状に作製される。そして、その行（カラム）と列（ロウ）とで位置を指定することにより所望のデータを得るようになされている。この場合、ＤＲＡＭに代表されるメモリでは、その機構上の特徴により、先にロウアドレスを指定し、次にカラムアドレスを指定するようになっている。

そして、高速ページモードでは、同じロウアドレスについてカラムアドレスを連続して指定する場合には、異なるロウアドレスについてカラムアドレスを指定する場合に比べて高速にアクセスすることができるようになっている。このような高速ページモードを持つメモリの一例として、日立製のメモリ（HM511OOOA-6）がある。

ところで、上述したように、本実施例のフーリエ変換装置では、第２のフェーズで縦方向に対するＤＦＴ処理を行い、第４のフェーズで横方向に対するＤＦＴ処理を行っている。このため、２次元状に作られた中間バッファメモリの縦方向と横方向に対してそれぞれデータの読み書きを行っている。

ここで、中間バッファメモリ４を横方向にストライプ状に配置した場合には、縦方向に対する高速ページモードが使えないので、横方向に対するメモリアクセスタイムは速いが、縦方向に対するメモリアクセスタイムが遅くなってしまう。一方、ブロック状に配置すれば、縦方向に対するデータの読み書き時に高速ページモードが使えるので、横方向に対するアクセスタイムも縦方向に対するアクセスタイムも共に速くすることができるようになる。

図９は、上記した日立製のメモリのアクセスタイムの様子を示すタイムチャートである。この図９の例では、同じロウアドレスについて２つのカラムアドレスを連続して指定した場合について示している。

すなわち、通常、１ワードのアクセスを行うのにかかる時間（サイクルタイム）は１２０ｎｓｅｃであるのに対して、高速ページモードにおいて２ワードのアクセスを行うのにかかる時間は１５５（＝６０＋４５＋５０）ｎｓｅｃである。つまり、１ワード当たりでは、７７．５ｎｓｅｃと通常時よりもアクセス時間が短くなっていることが図９から読み取れる。

このような日立製のメモリを中間バッファメモリとして用いた場合の具体例を次に示す。なお、ここでは、中間バッファメモリの全メモリ容量は２¹⁸ワード（縦２⁹ワード×横２⁹ワード）であるとする。

まず、図１０に示すように、中間バッファメモリを２⁹ワード分ずつ横方向にストライプ状に配置する場合について考える。この場合、第２のフェーズで求められたデータを中間バッファメモリに縦方向に書き込む際には、高速ページモードが使えないので、縦方向に対して１ワード当たり１２０ｎｓｅｃの時間がかかる。

また、第４のフェーズにおいて上記中間バッファメモリからデータを読み出す際に、横方向に対して１ワード当たりにかかるアクセス時間は、（６０＋４５×（２⁹−１）＋５０）／２⁹≒４５．１３ｎｓｅｃである。よって、メモリアクセスに関するデータレートの上限は、１２０＋４５．１３＝１６５．１３ｎｓｅｃ／ワードとなる。

次に、図１１に示すように、中間バッファメモリを２⁹ワード分ずつブロック状（縦２⁴個×横２⁵個）に配置する場合について考える。この場合、縦方向に対するメモリアクセス時に高速ページモードを使うことが可能であるので、第２のフェーズで求められたデータを中間バッファメモリに書き込む際にかかる時間は、縦方向に対して１ワード当たり（６０＋４５×１５＋５０）／１６≒４９．０６ｎｓｅｃである。

また、第４のフェーズにおいて上記中間バッファメモリからデータを読み出す際に、横方向に対して１ワード当たりにかかるアクセス時間は、（６０＋４５×３１＋５０）／３２≒４７．０３ｎｓｅｃである。よって、メモリアクセスに関するデータレートの上限は、４９．０６＋４７．０３＝９６．０９ｎｓｅｃ／ワードとなる。

以上の計算結果から明らかなように、中間バッファメモリをブロック状に配置することにより、ストライプ状に配置する場合に比べてメモリアクセス時間を短くすることができる。これにより、上述したようにフーリエ変換処理を行う際の演算量を減らすことができるだけでなく、処理の過程で使用する中間バッファメモリへのアクセス時間を削減することもできるようになり、全体としての処理時間を更に短くすることができる。

第６番目の例は、第２のフェーズの処理と第４のフェーズの処理とを並列に動作させる場合に、中間バッファメモリにデータを読み書きする際のアドレッシング動作を工夫することにより、中間バッファメモリを１ページ分だけ用意すれば済むようにしたものである。

第４のフェーズの処理を行う際には、第２のフェーズで求められたデータを用いるため、第２のフェーズの処理が終わらなければ第４のフェーズの処理は行うことができない。したがって、第２のフェーズの処理と第４のフェーズの処理とを並列に動作させる場合は、通常は、図１２に示すように、第２のフェーズ用と第４のフェーズ用との２ページ分の中間バッファメモリが必要になる。

すなわち、第２のフェーズと第４のフェーズとを並列動作させる場合には、図１２（ａ）に示すように、第２のフェーズにおける縦方向のＤＦＴ処理で求められるデータを縦方向に順次記憶していくと同時に、図１２（ｂ）に示すように、既に求められたデータを第４のフェーズにおいて横方向に読み出して横方向のＤＦＴ処理を順次行っていく必要がある。

したがって、第２のフェーズで求められるデータを縦方向に順次記憶していくためのページと、第４のフェーズでデータを横方向に読み出して使用するためのページとの２ページが中間バッファメモリとして必要になる。しかし、このように中間バッファメモリを２ページも用意したのでは、メモリ容量が非常に大きくなってしまう。

そこで、この第６番目の例では、今までのように第２のフェーズで求められたデータは縦方向に書き込み、第４のフェーズの処理ではデータを横方向に読み出すというように一定としないで、図１３に示すように、１回目に行う第２、第４のフェーズではデータを縦方向に読み書きする。２回目に行う第２、第４のフェーズではデータを横方向に読み書きするというように、アドレッシングの方向を縦と横で交互に切り換えていくようにする。

すなわち、図１３（ａ）において、１回目に行う第４のフェーズの処理では、中間バッファメモリに既に記憶されているデータ（この第４のフェーズの処理よりも前に行われた０回目の第２のフェーズの処理で求められたデータ）が縦方向に順次読み出される。

そして、この第４のフェーズの処理と同時に行われている１回目の第２のフェーズの処理で求められたデータが、上記読み出しによって空になった縦方向の領域に順次書き込まれる。すると、最終的には、中間バッファメモリの全ての領域に、１回目の第２のフェーズの処理で求められたデータが記憶される。

次に、図１３（ｂ）において、２回目に行う第４のフェーズの処理では、中間バッファメモリに記憶されているデータ（上記１回目の第２のフェーズの処理で求められたデータ）が横方向に順次読み出される。

そして、この第４のフェーズの処理と同時に行われている２回目の第２のフェーズの処理で求められたデータが、上記読み出しによって空になった横方向の領域に順次書き込まれる。すると、最終的には、中間バッファメモリの全ての領域に、２回目の第２のフェーズの処理で求められたデータが記憶される。この後は、再び図１３（ａ）に示す処理が行われる。

以上のように、アドレッシングの方向を交互に切り換えてデータの読み書きを行うようにすれば、データを読み出して空きになった領域を有効に活用して、１つの中間バッファメモリを第２のフェーズ用と第４のフェーズ用とで共用することができ、中間バッファメモリを１ページ分だけ用意すれば済むようになる。

第７番目の例は、図５に示した第２番目の例を応用した例である。図５に示したように複数のＤＦＴ装置を用いて処理を並列化させた場合には、中間バッファメモリ２３へのアクセスが非常に多くなる。そこで、この第７番目の例は、上記中間バッファメモリ２３を複数のメモリに分割して用意するとともに、クロスバスイッチなどのデータ振り分け装置を用いることにより、メモリアクセス時における並列動作性を高めることができるようにしたものである。

図１４は、この第７番目の例を実現するための装置の構成を示す図である。なお、この図１４に示す装置は、図５に示した装置を変形したものであり、図５中に示した周期ｎ₁、ｎ₂の値をそれぞれ４とし、ｎ₁長ＤＦＴ処理を行う装置の数ｌ₁、ｎ₂長ＤＦＴ処理を行う装置の数ｌ₂をそれぞれ４個とした場合について示したものである。

すなわち、本装置は、第２のフェーズの処理を行う４個の４点フーリエ変換装置５１ａ，５１ｂ，５１ｃ，５１ｄと、データ振り分け装置５２と、並列動作可能な４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄと、第４のフェーズの処理を行う４個の４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄとにより構成される。なお、ここでは、説明の簡略化のため、回転演算装置は図示を省略している。

次に、上記のように構成した装置の動作を、図１５に示す中間データの配置図を参照しながら説明する。本装置では、第２のフェーズで縦方向に４点フーリエ変換を行い、第４のフェーズで横方向に４点フーリエ変換を行うことにより、第１〜第１６ワード（図１５に丸付の数字で示している）の１６点周波数解析を実行する。

このとき、上述した第２のフェーズの処理を行う４個の４点フーリエ変換装置５１ａ，５１ｂ，５１ｃ，５１ｄは、それぞれ図１５の縦方向に対するデータを用いてフーリエ変換を同時に行う。これにより、第１サイクルでは、第１、第２、第３、第４ワードについてフーリエ変換されたデータが同時に得られる。

このようにして同時に得られた４個のデータは、データ振り分け装置５２により４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに１ワードずつ振り分けられて記憶される。ここで、各ワードのデータが記憶される中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄの種類を、それぞれＡ〜Ｄの符号を付して示した。

通常、４個のデータを１個の中間バッファメモリに書き込むためには、４サイクル必要であるが、本実施例では、４個のデータを４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに振り分けて書き込むようにしているので、１サイクルで書き込みを行うことができる。

また、第２サイクル〜第４サイクルの各サイクルで同時にフーリエ変換されたデータについても同様に、データ振り分け装置５２により４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに１ワードずつ振り分けられて記憶される。このとき、同じフーリエ変換装置で変換されたデータが同じ中間バッファメモリ内に記憶されないように振り分けが行われる。

以上のような書き込み動作により、４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄには、図１５に示すような関係で各ワードのデータが記憶されることになる。すなわち、第１の中間バッファメモリ５３ａには、第１、第６、第１１、第１６ワードのデータが記憶され、第２の中間バッファメモリ５３ｂには、第５、第１０、第１５、第４ワードのデータが記憶される。

また、第３の中間バッファメモリ５３ｃには、第９、第１４、第３、第８ワードのデータが記憶され、第４の中間バッファメモリ５３ｄには、第１３、第２、第７、第１２ワードのデータが記憶される。

次に、第４のフェーズの処理を行う際には、上述した第４のフェーズの処理を行う４個の４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄは、それぞれ図１５の横方向に対するデータを用いてフーリエ変換を同時に行う。すなわち、第１サイクルでは、上記４個の４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄは、それぞれ第１、第５、第９、第１３ワードのデータを読み出してフーリエ変換を同時に行う。

この場合、図１５から明らかなように、各４点フーリエ変換装置５４ａ，５４ｂ，５４ｃ，５４ｄで同時に使用する４個のデータは、上記４個の中間バッファメモリ５３ａ，５３ｂ，５３ｃ，５３ｄに１ワードずつ分散して記憶されている。したがって、１個の中間バッファメモリに上記４個のデータが全て記憶されていたとしたなら読み出しに４サイクルかかるところを、本実施例では、１サイクルで読み出すことができる。

以上説明したように、図１４に示した第７番目の例の装置によれば、複数のフーリエ変換装置を用いてＤＦＴ処理を並列化動作させた場合に、中間バッファメモリへのアクセスも効率よく並列化させることができ、装置全体の並列動作性を向上させることができる。なお、参考のために、上述したデータの読み書きの手順を、図１６に示しておく。

本発明の一実施例であるフーリエ変換装置の構成を示すブロック図である。図１のフーリエ変換装置によって行われる第１〜第５のフェーズの処理内容を説明するための図である。本実施例のフーリエ変換装置をツリー構造にした場合に必要な中間バッファメモリの容量を、ＦＦＴの各バタフライ演算を並列化動作させた場合に必要な中間バッファメモリの容量と比較するための図である。第１番目の応用例による装置の構成を示す図である。第２番目の応用例による装置の構成を示す図である。第３番目の応用例による装置の構成を示す図である。第４番目の応用例による装置の構成を示す図である。図７に示した装置によって行われる時分割処理の様子を説明するための図である。第５番目の応用例で使用される高速ページモードを持つ中間バッファメモリのアクセスタイムの様子を示すタイムチャートである。中間バッファメモリをストライプ状に配置した様子を示す図である。中間バッファメモリをブロック状に配置した様子を示す図である。２ページ分の中間バッファメモリを用いてデータの読み書きを行う様子を説明するための図である。第６番目の応用例によるデータの読み書きの様子を説明するための図であり、１ページ分の中間バッファメモリを用いてデータの読み書きを行う様子を説明するための図である。第７番目の応用例による装置の構成を示す図である。複数の中間バッファメモリとそれに記憶されるデータとの関係を説明するための図である。第７番目の応用例によるデータの読み書きの手順を示す図である。

符号の説明

１第１の並べ替え手段
２ｎ₂長フーリエ変換手段
３回転演算手段
４中間バッファメモリ
５ｎ₁長フーリエ変換手段
６第２の並べ替え手段

Claims

横方向に周期ｎ₁、縦方向に周期ｎ₂の２次元状に配置された周期Ｎ（＝ｎ₁×ｎ₂）の時間成分の信号に対して、縦方向に対する周期ｎ₂のフーリエ変換を行うｍ個のｎ₂長フーリエ変換手段と、
上記ｍ個のｎ₂長フーリエ変換手段による変換結果を一時記憶するためのｍ個の中間バッファメモリと、
上記ｍ個の中間バッファメモリに記憶されたデータに対して回転演算を施す回転演算手段と、
上記回転演算手段による演算結果に対して、横方向に対する周期ｎ₁のフーリエ変換を行うｍ個のｎ₁長フーリエ変換手段と、
複数サイクルに亘って同じｎ₂長フーリエ変換手段により求められたデータが同じ中間バッファメモリ内に記憶されることがないようにするとともに、同じｎ₁長フーリエ変換手段により使用されるデータが同じ中間バッファメモリ内に記憶されることがないようにして、上記ｍ個のｎ₂長フーリエ変換手段によりそれぞれ求められたｍ個のデータを上記ｍ個の中間バッファメモリに１個ずつ振り分けて記憶するようにするデータ振り分け手段とを有し、
上記ｍ個のｎ₂長フーリエ変換手段を用いてｎ₁回のｎ₂長フーリエ変換処理を並列に行うとともに、上記ｍ個のｎ₁長フーリエ変換手段を用いてｎ₂回のｎ₁長フーリエ変換処理を並列に行うようにし、上記データ振り分け手段によって同一サイクルで振り分けられたｍ個のデータに対して、同じｎ₁長フーリエ変換手段を用いて互いに異なるサイクルでｎ₁長フーリエ変換処理を行うようにしたことを特徴とするフーリエ変換装置。