DSP_14离散傅立叶变换-FFT_2

1、2022-3-6数字信号处理 陈鹏 32993401快速傅立叶变换快速傅立叶变换 Fast Fourier Transform (FFT)Lesson 142022-3-6数字信号处理 陈鹏 32993402复习提问l时间抽取的时间抽取的FFT的两条规则？的两条规则？lFFT主要利用了什么的特性？主要利用了什么的特性？lFFT可分解多少级，每级有多少个蝶形单可分解多少级，每级有多少个蝶形单元，每个蝶形有多少次乘法和加法？元，每个蝶形有多少次乘法和加法？2022-3-6数字信号处理 陈鹏 32993403运算量的比较运算量的比较 pXm qXm1kNW pXm 1 qXm 1堞形计算流程图 11

2、2DFTM2DFTMM2FFT MkmmNmkmmNmNNx nX kXpXpW XqXqXpW Xq任何一个的，都可以通过次分解最后称为 点的来计算。次分解构成了从到的级迭代计算，每级由个堞形组成。流出图中每一个堞形的一般形式如右图所示，其输入和输出之间满足下列关系：NNMNNNMNF22log22log22FFTN，复数加法次数：复数乘法次数：计算的总运算量为点的时间抽选完成此，法和两次复数加法。因堞形计算需一次复数乘从上式看出，完成一个2022-3-6数字信号处理 陈鹏 32993404运算量的比较运算量的比较30/2/4/42283122411DFT NNNNNNNDNWWWjWjN

3、例如，当时，需要 级迭代计算，共需要复数乘法次和复数加法次。考虑到，与这几个系数相乘实际上不需要乘法运算，所以实际的运算量要更少。大多数情况下复数乘法所花时间最多，所以下面仅以复数乘法的计算次数为例来与直接计算进行比较。直接计算需要的乘法次数为，于是有2222 loglog2N1024205DFTFFT205NFFTNDFDFNNNNN例如，当时，则，即直接计算所需要复数乘法次数约为的倍，显然， 越大，的速度优势越大。下表列出了不同值所对应的两种计算方法的复数乘法次数和它们的比值。2022-3-6数字信号处理 陈鹏 32993405运算量的比较运算量的比较N所需复数乘法次数所需复数乘法次数减少

4、乘法次数减少乘法次数的倍数的倍数直接计算直接计算DFT用用FFT计算计算DFT2414.041644.0864125.416256328.03210248012.864409619221.41281638444836.625665536102464.05122621442304113.8102410485765120204.82048419430411264372.42022-3-6数字信号处理 陈鹏 32993406DFT计算 0*10*00*11*11*01*11 *01 *11 *1.0011.:11.NNNNNNNNNNNNNNNWWWXxXxWWWX Nx NWWW2022-3-6数

5、字信号处理 陈鹏 32993407FFT计算计算 0 x 2x 4x 6x2NW0NW11 1x 3x 5x 7x2NW0NW113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X10NW10NW10NW10NW2022-3-6数字信号处理 陈鹏 32993408蝶形的同址蝶形的同址(原位原位)计算计算FFT流程图中包含流程图中包含 级迭代运算，每级由级迭代运算，每级由 个蝶形计算构个蝶形计算构成。成。蝶形计算的优点是可以进行所谓的同址或原位计算蝶形计算的优点是可以进行所谓的同址或原位计算。现在来考虑。现在来考虑第一级的计算规律。设将输入第一级的计算规律。设将输入

6、分别存入计算机的存储单元分别存入计算机的存储单元中。首先，存储单元中。首先，存储单元 中的数据中的数据 进入运算器进入运算器并进行蝶形运算，并进行蝶形运算，由于以后的运算不需要用到这两个数据，因而不需由于以后的运算不需要用到这两个数据，因而不需要保留要保留。这样，蝶形运算后的结果便可以送到这样，蝶形运算后的结果便可以送到 存储起来。存储起来。类似地，类似地， 中的中的 进入运算器进行蝶形运算后送进入运算器进行蝶形运算后送回回 保存，等等。保存，等等。 7,3,5,1,6,2,4,0 xxxxxxxxN2log2/N 8,7,6,5,4,3,2,1MMMMMMMM 2,1 MM 4,0 xx 2

