数字信号处理 第四章

§4.1引言§4.2按时间抽取(DIT)的FFT算法§4.3按频率抽取(DIF)的FFT算法§4.4离散傅立叶反变换(IDFT)的快速计算方法§4.5进一步减少运算量的措施第四章快速傅立叶变换(FFT)数字信号处理§4.1引言全部计算N个X(k)N²次

复数乘

N(N-1)次

复数加或4N

²次实数乘

N(4N-2)次

实数加例如

10点DFT100次

复数乘；

1024点DFT1,048,576次

复数乘，即100万次的复数乘运算！结论：直接计算DFT的计算量和N的平方成正比一、DFT直接计算工作量很大计算一个X(k)工作量：N次

复数乘(N-1)次复数加或4N次

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

实数加••••对称性:周期性本章以基2的FFT算法为重点二、DFT的高效计算1965年

Cooley&Tukey

奠定FFT，把长序列短分解，利用WN因子的周期性和对称性，可导出一个高效的快速算法使得乘法计算量由N

2

次降为次。以1024点为例，计算量降为5120次，仅为原来的4.88%。可约性:§4.2按时间抽取(DIT)的FFT算法(库利-图基算法)一、算法原理（时域奇偶分，频域前后分）设x(n)长度N，N=2M，M为自然数x2(r)=x(2r+1)x1(r)=x(2r)

1、第一次抽取：x(n)的DFT为：将x(n)按偶、奇分成两组，可得两各自长度为N/2的奇偶序列其中X1

(k)和X2

(k)分别为

x(2r)和x(2r＋1)的N/2点DFT：由于它们均以N/2为周期，且，因此这样，将一个N点DFT分解成两个N/2点DFT。由于X1

(k)和X2

(k)都是N/2点DFT，而X(k)有N点，所以得计算后N/2点.••••☉☉☉☉-1X(k)X1(k)X2(k)同理用下面的蝶形图也可清楚地说明这种运算。AA+BCCBA-BC蝶形运算符号一个蝶形运算：一次复数乘、两次复数加运算量：几次乘？几次加？运算量减少近一半经过一次时域抽取计算量：复数加：复数乘：碟形运算2、蝶形运算••••☉☉☉☉-1X(k)X1(k)X2(k)直接计算需要8×8次复数乘、8×7次复数加36次复数乘32次复数加以N＝8为例DFT(N=8)☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉x(0)x(1)x(2)...x(7)X(0)X(1)X(2)...X(7)DFT(N=4)☉☉☉☉DFT(N=4)☉☉☉☉x(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)••☉☉☉☉☉☉☉☉X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)3、第二次抽取将

x1(r)

按奇偶分解成两个N/4长的子序列x3(l

)和

x4(l

)

于是同样，将

按奇偶分解成两个N/4长的子序列和

经过第二次分解，将N/2点的DFT分解成两个N/4点的DFT和N/4个蝶形运算。依次类推，经过M－1次分解，最后将N点DFT分解成N/2个2点DFT。当N=8时，•DFT(N=2)☉☉DFT(N=2)☉☉DFT(N=2)☉☉DFT(N=2)☉☉•••☉☉☉☉☉☉☉☉•☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉•••••••••••8点FFT运算流图2.DFT-FFT与直接计算DIT算法运算量比较每级蝶形有多少次复数乘和复数加？二、算法的讨论1.级的概念DIT-FFT算法过程，将N点DFT先分成两个N/2点DFT，再……直至

N/2个两点DFT。每分一次，称为一“级”运算。N点DFT可以分成M级，从左到右依次是1，2，…，M级，每级有N/2个蝶形M＝log2N。此算法以2为基，写作

N＝2M(不足位，补零延伸)。全部“蝶形”数：NM/2，M级，每级N/2个蝶形；一个蝶形运算：一次复数乘、两次复数加。复数乘法次数：NM/2，复数加法次数：NM。都<<N2，在N值很大时，十分高效。直接DFT，复数乘N平方次，复数加为N(N-1)次。N/2次复数乘，N次复数加FFT•••••每次运算结果存入原输入数据占用的存贮单元3.原位计算（同址运算）这种利用同一存贮单元存贮蝶形计算输入输出数据的方法称为原位(址)计算。原位计算可节省大量内存，使设备成本降低N＝2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成设N个存贮单元存入数据A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)••••☉☉☉☉X

L

(k)X

L

(

j

)X

L-1

(k)X

L-1

(j)4.码位倒置（倒位序规律）顺位序二进顺序码二进倒置码倒位序

0000000010011004201001023011110641000011510110156110011371111117

按相似原理：若按自然序x(0)，x(1)，x(2)，…输入后不进行变址运算，则输出将倒位序：X(0)，X(4)，X(2)，X(6)….…。由DIT－FFT流图可以看出，变换后的输出

X

(k)依照正序排列，输入序列x

(n)

不再是原来的自然顺序，这是由于对x

