数字信号处理第四章-快速傅里叶变换(FFT)

第四章快速傅里叶变换（FFT）快速傅里叶变换（FFT）

离散傅里叶变换（DFT）

N次复数乘法，N－1次复数加法N快速傅里叶变换（FFT）1965年，图基和库利提出了快速傅里叶变换（FFT），不断把长序列分解成短序列，再进行DFT，并利用周期性和对称性来减少DFT的运算次数。主要内容

基2FFT算法

进一步减少运算量的措施分裂基FFT算法离散哈特莱变换（DHT）快速傅里叶变换（FFT）基2FFT算法快速傅里叶变换（FFT）时域抽取法FFT（DIT--FFT）频域抽取法FFT（DIF--FFT）基2快速傅里叶算法IDFT的高效算法ABABCDCD运算流图A-1C-1BD-1-1以N＝4为例快速傅里叶变换（FFT）时域抽取法FFT（DIT--FFT）快速傅里叶变换（FFT）蝶形运算试画出N＝8的DFT的一次时域抽取分解图快速傅里叶变换（FFT）-1-1-1-12个N/2点DFT运算N/2个蝶形运算快速傅里叶变换（FFT）快速傅里叶变换（FFT）-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）-1-1-1-1-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）-1-1-1-1-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）DIT-FFT算法与直接计算DFT运算量的比较快速傅里叶变换（FFT）DIT-FFT的运算规律及编程思想蝶形运算的规律和通式旋转因子的规律性的存储问题快速傅里叶变换（FFT）一、原位计算-1-1-1-1-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）二、旋转因子快速傅里叶变换（FFT）三、蝶形运算规律快速傅里叶变换（FFT）四、编程思想及程序框图开始送入x(n),MN=2M倒序L=1，MJ=0，B-1B=2L-1P=2M-LJ输出结束k=J,N-1,2L快速傅里叶变换（FFT）四、序列的倒序-1-1-1-1-1-1-1-1-1-1-1-1输出是自然序列，输入称为倒位序列，即二进制数倒位快速傅里叶变换（FFT）

快速傅里叶变换（FFT）

00

0

00

0

00

10

0

11

0

04

20

1

00

1

02

30

1

11

1

06

41

0

00

0

11

51

0

11

0

15

61

1

00

1

13

71

1

11

1

17自然顺序n二进制n2n1n0

倒位序二进制n0n1n2

