做网站公司职务,网络宣传,微商城是怎么做的,设计工作室logo图片数字世界的“棱镜”#xff1a;离散傅里叶变换#xff08;DFT#xff09;完全解析
在上一章#xff0c;我们探索了Z变换和离散时间傅里叶变换#xff08;DTFT#xff09;。我们知道#xff0c;DTFT是一个无比强大的理论工具#xff0c;它能将一个时域离散序列的“基因…数字世界的“棱镜”离散傅里叶变换DFT完全解析
在上一章我们探索了Z变换和离散时间傅里叶变换DTFT。我们知道DTFT是一个无比强大的理论工具它能将一个时域离散序列的“基因图谱”——也就是它的频谱——完整地揭示出来。理论上只要我们知道了信号的DTFT就知道了它包含的所有频率成分。
但这里有一个巨大的“但是”。DTFT是理论上的完美却在实践中遇到了一个无法逾越的鸿沟
DTFT的定义是针对无限长序列的。而在现实世界中我们用计算机处理的信号无论是音频、图像还是一段传感器数据都必然是有限长度的。DTFT计算出的频谱 X ( e j ω ) X(e^{j\omega}) X(ejω) 是一个关于频率 ω \omega ω 的连续函数。计算机天生只能处理离散的数据点它无法存储和计算一个连续函数。
这就好比我们拥有一张描绘了整个地球的、精度无限的完美地图DTFT但我们的工具只是一台内存有限的普通电脑。我们不可能把整张地图装进电脑。我们该怎么办
答案是对地图进行采样我们只在有限的区域内信号的有限长度选取有限个有代表性的地点频谱的有限个点来观察。这个为计算机量身定做的、从理论走向实践的“采样版”傅里叶变换就是我们今天的主角——离散傅里叶变换Discrete Fourier Transform, DFT。
DFT是数字信号处理领域应用最广泛的工具没有之一。从你的手机音乐播放器里的频谱显示到通信系统中的调制解调再到各种高效的滤波算法背后都有DFT的身影。理解它是你从理论学习迈向工程实践的决定性一步。
从理想到现实DFT的诞生
让我们再次明确一下从完美的DTFT到实用的DFT我们必须解决的两个核心问题
信号长度问题我们无法处理无限长的信号 x ( n ) x(n) x(n)。解决方案我们只截取信号中一段有限的长度比如 N N N 个点来进行分析。频谱连续问题我们无法计算连续的频谱 X ( e j ω ) X(e^{j\omega}) X(ejω)。解决方案我们只在频谱的一个周期通常是 [ 0 , 2 π ) [0, 2\pi) [0,2π)内等间隔地计算 N N N 个点的频谱值。
这两个解决方案合在一起就构成了DFT的本质。
DFT的核心定义
对于一个长度为 N N N 的有限长序列 x ( n ) x(n) x(n)其中 n 0 , 1 , … , N − 1 n0, 1, \dots, N-1 n0,1,…,N−1它的N点DFT定义为 X ( k ) ∑ n 0 N − 1 x ( n ) W N k n , k 0 , 1 , … , N − 1 X(k) \sum_{n0}^{N-1} x(n) W_N^{kn}, \quad k0, 1, \dots, N-1 X(k)n0∑N−1x(n)WNkn,k0,1,…,N−1 相应地从频域序列 X ( k ) X(k) X(k) 恢复时域序列 x ( n ) x(n) x(n) 的逆变换IDFT为 x ( n ) 1 N ∑ k 0 N − 1 X ( k ) W N − k n , n 0 , 1 , … , N − 1 x(n) \frac{1}{N} \sum_{k0}^{N-1} X(k) W_N^{-kn}, \quad n0, 1, \dots, N-1 x(n)N1k0∑N−1X(k)WN−kn,n0,1,…,N−1 这里的 W N W_N WN 是一个非常重要的符号它被称为旋转因子Twiddle Factor其定义为 W N e − j 2 π N W_N e^{-j\frac{2\pi}{N}} WNe−jN2π W N k W_N^k WNk 代表了在复平面单位圆上从(1, 0)点开始按顺时针方向转过 k k k 个 2 π / N 2\pi/N 2π/N 角度后到达的点。整个DFT的计算本质上就是将时域信号 x ( n ) x(n) x(n) 与这些在单位圆上旋转的点进行内积运算从而衡量出信号在各个特定频率上的分量大小。
DFT与Z变换/DTFT的血缘关系
DFT并不是一个凭空冒出来的全新概念它与我们在上一章学习的Z变换和DTFT有着深刻的血缘关系。
一个有限长序列 x ( n ) x(n) x(n) 的Z变换为 X ( z ) ∑ n 0 N − 1 x ( n ) z − n X(z) \sum_{n0}^{N-1} x(n) z^{-n} X(z)n0∑N−1x(n)z−n 它的DTFT则是Z变换在单位圆上的取值 X ( e j ω ) X ( z ) ∣ z e j ω ∑ n 0 N − 1 x ( n ) e − j ω n X(e^{j\omega}) X(z)|_{ze^{j\omega}} \sum_{n0}^{N-1} x(n) e^{-j\omega n} X(ejω)X(z)∣zejωn0∑N−1x(n)e−jωn 现在让我们在DTFT的频谱上等间隔地采样N个点。采样点的频率为 ω k 2 π k N \omega_k \frac{2\pi k}{N} ωkN2πk其中 k 0 , 1 , … , N − 1 k0, 1, \dots, N-1 k0,1,…,N−1。将这个 ω k \omega_k ωk 代入DTFT的公式 X ( e j ω k ) ∑ n 0 N − 1 x ( n ) e − j ( 2 π k N ) n ∑ n 0 N − 1 x ( n ) ( e − j 2 π N ) k n ∑ n 0 N − 1 x ( n ) W N k n X(e^{j\omega_k}) \sum_{n0}^{N-1} x(n) e^{-j (\frac{2\pi k}{N}) n} \sum_{n0}^{N-1} x(n) (e^{-j\frac{2\pi}{N}})^{kn} \sum_{n0}^{N-1} x(n) W_N^{kn} X(ejωk)n0∑N−1x(n)e−j(N2πk)nn0∑N−1x(n)(e−jN2π)knn0∑N−1x(n)WNkn 看这个结果不就是我们定义的DFT X ( k ) X(k) X(k) 吗
所以我们得出了一个至关重要的结论 一个N点有限长序列的N点DFT就是其DTFT或Z变换在单位圆上的N个等间隔采样点。 (上图展示了Z平面上的单位圆DFT的计算就相当于在这个单位圆上等间隔地取N个点并计算Z变换在这些点上的值。)
这个结论完美地将理论DTFT/Z变换与实践DFT联系在了一起。DFT通过在频域进行采样成功地将一个连续的频谱问题转化为了一个计算机可以处理的离散问题。
DFT的“怪癖”循环的魔咒
将无限和连续的世界强行压缩到有限和离散的世界必然会带来一些“副作用”。DFT最核心、最独特也最容易让初学者困惑的特性就是它的隐含周期性Implied Periodicity。
当你对一个长度为N的序列 x ( n ) x(n) x(n) 进行N点DFT时DFT算法“看待”这个序列的方式并不是一个孤立的、长度为N的片段。它会固执地认为你给它的这个 x ( n ) x(n) x(n)其实是一个周期为N的无限长周期序列中的一个主值周期。
(上隐含周期性一个有限长序列被DFT看作是首尾相连的圆形序列并进行周期延拓。)
这个“自作多情”的假设给DFT的性质带来了深刻的影响其中最关键的就是循环移位和循环卷积。
线性卷积 vs. 循环卷积一个不小心就踩的“坑”
在上一章我们知道LTI系统中信号的传递是通过线性卷积完成的并且在频域上有一个优美的性质时域的线性卷积对应频域的乘积。 x ( n ) ∗ h ( n ) ⟷ X ( e j ω ) H ( e j ω ) x(n) \ast h(n) \longleftrightarrow X(e^{j\omega}) H(e^{j\omega}) x(n)∗h(n)⟷X(ejω)H(ejω)
我们自然希望DFT也能保持这个美好的性质。但由于隐含周期性的存在事情发生了变化。在DFT的世界里时域的运算不再是线性的而是循环的。
线性卷积的公式是 y L ( n ) ∑ k − ∞ ∞ x ( k ) h ( n − k ) y_L(n) \sum_{k-\infty}^{\infty} x(k) h(n-k) yL(n)k−∞∑∞x(k)h(n−k) 而N点循环卷积的公式是 y C ( n ) x ( n ) ⊗ h ( n ) ∑ m 0 N − 1 x ( m ) h ( ( n − m ) N ) y_C(n) x(n) \otimes h(n) \sum_{m0}^{N-1} x(m) h((n-m)_N) yC(n)x(n)⊗h(n)m0∑N−1x(m)h((n−m)N) 注意那个 ( ( n − m ) N ) ((n-m)_N) ((n−m)N)它表示对 n − m n-m n−m 的结果进行模N运算即取余数。这就像在一个有N个刻度的时钟上做减法。例如在8点循环卷积中从第1个位置后退3个位置不是到了-2而是到了第6个位置 ( 1 − 3 ) 8 − 2 ( m o d 8 ) 6 (1-3)_8 -2 \pmod 8 6 (1−3)8−2(mod8)6 。
DFT的卷积定理说的是 N点循环卷积对应N点DFT的乘积。 x ( n ) ⊗ h ( n ) ⟷ X ( k ) H ( k ) x(n) \otimes h(n) \longleftrightarrow X(k) H(k) x(n)⊗h(n)⟷X(k)H(k) 这带来了一个巨大的问题。我们通常想计算的是线性卷积但如果我们直接计算两个序列的DFT在频域相乘再做IDFT我们得到的将是循环卷积的结果。如果两个序列的长度不合适循环卷积的结果会因为“周期性”的重叠称为时间混叠而变得面目全非根本不是我们想要的线性卷积。
那么我们还能用DFT来帮助我们计算线性卷积吗 答案是肯定的只要我们使用一个绝妙的技巧——补零Zero-Padding。
假设我们有两个序列 x ( n ) x(n) x(n) 长度为 M M M h ( n ) h(n) h(n) 长度为 P P P。我们知道它们的线性卷积结果 y L ( n ) y_L(n) yL(n) 的长度将是 L M P − 1 L MP-1 LMP−1。
快速线性卷积的正确步骤
确定长度: 计算出线性卷积结果的长度 L M P − 1 L MP-1 LMP−1。补零: 将序列 x ( n ) x(n) x(n) 和 h ( n ) h(n) h(n) 的尾部都补上若干个零使它们的长度都达到 至少为L 的新长度 N N N为了后续FFT算法的效率通常会选择一个大于等于L的2的幂次方作为N。DFT: 对补零后的两个序列做N点DFT得到 X ( k ) X(k) X(k) 和 H ( k ) H(k) H(k)。频域相乘: 计算 Y ( k ) X ( k ) ⋅ H ( k ) Y(k) X(k) \cdot H(k) Y(k)X(k)⋅H(k)。IDFT: 对 Y ( k ) Y(k) Y(k) 做N点IDFT得到最终的结果 y ( n ) y(n) y(n)。
通过补零我们相当于把循环卷积的“时钟”刻度 N 拉得足够长使得在一个周期内翻转后的 h ( n ) h(n) h(n) 与 x ( n ) x(n) x(n) 进行卷积时其“尾部”不会“从时钟的另一头绕回来”污染到“头部”。这样在一个周期内计算出的循环卷积结果就和线性卷积的结果完全一样了。
这个利用DFT及其快速算法FFT来计算线性卷积的方法被称为快速卷积是数字信号处理中最高效的卷积计算方法。
DFT的威力从频谱分析到快速计算
掌握了DFT的定义和核心特性后我们来看看它在实际工程中的两大应用。
应用一数字频谱分析
DFT最直接的应用就是作为一种频谱分析仪。只要我们将一段信号比如一段录音送入计算机对其进行DFT得到的 X ( k ) X(k) X(k) 的幅度 ∣ X ( k ) ∣ |X(k)| ∣X(k)∣ 就告诉了我们这段信号在各个离散频率点 f k k ⋅ f s / N f_k k \cdot f_s / N fkk⋅fs/N 上的能量强度。这就像一个棱镜将混合在一起的白光时域信号分解成赤橙黄绿青蓝紫的彩色光谱频域信号。
然而我们必须清醒地认识到这个“数字棱镜”并非完美它会带来一些由“有限”观测所导致的必然误差
频谱泄漏Spectral Leakage: 我们对信号的观测是有限的这相当于给无限长的原始信号乘上了一个矩形“窗户”。这个操作在频域上会引起卷积使得原本单一频率的尖锐谱线“泄漏”成一个主瓣和多个旁瓣。这会导致我们探测到一些本不存在的频率分量并可能掩盖掉一些微弱的真实信号。选择不同的窗函数如汉宁窗、哈明窗可以在主瓣宽度和旁瓣抑制之间进行权衡以减小泄漏。 (上图展示了频谱泄漏效应。一个理想单频正弦波的频谱左应该是一个尖峰但由于加窗截断其实际DFT频谱右变成了一个有主瓣和多个旁-瓣的形状。)
栅栏效应Picket-Fence Effect: DFT只在N个离散的频率点上对真实频谱进行采样。如果一个信号的真实频率峰值恰好落在了两个采样点之间那么我们在两个采样点上观测到的幅度都将低于真实峰值。这就像我们透过一个栅栏看风景我们只能看到栅栏缝隙里的景象可能会错过最精彩的部分。增加DFT的点数N通过补零可以加密“栅栏”的缝隙更精确地找到峰值位置和大小。
应用二快速卷积的基石
如前文所述利用DFT进行快速卷积是其另一大核心应用。直接计算M点和P点序列的线性卷积其计算复杂度大约是 O ( M ⋅ P ) O(M \cdot P) O(M⋅P)。而利用DFT特别是下一章要讲的FFT算法进行快速卷积其计算复杂度大约是 O ( N log N ) O(N \log N) O(NlogN)其中 N N N 是补零后的长度。当序列很长时FFT方法的效率优势是压倒性的。
想象一下在图像处理中一个512x512的模糊核要对一张1920x1080的图像进行卷积滤波如果用直接法计算那将是天文数字。而利用2D-FFT进行快速卷积则可以在几秒钟内完成。这背后全都是DFT的功劳。
DFT的出现为我们打开了在频域对信号进行处理的大门也为下一章的快速傅里叶变换FFT——这个被誉为20世纪最重要的算法之一——铺平了道路。FFT并不是一种新的变换它只是实现DFT的一种极其高效的算法。没有DFT的理论基础FFT就无从谈起。
总结掌握DFT掌握实践
今天我们踏上了一段从理想到现实的旅程。我们理解到
DFT是为计算机而生的傅里叶变换。它通过对信号时域和频域的同时“离散化”解决了DTFT无法在计算机上实现的问题。DFT是DTFT的采样。N点DFT的本质是在单位圆上对序列的Z变换或DTFT进行N点等间隔采样。DFT的核心“怪癖”是隐含周期性。这导致了时域运算的“循环”特性最典型的就是循环卷积。补零是关键技巧。通过对序列进行恰当的补零我们可以利用DFT的循环卷积定理来高效地计算线性卷积这就是快速卷积的原理。DFT是强大的分析工具。作为数字频谱分析仪它能揭示信号的频率构成但我们也需警惕频谱泄漏和栅栏效应等实践中的问题。
DFT是连接理论与工程的坚固桥梁。掌握了它你就不再仅仅是看着数学公式而是真正拥有了用计算机分析和处理信号的利器。在下一章我们将为这把利器装上一个强力马达——FFT算法让它的威力发挥到极致。 习题
第1题 (概念题)
一位工程师说“我用计算机直接计算了一个信号的DTFT频谱发现它是一个连续的平滑曲线。” 这句话在严格意义上正确吗为什么
第2题 (计算题)
有两个长度为4的序列 x ( n ) { 1 , 2 , 2 , 1 } x(n)\{1, 2, 2, 1\} x(n){1,2,2,1} 和 h ( n ) { 1 , − 1 , 0 , 0 } h(n)\{1, -1, 0, 0\} h(n){1,−1,0,0}。请计算它们的4点循环卷积 y C ( n ) x ( n ) ⊗ h ( n ) y_C(n) x(n) \otimes h(n) yC(n)x(n)⊗h(n)。
第3题 (应用题)
你希望使用DFT以及未来的FFT来计算两个有限长序列的线性卷积。第一个序列 x 1 ( n ) x_1(n) x1(n) 的长度为30个点第二个序列 x 2 ( n ) x_2(n) x2(n) 的长度为20个点。为了得到正确的结果你需要对这两个序列进行补零然后进行DFT。请问你选择的DFT点数N最小应该是多少 答案
第1题答案:
这句话在严格意义上不正确。
原因: 计算机无法直接计算或存储一个真正的连续函数。DTFT的频谱 X ( e j ω ) X(e^{j\omega}) X(ejω) 是一个关于连续变量 ω \omega ω 的函数。这位工程师看到的“连续平滑曲线”实际上是计算了大量点的DFT例如对原信号大量补零后做DFT然后在绘图时将这些密集的离散点用直线连接起来从而在视觉上产生了连续的效果。其本质仍然是离散点而不是真正的连续函数。
第2题答案:
我们可以使用定义法计算。循环卷积 y C ( n ) ∑ m 0 3 x ( m ) h ( ( n − m ) 4 ) y_C(n) \sum_{m0}^{3} x(m) h((n-m)_4) yC(n)∑m03x(m)h((n−m)4)。 y C ( 0 ) x ( 0 ) h ( 0 ) x ( 1 ) h ( − 1 ) 4 x ( 2 ) h ( − 2 ) 4 x ( 3 ) h ( − 3 ) 4 y_C(0) x(0)h(0) x(1)h(-1)_4 x(2)h(-2)_4 x(3)h(-3)_4 yC(0)x(0)h(0)x(1)h(−1)4x(2)h(−2)4x(3)h(−3)4 x ( 0 ) h ( 0 ) x ( 1 ) h ( 3 ) x ( 2 ) h ( 2 ) x ( 3 ) h ( 1 ) x(0)h(0) x(1)h(3) x(2)h(2) x(3)h(1) x(0)h(0)x(1)h(3)x(2)h(2)x(3)h(1) ( 1 ) ( 1 ) ( 2 ) ( 0 ) ( 2 ) ( 0 ) ( 1 ) ( − 1 ) 1 − 1 0 (1)(1) (2)(0) (2)(0) (1)(-1) 1 - 1 \mathbf{0} (1)(1)(2)(0)(2)(0)(1)(−1)1−10 y C ( 1 ) x ( 0 ) h ( 1 ) x ( 1 ) h ( 0 ) x ( 2 ) h ( − 1 ) 4 x ( 3 ) h ( − 2 ) 4 y_C(1) x(0)h(1) x(1)h(0) x(2)h(-1)_4 x(3)h(-2)_4 yC(1)x(0)h(1)x(1)h(0)x(2)h(−1)4x(3)h(−2)4 x ( 0 ) h ( 1 ) x ( 1 ) h ( 0 ) x ( 2 ) h ( 3 ) x ( 3 ) h ( 2 ) x(0)h(1) x(1)h(0) x(2)h(3) x(3)h(2) x(0)h(1)x(1)h(0)x(2)h(3)x(3)h(2) ( 1 ) ( − 1 ) ( 2 ) ( 1 ) ( 2 ) ( 0 ) ( 1 ) ( 0 ) − 1 2 1 (1)(-1) (2)(1) (2)(0) (1)(0) -1 2 \mathbf{1} (1)(−1)(2)(1)(2)(0)(1)(0)−121 y C ( 2 ) x ( 0 ) h ( 2 ) x ( 1 ) h ( 1 ) x ( 2 ) h ( 0 ) x ( 3 ) h ( − 1 ) 4 y_C(2) x(0)h(2) x(1)h(1) x(2)h(0) x(3)h(-1)_4 yC(2)x(0)h(2)x(1)h(1)x(2)h(0)x(3)h(−1)4 x ( 0 ) h ( 2 ) x ( 1 ) h ( 1 ) x ( 2 ) h ( 0 ) x ( 3 ) h ( 3 ) x(0)h(2) x(1)h(1) x(2)h(0) x(3)h(3) x(0)h(2)x(1)h(1)x(2)h(0)x(3)h(3) ( 1 ) ( 0 ) ( 2 ) ( − 1 ) ( 2 ) ( 1 ) ( 1 ) ( 0 ) − 2 2 0 (1)(0) (2)(-1) (2)(1) (1)(0) -2 2 \mathbf{0} (1)(0)(2)(−1)(2)(1)(1)(0)−220 y C ( 3 ) x ( 0 ) h ( 3 ) x ( 1 ) h ( 2 ) x ( 2 ) h ( 1 ) x ( 3 ) h ( 0 ) y_C(3) x(0)h(3) x(1)h(2) x(2)h(1) x(3)h(0) yC(3)x(0)h(3)x(1)h(2)x(2)h(1)x(3)h(0) ( 1 ) ( 0 ) ( 2 ) ( 0 ) ( 2 ) ( − 1 ) ( 1 ) ( 1 ) − 2 1 − 1 (1)(0) (2)(0) (2)(-1) (1)(1) -2 1 \mathbf{-1} (1)(0)(2)(0)(2)(−1)(1)(1)−21−1
所以4点循环卷积的结果是 y C ( n ) { 0 , 1 , 0 , − 1 } y_C(n) \{0, 1, 0, -1\} yC(n){0,1,0,−1}。
第3题答案:
线性卷积结果的长度为 L M P − 1 L M P - 1 LMP−1。 在这里 M 30 M 30 M30, P 20 P 20 P20。 所以线性卷积结果的长度 L 30 20 − 1 49 L 30 20 - 1 49 L3020−149。
为了使用DFT/FFT计算线性卷积而不产生时间混叠补零后的长度即DFT的点数N必须大于或等于线性卷积结果的长度L。 所以DFT点数N的最小值是 49。
在实际应用中为了利用FFT算法的高效性通常会选择大于等于49的第一个2的幂次方即 N 64 N64 N64。
