高速フーリエ変換FFTが高速な理由

2025/03/08

　本記事では、音の圧縮体験ツールの実装に使用した「高速フーリエ変換(FFT)」を題材に、 どういう考え方で高速化していくのかを紹介します。 処理の概要はこちらで視覚的に解説していますので、併せてご覧ください。

フーリエ変換後のデータ量は元データと同じ

　まずはフーリエ変換の基本的な情報を確認していきます。 フーリエ変換は、元データと同じ量の変換結果が得られます。 例えばデータ量が8個のときには、8個のフーリエ変換結果が求められます

データ量に応じて計算量が決まる

　ここで例えば \(F_0\) を求めるためには、この図のように \(D_0\) から \(D_7\) までのすべてのデータを演算して計算します。 つまり \(F_0\) を求めるために8回の計算が必要です。 \(F_1\) を求めるためにも、\(D_0\) から \(D_7\) までのすべてのデータを用いるので、8回の計算が必要です。
　その他もそれぞれ8回の計算が必要です。 つまり全8個のフーリエ変換結果を算出するには \(8 \times 8 = 64\)回の計算が必要になります。 データ量が倍の16個になれば \(16 \times 16 = 256\)回の計算、32個になれば \(32 \times 32 = 1024\)回の計算が必要です。 データ量の2乗回の計算が必要になります。

音声データの秒数が増えると計算量が爆発的に増える

　フーリエ変換が扱うのは主に音声データです。
　音声データは、例えば44.1KHzでサンプリングしていれば1秒間で44,100個です。 その場合の計算量は1,944,810,000回。 この秒数が増えると計算量は爆発的に増えることになります。 そのため、可能であれば改善したいポイントです。

\(O(N^2)\)

　この計算量を数式で表すと、データ量が \(N\)個 なら \(N^2\) の計算量ということになります。 これを \(N^2\)のオーダーと呼び、\(O(N^2)\) などと書きます。
　なお厳密には、それぞれ1回でどのようなの計算がなされているかも気になるところですが、オーダーを考えるときには無視します。 データ量の増加に応じて、計算量が爆発的に増えてしまうなら、それぞれ1回の計算速度は、ほとんど影響がないからです。 重要なのはデータ量の増加に対して、計算量がどの程度増えるかです。

高速化は、理論、実装、の順

　コンピュータープログラミングにおいて、高速化したい場面はよくあります。 ゲームの世界では、例えば1秒間に60回画面を更新する場合、\(\frac{1}{60}\)秒内で一通りの処理を完了しなければならず、高速化の要求は常にあります。
　その時に検討すべきは、一般的にはまず、理論的に計算量が減らせるなら、そちらを優先します。 実装テクニックによる高速化も重要ですが、先に検討すべきは理論による高速化です。
　本記事では、フーリエ変換の計算量を理論的に減らす、高速フーリエ変換、FFTの実装について解説します。 実装テクニックについてはこちらの記事で解説しています。

高速フーリエ変換の概要

　高速フーリエ変換の概要は以下の通りです。

偶数番要素と奇数番要素に分ける

　まず、データの配列が0から始まるとして、その要素を、偶数番目と奇数番目に分けて、新たなデータ配列を2つ作ります。

それぞれフーリエ変換を計算する

　それらの2つのデータ配列に対して、フーリエ変換を実施します。

加算と減算で変換完了

　解答データ配列は、求められたフーリエ変換結果を、前半は加算、後半は減算することで求めます。

　なお厳密には単純な加減算ではありませんが、本記事は計算量の把握が目的のため、ここでは計算式を省略します。 筆者は詳細を解説しているネット上の記事も参考にしましたので、興味のある方は調べてみてください。 なお回転因子を用いた式の理解が必要になります。

半分にしたものを2回計算して計算量が変わる？

　直感的には、半分にしたものを2つ作って、それぞれ計算しても、合計速度は変わらないように感じます。 しかしご案内の通り、データ量の2乗の計算量になりますので、半分にすると計算量は \(\frac{1}{4}\)になります。 それを2倍しても \(\frac{1}{2}\) で済みます。

