第二章数字信号处理的基本算法

1、大连理工大学出版社DSP原理与实训指导原理与实训指导新世纪高职高专教材编审委员会组编新世纪高职高专教材编审委员会组编主编喻宗泉主编喻宗泉大连理工大学出版社第二章第二章 数字信号处理的基本算法数字信号处理的基本算法2.1数字信号处理的一般程数字信号处理的一般程序序2.2傅立叶变换的四种形式傅立叶变换的四种形式2.3离散信号的傅立叶变换离散信号的傅立叶变换2.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.5DFT的快速算法的快速算法2.6基基-2FFT算法算法2.7基基-4FFT算法算法2.8离散傅立叶反变换快速算法离散傅立叶反变换快速算法大连理工大学出版社2.1数字数字信号处理的一般程序

2、信号处理的一般程序 要想实现数字信号处理，一般程序必须经过如下几个阶段。要想实现数字信号处理，一般程序必须经过如下几个阶段。（1 1）首先要获得数字信号，得到的数字信号通常是离散时间信号）首先要获得数字信号，得到的数字信号通常是离散时间信号（2 2）完成信号之间的傅立叶变换）完成信号之间的傅立叶变换（3 3）用软件或硬件完成数字滤波功能）用软件或硬件完成数字滤波功能 （4 4）选择合适的）选择合适的DSPDSP芯片芯片 （5 5）从硬件和软件两个方面设计组成）从硬件和软件两个方面设计组成DSPDSP系统系统 （6 6）用仿真器调试硬件。）用仿真器调试硬件。 （7 7）用）用DSPDSP开发工具

3、调试软件程序开发工具调试软件程序 （8 8）将软件脱离开发系统，装入实际系统中运行）将软件脱离开发系统，装入实际系统中运行 大连理工大学出版社2.1数字数字信号处理的一般程序信号处理的一般程序获取数字信号选择时域频域间的傅立叶变换确定数字滤波方案选择DSP芯片组成硬件电路编制软件程序组成DSP系统用仿真器调试硬件用开放工具调试软件系统统调运行大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式 将自变量为时间的时域函数转变成自变量为频率的频域将自变量为时间的时域函数转变成自变量为频率的频域函数，称为傅立叶变换。反之称为傅立叶反变换。函数，称为傅立叶变换。反之称为傅立叶反变换。 傅立

4、叶变换反映了时间信号与频率信号之间的对应关系。傅立叶变换反映了时间信号与频率信号之间的对应关系。 鉴于时间信号有连续时间信号和离散时间信号之分，鉴于时间信号有连续时间信号和离散时间信号之分，与时间函数对应的频率函数中，频率的取值可以为连续值与时间函数对应的频率函数中，频率的取值可以为连续值或离散值，因此傅立叶变换就有四种形式。或离散值，因此傅立叶变换就有四种形式。 在在DSPDSP领域用得最多的是离散时间信号与离散频率信领域用得最多的是离散时间信号与离散频率信号之间的傅立叶变换。号之间的傅立叶变换。 大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式2.2.1连续时间连续时间信号

