**
Derivation of CZT:**

Along the contour of (1.7), (1.3)

** **k=0,1,2,3,……………..N-1,

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

** **(1.12)

using equation (1.7) we can define ** **as

(1.13)

Where K=0,1,2,………….M-1

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

n=0,1,2,….,N-1; (1.14)

2) Convolving with the sequence define as

(1.15)

To give a sequence

k=0,1,2,3……M-1. (1.16)

3) Multiplying by to give

k=1,2,3…….M-1

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 1^{st} and 3^{rd} step
for different input sequences and circular convolution for one times for 2^{nd}
step and how Circular Convolution process and Discrete Fourier Transformation
is done will describe in the chapter (2) and chapter(3) respectively.

[1] DFT of two sequence and as value of A=1 for N=M and the result will be.

[2] Circular convolution between and and the output of circular convolution is.

[3] 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

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 X_{n} and seek M samples of X_{k} 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 y_{n} from x_{n} 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 V_{r}, r=0,1,…,L-1.

6) Multiply
V_{r }and point by point, giving G_{r}:

r=0,1,…,L-1.

7) Compute the L point IDFT, of.

8) Multiply by to give the desired

, k=0,1,2…,M-1.

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.