基2FFT的算法推导及python仿真
fft的算法推导主要用到旋转因子的周期性、对称性和可约性：
基2fft的频域抽取法，将x(n)按照n的自然顺序划分为前后两个部分：
所以当k为偶数时，前后两部分相加。当k为奇数时相减。将频域x(k)划分为奇偶两个序列，n点dft就被分解为两个n/2点的dft：
可以得到蝶形图如下：
进而可以得到基2fft频域抽取代码的实现方法：
随后是数据倒换，如下图：
可以看到基2fft频域抽取后的输出位置排序就是自然数二进制码按位倒读的值。
根据推导结果我们编写python实现代码：
首先根据fft的点数计算需要迭代的次数，根据迭代次数例化一个loop_num+1*n的数组一共来存储输入及中间迭代的结果，同时将输入x送入第一行作为输入：
import numpy as npimport matplotlib.pyplot as plt#频域抽取的基2fftloop_num= int(np.log2(n))data=np.zeros((loop_num+1,n),dtype=np.complex)data[0]=x随后开始fft的迭代，循环变量i一共来表征迭代的次数；循环变量p用来表征每次循环将将数据换分为几块；循环变量j用来进行蝶形运算。通过循环完成fft的迭代及运算，代码如下：
for i in range(loop_num): k=i+1 for p in range(2**i): for j in range(n//(2**k)): data[i+1][j +p*(n//(2**i))] = data[i,j+p*(n//(2**i))] + data[i,j+n//(2**k) +p*(n//(2**i))] data[i+1][j+n//(2**k) +p*(n//(2**i))] = (data[i,j+p*(n//(2**i))] - data[i,j+n//(2**k) +p*(n//(2**i))])*np.e**(-1j*2*j*np.pi*(2**i)/n)最终将fft蝶形运算的结果进行输出倒序，定义rev2(k,n)递归函数达到按bit翻转的目的，最终输出fft结果为fft_out：
def rev2(k,n): if (k==0): return (0) else: return(((rev2(k//2,n)//2)+(k%2)*(n//2)))#输出倒序fft_out = np.ones_like(data[0,:])for k in range (n): fft_out[rev2(k,n)] = data[loop_num,k]最后为了验证代码正确性，直接调用python的fft库函数得到xf为库函数的结果，与fft_out相减并画图，观察误差。
xf = np.fft.fft(x)plt.plot(abs(xf))plt.plot(abs(fft_out-xf))输入1024点的任意复数：
x = [int(np.round(np.sin(i)*1024))+int(np.round(np.cos(i)*1024))*1j for i in n]
波形如下：
运行python算法得到结果如下，图中蓝线是fft计算的结果，橙线是fft库函数计算结果与fft_out相减的差，差值为0，认为我们的迭代算法正确。
TotalMounterPro的重要功能
这么一款可穿戴式智能键盘，是不是挺酷！
简单总结了一下PCB调试、测试以及项目报告过程中的一些关键环节
MAXREFDES100健康传感器平台的应用
如何从0到1构建一个稳定、高性能的Redis集群？
基2FFT的算法推导及python仿真
为了能让5G早些商用落地，高通也是做了大量部署
一文了解人工智能时代零售业的智能变革
提高TinyML、ML-DSP和深度学习工作负载的能效
指纹识别技术的基本原理是怎样的
借助人工智能，建设一场马拉松智能城市
LG正式发布新平板G Pad 5 10.1 搭载“陈年老U”骁龙821
差动继电器工作原理
黄河大峡水电站2号水轮发电机转轮顺利吊入并安装调整就位
博世陈玉东：5月份被催芯片，已经焦头烂额
两种常见的MOSFET驱动电路
12W适配器电源ic U9513A销量稳步上升
瑞典和西班牙分别成为欧洲风电和太阳能电力企业PPA均价最便宜国家
黑科技满满的智能化妆镜，带你智享智能美妆时刻
90分智能解锁旅行箱评测 年轻人的第一款安全旅行箱
基2fft的频域抽取法，将x(n)按照n的自然顺序划分为前后两个部分：
所以当k为偶数时，前后两部分相加。当k为奇数时相减。将频域x(k)划分为奇偶两个序列，n点dft就被分解为两个n/2点的dft：
可以得到蝶形图如下：
进而可以得到基2fft频域抽取代码的实现方法：
随后是数据倒换，如下图：
可以看到基2fft频域抽取后的输出位置排序就是自然数二进制码按位倒读的值。
根据推导结果我们编写python实现代码：
首先根据fft的点数计算需要迭代的次数，根据迭代次数例化一个loop_num+1*n的数组一共来存储输入及中间迭代的结果，同时将输入x送入第一行作为输入：
import numpy as npimport matplotlib.pyplot as plt#频域抽取的基2fftloop_num= int(np.log2(n))data=np.zeros((loop_num+1,n),dtype=np.complex)data[0]=x随后开始fft的迭代，循环变量i一共来表征迭代的次数；循环变量p用来表征每次循环将将数据换分为几块；循环变量j用来进行蝶形运算。通过循环完成fft的迭代及运算，代码如下：
for i in range(loop_num): k=i+1 for p in range(2**i): for j in range(n//(2**k)): data[i+1][j +p*(n//(2**i))] = data[i,j+p*(n//(2**i))] + data[i,j+n//(2**k) +p*(n//(2**i))] data[i+1][j+n//(2**k) +p*(n//(2**i))] = (data[i,j+p*(n//(2**i))] - data[i,j+n//(2**k) +p*(n//(2**i))])*np.e**(-1j*2*j*np.pi*(2**i)/n)最终将fft蝶形运算的结果进行输出倒序，定义rev2(k,n)递归函数达到按bit翻转的目的，最终输出fft结果为fft_out：
def rev2(k,n): if (k==0): return (0) else: return(((rev2(k//2,n)//2)+(k%2)*(n//2)))#输出倒序fft_out = np.ones_like(data[0,:])for k in range (n): fft_out[rev2(k,n)] = data[loop_num,k]最后为了验证代码正确性，直接调用python的fft库函数得到xf为库函数的结果，与fft_out相减并画图，观察误差。
xf = np.fft.fft(x)plt.plot(abs(xf))plt.plot(abs(fft_out-xf))输入1024点的任意复数：
x = [int(np.round(np.sin(i)*1024))+int(np.round(np.cos(i)*1024))*1j for i in n]
波形如下：
运行python算法得到结果如下，图中蓝线是fft计算的结果，橙线是fft库函数计算结果与fft_out相减的差，差值为0，认为我们的迭代算法正确。
TotalMounterPro的重要功能
这么一款可穿戴式智能键盘，是不是挺酷！
简单总结了一下PCB调试、测试以及项目报告过程中的一些关键环节
MAXREFDES100健康传感器平台的应用
如何从0到1构建一个稳定、高性能的Redis集群？
基2FFT的算法推导及python仿真
为了能让5G早些商用落地，高通也是做了大量部署
一文了解人工智能时代零售业的智能变革
提高TinyML、ML-DSP和深度学习工作负载的能效
指纹识别技术的基本原理是怎样的
借助人工智能，建设一场马拉松智能城市
LG正式发布新平板G Pad 5 10.1 搭载“陈年老U”骁龙821
差动继电器工作原理
黄河大峡水电站2号水轮发电机转轮顺利吊入并安装调整就位
博世陈玉东：5月份被催芯片，已经焦头烂额
两种常见的MOSFET驱动电路
12W适配器电源ic U9513A销量稳步上升
瑞典和西班牙分别成为欧洲风电和太阳能电力企业PPA均价最便宜国家
黑科技满满的智能化妆镜，带你智享智能美妆时刻
90分智能解锁旅行箱评测 年轻人的第一款安全旅行箱