数字信号处理基于MATLAB的FFT算法设计课设说明书(5)

旋转因子的周期性，对称性和可约性。利用这两个途径实现DFT的快速傅里叶变换(FFT)，FFT算法基本上可分为按时间抽取的FFT算法(DIT-FFT)和按频率抽取的FFT算法(DIF-FFT)。

旋转因子的性质：

kn(k N)nk(n N)WN WN WN(1) 周期性 (2) 共轭对称性 (3) 可约性

kn( k)n*k( n)*WN [WN] [WN]mknWNkn WmN,

/m

WNkn WNkn/m

本次课设要求用基2的按时间抽取的FFT算法(DIT-FFT)实现FFT功能，设序列x(n)的长度为N，且N满足N=2M，M为正整数。若N不能满足上述关系，可以将序列x(n)补零实现。按时间抽取基2-FFT算法的基本思路是将N点序列按时间下标的奇偶分为两个N/2点序列，计算这两个N/2点序列的N/2点DFT，计算量可减小约一半；每一个N/2点序列按照同样的划分原则，可以划分为两个N/4点序列，最后，将原序列划分为多个2点序列，将计算量大大降低。

按时间下标的奇偶将N点x(n)分别抽取组成两个N/2点序列，分别记为x1(n)和x2(n)，将x(n)的DFT转化为x1(n)和x2(n)的DFT的计算。

2rk

WN e

2

j2rk

N

j

x(2r) x1(r)

,

x(2r 1) x2(r)

nk

X k x n WN

n 0N 2N 1

r 0,1, ,

N 12

n 0,2,4...N 12

x n W

nkN

n 1,3,5...N 12

x n W

N 1

nkN

r 0,1N 12

x 2r W x r W

1

2rkN

r 0,1N 12

x 2r 1 W

2

2r 1 kN

2rkN

r 0,1r 0,1

x r W

2r 1 kN

利用旋转因子的可约性，即：

2

rk2

e

rk

WN

rkk

X k x1 r WN WN x2 r WNrk

r 0

r 0

k X（ WNX（k）,0 k N 11k）2

N

12N 12

用蝶形运算可表示为如图3-2所示：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数字信号处理基于MATLAB的FFT算法设计课设说明书(5)在线全文阅读。