快速傅里叶变换（Fast Fourier Transform, FFT）是一种用于将信号从时间域转换到频率域的算法。
傅里叶变换的核心思想是：任何周期性信号都可以分解成多个不同频率的正弦波或余弦波的叠加。
简单来说，FFT可以帮助我们理解一个信号的频率成分，即它由哪些频率组成，每个频率对应的振幅是多少，如下图所示。
1、时间转换为频率
假设我们有一个随时间变化的信号（例如音乐、心跳信号、电压波形等），这个信号可以用一系列数值来表示，比如一个音频文件中的采样值。在时间域，信号随时间变化，而通过傅里叶变换，我们可以将这些时间域的信号转换为频率域的表示。
具体步骤如下：
①采样：首先，我们需要对时间信号进行采样，得到一系列离散的数值点。假设采样频率是 fs，采样点数是 N，即我们有 N 个采样值。
②计算频率分量：FFT 将这些采样点转换为频率域的分量。结果是一个复数序列，其中每个复数值对应一个频率分量。FFT 的结果告诉我们信号中不同频率的“权重”是多少。
③频率分辨率：FFT 结果中的每个点对应一个频率值。计算方式为：
其中，fs 是采样频率，N 是采样点数。这个 Δf 是频率分辨率，即每个频率分量之间的间隔。
④频率范围：FFT 的输出频率范围是从 0 到 fs/2（即采样频率的一半），这是因为奈奎斯特定理表明，采样频率必须是最高频率分量的两倍，才能避免混叠。
2、幅值计算
FFT 的输出结果是复数形式，表示频率分量的振幅和相位。每个频率分量的幅值（或叫“强度”）可以通过复数的模计算出来。对于复数 Z=a+bi，其模可以表示为：
具体步骤：
①FFT 输出的复数形式：FFT 的结果是频率分量的复数形式 X(f)，其中实部 a 和虚部 b 分别表示余弦和正弦分量的系数。
②计算幅值：我们对每个复数值计算其模，即：
这个模值就是每个频率分量对应的幅值，也可以理解为该频率在信号中的“强度”或“能量”。
③幅值归一化：通常，FFT 输出的幅值需要除以采样点数 N 才能得到正确的幅值大小，尤其是当信号是周期性的或者我们对幅值的绝对大小感兴趣时。即：
3、总结
时间信号通过采样得到离散的数据点，FFT 将这些数据点转换成不同频率分量的复数值。
