第九章离散傅里叶变换

前言：引入DFT的原因计算机应用于信号处理的基本条件：1.连续函数转变为离散数据(时域与频域)；2.计算范围从无限宽收缩到一个有限区间。离散傅里叶变换研究内容：1.如何在频域进行离散化？2.时域上的样本与频域上的样本之间的数学关系是怎样的？现在是1页\一共有82页\编辑于星期四现在是2页\一共有82页\编辑于星期四主要内容离散傅里叶级数（DFS）离散傅里叶变换（DFT）快速傅里叶变换（FFT）现在是3页\一共有82页\编辑于星期四一.DFT是重要的变换

1.分析有限长序列的有用工具。

2.在信号处理的理论上有重要意义。

3.在运算方法上起核心作用，谱分析、卷积、相关都可以通DFT在计算机上实现。§9-1 引言现在是4页\一共有82页\编辑于星期四二.DFT是现代信号处理桥梁

DFT要解决两个问题： 一是离散与量化， 二是快速运算。信号处理DFT(FFT)傅氏变换离散量化现在是5页\一共有82页\编辑于星期四

FT傅立叶变换t00时域：连续、非周期，频域：非周期、连续§9.2傅里叶变换的几种可能形式现在是6页\一共有82页\编辑于星期四FS

傅立叶级数时域：连续、周期，频域：非周期、离散0t------01111111111现在是7页\一共有82页\编辑于星期四DTFTx(nT)T-T0T2Tt0------时域：离散、非周期频域：周期、连续现在是8页\一共有82页\编辑于星期四

时域

频域连续非周期非周期连续傅里叶变换连续周期

非周期离散 傅里叶级数离散非周期周期连续

序列的傅里叶变换离散周期周期离散离散傅里叶级数傅里叶变换形式傅里叶变换的4种形式现在是9页\一共有82页\编辑于星期四

但是，前三种傅里叶变换对都不适于计算机上运算，因为它们至少在一个域（时域或频域）中函数是连续的。 因此，我们感兴趣的是时域和频域都是离散的情况。现在是10页\一共有82页\编辑于星期四时域：离散、周期，频域：周期、离散现在是11页\一共有82页\编辑于星期四§9.3DFS与DFT连续周期信号:抽样（抽样周期为T，一个周期内抽样N个点）得周期序列

一、离散傅里叶级数是周期为N的周期序列1、DFS的引入现在是12页\一共有82页\编辑于星期四

将两端乘

再从n=0到N-1求和，则：2、的求取现在是13页\一共有82页\编辑于星期四现在是14页\一共有82页\编辑于星期四3、将定标因子1/N移到表达式中。保持与Z变换相同的形式？现在是15页\一共有82页\编辑于星期四设则离散傅氏级数表示为：正变换：反变换：4、离散傅氏级数的表示：现在是16页\一共有82页\编辑于星期四DFS的图示说明n0N-N......k0N-N现在是17页\一共有82页\编辑于星期四5、函数的几个性质：1.共轭对称性：2.周期性：i为整数3.可约性：4.正交性：i为整数现在是18页\一共有82页\编辑于星期四二、离散傅里叶变换在进行DFS分析时，时域、频域序列都是无限长的周期序列周期序列实际上只有有限个序列值有意义长度为N的有限长序列可以看成周期为N的周期序列的一个周期（主值序列）借助DFS变换对，取时域、频域的主值序列可以得到一个新的变换—DFT，即有限长序列的离散傅里叶变换现在是19页\一共有82页\编辑于星期四另一种表示其中表示对n取模N运算(或模N的余数)。则若1、周期序列与主值序列的关系现在是20页\一共有82页\编辑于星期四举例：设周期为N=6。则有周期序列和求余运算：

这是因为：(19=3×6+1)

同理这是因为：(-2=-1×6+4)

