①直接利用DFT计算:复乘次数为N2,复加次数为N(N-1)利用FT计算:复乘次数为og:n复加次数为log:解

一、傅立叶变换 一离散时间傅立叶变换(Discrete-Time- Fourier Transform,DTFT)(定义、收敛条件、性质)离散傅立叶变换( Discrete Fourier Transform,DFT)(定义、性质) 二、Z变换(定义、收敛条件、逆变换、性质)

一、二维DFT

3.3频率抽样理论 一,频域采样定理 时间(频率)函数抽样导致频率(时间)函数周期化对Z变换在单位圆上等间隔抽样一即对X(e抽样,频率抽样点数为N,则:

3.1离散傅立叶变换的定义 DFT的定义 设x(n)是一个长度为M的有限长序列,则定义的N点离散傅立 叶变换为

第四章快速傅立叶变换(FFT) 主要内容: 一、/DFT的问题及解决途径 二、FFT的原理和复杂性 三、按时间抽取的FFT算法 四、按频率抽取的FFT算法 五、离散傅立叶反变换的快速算法 六、线性调频z变换(chirp-z变换)算法 七、线性卷积的FFT算法

一、FFT算法的基本思想