基于MATLAB的FFT算法实现(论文)(12)

序列，将计算量大大降低。

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

x(2r) x1(r)

, x(2r 1) x(r) 2

nk

Xk xnW N

n 0N 1

r 0,1, ,

N

12

N 2

n 0,2,4...N 12

x n W

nkN

n 1,3,5...N 12

N 1

nk

x n WN

r 0,1N 12

2rk

x 2r WN

r 0,1N

12

x 2r 1 WN

2r 1 k

r 0,1

x r W

1

2rkN

r 0,1

x r W

2

2r 1 kN

nk

利用系数 WN的可约性，即

2rkW N e

2

2rk

N

j

e

N12r 0

2 rk2

rk

WN

rkk

X k x1 r WN WN x2 r WNrk

r 0

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

N

12

用蝶形运算可表式为：

以此类推，还可以把x1(n)和x2(n)按n值得奇偶分为两个序列，这样就达到了降N得目的，从而减少了运算量。

FFT对DFT的数学运算量改进：

直接采用DFT进行计算，运算量为N^2次复数乘法和N*(N-1)次复数乘法。

第 9 页 共 23页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库基于MATLAB的FFT算法实现(论文)(12)在线全文阅读。