| コラム13 FFTを理解する ●複素行列の因数分解を繰り返して高速化するFFT スマホアプリの「DFTのイメージ」におけるDFTは点数（N）が１０でしたが、Nの値は百以上になるのが一般的です。 DFTにおける複素乗算の回数はN^2 になります。よってNが増えるにつれて演算量が膨大になり、演算に時間がかかったり、ハードが大きくなったりします。それを解決するために提案されたアルゴリズムがFFT(Fast Fourier Transform、高速フーリエ変換)です。 ■点数が2の累乗なら劇的に乗算を減らせるFFT DFTの複素乗算回数がN^2であるのに対し、FFTのそれは(N/2) log2(N)になります。前出マンガの例では8^2 = 64回だったものが(8/2) log2(8) = 12回に低減されました（図1‐75）。 FFTの点数が256、512、1024・・・と増えていくとDFTとの差はさらに顕著になります（表1-1）。このようなFFTの発明により、波形のスペクトルが短時間で算出できるようになりました。 ● AB+AC = A(B+C) がFFTの基本 DFTの行列には「周期性」と「対称性」が強く存在します。それらを利用して複素行列を上手に「因数分解」するのがFFTの本質です。その手順はスマホアプリ「FFT−高速化のメカニズム」をじっくりご覧になれば分かると思います。 ●本稿で扱うFFTは「時間間引き」の手法 なおFFTには主に2種類の手法があります。本稿で説明したものはx[n]のnを偶数と奇数に分けたりしているため「時間間引き」の手法といいます。それに対しX[k]のkを偶数・奇数に分けていく手法を「周波数間引き」といいます。（＊） （＊）周波数間引きのFFTを説明する秀逸なJavaアプレット（井澤裕司氏のサイト）。 http://www7b.biglobe.ne.jp/~yizawa/InfSys1/basic/chap7/index.htm ●FFTはデータの入れ方に工夫が必要になる ただ図1-75を見ると、入力データx[n]はn=0から順に並んでいるわけではなく、上からx[0], x[4], x[2], x[6], x[1], x[5], x[3], x[7]となっています。実はこの並び方には、表1-2のような「ビットの並びが逆」という規則性があります。 表1-2 FFTはこの順序で入力データx[n]を読み出してバタフライ演算する
●データの入れ替えは意外と単純 「時間間引き」の手法のFFTでは、同表のような入力x[n]の並び替え（ビット逆順ソート）を行い、その後にバタフライ演算を実行します。また「周波数間引き」の手法のFFTでは、バタフライ演算の後、出力X[k]をビット逆順ソートするのが一般的です。 ●ビット逆順ソートで多少時間がかかるがFFTの方が断然速い 表1-1に示すように、Nが大きくなるにつれて演算量が大幅に低減されます。FFTには前処理として「ビット逆順ソート」が必要になりますが、それにかかる時間は微々たるものです。したがって昨今はほとんどの場合でFFTを適用します。 目次へ戻る |