I am attempting to implement a chirp z algorithm to handle random sized DFTs, and I can not seem to obtain any meaningful results. I have gone over several write ups and "think" I have a handle on what a chirp transform should do, but I wanted to ask here to double check and make sure my understanding of the process is sound. In pseudo code, here is the process I am applying.
*function Chirpz(input x[n], discrete values such that n = 0, 1, ... N - 1)* *// To keep numbers in perspective I will assume N = 5.* M = The minimum power of 2 which is greater than 2N - 1 // In our case of N=5 => M=16. Pad x[n] with 0s so that it has a total length of M. // Create y[n] by performing the following: value = 1 - N<br> for n = 0 to n = 2N - 1<br> y[n] = e^i(PI / N * value * value) // W^((k - n)^2 / 2) value = value + 1<br> next n Pad y[n] with 0s so that it has a total length of M. // Multiply x[n] by W^(-n^2 / 2): for n = 0 to n = N x[n] = x[n] * e^-i(PI / N * n * n) Perform FFT(x[n]) which has M elements using a radix-2 FFT algorithm Perform FFT(y[n]) which has M elements using a radix-2 FFT algorithm // With the results of the FFTs now in x[n] and y[n], multiply each value: for n = 0 to n = M x[n] = x[n] * y[n] Perform IFFT(x[n]) which has M elements using radix-2 FFT algorithm // Multiply x[n] by W^(-k^2 / 2) for n = 0 to n = M x[n] = x[n] * e^-i(PI / N * n * n) // Now the first N elements in x[n] "should" have the result X[k] = x[n] for n from 0 to N - 1 return X[k]
But my results don't match anything near what is returned by fftw3 given the same input. In fact my results look to be garbage. As I am pretty new to this, I just want to make sure my understanding of the algorithm is sound.