倒位顺序n倒序数则是在M位二进制数最高位加1，逢2向右进位快速傅里叶变换（FFT）LH=N/2J=LHN1=N-2I=1，N1I>=JT=X(I)A(I)=X(J)A(J)=TK=LHNJ<KYJ=J+KJ=J-KK=K/2NY快速傅里叶变换（FFT）频域抽取法FFT（DIF--FFT）快速傅里叶变换（FFT）快速傅里叶变换（FFT）-1-1-1-1快速傅里叶变换（FFT）-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）-1-1-1-1-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）比较DIF-FFT算法与DIT-FFT算法的异同点：1.运算次数相同相同点2.公式、图形类似不同点1.DIF-FFT：输入是自然序列，输出是到位序列；DIT-FFT：输入是到位序列，输出是自然序列。2.DIF-FFT：蝶形运算是先乘后加减；DIT-FFT：蝶形运算是先加减后乘。快速傅里叶变换（FFT）FFT的变形运算支路传输比不变，改变输入点，输出点以及中间节点的排列-1-1-1-1-1-1-1-1-1-1-1-1快速傅里叶变换（FFT）IDFT的高效算法-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1乘法次数增加了（N/2)(M-1）次快速傅里叶变换（FFT）进一步减少运算量措施快速傅里叶变换（FFT）

1.多类蝶形运算N=2M点FFT共需MN/2次复乘快速傅里叶变换（FFT）

1.多类蝶形运算快速傅里叶变换（FFT）

1.多类蝶形运算快速傅里叶变换（FFT）一类蝶形单元运算：包括所有旋转因子

1.多类蝶形运算二类蝶形单元运算：去掉旋转因子三类蝶形单元运算：再去掉旋转因子四类蝶形单元运算：再处理旋转因子快速傅里叶变换（FFT）

2.旋转因子的生成一种方法是在每级运算中直接产生；二种方法是在FFT程序开始前预先计算出旋转因子，存放在数组中，作为旋转因子表，在程序执行中直接查表。快速傅里叶变换（FFT）

3.实序列的FFT算法例1：设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点DFT。要求：试设计用一次N点FFT完成计算X(k)的高效算法。解：本题的解题思路是DIT－FFT思想；在时域分别抽取偶数点和奇数点x(n)，得到两个N点实序列x1(n)和x2(n)：x1(n)=x(2n),n=0,1,……,N-1

x2(n)=x(2n+1),n=0,1,……,N-1根据DIT－FFT的思想，只要求得x1(n)和x2(n)的N点DFT，再经过简单的一级蝶形运算就可得到x(n)的2N点DFT。因为x1(n)和x2(n)均为实序列，所以根据DFT的共轭对称性，可用一次N点FFT求得X1(k)和X2(k)。做法如下：令y(n)=x1(n)+jx2(n)Y(k)=DFT[y(n)]则X1(k)=DFT[x1(n)]=Yep(k)=[Y(k)+Y*(N-k)]/2jX2(k)=DFT[x2(n)]=Yop(k)=[Y(k)-Y*(N-k)]/22N点DFT[x(n)]=X(k)可由X1(k)和X2(k)得到：

X(k)=X1(k)+W2NkX2(k)X(k+N)=X1(k)-W2NkX2(k),k=0,1,…,N-1这样，通过一次N点FFT计算完成了计算2N点DFT。例2：设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点DFT。若已知X(k)，要求：试设计用一次N点IFFT完成计算x(n)的高效算法。解：设x1(n)=x(2n),n=0,1,……,N-1

x2(n)=x(2n+1),n=0,1,……,N-1 X1(k)=DFT[x1(n)],k=1,1,…,N-1

X2(k)=DFT[x2(n)],k=1,1,…,N-1

由DIT－FFT的算法，有以下关系式：

X(k)=X1(k)+W2NkX2(k),k=1,1,…,N-1X(k+N)=X1(k)-W2NkX2(k)

由以上两可解出X1(k)和X2(k)。

X1(k)=[X(k)+X(k+N)]/2X2(k)=W2N-k[X(k)–X(k+N)]/2由上面分析可得出运算过程如下： （1）由X(k)计算出X1(k)和X2(k)； （2）由X1(k)和X2(k)构成N点频域序列Y(k)：

Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k)其中Yep(k)=X1(k)，Yop(k)=jX2(k)，进行N点IFFT运算，得到

y(n)=IFFT[Y(k)]=Re[y(n)]+jIm[y(n)],n=0,1,…,N-1由DFT的共轭对称性

Re[y(n)]=[y(n)+y*(n)]/2=DFT[Yep(k)]=x1(n)jIm[y(n)]=[y(n)-y*(n)]/2=DFT[Yop(k)]=jx2(n)由x1(n)和x2(n)合成x(n)：当n=偶数（n=0,1,…,2N-1）时x(n)=x1(n/2)当n=奇数（n=0,1,…,2N-1）时x(n)=x2((n-1)/2)分裂基FFT算法快速傅里叶变换（FFT）1984年，法国的杜梅尔和霍尔曼将基2和基4分解糅合在一起，提出了分裂基FFT算法，其运算量有所减少，运算流图相似，运算程序较短，是一种实用的高效算法。快速傅里叶变换（FFT）快速傅里叶变换（FFT）快速傅里叶变换（FFT）快速傅里叶变换（FFT）快速傅里叶变换（FFT）快速傅里叶变换（FFT）L形蝶形图一个N点DFT可分解成一个N/2点DFT和两个N/4点DFT快速傅里叶变换（FFT）-1-1-j-1快速傅里叶变换（FFT）离散哈特莱变换（DHT）快速傅里叶变换（FFT）计算出X(k)的前N/2个值，则后N/2个值可求直接对实序列进行实数域变换的离散哈特莱变换快速傅里叶变换（FFT）证明：快速傅里叶变换（FFT）证明：快速傅里叶变换（FFT）

DHT的核函数是DFT核函数的实部与虚部之和快速傅里叶变换（FFT）快速傅里叶变换（FFT）1.DHT是实值变换2.DHT的正反变换具有相同形式DHT的主要优点：3.DHT与DFT间的关系简单快速傅里叶变换（FFT）

1.DFT的线性快速傅里叶变换（FFT）

2.X(N-n）的DHT快速傅里叶变换（FFT）证明：快速傅里叶变换（FFT）

3.循环移位性质快速傅里叶变换（