第12章 高速フーリエ変換(Fast Fourier Transform)

目次

12.1. 使用する数学のまとめ
12.2. フーリエ変換(Fourier Transform)の定義
12.3. 離散フーリエ変換(Discrete Fourier Transform)
12.4. 高速フーリエ変換(Fast Fourier Transform)
12.4.1. Cooley-Tukey型アルゴリズム
12.4.2. Bit Reversal
12.5. 実装例(CPU)
12.6. 実装例(GPU)

注記

本項目では読者が微積分、三角関数、複素数等の基本的な高等数学の知識と符号処理の知識を持つ事を想定します。数学に自信のない方はとばして構いません。本書がターゲットとする読者が使用する可能性は低いものの、科学技術計算、画像処理系の技術者が頻繁に用いる重要なアルゴリズムのため解説することにしました。データ並列プログラミングの要素を詰め込んだアルゴリズムですので、画像処理とは無関係な方が学ぶことにも意義はあると考えます。バイトニック整列、基数整列やヒストグラムのソースコードが理解できた後に目を通すことを推奨します。

高速フーリエ変換は、通信技術(スペクトラル分析、周波数分析)、音声データからのノイズ除去、画像パターンの推定、航空機レーダー探知、移動通信機(携帯電話等)のシグナル分析などに使われる技術で、おそらく工学で使用される数学の中で最も使用されているものの一つです。色、音、電磁波等の信号データと相性が良いとされています。

高速フーリエ変換を一言で定義するなら信号の周波数領域への変換です。信号変換により信号の周波数成分(周波数毎の強さ)を解析することが可能となります。高速フーリエ変換は「FFT」と呼ばれることがあります。

「高速」フーリエ変換(FFT)は「フーリエ変換」(Fourier Transform, FT)の一種ですが、名前の通り高速な周波数領域への変換を可能とします。その最大の利点は高速に処理ができるため、リアルタイムで解析が必要な分野への応用が可能となったことです。

Copyright 2018-2019, by Masaki Komatsu