Efficient scheme for computing samples of the z-transform. (Important special case: DFTs)
Let
, where
,
.
We wish to compute
samples,
of
Note that
, So
Thus,
can be compared by
- Premultiply
by
,
to make
- Linearly convolve with
- Post multiply by to get
to get
.
1. and
3. require
and
operations respectively.
2. can be performed efficiently
using fast convolution.
is required only for
, so this linear convolution can be implemented with
FFTs.
Wrap
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".