《信号分析与处理》第六章 快速傅里叶变换FFT

1、1第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第一节第一节 提高离散傅里叶变换运算速度的基本思路提高离散傅里叶变换运算速度的基本思路 DFTDFT： 计算机分析与处理，速度限制，实用计算机分析与处理，速度限制，实用效果较差，只应用于采样数据离线处理或事效果较差，只应用于采样数据离线处理或事后处理。后处理。 19651965年，科学家年，科学家J.W.CooleyJ.W.Cooley和和J.K.TukeyJ.K.Tukey设计设计了快速傅里叶算法，计算效率提高了了快速傅里叶算法，计算效率提高了1 1到到2 2个个数量级，离散系统分析开始了真正实用，数量级，离散系统分析开始了真正实用，

2、DFTDFT成为了数字信号处理的核心。成为了数字信号处理的核心。2第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第一节第一节 提高离散傅里叶变换运算速度的基本思路提高离散傅里叶变换运算速度的基本思路离散傅里叶变换的计算特点：离散傅里叶变换的计算特点： 快速傅里叶变换的基本思路：快速傅里叶变换的基本思路： nkNW的周期性和对称性的周期性和对称性 3第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取的快速傅里叶变换算法 时间抽取算法的基本思想：时间抽取算法的基本思想： k1N2k1N2X(k)+W X(k) , k =k NX(k )

3、=,k=0, 1, ., -1N2X(k)-W X(k) , k =k+24第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取的快速傅里叶变换算法 0142114201421142X(0)= X (0)+W X (0)X(1)= X (1)+W X (1)X(2)= X (0)-W X (0)X(3)= X (1)-W X (1)N N为为4 4时为例时为例01rk12120r=01201rk22220r=022X (0)=x(0)+W x(2)X (k)=x(2r)W , k=0, 1 X (1)=x(0)-W x(2)X (0)=x(1

4、)+W x(3)X (k)=x(2r+1)W , k=0, 1 X (1)=x(1)-W x(3)5第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取的快速傅里叶变换算法 6第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取的快速傅里叶变换算法 N=47第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取的快速傅里叶变换算法N=8 8第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取

5、的快速傅里叶变换算法9第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里叶变换算法时间抽取的快速傅里叶变换算法码位倒置：序列输入顺序为码位倒置顺序，输出顺序为自然顺序码位倒置：序列输入顺序为码位倒置顺序，输出顺序为自然顺序 表表6-2 6-2 自然顺序与码位倒置顺序（自然顺序与码位倒置顺序（N N=8=8）自然顺序二进制表示码位倒置码位倒置顺序000000001001100420100102301111064100001151011015611001137111111710第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第二节第二节 时间抽取的快速傅里

6、叶变换算法时间抽取的快速傅里叶变换算法FFTFFT时间抽取算法的运算规律：时间抽取算法的运算规律： 11第十章第十章 数字信号处理的实现数字信号处理的实现第二节第二节 快速傅里叶变换的软件实现快速傅里叶变换的软件实现基基2 2时间抽取算法为例，结合其流程图的特点和算法规律时间抽取算法为例，结合其流程图的特点和算法规律 码位倒置程序码位倒置程序雷德算法雷德算法：采用二进制的：采用二进制的“反向进位加法反向进位加法”依次产生对应某一字长依次产生对应某一字长的码位倒置排列序列。将权值最高的数值与的码位倒置排列序列。将权值最高的数值与1 1相加，若有进位，就相加，若有进位，就向较低一级权值位进位，即由

7、左向右进位。向较低一级权值位进位，即由左向右进位。 1213第十章第十章 数字信号处理的实现数字信号处理的实现第二节第二节 快速傅里叶变换的软件实现快速傅里叶变换的软件实现蝶形运算程序蝶形运算程序外层循环外层循环中层循环中层循环内层循环内层循环级控制循环级控制循环群控制循环群控制循环蝶控制循环蝶控制循环14第十章第十章 数字信号处理的实现数字信号处理的实现第二节第二节 快速傅里叶变换的软件实现快速傅里叶变换的软件实现蝶形运算程序 15第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第三节第三节频率频率抽取的快速傅里叶变换算法抽取的快速傅里叶变换算法X(k)x(n)奇偶分解奇偶分解前后分解

8、前后分解16第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第三节第三节频率频率抽取的快速傅里叶变换算法抽取的快速傅里叶变换算法N N=4=4的频率抽取算法蝶形图的频率抽取算法蝶形图17第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第三节第三节频率频率抽取的快速傅里叶变换算法抽取的快速傅里叶变换算法N N=8=8的频率抽取算法蝶形图的频率抽取算法蝶形图18第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第四节快速傅里叶反变换算法第四节快速傅里叶反变换算法 N-1nkNn=0N-1-nkNk=0X k =x n W1x n =X k WN19第六章第六章 快速傅里叶变换快速傅

9、里叶变换FFTFFT第四节快速傅里叶反变换算法第四节快速傅里叶反变换算法FFTFFT时间抽取算法时间抽取算法IFFTIFFT频率抽取算法频率抽取算法奇偶分解奇偶分解奇偶分解奇偶分解前后分解前后分解前后分解前后分解x(n)X(k)X(k)x(n)FFTFFT频率抽取算法频率抽取算法IFFTIFFT时间抽取算法时间抽取算法前后分解前后分解前后分解前后分解奇偶分解奇偶分解奇偶分解奇偶分解x(n)x(n)X(k)X(k)20第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第四节快速傅里叶反变换算法第四节快速傅里叶反变换算法N N=8=8的的IFFTIFFT时间抽取算法蝶形图时间抽取算法蝶形图 2

10、1第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第四节快速傅里叶反变换算法第四节快速傅里叶反变换算法 *1x n =FFTX (k)N直接利用直接利用FFTFFT算法计算算法计算IFFTIFFT： 22第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第五节离散卷积的快速算法第五节离散卷积的快速算法 N-1NNm=0 x nh n =x m h n-mRn 1N -1+m=-m=0y n =x n *h n =x m h n-m =x m h n-m离散卷积（线性卷积）离散卷积（线性卷积） 循环卷积（圆周卷积）循环卷积（圆周卷积） 23第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第五节离散卷积的快速算法第五节离散卷积的快速算法 +LpLr=-x nh n =y n+rL R n = y n R n循环卷积的计算结果就是将线性卷积经过周期延拓后循环卷积的计算结果就是将线性卷积经过周期延拓后再取主值区间的序列值再取主值区间的序列值 24第六章第六章 快速傅里叶变换快速傅里叶变换FFTFFT第五节离散卷积的快速算法第五节离散卷积的快速算法用循环卷积计算线性卷积的方法：用循环卷积计算线性卷积的方法： 线性卷积快速算法：线性卷积快速算法： 重叠相加法：重叠相加法： 2