<< Chapter < Page | Chapter >> Page > |
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$
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
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".
Notification Switch
Would you like to follow the 'Digital signal processing: a user's guide' conversation and receive update notifications?