1
$\begingroup$

I am debugging an FFT. My FFT uses complex numbers in polar form, $(r,\theta)$.

I am trying to establish that it works, with a unit test. My real values are all correct, after a polynomial multiplication...

However, I pad out my polynomials to a power of two with complex zeros, and when the multiplication is complete, I have random angle values in the polar form of the complex numbers.

For instance, I multiply the following polynomials, listed in standard form by their coefficients:

$$ A = \lbrace1,2,3\rbrace\\ B = \lbrace4,5,6\rbrace\\ $$

And I am expecting the answer to be: $$ C = \lbrace (4,0),(13,0),(28,0),(27,0),(18,0),(0,0),(0,0),(0,0)\rbrace $$

However, my FFT returns this exactly (ignoring floating point errors), except the last three terms are:

$$ C = \lbrace \ldots,(0,4.518),(0,0.4769),(0,2.2877)\rbrace $$


My question is whether these angle values in the extra terms are expected, or whether this is a sign of something going wrong in my FFT code?

(this is tricky for me, because it seems like everything is calculating correctly; and shouldn't it not work at all in a d&c if something is wrong?)

$\endgroup$
  • $\begingroup$ @evil for some reason, it is claiming I am trying to create a new tag. Not sure whether I should delete the question or not.... $\endgroup$ – donlan May 25 '17 at 2:33
  • 1
    $\begingroup$ You are right, something is odd. The system suggests fft but then tells it is new one. Anyway, the core of your question is interesting one. I wouldn't just take a word for it. $\endgroup$ – Evil May 25 '17 at 2:42
  • $\begingroup$ @evil ok, thanks man--will wait and see. $\endgroup$ – donlan May 25 '17 at 2:44
2
$\begingroup$

Zero-padding is used to compute longer FFT, in your case the signal is padded to be power of 2. In fact, there is no need to do so, there are FFT available using different lengths (also prime ones).

The zero-padding does not introduce new data, does not change sampling frequency of the original signal, it just interpolates the values. In your example there are 5 points, padding them to 8 introduces additional result bins that are closer to each other - this makes particular frequency bin shift, which is stored in the phase component of the result.

So the most probably your FFT is fine, just the test changes the distance between frequency bins, but this step is not included in reading phase, so the test is faulty.

$\endgroup$
2
$\begingroup$

In polar coordinates, $(0,x) = (0,y)$ for any $x$ and $y$, so there's no issue. You've simply used a representation that has multiple representations of the complex number $0 + 0i$.

Going beyond your question a bit, I'd probably test (additionally) with randomized testing of properties of the Fourier transform such as linearity, Parseval's theorem, and the shift theorem. Technically, linearity, the shift theorem, and the impulse response would completely characterize the Fourier transform.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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