Chirp-z Transform 1.3 2004/05/19 10:47:47 GMT-5 2004/06/18 10:15:00.017 GMT-5 Douglas L. Jones dl-jones@uiuc.edu Harika Basana ilsai@rice.edu Douglas L. Jones dl-jones@uiuc.edu Kyle Clarkson kclarks@rice.edu z-tranform DFT Efficient scheme for computing samples of the z-transform. (Important special case: DFTs) Let z k A W k , where A Ao θo , W Wo φo . We wish to compute M samples, k 0 1 2 … M 1 of X zk n N 1 0 x n zk n n N 1 0 x n A n W nk

Note that k n 2 n 2 2 n k k 2 n k 1 2 n 2 k 2 k n 2 , So X zk n N 1 0 x n A n W n 2 2 W k 2 2 W k n 2 2 W k 2 2 n N 1 0 x n A n W n 2 2 W k n 2 2 Thus, X zk can be compared by Premultiply x n by A n W n 2 2 , n 0 1 … N 1 to make y n Linearly convolve with W k n 2 2 Post multiply by to get W k 2 2 to get X zk . 1. and 3. require N and M operations respectively. 2. can be performed efficiently using fast convolution.

W n 2 2 is required only for N 1 n M 1 , so this linear convolution can be implemented with L N M 1 FFTs. Wrap W n 2 2 around L when implementing with circular convolution. So, a weird-length DFT can be implemented relatively efficiently using power-of-two algorithms via the chirp-z transform. Also useful for "zoom-FFTs".