数字信号处理(中澳双语8-1)-第二十讲

郑州大学信息工程学院1DigitalSignalProcessing数字信号处理郑州大学信息工程学院蒋慧琴第八章DFT的有效计算：

快速傅立叶变换

FFT-FastFourierTransform本章内容1)明确FFT与DFT的关系：只是计算方法的改进，基本没有引入新的物理概念；2)掌握FFT算法的原理：利用DFT的运算规律及其中某些算子的特殊性质（的周期性和对称性），找出减少乘法和加法运算次数的有效途径；3)掌握基-2DIT—FFT和基-2DIF—FFT算法的基本思想及特点（算法思想，运算量，运算流图，结构规则等）。郑州大学信息工程学院34

对每个特定k,

X(k)的

DFT的计算：有(N－1)个复加和

N

个复乘；

计算整个DFT

共有N(N-1)个复加和N2

个复乘；通过利用

的对称性和周期性，整个DFT的复乘计算量可减至为

Nlog2N

FastFourierTransform(FFT).8.1DFT的有效计算：FFT算法(概述)2.用分而治之的方法计算DFT基本原理:把计算长度为的序列的DFT逐次地分解成计算长度较短序列的离散傅里叶变换。将序列储存在二维数组中，它的每个数据都依赖于下标到下标的映射。计算所得的DFT值储存在一个类似的排列中，映射是从下标到下标对(p,q)的映射,567例8.1.1考虑时的点DFT的计算

8对每一列计算5点DFT

9当按照从第一行到第五行的顺序读取时，得到如下序列：

出现在输入数据序列或输出DFT序列中的重排是大多数FFT算法的一个共有的特性。

算法一1)按列向储存信号；2)计算每一行的点DFT；3)用乘上所得数组；4)计算每一列的点DFT；5)按行向读取所得数组。

假如输入序列按行向存储，所得变换序列按列向存储

算法二：1)按行向储存信号；2)计算每一列的点DFT；3)用相位因子乘上所得数组；4)计算每一行的点DFT；5)按列向读取所得数组。

10两种算法其复杂性相同，但它们在计算的排列上不同的。

郑州大学信息工程学院11FFT算法分类:时间抽选法

DIT:Decimation-In-Time频率抽选法

DIF:Decimation-In-Frequency按时间抽取（DIT）的FFT算法1、算法原理 设序列点数N=2L，L

为整数。若不满足，则补零郑州大学信息工程学院12（DecimationInTime）将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。将N点DFT定义式分解为

两个长度为N/2的DFT13记：………（1）（这一步利用：）郑州大学信息工程学院14再利用周期性求X(k)的后半部分将上式表达的运算用一个专用“蝶形”信流图表示。郑州大学信息工程学院15注：a.上支路为加法，下支路为减法；

b.乘法运算的支路标箭头和系数。用“蝶形结”表示上面运算的分解： 郑州大学信息工程学院16郑州大学信息工程学院17分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半郑州大学信息工程学院18进一步分解由于，仍为偶数，因此，两个点DFT又可同样进一步分解为4个点的DFT。郑州大学信息工程学院19“蝶形”信流图表示

N点DFT分解为四个N/4点的DFT郑州大学信息工程学院20郑州大学信息工程学院21“蝶形”信流图表示

类似进一步分解类似的分解一直继续下去，直到分解为最后的两类蝶形运算为止(2点DFT).如上述N=8=23，N/4=2点中：郑州大学信息工程学院221点DFTx(0)1点DFTx(4)X3(0)X3(1)郑州大学信息工程学院23进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)因此8点FFT时间抽取方法的信流图如下——郑州大学信息工程学院24FFT运算量与运算特点

1．N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2．每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3．计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N次复乘法；复加法L*N=Nlog2N次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当N大时，此倍数很大。郑州大学信息工程学院25郑州大学信息工程学院26比较DFT可以直观看出，当点数N越大时，FFT的优点更突出。DITFFT中最主要的蝶形运算实现（1）参与蝶形运算的两类结点（信号）间“距离”（码地址）与其所处的第几级蝶形有关；第m级的“结距离”为

