离散傅里叶变换

Discrete Fourier Transform DFT

是傅里叶变换在离散数据上的一个应用。它是一种将离散时间信号转换为频域表示的数学工具。
DFT 是数字信号处理中的核心算法，广泛应用于图像处理、音频分析、数据压缩、通信系统等领域。

对于一个长度为 $N$ 的离散时间序列 $x [n]$ ，其离散傅里叶变换（DFT）定义为：

\begin{array}{r} X [k] = \sum_{n = 0}^{N - 1} x [n] \cdot e^{- i \frac{2 π}{N} k n} \end{array}

其中， $X [k]$ 是频域中的第 $k$ 个分量， $n$ 是时间域中的离散索引， $k$ 是频率域中的离散索引， $i$ 是虚数单位。

对应的逆离散傅里叶变换（Inverse Discrete Fourier Transform，IDFT）将频域信号转换回时间域，定义为：

\begin{array}{r} x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] \cdot e^{i \frac{2 π}{N} k n} \end{array}

由于直接计算 DFT 涉及 $N$ 次乘法和 $N - 1$ 次加法，对于大的 $N$ ，计算量是非常大的。快速傅里叶变换（FFT）是一种高效的算法，可以将 DFT 的计算复杂度从 $O (N^{2})$ 降低到 $O (N \log N)$ ，极大地提高了计算效率。

离散傅里叶变换是现代数字技术中不可或缺的一部分，它的应用几乎遍及所有需要处理离散数据的领域。