快速傅里叶变换FFT原理与实现
FFT原理与实现
2010-10-07 21:10:09| 分类：数字信号处理 | 标签：fft dft |举报|字号订阅
在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。
DFT计算公式
本文不加推导地直接给出DFT的计算公式：
其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取连续的N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N 截至的N个频率点的相对幅度。
N点DFT的计算量
根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。
旋转因子WN的特性
1.WN的对称性
2.WN的周期性
3.WN的可约性
根据以上这些性质，我们可以得到式(5)的一系列有用结果
基-2 FFT算法推导
假设采样序列点数为N=2^L，L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下：
于是根据DFT计算公式(1)有：
至此，我们将一个N点的DFT转化为了式(7)的形式，此时k的取值为0到N-1,现在分为两段来讨论，当k为0～N/2-1的时候，因为x1(r)，x2(r)为N/2点的序列，因此，此时式(7)可以写为：
而当k取值为N/2~N-1时，k用k’+N/2取代，k’取值为0~N/2-1。对式(7)化简可得：
综合以上推导我们可以得到如下结论：一个N点的DFT变换过程可以用两个N/2点的DFT变换过程来表示，其具体公式如式(10)所示DFT快速算法的迭代公式：
上式中X'(k’)为偶数项分支的离散傅立叶变换，X''(k’’)为奇数项分支的离散傅立叶变换。式(10)的计算过程可以用图1的蝶形算法流图直观地表示出来。
图1 时间抽取法
蝶形运算流图
在图1中，输入为两个N/2点的DFT输出为一个N点的DFT结果，输入输出点数一致。运用这种表示方法，8点的DFT可以用图2来表示：
图2 8点DFT的4点分解
根据公式(10)，一个N点的DFT可以由两个N/2点的DFT运算构成，再结合图1的蝶形信号流图可以得到图2的8点DFT的第一次分解。该分解可以用以下几个步骤来描述：
1.将N点的输入序列按奇偶分为2组分别为N/2点的序列
2.分别对1中的每组序列进行DFT变换得到两组点数为N/2的DFT变换值X1和X2
3.按照蝶形信号流图将2的结果组合为一个N点的DFT变换结果
根据式(10)我们可以对图2中的4点DFT进一步分解，得到图3的结果，分解步骤和前面一致。
图3 8点DFT的2点分解
最后对2点DFT进一步分解得到最终的8点FFT信号计算流图：
图4 8点DFT的全分解
从图2到图4的过程中关于旋转系数的变化规律需要说明一下。看起来似乎向前推一级，在奇数分组部分的旋转系数因子增量似乎就要变大，其实不是这样。事实上奇数分组部分的旋转因子指数每次增量固定为1，只是因为每向前推进一次，该分组序列的数据个数变少了，为了统一使用以原数据N为基的旋转因子就进行了变换导致的。每一次分组奇数部分的系数WN,这里的N均为本次分组前的序列点数。以上边的8点DFT为例，第一次分组N=8,第二次分组N为4，为了统一根据式(4)进行了变换将N变为了8，但指数相应的需要乘以2。
N点基-2 FFT算法的计算量
从图4可以看到N点DFT的FFT变换可以转为log2(N)级级联的蝶形运算，每一级均包含有N/2次蝶形计算。而每一个蝶形运算包含了1次复数乘法，2次复数加法。因此N点FFT计算的总计算量为：复数乘法——N/2×log2(N) 复数加法——N×log2(N)。假设被采样的序列为实数序列，那么也只有第一级的计算为实数与复数的混合计算，经过一次迭代后来的计算均变为复数计算，在这一点
上和直接的DFT计算不一致。因此对于输入序列是复数还是实数对FFT算法的效率影响较小。一次复数乘法包含了4次实数乘法，2次实数加法，一次复数加法包含了2次复数加法。因此对于N点的FFT计算需要总共的实数乘法数量为：2×N×log2(N)；总的复数加法次数为：2xNxlog2(N)。
N点基-2 FFT算法的实现方法
从图4我们可以总结出对于点数为N=2^L的DFT快速计算方法的流程：
1.对于输入数据序列进行倒位序变换。
该变换的目的是使输出能够得到X(0)~X(N-1)的顺序序列，同样以8点DFT为例，该变换将顺序输入序列x(0)~x(7)变为如图4的
x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)序列。其实现方法是：假设顺序输入序列一次村在A(0)~A(N-1)的数组元素中，首先我们将数组下标进行二进制化(例：对于点数为8的序列只需要LOG2(8) = 3位二进制序列表示，序号6就表示为110)。二进制化以后就是将二进制序列进行倒位，倒位的过程就是将原序列从右到左书写一次构成新的序列，例如序号为6的二进制表示为110，倒位后变为了011，即使十进制的3。第三步就是将倒位前和倒位后的序号对应的数据互换。依然以序号6为例，其互换过程如下：
temp = A(6); A(6) = A(3); A(3) = A(6);
实际上考虑到执行效率，如果对于每一次输入的数据都需要这个处理过程是非常浪费时间的。我们可以采用指向指针的指针来实现该过程，或者是采用指针数组来实现该过程。
2.蝶形运算的循环结构。
从图4中我们可以看到对于点数为N = 2^L的fft运算，可以分解为L阶蝶形图级联，每一阶蝶形图内又分为M个蝶形组，每个蝶形组内包含K个蝶形。根据这一点我们就可以构造三阶循环来实现蝶形运算。编程过程需要注意旋转因子与蝶形阶数和蝶形分组内的蝶形个数存在关联。
3.浮点到定点转换需要注意的关键问题
上边的分析都是基于浮点运算来得到的结论，事实上大多数嵌入式系统对浮点运算支持甚微，因此在嵌入式系统中进行离散傅里叶变换一般都应该采用定点方式。
对于简单的DFT运算从浮点到定点显得非常容易。根据式(1)，假设输入x(n)是经过AD采样的数字序列，AD位数为12位，则输入信号范围为0~4096。为了进行定点运算我们将旋转因子实部虚部同时扩大2^12倍，取整数部分代表旋转因子。之后，我们可以按照(1)式计算，得到的结果与原结果成比例关系，新的
结果比原结果的2^12倍。但是，对于使用蝶形运算的fft我们不能采用这种简单的放大旋转因子转为整数计算的方式。因为fft是一个非对称迭代过程，假设我
们对旋转因子进行了放大，根据蝶形流图我们可以发现其最终的结果是，不同的输入被放大了不同的倍数，对于第一个输入x(0)永远也不会放大。举一个更加形象的例子，还是以图4为例。从图中可以看出右侧的X(0)可以直接用下式表示：
从上式我们可以看到不同输入项所乘的旋转因子个数(注意这里是个数，就算是wn^0，也被考虑进去了，因为在没有放大时wn^0等于1，放大后所有旋转因子指数模均不为1，因此需要考虑)。这就导致输入不平衡，运算结果不正确。经
查阅相关资料，比较妥善的做法是，首先对所有旋转因子都放大2^Q倍，Q必
须要大于等于L，以保证不同旋转因子的差异化。旋转因子放大，为了保证其模为1，在每一次蝶形运算的乘积运算中我们需要将结果右移Q位来抵消这个放大，从而得到正确的结果。之所以采用放大倍数必须是2的整数次幂的原因也在于此，我们之后可以通过简单的右移位运算将之前的放大抵消，而右移位又代替了除法运算，大大节省了时间。
4.计算过程中的溢出问题
最后需要注意的一个问题就是计算过程中的溢出问题。在实际应用中，AD虽然有12位的位宽，但是采样得到的信号可能较小，例如可能在0~8之间波动，也就是说实际可能只有3位的情况。这种情况下为了在计算过程中不丢失信息，一般都需要先将输入数据左移P位进行放大处理，数据放大可能会导致溢出，从
而使计算错误，而溢出的极限情况是这样：假设我们数据位宽为D位(不包括符号位)，AD采样位数B位，数字放大倍数P位，旋转因此放大倍数Q位，FFT
级联运算带来的最大累加倍数L位。我们得到:
假设AD位宽12，数据位宽32，符号位1位，因此有效位宽31位，采样点数N，那么我们可以得到log2(N)+P+Q<=19,假设点数128,又Q>=L可以得到放大
倍数P<=5。
FFT代码示例
根据以上的分析，我整理了一份128点的FFT代码如下，该代码在keil中仿真
运行，未发现问题。
#define N 128 #define POWER 6//该值代表了输入数据首先
被放大的倍数，放大倍数为2^POWER #define P_COEF 8//该值代表了旋转
因子被放大的倍数，放大倍数为2^POWER #if (N == 4) #define L
2//L的定义满足L = log2(N) #elif (N == 8) #define L 3//L的
定义满足L = log2(N) #elif (N == 16) #define L 4//L的定义满
足L = log2(N) #elif (N == 32) #define L 5//L的定义满足L = log2(N) #elif (N == 64) #define L 6//L的定义满足L = log2(N)
#elif (N == 128) #define L 7//L的定义满足L = log2(N) #endif //AD采样位数为12位，本可以采用s16 x[N]定义数据空间，但是为了节省存储
空间，fft结果也将存储在该变量空间。由于受//fft影响变量需要重新定义，定义的方式及具体原因如下：//fft过程会乘以较大旋转因子，因此需要32位
定义//fft过程会产生负数，因此需要有符号定义//fft过程会出现复数，因
此需要定义二维数组，[][0]存放实部，[][1]存放虚部 s32 x[N][2] = {}; //
定义*p[N]是为了在第一次指针初始化以后，该数组指针按照位倒序指向数据变
量x//p[i][0]代表了指向数据的实部，p[i][1]代表了指向数据的虚部 s32
*p[N]; //定义旋转因子矩阵//旋转因子矩阵存储了
wn^0,wn^1,wn^2...wn^(N/2-1)这N/2个复数旋转因子 s16 w[N>>1][2] = {256,0,256,-13,255,-25,253,-38,251,-50,248,-62,245,-74,241,-86,237,-9 8,231,-109,226,
-121,220,-132,213,-142,206,-152,198,-162,190,-172,1 81,-181,172,-190,162,-198,152,
-206,142,-213,132,-220,121,-226,109,-231,98,-237,86
,-241,74,-245,62,-248,50,-251,38,
-253,25,-255,13,-256,0,-256,-13,-256,-25,-255,-38,-253,-50,-251,-62,-248,-74,-245,-86,
-241,-98,-237,-109,-231,-121,-226,-132,-220,-142,-2
13,-152,-206,-162,-198,-172,-190,-181,
-181,-190,-172,-198,-162,-206,-152,-213,-142,-220,-
132,-226,-121,-231,-109,-237,-98,-241,
-86,-245,-74,-248,-62,-251,-50,-253,-38,-255,-25,-2
56,-13}; void init_pointer(void) { unsigned char i = 0;
unsigned char j = 0; unsigned char k = 0; for(i = 0; i < N; i++)
{ j = 0; for(k = 0; k < L; k++) { j |= (((i >>
k)&0x01)<<(L-k-1)); } p[i] = &x[j][0]; } } /*
*description:基2fft主函数,该函数将借助指针数组p对全局变量数组x进行
fft计算 * 并将结果存储在数组x中 *global var:rw->x; r->p,w。
(r表示读，w表示写，rw表示读写) */void fft2(void) { u8 i;//i用于表
示蝶形图级联的阶数 u8 j;//表示蝶形分组起始点序列，蝶形分组跨度为2^i
u8 k;//k表示蝶形组内偶数分支序列点号 u8 gp_distance = 1;//蝶形分组
跨度 u8 temp;//temp用于记录当前组间距离的一半,同时也表示了同一碟形
两分支间的距离 u8 gp_hf = 0;//记录当前组的中间点序号 u8 delta = N;//
旋转因子下标增量，本来下标初始值应该为N/2，但是。。 s16 *pw =
&(w[0][0]); int tp_result[2]; //用于临时存放旋转因子和奇数分
组的乘积//输入信号序列放大for(i = 0; i < N; i++) { x[i][0] <<= POWER; x[i][1] <<= POWER; } for(i = 0; i < L; i++) { temp
= gp_distance; gp_distance <<= 1; for(j = 0; j < N;
j+=gp_distance) { gp_hf = temp + j; pw = &(w[0][0]); for(k = j; k < gp_hf; k++)//完成一组内的所有蝶形运算 { //蝶形
运算中的一组复数乘法过程 tp_result[0] = pw[0] *
(p[k+temp][0]) - pw[1] * (p[k+temp][1]); tp_result[1] = pw[0]
* (p[k+temp][1]) + pw[1] * (p[k+temp][0]); tp_result[0] >>=
P_COEF; tp_result[1] >>= P_COEF; //蝶形运算中的
2组复数加法过程 p[k+temp][0] = p[k][0] - tp_result[0]; p[k+temp][1] = p[k][1] - tp_result[1]; p[k][0] +=
tp_result[0]; p[k][1] += tp_result[1];
pw += delta; } } delta >>= 1; } }
FFT超全快速傅里叶
快速傅里叶变换 FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外，FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。 虽然很多人都知道FFT是什么，可以用来做什么，怎么去做，但是却不知道FFT之后的结果是什意思、如何决定要使用多少点来做FFT。 现在圈圈就根据实际经验来说说FFT结果的具体物理意义。一个模拟信号，经过ADC采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍，这些我就不在此罗嗦了。 采样得到的数字信号，就可以做FFT变换了。N个采样点，经过FFT之后，就可以得到N个点的FFT结果。为了方便进行FFT运算，通常N取2的整数次方。 假设采样频率为Fs，信号频率F，采样点数为N。那么FFT之后结果就是一个为N点的复数。每一个点就对应着一个频率点。这个点的模值，就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢？假设原始信号的峰值为A，那么FFT的结果的每个点（除了第一个点直流分量之外）的模值就是A的N/2倍。而第一个点就是直流分量，它的模值就是直流分量的N倍。而每个点的相位呢，就是在该频率下的信号的相位。第一个表示直流分量（即0Hz），而最后一个点N的再下一个点（实际上这个点是不存在的，这里是假设的第N+1个点，也可以看做是将第一个点分做两半分，另一半移到最后）则表示 采样频率Fs，这中间被N-1个点平均分成N等份，每个点的频率依次增加。例如某点n所表示的频率为：Fn=(n-1)*Fs/N。由上面的公式可以看出，Fn所能分辨到频率为为Fs/N，如果采样频率Fs为1024Hz，采样点数为1024点，则可以分辨到1Hz。1024Hz的采样率采样1024点，刚好是1秒，也就是说，采样1秒时间的信号并做FFT，则结果可以分析到1Hz，如果采样2秒时间的信号并做FFT，则结果可以分析到0.5Hz。如果要提高
快速傅里叶变换(FFT)课程设计
快速傅里叶变换(FFT)的DSP 实现 (马灿明 计算机学院 计算机应用技术 2110605410) 摘要:本文对快速傅里叶变换(FFT)原理进行简单介绍后，然后介绍FFT 在TMS320C55xx 定 点DSP 上的实现，FFT 算法采用C 语言和汇编混合编程来实现，算法程序利用了CCS 对其结果进行了仿真。 关键字：FFT ，DSP ，比特反转 1.引言 傅里叶变换是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT ）是连续傅里叶变换在离散系统中的表现形式。由于DFT 的计算量很大，因此在很长一段时间内使其应用受到很大的限制。 20世纪60年代由Cooley 和Tukey 提出了快速傅里叶变换（FFT ）算法，它是快速计算DFT 的一种高效方法，可以明显地降低运算量，大大地提高DFT 的运算速度，从而使DFT 在实际中得到了广泛的应用，已成为数字信号处理最为重要的工具之一。 DSP 芯片的出现使FFT 的实现变得更加方便。由于多数的DSP 芯片都能在单指令周期内完成乘法—累加运算，而且还提供了专门的FFT 指令（如实现FFT 算法所必需的比特反转等），使得FFT 算法在DSP 芯片上实现的速度更快。本节首先简要介绍FFT 算法的基本原理，然后介绍FFT 算法的DSP 实现。 2.FFT 算法的简介 快速傅里叶变换（FFT ）是一种高效实现离散傅里叶变换（DFT ）的快速算法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理等领域有着广泛的应用。 2.1离散傅里叶变换DFT 对于长度为N 的有限长序列x(n)，它的离散傅里叶变换（DFT ）为 1,1,0, )()(1 0-==∑-=N k W n x k X n n nk N （1） 式中， N j N e W /2π-= ，称为旋转因子或蝶形因子。 从DFT 的定义可以看出，在x(n)为复数序列的情况下，对某个k 值，直接按（1） 式计算X(k) 只需要N 次复数乘法和（N-1）次复数加法。因此，对所有N 个k 值，共需要N 2 次复数乘法和N(N-1)次复数加法。对于一些相当大有N 值（如1024点）来说，直接计算它的DFT 所需要的计算量是很大的，因此DFT 运算的应用受到了很大的限制。 2.2快速傅里叶变换FFT 旋转因子W N 有如下的特性。 。对称性： 2/N k N k N W W +-= 。周期性： N k N k N W W += 利用这些特性，既可以使DFT 中有些项合并，减少了乘法积项，又可以将长序列的DFT
详解FFT(快速傅里叶变换FFT.
kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R N (k ) n =0 在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N 次复数乘法和 N －1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N ? 1) 次复数加法。即计算量是与 N 2 成正比的。 FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。 W N 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT 运算： （1） 周期性： ( k + N ) n N = W kn = W ( n + N ) k （2） 对称性：W ( k + N / 2 ) = ?W k N N 利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子： 求当 N ＝4 时，X(2)的值
fft快速傅里叶变换 c语言实现
#include 实验四 快速傅里叶变换（FFT ） 4.1实验目的 1）加深对快速傅里叶变换（FFT ）基本理论的理解； 2）了解使用快速傅里叶变换（FFT ）计算有限长序列和无限长序列信号频谱的方法； 3）掌握用MATLAB 语言进行快速傅里叶变换时常用的子函数。 4.2实验原理 1）用MATLAB 提供的子函数进行快速傅里叶变换 从理论学习可知，DFT 是唯一在时域和频域均为离散序列的变换方法，它适用于有限长序列。尽管这种变换方法是可以用于数值计算的，但如果只是简单的按照定义进行数据处理，当序列长度很大时，则将占用很大的内存空间，运算时间将很长。 快速傅里叶变换是用于DFT 运算的高效运算方法的统称，FFT 只是其中的一种。FFT 主要有时域抽取算法和频域抽取算法，基本思想是将一个长度为N 的序列分解成多个短序列，如基2算法、基4算法等，大大缩短了运算的时间。 MATLAB 中提供了进行快速傅里叶变换（FFT ）的子函数，用fft 计算DFT ，用ifft 计算IDFT 。 2）用FFT 计算有限长序列的频谱 基本概念： 一个序号从1n 到2n 的时域有限长序列()x n ，它的频谱()j X e ω定义为它的离散时间傅里叶变换，且在奈奎斯特（Nyquist ）频率范围内有界并连续。序列的长度为N ，则211N n n =?+。计算()x n 的离散傅里叶变换（DFT ）得到的是()j X e ω的N 个样本点()k j X e ω。其中数字频率为 k 2πω()d ωk k N == 式中：d ω为数字频率的分辨率；k 取对应－(N －1)/2到(N －1)/2区间的整数。 在实际使用中，往往要求计算出信号以模拟频率为横坐标的频谱，此时对应的模拟频率为 s s 2π2π?ω/T ()()T k k k k kD N L ==== 式中：D 为模拟频率的分辨率或频率间隔；T s 为采样信号的周期，Ts ＝1/Fs ；定义信号时域长度L ＝N T s 。 第一章 快速傅里叶变换（FFT ） 4.1 填空题 （1）如果序列)(n x 是一长度为64点的有限长序列)630(≤≤n ，序列)(n h 是一长度为128点 的有限长序列)1270 (≤≤n ，记)()()(n h n x n y *=（线性卷积），则)(n y 为 点的序列，如果 采用基FFT 2算法以快速卷积的方式实现线性卷积，则FFT 的点数至少为 点。 解：64+128-1＝191点; 256 (2)如果一台通用机算计的速度为：平均每次复乘需100s μ，每次复加需20s μ，今用来计算N=1024点的DFT )]([n x 。问直接运算需（ ）时间，用FFT 运算需要（ ）时间。 解：①直接运算：需复数乘法2 N 次，复数加法） （1-N N 次。 直接运算所用计算时间1T 为 s s N N N T 80864.12512580864020110021==?-+?=μ）（ ② 基2FFT 运算：需复数乘法 N N 2log 2 次，复数加法N N 2log 次。 用FFT 计算1024点DTF 所需计算时间2T 为 s s N N N N T 7168.071680020log 100log 2 222==?+?=μ。 (3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子k N j e π2-的 来减少计算量，其特点是 _______、_________和__________。 解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置 （4）N 点的FFT 的运算量为复乘 、复加 。 解：N N L N mF 2log 2 2== ；N N NL aF 2log == 4.2 选择题 1．在基2DIT —FFT 运算中通过不断地将长序列的DFT 分解成短序列的DFT ，最后达到2点DFT 来降低运算量。若有一个64点的序列进行基2DIT —FFT 运算，需要分解 次，方能完成运算。 A.32 B.6 C.16 D. 8 解：B 2．在基2 DIT —FFT 运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号点序号为8，则倒序后该信号点的序号为 。 A. 8 B. 16 C. 1 D. 4 解：C 3．在时域抽取FFT 运算中，要对输入信号x(n)的排列顺序进行“扰乱”。在16点FFT 中，原来x(9) 快速傅里叶变换(FFT)的原理及公式 原理及公式 非周期性连续时间信号x(t)的傅里叶变换可以表示为 式中计算出来的是信号x(t)的连续频谱。但是，在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。 有限长离散信号x(n)，n=0，1，…，N-1的DFT定义为： 可以看出，DFT需要计算大约N2次乘法和N2次加法。当N较大时，这个计算量是很大的。利用WN的对称性和周期性，将N点DFT分解为两个N／2点 的DFT，这样两个N／2点DFT总的计算量只是原来的一半，即(N／2)2+(N／2)2=N2／2，这样可以继续分解下去，将N／2再分解为N／4点DFT等。对于N=2m点的DFT都可以分解为2点的DFT，这样其计算量可以减少为(N／2)log2N 次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。 将x(n)分解为偶数与奇数的两个序列之和，即 x1(n)和x2(n)的长度都是N／2，x1(n)是偶数序列，x2(n)是奇数序列，则 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N／2点DFT。由于X1(k)和X2(k)均以N／2为周期，且WN k+N/2=-WN k，所以X(k)又可表示为： 上式的运算可以用图2表示，根据其形状称之为蝶形运算。依此类推，经过m-1次分解，最后将N点DFT分解为N／2个两点DFT。图3为8点FFT的分解流程。 FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。 关于FFT精度的说明： 因为这个变换采用了浮点运算，因此需要足够的精度，以使在出现舍入误差时，结果中的每个组成部分的准确整数值仍是可辨认的。为了FFT的舍入误差，应该允许增加几倍log2(log2N)位的二进制。以256为基数、长度为N字节的数 FFT原理与实现 2010-10-07 21:10:09| 分类：数字信号处理 | 标签：fft dft |举报|字号订阅 在数字信号处理中常常需要用到离散傅立叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长，不利于计算机实时对信号进行处理。因此至DFT被发现以来，在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法——FFT，被发现，离散傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。 DFT计算公式 本文不加推导地直接给出DFT的计算公式： 其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)为输入序列x(n)对应的N个离散频率点的相对幅度。一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度值实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取连续的N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N 截至的N个频率点的相对幅度。 N点DFT的计算量 根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计算N各点的X(k)共需要N^2次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*N^2次实数乘法，2*N*(N-1)次实数加法。 旋转因子WN的特性 1.WN的对称性 2.WN的周期性 3.WN的可约性 根据以上这些性质，我们可以得到式(5)的一系列有用结果 基-2 FFT算法推导 假设采样序列点数为N=2^L，L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下： 于是根据DFT计算公式(1)有： kn N W N N 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。 快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。 DFT 的定义式为 N ?1 X (k ) = ∑ x (n )W N R N (k ) n =0 在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N 次复数乘法和 N －1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N ? 1) 次复数加法。即计算量是与 N 2 成正比的。 FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。 W N 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT 运算： （1） 周期性： ( k + N ) n N = W kn = W ( n + N ) k （2） 对称性：W ( k + N / 2 ) = ?W k N N 利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子： 求当 N ＝4 时，X(2)的值 快速傅里叶变换的原理及其应用 摘要: 快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换. 虽然傅里叶运算在各方面计算中有着 重要的作用，但是它的计算过于复杂，大量的计算对于系统的运算负担过于庞大，使得一些对于耗电量少，运算速度慢的系统对其敬而远之，然而，快速傅里叶变换的产生，使得傅里叶变换大为简化，在不牺牲耗电量的条件下提高了系统的运算速度，增强了系统的综合能力，提高了运算速度，因此快速傅里叶变换在生产和生活中都有着非常重要的作用，对于学习掌握都有着非常大的意义。 关键词：快速傅氏变换；图像处理；matlab 前言： 傅里叶变换在信号处理中具有十分重要的作用，但是基于离散时间的傅里叶变换具有很大的时间复杂度，根据傅里叶变换理论，对一个有限长度且 长度为N的离散信号，做傅里叶变换的时间复杂度为) O，当N很大时τ， (2 N 其实现的时间是相当惊人的（比如当N为4 10 10时，其完成时间为τ8 (τ为计算机的时钟周期）），故其实现难度是相当大的，同时也严重制约了DFT在信号分析中的应用，故需要提出一种快速的且有效的算法来实 现。正是鉴于DFT极其复杂的时间复杂度，1965年..JWCooley 和..JWTukey巧妙地利用 NW因子的周期性和对称性，提出了一个DFT的快速算法，即快速傅里叶变换（FFT），从而使得DFT在信号处理中才得到真正的广泛应用。 傅立叶变化的原理； （1）原理 《测试信号分析及处理》课程作业 快速傅里叶变换 一、程序设计思路 快速傅里叶变换的目的是减少运算量，其用到的方法是分级进行运算。全部计算分解为M 级，其中N M 2log =；在输入序列()i x 中是按码位倒序排列的，输出序列()k X 是按顺序排列；每级包含2N 个蝶形单元，第i 级有i N 2 个群，每个群有12-i 个蝶形单元； 每个蝶形单元都包含乘r N W 和r N W -系数的运算，每个蝶形 单元数据的间隔为12-i ，i 为第i 级； 同一级中各个群的系数W 分布规律完全相同。 将输入序列()i x 按码位倒序排列时，用到的是倒序算法——雷德算法。 自然序排列的二进制数，其下面一个数总比上面的数大1，而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位仅为而得到的。 若已知某数的倒序数是J ，求下一个倒序数，应先判断J 的最高位是否为0，与2 N k =进行比较即可得到结果。如果J k >，说明最高位为0，应把其变成1，即2 N J +，这样就得到倒序数了。如果J k ≤，即J 的最高位为1，将最高位化为0，即2N J -，再判断次高位；与4N k =进行比较，若为0，将其变位1，即4 N J +，即得到倒序数，如果次高位为1，将其化为0，再判断下一位……即从高位到低位依次判断其是否为1，为1将其变位0，若这一位为0，将其变位1，即可得到倒序数。若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。 注：因为0的倒序数为0，所以可从1开始进行求解。 二、程序设计框图 （1）倒序算法——雷德算法流程图 (2)FFT算法流程 快速傅里叶变换FFT的C语言算法彻底研究LED音乐频谱显示的核心算法就是快速傅里叶变换，FFT的理解和编程还是比较难的，特地撰写此文分享一下研究成果。 一、彻底理解傅里叶变换 快速傅里叶变换（Fast Fourier Transform)是离散傅里叶变换的一种快速算法，简称FFT，通过FFT可以将一个信号从时域变换到频域。模拟信号经过A/D转换变为数字信号的过程称为采样。为保证采样后信号的频谱形状不失真，采样频率必须大于信号中最高频率成分的2倍，这称之为采样定理。假设采样频率为fs，采样点数为N，那么FFT结果就是一个N点的复数，每一个点就对应着一个频率点，某一点n(n 从1开始)表示的频率为：fn=(n-1)*fs/N。举例说明：用1kHz的采样频率采样128点，则FFT结果的128个数据即对应的频率点分别是0，1k/128，2k/128，3k/128，…，127k/128 Hz。这个频率点的幅值为：该点复数的模值除以N/2（n=1时是直流分量，其幅值是该点的模值除以N）。 二、傅里叶变换的C语言编程 1、对于快速傅里叶变换FFT，第一个要解决的问题就是码位倒序。假设一个N 点的输入序列，那么它的序号二进制数位数就是t=log2N.码位倒序要解决两个问题：①将t位二进制数倒序；②将倒序后的两个存储单元进行交换。如果输入序列的自然顺序号i用二进制数表示，例如若最大序号为15，即用4位就可表示n3n2n1n0，则其倒序后j对应的二进制数就是n0n1n2n3，那么怎样才能实现倒序呢？利用C语言的移位功能！ 程序如下，我不多说，看不懂者智商一定在180以下！复数类型定义及其运算#define N 64 //64点 #define log2N 6 //log2N=6 /*复数类型*/ typedef struct { float real; float img; }complex; complex xdata x[N]; //输入序列 /*复数加法*/ complex add(complex a,complex b) { complex c; c.real=a.real+b.real; c.img=a.img+b.img; return c; } /*复数减法*/ complex sub(complex a,complex b) { complex c; c.real=a.real-b.real;实验四 快速傅里叶变换(FFT)
快速傅里叶变换(FFT)试题
快速傅里叶变换(FFT)的原理及公式
快速傅里叶变换FFT原理与实现
详解FFT(快速傅里叶变换FFT
快速傅里叶变换的原理及其应用
快速傅里叶变换(FFT)原理及源程序
快速傅里叶变换fft变换
- 详解FFT(快速傅里叶变换FFT
- FFT超全快速傅里叶
- 快速傅里叶变换(FFT)试题
- 快速傅里叶变换(FFT)试题汇编
- 快速傅里叶变换fft变换
- 快速傅里叶变换FFT2
- 利用fft对语音信号进行快速傅里叶变换
- 第24章 快速傅里叶变换原理(FFT)
- FFT(FastFourierTransformation)快速傅里叶变换
- 实验四 快速傅里叶变换(FFT)
- 快速傅里叶变换(FFT)试题
- 快速傅里叶变换(FFT)原理及源程序
- 快速傅里叶变换(FFT)课程设计
- 快速傅里叶变换(FFT)的原理及公式
- 第三章第三节快速傅里叶变换(FFT)
- 快速傅里叶变换(FFT)
- fft快速傅里叶变换 c语言实现
- 快速傅里叶变换FFT原理与实现
- 快速傅里叶变换的原理及其应用
- FFT快速傅里叶变换(蝶形算法)详解解析