# Discrete fourier tranforms -help

1. Apr 13, 2005

### rainbowings

discrete fourier tranforms -help!!

How does one write the orthogonality condition for discrete fourier tranforms - alternatley, how does one express the kronecker delta as a sum over exp(i k x) kind of thing. One last thing - what is the mormalization constant in front of the sum (analogous to the 1/2 pi for the fourier resolution of the dirac delta function)?

2. Apr 13, 2005

### rbj

i would suggest posting to comp.dsp your question. i can maybe deal with it here if you could be a bit more specific.

do you want to know why the basis functions are orthogonal to each other? is that your first question?

the kronecker delta is not periodic, so a sum of exp(i k x) would have to be an integral instead. the inverse DFT of a sequence all having 1 for coefficients is a repeated delta, but i wouldn't call that a kronecker delta.

usually the forward DFT has not normalization constant in front and the inverse DFT has a 1/N in front. but that could be switched, or you could have 1/sqrt(N) in front of both.

3. Apr 13, 2005

### Hurkyl

Staff Emeritus
Are you just asking for the DFT formula?

$$\hat{f}(s) = \frac{1}{N} \sum_{t=0}^{N-1} \omega^{-st} f(t)$$

Or maybe it's +st, not -st, I forget.

&omega; is your favorite (primitive) N-th root of unity. exp(2 &pi; i / N) is usually a good choice.

4. Apr 13, 2005

### rainbowings

Thanks rbj and Hurkyl. Two more questions - what does DFT stand for and how would i derive this? what happens if "s" is a vector?

5. Apr 13, 2005

### Hurkyl

Staff Emeritus
Then the sum is over the whole vector space (change the normalization appropriately), and the exponent is a dot product.

(P.S. I think I might have made an assumption in that formula...)

6. Apr 13, 2005

### rbj

well it's not exactly the question(s) you started with. and it looks like you have three.

that's kinda funny when i look at the title you gave the thread.

it's in textbooks. it might be a little much to derive here. there's a hint below.

i don't get where "s" comes from at all. using the language of Electrical Engineers (who are the folks i think that deal with the DFT the most), the most common expression of the DFT:

DFT:

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N}$$

inverse DFT:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N}$$

[ i deleted some text because it made the math rendering break. ] ... essentially the DFT maps a periodic sequence of period N to another periodic sequence of period N.

you can define one equation arbitrarily and, given that, prove the other is true by noting

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = 0$$

when $k \ne m$ (both are integers) and

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = N$$

when $k = m$.

the rest is plug and chug.

r b-j

Last edited: Apr 14, 2005
7. Apr 13, 2005

### rbj

boy, i dunno what wrong with this thing, but i can't get the tex to come out right at all, so i am giving up trying. hey PF folks, your tex rendering is a little bit schitz.

r b-j

8. Apr 14, 2005

### rainbowings

thanx r-b-j ... that helped. and yes, i thought of density functional theory but not the title of my own thread when i saw DFT - sometimes one does overlook the obvious!