mac*_*die 10
至于问题的第一部分,前物理学教授Bartosz Milewski有一个非常好的解释,FFT是什么以及它是如何工作的.
此外,掌握一天的傅里叶变换也值得一读.
用英语讲 (？)
假设你有来自扬声器的声音.
然后你设置,让我们在这里得到一个很好的圆数,1024个谐波振荡器,它们会响应特定的频率范围.
播放声音,比如一秒钟.
振荡器开始引起扬声器发出的声音.在上述第二个之后,你会读到每个振荡器产生共振的程度.因此,您可以获得离散傅里叶变换,这意味着您可以获得每个频率范围对扬声器发出的声音的贡献程度.
您可以将其视为一系列频率范围的强度,而不是将声音视为由波形引起的气压量,在时隙中发生变化.
当然在解释DFT时,扬声器部分并不合适,因为您必须处理采样输入.因此,在这种情况下,实际应在1/44秒之后测量1024个数字"振荡器",假设音频以44kHz的速率采样.
快速傅里叶变换是一种执行离散傅里叶变换的算法,计算机可以很容易地在输入信号上运行.它强加了你必须在实现中使用的一些约束(例如,样本的数量必须是2的幂),因为它使用一些聪明的技巧来大大减少对样本缓冲区执行的计算量.
实际上没有必要更深入,因为我给出的两个链接提供了一个非常明确的解释.请注意,如果不了解其背后的数学,就不可能从理论到实施.
我希望这个介绍有道理!
傅里叶分析是一系列数学技术,所有这些都基于将信号分解为正弦曲线.离散傅里叶变换(DFT)是与数字化信号一起使用的系列成员.
来自Wolfram,
快速傅立叶变换(FFT)是离散傅立叶变换算法,其将N点所需的计算次数从2N ^ 2减少到2NlgN,其中lg是基数-2对数.如果要变换的函数与采样频率不是谐波相关的,则FFT的响应看起来像sinc函数(尽管积分功率仍然是正确的).使用变迹函数通过变迹可以减少混叠(也称为泄漏).然而,混叠减少是以扩大光谱响应为代价的.
它通常作为信号处理课程的一部分进行教学.因此,您一定需要处理一些图像/声音处理.:)
请参阅斯坦福工程学院的这些讲座:这里
基本上,DFT是
而Cooley-Tukey FFT算法的伪代码如下:
Y0,...,N?1 ? ditfft2(X, N, s): DFT of (X0, Xs, X2s, ..., X(N-1)s):
if N = 1 then
Y0 ? X0 trivial size-1 DFT base case
else
Y0,...,N/2?1 ? ditfft2(X, N/2, 2s) DFT of (X0, X2s, X4s, ...)
YN/2,...,N?1 ? ditfft2(X+s, N/2, 2s) DFT of (Xs, Xs+2s, Xs+4s, ...)
for k = 0 to N/2?1 combine DFTs of two halves into full DFT:
t ? Yk
Yk ? t + exp(?2?i k/N) Yk+N/2
Yk+N/2 ? t ? exp(?2?i k/N) Yk+N/2
endfor
endif
(从http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm中无耻地复制)
另外,你可能想要研究一下
- http://www.fftw.org/download.html
- http://www.developer.com/java/other/article.php/3457251
- http://www.dspguide.com/pdfbook.htm