离散傅里叶变换(Discrete Fourier Transform,DFT)是一种把有限长度离散序列转换为离散频率成分的数学变换。它在时域与频域两端都采用离散序列,可视为对离散时间傅里叶变换(DTFT)进行均匀频域取样的结果。长度为 N 的输入序列及其 DFT 都可理解为周期离散信号的一个主值区间,因此DFT天然具有周期性边界。
对于 N 点序列 x[n],DFT定义为 X[k] = Σx[n]e−i2πnk/N,其中 n 与 k 均取0至N−1,i为虚数单位。每个 X[k] 表示输入序列在对应复指数基上的分量,其幅值和相位共同描述该离散频点的频域信息。逆离散傅里叶变换(IDFT)使用相反符号的指数项,并乘以1/N,可从全部频域系数恢复原序列。
从线性代数角度看,周期为 N 的离散信号构成 N 维复数空间,而复指数序列构成一组正交基。DFT就是把信号投影到这组基上。它是可逆线性变换,并满足普朗歇尔定理与帕塞瓦尔定理,使时域内积及能量可以在相应归一化关系下转换到频域。
DFT的处理链通常包括连续信号取样、有限长度截取或加窗、频域变换以及结果分析。连续信号经过时域取样后形成离散序列,其DTFT在频域仍然连续;DFT再于间隔为2π/N的 N 个频点上对DTFT取样,得到有限频域序列。
N点DFT只能观察 N 个离散频点,这种限制称为栅栏效应。向原序列末端补零并计算更长的DFT,可以取得DTFT在更多频率位置上的数值,使频谱曲线显示得更密集,但不会提高由实际取样时长决定的物理频谱分辨率。提高真正的分辨率需要在满足取样定理的条件下增加时域取样长度。
DFT还把圆周卷积转换为频域逐点乘法。若实际目标是线性卷积,则须把输入序列补零至足够长度,避免周期延拓造成卷积结果回绕。时域循环移位会在频域产生相位变化,而时域乘以复指数则对应频域循环移位。
按定义直接计算 N 点DFT约需 O(N²)次运算。实际系统通常采用快速傅里叶变换(FFT)计算DFT及其逆变换,把复杂度降低至 O(N log N)。FFT不是另一种变换,而是一类高效计算DFT的算法。库利-图基算法利用分治策略把较长DFT拆分成多个较短DFT,也可采用不同基数及互质因子等分解形式;只需少量指定频点时,还可使用格策尔算法计算相应DFT系数。
DFT广泛用于信号处理、数码通信、音讯处理、图像处理和数值分析。频谱分析会对连续信号均匀取样并截取为有限序列,再利用DFT观察频率成分;取样频率不合适可能产生混叠,有限截取则可能引起频谱泄漏,通常通过适当取样、选择序列长度及加窗处理控制这些影响。
在数据压缩中,DFT可把时域或空间域数据转换到频域,以频率系数表示语音、音讯、图像或视频信息,再由逆变换重建信号。多维DFT也用于谱方法求解微分方程。长整数与多项式乘法则利用卷积定理,把卷积转换为频域逐点乘法,再经逆变换取得结果。