Derivation of CZT:
Along the contour of (1.7), (1.3)
which, at first appearance, seems to require NM complex multiplications and additions, as we have already observed. But, let us use the ingenious substitution, due to Bluestein
using equation (1.7) we can define as
but, in fact, (1.13) can be thought of as a three-step process consisting of:
1) Forming a new sequence by weighting the according to the equation
2) Convolving with the sequence define as
To give a sequence
3) Multiplying by to give
Fig. 3. Block diagram for computing values of the z-transform using the CZT algorithm.
Form the above block diagram we can see that we have to do DFT for two times for 1st and 3rd step for different input sequences and circular convolution for one times for 2nd step and how Circular Convolution process and Discrete Fourier Transformation is done will describe in the chapter (2) and chapter(3) respectively.
 DFT of two sequence and as value of A=1 for N=M and the result will be.
 Circular convolution between and and the output of circular convolution is.
 Again DFT between the output of circular convolution and and the final result is which is the result of chirp Z-transformation (CZT).
The three-step process is illustrated in Fig. 3. Steps 1 and 3 require N and M multiplications, respectively, and step 2 is a convolution which may be computed by the high-speed technique, which described in chapter (2). Step 2 is the major part of the computational effort and requires a time roughly proportional to (N+M) log (N+M). Bluestein employed the substitution of (1.12) to convert a DFT to a convolution as in Fig. 3. The linear system to which the convolution is equivalent can be called a chirp filter which is, in fact, also sometimes used to resolve a spectrum. Bluestein showed that for N a perfect square, the chirp filter could b
Synthesized recursively with multipliers and the computationo f a DFT could then be proportional to N3/2.
The flexibility and speed of the CZT algorithm are related to the flexibility and speed of the method of high speed convolution using the FFT. The reader should recall that the product of the DFT's of two sequences is the DFT of the circular convolution of the two sequences and, therefore, a circular convolution is computable as two DFT's, the multiplication of two arrays of complex numbers, and an inverse discrete Fourier transform (IDFT), which can also be computed by the FFT. Ordinary convolutions can be computed as circular convolutions by appending zeroes to the end of one or both sequences so that the correct numerical answers for the ordinary convolution can result from a circular convolution. We shall now summarized the details of the CZT algorithm on the assumption that an already existing FFT program (or special-purpose machine)is available to compute DFT’s and IDFT’
Begin with a waveform in the form of N samples Xn and seek M samples of Xk where A ad W have also been chosen.
1) Choose L, the smallest integer greater than or equal to N+M-1 which is also compatible with our high-speed FFT program. For most users this will mean L is a power of two. Not w that while many FFT programs will work for arbitrary L; they are not equally efficient for all L. At the very least, L should be highly composite.
2) From an L point sequence yn from xn by
3) Compute the L point DFT of by the FFT. Call this , r=0,1,…,L-1.
4) Define an L point sequence by the relation
Of course, if L is exactly equal to M+N-1, the region in which is arbitrary will not exist. If the region exists an obvious possibility is to increase m, the desired number of point of the Z-transform we compute, until the region does not exist.
Note the could be cut into two with a cut between n=M-1 and n=L-N+1 and if the two pieces were abutted together differently, the resulting sequence .This is illustrated in fig 4. The sequence is defined the way it is in order to force the circular convolution to give us the desired numerical results of an ordinary convolution.
5) Compute the DFT of and call it Vr, r=0,1,…,L-1.
6) Multiply Vr and point by point, giving Gr:
7) Compute the L point IDFT, of.
8) Multiply by to give the desired
The for are discarded.
Fig. 4 represents typical waveforms (magnitude shown, phase omitted) involved in each step of the process.
Fig.4. Schematic representation of the various sequence involved in the CZT algorithm.(a)The input sequence with N values.(b)The weighted input sequence =.(c) The DFT of .(d) The values of the indefinite sequence.(e) The sequence formed appropriately from sequence of .(f)The DFT of .(g)The product =..(h) The IDFT of .(i) The desired M values of the z-Transform.