同样：X(k)也是一个N点的有限长序列现在是21页\一共有82页\编辑于星期四2、DFT的定义现在是22页\一共有82页\编辑于星期四3、DFT的矩阵形式其中：现在是23页\一共有82页\编辑于星期四4、离散傅里叶变换(DFT)的特点序列x(n)在时域是有限长的(长度为N)，它的离散傅里叶变换X(k)也是离散、有限长的(长度也为N)。n为时域变量，k为频域变量。离散傅里叶变换与离散傅里叶级数没有本质区别，DFT实际上是离散傅里叶级数的主值，DFT也隐含有周期性。离散傅里叶变换(DFT)具有唯一性。现在是24页\一共有82页\编辑于星期四例1、计算(N=12)的N点DFT.解：

现在是25页\一共有82页\编辑于星期四现在是26页\一共有82页\编辑于星期四§9.4离散傅里叶变换的性质1、线性这里，序列长度及DFT点数均为N若不等，分别为N1，N2，则需补零使两序列长度相等，均为N，且若则现在是27页\一共有82页\编辑于星期四

有限长序列的圆周移位导致频谱线性相移，而对频谱幅度无影响。(1)圆周移位2、时移特性(2)时移特性现在是28页\一共有82页\编辑于星期四从图中两虚线之间的主值序列的移位情况可以看出：当主值序列左移m个样本时，从右边会同时移进m个样本好像是刚向左边移出的那些样本又从右边循环移了进来因此取名“循环移位”。显然，循环移位不同于线性移位现在是29页\一共有82页\编辑于星期四3、频移特性时域序列的调制等效于频域的圆周移位现在是30页\一共有82页\编辑于星期四eg：现在是31页\一共有82页\编辑于星期四4、时域圆周卷积设则(1)定理现在是32页\一共有82页\编辑于星期四圆周卷积步骤：1）翻褶2）圆周移位3）相乘4）相加(2)圆周卷积的计算现在是33页\一共有82页\编辑于星期四Eg1.N-10nN-10n现在是34页\一共有82页\编辑于星期四0m0m0m0m现在是35页\一共有82页\编辑于星期四现在是36页\一共有82页\编辑于星期四0233211N-1n最后结果：现在是37页\一共有82页\编辑于星期四1）.线性卷积的长度为的长度为2）圆周卷积（3）线性卷积与圆周卷积的关系现在是38页\一共有82页\编辑于星期四3)关系补‘0’加长现在是39页\一共有82页\编辑于星期四x(n)的N点DFT是

x(n)的z变换在单位圆上的N点等间隔抽样；

x(n)的DTFT在区间[0,2π]上的N点等间隔抽样。§9-5现在是40页\一共有82页\编辑于星期四一.DFT的计算工作量

两者的差别仅在指数的符号和因子1/N.

§9-6FFT的应用现在是41页\一共有82页\编辑于星期四DFT与IDFT运算特点复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)当N很大时,运算量将是惊人的,如N=1024,要完成1048576次(一百多万次)运算.这样,难以做到实时处理.现在是42页\一共有82页\编辑于星期四二.改进的途径

1.的对称性和周期性对称性:周期性:2、N点DFT2个N/2点DFT现在是43页\一共有82页\编辑于星期四

利用上述特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度.1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N

次复数乘法运算.例如N=1024=210

时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍现在是44页\一共有82页\编辑于星期四三、基2FFT算法的思路把一个序列分为长度减半的偶序列和奇序列,原序列的DFT就由这两个N/2序列求得.进一步把N/2序列分解成两个N/4序列,一直分解到2点序列.现在是45页\一共有82页\编辑于星期四Eg.N=8的FFT1,3,5,70,2,4,60,42,61,53,7x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第一级第二级第三级现在是46页\一共有82页\编辑于星期四四.算法原理(基2FFT)1.先将按n的奇偶分为两组N/2点作DFT,设N=2M,不足时,可补些零。

n为偶数时:n为奇数时:现在是47页\一共有82页\编辑于星期四因此现在是48页\一共有82页\编辑于星期四

其中,2.两点结论:(1)G(k),H

(k)均为N/2点的DFT。

(2)X(k)=G(k)+W

H

(k)只能确定出