7、,1 MM 4,3 MM 6,2xx 4,3 MM2022-3-6数字信号处理 陈鹏 32993409蝶形的同址蝶形的同址(原位原位)计算计算第二级运算与第一级类似，不过，第二级运算与第一级类似，不过， 存储单元中的数据存储单元中的数据进行蝶形运算后的结果被送回到进行蝶形运算后的结果被送回到 保存，保存， 中的数据进行蝶形运算后结果送回到中的数据进行蝶形运算后结果送回到 保存，等等。保存，等等。这样一直到最后一级的最后一个蝶形运算完成。可以看出，这样一直到最后一级的最后一个蝶形运算完成。可以看出，每一每一级的蝶形的输入与输出在运算的前后可以存储在同一地址级的蝶形的输入与输出在运算的前后可以存储

8、在同一地址(原来位原来位置上置上)的存储单元中，这种同址运算的优点是可以的存储单元中，这种同址运算的优点是可以节省存储单元节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。从而降低对计算机存储量的要求或降低硬件实现的成本。 3,1 MM 3,1 MM 4,2 MM 4,2 MM2022-3-6数字信号处理 陈鹏 329934010变址计算变址计算从前面所示的从前面所示的FFT流程图中可以看出，同址计算要求输入流程图中可以看出，同址计算要求输入 是是“混序混序”排列的。所谓输入为排列的。所谓输入为“混序混序”，并不是说输入是杂乱无章的，并不是说输入是杂乱无章的，实际上它是有规律的。

9、如果输入实际上它是有规律的。如果输入 的序号用二进制码来表示，的序号用二进制码来表示，就可以发现就可以发现输入的顺序恰好是正序输入的输入的顺序恰好是正序输入的“码位倒置码位倒置”，下表列出了，下表列出了这种规律。这种规律。实际运算中，按码位倒置顺序输入数据实际运算中，按码位倒置顺序输入数据 ，特别当，特别当N较大时，是较大时，是很不方便的。因此，数据总是按自然顺序输入存储，然后很不方便的。因此，数据总是按自然顺序输入存储，然后通过通过“变址变址”运算将自然顺序换成码位倒置顺序存储运算将自然顺序换成码位倒置顺序存储。 nx nx nx2022-3-6数字信号处理 陈鹏 329934011变址计算

10、变址计算码位倒置顺序码位倒置顺序自然顺序自然顺序二进制表示二进制表示码位倒置码位倒置码位倒置顺序码位倒置顺序x(0)x(000)x(000)x(0)x(1)x(001)x(100)x(4)x(2)x(010)x(010)x(2)x(3)x(011)x(110)x(6)x(4)x(100)x(001)x(1)x(5)x(101)x(101)x(5)x(6)x(110)x(011)x(3)x(7)x(111)x(111)x(7)2022-3-6数字信号处理 陈鹏 329934012实现由自然顺序存储到码位倒置顺序存储的过程如下图所示。实现由自然顺序存储到码位倒置顺序存储的过程如下图所示。图中用图中

11、用 表示自然顺序的标号，用表示自然顺序的标号，用 表示码位倒置的标号。表示码位倒置的标号。变址计算变址计算 1M 2M 3M 4M 5M 6M 7M 8M 1x 2x 3x 4x 5x 6x 7x 0 x 0 x 4x 2x 6x 1x 3x 5x 7x nx lx存储单元变址自然顺序输入码位倒置顺序码位倒置的变址处理nl2022-3-6数字信号处理 陈鹏 329934013变址计算变址计算当当 时，时， 和和 不必互相调换；不必互相调换；当当 时，将时，将 和和 进行调换；进行调换；当当 时，时， 和和 不能再进行调换，因为前面已经将不能再进行调换，因为前面已经将它们调换了一次了。它们调换了

12、一次了。这样，按自然顺序输入的数据这样，按自然顺序输入的数据 经过变址计算后变成了码经过变址计算后变成了码位倒置的顺序排列，便可进入第一级的蝶形运算。可以位倒置的顺序排列，便可进入第一级的蝶形运算。可以参看书参看书后附录的后附录的 C 语言程序语言程序实现的实现的FFT算法。算法。nl lx nx nxnl nx lxnl nx lx2022-3-6数字信号处理 陈鹏 329934014时间抽取时间抽取基基2 FFT算法算法 0 x 2x 4x 6x2NW0NW11 1x 3x 5x 7x2NW0NW113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X10NW1

