基-2FFT算法的软件实现(共13页).doc

实验二 基-2FFT算法的软件实现一、实验目的1、 加深对DFT算法原理和基本性质的理解；2、 熟悉FFT算法的流程；3、 了解FFT算法的应用。二、基本原理1、 DFT算法原理（见教材第三章）2、 按时间抽取（DIT）的-2FFT算法（1）算法原理序列x(n)的N(N=2-M)点DFT为，k=0, 1, , N-1 （2.1）将式（2.1）按n的奇偶性分解为 （2.2）令, ，因为, 所以式（2.2）可写成 （2.3）式（2.3）说明，按n的奇偶性将x(n)分解为两个N/2长的序列x1(l)和x2(l)，则N点DFT可分解为两个N/2点DFT来计算。用X1(k)和X2(k)分别表示 （2.4） （2.5）将(2.4)式和(2.5)式代入(2.31)式，并利用和X1(k)、 X2(k)的隐含周期性可得到：