(即原位计算迭代）（2）每级迭形结构为郑州大学信息工程学院27郑州大学信息工程学院28

蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L–m位，把右边空出的位置补零，结果为r的二进制数。（3）的确定：第m级的r取值：四、FFT算法中一些概念

（1）“级”概念将N

点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT.

每分一次称为“一”级运算。因为N=2M所以N点DFT可分成M级如上图所示依次m

=

0,

m

=

1

….

M-1共M级郑州大学信息工程学院29（2）“组”概念郑州大学信息工程学院30

每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的因子分布，第m级的组数为：例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为(3)因子的分布郑州大学信息工程学院31结论：每由后向前（m由M-1-->0级）推进一级，则此系数为后级系数中偶数序号的那一半。郑州大学信息工程学院32

例用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为 次，仅为直接计算DFT所需时间的10万分之一。即原需要3000小时，现在只需要2分钟。按频率抽取（DIF）的FFT算法与DIT-FFT算法类似分解，但是抽取的是X(k)。即分解X(k)成奇数与偶数序号的两个序列。设：N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：33（DecimationInFrequency)一、算法原理郑州大学信息工程学院34下面讨论郑州大学信息工程学院35按k的奇偶将X(k)分成两部分：显然：郑州大学信息工程学院36令：用蝶型结构图表示为：郑州大学信息工程学院37x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)郑州大学信息工程学院38N/2仍为偶数，进一步分解：N/2→N/4郑州大学信息工程学院39x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)按照以上思路继续分解，即一个N/2的DFT分解成两个N/4点DFT，直到只计算2点的DFT，这就是DIF-FFT算法。郑州大学信息工程学院402个1点的DFT蝶形流图进一步简化为蝶形流图：1点DFTx3(0)1点DFTx3(1)X(0)X(4)X(0)X(4)x3(0)x3(1)郑州大学信息工程学院41二、按频率抽取FFT蝶形运算特点1）原位计算郑州大学信息工程学院42-1L级蝶形运算，每级N/2个蝶形，每个蝶形结构：

m表示第m级迭代，k，j表示数据所在的行数郑州大学信息工程学院432）蝶形运算对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-m=N/2m第m级运算：郑州大学信息工程学院44

蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移m-1位，把右边空出的位置补零，结果为r的二进制数。存储单元输入序列x(n):N个存储单元系数：N/2个存储单元郑州大学信息工程学院45三、DIT与DIF的异同基本蝶形不同DIT:先复乘后加减DIF:先减后复乘运算量相同都可原位运算DIT和DIF的基本蝶形互为转置4、

基4-FFT算法

在DFT中当数据点数为4的幂时，采用基4算法计算更加有效。(1)按时间抽取的基4-FFT算法(2)按频率抽取的基4-FFT算法46IDFT的FFT算法

（FFT应用一）

一、从定义比较分析郑州大学信息工程学院47与DFT的比较：

1）、旋转因子WN-kn

的不同；

2）、结果还要乘1/N。郑州大学信息工程学院48二、实现算法——直接使用FFT程序的算法共轭FFT共轭乘1/N直接调用FFT子程序计算IFFT的方法：三、实序列的FFT算法1、实序列的FFT：减少运算量x(n)为实序列，X(k)共轭对称：只需求得一半2、用一个N点DFT计算两个实序列的N点DFT设x1(n)和x2(n)分别是长度为N的实序列令y(n)＝x1(n)＋jx2(n)，则

Y(k)=DFT[y(n)]

493、用一个N点DFT计算2N点实序列的DFT设x(n)为2N点实序列，按x(n)的序号为偶数和奇数抽取序列，分别作为新构造序列的实部和虚部，即则y(n)为N点复序列50对y(n)进行N点FFT,输出Y(k),则根据D