Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

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.

share|improve this question
1  
I asked a very similar question here only a couple days ago. Take a look. –  Mohammad Feb 22 '13 at 14:40
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.