高速フーリエ変換

今週の講義は金曜日のみです。演習はありません。本日のテーマは高速フーリエ変換です。この言葉はいろいろなところで聞いたことがあるとおもいます。英語では Fast Fourie Transform、略称FFTとよび、先週学習した離散（逆）フーリエ変換のような変換の定義ではなく、計算の高速化をはかるアルゴリズムのことです。

データ長がNの離散データの離散フーリエ変換は回転子

を要素にもつN次元の複素行列WとN次元のデータベクトルx の積

によって記述できることを示しました。その回転子行列が固有の性質を持つことは、演習で確認したとおもいます。FFTはこの性質を巧みに計算アルゴリズムに取り入れたものです。前回の演習の時間（または復習）での最後の問題の計算は手を抜かずに自身で計算しましたか。 FFTのアルゴリズムを理解するために、まだ計算していない受講生は必ず確認してください。

このアルゴリズムの特徴を結論から説明していきましょう。なぜそうなるかより、どうしているのかを追求します。 FFTの計算アルゴリズムはバタフライ演算と呼ばれる独特の計算方式に帰着されます。まずその計算の技法（教科書102ページ図 3.11）を確認します。

この計算では２つのデータの加算 (p[n] + p[m])と（複素）乗算および（複素）加算(p[n]- α p[m]) により変換しています。 N=2^M個のデータの離散フーリエ変換ではこの計算をM段、各段においてN/2=2 ^M-1のバタフライ演算を行います。このことはよく覚えておいてください。

以下ではほとんどの教科書がそうしているように、データ長がN=2³=8の場合について考えていきます。教科書の102ページの図 3.11を見てください。この場合 M=3段のバタフライ演算を各段でN/2=2²=4繰り返していることが ○印の個数で確認できるとおもいます。それでは N=8の場合について回転子を複素空間上に図示しましょう。回転子行列の構成は先週の演習問題の最後の解答と同じです。ただし、議論の便宜上今回は要素番号をマイナス側にふっています。

バタフライ演算を実現するために、変換後の周波数ベクトルX の並び替えを行います。この並び替えはビットリバースを利用します。要素番号をビット表示し、それを左右逆転させます。これにより離散周波数ベクトルを

のように並び替えます。これは連立方程式を並び変えたことに相当しますので、この順番で回転子の行列の列を並び替えます。そうすると教科書99ページ(3.51)式に載っている行列と同じものが導出できますので、各自確かめてみてください。

注）

ここでは変数Xが横ベクトルですので列の交換をしてください。教科書どおりにW₈を並び替えてからそのエルミート行列をとっても同じです。

教科書では並び替えた行列のエルミート行列をW₈^'Hと表記しています。さて、バタフライ演算はこの行列をブロックに分け演算を細かくみていきますと、各段において先ほどのバタフライ演算が実行されているのがわかります。

このように離散フーリエ変換ではその係数が循環的であるために大幅に計算を節約できることがわかります。これを最後にもうすこし具体的にみてみましょう。最初にFFTではM段で2/N=2^M-1回の反復バタフライ演算をおこなっているわけですから、その演算回数は

となります。一方離散フーリエ変換をそのまま実施するということは、N次元の正方行列とN次元ベクトルの乗算ですから、 N回の乗算と和算をN回繰り返す、すなわちN² となります。つまり

であれば計算効率が上がっていることになります。いったいどれぐらいの効果があるのかN=2^M に具体的に数字を代入して確認してください。データ長が長いほど驚くべき効果があることがわかるはずです。たとえば、N=2¹²=4096の場合オーバーヘッドを考えず単純に 16777216回の演算に対し、 FFTでは24576回、すなわち約683倍の速さとなります。

本日学習したことについての補足します。

補足（１）

データ長が2^Mでなくてもこの計算は可能です。実際どうするのかは教科書で指摘されていますので確認しましょう。

補足（２）

FFTのアルゴリズムを理解するためにプログラム (C, Java,C# etc) を自分で作成することを勧めます。エレガントなプログラムを借りてくればよいという考えももちろんありますが、内容を理解するには、これが一番早道です。教科書どおりの初等的なプログラムでよいので、是非自身で組んでみてください。プログラム作成のポイントをまとめます。

ビットリバースによる要素並び替えプログラムを作成しておくと便利

CやC# でプログラムを組んだ場合、複素演算は組み込み関数としてはありませんので、そのクラスライブラリを作成する必要があります。がここでの複素演算は簡単ですので、実数部、虚数部に最初から分けて演算したほうが得策です。

Ｃプログラムの作成例をここであげておきますので、できれば自分でプログラムを組んでから比べてみてください。プログラムは次回の講義日に配布します。

補足（３）

今後の授業を理解するために、各自でプログラムを実行しながら確かめてみてください。開発コードの使用法等については次回の講義中に説明します。ところで毎年計算ソフトの紹介をしているとダウンロードしたのに使えないという問い合わせがあります。授業で紹介するフリーソフトはいずれもLinuxの世界ではボランテイアにより提供されているものです。したがって使用環境が異なると、使えないこともよくあります。情報工学の関連分野の技術者、研究者をめざす学生諸君はソースコードを取り寄せて自分でコンパイルするぐらいの気概をもってほしいと考えています。どうしてもだめならどんどんこちらに質問してください。