啁啾-Z轉換(Chirp-Z transform)為離散傅立葉變換(DFT)的一般化,是一種適合於計算當取樣頻率間隔(sampling frequency interval)與取樣時間間隔(sampling time interval)乘積的倒數不等於信號的時頻分佈面積時的演算法,其為利用卷積來實現任意大小的離散傅立葉變換(DFT)的快速傅立葉變換演算法。
具體來說,啁啾-Z轉換沿着對數螺旋輪廓,計算出有限數量的點 zk 的Z轉換,其定義如下:
![{\displaystyle X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}}](//wikimedia.org/api/rest_v1/media/math/render/svg/241800fdadb99ae37f4704f69cf56793e203febc)
![{\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1}](//wikimedia.org/api/rest_v1/media/math/render/svg/1fef365d50bcfbee34843f94c92f70c777be66cb)
其中A為起始點,W為點與點之間的比率,M為需要計算的點的數量。
離散信號
的離散傅立葉變換可以寫成下列的形式
![{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}](//wikimedia.org/api/rest_v1/media/math/render/svg/a86d5a74ea5f39f059809b12d5e332e907025da4)
其中
這項的
可以利用平方式展開得到,如下式所示
![{\displaystyle (n-k)^{2}=n^{2}-2nk+k^{2}\Rightarrow nk=-{\frac {(n-k)^{2}-n^{2}-k^{2}}{2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/6fadcef24a0694f5a15da010444588e3c2e5f8ed)
所以
![{\displaystyle e^{-{\frac {2\pi i}{N}}nk}=e^{{\frac {2\pi i}{N}}{\frac {(n-k)^{2}-n^{2}-k^{2}}{2}}}=e^{{\frac {\pi i}{N}}(n-k)^{2}}e^{-{\frac {\pi i}{N}}n^{2}}e^{-{\frac {\pi i}{N}}k^{2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e678fd540345164210b82c80969f46d672ddc1eb)
而將此平方展開式帶回原式我們可以得到
![{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}(x_{n}e^{-{\frac {\pi i}{N}}n^{2}})e^{{\frac {\pi i}{N}}(n-k)^{2}}\qquad k=0,\dots ,N-1.}](//wikimedia.org/api/rest_v1/media/math/render/svg/ccaae8129273fdaa230294e0aea75b4637df0191)
上面的累加結果恰為兩個序列 an 及 bn 的卷積,兩序列的定義如下:
![{\displaystyle a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/4eccd02c72465fed87eb47dc39f2368b3360a2cf)
![{\displaystyle b_{n}=e^{{\frac {\pi i}{N}}n^{2}},}](//wikimedia.org/api/rest_v1/media/math/render/svg/96566700b35af7bcd73c5c53142ca835ffbd69ef)
而產生的卷積結果會再乘上 N 個相位的參數 bk*:
![{\displaystyle X_{k}=b_{k}^{*}\sum _{n=0}^{N-1}a_{n}b_{k-n}\qquad k=0,\dots ,N-1.}](//wikimedia.org/api/rest_v1/media/math/render/svg/4f0b7d93de64689feb1ea5d3e836846e64d00123)
因此離散信號
的離散傅立葉變換現在可以分成三個步驟來實現:
- STEP 1:對於信號
的每一個取樣點都乘上![{\displaystyle e^{-{\frac {\pi i}{N}}n^{2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/eac9b011ae1c25c009e7520b0c1ddf789e511724)
- STEP 2:接着再與
做線性卷積
- STEP 3:最後乘上
![{\displaystyle e^{-{\frac {\pi i}{N}}k^{2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/698e78cbf4a6dab6149cf3c2a1e60ea554e11968)
如此即可得到不同頻率成分的
。
此卷積動作可以透過卷積理論所實現,其中,由於這些快速傅立葉轉換結果的長度 N 不同,導致我們必須透過補零的方式,將快速傅立葉轉換的結果補至長度大於或等於 2N - 1,才能精確計算其卷積結果。此外,布魯斯坦演算法提供一個時間複雜度為 O(N log N) 的方式計算質數大小的離散傅立葉轉換。
在布魯斯坦演算法的卷積過程中使用補零的方式是值得討論的。如果我們將訊號補至長度為 M ≥ 2N–1,代表 an 被擴展至長度為 M 的陣列 An,其中當 0 ≤ n < N 時,An = an,否則 An = 0。然而,基於卷積中的 bk–n 項, bn 需要 n 的正值和負值。在陣列中補零的離散傅立葉轉換的周期性邊界,代表着 -n 等於 M - n。因此,bn 被擴展到長度為 M 的陣列 Bn,其中 B0 = b0,Bn = BM–n = bn(當 0 < n <),否則,Bn = 0。然後根據通常的捲積定理對 A 和 B 進行快速傅立葉轉換,逐點相乘,並進行逆快速傅立葉轉換以獲得 a 和 b 的卷積。
讓我們更準確地說明,布魯斯坦演算法的離散傅立葉轉換需要什麼類型的捲積。如果序列 bn 在具有周期 N 的 n 中是具有周期性的,那麼它將是長度為 N 的循環卷積,並且,為了計算上的方便而使用補零的方式。但是,通常情況並非如此:
![{\displaystyle b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}e^{{\frac {\pi i}{N}}(2Nn+N^{2})}=(-1)^{N}b_{n}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/110e0f5e742f2e1368a4adb4faa308f6c2370e28)
因此,當 N 為偶數時,卷積是具有週期性的,但在這種情況下,人們通常使用更有效率的快速傅立葉轉換演算法,例如Cooley-Tukey演算法;反之,當 N 為奇數時,bn 是反週期性的,並且具有長度 N 的負循環卷積。然而,當如上所述,使用補零的方式江陣列補到至少 2N−1 的長度時,兩者之間的差異消失。
上述提到的布魯斯坦演算法也可以基於單方面的Z轉換,用以計算更一般化的轉換(Rabiner et al, 1969),特別是具有以下形式的轉換:
![{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}](//wikimedia.org/api/rest_v1/media/math/render/svg/2a45e8ba154c6d1f3aff5908a8b9203732af4d99)
其中 z 為任意複數,N以及M分別為輸入及輸出的數量。
由前面所提到的布魯斯坦演算法,我們可以進行如此的轉換。例如,獲得訊號某一部分頻譜中的內插值,以及在傳遞函數分析中增加任意極點,皆為其應用之一。
該演算法被稱為啁啾-Z轉換演算法,是因為在傅立葉轉換的情境(|z| = 1)下,一序列 bn 是一複數正弦波,而在雷達系統中則被稱作「啁啾」。
- Jian-Jiun Ding, class lecture of Time Frequency Analysis and Wavelet transform, Graduate Institute of Communication Engineering, National Taiwan University, Taipei, Taiwan, 2007.
- Jian-Jiun Ding, class lecture of Time Frequency Analysis and Wavelet transform, Graduate Institute of Communication Engineering, National Taiwan University, Taipei, Taiwan, 2018.
- http://cnx.org/content/m12013/latest/(頁面存檔備份,存於互聯網檔案館)