3.1 Chirp-z transform

Let $z^k=AW^{-k}$ , where $A=A_{o}e^{i{}_o}$ , $W=W_{o}e^{-(i{}_o)}$ .

We wish to compute $M$ samples, $k$

0 1 2 M 1

Note that $((k-n)^2=n^2-2nk+k^2)\implies (nk=\frac{1}{2}(n^2+k^2-(k-n)^2))$ , So $$X(z_k)=\sum_{n=0}^{N-1} x(n)A^{-n}W^{\left(\frac{n^2}{2}\right)}W^{\left(\frac{k^2}{2}\right)}W^{\left(\frac{-(k-n)^2}{2}\right)}$$ $$W^{\left(\frac{k^2}{2}\right)}\sum_{n=0}^{N-1} x(n)A^{-n}W^{\left(\frac{n^2}{2}\right)}W^{\left(\frac{-(k-n)^2}{2}\right)}$$

Thus, $X(z_k)$ can be compared by

• Premultiply $x(n)$ by $A^{n}W^{\left(\frac{n^2}{2}\right)}$ , $n$
  0 1 N 1
  to make $y(n)$
• Linearly convolve with $W^{\left(\frac{-(k-n)^2}{2}\right)}$
• Post multiply by to get $W^{\left(\frac{k^2}{2}\right)}$ to get $X(z_k)$ .

1. and 3. require $N$ and $M$ operations respectively. 2. can be performed efficiently using fast convolution.

$W^{-\left(\frac{n^2}{2}\right)}$ is required only for $-(N-1)\le n\le M-1$ , so this linear convolution can be implemented with $L\ge N+M-1$ FFTs.

Also useful for "zoom-FFTs".