0.4 The dft as convolution or filtering  (Page 2/4)

where the square matrix should contain the terms of $W^{nk}$ but for clarity, only the exponents $nk$ are shown. Separating the $x\left(0\right)$ term, applying the mapping of [link] , and using the primitive roots $r=2$ (and $r^{-1}=3$ ) gives

and

which can be seen to be a reordering of the structure in [link] . This is in the form of cyclic convolution as indicated in [link] . Rader first showed this in 1968 [link] , stating that a prime length-N DFT could be converted into a length-(N-1)cyclic convolution of a permutation of the data with a permutation of the W's. He also stated that a slightly more complicatedversion of the same idea would work for a DFT with a length equal to an odd prime to a power. The details of that theory can be foundin [link] , [link] .

Until 1976, this conversion approach received little attention since it seemed to offer few advantages. It hasspecialized applications in calculating the DFT if the cyclic convolution is done by distributed arithmetic table look-up [link] or by use of number theoretic transforms [link] , [link] , [link] . It and the Goertzel algorithm [link] , [link] are efficient when only a few DFT values need to be calculated. It may also have advantages when used with pipelined orvector hardware designed for fast inner products. One example is the TMS320 signal processing microprocessor which is pipelined for innerproducts. The general use of this scheme emerged when new fast cyclic convolution algorithms were developed by Winograd [link] .

The chirp z-transform (or bluestein's algorithm)

The DFT of $x\left(n\right)$ evaluates the Z-transform of $x\left(n\right)$ on $N$ equally spaced points on the unit circle in the $z$ plane. Using a nonlinear change of variables, one can create a structure which is equivalentto modulation and filtering $x\left(n\right)$ by a “chirp" signal. [link] , [link] , [link] , [link] , [link] , [link] .

The mathematical identity ${(k-n)}^2=k^2-2kn+n^2$ gives

which substituted into the definition of the DFT in Multidimensional Index Mapping: Equation 1 gives

This equation can be interpreted as first multiplying (modulating) the data $x\left(n\right)$ by a chirp sequence ( $W^{n^2/2}$ , then convolving (filtering) it, then finally multiplying the filter output by the chirp sequence to give the DFT.

Define the chirp sequence or signal as $h\left(n\right)=W^{n^2/2}$ which is called a chirp because the squared exponent gives a sinusoid with changing frequency.Using this definition, [link] becomes

We know that convolution can be carried out by multiplying the DFTs of the signals, here we see that evaluation of the DFT can be carried out by convolution. Indeed,the convolution represented by $*$ in [link] can be carried out by DFTs (actually FFTs) of a larger length. This allows a prime length DFT to be calculated by avery efficient length- $2^M$ FFT. This becomes practical for large $N$ when a particular non-composite (or $N$ with few factors) length is required.

As developed here, the chirp z-transform evaluates the z-transform at equally spaced points on the unit circle. A slight modification allows evaluation on a spiral andin segments [link] , [link] and allows savings with only some input values are nonzero or when only some output values are needed. The story of the development of thistransform is given in [link] .