利用FFT算法实现快速傅里叶变换
简 介： 利用fft算法实现快速傅里叶变换， 在理论、工程中具有非常广泛的应用。除了能够在合适的计算平台完成fft算法，同时还需要注意到它在频谱分析中可能带来的频率混叠以及频率泄露等问题。
01 python算法 今天下午的信号与系统， 给同学们介绍了离散傅里叶变换的基本应用， 并且介绍了快速傅里叶变换(fft)的主要思想与算法。fft算法因其优异的性能和广泛的应用， 堪称信息处理领域的原子武器。实现fft编程语言很多， 比较来比较去， 利用python语音所描述的该算法最为简明和优雅。
1.1 fft算法代码 下面的代码是在 the fast fourier transform (fft): most ingenious algorithm ever? 视频中给出的 fft 递归算法形式， 最大精度反映了fft算法核心。
这个代码实现了dif（时域抽取快速傅里叶变换）， 利用递归定义，将fft核心算法中的分而治之体现的淋漓尽致， 突出了递归核心中的核心思想。
def fft(p): n = len(p) if n * 1: return p ye = fft(p[0::2]) yo = fft(p[1::2]) y = [0]*n w = exp(-1j*2*pi/n) for j in range(n//2): yow = w**j * array(yo) y[j] = ye[j] + yow[j] y[j+n//2] = ye[j] - yow[j] return y 利用python语音中对于数组切片操作语法， 还可以将上面fft算法中的循环部分都替换成关于数组的操作， 使得实际运算速度得到提高。
def fft1(p): n = len(p) if n * 1: return p ye = fft(p[0::2]) yo = fft(p[1::2]) w = exp(-1j*2*pi/n)**array(list(range(n//2))) yow = w*yo y = [0]*n y[:n//2] = ye + yow y[n//2:] = ye - yow return y 1.2 fft 算法测试 为了测试算法的有效性， 下面对于一个方波信号计算对应的fft结果。
测试算法代码如下：
len = 1024onelen=10p1 = [1]*onelen+[0]*(len-onelen)y = fft(p1)plt.plot(abs(array(y)), label='abs(fft)')plt.plot(p1, label='data')plt.xlabel(y)plt.ylabel(abs(fft(y)))plt.grid(true)plt.legend(loc='upper right')plt.tight_layout()plt.show() 下面是测试利用python语言实现的fft算法计算结果。
▲ 图1.2.1 利用python语音实现的fft算法测试结果 02 其它语言fft fft算法贵在计算效率，前面使用python实现fft，虽然形式上优雅，但实际执行效率不高。提高执行效率，还是需要使用编译语言。
2.1 fortran fft算法 在我上大学期间所学的编程语言为fortran， 估计现在没有多少同学学习这个算法语言。下面给出了利用fortran语言实现的fft算法程序。
算法整体上包括有两个阶段：
第一个阶段实现了对输入数据进行倒读顺序排列； 第二阶段利用三重循环实现了分组蝶形运算。 当然了，时过三十年再看fortran感觉十分酸爽， 但它简练语言和执行高效还是让我们回忆起当年编程时所感觉到的快乐。
▲ 图 fortran 语言实现的fft算法 2.2 c语言fft算法 下面是在网络上博文 c++ program to compute discrete fourier transform using fast fourier transform approach[1] 给出的fft算法， 没有对其功能进行测试。相比于前面利用python，fortran来看， c语言实现fft就显得非常啰嗦了。
#include #include #include #include using namespace std;unsigned int bitreverse(unsigned int x, int log2n) { int n = 0; int mask = 0x1; for (int i = 0; i < log2n; i++) { n <>= 1; } return n;}const double pi = 3.1415926536;templatevoid fft(iter_t a, iter_t b, int log2n) { typedef typename iterator_traits::value_type complex; const complex j(0, 1); int n = 1 << log2n; for (unsigned int i = 0; i < n; ++i) { b[bitreverse(i, log2n)] = a[i]; } for (int s = 1; s <= log2n; ++s) { int m = 1 1; complex w(1, 0); complex wm = exp(-j * (pi / m2)); for (int j = 0; j < m2; ++j) { for (int k = j; k < n; k += m) { complex t = w * b[k + m2]; complex u = b[k]; b[k] = u + t; b[k + m2] = u - t; } w *= wm; } }} ※ 总 结 ※ 利用fft算法实现快速傅里叶变换， 在理论、工程中具有非常广泛的应用。除了能够在合适的计算平台完成fft算法，同时还需要注意到它在频谱分析中可能带来的频率混叠以及频率泄露等问题。
PCB设计中如何使用跳线 如何设置跳线的要求
延时控制电路工作过程
移动互联网催生安防新模式,企业如何运用互联网思维转型升级
MediaTek推出高度集成双模5G调制解调器
Xilinx推出业界首款“一体化 SmartNIC 平台”
利用FFT算法实现快速傅里叶变换
以高瓦数数字放大器进行设定
现代电子产品可靠性的概述
工业数据采集的范围、特点及结构
直流电机运转不正常的原因有哪些
如何将小型光伏系统与网格进行同步
零漂移桥式传感放大器AD8555的性能特点及应用范围
可编程性在电池充电器的集成电路中实现
为什么说三星将最有可能接手GlobalFoundries？
oppor11什么时候上市?oppor11详细配置曝光,网友：再也不用买iphone7了
【火爆推进中】电子工程师的梦想！手把手DIY专属实验室
米尔科技 ATMEL AT91SAM9G45 ARM9单板机概述
【启扬方案】智能化解锁“智慧出游”新模式
物联网技术在智慧医院的应用
各主要尺寸液晶面板试探性涨价亦难以持续
01 python算法 今天下午的信号与系统， 给同学们介绍了离散傅里叶变换的基本应用， 并且介绍了快速傅里叶变换(fft)的主要思想与算法。fft算法因其优异的性能和广泛的应用， 堪称信息处理领域的原子武器。实现fft编程语言很多， 比较来比较去， 利用python语音所描述的该算法最为简明和优雅。
1.1 fft算法代码 下面的代码是在 the fast fourier transform (fft): most ingenious algorithm ever? 视频中给出的 fft 递归算法形式， 最大精度反映了fft算法核心。
这个代码实现了dif（时域抽取快速傅里叶变换）， 利用递归定义，将fft核心算法中的分而治之体现的淋漓尽致， 突出了递归核心中的核心思想。
def fft(p): n = len(p) if n * 1: return p ye = fft(p[0::2]) yo = fft(p[1::2]) y = [0]*n w = exp(-1j*2*pi/n) for j in range(n//2): yow = w**j * array(yo) y[j] = ye[j] + yow[j] y[j+n//2] = ye[j] - yow[j] return y 利用python语音中对于数组切片操作语法， 还可以将上面fft算法中的循环部分都替换成关于数组的操作， 使得实际运算速度得到提高。
def fft1(p): n = len(p) if n * 1: return p ye = fft(p[0::2]) yo = fft(p[1::2]) w = exp(-1j*2*pi/n)**array(list(range(n//2))) yow = w*yo y = [0]*n y[:n//2] = ye + yow y[n//2:] = ye - yow return y 1.2 fft 算法测试 为了测试算法的有效性， 下面对于一个方波信号计算对应的fft结果。
测试算法代码如下：
len = 1024onelen=10p1 = [1]*onelen+[0]*(len-onelen)y = fft(p1)plt.plot(abs(array(y)), label='abs(fft)')plt.plot(p1, label='data')plt.xlabel(y)plt.ylabel(abs(fft(y)))plt.grid(true)plt.legend(loc='upper right')plt.tight_layout()plt.show() 下面是测试利用python语言实现的fft算法计算结果。
▲ 图1.2.1 利用python语音实现的fft算法测试结果 02 其它语言fft fft算法贵在计算效率，前面使用python实现fft，虽然形式上优雅，但实际执行效率不高。提高执行效率，还是需要使用编译语言。
2.1 fortran fft算法 在我上大学期间所学的编程语言为fortran， 估计现在没有多少同学学习这个算法语言。下面给出了利用fortran语言实现的fft算法程序。
算法整体上包括有两个阶段：
第一个阶段实现了对输入数据进行倒读顺序排列； 第二阶段利用三重循环实现了分组蝶形运算。 当然了，时过三十年再看fortran感觉十分酸爽， 但它简练语言和执行高效还是让我们回忆起当年编程时所感觉到的快乐。
▲ 图 fortran 语言实现的fft算法 2.2 c语言fft算法 下面是在网络上博文 c++ program to compute discrete fourier transform using fast fourier transform approach[1] 给出的fft算法， 没有对其功能进行测试。相比于前面利用python，fortran来看， c语言实现fft就显得非常啰嗦了。
#include #include #include #include using namespace std;unsigned int bitreverse(unsigned int x, int log2n) { int n = 0; int mask = 0x1; for (int i = 0; i < log2n; i++) { n <>= 1; } return n;}const double pi = 3.1415926536;templatevoid fft(iter_t a, iter_t b, int log2n) { typedef typename iterator_traits::value_type complex; const complex j(0, 1); int n = 1 << log2n; for (unsigned int i = 0; i < n; ++i) { b[bitreverse(i, log2n)] = a[i]; } for (int s = 1; s <= log2n; ++s) { int m = 1 1; complex w(1, 0); complex wm = exp(-j * (pi / m2)); for (int j = 0; j < m2; ++j) { for (int k = j; k < n; k += m) { complex t = w * b[k + m2]; complex u = b[k]; b[k] = u + t; b[k + m2] = u - t; } w *= wm; } }} ※ 总 结 ※ 利用fft算法实现快速傅里叶变换， 在理论、工程中具有非常广泛的应用。除了能够在合适的计算平台完成fft算法，同时还需要注意到它在频谱分析中可能带来的频率混叠以及频率泄露等问题。
PCB设计中如何使用跳线 如何设置跳线的要求
延时控制电路工作过程
移动互联网催生安防新模式,企业如何运用互联网思维转型升级
MediaTek推出高度集成双模5G调制解调器
Xilinx推出业界首款“一体化 SmartNIC 平台”
利用FFT算法实现快速傅里叶变换
以高瓦数数字放大器进行设定
现代电子产品可靠性的概述
工业数据采集的范围、特点及结构
直流电机运转不正常的原因有哪些
如何将小型光伏系统与网格进行同步
零漂移桥式传感放大器AD8555的性能特点及应用范围
可编程性在电池充电器的集成电路中实现
为什么说三星将最有可能接手GlobalFoundries？
oppor11什么时候上市?oppor11详细配置曝光,网友：再也不用买iphone7了
【火爆推进中】电子工程师的梦想！手把手DIY专属实验室
米尔科技 ATMEL AT91SAM9G45 ARM9单板机概述
【启扬方案】智能化解锁“智慧出游”新模式
物联网技术在智慧医院的应用
各主要尺寸液晶面板试探性涨价亦难以持续