数字信号处理-西电第4章

来源：网络收集时间：2026-07-12

导读：第4章快速傅里叶变换(FFT) 第4章快速傅里叶变换(FFT)4.1 引言 4.2 基2FFT算法4.3 进一步减少运算量的措施 4.4 其他快速算法简介习题与上机题第4章快速傅里叶变换(FFT) 4.1 引言DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换

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

第4章快速傅里叶变换(FFT)4.1 引言

4.2 基2FFT算法4.3 进一步减少运算量的措施

4.4 其他快速算法简介习题与上机题

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

4.1 引言DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比，

当N较大时，计算量太大，所以在快速傅里叶变换FFT(Fast Fourier Transform)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965 年提出DFT的一种快速算法以后，情况才发生了根本的变化。

第4章快速傅里叶变换(FFT)自从1965年库利(T. W. Cooley)和图基(J. W. Tuky)在《计算数学》(Math. Computation, Vol. 19, 1965)杂志上发表了著名的《机器计算傅里叶级数的一种算法》论文后，桑德(G. Sand)—图基等快速算法相继出现，又经人们进行改进，很快形成一套高效计算方法，这就是现在的快速傅里叶变换(FFT)。这种算法使DFT的运算效率提高了1 ~ 2个数量级，

为数字信号处理技术应用于各种信号的实时处理创造了条件，大大推动了数字信号处理技术的发展。

第4章快速傅里叶变换(FFT)人类的求知欲和科学的发展是永无止境的。多年来，

人们继续寻求更快、更灵活的好算法。1984年，法国的杜哈梅尔(P. Dohamel)和霍尔曼(H. Hollmann)提出的分裂基快速算法，使运算效率进一步提高。本章主要讨论基 2FFT算法及其编程思想。

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

4.2 基2FFT算法4.2.1 直接计算DFT的特点及减少运算量的基本途径有限长序列x(n)的N点DFT为



kn X (k ) x(n)WN n 0

N 1

k 0, 1, , N 1 (4.2.1)

考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)的1个值需要N次复数乘法和 (N-1)次复数加法。因此，计算X(k)的所有N个值，共需N2次复数乘法和N(N-1)次复数加法运算。

第4章快速傅里叶变换(FFT)当 N 1 时，N(N-1)≈N2。由上述可见，N点DFT的乘法和加法运算次数均为N2。当N较大时，运算量相当可观。例如N=1024时，N2=1 048 576。这对于实时信

号处理来说，必将对处理设备的计算速度提出难以实现的要求。所以，必须减少其运算量，才能使DFT在各种科学和工程计算中得到应用。 如前所述，N点DFT的复乘次数等于N2。显然，把 N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外，旋转因子具有明显的周期性和对称性。其周期性表现为  m WN lN e j 2π ( m lN ) N j 2π m N

m WN

(4.2.2)

第4章快速傅里叶变换(FFT)其对称性表现为 WN m WNN m

或者m N 2

m [WNN m ]* WN

(4.2.3a)

(4.2.3b)

FFT算法就是不断地把长序列的DFT分解成几个短序

列的DFT,并利用 WNkn 的周期性和对称性来减少DFT的运算次数。算法最简单最常用的是基2FFT。

第4章快速傅里叶变换(FFT)4.2.2 时域抽取法基2FFT基本原理基2FFT算法分为两类：时域抽取法FFT(DecimationIn Time FFT,简称DIT-FFT ); 频域抽取法FFT (Decimation In Frequency FFT,简称DIF-FFT)。本节介绍DIT-FFT算法。 设序列x(n)的长度为N,且满足N=2M,M为自然数。按n的奇偶把x(n)分解为两个N/2点的子序列 

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

N r 0, 1, , 1 2 N r 0, 1, , 1 2

第4章快速傅里叶变换(FFT)则x(n)的DFT为

X (k )

n 偶数 N / 2 1

x(n)WNkn

n 奇数

x(n)WNkn x(2r 1)WNk (2 r 1) x2 (r )WN2 kr

r 0

x(2r )WN2 kr

N / 2 1

r 0

N / 2 1

r 0

