快速傅里叶变换1

第五章 快速傅里叶变换

本章目录 直接计算DFT的问题及改进的途径 按时间抽取的基2-FFT算法 时间抽取的 FFT算法 按频率抽取的基2-FFT算法 频率抽取的基2 FFT算 快速傅里叶逆变换(IFFT)算法 快速傅里叶逆变换(IFFT)算法 Matlab实现 Matlab实现

5.1 引言 DFT在实际应用中很重要: 可以计算信号的频 DFT在实际应用中很重要: 谱、功率谱和线性卷积等。 直接按DFT变换进行计算，当序列长度N 直接按DFT变换进行计算，当序列长度N很 大时，计算量非常大，所需时间会很长。 FFT并不是一种与DFT不同的变换，而是 FFT并不是一种与DFT不同的变换，而是 DFT的一种快速计算的算法。 DFT的一种快速计算的算法。

5.2 直接计算 直接计算DFT的问题及改进的途径 的问题及改进的途径 DFT的运算量 DFT的运算量 设复序列x(n) 长度为 点，其DFT为 长度为N点 设复序列 为X (k ) = ∑ x( n)WNnkn= n=0 N 1

k=0,, ,N-1 ,,…, ,,

(1)计算一个X(k) 值的运算量 )计算一个复数乘法次数： 复数乘法次数： N 复数加法次数： 复数加法次数： N-1

5.2.1 DFT的运算量 的运算量(2)计算全部 个X(k) 值的运算量 )计算全部N个复数乘法次数： 复数乘法次数： N2 复数加法次数： 复数加法次数： N(N-1)

(3)对应的实数运算量 )X ( k ) = ∑ x( n)Wn =0N 1 n =0

N 1

nk N

= ∑ [Re x( n) + j Im x( n)][Re WNnk + j Im WNnk ]n =0

N 1

= ∑ {[Re x( n) Re WNnk Im x(n) Im WNnk ]

+ j[Re x ( n) Im WNnk + Im x ( n) Re WNnk ]}5

一次复数乘法： 次实数乘法 一次复数乘法： 4次实数乘法 一个X(k) : 一个

+ 2次实数加法 次实数加法

4N次实数乘法 + 次实数乘法 2N+2(N-1)= 2(2N-1)次实数加法 次实数加法

所以 整个N点DFT运算共需要： 整个 点 运算共需要： 运算共需要 实数乘法次数： 实数乘法次数： 4 N2 实数加法次数： 实数加法次数： N×2(2N-1)= 2N(2N-1)

DFT运算量的结论 运算量的结论N点DFT的复数乘法次数举例 点 的复数乘法次数举例 N 2 4 8 16 32 N2 4 16 64 256 1028 N 64 128 256 512 1024 N2 4049 16384 65 536 262 144 1 048 576

结论： 很大时， 结论：当N很大时，其运算量很大，对实时性很强的信号 很大时 其运算量很大， 处理来说，要求计算速度快，因此需要改进DFT的计算 处理来说，要求计算速度快，因此需要改进 的计算 方法，以大大减少运算次数。 方法，以大大减少运算次数。7

nk 的以下特性对DFT进行分解： 进行分解： 主要原理是利用系数 W N 的以下特性对 进行分解

5.2.2 减少运算工作量的途径(WNnk ) WN = nk

(1)对称性 ) (2)周期性 ) (3)可约性 )

= WNk ( N n )

( WN n + N ) k = WNn ( k + N ) = W

Nnk

mnk WmN = WNnk

/ WNnk = WNnk mm /( k WN k + N / 2 ) = WN

另外， 另外，

WNN / 2 = 1

5.3 按时间抽取的基 按时间抽取的基2-FFT算法 算法 算法原理 按时间抽取基-2FFT算法与直接计算 按时间抽取基-2FFT算法与直接计算 DFT运算量的比较 DFT运算量的比较 按时间抽取的FFT算法的特点 按时间抽取的FFT算法的特点 按时间抽取FFT算法的其它形式流程图 按时间抽取FFT算法的其它形式流程图

5.3.1 算法原理设N=2L,将x(n)按 n 的奇偶分为两组： = 按 的奇偶分为两组：

x(2r ) = x1 (r )x(2r + 1) = x2 (r )则

r =0,1,…, 1 , ,

N 2

nk X (k) = DFT[x(n)] = ∑ x(n)WN n=0N 1 N 1

N 1

=

n=0 n为偶数

∑ x(n)W

nk N

+

n=0 n为奇数

nk x (n)WN ∑

=

2 ( = ∑ x(2r)WN rk + ∑ x(2r +1)WN2r +1)k r =0 r =0

n =0 n为偶数 N 1 2

∑ x(n)W

N 1

nk N

+

n =0 n为奇数 N 1 2

nk x(n)WN ∑

N 1

rk k rk = ∑x1(r)WN +WN ∑x2 (r)WN r =0 2 r =0 2

N 1 2

N 1 2

k = X1 (k) + WN X 2 (k )

式中， 分别是x 式中，X1(k)和X2(k)分别是 1(n)和x2(n)的N/2的DFT。 和 分别是 和 的 的 。 另外，式中 的取值范围是 的取值范围是： , , , 另外，式中k的取值范围是：0,1, …,N/2-1 。 -

k X 因此， 只能计算出X(k)的前一半值。 的前一半值。 因此， (k) = X1(k) +WN X2 (k) 只能计算出 的前一半值

后一半X(k) 值， N/2 , N/2 +1, …,N ? 后一半 ， , 利用 可得到N X1 ( + k ) = 2rk r N WN (2 2+ k ) = WN 2N 2 1 r =0

∑ x (r )W1

r ( N 2+ k ) N 2

rk = ∑ x1 (r )WN 2 = X 1 (k ) r =0

N 2 1

同理可得X2(

N + k ) = X 2 (k ) 2

考虑到 及前半部分X(k) 及前半部分

( WN N 2 + k ) = WNN 2 WNk = WNk

k X (k) = X1(k) +WN X2 (k)

k=0,1, …,N/2-1 , , , - 因此可得后半部分X(k) 因此可得后半部分X (k + N N N k ) = X 1 (k + ) + WN + N 2 X 2 (k + ) 2 2 2k = X 1 ( k ) WN X 2 ( k )

k=0,1, …,N/2-1 , , , -

蝶形运算k X (k) = X1(k) +WN X2 (k)

蝶形运算式X ( k ) = X 1 ( k ) WNk X 2 ( k )

蝶形运算信 号流图符号

因此，只要求出 个 点的DFT,即X1(k)和X2(k),再 因此，只要求出2个N/2点的 点的 ， 和 ， 经过蝶形运算就可求出全部X(k)的值，运算量大大减少。 的值， 经过蝶形运算就可求出全部 的值 运算量大大减少。

以8点为例第一次按奇偶分解 点为例第一次按奇偶分解为例， 以N=8为例， 为例 分解为2个 点 分解为 个4点 的DFT,然后 ， 做8/2=4次蝶形 次蝶形 运算即可求出 所有8点 所有 点X(k)的 的 值。

W

W WW

蝶形运算量比较 N点DFT的运算量 点DFT的运算量复数乘法次数： N2 复数加法次数： N(N-1)

分解一次后所需的运算量=2 N/2的DFT+ 分解一次后所需的运算量=2个N/2的DF

T+ N/2蝶形： N/2蝶形：复数乘法次数： 2*(N/2)2+N/2=N2/2+N/2 复数加法次数： 2*(N/2)(N/2-1)+2*N/2=N2/2

因此通过一次分解后，运算工作量减少了差 不多一半。16