高级变换用语言编程实现dftfft.pdfVIP

1实验目的

1.1不使用MATLAB现有的FFT函数，自己编写所有具体算法。

1.2给出流程图和理论计算结果。

1.3设计实验，给出DFT和FFT算法差异的证明，如复杂度等。（精度、不同长度的序列

等）

1.4分析数据，给出结论。

2实验原理

2.1离散傅里叶变换的快速算法FFT

N点序列x(n)的DFT为：

N−1

nkk=0,,N−1

X(k)=x(n)W

N

n=0

మಘ

୬୩◌ି୨୬୩

由于系数W=eొ◌是一个周期函数：

nk(N+n)kn(N+k)

W=W=W

NNN

nkmnknknk/m

W=WW=W

NmNNN/m

↓

2π

−jmnk

mN

e

2πN

−j⋅

N2−jπ

e=e=−1

↑

0N/2(k+N/2)k

W=1W=−1W=−W

NNNN

且是对称的：

nk*−nk(N−n)kn(N−k)

(W)=W=W=