プログラミングイメージ

　イメージを掴むために、仮想的なプログラミングコードを見てみましょう。
　後半(else以下)がこのプログラムの中心です。 偶数番データ配列のFFTと、奇数番データ配列のFFTを求め、結果を加減算して配列を構築しています。 データ配列がこれ以上分割できなくなった場合、すなわち要素数1のときは、答えを計算して返します。
　特徴として、FFT関数の中で、FFT関数を呼び出している部分が挙げられます。 この、自分自身を呼び出す形の関数定義を再起定義(さいきていぎ)と呼びます。 再起定義を使うと、一見複雑そうな計算でも、このようにスッキリとしたプログラミングが可能になることがあります。

詳細な動きを確認

　このプログラムを念頭に、詳細な動作を確認していきましょう。

究極まで半分に

　まずはデータ配列を、要素数が1になるまで半分にしていきます。

フーリエ変換

　これ以上半分にできなくなったら、フーリエ変換をします。 具体的には、そのままのデータになります。

加減算で次の結果に

　求められた解答を、加減算で合成します。
　こうして求められた例えば [\(F_0F_1\)] は、実は [\(D_0D_4\)] のフーリエ変換結果です。

加減算でさらに次の結果に

　さらに加減算で解答を構築していきます。

最後に加減算して完了

　最後まで戻ってきたら完了です。

高速フーリエ変換の計算オーダー

　本記事で紹介した高速フーリエ変換の計算量は、元データ量 \(N\) に対して \(N\)個のデータを求めることは変わりません。 しかし、それぞれを求めるために \(N\) 回の計算が必要だったところが、\(N\) を半分にしていき1になる回数の計算量になります。
　具体的には、データ数が8個のときには \( 8 \times 3 = 24\)回、16個なら \( 16 \times 4 = 64\)回、32個なら \( 32 \times 5 = 160\)回です。 最初に求めた、64回、256回、1024回という増え方に対して、明らかに減っています。
　このような増え方は、オーダーとしては \(log\) で表現します。 本記事の計算オーダーは \(O(N \log N)\) です。
　\(log\)は、簡単にいうと桁数を求めるものです。 \(\log 100 = 2\)、\(\log 1000 = 3\)です。
　高速フーリエ変換により \(O(N^2)\) だったところを \(O(N \log N)\) に高速化できました！

考え方は応用できる

　高速フーリエ変換は限定的な理論の中の話ですが、考え方は応用できます。
　例えば、辞書に登録されている単語を検索するプログラムを書くとします。 単純に先頭から順番に調べるプログラムはオーダーとして \(O(N)\) 回の処理が必要になります。 しかしまず辞書を半分に割って、求める単語が前半と後半のどちらに含まれるかを判断し、 含まれている半分の辞書をさらに半分に割って、という処理を繰り返すことで、 \(O( \log N) \)回の処理に減らせます。
　このように、処理を高速化したい場合には、まずは理論的に計算量を減らす方法を考察することが重要です。

まとめ

　本記事では、高速フーリエ変換が高速な理由を解説しました。 計算量とオーダーの考え方、その応用、また再起定義についても解説しています。
　こちらの記事ではさらに、高速フーリエ変換の実装に関する工夫を解説していますので、ぜひそちらもご覧ください。

補足

・FFTは Fast Fourier Transform です。直訳で「高速フーリエ変換」です。
・高速フーリエ変換はデータ量が2のべき乗の場合のみ適用できます。実装では2のべき乗になるように空のデータを加えます。
・今回説明したフーリエ変換は、厳密には離散フーリエ変換です。これはデジタルデータを処理するフーリエ変換です。
・再起定義関数の処理順番は偏ります。各フロー図は処理全体をイメージするために使用してください。
・フーリエ変換の実装ではこちらとこちらのサイトを参考にさせてもらいました。
・画像内のラスタライズ文字フォントにOpen Font LicenseのZen Antiqueを使用しております。
・数式表現にMathJaxを使用しております。助かります！

カテゴリー：オーディオ推し,プログラミング

Copyright (C) Logic Lovers Inc.

Loading...

Loading...