本文共 935 字,大约阅读时间需要 3 分钟。
FFT:
快速傅里叶变换(Fast FourierTransform)是离散傅立叶变换(DFT)的高速算法,能够将一个信号时域变换到频域。Why:有些信号在时域上是非常难看出什么特征的,可是如果变换到频域之后,就非常easy看出特征了。这就是非常多信号分析採用FFT变换的原因。另外,FFT能够将一个信号的频谱提取出来,这在频谱分析方面也是经经常使用的。FFT物理意义:
一个模拟信号,经过ADC採样之后,就变成了数字信号。採样定理告诉我们,採样频率要大于信号频率的两倍(定理)。採样得到的数字信号,就能够做FFT变换了。N个採样点,经过FFT之后,就能够得到N个点的FFT结果。为了方便进行FFT运算,通常N取2的整数次方。如果採样频率为Fs,信号频率F,採样点数为N。那么FFT之后结果就是一个为N点的复数(e.g., a+bi)。对于第n个点:
模值为:根号sqrt(a^2 + b^2)), 频率为:(n-1)Fs/N 幅度为:模值/(N/2) 相位为:b/a ,(换算为角度,需乘360)如果原始信号的峰值为A,那么FFT的结果的每一个点(除了第一个点直流分量之外)的模值就是A的N/2。
在算法竞赛中的运用主要是用来加速多项式的乘法。
需搞明白的概念:多项式表达式、点值表达式、复数、复数的单位根(傅里叶变换里用到的概念,有折半引理、和消去引理)
什么是卷积?参考了知乎名嘴:
转载地址:http://rtiyk.baihongyu.com/