DFT与FFT：离散频谱表示与快速计算方法

本章节主要讨论的是按时间抽取的离散傅立叶变换（DFT）算法，它是数字信号处理中的核心概念，特别是在快速傅立叶变换（FFT）的背景下。首先，我们回顾了离散傅立叶变换的基本概念，它是对有限长序列的离散频谱表示，通过对连续时间傅立叶变换（DTFT）的限制和离散化，使得信号在频域上的处理更为实际。 1. **从有限长序列的DTFT到DFT**：DTFT是无限长序列的频域表示，但计算机处理的是有限数据。DFT将无限序列通过取模运算（余数运算）转换成周期性延拓，即先将序列视为周期函数，然后取其主值。例如，对于序列x[n]，其DFT X[k]可以通过公式 \( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N} \) 计算，其中N是采样点数，\( e^{-j2\pi kn/N} \) 是复数单位。 2. **取模运算与周期延拓**：余数运算对于DFT至关重要，它确保了信号在有限长度下处理的正确性。取模操作将序列映射到一个周期范围内，便于计算机高效计算。同时，这种周期延拓的概念意味着信号在每个周期内的行为是相同的。 3. **从DFS（离散频谱函数）到DFT**：DFS是DFT的一种特殊形式，通常用于描述非周期信号的频谱，它是一个连续的频率函数。由于DFS不适于计算机直接计算，DFT作为一种离散对称版本，将频谱采样固定在有限数量的点上，如 \( k = 0, 1, ..., N-1 \)，每点对应一个特定的频率 \( \frac{2\pi k}{N} \)。 4. **频率离散化与采样点数N**：DFT中的频率采样是均匀的，间距为 \( \frac{2\pi}{N} \)，这称为频率离散化。选择合适的N可以平衡频率分辨率和计算复杂度，因为N越大，频率分辨率越高，但DFT计算所需的时间也会增加。 5. **计算机实现：DFT与FFT**：由于DFT计算的复杂度为O(N^2)，对于大样本数据，效率较低。这就是为何引入快速傅立叶变换（FFT），它利用了DFT的结构，通过高效的算法将计算复杂度降低到O(N log N)或更低，极大地提高了频域分析的速度。 总结来说，本章节详细介绍了按时间抽取的DFT算法，包括其与DTFT的关系，取模运算在DFT中的作用，以及如何通过DFS向DFT过渡，最后强调了在实际应用中，尤其是计算机处理时，DFT和FFT的实用价值。理解这些概念对于深入研究信号处理、通信工程、图像处理等领域至关重要。