デジタルフーリエ変換とＦＦＴ

前章では、連続的な一次元空間である時間軸を考え、その一部または全体で定義された曲線的な関数に対して、フーリエ変換というものを考えました。

ただし、通信技術はどんどんデジタル化されています。

すなわち空間は連続的でなく、離散的な空間でサンプリングされたようなデータを扱うことになります。

その各サンプリング点におけるデータも、物理量そのものというより、それを何ビットかで量子化したものとなっています。

通信ではありませんが、これはＬＰレコードとＣＤを比較すればわかるでしょう。

ＬＰの場合、時間とほぼ等価なのは溝内の位置ですが、これは連続しています。

そこに音声信号にしたがって凹凸があるわけですが、その凹凸量も、特に単位となる大きさが決まっているわけではありません。

これに対してＣＤ（元々の規格）の場合、１秒を約４万４千回に分けてそこでのみ信号を与えるとともに、個々の信号値は左右合計32ビットで量子化されています。

量子化はともかく、このようにサンプリングされた数字列は、普通の意味でフーリエ変換を行っても意味がありません。

その代わりに行われるのがＤＦＴと略されることの多い、デジタルフーリエ変換です。

サンプリング点を0, 1, 2, ... , N-1で表わし、それぞれの点で数字列ｆ0, ｆ1, ｆ2, ... , ｆN-1が与えられているとします。

この時、ＤＦＴされた結果はやはりN個の数字列であり、その値は以下のように与えられます。

ただしΣは0からN-1までのkに対して和をとることに相当します。

Ｆj ＝ Σｆk * exp(-2πijk/N)～jは0, 1, 2, ... , N-1逆にＦjの各値からｆkの各値を求めることができます。

これはデジタルフーリエ逆変換（ＩＤＦＴ）です。

これに対して、ＦＦＴあるいは高速フーリエ変換という言葉を聞いたことがあるかもしれません。

ある特定のjに対し、Ｆjを計算するために、ｆkと何かの乗算を、N回程度行う必要があります（複素数なので正しくは2N回ですが、２倍の誤差を含めて「程度」という言葉を使います）。

そしてjの値自体、N個ありますから、結局すべてのＦjを求める（＝ＤＦＴを実行する）ためにはN×N回程度の乗算処理が必要となります。

しかしアルゴリズムを工夫することで、実は同じＤＦＴを、N×N回程度よりはるかに少ない回数の乗算処理で実行できるのです。

具体的にはN×logN回程度ということになります。

これが高速フーリエ変換です。

アルゴリズムを具体的にどう工夫するかは、信号処理などの教科書を参照してください。