数字信号处理第三四章DFT及FFT

1、第三章 DFT主要内容：主要内容：引言引言2/2/)(1)()()(pptttjmcpctjccdtetxtmXFourierdtetxjXFourier 变换（级数）：周期连续时间信号的变换：非周期连续时间信号的频谱连续频谱连续,非周期非周期频谱离散频谱离散,非周期非周期DTFT )(nnjjenxeX 非周期离散时间（或有限长序列非周期离散时间（或有限长序列xn）的）的Fourier 变换变换若若 0n N1 离散离散Fourier变换变换 (DFT) 周期离散时间序列周期离散时间序列的的Fourier 变换变换DFS频谱连续频谱连续,周期周期频谱离散频谱离散, 周期周期频谱离散频谱离散一

2、、离散傅里叶级数（一、离散傅里叶级数（DFSDFS）3.13.1周期序列的周期序列的ZTZT不收敛不收敛可用离散傅里叶级数表示离散周期序列，即用可用离散傅里叶级数表示离散周期序列，即用周期为周期为N N的复制数序列来表示的复制数序列来表示1021NkknjNekXNnx令令WN = ej 2/N旋转因子旋转因子)/sin()/sin() 1(NkNkMekNMnukNnuMkNjknRM可见可见0100200300400500600700800-0.4-0.200.20.40.60.810100200300400500600700800-0.4-0.200.20.40.60.81MNMN-2N

3、/M -N/M 0 N/M 2N/M e.g. M=4,N=12)(kX)(jeXX(k)二、离散傅里叶级数的性质二、离散傅里叶级数的性质3.1 3.1 离散傅里叶变换及其性质离散傅里叶变换及其性质一、离散傅里叶变换定义一、离散傅里叶变换定义8、DFT与与ZT、序列、序列Fourier的关系的关系 x(n)x(n)的离散傅里叶变换的结果与变换区间的离散傅里叶变换的结果与变换区间N N的长度有关的长度有关二、离散傅里叶变换的性质二、离散傅里叶变换的性质B B、序列分解、序列分解C C、DFTDFT的共轭对称性的共轭对称性有限长序列有限长序列有限长共轭对称序列有限长共轭对称序列有限长共轭反对称序列

4、有限长共轭反对称序列ReDFTx(n)ImDFTx(n)ReDFTxep(n)ImDFTxep(n)ReDFTxop(n)ImDFTxop(n)ReDFTx(n)ImDFTx(n)ReDFTxep(n)ImDFTxep(n)ReDFTxop(n)ImDFTxop(n)ReDFTx(n)ImDFTx(n)ReXepImXopM=16点循环卷积点循环卷积M=8点循环卷积点循环卷积X1(n)，N1=4X2(n)，N2=4循环卷积的圆形示意图循环卷积的圆形示意图3.3 3.3 频率采样频率采样Frequency SamplingFrequency Sampling一、序列的几种变换之间的关系一、序列的

5、几种变换之间的关系二、由二、由N N个频率取样值个频率取样值X(k)X(k)恢复序列恢复序列x(n)x(n)三、从三、从N N个取样值恢复个取样值恢复X(Z)X(Z)或或X(eX(ejwjw) )3.4 利用循环卷积计算线性卷积L=5点循环卷积点循环卷积L=6点循环卷积点循环卷积L=7点循环卷积点循环卷积L=8点循环卷积点循环卷积分段卷积分段卷积 3.5 3.5 快速傅里叶变换快速傅里叶变换Fast Fourier TransformFast Fourier TransformFFTFFT一、一、DFTDFT的计算量的计算量直接利用直接利用DFTDFT的定义式计算的定义式计算DFTDFT，如下

6、式所示，如下式所示二、时间抽选的基二、时间抽选的基2-FFT( )2-FFT( )Decimation-In-TimeDecimation-In-TimeDIT FFTDIT FFTMN2MN2时间偶奇分时间偶奇分 频率前后分频率前后分计算量：一个复数乘法，两个复数加法计算量：一个复数乘法，两个复数加法1.本级有本级有4个（个（N/2）蝶形蝶形2.N点点DFT可由两个可由两个N/2DFT计算计算8点点FFT示意图示意图1N/2点点DFT可由两个可由两个N/4DFT计算计算本级共有有本级共有有4个（个（N/2）蝶形蝶形8点点FFT示意图示意图2（基本原则同示意图（基本原则同示意图1）时间时间偶奇

7、偶奇分分频率前后分频率前后分8点点DFT的的FFT示意图示意图共有共有3（M）级，每级有）级，每级有4（N/2）个蝶形，共）个蝶形，共M* N/2个蝶形个蝶形两点两点DFT，蝶形，蝶形不能再分解了不能再分解了基本运算：蝶形运算环节基本运算：蝶形运算环节FFT的运算量为：的运算量为： M* N/2个复数乘法，个复数乘法， M* N个复数加法个复数加法31）同址（原位）运算）同址（原位）运算每一级的蝶形的输入与输出在每一级的蝶形的输入与输出在运算前后运算前后可以存储在可以存储在同一地址同一地址的存储单元中。的存储单元中。同址运算的优点：节省存储单元，降低了硬件实现成本同址运算的优点：节省存储单元，

8、降低了硬件实现成本2）蝶形运算两节点间的）蝶形运算两节点间的“距离距离”第一级：第一级：1第二级第二级2第三级：第三级：4蝶形两节点的蝶形两节点的“距离距离”：其中：其中：L:第几级蝶形运算第几级蝶形运算3）旋转因子的变化规律）旋转因子的变化规律第一级第一级第二级第二级第三级第三级4)蝶形运算规律蝶形运算规律第第L级级5)变址运算变址运算混混 序序正序输入正序输入正序输出正序输出变址运算变址运算变址运算的目的：实现变址运算的目的：实现FFT算法的算法的正序正序输入、输入、正序正序输出输出变址计算：变址计算：IJ，x(I)与与x(J)交换位置交换位置6）编程思想）编程思想三、频率抽选基三、频率抽

9、选基2-FFT2-FFT算法算法Decimation-In-Frequency FFT-DIF FFTDecimation-In-Frequency FFT-DIF FFT 对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点怎样排列，所得到的流程图总是等效的。论节点怎样排列，所得到的流程图总是等效的。 对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点怎样排列，所得到的流程图总是等效的。论节点怎样排列，所得到的流程图总是等效的。四、快速逆傅里叶变换四、快速逆傅里叶变换-IFFT对上式两端取共轭对上式两端取共轭X*(k)的的DFT五、实序列的五、实序列的FFTFFT进一步减小计算量为为实实函函数数)( nx1.构建两个新序列构建两个新序列2.用用FFT计算出计算出D