① 单片机实现傅立叶变换
用FPGA这种单片机
在对FFT（快速傅立叶变换）算法进行研究的基础上，描述了用FPGA实现FFT的方法，并对其中的整体结构、蝶形单元及性能等进行了分析。
关键词：
FPGA FFT
傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数N的平方成正比关系，因此，在N较大时，直接应用DFT算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用FPGA来实现2k／4k／8k点FFT的设计方法。
1 整体结构
一般情况下，N点的傅立叶变换对为：
其中，WN＝exp(－2 pi／N)。X(k)和x(n)都为复数。与之相对的快速傅立叶变换有很多种,如DIT(时域抽取法)、DIF（频域抽取法）、Cooley－Tukey和Winograd等。对于2n傅立叶变换，Cooley－Tukey算法可导出DIT和DIF算法。本文运用的基本思想是Cooley－Tukey算法，即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然DIT与DIF有差别，但由于它们在本质上都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能上的优劣之分，所以可以根据需要任取其中一种，本文主要以DIT方法为对象来讨论。
N＝8192点DFT的运算表达式为：
式中，m＝(4n1＋n2)(2048k1＋k2)(n＝4n1＋n2，k＝2048k1＋k2)其中n1和k2可取0,1,．．．,2047,k1和n2可取0,1,2,3。
由式（3）可知，8k傅立叶变换可由4×2k的傅立叶变换构成。同理，4k傅立叶变换可由2×2k的傅立叶变换构成。而2k傅立叶变换可由128×16的傅立叶变换构成。128的傅立叶变换可进一步由16×8的傅立叶变换构成，归根结底，整个傅立叶变换可由基2、基4的傅立叶变换构成。2k的FFT可以通过5个基4和1个基2变换来实现；4k的FFT变换可通过6个基4变换来实现；8k的FFT可以通过6个基4和1个基2变换来实现。也就是说：FFT的基本结构可由基2／4模块、复数乘法器、存储单元和存储器控制模块构成，其整体结构如图1所示。
图1中，RAM用来存储输入数据、运算过程中的中间结果以及运算完成后的数据，ROM用来存储旋转因子表。蝶形运算单元即为基2／4模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结果。
2 蝶形运算器的实现
基4和基2的信号流如图2所示。图中，若A＝r0＋j＊i0，B＝r1＋j＊i1，C＝r2＋j＊i2，D＝r3＋j＊i3是要进行变换的信号，Wk0＝c0＋j＊s0＝1，Wk1＝c1＋j＊s1，Wk2＝c2＋j＊s2，Wk3＝c3＋j＊s3为旋转因子，将其分别代入图2中的基4蝶形运算单元，则有：
A′＝[r0＋(r1×c1－i1×s1)＋(r2×c2－i2×s2)＋(r3×c3－i3×s3)]＋j[i0＋(i1×c1＋r1×s1)＋(i2×c2＋r2×s2)＋(i3×c3＋r3×s3)]� （4）
B′＝[r0＋(i1×c1＋r1×s1)－(r2×c2－i2×s2)－(i3×c3＋r3×s3)]＋j[i0－(r1×c1－i1×s1)－(
i2×c2＋r2×s2)＋(r3×c3－i3×s3)] (5）
C′＝[r0－(r1×c1－i1×s1)＋(r2×c2－i2×s2)－(r3×c3－i3×s3)]＋j[i0－(i1×c1＋r1×s1)＋(i2×c2＋r2×s2)－(i3×c3＋r3×s3)] （6）
D′＝[r0－(i1×c1＋r1×s1)－(r2×c2－i2×s2)＋(i3×c3＋r3×s3)]＋j[i0＋(r1×c1－i1×s1)－(i2×c2＋r2×s2)－(r3×c3－i3×s3)]� （7）
看明白了吗？
② 傅里叶变换
离散傅里叶变换(discrete Fourier transform) 傅里叶分析方法是信号分析的最基本方法，傅里叶变换是傅里叶分析的核心，通过它把信号从时间域变换到频率域，进而研究信号的频谱结构和变化规律。但是它的致命缺点是： 计算量太大，时间复杂度太高，当采样点数太高的时候，计算缓慢， 由此出现羡梁了DFT的快速实现，即下面的快速傅里叶变换FFT。
这里原始信号的三个正弦波的频率分别为，200Hz、400Hz、600Hz,最大频率为600赫兹。根据采样定理，fs至少是600赫兹的2倍，这里选择1400赫兹，即在一秒内选择1400个点。
1400
[-4.18864943e-12+0.j 9.66210986e-05-0.04305756j 3.86508070e-04-0.08611996j
8.69732036e-04-0.12919206j 1.54641157e-03-0.17227871j]
换之后的结果数据长度和原始采样信号是一样的
每一个变换之后的值是一个复数，为a+bj的形式下标为0和 N /2的两个复数的虚数部分为0，下标为i和 N - i 的两个复数共辄，也就是其虚部数值相同、符号相反。再用ifft()从频域转回时域之后，出现了由误差引起的很小的虚部，用np.real()取其实部即可．
由于一半是另一半的共轭，因此只需要关心一半数据．fft转换后下标为0的春派巧实数表示时域信号中的直流成分（不随时间变化）
振幅谱的纵坐标很大，而且具有对称性
Y=A1+A2 cos(2πω2+φ2）+A3 cos(2πω3+φ3）+A4*cos(2πω4+φ4）
经过FFT之后，得到的“振幅图”中，
第一个峰值（频率位置）的模是A1的N倍，N为采样点，本例中为N=1400，此例中没有，因为信号没有常数项A1
第二个峰值（频率位置）的模是A2的N/2倍，N为采样点，
第三个峰值（频率位置）的模是A3的N/2倍，N为采样点，
第四个峰值（频率位置）的模是A4的N/2倍，N为采样点，
STFT短时傅里叶变换，实际上是对一系列加窗数据做FFT。有的地方也会提到DCT（离散傅里叶变换），而DCT跟FFT的关系就是：FFT是实现DCT的一种快速算法。
FFT有个参数N，表示对多少个点做FFT，如果一帧里面的点的个数小于N就会zero-padding到N的长度。每个点对应一个频率点，某一点n（n从1开始）表示的频率为:
第一个点（n=1，Fn等于0）表示直流信号，最后一个点N的下一个点（实际上这个点是不存在的）表示采样频率Fs。
FFT后我们可以得到N个频点，比如，采样频率为16000，N为1600，那么FFT后就会得到1600个点扒键，FFT得到的1600个值的模可以表示1600个频点对应的振幅。因为FFT具有对称性，当N为偶数时取N/2+1个点，当N为奇数时，取(N+1)/2个点，比如N为512时最后会得到257个值。
scipy.signal.stft（x，fs = 1.0，window =‘hann’，nperseg = 256，noverlap = None，nfft = None，detrend = False，return_oneside = True，boundary =‘zeros’，padded = True，axis = -1 ）