快速傅里叶变换(FFT)

1、第4章快速傅立叶变换(FFT)，4.1简介基于4.2的2FFT算法4.3操作量进一步减少的措施4.4分割本机FFT算法4.5离散hartter transform(DHT)，4.1简介，DFT是信号分析和处理中的重要转换。DFT根据转换间隔长度n的平方直接计算，如果n大，则计算太大，因此在发生快速傅立叶变换(FFT)之前，使用DFT算法对频谱分析和信号的实时处理不切实际。直到1965年Cooley和Tukey发现DFT的快速算法后，才发生根本性的变化。基于4.2的2FFT算法，4.2.1直接DFT的特征，以及减少运算量的基本路径长度为N的有限长序列x(n)的DFT，以考虑x(n)为多个序列的典

2、型情况，对其中一个k值计算直接X(k)值为(4.2.1)，(因此，N点DFT的乘数为N2，加数为N(N-1)。N1点，即n点DFT的乘法和加法次数与N2成正比，如果n大，则运算量相当。(4.2.1)，注意：通常使用算术乘法和算术加法的数量作为计算复杂性的度量。因为这个方法使用起来很简单。在计算机上使用软件实现这些算法时，乘法和加法的次数与计算速度直接相关。但是，在常用VLSI实现中，芯片的面积和功率要求是最重要的考虑因素，并且可能与算法的计算次数没有直接关系。显然，将n点DFT分解为几个较短的DFT可以大大减少乘法次数。此外，旋转系数WmN具有明显的周期性、对称性和可约性。周期性为(4.2.2

3、)，对称性为(4.2.2时间区域提取方法2 FFT基本原理FFT算法基本上是时间区域提取方法FFT(Decimation In Time FFT，简称DIT-FFT)和频域提取方法FFT(Decimation In ffft)DIT-FFT算法如下：如果序列x(n)的长度为N，满足，自然数，x(n)作为N的奇偶校验分解为两个N/2点的子序列，则x(n)的DFT为x (n)的DFT，因此X1(k)和X2(k) 分解后的多重乘法和多重加法计算：复数乘法：复数加法：1分解后的操作数几乎减半，因此可以进一步分解N/2点DFT。图4.2.2 N点DFT的时域提取分解图(N=8)，与第一次分解一样，将x1

4、(r)分解为两个N/4长度子序列x3(l)和x4(l)，即X1(k)(4.2.11)。其中，图4.2.3 N点DFT的第二时间区域提取分解图(N=8)、图4.2.4 N点dit-FFT运算流程图(N=8)、4.2.3 DIT-FFT算法和直接计算DFT运算量的比较流程图分别为N/每个级别操作需要N/2多个乘法和N个复数加法(每个正切需要两个复数加法)。因此，m级操作所需的复数乘法总数为，复数加法为。例如，在N=210=1024的情况下，图4.2.5 FFT算法和直接计算DFT所需乘法次数的比较曲线MATLAB提供了计算矢量x的DFT的FFT函数。通过调用X=fft(x，N)计算N点的DFT。如

5、果向量x的长度小于n，则x会补0。如果省略n，则DFT的长度为x的长度。x为矩阵时，fft(x，N)计算x每列的N点的DFT。Fft是用机器语言编写的，运行速度快。如果n是2的幂，则使用基本2 FFT算法；否则，将n分解为几个素元素，并使用慢基于混合的FFT算法。如果n是小数，FFT算法将被原始DFT算法淘汰。4.2.4 DIT-FFT的计算规则和编程思想1。in situ计算1)在图4.2.4中，您可以看到dit-FFT的计算过程非常规则。N=2M点FFT执行m级操作，每个级由N/2蝴蝶操作组成。(2)在同一级别，每个蝴蝶形状的两个输入数据对于仅计算原始折叠很有用，每个蝴蝶形状的输入、输出数

6、据节点位于同一水平线。也就是说，一旦计算出一只蝴蝶，结果数据可以立即存储在原始输入数据占用的存储设备上。3) m级操作后，X(k)的n个值将按顺序存储在存储原始输入序列数据的n个存储单元中。使用相同的存储设备存储蝴蝶计算输入和输出数据的这种方法称为位置计算，可以大大节省内存。2.旋转系数的变化规律在N点DIT-FFT运算流程图中，如上所述，每个级别的N/2折叠。每个折痕乘以系数WpN，然后将其称为旋转系数，p称为旋转系数指数，观察图4.2.4很容易看出级别l共有2L-1个不同的旋转系数。如果N=23=8，则每个标高的旋转系数表示为：L=1时，L=2时，L=3时，N=2M时，层L的旋转系数为(4

7、.2.12)，(4.2.13)，(4.2.13)，3。序列的逆序DIT-FFT算法的输入序列的排序看起来很乱，但是仔细分析的话，这种逆序看起来很有规律。N=2M，因此顺序数是m位二进制数(nm-1 nm-2.n 1n0)。图4.2.7形成逆序的树视图(N=23)，表4.2.1顺序和逆序二进制比较表，4.2.5频域提取方法FFT(DIF-FFT)默认2快速算法中，频域提取方法FFT也是常用的快速算法DIF-FFT。如果将序列x(n)的长度设置为N=2M，并将x(n)前后除以一半，则DFT可能以如下形式出现：将X(k)分解为偶数和奇数数组，k为偶数(k=2r，r=0，1，n/2-1)，则(4.2.

8、14)，x1 (n)，k为奇数(k=2r1，r=0，1，如果取n/2-1)，将(4.2.15)、X1(n)和x2(n)分别替换为(4.2.14)和(4.2.15)格式，则(4.2.16)比较DFT和IDFT的计算公式：将DFT表达式中的系数更改为，最后乘以，这是IDFT的计算公式。因此，在上述DIT-FFT和DIF-FFT算法中，可以通过更改旋转系数并将其乘以最终输出来计算IDFT。如果要直接调用FFT子例程来计算IFFT，可以使用以下方法：也就是说，从下而上两边同时取和，4.3.2实际序列的FFT算法1。将x(n)设定为n点实际序列。X(n)的偶数点和奇数点分别用作新构造序列y(n)的实际部分和虚拟部分。也就是说，y(n)的N/2点FFT，输出Y(k)根据DIT-FFT的想法和样式