按频率抽取快速傅里叶变换DIF.pdf

4.3 基-2按频率抽取的FFT算法 Decimation-in-Frequency(DIF) (Sander-Tukey) 一、算法原理 • 设输入序列长度为N=2M(M为正整数，将该序 列的频域的输出序列X(k)(也是N 点序列，按其 频域顺序的奇偶分解为越来越短的子序列，称 为基-2按频率抽取的FFT算法。也称为Sander- Tukey算法。 设序列点数N=2M ，M 为整数。 对X (k)按k 的奇偶分组前，先将输入x(n)按n 的 顺序分成前后两半： N 1 N /21 N 1 X (k ) x(n)W nk x(n)W nk  x(n)W nk N N N n 0 n 0 n N / 2 N / 21 nk N / 21  N  nN k  2  ( )   x n WN x n WN n 0 n 0  2  N / 21   N  Nk / 2  nk x (n) x n  2 WN WN n 0   WN / 2 1 N N / 21  k  N  nk    x (n) ( 1) x n 2 WN n 0   k 0,1,..., N 1 按k 的奇偶将X (k)分成两部分：  k 2r  r 0,1,..., N / 2 1 k 2r 1  N / 21   N  2nr X r x n x n W (2 )  ( )    2  N n 0   N / 21   N  nr x n x n W 