5、与连续频率信号间的傅立叶变换信号与连续频率信号间的傅立叶变换设连续时间信号设连续时间信号f(t)对应的频谱密度函数为对应的频谱密度函数为F(j)，则傅立叶，则傅立叶变换为：变换为： dtetfjFtj傅立叶反变换为：傅立叶反变换为： dejFtftj210f(t) t0 )F( j k0连续时间信号与连续频率信号间的变换连续时间信号与连续频率信号间的变换 大连理工大学出版社 设设f(t)是周期为是周期为T的连续时间函数，展开成傅立叶级数的连续时间函数，展开成傅立叶级数后的系数为后的系数为F(jk0)，则由，则由f(t)求取求取F(jk0)的正变换为：的正变换为： 2.2傅立叶变换的四种形式傅立

6、叶变换的四种形式2.2.2连续时间连续时间信号与离散频率信号间的傅立叶变换信号与离散频率信号间的傅立叶变换 22001TTtjkdtetfTjkF由由F(jk0)求取求取f(t)的反变换为：的反变换为： tjkkejkFtf00式中式中k表示谐波次数，表示谐波次数，0表示离散频率两相邻谱线间的角频间隔，且表示离散频率两相邻谱线间的角频间隔，且F(jk0)为离散频谱的非周期函数。为离散频谱的非周期函数。 大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式2.2.2连续时间连续时间信号与离散频率信号间的傅立叶变换信号与离散频率信号间的傅立叶变换0f(t) t0 )F( j k0T0连

7、续时间信号与离散频率信号间的变换连续时间信号与离散频率信号间的变换 大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式2.2.3离散时间离散时间信号与连续频率信号间的傅立叶变换信号与连续频率信号间的傅立叶变换 设设f(n)是非周期离散时间信号，对应的连续频率频谱密度是非周期离散时间信号，对应的连续频率频谱密度信号为信号为 )()(TjjeFeF式中式中=T表示数字频率，表示数字频率，表示模拟频率，表示模拟频率，T表示将模拟信表示将模拟信号数字化采样时的抽样间隔。从离散时间信号求得连续频率号数字化采样时的抽样间隔。从离散时间信号求得连续频率信号的傅立叶正变换为：信号的傅立叶正变换为

8、： nTnjTjenfeF从连续频率信号求得离散时间信号的反变换为：从连续频率信号求得离散时间信号的反变换为： deeFnfnjj21大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式2.2.3离散时间离散时间信号与连续频率信号间的傅立叶变换信号与连续频率信号间的傅立叶变换0f(n)0)F( ej T =2/0TTn 2)F( ej 或离散时间信号与连续频率信号间的变换离散时间信号与连续频率信号间的变换 大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式2.2.4离散时间离散时间信号与离散频率信号间的傅立叶变换信号与离散频率信号间的傅立叶变换 设设f(n)为周期离散

9、时间信号，相应的离散频谱密度为为周期离散时间信号，相应的离散频谱密度为F(k)，则正变换为：则正变换为： 10/2)()(NnNnkjenfkF相应反变换为：相应反变换为： 10/2)(1)(NkNnkjekFNnf式中式中f(n)=f(nT) NkjeFkF2N是有限长序列的抽样点数。是有限长序列的抽样点数。 大连理工大学出版社2.2傅立叶变换的四种形式傅立叶变换的四种形式2.2.4离散时间离散时间信号与离散频率信号间的傅立叶变换信号与离散频率信号间的傅立叶变换f(n)0Nn )F( k.1 2 .N -10N.1 2 .N -1K离散时间信号与离散频率信号间的变换离散时间信号与离散频率信号

10、间的变换 大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.1离散时间离散时间信号的傅立叶变换信号的傅立叶变换离散时间信号离散时间信号f(n)的傅立叶变换定义成的傅立叶变换定义成： nnjjenfeF上式成立的条件是序列上式成立的条件是序列f(n)满足：满足： nnf如果把如果把f(n)视为模拟信号的抽样序列，设抽样频率为视为模拟信号的抽样序列，设抽样频率为fs=1/T，其中其中T是抽样时间间隔，模拟信号频率是抽样时间间隔，模拟信号频率s=2/T ，则有，则有 f(n)f(nT) T )()(TjjeFeFnTnjenTf)(大连理工大学出版社2.3离散信号的离散信号的傅

11、立叶变换傅立叶变换2.3.1离散时间离散时间信号的傅立叶变换信号的傅立叶变换将变换关系离散化后，设将变换关系离散化后，设k，T2fk，则，则 1000NnTnjkTjkenTfeF式中式中N=fs / / f = s / /， 1022NnNnjkNjkenfeF 代入得代入得 对于对于F(ej)的傅立叶反变换，有以下定义：的傅立叶反变换，有以下定义： d21njjeeFnf大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.2周期序列的离散周期序列的离散傅立叶级数傅立叶级数DFS 设设x(n)是一个任意的以是一个任意的以N为周期的离散时间周期序列，为周期的离散时间周期序列

12、，因序列有周期性，因此可以展开成如下的傅立叶级数：因序列有周期性，因此可以展开成如下的傅立叶级数： 102NkNknjkeanx 式中式中ak是离散傅立叶级数的系数，是离散傅立叶级数的系数，N是非零的某一个是非零的某一个整数。如果将上式两边乘以，并对整数。如果将上式两边乘以，并对n在一个周期在一个周期N内求和，内求和，即可求得即可求得ak。 10/21NnNknjkenxNa其中，其中，k取值范围为取值范围为(-，)中的整数。中的整数。 大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.2周期序列的离散周期序列的离散傅立叶级数傅立叶级数DFS 如果如果k发生变化，就成为周

13、期为发生变化，就成为周期为N的周期函数，由此的周期函数，由此ak成为周期为成为周期为N的周期序列，若设：的周期序列，若设：x(k)=N ak则有：则有： 102NnNknjenxkx x(k)称为称为x(n)的离散傅立叶级数系数，记为的离散傅立叶级数系数，记为DFS ： x(k)=DFSx(n)上式就是离散傅立叶级数上式就是离散傅立叶级数DFS的正变换。的正变换。 大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.2周期序列的离散周期序列的离散傅立叶级数傅立叶级数DFS相应的反变换为已知相应的反变换为已知x(k)求求x(n)： )(IDFS)(kXnx10/2)(1NkN

14、knjekxN 反变换公式表明如何将周期序列分解成反变换公式表明如何将周期序列分解成N次谐波，次谐波，X(k)和和x(n)都是周期为都是周期为N的序列，第的序列，第k次谐波的频率是次谐波的频率是k=2kN，其中其中k=0，1，2，N-1，谐波幅值，谐波幅值 ，相位相位argX (k)，k=0表示直流分量，直流分量幅值为：表示直流分量，直流分量幅值为：NkX/)( 1010NnnxNX大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.3有限长序列的离散有限长序列的离散傅立叶变换傅立叶变换DFT主值序列和周期延拓主值序列和周期延拓1 设设f(n)是一个长度为是一个长度为N的有

15、限序列，它的取值特征是的有限序列，它的取值特征是n为为整数，且整数，且f(n)仅当仅当n从从0到到N-1时有值，当时有值，当n为其它值时为其它值时f(n)为为0。下图就是有限长序列下图就是有限长序列 其它70,0nnnf当当N=8时的示意图。时的示意图。 f(n)n 0 1 2 3 4 5 6 7大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.3有限长序列的离散有限长序列的离散傅立叶变换傅立叶变换DFT 如果以如果以N为周期将为周期将f(n)进行延拓，延拓结果获得一个周期进行延拓，延拓结果获得一个周期序列序列x(n)，如图，如图2-9所示，所示，x(n)和和f(n)的关

16、系如下：的关系如下： rrNnfnxnNnnxnf为其它10,0,将将f(n)称为称为x(n)的一个主值序列，因为的一个主值序列，因为f(n)是是x(n)的某一个周的某一个周期。而周期序列可以看成是主值序列周期延拓的结果。期。而周期序列可以看成是主值序列周期延拓的结果。 x(n)0n 1 2 3 4 5 6 7.周期序列周期序列x(n) 大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.3有限长序列的离散有限长序列的离散傅立叶变换傅立叶变换DFT有限长序列有限长序列DFT2 如果如果f(n)是有限长时域序列的话，是有限长时域序列的话，F(k)就是其转换到频域就是其转换到频

17、域的有限长频域序列。由此得到的有限长频域序列。由此得到f(n)的离散傅立叶变换：的离散傅立叶变换： 式中式中k的取值为的取值为0，N-1。 反变换为：反变换为： 1021NkNknjekFNkFIDFTnf式中式中n的取值为的取值为0，N-1 大连理工大学出版社2.3离散信号的离散信号的傅立叶变换傅立叶变换2.3.3有限长序列的离散有限长序列的离散傅立叶变换傅立叶变换DFT有限长序列有限长序列DFT2引进矩阵序列引进矩阵序列RN(n)： 10,1,0NnnRN其它正变换可写成：正变换可写成： kRkXkRenfkFNNnNNknj102反变换表示成：反变换表示成： nRnxnRekFNnfNN

18、NnNknj1021大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.1周期性周期性离散时间信号的傅立叶变换以离散时间信号的傅立叶变换以2为周期，用式子表示成：为周期，用式子表示成： rjjeFeF2式中式中r=0，1，2，为正整数。，为正整数。 是周期离散时间信号的角频率，是周期离散时间信号的角频率，0的量是信号的的量是信号的直流分量，由于以直流分量，由于以2为周期，因此信号的直流分量发生在为周期，因此信号的直流分量发生在2r处，其中处，其中r=0，1，2，。信号的低频分量集中。信号的低频分量集中在在2r附近。信号的最高频率位于附近。信号的最高频率位于处，

19、于是在处，于是在附附近集中了信号的最高频率。近集中了信号的最高频率。 大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.1周期性周期性 以以f()cos n为例，如果为例，如果2r (r=0，1，2，)，周期序列，周期序列cos n的谱线呈齿状，序列幅值维持为的谱线呈齿状，序列幅值维持为常数不变。如果常数不变。如果(2r1)，则序列幅值从正值跳到负值，则序列幅值从正值跳到负值，从最大跳到最小，再从最小跳到最大。下图分别画出了从最大跳到最小，再从最小跳到最大。下图分别画出了不不同取值时的两种同取值时的两种cos n波形。波形。 大连理工大学出版社2.42.4离

20、散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.2线性线性 设有两个离散序列设有两个离散序列x(n)和和y(n)，相应傅立叶变换分别为，相应傅立叶变换分别为X(k)和和Y(k)： X(k)=DFTx(n) Y(k)=DFTy(n)则有则有 aX(k)+bY(k)=DFTax(n)+by(n)式中式中a，b是任意常数。是任意常数。用文字叙述成：两个离散序列和的傅立叶变换等于各自离散用文字叙述成：两个离散序列和的傅立叶变换等于各自离散傅立叶变换之和。傅立叶变换之和。大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.2线性线性 现将序列长度的问题说明如下：现

21、将序列长度的问题说明如下： 两个离散序列的长度相同时，相加后的长度不变。例两个离散序列的长度相同时，相加后的长度不变。例如设如设x(n)和和y(n)的长度都是的长度都是N，则，则ax(n)+by(n)的长度也是的长度也是N。 两个离散序列的长度不同时，相加后的长度等于较长两个离散序列的长度不同时，相加后的长度等于较长序列的长度。例如设序列的长度。例如设x(n)的长度为的长度为Nx，y(n)的长度为的长度为Ny。若。若NxNy，则，则ax(n)+by(n)的长度为的长度为Nx。反之若。反之若NxNy，则，则ax(n)+by(n)的长度为的长度为Ny。 大连理工大学出版社2.42.4离散傅立叶变换

22、的运算特征离散傅立叶变换的运算特征2.4.3奇偶对称性奇偶对称性 离散时间序列的傅立叶变换与连续时间傅立叶变换类似，离散时间序列的傅立叶变换与连续时间傅立叶变换类似，存在条件奇偶对称性。这一性质说的是如果序列存在条件奇偶对称性。这一性质说的是如果序列f(n)的离散的离散傅立叶变换为傅立叶变换为F(k)，则，则f(n)和和F(k)具有相同的奇偶性。即：具有相同的奇偶性。即： 如果如果f(n)为奇（偶）对称序列，则为奇（偶）对称序列，则F(k)也为奇（偶）对也为奇（偶）对称序列；称序列； 反之反之F(k)为奇（偶）对称序列，则为奇（偶）对称序列，则f(n)也为奇（偶）对也为奇（偶）对称序列。称序列

23、。大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.4共轭对称性共轭对称性 设设f(n)是一个离散时间复序列，由实部和虚部组成。用是一个离散时间复序列，由实部和虚部组成。用下标下标r表示序列的实部；用下标表示序列的实部；用下标i表示序列的虚部，复序列可表示序列的虚部，复序列可以表示成：以表示成：f(n)=fr(n)+j fi(n) 如果如果f(n)的离散傅立叶变换为的离散傅立叶变换为F(k)：F(k)=DFTf(n)且且F(k)的条件共轭偶部和奇部分别用的条件共轭偶部和奇部分别用Fe(k)和和F0(k)表示，则有表示，则有如下关系式成立：如下关系式成立： F

24、e(k)=DFTfr(n) F0(k)=DFTfi(n)大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.5时移特性和频移特性时移特性和频移特性 时移特性又称为移位性质，描述的是离散时间序列信号在时移特性又称为移位性质，描述的是离散时间序列信号在延时一段时间后的傅立叶变换取什么样的形式。延时一段时间后的傅立叶变换取什么样的形式。)()(DFS(DFT00kRnnxnnfNNknjekF/20)( 考虑到时域与频域之间的对偶关系，可得考虑到时域与频域之间的对偶关系，可得f(n)的频移特性的频移特性: NnljenflkF/2IDFT 设设f(n)的离散傅立叶变

25、换为的离散傅立叶变换为F(k)，f(n)为有限长非周期序为有限长非周期序列。将列。将f(n)以周期以周期N完成周期延拓，得周期序列完成周期延拓，得周期序列x(n)，设移位，设移位延时为延时为n0，则，则f(n+n0)的傅立叶变换为：的傅立叶变换为：大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.6频域卷积特性频域卷积特性设设f(n)、h(n)皆是长度为皆是长度为N的有限长序列，且的有限长序列，且N-1n0 F(k)=DFTf(n) H(k)=DFT h(n)又设又设 y(n)=f(n) h(n)则则 )()()(kHkFkY)()(1kHkFN式中式中“”

26、表示卷积和表示卷积和 大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征2.4.6频域卷积特性频域卷积特性若将自变量改用若将自变量改用ej，则周期为，则周期为2，有，有 nnjjenhnfeY)()()()()(21jjeFeH表示表示 )()(1)(kHkFNkY成立，即时域内两离散时间序列相乘，可转化到频域内形成立，即时域内两离散时间序列相乘，可转化到频域内形成卷积关系。成卷积关系。 大连理工大学出版社2.42.4离散傅立叶变换的运算特征离散傅立叶变换的运算特征性质性质信号序列信号序列傅立叶变换表示傅立叶变换表示周期性周期性f(n) 线性线性f(n)、x(n)奇

27、偶对称性奇偶对称性f(n)为奇（偶）对为奇（偶）对称序列称序列 也为奇（偶）对也为奇（偶）对称序列称序列共轭对称性共轭对称性f(n)=fr(n)+jfi(n)r：实部：实部i：虚部：虚部Fe(k)=DFTfr(n)Fo(k)=DFTfi(n)e：共轭偶部：共轭偶部o：共轭奇部：共轭奇部a、b为常数为常数)(jjebXeaF)(jeFr=0,1,2,)()()2(rjjeFeF大连理工大学出版社时移特性时移特性f(n+n0)频移特性频移特性卷积特性卷积特性f(n)y(n)=f(n)h(n)Parseval（巴塞菲尔（巴塞菲尔）定理）定理f(n)2.42.4离散傅立叶变换的运算特征离散傅立叶变换的

28、运算特征 NknjekFnnf020DFT NnljenflkF2IDFT kHkFNkY1 njdeFnf2221大连理工大学出版社2.52.5DFT的快速算法的快速算法快速快速傅立叶变换傅立叶变换FFT2.5.1FFT的种类的种类 按照离散时间序列是输入有序还是输出有序，按照离散时间序列是输入有序还是输出有序，FFT算法算法可分为时域抽取法可分为时域抽取法(Decimation In Time FFT)和频域抽取法和频域抽取法(Decimation In Frequency FFT)两种，前者简称两种，前者简称DIT-FFT，后，后者简称者简称DIF-FFT。 把输入有限长离散时间序列划分

29、成两个子序列分别计算把输入有限长离散时间序列划分成两个子序列分别计算的的FFT算法，称为基算法，称为基-2FFT算法，（或算法，（或“基基2FFT算法算法”）。）。把输入有限长离散时间序列划分成把输入有限长离散时间序列划分成4个子序列分别计算的个子序列分别计算的FFT算法，称为基算法，称为基-4FFT算法，（或算法，（或“基基4FFT算法算法”）。）。 大连理工大学出版社2.52.5DFT的快速算法的快速算法快速快速傅立叶变换傅立叶变换FFT2.5.2FFT算法设计思路算法设计思路设设f(n)是长度为是长度为N的有限长序列，它的离散傅立叶变换的有限长序列，它的离散傅立叶变换DFT为：为： )(

30、DFT)(nxkF10)(NnknNWnf 对于所有对于所有F(k) 的的N个值，运算的总次数为个值，运算的总次数为N2次复数乘法次复数乘法和和N（N-1）次复数加法。）次复数加法。 减少运算量的有效做法是将减少运算量的有效做法是将N个点的个点的DFT分成几个较短分成几个较短的的DFT分头计算，例如等份成分头计算，例如等份成M个，每一个短的个，每一个短的DFT长度长度只有只有N/M。 大连理工大学出版社2.52.5DFT的快速算法的快速算法快速快速傅立叶变换傅立叶变换FFT2.5.2FFT算法设计思路算法设计思路计算计算F(k)总的运算工作量为：总的运算工作量为： MNMMNMMNMNMN/2

31、)/(2) 1/(/)/(222与不等分成与不等分成M时的计算相比，总的工作量下降了时的计算相比，总的工作量下降了1/M。 如果把每一个短的如果把每一个短的DFT继续分解成继续分解成P个更短序列的个更短序列的DFT，计算的工作量将又下降计算的工作量将又下降1/P，继续等分下去再计算，结果将使，继续等分下去再计算，结果将使离散傅立叶变换进行得更快，能使离散傅立叶变换进行得更快，能使DFT的运算速度提高几个数的运算速度提高几个数量级。量级。 此外，利用的周期性质、对称性质及一些特殊值还能进一此外，利用的周期性质、对称性质及一些特殊值还能进一步加快运算速度。步加快运算速度。大连理工大学出版社 利用分

32、解长序列的利用分解长序列的DFT、的性质快速实现、的性质快速实现DFT运算的算运算的算法被称为快速傅立叶变换法被称为快速傅立叶变换(Fast Fourier Transform，FFT)算法。算法。 2.52.5DFT的快速算法的快速算法快速快速傅立叶变换傅立叶变换FFT2.5.2FFT算法设计思路算法设计思路将序列将序列f(n)不断分成不断分成2个的这种个的这种FFT算法称为基算法称为基-2FFT算法。算法。将序列将序列f(n)不断分成不断分成4个的这种个的这种FFT算法称为基算法称为基-4FFT算法。算法。大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法F

33、FT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1 设设f(n)的离散傅立叶变换为的离散傅立叶变换为F(k)，其中，其中n、k的取值范围均的取值范围均为为0，N-1。不失一般计，设长度。不失一般计，设长度N为偶数，若为偶数，若N为奇数，可为奇数，可补充一个零使补充一个零使N为偶数。为偶数。 将将f(n)分成两部分，偶数部分组成一个偶序列，奇数部分分成两部分，偶数部分组成一个偶序列，奇数部分组成一个奇序列，分别用组成一个奇序列，分别用f1(i)和和f2(i)表示，偶序列表示，偶序列f1(i)为：为： f1(i)=f(2i) 式中式中 12/0Ni奇序列奇序列f2(i)为：为： f2(i)=

34、f(2i+1) 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1各自的离散傅立叶变换：各自的离散傅立叶变换：F1(k)=DFTf1(i) F2(k)=DFTf2(i)有有iikNNiikNNnknNNnknNNnknNWifWifnWnfnWnfWnfnfDFTkF为奇数为偶数大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1考虑到考虑到f1(i)=f(2i)， f2(i)=

35、f(2i+1)且且 kiNikNWW22则则F(k)可写成：可写成： kFWkFWifWWifWWifWifkFkNNikiNkNNikiNkNNikiNNikiN2112022120211202212021大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1 上式表明，按照上式表明，按照n的奇偶性能将的奇偶性能将f(n)分解成两个序列分解成两个序列f1(i)和和f2(i)，每个序列的长度均为，每个序列的长度均为N/2。而。而N个点的离散傅立叶变换个点的离散傅立叶变换F(k)又可以分解成两个又可以分解成两个

36、N/2点的点的DFT进行运算，进行运算，F1(k)和和F2(k)就就分别是分别是f1(i)和和f2(i)的的N/2点点DFT。这里，。这里，k的取值为的取值为k=0，1，2，N/2-1。 kNNkNWW2 如果如果F1(k)和和F2(k)的表达式代入到的表达式代入到F(k)中，考虑到中，考虑到 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1利用利用F1(k)和和F2(k)的隐含周期性，的隐含周期性，则有则有: kFWifWifNkFkFWkFNkFikNNiNkiNNikN12120122120112

37、122 kFNkF222大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1 F1(k)、F2(k)的前半部分值的前半部分值(k取值取值0，N/2-1)与后半部分与后半部分值值(k取值取值N/2，N-1)相等。相等。 由离散傅立叶变换的对称性：由离散傅立叶变换的对称性： kNNNkNNkNWWWW22能把能把F(k)分解成前后两部分。其中前半部分的自变量为分解成前后两部分。其中前半部分的自变量为k：0，N/2-1，F(k)表示成：表示成： kFWkFkFkN21大连理工大学出版社2.62.6基基-2FFT算

38、法算法2.6.1时域抽取法时域抽取法FFT将将f(n)分成奇序列和偶序列分成奇序列和偶序列 1后半部分的自变量为后半部分的自变量为k：N/2，N-1，F(k+N/2)表示成：表示成： kFWkFNkFWNkFNkFkNNkN21221222 因此，因此，F(k)的所有值可通过以下方法求出：的所有值可通过以下方法求出： 只需求得奇、偶序列前半个区间只需求得奇、偶序列前半个区间(k取值取值0，N/2-1)内所内所有有F1(k)、F2(k)之值。之值。 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT蝶形流程蝶形流程2 使用流程图来表示信号的输入输出间关系，是

39、一种直观使用流程图来表示信号的输入输出间关系，是一种直观表示表示FFT的方法。例如方程组：的方法。例如方程组： 12, 2 , 1 , 0,12, 2 , 1 , 0,22121NkNkkFWkFNkFkFWkFkFkNkN可以用流程图表示，如图所示，该图称为蝶形流程图。可以用流程图表示，如图所示，该图称为蝶形流程图。 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT蝶形流程蝶形流程2 图中图中F1(k)、F2(k)是输入，是输入，F(k)、F(k+N/2)是输出，输入是输出，输入信号前的系数标注在箭头处，箭头前没有标注的表示流程系信号前的系数标注在箭头

40、处，箭头前没有标注的表示流程系数为数为1，箭头表示信号的流向，相交点表示求和。，箭头表示信号的流向，相交点表示求和。 F (k)1F (k)2F(k)= F (k)+ W1NkF (k)2F(k+ N /2) =F (k)- W1NkF (k)2蝶形流程图蝶形流程图 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3 设设N=8对对f(n)和和F(k)进行分解，其中进行分解，其中f(n)有有f(0)，f(1)，f(7)；F(k)有有F(0)，F(1)，F(7)。 考虑到考虑到n=0，1，2，7，将，将f(n)分成偶数序列分成偶数序

41、列f1(i)和奇和奇数序列数序列f2(i)，i=0，1，2，3。f1(i)由由f(0)，f(2)，f(4)，f(6)组成；组成；f2(i)由由f(1)，f(3)，f(5)，f(7)组成。它们的组成。它们的DFT分别用分别用F1(k)(k=0，1，2，3)和和F2(k)(k=0，1，2，3)表示。如图所示。表示。如图所示。 大连理工大学出版社f(0)= f1( 0)f(2)= f1( 1)f(4)= f1( 2)f(6)= f1( 3)f(1)= f2( 0)f(3)= f2( 1)f(5)= f2( 2)f(7)= f2( 3)N /2点DFTN /2点DFTF1( 0)F1( 1)F1( 2

42、)F1( 3)F2( 0)F2( 1)F2( 2)F2( 3)f(n)分解分解 2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3设设k=0，1，2，3，F(k)的产生用的产生用 kFWkFkFkN21得：得： 333222111000231221211201FWFFFWFFFWFFFWFFNNNN大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3F1( 0)F1( 1)F

43、1( 2)F1( 3)F2( 0)F2( 1)F2( 2)F2( 3)F(0)F(1)F(2)F(3)WWWWNNNN0123F(0)F(3)的产生的产生 由此画成如图所示：由此画成如图所示： 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3而而F(k+N/2)的产生用的产生用 83210,221NkkFWkFNkFkN，得：得： 337226115004231221211201FWFFFWFFFWFFFWFFNNNN大连理工大学出版社由此画成图如图所示：由此画成图如图所示： 2.62.6基基-2FFT算法算法2.6.1时域抽取

44、法时域抽取法FFTN=8点点DFT分解分解3F1( 0)F1( 1)F1( 2)F1( 3)F2( 0)F2( 1)F2( 2)F2( 3)F(4)F(5)F(6)F(7)WWWWNNNN0123-1-1-1-1F(4)F(7)的产生的产生 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3 如果将上述三图合在一起，便可以画出由如果将上述三图合在一起，便可以画出由f(n)F(k)的流的流程，如下图所示。程，如下图所示。 f(0)= f1( 0)f(2)= f1( 1)f(4)= f1( 2)f(6)= f1( 3)f(1)= f2

45、( 0)f(3)= f2( 1)f(5)= f2( 2)f(7)= f2( 3)N /2点DFTN /2点DFTF1( 0)F1( 1)F1( 2)F1( 3)F2( 0)F2( 1)F2( 2)F2( 3)WWWWNNNN0123-1-1-1-1F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)由由f(n)到到F(k)的流程的流程 大连理工大学出版社 再看再看f1(i)和和f2(i)，i =0，1，2，3，它们虽然分别是，它们虽然分别是f(n)的偶、的偶、奇序列，但它们各自的长度奇序列，但它们各自的长度N/2=4仍然为偶数。既然为偶数，仍然为偶数。既然为偶数，就可以将就可以将f

46、1(i)分解成两个序列：一个奇数序列、一个偶数序列，分解成两个序列：一个奇数序列、一个偶数序列，这样分解后每个序列的长度应为这样分解后每个序列的长度应为N/4=2。同理，。同理，f2(i)也可以分也可以分解长度为解长度为N/4的两个序列。的两个序列。 2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3大连理工大学出版社f(0)= f1(0)= f3(0)f(4)= f1(2)= f3(1)f(2)= f1(1)= f4(0)f(6)= f1(3)= f4(1)f(1)= f2(0)= f5(0)f(5)= f2(2)= f5(1)f(3)= f2(

47、1)= f6(0)f(7)= f2(3)= f6(1)F1(0)F1(1)F1(2)F1(3)F2(0)F2(1)F2(2)F2(3)WWWWNNNN0123-1-1-1-1F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)N /4点DFTN /4点DFTN /4点DFTN /4点DFTF3(0)F3(1)F4(0)F4(1)F5(0)F5(1)F6(0)F6(1)WWWWNNNN0202-1-1-1-12.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3一个一个f(n)被分解成了被分解成了4个序列个序列 大连理工大学出版社2.62.6

