2、FFT算法的基本思想 考察DFT与IDFT的运算发现，利用以下两个特性可减少运算 量： 1)系数=e 是一个周期函数，它的周期性和 对称性可用来改进运算，提高计算效率。 例wN-)=wWN-0=wW 又如w2=-因w2》=-w 利用这些周期性和对称性，使DFT运算中有些项可合并； 2)利用wW心的周期性和对称性，把长度为N点的大点数的 DFT运算依次分解为若千个小点数的DFT。因为DFT的计算量正 比于N2,N小，计算量也就小。 F℉T算法正是基于这样的基本思想发展起来的。它有多种形 式，但基本上可分为两类：时间抽取法和频率抽取法
2、FFT算法的基本思想 考察DFT与IDFT的运算发现，利用以下两个特性可减少运算 量： 1）系数 是一个周期函数，它的周期性和 对称性可用来改进运算，提高计算效率。 例 又如 因此 利用这些周期性和对称性，使DFT运算中有些项可合并； 2）利用 的周期性和对称性，把长度为N点的大点数的 DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正 比于N 2 ，N小，计算量也就小。 FFT算法正是基于这样的基本思想发展起来的。它有多种形 式，但基本上可分为两类：时间抽取法和频率抽取法
3.3 FFT算法具体实现
3.3 FFT算法具体实现
一、按时间抽取的FFT(N,点DFT运其的分解》 先从一个特殊情况开始，假定N是2的整数次方（基2） N=2M,M:正整数 首先将序列x()分解为两组，一组为偶数项，一组为奇数项， x(2r)=x() r=0,1,.,N/2-1 x(2r+1)=x2(r)
一、按时间抽取的FFT（N点DFT运算的分解） 先从一个特殊情况开始，假定N是2的整数次方（基2） N=2M ，M：正整数 首先将序列x（n）分解为两组，一组为偶数项，一组为奇数项， r=0,1，.，N/2-1
将DFT运算也相应分为两组： x(K)=DFT(m]=∑xn)w n=0 偶数n=0 奇数n=1 N/2 W/2-1 ∑x(2rw+∑x(2r+1)wr+ r=0 r=0 N/2- N/2-1 ∑x(2r)w+w∑x(2r+1w r三0 r三0
将DFT运算也相应分为两组：
21 2元 2n 因为 =e =e =w 故 N/2-1 N/2-1 X(k)=∑x(2m)w*+T∑2r+1W 2 =G(k)+WH(k) 其中 N/2-1 Gk)=∑(2r)w N/2-1 A(k)=∑x(2r+w r=0 AN
因为 故 其中