第四章 快速傅里叶变换FFT

第4章 快速傅里叶变换

第四章 快速傅里叶变换

第4章 快速傅里叶变换

4.1 4.2

引言 直接计算DFT的问题及改进的途径

4.34.4 4.5 4.6 4.7

按时间抽取(DIT)的基2-FFT算法按频率抽取(DIF)的基2-FFT算法 离散傅里叶反变换(IDFT)的快速计算方法 线性卷积的FFT算法——快速卷积 FFT的其他应用

第4章 快速傅里叶变换

本章学习目标理解按时间抽选的基-2FFT算法的算法原理、运算 流图、所需计算量和算法特点

理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点 了解IFFT算法 理解线性卷积的FFT算法及分段卷积算法

第4章 快速傅里叶变换

4.1 引 言快速傅里叶变换(FFT)并不是一种新的变换， 而是 离散傅里叶变换(DFT)的一种快速算法。  由于有限长序列在其频域也可离散化为有限长序列， 因此离散傅里叶变换(DFT)在数字信号处理中是非常有 用的。例如，在信号的频谱分析、 系统的分析、 设计和 实现中都会用到DFT的计算。 但是，在相当长的时间里， 由于DFT的计算量太大，即使采用计算机也很难对问题进 行实时处理，所以并没有得到真正的运用。 直到1965年

首次发现了DFT运算的一种快速算法以后，情况才发生了根本的变化。

第4章 快速傅里叶变换

人们开始认识到DFT运算的一些内在规律，从而很快

地发展和完善了一套高速有效的运算方法， 这就是现在人们普遍称之为快速傅里叶变换(FFT)的算法。 FFT出现后使DFT的运算大大简化，运算时间一般可缩

短一二个数量级之多，从而使DFT的运算在实际中真正得到了广泛的应用。本章主要介绍最基本的基2-FFT 算法及其编程思想。

第4章 快速傅里叶变换

4.2 直接计算DFT的问题及改进的途径4.2.1 直接计算DFT的运算量问题 设x(n)为N点有限长序列，其DFT为

X (k ) x(n )Wn 0

N 1

nk N

k=0, 1, …, N-1

(4-1)

反变换(IDFT)为

1 x ( n) N

X (k )Wk 0

N 1

nk N

n=0, 1, …, N-1

(4-2)

第4章 快速傅里叶变换

直接计算的运算量 一个X(k)值 N个X(k)值 一个X(k)值 N个X(k)值

复数乘法 N次 N2次 实数乘法 4N次 4N2次

复数加法 (N-1)次 N(N-1)次 实数加法 2N+2(N-1)次 2N(2N-1)次

第4章 快速傅里叶变换 例1 根据式(4-1),对一幅N×N点的二维图像进行

DFT变换，如用每秒可做10万次复数乘法的计算机，当 N=1024时，问需要多少时间(不考虑加法运算时间)? 

解： 直接计算DFT所需复乘次数为(N2)2≈1012次，因此用每秒可做10万次复数乘法的计算机，则需要近3000小时。 这对实时性很强的信号处理来说，要么提高计算速度， 而这样，对计算速度的要求太高了。另外，只能通过改进 对D

FT的计算方法，以大大减少运算次数。

第4章 快速傅里叶变换 4.2.2 改善途径 能否减少运算量，从而缩短计算时间呢？仔细观察 DFT的运算就可看出， 利用系数WNnk的以下固有特性，就

可减少运算量： (1) WNnk的对称性kn ( ( (WN )* WN kn WN N k ) n WN N n ) k

(2) WNnk的周期性

W

nk N

W

( n N )k N

W

n(k N ) N

第4章 快速傅里叶变换

(3) WNnk的可约性

W另外

kn N

W

mnk mN

e

j

2 mnk mN

,W

kn N

W

nk / m N /m

n ( ( k WN ( N k ) WN N n ) k WN nk ,WNN / 2 1,WNk N / 2 ) WN

FFT算法的基本思想：利用DFT系数的特性，合并DFT运算

中的某些项，把长序列DFT转换成短序列DFT,从而减少其运算量。 FFT算法分类：1.时域抽选法FFT(DIT-FFT) 2.频域抽选法FFT(DIF-FFT)

第4章 快速傅里叶变换

4.3 按时间抽取(DIT)的基 -2 FFT算法4.3.1 算法原理 设序列x(n)长度为N,且满足N=2L ,L为正整数。按n的 奇偶把x(n)分解为两个N/2点的子序列：

x(2r ) x1 ( r ) x(2r 1) x2 ( r )

N r 0,1, , 1 2

(4-4)

第4章 快速傅里叶变换

则可将DFT化为 N 1 nk X (k ) DFT [ x(n)] x(n)WN n 0

n 0 n为偶数

x(n)W

N 1

nk N

n 0 n为奇数

nk x(n)WN

N 1

N 1 2 r 0

2 x(2r )WN rk

N 1 2 r 0

( x(2r 1)WN 2 r 1) k N 1 2 r 0

N 1 2 r 0

2 k x1 ( r )(WN ) rk WN

2 x2 ( r )(WN ) rk

2 由于 WN e

2 j 2 N

e

j 2 /( N / 2 )N 1 2

WN / 2, 故上式可表示成

X (k )

N 1 2

r 0

