Connexions

You are here: Home » Content » Chirp-z Transform
Content Actions

Chirp-z Transform

Module by: Douglas L. Jones

Summary: Efficient scheme for computing samples of the z-transform. (Important special case: DFTs)

Let zk=AW-k z k A W k , where A=Aoⅇⅈθo A Ao θo , W=Woⅇ-ⅈφo W Wo φo .
We wish to compute MM samples, k=012…M-1 k 0 1 2 … M 1 of Xzk=∑n=0N-1xnzk-n=∑n=0N-1xnA-nWnk X zk n N 1 0 x n zk n n N 1 0 x n A n W nk
figure3.png
Figure 1
Note that k-n2=n2-2nk+k2⇒nk=12n2+k2-k-n2 k n 2 n 2 2 n k k 2 n k 1 2 n 2 k 2 k n 2 , So Xzk=∑n=0N-1xnA-nWn22Wk22W-k-n22 X zk n N 1 0 x n A n W n 2 2 W k 2 2 W k n 2 2 =Wk22∑n=0N-1xnA-nWn22W-k-n22 W k 2 2 n N 1 0 x n A n W n 2 2 W k n 2 2
Thus, Xzk X zk can be compared by
  1. Premultiply xn x n by AnWn22 A n W n 2 2 , n= 0 1 …N-1 n 0 1 … N 1 to make yn y n
  2. Linearly convolve with W-k-n22 W k n 2 2
  3. Post multiply by to get Wk22 W k 2 2 to get Xzk X zk .
1. and 3. require NN and MM operations respectively. 2. can be performed efficiently using fast convolution.
figure8.png
Figure 2
W-n22 W n 2 2 is required only for -N-1≤n≤M-1 N 1 n M 1 , so this linear convolution can be implemented with L≥N+M-1 L N M 1 FFTs.
note: Wrap W-n22 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".

Comments, questions, feedback, criticisms?

Send feedback