快速傅里叶变换——理论
离散信号傅里叶变换的公式如下所示：
离散傅里叶变换的an和bn 离散傅里叶变换例题解析
离散傅里叶变换的原理是将原本非周期的信号复制扩展为周期信号，在实际的数字电路处理中，处理的信号是有限长的，取长度为N，即N为信号 的周期，对于有限长周期信号，其离散傅里叶变换有如下性质：
其中 为周期信号的傅里叶级数，而 表示当且仅当 时有 ，因此可以将傅里叶变换转为离散表达，如下所示：
考虑 以N为周期，因此仅需要计算k从0到N-1即可，取 此公式写成矩阵乘法模式如下所示：
W为一个 的方阵，该计算的复杂度为
对于系数矩阵中的元素 ，其公式如下所示：
考虑 ，推导公式如下所示：
再考虑 和 的情况：
再考虑 和 的情况：
最后考虑 且 或 的情况：
根据上述推导，可以得出系数W具有以下四条性质，这三条性质会在后续推导中用到：
基n快速傅里叶变换用于一个长度N为 的序列，例如基2快速傅里叶作用在 的序列上，基4快速傅里叶作用在 的序列上。现在考虑基2FFT的推导（硬件实现一般使用基4或基8FFT实现），首先写出有限长离散序列的傅里叶变换，记一个信号 的FFT变换为 ：
快速傅里叶变换的核心思想为 分而治之 ，即 分治法 ，该思想的核心是将一个长度为N的问题，分级为两个长度为 的问题，应用在这里即是需要将一个序列长度为N的FFT变换问题分解为两个序列长度为 的FFT变换。首先进行如下变换：
矩阵的形式如下所示：
根据W的性质 ，代入后有：
矩阵形式的表达如下所示，现在的矩阵为两个个高度为N，长度为N/2的矩阵。
代入 ，根据W的性质 有：
矩阵表达如下所示：
代入 ，根据W的性质 有：
矩阵表达如下所示：
根据上述推导，一个长度为N点的离散傅里叶变换被变为一个长度为 的离散傅里叶变换，取 公式如下所示：
根据频域抽取基2FFT的算法，除了按前后分类外，还可以直接按奇偶进行分类，公式如下所示：
对应的矩阵表示为：
取序列 ， 代入上述表达式，取 再代入W的变换性质可得：
其对应的矩阵为：
即将对F[k]的上半部分结果分解为两个FFT结果的和，即：
现在考虑F[k]的下半部分，公式如下所示：
取 ，代入有：
代入W的性质 和 ，有：
将变量i更换为k，其矩阵形式为：
最终可以将结果汇总为：
蝶形运算的公式如下，蝶形运算输入为 和 ，输出为 和 ，系数为 ：
其转换为矩阵表达为：
蝶形公式对应着2点FFT的计算，2点FFT的计算如下所示：
转换为矩阵表达为：
对应到蝶形运算有：
首先列出基2频域抽取FFT的分治公式：
以一个8点FFT为例，输入序列为：
进行第一次分治，分为两个4点FFT，序列为：
示意图如下所示，偶数标号的结果由第一个FFT生成，奇数标号的结果由第二个FFT生成：
随后进行第二次分治，将每个4点FFT分解为两个2点FFT，每个序列为：
示意图如下所示：
最终通过2点FFT计算出结果，但如上图所示，计算出的结果位置与标号并不对应，例如计算输出的标号为2的数据（Y10[1]）应当位于输出序列（X）的标号4（X[4]）。其变换规律为计算输出的标号为n的数据（第n+1个数据）对应到输出序列标号为m的数据，n为m的二进制反序。以计算输出标号为6（第七个数据）的数据Y13[0]为例，6的二进制为110，反序为011，对应十进制数为3，即有 。
首先列出时域抽取FFT的分治公式：
傅里叶级数 a0 an bn 怎么求
f(x)=a0 + a1*cos(wx) + a2*cos(2wx) + ...+ b1*sin(wx) +b2*sin(2wx) +...
所以
f(-x)=a0 + a1*cos(-wx) + a2*cos(-2wx) + ...+ b1*sin(-wx) +b2*sin(-2wx) +...
cos是偶函数,sin是奇函数,所以
f(-x)=a0 + a1*cos(wx) + a2*cos(2wx) + ...- b1*sin(wx) -b2*sin(2wx) +...
所以f(-x)的a0'就是a0,an'就是an,但是bn'=-bn
a0=1/μ∫f（x）dx
an=1/μ∫f（x）cosnx/μdx
bn=1/μ∫f（x）sinnx/μdx
积分区间为（-μ，μ）
μ可以等于π
傅立叶变换的定义
1、离散信号分析：
会求解离散序列的Z变换及反Z变换、理解傅立叶变换的定义、物理意义；掌握离散信号的频谱求解方法，序列傅立叶变换的性质，在此基础上分析信号频谱的特点。
2、离散系统分析：
会通过差分方程描述系统结构或由系统结构写出差分方程，求解系统的时域特性和Z域特性（H（z）），理解离散系统的频率响应特性的定义及其物理意义，掌握系统的频率响应的公式求解方法和几何作图求解方法，并在基础上能够分析系统的频域特性（包括幅频和相频特性），在频域内求解系统的响应。会判断什么是最小相移系统，最大相移系统和全通系统。
3、离散傅立叶级数：
理解离散傅立叶级数的定义、性质及其物理意义，掌握离散的周期序列的频谱求解方法及其特点，会计算序列的周期卷积。
4、离散傅立叶变换及快速傅立叶变换：
理解离散傅立叶变换的定义，掌握离散傅立叶变换的计算方法。深刻理解离散傅立叶变换每个性质的物理意义并能够证明，如：平移特性、滤波特性、对称特性、圆周卷积与线性卷积的关系、圆周卷积定理、频域取样定理，频率特性的内插方法等等，会计算圆周卷积。正确理解快速傅立叶变换的本质，掌握按时间抽取和按频率抽取的两种快速傅立叶变换方法。了解加权技术的应用背景及常用窗函数的频谱特性，了解线性调频Z变换的基本原理。
5、数字滤波器的结构：
掌握无限长冲激响应数字滤波器（IIR DF）和有限长冲激响应数字滤波器（FIR DF）的时域、Z域的描述形式与区别，它们各自的常用结构形式。
6、数字滤波器的设计：
掌握IIR DF的两种典型设计方法（脉冲响应不变法和双线性变换法，注意：包括相应的模拟滤波器设计方法）及各自的特点，掌握FIR DF的两种典型设计方法（窗函数设计法和频率取样设计法）及各自的特点，掌握具有线性相位的FIR DF的时域和频域特点，了解数字滤波器的计算机辅助设计方法。
虽然我曾经也算是学数学的，但也没搞太明白，就知道很有用，而且操作比较复杂
