#include <nitro/math/fft.h>
void MATH_FFTReal( fx32* data, u32 nShift, const fx16* sinTable, const fx16* sinTable2 );
| data | 変換するデータへのポインタ。変換後のデータは上書きされる。 |
| nShift | 入力実数の個数に2を底とした対数を取った値。 |
| sinTable | sin 値のテーブルのポインタ。 |
| sinTable2 | sinTable を一つおきに間引いた sin 値テーブルへのポインタ。 |
なし。
実数列を入力とし、複素数列を出力する離散フーリエ変換を高速フーリエ変換のアルゴリズムを用いて行います。
虚数部分を 0 で埋めた MATH_FFT 関数でも同じ変換を行えますが、
こちらのほうが使用するメモリ量が半分ですみ、また計算時間も半分程度となります。
以下、2nShift(2のnShift乗) を N と置きます。data は fx32 型の長さ N の配列で、変換したい実数値のデータです。
sinTable は sinTable[k] = sin( (2π/N) * k ) (k = 0, 1,..., N*3/4-1) となるように fx16 型の sin 値を代入した、長さ N*3/4 の配列へのポインタです。MATH_MakeFFTSinTable()で作成することもできます。
sinTable2 は sinTable2[k] = sin( (2π/(N/2)) * k ) (k = 0, 1,..., (N/2)*3/4-1) となるように fx16 型の sin 値を代入した、長さ (N/2)*3/4 の配列へのポインタです。MATH_MakeFFTSinTable()で nShift 引数に1少ない値を与えて作成することもできます。
離散フーリエ変換の結果は複素数列になりますが、実数列を与えているため、独立な数値は半分だけとなります。そのため、独立の部分だけを取り出し、N/2+1 個の複素数列（ただし、最初と最後は必ず虚数成分が0）として data に上書きして返されます。
結果的に使用する配列サイズは入力データと同じ N です。
返り値は実数と虚数が交互に格納される形式です。また、変則的に、N/2 番目の値（必ず実数）は、0 番目の値（必ず実数）の虚数部分に格納されて返されます。
すなわち、i を虚数単位とすると、
{data[0], data[2]+i*data[3], ..., data[N-2]+i*data[N-1], data[1]} という N/2+1 個の複素数からなる数列が変換結果となります。なお、独立ではないため省略された後半半分は、1 番目から N/2-1 番目までの複素数列の順番を逆転させて複素共役をとった値になります。
離散フーリエ変換とは、fn (n = 0, 1, ... N-1) を時間軸に沿った複素数のサンプリング値としたとき、
fn = Σk = 0N-1 Fke-i2πkn/N
上式を満たすような Fm (m = 0, 1, ... N-1) を求める演算です。
Fm は入力信号を正弦波の重ね合わせに分解した場合の各周波数の係数と見ることができます。
高速フーリエ変換は離散フーリエ変換を N*log(N) のオーダーの時間計算量で行うアルゴリズムです。
固定小数点数を用いて計算しているため、大きな値を入力として与えると桁あふれを起こす危険があります。
入力値を s32 型として見たときの絶対値が 0x80000000/N 以上にならないことを目安としてください。
また、順変換と逆変換を行った場合の誤差は最大で FX32_ONE の数倍程度となります。
MATH_MakeFFTSinTable, MATH_FFT, MATH_IFFT, MATH_IFFTReal
2009/03/23 数式の誤記の修正
2005/07/21 sinTable の説明の修正
2005/07/11 説明の修正
2005/05/13 初版