projectus.freehost7.com:UG and PG level projects,mini projects and many more here ...

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 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.

[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 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:

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.