快速傅里叶变换(FFT).ppt

1、本章的主要内容是介绍进一步降低基数-2FFT算法计算复杂度的措施。第四章，快速傅立叶变换，离散傅立叶变换是信号分析和处理中的一种重要变换。然而，离散傅立叶变换的计算量与变换区间长度n的平方成正比，当n较大时，计算量太大，直接用离散傅立叶变换算法进行频谱分析和实时信号处理是不切实际的。1965年，一种快速的离散傅立叶变换算法被发现，它将离散傅立叶变换的运算效率提高了12个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件，促进了数字处理技术的发展。1984年，提出了分裂基的快速算法，进一步提高了运算效率；4.1引言，4.2.1离散傅立叶变换直接计算的特点和减少计算量的基本方法：2 .减

2、少计算量的思路和方法：离散傅立叶变换在N点的复数乘法次数等于N2。将N点离散傅立叶变换分解成几个更短的离散傅立叶变换可以大大减少乘法次数。此外，旋转因子WmN具有周期性和对称性。基于4.2的2FFT算法，考虑到x(n)是一个复数序列的一般情况，对于k的某个值，它需要N次复数乘法和(N-1)次复数加法来直接根据上述公式计算X(k)的值。方法：将n分解成较小的值：将序列分解成几个较短的序列，分别计算它们的离散傅立叶变换值，这样可以大大减少乘法次数；利用旋转因子WNk的周期性和对称性进行合并和分类，以减少离散傅立叶变换运算的次数。周期性：对称性：3。快速傅立叶变换算法不断地将长序列的离散傅立叶变换分

3、解成若干短序列的离散傅立叶变换，并利用旋转因子的周期性和对称性减少离散傅立叶变换的运算次数。4.2基2FFT算法，4.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两类：时域抽取FFT(简称DIT-FFT)和频域抽取FFT(简称DIFFFT)。1.时域抽取FFT的算法思想是：根据n是奇数还是偶数，将序列x(n)分成两组：x1(n)和x2(n );两个N/2点离散傅立叶变换用于完成一个N点离散傅立叶变换的计算。假设序列x(n)的长度为N，并满足以下要求：(1)根据N的奇偶性，将x(n)分解为N/2个点的两个子序列，4.2是基于2FFT算法的自然数，以及(2)序列x(n)的N点DFT x

4、(k)由N/2个点X1(k)表示，X2(k) X1(k)和X2(k)都以N/2为循环，x (k)可以表示为：上述公式的运算由下图所示的流程图符号表示，即基于4.2的2FFT算法，该算法将N点离散傅立叶变换分解为两个N/2点离散傅立叶变换，并通过一次复数乘法和两次复数加法运算完成一次蝶形运算。经过一次分解后，复数乘法和复数加法的次数为2(N/2)2 N/2和N2/N2/2，4.2基2FFT算法，DIT-2FFT(时域抽取图)，N=8点，和(3)第二次分解：x1(r)可以分解成两个子序列x3，长度为N/4，根据r取奇数和偶数4.2基2FFT算法，n=8点离散傅立叶变换的二次时域提取分解图，k=0，

5、1，n/4-1；再分解一次，对于N=8的点，可以分解三次。4.2基2快速傅立叶变换算法，4.2基2快速傅立叶变换算法，4.2.3双离散傅立叶变换算法与直接计算离散傅立叶变换运算1的比较。直接离散傅立叶变换运算N点运算：复数乘法次数：神经网络复数加法次数：N(N-1) 2。双二阶快速傅立叶变换的N点运算：复数乘法次数：Mn/2=N/2对数2n；重复次数：2 N/2M=Nlog2N。可以看出，快速傅立叶变换大大减少了运算次数，提高了运算速度。基于4.2的2FFT算法，整个运算流程图中有M级蝴蝶，每个运算流程图中有N/2个蝴蝶，每个蝴蝶需要一个复数乘法和两个复数加法运算。4.2.4快速傅立叶变换1的

6、运算规则和编程思想。现场计算快速傅立叶变换与N=2M点，有M蝴蝶操作，每一阶段有N/2蝴蝶操作。在同一个阶段，每个蝴蝶的两个输入数据只对这个蝴蝶有用在M级操作之后，X(k)的N个值可以存储在最初存储输入序列数据的N个存储单元中。原位计算：一种使用同一存储单元存储蝴蝶计算的输入和输出数据的方法。优点：节省存储空间，降低设备成本。4.2基数-2快速傅立叶变换算法，2。旋转因子的变化规律在N点快速傅立叶变换操作流程图中，每个蝴蝶都乘以旋转因子WpN，P称为旋转因子的指数。在N8 23，每个阶段的第一旋转因子：L=1，其中一个旋转因子：Wnp=WN/4J=W2LJ=0；第二个：L=2，有两个旋转因子：

7、wnp=wn/2j=w2ljj=0；第三级：L=3，有四个旋转因子：wnp第一级有2L-1个不同的旋转因子：Wnp=w2ljj=0，1，2，2l-112l=2m2m=n2lm。因此，第一阶段操作的旋转因子可以根据上述两个公式来确定。4.2基数-2FFT算法，p=J2M-1，j=0，1，2，2L-11，3，在同一阶段，相同的旋转因子对应于蝴蝶的数量，而相同的旋转因子用于2M-1蝴蝶；4.在同一阶段，蝶式操作使用相同旋转因子之间的“距离”。在第一阶段，蝴蝶距离：D=2L。5.同一个蝶形运算的两个输入数据之间的距离在具有反相输入序列和原始输出序列的快速傅立叶变换中，第一级中每个蝶形运算的两个输入数据

