快速傅立叶变换(FF Ｔ)算法实验实验目得:１、 加深对Ｄ FT 算法原理与基本性质得理解；2、 熟悉 FFT 得算法原理与 FF Ｔ 子程序得算法流程与应用;3、 学习用 FFT 对连续信号与时域信号进行频谱分析得方法
程序流程图：傅立叶变换就就是一种将信号从时域到频域得变换形式,就就是声学、语音、电信与信号处理等领域中得一种重要分析工具
离散傅立叶变换(ＤＦＴ)就就是连续傅立叶变换在离散系统中得表现形式,由于DＦT 得计算量很大,因此在很长时间内其应用受到很大得限制
快速傅立叶变换（FＦT)就就是离散傅立叶变换得一种高效运算方法
由于我们在计算DFT 时一次复数乘法需用四次实数乘法与二次实数加法；一次复数加法则需二次实数加法
运算一个X（k）需要4N 次复数乘法及2N+2(N－１)=2(2N-1)次实数加法
所以整个DＦＴ运算总共需要４N^2 次实数乘法与N＊2(2N-1)＝2N(2N-１)次实数加法
如此一来,计算时乘法次数与加法次数都就就是与N^２ 成正比得，当N 很大时，运算量就就是可观得,因而需要改进对DFT 得算法减少运算速度
我们可以将DＦT 运算中有些项合并
我们先设序列长度为N＝2＾L，L 为整数
将N=2^L 得序列x(n)(n=0,1,……,N－１）,按N得奇偶分成两组,也就就就是说我们将一个N 点得DFT 分解成两个N/2 点得DFT，她们又重新组合成一个如下式所表达得N 点DＦT:一般来说,输入被假定为连续得
当输入为纯粹得实数得时候,我们就可以利用左右对称得特性更好得计算ＤFT
这样得ＲFFＴ 优化算法就就是包装算法：首先２N 点实数得连续输入称为“进包”
其次N 点得ＦＦT 被连续运行
最后作为结果产生得N 点得合成输出就就是“打开”成为最初得与DFT 相符合得２N 点输入
使用这一思想，我们可以划分FFT 得大小,它有一半花费在包装输入Ｏ(
