2
$\begingroup$

I'm currently trying to do some Fourier transformations, or at least trying to understand them. The only thing I'm worried about is the complex part of the function. All I have is some basic, self thought, understanding about complex numbers.

As far as I'm concerned, a complex number exists of a real part and a complex part. In the following DFT it seems it has no real part. Is that correct?

alt text

I think we can simplify it to the following, since the others are just modifiers.

$e^{-i}$

But for some reason, im not getting the good value's. Perhaps i'm doing something wrong, but im not quite sure.

Edit:

I just realised this may be a bit vague, but my questions are

  1. Does the function F(k,l) return a complex number, with no real part.
  2. Is there a special rule about $e^{-i}$

Edit2:

Okay, I'm sorry for asking these basic questions, this is all way beyond the math I've learned at school xD. But I understand most of the DFT now. Only there's one thing I don't understand and that:

  1. What does the $F(k,l)$ part of the function define.
  • 0
    Okay, since I don't see how that practically works. Lets say I have a matrix with 4 entries in it. So I have F(0,0), F(1,0), F(0,1) and F(1,1). For every pixel in the matrix, I'd have to calculate the DFT. Doesn't it give it a complexity of $O(N^4)$ instead of $O(N^2)$2010-12-03

1 Answers 1

4

Your sum has both real and imaginary parts. Because

$e^{ix}= \cos(x) + i \sin(x) \; .$

Is $f(a,b)$ in your formula a real number? Then the transform has real and imaginary components in general. (For certain choices of $f(a,b)$, you can have purely real numbers.)

If you mean $e^{-i}$, then use the formula I provided you and you should be able to compute it.

  • 1
    In fact, quite a number of well-tuned FFT programs internally cache a bunch of frequently-used trig function values in an array, since array accesses are usually cheaper than computing trig functions *ab initio*.2010-12-03