8、之间的距离是B=2L-1。6.在具有码位反转的输入序列x(n)被M级时域奇、偶选择之后，输出序列X(k)和输入序列之间的顺序关系被反转。4.2基础2快速傅立叶变换算法，7。蝶形运算的规则序列在时域中被选择并存储在阵列中。如果蝶式运算的两个输入数据被B点分开，则蝶式运算可以通过原位计算以下列形式表示：4.2基2FFT算法，8。根据快速傅立叶变换的原理和过程，快速傅立叶变换的完整程序框图包括以下几个部分：(1)逆序30。(2)循环层1:确定操作的数量，l=1m(n=2m)；确定一只蝴蝶和两个输入数据b=2l-1之间的距离。(3)环路层2:确定l级(B=)2L-1旋转因子。旋转因子指数p=2M-LJ

9、，j=0 B- 1；(4)循环层3:用于相同旋转因子的相同级别的2M-L蝴蝶运算：k的值范围从j到N-1，步长为2L(使用相同旋转因子的蝴蝶之间的距离)。(5)完成蝴蝶操作。4.2基数-2快速傅立叶变换算法，9。反向序列N=2M，序列号由m位二进制数(nM-1nM-2n1n0)2表示。m次奇偶时域采样的过程如下：最低位按0和1分为偶数和奇数组，下一个低位也按0和1分组，依此类推，m次分解后形成反图如下：(n2n1n0)2，思考问题：假设N=16点，在DIT-FFT运算中，序数为2的二进制数被反相后是多少？基于4.2的2FFT算法，序列号增加1，其被携带到序列号的二进制数的最低位的左边，并且被携

10、带到m位的二进制数的最高位的右边，(0010-0100)，序列和反转的二进制数的比较表，N=2M，由m位的二进制数表示， 然后是从左到右的十进制权重。倒序数在计算机上的实现过程如下：基于4.2的2FFT算法，倒序数的十进制运算规则，倒序框图，以实现原位运算，节省存储空间，提高运算速度。 在倒序数j形成之后，存储在原始存储器中的输入序列需要重新排列。下面首先分析N=8点的逆序定律。4.2基2FFT算法、输入序列和数组，分析上图中N=8点的逆序规律，顺序号I和逆序号J之间存在关系：当I=J时，不交换；不要交换，直接更新订单值；I，J，x(0)，x(2)，x(5)，x(7)，计算倒数值，交换数组中的

11、数据，不交换数据，避免交换一对之前交换过的数据，再计算下一个倒数值。4.2.5频域抽取快速傅立叶变换在基2的快速算法中，频域抽取快速傅立叶变换也是一种常见的快速算法。1.算法思想和操作过程：让序列x(n)的长度为N=2M，将序列x(n)分成两组：x1(n)和x2(n)，用两个N/2点离散傅立叶变换计算一个N点离散傅立叶变换。4.2基2FFT算法，N，4.2基2FFT算法，将X(k)分解为偶数组和奇数组，当k为偶数(k=2r，r=0，1，n/2-1)时，当k为奇数(k=2r1，r=0，1，n/2-1)时，X(k)可以根据奇、偶k值分成两组，的偶数组为x1(n)的N/2 DFT，奇数组为N 输入序

12、列x1(n)和x2(n)根据前后方向被分成长度为N/4的四个子序列，它们的n=0，1，N/4-1，4.2是基于2FFT算法的。 经过三次分解，得到的DIFFFT运算流程图(N=8)是：基于4.2的2FFT算法，2，2，3，3，3，3，3，3，3，3，3，3，3，3，3，3当N=2M时，有m个运算阶段，每个阶段有N/2个蝴蝶，DIT和DIF算法有相同的运算次数。DIT与DIF的不同之处在于，DIT快速傅立叶变换算法的输入序列是自然序列，输出序列是逆序列。因此，在M级运算完成之后，输出数据需要被反转，以便以自然顺序得到X(k)。蝶形运算符号不同：先相乘，再相加/相减；DIF-快速傅立叶变换蝶形运算

13、首先被加/减，然后被相乘。3、其它形式的快速傅立叶变换运算流程图通过改变输入输出节点和中间节点的排列顺序，可以得到不同变形的快速傅立叶变换运算流程图。因此，上面介绍的快速傅立叶变换和DIF快速傅立叶变换的操作流程图并不是唯一的。基于4.2的快速傅立叶变换算法，通过同样的方法可以得到快速傅立叶变换的另一种变型操作流程图，输入和输出按顺序排列，但不能使用原位计算。基于4.2的2快速傅立叶变换算法，4.2.6 IDFT高效算法的一种变型操作流程图1快速傅立叶变换与IDFT公式的比较上述快速傅立叶变换算法流程图也可用于IDFT逆离散傅立叶变换。根据运算公式可以看出，只需将离散傅立叶变换的系数WNkn改

14、为WN-kn，最后的结果乘以1/N，即为IDFT的运算公式。在第四章中，快速傅里叶变换(FFT)，X(k)，n，2，IDFT快速算法是通过FFT流程图实现的。将双离散傅立叶变换或DIF-快速傅立叶变换蝶形运算流程图中的旋转因子WNp改为WN-p，在输出IDFT快速算法的最终结果之前乘以1/N常数；为了防止溢出，在每一级运算中，输出分支可以乘以1/2，从而实现系数的分级共享。在IDFT快速算法中，输入序列是X(k)，而输出序列是x(n)。节点对应：DIF-IFFT对应DIF-IFFT对应DIF-IFFT，第4章快速傅里叶变换，快速傅里叶变换运算流程图，第4章快速傅里叶变换，快速傅里叶变换运算流程图(防止溢