本帖最后由 andy520520 于 2025-3-15 17:45 编辑
上面的FFT计算完全是错误的，不知道是哪里搞的
计算N点的FFT，分为log2(N) 层，每层N/2个蝶形，每个蝶形有一个复数乘法，旋转因子的表格 twiddle_factors_table[N/2]旋转因子表格大小是N/2
stage = 0 , 1 , 2 , ... , log2(N)- 1
在第0层， W_N^0 = 1
在第一层， W_N^0 = 1, W_N^(N/2^(stage +1)))
在第二层， W_N^0 = 1, W_N^(N/2^(stage + 1)), W_N^(2 *N/2^(stage + 1)), W_N^(3 * N/ 2^(stage + 1))
下面给出旋转因子表格
#define SCALE_FACTOR (1 << 14) // 在乘法的时候再缩回
// 定义复数结构体，元素类型改为
typedef struct
{ long int real;
long int imag;
} complex_int;
// 获取旋转因子表
void get_twiddle_factors(int n, complex_int *twiddle_factors)
{
for (int k = 0; k < n / 2; k++)
{
double angle = -2 * M_PI * k / n;
double real_part = cos(angle);
double imag_part = sin(angle);
// 将实部和虚部乘以放大因子并取整
twiddle_factors[k].real = (long int)(real_part * SCALE_FACTOR);
twiddle_factors[k].imag = (long int)(imag_part * SCALE_FACTOR);
}
}
FFT的精髓在下面的公式 ,合并了复数乘法，减少了乘法的次数，基2时间抽取法的FFT，乘法次数是 N/2 * log2(N)
t = W_N^k * odd[k]
X[k] = oven[k] + t
X[k + N/2] = even[k] - t
|
