Chirp z algorithm clarification

Question

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.

Thanks.

Answer 1

Ok, after some head scratching and re-re-re-reading I realize what I was missing. When creating the chirp signal used in convolution, the values of (k - n) which result in a negative need to be wrapped around and placed at the end of the signal rather than in the beginning.

So, replacing:

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

With the following:

// Create y[n] by performing the following:

// Take care of values of k - n which are greater than zero.
for n = 0 to N - 1
y[n] = e^i(PI / N * n * n)

// Add the zero padding.
for n = N to M - N
y[n] = 0

// Now place the negative values at the end of the signal
for n = 1 - N to -1
y[M + n] = e^i(PI / N * n * n)

Yields the expected results.