在连续时间信号处理的基础上，我们探讨了离散时间下的信号分析工具。连续时间的傅里叶级数处理的是连续周期信号，而傅里叶变换则针对非周期信号。为了处理理想情况，我们引入了拉普拉斯和z变换，但它们在计算机上实施有限，因此我们需要关注离散情况。

离散世界中，离散傅里叶级数(DFS)处理离散周期信号，离散时间傅里叶变换(DTFT)则是离散非周期信号的对应。而离散傅里叶变换(DFT)则聚焦于离散周期信号的主成分，它是一个周期取样版本。为了将连续信号转换为离散且周期，我们需要先在时域上采样，随后在频域上再进行周期化，最终研究的是信号的周期部分，即DFT。快速傅里叶变换(FFT)则是为了优化DFT的计算机计算效率。

DFT和DFS本质上相同，只是在N点取样上有所区别。DFT的计算可以通过矩阵乘法表示，使用DFT矩阵进行计算，而逆变换IDFT遵循特定的归一化规则。FFT利用DFT的性质，如旋转因子、周期性和共轭对称性，将计算复杂度从[公式]降低到[公式]。其中，频域抽取FFT和时域抽取FFT采用了不同的分治策略，最终计算复杂度为[公式]。