13、0NW10NW10NW2022-3-6数字信号处理 陈鹏 329934015其它形式的其它形式的流程图流程图时间抽选时间抽选FFT算法还有另外一些形式的流程图。对于任何流程图，算法还有另外一些形式的流程图。对于任何流程图，只要只要保持各节点所连之路及其传输系数不变保持各节点所连之路及其传输系数不变，则不论节点位置怎样排列，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到所得到的流程图总是等效的，因而都能得到DFT的结果。把前面介绍的结果。把前面介绍的的FFT流程图中流程图中 x(4) 水平线和水平线和 x(1) 水平线互换，水平线互换， x(6) 水平线和水平线和 x(3) 水平

14、线互换水平线互换，其它不动，则得到下图所示的流程图，显然它的输入是，其它不动，则得到下图所示的流程图，显然它的输入是正序排列的，而输出是码位倒置排列的，所以输出要进行变址计算。正序排列的，而输出是码位倒置排列的，所以输出要进行变址计算。下图所示的流程图相当于最初由库利和图基给出的时间抽选算法。下图所示的流程图相当于最初由库利和图基给出的时间抽选算法。还有一种形式的流程图是还有一种形式的流程图是输入输出都是正序排列的输入输出都是正序排列的，但这类流程图，但这类流程图不不能进行同址计算能进行同址计算，它需要两列长度为，它需要两列长度为 N 的复数存储器。的复数存储器。2022-3-6数字信号处理

15、陈鹏 329934016“顺序顺序”输入和输入和“混序混序”输出输出 0 x 2x 4x 6x2NW0NW11 1x 3x 5x 7x2NW0NW113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X10NW10NW10NW10NW算法流程图另一种时间抽选FFT2022-3-6数字信号处理 陈鹏 329934017频率抽取频率抽取基基2 FFT算法算法2022-3-6数字信号处理 陈鹏 329934018频率抽取频率抽取基基2 FFT算法算法下面介绍频率抽选基下面介绍频率抽选基2FFT算法。这种算法简称为频率抽算法。这种算法简称为频率抽取取FFT算法。它的推导过程

16、遵循以下两条规则：算法。它的推导过程遵循以下两条规则：(1) 对时对时间进行前后分解间进行前后分解；(2) 对频率进行奇偶分解对频率进行奇偶分解。设设 ，M 为正整数。为了推导方便，取为正整数。为了推导方便，取 ，即离散时间信号为即离散时间信号为kNWMN2823N 7,6,5,4,3,2,1,0 xxxxxxxxnx2022-3-6数字信号处理 陈鹏 329934019频率抽取频率抽取基基2 FFT算法算法按照规则按照规则(1)，将序列，将序列 分为前一半和后一半，即分为前一半和后一半，即这样这样 7,6,5,43,2,1,0 xxxxxxxx nxDFT式子不是注意这个 12/012/01

17、2/012/0212/012/12/01021212NnknNkNnknNkNnknNNnknNNkNNnknNNNnknNNnknNNnnkNWNnxnxWNnxWnxWNnxWWnxWnxWnxWnxkX2022-3-6数字信号处理 陈鹏 329934020频率抽取频率抽取基基2 FFT算法算法NjNeW2 /2 1220/2 1/20(2)0 ,2 ,4 ,61 ,3 ,5 ,7221212 ,0,1,2,12221Nrn rNnNnrNnX kX kXXXXXXXXXrXrNXrx nx nWNNx nx nWrXrx n 按照规则，将按奇偶分，即如果用和分别表示频率的偶数项和奇数项，

18、则有 /2 121210/2 1/2012 ,0,1,2,122NrnrNnNnnrNNnNx nWNNx nx nW Wr 2022-3-6数字信号处理 陈鹏 329934021频率抽取频率抽取基基2 FFT算法算法NjNeW2 /2 1/20/2 1/202 ,0,1,2,1222 ,0,1,2,1221DFT2NrnNnNnrnNNnNg nx nx nNnNh nx nx nXrg n WNnXrh n WWN令得到上两式所表示的是点的。在实际计算中， ,DFT2DFTnnNNg nh nNh n Wg nh n W首先形成序列和然后计算最后计算和的点的，便得到偶数输出点和奇数输出点的

