动机
周期信号既可以用各时刻的数值描述,也可以用组成它的频率描述。后一种表示有助研究振荡、滤波及周期微分方程。然而计算机存储的是有限样本,不是连续函数。离散傅里叶(Fourier)变换(DFT)是有限维向量空间的坐标变换;快速傅里叶变换(FFT)是计算同一变换的高效算法。两者都不能自动恢复采样时丢失的所有信息。
我们固定指数的正负号和归一化惯例。其他软件可能在正变换乘 1 / N 1/N 1/ N ,或将系数平均分配给正逆变换;只要逆变换配合,数学结论相同。
定义
对可积的 2 π 2\pi 2 π 周期函数,其复傅里叶系数为 c k = ( 2 π ) − 1 ∫ 0 2 π f ( t ) e − i k t d t c_k=(2\pi)^{-1}\int_0^{2\pi}f(t)e^{-ikt}\,dt c k = ( 2 π ) − 1 ∫ 0 2 π f ( t ) e − ik t d t 。对样本 x 0 , … , x N − 1 ∈ C x_0,\ldots,x_{N-1}\in\mathbb C x 0 , … , x N − 1 ∈ C ,定义
X k = ∑ j = 0 N − 1 x j e − 2 π i j k / N , k = 0 , … , N − 1. X_k=\sum_{j=0}^{N-1}x_j e^{-2\pi i jk/N},\qquad k=0,\ldots,N-1. X k = j = 0 ∑ N − 1 x j e − 2 π ij k / N , k = 0 , … , N − 1. X X X 的指标按模 N N N 理解;即使没有指定连续信号,DFT 仍是一个有限和。
对所有整数 j j j ,e 2 π i m j / N e^{2\pi i mj/N} e 2 π imj / N 与 e 2 π i ( m + N ) j / N e^{2\pi i(m+N)j/N} e 2 π i ( m + N ) j / N 相同,故指标表示频率的同余类。若输入为实数,直接对和式取共轭得 X N − k = X k ‾ X_{N-k}=\overline{X_k} X N − k = X k ;任意复数输入则未必有此性质。
主要结果
对整数 m m m ,若 N N N 整除 m m m ,则 ∑ j = 0 N − 1 e 2 π i j m / N = N \sum\limits_{j=0}^{N-1}e^{2\pi i jm/N}=N j = 0 ∑ N − 1 e 2 π ij m / N = N ;否则该和为零。因此反 DFT 为
x j = 1 N ∑ k = 0 N − 1 X k e 2 π i j k / N . x_j=\frac1N\sum_{k=0}^{N-1}X_k e^{2\pi i jk/N}. x j = N 1 k = 0 ∑ N − 1 X k e 2 π ij k / N .
若 N N N 整除 m m m ,每项均为一。否则公比 q = e 2 π i m / N ≠ 1 q=e^{2\pi i m/N}\ne1 q = e 2 π im / N = 1 ,但 q N = 1 q^N=1 q N = 1 ,故等比和 ( 1 − q N ) / ( 1 − q ) = 0 (1-q^N)/(1-q)=0 ( 1 − q N ) / ( 1 − q ) = 0 。把正变换代入反变换并交换有限和,正交性只留下与 j j j 模 N N N 相同的样本,结果即 x j x_j x j 。
对 x , y ∈ C N x,y\in\mathbb C^N x , y ∈ C N 定义 ( x ∗ y ) j = ∑ m = 0 N − 1 x m y ( j − m ) m o d N (x*y)_j=\sum\limits_{m=0}^{N-1}x_m y_{(j-m)\bmod N} ( x ∗ y ) j = m = 0 ∑ N − 1 x m y ( j − m ) mod N ,则其 DFT 为 X k Y k X_kY_k X k Y k 。
将卷积代入 DFT,并以模 N N N 变量 ℓ = j − m \ell=j-m ℓ = j − m 换元。当 j j j 遍历所有剩余类,ℓ \ell ℓ 也是如此。指数因子分解为 e − 2 π i m k / N e − 2 π i ℓ k / N e^{-2\pi i mk/N}e^{-2\pi i\ell k/N} e − 2 π imk / N e − 2 π i ℓ k / N ,两个有限和便分别为 X k X_k X k 、Y k Y_k Y k 。模运算不可忽略:DFT 相乘得到的是循环卷积,而非自动得到普通线性卷积。
例题
取 x = ( 1 , 2 , 1 , 0 ) x=(1,2,1,0) x = ( 1 , 2 , 1 , 0 ) ,直接代入得 X 0 = 4 X_0=4 X 0 = 4 、X 1 = − 2 i X_1=-2i X 1 = − 2 i 、X 2 = 0 X_2=0 X 2 = 0 、X 3 = 2 i X_3=2i X 3 = 2 i 。例如 X 1 = 1 + 2 ( − i ) + 1 ( − 1 ) + 0 ( i ) = − 2 i X_1=1+2(-i)+1(-1)+0(i)=-2i X 1 = 1 + 2 ( − i ) + 1 ( − 1 ) + 0 ( i ) = − 2 i 。反变换在 j = 1 j=1 j = 1 给 ( 4 + ( − 2 i ) i + 0 + ( 2 i ) ( − i ) ) / 4 = 2 (4+(-2i)i+0+(2i)(-i))/4=2 ( 4 + ( − 2 i ) i + 0 + ( 2 i ) ( − i )) /4 = 2 。共轭配对反映输入为实数。
在 t j = 2 π j / 8 t_j=2\pi j/8 t j = 2 π j /8 处,e 2 i t e^{2it} e 2 i t 与 e 10 i t e^{10it} e 10 i t 均等于 e 2 π i ( 2 ) j / 8 e^{2\pi i(2)j/8} e 2 π i ( 2 ) j /8 。两者的八个样本完全相同,所以只看这些样本的算法无法判断原本是哪个频率。频率 2 2 2 与 10 10 10 属同一剩余类;要唯一辨别连续频率,必须加入频带限制或其他先验信息。
令 x = y = ( 1 , 1 , 0 ) x=y=(1,1,0) x = y = ( 1 , 1 , 0 ) ,N = 3 N=3 N = 3 ,循环卷积为 ( 1 , 2 , 1 ) (1,2,1) ( 1 , 2 , 1 ) ;普通乘积多项式次数为二,所以没有回绕。若 N = 2 N=2 N = 2 且 x = y = ( 1 , 1 ) x=y=(1,1) x = y = ( 1 , 1 ) ,循环卷积为 ( 2 , 2 ) (2,2) ( 2 , 2 ) ,因次数二的系数回绕至零号位置;普通线性卷积是 ( 1 , 2 , 1 ) (1,2,1) ( 1 , 2 , 1 ) 。将长度 p p p 、q q q 的序列补零至 N ≥ p + q − 1 N\ge p+q-1 N ≥ p + q − 1 ,可防止非零线性卷积范围内的回绕。
概念视角 代数
在单位根处求多项式的值 把样本配成多项式 P ( z ) = ∑ j = 0 N − 1 x j z j P(z)=\sum\limits_{j=0}^{N-1}x_jz^j P ( z ) = j = 0 ∑ N − 1 x j z j 。设 ω N = e − 2 π i / N \omega_N=e^{-2\pi i/N} ω N = e − 2 π i / N ,则 X k = P ( ω N k ) X_k=P(\omega_N^k) X k = P ( ω N k ) :DFT 就是在 N N N 个不同的 N N N 次单位根处求 P P P 的值,而逆 DFT 是由这些值插值。由于每个节点都有 z N = 1 z^N=1 z N = 1 ,循环卷积就是模 z N − 1 z^N-1 z N − 1 的多项式乘法,这正是卷积定理;把长度为 p p p 、q q q 的序列补零到 N ≥ p + q − 1 N\ge p+q-1 N ≥ p + q − 1 使乘积次数太小而不会绕回。下文的基二拆分就是 P ( z ) = P e ( z 2 ) + z P o ( z 2 ) P(z)=P_{\mathrm e}(z^2)+z\,P_{\mathrm o}(z^2) P ( z ) = P e ( z 2 ) + z P o ( z 2 ) 。
方法与推理
写 ω N = e − 2 π i / N \omega_N=e^{-2\pi i/N} ω N = e − 2 π i / N 。快速算法建立在一个恒等式上:它把偶数长度的变换拆成两个一半长度的变换。
设 N N N 为偶数,E E E 与 O O O 分别为 ( x 0 , x 2 , … , x N − 2 ) (x_0,x_2,\ldots,x_{N-2}) ( x 0 , x 2 , … , x N − 2 ) 和 ( x 1 , x 3 , … , x N − 1 ) (x_1,x_3,\ldots,x_{N-1}) ( x 1 , x 3 , … , x N − 1 ) 的长度为 N / 2 N/2 N /2 的 DFT。对 0 ≤ k < N / 2 0\le k\lt N/2 0 ≤ k < N /2 ,
X k = E k + ω N k O k , X k + N / 2 = E k − ω N k O k . X_k=E_k+\omega_N^kO_k,\qquad X_{k+N/2}=E_k-\omega_N^kO_k. X k = E k + ω N k O k , X k + N /2 = E k − ω N k O k . 若 N = 2 m N=2^m N = 2 m ,递归拆分到长度一,就能用 ( N / 2 ) log 2 N (N/2)\log_2N ( N /2 ) log 2 N 次旋转因子复数乘法和 N log 2 N N\log_2N N log 2 N 次复数加法算出 DFT。
由 ω N 2 r k = ω N / 2 r k \omega_N^{2rk}=\omega_{N/2}^{rk} ω N 2 r k = ω N /2 r k ,把偶数与奇数位置分开得
X k = ∑ r = 0 N / 2 − 1 x 2 r ω N / 2 r k + ω N k ∑ r = 0 N / 2 − 1 x 2 r + 1 ω N / 2 r k . X_k=\sum_{r=0}^{N/2-1}x_{2r}\omega_{N/2}^{rk}
+\omega_N^k\sum_{r=0}^{N/2-1}x_{2r+1}\omega_{N/2}^{rk}. X k = r = 0 ∑ N /2 − 1 x 2 r ω N /2 r k + ω N k r = 0 ∑ N /2 − 1 x 2 r + 1 ω N /2 r k . 设两个长度 N / 2 N/2 N /2 的变换分别为 E k E_k E k 和 O k O_k O k 。由周期性及 ω N k + N / 2 = − ω N k \omega_N^{k+N/2}=-\omega_N^k ω N k + N /2 = − ω N k ,对 0 ≤ k < N / 2 0\le k<N/2 0 ≤ k < N /2 得到蝶形计算 X k = E k + ω N k O k X_k=E_k+\omega_N^kO_k X k = E k + ω N k O k 和 X k + N / 2 = E k − ω N k O k X_{k+N/2}=E_k-\omega_N^kO_k X k + N /2 = E k − ω N k O k 。在精确算术中,这只是重新排列,没有引入近似。
计数方面,设 M ( N ) M(N) M ( N ) 与 A ( N ) A(N) A ( N ) 为旋转因子乘法和加法的次数,并有 M ( 1 ) = A ( 1 ) = 0 M(1)=A(1)=0 M ( 1 ) = A ( 1 ) = 0 ,因为长度为一的 DFT 是恒等映射。每一层用 N / 2 N/2 N /2 次乘法 ω N k O k \omega_N^kO_k ω N k O k (每个乘积供两个输出使用),以及 N N N 次加减法,故 M ( N ) = 2 M ( N / 2 ) + N / 2 M(N)=2M(N/2)+N/2 M ( N ) = 2 M ( N /2 ) + N /2 、A ( N ) = 2 A ( N / 2 ) + N A(N)=2A(N/2)+N A ( N ) = 2 A ( N /2 ) + N 。对 m m m 归纳得 M ( 2 m ) = m 2 m − 1 M(2^m)=m2^{m-1} M ( 2 m ) = m 2 m − 1 、A ( 2 m ) = m 2 m A(2^m)=m2^m A ( 2 m ) = m 2 m :确实 2 ( m − 1 ) 2 m − 2 + 2 m − 1 = m 2 m − 1 2(m-1)2^{m-2}+2^{m-1}=m2^{m-1} 2 ( m − 1 ) 2 m − 2 + 2 m − 1 = m 2 m − 1 ,且 2 ( m − 1 ) 2 m − 1 + 2 m = m 2 m 2(m-1)2^{m-1}+2^m=m2^m 2 ( m − 1 ) 2 m − 1 + 2 m = m 2 m 。直接计算全部 N N N 个和需要 O ( N 2 ) O(N^2) O ( N 2 ) 次运算。
证明透视
为什么每个半长变换用了两次 正确性用到单位根的两个事实,分别在两处。恒等式 ω N 2 = ω N / 2 \omega_N^2=\omega_{N/2} ω N 2 = ω N /2 把偶数下标与奇数下标的和变成真正的长度为 N / 2 N/2 N /2 的 DFT。关键一步是周期性:E E E 与 O O O 关于 k k k 的周期为 N / 2 N/2 N /2 ,故 E k + N / 2 = E k E_{k+N/2}=E_k E k + N /2 = E k 、O k + N / 2 = O k O_{k+N/2}=O_k O k + N /2 = O k ,而 ω N N / 2 = − 1 \omega_N^{N/2}=-1 ω N N /2 = − 1 使旋转因子变号。因此同一对 ( E k , O k ) (E_k,O_k) ( E k , O k ) 同时给出 X k X_k X k 与 X k + N / 2 X_{k+N/2} X k + N /2 ,工作量减半正是来自这种重用。递归会终止,因为每一层长度减半;到长度一时 DFT 是恒等映射,论证在这里闭合。每一层都用到 N N N 为偶数;N = 2 m N=2^m N = 2 m 时这一直成立,计数因此简洁。其他长度会在奇数因子处停止拆分,需要另一种分解。
原位实现仍须处理下标次序、临时存储、舍入和归一化。FFT 不是另一种变换,基二也不是唯一算法。
考虑周期边界条件下的 − u ′ ′ = f -u''=f − u ′′ = f 。对光滑周期解,其系数满足 k 2 u k = f k k^2u_k=f_k k 2 u k = f k ;k ≠ 0 k\ne0 k = 0 时 u k = f k / k 2 u_k=f_k/k^2 u k = f k / k 2 。零频率要求 f 0 = 0 f_0=0 f 0 = 0 ,而 u 0 u_0 u 0 仍可任意选,直至指定平均值。这个连续傅里叶论证不能混同于任意有限差分系统:离散导数有自己的频率乘子。例如周期中心二阶差分的 − D h 2 -D_h^2 − D h 2 乘子为 4 sin 2 ( π k / N ) / h 2 4\sin^2(\pi k/N)/h^2 4 sin 2 ( π k / N ) / h 2 ,并不恰等于 ( 2 π k / L ) 2 (2\pi k/L)^2 ( 2 π k / L ) 2 。
基向量与能量
令 v k v_k v k 的第 j j j 项为 e 2 π i j k / N e^{2\pi i jk/N} e 2 π ij k / N 。离散正交性表明这些向量在复内积下互相正交,且每个范数平方为 N N N 。C N \mathbb C^N C N 中有 N N N 个非零正交向量,故构成一组基。反 DFT 将样本向量展开成这组基,系数为 X k / N X_k/N X k / N ;因此精确 DFT 不会丢失有限样本信息。
能量恒等式 ∑ j ∣ x j ∣ 2 = N − 1 ∑ k ∣ X k ∣ 2 \sum\limits_j|x_j|^2=N^{-1}\sum\limits_k|X_k|^2 j ∑ ∣ x j ∣ 2 = N − 1 k ∑ ∣ X k ∣ 2 由正交展开得出,系数 1 / N 1/N 1/ N 取决于我们的归一化。若正逆变换都乘 1 / N 1/\sqrt N 1/ N ,矩阵便是酉矩阵,两边平方和相等。必须计算完整复频谱,包括高指标代表的负频率;删去一半而不调整共轭配对会改变总能量。
连续级数的采样
为了严格交换求和,假设 f ( t ) = ∑ m ∈ Z c m e i m t f(t)=\sum\limits_{m\in\mathbb Z}c_m e^{imt} f ( t ) = m ∈ Z ∑ c m e im t 且 ∑ m ∣ c m ∣ < ∞ \sum\limits_m|c_m|<\infty m ∑ ∣ c m ∣ < ∞ 。在 t j = 2 π j / N t_j=2\pi j/N t j = 2 π j / N 采样,代入并用离散正交性可得
X k N = ∑ ℓ ∈ Z c k + ℓ N . \frac{X_k}{N}=\sum_{\ell\in\mathbb Z}c_{k+\ell N}. N X k = ℓ ∈ Z ∑ c k + ℓ N .
每个计算频格把同一同余类的所有连续系数相加,这是混叠的明确公式。绝对收敛保证交换无限和与有限和合法;没有此条件便须另行指定收敛意义。若已知频带且每个同余类最多一个非零系数,便可避免这种碰撞。
当实数输入且 N N N 为偶数,零频格与 N / 2 N/2 N /2 频格都是自己的共轭伴侣,因此为实数;其他频格以 k k k 和 N − k N-k N − k 配对。样本 ( − 1 ) j (-1)^j ( − 1 ) j 位于 Nyquist 频格。此边界的正负代表在样本上重合,不能当成两个独立测量。常见采样率规则依赖假设的频带和端点惯例,并非 FFT 本身的性质。
完整蝶形计算
取 x = ( 1 , 2 , 1 , 0 ) x=(1,2,1,0) x = ( 1 , 2 , 1 , 0 ) ,偶数子序列为 ( 1 , 1 ) (1,1) ( 1 , 1 ) ,奇数子序列为 ( 2 , 0 ) (2,0) ( 2 , 0 ) ;其二点变换分别为 E = ( 2 , 0 ) E=(2,0) E = ( 2 , 0 ) 、O = ( 2 , 2 ) O=(2,2) O = ( 2 , 2 ) 。因 ω 4 = − i \omega_4=-i ω 4 = − i ,k = 0 k=0 k = 0 的蝶形给 X 0 = 2 + 2 = 4 X_0=2+2=4 X 0 = 2 + 2 = 4 、X 2 = 2 − 2 = 0 X_2=2-2=0 X 2 = 2 − 2 = 0 ;k = 1 k=1 k = 1 给 X 1 = 0 − i ( 2 ) = − 2 i X_1=0-i(2)=-2i X 1 = 0 − i ( 2 ) = − 2 i 、X 3 = 0 + i ( 2 ) = 2 i X_3=0+i(2)=2i X 3 = 0 + i ( 2 ) = 2 i 。两个结果共用同一中间变换,这正是加速的来源。
若长度不是二的幂,上述等分递归不能只靠相同的二分一直做到一;其他分解、小型直接变换或其他 FFT 算法仍可处理。补零会改变长度及频率格点,是有数学影响的计算选择,并不表示原始序列多了样本。
循环移位与滤波
设 s s s 为整数移位,令 y j = x ( j − s ) m o d N y_j=x_{(j-s)\bmod N} y j = x ( j − s ) mod N 。对有限 DFT 和式换元得 Y k = e − 2 π i s k / N X k Y_k=e^{-2\pi i sk/N}X_k Y k = e − 2 π i s k / N X k 。移位改变相位,但 ∣ X k ∣ |X_k| ∣ X k ∣ 不变。因此单靠幅值一般无法恢复原来的样本位置:即使把非常数序列移位,幅值仍然相同。在滤波器中,把 X k X_k X k 乘以指定增益,按卷积定理相当于与这些增益的反 DFT 作循环卷积。若目标是对有限记录作线性滤波,必须说明适当的补零与边界处理。
在适当光滑及可分部积分的假设下,周期函数微分会把第 k k k 个连续傅里叶系数乘以 i k ik ik 。高频被放大,所以微分可能放大高频噪声。反过来,积分把非零频率除以 i k ik ik ,却不能决定平均值;要存在周期原函数,被积函数须有零平均值,而原函数的加法常数另行指定。这些性质是傅里叶方法的动机,但不能免除截断及测量噪声的问题。
有限观测窗造成的泄漏
DFT 将有限样本列表视为周期离散序列的一个周期。若记录中的正弦波在观测区间内没有完成整数个周期,其周期延拓在边界就不匹配,能量随之散布到多个频格。这称为频谱泄漏,并非变换出错:变换精确地表示了它所接收的有限列表。
窗函数在变换前把记录乘以选定的权重,目的是控制边界的过渡,以较宽的主瓣换取较低的旁瓣。窗函数也会改变幅值,所以估计振幅时需要该窗的归一化。不存在与测量目的无关、普遍最佳的窗。若两个频率很接近,记录长度、噪声及窗函数都有影响;单凭插值后的图像不能确定两者可被区分。
由共轭频格重建
设 N = 4 N=4 N = 4 、x j = cos ( 2 π j / 4 ) x_j=\cos(2\pi j/4) x j = cos ( 2 π j /4 ) ,即 ( 1 , 0 , − 1 , 0 ) (1,0,-1,0) ( 1 , 0 , − 1 , 0 ) 。Euler 公式把样本写成正频率向量的一半加负频率向量的一半,因此 X 1 = X 3 = 2 X_1=X_3=2 X 1 = X 3 = 2 ,其余频格为零。用反变换重建得
x j = 1 4 ( 2 e 2 π i j / 4 + 2 e − 2 π i j / 4 ) = cos ( 2 π j / 4 ) . x_j=\frac14(2e^{2\pi ij/4}+2e^{-2\pi ij/4})=\cos(2\pi j/4). x j = 4 1 ( 2 e 2 π ij /4 + 2 e − 2 π ij /4 ) = cos ( 2 π j /4 ) .
因此在这个约定下,实余弦出现在两个频格。任一频格中的值 2 2 2 本身并不是余弦的振幅;除以 N N N 得复系数 1 / 2 1/2 1/2 ,再与其共轭伴侣合并才还原振幅一。零频及 Nyquist 频率没有不同的伴侣,所以不能盲目套用同一加倍规则。
滤波与零频模态
权重为 ( 1 / 2 , 1 / 2 , 0 , … , 0 ) (1/2,1/2,0,\ldots,0) ( 1/2 , 1/2 , 0 , … , 0 ) 的循环平均,频率响应是 H k = ( 1 + e − 2 π i k / N ) / 2 H_k=(1+e^{-2\pi ik/N})/2 H k = ( 1 + e − 2 π ik / N ) /2 ,其幅值为 ∣ cos ( π k / N ) ∣ |\cos(\pi k/N)| ∣ cos ( π k / N ) ∣ 。因 H 0 = 1 H_0=1 H 0 = 1 ,它保留平均值;若 N N N 为偶数,H N / 2 = 0 H_{N/2}=0 H N /2 = 0 ,交替的 Nyquist 分量被消去。它也改变相位,反映两个权重的位置不对称。这个有限例子说明,频率乘子的反变换同时描述了数值滤波器及其边界约定。
概念视角 算法
FFT 是线性映射的分解 DFT 矩阵有 N 2 N^2 N 2 个元素,但奇偶恒等式将其作用分解成两个较小变换和稀疏蝶形运算。每层先以排列聚集奇偶样本,两个子变换独立计算,再用旋转因子组合成对输出。精确算术下,这些稀疏阶段的乘积等于原本 DFT 矩阵。此观点解释加速原因,也指出实现中排序和舍入误差出现的位置;变换本身没有改变。
常见误解
未指定采样间距之前,DFT 频格并不是物理频率。采样间距为 Δ t \Delta t Δ t 时,第 k k k 格可表示每单位时间 k / ( N Δ t ) k/(N\Delta t) k / ( N Δ t ) 个周期;对高下标频格,负频率代表 ( k − N ) / ( N Δ t ) (k-N)/(N\Delta t) ( k − N ) / ( N Δ t ) 可能才有物理意义。
对实数数据,振幅为一、位于第 k k k 格的余弦在第 k k k 与第 N − k N-k N − k 格各出现 N / 2 N/2 N /2 ,所以单侧振幅是 ∣ X k ∣ / N |X_k|/N ∣ X k ∣/ N 的两倍。第零格以及(N N N 为偶数时)第 N / 2 N/2 N /2 格没有另一个配对:常数序列 x j = 1 x_j=1 x j = 1 给出 X 0 = N X_0=N X 0 = N ,若加倍就会报告振幅为二。
周期延拓不连续时傅里叶系数可能缓慢衰减,端点不匹配也会造成泄漏。快速计算和光滑图像都不能证明采样充分。
反例模式
补零不能消除混叠 断言:把采样记录补零到更长,就能显示原网格无法分辨的频率。取 e 2 i t e^{2it} e 2 i t 与 e 10 i t e^{10it} e 10 i t 在 t j = 2 π j / 8 t_j=2\pi j/8 t j = 2 π j /8 处的八个样本。由于 e 10 i t j = e 2 i t j e 8 i t j = e 2 i t j e^{10it_j}=e^{2it_j}e^{8it_j}=e^{2it_j} e 10 i t j = e 2 i t j e 8 i t j = e 2 i t j ,两者完全相同。各补上八个零后得到两个相同的长度为十六的序列,因此十六点变换也相同。任何处理补零数据的方法都不能把两个信号分开。补零只是在有限记录的变换上插值;要分开两个频率,需要更细网格上的新样本或已知的频带限制。
快速检查
快速检查
(计算常数序列 x j = 3 x_j=3 x j = 3 (j = 0 , … , N − 1 j=0,\ldots,N-1 j = 0 , … , N − 1 )的 DFT,并验证逆变换。)
解答 · 答案 由离散正交性,X k = 3 ∑ j e − 2 π i j k / N X_k=3\sum\limits_je^{-2\pi ijk/N} X k = 3 j ∑ e − 2 π ij k / N 在 k = 0 k=0 k = 0 时为 3 N 3N 3 N ,其他频格为零。逆变换给出每个 j j j 都有 x j = N − 1 ⋅ 3 N = 3 x_j=N^{-1}\cdot3N=3 x j = N − 1 ⋅ 3 N = 3 。
习题
快速检查
(用上述约定计算 ( 1 , 0 , − 1 , 0 ) (1,0,-1,0) ( 1 , 0 , − 1 , 0 ) 的四点 DFT。)
解答 · 答案 这里 X k = 1 − ω 4 2 k = 1 − ( − 1 ) k X_k=1-\omega_4^{2k}=1-(-1)^k X k = 1 − ω 4 2 k = 1 − ( − 1 ) k ,故四个值为 ( 0 , 2 , 0 , 2 ) (0,2,0,2) ( 0 , 2 , 0 , 2 ) 。例如 X 1 = 1 + ( − 1 ) ( − 1 ) = 2 X_1=1+(-1)(-1)=2 X 1 = 1 + ( − 1 ) ( − 1 ) = 2 。
快速检查
(证明 ∑ j = 0 N − 1 ∣ x j ∣ 2 = N − 1 ∑ k = 0 N − 1 ∣ X k ∣ 2 \sum\limits_{j=0}^{N-1}|x_j|^2=N^{-1}\sum\limits_{k=0}^{N-1}|X_k|^2 j = 0 ∑ N − 1 ∣ x j ∣ 2 = N − 1 k = 0 ∑ N − 1 ∣ X k ∣ 2 。)
解答 · 答案 代入 X k = ∑ j x j ω N j k X_k=\sum\limits_jx_j\omega_N^{jk} X k = j ∑ x j ω N j k ,展开 ∣ X k ∣ 2 = ∑ j , ℓ x j x ℓ ‾ ω N ( j − ℓ ) k |X_k|^2=\sum\limits_{j,\ell}x_j\overline{x_\ell}\omega_N^{(j-\ell)k} ∣ X k ∣ 2 = j , ℓ ∑ x j x ℓ ω N ( j − ℓ ) k 并对 k k k 求和。正交性消去所有 j ≠ ℓ j\ne\ell j = ℓ 的交叉项,剩下 N ∑ j ∣ x j ∣ 2 N\sum\limits_j|x_j|^2 N j ∑ ∣ x j ∣ 2 。
快速检查
(在八个等距点上,哪个小于八的非负下标与频率 − 1 -1 − 1 有相同样本?解释原因。)
解答 · 答案 是 7 7 7 ,因为 − 1 ≡ 7 ( m o d 8 ) -1\equiv7\pmod8 − 1 ≡ 7 ( mod 8 ) ;对每个整数 j j j 都有 e − 2 π i j / 8 = e − 2 π i j / 8 e 2 π i j = e 2 π i 7 j / 8 e^{-2\pi ij/8}=e^{-2\pi ij/8}e^{2\pi ij}=e^{2\pi i7j/8} e − 2 π ij /8 = e − 2 π ij /8 e 2 π ij = e 2 π i 7 j /8 。
快速检查
(求 ( 1 , 2 , 0 ) (1,2,0) ( 1 , 2 , 0 ) 与 ( 1 , 0 , 1 ) (1,0,1) ( 1 , 0 , 1 ) 的长度为三的循环卷积,并与普通线性卷积比较。)
解答 · 答案 用模三下标计算得 ( 3 , 2 , 1 ) (3,2,1) ( 3 , 2 , 1 ) 。普通卷积为 ( 1 , 2 , 1 , 2 ) (1,2,1,2) ( 1 , 2 , 1 , 2 ) ;最后的系数回绕加到零号位置,那里得到 1 + 2 = 3 1+2=3 1 + 2 = 3 。这说明线性卷积须补零到长度至少 3 + 3 − 1 = 5 3+3-1=5 3 + 3 − 1 = 5 。
延伸学习
傅里叶级数收敛、离散余弦变换、多维 FFT、窗函数、非均匀采样及数值误差均需另外研究。这里的有限恒等式不依赖每个连续傅里叶级数逐点收敛的说法。