rk k x1 (r )WN / 2 WN

r 0

rk k x2 (r )WN / 2 X 1 (k ) WN X 2 (k )

(4-5)

第4章 快速傅里叶变换

式中，X1(k)与X2(k)分别是x1(r)及x2(r)的N/2点DFT:

X 1 (k ) X 2 (k )

N 1 2 r 0

rk x1 (r )WN / 2

N 1 2 r 0

rk x(2r )WN / 2 N 1 2 r 0

(4-6)

N 1 2 r 0

rk x2 (r )WN / 2

rk x(2r 1)WN / 2

(4-7)

由此，我们可以看到，一个N点DFT已分解成两个N/2点的 DFT。 这两个N/2点的DFT再按照式(4-5)组合成一个N

点DFT。这里应该看到X1(k),X2(k)只有N/2个点，即k=0,1, …, N/2-1。而X(k)却有N个点，即k=0, 1, …, N-1, 故用式 (4-5)计算得到的只是X(k)的前一半的结果，要用X1(k),

X2(k)来表达全部的X(k)值，还必须应用系数的周期性， 即

第4章 快速傅里叶变换

W这样可得到N 1 2

N r k 2 N /2

rk WN / 2N 1 2 r 0

N X 1 k x1 ( r )W 2 r 0 同理可得

N r k 2 N /2

rk x1 ( r )WN / 2 X 1 (k ) (4-8)

N X 2 k X 2 (k ) 2

(4-9)

式(4-8)、式(4-9)

说明了后半部分k值(N/2≤k≤N-1)所 对应的X1(k), X 2(k)分别等于前半部分k值(0≤k≤N/2-1)所 对应的X1(k),X2(k)。

第4章 快速傅里叶变换

再考虑到WkN 的以下性质:

W

N k 2 N

k k WNN / 2WN WN

(4-10)

这样，把式(4-8)、式(4-9)、式(4-10)代入式 (4-5),就可将X(k)表达为前后两部分：

N X (k ) X 1 (k ) W X 2 (k ) k 0,1, , 1 (4-11) 2k N

N N X k X1 k W 2 2

N k 2 N

k X 1 (k ) WN X 2 (k )

N X2 k 2 N k 0,1, , 1 (4-12) 2

第4章 快速傅里叶变换

X1 (k)

X1 (k)+ WN X2 (k)

k

X2 (k)

k WN

-1

X1 (k)- WN X2 (k)

k

图 4-1 时间抽取法蝶形运算流图符号

第4章 快速傅里叶变换x1 (0)=x(0) x1 (1)=x(2) x1 (2)=x(4) x1 (3)=x(6) x2 (0)=x(1) x2 (1)=x(3) x2 (2)=x(5) x2 (3)=x(7) X1 (0) X1 (1) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)

N 点 2 X1 (2) DFT X1 (3)0 X2 (0) WN

N 点 2 X2 (2) WN 2 DFT 3 X2 (3) WN

X2 (1) W

1 N

-1 -1 -1 -1

图 4-2 按时间抽取将一个N点DFT分解 为两个N/2点DFT(N=8)

第4章 快速傅里叶变换 一次分解后的运算量 一个N/2点DFT 两个N/2点DFT 复数乘法 (N/2)2次 N2/2次 1次 N/2次 N2/2+N/2 ≈N2/2 复数加法 N/2(N/2-1)次 N(N/2-1)次 2次 N次 N(N/2-1)+N ≈N2/2

一个蝶形N/2个蝶形 总计

经一次分解，运算量减少近一半

第4章 快速傅里叶变换 与第一次分解相同，将x1(r)按奇偶分解成两个N/4 长的子序列x3(l)和x4(l),即

x1 (2l ) x3 (l ) x1 (2l 1) x4 (l )

N l 0,1, , 1 4N 1 4 l 0

(4-13)

X 1 (k )

N 1 4 l 0

2 x1 (2l )WN lk2 /

( x1 (2l 1)WN 2/ l2 1) k N 1 4 l 0

N 1 4 l 0

lk k x3 (l )WN / 4 WN / 2

lk x4 (l )WN / 4

k X 3 ( k ) WN / 2 X 4 ( k )

k 0,1, , N 1 4

第4章 快速傅里叶变换 且 N k X 1 k X 3 (k ) WN / 2 X 4 (k ) 4 lk X 3 ( k ) x3 (l )WN / 4 l 0 N 1 4

N k 0,1, , 1 4(4-14)

式中：

lk X 4 (k ) x4 (l )WN / 4 l 0

N 1 4

(4-15)

图4-3给出N=8时，将一个N/2点DFT分解成两个N/4点DFT, 由这两个N/4点DFT组合成一个N/2点DFT的流图。

第4章 快速傅里叶变换X3 (0)

x3 (0)= 1 (0)= x x(0) x3 (1)= 1 (2)= x x(4)

N 点 4 X3 (1) DFT

X1 (0) X1 (1)

x4 (0)= 1 (1)= x x(2) x4 (1)= 1 (3)= x x(6)

X4 (0)

N 点 4 X4 (1) DFT

0 WN / 2

-11 WN / 2

X1 (2) X1 (3)

-1

图 4-3 N/2点DFT分解为两个N/4点DFT

本文来源：https://www.bwwdw.com/article/mh81.html