(n)作奇偶抽取所产生的。对N＝8，其自然序号是0，1，2，3，4，5，6，7第一次按奇偶分开，x(n)的序号是0，2，4，6|1，3，5，7每一组再作奇偶分开后序号是0，4|2，6|1，5|3，7先按自然顺序输入，

变址运算将顺序码的二进制位倒置倒位序x(n2n1n0)n0n1n201010101110100000100010110001101011111描述倒位序的树状图掌握这一规律可以做到正确的编程4.旋转因子的分布规律

在N点DIT－FFT运算流图中，每级有N/2个蝶形，每个蝶形要乘以因子W

r；第一次将N点DFT分成两个N/2点DFT，这时出现的W

r因子是：再往下分时，依次是，故每一级W

r因子的分布规律是：…W

r因子的一般分布规律：5、蝶形运算两点间的距离

以8点FFT为例，输入是倒位序的输出是自然顺序，第一级（第1列）每个蝶形两点间的“距离”为1，第二级每个蝶形的两点“间距离”为2，第三级为4，由此类推，对于点FFT，当输入为倒位序，输出为正常顺序，其第L级运算，每个蝶形的两点“距离”为。§4.3按频率抽取(DIF)的FFT算法(桑德-图基算法)一、算法原理（时域前后分，频域奇偶分）设x(n)长度N=2M，并将x

(n)分成前后两段：∴令后者的n=m+N/2，得：k为偶数k为奇数其中因此，按k奇偶将X(k)分解成偶数组和奇数组：令k＝2r令k＝2r+1☉☉☉☉x(n+N/2)x

(n)x1(n)x2(n)••••☉☉☉☉X形运算单元蝶形运算单元☉☉☉☉•按频率抽取法的蝶形运算流图符号DIF-FFT一次分解运算流图(N=8)☉☉☉☉☉☉☉☉••DFT(N/2)☉☉☉☉DFT(N/2)☉☉☉☉••X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)☉☉☉☉☉☉☉☉☉☉☉☉••☉☉☉☉••••8点DFT的DIF-FFT三级运算流图输入为顺序，输出为倒序二、运算量次复数加法。次复数乘法，DIF和DIT具有一样的运算量：三、原位运算

与DIT一样，DIF很有规律，其每级（每列）计算都是由N/2个蝶形运算构成，每一个蝶形结构都完成下述基本迭代运算。此蝶形运算也是由一次复数乘和两次复数加组成。三、按频率抽取法和按时间抽取法的异同点1.基2DIT－FFT算法(1)算法思想：时域M级奇偶抽取，并利用，将N点DFT变成M级蝶形运算。(2)运算量：复数乘法次数复数加法次数(3)

特点：运算流图结构规则，可原位计算，程序简短，应用广泛。2.基2DIF－FFT算法(1)算法思想：频域对X(k)进行M级奇偶抽取，并利用

将N点DFT变成M级DIF－FFT蝶形运算.(2)运算量及特点与基2DIF－FFT相同。4、DIT与DIF的联系5、通常多使用基2的FFT，因为它简单、效率高。

当N为任意数时，可将x(n)延伸补0；若不允许延伸情况下，可考虑基r的FFT（如r=3,4,….），或混合基FFT。3、DIT与DIF的本质区别在于基本蝶形的不同

(1)只要保持各节点所连的支路和传输系数不变，变换节点位置的排列，可以得到其它等效形式的流图。(2)DIT与DIF的流图满足转置定理：将所有支路方向都反向，并且交换输入和输出，但节点变量值不交换。DIF的复数乘法出现在减法之后，而DIT是先复数乘再作加法。•••••按时间抽取蝶形运算单元按频率抽取蝶形运算单元☉☉☉☉•时间抽取基2-FFT算法的原理示意图X(n).........N/2点碟形组合N/4蝶形组合N/4蝶形组合N/8碟形组合N/8碟形组合N/8碟形组合N/8碟形组合X(k)NN/2N/4N/82点DFT2点DFT2点DFT...4点碟形组合2点DFT4点碟形组合...248x(n)N/2碟形分解N/4碟形分解N/4碟形分解N/8碟形分解N/8碟形分解N/8碟形分解N/8碟形分解NN/2N/4频率抽取基2-FFT算法的原理示意图N/8.........2点DFT2点DFT2点DFT...4点碟形分解2点DFT4点碟形分解...24X(k)§4.4离散傅立叶反变换(IDFT)的快速计算方法由定义：两者作比较，得到启发修改DFT运算中的各个系数-----将改为，最后乘以1/N。由于乘以1/N，等于各级乘以1/2因子，因此将常数1/N分解为，分散到各级中，即每一级都乘以因子1/2。方法一：不足：需要改变FFT的程序和参数才能实现。方法二：不修改FFT的程序和参数，利用共轭变换的方法∵∴

取共轭直接访问FFT程序取共轭乘系数X(k)优点：DFT和IDFT可以共用一个子程序模块由定义：§4.5进一步减少运算量的措施1.多类蝶形单元运算2.旋转因子的生成在FFT中，乘法主要来自旋转因子，在编程时，正、余弦函数的产生