FFT

高速フーリエ変換。

直交変換の一つで、離散フーリエ変換(DFT))のディジタル化信号周波数成分(スペクトル)を計算する演算処理を高速に行なうアルゴリズムの一つ。

フーリエ変換は信号解析に於いて最も基本となる技術で、相関関数や畳み込みなどに広く応用されている。しかし離散フーリエ変換(DFT)は定義式の通りに計算するとディジタル信号のデータ数の2乗に比例する時間がかかるため、必ずしも実用的ではなかった。フーリエ変換に用いる行列の要素W^kx(W=exp(i2π/n))の指数部kxは、mod nの演算が行なわれるため、同じ値が行列内に多く出現する。この性質を利用し、同じ演算をまとめる事で高速化を図ったのがFFT法である。但し、FFT法で計算できるのは一般にデータ数が2のn乗になっているものに限られる。例えばn=8の時は64回の演算が24回に短縮される。原理的には2のn乗でなくても良いが、2のn乗以外では効率が落ちてしまう。2のn乗の場合は、計算時間もクイックソートと同様にn×log(n)に比例する程度になる。

各種目的に使われ、オーディオ用途では "FFTアナライザー" という専門の測定器も存在する。高速とはいってもかなりの演算量を必要とするので、オーディオ信号をリアルタイムにFFT変換する場合、一般のCPUでは処理が追いつかず、別途DSPが必要になる場合が多い。

周波数分析したデータを元に逆変換を行なって元のデータを復元することも可能。さらにスペクトルのデータに対してある部分の周波数成分を欠落させたりすることで、非可逆圧縮やデータの加工も可能である。

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)