快速傅里叶变换（Fast Fourier Transform，FFT）是一种将时域信号转换为频域信号的高效算法。它的原理是将信号分解为基于正弦和余弦函数的复数的线性组合，从而得到它的频域表示。FFT的公式如下： 

X[k] = Σx[n]e^(-j2πnk/N) n=0,1,...,N-1