快速傅里叶变换（FFT）的原理、实现及代码解析（附C#源码）

2024-07-12 07:55| 来源: 网络整理| 查看: 265

可见，第L级的旋转因子为：

j代表旋转因子的个数，第L级的旋转因数个数为num=Math.Pow(2, L).(2的幂不会打)同时，还可以看到，每个蝶的两个输入点下标跨度是不一样的。比如第一级中是相邻两个数据作蝶运算，第二级中是两个输入点隔开一个点，而第三级隔开三个点。不难找到规律：第L级中，第二个输入点的坐标是第一个点的坐标+space，space=Math.Pow(2, L)=num。

利用以上性质，FFT的算法是写一个三重循环，

第一重循环对每一级运算（每级含num=Math.Pow(2, L)个蝶形）；

第二重对每一个旋转因子对应的蝶运算，那么有几个蝶呢？很简单，每级都应该有N/2个蝶，而每个因子对应N/2 / num个蝶；

第三重循环对每个蝶进行计算，需要注意的一是循环下标起始点的位置，二是每次计算需要申明临时变量来保存输入数据点。下面奉上C#源码：

//FFT算法 private void Dit2_FFT(ref double[] data_r, ref double[] data_i,ref double[] result_r,ref double[] result_i) { if (data_r.Length == 0 || data_i.Length == 0 || data_r.Length != data_i.Length) return; int len = data_r.Length; double[] X_r = new double[len]; double[] X_i = new double[len]; for (int i = 0; i < len; i++)//将源数据复制副本，避免影响源数据的安全性 { X_r[i] = data_r[i]; X_i[i] = data_i[i]; } DataSort(ref X_r, ref X_i);//位置重排 double WN_r,WN_i;//旋转因子 int M = (int)(Math.Log(len) / Math.Log(2));//蝶形图级数 for (int l = 0; l < M; l++) { int space = (int)Math.Pow(2, l); int num = space;//旋转因子个数 double temp1_r, temp1_i, temp2_r, temp2_i; for (int i = 0; i < num; i++) { int p = (int)Math.Pow(2, M - 1 - l);//同一旋转因子有p个蝶 WN_r = Math.Cos(2 * Math.PI / len * p * i); WN_i = -Math.Sin(2 * Math.PI / len * p * i); for (int j = 0, n = i; j < p; j++, n += (int)Math.Pow(2, l + 1)) { temp1_r = X_r[n]; temp1_i = X_i[n]; temp2_r = X_r[n + space]; temp2_i = X_i[n + space];//为蝶形的两个输入数据作副本，对副本进行计算，避免数据被修改后参加下一次计算 X_r[n] = temp1_r + temp2_r * WN_r - temp2_i * WN_i; X_i[n] = temp1_i + temp2_i * WN_r + temp2_r * WN_i; X_r[n + space] = temp1_r - temp2_r * WN_r + temp2_i * WN_i; X_i[n + space] = temp1_i - temp2_i * WN_r - temp2_r * WN_i; } } } result_r = X_r; result_i = X_i; }

我写了一个简单的测试界面，包含了上述的所有算法，效果如下：

用微信扫描二维码

为博主打个赏

金额随意快来“打”我呀要买枸杞当归补补~～

我已将源码上传资源，方便大家学习交流：点击打开链接

http://lib.csdn.net/article/computernetworks/14327

【本文地址】

公司简介

联系我们