10/3/2019,1,正交变换及其快速算法,3.1 快速傅里叶变换(FFT),FFT算法分类： 1) 按时间抽取(DIT) 2) 按频率抽取(DIF),快速傅里叶变换(FFT),10/3/2019,2,3.1.1 按时间抽取(DIT)的FFT,按时间抽取(DIT)的FFT,10/3/2019,3,这样，一个N点的DFT被分解成两个N/2点的DFT,10/3/2019,4,10/3/2019,5,总结：FFT算法的两个特点 1) 原位运算 即每一级运算的结果仍然存储在原来的存储器中 2) 变址 输入倒序，输出顺序，存在“码位倒置”,10/3/2019,6,3.1.2 按频率抽取(DIF)的FFT,按频率抽取(DIF)的FFT,10/3/2019,7,10/3/2019,8,3.1.3 IFFT的运算方法,算法一：FFT流图中所有系数变符号，再除以常数N, 然后输入输出位置对换，即为IFFT,算法二：改变蝶形公式 时间抽取的FFT频率抽取的IFFT 频率抽取的FFT时间抽取的IFFT,IFFT的运算方法,10/3/2019,9,3.1.4 混合基FFT算法,定义：当N是一个复合数,即可把N分解成一些因子的乘积 则可以用FFT的一般算法,混合基FFT算法,10/3/2019,10,10/3/2019,11,3.2 快速傅里叶变换的应用,3.2.1 利用FFT求线性卷积快速卷积,快速卷积的步骤：,利用FFT求线性卷积快速卷积,10/3/2019,12,3.2.2 利用FFT求相关快速相关,快速卷积的步骤：,利用FFT求相关快速相关,10/3/2019,13,附：如果x(n)=y(n)则求得的是自相关序列,