48、基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFTN=8点点DFT分解分解3继续进行奇偶划分，这样一个继续进行奇偶划分，这样一个f(n)可被分解成可被分解成8个序列：个序列： F(0)f(4)f(2)f(6)f(1)f(5)f(3)f(7)WWWWNNNN0123-1-1-1-1F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)WWWWNNNN0202-1-1-1-1WWNN00WWNN00-1-1-1-1大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT自然顺序和倒位顺序自然顺序和倒位顺序4 在在DFT分解流程中，从输入分解流程中，

49、从输入f(n)到输出到输出F(k)遵循着自然顺遵循着自然顺序和倒位顺序的规律。以序和倒位顺序的规律。以N=8为例，输入为例，输入f(n)有有8个：个：f(0)，f(1)，f(7)；输出；输出F(k)也有也有8个：个：F(0)，F(1)，F(7)。即。即n=0，1，7；k=0，1，7。 如果如果n和和k都用二进制数表示，则都用二进制数表示，则n=000，001，010，111；k=000，001，010，111。大连理工大学出版社 二进制数从小到大的排列顺序称为自然顺序，将二进制数二进制数从小到大的排列顺序称为自然顺序，将二进制数的最高位变成最低位，次高位变成次低位，的最高位变成最低位，次高位变

50、成次低位，这样形成的排，这样形成的排列顺序为倒位顺序。用式子来表示，如果列顺序为倒位顺序。用式子来表示，如果n2n1n0为自然顺序，为自然顺序，则则n0n1n2就是倒位顺序，其中就是倒位顺序，其中n0、n1、n2仅取值仅取值0或或1。 2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT自然顺序和倒位顺序自然顺序和倒位顺序4 本节讨论的本节讨论的N=8点点f(n)分解成分解成8个序列例子中，个序列例子中，f(n)遵循倒遵循倒位顺序，位顺序，F(k)遵循自然顺序。遵循自然顺序。 大连理工大学出版社2.62.6基基-2FFT算法算法2.6.1时域抽取法时域抽取法FFT自然顺序和倒