19、。计算流程图如下图所示。2022-3-6数字信号处理 陈鹏 329934022频率抽取频率抽取基基2 FFT算法算法1111DFT2点NDFT2点N 0 x 2x 4x 6x 1x 3x 5x 7x 0X 4X 2X 6X 7X 1X 5X 3X3NW2NW1NW0NW)8(DFT2/DFTNNN计算的频率抽选流程图点的分解成两个点2022-3-6数字信号处理 陈鹏 329934023频率抽取频率抽取基基2 FFT算法算法 14/02/12/4/2/42/14/02/12/4/2/14/02/41 4 DFT4/DFT2/DFT2/2/2NnknNkNNnknNkNNNnknNNNnknNNn

20、knNWNngngWNngWWngWngWngkGngNNNNN分为前后两组，得到将：来求得。推导过程如下点的成两个可以分解点的数组，也就是将输出再分为偶数组和奇的点仍是偶数，可以将的整数幂，所以是由于2022-3-6数字信号处理 陈鹏 329934024频率抽取频率抽取基基2 FFT算法算法NjNeW2 的流程图。点的个继续分解成的将两个。这样可得到下图所示点的是上面式子表示的计算都通过类似的推导可得率的偶数项为再进行奇偶分，则得频对频率DFT44DFTDFT214, 2 , 1 , 0,41214, 2 , 1 , 0,4214, 2 , 1 , 0,41214, 2 , 1 , 0,42

21、14/04/24N14/04/4N14/04/214/04/N/N/NrWWWNnhWnhrHNrWWNnhWnhrHNrWWNngngrGNrWNngngrGkXNnrnNnNnNnNNnrnNnNnNNnrnNnNNnrnN2022-3-6数字信号处理 陈鹏 329934025频率抽取频率抽取基基2 FFT算法算法11111111DFT4点N 0 x 2x 4x 6x 1x 3x 5x 7x 0X 2X 4X 6X 7X 1X 3X 5X3NW2NW1NW0NWDFT4点NDFT4点NDFT4点N0NW2NW0NW2NW)8(DFT4/DFTNNN的频率抽选点的经两次分解成四个点2022-

22、3-6数字信号处理 陈鹏 329934026频率抽取频率抽取基基2 FFT算法算法流程图两点DFT形单元有所不同。单元与时间抽选中的蝶运算，但是这里的蝶形图的基本运算也是蝶形流程算法一样，下图所示的与时间抽选的流程图如下图所示。点的完整的流程图代入上图就得到示，将所有两点如右图所的，不能再分解了，两点的就是两点点的，所以上图中因为FFTFFT8DFTDFTDFTDFT4/8NN 0X 4X10NW与时间抽选一样，频率抽选与时间抽选一样，频率抽选FFT算法也算法也具有同址计算的优点具有同址计算的优点。但是，。但是，与时间抽选不同的是，频率抽选与时间抽选不同的是，频率抽选FFT算法的信号算法的信号

23、输入为正序输入为正序排列，输排列，输出为码位倒置排列，因此，出为码位倒置排列，因此，输出要进行变址计算输出要进行变址计算。2022-3-6数字信号处理 陈鹏 329934027蝶形单元对比 pXm qXm1kNW pXm 1 qXm 110NW pXm qXm pXm 1 qXm 1时间抽取的方法时间抽取的方法频率抽取的方法频率抽取的方法2022-3-6数字信号处理 陈鹏 329934028频率抽取频率抽取基基2 FFT算法算法11111111 0 x 2x 4x 6x 1x 3x 5x 7x 0X 4X 2X 6X 7X 1X 5X 3X3NW2NW1NW0NW0NW2NW0NW2NW0NW

24、0NW0NW0NW1111)8(FFTN流程图频率抽选的2022-3-6数字信号处理 陈鹏 329934029频率抽取频率抽取基基2 FFT算法算法元频率抽选的堞形运算单 rNmmmmmmWqXpXqXqXpXpX11 FFT流程图，满足以下关系算法的一般化的右图所示的是频率抽选的计算量是一样的。选的算法的计算量与时间抽频率抽选的复数加法次数：，复数乘法次数：量为个蝶形。因此，总计算级迭代运算，每级有共有个流程图次复数加法。图示的整次复数乘法和括显然，一个堞形计算包FFTFFTlog log2 2log 2 1 222NNNNNNFF10NW pXm qXm pXm 1 qXm 12022-3-6数字信号处理 陈鹏 329934030IFFT的计算的计算FFT算法同样可以用于算法同样可以用于IDFT的计算，称为的计算，称为快速傅里叶反变换快速傅里叶反变换，简写为，简