FFTの組み込み実装入門
FFT（高速フーリエ変換）は、組み込みシステムにおいて信号処理を高速化するための重要な技術です。この記事では、C言語によるFFTの基本構造から実装手順を解説します。
FFTとは
FFT（高速フーリエ変換）はDFT（離散フーリエ変換）を高速化したアルゴリズムです。フーリエ変換は信号を周波数成分に分解し、データの特性を理解する際に使用します。振動解析、画像処理、通信システムなどさまざまな分野で使われている技術です。デジタル信号は離散的なサンプルで表現されるため、信号を周波数に変換するときにDFTを利用することで各周波数成分の振幅と位相を求められます。
DFTは一般に計算量がO(N^2)ですが、FFTではO(N log N)まで削減できます。特にRadix-2 FFTはサンプル数Nが2のべき乗（N=2^k）のときに実装しやすく高速化しやすい一方、Nが合成数の場合でも混合基数(mixed-radix)などでFFT計算は可能です。組み込み開発における実装はC言語でのリアルタイム処理が要求されることが多く、FFTは処理速度の高速化に重要な位置を占めます。
FFTの使用例
FFTは音声処理や画像処理に使われます。音声処理では周波数ごとに音を分解して、特定の成分のカット・加工ができるようになります。この役割を担うのが FFT です。
画像処理ではグレースケールの画像を二次元配列として扱うことで、周波数を解析します。画像のぼかし、エッジ強調などの加工もFFTによる周波数フィルタリングによって可能になります。
Cooley-Tukeyのアルゴリズム
FFTのアルゴリズムとして有名なのが、Cooley-Tukeyのアルゴリズムです。大きな離散フーリエ変換を小さく分割することで計算速度を上げています。DFTに比べて計算量を落とせますが、最も一般的なRadix-2形態の実装では、入力データ数（サンプル数）が2のべき乗に制限されます。
Cooley-Tukeyを実装するときは、forループで要素数を因数分解しながら並べ替え、離散フーリエ変換を分解していくことを繰り返します。計算していく間に足し算や掛け算を繰り返すため、FFTは煩雑になりがちです。その複雑な計算の過程をわかりやすく示すために、シグナルフローグラフが使われます。左から右に進む直線が合流したり、線の途中に補足の数字を入れたりすることで、バタフライ演算の計算過程を図示します。
ビットリバース
ビット反転処理（bit-reversal permutation）はデータの並べ替えステップとしてバタフライ演算と組み合わされ、反復型のRadix-2 FFTでは、インプレース（in-place：追加メモリを使用しない）で計算する都合上、入力または出力にビット反転順の配置が現れます。Radix-2のDIT（Decimation-in-Time）形態では入力データをビット反転順に並べ替えた上でバタフライ演算を実行し、逆に、DIF（Decimation-in-Frequency）形態ではバタフライ演算後にビット反転処理をおこないます。いずれの形態でも、DFTと同じ結果を得るためにビット反転処理が不可欠です。
C言語での実装ポイント
組み込みデバイスの制御にはリアルタイム性が求められます。速い処理のためにDFTを避け、FFTを使ったとしても、メモリアクセスに時間がかかっていては意味がありません。その点、C言語はメモリアクセスを気にしながら実装が可能なため、FFTを実装する言語として向いています。
FFT の実装においても、高速化を目的とした工夫がいくつかあります。
ループの高速化を図れるループアンローリングはその典型例です。ループの主要部分を展開してコーディングすることでメモリアクセス回数を減らせます。
コンパイラの最適化が制限される環境では、配列のインデックスアクセスをポインタ演算に置き換えることで、アドレス計算のオーバーヘッドを削減できます。また、構造体などの大きなデータを関数へ渡す際にポインタ渡しにすれば値のコピーを省け、リソースと処理時間を削減できます。
コード上で処理時間を表示する実装にして、どの処理が一番速いかを確認するのも重要です。
組み込み用途でのFFT実装の注意点
組み込みシステムにおけるFFTの実装は計算速度とリソース制約のバランスを取ることが必要です。
信号のやり取りはリアルタイム性を要求されるため、処理時間の短い実装方式を検討しなければなりません。また割り込みタスクで処理が中断されると、ほかにリアルタイム性を必要とする処理が遅延する原因になります。設計する際はそれぞれに配慮が必要です。
長期間使いたい機器や、バッテリ交換が難しい機器に搭載されたマイコンでは、消費電力を抑えるために演算回数を削減しなければなりません。モジュール自体が不必要な機能を低消費電力モードに切り換えてくれるものもあります。
FFT自体を高速化、省エネ化することはもちろん重要ですが、マイコンの周辺回路まであわせて検討するため、トータルでバランスを見ていく必要があります。