x1 (r )WN2 kr WNk

N / 2 1

r 0

第4章快速傅里叶变换(FFT)因为 2 WN kr e j

2π 2 kr N

2π kr N 2

kr WN / 2

所以

X (k )

N / 2 1

r 0

x1 (r )W

kr N /2

r N

N / 2 1

r 0

x2 (r )WNkr/ 2

X 1 (k ) WNk X 2 (k )

k 0,1, 2, , N -1(4.2.4)

第4章快速傅里叶变换(FFT)其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT, 即

X 1 (k ) X 2 (k )

N / 2 1

r 0

kr x1 (r )WN / 2 DFT[ x1 (r )]N

(4.2.5)

N / 2 1

r 0

kr x2 (r )WN / 2 DFT[ x2 (r )]N

(4.2.6)

由于X1(k)和X2(k)均以N/2为周期，且 WN X(k)又可表示为

N 2

k WN ,因此

第4章快速傅里叶变换(FFT)k X (k ) X 1 (k ) WN X 2 (k ),

k 0, 1, ,

N 1 2

(4.2.7)X (k N k ) X 1 (k ) WN X 2 (k ), 2 k 0, 1, , N 1 2

(4.2.8) 这样，就将N点DFT分解为两个N/2点DFT和(4.2.7)式以及 (4.2.8)式的运算。(4.2.7)和(4.2.8)式的运算可用图4.2.1所示的流图符号表示，称为蝶形运算符号。采用这种图示法，经过一次奇偶抽取分解后，N点DFT运算图可以用图4.2.2表示。图中，N=23=8, X(0)~X(3)由(4.2.7)式给出，而X(4)~

X(7)则由(4.2.8)式给出。

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

图4.2.1 蝶形运算符号

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

图4.2.2 8点DFT一次时域抽取分解运算流图

第4章快速傅里叶变换(FFT)由图4.2.1可见，要完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。由图4.2.2容易看出，经过一次分解后，计算1个N点DFT共需要计算两个N/2点DFT 和N/2个蝶形运算。而计算一个N/2点DFT需要(N/2)2次复数乘法和N/2(N/2-1)次复数加法。所以，按图4.2.2计算N

点DFT时，总共需要的复数乘法次数为

N N N ( N 1) 2 2 2 2 2

N2 2 N 1

第4章快速傅里叶变换(FFT)复

数加法次数为  

N 2N N 2 N 1 2 2 2

由此可见，仅仅经过一次分解，就使运算量减少近一半。

既然这样分解对减少DFT的运算量是有效的，且N=2M,N/2仍然是偶数，故可以对N/2点DFT再作进一步分解。与第一次分解相同，将x1(r)按奇偶分解成两个N/4点

的子序列x3(l)和x4(l),即

x3 (l ) x2 (2l )

x4 (l ) x1 (2l 1)

N l 0, 1, , 1 4

第4章快速傅里叶变换(FFT)X1(k)又可表示为

X 1 (k )

N / 4 1 l 0

2 x1 (2l )WN kl2 /

N / 4 1 l 0

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

N / 4 1 l 0

x3 (l )W

kl N /4

X 3 (k ) W

k N /2

X 4 (k )

N k 0, 1, , 1 2(4.2.9)

第4章快速傅里叶变换(FFT)式中N / 4 1



X 3 (k ) X 4 (k )

l 0

kl x3 (l )WN / 4 DFT[ x3 (l )]N

N / 4 1



l 0

kl x4 (l )WN / 4 DFT[ x4 (l )]N

m 同理，由X3(k)和X4(k)的周期性和 W N / 2 的对称性

k N /4 N /2

k WN / 2

< …… 此处隐藏：2275字，全部文档内容请下载后查看。喜欢就下载吧 ……

数字信号处理-西电第4章.doc 将本文的Word文档下载到电脑，方便复制、编辑、收藏和打印

下载这篇word文档

本文链接：https://www.jiaowen.net/wenku/125722.html（转载请注明文章来源）

上一篇：【全国百强校】内蒙古巴彦淖尔市第一中学2016-2017学年高一6月月
下一篇：N34-汽车基础知识培训