离散傅里叶变换.pptxVIP

离散傅里叶变换;

快速傅里叶变换(FastFourierTrasform。简称FFT)是一种减少DFT计算时间的算法。在此出现之前，虽然DFT为离散信号的分析从理论上提供了变换工具，但是很难实现，因为计算时间很长。例如，对采样点N＝l000，DFT算法运算量约需200万次，而FFT仅约需1.5万次，可见FFT方法大大地提高了运算效率。因此，FFT方法于1965年由美国库利—图基(J.W.Cooley—J.W.Tukey)首先提出时，曾被认为是信号分析技术的划时代的进步。;FFT:FastFourierTransform

1965年，JamesW.Cooley和JohnW.Tukey在《计算数学》（《MathematicsofComputation》）上发表了“一种用机器计算复序列傅立叶级数的算法（AnalgorithmforthemachinecalculationofcomplexFourierseries）”论文。;计算DFT复数运算量;利用的固有对称性和周期性

改善DFT的运算效率;第6页，共61页，星期日，2025年，2月5日;时间抽取基-2FFT算法

Decimation-in-Time(DIT);一、算法原理;二、按时间抽选的基-2FFT算法;则x(n)的DFT:;一个N点的DFT被分解为两个N/2点DFT。X1(k)，X2(k)这两个N/2点的DFT按照：

;再利用周期性求X(k)的后半部分;求出后半部的表示式;频域中的N个点频率成分为：;由于N=2^L，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。;例子：求N=23=8点FFT变换

（1）先按N=8--N/2=4，做4点的DFT：;2、蝶形结;将N=8点分解成2个4点的DFT的信号流图;(2)N/2(4点)--N/4(2点)FFT

a先将4点分解成2点的DFT：;b求2点的DFT;c一个2点的DFT蝶形流图;d另一个2点的DFT蝶形流图;(3)将N/4（2点）DFT再分解成2个1点的DFT

a求2个一点的DFT;b2个1点的DFT蝶形流图;(4)一个完整N=8的按时间抽取FFT的运算流图;3按时间抽取FFT算法的特点;算法特点;例：N=8FFT运算，输入:;码位倒序规则;例子;倒位序;1.计算速度

当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。

;第33页，共61页，星期日，2025年，2月5日;;如N=512、1024和8192时，DFT的复数乘法运算

N2=5122=218=262144（26万次）

N2=10242=220=1048576（105万次）

N2=81922=226=6千7百万次）

对于大的N，在实际中是不能接受的，无法“实时”应用DFT。

Cooley与Tukey提出的FFT算法，大大减少了计算次数。如N=512时，FFT的乘法次数约为2000次，提高了约128倍，而且简化随N的增加而巨增，因而，用数值方法计算频谱得到实际应用。;频率抽取基-2FFT算法

Decimation-in-Frequency(DIF);算法原理;第38页，共61页，星期日，2025年，2月5日;按k的奇偶将X(k)分成两部分：;令;;N/2仍为偶数，进一步分解：N/2N/4;;同理：;第45页，共61页，星期日，2025年，2月5日;逐级分解，直到2点DFT;x1(0);DIF与DIT比较1;不同之处

DIF与DIT两种算法结构倒过来

DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。

DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。

蝶形结不同

DIT的复数相乘出现在减法之前。

DIF的复数相乘出现在减法之后。;快速傅里叶逆变换(IFFT);以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算IFFT的方法。;利用FFT计算IFFT的思路1;把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k)，原来按x(n)的奇、偶次序