数字信号处理-课件 第5章 FFT快速傅氏变换.pptx

第5章F

快速傅氏变换

点击进入

§5-1引言

目§5-2DFT的运算量及改进的途径

§5-3按时间抽取(DIT)的FFT算法

录§5-4DIF的FFT算法

§5-5IFFT算法

§5-6线性卷积的FFT算法

2024年12月22日星期日

5-1引言

DFT在实际应用中很重要：可以计算信号

的频谱、功率谱和线性卷积等。

◆直接按DFT变换进行计算，当序列长度M很

大时，计算量非常大，所需时间会很长。

◆FFT不是一种新的变换，而是DFT算法的一

种改进，这种改进实现了快速计算的目的

§5-2DFT的运算量及改进途径

5.2.1DFT的计算量估计

k=0,1,,N-1

,n=0,1,…,N-1

两公式基本结构类似，其差别仅在WN指数

的符号不同、及逆变换的因子1/N.

2024年12月22日星期日

个X(k)的运算量，如X(1)

X(1)=x(0)W°+x(1)WN+x(2)W²+…+x(N-1WN-

通常x(n)和WN都是复数，所以计算一个

X(k)的值需要N次复数乘法运算，和N-1次

复数加法运算.

计算全部X(k)就要N²次复数乘法运

算，N(N-1)次复数加法运算.

当N很大时，运算量将是惊人的，如N=1024,

则要完成1048576次(一百多万次)运算.这

样，难以做到实时处理.

2024年12月22日星期日

运算量估计结论

1.乘法运算的时间是加法的一个量级以上

2.DFT运算量与N²成正比

降低运算量的措施：

1)N—运算量I(有效途径)

2)利用W的有关特性

2024年12月22日星期日

5.2.1降低运算量的途径

1.利用WNk的特性

对称性：

周期性：

可约性：

得：

N

WN²=-1

利用上述特性，可以将有些项合并.

2024年12月22日星期日

2.将DFT分解为短序列

可以有效降低运算量，提高运算速度.

1965年，cooley和Tukey首先提出FFT算法.对于

N点DFT,仅需(N/2)log₂N次复数乘法运算.

如：N=1024=210,需要计算的次数是：

(1024/2)log2210=512*10=5120次

而5120/1048576=4.88%

速度提高20倍

2024年12月22日星期日

§5-3按时间抽取(DIT)FFT算法

—库利-图基算法

算法原理

按时间抽取基-2FFT算法与直接计

算DFT运算量的比较

按时间抽取的FFT算法的特点

按时间抽取FFT算法的其它形式流

程图

2024年12月22日星期日

§5-3按时间抽取(DIT)的FFT算法

—库利一图基算法

5.3.1算法原理(基2-FFT)

1.N点DFT分解为两个N/2点DFT

(1)先将x(n)按n的奇偶分为两组作DFT,设

N=2L,不足时，可补些零。这样有：

n为偶数时：x(2r)=x₁(r),r=0,1,…,2-1

n为奇数时：x(2r+1)=x₂(r),r=0,1,…,2-1

N-1

因此，X(k)=DFT[x(n)]=∑x(n)W

n=0

2024年12月22日星期日

X(k)=艺x(n)Wn+