FFT的比较简单易懂点的资料

先讲讲向量：a=a1*e1+a2*e2+a3*e3.....简记为a=ai*ei，ei相互正交
要把a1求出来，利用a*e1=a1*e1*e1+a2*e2*e1....=a1*e1*e1
所以求某个向量f在某基底c的分量只需要求内积f*c并除以c的模平方即可
即f(x)中cos(kx)的成分=<f(x),cos(kx)>/<cos(kx),cos(kx)>
两个函数的内积定义为乘积的积分，就好像两个向量的内积为对应下标项相乘并求和一样，离散傅里叶其实就是后者
所以某频率分量强度(余弦部分)就是∫f(x)*cos(kx)*dx / ∫cos(kx)*cos(kx)*dx
忽略了区间什么的，不要在意这些细节
FFT就是把公式用复数写了一遍，并找出其中的一些重复项，可以化简的地方什么的改进了下

是c#的：
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
/// <summary>
/// 快速傅立叶变换(Fast Fourier Transform)。
/// </summary>
public class TWFFT
{
private TWFFT()
{
}
private static void bitrp(float[] xreal, float[] ximag, int n)
{
// 位反转置换 Bit-reversal Permutation
int i, j, a, b, p;
for (i = 1, p = 0; i < n; i *= 2)
{
p++;
}
for (i = 0; i < n; i++)
{
a = i;
b = 0;
for (j = 0; j < p; j++)
{
b = b * 2 + a % 2;
a = a / 2;
}
if (b > i)
{
float t = xreal[i];
xreal[i] = xreal[b];
xreal[b] = t;
t = ximag[i];
ximag[i] = ximag[b];
ximag[b] = t;
}
}
}
public static int FFT(float[] xreal, float[] ximag)
{
//n值为2的N次方
int n = 2;
while (n <= xreal.Length)
{
n *= 2;
}
n /= 2;
// 快速傅立叶变换，将复数 x 变换后仍保存在 x 中，xreal, ximag 分别是 x 的实部和虚部
float[] wreal = new float[n / 2];
float[] wimag = new float[n / 2];
float treal, timag, ureal, uimag, arg;
int m, k, j, t, index1, index2;
bitrp(xreal, ximag, n);
// 计算 1 的前 n / 2 个 n 次方根的共轭复数 W'j = wreal [j] + i * wimag [j] , j = 0, 1, ... , n / 2 - 1
arg = (float)(-2 * Math.PI / n);
treal = (float)Math.Cos(arg);
timag = (float)Math.Sin(arg);
wreal[0] = 1.0f;
wimag[0] = 0.0f;
for (j = 1; j < n / 2; j++)
{
wreal[j] = wreal[j - 1] * treal - wimag[j - 1] * timag;
wimag[j] = wreal[j - 1] * timag + wimag[j - 1] * treal;
}
for (m = 2; m <= n; m *= 2)
{
for (k = 0; k < n; k += m)
{
for (j = 0; j < m / 2; j++)
{
index1 = k + j;
index2 = index1 + m / 2;
t = n * j / m; // 旋转因子 w 的实部在 wreal [] 中的下标为 t
treal = wreal[t] * xreal[index2] - wimag[t] * ximag[index2];
timag = wreal[t] * ximag[index2] + wimag[t] * xreal[index2];
ureal = xreal[index1];
uimag = ximag[index1];
xreal[index1] = ureal + treal;
ximag[index1] = uimag + timag;
xreal[index2] = ureal - treal;
ximag[index2] = uimag - timag;
}
}
}
return n;
}
}
}