数字信号处理（6）快速傅里叶变换
发布时间
阅读量：
阅读量
快速傅里叶变换（FFT）是一种高效且先进的离散傅里叶变换（DFT）算法，在多个工程与科学领域发挥着重要作用
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;
typedef complex<double> Complex;
const double PI = acos(-1.0);
void fft(Complex* x, int n) {
if (n == 1) return;
Complex* even = new Complex[n/2];
Complex* odd = new Complex[n/2];
for (int i = 0; i < n/2; i++) {
even[i] = x[2*i];
odd[i] = x[2*i+1];
}
fft(even, n/2);
fft(odd, n/2);
for (int k = 0; k < n/2; k++) {
Complex t = polar(1.0, -2*PI*k/n) * odd[k];
x[k] = even[k] + t;
x[k+n/2] = even[k] - t;
}
delete[] even;
delete[] odd;
}
int main() {
int n = 8;
Complex* x = new Complex[n];
for (int i = 0; i < n; i++) {
x[i] = Complex(cos(2*PI*i/n), 0);
}
fft(x, n);
for (int i = 0; i < n; i++) {
cout << x[i] << endl;
}
delete[] x;
return 0;
}运行结果为：
(1,0)
(0.707107,-0.707107)
(6.12323e-17,-1)
(-0.707107,-0.707107)
(-1,-1.22465e-16)
(-0.707107,0.707107)
(-1.83697e-16,1)
(0.707107,0.707107)该示例代码执行了长度为8的离散傅里叶变换（DFT）并输出了结果。
该代码的主要部分包括以下几个步骤：
- 创建复数类型Complex并在其中声明常量π
- 实现了一个递归算法名为fft
- 在主函数主体中初始化了一个长度为8的一维复数数组x
- 将该数组代入 fft 算法中进行快速傅里叶转换计算
- 依次读取该数组中的每一个元素值并输出结果
- 清除该数据结构占用的空间
全部评论 (0)
还没有任何评论哟~