51、位顺序自然顺序和倒位顺序4 产生自然顺序及倒位顺序的原因是在时域抽取的产生自然顺序及倒位顺序的原因是在时域抽取的FFT算法算法中，不停顿地对输入序列进行奇偶分组，分组过程形成了一个中，不停顿地对输入序列进行奇偶分组，分组过程形成了一个倒位序列的树状图，如图所示。倒位序列的树状图，如图所示。 f(n)偶奇偶偶偶偶偶偶01000000奇 1奇 1奇 1奇 1奇 1奇 1000001010011100101110111F(k)大连理工大学出版社2.62.6基基-2FFT算法算法F(0)F(4)F(2)F(6)F(1)F(5)F(3)F(7)WWWWNNNN0213-1-1-1-1WWWWNNNN00

52、22WWNN00WWNN00-1-1-1-1f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)f(n)自然顺序自然顺序F(k)倒位顺序的倒位顺序的FFT流程图流程图 2.6.1时域抽取法时域抽取法FFT其他形式的其他形式的FFT流程流程5大连理工大学出版社2.6.1时域抽取法时域抽取法FFT其他形式的其他形式的FFT流程流程52.62.6基基-2FFT算法算法F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)WWWWNNNN0213-1-1-1-1WWWWNNNN0022WWNN00WWNN00f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)f(n)

