Discrete Fourier Transform DFT
是傅里叶变换在离散数据上的一个应用。它是一种将离散时间信号转换为频域表示的数学工具。 DFT 是数字信号处理中的核心算法，广泛应用于图像处理、音频分析、数据压缩、通信系统等领域。
定义
对于一个长度为 的离散时间序列 ，其离散傅里叶变换（DFT）定义为：
X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-i\frac{2\pi}{N}kn} \end{align}$$ 其中，$X[k]$ 是频域中的第 $k$ 个分量，$n$ 是时间域中的离散索引，$k$ 是频率域中的离散索引，$i$ 是虚数单位。 ### 逆变换 对应的逆离散傅里叶变换（Inverse Discrete Fourier Transform，IDFT）将频域信号转换回时间域，定义为： $$\begin{align} x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] \cdot e^{i\frac{2\pi}{N}kn} \end{align}$$ ### 快速傅里叶变换（FFT） 由于直接计算 DFT 涉及 $N$ 次乘法和 $N-1$ 次加法，对于大的 $N$，计算量是非常大的。快速傅里叶变换（FFT）是一种高效的算法，可以将 DFT 的计算复杂度从 $O (N^2)$ 降低到 $O (N \log N)$，极大地提高了计算效率。 ### 应用 1. **频谱分析**：分析信号的频率成分。 2. **滤波**：设计滤波器去除或保留特定频率的信号。 3. **图像处理**：图像压缩、图像分析等。 4. **音频处理**：音频压缩、降噪、声音合成等。 5. **数据压缩**：通过变换编码减少数据量。 离散傅里叶变换是现代数字技术中不可或缺的一部分，它的应用几乎遍及所有需要处理离散数据的领域。 --- ## AI 结构化补充（2026-05-02） **Discrete Fourier Transform** 离散傅里叶变换（DFT） 是傅里叶变换在离散数据上的一个应用。它是一种将离散时间信号转换为频域表示的数学工具。 DFT 是数字信号处理中的核心算法，广泛应用于图像处理、音频分析、数据压缩、通信系统等领域。 ### 定义 对于一个长度为 $N$ 的离散时间序列 $x[n]$，其离散傅里叶变换（DFT）定义为： $$\begin{align} X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-i\frac{2\pi}{N}kn} \end{align}$$ 其中，$X[k]$ 是频域中的第 $k$ 个分量，$n$ 是时间域中的离散索引，$k$ 是频率域中的离散索引，$i$ 是虚数单位。 这个定义采用许多 DFT 文献和 MATLAB 的负号约定：\omega=e^{-2\pi i/N}.
w=e^{+2\pi i/N},
于是 $\omega=\overline w$。因此同一个矩阵符号在不同书写习惯下可能表示互为共轭的矩阵；判断公式时要同时看指数符号、归一化因子和变换方向。MATLAB 的 `fft` 使用负号指数，`ifft` 使用正号指数并带有因子 $1/N$。 ### 逆变换 对应的逆离散傅里叶变换（Inverse Discrete Fourier Transform，IDFT）将频域信号转换回时间域，定义为： $$\begin{align} x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] \cdot e^{i\frac{2\pi}{N}kn} \end{align}$$ ### 快速傅里叶变换（FFT） 由于直接计算每个频率分量都涉及 $N$ 次乘法和 $N-1$ 次加法，完整 DFT 的计算量随 $N^2$ 增长。快速傅里叶变换（FFT）是一种高效的算法，可以将 DFT 的计算复杂度从 $O(N^2)$ 降低到 $O(N \log N)$，极大地提高了计算效率。 ### 应用 1. **频谱分析**：分析信号的频率成分。 2. **滤波**：设计滤波器去除或保留特定频率的信号。 3. **图像处理**：图像压缩、图像分析等。 4. **音频处理**：音频压缩、降噪、声音合成等。 5. **数据压缩**：通过变换编码减少数据量。 离散傅里叶变换是现代数字技术中不可或缺的一部分，它的应用几乎遍及所有需要处理离散数据的领域。 ### 矩阵形式与正交性 令 $\omega_N=e^{-2\pi i/N}$，DFT 可写为X=F_Nx,\qquad (F_N)_{k,n}=\omega_N
这里的 $F_N$ 是 [[傅里叶矩阵\|傅里叶矩阵]]。由于 [[单位根\|单位根]] 满足\sum_{n=0}^{N-1}\omega_N^{(k-\ell)n}
\begin{cases} N,&k=\ell,\ 0,&k\ne\ell, \end{cases}
所以 $F_N^*F_N=NI$，归一化矩阵 $N^{-1/2}F_N$ 是 [[酉矩阵\|酉矩阵]]。这说明 DFT 本质上是复内积空间中的正交基坐标变换。 ### 循环矩阵的特征值视角 DFT 还可以看成把 [[循环矩阵\|循环矩阵]] 的生成向量变成特征值向量。仍采用本页的负号约定\omega_N=e^{-2\pi i/N},\qquad (F_N)_{k,n}=\omega_N
C=c_0I+c_1P+\cdots+c_{N-1}P
其中 $P$ 是左循环移位矩阵，则向量v(\omega_N^k)=(1,\omega_N^k,\omega_N^{2k},\ldots,\omega_N^{(N-1)k})^{\mathsf T}
是 $C$ 的特征向量，对应特征值\mu_k=c_0+c_1\omega_N^k+\cdots+c_{N-1}\omega_N
F_Nc=(\mu_0,\mu_1,\ldots,\mu_{N-1})^{\mathsf T}
给出循环矩阵的特征值。 若改用正号单位根 $\lambda_k=e^{2\pi i k/N}$，则使用 $F_N^{(+)}=\overline{F_N}$。例如 $N=4$ 时，正号顺序可写成 $\lambda=1,i,-1,-i$，特征值为 $c_0+c_1\lambda+c_2\lambda^2+c_3\lambda^3$；这与本页 DFT 约定只是共轭和频率排序的差异，不应在同一推导中混合。 ### 典型例子 若 $x[n]=1$ 对所有 $n=0,\dots,N-1$ 成立，则X[0]=N,\qquad X[k]=0\quad(k=1,\dots,N-1).
常数序列只含零频成分。若 $x[n]=e^{2\pi i rn/N}$，则 DFT 只在第 $r$ 个频率上非零，说明复指数序列正是 DFT 的基向量。 ### 与相邻概念关系 DFT 的每个输出 $X[k]$ 都是一个 [[傅里叶系数\|傅里叶系数]]，表示原序列在第 $k$ 个离散频率上的投影。它也是特殊 [[矩阵表示\|矩阵表示]]：输入坐标从时间索引基变为频率基。若只保留部分频率系数再逆变换，就得到频域的 [[低秩近似\|低秩近似]] 或压缩思想；若全部保留，则变换可逆且不丢失信息。 ### 有限傅里叶级数与插值视角 若采用正号根 $w=e^{2\pi i/n}$，并把(F_n^{(+)})_{j,k}=w^{jk},\qquad j,k=0,\ldots,n-1,
y=F_n
\sum_{k=0}^{n-1} c_k e
x_j=\frac{2\pi j}{n},\qquad j=0,\ldots,n-1
y_j=\sum_{k=0}^{n-1}c_kw
c=(F_n^{(+)})^{-1}y=\frac{\overline{F_n
从样本 $y$ 恢复系数 $c$。 这也是多项式插值问题。令p(z)=c_0+c_1z+\cdots+c_{n-1}z
则 $y_j=p(w^j)$，也就是在 $1,w,\ldots,w^{n-1}$ 这些单位根节点上求值。Fourier 矩阵正是这些特殊节点上的 Vandermonde（[[范德蒙德矩阵\|范德蒙德矩阵]]）；从样本反求 $c$，就是在单位根节点上的插值。若回到本页开头的 DFT 负号约定，则相应矩阵换成 $\overline{F_n^{(+)}}$。