本文目录
- FFT算法分几种
- DFT与FFT变换的原理
- FFT原理的FFT应用
- FFT的公式是什么和算法是怎样实现
- “DFT、IDFT、FFT、IFFT”各是什么
- FFT的原理，怎样分析出频率的，越详细越好
- 为什么FFT能将正弦信号能量累积起来，而噪声能量却累积不起来
- 如何理解FFT
FFT算法分几种
FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。 网上有帮助文档: http://www.5doc.com/doc/123035(右上角有点击下载)
DFT与FFT变换的原理
无限长的序列也往往可以用有限长序列来逼近。对于有限长的序列我们可以使用离散傅立叶变换（DFT）(公式没法输入，不好意思)。DFT是对序列傅立叶变换的等距采样。是序列傅立叶变换的等距采样。
快速傅立叶变换FFT并不是与DFT不相同的另一种变换，而是为了减少DFT运算次数的一种快速算法。它是对DFT变换式进行一次次的分解，使其成为若干小点数DFT的组合，从而减小运算量。常用的FFT是以2为基数，它的运算效率高，程序比较简单，使用也十分地方便。
FFT的算法基本上可以分为两大类：按时间抽取（DIT）和按频率抽取（DIF）。
先说说这些基本的东西，想要具体了解，百度下，资料一大片的！！
FFT原理的FFT应用
DFT变换则说明对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息。所以只要时间序列足够长，采样足够密，频域采样也就可较好地反映信号的频谱趋势，所以FFT可以用以进行连续信号的频谱分析。
当然，这里作了几次近似处理：
1）用离散采样信号的傅立叶变换来代替连续信号的频谱，只有在严格满足采样定理的前提下，频谱才不会有畸变，否则只是近似；
2）用有限长序列来代替无限长离散采样信号。 线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。
以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:
将长为N2的序列x(n)延长到L,补L-N2个零
将长为N1的序列h(n)延长到L,补L-N1个零
如果L≥N1+N2-1,则圆周卷积与线性卷积相等,此时,可有FFT计算线性卷积,方法如下:
a.计算X(k)=FFT
b.求H(k)=FFT
c.求Y(k)=H(k)Y(k) k=0～L-1
d.求y(n)=IFFT n=0～L-1
可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。计算表明,L》32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性,因此,也称上述圆周卷积方法为快速卷积法 信号是实数序列,任何实数都可看成虚部为零的复数,例如,求某实信号y(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0),再用FFT求其离散付里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算,下面介绍两种方法。
（1）一个N点FFT同时计算两个N点实序列的DFT
设x1(n),x2(n)是彼此独立的两个N点实序列,且X1(k)=DFT
可通过一次FFT运算同时获得X1(k),X2(k)。算法如下：
首先将x1(n),x2(n)分别当作一复序列的实部及虚部,令
x(n)=x1(n)+jx2(n)
通过FFT运算可获得x(n)的DFT值 X(k)=DFT=X1(k)+jX2(k)
利用离散付里叶变换的共轭对称性
X1(K)=1/2*
X2(K)=1/2*
有了x(n)的FFT运算结果X(k),由上式即可得到X1(k),X2(k)的值。
FFT的公式是什么和算法是怎样实现
二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0; i《M; i++)
FFT_1D(ROW，N);
for (int j=0; j《N; j++)
FFT_1D(COL，M);
其中，ROW是对矩阵的第i列的一种简单表示方法。
所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。
【1D-FFT的算法实现】
设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ：
(A)
由于
所以，(A)式可以改写成下面的形式：
按照FFT的定义，上面的式子实际上是：
其中，k的取值范围是 0~N-1。
我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示
“DFT、IDFT、FFT、IFFT”各是什么
DFT，即可测试性设计（Design for Testability, DFT）是一种集成电路设计技术，它将一些特殊结构在设计阶段植入电路，以便设计完成后进行测试。电路测试有时并不容易，这是因为电路的许多内部节点信号在外部难以控制和观测。通过添加可测试性设计结构，例如扫描链等，内部信号可以暴露给电路外部。总之，在设计阶段添加这些结构虽然增加了电路的复杂程度，看似增加了成本，但是往往能够在测试阶段节约更多的时间和金钱。
IDFT就是Inverse Discrete Fourier Transform 离散傅里叶逆变换。FFT就是Fast Fourier Transform 快速傅里叶变换。
两者的应用都是将时域中难以处理的信号转换成易于处理的频域信号，分析完成后进行傅里叶反变换即得到原始的时域信号。
两者的异同是：我们知道在数学上用级数来无限逼进某个函数，以便简化计算过程而又不致使误差过大，这样工程上才能应用，否则一些数学模型是无法实现快速求解的。
IDFT：对于有限长的序列我们可以使用离散傅立叶变换，IDFT是对序列傅立叶变换的等距采样。
FFT：并不是与IDFT不相同的另一种变换（即原理是一样的），而是为了减少IDFT运算次数的一种快速算法。它是对IDFT变换式进行一次次的分解，使其成为若干小点数IDFT的组合，从而减小运算量。常用的FFT是以2为基数，它的运算效率高，程序比较简单，使用也十分地方便。
IFFT——Inverse Fast Fourier Transform 快速傅里叶逆变换。
快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
FFT的原理，怎样分析出频率的，越详细越好
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。DFT的运算为：式中由这种方法计算DFT对于X（K）的每个K值
为什么FFT能将正弦信号能量累积起来，而噪声能量却累积不起来
这要弄懂FFT的基本原理，简单说，FFT，傅里叶变换是一种看同一事物的不同方法，比如有张人体画相，你当然可以用小格子顺序分隔开，一个一个格子复原这张画；傅里叶变换的方法是先看粗线条，把轮廓画好，然后再逐渐画得越来越细节，在傅里叶变换里面，粗线条就相当于低频信号，而细节就相当于高频信号。一般事物的通常规律是，低频信号要强于高频信号并决定主要性质，而高频成分越高，越细腻，但也影响比例越小。
好了，现在回头解释你的问题，噪声信号如果用FFT的角度看，相当于在任何频谱范围内都有一个平均的分布，如果只是截取有效声音频谱范围内的信号，那么噪声就可以被大大消弱，当然你也会多少损失有效的高频信号，但相对你耳朵的主观辨别能力，这些损失相对于噪声的影响来说大可忽略，这样你就感觉正弦信号能量累积起来了。噪声大部分都被甩掉了，自然就弱了。
这个过程的全程是 待处理信号－－FFT－－滤除高频信号－－－反FFT复原－－处理后信号。
这个信号处理过程不仅用在声音上、在图像、电信、光学等领域都有应用，原理都是一样的，不过在针对不同的对象和目的，在滤除环节上处理不同，除了滤除低频的还有专门滤除高频的也有对确定频谱范围进行控制的。
如何理解FFT
fft在matlab中可以按原理采样来运算，也可以用快速fft算法。
clear
fs=1000
t=0:1/fs:0.6;
f1=100;
f2=300;
x=sin(2*pi*f1*t)+sin(2*pi*f2*t);
subplot(711)
plot(x);
title(’f1（100Hz）\f2(300Hz)的正弦信号，初相0’)
xlabel(’序列（n）’)
grid on
number=512
y=fft(x,number);
n=0:length(y)-1;
f=fs*n/length(y);
subplot(713)
plot(f,abs(y));
title(’f1\f2的正弦信号的FFT（512点）’)
xlabel(’频率Hz’)
grid on
x=x+randn(1,length(x));
subplot(715)
plot(x);
title(’原f1\f2的正弦信号（含随机噪声）’)
xlabel(’序列（n）’)
grid on
y=fft(x,number);
n=0:length(y)-1;
f=fs*n/length(y);
subplot(717)
plot(f,abs(y));
title(’原f1\f2的正弦信号（含随机噪声）的FFT（512点）’)
xlabel(’频率Hz’)
grid on