53、自然顺序自然顺序F(k)自然顺序的自然顺序的FFT流程图流程图 大连理工大学出版社 时域抽取法时域抽取法FFT的要点是将输入时间序列按的要点是将输入时间序列按n为偶数和奇为偶数和奇数不断分解；数不断分解； 频域抽取法频域抽取法FFT的要点是将输出频域序列按的要点是将输出频域序列按k为偶数和奇为偶数和奇数不断分解。数不断分解。 设设f(n)的离散傅立叶变换为的离散傅立叶变换为F(k)，且，且0nN-1，0kN-1。又设又设N为偶数，若为偶数，若N为奇数，则添加一个零使其为偶数。为奇数，则添加一个零使其为偶数。 若设，若设， ，则可将，则可将F(k)分解成偶、奇两个序列，分分解成偶、奇两个序列，分

54、别用别用F1(i)和和F2(i)表示：表示： F1(i)=F(2i) F2(i)=F(2i+1)12/0Ni2.6.2频域抽取法频域抽取法FFT2.62.6基基-2FFT算法算法大连理工大学出版社2.6.2频域抽取法频域抽取法FFT2.62.6基基-2FFT算法算法 若若F1(i)和和F2(i)的离散傅立叶反变换为的离散傅立叶反变换为f1(n)和和f2(n)，12/0Ni，则，则 iFnfiFnf2211IDFTDFTI当当i位于位于0，N-1内时，按内时，按DFT有：有： 1212010NNnnkNNnnkNNnnkNWnfWnfWnfkF大连理工大学出版社2.6.2频域抽取法频域抽取法FFT2.62.6基基-2FFT算法算法上式第二项表示成：上式第二项表示成： kNNnNNNnNNnnkNWNNnfWnf2212021222将将n-N/2用用n取代，有取代，有 nkNNnkkNnNNnNNnnkNW