動機
週期信號既可以用各時刻的數值描述,也可以用組成它的頻率描述。後一種表示有助研究振盪、濾波及週期微分方程。然而電腦儲存的是有限樣本,不是連續函數。離散傅立葉(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、窗函數、非均勻取樣及數值誤差均需另外研究。這裏的有限恆等式不依賴每個連續傅立葉級數逐點收斂的說法。