X(k)的k=0,1,…(N/2-1)时的值；即前N/2点的结果。kN现在是49页\一共有82页\编辑于星期四同理,3.X(k)后N/2个点的确定*X(k)的后N/2个点，也完全由G(k),H(k)确定*N点的DFT可由两个N/2点的DFT来计算。现在是50页\一共有82页\编辑于星期四实现上式运算的流图称作蝶形运算

k=0,1,…(N/2-1)4.蝶形运算（N/2个蝶形)11-1由X1(k)、X2(k)表示X(k)的运算是一种特殊的运算-碟形运算

k=0,1,…(N/2-1)现在是51页\一共有82页\编辑于星期四

例N=8时的FFT:

1、2个N/2点DFT（1）将分成奇偶序列，并计算X(k)现在是52页\一共有82页\编辑于星期四其中现在是53页\一共有82页\编辑于星期四

g(0)=x(0)

g(1)=x(2)

N/2点

g(2)=x(4)DFT

g(3)=x(6)

h(0)=x(1)

h(1)=x(3)

N/2点

h(2)=x(5)

DFT

h(3)=x(7)

12G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（2）对X

(k)和X

(k)进行蝶形运算如下图所示:现在是54页\一共有82页\编辑于星期四2、

4个N/4点DFT（1）将分成奇偶序列，并进行DFT现在是55页\一共有82页\编辑于星期四其中现在是56页\一共有82页\编辑于星期四（2）将分成奇偶序列,并进行DFT现在是57页\一共有82页\编辑于星期四现在是58页\一共有82页\编辑于星期四WN0WN0WN0W0N-1-1-1-1P(0)P(1)Q(0)Q(1)Y(0)Y(1)Z(0)Z(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)8点DFT的FFT的运算流图如下现在是59页\一共有82页\编辑于星期四1.蝶形运算蝶形单元蝶距:2m-1（第m级蝶形运算）

五.FFT算法的特点现在是60页\一共有82页\编辑于星期四输入数据、中间运算结果和最后输出均用同一存储器。

2.原位运算WN0WN0WN0W0N-1-1-1-1P(0)P(1)Q(0)Q(1)Y(0)Y(1)Z(0)Z(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)现在是61页\一共有82页\编辑于星期四

3

倒位序运算FFT运算流程中，输出X(k)按正常顺序排列在存储单元,而输入是按顺序:

这种顺序称作倒位序,即二进制数倒位。现在是62页\一共有82页\编辑于星期四是由奇偶分组造成的,以N=8为例说明如下:现在是63页\一共有82页\编辑于星期四倒位序的实现

输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列。

设输入序列的序号为n,二进制为

(n2n1n0)2,倒位序顺序用

表示,其倒位序二进制为(n0n1n2)2

。现在是64页\一共有82页\编辑于星期四

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二进制nnn倒位序二进制nnn倒位顺序n^210012码位倒序（N=8）现在是65页\一共有82页\编辑于星期四码位倒序（N=16）现在是66页\一共有82页\编辑于星期四A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)倒位序的变址处理方法存储单元自然顺序变址倒位序现在是67页\一共有82页\编辑于星期四蝶距为1蝶距为2WN0WN0WN0W0N-1-1-1-1P(0)P(1)Q(0)Q(1)Y(0)Y(1)Z(0)Z(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)现在是68页\一共有82页\编辑于星期四4.WNr

的分布规律第1级：第2级：……第i级:……第L级:现在是69页\一共有82页\编辑于星期四

5.存储单元

存输入序列

(n),n=0,1,,N-1,计N

个单元;

存放系数

,r=0,1,,N/2-1,

需N/2个存储单元；共计(N+N/2)个存储单元。现在是70页\一共有82页\编辑于星期四三、FFT运算量1．N=2时，共有L=logN级蝶形运算；每一级有N/2个蝶形单元。2．每一级有N个输入中间数据，且每级只用到本级的输入中间数据，适合于迭代运算。3．计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N次复乘法；复加法L*N=Nlog2N

次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)

。当N大时，此倍数很大。2L现在是71页\一共有82页\编辑于星期四§9-7DFT的应用一、利用FFT计算线卷积1、

时