离散傅里叶变换

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}

快速傅里叶变换（FFT）

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

应用

频谱分析：分析信号的频率成分。
滤波：设计滤波器去除或保留特定频率的信号。
图像处理：图像压缩、图像分析等。
音频处理：音频压缩、降噪、声音合成等。
数据压缩：通过变换编码减少数据量。

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

AI 结构化补充（2026-05-02）

Discrete Fourier Transform 离散傅里叶变换（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$ 是虚数单位。

这个定义采用许多 DFT 文献和 MATLAB 的负号约定：

ω = e^{- 2 π i / N} .

线性代数中讨论有限 Fourier 合成时，也常取

w = e^{+ 2 π i / N},

于是 $ω = \overset{―}{w}$ 。因此同一个矩阵符号在不同书写习惯下可能表示互为共轭的矩阵；判断公式时要同时看指数符号、归一化因子和变换方向。MATLAB 的 fft 使用负号指数，ifft 使用正号指数并带有因子 $1 / N$ 。

逆变换

对应的逆离散傅里叶变换（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}

快速傅里叶变换（FFT）

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

应用

频谱分析：分析信号的频率成分。
滤波：设计滤波器去除或保留特定频率的信号。
图像处理：图像压缩、图像分析等。
音频处理：音频压缩、降噪、声音合成等。
数据压缩：通过变换编码减少数据量。

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

矩阵形式与正交性

令 $ω_{N} = e^{- 2 π i / N}$ ，DFT 可写为

X = F_{N} x, (F_{N})_{k, n} = ω_{N}^{k n} .

这里的 $F_{N}$ 是傅里叶矩阵。由于单位根满足

\sum_{n = 0}^{N - 1} ω_{N}^{(k - ℓ) n} = {\begin{cases} N, & k = ℓ, \\ 0, & k \neq ℓ, \end{cases}

所以 $F_{N}^{*} F_{N} = N I$ ，归一化矩阵 $N^{- 1 / 2} F_{N}$ 是酉矩阵。这说明 DFT 本质上是复内积空间中的正交基坐标变换。

循环矩阵的特征值视角

DFT 还可以看成把循环矩阵的生成向量变成特征值向量。仍采用本页的负号约定

ω_{N} = e^{- 2 π i / N}, (F_{N})_{k, n} = ω_{N}^{k n} .

若循环矩阵写成

C = c_{0} I + c_{1} P + \dots + c_{N - 1} P^{N - 1},

其中 $P$ 是左循环移位矩阵，则向量

v (ω_{N}^{k}) = (1, ω_{N}^{k}, ω_{N}^{2 k}, \dots, ω_{N}^{(N - 1) k})^{T}

是 $C$ 的特征向量，对应特征值

μ_{k} = c_{0} + c_{1} ω_{N}^{k} + \dots + c_{N - 1} ω_{N}^{(N - 1) k} .

因此

F_{N} c = (μ_{0}, μ_{1}, \dots, μ_{N - 1})^{T}

给出循环矩阵的特征值。

若改用正号单位根 $λ_{k} = e^{2 π i k / N}$ ，则使用 $F_{N}^{(+)} = \overset{―}{F_{N}}$ 。例如 $N = 4$ 时，正号顺序可写成 $λ = 1, i, - 1, - i$ ，特征值为 $c_{0} + c_{1} λ + c_{2} λ^{2} + c_{3} λ^{3}$ ；这与本页 DFT 约定只是共轭和频率排序的差异，不应在同一推导中混合。

典型例子

若 $x [n] = 1$ 对所有 $n = 0, \dots, N - 1$ 成立，则

X [0] = N, X [k] = 0 (k = 1, \dots, N - 1) .

常数序列只含零频成分。若 $x [n] = e^{2 π i r n / N}$ ，则 DFT 只在第 $r$ 个频率上非零，说明复指数序列正是 DFT 的基向量。

与相邻概念关系

DFT 的每个输出 $X [k]$ 都是一个傅里叶系数，表示原序列在第 $k$ 个离散频率上的投影。它也是特殊矩阵表示：输入坐标从时间索引基变为频率基。若只保留部分频率系数再逆变换，就得到频域的低秩近似或压缩思想；若全部保留，则变换可逆且不丢失信息。

有限傅里叶级数与插值视角

若采用正号根 $w = e^{2 π i / n}$ ，并把

(F_{n}^{(+)})_{j, k} = w^{j k}, j, k = 0, \dots, n - 1,

则矩阵式

y = F_{n}^{(+)} c

可以理解为有限傅里叶级数

\sum_{k = 0}^{n - 1} c_{k} e^{i k x}

在等距点

x_{j} = \frac{2 π j}{n}, j = 0, \dots, n - 1

上的取值：

y_{j} = \sum_{k = 0}^{n - 1} c_{k} w^{j k} .

逆变换用

c = (F_{n}^{(+)})^{- 1} y = \frac{\overset{―}{F_{n}^{(+)}}}{n} y

从样本 $y$ 恢复系数 $c$ 。

这也是多项式插值问题。令

p (z) = c_{0} + c_{1} z + \dots + c_{n - 1} z^{n - 1},

则 $y_{j} = p (w^{j})$ ，也就是在 $1, w, \dots, w^{n - 1}$ 这些单位根节点上求值。Fourier 矩阵正是这些特殊节点上的 Vandermonde（范德蒙德矩阵）；从样本反求 $c$ ，就是在单位根节点上的插值。若回到本页开头的 DFT 负号约定，则相应矩阵换成 $\overset{―}{F_{n}^{(+)}}$ 。